3.2. Симплекс-метод решения задач линейного программи­рования

Поскольку, как было показано в п. 3.1 решение задачи линейного программирования находится в одной из крайних (угловых) точек ОДЗ, важным вопросом является изучение не системы неравенств (4), а соответствующей системы уравнений AX = B, решение которой дает угловые точки ОДЗ.

Если уравнения системы АX = B линейно независимы, то система имеет множество решений при n > m и единственное решение при n = m. При решении задачи линейного программирования симплекс-методом всегда будет выполняться n > m, поэтому для получения некоторого одного решения, «лишние» n – m переменных приравниваются нулю.

Если приравнять к нулю n – m произвольных переменных (например, переменные x_m+1, x_m+2, …, x_n) и, решив систему, найти значения оставшихся m переменных (x₁, x₂, …, x_m), то такое решение называется базисным.

Если нулю приравнять некоторые другие n – m переменных – получим другое базисное решение. Любое базисное решение, у которого все переменные неотрицательные называется допустимым базисным решением.

Переменные, которые были приравнены нулю, называются небазисными. Оставшиеся т переменных, значение которых получены из решения системы, называются базисными.

Допустимое базисное решение представляет собой угловую вершину ОДЗ.

Решение задачи симплекс-методом сводится к направленному перебору смежных друг с другом угловых точек, которые представляют собой допустимые базисные решения.

Сформулируем в общем виде алгоритм симплекс-метода:

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

2: Выделение исходного базисного решения (по возможности из стандартной формы). То есть определение тех переменных n – m переменных, которые приравниваются нулю и нахождение значений оставшихся базисных переменных.

3: Определение, является ли полученное базисное решение оптимальным, если да, то решение окончено, иначе переходим к шагу 4.

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

5: Использование эквивалентных преобразований методом Жордана-Гаусса для нахождения нового допустимого базисного решения. Переход к шагу 3.

Чтобы привести задачу линейного программирования к стандартной форме необходимо:

1. Убедиться, что во всех ограничениях правые части b_i неотрицательны. Если есть отрицательные правые части ограничений, такие ограничения нужно умножить на –1 (при этом учесть, что в ограничениях типа  или  знак ограничения изменится на противоположный).

2. К левой части ограничений типа  нужно прибавить новую, дополняющую переменную S, которая уравнивала бы левую и правую часть и показывала бы насколько левая часть ограничения меньше правой.

То есть ограничение

a_i1x₁ + …+ a_inx_n £ b_i

в стандартном виде будет выглядеть так:

a_i1x₁ + …+ a_inx_n + S_i = b_i.

3. Из левой части ограничений типа  нужно вычесть новую, избыточную переменную e, которая уравнивала бы левую и правую часть и показывала бы насколько левая часть ограничения больше правой.

То есть ограничение

a_i1x₁ + …+ a_inx_n  b_i

в стандартном виде будет выглядеть так:

a_i1x₁ + …+ a_inx_n – e_i = b_i.

Дополняющие переменные S и избыточные e будем называть вспомогательными, в то время, как переменные x – основными.

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

В качестве исходных базисных переменных в задачах с ограничениями  удобно брать переменные S₁, …, S_n.

Реализацию алгоритма симплекс-метода проиллюстрируем на следующем примере.

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

Таблица 3.1 – Исходные данные к примеру 3.2

Ресурсы	Шкаф	Стол	Стул
Древесина	8 м2	6 м2	1 м2
Отделочные работы	4 часа	2 часа	1,5 часа
Столярные работы	2 часа	1,5 часа	0,5 часа

В распоряжении фабрики ежедневно имеется 48 м² древесины, 20 часов времени на участке отделки, 8 часов на столярном участке. Известно также, что потребность в шкафах и стульях неограниченна. Однако не более 5 столов может быть продано ежедневно. Цены реализации продукции следующие: шкаф – 60 у.е., стол – 30 у.е., стул – 20 у.е.

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

Построим математическую модель. Обозначим х₁ – количество производимых шкафов, х₂ – число столов, х₃ – количество стульев.

Задача линейного программирования примет вид:

1) Целевая функция

2) Система ограничений

3) Ограничения на знак переменных

х₁, х₂, х₃ 0 .

Преобразуем модель к стандартной форме:

(5)

В качестве исходного базиса, очевидно, удобно выбрать переменные S₁, S₂, S₃, S₄, так как очевидно базисное решение:

S₁ = 48, S₂ = 20, S₃ = 8, S₄ = 5.

Дальнейшие шаги алгоритма симплекс-метода (шаг 3, 4, 5) удобно представить в специальной таблице, называемой симплекс-таблицей.

Построим первую симплекс-таблицу. В первом столбце укажем переменные, образующие базис, во втором столбце (c_j) – коэффициенты целевой функции, при переменных, входящих в базис. В третьем столбце (b_i) – правые части ограничений. В остальных столбцах (x₁, x₂, …, S₄) записываются коэффициенты целевой функции и коэффициенты в ограничениях при соответствующих переменных.

