Практические работы / ПР №14 / пр14

Практическая работа №14

Транспортная задача (Т-задача)

Цель: закрепить теоретические знания и развить практические навыки ре-шения транспортных задач.

Ход работы

Задание: Найти опорное решение для Т-задачи.

1) Решение метода северо-западного угла:

2) Решение методом потенциалов.

Опорный план найдем методом двойных отметок:

Вычисление потенциалов:

a1 + b2 = 2; a2 + b4 = 5; a4 + b3 = 4;

a1 + b5 = 10; a3 + b4 = 6; a4 + b5 = 8;

a2 + b1 = 5; a3 + b5 = 26;

Потенциалы:

a1	0	b1	–10
a2	15	b2	2
a3	16	b3	9
a4	– 5	b4	–10
		b5	10

Всоответствии с алгоритмом метода потенциалов определим побочные стоимости (псевдостоимости) для свободных (незаполненных) клеток:

c'11 = a1 + b1 = 0 – 10 = –10;

c'13 = a1 + b3 = 0 + 9 = 9;

c'14 = a1 + b4 = 0 – 10 = –10;

c'22 = a2 + b2 = 15 + 2 = 17;

c'23 = a2 + b3 = 15 + 9 = 24;

c'25 = a2 + b5 = 15 + 10 = 25;

c'31 = a3 + b1 = 16 – 10 = 6;

c'32 = a3 + b2 = 16 + 2 = 18;

c'33 = a3 + b3 = 16 + 9 = 25;

c'41 = a4 + b1 = – 5 – 10 = – 15;

c'42 = a4 + b2 = – 5 + 2 = – 3;

c'44 = a4 + b4 = – 5 – 10 = –15.

и соответствующие величины s_ij :

s11 = 30 – (–10) = 40;

s13 = 5 – 9 = – 4;

s14 = 6 – (–10) = 16;

s22 = 29 – 17 = 12;

s23 = 9 – 24 = -15;

s25 = 7 – 25 = -18;

s31 = 16 – 6 = 10;

s32 = 24 – 18 = 6;

s33 = 14 – 25 = – 11;

s41 = 13 – (–15) = 28;

s42 = 28 – (– 3) = 31;

s44 = 25 – (–15) = 40;

Так как в клетках (1,3), (2,3), (2,5) и (3,3) (значения цены цикла s_ij < 0), найденный опорный план не оптимален. Улучшим его, введя в базис одну из свободных переменных, а именно (2,5), ибо для нее цена цикла наименьшая и равна –18.

Вычисление потенциалов:

a1 + b2 = 2; a2 + b5 = 7; a4 + b3 = 4;

a1 + b4 = 6; a3 + b4 = 6; a4 + b5 = 8.

a1 + b5 = 10; a3 + b5 = 26;

a2 + b1 = 5;

Потенциалы:

a1	0	b1	8
a2	– 3	b2	2
a3	0	b3	6
a4	– 2	b4	6
		b5	10

c'11 = a1 + b1 = 0 – 8 = –8;

c'13 = a1 + b3 = 0 + 5 = 5;

c'22 = a2 + b2 = –2 + 2 = 0;

c'23 = a2 + b3 = –3 + 6 = 3;

c'24 = a2 + b4 = –3 + 6 = 3;

c'31 = a3 + b1 = 0 + 8 = 8;

c'32 = a3 + b2 = 0 + 2 = 2;

c'33 = a3 + b3 = 0 + 6 = 6;

c'41 = a4+ b1 = – 2 – 8 = -10;

c'42 = a4+ b2 = – 2 + 2 = 0;

c'44 = a4+ b4 = – 2 + 6 = 4.

и соответствующие величины s_ij :

s11 = 30 – (–8) = 38;

s13 = 5 – 5 = 0;

s22 = 29 – 0 = 29;

s23 = 9 – 3 = 6;

s24 = 5 – 3 = 2;

s31 = 16 – 8 = 8;

s32 = 24 – 2 = 22;

s33 = 14 – 6 = 8;

s41 = 13 – (–10) = 23;

s42 = 28 – 0 = 28;

s44 = 25 – 4 = 21.

Так как псевдостоимости не превосходят стоимостей, следовательно полученный план оптимальный. Т-задача решена.