Двойственный симплекс-метод
Двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами. В обычном симплексном алгоритме план всегда должен быть допустимым. Допустимый план — это такой план, который удовлетворяет всем ограничениям задачи при обязательном условии неотрицательности неизвестных, то есть любые числа в итоговом столбце положительны. План называется недопустимым (или условно-оптимальным), если в итоговом столбце имеются отрицательные числа, зато оценки целевой строки соответствуют целевой функции, то есть являются положительными при решении на максимум и отрицательными при решении на минимум. В процессе решения двойственным методом план является недопустимым. При использовании двойственного метода сначала применяют обычную симплекс-процедуру и добиваются того, чтобы все оценки соответствовали цели решения задачи, причем пока не обращают внимания на знаки чисел в итоговом столбце. Только когда такой условно-допустимый план достигнут, смотрят на эти знаки. Если в итоговом столбце оказались отрицательные числа, план изменяется так, чтобы недопустимость уменьшилась, а затем и исчезла, но чтобы двойственные оценки продолжали соответствовать при этом цели решения задачи. Возможность придавать в процессе решения отрицательные значения неизвестным, входящим в план, в случае, если ограничения заданы неравенствами, позволяет избавиться от искусственных неизвестных, это сокращает размеры задачи, а значит, и вычислений[21].
Рассмотрим алгоритм решения задач двойственным симплексным методом.
1. Математическая модель прямой задачи линейного программирования должна быть в стандартной форме записи. В противном случае ее надо привести к стандартной форме записи.
2. Для прямой задачи составляется двойственная.
3. Обе задачи приводят к каноническому виду.
4. Выражают базисные переменные обеих задач через основные переменные.
5. Находят исходное решение прямой и двойственной задач и проверяют его на оптимальность. Для этого заполняют симплекс-таблицу двойственного симплекс-метода. Строки таблицы 1-го шага (верхние части клеток) заполняют по данным системы ограничений и целевой функции прямой задачи. Столбцы таблицы 1-го шага (верхние части клеток) заполняют по данным системы ограничений и целевой функции двойственной задачи.
Симплексная таблица двойственного симплекс-метода имеет следующий вид:
| yбаз | ym+1 | ym+2 | ¼ | ym+n | 
| ||
| yсв | xсв xбаз | - x1 | - x2 | ¼ | - xn | bi | |
| y1 | xn+1 | h11 | h12 | ¼ | h1n | l1 | |
| y2 | xn+2 | h21 | h22 | ¼ | h2n | l2 | |
| ¼ | ¼ | ¼ | ¼ | ¼ | ¼ | ¼ | |
| ym | xn+m | hm1 | hm2 | ¼ | hmn | lm | |
| cj | 
| - c1 | - c2 | ¼ | - cn | 
|
Решение является оптимальным, если в строке и столбце bi нет отрицательных элементов.
В противном случае следует провести изменения в базисных переменных.
6. Выбор разрешающей строки. Находят отрицательный элемент в строке . В столбце над этим найденным элементом выбирают любой положительный элемент, эта строка – разрешающая.
Если в столбце над найденным элементом нет положительных элементов, то ПЗЛП не имеет смысла (целевая функция не ограничена в области допустимых решений), а ДЗЛП не имеет решения.
7. Выбор разрешающего столбца. Элементы строки делят на соответствующие элементы разрешающей строки под переменными. Из полученных отношений выбирают максимальное отрицательное отношение, этот столбец – разрешающий (максимальным из отрицательных отношений может быть отношение 
– отрицательный ноль).
Если среди полученных отношений нет отрицательных, то ПЗЛП не имеет решения, ДЗЛП не имеет смысла или решения.
На пересечении разрешающей строки и разрешающего столбца получен разрешающий элемент.
8. Заполнение нижних частей клеток таблицы. Под разрешающим элементом всегда ставят «1». Остальные элементы разрешающей строки переписываются без изменений. Остальные элементы разрешающего столбца переписываются с противоположным знаком. Остальные элементы таблицы находят по правилу прямоугольника: искомый элемент умножают на разрешающий и из этого произведения вычитают произведение элементов, расположенных на противоположной диагонали прямоугольника, образуемого искомым и разрешающим элементами (все элементы из верхних клеток).
9. Построение новой симплекс-таблицы. Изменяют базисные переменные: меняют местами переменные из разрешающей строки и разрешающего столбца. Элементы из нижних клеток предыдущей симплекс-таблицы делят на верхний разрешающий элемент и записывают на соответствующие места в верхние клетки новой симплекс-таблицы.
Если в новой таблице в строке есть отрицательные элементы, то следует сделать следующий шаг симплекс-метода. (Нецелесообразно выбирать за разрешающую строку – те же строки, что и на предыдущих шагах).
Если в новой таблице в строке нет отрицательных элементов, а в столбце свободных членов остались отрицательные элементы, то строка с отрицательным значением 
выбирается за разрешающую, и выполняется следующий шаг симплекс-метода.
Если в строке есть нулевой элемент, то это признак альтернативного оптимума для ПЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода: Столбец с нулевым элементом в строке выбирается за разрешающий. Находят неотрицательные отношения столбца свободных членов к соответствующим элементам разрешающего столбца. Из полученных отношений выбирают минимальное неотрицательное отношение – это разрешающая строка, разрешающий элемент найден. Затем выполняют еще один шаг симплекс-метода.
Если в столбце есть нулевой элемент, то это признак альтернативного оптимума для ДЗЛП. Для нахождения альтернативного решения выполняется еще один шаг симплекс-метода. При этом строка с нулевым элементом в столбце выбирается за разрешающую.
Рассмотрим решение задачи из п. 4.3 двойственным симплекс-методом.
Канонический вид:
Выразим базисные переменные через свободные:
Введем соответствие основных переменных прямой задачи и дополнительных переменных двойственной задачи, а также дополнительных переменных прямой задачи и основных переменных двойственной задачи:
х1
y4
| х2
y5
| х3
y1
| х4
y2
| х5
y3
|
Составим симплекс-таблицу
| yбаз | y4 | y5 |
| |
| yсв | xсв xбаз | - x1 | - x2 | bi |
| y1 | x3 | 2 | 4 | |
| y2 | x4 | «1» | ||
| y3 | x5 | 1 | 8 | |
| cj |
| - 3 | - 4 | 0 |
Решение ПЗЛП выписывается по строкам, значения базисных переменных берутся из столбца bi, если переменная с соответствующим индексом не входит в базис, то ее значение равно нулю: 
= (0, 0, 4, 3, 8), = 0.
Решение ДЗЛП выписывается по столбцам, значения базисных переменных берутся из строки cj, если переменная с соответствующим индексом не входит в базис, то ее значение равно нулю: 
= (0, 0, 0, -3, -4), 
= 0.
Данное решение не является оптимальным, поскольку решение не допустимое (не выполнено условие неотрицательности переменных), ему соответствуют отрицательные элементы в строке .
Над минимальным отрицательным элементом «-4» в строке выбираем положительный, например «1», в строке x4, следовательно, эта строка – разрешающая (выделена жирным шрифтом).
Находим максимальное отношение среди отношений элементов в строке целевой функции к соответствующим элементам разрешающей строки
.
Поскольку максимальное отношение соответствует первому столбцу, то – он разрешающий (выделен жирным шрифтом).
Разрешающий элемент «1» находится на пересечении разрешающей строки и разрешающего столбца.
Заполняем нижние части клеток. Под разрешающим элементом ставим «1». В разрешающей строке остальные элементы переписываем без изменения, а в разрешающем столбце остальные элементы записываем с противоположным знаком. Оставшиеся клетки заполняем по правилу прямоугольника:
клетка на пересечении первой строки и второго столбца:
| 2 | |
| «1» |
2×1 - 1×1 = 1;
клетка на пересечении третьей строки и второго столбца:
| «1» | |
| 1 |
1×1 - 2×1 = -1;
клетка на пересечении четвертой строки и второго столбца:
| «1» | |
| ¼ | ¼ |
| - 3 | - 4 |
- 4×1 - (-3)×1 = -1;
клетка на пересечении первой строки и третьего столбца:
| ¼ | 4 | |
| «1» | ¼ |
4×1 - 3×1 = 1;
клетка на пересечении третьей строки и третьего столбца:
| «1» | ¼ | |
| ¼ | 8 |
8×1 - 3×2 = 2;
клетка на пересечении четвертой строки и третьего столбца:
| «1» | ¼ | |
| ¼ | ¼ | ¼ |
| - 3 | ¼ | 0 |
0×1 - 3×(-3) = 9;
Таким образом, получаем следующую таблицу:
| yбаз | y4 | y5 |
| |
| yсв | xсв xбаз | - x1 | - x2 | bi |
| y1 | x3 | -1 | 2 1 | 4 1 |
| y2 | x4 | «1» | ||
| y3 | x5 | -2 | 1 -1 | 8 2 |
| cj |
| - 3 | - 4 -1 | 0 9 |
Переходим к следующей симплекс-таблице. При этом в базис включается пара переменных х1, у4, соответствующих разрешающему столбцу, а из базиса выводится пара переменных х4, у2, соответствующая разрешающей строке. В следующей таблице данные пары переменных меняются местами. Верхние части клеток заполняются элементами, полученными в результате деления соответствующих (стоящих на аналогичном месте) элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «1»:
| yбаз | y2 | y5 |
| |
| yсв | xсв xбаз | - x4 | - x2 | bi |
| y1 | x3 | -1 | 1 | |
| y3 | x1 | 1 | 3 | |
| y3 | x5 | -2 | -1 | 2 |
| cj |
| 3 | -1 | 9 |
Решение ПЗЛП на втором шаге двойственного симплекс-метода также выписывается по строкам: 
= (3, 0, 1, 0, 2), 
= 9, решение ДЗЛП выписывается по столбцам: 
= (0, 3, 0, 0, -1), 
= 9. Данное решение также не оптимальное, поскольку еще остался отрицательный элемент «-1». Необходим еще один шаг двойственного симплекс-метода.
Над отрицательным элементом «-1» в строке выбираем положительный, предпочтительнее «1», в строке x3, поскольку вторая строка была выбрана на предыдущем шаге метода, следовательно, первая строка – разрешающая (выделена жирным шрифтом).
Находим максимальное отношение среди отношений элементов в строке целевой функции к соответствующим элементам разрешающей строки
.
Поскольку максимальное отношение соответствует второму столбцу, то – он разрешающий (выделен жирным шрифтом).
Разрешающий элемент «1» находится на пересечении разрешающей строки и разрешающего столбца.
Заполняем нижние части клеток. Под разрешающим элементом ставим «1». В разрешающей строке остальные элементы переписываем без изменения, а в разрешающем столбце остальные элементы записываем с противоположным знаком. Оставшиеся клетки заполняем по правилу прямоугольника аналогично предыдущему шагу метода, получаем следующую таблицу:
| yбаз | y2 | y5 |
| |
| yсв | xсв xбаз | - x4 | - x2 | bi |
| y1 | x3 | -1 -1 | «1» | 1 |
| y3 | x1 | 1 2 | -1 | 3 2 |
| y3 | x5 | -2 -3 | -1 1 | 2 3 |
| cj |
| 3 2 | -1 1 | 9 10 |
Переходим к следующей симплекс-таблице. При этом в базис включается пара переменных х2, у5, соответствующих разрешающему столбцу, а из базиса выводится пара переменных х3, у2, соответствующая разрешающей строке. В следующей таблице данные пары переменных меняются местами. Клетки следующей таблицы заполняются элементами, полученными в результате деления соответствующих элементов из предыдущей таблицы в нижних частях клеток на разрешающий элемент «1». Поскольку в нижних частях клеток таблицы все элементы положительные и разрешающий элемент также положительный, то в следующей таблице будет получено оптимальное решение и нет необходимости делить на две части клетки в последней таблице:
| yбаз | y2 | y1 |
| |
| yсв | xсв xбаз | - x4 | - x3 | bi |
| y5 | x2 | -1 | 1 | 1 |
| y3 | x1 | 2 | -1 | 2 |
| y3 | x5 | -3 | 1 | 3 |
| cj |
| 2 | 1 | 10 |
Оптимальное решение ПЗЛП: 
= (2, 1, 0, 0, 3), 
= 10, оптимальное решение ДЗЛП: 
= (1, 2, 0, 0, 0), 
= 10.
Данное решение аналогично решению, полученному в соответствии с методом одновременного решения пары взаимодвойственных задач.