8.7. Симплексный метод общие положения

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

Когда рассматриваемая модель содержит т уравнений ограничений, вычислительная процедура симплексного методаза­ключается в следующем:

Шаг 1.Выберем тпеременных, задающих допустимое пробное ре­шение. Исключим эти переменные из выражения для целевой функции.

Шаг 2.Проверим, нельзя ли за счет одной из переменных, прирав­ненных вначале к нулю, улучшить значение целевой функции, прида­вая ей отличные от нуля (причем только положительные) значения. Если это возможно, перейдем к шагу 3. В противном случае прекра­тим вычисления.

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

Шаг 4.Разрешим систему т.уравнений относительно переменных, вошедших в новое пробное решение. Исключим эти переменные из вы­ражения для целевой функции. Вернемся к шагу 2.

Симплексная вычислительная процедура формальна, и ее использо­вание не обязательно должно связываться с конкретным содержанием задачи. Ниже приведено несколько типичных задач, решаемых сим­плексным методом.

Задача 8.9.Корма трех видовВ₁, В₂,В₃ содержат определенное количество питательных веществ А₁, А₂, A₃. Цены, по которым поку­паются эти корма, различны. Требуется составить кормовой рацион, со­стоящий из указанных кормов, так, чтобы в нем было не менее заданных ко­личеств питательных веществ и чтобы он был самым дешевым.

Задача 8.10.Есть три вида станков: А₁, А₂, А₃. На этих станках по­следовательно обрабатываются детали четырех видов: В₁, В₂, В₃, б₄. Известно сколько часов каждая деталь изготавливается на каждом стан­ке, сколько времени может проработать каждый станок и какая при­быль может быть получена от продажи детали каждого типа. Требуется найти оптимальный план работы станков, чтобы получить максималь­ную прибыль.

Задача 8.11.Имеются автомобили трех типов А_1;A₂, A₃, рабо­тающие на перевозке однородного груза у трех потребителей В₁, В₂, В₃. Известна производительность каждого автомобиля у каждого по­требителя и себестоимость использования автомобиля. Требуется так закрепить автомобили за потребителями, чтобы была наименьшая се­бестоимость (максимальная производительность) и др.

Вычислительная процедура симплексного метода

Чтобы получить представление о сущности симплексного метода, рассмотрим следующую задачу.

Задача 8.12.В авторемонтном предприятии, выпускающем неодно­родную продукцию, руководитель стремится определить, какими должны быть уровни производства для каждого узла и агрегата в течение некото­рого наперед заданного периода. Эти уровни ограничены технологиче­скими и другими «внутренними» для данного предприятия условиями, приведенными в табл. 8.18.

В рамках этих ограничений руководство данного предприятия пыта­ется оптимизировать целевую функцию.

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

Z=4X₁+5X₂+9X₃+llX₄->max (8.76)

Таблица 8.18

Технологические условия производства продукции

Показатели	Количество на единицу продукции для технологических процессов				Имеется в наличии всего
	№1	№2	№3	№ 4
Трудовые ресурсы	1	1	1	1	≤15
Материала типа А	7	5	3	2	≤120
Материала типа В	3	5	10	15	≤100
Доход с единицы продукции	4	5	9	11	max
Объем выпускаемой продукции	X1	Х2	Хз	X4	-

при ограничениях

Обозначим через Х₀значение целевой функции и введем в рассмот­рение свободные переменные. В результате получим следующую систе­му уравнений:

где все переменные могут принимать лишь неотрицательные значение.

Введение в рассмотрение переменной Х₀позволяет записать выражение для целевой функции в виде уравнения.

Задача шага 1 заключаетсяв том, чтобы выбрать первоначальное допустимое решение системы уравнений (8.78). Существует множество таких решений, однако удобнее всего начать с Х₀=0, Х₅=15, Х₆ = 120, Х₇ = 100при нулевых значениях остальных переменных. Другими словами, строится первое пробное решение с помощью только свободных переменных. Назовем его исходным базисным решением, а переменные X₀ , Х₅ , Xg, Х₇- базисными переменными или сокращенно базисом. Остальные переменные логично назвать внебазисными (небазисными) переменными.

