5.5.4. Знаходження змінної, що виводиться з базису (побудова циклу)

Цей крок еквівалентний використанню умови допустимості в симплекс-методі. Оскільки всі коефіцієнти в обмеженнях транспортної задачі дорівнюють або нулю, або одиниці, відношення, що використовуються під час перевірки умови допустимості, завжди будуть мати знаменник, що дорівнює одиниці. Тому значення базисних змінних одразу ж дають відповідні відношення.

Для визначення мінімального відношення побудуємо замкнений цикл, який відповідає змінній, що вводиться ( на першiй iтерацiї). Призначення цього циклу – компенсувати зміну небазисної змінної з метою відновлення балансу за рядками та стовпчиками (цей цикл називають компенсаторним).

Цикл починається та закінчується обраною небазисною змінною. Він складається з послідовності горизонтальних та вертикальних (зв’язаних) відрізків, кінцями яких повинні бути базисні змінні (за винятком тих кінців, які стосуються змінної, що вводиться до базису). Це означає, що кожна клiтина, що стоїть у вершині (зламі) циклу, повинна містити базисну змінну. Табл. 5.5 ілюструє цикл, який відповідає ввідній змінній для початкового базисного розв’язку задачі з табл. 5.2. Цей цикл можна виразити за допомогою базисних змінних таким чином:.Несуттєво, у якому напрямі (за чи проти годинникової стрілки) проводиться обхід циклу. Відзначимо, що відповідно до наступної теореми 4 та її наслідкiв для кожного базисного розв’язку та відповідної небазисної змінної можна побудувати лише один цикл.

Теорема 4 (про єдиність циклу)

Сукупність векторів ,(i,j)Î R (R — деяка множина пар індексів) буде лінійно-залежною тоді і тільки тоді, коли з множини відповідних їм клітин транспортної задачі можна обрати частину, що утворює цикл.

Наслідок 1. Допустимий розв’язок транспортної задачі є базисним тоді, і тільки тоді, коли з клітин, що займає цей розв’язок, не можна утворити жодного циклу.

Наслідок 2. Якщо таблиця транспортної задачі містить базисний розв’язок задачі (5.1) — (5.3), то для кожної вільної клітини цієї таблиці можна утворити один і тільки один цикл, що містить цю клітину та деяку частину зайнятих клітин.

Нехай маємо деякий ДБР {} i нехай за змiнну, що вводиться у базис, обрано змiнну(їй вiдповiдає клiтина транспортної таблицi). Згiдно з нас­лiдком 2 для небазисної змiнноїзавжди iснує компенсаторний цикл клiтин, що замикається на клiтинi, і при тому лише єдиний. При цьому змiннiйнадається деяке значення  0.

Перемiщення по циклу будь-якого числа  не змiнить балансових рiвностей по рядках i стовпчиках таблицi. I при цьому для компенсацiї змiни колишньої небазисної змiнної деякi базиснi змiннi збiльшуються на, а деякi — зменшуються на .

Позначимо знаком "+" ті клiтини циклу, які вiдповiдають базисним клiтинам, що збiльшуються на , а знаком "–" – ті, що зменшуються на . Множина пар iндексiв базисних змiнних вiдповiдно розбивається на три пiдмножини, що не перетинаються:

При довiльному виборi значення  деякi змiннi у новому розв’язку можуть стати вiд’ємними. Отже, щоб новий розв’язок залишався допустимим, має виконуватися така умова:

(5.19)