Симплекс-метод решения задач линейного программирования.

Симплекс-метод – один из наиболее эффективных методов численного решения задач ЛП. Суть понятия «симплекс» заключается в следующем. Для тела в k -мерном пространстве симплексом называется множество, состоящее из k +1 вершин этого тела. Так, при k = 2, т.е. на плоскости, симплексом будут вершины треугольника; при k = 3 симплексом являются вершины четырехгранника, например тетраэдра, и т.д. Такое название методу дано по той причине, что в его основе лежит последовательный перебор вершин ОДЗП с целью определения координат той вершины, в которой функция цели имеет кстремальное значение.

Решение задачи с помощью симплекс-метода разбивается на два основных этапа. На первом этапе находят одно из решений, удовлетворяющее системе ограничений . Системы, в которых переменных больше, чем ограничений N > m, называются неопределенными. Они приводятся к определенным системам (N = m) путем приравнивания к нулю N-m каких-либо переменных. При этом остается система m уравнений с m неизвестными, которая имеет решение, если определитель системы отличен от нуля. В симплекс-методе вводится понятие базисных переменных, или базиса. Базисом называется любой набор из m таких переменных, что определитель, составленный из коэффициентов при этих переменных в m-ограничениях, отличен от нуля. Остальные N-m переменных называются небазисными, или свободными переменными. Если принять, что все небазисные переменные равны нулю, и решать систему ограничений относительно базисных переменных, то получим базисное решение.

В системе из m уравнений с N неизвестными общее число базисных решений при N > m определяется числом сочетаний

Базисное решение, в котором все x_i0, i = 1,m, называется допустимым базисным решением. Таким образом, первый этап решения, используя симплекс-метод, завершается нахождением допустимого базисного решения, хотя бы и неудачного.

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

1) базисные переменные и функция цели выражаются через небазисные переменные;

2) по определенному правилу выбирается та из небазисных переменных, изменение значения которой способно улучшить значение F(x) , и она вводитя в базис;

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

4) базисные переменные и функция цели выражаются через новые небазисные переменные, и повторяются операции 2) и 3).

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

Рассмотрим пример, относящийся к задачам организационно-экономического управления и помогающий уяснить содержание симплекс-метода.

Пример 1. На приобретение оборудования для нового участка выделено 20 тыс. y.e. Оборудование должно быть размещено на площади, не превышающей 72 м². Может быть заказано оборудование двух видов: 1) оборудование стоимостью 5 тыс. y.e., занимающее площадь 6 м² и дающее 8 тыс. ед. продукции за смену; 2) оборудование стоимостью 2 тыс. y.e., занимающее площадь 12 м² и дающее за смену 4 тыс. ед. продукции. Найти оптимальный вариант приобретения оборудования, обеспечивающий максимум общей производительности участка, используя симплекс-метод.

Обозначим неизвестное количество оборудования первого и второго видов соответственно через x₁ и x₂. Функция цели может быть записана следующим образом: F(x) = 8x₁ + 4x₂(max). Ограничения по площади: 6x₁ +12x₂≤72; ограничения по стоимости: 5x₁ + 2x₂≤20 ; ограничения на знак переменных x₁≥0 ; x₂≥0.

Разделим коэффициенты первого из ограничений на 6 и приведем ограничения к виду равенств, вводя дополнительные переменные x₃ и x₄:

x₁ + 2x₂ + x₃ =12, (1)

5x₁ + 2x₂ + x₄ = 20 . (2)

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

1-й шаг. Для решения симплекс-методом выберем в качестве базисных переменных (БП) x₂ и x₄, так как определитель, составленный из коэффициентов при этих переменных в ограничениях задачи отличен от нуля.

Тогда x₁ и x₃ будут небазисными переменными (НП). Выразим базисные переменные и F(x) через небазисные.

(3)

x₄ = 20 - 2x₂ - 5x₁. (4)

x₄ = 8 - 4x₁ + x₃. (5)

Тогда

F(x) = 8x₁ + 4x₂ = 24 + 6x₁ - 2x₃ . (6)

На каждом шаге решения задачи симплекс-методом НП приравниваются к нулю, следовательно, БП и F(x) будут равны свободным членам в соответствующих выражениях:

x₁ = 0, x₃ = 0, x₂ = 6, x₄ = 8, F(x) = 24.

Это решение соответствует координатам вершины A ОДЗП на рис. 1. Оптимальность решения проверяется по выражению F(x) для функции цели. Переменная x₃ входит в это выражение с отрицательным коэффициентом; если вводить x₃ в базис на следующем шаге, то она примет положительное значение, и от числа 24 некоторая величина будет вычитаться, т.е. значение F(x) уменьшится. Если же вводить в базис на следующем шаге x₁, то значение функции цели увеличится, т.е. улучшится.

Применяя симплекс-метод, из базиса исключают ту переменную, которая раньше обратится в нуль при введении в базис x₁. Анализируя (3) и (5), определяем, что из базиса следует исключить x₄. На следующем шаге местами поменяются переменные x₁ и x₄.

2-й шаг симплекс-метода. x₁ и x₂ – базисные переменные, x₃ и x₄ – небазисные. Выразим базисные переменные и F(x) через небазисные переменные. Из (5) следует

x₁=2+(1/4)x₃-(1/4)x₄ (7)

Рис. 1. Графическая интерпритация к примеру 1, используя симплекс-метод.

Подставив (7) в (3), получим

x₂=5-(5/8)x₃+(1/8)x₄

Тогда F(x) = 8x₁ + 4x₂ = 36 - (1/2)x₃ -(3/4)x₄ . В результате x₃ = x₄ = 0 (как небазисные), x₁ = 2, x₂ = 5, F = 36 . Это решение соответствует координатам вершины В на рис. 1. Найденное решение симплекс-методом будет оптимальным, улучшить значение F(x) нельзя, так как переменные x₃ и x₄ входят в выражение для функции цели с отрицательными коэффициентами.

Таким образом, применяя симплекс-метод, нашли, что максимальная производительность участка 36 тыс. ед. продукции за смену будет обеспечена при закупке 2 ед. оборудования первого вида и 5 ед. оборудования второго вида. Дополнительные переменные x₃ и x₄ имеют смысл неиспользованных ресурсов. В данном примере все ресурсы по площади и по стоимости использованы полностью (x₃ = x₄ = 0).