Мітки: транспортна задача

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

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

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

Читати далі

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

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

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

Читати далі

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

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

Читати далі

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

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

Читати далі

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

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

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

Читати далі