Здавалка
Главная | Обратная связь

Ціна циклу перерахування



 

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

Наприклад, ціна циклу перерахування, зазначеного в таблиці 5.4, дорівнює (1+3)-(2+6)=4-8= - 4.

Ціна циклу перерахування - це збільшення цільової функції при зрушенні h=1 по циклу перерахування.

Якщо, наприклад, зробити одиничне зрушення по циклу перерахування таблиці 5.5, вийде план перевезень, сумарна вартість якого 430 - 4 = 426.

Має місце твердження: при зрушенні на величину h >= 0 по циклу перерахування з ціною γ , збільшення Δf цільової функції обчислюється за формулою

Δf = γ · h (5.5)

У справедливості формули (5.5) можна переконатися на прикладах таблиць 5.4, 5.5, 5.6. З формули (5.5) виходить, що при додатному зрушенні по циклу перерахування з від’ємною ціною значення цільової функції зменшується. Тому пошук оптимального плану перевезень зводиться до виявлення циклів перерахування з від’ємною ціною й здійснення максимально припустимих зрушень по них. А якщо циклів перерахування з від’ємною ціною не виявиться?

Теорема: Опорний план перевезень, при якому всі цикли перерахування мають від’ємні ціни, є оптимальний.

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

Потенціали

 

Нехай у транспортній задачі з пунктами відправлення А1, А2,..., Аm і пунктами призначення В1, В2,..., Вn є деякий опорний план перевезень. Поставимо кожному пункту відправлення Ai число αi ( ), кожному пункту призначення Вj - число βj ( ) так, щоб для кожної базисної клітинки (p,q) виконувалася рівність

αp + βq = cpq (5.6)

Числа αi і βj називаються потенціалами пунктів відправлення й призначення відповідно.

Для відшукування потенціалів потрібно для кожної базисної клітинки скласти рівняння вигляду (5.6) і вирішити отриману систему m + n – 1 рівнянь із m + n невідомими. Така система має нескінченно багато рішень. Щоб одержати конкретне рішення, один з потенціалів вважають рівним 0.

Знайдемо, наприклад, систему потенціалів для опорного плану, наведеного у таблиці 5.6. Складемо систему рівнянь:

Покладемо α1=0. Тоді β1=2; β3=1; α2=2; α3=1; β2=1.
Доповнимо таблицю 5.6 стовпцем з потенціалами αi і рядком з потенціалами βj, одержимо таблицю 5.7.

 

Таблиця 5.7

 

Пп Пв В1 В2 В3 Запаси αi
А1 2 2 0 1 3 1 1
А2 4 4 60 3 2 3 5
А3 3 3 2 2 40 2 6
Потреби 150=150  
βj    

 

Назвемо псевдовартістю перевезення одиниці вантажу з пункту Аi у пункт Вj величину

Розраховані для таблиці 5.7 псевдовартості розміщені в лівих верхніх кутах цієї таблиці.

Потенціали і псевдовартості мають цікаву економічну інтерпретацію. Припустимо, що є перевізник, що бере з пункту Аi плату αi за вивіз одиниці вантажу, а з пункту Вj - плату βj за ввезення одиниці вантажу. Тоді псевдовартість – це той виторг, що одержує перевізник за перевезення одиниці вантажу з пункту Аi у пункт Вj. Корисно застосувати цю інтерпретацію для кращого розуміння тієї умови оптимальності опорного плану, що буде наведено нижче.

А поки доведемо наступне твердження:

ціна γij циклу перерахунку, що проходить через вільну клітинку (ij), виражається формулою

 

Для доказу розглянемо рисунок 5.1.

 

 
 

 


Рис. 5.1.

Клітинка (ij) - єдина вільна клітка зображеного циклу перерахування. Ціна γij циклу перерахування, відповідно до визначення, дорівнює

Оскільки для базисних клітинок виконуються рівності (5.6), то
можна записати:

, що й було потрібно довести.

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

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

Наприклад, опорний план перевезень таблиці 5.7 не є
оптимальний, оскільки для клітинки (2.2) псевдовартість більше
вартості. Ціна циклу перерахування, що проходить через цю клітинку
від’ємна й дорівнює 2–3=–1 (у цьому можна зайвого разу
переконатися, підрахувавши ціну, виходячи з визначення). Зробивши максимально припустиме зрушення величиною h=40, одержимо таблицю 5.8.

 

Таблиця 5.8

 

Пп Пв В1 В2 В3 Запаси αi
А1 2 2 0 0 3 1 1
А2 4 4 20 2 2 3 5
А3 3 3 1 2 2 6
Потреби 150=150  
βj    

 

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

fmin=40• 1+20• 4+40• 2+50• 3=350 грошових одиниць.

 







©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.