Двойственный симплекс метод основан на теории двойственности и используется для решения задач линейного программирования, свободные члены (bi, i = 1, 2, …, m), которых могут принимать любые значения, а система ограничений задана неравенствами
≤, ≥, =.
В двойственном симплекс методе оптимальное решение получается в результате движения по псевдобазисным решениям к области допустимых решений. Когда полученное решение оказывается допустимым, процесс вычислений заканчивается, так как это решение является оптимальным.
Суть симплекс метода поясним, анализируя решение конкретной задачи линейного программирования [37].
Пусть необходимо минимизировать целевую функцию
f = 2x1 + x2 → max,
при ограничениях
3x1 + x2 ≥ 3;
4x1 + 3x2 ≥ 6;
x1 + 2x2 ≤ 3;
∀xj ≥ 0.
С начало необходимо преобразовать все ограничения в неравенства со знаком ≤, а затем ввести дополнительные переменные для перехода из неравенств в равенства. В результате получим
f = 2x1 + x2 → max,
при ограничениях
–3x1 – x2 + x3 = –3;
–4x1 – 3x2 + x4 = –6;
x1 + 2x2 + x5 = 3;
∀xj ≥ 0.
Попытка составить для данной задачи начальную симплекс-таблицу приводит к выводу, что значения дополнительных переменных не обеспечивают получение допустимого базисного решения. Так как целевая функция подлежит минимизации, а все коэффициенты f – уравнения неположительны, начальное базисное решение:
x3 = –3; x4 = –6; x5 = 3.
оптимальное, но недопустимое.
Начальная симплекс-таблица, соответствующая этому оптимальному, но недопустимому решению имеет вид, приведенной в табл. 2.7
Таблица 2.7
БП |
x1 |
x2 |
x3 |
x4 |
x5 |
bi |
x3 |
–3 |
–1 |
1 |
0 |
0 |
–3 |
x4 |
–4 |
–3 |
0 |
1 |
0 |
–6 |
x5 |
1 |
2 |
0 |
0 |
1 |
3 |
f |
–2 |
–1 |
0 |
0 |
0 |
0 |
Для выбора следующего базисного решения в качестве исключаемой переменной выбирается наибольшее по абсолютной величине отрицательная базисная переменная (при наличии альтернативы выбирается произвольная). Если все базисные переменные неотрицательные, процесс вычисления заканчивается, так как полученное решение допустимое и оптимальное.
Затем в качестве включаемую в базис переменной выбирается переменная из числа небазисных. Для этого вычисляются отношения коэффициентов f – строки к соответствующим коэффициентам строки, принадлежащей исключаемой переменной. Отношения с положительным или нулевым значением знаменателя не учитываются.
В задаче минимизации вводимой переменной должно соответствовать наименьшее из указанных отношений, а в задаче максимизации – отношение наименьшее по абсолютной величине (при наличии альтернатив выбор делается произвольно).
Если знаменатели всех отношений равны нулю или положительные, задача не имеет допустимых решений.
В табл. 2.7 исключаемой переменной является x4 = –6, так как она имеет наибольшее по абсолютной величине отрицательное значение. Отношения, вычисленные для определения новой базисной переменной, приведены в табл. 2.8.
Таблица 2.8
Переменные |
x1 |
x2 |
x3 |
x4 |
x5 |
x4 |
–4 |
–3 |
0 |
1 |
0 |
f |
–2 |
–1 |
0 |
0 |
0 |
Отношения |
|
|
– |
– |
– |
В качестве исключаемой переменной выбирается x2, так как этой переменной соответствует минимальное отношение.
Последующее стандартное преобразование симплекс-алгоритма (см. раздел 2.3.3) приводит к следующей симплекс-таблице (табл. 2.9):
Таблица 2.9
БП |
x1 |
x2 |
x3 |
x4 |
x5 |
bi |
x1 |
|
0 |
1 |
|
0 |
–1 |
x2 |
|
1 |
0 |
|
0 |
2 |
x5 |
|
0 |
0 |
|
1 |
–1 |
f |
|
–1 |
0 |
|
0 |
2 |
Новое решение также оптимальное, но не допустимое (x3 = –1 и x5 =–1).
Если в качестве новой исключаемой переменной выбрать (произвольно) x3, то вводимой в базис переменной будет x1 и в результате имеем следующую симплекс-таблицу (табл. 2.10):
Таблица 2.10
БП |
x1 |
x2 |
x3 |
x4 |
x5 |
bi |
x1 |
1 |
0 |
|
|
0 |
|
x2 |
0 |
1 |
|
|
0 |
|
x5 |
0 |
0 |
–1 |
1 |
1 |
0 |
f |
0 |
0 |
|
|
1 |
|
Полученное решение исходной задачи
и
является оптимальным и допустимым.