Определение оптимальности плана. Построение новой симплексной таблицы

В симплексных таблицах формальным признаком оптимальности является содержание оценочной строки.

Ключевая теорема симплексного метода (Z на максимум): Если после выполнения очередной итерации: найдется хотя бы одна отрицательная оценка , а в столбце , где она стоит, есть хотя бы один положительный элемент , то опорное решение можно улучшить , выполнив следующую итерацию ; найдется хотя бы одна отрицательная оценка , столбец которой не содержит положительных элементов , то функция Z неограниченна в области допустимых решений (Zmax ); все оценки окажутся неотрицательными , то достигнуто оптимальное решение .

Согласно данной теоремы:

1. Просматриваются оценки Z - строки. Если они все неотрицательны, то получено оптимальное решение при решении на максимум целевой функции, если все оценки  0, то получено оптимальное решении при решении на минимум целевой функции.

2. Если оптимальное решение не получено, то выбирается разрешающий столбец по наибольшей по абсолютной величине отрицательной оценке Z - строки при решении на максимум и по наибольшей положительной оценке при решении на минимум целевой функции.

3. Составляются симплексные отношения - отношения свободных членов к положительным коэффициентам разрешающего столбца. Минимальное из этих отношений ( min a_i 0/ a_ip) определит разрешающую строку. Коэффициент, находящийся на пересечении разрешающей строки и разрешающего столбца, называется разрешающим элементом.

Если в разрешающем столбце нет ни одного положительного коэффициента , то задача не имеет решения по причине неограниченности целевой функции (Zmax+ ,Zmin- ).

4. Осуществляется переход к новой таблице, где базисная переменная заменяется на свободную, соответствующую разрешающему столбцу.

5. Бывший разрешающий элемент заменяется обратным по величине (1/ а_qp).

6. Все остальные элементы бывшего разрешающего столбца делятся на разрешающий элемент и меняют знаки на противоположный.

Если в бывшем разрешающем столбце в какой-то строке стоял “0”, то эта строка переносится в следующую таблицу без изменений.

7. Все остальные элементы бывшей разрешающей строки делятся на разрешающий элемент .

Если в бывшей разрешающей строке в каком-то столбце стоял “0”, то этот столбец переносится в следующую таблицу без изменений.

8. Остальные элементы таблицы пересчитываются по правилу “прямоугольника”:

aij=	Исходный коэффициент	-	Коэффициент разрешающей строки	х	Коэффициент разрешающего столбца
			Разрешающий элемент

a_ij . . . . a_ip

. . . . . . . . . a_ij = a_ij - a_qj *a_ip/ a_qp , где

a_qj. . . (a_qp) i =1,2,..... j=0,1,..... , т.е. и столбцов свободных

членов.

9. Осуществляется контроль за правильностью расчетов для элементов Z-строки по формуле (2).

10. Если ошибок нет, то алгоритм повторяется с пункта 1.

В первой симплексной таблице нашего примера все коэффициенты оценочной строки отрицательны. Следовательно, согласно теореме, план (на максимум целевой функции) не является оптимальным и требует улучшения.

В последнем столбце рассчитывают симплексные отношения.

Таблица 2.1

Симплексная таблица (исходное опорное решение)

Св.П	Cj	-2	1	2
Б.П.	Ci	ai0	X1	X2	ai0/aip
X3	0	4	3	1	4
X4	0	4	1	(3)	4/3
Z		2	-1	-2 

Исходное опорное решение: Х₁(0,0,4,4); Zmax=2

Во второй симплексной таблице меняем местами базисную переменную X₄ и свободную X₂.

На месте бывшего разрешающего элемента запишем обратную величину, т.е. 1/3.

Все остальные элементы разрешающей строки в новой таблице вычислим путем деления на разрешающий элемент: 4/3; 1/3.

Все остальные элементы бывшего разрешающего столбца определим путем деления на разрешающий элемент. Результат запишем в новую таблицу с противоположным знаком: -1/3; 2/3.

Все остальные элементы таблицы вычислим по правилу «прямоугольника».

Первая строка: 4 – 4  1/3 =8/3 3 – 1  1/3 =8/3

Оценочная строка: 2 – 4  (-2)/3 =14/3 -1 – 1  (-2)/3 = -1/3

Таблица 2.2.

Вторая симплексная таблица

Св.П	Cj	-2	1	0
Б.П.	Ci	ai0	X1	X4	ai0/aip
X3	0	8/3	(8/3)	-1/3	1
X2	2	4/3	1/3	1/3	4
Z		14/3	-1/3 	2/3

Проверим правильность заполнения Z – строки по формуле (2).

а₀₀ = 0  8/3 + 2  4/3 – (-2) = 14/3

а₀₁ =0  8/3 + 2  1/3 – 1 = -1/3

а₀₂ =0 (-1/3) + 2  1/3 – 0 = 2/3

Так как в оценочной строке есть еще отрицательные оценки, оптимальное решение не получено, можем записать только опорное решение:

X₂( 0,4/3,8/3,0) Zmax=14/3

По тому же алгоритму пересчитываем коэффициенты четвертой таблицы.

Таблица 2.3.

Третья симплексная таблица

Св.П	Cj	-2	0	0
Б.П.	Ci	ai0	X3	X4
X1	1	1	3/8	-1/8
X2	2	1	-1/8	3/8
Z		5	1/8	5/8

Все оценки неотрицательны, следовательно, получено оптимальное решение Хопт(1,1,0,0) Zmax=5

Пример2

Задача решалась на максимум функции (Z max). На последнем шаге была получена следующая таблица.

Таблица 2.4.

Последняя симплексная таблица

Св.П	Cj	0	1	0
Б.П.	Ci	ai0	X3	X2
X1	2	2	1	-1
X4	0	1	1	-1/2
Z		4	1	-2 

В разрешающем столбце нет ни одного положительного элемента, следовательно, Zmax ,т.е. задача линейного программирования не имеет решения по причине неограниченности целевой функции Z сверху.