Основные положения симплекс-метода

Для решения рассматриваемой задачи вернемся к теории.

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

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

В геометрии есть такое понятие "симплекс". Симплексом тела в k -мерном пространстве называют совокупность k +l его вершин. Так, для плоскости при k = 2 симплексом будут три вершины треугольника, при k = 3— четыре вершины четырехгранника и т. д. С учетом этого понятия аналитический метод решения задачи линейного программирования называют симплекс-методом. Вычисления, обеспечивающие определение значения целевой функции и переменных в одной вершине, называются итерацией.

Аналитическое решение задачи линейного программирования — дело весьма сложное, поэтому подробно описывать его не будем, а изложим лишь те его основные идеи, которые реализованы в Excel.

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

По сравнению с системой (8) в системе (9) введены дополнительные переменные y_i и выполнен переход от системы неравенств к системе уравнений. Следует подчеркнуть, что с точки зрения содержания величина у; равна величине неиспользованного ресурса.

(9)

Систему (3.1.9) перепишем в следующем виде:

(10)

Систему (10) можно представить в виде таблицы, приведенной на рис. 7.

Рис. 7

Таблица (рис. 7) называется симплекс-таблицей и является основной формой решения задачи линейного программирования. В этой таблице все переменные делятся на свободные и базисные. Свободные переменные находятся в ячейках C3:F3, базисные — в ячейках А5:А7. Если переменная свободная, то ее значение равно нулю. На рис. 7 все основные переменные свободные, следовательно,

x ₁ = x ₂ = x ₃ = x ₄ = 0.

Значения базисных переменных приведены в ячейках В5:В7, следовательно,

y ₁= 16; у ₂= 110; у ₃ = 100.

Действительно, если x ₁ = x ₂ = х ₃ = x ₄ = 0, т.е. продукция не выпускается, то величина у неиспользованного ресурса будет равна всему имеющемуся ресурсу, и прибыль при этом, естественно, будет равна 0 (В4 = 0).

Как мы знаем, решения бывают допустимыми и оптимальны­ми. Каждое решение имеет свой признак. Приведем (без дока­зательства, достаточно сложного) эти очень важные признаки, которые нам потребуются в дальнейшем.

Признак 1

Признак 1 определяет, является ли полученное решение допустимым. Согласно этому признаку решение является допустимым, если в столбце свободных членов В5:В7 (целевая функция не рассматривается) все величины неотрицательные.

Признак 2

Признак 2 определяет наличие оптимального решения, при этом возможны 2 варианта:

q Признак 2а

Целевая функция имеет минимальное значение в том случае, когда все элементы в строке целевой функции C4:F4 (свободный член не рассматривается) будут отрицательными. Следовательно, на рис. 7 приведено решение при минимизации целевой функции. Действительно, если ничего не выпускать, то

x ₁ = x ₂ = х₃ = x ₄ = 0,

и при этом прибыль будет F = В4 = 0.

q Признак 2б

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

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

Как мы говорили, поиск оптимального решения заключается в переборе вершин ОДР. При этом переход от одной вершины к другой производится по достаточно сложному алгоритму симплекс-метода, который заключается в обмене переменных. Каждый переход от одной вершины к другой, который, как мы знаем, называется итерацией, состоит в том, что одна базисная переменная приравнивается к нулю, т. е. переходит в свободную, а одна свободная переменная переводится в базисную. На каждой итерации проверяют удовлетворение признаков допустимого и оптимального решений. Такая процедура продолжается до тех пор, пока не будут удовлетворены оба признака. Применительно к нашей задаче последняя симплекс-таблица, полученная после второй итерации, будет иметь вид, приведенный на рис. 8.

Рис. 8

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

, (которые являются базисными);

(так как они свободные);

целевая функция F= 1320.

Таков результат решения задачи. Но это еще не все. Симплекс-таблица является мощным средством для выполнения анализа.

