и, що, то існує нетривіальне нуль-простір
2)
Вибираючи досить малим за нормою, можна домогтися того, що для вектор або
для і
для досить малих. Аналогічно можна показати, що при цьому і. Так як то отримуємо протиріччя з визначенням крайньої точки. Для спрямованого перегляду крайніх точок допустимого багатогранника застосовують симплекс-метод, запропонований Дж. Данцигом і потім вдосконалений численними математиками. Основна ідея методу полягає в розбитті безлічі змінних x = x 1 , < b> x 2 ,. . ., x n на базисні і небазисні. Не применшуючи спільності, можна вважати, що базисні змінні є першими у векторі x, тобто x = ( x B , x N ) . p> Система обмежень канонічної форми задачі лінійного програмування може бути відповідно переписана у вигляді:
(3)
Припустимо, що матриця має повний ранг, тобто - невироджених. Тоді з рівності (5) слід
4)
Цільова функція задачі ОПР також може бути розбита на базисну і не базисну частини:
В
Підстановка (6) дає
5)
Припустимо, що ми знаходимося в деякій початковій точці із значенням цільової функції
В
Яким чином можна зменшити далі значення цільової функції? Зі співвідношення (5) випливає, що для цього досить зробити позитивними ті компоненти вектора, яким відповідають негативні значення координат вектора модифікованих вартостей
В
зберігаючи при цьому неотрицательность базисних змінних. p> Збільшення може бути пророблене різним чином, і за час існування симплекс-методу були пророблені численні експерименти з пошуку найбільш ефективних стратегій збільшення
Тут буде розглянута найпростіша:
В· серед компонент вектора знаходиться мінімальна;
В· відповідна небазисна мінлива отримує максимально можливу прирощення, що зберігає неотрицательность базисних змінних. p> Оскільки при збільшенні-й компоненти вектор набуває вид:
В
де це-й орт, а - ступінь збільшення цієї змінної чи крок алгоритму, то модифікований базисний вектор виражається наступним чином:
В
де - й стовпець матриці Крок визначається при цьому з умови:
В
Максимально можливе значення визначиться при цьому як
6)
Нехай - номер, на якій досягається мінімум (6). Очевидно, що при цьому
В
При цьому говорять, що мінлива виводиться з базису (звертається в нуль), а змінна вводиться в базис. Цільова функція при цьому зменшується на величину
В
Важливу роль в теорії симплекс-методу грає умова невироджених, в якому передбачається повний ранг A B і сувора позитивність базисного рішення ОІ. При цьому О»> 0 і Оґc...
