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

                                                        91


       Точно так же можно получить второй и третий элементы второй строки.


                            4.6.3.3. Опорное решение, опорный план

       Вернемся к общей задаче линейного программирования (на максимум):
                                Z=c1x1+c2x2+…+cnxn → max;
                          y1 = a11 (− x1 ) + a12 (− x2 ) + ... + a1n (− xn ) + b1 ≥ 0;
                         y 2 = a 21 (− x1 ) + a 22 (− x2 ) + ... + a 2 n (− xn ) + b2 ≥ 0;
                               .............................................................
                        y m = a m1 (− x1 ) + am 2 (− x2 ) + ... + a mn (− xn ) + bm ≥ 0;
                                           x1 ≥ 0; x 2 ≥ 0;...; xn ≥ 0.
        Введем такую терминологию. Совокупность значений основных переменных x1, x2,…, xn,
соответствующих какой-нибудь вершине многогранника ограничений будем называть опорным
планом задачи. Совокупность значений основных переменных x1, x2,…, xn и дополнительных
переменных y1, y2,…, ym, соответствующих какой-нибудь вершине многогранника ограничений,
будем называть опорным решением задачи.
        Опорное решение задачи, очевидно, содержит и его опорный план, но оно шире, т.к.
содержит еще и значения дополнительных переменных, т.е., в экономическом толковании, оно
еще содержит числовые значения всех остатков от ресурсов, которые получаются после
осуществления данного опорного плана.
        Если в данной вершине достигается максимум целевой функции Z, то опорный план и
опорное решение называются соответственно оптимальным планом и оптимальным решением.
        Из алгебраической характеристики вершины многогранника ограничений вытекает, что
все n+m чисел, составляющих опорное решение, должны быть неотрицательными и притом не
менее чем n из этих чисел должны быть равны нулю.
        Если пользоваться таблицами жордановых исключений и называть заключительным
столбцом и заключительной строкой соответственно столбец свободных членов (помещенный в
табл. 6 под 1) и строку коэффициентов целевой функции (помещенную внизу) без углового
элемента (D – в нижнем правом углу), то можно легко доказать следующие две теоремы.
        Теорема 1 (признак опорности решения). Если на каком-то шаге жордановых исключений
оказалось, что все элементы заключительного столбца неотрицательны, то, полагая верхние
переменные равными нулю, а боковые переменные равными соответствующим элементам
заключительного столбца, получим некоторое опорное решение.
        Для определенности изложения допустим, что мы имеем дело с четырехмерной задачей
(основные переменные x1, x2, x3, x4) с тремя ограничениями (дополнительные переменные y1, y2, y3)
и пусть на каком-то шаге жордановых исключений получилась таблица, в которой элементы
заключительного столбца (см. табл. 6) β1, β2, β3 неотрицательны. Тогда, полагая верхние
переменные x2=x4=y1=y3=0, получим, что боковые переменные принимают значения x1=β1, y2=β2,
x3=β3, т.е. они неотрицательны. Таким образом, значения всех 4+3=7 переменных неотрицательны
и не менее чем четыре из них (x2, x4, y1, y3) равны нулю. Следовательно, x2=0, x4=0, y1=0, y3=0,
x1=β1, y2=β2, x3=β3 есть опорное решение.
        Теорема 2 (признак оптимальности решения). Если на каком-то шаге жордановых
исключений оказалось, что все элементы заключительного столбца и все элементы
заключительной строки неотрицательны, то это означает, что достигнут максимум целевой
функции; при этом оптимальное опорное решение получится, если положить верхние переменные
равными нулю, а боковые переменные равными соответствующим элементам заключительного
столбца. Кроме того, значение заключительного углового элемента таблицы D равно
максимальному значению целевой функции (max Z).

       Таблица 6
                                            -x2     -x4      -y1     -y3      1