Транспортного типа.

На трех складах оптовой базы имеется груз в количествах соответственно 40, 80, 80 единиц. Этот груз необходимо перевезти в четыре магазина, каждый из которых заявил соответственно на 70, 20, 60 и 60 единиц. Стоимость доставки единицы груза (тарифы) из каждого склада А_i во все магазины В_j представляется матрицей:

5 4 2 1

C = 4 3 2 3 i

4 3 3 6

1 опорный план j

9 10 22 8 7 100

12 6 15 12 8 35

10 11 8 5 9 100

7 9 6 4 5 130

80 40 80 90 90

Составить оптимальный план перевозок грузов с минимальными транспортными затратами.

Решение:

1) Проверяем условия разрешимости задачи

₃

å a_{i =} 40+80+80=200

_I=1

₄

å b_j =70+20+60+60=210

_j=1

Суммарная потребность в грузе превышает его запасы на 210-200=10 единиц. Для получения закрытой модели введем дополнительный (фиктивный) склад А₄ с запасом груза равным a₄₌10 единиц с нулевым тарифом перевозок.

1. Формирование первого опорного плана (10П) методом минимальной стоимости.

10П (1 опорный план)

Vi Uj		V1 -16	V2-15	V3-O5	V4-12	Запасы аi
	Ai Bj	B1	B2	B3	B4
U1	A1		0			40
U2 -24	A2		-3		3
U3 -53	A3		3		- 6
U4 13	A4		0			(10)
Потребности BJ

Расклад груза по клеткам:

1) C_min=C₁₄=1 сюда весь груз а₁=40

Остальные клетки А_i обнуляем.

2) Следующая C_min =C_2/3=20 Сюда полностью потребность b₃=60 Оставшиеся 80-60=20 запишем требующиеся b₂=20

3)Окончательно формируем столбец В_4, т.е. в клетку 44 вносим дефицит А₄=10 и в клетку 34 недостающие А₃=10.

4)Остался столбец В₁ с клеткой А₃, в которую записываем требующиеся в В₁=70

Для оценки рентабельности полученного опорного плана перевозок. 10П применим метод “потенциалов” занятых клеток: разность “потенциалов” должна быть меньше расценки, т.е. V - U C или в свободных V -U -C 0.Так как при балансе – всё “закольцовано“, поэтому всё равно откуда начать проверки и заполнения всех потенциалов. Принято начинать с” северо-восточного узла “, задавший исходной любой цифрой, например, нулём.

1) U =0. Остальные находим из условия баланса V -U =C .

2) В строке U заполнения столбец V , поэтому V =C +U =1+0=1

3) Зная V можно определить в этом столбце U и U .

-U =C -V =6-1=5; U =-5

-U =C -V =0-1=-1; U =1

4) Чтобы перейти к следующей строке (U ) воспользуемся промежуточно-пустым известным столбцом (V ). C =3.

Т.о. -U =C -V =3-1=2; U =-2

5) Теперь, зная U , определим в этой строке V и V .

V =C +U =3-2=1

V =C +U =2-2=0

6) Зная U =-5(см.п3) определим для занятой клетки 31 (С =4) значение V =C +U =4-5=-1. Определяем резервы в незанятых клетках .

Баланс д.б. <0 и резерв там, где он >0 (!)

7) Для клетки 11.

V -U -C =-1-0-5= -6<0

8) Для клетки 12.

V -U -C =1-0-4=-3<0

9) Для клетки 13

V₃ - U₁ – C₁₃ =0-0–2=-2<0

10) Для клетки 21

V₁ – U₂ – C₂₁ =-1+2-4=-3<0

11) Для клетки 24

V₄ – U₂ – C₂₄ =1+2-3=0

12) Для клетки 32

V₂ – U₃ – C₃₂ =1+5-3=+3>0 (!!!)

13) Для клетки 33

V₃ – U₃ – C₃₃ =0+5-3=+2>0

14) Для клетки 41

V₁ – U₄ – C₄₁ =-1-1-0=-2<0

15) Для клетки 42

V₂– U₄ – C₄₂ =1-1-0=0

16) Для клетки 43

V₃ – U₄ – C₄₃ = 0-1-0=-1<0

Получаем резервы(>0) в клетках 32 и 33

(п.п.12 и 13).Однако больше в клетке 32

Формирование второго опорного плана (20П)

Осуществляем перемещением грузов по следующему правилу:

Строим исходный многоугольник, в одной из вершин которого стоит клетка 32.Против нее ставим +, что значит перенесение сюда груза. Затем по периметру многоугольника поочередно в углах ставим – и +, считая начало + с клетки 32.В соответствии со знаками перемещаем грузы, сохраняя балансы по строчкам и столбцам.

