Лабораторна робота 12 на тему Транспортна задача, Оптимізаційні методи та моделі, НУХТ

« Назад

Лабораторна робота 12 на тему Транспортна задача

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблиця 12.1

N° вар.	Витрати на перевезення одиниці вантажу
	А₁					А₂					А₃					А₄					А₅
	В₁	В₂	В₃	В₄	В₅	В₁	В₂	В₃	В₄	В₅	В₁	В₂	В₃	В₄	В₅	В₁	В₂	В₃	В₄	В₅	В₁	В₂	В₃	В₄	В₅
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° вар.	Запаси постачальників					Потреби споживачів
N° вар.	А₁	А₂	А₃	А₄	А₅	В₁	В₂	В₃	В₄	В₅
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

З повагою ІЦ "KURSOVIKS"!