Москвин Б.В. Теория принятия решений
Подождите немного. Документ загружается.
371
30 x
1
+ 20 x
2
→ max
0.1x
1
+ 0.4x
2
≤ 28
0.3x
1
+ 0.1x
2
≤ 18
x
1
,x
2
≥. 0,
или, производя замену x
1
= 0.1x
1
; x
2
= 0.1x
2
, получаем
300x
1
+ 200x
2
→ max
1x
1
+ 4x
2
≤ 28
3x
1
+ 1x
2
≤ 18
x
1
,x
2
≥ 0.
Аналогично, задача планирования выпуска продукции 2-го
цеха имеет вид
200x
3
+ 300x
4
→ max
1x
3
+ 3x
4
≤ 21
1x
3
+ 1x
4
≤ 9
2x
3
+ 1x
4
≤ 14
x
3
,x
4
≥ 0.
Решая данные задачи тем или иным методом, можно опре-
делить оптимальный выпуск продукции каждым цехом. Однако
эти решения в совокупности должны удовлетворять ограничени-
ям по использованию электрической энергии
0.1x
1
+ 0.1x
2
+ 0.1x
3
+ 0.1x
4
≤ 16,
или с учетом замены переменных
1x
1
+ 1x
2
+ 1x
3
+ 1x
4
≤ 16.
В целом задача принятия решения (с учетом того, что мож-
но изменить масштаб изменения целевой функции) имеет вид
3x
1
+ 2x
2
+ 2x
3
+ 3x
4
→ max
1x
1
+ 1x
2
+ 1x
3
+ 1x
4
≤ 16
1x
1
+ 4x
2
≤ 28
3x
1
+ 1x
2
≤ 18
1x
3
+ 3x
4
≤ 21
1x
3
+ 1x
4
≤ 9
2x
3
+ 1x
4
≤ 14
x
1
,x
2
x
3
,x
4
≥ 0.
Такая задача является задачей линейного программирова-
ния вида
f(x) = c
т
x → max
A x ≤ b
x ≥ 0
с блочно-диагональной матрицей условий A
372
║3 2 2 3 ║ x → max
1 1 1 1 16
1 4 0 0 x
1
28
3 1 0 0 x
2
18
A x = 0 0 1 3
×
x
3
≤
21
0 0 1 1 x
4
9
0 0 2 1 14
x = ║ x
1
x
2
x
3
x
4
║ ≥ 0.
Проведем ее решение на основе декомпозиционного алго-
ритма Данцига-Вулфа (см.15.2). В процессе координации Центр
сообщает подсистемам координирующий сигнал π
кi
, на основе
которого производится модификация целевых функций подсис-
тем; f
i
(x
i
,π
кi
) = (c
т
i
-π
т
ki
) x
i
. Подсистемы решают свои оптимизацион-
ные задачи и сообщают координатору оптимальные решения x
*
ir
(здесь r - номер итерации) и значения целевых функций f
ir
= f
i
(x
*
ir
).
(0). Задается начальный номер итерации r = 1. Центр со-
общает подсистемам координирующий сигнал π
т
ki
= 0
т
, i = 1,2.
Итерация 1.
(1) При координирующем сигнале π
т
ki
= 0
т
, i=1,2 подсисте-
мы решают свои оптимизационные задачи
Подсистема 1 Подсистема 2
3x
1
+ 2x
2
→ max 2x
3
+ 3x
4
→ max
1x
1
+ 4x
2
≤ 28 1x
3
+ 3x
4
≤ 21
3x
1
+ 1x
2
≤ 18 1x
3
+ 1x
4
≤ 9
x
1
,x
2
≥ 0. 2x
3
+ 1x
4
≤ 14 x
3
,x
4
≥ 0.
Произведем решение задач подсистем графо-аналитичес-
ким способом.
x
2
x
4
(4,6) (3,6)
6 6
4 4 (5,4)
2 2
x
1
x
3
0 2 4 6 0 2 4 6
Рис. 16.4.
373
В результате решения получим
x
*
11
= (4, 6); x
*
21
= (3, 6)
f
11
= c
т
1
x
*
11
= 24; f
21
= c
т
2
x
*
21
= 24.
Значения x
*
11
,f
11
; x
*
21
,f
21
сообщаются в Центр.
(2) Центр строит координирующую задачу вида (15.23)-
(15.26)
2 r
Σ Σ ϕ
ij
λ
ij
→ max,
i=1 j=1
2 r
Σ Σ α
ij
λ
ij
≤ b
o
,
i=1 j=1
2 r
Σ Σ λ
ij
= 1, i = 1,2,
i=1 j=1
λ
ij.
≥0, i=1,2, j=1,…, r,
Здесь α
ij
вычисляется по правилу α
ij
= A
oi
x
*
ij
. Так как r=1, то
4 3
α
11
=
1 1
= 10; α
21
=
1 1 = 9.
6 6
Тогда координирующая задача имеет вид
24λ
11
+
24λ
21
→ max
10λ
11
+
9λ
21
≤ 16
1λ
11
= 1
1λ
21
= 1
λ
11
, λ
21
≥ 0 .
Такая задача решения не имеет (т.к. при λ
11
=1, λ
21
=1. не
выполняется ограничение 10λ
11
+
9λ
21
≤ 16). Произведем ее по-
гружение в М-задачу (см. 3.6), причем назначим М = 100:
24λ
11
+
24λ
21
-100λ
4
-100λ
5
→ max
10λ
11
+
9λ
21
+ 1λ
3
≤ 16
1λ
11
+
1λ
4
= 1
1λ
21
+ 1λ
5
= 1
λ
11
, λ
21
, λ
3
, λ
4
, λ
5
≥ 0 .
374
Произведем решение данной задачи симплекс-методом
(см. 3.5). Каждая итерация симплекс-метода сопровождается за-
полнением таблицы вида
L
π
т
J
s
x
s
S
-1
Здесь
L
- значение целевой функции;
π
т
- транспонированный вектор двойственных оценок;
J
s
- номера базисных переменных;
x
s
- значение базисных переменных;
S
-1
- обратная матрица базиса.
Итерация 1;
-200.00 0.00-100.00-100.00
3 16.00 1.00 0.00 0.00
4 1.00 0.00 1.00 0.00
5 1.00 0.00 0.00 1.00
Итерация 2;
-76.00 0.00 24.00-100.00
3 6.00 1.00 -10.00 0.00
1 1.00 0.00 1.00 0.00
5 1.00 0.00 0.00 1.00
Итерация 3;
6.66 13.77-113.77-100.00
2 0.66 0.11 -1.11 0.00
1 1.00 0.00 1.00 0.00
5 0.33 -0.11 1.11 1.00
Итерация 4-решение задачи
10.80 12.40-100.00 -87.60
2 1.00 0.00 0.00 1.00
1 0.70 0.10 0.00 -0.90
4 0.30 -0.10 1.00 0.90
Итак, решение задачи:
λ
1
= 0.7; λ
2
= 1.0;
λ
4
= 0.3.
Здесь λ
1
= λ
11
; λ
2
= λ
21
.
(3) Координирующий сигнал p
к
= 12.4.
Тогда π
т
к1
= 12.4 × ║ 1 1 ║ = ║ 12.4 12.4 ║;
π
т
к2
= 12.4 × ║ 1 1 ║ = ║ 12.4 12.4 ║.
375
Эти сигналы поступают в подсистемы.
(4) Номер итерации r = r + 1 = 2.
Производится переход на шаг 1.
Итерация 2.
(1) При координирующих сигналах π
т
к1
= ║ 12.4 12.4 ║; π
т
к2
=
║ 12.4 12.4 ║. Производится модификация целевых функций по
правилу (c
т
i
- π
т
ki
) x
i
, тогда
f
1
(x) =
║ 3 - 12.4, 2 - 12.4 ║ x = ║ -9.4, -10.4 ║ x → max;
f
2
(x) =
║ 2 - 12.4, 3 - 12.4 ║ x = ║ -10.4, -9.4 ║ x → max;
Оптимальное решение при таких целевых функциях (см. рис.16.4)
x
*
12
= (0, 0); f
12
= 0;
x
*
22
= (0, 0); f
22
= 0.
Эти данные сообщаются Центру.
(2) Центр строит координирующую задачу. При этом рас-
считываются
0 0
α
12
=
1 1
= 0; α
22
=
1 1 = 0.
0 0
Тогда координирующая задача имеет вид
24λ
11
+
24λ
21
→ max
10λ
11
+
9λ
21
+
1λ
3
≤ 16
1λ
11
+ 1λ
12
= 1
1λ
21
+ 1λ
22
= 1
λ
11
, λ
21
, λ
12
, λ
22
, λ
3
≥ 0 .
Дополнительные переменные λ
4
, λ
5
исключены из коорди-
нирующей задачи, т.к. их роль теперь выполняют переменные
λ
12
, λ
22
.
Решаем координирующую задачу симплекс-методом.
Итерация 1;
0.00 0.00 0.00 0.00
3 16.00 1.00 0.00 0.00
4 1.00 0.00 1.00 0.00
5 1.00 0.00 0.00 1.00
Итерация 2;
24.00 0.00 24.00 0.00
3 6.00 1.00 -10.00 0.00
1 1.00 0.00 1.00 0.00
5 1.00 0.00 0.00 1.00
376
Итерация 3;
40.00 2.66 -2.66 0.00
2 0.66 0.11 -1.11 0.00
1 1.00 0.00 1.00 0.00
5 0.33 -0.11 1.11 1.00
Итерация 4 - решение задачи
40.80 2.40 0.00 2.40
2 1.00 0.00 0.00 1.00
1 0.70 0.10 0.00 -0.90
4 0.30 -0.10 1.00 0.90
Итак, решение задачи:
λ
1
= 0.7; λ
2
= 1.0;
λ
4
= 0.3.
Здесь λ
1
= λ
11
; λ
2
= l
21
; λ
4
= λ
12
.
(3) Координирующий сигнал π
к
= 2.4.
Тогда π
т
к1
= 2.4 × ║ 1 1 ║ = ║ 2.4 2.4 ║;
π
т
к2
= 2.4 × ║ 1 1 ║ = ║ 2.4 2.4 ║.
Эти сигналы поступают в подсистемы.
(4) Номер итерации r = r + 1 = 3.
Производится переход на шаг 1.
Итерация 3.
(1) При координирующих сигналах π
т
к1
= ║ 2.4 2.4 ║; π
т
к2
=
║ 2.4 2.4 ║. Производится модификация целевых функций по
правилу (c
т
i
- π
т
ki
) x
i
, тогда
f
1
(x) =
║ 3 - 2.4, 2 - 2.4 ║ x = ║ 0.6, -0.4 ║ x → max;
f
2
(x) =
║ 2 - 2.4, 3 - 2.4 ║ x = ║ -0.4, 0.6 ║ x → max;
Оптимальное решение при таких целевых функциях (см. рис.16.4)
x
*
13
= (6, 0); f
13
= 18;
x
*
23
= (0, 7); f
23
= 21.
Эти данные сообщаются Центру.
(2) Центр строит координирующую задачу. При этом рас-
считываются
6 0
α
12
=
1 1
= 6; α
22
=
1 1 = 7.
0 7
Тогда координирующая задача имеет вид
377
24λ
11
+
24λ
21
+ 18λ
13
+
21λ
23
→ max
10λ
11
+
9λ
21
+ 6λ
13
+
7λ
23
+ 1λ
3
≤ 16
1λ
11
+ 1λ
13
+ 1λ
12
= 1
1λ
21
+ 1λ
23
+ 1λ
22
= 1
λ
11
, λ
21
, λ
12
, λ
22
, λ
13
, λ
23
, λ
3
≥ 0 .
Решаем данную координирующую задачу симплекс-методом.
Итерация 1;
0.00 0.00 0.00 0.00
5 16.00 1.00 0.00 0.00
6 1.00 0.00 1.00 0.00
7 1.00 0.00 0.00 1.00
Итерация 2;
24.00 0.00 24.00 0.00
5 6.00 1.00 -10.00 0.00
1 1.00 0.00 1.00 0.00
7 1.00 0.00 0.00 1.00
Итерация 3;
40.00 2.66 -2.66 0.00
2 0.66 0.11 -1.11 0.00
1 1.00 0.00 1.00 0.00
7 0.33 -0.11 1.11 1.00
Итерация 4 - решение задачи
43.50 1.50 9.00 10.50
2 1.00 0.00 0.00 1.00
1 0.25 0.25 -1.50 -2.25
3 0.75 -0.25 2.50 2.25
Решение задачи:
λ
1
= 0.25; λ
2
= 1.0;
λ
3
= 0.75.
Здесь λ
1
= λ
11
; λ
2
= λ
21
; λ
3
= λ
13
.
(3) Координирующий сигнал π
к
= 1.5.
Тогда π
т
к1
= 1.5 × ║ 1 1 ║ = ║ 1.5 1.5 ║;
π
т
к2
= 1.5 × ║ 1 1 ║ = ║ 1.5 1.5 ║.
Эти сигналы поступают в подсистемы.
(4) Номер итерации r = r + 1 = 4.
Производится переход на шаг 1.
378
Итерация 4.
(1) При координирующих сигналах π
т
к1
= ║ 1.5 1.5 ║; π
т
к2
=
║ 1.5 1.5 ║. Производится модификация целевых функций по
правилу (c
т
i
- π
т
ki
) x
i
, тогда
f
1
(x) =
║ 3 - 1.5, 2 - 1.5 ║ x = ║ 1.5, 0.5 ║ x → max;
f
2
(x) =
║ 2 - 1.5, 3 - 1.5 ║ x = ║ 0.5, 1.5 ║ x → max;
Оптимальное решение при таких целевых функциях (см. рис.16.4)
x
*
13
= (6,0), (4,6);
x
*
23
= (0,7), (3,6).
Эти решения уже сообщались Центру, тогда решение зада-
чи Центра будет тем же самым, и координирующий сигнал не из-
менится. Следовательно, получено оптимальное решение.
λ
*
1
= λ
11
= 0.25; λ
*
2
= λ
21
= 1.0;
λ
*
3
= λ
13
= 0.75.
Тогда
x
*
1
= λ
11
x
*
11
+ λ
13
x
*
13
= 0.25 (4, 6) + 0.75 (6, 0) = = (16.5, 1.5);
x
*
2
= λ
21
x
*
21
= 1.0 (3,6) = (3.6).
Оптимальное значение целевой функции f
*
(x
*
) = 43.5.
Таким образом, 1-му цеху целесообразно выпускать про-
дукцию А
1
в количестве 55 единиц, продукцию А
2
в количестве 15
единиц; 2-му цеху целесообразно выпускать продукцию А
3
в ко-
личестве 30 единиц и продукцию А
4
в количестве 60 единиц.
Суммарный доход предприятия при таком плане выпуска продук-
ции составит 4350.
379
Библиографический список
1. Алексеев В.М., Тихомиров В.М., Фомин С.В. Оптималь-
ное управление. - М.: Наука, 1979. - 429 с.
2. Алексеев К.Б., Бебенин Г.Т. Управление космическими
летательными аппаратами. - М.: Машиностроение, 1974.- 340 с.
3. Алексеев О.Г. Комплексное применение методов дис-
кретной оптимизации. - М.: Наука, 1987. - 248 с.
4. Алиев Р.А. Методы интеграции в системах управления
производством. - М.: Энергоатомиздат, 1989. - 271 с.
5. Атанс М., Фалб П. Оптимальное управление. - М.: Маши-
ностроение, 1968. - 763 с.
6. Багриновский К.А. Основы согласования плановых реше-
ний. - М.: Наука, 1977. - 303с.
7. Баринов К.Н., Насонов В.П. Краевые задачи динамики
полёта космических аппаратов. - Л.: ЛВИКА им. А.Ф. Можайского,
1970. - 211 с.
8. Болтянский В.Г. Математические
методы оптимального
управления. - М.: Наука, 1966. - 408 с.
9. Брайсон А., Хо-Ю-Ши. Прикладная теория оптимального
управления. -М.: Мир, 1972. - 544 с.
10. Булавский В.А, Звягина Р.А., Яковлева М.А. Численные
методы линейного программирования. - М.: Наука, 1977. - 308 с.
11. Бурков В.Н., Кондратьев В.В. Механизмы функциониро-
вания организационных систем. - М.: Наука, 1981. - 383 с.
12. Вагнер
Г. Основы исследования операций. Т.1.- М.: Мир,
1972. - 335 с.
13. Васильев Ф.П. Численные методы решения экстре-
мальных задач. - М.: Наука, 1980. - 520 с.
14. Вентцель Е.С. Исследование операций. Задачи, прин-
ципы, методология - М.: Наука, 1988. - 208 с.
15. Военная системотехника и системный анализ. Учебник.
/Под ред. Соколова Б.В. - СПб.: ВИКУ им. А.Ф
. Можайского, 1999.
- 496 с.
16. Воробьев Н.Н. Основы теории игр. - М.: Наука, 1984.-
495 с.
17. Воронов А.А. Введение в динамику сложных управляе-
мых систем. - М.: Наука, 1985. - 352 с.
18. Габасов Р., Кириллова Ф.М. Качественная теория опти-
мальных процессов. - М.: Наука, 1971. - 508 с.
380
19. Гасс С. Линейное программирование. Методы и прило-
жения. - М.: Наука, 1961. - 303 с.
20. Гилл Ф., Мюррей У. Численные методы условной опти-
мизации. М.: Мир, 1977. - 290 с.
21. Гермейер Ю.Б. Введение в теорию исследования опе-
раций. - М.: Наука, 1971. - 384 с.
22. Гермейер Ю.Б. Игры с непротивоположными интереса-
ми. - М.: Наука, 1976. - 327 с.
23. Гольштейн Е.
Г., Юдин Д.Б. Новые направления в ли-
нейном программировании. - М.: Сов.радио, 1966. - 524 с.
24. Горелик В.А., Горелов М.А., Кононенко А.Ф. Анализ
конфликтных ситуаций в системах управления. - М.: Радио и
связь, 1991. - 288 с.
25. Давыдов Э.Г. Исследование операций. - М.: Высшая
школа, 1990. - 383 с.
26. Данциг Дж. Линейное программирование, его примене-
ния и обобщения. - М.: Прогресс, 1965. - 600 с.
27. Дружинин В.В., Конторов Д.С. Введение в теорию кон-
фликта. - М.: Радио и связь, 1989. - 288 с.
28. Дубов Ю.А., Травкин С.И., Якимец В.Н. Многокритери-
альные модели формирования и выбора вариантов систем. - М.:
Наука, 1986. - 296 с.
29. Емеличев В.А., Ковалев М.М., Кравцов
М.К. Многогран-
ники, графы, оптимизация. - М.: Наука, 1981. - 344 с.
30. Ермольев Ю.М., Ляшко И.И., Михалевич В.С., Тюптя
В.И. Математические методы исследования операций.- Киев.:
Вища школа, 1979. - 312 с.
31. Ермольев Ю.М., Ястремский А.И. Стохастические моде-
ли и методы в экономическом планировании. - М.: Наука,1979.-
256с.
32. Ефремов Р.Н
., Шестаков Н.Н., Юсупов Р.М. Прикладная
математика. Вып.3. Методы динамической оптимизации и теории
игр. - Л.: МО СССР, 1978. - 210 с.
33. Заде Л. Понятие лингвистической переменной и его
применение к принятию приближенных решений. - М.: Мир,1976.-
165с.
34. Зайченко Ю.П. Исследование операций.- Киев: Вища
школа, 1979. - 391 с.
35. Зангвилл У.И. Нелинейное программирование. -
М.: Сов.
радио, 1973. - 312 с.