Пример № 5.

Автотранспортному объединению, в составе которого 5 автохозяйств А_1, А_2, А_3, А_4, А₅ с парком автомашин соответственно 30, 40, 20, 30 и 50 однородных автомобилей поступили заказы на предоставление этих автомобилей предприятиям P₁, P₂, P₃, P₄, P₅, P₆ в количестве 35, 25, 40, 30, 35 и 35 соответственно. Необходимо составить план прикрепления автомобилей автохозяйств объединения к данным предприятиям при условии минимального суммарного порожнего пробега от автохозяйств до предприятий. Расстояния от всех автохозяйств до всех предприятий в километрах известны и представлены в матрице расстояний (табл.24).

Таблица 24

Исходные данные

Автохозяйство	Парк автомашин	Предприятие
		P1	P2	P3	P4	P5	P6
		Потребность в автомобилях
		35	25	40	30	35	35
А1	30	15	10	15	30	25	40
А2	40	10	20	20	35	20	45
А3	20	22	30	30	45	34	30
А4	30	25	36	30	48	50	43
А5	50	30	25	26	40	60	50

Для составления математической модели задачи определяются суммарный парк автомобилей автотранспортного объединения и суммарные потребности в а втомобилях предприятий,

автомашин,

автомашин. Суммарный объем заказов превышает суммарное наличие автомобилей в автохозяйствах на 30 автомашин. Это задача открытого типа.

Целевой функцией будет являться минимальный суммарный порожний пробег автомобилей

, где x_ij – количество автомобилей i-го автохозяйства, поданных j-му предприятию.

Система ограничений

, (i = 1,2,...,5),

, (j = 1,2,...,6),

.

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

Таблица 25

Начальный план прикрепления автомобилей

 

Значение целевой функции составит

L_нач = f(x) = 10· 25 + 15· 40 + 30· 30 + 10· 35 + 20· 35 + 30· 35 = 3850 км.

В примере имеются строки с разнозначными разностями R_i (первая, вторая, третья строки являются абсолютно недостаточными, а четвертая и пятая строки – абсолютно избыточными), поэтому план не является оптимальным, расчеты продолжаются и производится первая корректировка. Определяются значения D _j для каждого столбца [по формуле (16)] и находится минимальное из этих отношений, согласно пункту 4 алгоритма решения задач, D = min {15; 15; 11; 10; 30; 13} = 10.

Строится контур корректировки и находится значение корректировки Dx [по формуле (17)] Dx= min {50;30;65} = 30.

Выбранное значение D x переносится и корректируются поставки в матрице назначений автомобилей. Для этого найденное значение D x вычитается от цифровых значений в нечетных вершинах контура и прибавляется к значениям в четных вершинах. Получается новый скорректированный план прикрепления автомобилей (табл.26) с увеличенными на величину D в недостаточных строках расстояниями перевозки.

Таблица 26

Скорректированный план п рикрепления автомобилей (первая корректировка)

Для плана перевозок, представленного в табл. 26, D = min{5; 5; 1; 20; 3} = 1; D x = min {20; 40; 35} = 20. Разности R_i разнозначные, план не является оптимальным, решение продолжается (табл. 27–29) согласно алгоритму.

Таблица 27

Скорректированный план прикрепления автомобилей (вторая корректировка)Для плана перевозок, представленного в табл. 27,

D = min{4; 15; 4; 8; 19; 2} = 2; D x = min {30; 35; 15} = 15.

Таблица 28

Скорректированный план прикрепления автомобилей (третья корректировка)

Д ля плана перевозок, представленного в табл. 28,

D = min{2; 13; 2; 6; 14} = 2; D x = min {15; 20; 15} = 15.

Таблица 29

Скорректированный план прикрепления автомобилей (четвертая корректировка)

Автохозяйство	Парк автомашин	Предприятие						Ri
		P1	P2	P3	P4	P5	P6
		Потребность в автомобилях
		35	25	40	30	35	35
А1	30	30	25 25	30 5	45	40	55	-0
А2	40	25 35	35	35	50	35 35	60	-30
А3	20	33	41	41	56	45	41 20	-0
А4	30	25	36	30 15	48	50	43 15	-0
А5	50	34	29	30 20	44 30	64	54	-0

