Факторы социально-экономического развития и конкурентоспособности региона

 

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

Решение

Найдем начальное решение методом минимального элемента

Суммарные запасы продукции у поставщиков должны равняться суммарной

Запасы поставщиков 7 + 21 + 19 = 47 единиц продукции

Потребность потребителей: 16 + 8 + 6 + 8 + 9 =47 единиц продукции

Суммарные запасы продукции у поставщиков равны суммарной потребности потребителей.

1) Согласно условию задачи  составим таблицу. (тарифы маршрутов располагаются в нижнем правом углу ячейки)

В первую очередь, будем задействовать маршруты с наименьшей стоимостью доставки.

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1						7
A 2						21
A 3						19
Потребность	16	8	6	8	9

3 маршрута обладают наименьшим  тарифом - 2 ден. ед.   Из этих 3 маршрутов выберем произвольный

От поставщика A2 к потребителю B4 будем доставлять min = { 21 , 8 } = 8 единиц продукции

2)

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1						7
A 2						21   13
A 3						19
Потребность	16	8	6	8   0	9

2 маршрута обладают наименьшим  тарифом - 2 ден. ед.   Из этих 2 маршрутов выберем произвольный

От поставщика A3 к потребителю B1 будем доставлять min = { 19 , 16 } = 16 единиц продукции.

3)

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1						7
A 2						21   13
A 3						19   3
Потребность	16   0	8	6	8   0	9

Наименьший тариф равен 2 ден. ед.

От поставщика A3 к потребителю B5 будем доставлять min = { 3 , 9 } = 3 единиц продукции

4)

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1						7
A 2						21   13
A 3						19   0
Потребность	16   0	8	6	8   0	9   6

Наименьший тариф равен 3 ден. ед.

От поставщика A1 к потребителю B5 будем доставлять min = { 7 , 6 } = 6 единиц продукции

 

5)

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1						7   1
A 2						21   13
A 3						19   0
Потребность	16   0	8	6	8   0	9   0

Наименьший тариф равен 4 ден. ед.

От поставщика A2 к потребителю B2 будем доставлять min = { 13 , 8 } = 8 единиц продукции

6)

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1						7   1
A 2						21   5
A 3						19   0
Потребность	16   0	8   0	6	8   0	9   0

Наименьший тариф равен 5 ден. ед.

От поставщика A1 к потребителю B3 будем доставлять min = { 1 , 6 } = 1 единиц продукции

7)

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1						7   0
A 2						21   5
A 3						19   0
Потребность	16   0	8   0	6   5	8   0	9   0

От поставщика A2 к потребителю B3 будем доставлять 5 единиц продукции.

8)

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1						7   0
A 2						21   0
A 3						19   0
Потребность	16   0	8   0	6   0	8   0	9   0

Мы израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

Мы нашли начальное решение.

Стоимость доставки продукции, для начального решения, не сложно посчитать.

S = 1 * 5 + 6 * 3 + 8 * 4 + 5 * 6 + 8 * 2 + 16 * 2 + 3 * 2 =   139 ден. ед.

Каждому поставщику A i ставим в соответствие некоторое число - u i , называемое потенциалом поставщика.

Каждому потребителю B j ставим в соответствие некоторое число - v j , называемое потенциалом потребителя.

Найдем потенциалы поставщиков и покупателей. (поверьте, это очень просто)

Для задействованного маршрута, сумма потенциала поставщика и потребителя равна тарифу задействованного маршрута.

Примем u2 = 0

A2B2 :        v2 + u2 = 4        v2 = 4 - 0 = 4

A2B3 :        v3 + u2 = 6        v3 = 6 - 0 = 6

A2B4 :        v4 + u2 = 2        v4 = 2 - 0 = 2

A1B3 :        v3 + u1 = 5        u1 = 5 - 6 = -1

A1B5 :        v5 + u1 = 3        v5 = 3 - ( -1 ) = 4

A3B5 :        v5 + u3 = 2        u3 = 2 - 4 = -2

A3B1 :        v1 + u3 = 2        v1 = 2 - ( -2 ) = 4

Поставщик	Потребитель					U j
	B 1	B 2	B 3	B 4	B 5
A 1						u 1 = -1
A 2						u 2 = 0
A 3						u 3 = -2
V i	v 1 = 4	v 2 = 4	v 3 = 6	v 4 = 2	v 5 = 4

Найдем оценки незадействованных маршрутов (в таблице они располагаются в нижнем левом углу ячейки).

Оценка незадействованного маршрута = тариф маршрута - ( потенциал поставщика + потенциал потребителя ).

A1B1 :          11 = 3 - ( -1 + 4 ) = 0

A1B2 :          12 = 7 - ( -1 + 4 ) = 4

A1B4 :          14 = 8 - ( -1 + 2 ) = 7

A2B1 :          21 = 7 - ( 0 + 4 ) = 3

A2B5 :          25 = 6 - ( 0 + 4 ) = 2

A3B2 :          32 = 3 - ( -2 + 4 ) = 1

A3B3 :          33 = 4 - ( -2 + 6 ) = 0

A3B4 :          34 = 9 - ( -2 + 2 ) = 9

 

Поставщик	Потребитель					U j
	B 1	B 2	B 3	B 4	B 5
A 1						u 1 = -1
A 2						u 2 = 0
A 3						u 3 = -2
V i	v 1 = 4	v 2 = 4	v 3 = 6	v 4 = 2	v 5 = 4

 

Оценки всех незадействованных маршрутов неотрицательные. Следовательно, уменьшить общую стоимость доставки мы не сможем.

Ответ:

X опт =		0	0	1	0	6
		0	8	5	8	0
		16	0	0	0	3

 

S = 139 ден. ед.

 

Задача 15.

В регионе существует  5 поставщиков продукции А1, А2, А3, А4, А5 и 5 потребителей В1, В2, В3, В4, В5. Необходимо прикрепить поставщиков к потребителям таким образом, чтобы суммарное расстояние перевозок было минимальным. Расстояние перевозок от поставщиков до потребителей задано матрицей:

8	4	2	4	12
10	6	8	6	14
8	6	16	10	2
14	8	10	14	4
18	14	12	16	6