Транспортная задача линейного программирования

 

Задание:

Составить математическую модель транспортной задачи по исходным данным:

; ;

Если полученная модель окажется открытой, то свести ее к замкнутой и найти оптимальное решение транспортной задачи методом потенциалов.

Постановка задачи:

Однородный продукт, сосредоточенный в трехпунктах производства (хранения) в количествах 35,  55 и 80  единиц, необходимо распределить между n -четырьмя пунктами потребления, которым необходимо соответственно 30, 55, 44, 42 единиц. Стоимость перевозки единицы продукта из i -го пункта отправления ( ) в j-ый пункт назначения ( ) равна с _ij и известна для всех маршрутов. Она задана матрицей С:

 Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.

Обозначим через х_ij количество груза, планируемого к перевозке от i-го поставщика ( ) j-му ( ) потребителю.  При наличии баланса производства и потребления        (1)

Общий объем производства åа _i = 80+50+35= 170 меньше , требуется всем потребителям åb_i = 30+55+44+42=171.

Таким образом, имеет место дисбаланс между запасами и запросами. В математическом плане это означает, что наша задача – это задача открытого типа. Для устранения дисбаланса (приведения задачи к закрытому типу), введем фиктивный пункт производства с объемом производства, равным указанному дисбалансу т.е.  единице, причем тарифы на перевозку из этого пункта условимся считать равными нулю ( ).

Четырьмя условиями того, что из каждого пункта хранения вывозится весь продукт, являются:

Четырьмя условиями того, что каждому потребителю доставляется затребованное им количество продукта являются:

 

B A	b1=30		b2=55		b3=44		b4=42
a1=35	x11	2	x12	3	x13	6	x 14	4
a2=55	x21	4	x22	1	x23	5	x24	7
a3=80	x31	5	x32	2	x33	3	x34	3
a4=1	x41	0	x42	0	x43	0	x44	0

 

В качестве показателя эффективности выступает суммарная стоимость перевозок (L):

;

В качестве критерия эффективности правомерно считать принцип минимизации результата т.к. на лицо стремление уменьшить стоимость перевозок. Приходим к следующей математической постановке задачи: найти план перевозок x , компоненты которого обеспечивают минимизацию линейной формы L , при   следующих ограничениях на эти компоненты:

 

                                                     (1)

 

Решение:

Сформулированная задача является задачей линейного программирования, которая обладает двумя особенностями, а именно

1) коэффициент при каждой из неизвестных в системе ограничений (1) равен 1;

2) одно из уравнений системы ограничений линейно зависит от других, в силу чего число базисных неизвестных в системе равно .

Эти особенности позволяют решить задачу специально разработанными методами: методом северо-западного угла или методом наименьших затрат. Мы решим ее двумя способами.

 

Метод наименьших затрат

 

потреб произв		b1=30		b2=55		b3=44		b4=42
a1=35		30	2		3		6	5	4	p1=0
a2=55		0	4	55	1	*	5		7	p2=2
a3=80			5		2	44	3	36	3	p3=-1
a4=1			0		0		0	1	0	p4=-4
	q1=2			q2=-1		q3=4		q4=4

 

Обозначим через   m ) вектор симплексных множителей или потенциалов. Тогда .

Один из потенциалов можно выбрать произвольно, так как в системе (1) одно уравнение линейно зависит от остальных. Положим, что р₁ = 0. Остальные потенциалы находим из условия, что для базисных клеток . В данном случае получаем:

D ₁₁ = 0,     p ₁ + q ₁ - c ₁₁ = 0, q ₁ = 2

D ₁₄ = 0,     p ₁ + q ₄ - c ₁₄ = 0, q ₄ = 4

D ₃₄ = 0,     p₃ + q₄ – c₃₄ = 0, p₃ = -1

D ₃₃ = 0,     p₃ + q₃ – c₃₃ = 0, q₃= 4

D ₂₁ = 0,     p₂ + q₁ – c₂₁ = 0, p₂ = 2

D ₂₂ = 0,     p ₂ + q ₂ – c ₂₂ = 0, q ₂ = -1

D ₄₄ = 0,     p ₄ + q ₄ – c ₄₄ = 0, p ₄ =-4

Теперь по формуле вычисляем оценки всех свободных клеток:

D ₁₂ = p₁ + q₂ – c₁₂ = 0-1-3=-4

D ₁₃ = p₁ + q₃ – c₁₃ = 0+4-6 =-2

D ₂₃ = p₂ + q₃ – c₂₃ = 2+4-5 = 1             - max

D ₂₄ = p₂ + q₄ – c₂₄ = 2+4-7 = -1

D ₃₁ = p₃ + q₁ - c₃₁ = -1+2-5 = -4

D ₃₂ = p₃ + q₂ – c₃₂ = -1-1-2 = -4