Так как под X₀понимается в задаче прибыль, то предложенное пробное решение является не очень выгодным. Но его можно улучшить. Обратим внимание на коэффициенты при тех переменных, которые фигурируют в строке 0 и которые в предложенном выше пробном вари­анте не являются базисными (т. е. на коэффициенты при Х₁, Х₂, Х₃, Х₄). Каждый коэффициент в этой строке определяет величину положи­тельного приращения при увеличении значения соответствующей переменной на единицу. Таким образом, каждый коэффициент в строке О определяет положительное (если перед ним стоит знак минус) или отри­цательное (если перед ним стоит знак плюс) приращение Х₀при увели­чении на единицу соответствующей небазисной переменной.

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

Правило 1 (максимизация).Если в строке 0 имеются не­базисные переменные, коэффициенты при которых отрицательны, сле­дует выбрать переменную (обозначим ее через Xj) с наибольшим абсо­лютным значением стоящего перед ней коэффициента, т. е. ту перемен­ную, которая обеспечивает наибольшее удельное приращение значения целевой функции. В случае, когда все небазисные переменные строки О имеют положительные или нулевые коэффициенты, оптимальное ре­шение можно считать полученным.

В соответствии с правилом 1 в базис следует ввести переменную Х₄, так как каждое единичное приращение Х₄приводит к увеличению зна­чения X₀на 11. Увеличение значения Х₄возможно лишь за счет уменьшения значений базисных переменных в каждой строке, содержа­щей Х₄с положительным коэффициентом. Так, например, при увеличе­нии Х₄на единицу:

значение Х₅должно быть уменьшено на 1, чтобы удовлетворялось ограничение, приведенное в строке 1;

значение Х₂должно быть уменьшено на 2, чтобы удовлетворялось ограничение, приведенное в строке 2;

значение Х₇должно быть уменьшено на 15,чтобы удовлетворялось ограничение, приведенное в строке 3.

Сколь велико должно быть значение Х₄,чтобы значение одной из выбранных вначале базисных переменных достигло своей нижней гра­ницы, т. е. нуля. Такой предел для Х₄равняется 100/15 = 6,67, приХ₇= 0. Следовательно, в базис нужно включить Х₄, исключив из него Х₇.

Обобщая вышеизложенное, сформулируем следующее правило для шага 3.

Правило 2:

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

б) выберем отношение с наименьшим значением - в очередном пробном решении X jприравнивается именно этому значению. Пусть наименьшее из всех отношений правых частей (8.78) к соответствующим коэффициентам при Xjсоответствует переменной Х_к, входившей в предыдущее решение; тогда в очередном пробном решении следует по­ложить Х_к =0.

Результаты вычислений приведены в табл. 8.19.

Таблица 8.19

Итерация 1

Базисные перемен­ные	Рассматри­ваемое пробное решение	Коэффици­ент при Х4	Значения отношений	Минималь­ное значе­ние	Следующее пробное решение
Хо	0	-11	-	-	-
X5	15	1	15	-	-
X6	120	2	60	-	-
X7	100	15	100/15	6,67	Х4= 6,67; Х7= 0

Шаг 4.Перепишем соотношения (8.78) таким образом, чтобы в стро­ке 3 коэффициент при Х₄был равен единице, а в строках 0,1 и 2 - нулю. Процедуру, с помощью которой это достигается, называют операцией замены базиса. Сначала разделим обе части уравнения в строке 3 на ко­эффициент приХ₄, т. е. на 15

Обратим в нули коэффициенты при X₄в строках 0,1,2,действуя по следующей схеме:

1. умножить строку 3 на 11 и результат прибавить к строке 0;

2. умножить строку 3 на - 1 и результат прибавить к строке 1;

3. умножить строку 3 на - 2 и результат прибавить к строке 2.

В результате получим

Полученное уравнение (8.80) эквивалентно уравнению (8.78). Его удобство заключается в том, что, полагая X₁=X₂=...= Х₆ = Х₇ = 0, сразу можно определить значения переменных для нового пробного ба­зисного решения.X₀=220/3; Х₅=25/3; Х₆=320/3; Х₄=20/3. Прибыль для нового пробного решения равняется прибыли при предыдущем проб­ном базисе плюс значение новой базисной переменной, умноженной на удельный вклад новой базисной переменной, в приращении прибыли:

