Тема 2. Линейное программирование

ЗЛП графическим методом
3. Основы симплекс-метода
4. Транспортная задача

область решений (ОДР), соответствующая ограничениям
2. Строится вектор–градиент линейной формы

с координатами



3. Строится прямая , перпендикулярная вектору-градиенту. Прямая «передвигается» в направлении этого вектора в случае максимизации (в направлении, противоположном вектору - в случае минимизации) до тех пор, пока не покинет пределов многоугольной области.
4. Определяются координаты предельной точки.
Подставляются значения координат в выражение целевой функции, тем самым находятся ее экстремальные значения.

 300
х1+х2  150
х1,2  0

1 этап.
х1+ 3х2

=300

(0;100) и (300;0).

этап. Строится прямая , перпендикулярная вектору-градиенту.

Прямая «передвигается» до момента покидания ОДР.
Предельная точка – точка В.

А

В

С

= 150

х1+х2 = 150

х1 = 75 х2

= 75


Т.к. координаты точки В равны х1 = 75 и х2 = 75, то максимум ЦФ равен 375.


f = 2х1+3х2 = 2·75 + 3·75 = 375

животных использует два вида корма. В дневном рационе животного должно

содержаться не менее 6 единиц питательного вещества А и не менее 12 единиц питательного вещества В.
Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальными? Использовать данные таблицы:

корма 1 вида
х2 - кол-во корма 2 вида
F(Х)= 0,2

х1 + 0,3х2 → min
2 х1 + х2 ≥ 6
2 х1 + 4х2 ≥ 12
х1 , х2 ≥ 0

2 х1 + х2 ≥ 6
2 х1 + 4х2

≥ 12
х1 , х2 ≥ 0

2 х1 + х2 = 6

2 х1 + 4х2 ≥ 12

1

2

3

4

5

6

1

2

3

4

5

6

0

х1

х2

2 х1 + х2 ≥ 6
2 х1 + 4х2

≥ 12
х1 , х2 ≥ 0

Предельная точка: В(2;2)
min F(X) = 0,2 *2 + 0,3*2 = 1

1

2

3

4

5

6

1

2

3

4

5

6

0

х1

х2

(4;6)

В

А

С

пуста и ЗЛП решений не имеет.


х1

+ 2х2 = -10

(0;-5) и (10;0)

направлении оптимизации целевой функции. Задача не имеет решений.

вершинах многоугольника,
в симплексном методе оптимум ищется в вершинах n-мерного

многогранника, называемого симплексом.

необходимой, так называемой базисной, форме.
2. Находится так называемое опорное решение,

служащее «точкой отсчета».
3. Последовательно перебираются вершины симплекса.
Если в данной точке значение критерия больше (или меньше) предыдущего, то процесс продолжается.
Когда значение критерия уже нельзя улучшить, тогда решение найдено.

может вложить свой капитал в акции автомобильного концерна А и

строительного предприятия В.
Чтобы уменьшить риск, акций А должно быть приобретено по крайней мере в два раза больше, чем акций В, причем последних можно купить не более чем на 100 тыс. ден. ед.
Дивиденды по акциям А составляют 8% в год, по акциям В – 10%. Какую максимальную прибыль можно получить в первый год?
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум и почему?

концерна А
х2 – тыс. ден. ед. , вложенных в акции

предприятия В
F (х) = 0,08 х1+0,10 х2 → max - общая прибыль
x1+ х2 ≤ 300
х1- 2х2 ≥ 0
х2 ≤ 100
х1, х2 ≥ 0

акции концерна А
х2 – тыс. ден. ед. , вложенных в

акции предприятия В
F (х) = 0,08 х1+0,10 х2 → max - общая прибыль
x1+ х2 ≤ 300
х1- 2х2 ≥ 0
х2 ≤ 100
х1, х2 ≥ 0

ед., может вложить свой капитал в акции автомобильного концерна А

и строительного предприятия В.
Чтобы уменьшить риск, акций А должно быть приобретено по крайней мере в два раза больше, чем акций В,
причем последних можно купить не более чем на 100 тыс. ден. ед.
Дивиденды по акциям А составляют 8% в год, по акциям В – 10%.
Какую максимальную прибыль можно получить в первый год?
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на минимум и почему?

и улучшенный.
В обычный набор входит 3 кг азотных,
4

кг фосфорных и 1 кг калийных удобрений, а в улучшенный – 2 кг азотных, 6 кг фосфорных и 3 кг калийных удобрений.
Известно, что для некоторого газона требуется по меньшей мере 10 кг азотных, 20 кг фосфорных и 7 кг калийных удобрений.
Обычный набор стоит 3 ден. ед., а улучшенный – 4 ден. ед.
Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

