Решение транспортных задач методами линейного программирования

После введения в матрицу перевозок фиктивного потребителя при проверке на условие “вырождения” выясняется, что задача “вырожденная”, так как N_зан = 10, а сумма m + n = 5 + 8 = 13. Вводятся две фиктивные перевозки, равные нулю в клетки А₂В₅ и А₂В₆. Далее, после присвоения потенциалов строкам и столбцам и проверки плана по условиям оптимальности, выясняется, что нарушений условий оптимальности в данном плане нет. Представленный для проверки план перевозок является оптимальным.

В завершение решения необходимо проанализировать начальный и конечный планы перевозок.

Самым оптимальным  планом перевозок несомненно является начальный план, так как при  его составлении все потребители  прикреплялись к самым выгодным поставщикам. Однако этот план не может  быть реализован из-за нехватки продукции в пунктах А₅, А₃ и А₄. Начальный план показывает, что пункт производства А₁ является неперспективным и желательно развивать производство прежде всего в пунктах А₅, А₃ и А₄, причем, в первую очередь, именно в пункте А₅ (до 280 тыс. т продукции). Также можно сказать, что план, представленный в табл.18, вызывает увеличение общей себестоимости перевозок на 20? 5 = 100 тыс.руб., в табл. 19 – на 10· (5 + 5) = 100 тыс. руб., в табл. 20 – еще на 80· (5 + 5 + 5) = 1200 тыс. руб., в табл. 21 – на 60·(5 + + 5 + 5 + 15) = 1800 тыс. руб.

Итого, общие  дополнительные затраты, связанные  с прикреплением потребителей к  менее выгодным поставщикам из-за ограничений производства, составляют 3200 тыс. руб., что подтверждается при  сравнении начального и конечного  значений целевой функции D C = C_кон – C_нач = = 23050 – 19850 = 3200 тыс. руб.

Также, на каждом этапе расчета можно сопоставить  увеличение целевой функции с  затратами по альтернативному варианту. Например, план, представленный в табл.21, можно реализовывать, если развитие производства в пункте А₃ до 160 тыс. т не потребует затрат больше чем 1800 тыс. руб.

Необходимо  также отметить, что в конечном плане перевозок оказалось не вывезено из пункта А₁ 50 тыс. т продукции в связи с ее суммарным переизбытком.

Пример № 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