Пример решения транспортной задачи

Задача. Поставщик товара – оптовые коммерческие предприятия А₁, А₂, А₃, А₄ имеют запасы товаров а₁=280, а ₂=350, а ₃=415, а ₄=255 единиц и розничные торговые предприятия В₁, В₂, В₃ – подали заявки на закупку товара в объемах b₁=620, b₂=490, b₃=150 единиц.

Тарифы перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребления заданы матрицей перевозок:

4 17 7

C= 14 20 8

18 5 4

3 2 11

Найти такой план перевозки груза от поставщиков к потребителю, чтобы совокупные затраты на перевозку были минимальными.

Решение.

1) Проверим необходимое и достаточное условие разрешимости задачи:

280 + 350 + 415 + 255 = 1300

630+490+150 = 1260

> , следовательно, модель исходной

транспортной задачи является открытой.

Чтобы получить закрытую модель, введем фиктивного потребите­ля В4 с заявкой на Ь₄=40 единиц товара. Тарифы перевозки для В4 по­лагаем равными нулю. Занесем данные в таблицу 16.

Табл. 16

bj a i

2) Используя метод «северо-западного угла» построим первый опорный план.

Табл. 17

bj   a i
	2804	-17	-7	-0
	34014	1020	-8	-0
	-18	4155	-4	-0
	2553	652	15011	400

Число занятых клеток - 7, а должно быть т+п-1=4+4-1=7. Следо­вательно, опорный план является невырожденным. Значение целевой функции плана ₁:

F ()= 280∙4+340∙14+10∙20 + 415∙5+65∙2+150∙ 11 + 40∙ 0 = 9935

3) Проверим оптимальность плана ₁ для этого дополним таб­лицу 17 столбцом и строкой потенциалами.

Табл. 18

bj   a i					ui
	2804	-17	-7	-0	u1=0
	34014	1020	-8	-0	u2=10
	-18	4155	-4	-0	u3= - 5
	2553	652	15011	400	u4= - 8
v j	v 1=0	v 2=10	v 3=19	v 4=8

Найдем потенциалы по занятым клеткам u_j + u_i = c_ij и занесем в таблицу 18.

u₁+ v ₁=4 ] u₁=0

u₂+ v ₁=14 v ₁=4

u₂+ v ₂=20 u₂=10

u₃+ v ₂=5 v ₂=10

u₄+ v ₂=2 u₃=-5

u₄+ v ₃=11 u₄=-8

u₄+ v ₄=0 v ₃=19

v₄ =8

Оценим пустые клетки _ij=c_ij – (u_i + v _j).

₁₂=17 – (0+10) = 7

₁₃=7 – (0+19) = - 12

₁₄=0 – (0+8) = - 8

₂₃= 8 – (10+9) = - 21

₂₄=0 - (10+8)= - 18

₃₁=18– (-5 – 4) =19

₃₃=4 – (-5 +19) = -10

₃₄=0- (-5+8) = -3

₄₄=3 – (-8 +4) =7

Первый опорный план не является оптимальным, т.к. среди этих оце­нок есть отрицательные, поэтому переходим к улучшению плана ₁ .

4) «Худшую» оценку ₂₃= - 21 имеет клетка (2,3). Построим для нее цикл перераспределения груза.

10 0 0 10

+

65 150 75 140

+

В результате получим новый опорный план ₂ :

Табл. 19

bj   a i					ui
	2804	-17	-7	-0	u1=0
	34014	-20	108	-0	u2=10
	-18	4155	-4	-0	u3= 16
	-3	752	14011	400	u4= 13
v j	v 1=4	v 2=-11	v 3=-2	v 4=-13

F () = 280∙4 + 340∙14 + 10∙8 + 415∙5 + 75∙2 + 140∙ll + 40∙0 = 9725

5) Проверим план ₂ на оптимальность.

Оценим занятые клетки, дополним таблицу 19.

u₁+ v ₁=4 ] u₁=0

u₂+ v ₁=14 v ₁=4

u₂+ v ₃=8 u₂=10

u₃+ v ₂=5 v ₃=

u₄+ v ₂=2 u₄=13

u₄+ v ₃=11 v ₂= - 11

u₄+ v ₄=0 u₃=16

v₄ = - 13

Оценим пустые клетки.

₁₂=17 – (0 - 11) = 28

₁₃=7 – (0- 2) = 9

₁₄=0 – (0- 13) = 13

₂₂= 20 – (10- 11) = 21

