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

 

					Запаси
		80 -	+ 40
		+	-
Заявки

 

 

Із застосуванням транспортних таблиць Т-задача формулюється наступним чином: визначити такі позитивні значення обсягів перевезень , сума яких по кожному і –му ряду () дорівнює , і сума яких по кожній j-й колонці () дорівнює , при цьому сума добутків () по всіх клітинках буде мінімальною.

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

Згідно таблиці 4 маємо: m = 3; n = 4.

b₁ = 80 т.; b₂ = 100 т.; b₃ = 110 т.; b₄ = 70 т.; а₁ = 100 т.; а₂ = 120 т.; а₃ = 140 т.;

Заповнення обсягів перевезень починаємо з клітинки (звідси назва методу). Принцип заповнення: задовольнити максимально можливий обсяг замовлення ; якщо обсягу не вистачає, беремо частину від , якщо в щось залишається, віддаємо решту до і т.д.

Для розглянутого випадку робимо наступне:

1. Задовольнимо , решту відправимо до B₂;

2. Оскільки ще не задовільнено, додамо необхідний обсяг за рахунок (ще 80); решту відправимо до ;

3. Щоб повністю задовольнити , додамо необхідний обсяг за рахунок (ще 70). Решту відправимо до , задовольнив таким чином його повністю.

Підрахуємо кількість ненульових перевезень (зайнятих клітинок). Таких є 6, що відповідає обов'язкової умові (n + m – 1) = (4 + 3 – 1) = 6. Оскільки суми перевезень по рядах і колонках відповідають () і (), отриманий план перевезень є можливим і опорним, тому що цей план є початковим. Для отриманого плану можливо підрахувати загальні витрати на здійснення всіх перевезень. Якщо приймемо для спрощення С = 1 грн (вартість 1 ткм), то

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

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

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

Для кожного такого контуру знаходимо вартісну характеристику переміщення одиниці вантажу в незайняту клітинку (), не змінюючи баланс сум перевезень в рядках та стовпчиках. Для переміщення, наприклад, 1 т вантажу в отримуємо збільшення вартості на (), але для збереження балансу вантажів в рядках і стовпчиках зменшуємо на 1 т вантаж в клітинці , що викличе зменшення вартості перевезень на (). Оскільки зменшується на 1 т, додамо в клітинку також 1 т, що викличе збільшення вартості перевезення на (). Однак збільшення на 1 т повинно призвести до зменшення на 1 т, тобто до зменшення вартості перевезень на (). Це зменшення буде скомпенсоване раніше проведеним додаванням 1 т в незайняту клітинку . Таким чином, додавання 1 т в незайняту клітинку призведе до зміни вартості на величину вартісної характеристики (при С = 1 грн/ткм):

Іншими словами, переміщення одиниці вантажу (або будь-якого об’єму) по контуру не викличе зміни вартості перевезень, тобто така модернізація початкового плану недоцільна. Відзначимо, що вартість С = 1 грн/ткм входить в як додатній коефіцієнт при алгебраїчній сумі відстаней по даному контуру, тому будемо визначати в незайнятій (ij)-ї клітинці як алгебраїчну суму відстаней по даному контуру, причому для даної незайнятої клітинки ця відстань приймається завжди зі знаком “+”, потім за мірою просування по контуру (або в одну, або в іншу сторону – напрям проходження контуру не має значення) відстані приймають послідовно знаки “-” або “+”.

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

Визначаємо для всіх незайнятих клітинок:

;

;

α₃₁ = 9 – 4 + 7 – 6 + 1 – 6 = 1;

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

Об’єм вантажу, що переміщається, визначається як мінімальний з від’ємних об’ємів по даному контуру (). Таким чином, переміщення вантажу по даному контуру дозволить максимально завантажити клітинку і повністю розвантажити клітинку . Очевидно, що при цьому стане рівним (80 – 70) = 10, а стане рівним (40 + 70) = 110. Інші значення для даного контуру ; .

Очевидно, що загальна вартість перевезень повинна при цьому змінитися на:

і має бути рівною

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

 

 

Для отриманого плану перевезень маємо:

;

;

;

Перевіряємо загальну вартість перевезень:

.

Таблиця 3.4

 

					Запаси
		-		+
		+		-
Заявки

 

що співпадає з очікуваною вартістю перевезень. Але цей план не є також оптимальним, так як , тому будуємо замкнутий контур для клітинки , що має , і переносимо (згідно контуру в таблиці 1.4) в клітинку . Знову заповнюємо транспортну таблицю для скоректованого плану(див. табл. 3.5). При цьому зменшення вартості повинно складати , а загальна вартість

, і т.д.

Нагадаємо, що план буде оптимальним в тому випадку, якщо всі вартісні характеристики незаповнених клітинок будуть невід’ємними (). Після цього процес пошуку оптимального плану перевезень завершено. Зокрема для даного плану оптимальним буде наступний план перевезень, який має L_опт=950 грн. Цей метод оптимізації має назву розподільчий.

Більш простим методом оптимізації плану перевезень є метод потенціалів, суть якого полягає у наступному.

1. Приймаємо будь-який початковий потенціал u_i для i-го ряду таблиці; шукаємо заповнену клітинку (ij), для якої і визначаємо відповідний потенціал та рахуємо: v_j = l_ij - u_i. Робимо аналогічні розрахунки для решти рядів і колонок таблиці, спираючись на вже розраховані транспортні потенціали.

 

Таблиця 3.5

 

					Запаси
Заявки

 

2. Після визначення i (; ) перевіряємо нерівність для всіх (ij) незайнятих клітинок таблиці (тобто для ). Якщо ця нерівність має місце для усіх без виключення незайнятих клітинок, план перевезень є оптимальним.

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

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

Наприклад, є певний опорний план перевезень (табл. 3.6). Розрахуємо потенціали і , використовуючи саме зайняті клітинки, і занесемо їх в додаткові стовпчик і рядок.

Приймаємо , тоді ; . Використовуючи вже отримані потенціали, визначаємо решту потенціалів:

; ;

;

Відмітимо, що для отриманого плану (при C = 1 грн/ткм) маємо L = 980 грн, що набагато краще опорного плану, отриманого за методом північно-західного кута (L₁=1540 грн.).

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

; ; ;

; ; .

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

 

Таблиця 3.6

 

			-		+
	-1
	-4		3 +		-

 

Для цього шукаємо контур, що містить у решті кутів зайняті клітинки. Це контур: . Оскільки ми завантажуємо , присвоюємо їй знак “+”, потім, пересуваючись по контуру, послідовно міняємо знаки. Мінімальне абсолютне значення від’ємного обсягу знаходиться в клітинці і дорівнює x = 30 т. Пересуваємо цей обсяг по контуру з урахуванням знаків і отримуємо новий план перевезень. Далі процес повторюється до отримання оптимального плану.