Улучшение опорного плана. Формулы пересчета симплекс-таблиц

Затем заполняем  элементы столбцов векторов базиса и  по правилу треугольника вычисляем  элементы остальных столбцов. В результате в табл. 4 получаем новый опорный план X=(0; 8; 20; 0; 0; 96) и коэффициенты разложения векторов  через базисные векторы  и соответствующие значения  и 

Проверяем, является ли данный опорный план оптимальным  или нет. Для этого рассмотрим 4-ю строку, табл. 4. В этой строке среди чисел  нет отрицательных. Это означает, что найденный опорный план является оптимальным и 

Следовательно, план выпуска продукции, включающий изготовление 8 изделий В и 20 изделий С, является оптимальным. При данном плане выпуска изделий полностью используется сырье I и II видов и остается неиспользованным 96 кг сырья III вида, а стоимость производимой продукции равна 400 руб.

Оптимальным планом производства продукции не предусматривается изготовление изделий А. Введение в план выпуска продукции изделий вида А привело бы к уменьшению указанной общей стоимости. Это видно из 4-й строки столбца вектора P₁,где число 5 показывает, что при данном плане включение в него выпуска единицы изделия А приводит лишь к уменьшению общей величины стоимости на 5 руб.

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

Таблица 5

i	Базис	Сб	Р0	9	10	16	0	0	0
				P1	P2	P3	p4	p5	Р6
1 2 3 4 1 2 3 4 1 2 3 4	P4 р5 p6 P4 p3 p6 P2 p3 p6	0 0 0 0 16 0 0 16 0	360 192 180 0 72 24 108 384 8 20 96 400	18 6 5 -9 9 3/4 11/4 3 1 1/4 5/4 5	15 4 3 -10 9 1/2 3/2 -2 1 0 0 0	12 8 3 -16 0 1 0 0 0 1 0 0	1 0 0 0 1 0 0 0 1/9 -1/18 -1/6 2/9	0 1 0 0 -3/2 1/8 -3/8 2 -1/6 5/24 -1/8 5/3	0 0 1 0 0 0 1 0 0 0 1 0

 

Пример  2

Найти максимум функции  при условиях

Решение:  

Систему уравнений задачи запишем в векторной  форме:

где

Так как  среди векторов  имеется три единичных вектора, то для данной задачи можно непосредственно найти опорный план. Таковым является план Х=(0, 0, 20, 24; 0; 18). Составляем симплексную таблицу (табл. 6) и проверяем, является ли данный опорный план оптимальным.

Таблица 6

i	Базис	Сб	Р0	2	-6	0	0	5	0
				P1	P2	P3	p4	p5	Р6
1 2 3 4	p3 P4 p6	0 0 0	20 24 18 0	-2 -1 3 -2	1 -2 -1 6	1 0 0 0	0 1 0 0	1 3 -12 -5	0 0 1 0

Как видно из табл. 6, исходный опорный план не является оптимальным. Поэтому переходим к новому опорному плану. Это можно сделать, так как в столбцах векторов P₁и p₅, 4-я строка которых содержит отрицательные числа, имеются положительные элементы. Для перехода к новому опорному плану введем в базис вектор p₅ и исключим из базиса вектор p₄. Составляем таблицу итерации.

Таблица 7

i	Базис	Сб	Р0	2	-6	0	0	5	0
				P1	P2	P3	p4	p5	Р6
1 2 3	p3 P5 p6	0 5 0	12 8 114 40	-5/3 -1/3 -1 -11/3	5/3 -2/3 -9 8/3	1 0 0 0	-1/3 1/3 4 5/3	0 1 0 0	0 0 1 0

Как видно из табл.7, новый опорный план задачи не является оптимальным, так как в 4-й строке столбца вектора P₁ стоит отрицательное число -11/3. Поскольку в столбце этого вектора нет положительных элементов, данная задача не имеет оптимального плана.[1].

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

 

1. http://www.mathelp.spb.ru
2. Хемди А. Таха Глава 3. Симплекс-метод // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.:«Вильямс», 2007. — С. 95-141. — ISBN 0-13-032374-8
3. Акулич И.Л. Глава 1. Задачи линейного программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. — 319 с. — ISBN 5-06-002663-9
4. Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 5-8459-0857-4