Решение задач

  Возьмём нужную нам часть графика в  более крупном масштабе, учитывая, что по смыслу задачи t₁³0, t₂³0 : 

  

  

   В точке А достигается максимальное значение функции W. Найдём её координаты:

  

  A (107/3;160/3)

  W_max=107/3*7+160/3*8=676 

Программа «расшивки» имеет вид t₁=107/3 t₂=160/3 t₃=0, и прирост прибыли составит 676

Сводка  результатов: 

Сj	60	12	44	17	b	X4+i	yi	t
ai,j	4	2	4	1	180	0	7	107/3
	4	0	2	2	160	0	8	160/3
	2	4	3	0	109	9	0	0
хj	35	0	10	0	2540
∆j	0	2	0	6

 
 
 
 
 
 
 
 
 
 

 

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  Для найденной свободной клетки (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. Остальные потенциалы находим из условия, что для базисных клеток . В данном случае получаем:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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