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

Федеральное агентство по образованию

Государственное образовательное  учреждение высшего профессионального  образования

Государственный Университет Управления

Институт управления в промышленности и энергетике

Кафедра прикладной математики

 

 

 

 

 

Курсовая работа

По дисциплине: «Прикладная  математика»

 

 

 

 

 

Выполнил	Ким Е.А.
Институт	УИ 3-1
Вариант	4
Руководитель
Дата  сдачи на проверку
Дата  защиты
Оценка
Подпись руководителя

 

 

 

 

 

 

 

 

 

 

Москва 2011 

 

Содержание:

 

 

 

1. Линейная производственная  задача

Предприятие выпускает 4 вида продукции, используя 3 вида ресурсов.

Технологическая матрица  производства (A), запас ресурсов (B), удельная прибыль предприятия от производства и реализации каждого вида продукции (C) известны.

 

    

Требуется составить  такой план производства продукции X=(x₁,x₂,x₃,x₄), реализация которого обеспечивает предприятие наибольшей прибылью.

При производстве x₁ – единиц продукции Первого вида, x₂ – единиц продукции Второго вида, x₃ – единиц продукции Третьего вида, x₄ – единиц продукции Четвёртого вида предприятие затрачивает 3x₁+2x₂+6x₃+0x₄ единиц ресурсов Первого вида.

Очевидно, что оно не должно превышать имеющийся запас ресурса Первого вида, а именно 150.

Составив аналогичные  ограничения для ресурсов Второго  и Третьего видов, получаем систему  неравенств:

 

         (1)

 

Z=30x₁+11x₂+45x₃+6x₄

В качестве критерия эффективности правомерно принять принцип максимального результата, поэтому математическая постановка задачи выглядит следующим образом: найти вектор X, обеспечивающий максимум линейной форме Z=30x₁+11x₂+45x₃+6x₄ при ограничивающих неравенствах (1) на его компоненты.

Данная задача является задачей линейного программирования. Для её решения симплексным методом  проведём систему ограничений к  предпочтительному виду за счёт введения в левую часть каждого ограничения  по одной дополнительной неотрицательной неизвестной x₅, x₆, x₇.

Переменные x₅, x₆, x₇ по экономическому смыслу будут представлять собой остаток ресурсов Первого, Второго и Третьего видов соответственно.

Выразим функцию Z таким образом для подстановки в таблицу:

0-Z=-30x₁-11x₂-45x₃-6x₄

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Решим систему симплексным  методом:

 

 

C	Базис	H	х1	х2	х3	х4	х5	х6	х7	Примечание
0	Х5	150	3	2	6	0	1	0	0	Min ∆j=-45 х3 – в базис min(H/ai3>0)= =min(150/6;130/3;124/2)=150/6=25 х5 – из базиса 1-е ур-ие разрешающее
0	Х6	130	4	2	3	5	0	1	0
0	Х7	124	4	3	2	4	0	0	1
		0-Z	-30	-11	-45	-6	0	0	0
										Min ∆j=-15/2 х1 – в базис min(50;22;74/3)=22 х6 – из базиса 2-е ур-ие разрешающее
45	X3	25	1/2	1/3	1	0	1/6	0	0
0	Х6	55	5/2	1	0	5	-1/2	1	0
0	Х7	74	3	7/3	0	4	-1/3	0	1
		1125-Z	-15/2	4	0	-6	15/2	0	0
										Все ∆j=>0 => решение оптимальное X=(22;0;14;0;0;0;8) Zmax=1290
45	Х3	14	0	2/15	1	-1	4/15	-1/5	0
30	Х1	22	1	2/5	0	2	-1/5	2/5	0
0	Х7	8	0	17/15	0	-2	4/15	-6/5	1
		1290-Z	0	7	0	9	6	3	0

 

 

Оптимальная производственная программа: x₁=22, x₂=0, x₃=14, x₄=0.

Остатки ресурсов: первого  вида –x₅=0, второго вида –x₆=0, третьего вида – x₇=8.

Узкими местами производства, т.е. ресурсами, использующимися полностью, являются 1-й и 2-й ресурсы, x₅=0 и x₆=0 соответственно.

 

Среди коэффициентов  при неизвестных в левой части  уравнения нет ни одного отрицательного. Если из этого уравнения выразить функцию цели z через остальные неотрицательные переменные

