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



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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



 

  Запаси
               
      80 -
 
 

 

  + 40
 
 

 

       
      +     -          
Заявки

 

 

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

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

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

b1 = 80 т.; b2 = 100 т.; b3 = 110 т.; b4 = 70 т.; а1 = 100 т.; а2 = 120 т.; а3 = 140 т.;

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

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

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

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-ї незайнятої клітинки буде від’ємним, то це свідчить про те, що переміщення вантажу в цю точку знижують загальну вартість перевезень, якщо ж , то переміщення в цю точку збільшується вартість перевезень; якщо , то вартість перевезень не змінюється.

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

;

;

α31 = 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. Приймаємо будь-який початковий потенціал ui для i-го ряду таблиці; шукаємо заповнену клітинку (ij), для якої і визначаємо відповідний потенціал та рахуємо: vj = lij - ui . Робимо аналогічні розрахунки для решти рядів і колонок таблиці, спираючись на вже розраховані транспортні потенціали.

 

Таблиця 3.5

 

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

 

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

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

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

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

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

; ;

;

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

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

; ; ;

; ; .

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

 

Таблиця 3.6

 

 
               
              -             +  
    -1                        
    -4         3 +         -    

 

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

 



Последнее изменение этой страницы: 2016-04-18; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.230.143.40 (0.012 с.)