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

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

Двойственный симплекс метод основан на теории двойственности и используется для решения задач линейного программирования, свободные члены (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

Отношения

shukaev671.wmf

shukaev672.wmf

 

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

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

Таблица 2.9

БП

x1

x2

x3

x4

x5

bi

x1

shukaev673.wmf

0

1

shukaev674.wmf

0

–1

x2

shukaev675.wmf

1

0

shukaev676.wmf

0

2

x5

shukaev677.wmf

0

0

shukaev678.wmf

1

–1

f

shukaev679.wmf

–1

0

shukaev680.wmf

0

2

 

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

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

Таблица 2.10

БП

x1

x2

x3

x4

x5

bi

x1

1

0

shukaev132.wmf

shukaev133.wmf

0

shukaev134.wmf

x2

0

1

shukaev135.wmf

shukaev136.wmf

0

shukaev137.wmf

x5

0

0

–1

1

1

0

f

0

0

shukaev138.wmf

shukaev139.wmf

1

shukaev681.wmf

 

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

shukaev140.wmf

shukaev141.wmf и shukaev142.wmf

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


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074