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

                                                 95


       Заметим, что те переменные yi, для которых коэффициенты α is ≤ 0, останутся
неотрицательными, каково бы ни было xs>0. Рассмотрим поэтому такое yi, для которого
коэффициент αis>0. Нужно, чтобы было
                                     yi=αis(-xs)+βi ≥ 0,
откуда получится, что для всех i, для которых αis>0, значение xs должно удовлетворять
неравенству
                                              βi
                                       xs ≤        (αis>0),
                                              α is
а для этого достаточно взять xs равным наименьшему из отношений βi/αis, которые составлены для
всех положительных элементов s-го столбца:
                                                           βi
                                         x s = min              .
                                               (α is   >0) α
                                                             is
        Пусть это минимальное отношение получается, когда i=r, т.е. в r-й строке, тогда следует
взять
                                                       βr
                                           xs =             .
                                                       α rs
        При этом значении xs получится, что r-я боковая переменная обратится в нуль:
                                 yr=αrs(-xs)+βr=αrs(-βr/αrs)+βr=0.
        Таким образом, yr станет базисной переменной (перейдет «наверх»), и вопрос о том, с
какой именно боковой переменной надо поменять ролями верхнюю переменную xs, решен.
        Получаем следующее правило улучшения опорного решения (плана). Если на каком-то шаге
жордановых исключений среди элементов заключительной строки имеются отрицательные, то
данное опорное решение можно улучшить, если сделать очередной шаг жордановых исключений,
придерживаясь такой последовательности:
1) в качестве ведущего столбца выбирается любой из тех столбцов, который находится над
    каким-нибудь имеющим отрицательное значение элементом заключительной строки;
2) отобрав в этом столбце только элементы с положительными значениями, делим на каждый из
    них соответствующий элемент заключительного столбца;
3) из всех полученных отношений выбираем наименьшее и ту строку, в которой оно
    (наименьшее) получается, берем в качестве ведущей; на пересечении отобранных столбца и
    строки получаем ведущий элемент.
        Пример. Используем пример предыдущего раздела (см. табл. 7). Заметим, что второй
элемент в заключительной строке (-1) отрицательный. Поэтому для улучшения плана берем
второй столбец в качестве ведущего. Составляем отношения свободных членов к положительным
элементам выбранного ведущего столбца; это будет 6/1 и 21/1. Минимальным оказалось
отношение 6/1. Поэтому берем строку для переменной y2 в качестве ведущей. На пересечении
выбранных столбца и строки получаем ведущий элемент (выделен). Сделав шаг жордановых
исключений с этим ведущим элементом (см. табл. 8), мы улучшили опорное решение: в табл. 7
Z=9, а в табл. 8 Z=15.
        Чтобы исчерпать вопрос об улучшении опорного решения остановимся еще на следующих
аспектах:
1) не может ли случиться, что в процессе улучшения нарушится опорность решения, т.е. что при
    переходе по правилу улучшения к следующей таблице в заключительном столбце появятся
    отрицательные элементы?
2) как поступить, если в столбце над отрицательным элементом заключительной строки (который
    выбирается ведущим) нет ни одного положительного элемента (все элементы оказались
    отрицательными или нулями)?
        Ответ на эти вопросы содержится в следующих двух теоремах.
        Теорема 1. При переходе от таблицы к таблице по правилу улучшения опорное решение
остается опорным.
        Допустим, что по правилу улучшения осуществлен переход от табл. 10 к табл. 11 с
ведущим элементом