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

                                                       92



                                x1=                                       β1

                                y2=                                       β2

                                x3=                                       β3

                                Z=        γ1      γ2        γ3     γ4      D

       Действительно, т.к. элементы заключительного столбца неотрицательны, то, согласно
теореме 1, указанное в формулировке решение является опорным.
       Рассмотрим целевую функцию Z (снова воспользуемся табл. 6):
                        Z = γ 1 (− x 2 ) + γ 2 (− x4 ) + γ 3 (− y1 ) + γ 4 (− y3 ) + D
       Для данного опорного решения x2=x4=y1=y2=0, поэтому для него Z=D. Но так как
коэффициенты γ1, γ2, γ3, γ4 неотрицательны, то для любого другого опорного плана (в котором по-
прежнему все переменные неотрицательны и хотя бы одна из верхних переменных отлична от
нуля) получим для целевой функции значение Z ' ≤ D; следовательно, указанное в формулировке
теоремы опорное решение является оптимальным и притом заключительный угловой элемент
D=max Z.
       Теорема доказана.
       Пример. Пусть в задаче с двумя основными и тремя дополнительными переменными на
каком-то шаге жордановых исключений получились данные, представленные в табл. 7.

       Таблица 7
                                                 -y1        -x2    1

                                        x1=       1         -1     6

                                        y2=       -3        1      6

                                        y3=       2         1     21

                                        Z=        5         -1     9

       Так как все элементы заключительного столбца положительны, то получаем опорное
решение x1=6; y2=6; y3=21; y1=0; x2=0. Оно показывает, что опорный план будет следующим:
x1=6; x2=0. Далее, первый ресурс исчерпан (y1=0), остаток второго ресурса равен 6 ед. (y2=6),
остаток третьего ресурса равен 21 ед. (y3=21). Однако это опорное решение – не оптимальное, т.к.
в заключительной строке имеется отрицательный элемент (-1).
       Сделаем еще один шаг жордановых исключений с ведущим элементом, взятым в табл. 7 в
рамку, т.е. поменяем ролями x2 и y2. Тогда получим табл. 8

       Таблица 8
                                                 -y1        -y2    1

                                        x1=       -2        1     12

                                        x2=       -3        1      6