Метод симплекс-таблиц.

Как известно общая задача линейного программирования имеет следующей вид:

{spoiler=Подробнее}

                                                        (1)

при условиях

                                     (2)

                               (3)

                                      (4)

где   ^А _{i  j ,}    В_{i  ,}  С _j  ^-- заданные    постоянные     величины    и   к

F=CX                                                                 (5)

при условияx

х ₁ P_{1   +} X₂ P₂ + ...+  Х_п   Р_п    =  Р­_о                                          (6)

x    С                                                                 (7)

где    С  =  (С_{1  ,} С  _{2  , .....  ,}  С  _n)   Х= ( Х :  ,  Х _{2 ,  ....  ,}   Х _n  ): CX­ _-  скалярное произведения: Р₁ ,  Р₂ ,  _....   Р_n   -n -мерный вектор столбце, составление из коэффициентов при неизвестных и свободных членах системы уравнений задачи:

P₀ =

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

при условиях

Здесь a_i ,b_i    и c_i (i=1,m; j=1,n) - заданные постоянные числи (m=n и b_i>0).

     (8)

при условиях

X₁P₁ + X₂P₂ + . . . + X_mP_m + . . . + X_nP_n = P₀   (9)

X_j>0         (j=1,n)    (10)

где

Так, как

b₁p₁ + b₂p₁ + . . . + b_mp_m = p₀

то на определению опорного плана Х=( b₁, b₂,...b_m ;0,0,....0) является опорном планом данной задачи. Этот план определяется системой единичных векторов Р₁, Р₂, ... Р_n которые образуют базис m-мерного пространства

Пусть 

Положим         так как векторы р_1,р_2,......,р_m- единичные, то x_ij=a_ij  и  z_i=,  a   A_j=.

ТЕОРЕМА: (признак оптимальности опорного плана)

Опорный план   х*=(х₁*,x₂*,….x_n*,0,0,0…..0) задачи (8)-(10)-является оптимальный если  А_j=0  для любого  j(j=1,n)     Исследование  опорного плана на оптимальность ,а также дальнейший вычислительный процесс удобного вести, записать так как показано в следующее таблице:

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

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

Столбце векторов р_i представляет собой  коэффициенты разложенный этик векторов данного базиса. В строке определяются исходными данными задачи, а показатели (m+1)-й строке вычисляют. В этой строке в столбце вектора р₀ записывают значение целевой функции ,которое она принимает при данном опорном плане, а в столбце вектора р_i -значение  D_i=z_i-c_i ;,m) на вектор С_б=(С₁;C₂;….,C_m)

Z_i=

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

F_n значение z_i находится как скалярное произведение вектора

F_i(i=1 =

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

1. для  j=m+1 , m+r,....... ,n(при  j=1,mZ_j=C_j)

По этому, в данном случая числа   :_j0  всех j от 1до n:

2) для  некоторых  индексов j  и  для каждого такого j  по крайней мере одно из чисел а_ji положительно.

3) для некоторого j  и  все соответствующие  этому индексу величины а_ij   (i=1,m)

В первом случае  на основании признака оптимальности исходный опорный план является оптимальным. Во втором случай целевая функция не ограничена сверху на множестве планов. А в третьем случае можно перейти от исходного плана  к новому  опорному плану ,при котором значение целевой функции увеличиться .

Этот переход от одного опорного плана к другому осуществляются исключением из исходного базис какого-нибудь из векторов и введением в него нового вектора.

Пусть, например, D_k0 и решено вести в базис вектор р_к.

Для определения вектора, подлежащего исключению из базиса ,находят min(в а_ik)  для всех а_ik. Пусть этот минимум достигает при i=2. Тогда из базиса исключают вектор р_r  а число а_rk называют разрешающим элементом.

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

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

b_i¹=                 при

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

a_i¹_j= при

После вычисления b_r¹_j  и  a_i¹_j  согласно но формулой 11 и  12  их значения заносят в след. табл.

Элементы (m+1) й  строки  этой  таблицы могут быть вычислены либо по формулам:

p₀¹=p₀-(b_r/a_rk) D_k                              (13)

D_j¹=D_j-(a_rj/a_rk) D_k                              (14)

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

После заполнения новой симплекс таблицы просматривают элементы(m+1)-й строки. Если все z_j-c_j, то новый опорный план является оптимальным.

Таким образом, решение симплексным методом осуществляется в определенной последовательности .

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

2)Вычисляется симплекс - разность для каждой переменной не входящей в базис;

3)Вводится  в базис переменная, удовлетворяющая условию max(x_r)=min(x_i¹/x_ir)

4)Исключается из решения переменная, соответствующая  max(x_r),ни вектор Р_i;

5)n 1-4 повторяется до тех пор, пока симплекс разность для всех переменных не входящих в базис, не станет равной нулю или отрицательной . это свидетельствует  о том , что оптимальное решение получено.

{/spoilers}