Методы оптимальных решений (стр. 7 )

Пример 4. Составить математическую модель, решить полученную задачу ЛП двумя способами: симплекс-методом и графически.

Пусть имеется три вида сырья в количествах 45 ед., 19 ед. и 10 ед. Из этого сырья нужно изготовить продукцию двух видов. Задан расход сырья каждого вида на производство единицы каждой продукции и прибыль от единицы продукции. Эти данные содержатся в таблице (25). Требуется найти такой план выпуска продукции из имеющегося сырья, при котором суммарная прибыль будет наибольшей.

Прод. Сырьё	1 пр.	2 пр.	Запасы сырья
1	5	9	45
2	3	3	19
3	2	1	10
Прибыль	5	6

Обозначим через х1 количество единиц продукции первого вида, через х2 - второго вида. Тогда на выпуск этой продукции будет израсходовано 5х1+9х2 ед. сырья первого вида, 3х1+ 3х2 ед. Сырья второго вида и 2х1 + х2 - третьего. Суммарная прибыль составит 5х1 + 6х2 денежных единиц. Так как нельзя израсходовать сырья больше, чем имеется, а суммарная прибыль зависит от количества выпущенной продукции, то получим следу. Математическую модель данной задачи.

Математическая модель.

5х1 + 9х2 £ 45

3х1 + 3х2 £

2х1 + х2

х1 ³ 0 х2 ³ 0 , (27)

¦(Х) = 5х1 + 6х2 ¾ max. (28)

