- •Загальні положення
- •1. Симплекс-метод
- •2. Метод потенціалів
- •2.1. Загальна постановка транспортної задачі
- •2.2. Методи побудови початкового плану
- •2.2.2. Метод найменшої вартості
- •2.2.3. Метод подвійної переваги
- •2.2.4. Випадок виродження
- •2.3. Матричний розв’язок транспортної задачі методом потенціалів
- •2.3.1. Побудова початкового плану
- •2.3.2. Обчислення потенціалів
- •2.3.3. Перевірка за умовою оптимальності
- •2.3.4. Цикл перерахування
- •2.4. Мережний спосіб розв’язку транспортної задачі методом потенціалів
- •2.4.1. Побудова початкового плану
- •2 .4.2. Обчислення потенціалів
- •2.4.3. Перевірка незавантажених ребер за умовою оптимальності (2.4)
- •2.4.4. Цикл перерахування
- •Порядок виконання й обсяг індивідуальних завдань
2.2. Методи побудови початкового плану
2.2.1. Метод північно-західного кута (діагональний). Таку назву одержав тому, що призначення перевезень починає ліворуч зверху (з північно-західного кута матриці) із клітки I.I (див. табл.6),
Таблиця 6
споживачі
ресурси
споживачів
ресурси
постачальників
Для призначення першого перевезення порівнюємо ресурси першого постачальника (підсумок першого рядка) 20 - з потребою першого споживача (підсумок першого стовпця) 15. Меншу величину (15) поміщаємо в клітку 1.1 і віднімаємо з обох порівнюваних величин. У підсумку першого стовпця ставимо букву "до" (потреба першого споживача задоволена), а в підсумку першого рядка проставляємо залишок 20-15=5. Перший стовпець з подальшого розгляду виключаємо. Оскільки залишок залишився в першому рядку, то перевезення призначаємо в сусідню клітку рядка 1.2. Порівнюючи підсумки першого рядка і другого стовпця, установлюємо перевезення рівне 5, віднімаючи її з порівнюваних величин. У підсумку першого рядка ставимо букву "до" (ресурси першого постачальника вичерпані), з подальшого розгляду його виключаємо, а у підсумку другого стовпця проставляємо залишок 25-5=20.
Оскільки залишок залишився в другому стовпці, те наступне перевезення призначаємо в цьому стовпці в клітку 2.2 і так доти, поки в підсумках усіх рядків і стовпців не буде стояти буква "до". У такому початковому плані перевезення розташовані, приблизно, за діагоналлю матриці.
2.2.2. Метод найменшої вартості
В
Таблиця 7
Визначаємо величину перевезення, яку необхідно помістити в неї, і продовжуємо процес до розподілу всього обсягу перевезень.
2.2.3. Метод подвійної переваги
Спочатку переглядаємо всі рядки матриці й у кожній з них відзначаємо яким-небудь умовним значком (наприклад, хрестиком) елемент із мінімальною вартістю. Потім переглядаємо стовпці і також відзначаємо в них елемент із мінімальною вартістю. У клітки, відзначені двічі, поміщаємо максимально можливі перевезення за правилами, описаними раніше. Якщо таких кліток мало, то після них використовуємо клітки, відзначені один раз; якщо ж і їх не вистачає, - то невідмічені клітки з можливо меншою вартістю.
2.2.4. Випадок виродження
При побудові початкового плану будь-яким методом після призначення чергового перевезення з подальшого розгляду виключається або рядок, або стовпець, а після призначення останнього перевезення - і рядок, і стовпець. Тому що сума рядків і стовпців m+n, те призначених перевезень m+n-1, тобто знайдено план - базисний розв’язок задачі. Однак іноді одночасно виключаються і рядок, і стовпець до призначення останнього перевезення, наприклад, тоді підсумки в стовпці і рядку виявилися рівні. Такий випадок називається «випадком виродження». Розв’язати задачу при цьому більшістю методів неможливо.
Щоб число перевезень залишалося рівним m+n-1, уводять нульові перевезення: так званий штучний нуль. У підсумку рядка, що виключається, або стовпця замість букви "до" проставляють як залишок нуль і надалі виконують з ним усі дії як з позитивним числом. Виключають ту сторону або стовпець, де в елементах, куди може потрапити нульове перевезення, великі вартості.
Наприклад, при побудові початкового плану методом найменшої вартості в клітку 2.2 унаслідок рівності підсумків виник випадок виродження. Виключаємо з подальшого розгляду другий рядок, а в підсумку другого стовпця записуємо залишок ПРО , залишаючи його для подальшого розгляду.