Скласти план вантажних перевезень з мінімальним вантажообігом.

Розв'язання.В наведеній задачі потреба всіх господарств у мінеральних добривах (150 + 100 + 150 + 200 =600 т) дорівнює сумарній наявності добрив на складах (2003 =600 т). Тому транспортна задачазакрита.Опорний план задачі побудуємо за методом “найкращого” елементу в матриці (транспортна таблиця 4.1).

Транспортна таблиця 4.1

Склади	Господарства								Наявність добрив, т	Потенціали рядків, uі
	S1		S2		S3		S4
D1	150	5	50	6		7		8	200	0
	-						+
D2		8	50	9	150	10		11	200	3
D3	0	7		14		15	200	20	200	2
	+						-
Потреба в добривах, т	150		100		150		200		600
Потенціали колонок, vj	5		6		7		18

У матриці найменша відстань – це відстань від складу D₁ до господарства S_1, яка дорівнює 5 км. Емність складу D₁ дорівнює 200 т, а потреба в добривах господарства S₁ – 150 т, тому в клітину (D_1,S₁) ставимо число 150. При цьому клітини (D_2,S₁) та (D_3,S₁) будуть незаповненими. Але на складі D₁ ще залишаються добрива в кількості 200-150 = 50 т. Ці добрива доцільно перевезти до господарства S₂ (відстань 6 км), тому в клітину (D_1,S₂) ставимо число 50. При цьому клітини (D_1,S₃) та (D_1,S₄) будуть незаповненими. Переходимо до розподілу мінеральних добрив зі складу D₂. Найближча відстань від складу D₂ до господарства S₁

8 км, але потреба в добривах для господарства S₁ уже задоволена. Тому добрива перевозимо до господарства S₂ (9 км) в кількості 100 – 50 = 50 т, а до S₃ (10 км) – 200 - 50 = 150 т. В клітинах (D_2,S₂) і (D_2,S₃) ставимо відповідно числа 50 і 150. При цьому клітини (D_2,S₄), (D_3,S₂) та (D_3,S₃) будуть незаповненими.

Зі складу D₃ мінеральні добрива можна перевезти тільки до господарства S₄, тому що три перших господарства свої потреби вже задовольнили. Ставимо в клітину (D_3,S₄) число 200.Обсяг вантажоперевезень транспортній таблиці 4.1 дорівнює Z₁=1505+506+509+15010+07+20020 = 7000 ткм.

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

m+n–1=3+ 4 – 1 = 6. В транспортній таблиці 4.1 кількість заповнених клітин дорівнює 5, тому в клітину (D_3,S₁) вводимо "нуль-поставку" так, щоб заповнені клітини разом з "нуль-поставкою" не складали циклу.

Для визначення потенціалів складемо систему рівнянь для заповнених клітин транспортної таблиці 4.1: u₁+v₁ = 5; u₁+v₂ = 6; u₂+v₂ = 9; u₂+v₃ = 10; u₃+v₁= 7; u₃+v₄= 20. Поклавши, наприклад, u₁=0, одержимо значення потенціалів, які запишемо в транспортну таблицю 4.1: v₁=5-u₁=5-0=5; v₂=6-u₁=6-0=6;

u₂=9-v₂=9-6=3; v₃=10-u₂=10-3=7; u₃=7-v₁=7-5=2; v₄=20-u₃=20-2=18.

Перевіримо виконання умови оптимальності для незаповнених клітин

(u_i+ v_j c_ij): клітина (D₁,S₃) – умова виконується (0+7 =7); клітина (D₁,S₄) – умова не виконується на 10 одиниць (0+18>8); клітина (D₂,S₁) – умова виконується (3+5 =8); клітина (D₂,S₃) – умова виконується (2+6 <14); клітина (D₂,S₄ )– умова не виконується на 10 одиниць (3+18 >11); клітина (D₃,S₃) - умова виконується (2+7 <15). Таким чином, розв'язок в транспортній таблиці 4.1 не оптимальний, тому що умова оптимальності не виконується для клітин (D₁,S₄) та (D₂,S₄). В зв'язку з тим, що для клітини (D₁,S₄) та (D₂,S₄) різниця між сумою потенціалів і оцінкою клітини однакова, вибираємо ту, де оцінка клітини найменша (D₁,S₄). В транспортній таблиці 4.1 цикл побудуємо до клітини (D₁,S₄). Отримуємо додатній "півцикл" з вершинами (D₁,S₄) та (D₃,S₁) і від'ємний "півцикл" з вершинами (D₁,S₁) та (D₃,S₄). У від'ємному "півциклі" знаходимо вершину з найменшим числом. Це клітина (D₁,S₁) з числом 150. Тепер це число додаємо в клітинах циклу перерахунків із знаком "+" і віднімаємо в клітинах із знаком "-". В результаті отримуємо новий базисний розв'язок транспортної задачі (транспортна таблиця 4.2).

Транспортна таблиця 4.2

Склади	Господарства								Наявність добрив, т	Потенціали рядків, uі
	S1		S2		S3		S4
D1		5	50	6		7	150	8	200	0
			-				+
D2		8	50 +	9	150 -	10		11	200	3
D3	150	7		14		15	50	20	200	12
Потреба в добривах, т	150		100		150		200		600
Потенціали колонок, vj	-5		6		7		8

