(2.11) в (2.1), маємо
(2.13)
Якщо позначити
, (2.14)
, (2.15)
то (2.13) прийме вигляд
(16)
З отриманих співвідношень напрошуються наступні висновки.
Критерій 1 (критерій оптимальності). Якщо все D k Ві 0, то обраний план для задачі максимізації є оптимальним. p> Критерій 2. Якщо виявляється деяка D k <0 і хоча б одне із значень Z jk > 0, то перехід до нового плану збільшить значення цільової функції.
Цей висновок з очевидністю випливає з (2.16); в такій ситуації згідно (2.12) думаємо k-ю змінну рівній Q і перетворимо значення інших (Базисних) змінних відповідно до (2.11). p> Критерій 3 . Якщо виявляється деяка D k <0, але всі Z jk ВЈ 0, то лінійна форма завдання не обмежена по максимуму.
Цей висновок випливає з того, що згідно (2.11) компоненти нового плану зберігають неотрицательность при будь-якому Q> 0 (в тому числі і при як завгодно великому) та відповідно до (2.16) з'являється можливість необмеженого зміни значення цільової функції.
Припущення про те, що базисними є перші m компонент плану, не є принциповим, і вказівка ​​діапазону по j від 1 до m в (2.11) - (2.15) можна замінити на вказівка ​​про приналежність до базису "jГЋБ".
Якщо всі опорні плани завдання є невиродженими (число позитивних компонент одно m), то Q відмінно від нуля і перехід до нового планом згідно (2.16) змінює значення цільової функції, що гарантує досягнення екстремуму за кінцеве число кроків. За наявності вироджених планів можливо т. зв. зациклення (повернення до раніше розглянутим планами), але на практиці зациклення ніколи не виникало.
В
2.2 Прямий алгоритм симплексного методу [1]
Нехай вихідна завдання приведена до канонічної формі і початковий базис утворює одиничну матрицю. Тоді базисні компоненти опорного плану збігаються з правими частинами обмежень і коефіцієнти Z jk розкладу вектора X k по такому базису збігаються з компонентами цього вектора.
Для однаковості опису обчислювальної процедури надалі будемо користуватися т.зв. симплексной таблицею виду:
C
Базис
План
C 1
C 2
C m
C m +1
C k
C n
баз
плану
...
