Стратегия управления доставкой груза на транспорте

 

Исходный план задачи, полученный с помощью правила северо-западного угла, приведен в таблице 1.3 в виде возможных значений X_ij. Легко проверить, что этот набор значений X_ij является планом, так как удовлетворяются ограничения по каждой строке и каждому столбцу. Суммарные затраты регулировки порожних вагонов для этого плана можно получить, умножая выделенные значения X_ij таблицы 1.3 на соответствующие значения L_ij из таблицы 1.2 и суммируя полученные произведения. При этом получим:

L=(100·310+50·250+80·335+30·210+170·310+10·230+90·140)= 144200 ваг-км.

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

Присвоим первому поставщику потенциал  U₁ = 100. От первого поставщика порожние вагоны направляют первому, второму и третьему потребителю. Следовательно, V₁ = 100 + 310 = 410, V₂ = 100 + 250 = 350, V₃ = 100 + + 335 = 650. Зная потенциалы третьего потребителя, найдем потенциал второго поставщика: U₂ = V₃ – L₂₃ = 435 – 210 = 225. Потенциал четвертого потребителя V₄ = 225 + 310 = 535. Потенциал третьего поставщика U₃ = V₄ –     – L₃₄ = 535 – 230 = 305. Потенциал пятого потребителя V₅ = 305 + 140 = 445.

Проверка плана на оптимальность. Когда построен план и определена соответствующая ему целевая функция, определим, является ли полученный план оптимальным. План считается оптимальным, если для всех свободных ячеек выполняется условие .

Осуществляем проверку:

U₁ + L₁₄ = 100 + 170 = 270 < 535 – условие не выполняется;

U₁ + L₁₅ = 100 + 80 = 180 < 445 – условие не выполняется;

U₂ + L₂₁ = 225 + 110 = 335 < 410 – условие не выполняется;

U₂ + L₂₂ = 225 + 570 = 795 ≥ 350 – условие выполняется;

U₂ + L₂₅ = 225 + 400 = 625 ≥ 445 – условие выполняется;

U₃ + L₃₁ = 305 + 150 = 455 ≥ 410 – условие выполняется;

U₃ + L₃₂ = 305 + 310 = 615 ≥ 350 – условие выполняется;

U₃ + L₃₃ = 305 + 250 = 555 ≥ 435 – условие выполняется.

Для улучшения плана (целевая  функция L = 144200 ваг-км) необходимо переместить перевозку в ячейку, где условие оптимальности нарушено больше всего, то есть разность потенциалов максимальная (ячейки с индексами 14 и 15). Будем использовать ячейку с индексом 15. Второй опорный план представим в таблице 1.4.

Таблица 1.4 – Второй опорный план

Пункты отправления	Пункты назначения
	Г (410)	В (350)	Е (170)	З (270)	И (180)	Избыток вагонов
А (100)	100	50			80	230
Б (-40)			110	90		200
Д (40)				90	10	100
Недостаток вагонов	100	50	110	180	90	530

 

L=(100·310+50·250+80·80+110·210+90·310+90·230+10·140)=123000 ваг-км.

Осуществляем проверку:

U₁ + L₁₃ = 100 + 335 = 435 ≥ 170 – условие выполняется;

U₁ + L₁₄ = 100 + 170 = 270 ≥ 270 – условие выполняется;

U₂ + L₂₁ = -40 + 110 = 70 < 410 – условие не выполняется;

U₂ + L₂₂ = -40 + 570 = 530 ≥ 350 – условие выполняется;

U₂ + L₂₅ = -40 + 400 = 360 ≥ 180 – условие выполняется;

U₃ + L₃₁ = 40 + 150 = 190 < 410 – условие не выполняется;

U₃ + L₃₂ = 40 + 310 = 350 ≥ 350 – условие выполняется;

U₃ + L₃₃ = 40 + 250 = 290 ≥ 170 – условие выполняется.

Для улучшения плана (целевая функция L = 123000 ваг-км) необходимо переместить перевозку в ячейку, где условие оптимальности нарушено больше всего, то есть разность потенциалов максимальная (ячейка с индексом 31). Будем использовать ячейку с индексом 31. Третий опорный план представим в таблице 1.5.

Таблица 1.5 – Третий опорный план

Пункты отправления	Пункты назначения
	Г (410)	В (350)	Е (390)	З (490)	И (180)	Избыток вагонов
А (100)	90	50			90	230
Б (180)			110	90		200
Д (260)	10			90		100
Недостаток вагонов	100	50	110	180	90	530

 

L=(90·310+50·250+90·80+110·210+90·310+10·150+90·230)=120800 ваг-км.

Осуществляем проверку:

U₁ + L₁₃ = 100 + 335 = 435 ≥ 390 – условие выполняется;

U₁ + L₁₄ = 100 + 170 = 270 < 490 – условие не выполняется;

U₂ + L₂₁ = 180 + 110 = 290 < 410 – условие не выполняется;

U₂ + L₂₂ = 180 + 570 = 750 ≥ 350 – условие выполняется;

U₂ + L₂₅ = 180 + 400 = 580 ≥ 180 – условие выполняется;

U₃ + L₃₂ = 260 + 310 = 570 ≥ 350 – условие выполняется;

U₃ + L₃₃ = 260 + 250 = 510 ≥ 390 – условие выполняется;

U₃ + L₃₅ = 260 + 140 = 400 ≥ 180 – условие выполняется.

