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

Изложение двойственного симплекс-метода.

Двойственный симплекс-метод (ДСМ) непосредственно применяется к решению почти каноничной задачи линейного программирования (МКЗЛП), которая формулируется таким образом:

Найти вектор x = (x₁...,xn), что минимизирует линейную функцию

L(x)= c₁x₁ +... + c_nx_n (4.1)

и удовлетворяет систему линейных ограничений

x_i + a_i,m+1 x_m+1 +... + a_inx_n = a_i0, i=1...,m (4.2)

x_j ³ 0, j=1...,n (4.3)

(компоненты a_i0 вектора ограничений A₀ могут быть отрицательными) при дополнительном условии: относительные оценки (симплекс - разницы) D j переменных x_j неотъемлемые.

Вектор x= (x₁...,xn) называется почти допустимым базисным решением (МДБР) МКЗЛП, если его компоненты удовлетворяют ограничение (4.2), и ненулевым компонентам x_j отвечают линейно независимые векторы условий Aj.

Базис и базисная матрица МДБР определяются подобно тому, как это делается для СЗЛП.

МКЗЛП является случаем части СЗЛП. Существуют методы сведения произвольной ЗЛП к почти каноничному виду.

Признак оптимума: Если на некотором шаге ДСМ компоненты МДБР x* неотъемлемые, то x* — оптимальное решение МКЗЛП.

Признак отсутствия решения: Оптимального решения МКЗЛП не существует, если на каком-либо шаге ДСМ в строке с a_i0<0 все компоненты a_ij ³ 0, j=1...,n. В этом случае допустимое множество решений МКЗЛП пустое.

Алгоритм двойственного симплекс-метода.

На каждом шагу ДСМ выполняются такие действия (расчетные формулы наводятся лишь для первого шага).

1. Рассматривается МДБР x= (a10..., am0,0,...,0).

Вычисляются относительные оценки (симплекс - разницы) D j небазисных переменных x_j, j=m+1...,n, за формулой:

D j=c_j – (c_б, Aj)

где c_б= (c₁..., cm), Aj — вектор условий, что отвечает переменной x_j (относительные оценки базисных переменных равняются нулю).

Если для всех i=1...,m выполняется условие a_i0 ³ 0, то МДБР x будет оптимальным решением МКЗЛП. Конец вычислений.

Если существует такое и, что a_i0<0, а коэффициенты a_ij ³ 0, j=1...,n, то МКЗЛП не имеет допустимых решений. Конец вычислений.

2. Если существуют индексы и, для которых a_i0<0, а среди соответствующих компонент a_ij, j=1...,n, есть отрицательные, то находят l:

l=argmin a_i0

и: a_i0<0

вычисляют отношение gj=– D j/a_lj для всех a_lj<0 и определяют k:

k=argmin gj.

и: a_lj<0

3. Переходят к новому МДБР, исключая из базиса вектор A_l и вводя к базису вектор A_k. Упомянутый переход осуществляется с помощью симплекс - превращений (элементарных превращений Жордана - Гаусса с ведущим элементом a_lk) над элементами расширенной матрицы условий. Переход к пункту 1.

Программное обеспечение.

Обучающий модуль, с помощью которого ЗЛП Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПО–МО.

Задание.

Решить двойственным симплекс-методом задачи линейного программирования, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1 – №9), а также следующие задачи.

Во всех задачах, которые предлагаются дальше, все переменные неотъемлемые.

1)	6 x1 + 4 x2 ® min	2)	2 x1 + 3 x2 ® min	3)	–6 x1 – 4 x2 ® max
	2 x1 + x2 ³ 3		x1 + 5 x2 ³ 16		2 x1 + x2 ³ 3
	x1 – x2 £ 1		3 x1 + 2 x2 ³ 12		x1 – 2 x2 £ 2
	– x1 + 2 x2 ³ 1;		2 x1 + 4 x2 ³ 16;		3 x1 + 2 x2 ³ 1;

4)	6 x1 + 4 x2 ® min	5)	7 x1 + x2 ® min	6)	7 x1 + 10 x2 ® min
	2 x1 + x2 ³ 3		x1 + x2 ³ 3		2 x1 + 28 x2 ³ 17
	3 x1 + 2 x2 ³ 1		5 x1 + x2 ³ 5		x1 + 2 x2 ³ 3;
	– x1 – x2 ³ 6;		x1 + 5 x2 ³ 5;		x1 + 17 x2 ³ 19;

7)	x1 + x2 + 2 x3 ® min	8)	–15x1 – 33 x2 ® max
	2 x1 – x2 – 3 x3 + x4 = – 3		3 x1 + 2 x2 ³ 6
	x1 – 3 x2 – 4 x3 + x5 = – 1;		6 x1 + x2 ³ 6;

9)	x1 + 2 x2 ® min	10)	78 x1 + 52 x2 ® min	11)	5 x1 + 4 x2 ® min
	2 x1 + x2 £ 18		6 x1 + 2 x2 ³ 9		x1 + x2 £ 6
	x1 + 2 x2 ³ 14		-10 x1 + 14 x2 ³ 13		2 x1 + x2 ³ 9
	x1 – 2 x2 £ 10;		11 x1 - x2 ³ 6;		3 x1 + x2 ³ 11.

Ответы:

1) x* = (1; 1), L (x*)= 10.

2) x* = (2; 3), L (x*)= 13.

3) x* = (1.5; 0), L (x*)= -9.

4) Решения нет (D = Æ).

5) x* = (0; 5), L (x*)= 5.

6) x* = (0; 1.5), L (x*)= 15.

7) x* = (0; 0; 1; 0; 3), L (x*)= 2.

8) x* = (2; 0), L (x*)= -30.

9) x* = (7.33; 3.33), L (x*)= 14.

10) x* = (0.96; 1.62), L (x*)= 159.12.

11) x* = (4.5; 0), L (x*)= 22.5.

Лабораторная работа 5.