Метод найменшої вартості

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

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

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

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

Контрольні питання:

1. Що таке припустимий план перевезень?

2. Суть методу мінімального елементу?

3. Звідки метод «северо-западного угла» одержав свою назву?

4. Суть методу подвійного припущення?

Література [1,7]

Практична робота 9. Створення припустимого плану перевезень.

Мета: навчитись використовувати метод Фогеля.

Задача

Дані пр..роботи №8.

Завдання

1. Знайти припустимий план закріплення споживачів за постачальниками.

2. Знайти транспортну роботу за результатами кожного з методів.

Методичні вказівки Метод Фогеля

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

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

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

Крок З.

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

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

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

г) У всіх інших випадках необхідно перейти до кроку 1.

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

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

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