Двойственный симплекс-метод
Двойственная задача линейного программирования
Ая итерация
План можно улучшить. Вводимой переменной будет х6 , а выводимой х5
3-ая итерация
План улучшить нельзя, так как в индексной строке нет отрицательных элементов, следовательно найден оптимальный план.
X*=(0;0;11/2;035;0;1)
Оптимальное значение целевой функции берем в индексной строке в колонке «план» (в последнем разделе), Так как исходная целевая функция стремилась к min , то у полученного значения целевой функции из последнего раздела меняется знак на противоположный т.е. :
F*=-68
Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу линейного программирования, называемую двойственной или сопряженной по отношению к исходной или прямой. Связь исходной и двойственной задач заключается в том, что решение одной из них может быть получено из решения другой.
Дадим определение двойственной задачи по отношению к общей задаче линейного программирования, состоящей в нахождении максимального значения функции
F = C1X1 + C2X2+…+CnXn (1)
при условиях
(2)
xj≥0 (j=1,n) (3)
Задача, состоящая в нахождении минимального значения функции
F*=b1y1+b2y2+…+bmym (4.)
при условиях
(5)
yi≥0 (i=1,m) ( 6)
называется двойственной задачей по отношению к задаче (1) – (3)..
Задачи (1) – (3) и (4) – (6) образуют пару задач, называемую в линейном программировании двойственной парой.
Сравнивая две сформулированные задачи, видим, что двойственная задача по отношению к исходной составляется согласно следующим правилам:
1. Целевая функция исходной задача задается на max , а целевая функция двойственной задачи на min .
2. Матрица:
составленная из коэффициентов при неизвестных в система ограничений (2) исходной задачи и аналогичная матрица
в двойственной задаче получаются друг из друга транспонированием(т.е. заменой строк столбцами, а столбцов – строками).
3. Число переменных в двойственной задаче равно числу соотношений в системе ( 2) исходной задачи, а число ограничений в системе(5) двойственной задачи равно числу переменных в исходной задаче.
4. Коэффициентами при неизвестных целевой функции двойственной задачи являются свободные члены системы (2) исходной задачи, а правыми частями в системе ограничений двойственной задачи – коэффициенты при неизвестных в целевой функции исходной задачи .
5. Если переменная xj исходной задачи может принимать лишь положительные значения, то j-тое условие в системе (5) двойственной задачи является неравенством вида «≥». Если же переменная xj может принимать как положительные так и отрицательные значения, то j-тое соотношение в системе (5) является уравнением.
6. Если i-е соотношение в системе (2) исходной задачи является неравенством, то i-тая переменная двойственной задачи yi≥0 . В противном случае переменная yi может принимать как положительные так и отрицательные значения.
Двойственные пары задач обычно подразделяются на симметричные и несимметричные.
В симметричной паре двойственной задачи ограничения вида (2) исходной задачи и соотношения (5) двойственной задачи являются неравенствами вида « ≤», т.е переменные обеих задач могут принимать только неотрицательные значения.
Он требует, чтобы задача была задана в виде основной задачи линейного программирования. Вместе с тем его можно применять при решении задач линейного программирования, у которых свободные члены системы ограничений могут быть любыми числами(как положительные , так и отрицательные).
Пусть требуется определить max значения функции:
F=C1X1+C2X2+…+CnXn →max
при условиях :
x1p1+x2p2+…+xmpm+xm+1pm+1+…+xnpn= po ,
где:
xj≥0 (j=1,n)
Таким образом, векторы р1;p2; … ;pm – единичные векторы, образующие базис.
Среди чисел bi имеются отрицательные (i=1,m).
В данном случае решение X = (b1, b2 , … ,bm, 0, 0, … ,0) является решением системы линейных уравнений, представляющих решение исходной задачи, но не является решением самой исходной задачи.
Такое решение Х называют псевдопланом (т.к. по условию xj≥0, а среди bi есть отрицательные числа.)
Рассмотрим алгоритм двойственного симплекс-метода:
1. Составляют симплекс-таблицу и находят псевдоплан задачи.
2. Проверяют псевдоплан на оптимальность или устанавливают неразрешимость задачи. Если в колонке «План» нет отрицательных чисел, то псевдо план является оптимальным. Если отрицательные числа имеются, то переходят к новому псевдоплану, либо устанавливают неразрешимость задачи.
3. Выбирают направляющую строку путем определения наибольшего по модулю отрицательного числа в колонке «План». Затем определяют направляющий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов «m+1»-ой строки к соответствующим отрицательным элементам направляющей строки.
В результате определяют вектор, выводимый из базиса и вектор, вводимый в базис.
4. Находят новый псевдоплан путем пересчета элементов нового раздела симплекс-таблицы и повторяют все действия с пункта 2.
Пример: найти максимальное значение функции
F=-x1+x2+x3 →max
при условиях: