2 Двойственная задача
Для задачи, приведенной в задании 1:
1) составить двойственную задачу;
2) привести оптимальный план двойственной задачи, вычислить значение целевой функции;
3) сделать вывод о найденном решении прямой задачи;
4) провести двойственный анализ, применив вторую и третью теоремы двойственности.
Составим задачу, двойственную данной:
Система ограничений:
Ее решение:
y1=3/4, y2=31/4, y3=0, y4=0, y5=0.
F = 1093.
Проверка:
Значения целевых функций прямой и двойственной задачи совпадают.
По второй теореме двойственности следует:
Так как y1 = 3/4 > 0, значит данный ресурс будет использован полностью.
Так как y2 = 31/4 > 0, значит данный ресурс будет использован полностью.
Так как y3 = 0, значит данный ресурс избыточен.
По третьей теореме двойственности:
При изменении первого ресурса (Т1 = 238) на единицу, значение целевой функции изменяется на Y1 = 3/4.
При изменении второго ресурса (Т2 = 118) на единицу, значение целевой функции изменяется на Y2 = 31/4.
При изменении третьего ресурса (Т3 = 123) на единицу, значение целевой функции не изменится.
3 Задача о распределении капиталовложений динамического программирования
Решить задачу о распределении капиталовложений динамического программирования (1 вариант).
Для реконструкции и модернизации производства на n предприятиях выделены денежные средства с. По каждому из n предприятий известен возможный прирост gi(x) (i = 1..n) выпуска продукции в зависимости от выделенной ему суммы x (0 ≤ x ≤ c). Требуется:
распределить средства с между предприятиями так, чтобы суммарный прирост выпуска продукции на всех n предприятиях достиг максимальной величины fn(c) (этот основной результат получить для с=100 млн. руб. и n=4);
используя выполненное решение основной задачи, найти оптимальное распределение:
100 млн. руб. между тремя предприятиями;
80 млн. руб. между тремя предприятиями.
Исходные данные представлены в таблице 3.
Таблица 3
|
Предприятия |
|||
№1 |
№2 |
№3 |
№4 |
|
Z1(u1) |
Z2(u1) |
Z3(u1) |
Z4(u1) |
|
20 |
10 |
12 |
11 |
16 |
40 |
31 |
26 |
36 |
37 |
60 |
42 |
36 |
45 |
46 |
80 |
62 |
54 |
60 |
63 |
100 |
76 |
78 |
77 |
80 |
Пошаговое решение представлено в таблицах 4-7.
Таблица 4
X3 |
U4 |
Z4 |
F4 |
0 |
0 |
0 |
0 |
20 |
20 |
13 |
13 |
40 |
40 |
27 |
27 |
60 |
60 |
44 |
44 |
80 |
80 |
69 |
69 |
100 |
100 |
73 |
73 |
Таблица 5
X2 |
U3 |
X3 |
Z3 |
F4 |
Z3+F4 |
F3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
20 |
0 |
20 |
0 |
13 |
13 |
- |
20 |
0 |
16 |
0 |
16 |
16 |
|
40 |
0 |
40 |
0 |
27 |
27 |
- |
20 |
20 |
16 |
13 |
29 |
- |
|
40 |
0 |
32 |
0 |
32 |
32 |
|
60 |
0 |
60 |
0 |
44 |
44 |
- |
20 |
40 |
16 |
27 |
43 |
- |
|
40 |
20 |
32 |
13 |
45 |
45 |
|
60 |
0 |
40 |
0 |
40 |
- |
|
80 |
0 |
80 |
0 |
69 |
69 |
69 |
20 |
60 |
16 |
44 |
60 |
- |
|
40 |
40 |
32 |
27 |
59 |
- |
|
60 |
20 |
40 |
13 |
53 |
- |
|
80 |
0 |
57 |
0 |
57 |
- |
|
100 |
0 |
100 |
0 |
73 |
73 |
- |
20 |
80 |
16 |
69 |
85 |
85 |
|
40 |
60 |
32 |
44 |
76 |
- |
|
60 |
40 |
40 |
27 |
67 |
- |
|
80 |
20 |
57 |
13 |
70 |
- |
|
100 |
0 |
70 |
0 |
70 |
- |
Таблица 6
X1 |
U2 |
X2 |
Z2 |
F3 |
Z2+F3 |
F2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
20 |
0 |
20 |
0 |
16 |
16 |
16 |
20 |
0 |
11 |
0 |
11 |
- |
|
40 |
0 |
40 |
0 |
32 |
32 |
32 |
20 |
20 |
11 |
16 |
27 |
- |
|
40 |
0 |
19 |
0 |
19 |
- |
|
60 |
0 |
60 |
0 |
45 |
45 |
45 |
20 |
40 |
11 |
32 |
43 |
- |
|
40 |
20 |
19 |
16 |
35 |
- |
|
60 |
0 |
30 |
0 |
30 |
- |
|
80 |
0 |
80 |
0 |
69 |
69 |
69 |
20 |
60 |
11 |
45 |
56 |
- |
|
40 |
40 |
19 |
32 |
51 |
- |
|
60 |
20 |
30 |
16 |
46 |
- |
|
80 |
0 |
44 |
0 |
44 |
- |
|
100 |
0 |
100 |
0 |
85 |
85 |
85 |
20 |
80 |
11 |
69 |
80 |
- |
|
40 |
60 |
19 |
45 |
64 |
- |
|
60 |
40 |
30 |
32 |
62 |
- |
|
80 |
20 |
44 |
16 |
60 |
- |
|
100 |
0 |
59 |
0 |
59 |
- |
Таблица 7
X0 |
U1 |
X1 |
Z1 |
F2 |
Z1+F2 |
F1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
20 |
0 |
20 |
0 |
16 |
16 |
16 |
20 |
0 |
9 |
0 |
9 |
- |
|
40 |
0 |
40 |
0 |
32 |
32 |
32 |
20 |
20 |
9 |
16 |
25 |
- |
|
40 |
0 |
18 |
0 |
18 |
- |
|
60 |
0 |
60 |
0 |
45 |
45 |
45 |
20 |
40 |
9 |
32 |
41 |
- |
|
40 |
20 |
18 |
16 |
34 |
- |
|
60 |
0 |
24 |
0 |
24 |
- |
|
80 |
0 |
80 |
0 |
69 |
69 |
69 |
20 |
60 |
9 |
45 |
54 |
- |
|
40 |
40 |
18 |
32 |
50 |
- |
|
60 |
20 |
24 |
16 |
40 |
- |
|
80 |
0 |
38 |
0 |
38 |
- |
|
100 |
0 |
100 |
0 |
85 |
85 |
85 |
20 |
80 |
9 |
69 |
78 |
- |
|
40 |
60 |
18 |
45 |
63 |
- |
|
60 |
40 |
24 |
32 |
56 |
- |
|
80 |
20 |
38 |
16 |
54 |
- |
|
100 |
0 |
50 |
0 |
50 |
- |
Оптимальный план распределения кредита - 100 млн. 4 предприятия:
U1* = 0; X1 = 100;
U2* = 0; X2 = 100;
U3* = 20; X3 = 80;
U4* = 80.
При кредите в 100 млн. денежных единиц на три предприятия:
U2* = 0; X1 = 100;
U3* = 20; X2 = 80;
U4* = 80.
При кредите в 80 млн. денежных единиц на три предприятия:
U2* = 0; X1 = 80;
U3* =0; X2 = 80;
U4* = 80.