37. Транспортні задачі

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

 

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

Найпростіша класична постановка транспортної задачі за критерієм вартості полягає у наступному.

 

Нехай є m пунктів доставки (або пунктів виробництва) А₁, А₂,...,А_m, в яких розміщено однорідний вантаж в обсязі а₁, а₂, ..., а_m одиниць. Цей вантаж повинен бути доставлений у деяку систему з n пунктів В₁, В₂,..., В_n з обсягом попиту відповідно b₁, b₂, ..., b_n. Передбачається, що можливе транспортування з кожного пункту постачання в кожний пункт споживання. Відомі транспортні витрати С_ij , пов’язані з доставкою одиниці вантажу з пунктів А_i в пункти В_j (i=1,m; j =1,n).

 

Задача полягає у складанні такого плану перевезень, який забезпечує виконання наступних умов:

 

·        запаси кожного постачальника повинні бути повністю вивезені;

 

·         попит всіх пунктів споживання повинен бути задовільнений за рахунок розподілу всього запасу вантажів

 

 

·         забезпечити мінімальні транспортні витрати.

 

Умови транспортної задачі подають у формі таблиці, яка має вигляд

 

Постачальники Аі	Споживачі Вj							Наявність вантажу
	В1	В2	...	Вj	...	Вn
А1	С11	С12	...	С1j	...	С1n	а1
А2	С21	С22	...	С2j	...	С2n	а2
...	...	...	...	...	...	.....	...
Аi	Сi1	Сi2	...	Сij	...	Cin	ai
....	...	...	...	...	...	...	...
Am	Cm1	Cm2	...	Cmj	...	Cmn	am
Потреба у вантажах	b1	b2	...	bj	...	bn

 

Позначимо через x_ij кількість вантажу, який перевозиться з пункту постачання А_i в пункт споживання В_j та будемо розглядати змінні x_ij, які задають план перевезень як компоненти матриці перевезень Х розміром m х n .

 

 

38. Методи розвязування транспортних задач

Специфічними для транспортної задачі є такі дві обставини:

1. кожна із змінних входить в два рівняння системи (1)-(2),

2. всі коефіцієнти при змінних приймають лише два значення 0 або 1.

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

Метод потенціалів — це метод послідовного покращення плану (перевезень) з використанням другої теореми двоїстості для перевірки оптимальності.

Угорський метод — це метод послідовної побудови допустимого плану, який автоматично виявляється оптимальним. В основі угорського алгоритму лежить метод чергування ланцюгів.

Початковий опорний план

Для початку розв'язування слід визначити початковий опорний план, тобто значення , що задовольняють умови (1)-(3), при чому лише щонайбільше n + m + 1 з них є ненульовими і не обов'язково досягається мінімум лінійної функції Найпоширенішими методами пошуку початкових опорних планів є метод північно-західного кута, метод найменшої вартості і метод Фогеля.

Метод північно-західного кута

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

Крок 1. Змінній присвоюється максимальне значення, що допускається обмеженнями на попит і пропозицію.

Крок 2. Викреслюється рядок (або стовпець) з повністю реалізованою пропозицією (з задоволеним попитом). Це означає, що в викресленою рядку (стовпці) ми не будемо присвоювати значення іншим змінним (крім змінної, визначеної на першому етапі). Якщо одночасно задовольняються попит і пропозиція, викреслюється лише рядок або тільки стовпець.

Крок 3. Якщо не викреслено тільки один рядок або тільки один стовпець, процес зупиняється. В іншому випадку переходимо до клітини праворуч, якщо викреслять стовпець, або до клітини знизу, якщо викреслена рядок. Потім повертаємось до першого етапу.

Наприклад для попереднього прикладу початковий опорний план буде рівним:

					Кількість
	5	10			15
		5	15	5	25
				10	10
Кількість	5	15	15	15

В даній таблиці на перетині рядка і подано значення в початковому опорному плані (пустим клітинам відповідає значення нуль).

Метод найменшої вартості

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

Наприклад для попереднього прикладу початковий опорний план буде рівним:

					Кількість
		15			15
		0	15	10	25
	5			5	10
Кількість	5	15	15	15

Метод Фогеля

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

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

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

Крок З.

а) Якщо не викреслено тільки один рядок або тільки один стовпець з нульовим попитом або пропозицією, обчислення завершуються.

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

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

г) У всіх інших випадках необхідно перейти до кроку 1.

метод потенціалів

У методі потенціалів кожному рядку i і кожному стовпцю j транспортної таблиці ставляться у відповідність числа (потенціали) і . Для кожної базисної змінної потенціали і задовольняють рівнянню:

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

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

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

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

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

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