Симплекс-метод решения задачи линейного программирования. Коэффициенты при базисных переменных

Аннотация лекции. Лекция посвящена симплекс-методу решения задачи линейного программирования. Рассмотрены основы решения задачи в общем виде (с построением симплексной таблицы).

3.2.2 Решение задачи в общем виде. Симплексная таблица

Вернемся к решению задачи в общем виде из раздела 3.2, начиная с исходного опорного плана Х = (b₁, b₂, . . . b_m, 0 ... 0 ). Обозначим z целевую функцию задачи. На

14243

n m−

                                                                                                          n                         m

исходном плане значение целевой функции zc_j x_j c_i b_i , так как слагаемые, соответствующие небазисным переменным, обратятся в 0. 

Для применения симплекс-метода к системе необходимо приписать еще одно

n

ограничение - c_j x_j = 0. 

В решенном примере это было четвертое ограничение. Поскольку в этом примере базисные переменные исходного опорного плана (х_5-7) не входили в целевую функцию, то и в критериальное ограничение они не вошли. В общем случае это не так. Например, если бы задача имела вид:

max -5х₁ + 2х₃ 

                                                  -2,5х₁ – 0,5х₂ + х₃           + 0,5х₅                                               = 1

                                                   1,5х₁ + 0,5х₂  + х₄ - 0,5х₅ + х₆               = 4

                                                  -3х₁                                    + 5х₄                                 + х₇  = 7

х_1-7 ≥ 0 то в качестве базисных в исходном опорном плане следовало бы взять переменные х₃, х₆ и

n х₇. Одна из них - х₃ - входит в целевую функцию. Уравнение z - c_j x_j = 0 здесь приняло

бы вид: z + 5х₁ - 2х₃ = 0. Чтобы увеличить z, здесь следовало бы увеличить х₃. Но переменная х₃ и так является базисной, уже равна 1, и из ограничений следует, что увеличить ее до большего значения невозможно. Такое затруднение возникло из-за того, что после добавления критериального ограничения столбцы коэффициентов перестали быть единичными. Базисные переменные должны входить в него с нулевыми коэффициентами, а в последней задаче это не так.

Чтобы избежать этого, выразим базисную переменную х₃ из первого ограничения

через небазисные         (-2,5х₁     –     0,5х₂       + х₃       +     0,5х₅     =         1 ⇔ х₃        =                                            1         + 

+ 2,5х₁ + 0,5х₂ - 0,5х₅) и подставим в целевую функцию: z = -5х₁ + 2х₃ = -5х₁ +

n

+ 2*(1 + 2,5х₁ + 0,5х₂ - 0,5х₅) = 2 + х₂ - х₅. Теперь уравнение z - c_j x_j = 0 примет вид: z - х₂ + х₅ = 2, т.е. вид уравнения (4`) из системы (16). Рекомендуется сравнить остальные ограничения последней задачи с уравнениями (16): они в точности совпадают; и целевая функция взята из того же примера.

Итак, в общем случае после введения критериального ограничения столбцы при базисных переменных могут перестать быть единичными. Чтобы избежать этого, выразим базисные переменные x_1-m из ограничений через небазисные: 

x1 = b1 - a1 m+1xm+1 - . . . -a1 nxn

…

x i = b i - a i m+ 1xm+ 1 - . . . -a i nxn

…

xm = bm - am m+1xm+1 - . . . -am nxn  

                                                                                            n                         m                           n

и подставим их в целевую функцию: z = ∑c_j x _j =∑c_j x _j + ∑c_j x_j = c₁(b₁ - a_{1 m+1}x_m+1 - .

                                                                                          j 1=                j 1=              j m 1= +

. . -a_{1 n}x_n) + . . . + c_m(b_m - a_{m m+1}x_m+1 - . . . - a_{m n}x_n) + c_m+1x _m+1 + . . . + c_nx_n. 

После приведения подобных членов и переноса свободного члена в правую часть критериальное ограничение примет следующий вид: z + x_m+1(c₁a_{1 m+1} + . . . + c_ma_{m m+1} - c _m+1)

m

+ . . . + x_n(c₁a_{1 n}+ . . . + c_ma_{m n} - c_n) = c₁b₁ + . . . + c_mb_m; или z + x_m+1(∑ci aim+1 - c_m+1) + … + i 1=

m x_n( ∑c_i ain - c_n) = _∑^m cbi      _i .

       i 1=                             i=1

Обозначим коэффициенты при переменных x_j в критериальном ограничении -  m

∆_j = ∑ci aij - c_j; а свободный член этого ограничения - d = ∑^m cbi  _i . 

          i 1=                                                                                                                  i=1

Отметим, что коэффициенты при базисных переменных в критериальном ограничении будут нулевыми, что и требовалось получить. Но и эти нулевые коэффициенты

m

также можно рассчитать по формулам ( ∑ci aij - c_j): поскольку базисные