- •3. Методы получения оптимальных решений злп
- •3.1. Графический метод решения злп
- •3.1.1. Алгоритм решения графическим методом
- •3.1.2. Особые случаи решения злп графическим методом
- •3.2. Симплекс-метод решения злп
- •3.2.1. Аналитический симплекс-метод
- •3.2.2. Табличный симплекс-метод
- •Исходная таблица для симплекс-метод.
- •Исходная таблица для симплекс-метода
- •Итоговая таблица с оптимальным решением
- •3.2.3. Метод искусственного базиса (м-метод)
- •Исходная таблица для решения задачи м-методом
- •Промежуточный результат м-метода
- •Итоговая симплекс-таблица
- •3.2.4. Особые случаи решения злп симплекс-методом
- •Выбор разрешающей строки
- •Исходная таблица с базисом х3, х4
- •Решение с базисом х2, х3
3.2. Симплекс-метод решения злп
3.2.1. Аналитический симплекс-метод
Для случая, когда число переменных более 3-х, геометрический метод становится невозможным. В этом случае применяются другие методы, среди которых наиболее универсальным является симплексный метод (симплекс-метод), разработанный американским учёным Дж. Данцигом. Алгоритм решения можно представить следующим образом:
-
Систему ограничений (2.5) приводят к каноническому виду и составляют расширенную матрицу этой системы.
-
Определяют ранг матрицы и, используя метод Жордана – Гаусса, выражают базисные переменные через свободные переменные. Обязательным условием является положительность свободных членов (постоянных). Целевую функцию, стремящуюся, например, к min, также выражают через свободные переменные.
-
Приравнивая все свободные переменные к нулю, получают начальное опорное решение (базисное решение) и соответствующее значение целевой функции.
-
Далее решение разбивается на ряд шагов (этапов, итераций), заключающихся в том, что от исходного базиса переходят к другому базису с таким расчётом, чтобы значение целевой функции уменьшалось или, по крайней мере, не увеличивалось (для задачи на min).
Идею метода проследим на примере.
Пример 3.4.
.
1. Система приведена к каноническому виду (см. раздел 2).
2. Ранг основной и расширенной матрицы r = 3, тогда в соответствии с теоремой Кронекера-Капелли система совместна и базис относительно переменных х1, х2, х3 уже выделен. Свободные члены после выражения базисных переменных остаются положительными.
Целевая функция выражена через свободные переменные х4 и х5 и стремится к min.
3. Приравниваем свободные переменные х4 и х5 к нулю и получим начальное опорное решение
для которого . Все вышеперечисленные действия представляют собой 0-й шаг. Обращаем внимание, что свободные переменные равны нулю, а базисные переменные приняли положительные значения.
4. На 1-м шаге попытаемся уменьшить значение f (), что можно добиться только увеличением значения х5, так как оно стоит со знаком « – ». Увеличим значение х5 так, чтобы х1, х2, х3 не стали отрицательными, оставив х4 = 0. Из 2-го уравнения системы следует, что х5 можно увеличить до 2. Т. о., получаем новое решение = (5,0,1,0,2) и f () = – 2 уменьшилось.
На 2-м шаге за свободные переменные принимают х2 и х4 (нулевые значения в ), а остальные переменные за новый базис х1, х3, х5 (ненулевые значения в ). Для этого из 2-го уравнения системы выражают х5 через х2 и х4. Базисные переменные х1, х3 и целевую функцию f () также выражаем через новые свободные переменные х2 и х4.
.
Для уменьшения будем увеличивать х4. Из системы видно, что при условии неотрицательности х3 (х2=0) значение х4 можно увеличить до х4= (третье уравнение). Тогда новое допустимое решение =(,0,0,,) и f () = – .
3-й шаг. Свободные переменные х2 и х3, а базисные х1, х4, х5. Из третьего уравнения выражаем х4 через х2 и х3, а в первом и третьем уравнениях делаем преобразования с учетом выражения х4 через х2 и х3. Кроме того, преобразовываем значение целевой функции с учетом выражения х4 через х2 и х3. Получим:
Т. к. в последнее выражение целевой функции все переменные входят с положительными коэффициентами, то её наименьшее значение достигается при х2 = 0, х3 = 0. Это означает что решение = (,0,0,,) является оптимальным, т.е. f min() = – .
Анализируя ход решения, т.е. минимизацию, можно сделать выводы:
-
Если все коэффициенты при свободных неизвестных в выражении для целевой функции положительны (неотрицательны), то значение , равное значению свободного члена (константы), является минимальным, а базисное решение – оптимальным.
-
Если в целевой функции имеется свободная переменная с отрицательным коэффициентом, а в системе при этом неизвестном все коэффициенты положительны, то задача решения не имеет.
-
Если в целевой функции имеется свободная переменная, коэффициент при которой отрицателен, и в системе уравнений при этой переменной также имеется хотя бы один отрицательный коэффициент, то оптимальное решение может быть найдено посредством проведения итераций.