залишивши осередку, відповідні вільним змінним, порожніми. У крайній правий стовпчик внесемо значення невідомих u 1 , ..., u m , в нижню рядок - значення невідомих v 1 , ..., v n ,. Ці m + n невідомих для всіх ( i , j ) , відповідних базисним змінним, повинні задовольняти лінійної системи рівнянь u i + v j = p ij .
pll
plj
pln
ul
.
...
.
.
...
.
.
.
.
pil
pij
pin
ui
.
...
.
.
...
.
.
.
.
pml
pmj
pmn
um
vl
...
vj
...
vn
Для всіх базисних рішень ця система має трикутний вигляд, ранг її матриці дорівнює n + m - 1 . Отже, систему завжди можна вирішити наступним способом. p> Вважають v n = 0. Якщо значення k невідомих визначені, то в системі завжди є рівняння, одне з невідомих в якому вже знайдено, а інше ще немає. p> Змінні u i і v j симплекс - множниками . Іноді вони називаються також потенціалами , а цей метод рішення називають методом потенціалів .
Приклад 2. tabletable border=1 cellspacing=0 cellpadding=0>
5
u1
6
4
7
u2
3
1
8
u3
v1
v2
v3
v4
v5
v 5 = 0 В® u 3 = 8, так як u 3 + u 5 = p 35 = 8, В® v 4 = -7, Так як u 3 + v 4 = p 34 = 1, В® v 3 = -5, Так як u 3 + v 3 = 3, В® u 2 = 12 В® v 2 = -8, В® v 1 = -6 В® u 1 = 11.
Симплекс - множники потрібні для того, щоб знайти вільну комірку ( i , j ) , яка при заміні базису переходить в базисну (це відповідає відшукання дозволяє стовпця в симплекс - методі).
Для визначення симплекс - множників ми вносимо на вільні місця в таблиці значення
p Вў ij = p ij - u i - v j
(коефіцієнти цільової функції, перелічені для вільних змінних). Якщо все p Вў ij 0, то базисне рішення оптимально. В іншому випадку ми вибираємо довільне p Вў a b < ; 0, найчастіше найменше. Індексом a b <...
