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

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

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

Читати далі

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

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

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

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

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

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

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

Читати далі

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

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

Читати далі

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

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

Читати далі

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

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

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

Читати далі

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

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

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

Читати далі

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

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

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

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

Читати далі

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

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

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

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

Читати далі