Последняя строка симплекс-таблицы () особая. Она получается из целевой функции следующим образом. В целевой функции все переменные переносятся в левую часть. Получается . Полученные коэффициенты и правая часть целевой функции (0) записывается по аналогии с коэффициентами ограничений: в столбце b_i – правая часть целевой функции, которая изначально равна нулю, в остальных столбцах – обратные значения коэффициентов целевой функции (–с_j) при соответствующих переменных.

Таким образом, исходная симплекс-таблица имеет вид:

Таблица 3.2 – Исходная симплекс-таблица к примеру 3.2

Базис	cj		х1	х2	х3	S1	S2	S3	S4	с.о.
			60	30	20	0	0	0	0
S1	0	48	8	6	1	1	0	0	0	48:8 = 6
S2	0	20	4	2	3/2	0	1	0	0	20:4 = 5
S3	0	8	2	3/2	1/2	0	0	1	0	8:2 = 4
S4	0	5	0	1	0	0	0	0	1	–
		0	-60	-30	-20	0	0	0	0	max

Заметим, что столбец отражает не только правые части ограничений, он также показывает значение базисных переменных S₁, …, S₄. (Напомним, что значение небазисных переменных х₁, х_2, х₃ равно нулю.) Тот же столбец в строке целевой функции отражает значение целевой функции при данном базисном решении. Ведь, действительно, целевая функция Z при х₁ = х₂ = х₃ = 0, тоже равна нулю.

Последняя строка таблицы называется строкой целевой функции или индексной строкой.

Признаком оптимальности в задаче на максимум является наличие в индексной строке всех неотрицательных значений. В нашем примере индексная строка содержит отрицательные элементы (–60, –30, –20). Следовательно, текущее базисное решение неоптимально и его нужно улучшать.

В случае если решается задача на минимум, можно использовать один из двух вариантов:

1) умножить целевую функцию на –1 и решать задачу не на минимум, а на максимум;

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

Определив, что текущее базисное решение неоптимально, нужно выяснить какую из небазисных переменных х₁, х_2, х₃ нужно включить в базис. Коэффициент –60 в индексной строке показывает, что при введении в базис переменной x₁ в базис со значением 1, целевая функция улучшится на 60 единиц. При введении в базис x₂ со значением 1, ЦФ улучшится на 30 единиц. При введении в базис x₃ – на 20.

Наилучший прирост целевой функции дает введение в базис переменной x₁.

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

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

Столбец с переменной, которая собирается войти в базис называется разрешающим столбцом. В нашей задаче разрешающим, является столбец х₁.

Выясним, какая переменная выйдет из базиса и с каким значением переменная х₁ войдет в базис. Эти задачи взаимосвязанные. Вывести из базиса нужно такую переменную, чтобы став равной нулю, она не привела к тому, что какая-то из остальных базисных переменных станет отрицательной (недопустимой). Нужно, чтобы приравняв одну из базисных переменных нулю, остальные базисные переменные, в том числе и та, которая входит в базис, оставались неотрицательными.

Поэтому для определения того, какая переменная покинет базис, необходимо рассчитать отношения , где b_i – значения коэффициентов правых частей ограничений в столбце b_i симплекс-таблицы, a_ij – значения разрешающего столбца ( j):

48:8 = 6; 20:4 =5; 8:2 = 4.

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

Из полученных неотрицательных симплексных отношений выбираем наименьшее. В нашем случае наименьшее симплексное отношение получается в строке 3) S₃, следовательно, переменная S₃ покинет базис, а данная строка будет разрешающей строкой.

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

Вместо S₃ в третью строку новой симплекс-таблицы войдет х₁ с коэффициентом c_j равным 60, т.к. 60 – коэффициент целевой функции при x₁.

Разрешающий столбец , который сейчас имеет вид

, нужно преобразовать к виду ,

то есть к такому же виду, какой имел столбец S₃ в таблице 3.2.

Воспользуемся методом Жордана-Гаусса.

На месте разрешающего элемента нужно получить единицу. Следовательно, всю разрешающую строку (кроме столбца с_j) нужно разделить на разрешающий элемент.

Строку 3) х₁ разделим на 2, она примет вид:

3)

4

1

3/4

1/4

0

0

1/2

0

Строку 4) S₄ переносим из первой симплекс-таблицы во вторую без изменений, так как в столбце х₁ уже находится нулевой элемент.

Строку 1) S₁ необходимо обновить таким образом, чтобы в столбце х₁ был коэффициент 0. Для этого из строки S₁ следует вычесть разрешающую строку х₁, умноженную на 8.

1) S1 8х1 S1-8х1	48	8	6	1	1	0	0	0
	-32	-8	-6	-2	0	0	-4	0
	16	0	0	-1	1	0	-4	0

Со строкой 2) S₂ поступаем аналогично (из строки S₂ следует вычесть 4 строки ):

2) S2 4х1 S2-4х1	20	4	2	3/4	0	1	0	0
	-16	-4	-3	-1	0	0	-2	0
	4	0	-1	1/2	0	1	-2	0

