Симплекс-метод.

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

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

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

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

Симплексом называется простейший выпуклый много­гранник при данном числе измерений. В частности, при - произвольный треугольник, - произволь­ный тетраэдр.

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

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

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

(1)

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

(2).

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

Будем считать, что все уравнения системы (2) линейно независимы, т.е. ни одно из них нельзя получить как линейную комбинацию других. В противном случае линейно зависимые уравнения можем отбросить. И кроме того, эта система совместна, т.е. среди урав­нений системы нет противоречивых. Ясно, что при этих предположениях число уравнений меньше числа пере­менных , поскольку при система (2) имеет единственное решение, что исключает всякую оптимиза­цию; при не выполняются сделанные выше пред­положения.

Выразим первые переменных через остальные с помощью уравнений (2):

(3).

Переменные называются базисными, а вектор - базисом; - свободные переменные.

Используя соотношения (3), можно выразить ли­нейную целевую функцию (1) через свободные переменные:

(4).

Процесс оптимизации начнем с некоторого начально­го (опорного) решения, например при нулевых значе­ниях свободных переменных. Тогда получим

(5).

При этом целевая функция (4) принимает значение .

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

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

Пусть теперь среди коэффициентов формулы (4) хотя бы один отрицательный, например . Это означает, что при увеличении переменной целевая функ­ция уменьшается по сравнению со значением , соответ­ствующим решению (5). Поэтому в качестве нового опорного выбирается решение при следующих значениях свободных параметров:

(6).

При этом базисные переменные, вычисляемые по формулам (3), равны

(7).

Если все коэффициенты неотрицательны, то можно увеличивать неограниченно; в этом случае не существует оптимального решения задачи. Однако на практике такие случаи, как правило, не встречаются. Обычно среди коэффициентов имеются отрицательные, а это влечет за собой угрозу сделать некоторые пе­ременные в (7) отрицательными из-за большого значения . Следовательно, переменную можно увеличивать лишь до тех пор, пока базисные переменные остаются неотрицательными. Это и является условием выбора значения . Его можно записать в виде

(8).

Среди всех отрицательных коэффициентов найдем наибольший по модулю. Пусть его значение равно , а соответствующее ему значение равно . Тогда из (8) получим максимально возможное значение переменной на данном шаге оптимизации: , и новое опорное решение запишем в виде

, ,

, (9).

целевая функция при этих значениях проектных параметров равна

(10).

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

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

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