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

Знаходження початкового опорного плану транспортної задачі методом плаваючих зон

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

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

Читати далі

Розв’язок транспортної задачі розподільчим методом

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

Читати далі

Використання методу диференціальних рент для знаходження оптимального плану транспортної задачі

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

  1. У кожному стовпчику транспортної таблиці знаходимо мінімальний тариф. Знайдені тарифи позначаємо колами, що їх оточують, і заповнюємо відповідні комірки максимально можливими перевезеннями. Таким чином, отримуємо розподіл, що в загальному може не задовільняти обмеженням транспортної задачі (якщо отриманий таким чином розподіл задовільняє обмеженням задачі, то він вважається оптимальним, і алгоритм методу диференціальних рент на цьому закінчується).
  2. Скорочуємо нерозподілені поставки продукту так, щоб при цьому загальна вартість перевезень залишалась мінімальною. Для цього виконуємо наступні кроки:
    1. визначаємо надлишкові та недостатні рядки (рядок є недостатнім (від’ємним), якщо запаси відповідного пункту відправлення розподілені повністю, а потреби пунктів призначення не задоволені; рядок є надлишковим (додатним), якщо потреби задоволені і при цьому залишився товар у відповідному пункті відправлення);
    2. для кожного стовпчика знаходимо різницю між тарифами у колі та найближчим до нього тарифом, який записаний в надлишковому рядку. Якщо тариф у колі знаходиться в позитивному (надлишковому) рядк, то  різницю не визначаємо; серед різниць знаходимо найменшу – проміжну ренту;
    3. переходимо до нової таблиці – додаємо до відповідних тарифів, які знаходяться у від’ємних (недостатніх) рядках, проміжну ренту. Інші елементи не змінюємо.

Читати далі

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

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

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

Читати далі

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

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

  1. На довільному кроці методу, для кожного рядка та стовпця обчислюється різниця (“штраф”) між значеннями найменшої вартості та вартості, наступної за величиною. Якщо ж виявиться, що в рядку чи стовпці містятся дві комірки з однаковими мінімальними значеннями тарифів, то беремо саме їх. В такому випадку різниця буде дорівнює нулю.
  2. Обчислені штрафи записуються у додаткові рядки та стовпі транспортоної таблиці.
  3. Виокремлюємо рядок чи стовпець з найбільшим “штрафом” (якщо їх є декілька, то обираємо довільний з них).
  4. У виокремленому на попередньому кроці рядку чи стовпці, обираємо комірку з найменшою вартістю.
  5. Для обраної комірки встановлюємо величину перевезунь, аналогічно методу мінімального елемента, після чого, повторюємо всі вищеописані дії знову, тільки вже не враховуючи заповнені клітини.

Читати далі