2015-04-20
596
Он требует, чтобы задача была задана в виде основной задачи линейного программирования. Вместе с тем его можно применять при решении задач линейного программирования, у которых свободные члены системы ограничений могут быть любыми числами(как положительные, так и отрицательные).
Пусть требуется определить 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
при условиях:
