Симплексный метод решения задачи

В исходную систему неравенств, представляющих собой ограничения на все три вида сырья

(11.1)

(11.2)

(11.3)

введем дополнительные переменные с коэффициентами = 1 и с нулевым коэффициентом в целевую функцию. Дополнительные переменные рассматриваются как показатели недоиспользования имеющегося сырья (ресурсов). Тогда неравенства (11) можно записать как систему равенств

(12.1)

(12.2)

(12.3)

Целевая функция при этом примет вид

(13)

где , , - количество недоиспользованного ресурса 1-го, 2-го и 3-го видов сырья.

Примем , , как базисные переменные, а Х₁ и Х₂ – как небазисные переменные. Это связано с тем, что в допустимом множестве, представляющем собой многоугольник ОАВСD (см. рис. 1), в самом начале решения все известно лишь в начале осей координат, где Х₁=0; Х₂ =0. Поскольку сырье еще не запущено в производство и ресурсы оказались не тронутыми, то можно записать: =7200, =9900, =12600. Именно с этой точки и начинается процедура решения, а первый допустимый план принимает вид: Х₁=0; Х₂ =0; =7200, =9900, =12600.

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

Первая таблица (таблица 1) рассматривается как запись условий задачи и первого варианта решения.

Таблица 1. Первый план решения задачи

Cj	Базис. перем.	План
Х1	Х2	Х3	Х4	Х5
	Х3
	Х4
	Х5		4,80
Zj - Cj		-45	-27

В первом столбце таблицы записываются стоимости С_j целевой функции. Во втором – базисные переменные , , . Их стоимости С_j как вида продукта - нулевые. Начиная с третьего столбца, первая строка делится пополам. В нижней части этой строки последовательно записываются все переменные Х_i , а в верхней - все коэффициенты целевой функции (13) при этих переменных. Затем в следующих нижних трех строках под этими переменными записывается матрица коэффициентов левой части системы уравнений (12). Нижняя строка называется индексной. Каждый ее элемент находится по формуле:

(14)

где (15)

- коэффициенты таблицы i-той строки и j-того столбца.

Поскольку в первой таблице Х₁=0; Х₂ =0 , то z_j =0 и, следовательно, коэффициенты: поэтому в нижней строке все коэффициенты целевой функции (13), ранее записанные в верхней строке, оказываются со знаком минус.

Вектор – столбец описывает выпуск соответствующего вида продукта (соответствующий технологический способ). Элементы индексной строки характеризуют эффективность технологического способа по отношению к сложившейся структуре производства. Если задача решается на max, то оценка (+) в индексной строке показывает, на сколько уменьшается прибыль при включении в план соответствующего технологического способа. При (-) оценке наблюдается увеличение прибыли при включении в план этого способа. Если же задача решается на min, то результаты оказываются обратными.

Таким образом, при решении задач на max отсутствие в индексной строке (-) оценки свидетельствует о том, что получено оптимальное решение. В противном случае возможно улучшение плана. Тогда выбирают наибольшую по абсолютной величине (-) оценку и в новый план вводят технологический способ, соответствующий этой оценке. Столбец с наибольшей по абсолютной величине (-) оценкой называется ключевым. В первом плане решения задачи (таблица 1) ключевым является столбец Х₁.

Для удобства восприятия процедуры обработки симплекс-таблиц выделим вариативную часть таблицы 1 и продемонстрируем этап обработки данных на примере (см. табл. 1.1) упрощенного аналога первой таблицы. В этой таблице выделим жирным шрифтом ключевой столбец h, который соответствует столбцу продукта Х₁ с индексом j = 2. Далее построчно разделим элементы столбца j = 1 свободных членов (столбец план в табл. 1) на построчно соответствующие элементы ключевого столбца. Строка r (табл.1.2) с наименьшим частным выделяется жирным шрифтом и называется ключевой. Эта строка (i = 1) указывает на то, какая из переменных должна быть выведена из последующего плана (в данном случае переменная Х₃), а вместо нее в новый план должна быть введена переменная ключевого столбца (переменная Х₁ ).

Элемент, лежащий на пересечении ключевых столбца и строки, называется главным ключевым элементом (ГКЭ).

Содержимое каждой клетки вариативной части матрицы (табл.1.1) обозначим как К_ij . Тогда содержимое ГКЭ для первой таблицы . Представление информации в форме таблицы 1.1 дает возможность подготовить рекуррентные формулы для расчета К_ij для последующих таблиц.

Таблица 1.1. Упрощенный аналог таблицы 1

	Столбцы j
	2 = h
