им методом. Однак матриця системи обмежень транспортної задачі настільки своєрідна, що для її рішення розроблені спеціальні методи. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім, поліпшуючи його, отримати оптимальне рішення.
У загальній постановці транспортної завдання передбачається, що з будь-якого пункту виробництва будь-який пункт споживання може бути перевезено будь-яку кількість вантажу.
У цілому ряді випадків оптимізації планування перевезень доводиться враховувати обмежені можливості транспортних шляхів і засобів. Тому математичну модель транспортної задачі:
(1.7)
i = 1,2, ..., m, (1.8)
j = 1,2, ..., n, (1.9)
(1.10)
повинні бути введені додаткові обмежувальні умови, що враховують можливість транспортних шляхів і засобів.
Якщо позначитися транспортні можливості між пунктами I і j через dij, то кількість вантажу, що може бути перевезено в цьому напрямі за планований період часу, не повинно перевищувати транспортних можливостей, тобто
(1.11)
Тоді обмеження 1.10, 1.11 об'єднуються, і модель задачі ускладнюється двосторонніми обмеженнями на змінні
(1.12)
При цьому загальна транспортна можливість доріг, що з'єднують I-й пункт виробництва з усіма n пунктами споживання, повинна бути рівна або більше кількості продукції, призначеної до постановки з цього i-го пункту всім n споживача, тобто
i = 1,2, ..., m, (1.13)
Загальна ж транспортна можливість доріг, що з'єднують j-й пункт споживання з усіма m пунктами виробництва, повинна бути рівна або більше кількості продукції, які треба поставити в цей j-й пункт від всіх m постачальників, тобто
i = 1,2, ..., n, (1.14)
Існують різні підходи до вирішення цього завдання. Розглянемо найбільш простий з них. p> Шляхів деяких перетворень умов її можна звести до типу звичайної транспортної задачі. Для цього пункт виробництва чи споживання, для яких умови обмежені транспортні можливості, розбивається на два умовних пункту. При цьому слід підкреслити неодмінно один пункт.
Потужність умовного постачальника А ' i - приймається рівний встановленої можливості засобів, що з'єднують пункт і з споживачами j
A ' i = d ij ( 1.15)
а потужність умовного постачальника А ' j - рівною різниці між заданими в умові завдання потужністю постачальника в пункті I і можливістю коштів між I-м і j-м пунктами, тобто
a'' i = a i -d ij . (1.16)
При цьому витрати на поставку вантажів з пунктів I 'в пункт jc ij приймаються рівними дійсним витратам c ij наведеним в умові завдання. В оптимальному рішення змінні х ij можуть мати будь-яке невід'ємне значення від нуля до a ' i , тобто
(1.17)
На відміну від них змінні х ij в оптимальному рішенні неодмінно повинні бути рівні нулю, оскільки потужність А ' j характеризує кількість у пункті і понад встановленої засобів, що з'єднують пункти i та j, отже це частина вантажу повинна бути спрямована не j-му а будь-якому іншому споживачу. Для того, щоб у оптимальному рішенні забезпечити значення змінних х ij дорівнює нулю, витрати на постачання вантажу з пункту i'' в пункт j приймаються рівними М, т. е c ij = М.
При мінімізації цільової функції (1.7) і коефіцієнтах c ij = М, в оптимальному рішенні отримаємо
В
Звідси випливає, що
X ij = X i ' j + X i ' j = X ij ( 1.18)
Тоді, виходячи з умов (1.15), (1.17), отримаємо
В
Таким чином, обсяг поставки вантажу з пункту i в пункт j НЕ перевищить встановленої здатності транспортних засобів, що забезпечують ці пункти.
Якщо для якої то пари пунктів виробництва i споживання s транспортні можливості не обмежені, обсяг поставки вантажу від постачальника Аi до споживача B s визначиться як сума значень пари відповідних змінних:
В
Подальший розрахунок буде виконаний за допомогою угорського методу вирішенні транспортного алгоритму.
1.6 Рішення транспортної задачі з обмеженими можливостями транспортних коштів угорським методом
Попередній етап. За вихідній матриці З виконується побудова матриці С ', а потім матриці Co, за відомими правилам.
Виконується побудова початкового плану Xo. Побудова плану виконується, зверху-вниз по стовпцях матриці Co починаючи з лівого, для O матриці Co, при цьому враховується...