Посмотрим, что еще можно узнать из симплекс-таблицы. На рис. 8 видно, что свободные переменные y ₁ = у ₃= 0, а базисная переменная y ₂ = 26. Это значит, что в оптимальном плане величины неиспользованных трудовых и финансовых ресурсов равны нулю. Следовательно, эти ресурсы используются полностью. Вместе с тем, величина неиспользованных ресурсов для сырья у ₂ = 26, значит, имеются излишки сырья. Вот какие выводы можно сделать с помощью симплекс-таблицы.

И это тоже, оказывается, еще не все. Но об этом чуть позже.

 

Анализ оптимального решения

Жизнь, как правило, не стоит на месте. Как говорится, все течет, все изменяется. В том числе и исходные данные, для которых находилось оптимальное решение. Изменится ли при этом полученное оптимальное решение? Чтобы ответить на этот вопрос, обратимся к нашей модели (8). Посмотрим, как влияет на оптимальное решение изменение двух элементов математической модели:

c_j — прибыли, получаемой при продаже единицы продукции x_j;

b_i — количества располагаемого ресурса.

Анализ влияния изменения c_j

В математической модели (8) целевая функция равна

F = 60 х ₁+70 х ₂+120 х ₃+130 х ₄®mах.

Допустим, прибыль от продажи Прод1 c ₁= 60 изменится на величину D c ₁ и станет

(11)

Рис. 9

При этом строка целевой функции в исходной симплекс-таблице (рис. 7) примет такой вид, как на рис. 9.

В результате поиска опти­мального решения фраг­мент последней симплекс-таблицы будет иметь вид, представленный на рис. 10. Отсюда можно сделать вывод, что к величинам, находящимся в таблице рис. 8, добавляются величины в строке х_j (ячейки B3:F3), умноженные на D c ₁.

Рис. 10

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

Значит, решение будет оптимальным при условии

(12)

Преобразуя (3.2.12), запишем:

и окончательно

-12<D c ₁<40.

Условие (12) определяет пределы изменения До при которых сохраняется структура оптимального плана, т. е. будет выгодно по-прежнему выпускать продукцию x ₁.

В отчетах Excel нижний предел (в примере равный 12) называется допустимое уменьшение, верхний предел, равный 40, — допустимое увеличение.

Если от пределов приращений D c ₁ перейти к пределам значения величины c ₁, то можно записать

(13)

Таким образом, при изменении c ₁ в пределах

(14)

будет по-прежнему выгодно выпускать продукцию x ₁. При этом значение целевой функции будет

F = 1320 +10D с ₁.

Если выполнить аналогичные преобразования с с ₂, с₃, с ₄, то получим -

(15)

И далее по зависимостям, аналогичным (13), не трудно перейти к пределам значений c ₂, с ₃, с ₄.

Анализ влияния изменения b_i

Рассмотрим влияние изменения ресурсов на примере изменения имеющегося количества сырья. При изменении трудовых ресурсов на D b ₁ ограничение для них будет иметь вид:

x ₁+ x ₂+ x ₃+ x ₄< 16+D b ₁,

что запишем в виде

y ₁ = (16+D b ₁) - (x ₁+ x ₂+ x _З+ x ₄).

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

Рис.11 Рис. 12

В соответствии с признаком 1 решение будет допустимым в том случае, если все элементы в столбце свободных членов бу­дут неотрицательными. Значит, из рис. 12 следует

откуда

Тогда для сохранения структуры оптимального плана изменение трудовых ресурсов должно быть в пределах

Аналогично можно получить значения для D b ₂, D b ₃ и записать

(16)

Переход от D b_i к пределам b_i производится по зависимостям

(3.2.17)

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

(18)

Найденные пределы показывают границы, в которых могут изменяться ресурсы, чтобы структура оптимального решения, т. е. номенклатура выпускаемой продукции, остались без изменений. А это означает, что при изменении трудовых ресурсов в найденных пределах оптимальным, т. е. обеспечивающим наибольшую прибыль, является выпуск той же продукции x ₁ и х ₃, но в других количествах. При этом необходимо будет выпускать