Задача (является общей, так как система ограничений (26) состоит из неравенств. Введя дополнительные неизвестные х3 ³ 0, х4 ³ 0, х5 ³ 0 и прибавив их к левым частям неравенств (26), получим основную задачу вида:

5х1 + 9х2 + х3 = 45,

3х1 + 3х2 + х4 =19, (29)

2х1 + х2 + х5 =10,

xj ³ 0 (j = 1¸5) (30)

¦(X) = 5х1 + 6х2 + 0 × х3 + 0 × х4 + 0 × х5 ¾ max. (31)

Основная задача (является канонической и легко решается симплекс-методом. Предлагается решить ее самостоятельно.

Приведем только ответ, а именно Х *= (3, 10/3, 0, 0, 2/3) - оптимальный план основной задачи (, ¦(Х*) = 35 - максимальное значение целевой функции - (31).

Отбросив значения дополнительных неизвестных, получим оптимальный план Х* (3,10/3) общей задачи (, причем максимальное значение целевой функции ¦(Х*) = 35 останется тем же.

Таким образом, для того, чтобы получить максимальную прибыль, равную 35 ед., следует выпустить 3 ед. продукции первого вида и 10/3 » 3,3 ед. продукции второго вида. Значения дополнительных неизвестных х*3 = х*4 = 0, х*5= 2/3 показывают, что сырье первого и второго вида используется полностью, третьего вида - не полностью.

Общая задача (содержит два неизвестных и поэтому может быть решена графически.

3. Графическое решение задачи.

Введем систему декартовых координат на плоскости х1Ох2 и построим множество планов задачи (Каждое линейное неравенство системы (26) определяет полуплоскость по одну сторону от граничной прямой, заданной соответствующим равенством. Множество планов задачи есть пересечение полуплоскостей, представляющее собой выпуклый многоугольник или выпуклую незамкнутую многоугольную область.

Построим каждую из граничных прямых по двум точкам (рис. 1).

(1) 5х1 + 9х2 = 45: (9, 0), (0,5);

(2) 3х1 + 3х2 = 19: (6,3; 0), (0;6,3);

(3) 2х1 + х2 = 10: (5, 0), (0,10).

Направление полуплоскости можно определить по одной точке, принадлежащей ей, например, точке О (0, 0). Если граничная прямая проходит через начало координат, то удобно проверять какую-либо точку, лежащую на одной из осей. В нашем случае при х1= 0 и х2= 0 неравенства системы (26) превращаются в верные числовые неравенства: 0 < 45, 0 < 19, 0 < 10. Следовательно, все три полуплоскости содержат точку О (0,0), то есть обращены к на чалу координат. На рис.1 это показано стрелками около каждой граничной прямой.

Так как х1 ³ 0, х2 ³ 0, то множество планов задачи (представляет собой общую часть трех полуплоскостей, попавшую в первую координатную четверть, то есть выпуклый пятиугольника (на рис. 1 он закрашен). Целевую функцию (Х) = 5х1 + 6х2 можно изобразить на плоскости в виде сетки параллельных прямых. Однако, достаточно построить одну прямую, соответствующую какому-либо значению функции, например, ¦(Х) = 18. Эта прямая пройдет через точки (3,6; О) и (0, 3). На рис. 1 она показана пунктиром. Далее передвигаем эту прямую параллельно самой себе в направлении от начала координат (в этом направлении целевая функция возрастает), пока она не встретит последнюю на своем пути точку области планов. Ее координаты найдем из системы уравнений прямых (1) и (2), пересекающихся в этой точке:

5х1 + 9х2 = 45,

3х1 + 3х2 =

Х2

10

6,3

5 X*= (3,10/3)

¦max

0 ¦=19 (1) х1

Рис. 1

Решив систему уравнений (32), получим х1 = 3, х2 =10/3 . Значит,

Х* = (3, 10/3) — оптимальный план задачи (

¦(Х*) = 5 × 3 + 6 × 10/3 = 35 — максимальное значение целевой функции (28).

Как видим, ответы, полученные симплекс-методом и графически, оказались одинаковыми.

3. Симметричные двойственные задачи.

Парой симметричных, двойственных задач называются две, тесно связанные между собой задачи ЛП, которые удобно записать схематически в виде (33) (см. ниже). Задача ЛП, в которой целевая функция максимизируется, а все неравенства “типа £“, называется стандартной задачей максимизации; если целевая функция минимизируется, а все неравенства “типа ³ ” - стандартной задачей минимизации. Пара симметричных двойственных задач состоит из стандартной задачи максимизации и стандартной задачи минимизации, причем эти задачи обладают рядом особенностей, которые хорошо видны в схеме (33) и позволяют сформулировать правила составления двойственных задач.

Задача 1. Задача 2.

Max ¦ (Х) = с1х1 + с2х2 + с3х3 Min g(Y) = b1y1 + b2y2

при условиях: х ³ 0, х ³ 0, х ³ 0. при условиях: y1 ³ 0, y2 ³

а11х1 + а12х2 + а13х3 £ b1, a11y1 + a21y2 ³ c1,

a21x1 + a22x2 + a23x3 £ b2/ a12y1 + a22y2 ³ c2,

a13y1 + a23y2 ³ c3.

Правила составления пары симметричных двойственных задач.

1. Одна из задач является стандартной задачей максимизации, другая стандартной задачей минимизации.

2. Количество неизвестных в одной из задач равно количеству основных ограничений в другой задаче.

3. Матрица коэффициентов при неизвестных в неравенствах одной задачи получается транспонированием матрицы коэффициентов другой задачи.

4. Свободные члены неравенств одной задачи совпадают с коэффициентами целевой функции другой задачи.

Если решить одну из двойственных задач (33), то на основании теорем двойственности можно сделать вывод о существовании или отсутствии решения другой задачи. При этом возможны три случая.

Три случая решения пары двойственных задач.

Результат решения задачи 1.

1. Задача 1 имеет оптимальный план.

2. В задаче 1 планы есть, но целевая функция не ограничена сверху на множестве планов, значит, оптимального плана не существует.

3. В задаче 1 вообще нет Планов, а значит, нет и оптимального плана.

Выводы для задачи 2

1. Задача 2 также имеет оптимальный план.

2. В задаче 2 вообще нет планов, а значит, нет и оптимального плана.

3. В задаче 2 или нет планов, или целевая функция не ограничена снизу на множестве планов, но в обоих случаях оптимального плана не существует.

Если же решена задача 2, то аналогичные выводы можно сделать для двойственной ей задачи.

При решении одной из двойственных задач симплекс-методом в тех же симплексных таблицах одновременно преобразовывается и другая задача. Если решенная задача имеет оптимальный план, который содержится в столбце свободных членов последней симплексной таблицы, то и двойственная задача имеет оптимальный план, и он содержится в индексной строке последней симплексной таблицы решенной задачи.

Пример 5. Для задачи ЛП вида

2х1 +х2 £ 5,

х1 - х2 ³ 1, (34)

х1 + 3х2 £ 10,

х1 ³ 0, х2 ³ 0, (35)

¦(Х) = 5х1 - 8х2 ¾ min (36)

составить двойственную. Решив одну из двойственных задач симплекс-методом, получить ответы для обеих.

Задача (не является стандартной задачей минимизации, так как целевая функция минимизируется, а среди неравенств (34) есть неравенства «типа £». Умножив обе части каждого такого неравенства на -1, получим стандартную задачу минимизации. Составим для нее двойственную и полученную пару двойственных задач запишем по принятой выше схеме.

Задача 1 Задача 2

Min ¦(Х) = 5х1 - 8х2 Max g (Y) = -5у1 + у2 -10у3