Лабораторна робота № 12. «Транспортна задача»

На практиці при перевезенні вантажів може виникнути одна з трьох ситуацій.

І.

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

Введемо позначення:

х_ij – змінні, які підлягають розшуку та виражають кількість вантажу, який перевозиться від і-го постачальника до j-го споживача (і=1...m, j=1...n);

с_ij – вартість перевезення одиниці вантажу від i-го постачальника до j-го споживача;

а_i – кількість одиниць вантажу у і-го постачальника;

b_j – кількість одиниць вантажу, яка потрібна j-му споживачу.

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

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

. (12.1)

Така економіко-математична модель транспортної задачі називається закритою та з урахуванням умови (8.1) вона має вид:

; (12.2)

(12.3)

. (12.4)

Дана транспортна задача є збалансованою.

У наведених виразах формула (12.2) відповідає цільовій функції з мінімізації транспортних витрат. Формули (12.3) є обмеженнями задачі:

перша формула характеризує те, що весь вантаж від постачальників має бути вивезеним;

друга формула відтворює той факт, що попит споживачів задоволений.

Формула (12.4) є умовою невід'ємності змінних.

ІІ.

Кількість вантажу у постачальників більше попиту у ньому з боку споживачів:

(12.5)

Це означатиме, що частина вантажу у постачальників залишиться, а споживачі отримають весь потрібний їм вантаж. Тому знак у першому обмеженню (12.3) зміниться з "=" на "≥". Інші формули розглянутої моделі (12.2)–(12.4) залишаться такими ж.

ІІІ.

Кількість вантажу у постачальників менше попиту в ньому у споживачів:

(12.6)

Це означатиме, що кожен постачальник увесь свій вантаж вивезе, а частина споживачів отримає вантажу менше відповідної кількості. Тому друге обмеження у формулах (12.3) буде мати знак "≤". Інші формули моделі (12.2)–(12.4) залишаться без зміни.

Економіко-математичні моделі у ситуаціях II і III називаються відкритими, а самі задачі – незбалансованими.

У всіх трьох розглянутих моделях кількість основних змінних складає m´n, а кількість обмежень – (m+n).

Найбільш простою та часто використовуємою є закрита модель (12.2)–(12.4). З особливостями реалізації відкритих моделей можна познайомитися у спеціальній літературі.

1. Постановка транспортної задачі

Визначити, чи є дана транспортна задача збалансованою або незбалансованою.

Знайти оптимальний розв'язок транспортної задачі, якщо задані витрати на перевезення одиниці вантажу від постачальників А₁, А₂, А₃, А₄, А₅ до споживачів В₁,В₂, В₃, В₄, В₅.

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

Таблиця 12.1

N° вар.	Витрати на перевезення одиниці вантажу
	А1					А2					А3					А4					А5
	В1	В2	В3	В4	В5	В1	В2	В3	В4	В5	В1	В2	В3	В4	В5	В1	В2	В3	В4	В5	В1	В2	В3	В4	В5
