Описание симплекс-метода

Все нужные базовые ответы комфортно приобретать в таблице Гаусса.

Последнюю строчок, которую назовём индексной строчком и заполняем её коэффициентами , вольный член


Любая итерация осуществляется известными элементарными преобразованиями Гаусса:

Выбирается разрешающий (ведущий) коэффициент . разрешающий (ведущий) коэффициент нельзя брать в последней строчке.

Разрешающая строка делится на , а разрешающий столбец заменяется единичным – с 1 вместо .

Все остальные элементы блока пересчитываются по формулам:


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

Наряду с этим нужно смотреть за тем, дабы новые свободные члены оставались неотрицательными.

Предположим, что ЗЛП (1.3) есть невырожденной, а базовое ответ (1.5) – допустимым.

Обозначим его:

тогда таблица имеет следующий вид

Наряду с этим .

В базе симплекс-способа (СМ) лежит следующая теорема.

Теорема оптимальности ответа.

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

В случае если коэффициенты индексной строчки имеют различные символы, то допустимое базовое ответ не есть оптимальным как в задаче на максимум, так и в задаче на минимум и направляться переходить к второму базовому ответу (замыслу).

Очередное допустимое базовое ответ (замысел) получается тем же методом, но с учетом некоторых изюминок.

Разглядим задачу на максимум; задача на минимум решается по подобной схеме.

1) Разрешающий столбец нужно выбирать так, дабы не покупать лишних хороших коэффициентов в индексной строчке (не смотря на то, что это время от времени неизбежно, см. теорему оптимальности).

Время от времени в качестве разрешающего берут столбец с большим коэффициентом индексной строки.

2) Неверный выбор разрешающей строки может привести к недопустимому ответу.

Верный выбор строчка сост. в следующем.

Предположим, что выбран разрешающий столбец с номером – .

Составим отношения

свободных участников уравнений к хорошим коэффициентам разрешающего столбца (индексная строка тут не участвует).

Отыщем

.

Строчок с этим числом нужно вычислять разрешающей.

В случае если таких строчков пара, то выбор среди них равнодушен.

3) В случае если ведущий (разрешающий) коэффициент выбран верно, то соответствующие элементарные преобразования приводят лишь к допустимому ответу.

При необходимости процедура нахождения допустимого базового ответа повторяется до получения оптимального ответа, если оно существует.

Ситуации, в которых получение оптимального ответа

Недостижимо

1) Предположим, что полученное БР задачи на максимум не оптимально: к примеру, в индексной строчке имеется один хороший коэффициент. Тем самым выяснена переменная, которую, направляться ввести в базис.

Вместе с тем коэффициенты базового столбца неположительные. Следовательно, ввести эту переменную в базис запрещено: это приведет к недопустимому ответу.

При таких условиях задача не имеет решения по обстоятельству неограниченности ЦФ в ОДР.

2) Предположим, что при поиске первого базового ответа наталкиваемся на недопустимые ответы и, не удаётся взять допустимого ответа.

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

Лекция 2 Симплекс-способ


Также читать:

Понравилась статья? Поделиться с друзьями: