Методы принятия управленческих решений: для менеджеров

47 сумму элементов, входящих в столбцы B,Ai,A2,...,A „. В столбце 0 для каждой строки записывают наименьшее из отношений bjjajj^ для > 0 , где к - номер разрешающего столбца. Столбец 0 заполняется после того, как очередной опорный план проверен на оптимальность. Он используется для выбора разрешающей строки на очередном симплекс-шаге. Значения Ду =zy - cj называются оценками плана. Они за­ носятся в нижние ячейки столбцов ^„+1, ^ т + 2 ' - • Значения г, т ВЫЧИСЛЯЮТ п о формуле Z j = ^ , у = m+1,« . /=1 т в нижнюю ячейку столбца В заносят значение L= У^ сjbj ; = 1 Симплекс-метод основан на следующих теоремах. Теорема 1 (Признак оптимальности опорного плана). Опор­ ный план ,дс2,...,д:„,0,...,о) задачи (33)-(35) является опти­ мальным, если Ду = Zj - Cj <0 для любого j, j = \,п (36) Теорема 2. Если Д^ >0 для некоторого j = k н среди чисел , г = 1,и, нет положительных (все они отрицательные или равные нулю), то целевая функция (33) задачи (33)-(35) не ограничена на множестве ее планов (решений). Теорема 3. Если опорный план Xq задачи (33)-(35) не выро­ жден и все Д^ >0 , но среди чисел есть положительные, то су­ ществует опорный план X], для которого выполняется неравенство ЦХО<ЦХо). Неравенства (36) являются условием оптимальности плана ЗЛП при отыскании минимума целевой функции.