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

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

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

Читати повністю

Рішення транспортної задачі методом Фогеля в середовищі програмування delphi

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

Головне вікно розглядуваного delphi-проекту ділиться на три частини: панелі інструментів (складається з двох компонентів типу TSpinEdit та двох кнопок типу TButton), робочої області (містить транспортну таблицю) та статусного рядка, основним призначенням якого є вивід загальної вартості перевезень згідно побудованого опорного плану. Розглянемо призначення кожного з цих елементів більш детально:

  1. Поля вибору "Пункти призначення" та "Пункти відправлення" відповідають за кількість пунктів які беруть участь в перевезенні, а також розмірність транспортної таблиці.
  2. Кнопки "Знайти опорний план методом Фогеля" та "Очистити" відповідають за побудову початкового плану транспортної задачі та підготовку програми до нового прикладу відповідно.
  3. Нарисована на канві форми транспортна таблиця у комірки якої, способом введення з клавіатури, записуються тарифи на перевезення одиниці продукції, загальні потреби у товарі кожного з пунктів призначення і загальна кількість запасів кожного з пунктів відправлення.

Читати повністю

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

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

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

Читати повністю

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

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

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

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

Читати повністю

Програмна реалізація методу потенціалів на Delphi

Метод потенціалів дає змогу, починаючи з деякого опорного плану (визначається методом північно-західного кута або методом мінімального елемента), знайти розв'язок транспортної задачі. Загальна схема даного методу наступна: у заданому початковому опорному плані перевезень кожному з пунктів відправлення і призначення ставлять у відповідність деяке число, яке називається його потенціалом. Щоб визначити дані потенціали для кожної зайнятої клітинки таблиці розв'язують рівняння metod_potencialiv_delphi1. Щоб знайти значення потенціалів з цієї системи рівнянь, потрібно присвоїти одному з них довільне значення і потім послідовно обчислювати значення інших потенціалів.

Далі для усіх вільних клітинок знаходимо metod_potencialiv_delphi2. Якщо всі ці числа є додатними, то опорний план є оптимальним і розв'язок завершується. В іншому випадку, переходимо до іншого опорного плану і знову перевіряємо його на оптимальність.

Читати повністю

Метод північно-західного кута на Delphi

Програма реалізує знаходження опорного плану транспортної задачі за методом північно-західного кута. Отже, запустимо дану програму, і спробуємо розв'язати конкретну задачу.

metod_pivnicho-zahidnoho_kyta_delphi11

В якості прикладу розглядається задача розв'язок якої міститься за посиланням методом північно-західного кута, а саме: на три бази pnz3 поступив товар в кількості 140; 180; 160. Цей груз треба перевезти в п'ять пунктив призначення pnz4 в кількостях 60; 70; 120; 130; 100. Тарифи перевезення записані в наступній таблиці:

Читати повністю

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

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

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

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

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

тоді даний опорний план є оптимальним. Метод потенціалів — називаються потенціалами пунктів відправлення та пунктів призначення.

Читати повністю

« Попередня сторінкаНаступна сторінка »