Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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




Дадим определение двлйственной задачи по отношению к общей ЗЛП, состоящей в нахождении максимального значения функции Z=C1x1+C2x2+...+Cnxn (2.67)

при условиях

(2.68) xj ³0 (2.69)

Опр: Задача, состоящая в нахождении минимального значения функции

Z*=b1y1+b2y2+...+bnyn (2.70)

при условиях

(2.71) yi ³ 0 (2.72)

называется двойственной по отношению к задаче (2.67) (2.69).

Двойственная задача по отношению к исходной составляется согласно следующим правилам:

1. Целевая функция исходной задачи (2.67) (2.69) задается на максимум, а целевая функция двойственной (2.70) (2.72) на минимум.

2. Матрица

,

составленная из коэффициентов при неизвестных в системе ограничений (2.68) исходной задачи, и аналогичная матрица

в двойственной задаче получаются друг из друга транспонированием.

3. Число переменных в двойственной задаче равно числу соотношений в системе (2.70) исходной задачи, а число ограничений в системе (2.71) двойственной задачи числу переменных в исходной задаче.

4. Коэффициентами при неизвестных в целевой функции (2.70) двойственной задачи являются свободные члены в системе (2.68) исходной задачи, а правыми частями в соотношениях системы (2.71) двойственной задачи коэффициенты при неизвестных в целевой функции (2.67) исходной задачи.

5. Если переменная хj исходной задачи может принимать только лишь положительные значения, то j- е условие в системе (2.71) двойственной задачи является неравенством вида «³». Если же переменная хj может принимать как положительные, так и отрицательные значения, то j -е соотношение в системе (2.71) представляет собой уравнение. Аналогичные связи имеют место между ограничениями (2.68) исходной задачи и переменными двойственной задачи. Если i- е соотношение в системе (2.68) исходной задачи является неравенством, то i- я переменная двойственной задачи yi ³0. В противоположном случае переменная yi может принимать как положительные, так и отрицательные значения.

Поделиться:





Читайте также:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...