Для улучшения плана (целевая  функция L = 120800 ваг-км) необходимо переместить перевозку в ячейку, где условие оптимальности нарушено больше всего, то есть разность потенциалов максимальная (ячейка с индексом 14). Будем использовать ячейку с индексом 14. Четвертый опорный план представим в таблице 1.6.

 

 

 

 

Таблица 1.6 – Четвертый опорный план

Пункты отправления	Пункты назначения
	Г (410)	В (350)	Е (170)	З (270)	И (180)	Избыток вагонов
А (100)	90	50		90		230
Б (-40)			110	90		200
Д (260)	10				90	100
Недостаток вагонов	100	50	110	180	90	530

 

L=(90·310+50·250+90·170+110·210+90·310+10·150+90·140)=120800 ваг-км.

Осуществляем проверку:

U₁ + L₁₃ = 100 + 335 = 435 ≥ 170 – условие выполняется;

U₁ + L₁₅ = 100 + 80 = 180 ≥ 180 – условие выполняется;

U₂ + L₂₁ = -40 + 110 = 70 < 410 – условие не выполняется;

U₂ + L₂₂ = -40 + 570 = 530 ≥ 350 – условие выполняется;

U₂ + L₂₅ = -40 + 400 = 360 ≥ 180 – условие выполняется;

U₃ + L₃₂ = 260 + 310 = 570 ≥ 350 – условие выполняется;

U₃ + L₃₃ = 260 + 250 = 510 ≥ 170 – условие выполняется;

U₃ + L₃₄ = 260 + 230 = 490 ≥ 270 – условие выполняется.

Для улучшения плана (целевая  функция L = 120800 ваг-км) необходимо переместить перевозку в ячейку, где условие оптимальности нарушено больше всего, то есть разность потенциалов максимальная (ячейка с индексом 21). Будем использовать ячейку с индексом 21. Пятый опорный план представим в таблице 1.7.

Таблица 1.7 – Пятый опорный план

Пункты отправления	Пункты назначения
	Г (190)	В (350)	Е (290)	З (270)	И (180)	Избыток вагонов
А (100)		50		90	90	230
Б (80)	90		110			200
Д (40)	10			90		100
Недостаток вагонов	100	50	110	180	90	530

 

L=(50·250+90·170+90·80+90·110+110·210+10·150+90·230)=90200 ваг-км.

Осуществляем проверку:

U₁ + L₁₁ = 100 + 310 = 410 ≥ 190 – условие выполняется;

U₁ + L₁₃ = 100 + 335 = 435 ≥ 290 – условие выполняется;

U₂ + L₂₂ = 80 + 570 = 650 ≥ 350 – условие выполняется;

U₂ + L₂₄ = 80 + 310 = 390 ≥ 270 – условие выполняется;

U₂ + L₂₅ = 80 + 400 = 480 ≥ 180 – условие выполняется;

U₃ + L₃₂ = 40 + 310 = 350 ≥ 350 – условие выполняется;

U₃ + L₃₃ = 40 + 250 = 290 ≥ 290 – условие выполняется;

U₃ + L₃₅ = 40 + 140 = 180 ≥ 180 – условие выполняется.

Выполнив проверку по свободным ячейкам, видим, что условие  выполняется. Количество занятых клеток равно 7, что также удовлетворяет требованиям. Следовательно, данный план является оптимальным.

Определим оптимальное  распределение порожних грузовых вагонов при перевозке лесных грузов.

В таблице 1.8 и 1.9 приведены  условия задачи и удельный (на 1 грузовой вагон) затраты на порожний пробег.

Таблица 1.8 – Условие задачи

Пункты отправления	Пункты назначения
	D1	D2	D3	D4	D5	Избыток вагонов
S1	X11	X12	X13	X14	X15	115
S2	X21	X22	X23	X24	X25	85
Недостаток вагонов	50	50	30	30	40	200

 

Таблица 1.9 – Расстояние между пунктами отправления и назначения

Пункты отправления	Пункты назначения
	D1(А)	D2(В)	D3(Д)	D4(Е)	D5(И)	Избыток вагонов
S1(Г)	310	460	150	100	290	115
S2(Ж)	245	225	275	90	165	85
Недостаток вагонов	50	50	30	30	40	200

 

Таблица 1.10 – Первый опорный план

Пункты отправления	Пункты назначения
	А (410)	В (560)	Д (250)	Е  (65)	И (140)	Избыток вагонов
Г (100)	50	50	15			115
Ж (-25)			15	30	40	85
Недостаток вагонов	50	50	30	30	40	200

 

L=(50·310+50·460+15·150+15·275+30·90+40·165)=54175 ваг-км.

Осуществляем проверку:

U₁ + L₁₄ = 100 + 100 = 200 ≥ 65 – условие выполняется;

U₁ + L₁₅ = 100 + 290 = 390 ≥ 140 – условие выполняется;

U₂ + L₂₁ = -25 + 245 = 220 < 410 – условие не выполняется;

U₂ + L₂₂ = -25 + 335 = 310 < 560 – условие не выполняется.

Для улучшения плана (целевая  функция L = 54175 ваг-км) необходимо переместить перевозку в ячейку, где условие оптимальности нарушено больше всего, то есть разность потенциалов максимальная (ячейка с индексом 22). Будем использовать ячейку с индексом 22. Второй опорный план представим в таблице 1.11.