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

Б	Б	Н	45	60	21	14	0	0	0	Примечания
			Х1	Х2	Х3	Х4	Х5	Х6	Х7
60	Х2	15	0	1	3/5	–3/5	1/5	–1/10	0
45	Х1	30	1	0	–1/5	6/5	–1/15	1/5	0
0	Х7	7	0	0	18/5	32/5	–7/15	–1/10	1
	Z	2250	0	0	6	4	15	3	0

При выполнении оптимальной производственной программы первый и второй ресурсы используются полностью, тем самым они образуют "узкие места" производства. Будем их заказывать дополнительно. Пусть T = (t₁,t₂, 0) — вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие H + Q^–1 = 0 или H– Q^–1T, где H — значения базисных переменных в последней симплексной таблице, а Q^–1 — обращенный базис, который образуют столбцы при балансовых переменных в этой таблице.

Задача состоит в том, чтобы найти вектор T , максимизирующий суммарный прирост прибыли W = 9t₁ + 3t₂ (1) при условии, сохранения двойственных оценок ресурсов (и, следовательно, ассортимента выпускаемой продукции)

(2)

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

(3)

причем по смыслу задачи t₁ ≥ 0, t₂ ≥ 0

(4)

Переписав неравенства (2) и (3) в виде системы:

1/5t₁ – 2/10t₂ ≤ 15

–1/15t₁ + 1/5t₂ ≤ 30 (5)

–7/15t₁ – 1/10t₂ ≤ 7

t₁ ≥ 0, t₂ ≥ 0 (6)

t₂ ≤ 150 + 2t₁

t₁ ≤ 450+ 3t₂

t₂ ≤ 70 – 14/3t₁

t₁ ≤ 60

t₂ ≤ 70

t₁ ≥ 0, t₂ ≥ 0

приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).

Эту задачу можно решить графически:

Программа "расшивки" имеет вид t₁= 0 , t₂= 70,t₃= 0,

а прирост прибыли составил

W_max= 9∙0+ 3∙70 =210

Z_o=Z_max + W_max = 2250 + 210 = 2460

3. Транспортная задача.

Дан однородный продукт, сосредоточенный в m пунктах производства (хранения) в количествах a₁,a₂,…..a_m единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно b1,b2,….b_n единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна c_ij и известна для всех маршрутов.

3 6 3 1 50

C= 6 2 1 6 A= 70 B= (45, 60, 21, 24)

10 3 5 7 40

A – вектор объемов производства

B – вектор потребностей потребителей

C – матрица транспортных издержек

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

Обозначим через x_ij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю.

–открытая модель транспортной задачи

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

найти план перевозок

Х=(x_ij), i= 1,m; j = 1,n

минимизирующий общую стоимость всех перевозок

L=c_ij*x_ij

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

Xija_i , i= 1,m

Так как общий объем производства 50+70+40=160 больше суммарных запросов всех потребителей45+60+21+24=150, т.е. имеем открытую модель транспортной задачи, то для сведения задачи к замкнутой модели введем фиктивного потребителя и, считая, что поставщики равноправны, все тарифы на поставки продукта фиктивному потребителю положим равными нулю, т.е. С₁₅=0, С₂₅=0, С₃₅=0, при этом b₅=10 (160 – 150=10). Первое базисное допустимое решение строим по правилу "северо-западного угла.

Потребление Производство	b1=45	b2=60	b3=21	b4=24	b5=10
50	45 ^3	5 ^6	√ ^3	√^1	√ ^0	p1= 0
70	√ ^6	55 ^2	15 ^1	√ ^6	√ ^0	p2= -4
40	√ ^10	√ ^3	6 ^5	24 ^7	10 ^0	p3=0
	q1=3	q2=6	q3=5	q4= 7	q5 = 0

Принимаем p₁ = 0. Из отношения p_i = c_ij – q_j и q_j=c_ij–p_i находим все последующие значения p и q.

q1=3–0=3 p3=5–5=0

q2=6–0=6 q4=7–0=7

p2=2–6=-4 q5=0– 0=0

q3=1+4=5

