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

2.1. Загальна постановка транспортної задачі

Метод потенціалів найчастіше використовується для розв’язку задач, пов'язаних із плануванням перевезень вантажів на залізничному, автомобільному й інших видах транспорту.

Такі задачі одержали загальну назву - транспортні.

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

Класична транспортна задача лінійного програмування - це задача про найбільш економічний план перевезень однакових або взаємозамінних вантажів з пунктів виробництва в пункти споживання. Іншими словами - це задача про оптимальне прикріплення споживачів до постачальників. Але її можна застосовувати і для розробки породового плану передачі порожніх вагонів і інших задач.

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

План перевезень можна зобразити у виді таблиці (матриці), рядки якої відповідають станціям відправлення, стовпці - станціям призначення (табл. 5).

Ліворуч від таблиці проставлено номери відправників (постачальників) 1, 2,…i…m; зверху - номери споживачів 1, 2,…j…n;праворуч-ресурси кожного відправника a₁, a₂,…a_m;унизу - потреба кожного споживача b₁, b₂,…b_n...

Таблиця 5

Кожен елемент матриці на перетині рядка і стовпця означає можливе перевезення від визначеного постачальника визначеному споживачеві. У верхньому лівому куті кожної клітки указується вартість перевезення одиниці вантажу C_ij, . Витрати на одне перевезення від постачальника i до споживача j визначаються як добутки C_ijx_ij, а витрати на всі перевезення

(2.1)

де x_ij – величина перевезення (кількість одиниць або обсяг вантажу) від постачальника i споживачеві j. Аргументи x_ij цієї лінійної функції пов'язані між собою у такий спосіб.

Сума всіх перевезень, розташованих у першому рядку матриці (див. табл. 5 ), повинна дорівнювати розмірам відправлення першого постачальника, тобто

x₁₁ +x₁₂+…+x_1j+…x_1n=a₁...

Аналогічні рівності для всіх інших рядків. Вони становлять систему лінійних рівнянь

(i=1, 2,…m)...

Сума перевезень, відбитих першим стовпцем, повинна відповідати потребам першого споживача

x₁₁ +x₂₁+…+x_i1+…x_m1=b₁...

Для всіх стовпців - це система лінійних рівнянь

(j=1, 2,…n)...

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

X_ij (i=1, 2,…m;j=1,2,…n)...

Таким чином, транспортна задача лінійного програмування в загальному виді формується так: необхідно привести до мінімуму (або максимуму) лінійну функцію (2.1)

з ненегативними аргументами, зв'язаними системою лінійних обмежень:

(2.2)

(i=1, 2,…m)...

(j=1,2,…n).

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

і відкриту модель, коли ця умова не дотримується.

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

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

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

Обмеження (2.2) транспортної задачі - система m+n лінійних рівнянь: m - по рядках і n -за стовпцями матриці. Однак у такому виді її не розв’язують, тому що рівняння залежать одне від одного:

у сумі m рівнянь дають - n рівнянь - . Але оскільки то будь-яке рівняння можна виразити як комбінацію інших.

Таким чином, система складається з m+n-1 лінійно незалежних рівнянь і одного вивідного.

Для розв'язку системи істотні лише лінійно незалежні рівняння. Вивідне рівняння можна виключити. Залишається система m+n-1 лінійно незалежних рівнянь з mn невідомими. Стосовно системи (2.2) вона базисна.

При її розв’язку як базисної необхідно вибрати m+n-1 невідомих. Цими невідомими і будуть перевезення в базисному плані транспортної задачі.