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

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

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

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

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

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

Таблица 8.18

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

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

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

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

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

Задача шага 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.Перепишем соотношения (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

При этом в очередной базис можно включить либо Х₁,либоХ₂,ли­бо Х₃. На основании правила 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

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

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

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

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

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

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