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

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

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

Читати далі

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

Всі методи рішення транспортної задачі спираються на виконання таких етапів:

  1. Побудова початкового опорного плану (метод північно-західного кута, метод мінімального елемента, метод апроксимації Фогеля та інші).
  2. Визначення оптимальності отриманого плану.
  3. Поліпшення отриманого плану.

Очевидно, що етапи два і три повторюються до отримання оптимального рішення (плану).

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

Розглянемо алгоритм, який реалізує цей метод.

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

Читати далі

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

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

Читати далі

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

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

Читати далі

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

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

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

Читати далі