Розв’язання транспортної задачі методом північно-західного кута

Розглядаючи основні принципи формулювання транспортної задачі, ми вияснили, що першим етапом рішення будь-якої задачі такого типу, є побудова початкового опорного плану перевезень, тобто плану, що задовольняє всім її обмеженням.

Зазначимо, що найбільш відомими і водночас напростішими методами, що дозволяють здійснити це є метод північно-західного кута та метод мінімальної вартості.

Основна їх суть полягає в тому, що початковий план перевезень знаходиться не більше ніж за m + n - 1 кроків, на кожному з яких у транспортній таблиці заповнюють одну комірку, яку, в подальшому, називають зайнятою.

Заповнення однієї комірки забезпечує повністю, або задоволення потреб у вантажі одного з пунктів призначення (споживача), або вивезення вантажу з одного з пунктів відправлення (постачальника).

Відрізняються ж отримані за допомогою цих методів плани лише по принципу вибору заповнюваних комірок і в залежності від цього можуть давати плани, більшою чи меншою мірою відмінні від оптимального.

Розглянемо метод північно-західного кута. Для цього припустимо, що умова транспортної задачі задана у вигляді наступної транспортної таблиці:

Транспортна задача метод північно-західного кута

Тоді, згідно з алгоритмом, на першому кроці, із співвідношення x11 = min(a1, b1) знаходимо значення об’єму перевезень від першого постачальника до першого споживача. Зазначимо, що при цьому, можливі три варіанти:

  • якщо a1 < b1, то x11 = a1, рядок i = 1 виключається з подальшого розгляду (запаси постачальника A1 повністю вичерпані), а потреби першого споживача b1 (стовпець j = 1) зменшується на величину a1;
  • якщо a1 > b1, то x11 = b1, стовпець j = 1 виключається з подальшого розгляду (потреби споживача B1 повністю задоволені), а наявність вантажу у першого постачальника (рядок i = 1) зменшується на величину b1;
  • якщо a1 = b1, то x11 = a1 = b1, рядок i = 1 і стовпець j = 1 виключаються з подальшого розгляду. Даний варіант призводить до виродження вихідного плану.

Потім аналогічні операції проробляють з частиною таблиці, починаючи з її північно-західного кута.

На останньому кроці, залишиться один рядок і один стовпець. Після заповнення комірки, яка знаходиться на їх перетині, процес побудови початкового опорного плану методом північно-західного кута завершується.

Після цього, отриманий план необхідно перевірити на вирожденність. Якщо кількість зайнятих комірок дорівнює m + n - 1, то план є невироджених, в іншому випадку – виродженим.

Якщо план вироджений, тобто кількість зайнятих комірок виявилася меншою за число m + n - 1, то незаповнені комірки з мінімальними вартостями перевезень заповнюються нулями, щоб загальна кількість зайнятих комірок стала рівною m + n - 1.

При цьому слід пам’ятати, що в транспортній таблиці не повинно бути жодного прямокутника, всі вершини якого є зайнятими комірками. До прикладу, змінні x11, x12, x21, x22 або x11, x1n, x31, x3n не можуть бути одночасно базисними.

Приклад 1: знайти початковий опорний план перевезень транспортній задачі, заданої наступною таблицею:

Транспортна задача метод північно-західного кута

Для цього, на першому кроці, скориставшись співвідношенням x11 = min(a1, b1) знаходимо значення об’єму перевезень від постачальника A1 до споживача B1:

Метод північно-західного кута - крок №1

Зазначимо, що в даному випадку, стовпець номер один транспортної таблиці  виключається з подальшого розгляду (потреби споживача номер один задоволені в повному обсязі), а наявність вантажу у першого постачальника зменшується на величину b1 = 60, тобто a1 = 80.

Перейшовши до кроку номер два, задовольняємо потреби другого пункту призначення. В результаті отримаємо:

Метод північно-західного кута - крок №2

Тобто за рахунок залишку запасів першого пункту відправлення ми також, в повному обсязі, задовольнили потреби і споживача B2.

Отже, стовпець номер два також виключається з розгляду, а наявність вантажу у постачальника A1 знову-таки зменшується: a1 = 10.

На третьому кроці, задовольняємо потреби споживача B3 (після задоволення потреб пунктів B1 та B2 третьому споживачеві від першого відправника дісталось лише a1 = 10 одиниць продукції):

Метод північно-західного кута - крок №3

Рядок i = 1 виключається з подальшого розгляду, а потреби третього споживача зменшуються на 10 одиниць: b3 = 110.

Проробляючи аналогічні операції далі:

  • Метод північно-західного кута - крок №4, стовпець j = 3 виключається з подальшого розгляду, а наявність продукції на складі A2 зменшується на b3 = 110 одиниць: a2 = 70;
  • Метод північно-західного кута - крок №5, рядок i = 2 виключається з подальшого розгляду, а потреби четвертого споживача зменшуються на a2 = 70 одиниць: b4 = 60;
  • Метод північно-західного кута - крок №6, стовпець j = 4 виключається з подальшого розгляду, а наявність продукції на складі A3 зменшується на b4 = 60 одиниць: a3 = 100;
  • оскільки в транспортній таблиці залишився один рядок (i = 3) та один стовпець (j = 5) – це останній крок процесу, x35 = 100.

на сьомій ітерації, отримаємо кінцеву таблицю, у зайнятих комірках якої містяться числа, які приймаємо в якості початкового опорного плану заданої транспортної задачі (з огляду на те, що кількість зайнятих комірок дорівнює (n + m - 1) = 7 являється невиродженим) з сумарними витратами F = 1380 умовних одиниць.

Транспортна задача метод північно-західного кута

Зауваження: виходячи з того, що при складанні початкового опорного плану методом північно-західного кута вартість перевезення одиниці продукції не враховувалася, то побудований, у такий спосіб, план являється далеким від оптимального.

Блок-схема алгоритму побудови початкового опорного плану методом північно-західного кута.

Транспортна задача метод північно-західного кута

3 коментаря

  1. А звідки ми беремо цифри у верхніх кутах?

  2. Цифри у верхніх кутах беруться з умови задачі і відповідають за вартість перевезення одиниці товару з Аі-го пункту відправлення в Bj-й пункт призначення.

  3. Дуже-дуже дякую за таке детальне пояснення! Все чітко і зрозуміло!

Залишити коментар

Your email address will not be published. Required fields are marked *

*