В плане, представленном в табл. 29, все строки являются недостаточными, следовательно решение закончено. Для расчета суммарного порожнего пробега автомобилей конечного плана прикрепления и проверки решения методом потенциалов необходимо восстановить первоначальную реальную матрицу себестоимостей перевозок (табл. 30). Причем здесь необходимо заметить, что автохозяйство А₂ имеет в наличии только 40 автомашин, поэтому предоставить предприятиям P₁ и P₅ оно может 40 вместо заказанных 70 автомашин. Следовательно, какое-либо из этих предприятий получит автомашин меньше чем было заказано. Исходя из условия наименьшего порожнего пробега автомашин предприятию P₅ будет выделено только 5 машин из 35 заказанных.

Таблица 30

Конечный план прикрепления автомобилей

Автохозяйство	Парк автомашин	Предприятие
		P1	P2	P3	P4	P5	P6
		Потребность в автомобилях
		35	25	40	30	35	35
А1	30	15	10 25	15 5	30	25	40
А2	40	10 35	20	20	35	20 5	45
А3	20	22	30	30	45	34	30 20
А4	30	25	36	30 15	48	50	43 15
А5	50	30	25	26 20	40 30	60	50

Конечное значение целевой функции составит

L_кон = f (x) = 10· 25 + 15· 5 + 10· 35 + 20· 5 + 30· 20 + 30· 15 + 43· 15 + 26· 20 + 40· 30 = 4190 км.

Итак, из расчета следует, что конечное значение целевой функции превысило начальное значение на

DL=L_кон–L_нач=4190–3850=340 км.

Полученный конечный план необходимо проверить на оптимальность методом потенциалов.

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

= 200 – 170 = 30 автомобилей. Расстояния в клетках, связанных с фиктивным автохозяйством, принимаются равными нулю (табл. 31).

После введения в матрицу перевозок фиктивного поставщика при проверке на условие “вырождения” выясняется, что данное условие не выполняется, так как N_зан = 10, а сумма m + n = 5 + 6 = 12. Вводится фиктивная перевозка в клетку А₂P₂. После присвоения потенциалов строкам и столбцам, и проверки плана по условиям оптимальности [формула (9)], выясняется, что в плане есть нарушения условий оптимальности. Производится корректировка плана прикрепления автомобилей методом потенциалов (табл.31–34).

Таблица 31

Проверка решения методом п отенциалов

Таблица 32

Проверка решения методом потенциалов (первая корректировка)

Таблица 33

Проверка решения методом потенциалов (вторая корректировка)

Таблица 34

Проверка решения методом потенциалов (третья корректировка)

Автохозяйство	Парк автомашин	Предприятие						Ui
		P1	P2	P3	P4	P5	P6
		Потребность в автомобилях
		35	25	40	30	35	35
А1	30	15 0	10 25	15 5	30	25	40	50
А2	40	10 5	20	20	35	20 35	45	55
А3	20	22	30	30	45	34	30 20	49
А4	30	25 30	36	30	48	50	43	44
А5	50	30	25	26 35	40 15	60	50	39
Афикт	30	0	0	0	0 15	0	0 15	79
Vj		65	60	65	79	75	79

В плане прикрепления автомобилей, приведенном в табл.34, выполняются условия оптимальности [см. формулу (9)], следовательно план оптимален.

Таблица 35

Конечный итоговый план прикрепления автомобилей

Автохозяйство	Парк автомашин	Предприятие
		P1	P2	P3	P4	P5	P6
		Потребность в автомобилях
		35	25	40	30	35	35
А1	30	15	10 25	15 5	30	25	40
А2	40	10 5	20	20	35	20 35	45
А3	20	22	30	30	45	34	30 20
А4	30	25 30	36	30	48	50	43
А5	50	30	25	26 35	40 15	60	50

Итоговое значение целевой функции составит

L_итог = f(x) = 10· 25 + 15· 5 + 10· 5 + 20· 35 + 30· 20 + 25· 30 + 26· 35 + 40· 15 = = 3935 км.

Итак, план, скорректированный методом потенциалов, позволил уменьшить суммарный порожний пробег автомобилей по сравнению со значением целевой функции, полученным в результате решения методом условно-оптимальных планов. Величина уменьшения целевой функции

DL=L_итог–L_кон=3935–4190=-255 км.

При анализе решения видно, что автомобили недопоставлены предприятиям P₄ (в количестве 15 автомашин) и P₆ (в количестве 15 автомашин), в отличие от плана, приведенного в табл.31, где из-за нехватки автомобилей, был не полностью выполнен заказ предприятия P₅ (недопоставка 30 автомашин).