Линейное программирование. Некоторые примеры экономических задач, приводящих к модели линейного программирования. Геометрическая интерпретация и графическое решение задачи ЛП, страница 11

     Эти теоремы показывают, что при решении задач ЛП фактически можно рассматривать только опорные планы, а не все допустимые. В примерах 7 – 9  рассматривались изменения значений целевой функции и базисных переменных при возрастании одной из свободных переменных. Из анализа этих изменений ясно, как надо выбирать разрешающий элемент «текущей» симплексной таблицы, чтобы улучшить соответствующий опорный план, и как определить, получен ли уже оптимальный план и существуют ли вообще оптимальные планы. Такое   последовательное  улучшение опорных планов - главная идеяосновного алгоритма численного решения задач ЛП, получившего название симплекс-метода.

     Для применения симплекс-метода задачу ЛП надо привести к каноническому виду (см. п.2). Кроме того, предполагается, что уже найдена одна из допустимых

симплексных таблиц – начальная симплексная таблица. Ниже будет показано, как можно найти такую таблицу или установить, что задача ЛП не имеет  допустимых планов.

Алгоритм   симплекс-метода

      Шаг 1. Объявить начальную симплексную таблицу и соответствующий опорный план текущими.

      Шаг 2 (Проверка оптимальности). Просмотреть строку F  текущей таблицы (кроме свободного члена).

      а) Если в строке  F нет отрицательных элементов (все , то текущий опорный план – оптимальный; если  при этом нет и нулевых элементов, то оптимальный план - единственный, если нулевые элементы есть, то  множество оптимальных планов бесконечно.

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

     Шаг 3 (Выбор разрешающего элемента). Просмотреть  разрешающий столбец текущей таблицы (кроме элемента строки F).

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

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

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

     Шаг 5. Перейти к шагу 2.

     Результатом применении симплекс-метода будет цепочка допустимых симплексных таблиц   и соответствующих опорных планов   такая, что   В большинстве задач ЛП значения целевой функции  строго  возрастают и решение задачи завершается  через конечное число шагов на таблице, удовлетворяющей требованиям шага 2а)  или шага  3а). Особые случаи всегда связаны с вырожденностью решаемой задачи. Задача ЛП называется вырожденной, если у нее есть опорные планы, в которых кроме всех свободных переменных равны нулю и некоторые базисные. Разберем подробно простейший из таких особых случаев.

     Пример 10. Решить симплекс-методом задачу ЛП   с ограничениями  

     Решение. Начальная таблица   находится  так же, как в предыдущих примерах. Одна из возможных цепочек состоит из трех таблиц:     

                     

     Начальной   таблице       соответствует  опорный план