Линейное программирование. Геометрическая интерпретация и графический метод решения задачи линейного программирования, страница 8

Рассмотрим этот процесс подробнее. Пусть переменная x_s входит в r-е уравнение с коэффициентом a_rs¹0. Для того чтобы она стала базисной, разделим r-е уравнение на a_rs (получим x_s с коэффициентом 1) и результат вычтем из каждого оставшегося уравнения i=1, …, m, i¹r, умножая его каждый раз на соответствующий коэффициент a_is (получим x_s с коэффициентом 0). Совокупность операций, составляющих шаг жордановых исключений, называется жордановым преобразованием, коэффициент a_rs – ведущим (разрешающим) элементом, строка r и столбец s – соответственно ведущими строкой и столбцом. Формулы для расчета коэффициентов a^¢_rj, b^¢_i новой системы, получаемой в результате одного шага жордановых исключений с ведущим элементом a_rs, имеют вид:

                                           a^¢_{r j}= a_rj,    j=1, …, n;                         (2.14)                               

                                           b^¢_r = b_r;

                                            a^¢_{i j} = a_ij   – a_rj,     j=1, …, n;               (2.15)                                 

                                            b^¢_i = b_i   – b_r;

                                            i=1, …, m, i¹r.

Вычисления по формулам (2.15) можно описать с помощью так называемого правила прямоугольника (рисунок 2.4): чтобы найти преобразованный элемент a^¢_ij, надо из элемента a_ij вычесть произведение коэффициентов, стоящих напротив его в ведущих столбце и и строке, деленное на ведущий элемент, расположенный по диагонали от элемента a_{ij .}

Рис.  2.4 –  Правило прямоугольника

При этом элементы ведущего столбца принимают значения a^¢_is=0 для всех i =1, …, m, i¹r,  a^¢_rs=1.

Итак, последовательность действий, выполняемых на одном шаге жордановых исключений в соответствии с формулами (2.14) (2.15), такова: 1) элементы, не принадлежащие ведущей строке или столбцу, вычисляются по правилу прямоугольника; 2) все остальные элементы ведущей строки делятся на ведущий элемент  (при  этом  ведущий  эле-  

мент заменяется единицей); 3) все остальные элементы ведущего столбца  заменяются нулями.

Приведенные выше сведения позволяют теперь перейти к непосредственному изложению сущности симплекс-метода.

2.5.3. Сущность и процедура симплекс-метода

В «геометрической» трактовке сущность симплекс-метода состоит в целенаправленном «движении» от одной крайней точки многогранника решений к другой до нахождения оптимальной точки. Это «движение» организуется таким образом, что каждая следующая точка оказывается «лучше» предыдущей в смысле приближения к оптимуму.

Перед переходом к «алгебраической» трактовке метода отметим (см. рисунок 2.3) имеющееся взаимно однозначное соответствие между крайней точкой многогранника решений и опорным планом задачи ЛП (см. теорему 2.4), а также соответствие между опорным планом задачи ЛП и базисным решением системы уравнений, задающей ограничения в канонической форме задачи (2.4) [4].

С учетом этого идея перебора крайних точек многогранника решений задачи ЛП в стандартной форме (2.1) переходит в требование последовательного анализа базисных решений (опорных планов) системы уравнений задачи в канонической форме (2.4).

Можно выделить три укрупненных этапа симплекс-метода.

1. Построение исходного опорного плана (исходного допустимого базисного решения).

2. Проверка найденного опорного плана (допустимого базисного решения)  на оптимальность.

3. Если получен неоптимальный план, то перейти к новому  опорному плану, обеспечивающему большее (меньшее) или равное предыдущему значению ЦФ.