вже заповнені. Тоді елементи j-го стовпця визначають у Згідно з формулою
(3.3.5)
Якщо, то Х 0 - Оптимальний план Т-завдання. Якщо, то переходимо до першої ітерації. p> (k +1) - я ітерація. Кожна ітерація складається з двох або трьох етапів. Ітерація починається першим етапом, а закінчується другим. Між першим і другим етапами в загальному випадку кілька разів можуть бути проведені третій і перший етапи.
Припустимо, що вже проведено k ітерацій, причому. У цьому випадку необхідно, використовуючи матриці З k і Х k , провести наступну (k +1) - ю ітерацію. Перед початком ітерації виділяють знаком '+' ті стовпці матриці З k , для яких нев'язки за стовпцями дорівнюють
.
Перший етап. Якщо все ненульові елементи матриці З k опиняться в виділених стовпцях, то переходять до третього етапу. В іншому випадку нехай деякий невиділений нуль знаходиться в-му рядку і в-м стовпці. Тоді обчислюють значення нев'язності-й рядки:
.
Можливий один з двох випадків: 1), 2). У першому випадку-й рядок З k відзначають знаком '+' Праворуч від неї, а сам невиділений нуль відзначають штрихом. Далі переглядають елементи-й рядки, які лежать у виділених стовпцях і шукають серед них суттєві нулі (Нагадаємо, що істотним нулем З k називається такий елементВ , Для якого). Якщо таким істотним нулем виявився елемент, а сам стовпець пЃ - виділений, то знак виділення '+' на колонку пЃ знищують, а сам цей нуль відзначають зірочкою.
Потім переглядають пЃ-й стовпець і відшукують у ньому нуль (нулі), розташовані у відмінних від-й рядках. Якщо такий нуль є, то відзначають його штрихом і аналізують невязку його рядки.
Далі процес пошуку нулів і виділення їх (штрихами або зірочками) триває аналогічно, і за кілька кроків він закінчується одним з наступних фіналів:
1) знайдемо черговий невиділений нуль матриці З k , для якого невязкая в рядку. Тоді відзначивши його штрихом, переходимо до другого етапу;
2) всі нулі матриці З k виявилися виділеними, причому для кожного з нулів, що виділяються штрихом, нев'язка. Тоді переходимо до третього етапу.
У другому випадку, зазначивши цей нуль штрихом, відразу переходимо до третього етапу.
Другий етап. Полягає в побудові ланцюжка з нулів матриці З k , відмічених штрихами і зірочками, і в подальшому переході до нової матриці Х k +1
Нехай для деякого нуля зі штрихом матриці З k , розташованого, наприклад, у позиції (), нев'язка рядка. Починаючи з цього елемента, будують ланцюжок з відмічених нулів матриці З k : рухаючись по стовпці, вибирають нуль зі зірочкою, далі рухаючись від нього по рядку, знаходять нуль зі штрихом. Потім рухаються від нього по стовпці пЃ 2 до наступного нулю із зірочкою і т.д. Такий послідовний перехід від 0 'до 0 * по стовпці і від 0 * до 0 'по рядку здійснюють до тих пір, поки це можливо.
Можна довести, що процес побудови ланцюжка однозначний і закінчений, ланцюжок не має циклів, починається і закінчується нулем зі штрихом.
Після того як ланцюжок виду
В
побудована, здійснюють перехід до матриці від матриці Х k за формулами
(1.3.7)
де (1.3.8)
Таким чином,-мінімальний елемент серед сукупності парних елементів ланцюжка, нев'язності рядки, де починається ланцюжок, і шпальти, де вона закінчується.
Обчислюємо невязку для
На цьому (k +1) - я ітерація закінчується.
Третій етап. Отже, припустимо, що всі нулі виділені. Третій етап полягає в переході від матриці З k до еквівалентної матриці З ' k , в якій з'являється новий невиділений нуль (Або нулі). Нехай, де мінімум вибирають з усіх невиділених елементів матриці З k . Тоді з усіх елементів невиділених рядків матриці З k віднімають h, а до всіх елементів виділених стовпців додають h. В результаті отримують матрицю З ' k ( З ' k ~ C k ), в якій всі істотні нулі матриці З k залишаються нулями, і крім того, з'являються нові невиділені нулі.
Далі переходять до першого етапу, і залежно від його результату або переходять до другого етапу, або знову повертаються до третього етапу. За кінцеве число повторів пари етапів третій - перший обов'язково перейдемо до другого етапу.
Якщо після виконання другого етапу то Х k +1 - оптимальний план. В іншому випадку переходимо...
