Алгоритм симплекс-метода для задачи на максимум
Алгоритм симплекс-метода для задачи на максимум отличается от алгоритма для задачи на минимум только знаками индексной строки коэффициентов в целевой функции 
, а именно:
На шаге 2: 
:
На шаге 3 
. Целевая функция является неограниченной сверху на допустимом множестве.
На шаге 4: 
.
Пример решения задачи симплекс-методом
Решить задачу, записанную в виде (15).
Составим симплексную таблицу:
| 
| 
| |
| L | 0 | 1 | 2 |
| 3 | 1 | 1 |
| 1 | 
| 1 |
Так как коэффициенты строки целевой функции неотрицательны, то начальное базисное решение 
не является оптимальным. Значение целевой функции для этого базиса L=0.
Выбираем ведущий столбец – это столбец, соответствующий переменной 
.
Выбираем ведущую строку. Для этого находим 
. Следовательно, ведущая строка соответствует переменной 
.
Проводим преобразование симплексной таблицы, вводя переменную 
в базис и выводя переменную 
из базиса. Получим таблицу:
|
|
| 
| |
| L | -2 | 2 | -2 |
|
| 2 | 
| -1 |
|
| 1 |
| 1 |
Одна итерация метода завершена. Переходим к новой итерации. Полученная таблица неоптимальная. Базисное решение, соответствующее таблице, имеет вид 
. Значение целевой функции на этом базисе L= -2.
Ведущий столбец здесь – столбец, соответствующий переменной 
. Ведущая строка – строка, соответствующая переменной 
. После проведения преобразований получим симплексную таблицу:
|
|
|
|
|
|
| |
| L | 
| 
| 
|
|
| 
| 
|
|
|
| 
| 
|
|
Еще одна итерация завершена. Переходим к новой итерации.
Строка целевой функции не содержит положительных значений, значит, соответствующее базисное решение 
является оптимальным, и алгоритм завершает работу.
Метод искусственного базиса
Симплекс-метод применяется для решения задач ЛП, представленных в специальной форме:
(16)
Характерная особенность задачи (16) – известное базисное допустимое решение
Чтобы применить симплекс-метод для решения задачи ЛП в произвольной форме, необходимо привести эту задачу к виду (16), т. е. выделить начальное допустимое базисное решение. Для этого в симплекс-метод вводят подготовительный этап. Один из методов для реализации подготовительного этапа называется методом искусственного базиса и состоит в следующем [1,2,3].
Вычислительная схема метода искусственного базиса.
Шаг 1. Приводим задачу ЛП к канонической форме с неотрицательными правыми частями 
:
(17)
Шаг 2. В каждую i-ю строку ограничений (17) вводим искусственную неотрицательную переменную 
и строим вспомогательную задачу ЛП вида:
(18)
В задаче (18) 
– допустимое базисное решение и задача (18) легко может быть сведена к виду (16). Для этого целевую функцию необходимо выразить через свободные переменные 
:
|
|
|
Шаг 3. Для вспомогательной задачи (18) строим симплексную таблицу
| b | 
| … | 
| |
| 
| 
| … | 
|
| 
| 
| … | 
|
| … | … | …………………. | ||
| 
| 
| … | 
|
и находим оптимальное решение вспомогательной задачи с помощью симплекс-метода.
Шаг 4. Если 
и все переменные 
являются небазисными, то m переменных из 
войдут в базис и система ограничений, соответствующих симплексной таблице, будет иметь вид
(19)
Так как переменные 
, то их исключили из системы (19), не нарушив при этом равенств. Выражая целевую функцию основной задачи 
через небазисные переменные 
системы (19), получим исходную задачу (17) в виде (16).
Шаг 5. Если , но в базисе остались искусственные переменные 
, для которых 
(вырожденный случай), то проводим для каждой искусственной переменной из базиса следующее преобразование симплексной таблицы.
Выбираем ведущим столбцом столбец такой переменной 
, для которой элемент индексной строки 
, а элемент столбца 
. В этом случае строка искусственной переменной будет ведущей и после стандартного преобразования симплексной таблицы (шаг 6 из прямого симплекс-метода) искусственная переменная выведется из базиса. В результате получим симплексную таблицу, соответствующую шагу 4.
|
|
|
Шаг 6. Если 
, то допустимого решения в исходной задаче (17) не существует (не могут все искусственные переменные быть равными нулю в задаче (18), а значит система ограничений задачи (17) несовместна) – процесс решения исходной задачи (17) завершается.
Дата добавления: 2021-12-10; просмотров: 21; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!