D ₄₁ = p₄ + q₁ – c₄₁ = -4+2-0 = -2

D ₄₂ = p₄ + q₂ – c₄₂ = -4-1-0 = -5

D ₄₃ = p ₄ + q ₃ – c ₄₃ = -4-4-0 = -8

Находим наибольшую положительную оценку max ( ) = 1 = D ₂₃

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

Это будет 23-21-11-14-34-33-23:

30		5		30+		5-		30		5
0	*			0-					0
	44	36			44-	36+			44	36

 

min =0

 

потреб произв		b1=30		b2=55		b3=44		b4=42
a1=35		30	2		3		6	5	4	p1=0
a2=55			4	55	1	0	5		7	p2=1
a3=80			5		2	44	3	36	3	p3=-1
a4=1			0		0		0	1	0	p4=-4
	q1=2			q2=0		q3=4		q4=4

D ₁₄ = 0,      p₁ + q ₄ - c_{1 4} = 0, q ₄ = 4

D ₃₄ = 0,     p₃ + q₄ – c₃₄ = 0, p₃ = -1

D ₃₃ = 0,     p₃ + q₃ – c₃₃ = 0, q₃= 4

D _{2 3} = 0,     p₂ + q ₃ – c_{2 3} = 0, p₂ = 1

D ₂₂ = 0,     p₂ + q₂ – c₂₂ = 0, q₂ = 0

D ₄₄ = 0,     p₄ + q₄ – c₄₄ = 0, p₄=-4

 

Теперь по формуле вычисляем оценки всех свободных клеток:

D ₁₂ = p₁ + q₂ – c₁₂ = 0-3=-3

D ₁₃ = p₁ + q₃ – c₁₃ = 0+4-6 =-2

D ₂₁ = p₂ + q₃ – c₂₃ = 1+2-4 = -1

D ₂₄ = p₂ + q₄ – c₂₄ = 1+4-7=-2

D ₃₁ = p₃ + q₁ - c₃₁ = -1+2-5 = -4

D ₃₂ = p₃ + q₂ – c₃₂ = -1+0-2=-3

D ₄₁ = p₄ + q₁ – c₄₁ = -4+2=-2

D ₄₂ = p₄ + q₂ – c₄₂ = -4+0=-4

D ₄₃ = p ₄ + q ₃ – c ₄₃ = -4+4-0 = 0

Итак, , при

Таким образом, пришли к оптимальному решению

 

 Общая стоимость перевозок:   денежных единиц.

Для проверки полученного результата теперь решим задачу методом северо-западного угла.

Метод Северо-западного угла

потреб произв		b1=30		b2=55		b3=44		b4=42
a1=35		30	2	5	3		6		4	p1=0
a2=55			4	50	1	5	5		7	p2= -2
a3=80		*	5		2	39	3	41	3	p3=- 4
a4=1			0		0		0	1	0	p4=- 7
	q1=2			q2= 3		q3= 7		q4= 7

 

денежных единиц

 

D 11 = 0,     p1 + q1 - c11 = 0, q1 = 2 D 12 = 0,    p1 + q2 - c12 = 0,  q2 =-3 D 22 = 0,     p2 + q2 – c22 = 0, p2 = -2 D 33 = 0,     p3 + q3 – c33 = 0, q3= 7 D 34 = 0,     p3 + q4 – c34 = 0, q4 =7 D 44 = 0,     p4 + q4 – c44 = 0, p4=-7

Теперь по формуле вычисляем оценки всех свободных клеток: D 13 = p1 + q3 – c13 = 0+7-6=1 D 14 = p1 + q4 – c14 = 0+7-4=3 D 21 = p2 + q1 – c21 = -2+2-1 =-1 D 24 = p2 + q4 – c24 = -2+7-7 = -2 D 31 = p3 + q1 - c31 = -4+2-5=7 ( max) D 32 = p3 + q2 – c32 = -4+3-2=-3 D 41 = p4 + q1 – c41 = -7+2-0=-5 D 42 = p4 + q2 – c42 = -7+3=-4 D 43 = p 4 + q 3 – c 43 = -7+7=0

 

Находим наибольшую положительную оценку max ( ) = 7 = D ₃₁

 

 

Для найденной свободной клетки 31 строим цикл пересчета:

 

30	5			30 -	5+				35
	50	5			50-	5+			20	35
*		39				3 9-		30		9

 

min =3

 

потреб произв		b1=30		b2=55		b3=44		b4=42
a1=35		*	2	3 5	3		6		4	p1=0
a2=55			4	20	1	3 5	5		7	p2= -2
a3=80		30	5		2	9	3	41	3	p3=- 4
a4=1			0		0		0	1	0	p4=- 7
	q1=9			q2= 3		q3= 7		q4= 7