z = 1290 - 7х₂ - 9х₄ - 6х₅ - 3х₆                (2)

то становится совершенно очевидным (в силу того, что все x_j³0), что прибыль будет наибольшей тогда, когда x₂=0, x₄=0, x₅=0, x₆=0

Это означает, что производственная программа (2) является наилучшей и  обеспечивает предприятию наибольшую прибыль z_max = 1290

 

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

 

Для того, чтобы убедиться  в правильности полученного решения, следует проверить отношение  Н = Q^-1 * В:

 

 

Воспользуемся тем, что в оптимальной производственной программе х₂=0, х₄=0. Предположим, что продукции Второго и Четвёртого видов мы не намеревались выпускать с самого начала. Рассмотрим задачу с оставшимися двумя переменными, сохранив их нумерацию. Математическая модель задачи будет выглядеть следующим образом:

F(x₁,x₃)=30x₁+45x₃→max

 

 - направления наибольшего роста целевой функции F.

 

 

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

F(22;14)=F_max=30*22+45*14=1290

 

 

2. Двойственная задача

Некое предприятие «КПО», использующее те же ресурсы что и  предприятие из предыдущей задачи, желает приобрести все эти ресурсы. Оно желает приобрести их по ценам y₁, y₂ и y₃ соответственно за единицу каждого из трёх ресурсов. Величины у₁, у₂, у₃ принято называть расчетными, или двойственными, оценками ресурсов. Из условий предыдущей задачи нам известны затраты всех 3-х ресурсов для производства для каждого из 4-х видов продукции (A), количество ресурсов на производстве (B) и прибыль от единицы каждой продукции (C):

    

 

Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 3 единицы ресурса первого вида, 4 единицы ресурса второго вида и 4 единицы третьего. В ценах у₁, у₂, у₃ наши затраты составят 3у₁ + 4у₂ + 4у₃, т.е. столько заплатит предприятие «КПО» за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первой продукции мы получили бы прибыль 30. Следовательно, мы можем согласиться с предложением предприятия «КПО» только в том случае, если он заплатит не меньше 30 :

3у₁ + 4у₂ + 4у₃ ³ 30.

Соответственные условия  должны выполняться и для продукции  других видов, т.е.

 

Но при продаже требуется  учитывать и интересы покупателя. Естественным желанием покупателя является снижение расходов. Так как предприятие  желает закупить весь объём имеющихся ресурсов, то его затраты при ценах y₁, y₂ и y₃ составят , где коэффициенты при y₁, y₂ и y₃ - количество имеющихся ресурсов. Таким образом:

→ min

Кроме того, так как  цены не могут быть отрицательными, то .

Решение полученной задачи легко найти с помощью второй основной теоремы двойственности, согласно которой для оптимальных решений х(х₁,х₂,х₃,x₄) и у(у₁,у₂,у₃) пары двойственных задач необходимо и достаточно выполнение условий:

x ₁ (3y₁ + 4y₂ + 4y₃ - 30) = 0  y₁ (3x₁ + 2x₂ + 6x₃          - 150) = 0

x ₂ (2y₁ + 2y₂ + 3y₃ - 11) = 0  y₂ (4x₁ + 2x₂ + 3x₃ + 5x₄ - 130) = 0

x ₃ (6y₁ + 3y₂  + 2y₃  - 45) = 0  y₃ (4x₁ + 3x₂ + 2x₃ + 4x₄ - 124) = 0         .

x ₄ (     + 5y₂ + 4y₃  - 6) = 0

Ранее (см. Задачу 1) было найдено, что в решении исходной  задачи х₁>0 и х₃>0. Поэтому

3y₁ + 4y₂ + 4y₃ - 30 = 0

6y₁ + 3y₂  + 2y₃  - 45 = 0

Учитывая, что 3-ой ресурс был избыточным, то, согласно теореме  двойственности, его двойственная оценка , получим систему:

3y₁ + 4y₂ - 30 = 0

6y₁ + 3y₂ - 45 = 0          откуда следует у₁ = 6, у₂ = 3.

 

Таким образом, получили двойственные оценки ресурсов: у₁ = 6, у₂ = 3, у₃ = 0

причем общая оценка всех ресурсов равна  150*6+130*3+124*0=1290

Решение содержится в  последней строке последней симплексной  таблицы исходной задачи.

Экономический смысл  двойственных оценок:

