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

 В строке F таблицы   есть отрицательные элементы, (-3) – наибольший из них по модулю, поэтому столбец  разрешающий (выделен). В разрешающем столбце   есть положительные элементы (в данном случае все). Вычисляем симплексные отношения 12/4,  8/4,   8/4 (столбец ). Здесь оказались две  строки   с минимальным  симплексным отношением  , выбираем в качестве разрешающей одну из них, например  (выделена). Элемент 4 на пересечении строки   и столбца разрешающий. Далее выполняем симплексное преобразование таблицы    по правилам  1) - 5) и переходим к   меняем  местами   заменяем разрешающий элемент 4 на  1/4; остальные  элементы  разрешающей строки, 1  и  8, делим на 4; остальные элементы разрешающего столбца, 4, 4 и (-3), делим на (-4); все оставшиеся элементы, не принадлежащие ни строке   ни столбцу  пересчитываем по правилу  четырехугольника. Например, -2 в строке  F  заменяем  на    3 в столбце  – на   Теперь таблица   и опорный план  текущие,  и все операции начиная с шага 2 повторяются с таблицей   В строке   F  таблицы   еще  есть отрицательный элемент  в разрешающем столбце   есть положительные элементы 2 и 1/4.  После вычисления симплексных отношений ( почему в строке   вместо отношения стоит прочерк?) и выбора разрешающего  элемента  2  надо выполнить симплексное  преобразование таблицы   

т. е. перейти  к   При этом целесообразно  начать вычисления с элементов строки  F: если они окажутся  неотрицательными (в данном случае так и будет: получатся  ), то   будет заключительной, ей соответствует оптимальный опорный план. Чтобы выписать этот план  и  , нужен только столбец свободных членов таблицы, «внутренние» элементы   можно не вычислять. Итак, в данной задаче   единственный оптимальный  план  и 

   При втором  варианте выбора разрешающей строки в  вместо   получается другая цепочка таблиц:   где

                               

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

      Пример 10 показывает, что при применении симплекс-метода к вырожденной задаче нескольким  последовательным  таблицам может соответствовать один и тот же опорный план ( во второй  цепочке). Оказывается, что в других (более сложных) вырожденных задачах возможна следующая ситуация: нескольким таблицам  соответствует один и тот же опорный план и на некотором шаге очередная из этих таблиц повторяет одну из предыдущих – происходит зацикливание. В теории ЛП разработаны различные варианты уточнения основного  алгоритма симплекс-метода, позволяющие избежать зацикливания, но при решении практических задач они применяются очень редко, так как их использование сильно замедляет вычислительный процесс, а вероятность зацикливания ничтожно мала.

     В заключение приведем пример  решения задачи о ресурсах с помощью симплекс-метода.

     Пример 11. В таблице 4 представлены исходные данные задачи о ресурсах:

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

                                                                                                                        Таблица 4        

                                                                                                                  

     Решение. Обозначим     планируемые объемы производства по видам продукции. Математической моделью будет задача ЛП в стандартной (записана слева) или канонической (справа) форме:

                                   

                                           

                                                ,