Відмінності між версіями «Методи побудови опорного плану ТЗ.»

Версія за 18:44, 4 травня 2012

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

Ідея методу північно-західного кута полягає в тому, що заповнення таблиці починають, не враховуючи вартостей перевезень, з лівого верхнього (північно-західного) кута. У клітину записують менше з двох чисел Неможливо розібрати вираз (невідома помилка): a_{i}

та Неможливо розібрати вираз (невідома помилка): b_{i}

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

Метод північно-західного кута є найпростішим, однак і найменш ефективним. Визначимо загальну вартість перевезень згідно з початковим опорним планом.

Неможливо розібрати вираз (невідома помилка): F=110\times 4+40\times 4+10\times 3+50\times 1+10\times 4+80\times 2=880

(ум. од.).

Теорема

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

Метод мінімальної вартості

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

В результаті таких міркувань отримали початковий опорний план, загальна вартість перевезень для якого становить: Неможливо розібрати вираз (невідома помилка): F=70\times 4+80\times 5+60\times 1+50\times 1+40\times 2=870

Значення цільової функції менше за попередній варіант, значить цей план ближчий до оптимального.

Метод подвійної переваги

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

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

Неможливо розібрати вираз (невідома помилка): F=110\times 4+40\times 5+60\times 1+50\times 1+40\times 2=830

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