Зм 3.Транспортна задача

Теоретична частина. В класичній постановці транспортна задача формулюється так: нехай на m визначених пунктах (постачальники) зосереджено однорідний вантаж у кількостях a_i (i = 1,m ), який потрібно перевезти до n інших пунктів (споживачі) у кількостях b_j (j = 1,n ). Відомо, що відстань перевезення вантажу із i-го до j-го пункту дорівнює с_ij (i = 1,m; j = 1,n ). Обсяг перевезеного вантажу із i-го до j-го пункту позначимо через х_ij.

Скласти оптимальний план перевезення всього вантажу від постачальників до споживачів з умовою повного забезпечення потреби споживачів при мінімумі вантажоперевезень.

В загальному вигляді задачі транспортного типу розв"язуються як на мінімум, так і на максимум цільової функції. Математичний запис задачі транспортного типу такий: знайти вектор невідомих х = (х₁, х₂, ..., х_j, ..., х_n), при якому цільова функція Z досягає екстремуму

_{n m}

Z_ext = ∑ ∑ c_ij x_ij

^{j=1 i =1}

при обмеженнях:

_n

1) ∑ x_ij = b_i j  (1,n); i  (1,m)

^j=1

_m

2) ∑ x_{i j} = а_j

^{i =1}

3) x_ij >= 0

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

1-й етап - знаходження початкового розв’язку задачі - застосовуються декілька методів:

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

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

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

в) “найкращого” елементу матриці (транспортної таблиці) – в транспортній таблиці (матриці) знаходиться клітина з найменшою (при розв"язанні задачі на мінімум цільової функції) або з найбільшою (при розв"язанні задачі на максимум цільової функції) оцінкою с_ij клітини, в яку ставиться максимально можливий обсяг вантажу, потім наступна за нею клітина і так далі, поки не буде розподілено весь вантаж. Недоліки і переваги цього методу такі ж, як і в методі подвійної переваги.

Допустимий опорний план транспортної задачі, отриманий за будь-яким із наведених вище методів, повинен задовольняти таким умовам:

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

2) при розрахунках повинен забезпечуватися баланс вантажів по кожному рядку і по кожному стовпчику транспортної таблиці;

3) заповнені клітини (базисні невідомі) транспортної таблиці не повинні утворювати циклів (замкнутих контурів);

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

2-й етап-знаходження оптимального розв’язку транспортної задачі - умовою оптимальності розв'язку транспортної задачі є:

1) u_i+v_j = c_ij – для базисних невідомих (заповнені клітини);

2) u_i+v_j c_ij – для небазисних невідомих (незаповнені клітини) при розв'язанні

задачі на мінімум цільової функції;

3) u_i+v_j  c_ij – для небазисних невідомих (незаповнені клітини) при розв'язанні

задачі на максимум цільової функції,

де u_i - потенціали рядків,

v_j – потенціали колонок.

Розрахунок потенціалів проводять за такою схемою: поклавши u₁=0, значення решти потенціалів отримуємо згідно умови u_i+v_j = c_ij. Оптимальність розв'язку задачі на мінімум цільової функції перевіряємо для кожної незаповненої клітини за умовою u_i+v_j c_ij, а при розв'язку задачі на максимум цільової функції за умовою u_i+v_j  c_ij. Якщо розв’язок не оптимальний, то виконуються такі розрахунки:

1. Серед „неоптимальних” клітин вибирається та, у якої різниця між сумою потенціалів і оцінкою клітини найбільша (початкова клітина циклу перерахунків). Якщо ці різниці однакові для деяких клітин, то серед них вибирається клітина з меншою оцінкою при розв'язку задачі на мінімум цільової функції, або з більшою оцінкою при розв'язку задачі на максимум цільової функції.

2. До вибраної клітини будується цикл перерахунків, в якому всі клітини крім вибраної повинні бути заповненими (базисними). При цьому будь-якому рядку або будь-якому стовпчику транспортної таблиці можуть належати тільки дві вершини циклу перерахунку. Перехід від однієї клітини до іншої може бути тільки в заповненій клітині під кутом 90^о. Цикл повинен замикатися на першій (вибраній) незаповненій клітині (тобто там, де він починався).

Ц икли можуть бути різної конфігурації, наприклад:

3. У вибрану „неоптимальну” клітину циклу ставимо знак "+", а далі у вершинах циклу знаки по черзі "-", "+", "-" так, щоб у будь-якому рядку або у будь-якій колонці були тільки протилежні знаки, тобто "+" і "-". Отримуємо додатній "півцикл" з вершинами "+" і від'ємний "півцикл" з вершинами "-". У від'ємному "півциклі" знаходимо вершину з найменшим числом (вантажем), яке додаємо в клітинах циклу із знаком "+" і віднімаємо в клітинах із знаком "-". В результаті отримуємо новий базисний розв'язок транспортної задачі.

Розрахунки повторюються на кожній ітерації до отримання оптимального розв'язку.

Завдання 3. Розв”язання транспортних задач методом потенціалів

Мета завдання. Вивчити алгоритм розв'язання транспортних задач методом потенціалів.

Приклад 3. Потрібно перевезти мінеральні добрива з трьох складів (постачальники) ємністю по 200 т кожний до чотирьох господарств (споживачі), потреба яких в мінеральних добривах становить відповідно 150, 100, 150 та 200 т.

Відстані від складів до господарств наведені в таблиці, км

Склади	Господарства
	S1	S2	S3	S4
D1	5	6	7	8
D2	8	9	10	11
D3	7	14	15	20