Обсяг вантажоперевезень в транспортній таблиці 4.2 складає

Z₂ =.506+1508+509+15010+1507+5020=5450 ткм.

Розв'язок в транспортній таблиці 4.2 знову перевіряємо на оптимальність. Для цього складемо систему рівнянь для заповнених клітин (u_i+v_j=c_ij): u₁+v₂ = 6; u₁+v₄ = 8; u₂+v₂ = 9; u₂+v₃ = 10; u₃+v₁= 7; u₃+v₄ = 20. Поклавши u₁=0, одержимо потенціали, які запишемо в транспортну таблицю 4.2 : v₂=6-u₁=6-0=6; v₄=8-u₁=8-0=8; u₂=9-v₂=9-6=3; v₃=10-u₂=10-3=7; u₃=20-v₄=20-8=12; v₁=7-u₃=7-12=5. Перевіримо виконання умови оптимальності для незаповнених клітин (u_i+v_jc_ij): клітина (D₁,S₁) – умова виконується (0+(-5)< 5); клітина (D₁,S₃) - умова виконується (0+7=7); клітина (D₂,S₁) - умова виконується (3+(-5)<8); клітина (D₂,S₄) – умова виконується (3+8 =11); клітина (D₃,S₂) – умова не виконується на 4 одиниці (12+6 >14); клітина (D₃,S₃) - умова не виконується на 4 одиниці (12+7 >15).

В транспортній таблиці 4.2 розв'язок не оптимальний, тому що для клітин (D₃,S₂) та (D₃,S₃) умова оптимальності не виконується. До клітини (D₃,S₃) в транспортній таблиці 4.2 побудуємо цикл. У від'ємному "півциклі" знаходимо найменше число (50) і додаємо його у заповнених клітинах із знаком "+" та віднімаємо у клітинах із знаком "-". В результаті отримуємо новий розв'язок транспортної задачі, який запишемо в транспортній таблиці 4.3. Обсяг вантажоперевезень транспортній таблиці 4.3 дорівнює

Z₃=2008+1009+10010+1507+5015=5300 ткм.

Перевіримо опорний план в транспортній таблиці 4.3 на оптимальність. В транспортній таблиці 4.3 не виконується умова m+n -1, тому в клітину (D₁,S₂) вводимо "нуль-поставку". Поклавши u₁ = 0, одержимо значення потенціалів:

v₁= -1, v₂ = 6, v₃ = 7, v₄ = 8, u₂ =3, u₃=8.

Транспортна таблиця 4.3

Склади	Господарства								Наявність добрив, т	uі
	S1		S2		S3		S4
D1		5	0	6		7	200	8	200	0
D2		8	100	9	100	10		11	200	3
D3	150	7		14	50	15		20	200	8
Потреба в добривах, ц	150		100		150		200		600
vj	-1		6		7		8

Перевіримо виконання умови оптимальності для незаповнених клітин (u_i+v_jc_ij): клітина (D₁,S₁) - 0+(-1)<5-умова виконується; клітина (D₁,S₃)- 0+7=7- умова виконується; клітина (D₂,S₁) - 3+(-1)<8-умова виконується; клітина (D₂,S₄) - 3+8 =11-умова виконується; клітина (D₃,S₂) - 8+6= 14-умова виконується; клітина (D₃,S₄) 8+8 <20-умова виконується. Таким чином, розв'язок задачі в транспортній таблиці 4.3 є оптимальним.

Висновки. Мінеральні добрива потрібно перевозити:

- зі складу D₁ до господарства S₄–200 т;

- зі складу D₂ до господарства S₂ –100 т і до господарства S₃ –100 т;

- зі складу D₃ до господарства S₁ –150 т і до господарства S₃ –50 т.

Обсяг вантажоперевезень буде дорівнювати 5300 ткм, що на 1700 ткм менше, ніж у початковому плані ( Z₁-Z₃=7000 - 5300 = 1700).

Задачі для самостійного розв'язання

Задача 4.1. Потрібно скласти такий план перевезення худоби із п'яти господарств (таблиця 4.1) на три м'ясокомбінати (таблиця 4.2), щоб сумарні втрати живої ваги при перевезенні худоби були мінімальними. При цьому втрати живої ваги на 1 т її при перевезенні худоби відомі (таблиця 4.3).

Таблиця 4.1

Виробництво м'яса в господарствах, т

Варіант (за передостанньою цифрою шифру Р)	Господарства
	S1	S2	S3	S4	S5
0	10	15	10	20	15
1	15	15	20	10	10
2	10	10	15	15	20
3	20	10	15	10	10
4	15	20	10	10	10
5	8	12	15	15	20
6	12	25	13	10	10
7	15	15	10	18	12
8	10	15	15	15	15
9	15	15	15	20	10

Таблиця 4.2

Потужність м'ясокомбінатів, т

Варіант (за останньою цифрою шифру К)	М'ясокомбінати
	D1	D2	D3
0	30	30	20
1	25	25	30
2	20	20	40
3	40	20	20
4	30	25	25
5	35	25	20
6	20	25	35
7	15	40	30
8	25	35	25
9	35	30	15

Таблиця 4.3