2.6. Признак оптимальности опорного плана. Симплексные таблицы

Для того, чтобы было удобнее решать ЗЛП симплексным методом были придуманы симплексные таблицы, которые позволяют максимально алгоритмизировать процесс решения задачи линейного программирования. Симплексная таблица составляется только в том случае, если составлен начальный опорный план.

Пусть ЗЛП представлена в каноническом виде:

при

С помощью метода Гаусса (см. 1.12) преобразуем систему ограничений и приведем ее к следующему виду:

при

(i=)

Из записи ЗЛП видно, что первые m переменных являются базисными. При этом мы не нарушаем общности рассуждений, так как то, что базисными будут первые m переменных, позволит более наглядно проиллюстрировать теорию.

Составим симплексную таблицу:

БП	СБ	А			…			…		…
					…			…		…
			1	0	…	0		…		…
			0	1	…	0		…		…
…	…	…	…	…	…	…	…	…	…	…	…
			0	0	…	0		…		…
…	…	…	…	…	…	…	…	…	…	…	…
			0	0	…	1		…		…
			0	0	…	0		…		…

В первом столбце (БП) пишутся базисные переменные. Все базисные переменные пишутся В СООТВЕТСТВИИ С УРАВНЕНИЯМИ, ДЛЯ КОТОРЫХ ДАННЫЕ ПЕРЕМЕННЫЕ ЯВЛЯЮТСЯ ПРЕДПОЧТИТЕЛЬНЫМИ.

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

В третьем столбце (А) пишутся свободные члены в уравнениях системы ограничений.

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

В таблице со второй строки четвертого столбца пишутся все коэффициенты соответственных переменных в системе ограничений.

В последней строке пишутся оценки. Оценки считаются по формулам (см. 1.12):

…………………………………….

Оценки для базисных переменных равны 0.

Замечание: Оценки считаются как скалярное произведение соответственного столбца на столбец СБ минус коэффициент в целевой функции для данной переменной.

Последнюю строку называют индексной строкой симплексной таблицы. Значение – значением целевой функции для данного начального опорного плана, а все остальные Δ – оценками свободных переменных.

Теорема 1: (признак оптимальности опорного плана при решении задач на максимум) Пусть исходная ЗЛП решается на максимум. Если для некоторого опорного плана в индексной строке симплексной таблицы все оценки () неотрицательны, то такой план будет оптимальным.

Теорема 2: (признак оптимальности опорного плана при решении задач на минимум) Пусть исходная ЗЛП решается на минимум. Если для некоторого опорного плана в индексной строке симплексной таблицы все оценки () неположительны, то такой план будет оптимальным.

Пример 1: Составить симплексную таблицу и посчитать оценки для задачи линейного программирования вида:

при

Решение.

Построение начального опорного плана рассмотрено в 2.5.

при

Базис системы составляют переменные: , , , (представлены в соответствии с уравнениями, предпочтительными переменными которых являются данные переменные).

БП	СБ	А
			-12	32	0	0	-1	0	0	–M	–M
	32	23	-1	1	14	0	0	0	0	0	0
	–M	17	13	0	4	-1	0	0	0	1	0
	0	34	-4	0	-1	0	12	1	0	0	0
	–M	6	1	0	1	0	1	0	-1	0	1
св. чл		736	-20	0	448	0	1	0	0	0	0
M		-23	-14	0	-5	1	-1	0	1	0	0

=23∙32-17 M+0∙34-6∙M=-23∙M+736;

=-1∙32-13∙M-0∙4-1∙M+12=-14∙M-20;

=32∙1-0∙M+0∙0-0∙M-32=0∙M+0=0 (базисная переменная);

=32∙14-4∙M-0∙1-1∙M-0=-5∙M+448;

=32∙0+1∙M+0∙0-0∙M-0=1∙M+0;

=32∙0-0∙M+0∙12-1∙M+1=-1∙M+1;

=32∙0-0∙M+0∙1-0∙M-0=0∙M+0=0 (базисная переменная);

=32∙0-0∙M+0∙0+1∙M-0=1∙M+0=0;

=32∙0-1∙M+0∙0-0∙M+M=0∙M+0=0 (базисная переменная);

=32∙0-0∙M+0∙0-1∙M+M=0∙M+0=0 (базисная переменная);

Для данного начального опорного плана ответ: Z=-23∙M+736 при (0, 23, 0, 0, 0, 34, 0, 17, 6).

Замечание: Значение Z взято из индексной строки симплексной таблицы (пересечение индексной строки и столбика А). Значение базисных переменных из столбика А.

Данный опорный план не является оптимальным, т.к. в индексной строке симплексной таблицы есть отрицательные оценки, соответствующие свободным переменным.