Смысл правила 2 становится теперь более ясным. Если бы вместо Х₇из первоначального базиса исключить Х₅(или Х₆), тоХ₄, Х₇, Х₆(или Х5) приняли бы отрицательное значение, что противоречит предположению о том, что ни одна из переменных не может быть отри­цательной.

Итерация2.Завершив первую итерацию, следует вернуться к шагу 2, с тем, чтобы определить, является ли полученное решение опти­мальным. Если оптимум еще не достигнут, необходимо в соответствии с симплексным алгоритмом приступить к следующей итерации. Согласно правилу 1, возможность улучшить решение существует.

Таблица 8.20

Итерация 2

Базисные перемен­ные	Рассматри­ваемое пробное решение	Коэффици­ент при X,	Значения отношений	Минималь­ное значе­ние	Следующее пробное решение
Хо	220/3	-9/5	-	-	-
Х5	25/3	4/5	125/12	125/12	X1 = 125/12 Х6 = 0
Х6	320/3	33/5	1600/99	-	-
Х4	20/3	1/5	100/3	-	-

При этом в очередной базис можно включить либо Х₁,либоХ₂,ли­бо Х₃. На основании правила 1 выбор падает наX₁,так как эта пере­менная обеспечивает наибольшее удельное приращение для значения це­левой функции.

В соответствии с табл. 8.20 в очередном пробном решении Х₅сле­дует заменить на X₁. С учетом произведенной замены необходимо пре­образовать систему уравнений (8.80). Вначале выполним нормировку ко­эффициента при Х₁в строке 1:

Затем исключим X₁из уравнений в строках 0, 2, 3, действуя по сле­дующей схеме:

1. умножить строку 1 на 9/5 и результаты сложить со строкой 0

2. умножить строку 1 на -33/5 и результаты сложить со строкой 2;

3. умножить строку 1 на -1/5 и результаты сложить со строкой 3.

В результате получим:

Третье пробное базисное решение дало следующие результаты:

Итерация3.Завершив вторую симплекс-итерацию, видим (стро­ка 0), что решение может быть улучшено за счет Х₃. Определим, какая переменная должна быть исключена из базиса. Пронормируем коэффициентX₃в строке 3 путем деления обеих частей соответствующего уравнения на 7/12 и исключим Х₃из уравне­ний в строках 0, 1 и 2 следующим образом:

1. умножить строку 3 на 11/12 и результат сложить со строкой 0;

2. умножить строку 3 на 5/12 результат сложить со строкой 1;

3)умножить строку 3 на 13/12 и результат сложить со строкой 2.

В результате получим:

В строке 0 все коэффициенты положительны, следовательно, согласно правилу 1, полученное решение является оптимальным (табл. 8.21).

Таблица 8.21

Итерация 3

Базисные перемен­ные	Рассматри­ваемое пробное решение	Коэффици­ент при Х3	Значения отношений	Минималь­ное значе­ние	Следующее пробное решение
Хо	1105/12	- 11/12	-	-	-
X1	125/12	5/12	25	-	-
Х6	455/12	-13/12	-	-	Хз= 55/7,
Х4	55/12	7/12	55/7	55/7	Х4=0

Коэффициенты при переменных в окончательном варианте строки 0 иногда называют скрытыми издержками. Каждый коэффициент опреде­ляет отклонение значения целевой функции от оптимального при увели­чении значения соответствующей небазисной переменной на единицу. Таким образом, предприятие будет иметь прибыль 695/7 при выпуске продукции по технологическому процессу 1 и 3.

В кратком изложении симплексный метод состоит в следующем:

Шаг 1.Выбирается исходный базис.

Шаг 2.Используется правило 1. Если рассматриваемое пробное ре­шение не является оптимальным, осуществляется переход к шагу 3. В противном случае вычисления прекращаются.

Шаг 3.Выполняется процедура, предписанная правилом 2.

Шаг 4.Сменяется базис, после чего возвращаются к шагу 2.