Линейное программирование (Графический метод. Симплексный метод) (стр. 9 )

Симплексные таблицы. Исследование опорного плана на оптимальность и вычислительный процесс удобнее вести с помощью специальных таблиц.

Рассмотрим задачу линейного программирования в канонической форме, имеющей единичный неотрицательный базис

Исходные данные внесем в симплексную таблицу (таблица 1.7).

Таблица 1.7 – Симплексная таблица, содержащая исходные данные задачи

i (номер строки)	БП (базисная переменная)	Cб	bi			…			…
		…			…
1 2 … m	…	…	…	1 0 … 0	0 1 … 0	…	0 0 … 1	…	…	…
m+1				0	0	…	0		…

Номер строки записывают в столбец , название базисной переменной в каждой строке соответственно – в столбец БП (базисная переменная). Столбец Сб содержит коэффициенты при базисных переменных целевой функции. Столбец bi – свободные положительные члены системы ограничений. В таблице первые m строк определяются исходными данными задачи, а показатели m+1 строки - строки оценок вычисляют. Элемент (значение целевой функции при данном опорном плане) вычисляют по формуле . Формула () позволяет определить оценки для каждой переменной.

2 Признак оптимальности опорного плана.

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

-  если для некоторого опорного плана все оценки неотрицательны, то такой план оптимален (признак оптимальности опорного плана);

-  если существует такая отрицательная оценка, что в соответствующем столбце нет ни одного положительного элемента, то целевая функция на множестве допустимых планов не ограничена (признак неограниченности целевой функции);

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

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

3 Переход к плану, более близкому к оптимальному.

Переход от одного плана к другому осуществляется исключением из исходного базиса какой-нибудь переменной и включением в него новой переменной. Для определения переменной, включаемой в базис, рассматривают строку оценок и определяют =. Столбец j0 – направляющий столбец и переменную необходимо включить в базис. Для определения переменной, исключаемой из базиса, находят = для всех . Переменная , которой соответствует q, исключается из базиса. Строка i0 называется направляющей. Элемент, располагающийся на пересечении направляющих строки и столбца, называется разрешающим. Для завершения преобразований, ведущих к новому опорному плану, составляют таблицу по следующим правилам:

1)  Элементы строки i0 новой таблицы равны соответствующим элементам направляющей строки предыдущей таблицы, деленным на разрешающий элемент;

2)  В столбцах переменных, входящих в базис, на пересечении строк и столбцов одноименных переменных ставят 1, а все остальные элементы данных столбцов пишут равными нулю.

3)  Остальные элементы таблицы вычисляют по правилу треугольника. Находят три числа: первое число – число в предыдущей таблице, стоящее на месте искомого элемента; второе число – число в предыдущей таблице, стоящее на пресечении строки искомого элемента из новой таблицы и направляющего столбца; третье число – число в новой таблице стоящее на пересечении столбца искомого элемента и строки переменной добавленной в базис.

Эти три числа образуют треугольник:

искомое число = первое число-второе число´третье число

Пример Решить задачу с помощью симплексного метода.

приведем задачу к канонической форме, введя неотрицательные переменные и .

Опорный план задачи примет вид (0;0;15;13).

Внесем исходные данные задачи в симплексную таблицу (таблица 1.8)

Таблица 1.8 – Решение примера

БП	сб	bi	2	3	0	0	q
х1	х2	х3	х4
х3 х4	0 0	15 13	1 3	3 1	1 0	0 1
Dj		z=0	-2	-3	0	0
х2 х4	3 0	5 8		1 0	-	0 1
Dj		z=15	-1	0	1	0
х2 х1	3 2	4 3	0 1	1 0	-	-
Dj		z=18	0	0

Ответ: