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

Однородный продукт, сосредоточенный в трёх пунктах хранения с запасами A=(45;60;65) соответственно, необходимо распределить между четырьмя пунктами потребления, которым необходимо B=(31;40;41;49) единиц продукта соответственно. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна с_ij , а именно:

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

Общее количество продукции составляет: ∑a_i=45+60+65=170

Общая потребность в продукции составляет: ∑b_j=31+40+41+49=161

Таким образом имеем дисбаланс между запасом и потреблением. Для ликвидации дисбаланса введём фиктивного потребителя с потреблением равным: b₅=∑a_i - ∑b_j=170-161=9.

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

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

L=4x₁₁+ 5x₁₂+ 8x₁₃+ 6x₁₄+ 3x₂₁+ 2x₂₂+ 5x₂₃+ 1x₂₄+ 5x₃₁+ 6x₃₂+ 3x₃₃+ 2x₃₄+0+0+0+0

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

Число базисных неизвестных равно: k=n+m-1=5+3-1=7.

Первое базисное решение легко построить по правилу северо-западного угла.

A\B	b1=31		b2=40		b3=41		b4=49		b5=9		pi
a1=45	31	4	14	5		8		6		0	p1=0
a2=60		3	26	2	34	5		1		0	p2=-3
a3=65		5		6	7	3	49	2	9	0	p3=-2
qj	q1=3		q2=2		q3=6		q4=8		q5=2

Введем симплексные множители _ij = μ(p₁,p₂,p₃,q₁,q₂,q₃,q₄,q₅), которые выступают в качестве показателя эффективности перевозок, состоящие из p и q называемые потенциалами.

В качестве критерия эффективности плана перевозки выступает неположительность всех значений ₁₁ для свободных клеток.

Один из потенциалов выбираем произвольно, так как одно уравнение линейно зависит от остальных. Пусть p₁ = 0. Остальные потенциалы находим из условия, что для базисных клеток ∆_ij= p_i+q_j-C_ij=0. В данном случае получаем:

₁₁ = 0, p₁ + q₁ - c₁₁ = 0, 0+ q₁ -4 = 0, q₁ = 4

₁₂ = 0, p₁ + q₂ - c₁₂ = 0, 0+ q₂ -5 = 0, q₂ = 5

₂₂ = 0, p₂ + q₂ – c₂₂ = 0, p₂ + 5 -2 = 0, p₂ = - 3

₂₃ = 0, p₂ + q₃ – c₂₃ = 0, -3 + q₃ -5 = 0, q₃ = 8

₃₃ = 0, p₃ + q₃ – c₃₃ = 0, p₃+ 8 -3 = 0, p₃ = -5

₃₄ = 0, p₃ + q₄ – c₃₄ = 0, -5 +q₄ -2 = 0, q₄ = 7

₃₅ = 0, p₃ + q₅ – c₃₅ = 0, -5 + q₅ -0 = 0, q₅ = 5.

Произведем оценку (для свободных клеток), где нет поставок ∆_ij= p_i+q_j-C_ij:

₂₁ = p₂ + q₁ - c₂₁ = - 3 + 4 - 3 = - 2

₃₁ = p₃ + q₁ - c₃₁ = - 5 + 4 - 5 = - 6

₃₂ = p₃ + q₂ - c₃₂ = - 5 + 5 - 6 = - 6

₁₃ = p₁ + q₃ - c₁₃ = 0 + 8 - 8 = 0

₁₄ = p₁ + q₄ - c₁₄ = 0 + 7 - 6 = 1

₁₅ = p₁ + q₅ - c₁₅ = 0 + 5 - 0 = 5

₂₅ = p₂ + q₅ - c₂₅ = - 3 + 5 - 0 = 2

₂₄ = p₂ + q₄ - c₂₄ = - 3 + 7 - 2 = 2.

Так как решение не оптимально, т.е. существуют _ij, которые больше 0, поменяем набор базисных переменных. Для этого выберем ячейку, в которой оценка максимальна: max () = 5 = ₁₅ .