• двойственная оценка первого ресурса у₁=6 показывает, что добавление одной единицы первого ресурса обеспечит прирост максимальной прибыли в 6 единиц;
• двойственная оценка второго ресурса у₂=3 показывает, что добавление одной единицы второго ресурса обеспечит прирост прибыли в 3 единицы;
• оценка второй технологии Δ₂ = 7 показывает, что если произвести одну единицу продукции второго вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 7 единиц;
• оценка четвертой технологии  Δ₄ = 9 показывает, что если произвести одну единицу продукции четвертого вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 9 единиц.

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

При выполнении оптимальной  производственной программ Первый и  Второй  ресурсы используются полностью, то есть образуют “узкие места производства”. Будем заказывать их дополнительно. Пусть 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

 

Введем симплексные  множители 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₁ -3 = 0,  q₁ = 3

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

4. Анализ доходности  и риска финансовых операций

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

При проведении какой-либо финансовой операции возникает неопределенность и поэтому её результат невозможно предсказать заранее. Из этого можно сделать вывод, что финансовые операции рискованны, т.е. при их проведении возможен как прибыль, так и убыток.

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

Даны четыре финансовые операции Q₁, Q₂, Q₃, Q₄. Найти средние ожидаемые доходы M(Q_i) и риски r_i операций. Нанести точки (M(Q_i), r_i) на плоскость, найти финансовые операции, оптимальные по Парето. С помощью взвешивающей формулы (j (Q_i)= 2×M(Q_i) – r_i) найти лучшую и худшую операции.

Q1	2	6	8	14
	1/4	1/4	1/3	1/6
Q2	0	1	2	8
	1/3	1/3	1/6	1/6
Q3	2	3	4	10
	1/3	1/3	1/6	1/6
Q4	0	4	6	10
	1/5	1/5	1/5	2/5

Найдем M(Q_i) для каждой операции, показывающая средний ожидаемый доход, и - риск проведения данной операции.

M(Q₁)=2*1/4+6*1/4+8*1/3+14*1/6=7

M(Q₂)=0*1/3+1*1/3+2*1/6+8*1/6=2

M(Q₃)=2*1/3+3*1/3+4*1/6+10*1/6=4

M(Q₄)=0*1/5+4*1/5+6*1/5+10*2/5=6

 

D(Q_i)=M(Q_i²)-M²(Q_i)

D(Q₁)=64 – 49=15

D(Q₂)=11 2/3 – 4 =7 2/3

D(Q₃)=23 2/3 – 16=7 2/3

D(Q₄)=50 2/5 – 36=14 2/5

 

r₁=3,9

r₂=2,8

r₃=2,8

r₄=3,8

 

Теперь нанесём точки (M(Q_i), r_i) на плоскость.

Получили 4 точки. Чем  правее точка, тем более доходная операция, чем точка выше - тем  более она рисковая. Нас же интересует точка с максимальным доходом, но в то же время с минимальным  риском. Значит, нужно выбирать точку  правее и ниже. Точка (M(Q)’, r’) доминирует точку (M(Q),r) если M(Q)’=>M(Q) и r’<=r. В нашем случае 3-я операция доминирует 2-ю. Но 1-я, 3-я и 4-я операции несравнимы.

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

Для нахождения лучшей операции иногда применяют подходящую взвешивающую формулу, которая для пар (M(Q),r) дает одно число, по которому и определяют лучшую операцию. Например, пусть взвешивающая формула есть j (Q)= 2×M(Q) - r . Тогда получаем:

j (Q₁)=10,1 – max

j (Q₂)=1,2

j (Q₃)=5,2

j (Q₄)=8,2

Из расчётов видно, что 1-ая операция лучшая, а 2-ая худшая.

 

 

5. Распределение капитальных  вложений

Имеется производственное объединение, включающее в себя 4 предприятия. По плану в ближайшее время  должна проводится реконструкция этих 4-х предприятий. На реконструкцию  выделено 700 млн. руб. и суммы распределены между предприятиями кратно 100 млн. руб. После проведения реконструкции ожидается прирост прибыли от каждого предприятия в зависимости от вложенных в него капиталов. Эти данные известны и заданы таблицей:

 

xj	0	100	200	300	400	500	600	700
f1(x1)	0	42	58	71	80	89	95	100
f2(x2)	0	30	49	63	6	69	65	60
f3(x3)	0	22	37	49	59	68	76	82
f4(x4)	0	50	68	82	92	100	107	112