Симплексный метод

п.2.2. Симплексный метод

    Решение любой задачи линейного программирования можно найти либо симплексным методом, либо методом искусственного базиса. Прежде чем применять один из указанных методов, следует записать исходную задачу в форме основной задачи линейного программирования, если она не имеет такой формы записи.

    Симплексный метод решения задачи линейного  программирования основан на переходе от одного опорного плана к другому, при котором значение целевой  функции возрастает (при условии, что данная задача имеет оптимальный план, и каждый ее опорный план является невырожденным) Указанный переход возможен, если известен какой-нибудь исходный опорный план. Рассмотрим задачу, для которой этот план можно непосредственно записать.

    Пусть требуется найти максимальное значение функции

F=c₁x₁+c₂x₂+…+c_nx_n

при условиях

Здесь — заданные постоянные числа (m<n и b_i>0) Векторная форма данной задачи имеет следующий вид: найти максимум функции

           (2.35)

при условиях

      x₁P₁+x₂P₂+…+x_mP_m+…+x_nP_n=P₀, (2.36)

         х_j≥0  (2.37)

где 

    Так как 

b₁P₁+b₂P₂+…+b_mP_m=P₀,

то по определению опорного плана X=(b₁;b₂;…;b_m;0;…;0) является опорным планом данной задачи (последние n—m компонент вектора Х равны нулю). Этот план определяется системой единичных векторов Р₁, Р₂,…, Р_m, которые образуют базис m- мерного пространства. Поэтому каждый из векторов Р₁, Р₂,..., Р_n, а также вектор Р₀ могут быть представлены в виде линейной комбинации векторов данного базиса. Пусть

    Положим ; . Так как векторы P₁, P₂, …, P_m – единичные, то x_ij=a_ij и , а .

    Теорема 2.5. (признак оптимальности опорного плана). Опорный план задачи (2.35)-( 2.37) является оптимальным, если для любого j .

    Теорема 2.6. Если для некоторого j=k и среди чисел a_ik нет положительных (a_ik ≤ 0), то целевая функция (2.35) задачи (2.35)-( 2.37) не ограничена на множестве ее планов.

    Теорема 2.7. Если опорный план Х задачи (2.35) - (2.37) не вырожден и , но среди чисел a_ik есть положительные (не все a_ik ≤ 0), то существует опорный план Х’ такой, что F(Х’)  > F(Х).

    Сформулированные  теоремы позволяют проверить, является ли найденный опорный план оптимальным, и выявить целесообразность перехода к новому опорному плану.

      Исследование опорного плана на оптимальность, а также дальнейший вычислительный процесс удобнее вести, если условия задачи и первоначальные данные, полученные после определения исходного опорного плана, записать так, как показано в табл. 2.2.

    В столбце С_б этой таблицы записывают коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и векторы данного базиса.

    В столбце Р₀ записывают положительные компоненты исходного опорного плана, в нем же в результате вычислений получают положительные компоненты оптимального плана. Столбцы векторов Р_j представляют собой коэффициенты разложения этих векторов по векторам данного базиса.

    В табл. 2.2 первые m строк определяются исходными данными задачи, а показатели (m+1)-й строки вычисляют. В этой строке в столбце вектора Р₀ записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора Р_j – значение .

    Значение  z_i находится как скалярное произведение вектора Р_j, на вектор С₆=(с₁;c₂; ...; с_m):

    Значение  F₀ равно скалярному произведению вектора Р₀ на вектор Сб:

.

    После заполнения табл. 2.2 исходный опорный план проверяют на оптимальность. Для этого просматривают элементы (m+1)-й строки таблицы. В результате может иметь место один из следующих трех случаев:

1. для  j=m+1, m+2, …, n (при z_j=c_j). Поэтому в данном случае

числа для всех j от 1 до n;

2. для некоторого j и все соответствующие этому индексу величины a_ij≤0 ;
3. для некоторых индексов j, и для каждого такого j по крайней мере

одно  из чисел a_ij положительно.

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

    Для определения вектора, подлежащего  исключению из базиса, находят min(b_i/a_ik) для всех a_ik>0. Пусть этот минимум достигается при i = r. Тогда из базиса исключают вектор Р_r, а число a_rk называют разрешающим элементом.

    Столбец и строку, на пересечении которых  находится разрешающий элемент, называют направляющими.

    После выделения направляющей строки и  направляющего столбца находят  новый опорный план и коэффициенты разложения векторов Р_j через векторы нового базиса, соответствующего новому опорному плану. Это легко реализовать, если воспользоваться методом Жордана - Гаусса. При этом можно показать, что положительные компоненты нового опорного плана вычисляются по формулам:

      (2.38)

Таблица 2.2

 

Таблица 2.3

 

а коэффициенты разложения векторов Р_j, через векторы нового базиса, соответствующего новому опорному плану - по формулам:

      (2.39)

После вычисления и согласно формулам (2.38) и (2.39) и значения заносят в табл. 2.3. Элементы (m+1)-й строки этой таблицы могут быть вычислены либо по формулам:

      (2.40)

      (2.41)

либо  на основании их определения.

    Наличие двух способов нахождения элементов  (m+1)-й строки позволяет осуществлять контроль правильности проводимых вычислений.

    Из  формулы (2.40) следует, что при переходе от одного опорного плана к другому наиболее целесообразно ввести в базис вектор Р_j, имеющий индекс j, при котором максимальным по абсолютной величине является число . Однако с целью упрощения вычислительного процесса в дальнейшем будем вектор, вводимый в базис, определять, исходя из максимальной абсолютной величины отрицательных чисел . Если же таких чисел несколько, то в базис будем вводить вектор, имеющий такой же индекс, как и максимальное из чисел с_j, определяемых данными числами .

    Итак, переход от одного опорного плана  к другому сводится к переходу от одной симплекс-таблицы к другой. Элементы новой симплекс-таблицы можно вычислить как с помощью рекуррентных формул (2.38)-( 2.41), так и по правилам, непосредственно вытекающим из них. Эти правила состоят в следующем.

    В столбцах векторов, входящих в базис, на пересечении строк и столбцов одноименных векторов проставляются единицы, а все остальные элементы данных столбцов полагают равными нулю.

    Элементы  векторов Р₀ и Р_j, в строке новой симплекс-таблицы, в которой записан вектор, вводимый в базис, получают из элементов этой же строки исходной таблицы делением их на величину разрешающего элемента. В столбце С₆ в строке вводимого вектора проставляют величину c_k, где k - индекс вводимого вектора.

    Остальные элементы столбцов вектора Р₀ и Р, новой симплекс-таблицы вычисляют по правилу треугольника. Для вычисления какого-нибудь из этих элементов находят три числа:

1. число, стоящее в исходной симплекс-таблице на месте искомого элемента