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

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

Задача 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 имеются не­базисные переменные, коэффициенты при которых отрицательны, сле­дует выбрать переменную (обозначим ее через X j) с наибольшим абсо­лютным значением стоящего перед ней коэффициента, т. е. ту перемен­ную, которая обеспечивает наибольшее удельное приращение значения целевой функции. В случае, когда все небазисные переменные строки О имеют положительные или нулевые коэффициенты, оптимальное ре­шение можно считать полученным.

В соответствии с правилом 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

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

Не нашли, что искали? Воспользуйтесь поиском: