![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод потенціалів
Припустимо, що оплату перевезень здійснюють спільно виробник і споживач. Вони вносять так звані платежі: виробник платежі Суму цих платежів назвемо псевдовартістю:
При цьому виконуються умови: у всіх базисних клітинах псевдовартість повинна дорівнювати вартості перевезень:
де Технологія призначення платежів проста завдяки такому факту. Всього платежів Таблиця 2.4
Якщо Бачимо, що у клітині (3, 1) ціна циклу
Для цієї клітини доцільно побудувати цикл (позначений у табл. 2.4). Цей цикл має деяку особливість: величина
Отримаємо табл. 2.5 і знову призначимо платежі. Таблиця 2.5
Як видно з табл. 2.5, платежі можуть бути і від’ємними ( Таблиця 2.6
Здійснимо цикл для клітини (3, 2). Наведемо табл. 2.7 Таблиця 2.7
Тепер залишається лише одна клітина (3; 3) з від’ємною ціною:
Маємо: Таблиця 2.8
У табл. 2.8 всі псевдовартості менші за вартості, тому план оптимальний: всі інші Спостерігаємо той неочевидний факт, що перевезення
Алгоритм методу потенціалів: 1. Складаємо транспортну таблицю. 2. Будуємо допустимий і одночасно базисний план за методом північно-західного кута або за іншим методом. Знаходимо початкове значення цільової функції. 3. Призначаємо платежі. 4. Знаходимо вільну клітину, де 5. Фіксуємо оптимальні значення перевезень. Кінець. Крім методу потенціалів, існують інші ефективні методи розв’язування ТЗ, зокрема так званий угорський метод. Його досить складний алгоритм застосовний для розв’язування частинного випадку ТЗ – задачі про призначення.
|