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

Маємо постачальників іспоживачів. Початкові дані наведені в таблиці постачань (табл. 1.5).

Таблиця 1.5

Запаси постачальників	Потреби споживачів
			...		...
			...		...
			...		...
...	...	...	...	...	...	...
			...		...
...	...	...	...	...	...	...
			...		...

У таблиці позначено:

–запас товару у i-го постачальника; – потреби у товаріj-го споживача; – витрати на транспортування одиниці товарувід i-го постачальника j-му споживачу. Ці показники вважаються постійними, тобто .

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

Для побудови математичної моделі даної задачі позначимо через обсяг товару, який необхідно перевезти відi-го постачальника j-му споживачу . Оскільки обсяг товару не може бути від’ємним, маємо обмеження: .

План перевезень задається матрицею , а загальні витрати – функцією

Можливі три ситуації.

1. Попит дорівнює пропозиції: .

Математичний опис задачі складається з функції мети

та обмежень:

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

Така транспортна задача вважається замкненою, всі інші – відкритими.

2. Попит менший за пропозицію: .

Математичний опис задачі складається з функції мети

та обмежень:

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

3. Попит більший за пропозицію: .

Математичний опис задачі складається з функції мети

та обмежень:

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

Побудувати математичну модель задачі.

Задача 1.3. Вихідні дані транспортної задачі подані у вигляді таблиці постачань (табл. 1.6).

Таблиця 1.6

	bj	45	35	55	65
ai
40		4	1	2	5
60		3	2	3	7
90		4	4	5	2

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

Рішення

Побудуємо математичну модель транспортної задачі.

Позначимо – обсяг товару, який необхідно перевезти відi-го постачальника j-му споживачу , тоді план перевезень задається матрицею .

Сумарний обсяг товару, який є у постачальників, дорівнює

.

Сумарний обсяг товару, потрібного споживачам, дорівнює

.

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

Отже, математична модель транспортної задачі така: