СИМПЛЕКС-МЕТОД ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
(Идея симплекс-метода)
Чтобы решить задачу ЛП надо представить ее в каноническом виде:
(4.1)
(4.2)
С помощью метода Жордана-Гаусса преобразуем систему (2) и выделим базисные переменные.
Если 
, то система имеет единственное решение, подставляем его в целевую функцию (1) и получаем решение задачи ЛП.
Если 
, то выражаем базисные переменные через свободные. Пусть базисные переменные – 
,…, 
,свободные переменные – 
.
Получаем преобразованную задачу:
(4.3)
(4.4)
В этой задаче:
1. Система ограничений выражена через свободные переменные;
2. Целевая функция выражена через свободные переменные;
3. Все 
;
4. Все 
.
Это условие может быть обеспечено только в том случае, если система ограничений (4.2) имеет хотя бы одно неотрицательное решение.
Одно из решений системы (4.4) получается, если в ней свободные неизвестные приравнять к 0. Получаем базисное решение:
Симплекс-метод состоит в переходе от одного базисного решения к другому базисному решению, такому, что целевая функция F будет увеличиваться. При этом рассматриваются коэффициенты целевой функции.
Рассмотрим коэффициенты при свободных неизвестных в целевой функции:
(4.3)
Возможны следующие случаи:
Случай 1. Среди коэффициентов целевой функции (3) нет положительных:
|
|
|
Тогда если увеличивать любую свободную переменную, то целевая функция (4.3) будет уменьшаться.
Т.к. ищем максимальное решение, то уже найденное решение и будет оптимальным. Но оно может быть не единственным, если в целевой функции (4.3) есть коэффициенты, равные 0.
Случай 2. Среди коэффициентов целевой функции (4.3) найдется хотя бы один положительный, например 
.
Положим в уравнениях (4.3) и (4.4) все свободные переменные равными нулю, кроме 
.
Тогда система (4.4) и уравнение (4.3) примут вид:
(4.5)
(4.6)
Если 
увеличивать, то будет увеличиваться и целевая функция (4.5), но возможность роста определяется системой (4.6) и зависит от знаков коэффициентов 
.
Возможны следующие случаи:
Случай 1. Предположим, что среди коэффициентов нет положительных, т.е., 
,тогда любая переменная 
, 
либо не изменяется (если 
), либо растет (если 
), с ростом , оставаясь положительной.
Случай 2. Предположим, что среди коэффициентов есть положительные, тогда требование неотрицательности переменных приводит к неравенствам вида:
.
Это означает, что: 
, для тех индексов 
, у которых 
.
Максимальное значение, которое может принимать переменная 
, равно минимальному из отношений 
.
|
|
|
Допустим, что оно достигается при 
, т.е.:
Элемент 
называется разрешающим элементом. 
уходит в разряд базисных переменных, а 
становится свободной переменной.
Далее целевую функцию (4.3) и систему (4.4) записываем через новые свободные переменные.
И снова рассматривается новая целевая функция, если какую-нибудь переменную можно увеличить, то весь процесс повторяется. Если все коэффициенты при переменных (в целевой функции) не положительны, то найдено оптимальное решение.
Дата добавления: 2021-11-30; просмотров: 21; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!