Математичні моделі тз.

Для запису математичної моделі ТЗ введемо такі позначення:

x_ij - об’єм перевезень вантажу від і-го постачальника до j-го споживача;

Z - сумарна вартість перевезень вантажів.

Матрицю Х = (x_ij), i = , j = називають матрицею планування.

Сумарна вартість перевезень вантажів складає

Z = с_ij  x_ij  min (9.1)

Обмеження ТЗ сформулюємо, виходячи з таких міркувань:

а) всі запаси вантажів постачальників повинні бути вивезені

x_i1 + x_i2 +....+ x_in= x_ij= a_i, i= (9.2)

б) всі потреби споживачів повинні бути задоволені

x_1j + x_2j +....+ x_mj = x_ij= b_j , j= (9.3)

Для отримання розв’язку ТЗ необхiдно знайти такий невiд’ємний розв’язок x_ij  0, i= , j= системи (n+m) лiнiйних рiвнянь, який мінімізує цільову функцію (9.1) і задовольняє систему обмежень (9.2), (9.3).

Етапи розвязання транспортної задачі методом потенціалів.

Введемо деякі означення.

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

План називається опорним, якщо немає замкнутого циклу, всi вершини якого лежать в зайнятих клiтинах.

Опорний план називається невиродженим, якщо кількість заповнених клітинок таблиці 9.1 дорівнює m+n-1 (m - кількість постачальників, а n - кількість споживачів). В іншому випадку опорний план називається виродженим.

Процес розв’язання ТЗ методом потенціалів складається з таких етапів:

1. Перевіряють, чи дана ТЗ є закритою. Для цього знаходять суму запасів вантажу постачальників і суму потреб споживачів. Якщо ці суми рівні, то ТЗ закрита і можна будувати опорний план перевезень, якщо ні - то вводять фіктивного споживача (пункт 9.1.2, випадок 1), або фіктивного постачальника (пункт 9.1.2, випадок 2), і в результаті отримують закриту ТЗ.

2. Будують опорний план перевезень та перевіряють його на виродженість. Якщо план вироджений, то шляхом введення нульового вантажу в одну з порожніх клітинок табл. 8.1, зводять його до невиродженого.

3. Шляхом побудови системи потенціалів, її розв’язаннням та використанням критерію оптимальності, перевіряють опорний план на оптимальнiсть та, при необхідності, покращують його шляхом побудови циклу перевезень та перерозподілу вантажів в циклі.

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

В залежності від співвідношення запасів вантажів у постачальників та потреб споживачів розрізняють закриту та відкриту моделі ТЗ. Розглянемо їх.

Закрита модель тз

ТЗ, для якої сума запасів постачальників ( a_i) дорівнює сумі потреб споживачів ( b_j), тобто для якої виконується умова

a_i = b_j .

називається закритою транспортною задачею (ЗТЗ).

Економічна інтерпретація постановки ЗТЗ. Необхідно знайти такий план перевезень вантажу, щоб мiнiмізувати транспортні затрати на його перевезення при забезпеченні всіх потреб споживачів та повному вивезені запасів вантажів від постачальників.