Для обновления строки к ней необходимо прибавить 60 строк .

	0	-60	-30	-20	0	0	0	0
	240	60	45	15	0	0	30	0
	240	0	15	-5	0	0	30	0

Заполним вторую симплекс-таблицу.

Таблица 3.3 – Вторая симплекс-таблица к примеру 3.2

Базис	cj		х1	х2	х3	S1	S2	S3	S4	с. о.
			60	30	20	0	0	0	0
1) S1	0	16	0	0	-1	1	0	-4	0	–
2) S2	0	4	0	-1	1/2	0	1	-2	0	8
3) х1	60	4	1	3/4	1/4	0	0	1/2	0	16
4) S4	0	5	0	1	0	0	0	0	1	–
		240	0	15	-5	0	0	30	0	max

Из таблицы видно, что полученное новое базисное решение стало лучше предыдущего: выпуск 4 шкафов (x₁ = 4) позволяет получить уже 240 у.е. дохода. Однако, это решение не оптимальное. Это видно из индексной строки таблицы: требование оптимальности не выполнено, так как имеется отрицательный элемент (–5). Будем улучшать план. В качестве разрешающего столбца теперь выбираем столбец , так как он содержит отрицательный элемент (–5). Разрешающую строку выберем, как и ранее, используя симплексное отношение (16 не делим на (-1), так как отрицательные значения не рассматриваются):

4: = 8; 4: = 16.

Из полученных симплексных отношений выбираем наименьшее, следовательно, в качестве разрешающей строки выбираем вторую строку. Переменная х₃ вытесняет S₂ из базиса. Вновь используем метод Жордана-Гаусса, добиваемся того, чтобы столбец х₃ имел вид:

.

Заполним итоговую симплекс-таблицу.

Таблица 3.4 – Итоговая симплекс-таблица к примеру 3.2

Базис	cj		х1	х2	х3	S1	S2	S3	S4
			60	30	20	0	0	0	0
1) S1	0	24	0	-2	0	1	2	-8	0
2) х3	20	8	0	-2	1	0	2	-4	0
3) х1	60	2	1	5/4	0	0	-1/2	3/2	0
4) S4	0	5	0	1	0	0	0	0	1
		280	0	5	0	0	10	10	0

В строке целевой функции все коэффициенты при переменных неотрицательны, следовательно, мы нашли оптимальное из допустимых решений. Базис образуют переменные , то есть для получения максимального дохода следует выпускать продукцию и , так как переменная не входит в базис (а значит равна нулю). В столбце имеем оптимальные значения базисных переменных: x₁ = 2, x₃ = 8. Значения вспомогательных переменных S₁ = 24, S₄ = 5 можно интерпретировать следующим образом: 24 м² древесины осталось не использовано, спрос на столы не удовлетворен на 5 единиц. Тот факт, что S₂ = S₃ = 0, говорит о том, что все ресурсы по участку отделки и столярному участку использованы полностью.

Целевая функция нашей задачи имеет вид:

.

Для определения ее максимального значения подставим в нее значения переменных, образующих оптимальное базисное решение:

Это же значение видно в последней симплекс-таблице на пересечении индексной строки и столбца .

Таким образом, наибольший доход 280 у.е. получается при производстве 2 единиц товара (шкафы) и 8 единиц товара (стулья).

Проанализируем полученное решение.

Каждая из вспомогательных переменных S₁, …, S₄ соответствовала одному из ограничений и показывала, насколько левая часть ограничения (фактические затраты ресурсов) меньше правой части (их запаса). Таким образом, в тех ограничениях, где левая часть равна правой (запас ресурсов исчерпан полностью), соответствующая вспомогательная переменная S будет равна нулю. Вспомним, что такое ограничение называется связующим и отражает критический (дефицитный) ресурс.

Запасы ресурсов на участке отделки и столярном участке использованы полностью S₂ = S₃ = 0. Древесина же осталось неиспользованной (S₁ = 24). Если увеличить запас древесины (с 48 до, например, 68), приведет ли это к улучшению решения? Нет. Поскольку она и так осталась лишняя увеличение правой части несвязующего ограничения приведет к тому, что увеличится значение соответствующей вспомогательной переменной (станет S₁ = 44), но оптимальный план не изменится.

Дефицитные же ресурсы являются ценными в том смысле, что их увеличение приведет к возможности улучшения оптимального плана. Оценка ценности данных ресурсов приведена в строке целевой функции : при указанных переменных стоят коэффициенты 10. Эти величины называются теневыми ценами и отражают степень важности ресурса с точки зрения его вклада в оптимальный результат. Теневая цена показывает, насколько изменится значение целевой функции, если изменить правую часть соответствующего ограничения на 1 единицу. Теневые цены рассчитывается только для ресурсов, которые использованы полностью, то есть для связующих ограничений.

В строке целевой функции коэффициент 5 при свободной основной переменной x₂ носит название снижающей оценки и показывает, насколько ухудшится целевая функция, если мы примем решение производить хотя бы 1 стол. Снижающую оценку можно интерпретировать и с другой стороны: она показывает, насколько нужно увеличить цену на столы, чтобы их производство стало выгодно, и они вошли в базис.