льнити потребу другого замовника. Пола-гаю, вписуємо це значення в клітку і виключаємо з розгляду другий стовпець. На базі залишається змінений запас. У що залишилася новій таблиці з трьома рядками і чотирма стовпцями кліткою з найменшим значенням клітина, де. Заповнюємо описаним вище способом цю клітку і аналогічно заповнюємо наступні клітини. У результаті виявляються заповненими (У наведеній послідовності) наступні клітини:
.
На п'ятому кроці клітин з найменшими значеннями виявилося дві. Ми заповнили клітку для, поклавши. Можна було вибрати для заповнення іншу клітину, поклавши, що призведе в результаті до іншому опорного плану. Загальний обсяг перевезень у тонно-кілометрах для цього плану складе
.
Зауваження. У діагональному методі не враховуються величини тарифів, в методі ж найменшої вартості ці величини враховуються, і часто останній метод призводить до плану з меншими загальними витратами (що і має місце у нашому прикладі), хоча це й не обов'язково.
Крім розглянутих вище способів іноді використовується, так званий, метод Фогеля. Суть його полягає в наступному: У розподільній таблиці по рядках і стовпчиках визначається різниця між двома найменшими тарифами. Відзначається найбільша різницю. Далі в рядку (стовпці) з найбільшою різницею заповнюється клітка з найменшим тарифом. Рядки (стовпці) з нульовим залишком вантажу надалі в розрахунок не приймаються. На кожному етапі завантажується тільки одна клітина. Розподіл вантажу провадиться, як і раніше. p> 4.Понятіе потенціалу і циклу.
Для переходу від одного базису до іншого при вирішенні транспортної задачі використовуються так звані цикли.
Циклом перерахунку або коротше, циклом в таблиці перевезень називається послідовність невідомих, задовольняє таким умовам:
1. Одне з невідомих послідовності вільне, а всі інші - базисні.
2. Кожні два сусідніх у послідовності невідомих лежать або в одному стовпці, або в одному рядку.
3. Три послідовних невідомих не можуть перебувати в одному стовпці або в одному рядку.
4. Якщо, починаючи з якого-небудь невідомого, ми будемо послідовно переходити від одного до наступного за ним неизв стному то, через кілька кроків ми повернемося до вихідного невідомого.
Друга умова означає, що у двох сусідніх невідомих у циклі або перші, або другі індекси однакові.
Якщо кожні два сусідніх невідомих циклу з'єднати відрізком прямої, то буде отримано геометричне зображення циклу - замкнута ламана з чергуються горизонтальних і вертикальних ланок, одна з вершин якої знаходиться у вільній клітці, а інші - в базисних клітинах.
Можна довести, що для будь-якої вільної клітини таблиці перевезень існує один і тільки один цикл, що містить вільний невідоме з цієї клітини, і що число вершин у циклі завжди парне.
Так, наприклад, в таблиці перевезень, складеної за діагонального методу при рі...
