Тема 3. Транспортна задача.

Лекція 8

Тема лекції: Транспортна задача (продовження)

Мета: ознайомити студентів з основними теоремами та методами розв’язання транспортної задачі

 

План лекції

5. Метод потенціалів.

6. Приклад вирішення транспортної задачі.

7. Ускладнені задачі транспортного типу.

 

 

Література:

1. Лавріненко Н.М., Латинін С.М., Фортуна В.В., Безкровний О.І. Основи економіко-метематичного моделювання: Навч. Посіб. - Львів: «Магнолія 2006», 2010.- 540с.

2. Іванюта І. Д. Практикум з математичного програмування: Навчальний посібник / І. Д. Іванюта, В. І. Рибалка, І. А. Рудоміно-Дусятська. – К.: «Слово», 2008. - 296 с.

3. Кучма М. І. Математичне програмування: приклади і задачі: Навчальний посібник / М.І. Кучма. – Львів: «Новий Світ - 2000», 2006. - 344 с.

4. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высшая школа, 1993. – 336 с.

 

 

5. Метод потенціалів.

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

v_j - u_i = с_ji для x_ji>0 (6)

Оскільки заповнених клітинок є m+n-1, то система рівнянь (6) із m+n невідомих містить m+n-1 рівнянь. Прийнявши одне невідоме за нуль, наприклад, u₁=0, решту знаходимо.

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

Δ_ji =v_j - u_i - с_ji

Якщо, Δ_ji ≤0, то побудований опрний план є оптимальним.

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

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

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

Для вибраної вільної клітинки і клітинок, що пов’язані з нею циклом, здійснюють перерозподіл продукції в межах цього циклу за такими правилами:

· Кожній вершині циклу приписують певний знак, причому вільній клітинці – знак «+», а всім іншим по черзі- знаки «-» та «+»;

· У поржню клітинку переносять менше з чисел x_ji, що стоять у клітинках зі знком «-». Одночасно це число додають до відповідних чисел, які розміщені в клітинках зі знаком «+».

 

6. Приклад вирішення транспортної задачі.

Приклад 1. Розв’язати транспортну задачу.

 

						ui
vj

7. Ускладнені задачі транспортного типу.

Дуже часто при складанні математичної моделі задачі транспортного типу доводиться враховувати цілу низку додаткових обмежень, а потім застосовувати метод потенціалів.

Розглянемо ситуації, які зустрічаються найчастіше:

· Заборона на постачання від i-го до j – го споживача. Якщо окремі поставки від визначених постачальників до певних споживачів повинні бути виключені з плану перевезень, то це досягається штучним завищенням за цим маршрутом транспортних витрат (якщо витрати мінімізуються). Тобто тариф на перевезення за цим маршрутом покладається рівним деякому великому числу М.

· Фіксовані постачання, тобто певний обсяг поставок за деяким маршрутом обов’язково повинен ввійти в оптимальний план перевезень незалежно від вигідності. Наприклад, за маршрутом необхідно перевезти рівно d одиниць вантажу. У цьому випадку зменшують запас вантажу у відповідного постачальника і попит відповідного споживача на величину обов’язкової поставки d, а також вводять заборону на постачання за маршрутом і далі розв’язується отримана задача. Отриманий методом потенціалів розв’язок коригується з урахуванням цієї обов’язкової поставки і отримують .

· Обмеження на мінімальні постачання. Якщо за маршрутом необхідно перевезти не менше d одиниць вантажу, то в цьому випадку, аналогічно, як і при фіксованих постачаннях, зменшуються на величину d запаси відповідного постачальника і попит споживача. Але в цьому випадку не вводиться заборона на постачання за маршрутом .

· Обмеження на перепускні спроможності за певним транспортним маршрутом. Наприклад, за маршрутом можна перевезти не більше d одиниць вантажу. Тоді - й стовпчик розбивається на два та з попитом, який складає і відповідно. Транспортні тарифи в нових стовпчиках такі ж, але в клітині ставиться штучно завищений (блокующий) тариф. У оптимальному плані перевезень ці два стовпчики знову об’єднують в один.

Приклад 2. Розвязати транспортну задачу:

Додаткова умова: попит третього споживача задовольнити повністю за маршрутом перевезти рівно 10 од. продукції.