Лекция: Сформулируйте критерий отсутствия решения в алгоритме Р-метода

Алгоритмдвойственногосимплекс-метода:

1)выбирают разрешающую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов;

2)выбирают разрешающий столбец по наименьшему по абсолютной величине отношению элементов L строки к отрицательным элементам разрешающей строки;

3) пересчитываютсимплекснуютаблицупоправиламобычногосимплекс-метода;

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

35 В каком случае к решению ЗЛП необходимо применять двухэтапный симплекс-метод?

Рассмотрим задачу

= 0,4X1+ 0,3X2 + 0,1X3 + 0,1X5 + 0,2X6 (3.71)

2X2 + 2X3 + 4X4 + X5 = 150

X1 + X2 + 2X5 = 200 (3.72)

X1 + X3 + 2X6 = 300

; j = 1,...,6 (3.73)

Так как ограничения (3.72) рассматриваемой ЗЛП уже имеют вид строгих равенств, то для приведения ее к каноническому виду достаточно только изменить знак функции на противоположный и рассмотреть задачу нахождения –0,4X1 – 0,3X2 –
– 0,1X3 – 0,1X5 – 0,2X6 (3.74) при тех же ограничениях (3.72)–(3.73).

Рассмотрим расширенную матрицу А системы уравнений (3.72)

Так как матрица А не содержит единичной подматрицы порядка 3, то она не является К-матрицей ЗЛП и, следовательно, к задаче (3.71)–(3.73) не может быть применен симплекс-метод.

Рассмотрим метод отыскания исходного опорного плана (К-матрицы)- метод искусcтвенного базиса.

ПЕРВЫЙ ЭТАП – РЕШЕНИЕ ВСПОМОГАТЕЛЬНОЙ ЗАДАЧИ

ВТОРОЙ ЭТАП – РЕШЕНИЕ ИСХОДНОЙ ЗАДАЧИ

36 Какие ЗЛП не могут быть решены симплекс-методом?

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