Семенкин Е.С. Методы оптимизации. Практикум
Подождите немного. Документ загружается.
Это число, которое для других точек отлично от нуля, назовем
характеристикой точки.
2. Определяем соседние точки по отношению к фиксированной. В
кружках, обозначающих эти точки, записываем их характеристики С
ij
=0+l
ij
и
на связях ставим стрелки, направленные в сторону точки P
i
.
3. Отмечаем точку Р
i
; символом ∨ обозначающим, что операции над
ней закончены.
4. Переходим к любой соседней с Р
i
; точке, для которой
характеристика уже найдена. Пусть это точка P
i
’
. Определяем соседние с ней
точки и рассчитываем для них характеристики как сумму С
ij
+l
ji
’
=C
ji
’
5. Точку P
j
’
отмечаем знаком ∨ переходим к п. 4 алгоритма.
6. При определении C
ji
’
для соседних точек с Р
j
’
может оказаться, что
для некоторых из них С
ij
уже рассчитаны; В этом случае С
ji
’
сравниваем с С
ij
.
Если С
ji
’
≥С
ij
для всех таких точек, то С
ij
остаются без изменения; точку
P
j
’
отмечаем знаком ∨ и переходим к п. 4 алгоритма. Если для некоторой
точки С
ji
’
<С
ij
то С
ij
заменяем на С
ij
’
, соответственно изменяется связь, через
которую проходит кратчайшее расстояние. Точку Р
j
’
отмечаем знаком ∨
только в том случае, если точка, у которой изменилась характеристика, не
была ранее отмечена.
7. Если изменилась характеристика отмеченной точки, то
пересчитываем характеристики точек, соседних с ней, а затем отмечаем
точку Р
j
’
и переходим к п. 4 алгоритма.
8. Процесс продолжаем до тех пор, пока не будут отмечены все точки.
После этого выписываем кратчайшие расстояния (характеристики точек) и
маршруты, по которым они проходят. На этом первый этап заканчивается.
9. Переходим к следующему этапу, начиная с п. 1 алгоритма. Расчет
продолжаем до тех пор. пока не будут определены кратчайшие расстояния от
всех точек до каждой из них.
Процесс продолжаем до тех пор, пока не будут рассчитаны кратчайшие
расстояния от всех точек до каждой из них. Вычисления значительно
упрощаются, если длины отрезков, изображающих связи, задавать в одном и
том же масштабе (что обычно имеет место при решении конкретных
экономических задач). Если задача содержит более 50 точек, то ее следует
решать с помощью ЭВМ.
Необходимо отметить, что числа l
ij
можно интерпретировать по-
разному. Они могут означать (в зависимости от рассматриваемого
экономического процесса) расстояние, стоимость, себестоимость, время и т.
д.
Решить методом динамического программирования следующие задачи:
1. В Кызылский лесхоз прибыла лесоустроительная партия. Её задача
состоит в просмотре определённых участков леса, дальнейшего изложения
данных на планшетах и выяснение необходимости санитарных рубок. До
определённого пункта необходимо добраться за наименьший отрезок времени
(время дано в часах) Найти этот путь, если:
А)
5,4 1,2 3,1 2,3
6 1,2 3 2,5 1 9,3 2 1,5 3
2 1,1 2,3 0,5
5 6,1 4 1,5 4 1,5 3 2,3 3
4 3 2,5 2,1
Б)
0,4 1,1 0,1 0,3
0,6 0,3 1 1,2 1,8
1 1,1 0,7 0,5
2,5 3,4 2,8 1,3 0,3
4 3 2,5 2,1
5,6 2,3 3,3 2 2,8
7 2,4 4,9 4
2. Найти оптимальное управление процессом набора высоты и
скорости самолетом, позволяющее минимизировать общий расход горючего
при заданных условиях:
3. Определить кратчайшие расстояния по сети от каждой точки до всех
остальных и соответствующие пути, по которым они проходят:
13
12
1
0
15
10
8
13
14
12
12
15
13
11
10
10
8
9
11
13
12
13
15
10
14
16
17
15
14
13
12
11
10
9
11
13
12
14
13
15
10
10
10
13
11
12
14
11
10
10
12
12
13
18
18
12
14
15
14
13
19
20
21
18
19
9
10
12
15
13
16
19
V
k
V
H
0
0
V
0
H
H
k
S
k
S
0
4. Найти оптимальное управление процессом набора высоты и
скорости самолетом, позволяющее минимизировать общий расход горючего
при заданных условиях:
5. В лесной зоне необходимо проложить дорогу от пункта А до пункта Б,
срубив как можно меньше деревьев на пути. Найдите этот путь.
11 24 32 45 5 1 Б
11 10 19 8 7 6
12 23 14 15 16
22 21 20 19 18 17
23 24 25 26 27
33 32 31 30 29 28
34 35 36 27 38
44 43 42 41 40 39
А 15 46 17 28 49
H
H
k
0 V
0
V
k
V
1
1
1
1
9
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
1
1
1
8
1
1
9
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
1
2
1
2
2
1
2
1
1
2
2
1
1
H
0
S
S
Библиографический список
1. Андреева Е.А. , Цирулева В.М. Вариационное исчисление и методы
оптимизации. – М.: Высшая школа, 2006.
2. Ванько В.И. , Ермошина О.В. , Кувыркин Г.Н. Вариационное
исчисление и оптимальное управление. М.: МГТУ, 2006.
3. Григорьев А.В., Григорьева Т.В. Практикум по линейному
программированию. – Красноярск: КГТУ, 1998.
4. Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. Математическое
программирование. – М.: Высшая школа, 1976. – 352 с.
5. Пантелеев А. В. , Летова Т.А. Методы оптимизации в примерах и
задачах. – М.:Высшая школа, 2005.
6. Пантелеи В.А. , Бортаковский А.С. Оптимальное управление в
примерах и задачах. – М.: Высшая школа, 2001.
7. Сборник задач по дифференциальным уравнениям и вариационному
исчислению / под ред.В.К. Романко. – М.: ФИЗМАТЛИТ 2002.