Навігація по сторінці.
Розглядаючи основні принципи формулювання транспортної задачі, ми вияснили, що першим етапом рішення будь-якої задачі такого типу, є побудова початкового опорного плану перевезень, тобто плану, що задовольняє всім її обмеженням.
Зазначимо, що найбільш відомими і водночас напростішими методами, що дозволяють здійснити це є метод північно-західного кута та метод мінімальної вартості.
Основна їх суть полягає в тому, що початковий план перевезень знаходиться не більше ніж за кроків, на кожному з яких у транспортній таблиці заповнюють одну комірку, яку, в подальшому, називають зайнятою.
Заповнення однієї комірки забезпечує повністю, або задоволення потреб у вантажі одного з пунктів призначення (споживача), або вивезення вантажу з одного з пунктів відправлення (постачальника).
Відрізняються ж отримані за допомогою цих методів плани лише по принципу вибору заповнюваних комірок і в залежності від цього можуть давати плани, більшою чи меншою мірою відмінні від оптимального.
Метод північно-західного кута.
Розглянемо метод північно-західного кута. Для цього припустимо, що умова транспортної задачі задана у вигляді наступної транспортної таблиці:
Тоді, згідно з алгоритмом, на першому кроці, із співвідношення знаходимо значення об’єму перевезень від першого постачальника до першого споживача. Зазначимо, що при цьому, можливі три варіанти:
- якщо , то , рядок виключається з подальшого розгляду (запаси постачальника повністю вичерпані), а потреби першого споживача (стовпець ) зменшується на величину ;
- якщо , то , стовпець виключається з подальшого розгляду (потреби споживача повністю задоволені), а наявність вантажу у першого постачальника (рядок ) зменшується на величину ;
- якщо , то , рядок і стовпець виключаються з подальшого розгляду. Даний варіант призводить до виродження вихідного плану.
Потім аналогічні операції проробляють з частиною таблиці, починаючи з її північно-західного кута.
На останньому кроці, залишиться один рядок і один стовпець. Після заповнення комірки, яка знаходиться на їх перетині, процес побудови початкового опорного плану методом північно-західного кута завершується.
Після цього, отриманий план необхідно перевірити на вирожденність. Якщо кількість зайнятих комірок дорівнює , то план є невироджених, в іншому випадку – виродженим.
Якщо план вироджений, тобто кількість зайнятих комірок виявилася меншою за число , то незаповнені комірки з мінімальними вартостями перевезень заповнюються нулями, щоб загальна кількість зайнятих комірок стала рівною .
При цьому слід пам’ятати, що в транспортній таблиці не повинно бути жодного прямокутника, всі вершини якого є зайнятими комірками. До прикладу, змінні або не можуть бути одночасно базисними.
Транспортна задача методом північно-західного кута – розв’язування прикладів.
Приклад 1: знайти початковий опорний план перевезень транспортній задачі, заданої наступною таблицею:
Для цього, на першому кроці, скориставшись співвідношенням знаходимо значення об’єму перевезень від постачальника до споживача :
Зазначимо, що в даному випадку, стовпець номер один транспортної таблиці виключається з подальшого розгляду (потреби споживача номер один задоволені в повному обсязі), а наявність вантажу у першого постачальника зменшується на величину , тобто .
Перейшовши до кроку номер два, задовольняємо потреби другого пункту призначення. В результаті отримаємо:
Тобто за рахунок залишку запасів першого пункту відправлення ми також, в повному обсязі, задовольнили потреби і споживача .
Отже, стовпець номер два також виключається з розгляду, а наявність вантажу у постачальника знову-таки зменшується: .
На третьому кроці, задовольняємо потреби споживача (після задоволення потреб пунктів та третьому споживачеві від першого відправника дісталось лише одиниць продукції):
Рядок виключається з подальшого розгляду, а потреби третього споживача зменшуються на 10 одиниць: .
Проробляючи аналогічні операції далі:
- , стовпець виключається з подальшого розгляду, а наявність продукції на складі зменшується на одиниць: ;
- , рядок виключається з подальшого розгляду, а потреби четвертого споживача зменшуються на одиниць: ;
- , стовпець виключається з подальшого розгляду, а наявність продукції на складі зменшується на одиниць: ;
- оскільки в транспортній таблиці залишився один рядок () та один стовпець () – це останній крок процесу, .
на сьомій ітерації, отримаємо кінцеву таблицю, у зайнятих комірках якої містяться числа, які приймаємо в якості початкового опорного плану заданої транспортної задачі (з огляду на те, що кількість зайнятих комірок дорівнює являється невиродженим) з сумарними витратами умовних одиниць.
Зауваження: виходячи з того, що при складанні початкового опорного плану методом північно-західного кута вартість перевезення одиниці продукції не враховувалася, то побудований, у такий спосіб, план являється далеким від оптимального.
А звідки ми беремо цифри у верхніх кутах?
Цифри у верхніх кутах беруться з умови задачі і відповідають за вартість перевезення одиниці товару з Аі-го пункту відправлення в Bj-й пункт призначення.
Дуже-дуже дякую за таке детальне пояснення! Все чітко і зрозуміло!