II. СИМПЛЕКС-МЕТОД

I. Графическое решение ЗАДАЧИ ЛП

Использование графического метода удобно при решении задач ЛП с двумя переменными. При большем их числе необходимо применение алгебраического аппарата.

Графический способ решения задачи ЛП состоит из 2 этапов:

1. Построение пространства допустимых решений, удовлетворяющих всем ограничениям модели.

2. Нахождения оптимального решения среди всех точек пространства допустимых решений.

 

 

Пространство допустимых решений ограничено отрезками прямых, которые соединяются в угловых точках А, В, С, D, Е и F. Любая точка, расположенная внутри или на границе области, ограниченной ломаной ABCDEF, является допустимым решением, т.е. удовлетворяет всем ограничениям. Поскольку пространство допустимых решений содержит бесконечное число точек, необходима некая процедура поиска оптимального решения.

Для того чтобы найти оптимальное решение, необходимо определить направление возрастания целевой функции z = 5х₁ + 4х₂. Мы можем приравнять z к нескольким возрастающим значениям, например 10 и 15. Эти значения, подставленные вместо z в выражение целевой функции, порождают уравнения прямых; для значений 10 и 15 получаем уравнения прямых 5х₁ + 4х₂ = 10 и 5х₁ + 4х₂ =15. Целевая функция может возрастать до тех пор, пока прямые, соответствующие возрастающим значениям этой функции, пересекают область допустимых решений. Точка пересечения области допустимых решений и прямой, соответствующей максимально возможному значению целевой функции, и будет точкой оптимума.

На рис. видно, что оптимальное решение соответствует точке С. Эта точка является местом пересечения прямых (1) и (2), поэтому ее координаты х₁ и х₂ находятся как решение системы уравнений, задающих эти прямые:

 

Решением этой системы будет х₁ = 3 и х₂ = 1.5, при этом значение целевой функции равно z = 5х₁ + 4х₂ = 21. Полученное решение означает, что для фирмы оптимальным выбором будет ежедневное производство 3 т черной краски и 1.5 т – синей с ежедневным доходом в 21000 $.

 

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

Основное свойство симплекс-метода заключается в том, что решение задачи ЛП осуществляется итерационно. На каждой итерации алгоритм переходит к новой угловой точке, которая потенциально может улучшить значение целевой функции. Этот процесс перехода от одной угловой точки к следующей заканчивается, когда дальнейшее улучшение значений целевой функции невозможно.

Последовательность действий, выполняемых в симплекс-методе.

1. Находится начальное допустимое базисное решение.

2. На основе условия оптимальности определяется вводимая переменная. Если вводимых переменных нет, вычисления заканчиваются.

3. На основе условия допустимости выбирается исключаемая переменная.

4. Методом Гаусса-Жордана вычисляется новое базисное решение. Переход к п. 2.