Строки i	1 = r
	9900		4	0	1	0
	12600	4,80	6	0	0	1
	0	-45	-27	0	0	0

Заполнение второй симплекс-таблицы (табл. 2) начинается с ключевой строки по рекуррентной формуле:

. (16)

Например, в табл. 1.1 r – ключевая строка (i=1=r); h – ключевой столбец (j=2=h). Тогда - старое содержимое клетки; - (ГКЭ); - новое значение содержимого клетки, которое в табл. 2 записывается вместо 7200. Для клетки ГКЭ формула (16) примет вид:

.

Таким образом, в клетках ГКЭ результат всегда будет равен 1.

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

(17)

Например, в табл. 1 содержимое клетки K_i,j = K_4,3 = - 27. Для расчета нового содержимого этой клетки потребуются следующие данные из табл. 1:

К_r,j=K_1,3=2; K_i,h=K_4,2=-45; ; K_i,j = K_4,3 = - 27. (18)

Подставив исходные данные (18) в формулу (17), получим число:

(19)

которое запишется во вторую симплекс-таблицу 2. Таким же образом заполняются остальные клетки второй симплекс-таблицы.

Таблица 2. Второй план решения задачи (вторая симплекс-таблица)

Cj	Базис. перем.	План	Х1	Х2	Х3	Х4	Х5
	Х1			0,4	0,2
	Х4			1,6	-1,2
	Х5			4,08	-0,96
Zj - Cj			-9

В результате решения второго плана получено значение целевой функции F(X) = 64800, располагаемое в индексной строке столбца «План» и определяемое как

. (20)

В таблице 2 в индексной строке столбца Х₂ оказалось отрицательное число (-9), что свидетельствует о возможности улучшения плана за счет введения в новый план переменной Х₂. Этот столбец выделяется как ключевой h.

Построчно разделим элементы столбца свободных членов, образующих «План» в табл. 2, на соответствующие элементы ключевого столбца. Ключевой строкой r (табл. 2) с наименьшим частным оказалась строка переменной Х₄ , что означает необходимость вывода из последующего плана этой переменной. Вместо нее в новый план должна быть введена переменная Х₂.

Далее, как и в предыдущем случае, заполняется таблица 3.

Теперь в индексной строке последней таблицы 3 нет отрицательных чисел, что свидетельствует о том, что экстремум (в данном случае max) целевой функции достигнут.

Все результаты расчетов находятся в столбце «План» и в индексной строке таблицы 3. В соответствии с этими результатами оптимальный план по выпуску продуктов должен составлять: = 1125 единиц продукта 1-го вида и = 787 – целых единиц продукта 2-го вида. При этом прибыль предприятия с учетом округления до целых единиц продукта составит: условных единиц (у.е.). Если учитывать дробную часть продукта, то (у.е.).

Таблица 3. Третий план решения задачи (третья симплекс-таблица)

Cj	Базис. пер.	План	Х1	Х2	Х3	Х4	Х5
	Х1				0,5	-0,25
	Х2	787,5			-0,75	0,625
	Х5				2,1	-2,55
Zj - Cj	71887,5			2,25	5,625

Недоиспользованный ресурс (остаток) составил Х₅ = 2475 единиц сырья 3-го вида.

В последних трех клетках индексной строки записаны двойственные оценки ресурсов трех видов сырья: . Смысл двойственные оценки состоит в том, что при увеличении сырья первого вида на одну единицу целевая функция вырастит на 2,25 у.е., при увеличении сырья второго вида на одну единицу целевая функция вырастит на 5,625 у.е. Эти виды сырья являются дефицитными и их нужно приобретать в первую очередь. Двойственная оценка сырья третьего вида равна нулю ( ). Приобретение этого вида сырья не имеет смысла, поскольку имеется недоиспользованный ресурс: Х₅ = 2475 единиц сырья 3-го вида и его приобретение не даст увеличения целевой функции.

Двойственная задача

С каждой прямой задачей линейного программирования, представленной моделью (1.1) – (1.3), можно связать двойственную или сопряженную модель. В общем виде индексная запись такой двойственной задачи будет иметь вид:

; (21.1)

; (21.2)

. (21.3)

Запишем исходную прямую задачу (3.1) – (3.5) оптимального планирования продуктов :

; (22.1)

; (22.2)

; (22.3)

; (22.4)

, . (22.5)

Двойственная модель по отношению к модели (3.1) – (3.5) примет вид:

; (23.1)

; (23.2)

; (23.3)

. (23.4)