денежных единиц

D 12 = 0,    p1 + q2 - c12 = 0,  q2 =3 D 22 = 0,     p2 + q2 – c22 = 0, p2 = -2 D 23 = 0,     p2 + q3 – c23 = 0, q3 = 7 D 33 = 0,     p3 + q3 – c33 = 0, p3= -4 D 31 = 0,     p3 + q1 – c31 = 0, q1 =9 D 34 = 0,     p3 + q4 – c34 = 0, q4=7

Теперь по формуле вычисляем оценки всех свободных клеток: D 11 = p1 + q1 – c11 = 0+9-2=7(max) D 13 = p1 + q3 – c13 = 0+7-6=1 D 14 = p1 + q4 – c14 = 0+7-4=3 D 21 = p2 + q1 – c21 = -2+9-4 =3 D 24 = p2 + q4 – c24 = -2+7-7 = -2 D 32 = p3 + q2 – c32 = -4+3-2=-3 D 41 = p4 + q1 – c41 = -7+9=2 D 42 = p4 + q2 – c42 = -7+3=-4 D 43 = p 4 + q 3 – c 43 = -7+7=0

 

Находим наибольшую положительную оценку max ( ) = 7 = D ₁₁

Для найденной свободной клетки 11 строим цикл пересчета:

 

*	35			*	35-			30	5
	20	35			20+	35-			50	5
30		9		30-		9+				39

min =30

потреб произв		b1=30		b2=55		b3=44		b4=42
a1=35		30	2	5	3		6	*	4	p1=0
a2=55			4	50	1	5	5		7	p2= -2
a3=80			5		2	3 9	3	41	3	p3=- 4
a4=1			0		0		0	1	0	p4=- 7
	q1=2			q2= 3		q3= 7		q4= 7

 

 денежных единиц

 

D 11 = 0,    p1 + q1 - c11 = 0,  q1 =2 D 12 = 0,    p1 + q2 - c12 = 0,  q2 =3 D 22 = 0,     p2 + q2 – c22 = 0, p2 = -2 D 23 = 0,     p2 + q3 – c23 = 0, q3 = 7 D 33 = 0,     p3 + q3 – c33 = 0, p3= -4 D 34 = 0,     p3 + q4 – c34 = 0, q4=7

Теперь по формуле вычисляем оценки всех свободных клеток: D 13 = p1 + q3 – c13 = 0+7-6=1 D 14 = p1 + q4 – c14 = 0+7-4=3(max) D 21 = p2 + q1 – c21 = -2+2-4=-4 D 24 = p2 + q4 – c24 = -2+7-7 = -2 D 31 = p3 + q1 – c31 = -4+2-5=-7 D 32 = p3 + q2 – c32 = -4+3-2=-3 D 41 = p4 + q1 – c41 = -7+2=-5 D 42 = p4 + q2 – c42 = -7+3=-4 D 43 = p 4 + q 3 – c 43 = -7+7=0

 

Находим наибольшую положительную оценку max ( ) = 3= D ₁₄

Для найденной свободной клетки 14 строим цикл пересчета:

 

5		*		5-						5
50	5			50+	5-			55
	39	41			39+	41-			44	36

 

min =5

потреб произв		b1=30		b2=55		b3=44		b4=42
a1=35		30	2	0	3		6	5	4	p1=0
a2=55			4	55	1		5		7	p2= -2
a3=80			5		2	44	3	36	3	p3=-1
a4=1			0		0		0	1	0	p4=-4
	q1=2			q2= 3		q3=4		q4=4

 

D 11 = 0,    p1 + q1 - c11 = 0,  q1 =2 D 14 = 0,     p1 + q4 – c14 = 0, q4 = 4 D 34 = 0,     p3 + q4 – c34 = 0, p3= -1 D 12 = 0,     p1 + q2 – c12 = 0, q2 =3 D 22 = 0,     p2 + q2 – c22 = 0, p2=-2 D 33 = 0,     p3 + q3 – c33 = 0, q3= 4 D 44 = 0,     p4 + q4 – c44 = 0, p4= -4

Теперь по формуле вычисляем оценки всех свободных клеток: D 13 = p1 + q3 – c13 = 4-6=-2 D 21 = p2 + q1 – c21 = -2+2-4 =-4 D 24 = p2 + q4 – c24 = -2+4-7=-5 D 31 = p3 + q1 – c31 = -1+2-5=-4 D 32 = p3 + q2 – c32 = -1+3-2=0 D 41 = p4 + q1 – c41 = -4+2=-2 D 42 = p4 + q2 – c42 = -4+3=-1 D 43 = p4 + q3 – c43 = -4+4=0

 

Таким образом, пришли к оптимальному решению

 

 денежных единиц.