Висновок

Отже визначені опорні плани за двома методами. Мінімальна вартість перевезень за опорним планом метода МВ, 390<450.

Питання для контролю та самоперевірки 3

3.1 Перевірка задачі на закритість.

3.2 Алгоритм методу ПЗК.

3.3 Алгоритм методу МВ.

3.4 Обчислення загальної вартості перевезень.

ЛАБОРАТОРНА РОБОТА № 4

ПОШУК ОПТИМАЛЬНОГО ПЛАНУ ТРАНСПОРТНОЇ ЗАДАЧІ

Постановка задачі

Знайти оптимальний план транспортної задачі, який забезпечить мінімальну загальну вартість перевезень. Використати опорний план з табл. 3.2 (метод ПЗК), який наведений на стор. 11.

Розв’язок

Перевірка опорного плану на оптимальність виконується методом потенціалів. Якщо план Х^*=х^*_ij Т − задачі є оптимальним то йому відповідає система з m+n чисел u^*_i i v^*_j, які задовольняють умовам (4.1 − 4.3):

v^*_j − u^*_i = С_ij, якщо х_ij>0, (4.1)

v^*_j − u^*_i ≤ С_ij, якщо х_ij=0, (4.2)

(i=1, 2, … , m; j=1, 2, … , n). (4.3)

Числа u^*_i i v^*_j називаються потенціалами, відповідно постачальників і споживачів. Для перевірки плану на оптимальність потрібно скласти систему з рівнянь (3.14) для кожної заповненої комірки, розв’язати її, а потім обчислити значення S_ij= v^*_j − u^*_i − С_ij для кожної незаповненої комірки. Якщо S_ij≤0, план є оптимальним, а якщо “ні” потрібно будувати новий план.

Записується опорний план (4.4) і для нього складається система (4.5) з рівнянь виду (4.1) для заповнених комірок:

, (4.4)

(4.5)

Розв’язок (3.5): u₂= 0; v₂= 4; v₃= 6; u₁= 1; v₁= 3; u₃= 1; v₄= 7.

Потім обчислюються значення S_ij для кожної незаповненої комірки (4.4), які представлені в 4.6.

Умова S_ij≤0 для (4.6) не виконується. Щоб побудувати новий план потрібно визначити максимальне додатне значення S_ij і в комірку (2, 4) записати невідомий обсяг перевезень х₂₄=ρ. Потім формується замкнений цикл (він завжди єдиний) по заповненим комірках і записується -ρ в (3, 4), ρ в (3, 3) і -ρ в (2, 3), щоб не порушився баланс за рядками і стовпцями (табл. 4.1).

(4.6)

Таблиця 4.1 − Побудова замкненого циклу

2/ 10	3/ 10
	4/ 10	6/ 30 (-ρ)	(ρ)
		5/ 0 (ρ)	6/ 30 (-ρ)

За ρ вибирається мінімальний із обсягів в комірках з –ρ, тобто 30. Це значення додається до обсягів поставок в комірках, де ρ і віднімається де -ρ. При цьому в одній комірці обсяг перевезень стає нульовим, якщо таких комірок кілька в інші записується +0, щоб кількість заповнених комірок не змінилася. Новий план Х₂ записується в 4.7.

, (4.7)

Загальна вартість перевезень цукру за новим планом:

Х₂= 2∙10+3∙10+4∙10+5∙30+5∙30+6∙0 =390.

Побудований план (4.7) знову перевіряється на оптимальність, для нього складається система з 6-ти рівнянь (4.8) для заповнених комірок:

(4.8)

Розв’язок (3.21): u₂= 0; v₂= 4; v₄= 5; u₁= 1; v₁= 3; u₃= -1; v₃= 4.

Потім обчислюються значення S_ij для кожної незаповненої комірки (4.7), які представлені в 4.9:

(4.9)

Висновок

Всі значення S_ij≤0 в (4.9), тобто цей план оптимальний. Мінімальна загальна вартість перевезень для заданих умов Х_min=X₂=390. Це значення співпадає з загальною вартістю перевезень, яка визначена за опорним планом методу МВ (стор. 12), тобто він є оптимальним планом.

Питання для контролю та самоперевірки 4

4.1 Визначення потенціалів постачальників і споживачів.

4.2 Побудова і розв’язок системи рівнянь задачі.

4.3 Побудова замкненого циклу.

4.4 Перевірка на оптимальність побудованого плану.

ЛАБОРАТОРНА РОБОТА № 5

МЕТОДИКА БАГАТОКРИТЕРІАЛЬНОЇ ОПТИМІЗАЦІЇ

Постановка задачі

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

Розв’язок

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

Таблиця 5.1 − Дані про транспортні маршрути

№ маршруту	1	2	3	4	5	6	7	8
Час, хв.	30	40	45	50	55	60	70	80
Вартість, коп.	200	150	120	90	80	60	50	30

Потім визначаються вагові коефіцієнти (80-30) і (200-30) та будується узагальнена адитивна функція цінності:

. (5.1)

На наступному етапі обчислюються цінності кожного з транспортних маршрутів і визначається допустимий план х¹, який відповідає мінімуму (5.1). Результати розрахунків наведені в табл. 5.2.

Таблиця 5.2 − Цінності транспортних маршрутів

№ маршруту	1	2	3	4	5	6	7	8
Час / 50	0,6	0,8	0,9	1,0	1,1	1,2	1,4	1,6
Вартість / 170	1,18	0,88	0,71	0,53	0,47	0,35	0,29	0,18
Цінність (u)	1,78	1,68	1,61	1,53	1,57	1,55	1,69	1,78

Найкращий показник функції цінності має четвертий маршрут: х¹=4, y¹=f(x¹) = [50 хв.; 90 коп.]. Отримані результати надсилаються ОПР (особа, що приймає рішення).

ОПР не погоджується обрати план х¹ за розв’язок задачі та вводить по кожній цільовій функції припустимі рівні, які вона вважає задовільними: ,Але маршрут з такими параметрами відсутній, тому потрібно визначити реальність припустимих рівнів, що введені на попередньому етапі.

Задані первісні припустимі рівні є нереальними, за (5.2) обчислюються реальні рівні, що відповідають первісним: ,

(5.2)

Потім виконується пошук ефективного плану х², що задовольняє реальним рівням критерійних показників: х²=6, його оцінка y²=f(x²)=[60 хв.; 60 коп.] передається на затвердження ОПР.