планирует посеять кукурузу и сою.
Сев и уборка кукурузы требует

на каждый гектар 200 ден. ед. затрат, а сои – 100 ден. ед.
На покрытие расходов, связанных с севом и уборкой, фермер получил ссуду в 60 тыс. ден. ед..
Каждый гектар, засеянный кукурузой, принесет 30 центнеров, а каждый гектар, засеянный соей – 60 центнеров.
Фермер заключил договор на продажу, по которому каждый центнер кукурузы принесет ему 3 ден. ед., а каждый центнер сои – 6 ден. ед.
Однако, согласно этому договору, фермер обязан хранить убранное зерно в течение нескольких месяцев на складе, максимальная вместимость которого равна 21 тыс. центнеров.
Фермеру хотелось бы знать, сколько гектар нужно засеять каждой из этих культур, чтобы получить максимальную прибыль.

(Е) работ) поступает в оптовую продажу. Для производства красок используются

два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн, соответственно.
Расходы продуктов А и В на 1 т соответствующих красок приведены в таблице.

 


Изучение рынка сбыта показало, что суточный спрос на краску I никогда не превышает спроса на краску Е более чем на 1 т. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т в сутки. Оптовые цены одной тонны красок равны: 3000 ден. ед. для краски Е и 2000 ден. ед. для краски I.
Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

портфелю.
Клиент хочет вложить средства (не более 25000$) в два

наименования акций крупных предприятий в составе холдинга «Дикси».
Анализируются акции «Дикси –Е» и «Дикси –В». Цены на акции: «Дикси –Е» - 5$ за акцию; «Дикси –В» - 3$ за акцию.
Клиент уточнил, что он хочет приобрести максимум 6000 акций обоих наименований, при этом акций одного из наименований должно быть не более 5000 штук.
По оценкам «АВС» прибыль от инвестиций в эти две акции в следующем году составит: «Дикси –Е» - 1,1$; «Дикси –В» - 0,9$.
Задача консультанта состоит в том, чтобы выдать клиенту рекомендации по оптимизации прибыли от инвестиций.

типа деталей Х и Y.
Фонд рабочего времени равен 4000

чел.-ч в неделю.
Для производства одной детали типа Х требуется 1 чел./ч, а для производства одной детали типа Y – 2 чел./ч.
Производственные мощности завода позволяют выпускать максимум 2250 деталей Х и 1750 деталей Y в неделю.
Каждая деталь типа Х требует 2 кг металлических стержней и 5 кг листового металла, а для производства одной детали типа Y необходимо 5 кг металлических стержней и 2 кг листового металла.
Уровень запасов каждого вида металла составляет 10000 кг в неделю.
Еженедельно завод поставляет 600 деталей типа Х своему постоянному заказчику.
По профсоюзному соглашению общее число производимых в течение одной недели деталей должно составлять не менее 1500 штук.
Сколько деталей каждого типа следует производить, чтобы максимизировать общий доход за неделю, если доход от производства одной детали типа Х составляет 30 ден. ед., а от производства одной детали типа Y – 40 ден. ед.?

вещества (витамины) S1 S2 и S3. Содержание числа единиц питательных

веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в таблице:
 







Стоимость 1 кг корма I и II соответственно равна 4 и 6 ден. ед.
Необходимо составить дневной рацион, имеющий минимальную стоимость.

ресурсов. Норма расхода ресурсов на производство единицы продукции, общий объем

каждого ресурса заданы в таблице
 







Прибыль от реализации одной единицы продукции первого вида составляет 2 ден. ед., второго вида – 3 ден. ед.
Задача состоит в формировании производственной программы выпуска продукции, обеспечивающей максимальную прибыль от ее реализации.

«Тоник».
Однако объем производства ограничен количеством основного ингредиента и производственной

мощностью имеющегося оборудования.
Для производства 1 л «Лимонада» требуется 0,02 ч работы оборудования, а для производства 1 л «Тоника» – 0,04 ч.
Расход специального ингредиента составляет 0,01 кг и 0,04 кг на 1 л «Лимонада» и «Тоника» соответственно.
Ежедневно в распоряжении фирмы имеется 24 ч времени работы оборудования и 16 кг специального ингредиента.
Прибыль фирмы составляет 0,10 ден. ед. за 1 л «Лимонада» и 0,30 ден. ед. за 1 л «Тоника».
Сколько продукции каждого вида следует производить ежедневно, если цель фирмы состоит в максимизации ежедневной прибыли?