Учебное пособие 1260
.pdf
Рис. 8. Результаты решения распределительной задачи линейного программирования
19
ВАРИАНТЫ ЗАДАНИЯ № 1
На предприятии производятся n видов продукции, при этом используется оборудование m типов. Известны следующие данные о производственном процессе:
суточная производительность i-го оборудования по каждому j-му виду продукции ( ij ), т/сутки;
себестоимость производства продукции j-го вида на i-м оборудовании ( cij ) , руб./т;
фонды рабочего времени оборудования i-го вида ( ai ), сутки;
планируемый объём выпуска продукции j-го вида
( b j ), т;
m – количество строк, n – количество столбцов в матрицах ( ij ) и ( Сij ).
Требуется распределить выпуск продукции по оборудованию с целью минимизации общей себестоимости производства. План производства должен быть выполнен. Все виды оборудования должны быть задействованы в процессе производства. Производственные задания по видам оборудования должны иметь целочисленное выражение. Необходимо провести анализ решения и полученных результатов.
|
|
|
|
|
|
Вариант 1 |
|
|
|
|
|
3 |
7 4 |
3 |
|
1 |
2 |
4 |
3 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
ij 12 |
28 16 8 |
|
; |
cij |
4 |
5 |
3 |
8 |
; |
||
|
6 |
14 8 |
4 |
|
|
|
3 |
2 |
1 |
2 |
|
|
|
|
|
|
|||||||
|
(ai ) 320, 115, |
240 ; (b j ) 1320, 2324, 864, 984 . |
|||||||||
|
|
|
|
|
|
20 |
|
|
|
|
|
Вариант 2
|
|
2 |
4 |
6 |
|
|
|
|
1 |
2 |
3 |
|
|
|
|||
|
|
|
4 8 |
12 |
|
|
|
cij |
|
3 |
3 |
2 |
|
|
|
||
ij |
|
|
|
; |
|
|
|
; |
|
||||||||
|
|
|
24 |
48 |
72 |
|
|
|
|
|
2 |
5 |
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
6 |
9 |
|
|
|
|
|
1 |
2 |
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
(ai ) 260, 90, 146,169 ; (b j ) 3216, 2976, |
7056 . |
|||||||||||||
|
|
|
|
|
|
|
|
|
Вариант 3 |
|
|
|
|
|
|
|
|
|
|
16 |
56 |
24 |
|
32 |
|
|
|
|
|
|
3 |
2 |
4 |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
cij |
|
|
|
|
|
|
ij |
|
|
8 28 |
12 16 |
|
; |
|
|
1 5 6 |
||||||||
|
|
|
2 |
7 |
3 |
|
4 |
|
|
|
|
|
|
7 |
3 |
8 |
|
|
|
|
|
|
|
|
|
|
|
||||||||
(ai ) 94, 180, |
234 ; (b j ) 1344, 4424, 2664, |
1216 . |
|
||||||||||||||
|
|
|
|
|
|
|
|
|
Вариант 4 |
|
|
|
|
|
|
|
|
|
|
14 |
7 |
28 |
|
|
|
3 |
2 |
3 |
|
|
|
||||
|
|
|
28 14 |
56 |
|
|
cij |
|
4 |
1 |
2 |
|
|
|
|||
ij |
|
|
; |
|
|
|
; |
|
|||||||||
|
|
|
56 |
28 |
112 |
|
|
|
|
3 |
5 |
1 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
4 |
16 |
|
|
|
|
2 |
1 |
4 |
|
|
|
||
|
|
|
|
|
|
|
|
|
|
||||||||
(ai ) 72, 150, 97, |
84 ; |
(b j ) 2744, 2688, 1448 . |
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
Вариант 5 |
|
|
|
|
|
|
|
|
|
|
36 |
66 |
24 |
|
30 |
|
|
|
|
2 |
4 |
1 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ij |
|
|
6 11 |
4 5 |
|
; |
|
cij |
1 5 2 |
||||||||
|
|
|
18 |
33 |
12 |
|
15 |
|
|
|
|
|
|
2 |
4 |
1 |
|
|
|
|
|
|
|
|
|
|
|
||||||||
(ai ) 96, 360, |
410 ; (b j ) 3528, 1580, 5040, 1260 . |
|
|||||||||||||||
21
3
2 ;
3
7
6 ;
8
Вариант 6
|
|
|
10 |
4 |
22 |
|
|
|
|
|
|
|
|
|
5 |
1 |
|
2 |
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ij |
|
20 |
8 44 |
|
; |
|
|
|
|
|
|
cij |
|
3 2 3 |
|
; |
||||||||
|
|
|
|
5 |
2 |
11 |
|
|
|
|
|
|
|
|
|
|
2 |
1 |
|
4 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
40 |
16 |
88 |
|
|
|
|
|
|
|
|
|
|
1 |
6 |
|
3 |
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
(ai ) 192, 174, 136, |
153 ; |
(b j ) 7280, 864, 9856 . |
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
Вариант 7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
16 4 10 |
|
|
|
1 4 |
2 1 |
|
|
|
||||||||||||
|
ij |
|
18 |
96 24 60 |
; |
c |
ij |
|
|
4 3 |
2 3 |
|
; |
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
9 |
48 12 30 |
|
|
|
|
|
1 5 |
2 4 |
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
(ai ) 150, 151, 94 ; (b j ) 2448, 2016, 1152, 2340 . |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
Вариант 8 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
108 |
18 |
54 |
|
|
|
|
|
2 |
1 |
2 |
|
|
|
|
|
||||||
|
|
|
|
12 |
2 6 |
|
|
|
cij |
|
1 5 |
2 |
|
|
|
|
|
|
||||||
ij |
|
|
; |
|
|
|
|
; |
|
|
|
|
||||||||||||
|
|
|
|
54 |
9 |
27 |
|
|
|
|
|
|
1 |
6 |
3 |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
18 |
3 |
9 |
|
|
|
|
|
|
|
6 |
3 |
7 |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
(ai ) 162, 324, 96, 314 |
; (b j ) 6372, 2160, 6966 . |
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
Вариант 9 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
2 |
3 |
|
4 |
|
|
|
|
|
|
2 |
3 |
4 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ij |
|
|
28 |
8 12 16 |
|
; |
|
|
|
|
cij |
2 3 1 |
|
|||||||||||
|
|
|
|
14 |
4 |
6 |
|
8 |
|
|
|
|
|
|
|
|
2 |
4 |
6 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
(ai ) 220, 115, 240 ; |
(b j ) 2324, 384, 1320, 864 |
. |
|
|
|
|
|
|||||||||||||||||
22
6
3 ;
2
Вариант 10
|
|
28 |
14 |
7 |
|
|
|
1 |
3 |
2 |
|
|
|
||
|
|
|
56 |
28 |
14 |
|
|
cij |
|
3 |
2 |
1 |
|
|
|
ij |
|
|
|
; |
|
|
; |
|
|||||||
|
|
112 |
56 |
28 |
|
|
|
|
1 |
3 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
8 |
4 |
|
|
|
|
4 |
1 |
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
(ai ) 172, 150, 97, 241 ; |
(b j ) 14 448, 2744, 2688 |
. |
||||||||||
1. РЕШЕНИЕ ЗАДАЧ ДИНАМИЧЕСКОГО ПРОГРАММИРОВАНИЯ
Оптимизация решения о капиталовложениях в несколько объектов единовременно
Допустим, имеется возможность вложения средств С в группу из n предприятий на реконструкцию и модернизацию оборудования. Известен возможный прирост продукции на каждом предприятии в зависимости от выделенных ему
средств ri(x); i 1, n .
Необходимо таким образом распределить инвестиции С между предприятиями, чтобы общий прирост выпуска продукции на всех n предприятиях в сумме был максимальным.
Составим основное функциональное уравнение. Обозначим через f1 – максимально возможный прирост выпуска продукции на одном предприятии при различных значениях вкладываемых средств х. Каждому значению х отвечает определённый результат r1(x):
f1 |
( yn 1 ) max [ r1( x )], |
|
0 x yn 1 |
|
23 |
где yn-1 – допустимая сумма средств, которая может быть вложена в одно предприятие – это допустимое состояние процесса на начало первого шага вычислений.
На следующем шаге – оптимальный эффект от вложения средств в два предприятия получаем максимизируя объём прироста продукции на втором предприятии r2(x) плюс оптимальный результат, полученный на предыдущем шаге:
f2 ( yn 2 ) |
max [ r2 ( x ) f1( yn 2 x )], |
|
0 x yn 2 |
где yn-2 – средства, вкладываемые в два предприятия; х – средства, выделяемые второму предприятию;
(yn-2 – x) – средства, вкладываемые в первое предприятие.
В общем случае функциональное уравнение задачи, позволяющее максимизировать эффект, получаемый на i-м шаге, плюс оптимальное решение, полученное на предыдущем шаге, имеет вид:
fi ( yn i ) |
max [ ri ( x ) fi 1( yn i x )]. |
|
0 x yn i |
Задача. Составить оптимальный план распределения капиталовложений между четырьмя предприятиями (проектами) в размере С = 100 млн. ден. ед.
|
|
|
|
|
|
Таблица 1 |
Объём |
|
Прирост выпуска продукции ri(xi) в |
||||
капиталовложений |
|
|
зависимости от объёма |
|||
млн. ден. ед. |
|
капиталовложений, млн. ден. ед. |
||||
|
Проект |
|
Проект |
Проект |
Проект |
|
|
1 |
|
|
2 |
3 |
4 |
20 |
|
12 |
|
14 |
13 |
18 |
40 |
|
33 |
|
28 |
38 |
39 |
60 |
|
44 |
|
38 |
47 |
48 |
80 |
|
64 |
|
56 |
62 |
65 |
100 |
|
78 |
|
80 |
79 |
82 |
|
|
|
24 |
|
|
|
На первом этапе решения задачи динамического программирования, рассмотрим программу вложения средств в предприятие по шагам. На первом шаге максимизируем отдачу f1(C) от вложения средств x1 в одно (первое) предприятие:
f1( С ) max [ r1( x )],
0 x С
Таблица 2 Отдача от средств, вкладываемых в 1-ое предприятие
С \ х |
0 |
20 |
40 |
60 |
80 |
100 |
f1(C) |
x1 |
20 |
0 |
12 |
– |
– |
– |
– |
12 |
20 |
40 |
0 |
12 |
33 |
– |
– |
– |
33 |
40 |
60 |
0 |
12 |
33 |
44 |
– |
– |
44 |
60 |
80 |
0 |
12 |
33 |
44 |
64 |
– |
64 |
80 |
100 |
0 |
12 |
33 |
44 |
64 |
78 |
78 |
100 |
На втором шаге максимизируем отдачу f2(C) от вложения средств в два предприятия, из которыхx2 вкладываетсяво второе предприятие, с учётом результата, полученного на предыдущем шаге, при этом вложения в первое предприятие составят (С – х1):
f2 |
( С ) max [ r2 ( x ) f1( С x )], |
|
0 x С |
|
Таблица 3 |
Отдача от средств, вкладываемых во 2-ое предприятие и их остатков, вкладываемых в 1-ое предприятие
С \ х |
0 |
20 |
40 |
60 |
80 |
100 |
f2(C) |
x2 |
20 |
0+12 |
14+0 |
– |
– |
– |
– |
14 |
20 |
40 |
0+33 |
14+12 |
28+0 |
– |
– |
– |
33 |
0 |
60 |
0+44 |
14+33 |
28+12 |
38+0 |
– |
– |
47 |
20 |
80 |
0+64 |
14+44 |
28+33 |
38+12 |
56+0 |
– |
64 |
0 |
100 |
0+78 |
14+64 |
28+44 |
38+33 |
56+12 |
80+0 |
80 |
100 |
|
|
|
|
25 |
|
|
|
|
На третьем шаге максимизируем отдачу вложения средств в три предприятия, из вкладываетсяв третье предприятие, с учётом результата, полученного на предыдущем шаге:
f3 |
( С ) max [ r3 ( x ) f2 ( С x )], |
|
0 x С |
|
Таблица 4 |
Отдача от средств, вкладываемых в 3-е предприятие и их остатков (С – х2), вкладываемых в 1-ое и 2-ое предприятия
С \ х |
0 |
20 |
|
40 |
60 |
80 |
100 |
f3(C) |
x3 |
|
|
20 |
0+14 |
13+0 |
|
– |
– |
– |
– |
14 |
|
0 |
|
40 |
0+33 |
13+14 |
|
38+0 |
– |
– |
– |
38 |
|
40 |
|
60 |
0+47 |
13+33 |
|
38+14 |
47+0 |
– |
– |
52 |
|
40 |
|
80 |
0+64 |
13+48 |
|
38+33 |
47+14 |
64+0 |
– |
71 |
|
40 |
|
100 |
0+80 |
13+64 |
|
38+47 |
47+33 |
64+14 |
79+0 |
85 |
|
40 |
|
|
На четвёртом |
шаге максимизируем отдачу |
f4(C) от |
||||||||
вложения средств в четыре предприятия, из которыхx4 вкладываетсяв четвёртое предприятие, с учётом результата, полученного на предыдущем шаге:
f4 |
( С ) max [ r4 ( x ) f3 ( С x )], |
|
0 x С |
Таблица 5 Отдача от средств, вкладываемых в 4-ое предприятие и их остатков (С – х3), вкладываемых в 1-ое, 2-ое и 3-е предприятия
С \ х |
0 |
20 |
40 |
60 |
80 |
100 |
f4(C) |
x4 |
20 |
0+14 |
18+0 |
– |
– |
– |
– |
18 |
20 |
40 |
0+38 |
18+14 |
39+0 |
– |
– |
– |
39 |
40 |
60 |
0+52 |
18+38 |
39+14 |
48+0 |
– |
– |
56 |
20 |
80 |
0+71 |
18+52 |
39+38 |
48+14 |
65+0 |
– |
77 |
40 |
100 |
0+85 |
18+71 |
39+52 |
48+38 |
65+14 |
82+0 |
91 |
40 |
На втором этапе решения задачи динамического программирования, проанализируем таблицы в обратном
26
порядке. Максимальный прирост отдачи от вложения средств в размере 100 млн. ден. ед. на четырёх предприятиях составит 91 млн. ден. ед. (табл. 5). При этом в 4-ое предприятие следует вложить х4 = 40 млн. ден. ед. Остаток средств 100 – 40 = 60 млн. ден. ед. вкладывают в развитие 1-го, 2-го и 3-го предприятий. Из табл. 4 видно, что из этой суммы в 3-е предприятие следует вложить х3 = 40 млн. ден. ед. Остаток средств - 60 – 40 = 20 млн. ден. ед. вкладывают в развитие 1-го и 2-го предприятий. Из табл. 3 видно, что из этой суммы во 2- е предприятие следует вложить всю оставшуюся сумму х2 = 20 млн. ден. ед. Вложение средств в 1-ое предприятие нерентабельно.
f = 91, x1 = 0, x2 = 20, x3 = 40, x4 = 40.
ВАРИАНТЫ К ЗАДАНИЮ №2
Вариант 1
Прирост выпуска продукции на предприятиях, ri(x)
Средства с, |
|
|
|
|
тыс. руб. |
r1(x) |
r2(x) |
r3(x) |
r4(x) |
200 |
95 |
114 |
164 |
133 |
400 |
183 |
191 |
321 |
273 |
600 |
241 |
302 |
402 |
442 |
800 |
383 |
442 |
571 |
692 |
1000 |
501 |
591 |
701 |
733 |
27
Вариант 2
Прирост выпуска продукции на предприятиях, ri(x)
Средства с, |
|
|
|
|
тыс. руб. |
r1(x) |
r2(x) |
r3(x) |
r4(x) |
200 |
97 |
116 |
135 |
126 |
400 |
172 |
343 |
283 |
354 |
600 |
292 |
463 |
374 |
403 |
800 |
382 |
533 |
492 |
542 |
1000 |
472 |
752 |
612 |
734 |
Вариант 3
Прирост выпуска продукции на предприятиях, ri(x)
Средства с, |
|
|
|
|
тыс. руб. |
r1(x) |
r2(x) |
r3(x) |
r4(x) |
200 |
73 |
98 |
172 |
168 |
400 |
297 |
194 |
274 |
302 |
600 |
371 |
284 |
373 |
423 |
800 |
411 |
373 |
483 |
651 |
1000 |
593 |
463 |
661 |
815 |
Вариант 4
Прирост выпуска продукции на предприятиях, ri(x)
Средства с, |
|
|
|
|
тыс. руб. |
r1(x) |
r2(x) |
r3(x) |
r4(x) |
200 |
94 |
124 |
118 |
144 |
400 |
205 |
252 |
206 |
233 |
600 |
352 |
341 |
322 |
404 |
800 |
443 |
464 |
482 |
503 |
1000 |
574 |
574 |
613 |
583 |
|
|
28 |
|
|