Фрагмент симплекс-таблицы

с	Базис	A0=b	…	сj	…	Cs
			…	Aj	…	As
…	…	…	…	…	…	…
ck	Ak	xk0	…		…
…	…	…	…	…	…	…
сr	Ar	xr0	…		…
…	…	…	…	…	…	…
	C(х)/j	C(х^0)	…	j	…	s

Компоненты нового псевдоплана определяются согласно (1.69).

(1.69)

Другие элементы симплексной таблицы вычисляются по формулам (1.70), двойственные оценки – по формулам (1.71), а значение целевой функции на новом псевдоплане – по формуле (1.72).

, (1.70)

, (1.71)

. (1.72)

Теорема 1.10.

Применение правил 1 и 2, а также формул (1.69)  (1.72) обеспечивает:

1) переход к новому псевдоплану, т. е. гарантируется

1. ;

б) новый псевдоплан х^нов есть базисный план.

2) Значение целевой функции на новом псевдоплане не больше, чем значение целевой функции на предыдущем псевдоплане, т.е. С(х^нов)  С(х⁰).

П р и м е р 1.15. Решить следующую ЗЛП:

C(х) = 8x₁ + x₂ + x₃  min

4x₁ – x₂ + 2x₃  16

x₂ + 6x₃  4

x_j  0; j = 1, 2, 3.

Прежде всего, приведем данную ЗЛП к каноническому виду, умножив целевую функцию на (-1) и введя дополнительные переменные х₄ и х₅. Одновременно умножим первое и второе ограничение на (-1), чтобы получить единичный базис. В результате имеем каноническую форму ЗЛП:

C₁(х) = –8x₁ – x₂ – x₃  max

–4x₁ + x₂ – 2x₃ + x₄ = -16

–x₂ – 6x₃ + x₅ = -4

x_j  0; j = 1,5

Имеем базисный план х⁰ = (0; 0; 0; -16; -4), который не является допустимым. Однако это псевдоплан, так как двойственные оценки не отрицательные. Можем применить двойственный симплекс-метод. Строим симплексную таблицу (табл. 1.9) и решаем задачу.

Из базиса выводится вектор А₄ , поскольку min -16, -4 = -16.

Вектор, который вводится в базис, выбирается из соотношения

.

Следовательно, в базис входит вектор А₃, а ведущим элементом будет –2. На следующей итерации получаем в столбце A₀ = b все элементы положительные, а в строке оценок все элементы неотрицательные.

Таблица 1.9.

Симплексная таблица (пример 1.15)

			-8	-1	-1	0	0
с	Базис	A0=b	A1	A2	A3	A4	A5
0	A4	-16^*	-4	1	-2	1	0
0	A5	-4	0	-1	-6	0	1
	C1(х)/j	0	8	1	1	0	0
-1	A3	8	2	-1/2	1	-1/2	0
0	A5	44	12	-4	0	-3	1
	C1(X)/j	-8	6	3/2	0	1/2	0

Таким образом, на основании теоремы 1.9 можно сделать заключение, что получен оптимальный план х^* = (0; 0; 8; 0; 44); значение целевой функции канонической задачи C₁(х^*) = -8; значение целевой функции исходной задачи C(х^*) = 8.