Задача, двойственная задаче о диете
Проиллюстрируем выполнение теорем двойственности на примере задачи о диете (см. раздел 1.3.1).
Построим задачу, двойственную к задаче о составлении рациона, решение которой было найдено в разделе 4.2 (в которой минимальное содержание белка в рационе должно составлять 44 г, а не 110 г).
Для этого вначале необходимо добиться, чтобы во всех неравенствах прямой задачи стоял знак ³ (так как задача на минимум), т.е. умножить обе части второго и четвертого ограничения на -1:
min 4х1 + 15х2 + 40х3
380х1 + х2 + 2х3 ³ 4
-380х1 - х2 - 2х3 ³ -6
90х2 + 50х3 ³ 44
-20х2 - 80х3 ³ -25
х1 + х2 + х3 = 0,5
х1-3 ³ 0
Построим задачу, двойственную к данной*:
max 4y1 – 6y2 + 44y3 – 25y4 + 0,5у5
380y1 – 380y2 + у5 £ 4
y1 – y2 + 90y3 – 20y4 + у5 £ 15
2y1 – 2y2 + 50y3 – 80y4 + у5 £ 40
у1-4 ³ 0
Чтобы решить ее симплекс-методом, приведем ее к канонической форме. Для этого нужно ввести три дополнительных переменных. Кроме того, поскольку переменная у5 не ограничена по знаку (т.к. она соответствует уравнению прямой задачи), следует заменить ее на разность двух неотрицательных переменных (у5 = у5`- у5``):
max 4y1 – 6y2 + 44y3 – 25y4 + 0,5у5` – 0,5у5``
380y1 – 380y2 + у5` – у5``+ y6 = 4
y1 – y2 + 90y3 – 20y4 + у5` – у5``+ y7 = 15
2y1 – 2y2 + 50y3 – 80y4 + у5` – у5``+ y8 = 40
у1-4, 6-8, у5`, у5``³ 0
В этой задаче имеется готовый базис, и можно сразу же решить ее симплекс-методом, не используя метод искусственного базиса*. Решение приведено в таблице 20.
Таблица 20 – Решение двойственной задачи
Дата добавления: 2015-01-18 | Просмотры: 657 | Нарушение авторских прав
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|