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