Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Прикладные методы оптимизации

Шукаев Д. Н.,

2.5. Двойственный симплекс метод

Двойственный симплекс метод основан на теории двойственности и используется для решения задач линейного программирования, свободные члены (bi, i = 1, 2, …, m), которых могут принимать любые значения, а система ограничений задана неравенствами

≤, ≥, =.

В двойственном симплекс методе оптимальное решение получается в результате движения по псевдобазисным решениям к области допустимых решений. Когда полученное решение оказывается допустимым, процесс вычислений заканчивается, так как это решение является оптимальным.

Суть симплекс метода поясним, анализируя решение конкретной задачи линейного программирования [37].

Пусть необходимо минимизировать целевую функцию

f = 2x1 + x2 → max,

при ограничениях

3x1 + x2 ≥ 3;

4x1 + 3x2 ≥ 6;

x1 + 2x2 ≤ 3;

∀x_j ≥ 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

Для выбора следующего базисного решения в качестве исключаемой переменной выбирается наибольшее по абсолютной величине отрицательная базисная переменная (при наличии альтернативы выбирается произвольная). Если все базисные переменные неотрицательные, процесс вычисления заканчивается, так как полученное решение допустимое и оптимальное.

Затем в качестве включаемую в базис переменной выбирается переменная из числа небазисных. Для этого вычисляются отношения коэффициентов f – строки к соответствующим коэффициентам строки, принадлежащей исключаемой переменной. Отношения с положительным или нулевым значением знаменателя не учитываются.

В задаче минимизации вводимой переменной должно соответствовать наименьшее из указанных отношений, а в задаче максимизации – отношение наименьшее по абсолютной величине (при наличии альтернатив выбор делается произвольно).

Если знаменатели всех отношений равны нулю или положительные, задача не имеет допустимых решений.

В табл. 2.7 исключаемой переменной является x4 = –6, так как она имеет наибольшее по абсолютной величине отрицательное значение. Отношения, вычисленные для определения новой базисной переменной, приведены в табл. 2.8.

Таблица 2.8

В качестве исключаемой переменной выбирается x2, так как этой переменной соответствует минимальное отношение.

Последующее стандартное преобразование симплекс-алгоритма (см. раздел 2.3.3) приводит к следующей симплекс-таблице (табл. 2.9):

Таблица 2.9

Новое решение также оптимальное, но не допустимое (x3 = –1 и x5 =–1).

Если в качестве новой исключаемой переменной выбрать (произвольно) x3, то вводимой в базис переменной будет x1 и в результате имеем следующую симплекс-таблицу (табл. 2.10):

Таблица 2.10

Полученное решение исходной задачи

и

является оптимальным и допустимым.