Побудова опорного плану транспортної задачі методом подвійної переваги

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

  1. На першому кроці, у кожному стовпці транспортної таблиці відзначають знаком “V” комірку з найменшою вартістю.
  2. Потім те ж проробляють в кожному рядку. В результаті виконання другого кроку, деякі комірки транспортнї таблиці будуть містити відмітку “VV”.
  3. На останньму кроці, у комірки з подвійними відмітками (подвійна перевага) поміщають максимально можливі обсяги перевезень, щоразу виключаючи з розгляду відповідні стовпці або рядки. Потім розподіляють перевезення по комірках з одиничною відміткою. Решта перевезення розподіляють згідно  алгоритму методу мінімального елемента.

Читати далі

Перехід від одного плану перевезень в транспортній задачі до іншого використовуючи цикл перерахунку

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

Графічне представлення циклу перерахунку

Графічне представлення можливих конфігурацій циклу перерахунку

Читати далі

Транспортна задача лінійного програмування

Під назвою транспортна задача поєднується широке коло задач з єдиною математичною моделлю. Дані задачі відносяться до класу задач лінійного програмування і тому можуть бути вирішені відомим симплексним методом. Однак, звичайна транспортна задача має велике число змінних і розв’язання її симплексним методом може виявитись знадто громіздким. З іншого боку матриця системи обмежень транспортної задачі вельми своєрідна, тому для її рішення розроблені спеціальні методи. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім, поліпшуючи його, отримати послідовність опорних рішень, яка завершується оптимальним рішенням.

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

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

Читати далі