Численные методы. Корнюшин П.Н. - 93 стр.

                                                 93



                                       y3=   5        -1   15

                                       Z=    2        1    15

      Теперь уже все элементы заключительного столбца и заключительной строки строго
положительны. Следовательно, по второй теореме мы достигли максимума целевой функции Z.
Оптимальное решение:
                              x1=12; x2=6; y1=0; y2=0; y3=15;
оптимальный план: x1=12; x2=6.
       Остался резерв третьего ресурса в количестве 15 ед., первый и второй ресурсы исчерпаны.
Максимальное значение целевой функции max Z=15.
       Дополнение (признак оптимальности для задачи на минимум). Очевидно, что для задачи
линейного программирования на минимум, полученный в теореме 2, признак оптимальности
модифицируется следующим образом: если на каком-то шаге жордановых исключений
получилась таблица, в которой все элементы заключительного столбца неотрицательны, а все
элементы заключительной строки неположительны, то мы достигли минимума целевой функции;
при этом оптимальное решение получается так же, как и в случае задачи на максимум, и
заключительный угловой элемент дает минимальное значение целевой функции. Кроме того,
задачу на минимум некоторой линейной функции Z всегда можно решить как задачу на максимум
функции -Z.


                                4.6.3.4. Улучшение опорного плана

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

                     Z=    γ1     γ2                  γs            γn   D
элемент γs<0. Целевая функция имеет такое выражение: Z=γ1( )+γ2( )+…+γs(-xs)+…+ γn( )+D, где в
незаполненных скобках стоят верхние переменные, а скобка при γs для определенности заполнена
переменной -xs (хотя там могла оказаться и другая переменная, но это несущественно). Для
данного опорного решения значения переменных во всех скобках равны нулю (верхние
переменные!), следовательно, Z=D.
        Но если (для перехода из вершины A в соседнюю вершину B) двигаться по ребру, на
котором xs>0, а остальные верхние переменные по-прежнему равны нулю, то целевая функция
станет больше, чем в данной вершине, т.к. при
                                            γs<0, xs>0;
                                         Z=γs(-xs)+D>D,
и, следовательно, план будет улучшаться.
        Однако при увеличении xs, т.е. при движении по ребру АВ (рис. 6.23), можно продвинуться
далее соседней вершины B, следовательно, можно увеличивать xs только до такого значения, при
котором станет равной нулю именно та из внебазисных переменных, которая становится базисной
в вершине B, например, yr.