Задание 3

Выполнение этого задания требует знания алгоритма решения транспортной задачи.

Типовой пример:

У поставщиков А₁, А_2, А₃ имеется груз в количествах 300,150 и 250 единиц соответственно, который нужно перевезти пяти покупателям: 170 ед. потребителю В₁, 100 ед. – В₂, 110 ед. – В₃, 120 ед. – В₄, и 200 ед – В₅. Стоимость перевозки единицы товара от i-того поставщика j-тому покупателю задана в матрице:

С=

Требуется составить такой план перевозок, при котором затраты минимальны.

Решение:

Занесем данные задачи в таблицу 4 и составим первый опорный план методом наименьшего тарифа.

Таблица 4

Потребитель Поставщик	В1 β1=7		В2 β2=5		В3 β3=3		В4 β4=6		В5 β5=7		Запасы
А1 α1=0	170	7 –		5	110	3		8	20 +	7	300
А2 α2=2		8 +		10		4		6	150 -	9	150
А3 α3=-4		5	100	1		10	120	2	30	3	250
Потребности	170		100		110		120		200		700

Сумма поставок по строке должна равняться соответствующим запасам, а по столбцу – потребностям; число заполненных клеток – семи.

При составленном плане вычисляем затраты:

f=170·7 + 110·3 + 20·7 + 150·9 + 100·1 + 120·2 + 30·3=3440 ден. ед.

Проверяем план на оптимальность:

1. Для заполненных клеток: α_i +β_i = C_ij,

где

α_i – потенциал поставщиков;

β_i – потенциал покупателей;

C_ij – тариф.

полагая α1 = 0, получим: β1=7, α2=2, β2=5, α3=-4. β3=3, β4=6, β5=7,

2. Проверим для свободных клеток выполнение условия оптимальности решения: α_i +β_i C_ij, где C_ij – тариф. Это условие должно выполняться во всех пустых клетках.

α₁+β₂=0+5=5=5, (+)

α₁+β₄=0+6=6<8, (+)

α₂+β₁=2+7=9>8, (не выполняется)

α₂+β₂=2+5=7<10, (+)

α₂+β₃=2+3=5>4, (не выполняется)

α₂+β₄=2+6=8>6, (не выполняется)

α₃+β₁=-4+7=3<5, (+)

α₃+β₃=-4+3=-1<10, (+)

Условие оптимальности не выполняется для клеток (2,1), (2,3), (2,4), значит стоимость перевозок может быть уменьшена.

Составим цикл пересчета для клетки (2,1). Он проходит через клетки (1,1), (1,5), (2,1), (2,5) таблицы 1.

Перемещая по циклу поставку ρ = min (170, 150) = 150, переходим к новому плану (табл. 5):

Таблица 5

Потребитель Поставщик	В1 β1=7		В2 β2=5		В3 β3=3		В4 β4=6		В5 β5=7		Запасы
А1 α1=0	20	7 +		5	110	3		8	170 –	7	300
А2 α2=1	150	8 –		10		4	+	6		9	150
А3 α3=- 4		5	100	1		10	– 120	2	+ 30	3	250
Потребности	170		100		110		120		200		700

Затраты на перевозку при полученном плане:

f₂ = 20·7 + 110·3 + 170·7 + 150·8 + 100·1 + 120·2 + 30·3=3290 ден.ед.

Проверяем план на оптимальность:

1. Для заполненных клеток:

   α1=0, α2=1, α3=-4,

   β1=7, β2=5, β3=3, β4=6, β5=7.

2. Для свободных клеток:

α₁+β₂=0+5=5, (+)

α₁+β₄=0+6<8, (+)

α₂+β₂=1+5<10, (+)

α₂+β₃=1+3=4, (+)

α₂+β₄=1+6>6, (не выполняется)

α₃+β₁=-4+7<5, (+)

α₃+β₃=-4+3<10, (+)

Условие оптимальности не выполняется в клетке (2,4), следовательно, составленный план не является оптимальным.

Перейдем к третьему плану, составив цикл пересчета для клетки (2,4) Он проходит через клетки (2,1), (1,1), (1,5), (3,5), (3,4) таблицы 5.

Будем перемещать по циклу поставку ρ = min (150, 170, 120) =120. Новый план перевозок представлен в таблице 6:

Таблица 6

Потребитель Поставщик	В1 β1=7		В2 β2=5		В3 β3=3		В4 β4=5		В5 β5=7		Запасы
А1 α1=0	140	7		5	110	3		8	50	7	300
А2 α2=1	30	8		10		4	120	6		9	150
А3 α3= – 4		5	100	1		10		2	150	3	250
Потребности	170		100		110		120		200		700

Стоимость перевозок:

f₃ = 140·7 + 110·3 + 50·7 + 30·8 + 120·6 + 100·1 + 150·3=3170 (ден.ед).

Проверка на оптимальность:

1) Для заполненных клеток:

α1=0, α2=1, α3=-4,

β1=7, β2=5, β3=3, β4=5, β5=7.

2) Для свободных клеток:

α₁+β₂=0+5=5, (+)

α₁+β₄=0+5<8, (+)

α₂+β₂=1+5<10, (+)

α₂+β₃=1+3<4, (+)

α₂+β₅=1+7<9, (+)

α₃+β₃=-4+3<10, (+)

α₃+β₄=-4+5<2, (+)

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