Задача о «расшивке узких мест производства»

При выполнении оптимальной производственной программ Первый и Второй ресурсы используются полностью, то есть образуют “узкие места производства”. Будем заказывать их дополнительно. Пусть T = (t₁, t₂, t₃) – вектор дополнительных объёмов ресурсов.

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

Так как мы используем найденные оценки ресурсов, то должно выполняться условие:

H + Q^-1T ³ 0

Задача состоит в том, чтобы найти вектор Т(t₁; t_2; 0), максимизирующий суммарный прирост прибыли W = 6t₁ + 3t₂ при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы).

Обращённый базис Q, соответствующий оптимальной производственной программе, содержатся в последней симплексной таблице в первой, второй, третьей строках восьмого, девятого и десятого столбцов:

Подставив соответствующие значения, получим требуемую математическую модель:

предполагая, что дополнительно можно надеяться получить не более 1/3 первоначального объёма ресурса каждого вида, то есть:

Перепишем неравенства в другом виде и получим:

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

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

A (50;160/9)

W_max=50*6+160/9*3=1060/3=353 1/3

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

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

Сj	30	11	45	6	b	X4+i	yi	t
ai,j	3	2	6	0	150	0	6	50
	4	2	3	5	130	0	3	160/9
	4	3	2	4	124	8	0	0
хj	22	0	14	0	1290
∆j	0	7	0	9

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

Однородный продукт, сосредоточенный в трёх пунктах хранения с запасами A=(50;70;30) соответственно, необходимо распределить между четырьмя пунктами потребления, которым необходимо B=(30;11;45;36) единиц продукта соответственно. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна с_ij , а именно:

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

Общее количество продукции составляет: ∑a_i=50+70+30=150

Общая потребность в продукции составляет: ∑b_j=30+11+45+36=122

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

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

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

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

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

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

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

A\B	b1=30		b2=11		b3=45		b4=36		b5=28		pi
a1=50	30	3	11	2	9	6		7		0	p1=0
a2=70		7		8	36	3	34	5		0	p2=-3
a3=30		4		3		4	2	6	28	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₁ -3 = 0, q₁ = 3

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

₁₃ = 0, p₁ + q₃ – c₁₃ = 0, 0 + q₃ -6 = 0, q₃ = 6

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

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

₃₄ = 0, p₃ + q₄ – c₃₄ = 0, p₃ + 8 – 6 = 0, p₃ = - 2

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

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

₂₁ = p₂ + q₁ - c₂₁ = - 3 + 3 - 7 = - 7

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

₂₂ = p₂ + q₂ - c₂₂ = - 3 + 2 – 8 = - 9

₃₂ = p₃ + q₂ – c₃₂ = - 2 + 2 – 3 = - 3

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

₁₄ = p₁ + q₄ – c₁₄ = 0 + 8 – 7 = 1

₁₅ = p₁ + q₅ – c₁₅ = 0 + 2 – 0 = 2

₂₅ = p₂ + q₅ – c₂₅ = - 3 + 2 – 0 = -1.

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

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

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

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

A\B	b1=30		b2=11		b3=45		b4=36		b5=28		pi
a1=50	30	3	11	2		6		7	9	0	p1=0
a2=70		7		8	45	3	25	5		0	p2=-1
a3=30		4		3		4	11	6	19	0	p3=0
qj	q1=3		q2=2		q3=4		q4=6		q5=0

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

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

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

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

₃₅ = 0, p₃ + q₅ – c₃₅ = 0, p₃ + 0 – 0 = 0, p₃ = 0

₃₄ = 0, p₃ + q₄ – c₃₄ = 0, 0 + q₄ – 6 = 0, q₄ = 6

₂₄ = 0, p₂ + q₄ – c₂₄ = 0, p₂ + 6 – 5 = 0, p₂ = - 1.

₃₃ = 0, p₃ + q₃ – c₃₃ = 0, 0 + q₃ -4 = 0, q₃ = 4

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

₂₁ = p₂ + q₁ - c₂₁ = - 1 + 3 - 7 = - 5

₃₁ = p₃ + q₁ - c₃₁ = 0 + 3 - 4 = - 1

₂₂ = p₂ + q₂ - c₂₂ = - 1 + 2 – 8 = - 7

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

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

₃₃ = p₃ + q₃ – c₃₃ = 0 + 4 – 4 = 0

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

₂₅ = p₂ + q₅ – c₂₅ = - 1 + 0 – 0 = -1

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

L_min=3*30+ 2*11+ 3*45+ 5*25+ 6*11=438, т.е. минимальная стоимость перевозки всего груза из трех пунктов хранения в четыре пункта потребления составит 438 ед.