Для найденной свободной клетки (1;5) строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в базисных клетках. Это будет (1;5) – (1;2) – (2;2) – (2;3) – (3;3) – (3;5).

Находим максимальную поставку, которую можно передать по циклу: λmax=14.

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

A\B	b1=31		b2=40		b3=41		b4=49		b5=9		pi
a1=45	31	4	5	5		8		6	9	0	p1=0
a2=60		3	35	2	25	5		1		0	p2=-3
a3=65		5		6	16	3	49	2		0	p3=-5
qj	q1=4		q2=5		q3=8		q4=7		q5=0

Находим новые потенциалы, новые базисные оценки. Пусть p₁ = 0. Остальные потенциалы находим из условия, что для базисных клеток . В данном случае получаем:

₁₁ = 0, p₁ + q₁ - c₁₁ = 0, 0+ q₁ -4 = 0, q₁ = 4

₁₂ = 0, p₁ + q₂ - c₁₂ = 0, 0+ q₂ -5 = 0, q₂ = 5

₁₅ = 0, p₁ + q₅ – c₁₅ = 0, 0 + q₅ -0 = 0, q₅ = 0

₂₂ = 0, p₂ + q₂ – c₂₂ = 0, p₂ + 5 -2 = 0, p₂ = - 3

₂₃ = 0, p₂ + q₃ – c₂₃ = 0, -3 + q₃ -5 = 0, q₃ = 8

₃₃ = 0, p₃ + q₃ – c₃₃ = 0, p₃+ 8 -3 = 0, p₃ = -5

₃₄ = 0, p₃ + q₄ – c₃₄ = 0, -5 +q₄ -2 = 0, q₄ = 7

Произведем оценку (для свободных клеток), где нет поставок ∆_ij= p_i+q_j-C_ij:

₁₃ = p₁ + q₃ - c₁₃ = 0 + 8 - 8 = 0

₁₄ = p₁ + q₄ - c₁₄ = 0 + 7 - 6 = 1

₂₁ = p₂ + q₁ - c₂₁ = - 3 + 4 - 3 = - 2

₂₄ = p₂ + q₄ - c₂₄ = - 3 + 7 - 1 = 3

₂₅ = p₂ + q₅ - c₂₅ = - 3 + 0 - 0 = -3

₃₁ = p₃ + q₁ - c₃₁ = - 5 + 4 - 5 = - 6

₃₂ = p₃ + q₂ - c₃₂ = - 5 + 5 - 6 = - 6

₃₅ = p₃ + q₅ – c₃₅ = 0 - 5 - 0 = -5

Так как решение не оптимально, т.е. существуют _ij, которые больше 0, поменяем набор базисных переменных. Для этого выберем ячейку, в которой оценка максимальна: max () = 3 = ₂₄ .

Строим цикл пересчета и получаем следующее базисное допустимое решение:

A\B	b1=31		b2=40		b3=41		b4=49		b5=9		pi
a1=45	31	4	5	5		8		6	9	0	p1=0
a2=60		3	35	2		5	25	1		0	p2=-3
a3=65		5		6	41	3	24	2		0	p3=-5
qj	q1=4		q2=5		q3=8		q4=7		q5=0

Находим новые потенциалы и оценки.Наибольшую положительную оценку будет иметь свободная клетка (1;4). Для нее строим цикл пересчета и получаем следующее базисное допустимое решение:

A\B	b1=31		b2=40		b3=41		b4=49		b5=9		pi
a1=45	31	4		5		8	5	6	9	0	p1=0
a2=60		3	40	2		5	20	1		0	p2=-3
a3=65		5		6	41	3	24	2		0	p3=-5
qj	q1=4		q2=5		q3=8		q4=7		q5=0

Все оценки свободных клеток _ij ≤ 0, следовательно, мы получили оптимальное базисное допустимое решение:

L_min=31*4+5*6+40*2+20*1+41*3+24*2=425, т.е. минимальная стоимость перевозки всего груза из трех пунктов хранения в четыре пункта потребления составит 425 ед.