1ОП 2ОП

	20П (2опорный план)
Vj Ui		V126	V213	V304	V411	Запасы   ai
	Bj Ai	B1	B2	B3	B4
U1 01	A1
U2 -22	A2	4	3 10 -		3
U3 -25	A3	-4	3
U4 17	A4	0			-0
Потребности bj

Повторяем туже работу с 20П , что и с 10П (можно бы было работать только с изменными клетками 22, 24, 32 и 34, а так же с теми потенциалами, которые от них зависят через C_ij, но лучше – слошь, пусть с повторами, чтобы не пропустить):

Занятые клетки

1) Кл. 14 неизменно V₄=1

2) Кл. 24 - U₂ = C₂₄ – V₄ =3 – 1 = 2; U₂= -2

3) Кл. 22 V₂ = C₂₂ + U₂ = 3 – 2 = 1

4) Кл. 23 неизменно V₃ = 0

5)Кл.32 → -U₃=C₃₂-V₂=3-1=2; U₃=-2 (было -5)

6)Кл.31 → V₁=C₃₁+U₃=4-2=2; V₁=2 (было -1)

7)Кл.44 → неизменно U₄=1

Резервы свободных:

8)Кл.11 → V₁ -U₁-C₁₁ =2-0-5=-3<0

9)Кл.12 → V₂ -U₁-C₁₂ =1-0-4=-3<0

10)Кл.13 →V₃ -U₁-C₁₃ =0-0-2=-2<0

11)Кл.21 → V₁ –U₂-C₂₁ =2+2-4=0

12)Кл.33 → V₃ –U₃-C₃₃ =0+2-3=-1<0

13)Кл.34 → V₄ –U₃-C₃₄ =1+2-6=-3<0

14)Кл.41 → V₁ –U₄-C₄₁ =2-1-0= 1>0

15)Кл.42 → V₂ –U₄-C₄₂ =1-1-0=0

16)Кл.43 → V₃ –U₄-C₄₃ =0-1-0=-1<0

Т.о. исходный многоугольник с исходным углом в Кл.41 и знаком , а чередование знаков должно замкнуться, то углов д.б. четное количество.

3)Формирование третьего опорного плана (30П)

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

1) Кл.14 → неизменно V₄ =1

2) Кл.24 → -U₂=C₂₄ – V₄=-3-1=2; U₂=-2

3) Кл.23 →V₃ = C₂₃ +U₂- =2-2=0; V₃=0

			зоп (3опорный план)
U1 Vj		V1 15	V2 O5	V3 O3	V4 14	Запасы
	Ai Bj	В1	В2	В3	В4	ai
U1 O	А1		0		40
U2 -22	А2		-3		3
U3 -34	А3	-4	3
U4 17	А4	0 10			-0
Потребности
bj

4) Кл.33→ -U₃=C₃₃-V₃=3-0=3; U₃= -3

5) Кл.31→ V₁=C₃₁=U₃=4-3=1; V₁=1

6) Кл.32→ V₂=C₃₂+U₃=3-3=0; V₂=0

7) Кл.41→-U₄=C₄₁-V₁=0-1= -1; U₄=1

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

8) Кл.11→V₁-U₁-C₁₁=1-0-5= -4<0

9) Кл.12→V₂-U₁-C₁₂=0-0-4= -4<0

10) Кл.13→V₃-U₁-C₁₃=0-0-2= -2<0

11) Кл.21→V₁-U₂-C₂₁=1+2-4= -1<0

12) Кл.22→V₂-U₂-C₂₂=0+2-3= -1<0

13) Кл.33→V₃-U₃-C₃₃=0+3-3=0

14) Кл.34→V₄-U₃-C₃₄=1+3-6= -2<0

15) Кл.42→V₂-U₄-C₄₂=0-1-0= -1<0

16) Кл.43→V₃-U₄-C₄₃=0-1-0= -1<0

17) Кл.44→V₄-U₄-C₄₄=1-1-0=0

ЗОП является оптимальным, т.к. все оценки резервов £ 0

Анализ работы с опорными планами:

1ОП Y(x)=

2ОП Y(x)=

3ОП Y(x)=

Анализ полученного ЗОП.

Для минимизации транспортных расходов до Y_min=520 необходимо:

1)С I склада А₁ весь груз 40ед. направить в IV магазин B₄

2)Cо II склада А₂ 60 ед. отвезти в III магазин и 20 ед. отвезти в IV магазин В₄

3)С III склада А₃ 60 ед. отвезти в I магазин В₁ и 20 ед. отвезти во II магазин В₂

4)Весь груз будет развезен, но I магазин недополучит 10 ед. (дефицит).