- •Кафедра высшей математики
- •Экономико-математические методы и модели
- •Хабаровск 2002
- •2.3. Варианты заданий к задаче № 2
- •Задание: составить модель задачи и на примере ее решения проиллюстрировать свойства двойственных оценок.
- •Рассмотреть задачу по определению оптимального плана выпуска продукции, максимизирующего выручку при известных нормах расхода ресурсов, объемах ресурсов и ценах реализации продукции.
- •Вариант 1
- •Вариант 2
- •Вариант 3
- •Вариант 4
- •Вариант 5
- •Вариант 6
- •Вариант 7
- •Вариант 9
- •Вариант 10
- •4. Корреляционно–регрессионный анализ
- •4.1 Краткие теоретические сведения
- •4.2. Задача анализа матрицы парных коэффициентов корреляции
- •4.3. Уравнение линейной регрессии
- •4.4. Оценка точности уравнения регрессии
- •Вариант 1
- •Вариант 2
- •Вариант 3
- •Вариант 6
- •Вариант 7
- •Вариант 8
- •Вариант 9
- •Вариант 10
- •Задание №7
- •Библиографический список
- •Задание №7
- •Валентина Никитична Захарова
- •Экономико-математические методы и модели
54
Вариант 9
55
Вариант 10
56
57
Задание №5
5. Задача оптимального размещения производства 5.1. Краткие теоретические сведения
Эта задача относится к (задаче) производству одного или нескольких взаимозаменяемых видов продукции, но в условиях, когда наличные мощности поставщиков недостаточны для удовлетворения спроса потребителей. Это требует ввода новых мощностей за счет капитального строительства и реконструкции.
Обычно существует несколько возможных вариантов строительства и реконструкции, отличающихся по производственной мощности, местоположению, уровню капитальных затрат и других показателей.
К задаче оптимального закрепления потребителей за поставщиками добавляется задача оптимального прироста мощностей. Решение данной задачи должно обеспечить определение оптимальных вариантов размещения производства и перевозок продукции, при которых достигается минимум суммарных текущих затрат на производство продукции, ее транспортировку и приведенных капитальных вложений (оптимальных инвестиционных вложений) в создание новых мощностей или расширение действующих. Математическая модель задачи:
m |
n |
(Ci Eki |
Cij) xij min |
|||||||
i 1 j 1 |
||||||||||
|
|
|
|
|
|
|
|
|||
n |
|
|
|
|
|
|
|
|
|
|
xij |
Ai ,(i |
1, m), |
||||||||
|
||||||||||
j 1 |
|
|
|
|
|
|
|
|
||
m |
|
|
|
|
|
|
|
|
|
|
xij |
B j,(i |
1, n), |
||||||||
i 1 |
||||||||||
|
|
|
|
|
|
|
|
|
||
xij |
0, i |
1, m , |
j |
1, n , |
где Е - нормативный коэффициент эффективности капитальных вложений, ki- удельные капитальные вложения в i-ой отрасли, Ai -мощность i-го предприятия-поставщика, Вj - спрос j-го потребителя, хij - искомый объем перевозок продукции от i-го поставщика j-му потребителю.
Первая группа ограничений показывает, что действующих и добавленных мощностей больше, чем необходимо, вторая - что спрос потребителей готовой продукции должен быть удовлетворен.
Эта модель представляет собой открытую транспортную задачу, которая приводится к закрытой введением условного потребителя. Поставщиков, которые в оптимальном плане "прикрепились" к условному потребителю, использовать нецелесообразно. Если это относится к проектируемому предприятию, то соответствующий вариант отбрасывается, как нерациональный.
Если же к условному потребителю "прикрепилось" какое-либо
58
действующее предприятие, то следует рассмотреть вопрос о целесообразности его дальнейшей эксплуатации. Как правило, в оптимальный план попадают действующие предприятия, т.к. приведенные затраты на единицу продукции на этих предприятиях ниже, чем на проектируемых, где к затратам на производство продукции добавляются капитальные затраты.
Основная трудность при решении такого рода задач заключается в возможности получения нецелочисленных решений, когда в оптимальном плане часть мощности какого-либо поставщика относится на действительных, а часть на условного. В таких случаях приходится останавливаться на приближенных решениях.
5.2.Пример решения задачи
Рассмотрим решение задачи на условном примере. Пусть три
действующие |
предприятия |
А1, |
А2, |
А3 |
с |
мощностями |
аi (200,150,170), обеспечивают |
однородной |
продукцией |
четырех |
|||
потребителей со спросом b j |
(180,230,120,140). |
|
|
|
||
Недостающий прирост мощностей ( |
аi 520 |
b j |
670 ) планируется |
обеспечить за счет реконструкции первого предприятия (пристройки к нему нового цеха) и строительства нового предприятия А4. Себестоимость продукции: на действующих предприятиях Сi (5,6,3), после
реконструкции С1рек=4; на предприятие А4: С4=4. Удельные капитальные затраты на реконструкцию k1=6, на строительство A4: k4=8.
Нормативный коэффициент эффективности капитальных вложений, связанный со строительством и реконструкцией Ен=0,15.
Известна матрица транспортных затрат на доставку единицы продукции:
|
|
В1 |
В2 |
В3 |
В4 |
|
|
А1 |
4 |
3 |
7 |
2 |
|
С |
А2 |
5 |
1 |
3 |
4 |
|
А3 |
3 |
3 |
2 |
3 |
||
|
||||||
|
А4 |
6 |
4 |
5 |
8 |
Найти оптимальный план перевозок и прироста мощностей, обеспечивающий потребность продукции и минимизирующий суммарные издержки. Решение: аi 520. b j 720.
Каждому проектируемому варианту прироста мощности выделяем отдельную строку и даем недостающую мощность 150. Вычисляем затраты на производство и доставку продукции (ci+cij) для действующих
59
предприятий и приведенные затраты сi cij E ki для вариантов прироста
мощностей.
Первоначальный опорный план находим по методу минимального элемента. Первой заполняем клетку (3.3) с наименьшим тарифом. Поставку х33 определяем по правилу х33=min (a3, b3)=min (170,120)=120 . Следующими заполняются клетки в порядке возрастания тарифов с учетом предыдущих поставок х31=min (170-120; 150)=50 и т.д.
Получим таблицу
|
|
|
План X1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
180 |
230 |
120 |
140 |
150 |
|
A1 |
200 |
9 |
8 |
12 |
7 |
0 |
u1=0 |
|
|
130 |
70 |
4 |
0 |
0 |
|
A2 |
150 |
11 |
7 |
9 |
10 |
0 |
u2=-1 |
|
|
3 |
150 |
2 |
4 |
1 |
|
A3 |
170 |
6 |
6 |
5 |
6 |
0 |
u3=-3 |
|
|
50 |
1 |
120 |
2 |
3 |
|
A1 |
150 |
8,9 |
7,9 |
11,9 |
6,9 |
0 |
u4=- |
|
|
0 |
10 |
4 |
140 |
0,1 |
0,1 |
A4 |
150 |
11,2 |
9,2 |
10,2 |
13,2 |
0 |
u5=0 |
|
|
2,2 |
1,2 |
2,2 |
6,2 |
150 |
|
|
|
v1=9 |
v2=8 |
v3=8 |
v4=7 |
v5=0 |
|
Вычисляем суммарные издержки этого плана: z1=4725.
Задачу решаем методом потенциалов. Условия оптимальности по
теореме потенциалов: |
|
|
||
1). cij |
ui |
v j, для занятых клеток. |
|
|
2). cij |
ui |
v j , для свободных клеток. |
|
|
Обозначим разность между cij и ( ui v j ) через |
Eij , Eij cij (ui |
v j ) . |
||
Eij называются характеристиками свободных клеток |
( i, j ). Eij показывают, |
|||
на сколько изменится значение целевой функции z, если в клетку |
(i, j) |
переместить единицу груза.
Из 2-го условия теоремы о потенциалах следует, что план будет оптимальным, если все характеристики свободных клеток будут неотрицательны.
Число занятых клеток в таблице должно быть m+n–1=10–1=9. В нашем случае их восемь. Такой план называется вырожденным. Добавляем нулевую поставку в любую свободную клетку, но так, чтобы не замкнуть контур из занятых клеток. Положим, например, х15=0.
60
Потенциалы строк и столбцов вычислим по занятым клеткам из 1-го условия теоремы о потенциалах. В нашем примере потенциалов десять, а число уравнений, из которых они определяются, ( сij uij v j ) – девять.
Такая система имеет одну степень свободы, поэтому один из потенциалов задаем произвольно, например u1=0, а остальные определяются единственным образом.
Все характеристики свободных клеток в плане х1 неотрицательны, поэтому план оптимальный, но не единственный, т.к. Е41=0.
В оптимальном плане вариант А4 прикрепился к фиктивному потребителю, поэтому оптимальным вариантом прироста мощностей является реконструкция предприятия А1. Полученное решение целочисленное. При этом Zmin=4725.
5.3. Варианты заданий для выполнения задачи №5
Мощности трех действующих предприятий в пунктах А1, А2, А3 составляют ai (300;500;450) ед. однородной продукции. Перспективная
потребность в этой продукции четырех потребителей в пунктах В1, В2, В3,
В4 равна b j (520;380;240;360).
Увеличение выпуска продукции возможно за счет строительства новых предприятий в пунктах А4 и А5 и реконструкции действующих. Известны: сi -затраты на производство единицы продукции;
сi рек -затраты на производство после реконструкции;
ki -капитальные затраты на единицу готовой продукции, связанные с
реконструкцией и строительством;
cij -затраты на доставку единицы продукции от i –го предприятия до j –го
потребителя.
Ен=0,15-нормативный коэффициент эффективности, связанный со строительством и реконструкцией.
Определить оптимальный план строительства и реконструкции, обеспечивающий минимальные суммарные издержки на производство, доставку и прирост производственных мощностей.
|
|
|
|
B1 |
B2 |
B3 |
B4 |
|
|
|
|
A1 6 |
|
|
|
A1 |
4 |
A1 |
4 |
5 |
8 |
3 |
|
A |
4 |
А 5 |
|
A |
6 |
A |
2 |
10 4 |
6 |
||
2 |
|
1 |
|
|
2 |
2 |
|
|
|
|
|
сi A3 |
5 |
ci рек А2 |
3 |
ki |
A3 4 |
cij A3 |
7 |
5 |
5 |
4 |
|
A4 4 |
А3 |
4 |
|
A4 5 |
A4 3 5 |
6 |
7 |
||||
A5 5 |
|
|
|
A5 |
5 |
A5 5 |
4 |
8 |
3 |
61
Для выбора своего варианта пользуйтесь следующими правилами: Вариант 1. Реконструкция А1 и строительство А4. Вариант 2. Реконструкция А1 и строительство А5. Вариант 3. Реконструкция А2 и строительство А4. Вариант 4. Реконструкция А2 и строительство А5. Вариант 5. Реконструкция А3 и строительство А4. Вариант 6. Реконструкция А3 и строительство А5. Вариант 7. Реконструкция А1 и строительство А2. Вариант 8. Реконструкция А1 и строительство А3. Вариант 9. Реконструкция А2 и строительство А3. Вариант 10. Реконструкция А4 и строительство А5.
Задание №6
6.Двухэтапная производственно-транспортная задача
6.1Краткие теоретические сведения
Вотличие от классической транспортной задачи в двухэтапной задаче потребитель получает продукцию не от поставщика, а через промежуточное звено, например со склада.
Рассмотрим двухэтапную задачу: поставщик – склад - потребитель. Пусть m поставщиков однородной продукции с мощностями а1, a2,...,am
направляют ее p складам с пропускными способностями d1, d2,...,d p ,
которые, в свою очередь, поставляют эту продукцию потребителям со спросом b1,b2,...,bn. Известны издержки cik и сkj по доставке ед. продукции
от |
|
i –го поставщика на k –й склад и с k –го склада j –му потребителю |
|||||
|
|
|
|
|
|
|
|
i |
1, m; j 1,n;k 1, p . Найти оптимальный план перевозок и прикрепление |
поставщиков к складам, складов к потребителям, при котором суммарные издержки будут минимальными. Обычно в таких задачах выполняется
условие баланса: аi |
b j |
dk , т. е. количество груза, отправляемое |
i |
i |
k |
поставщиками равно суммарной потребности, а емкость складов превышает эту величину.
В случае |
аij |
b j |
dk задачу можно решать по частям: сначала |
||||
найти оптимальный |
план |
прикрепления |
складов |
к поставщикам |
|||
продукции, |
затем складов к |
потребителям. |
Если |
аi |
b j |
dk , то |
решение задачи по частям может привести к несогласованности планов оптимизации первого и второго этапов.
В этом случае задача решается одновременно в одной таблице.
62
Математическая модель задачи
z |
|
|
|
|
cik |
ckj xikj |
|
min , |
||||||||||
|
i |
k |
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1. |
|
|
xikj |
|
ai |
i |
1, m , |
|
|
|
||||||||
|
j |
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
2. |
|
|
xikj |
|
b j |
j |
|
|
1, n , |
|
|
|
||||||
|
i |
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3. |
|
|
xikj |
|
dk |
(k |
|
|
|
1, p) , |
|
|
|
|||||
|
i |
j |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
4. |
xikj |
0, |
i |
1,m , |
j |
|
1,n , k |
1, p . |
1-я группа ограничений показывает, что вся продукция вывозится с предприятий на склады, 2-я – что спрос потребителей должен быть удовлетворен, 3-я – что пропускная способность складов превышает суммарную мощность поставщиков и суммарный спрос потребителей. Такая задача решается методом фиктивной диагонали.
6.2.Пример решения задачи
Покажем реализацию этого метода на условном примере. Пусть предприятие имеет три цеха по производству продукции и два склада, где хранится изготовленная продукция перед отправкой ее потребителю. Со складов продукция доставляется трем потребителям. Известны мощности цехов по производству продукции ai 240,260,300 , пропускные
способности складов dk 400,600 , потребности потребителей в продукции
b j |
(270;330;200) , стоимость перевозки |
единицы |
груза с цеха на склад |
|||||
|
3 |
4 |
|
|
4 |
3 |
5 |
|
cik |
5 |
6 |
и со склада до потребителя |
ckj |
. Прямые поставки |
|||
|
2 |
4 |
|
|
6 |
3 |
4 |
|
|
|
|
|
|
|
|
продукции из цеха потребителю запрещены, потребитель получает готовую продукцию со складов. Определить оптимальный план перевозок, минимизирующий суммарные затраты. Склады на первом этапе являются потребителями продукции, на втором – поставщиками, поэтому им в таблице отводятся столбцы как потребителям и строки как поставщикам.
Так как |
потребители получают продукцию со складов, |
запретим прямые |
||||
поставки тарифами M |
, что обеспечивает условие оптимальности для |
|||||
клеток |
с |
cij |
M , |
так |
как для этих клеток |
характеристики |
ij cij |
ki |
v j |
M |
ki v j |
0 на всех этапах решения. |
|
63
Перевозки со склада на склад также запрещены, они блокируются запретительными тарифами М. Разрешается поставка склада самому себе, что означает размер неиспользованной мощности склада.
Заполним по методу минимального элемента сначала блок таблицы, в котором отражаются перевозки продукции со складов потребителям, затем фиктивную диагональ, затем перевозки от поставщиков на склады. Получим следующую таблицу.
План х1
|
|
d1=400 |
|
d2=600 |
|
b1=270 |
|
b2=330 |
|
b3=200 |
u1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
а1 |
240 |
0 |
3 |
240 |
4 |
|
M |
|
|
M |
M |
4 |
|
|
|
|
|
|
|
|
|
|
|
||
а2 |
260 |
100 |
5 |
160 |
6 |
|
M |
|
|
M |
M |
6 |
|
|
|
|
|
|
|
|
|
|
|
||
а3 |
300 |
300 |
2 |
1 |
4 |
|
M |
|
|
M |
M |
3 |
|
|
|
|
|
|
|
|
|
|
|
||
d1 |
400 |
|
0 |
|
M |
+ |
4 |
- |
3 |
5 |
-2 |
|
|
|
3 |
|
|
|
70 |
|
|
330 |
|
3 |
|
d2 |
600 |
|
M |
|
0 |
- |
6 |
|
+ |
3 |
4 |
0 |
|
|
|
|
|||||||||
|
|
|
|
200 |
|
200 |
|
-2 |
|
|
200 |
|
|
v j |
-1 |
|
0 |
|
6 |
|
5 |
|
4 |
|
Для этого плана общие издержки состовят: Z1=6290. Число занятых клеток в таблице m+n-1=5+5-1=9. Далее решаем задачу методом потенциалов.
Рассчитав потенциалы и характеристики для этого плана по аналогии с предыдущим, видим, что полученный план х1 неоптимальный, так как E54 2 . Строим для клетки (5,4) контур (5,4)-(5,3)-(4,3)-(4,4)-(5,4) и
перемешаем по нему поставку min(200,300) = 200. Получим план х2. При
этом z уменьшится на величину z E54 |
2 200 400 , в соответствии |
с экономическим смыслом характеристики |
|
План х2 оптимальный, так как все характеристики свободных клеток
неотрицательны, и не единственный, Е11 0 . zmin 6290 |
400 5890. |
Поставка в фиктивную диагональ х52=200 |
означает размер |
неиспользованной мощности второго склада. |
|
64
План х2
|
400 |
600 |
270 |
330 |
200 |
ui |
240 |
3 |
4 |
М |
М |
М |
4 |
|
0 |
240 |
|
|
|
|
260 |
5 |
6 |
М |
М |
М |
6 |
|
100 |
160 |
|
|
|
|
300 |
2 |
4 |
М |
М |
М |
3 |
|
300 |
1 |
|
|
|
|
400 |
0 |
|
4 |
3 |
5 |
0 |
|
1 |
М |
270 |
130 |
1 |
|
600 |
М |
0 |
6 |
3 |
4 |
0 |
|
|
200 |
2 |
200 |
200 |
|
v j |
-1 |
0 |
4 |
3 |
4 |
|
|
|
|
|
|
|
6.3.Варианты для выполнения задания №6
Условия заданий те же, что и в рассмотренном примере.
Номер |
Мощности цехов ( ai ) |
Пропускная |
Потребность в |
||||||||
вариан- |
|
тыс. шт |
|
|
способность |
продукции ( b j ) |
|||||
тов |
|
|
|
|
склада ( dk ). |
|
тыс. шт |
|
|||
|
а1 |
а2 |
|
а3 |
1 |
|
|
2 |
b1 |
b2 |
b3 |
1 |
260 |
240 |
300 |
500 |
|
|
500 |
200 |
270 |
330 |
|
2 |
260 |
320 |
180 |
500 |
|
|
400 |
260 |
250 |
250 |
|
3 |
170 |
520 |
130 |
600 |
|
|
500 |
300 |
200 |
320 |
|
4 |
155 |
235 |
190 |
350 |
|
|
350 |
150 |
170 |
260 |
|
5 |
120 |
305 |
115 |
270 |
|
|
280 |
210 |
130 |
200 |
|
6 |
140 |
180 |
230 |
350 |
|
|
300 |
150 |
200 |
200 |
|
7 |
300 |
240 |
560 |
600 |
|
|
650 |
250 |
500 |
350 |
|
8 |
360 |
250 |
440 |
600 |
|
|
600 |
250 |
450 |
350 |
|
9 |
180 |
350 |
180 |
350 |
|
|
500 |
230 |
230 |
250 |
|
10 |
230 |
150 |
160 |
320 |
|
|
320 |
160 |
180 |
200 |
|
|
|
|
5 |
4 |
|
6 |
5 |
7 |
|
|
|
|
|
cik |
4 |
5 |
ckj |
|
|
|
|||
|
|
3 |
8 |
4 |
|
|
|
||||
|
|
|
3 |
3 |
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
Прямые поставки продукции из цехов потребителям запрещены.