Симплекс-метод с естественным базисом

Симплекс-метод

 

Лекции 6, 7

Симплекс-метод с естественным  базисом

 

      Симплекс –метод основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает при условии, что задача имеет оптимальный план и каждый опорный план является невырожденным.

         Этот переход возможен, если известен какой-либо опорный план.

      В этом случае каноническая задача линейного программирования должна содержать единичную подматрицу порядка m

     Тогда очевиден первоначальный опорный план( неотрицательное базисное решение системы ограничений КЗЛП).

   Рассмотрим задачу, для которой это возможно.

   Пусть требуется найти максимальное значение функции

   

при условиях 

 

 

 

 

 

 

 

 

 

 

     Здесь                                            -заданные постоянные числа, причем

    Перепишем ЗЛП в векторной форме: найти максимум функции                                   

 

    при условиях

 

 

 

   Здесь

   Так как                                              ,

   то по определению опорного плана

                                                               ,

    где последние компоненты вектора  равны нулю, является опорным планом

   Опорный план называется невырожденным, если он содержит m положительных компонент. В противном случае он называется вырожденным.

         План, при котором целевая функция ЗЛП принимает свое максимальное

   (минимальное ) значение , называется оптимальным

    Этот план определяется системой единичных векторов , которые образуют базис m-векторного пространства.

         Проверка на оптимальность опорного плана происходит с помощью критерия оптимальности.

Признак оптимальности.

 

   1)Опорный план ЗЛП является оптимальным, если

 

 

 

для любого                   .

    2)Если для некоторого j=k

    и среди чисел  

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

   3)Если же для некоторого k выполняется условие              , но среди чисел          есть положительные, т.е. не все            , то можно получить новый опорный план, для которого значения целевой функции 

                                              .

   На основании признака оптимальности делаем вывод о целесообразности перехода к новому опорному плану.

Симплекс-таблица

Симплекс-таблица

 

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

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

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

   Здесь                            , т.е.

 

 

    Значение       

 

   После заполнения таблицы исходный опорный план проверяют на оптимальность. Для этого просматривают элементы (m+1)-й строки. Может иметь место один из 3-х случаев.

   1) Все Тогда составленный план оптимален.

   2) для некоторого j и все соответствующие этому j . Тогда целевая функция неограничена.

   3) для некоторых индексов j и для каждого такого j по крайней мере одно из чисел            положительно. Здесь можно перейти к новому опорному плану.

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

   В базис вводим вектор , давший минимальную отрицательную величину симплекс-разности

   Из базиса выводится  вектор       , который дает наименьшее положительное оценочное отношение 

 

 

   для всех              , т.е. минимум достигается при i=r.

    Число           называется разрешающим элементом.

 

 

   Строка      называется разрешающей строкой, элементы этой строки  в новой симплекс-таблице вычисляются по методу Жордана-Гаусса, т.е. по формулам:

      

 

 Элементы i-й строки –по формулам

   Значение нового опорного плана считают по формулам

 

 

 

 

   Значение целевой функции при переходе от одного опорного плана к другому , улучшенному, изменяется по формуле

        Процесс решения продолжаем до получения оптимального плана либо до установления неограниченности ЦФ.

        Если среди оценок оптимального плана нулевые только оценки , соответствующие базисным векторам, то оптимальный план единствен.

        Если же нулевая оценка соответствует вектору, не входящему в базис, то в общем случае это означает, что опорный план не единствен.

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

 

   1)Находят опорный план.

   2)Составляют симплекс-таблицу.

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

   4)Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим  по абсолютной  величине  отрицательным числом , а направляющая строка—минимальным числом Q.

   5)Определяют положительные компоненты нового опорного плана. Составляется новая таблица.

   6)Проверяют найденный опорный план на оптимальность.

Пример.

 

      Решить симплекс-методом ЗЛП

Решение.

 

   Приведем задачу к каноническому виду, введя новые переменные 

   В целевую функцию эти переменные войдут с нулевыми коэффициентами:

   Из коэффициентов при неизвестных и свободных членов составим векторы

 

 

 

 

   Единичные векторы  образуют единичную подматрицу и составляют базис первоначального плана. Свободные неизвестные приравниваются к нулю.

   Получаем первоначальный опорный план:

         Х= (0;0;350;240;150).

   Составим симплекс-таблицу и проверим план на оптимальность. В нашем примере           

 

  Для заполнения последней строки таблицы сразу вычислим симплекс-разности

 

 

   Для этого поочередно умножаем столбец Сб на соответствующие элементы каждого столбца

 

 

 

 

 

 

 

Составим теперь нулевую симплексную  таблицу

Таблица 0.

   Определяем разрешающий элемент симплексной таблицы. Т.к. имеется 2 отрицательные оценки, то выбираем ту, что дает максимальную по абсолютной величине отрицательную оценку, т. е. -20.

          Это означает, что в базис включается

    вектор       , а исключается из базиса тот вектор, которому соответствует                 

 

 

                                                                             .

 

 

 

 

   Разрешающим элементом

   является                   .

   Значение целевой функции в следующей симплекс-таблице будет равно:

   Элементы направляющей строки в новой таблице вычисляем, деля эту строку на ведущий элемент(в том числе и клетку в столбце план):

   Можно рассчитывать элементы строк методом Жордана-Гаусса, домножая 1-ю строку на (-0,5) и прибавляя ее ко 2-й, а затем на(-1) и прибавляя к 3-й, обнулив таким образом элементы 2-го выделенного (разрешающего) столбца, или по формулам треугольника

   Элементы 2-ой строки получаем по методу Жордана-Гаусса (или по формулам треугольника)

   Аналогично рассчитываем элементы 3-й строки.

   Значения нового опорного плана рассчитываем по формулам:

 

 

 

 

   После чего заполняем таблицу 1.

Таблица 1.

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

Вычислим симплекс-разности.

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

    

   Выводится из базиса вектор       , которому соответствует минимальное оценочное отношение 70. Переходим к следующему опорному плану. Вводим в базис вектор      , делим разрешающую строку на разрешающий элемент                           и заполняем 3-ю строку таблицы 2. После чего методом Жордана-Гаусса домножаем эту строку на (-0,286) и прибавляем к первой, затем домножим эту строку на (-1,857) и прибавляем ко второй.

Таблица 2

    Вычисляем симплекс-разности.

 

 

 

 

 

   План оптимален. Значение целевой функции