Методы оптимизации и теория управления
Министерство
образования и науки Российской Федерации
Государственное
образовательное учреждение
высшего
профессионального образования
«Комсомольский-на-Амуре
государственный технический университет»
Расчетно-графическое
задание
«Методы
оптимизации и теория управления»
Содержание
РГЗ
№ 3
Задача
1
Задача
2
Список
использованных источников
Задача 1
Распределите оптимальным образом денежные
средства величиной Х между N предприятиями. В результате выделения средств k-му
предприятию в размере u оно дает доход Jk(u).
Вариант 3. X = 100 тыс. руб., N = 4. Средства
предприятиям распределяются в количествах, кратных 25 тыс. руб., но не могут
превосходить 50 тыс. руб. Функции Jk(u), k = 1, …, 4, заданы в таблице 1:
Таблица 1
|
u
(тыс. руб.)
|
25
|
50
|
75
|
100
|
|
J1(u)
|
12
|
14
|
20
|
28
|
|
J2(u)
|
12
|
18
|
24
|
30
|
|
J3(u)
|
12
|
16
|
24
|
30
|
|
J4(u)
|
8
|
12
|
16
|
24
|
Решение.
этап. Условная оптимизация.
-й шаг: k = 4. Предположим, что все средства в
количестве u4 = 100 тыс. руб. отданы четвертому предприятию. В этом случае
максимальный доход, как это видно из таблицы 2, составит J4(U4)=12 тыс. руб. ,
следовательно, F4(c4)=J4(U4).
Таблица 2
|
с4 u4
|
0
|
25
|
50
|
75
|
100
|
|
0
|
0
|
-
|
-
|
-
|
-
|
|
25
|
-
|
8
|
-
|
-
|
-
|
|
50
|
-
|
-
|
12
|
-
|
-
|
|
75
|
-
|
-
|
16
|
-
|
|
100
|
-
|
-
|
-
|
-
|
24
|
|
F4(c4)
|
0
|
8
|
12
|
16
|
24
|
|
u*4
|
0
|
25
|
50
|
75
|
100
|
-й шаг: k = 3. Определяем оптимальную стратегию
при распределении денежных средств между четвертым и третьим предприятиями. При
этом соотношение Беллмана имеет вид:
на основе которого составлена таблица 3:
Таблица 3
|
с3
u3
|
25
|
50
|
75
|
100
|
|
0
|
8
|
12
|
16
|
24
|
|
25
|
12
|
20
|
24
|
28
|
|
50
|
-
|
16
|
24
|
28
|
|
75
|
-
|
-
|
24
|
32
|
|
100
|
-
|
-
|
-
|
30
|
|
F3(c3)
|
12
|
20
|
24
|
32
|
|
u*3
|
25
|
25
|
25,50,75
|
75
|
-й шаг: k = 2. Определяем оптимальную стратегию
при распределении денежных средств между вторым и двумя другими предприятиями,
используя следующую формулу для расчета суммарного дохода:
на основе которого составлена таблица 4:
Таблица 4
|
с2
u2
|
25
|
50
|
75
|
100
|
|
0
|
0
|
12
|
20
|
24
|
32
|
|
25
|
-
|
12
|
24
|
32
|
36
|
|
50
|
-
|
-
|
18
|
30
|
38
|
|
75
|
-
|
-
|
-
|
24
|
36
|
|
100
|
-
|
-
|
-
|
-
|
30
|
|
F2(c2)
|
0
|
12
|
24
|
32
|
38
|
|
u*2
|
0
|
0,25
|
25
|
25
|
50
|
4-й шаг: k = 1. Определяем оптимальную стратегию
при распределении денежных средств между первым и тремя другими предприятиями,
используя следующую формулу для расчета суммарного дохода:
на основе которого составлена таблица 5:
Таблица 5
|
с1
u1
|
0
|
25
|
50
|
75
|
100
|
|
0
|
0
|
12
|
24
|
32
|
38
|
|
25
|
-
|
12
|
24
|
36
|
44
|
|
50
|
-
|
14
|
26
|
38
|
|
75
|
-
|
-
|
-
|
20
|
32
|
|
100
|
-
|
-
|
-
|
-
|
28
|
|
F1(c1)
|
0
|
12
|
24
|
36
|
44
|
|
u*1
|
0
|
0,25
|
0,25
|
25
|
25
|
этап. Безусловная оптимизация.
Определяем компоненты оптимальной стратегии.
-й шаг. По данным таблицы 5 максимальный доход
при распределении 100 тыс. руб. между четырьмя предприятиями составляет: с1 =
100, F1(100) = 44. При этом первому предприятию нужно выделить u1* = 25.
-й шаг. Определяем величину оставшихся денежных
средств, приходящуюся на долю второго, третьего и четвертого предприятий:
с2 = с1 - u1* = 100 - 25 = 75.
По данным таблицы 4 находим, что оптимальный
вариант распределения денежных средств размером с2 = 75 между третьим и
четвертым предприятиями составляет: F2(75)=32 при выделении второму предприятию
u2* = 25.
-й шаг. Определяем величину средств,
приходящуюся на долю третьего и четвертого предприятий:
с3 = с2 - u2* = 75 - 25 = 50.
По данным таблицы 3 находим, что максимально
возможный прирост при распределении оставшихся средств размером с3 = 50 между
третьим и четвертым предприятиями составляет F3(50) = 20 при выделении третьему
предприятию u3* = 25.
Значит четвертому предприятию останется u4* =
25.
Таким образом, оптимальный план инвестиций: u* =
(25, 25, 25, 25), который обеспечивает максимальный прирост производства:
F(100) = J1(25) + J2(25) + J3(25) + J4(25) = 12 + 12 + 12 + 8= 44.
Задача 2
На заданной сети дорог имеется несколько
маршрутов по доставке груза из пункта 1 в пункт 10. Стоимость перевозки единицы
груза между отдельными пунктами сети проставлена у соответствующих ребер.
Необходимо определить оптимальный маршрут доставки груза из пункта 1 в пункт
10, который обеспечил бы минимальные транспортные расходы.
Рисунок 1
Решение.
этап. Условная оптимизация.
-й шаг. k=1.
(i)=Ci10
оптимизация денежный доход маршрут
На первом шаге в пункт 10 груз может быть
доставлен из пунктов 7, 8 или 9.
Таблица 6
|
j
i
|
10
|
F1(i)
|
j*
|
|
7
|
10
|
10
|
10
|
|
8
|
5
|
5
|
10
|
|
9
|
3
|
3
|
10
|
-й шаг. k=2.
Функциональное уравнение на втором шаге
принимает вид
Все возможные перемещения груза на втором шаге и
результаты расчета приведены в следующей таблице:
Таблица 7
7
|
8
|
9
|
F2(i)
|
j*
|
|
5
|
5+10
|
3+5
|
-
|
8
|
8
|
|
6
|
-
|
2+5
|
3+3
|
6
|
9
|
-й шаг. k=3.
Таблица 8
|
j i
|
5
|
6
|
F3(i)
|
j*
|
|
2
|
7+8
|
-
|
15
|
5
|
|
3
|
-
|
8+6
|
14
|
6
|
|
4
|
-
|
5+6
|
11
|
6
|
-й шаг. k=4.
Таблица 9
|
j i
|
2
|
3
|
4
|
F4(i)
|
j*
|
|
1
|
7+15
|
4+14
|
4+11
|
15
|
4
|
этап. Безусловная оптимизация.
На этапе условной оптимизации получено, что
минимальные затраты на перевозку груза из пункта 1 в пункт 10 составляют
F4(1)=15. Данный результат достигается при движении груза из 1-го пункта в 4-й.
По данным таблицы третьего шага необходимо двигаться в пункт 6, затем - в пункт
9 (см. таблицу второго шага) и из него - в конечный пункт (см. таблицу первого
шага). Таким образом, оптимальный маршрут доставки груза: 1®
4 ®
6 ®
9 ®
10. На рисунке 2 жирными стрелками показан оптимальный путь.
Рисунок 2
Список использованных источников
Некрасова
М.Г. Методы оптимизации и теория управления: Учебное пособие /
Комсомольск-на-Амуре: ГОУВПО «КнАГТУ», 2007. - 132 с.