ле так як будь-які сусідні опорні плани доставляють значення лінійної форми, то, очевидно,
.
Таким чином, цикл означає перехід від одного базису опорного плану до іншого базису того ж виродженого опорного плану. Причому, через деякий число таких переходів має місце повернення до раніше зустрівся, базису. У разі утворення циклу, тобто зациклення, завжди можна вийти з нього, спеціальним чином обравши В«дозволяє елементВ».
Алгоритм побудови початкового опорного плану
Метод послідовного поліпшення плану, який застосовується для вирішення ЗЛП, передбачає знання деякого вихідного опорного плану. Однак, далеко не завжди такий початковий опорний план може бути вказаний без будь-яких обчислень. Це можливо лише у випадку, коли серед стовпців матриці умов знайдеться достатня кількість таких стовпців, з яких складеться одинична матриця і ця матриця буде базисом шуканого початкового плану. p> Якщо ж такої можливості немає, то для побудови початкового опорного плану ЗЛП вирішується допоміжна ЗЛП (так звана задача) з розширеним вектором, що складається з вектора вихідної ЗЛП, доповненого штучними невід'ємними компонентами. Останні вводяться в систему обмежень так, щоб сформувався штучний одиничний базис. p> Отже, початковий опорний план задачі може бути знайдений за допомогою наступної допоміжної ЗЛП (L - завдання):
(11.1) (11.2) (11.3)
Так як матриця умов ЗЛП (11.1) - (11.3) вже містить одиничну підматрицю яка може бути взята в якості базису опорного плану, то початковим опорним планом цього завдання буде вектор
,
у якого небазисні компоненти а базисні.
Вирішуючи сформульовану задачу, наприклад, першим алгоритмом симплекс - методу, з вказаним початковим планом, в силу обмеженості лінійної форми зверху на безлічі своїх планів () виявиться, що процес рішення через кінцеве кроків приведе до оптимального опорного плану допоміжної задачі.
Нехай - оптимальний опорний план завдання, у якого всі штучні компоненти дорівнюють нулю. Тоді вектор є опорним планом вихідної задачі. Дійсно, всі додаткові змінні. Значить, компоненти вектора задовольняють обмеженням вихідної задачі, тобто вектор є деяким планом вихідної задачі. За побудови план є також опорним. br/>
Алгоритм штучного базису
алгоритм симплекс лінійне програмування
Далеко не завжди має сенс розділяти вирішення завдання лінійного програмування на два етапи - обчислення початкового опорного плану і визначення оптимального плану. Замість цього вирішується розширена завдання (М-задача). Вона має інші опорні плани (один з них завжди легко вказати), але ті ж рішення (оптимальні плани), що і вихідна задача. p> Розширена М-задача стосовно вихідної завданню записується таким чином:
; (10....