Затем по формуле ∆_ij = p_i + q_j – c_ij вычисляем оценки всех свободных клеток; для найденных свободных клеток строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Производим перераспределение поставок вдоль цикла пересчета. Продолжаем процесс до тех пор, пока не придем к таблице, для которой все ∆ij>0

∆₁₃=p₁+q₃–c₁₃=0+5-3=2 ∆₂₁=p₂+q₁–c₂₁=-4+3-6=-7 ∆₃₁= p₃+q₁–c₃₁=0+3-10=-7

∆₁₄=p₁+q₄–c₁₄=0+7-1=6 ∆₂₄= p₂+q₄–c₂₄=-4+7-6=-3 ∆₃₂= p₃+q₂–c₃₂=0+6-3=3

∆₁₅=p₁+q₅–c₁₅=0+0-0=0 ∆₂₅= p₂+q₅–c₂₅=-4+0-0=-4

∆₁₄=6max > 0

Потребление Производство	b1=45	b2=60	b3=21	b4=24	b5=10
50	45 ^3	√ ^6	√ ^3	5 ^1	√ ^0	p1= 0
70	√ ^6	60 ^2	10 ^1	√ ^6	√ ^0	p2= 2
40	√ ^10	√^3	11 ^5	19 ^7	10 ^0	p3=6
	q1=3	q2=0	q3=-1	q4= 1	q5 = -6

∆₁₂=p₁+q₂–c₁₂=0+0-6=-6 ∆₂₁=p₂+q₁–c₂₁=2+3-6=-1 ∆₃₁= p₃+q₁–c₃₁=6+3-10=-1

∆₁₃= p₁+q₃–c₁₃=0-3-1=-2 ∆₂₄= p₂+q₄–c₂₄=2+1-6=-3 ∆₃₂= p₃+q₂–c₃₂=6+0-3=3

∆₁₅=p₁+q₅–c₁₅=0-6-0=-6 ∆₂₅= p₂+q₅–c₂₅=2-6-0=-4

∆₃₂=3 max > 0

Потребление Производство	b1=45	b2=60	b3=21	b4=24	b5=10
50	45 ^3	√ ^6	√ ^3	5 ^1	√ ^0	p1= 0
70	√^6	49 ^2	21 ^1	√ ^6	√ ^0	p2= 5
40	√ ^10	11 ^3	√ ^5	19 ^7	10 ^0	p3=6
	q1=3	q2=-3	q3=-4	q4= 1	q5 = -6

∆₁₂=p₁+q₂–c₁₂=0-3-6=-9 ∆₂₁=p₂+q₁–c₂₁=5+3-6=2 ∆₃₁= p₃+q₁–c₃₁=6+3-10=-1

∆₁₃= p₁+q₃–c₁₃=0-4-3=-7 ∆₂₄= p₂+q₄–c₂₄=5+1-6=0 ∆₃₃= p₃+q₃–c₃₃=6-4-5=-3

∆₁₅=p₁+q₅–c₁₅=0-6-0=-6 ∆₂₅= p₂+q₅–c₂₅=5-6-0=-1

∆₂₁=2 max > 0

Потребление Производство	b1=45	b2=60	b3=21	b4=24	b5=10
50	26 ^3	√ ^6	√ ^3	24 ^1	√ ^0	p1= 0
70	19 ^6	30 ^2	21 ^1	√ ^6	√ ^0	p2= 3
40	√ ^10	30 ^3	√ ^5	√ ^7	10 ^0	p3=4
	q1=3	q2=-1	q3=-2	q4= 1	q5 = -4

∆₁₂=p₁+q₂–c₁₂=0-1-6=-7 ∆₂₄= p₂+q₄–c₂₄=3+1-6=-5 ∆₃₁= p₃+q₁–c₃₁=4+3-10=-3

∆₁₃= p₁+q₃–c₁₃=0-2-3=-5 ∆₂₅= p₂+q₅–c₂₅=3-4-0=-1 ∆₃₃= p₃+q₃–c₃₃=4-2-5=-3

∆₁₅=p₁+q₅–c₁₅=0-4-0=-4 ∆₃₄= p₃+q₄–c₃₄=4+1-7=-2

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

	26	0	0	24
X=	19	30	21	0
	0	30	0	0