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

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

Для того, щоб закріпити даний алгоритм більш детально розглянемо наступний приклад: на три бази pnz3 поступив товар в кількості 140; 180; 160. Цей груз треба перевезти в п'ять пунктив призначення pnz4 в кількостях 60; 70; 120; 130; 100. Тарифи перевезення записані в наступній таблиці:

pnz5

Знайти план перевезення даної транспортної задачі методом північно-західного кута.

Для цього, спочатку, не враховуючи вартостей перевезення, задовільняємо потреби першого пункту призначення pnz6, використовуючи запаси першого пункту відправлення pnz7. У нашому прикладі потреби в товарі пункту pnz61 становлять pnz8, а запаси відправника — pnz9. Тобто із запасів першого пункту відправлення ми можемо повністю задовільнити потреби першого пункту призначення. Тому у клітинку pnz10 записуємо менше із значень pnz11, pnz21, тобто 60. Після цього наша таблиця набуде такого вигляду:

pnz13

Тепер переходимо до задоволення потреб другого пункту призначення — pnz111, потреби якого становлять pnz12. Після задоволення потреб пункту pnz71, залишок запасів першго пункту відправлення становить 140 — 60 = 80 (цього достатно, щоб задовільнити потреби і другого пункту призначення). Тому записуємо в клітинку pnz14 значення 70 і переходимо до задоволення потреб пункту pnz15.

pnz16

Залишок запасів у першого пункту призначення, після задоволення потреб пунктів призначення pnz62 і pnz112, становить 140 — 60 — 70 = 10. Тому третьому споживачеві від першого відправника можемо перевезти лише 10 одиниць продукції. Отже, в клітинку pnz17 помістимо число 10.

pnz18

Після цього, оскільки запаси першого відправника повністю вичерпані, переходимо до використання запасів наступного постачальника pnz19. Його запаси рівні pnz20. А незадоволені потреби третього пункту призначення 120 — 10 = 110. Тому в клітинку pnz211 записуємо число 110, і третій споживач, у такий сопсіб, також отримав необхідну кількість продукції.

pnz22

Переходимо до задоволення потреб наступного споживача, а саме pnz23. У результаті часткового використання запасів другого пункту відправлення його залишок продукції становить 180 — 110 = 70. Отже від другого пункту відправлення до четвертого пункту призначення можна перевезти лише 70 одиниць продукції. Тому клітинка pnz24 міститиме число 70, і цим запаси постачальника pnz191 будуть також повністу вичерпані.

pnz25

Переходимо до використання запасів останнього пункту відправлення pnz26. Залишок потреб четвертого пункту становить 130 — 70 = 60. Для їх задоволення скористаємось запасами відправника pnz261. У клітинку pnz27 запишемо число 60 і потреби четвертого пункту також повністю задоволені.

pnz28

Переходимо до останнього споживача pnz29 з потребами pnz30, які повністю задовольняються за рахунок залишку третього відправника 160 — 60 =100, тобто у клітинку pnz31 запишемо число 100. Таким чином ми отримали кінцеву таблицю, у заповнених клітинках якої містяться числа, які означають можливий план перевезення продукції з загальною вартістю F = 60 * 2 + 70 * 3 + 10 * 4 + 110 * 1 + 70 * 4 + 60 * 7 + 100 * 2 = 1380 умовних одиниць.

pnz321

Матеріал був корисним, поділись в соціальних мережах:

Коментарі

2 коментаря по темі “Метод північно-західного кута”
  1. Артур пише:

    Результат вартості можливого плану неправильний - повинен бути 1380

  2. admin пише:

    Дякуємо за інформацію Артур. Виявлену Вами помилку було виправлено. Опорний план розглядуваної транспортної задачі виводиться правильно.

Якщо тобі сподобалась дана тема, залиш свій коментар