1.	1	2	3	4	4	3	5	6	4	3	6	2	1	2	3	4	4	3	5	6	4	3	6	2	4
2.	5	2	3	4	4	3	5	7	4	3	6	2	5	2	3	4	4	3	5	7	4	3	6	2	4
3.	5	2	3	4	4	3	4	5	4	7	5	4	5	2	3	4	4	3	4	5	4	7	5	4	4
4.	2	9	6	7	3	5	4	2	3	5	4	9	2	9	6	7	3	5	4	2	3	5	4	9	3
5.	7	6	5	6	2	4	3	1	5	3	6	8	7	6	5	6	2	4	3	1	5	3	6	8	2
6.	5	1	4	6	9	3	2	6	8	7	9	5	5	1	4	6	9	3	2	6	8	7	9	5	9
7.	3	5	2	4	6	1	8	9	7	5	3	2	3	5	2	4	6	1	8	9	7	5	3	2	6
8.	6	9	4	3	1	5	6	8	5	7	1	4	6	9	4	3	1	5	6	8	5	7	1	4	1
9.	5	1	4	6	9	3	2	6	8	7	9	5	5	1	4	6	9	3	2	6	8	7	9	5	9
10.	8	3	9	4	7	2	1	5	6	4	8	2	8	3	9	4	7	2	1	5	6	4	8	2	7
11.	1	2	3	4	4	3	5	6	4	3	6	2	1	2	3	4	4	3	5	6	4	3	6	2	4
10.	2	9	6	7	3	5	4	2	3	5	4	9	2	9	6	7	3	5	4	2	3	5	4	9	3
13.	7	6	5	6	2	4	3	1	5	3	6	8	7	6	5	6	2	4	3	1	5	3	6	8	2
14.	6	9	4	3	1	5	6	8	5	7	1	4	6	9	4	3	1	5	6	8	5	7	1	4	1
15.	4	2	3	5	4	3	5	7	4	3	6	2	4	2	3	5	4	3	5	7	4	3	6	2	4
16.	5	8	6	9	1	2	4	7	3	5	8	5	5	8	6	9	1	2	4	7	3	5	8	5	1
17.	4	6	9	4	5	7	6	8	4	9	3	2	4	6	9	4	5	7	6	8	4	9	3	2	5
18.	2	5	3	6	8	5	9	6	4	5	2	1	2	5	3	6	8	5	9	6	4	5	2	1	8
19.	7	5	3	1	5	9	8	6	2	4	5	7	7	5	3	1	5	9	8	6	2	4	5	7	5
20.	2	5	8	4	6	5	7	5	3	1	5	9	2	5	8	4	6	5	7	5	3	1	5	9	6
21.	8	2	4	6	5	3	1	5	7	5	9	5	8	2	4	6	5	3	1	5	7	5	9	5	5
22.	2	4	2	3	6	8	8	4	4	2	2	6	2	4	2	3	6	8	8	4	4	2	2	6	6
23.	5	2	3	4	4	3	5	7	4	3	6	2	5	2	3	4	4	3	5	7	4	3	6	2	4
24.	5	2	3	4	4	3	4	5	4	7	5	4	5	2	3	4	4	3	4	5	4	7	5	4	4
25.	2	9	6	7	3	5	4	2	3	5	4	9	2	9	6	7	3	5	4	2	3	5	4	9	3
26.	7	6	5	6	2	4	3	1	5	3	6	8	7	6	5	6	2	4	3	1	5	3	6	8	2
27.	9	5	6	4	7	5	1	5	2	3	4	6	9	5	6	4	7	5	1	5	2	3	4	6	7
28.	7	4	6	8	4	2	6	7	5	3	1	5	7	4	6	8	4	2	6	7	5	3	1	5	4
29.	8	5	4	6	8	5	2	1	3	5	6	7	8	5	4	6	8	5	2	1	3	5	6	7	8
30.	3	5	2	4	6	1	8	9	7	5	3	2	3	5	2	4	6	1	8	9	7	5	3	2	6

Продовження таблиці 12.1

N° вар.	Запаси постачальників					Потреби споживачів
	А1	А2	А3	А4	А5	В1	В2	В3	В4	В5
1.	15	15	45	60	45	60	20	30	45	10
2.	25	25	40	65	40	65	10	35	40	15
3.	35	35	20	35	20	35	25	30	55	20
4.	30	30	10	25	10	25	45	15	60	10
5.	25	25	55	40	55	40	30	25	15	35
6.	10	10	25	45	25	45	65	40	10	20
7.	50	50	85	20	85	20	75	15	25	70
8.	20	20	60	45	60	45	80	25	30	45
9.	25	25	40	65	40	65	10	35	40	15
10.	55	55	20	40	20	40	15	75	35	20
11.	25	25	55	40	55	40	30	25	15	35
10.	50	50	85	20	85	20	75	15	25	70
13.	10	10	25	45	25	45	65	40	10	20
14.	30	30	10	25	10	25	45	15	60	10
15.	25	25	40	65	40	65	10	35	40	15
16.	65	65	15	20	15	20	35	40	75	10
17.	20	20	85	45	85	45	15	35	65	55
18.	50	50	40	35	40	35	10	75	45	40
19.	35	35	40	15	40	15	20	35	30	10
20.	25	25	50	70	50	70	85	30	40	65
21.	55	55	45	25	45	25	65	15	25	40
22.	25	25	30	10	30	10	75	10	50	20
23.	25	25	40	65	40	65	10	35	40	15
24.	35	35	20	35	20	35	25	30	55	20
25.	30	30	10	25	10	25	45	15	60	10
26.	25	25	55	40	55	40	30	25	15	35
27.	85	85	65	50	65	50	80	25	10	45
28.	60	60	75	20	75	20	10	30	30	25
29.	40	40	80	25	80	25	15	40	25	65
30.	20	20	10	55	10	55	30	35	65	20