АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Задача, двойственная задаче о диете

Проиллюстрируем выполнение теорем двойственности на примере задачи о диете (см. раздел 1.3.1).

Построим задачу, двойственную к задаче о составлении рациона, решение которой было найдено в разделе 4.2 (в которой минимальное содержание белка в рационе должно составлять 44 г, а не 110 г).

Для этого вначале необходимо добиться, чтобы во всех неравенствах прямой задачи стоял знак ³ (так как задача на минимум), т.е. умножить обе части второго и четвертого ограничения на -1:

min 4х₁ + 15х₂ + 40х₃

380х₁ + х₂ + 2х₃ ³ 4

-380х₁ - х₂ - 2х₃ ³ -6

90х₂ + 50х₃ ³ 44

-20х₂ - 80х₃ ³ -25

х₁ + х₂ + х₃ = 0,5

х_1-3 ³ 0

Построим задачу, двойственную к данной*:

max 4y₁ – 6y₂ + 44y₃ – 25y₄ + 0,5у₅

380y₁ – 380y₂ + у₅ £ 4

y₁ – y₂ + 90y₃ – 20y₄ + у₅ £ 15

2y₁ – 2y₂ + 50y₃ – 80y₄ + у₅ £ 40

у_1-4 ³ 0

Чтобы решить ее симплекс-методом, приведем ее к канонической форме. Для этого нужно ввести три дополнительных переменных. Кроме того, поскольку переменная у₅ не ограничена по знаку (т.к. она соответствует уравнению прямой задачи), следует заменить ее на разность двух неотрицательных переменных (у₅ = у₅`- у₅``):

max 4y₁ – 6y₂ + 44y₃ – 25y₄ + 0,5у₅` – 0,5у₅``

380y₁ – 380y₂ + у₅` – у₅``+ y₆ = 4

y₁ – y₂ + 90y₃ – 20y₄ + у₅` – у₅``+ y₇ = 15

2y₁ – 2y₂ + 50y₃ – 80y₄ + у₅` – у₅``+ y₈ = 40

у_{1-4, 6-8,} у₅`, у₅``³ 0

В этой задаче имеется готовый базис, и можно сразу же решить ее симплекс-методом, не используя метод искусственного базиса*. Решение приведено в таблице 20.

Таблица 20 – Решение двойственной задачи

Дата добавления: 2015-01-18 | Просмотры: 621 | Нарушение авторских прав