25
250
50
200
Потреби
170
110
100
120
200
700
Вибір в якості х мінімального серед чисел, що стоять в негативних вершинах циклу, забезпечує допустимість нового базису.
Якщо мінімальне значення серед базисних невідомих, стоять в негативних вершинах циклу, приймається не в одній негативній вершині, то вільної залишають тільки одну з них, а в інших клітинах з тим же мінімальним значенням пишуть нулі. У цьому випадку нове базисне рішення буде виродженим.
Може статися, що й саме мінімальне значення серед чисел в негативних клітинах дорівнює нулю. Тоді перетворення таблиці перевезень зведеться до перестановки цього нуля у вільну клітину. Значення всіх невідомих при цьому залишаються незмінними, але рішення вважаються різними, так як різні базиси. Обидва рішення виродилися. p> Описане вище перетворення таблиці перевезень, в результаті якого перетвориться базис, називається перерахунком по циклу.
Зауважимо, що невідомі, що не входять в цикл, цим перетворенням не будуть зачіпатися, їх значення залишаються незмінними і кожне з них залишається або в групі базисних, або в групі вільних невідомих, як і до перерахунку.
З'ясуємо тепер, як перерахунок по циклу впливає на загальний обсяг витрат на перевезення і при якої умови ці витрати стають менше.
Нехай - деякий вільний невідоме, для якого ми побудували цикл і здійснили перерахунок по циклу з деяким числом . Якщо вершині циклу, що знаходиться в рядку і стовпці таблиці перевезень, приписаний знак "+", то значення невідомого , знаходиться в цій вершині, збільшується наВ , що в свою чергу викликає збільшення витрат на . де - тариф, відповідний цій клітці; якщо ж зазначеної вершині приписаний знак "-", то значення невідомого зменшується на, що викликає зменшення витрат на.
Складемо тарифи, відповідні позитивним вершин циклу, і віднімемо з цієї суми суму тарифів, відповідних негативним вершин циклу; отриману різницю назвемо алгебраїчною сумою тарифів для даного вільного невідомого. Підрахунок алгебраїчної суми тарифів можна витлумачити і так: пріпішем тарифами ті ж знаки, які приписані відповідним вершинам циклу, тоді алгебраїчна сума тарифів дорівнює сумі таких тарифів зі знаком ("відносних тарифів").
Тепер, очевидно, ми можемо, укласти, що в цілому при перерахунку але циклу, відповідному вільному невідомому загальний обсяг витрат на перевезення зміниться на твір алгебраїчної суми тарифів на, тобто на величину. Отже, якщо алгеб...