₂₄=0 - (10 - 13)= 3

₃₁=18– (16 + 4) = - 2

₃₃=4 – (16 - 2) = -10

₃₄=0- (16 - 13) = -3

₄₄=3 – (13 +4) = - 14

Второй опорный план ₂ так же не является оптимальным, продолжаем его улучшать.

6) Перезагрузим «худшую» клетку (4,1).

340 10 200 150

+

0 140 140 0

+ −

В результате получим новый опорный план _2:

Табл. 20

bj   a i					ui
	2804	-17	-7	-0	u1=0
	20014	-20	1508	-0	u2=10
	-18	4155	-4	-0	u3= 3
	1403	752	-11	400	u4= - 1
v j	v 1=4	v 2=3	v 3=-2	v 4=1

F ( ₃) =280∙4 + 200∙14 + 150∙8 + 415∙5 + 140∙3 + 75∙2 + 40∙0 = 7765

7) Проверим план ₃ на оптимальность.

Оценим занятые клетки, дополним таблицу 20.

u₁+ v ₁=4 ] u₁=0

u₂+ v ₁=14 v ₁=4

u₂+ v ₃=8 u₂=10

u₃+ v ₂=5 v ₃=

u₄+ v ₁=3 u₄= - 1

u₄+ v ₂=2 v ₂= 3

u₄+ v ₄=0 u₃=3

v₄ = 1

Оценим пустые клетки.

₁₂=17 – (0 +3) = 14

₁₃=7 – (0- 2) = 9

₁₄=0 – (0+1) = - 1

₂₂= 20 – (10+3) = 7

₂₄=0 - (10 +1) = - 11

₃₁=18– (3+ 4) = 11

₃₃=4 – (3 - 2) = 3

₃₄=0- (3 +1) = - 4

₄₄=3 – (- 1 - 2) = 6

План ₃ не является оптимальным.

8) Перезагрузим клетку (2,4).

200 0 160 40

+

140 40 180 0

+ −

Получим новый план ₄.

Табл. 21

bj   a i					ui
	2804	-17	-7	-0	u1=0
	16014	-20	1508	400	u2=10
	-18	4155	-4	-0	u3= 2
	1803	752	-11	-0	u4= - 1
v j	v 1=4	v 2=3	v 3=-2	v 4=-10

F ( ₄) = 280∙4+160∙14 + 150∙8 + 40∙0+415∙5 + 180∙3 + 75∙2 = 7325

9) Проверим план ₄ на оптимальность.

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

u₁+ v ₁=4 ] u₁=0

u₂+ v ₁=14 v ₁=4

u₂+ v ₃=8 u₂=10

u₂+ v ₄=0 v ₃= -2

u₃+ v ₂=5 v ₄= -10

u₄+ v ₁=3 u₄= -1

u₄+ v ₂=2 v ₂=3

u ₃ = 2

Для пустых клеток:

₁₂=17 – (0 +3) = 14

₁₃=7 – (0- 2) = 9

₁₄=0 – (0 - 10) = 10

₂₂= 20 – (10+3) = 7

₃₁=18– (2+ 4) = 12

₃₃=4 – (2 - 2) = 4

₃₄=0- (2 - 10) = 8

₄₃=11- (- 1 - 2) = 14

₄₄=0– (- 1 - 10) =11

Поскольку все оценки не отрицательны, то план оптимален.

280 0 0

160 0 150

_опт.= 0 415 0

180 75 0

F _опт.( ₄) = 7325 тысяч рублей.

Анализ плана. Первому поставщику A₁ следует весь товар отпра­вить первому заказчику B₁, второй поставщик А₂ должен отправить 160 ед. товара первому заказчику B₁ и 150 ед. товара - третьему заказ­чику В₃, третий поставщик А ₃ отправит весь товар заказчику В₂, а четвертый поставщик А₄ отправит 180 ед. товара заказчику B₁ и 75 ед. товара - заказчику В₂. При этом плане 40 ед. товара второго постав­щика А₂ остается нереализованным. Общая стоимость доставки това­ра заказчикам будет минимальной и составляет 7325 тысяч рублей.

Так как среди последних оценок - все строго положительные, то данный оптимальный план является единственным.

Замечание. Алгоритм и методы решения транспортной задачи мо­гут быть использованы при решении многих экономических задач, не имеющих отношение к транспортировке грузов.

Date: 2015-12-12; view: 492; Нарушение авторских прав