ГУАП
КАФЕДРА № 41
ОТЧЕТ ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
ассистент |
|
|
|
Н.Н. Григорьева |
|
|
|
|
|
|
|
|
|
|
должность, уч. степень, звание |
|
подпись, дата |
|
инициалы, фамилия |
ОТЧЕТ О ПРАКТИЧЕСКОЙ РАБОТЕ №3
ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
по курсу: ИССЛКДОВАНИЕ ОПЕРАЦИЙ
РАБОТУ ВЫПОЛНИЛ
СТУДЕНТ ГР. №
подпись, дата |
|
инициалы, фамилия |
Санкт-Петербург 2022
Цель работы
Решите задачи динамического программирования.
Индивидуальный вариант
Индивидуальный вариант номер 10 в соответствии с рисунком 1.
Рисунок 1 – Вариант задания
2
Ход работы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
1. |
|
Решение |
задачи |
|
|
эвакуации |
|
при |
ограничении |
на |
||||||||||||
грузоподъёмность G = 11. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
П1 |
П2 |
П3 |
П4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
g (вес) |
2 |
4 |
|
5 |
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
С (цена) |
30 |
60 |
70 |
80 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
x |
1 |
1 |
|
1 |
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
П4 |
|
|
|
|
|
П3 |
|
|
П2 |
|
|
П1 |
|
||||||
|
x4 |
|
|
φ4 |
|
|
|
x3 |
|
|
φ3 |
|
x2 |
|
|
φ2 |
|
|
x1 |
|
φ1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
0 |
|
0 |
|
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|||||
1 |
|
0 |
|
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
|
|
|
|
||||
2 |
|
0 |
|
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
|
|
|
|
||||
3 |
|
0 |
|
|
0 |
|
0 |
|
0 |
|
0 |
|
0 |
|
|
|
|
|
||||
4 |
|
0 |
|
|
0 |
|
0 |
|
0 |
|
1 |
|
60 |
|
|
|
|
|
||||
5 |
|
0 |
|
|
0 |
|
|
1 |
|
|
70 |
|
0 |
|
70 |
|
|
|
|
|
||
6 |
|
0 |
|
|
0 |
|
1 |
|
70 |
|
0 |
|
70 |
|
|
|
|
|
||||
7 |
|
1 |
|
|
80 |
|
0 |
|
80 |
|
0 |
|
80 |
|
|
|
|
|
||||
8 |
|
1 |
|
|
80 |
|
0 |
|
80 |
|
0 |
|
80 |
|
|
|
|
|
||||
9 |
|
1 |
|
|
80 |
|
1 |
|
70 |
|
1 |
|
|
130 |
|
|
|
|
|
|||
10 |
|
1 |
|
|
80 |
|
1 |
|
70 |
|
1 |
|
130 |
|
|
|
|
|
||||
11 |
|
1 |
|
|
80 |
|
1 |
|
70 |
|
1 |
|
130 |
|
|
1 |
|
160 |
||||
S1 |
= 11, x1 = 1 |
S2 |
= 9, x2 = 1 |
S3 |
= 5, x3 = 1 |
S4 |
= 0, x4 = 0 |
Ответ: X = {1, 1, 1, 0}
2.Решение задачи о распределении ресурсов.
x |
φ1 |
φ2 |
φ3 |
φ4 |
1 |
0,2 |
0,5 |
0,8 |
1,0 |
2 |
0,4 |
0,6 |
0,9 |
1,0 |
3 |
0,6 |
0,7 |
1,1 |
1,1 |
4 |
0,8 |
0,8 |
1,3 |
1,1 |
5 |
1,0 |
0,9 |
1,4 |
1,2 |
6 |
1,2 |
0,9 |
1,5 |
1,2 |
7 |
1,3 |
1,0 |
1,5 |
1,3 |
3
S |
|
|
|
|
П4 |
П3 |
|
|
|
П2 |
|
|
|
|
|
П1 |
||||||||||
|
|
x4 |
|
|
w4 |
x3 |
|
w3 |
|
x2 |
|
w2 |
|
x1 |
|
|
w1 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
0 |
|
0 |
|
0 |
|
0 |
|
|
0 |
0 |
|
|
0 |
|
0 |
|
0 |
|
||||||||
1 |
|
|
1 |
|
|
1,0 |
|
0 |
|
|
1,0 |
0 |
|
|
1,0 |
|
0 |
|
1,0 |
|
||||||
2 |
|
2 |
|
1,0 |
|
1 |
|
|
1,8 |
0 |
|
|
1,8 |
|
0 |
|
1,8 |
|
||||||||
3 |
|
3 |
|
1,1 |
|
1 |
|
|
1,9 |
|
1 |
|
|
2,3 |
|
0 |
|
2,3 |
|
|||||||
4 |
|
4 |
|
1,1 |
|
1 |
|
|
2,1 |
1,2 |
|
|
2,4 |
|
1 |
|
2,5 |
|
||||||||
5 |
|
5 |
|
1,2 |
|
1 |
|
|
2,3 |
1 |
|
|
2,6 |
|
2 |
|
2,7 |
|
||||||||
6 |
|
6 |
|
1,2 |
|
1 |
|
|
2,4 |
1 |
|
|
2,8 |
|
3 |
|
2,9 |
|
||||||||
7 |
|
7 |
|
1,3 |
|
1 |
|
|
2,5 |
1,2 |
|
|
2,9 |
|
|
4 |
|
|
3,1 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
S3 |
|
|
|
X3 |
φ3 |
|
|
|
S4 |
|
φ4 |
|
|
|
|
W3 |
|||||||||
|
1 |
|
|
|
0 |
|
0 |
|
|
|
|
1 |
|
|
1,0 |
|
|
|
|
1,0 |
|
|||||
|
|
|
|
1 |
|
0,8 |
|
|
|
|
0 |
|
|
0 |
|
|
|
|
0,8 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
0 |
|
0 |
|
|
|
|
2 |
|
|
1,0 |
|
|
|
|
1,0 |
|
|||||
|
2 |
|
|
|
1 |
|
0,8 |
|
|
|
|
1 |
|
|
1,0 |
|
|
|
|
1,8 |
|
|||||
|
|
|
|
|
2 |
|
0,9 |
|
|
|
|
0 |
|
|
0 |
|
|
|
|
0,9 |
|
|||||
|
|
|
|
|
0 |
|
0 |
|
|
|
|
3 |
|
|
1,1 |
|
|
|
1,1 |
|
||||||
|
3 |
|
|
|
1 |
|
0,8 |
|
|
|
|
2 |
|
|
1,0 |
|
|
|
|
1,8 |
|
|||||
|
|
|
|
2 |
|
0,9 |
|
|
|
|
1 |
|
|
1,0 |
|
|
|
|
1,9 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
3 |
|
1,1 |
|
|
|
|
0 |
|
|
0 |
|
|
|
|
1,1 |
|
|||||
|
|
|
|
|
0 |
|
0 |
|
|
|
|
4 |
|
|
1,1 |
|
|
|
1,1 |
|
||||||
|
|
|
|
|
1 |
|
0,8 |
|
|
|
|
3 |
|
|
1,1 |
|
|
|
1,9 |
|
||||||
|
4 |
|
|
|
2 |
|
0,9 |
|
|
|
|
2 |
|
|
1,0 |
|
|
|
|
1,9 |
|
|||||
|
|
|
|
|
3 |
|
1,1 |
|
|
|
|
1 |
|
|
1,0 |
|
|
|
|
2,1 |
|
|||||
|
|
|
|
|
4 |
|
1,3 |
|
|
|
|
0 |
|
|
0 |
|
|
|
|
1,3 |
|
|||||
|
|
|
|
|
0 |
|
0 |
|
|
|
|
5 |
|
|
1,2 |
|
|
|
1,2 |
|
||||||
|
|
|
|
|
1 |
|
0,8 |
|
|
|
|
4 |
|
|
1,1 |
|
|
|
1,9 |
|
||||||
|
5 |
|
|
|
2 |
|
0,9 |
|
|
|
|
3 |
|
|
1,1 |
|
|
|
2,0 |
|
||||||
|
|
|
|
3 |
|
1,1 |
|
|
|
|
2 |
|
|
1,0 |
|
|
|
|
2,1 |
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
4 |
|
1,3 |
|
|
|
|
1 |
|
|
1,0 |
|
|
|
|
2,3 |
|
|||||
|
|
|
|
|
5 |
|
1,4 |
|
|
|
|
0 |
|
|
0 |
|
|
|
|
1,4 |
|
|||||
|
|
|
|
|
0 |
|
0 |
|
|
|
|
6 |
|
|
1,2 |
|
|
|
1,2 |
|
||||||
|
|
|
|
|
1 |
|
0,8 |
|
|
|
|
5 |
|
|
1,2 |
|
|
|
2,0 |
|
||||||
|
|
|
|
|
2 |
|
0,9 |
|
|
|
|
4 |
|
|
1,1 |
|
|
|
2,0 |
|
||||||
|
6 |
|
|
|
3 |
|
1,1 |
|
|
|
|
3 |
|
|
1,1 |
|
|
|
2,2 |
|
||||||
|
|
|
|
|
4 |
|
1,3 |
|
|
|
|
2 |
|
|
1,0 |
|
|
|
|
2,3 |
|
|||||
|
|
|
|
|
5 |
|
1,4 |
|
|
|
|
1 |
|
|
1,0 |
|
|
|
|
2,4 |
|
|||||
|
|
|
|
|
6 |
|
1,5 |
|
|
|
|
0 |
|
|
0 |
|
|
|
|
1,5 |
|
|||||
|
|
|
|
|
0 |
|
0 |
|
|
|
|
7 |
|
|
1,3 |
|
|
|
1,3 |
|
||||||
|
|
|
|
|
1 |
|
0,8 |
|
|
|
|
6 |
|
|
1,2 |
|
|
|
2,0 |
|
||||||
|
|
|
|
|
2 |
|
0,9 |
|
|
|
|
5 |
|
|
1,2 |
|
|
|
2,1 |
|
||||||
|
7 |
|
|
|
3 |
|
1,1 |
|
|
|
|
4 |
|
|
1,1 |
|
|
|
2,2 |
|
||||||
|
|
|
|
4 |
|
1,3 |
|
|
|
|
3 |
|
|
1,1 |
|
|
|
2,4 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
5 |
|
1,4 |
|
|
|
|
2 |
|
|
1,0 |
|
|
|
|
2,4 |
|
|||||
|
|
|
|
|
6 |
|
1,5 |
|
|
|
|
1 |
|
|
1,0 |
|
|
|
|
2,5 |
|
|||||
|
|
|
|
|
7 |
|
1,5 |
|
|
|
|
0 |
|
|
0 |
|
|
|
|
1,5 |
|
|||||
4
S2 |
|
X2 |
|
φ2 |
|
S3 |
|
W3 |
|
W2 |
|||||
1 |
|
0 |
|
|
0 |
|
|
1 |
|
|
1,0 |
|
|
1 |
|
1 |
|
0,5 |
|
0 |
|
0 |
|
0,5 |
|
||||||
|
|
|
|
|
|
||||||||||
|
|
0 |
|
|
0 |
|
|
2 |
|
|
1,8 |
|
|
1,8 |
|
2 |
1 |
|
0,5 |
|
1 |
|
1,0 |
|
1,5 |
|
|||||
|
2 |
|
0,6 |
|
0 |
|
0 |
|
0,6 |
|
|||||
|
|
0 |
|
|
0 |
|
|
3 |
|
|
1,9 |
|
|
1,9 |
|
3 |
1 |
|
0,5 |
|
2 |
|
1,8 |
|
2,3 |
|
|||||
2 |
|
0,6 |
|
1 |
|
1,0 |
|
1,6 |
|
||||||
|
|
|
|
|
|
||||||||||
|
3 |
|
0,7 |
|
0 |
|
0 |
|
0,7 |
|
|||||
|
0 |
|
0 |
|
4 |
|
2,1 |
|
2,1 |
|
|||||
|
|
1 |
|
|
0,5 |
|
|
3 |
|
|
1,9 |
|
|
2,4 |
|
4 |
|
2 |
|
|
0,6 |
|
|
2 |
|
|
1,8 |
|
|
2,4 |
|
|
3 |
|
0,7 |
|
1 |
|
1,0 |
|
1,7 |
|
|||||
|
4 |
|
0,8 |
|
0 |
|
0 |
|
0,8 |
|
|||||
|
0 |
|
0 |
|
5 |
|
2,3 |
|
2,3 |
|
|||||
|
|
1 |
|
|
0,5 |
|
|
4 |
|
|
2,1 |
|
|
2,6 |
|
5 |
2 |
|
0,6 |
|
3 |
|
1,9 |
|
2,5 |
|
|||||
3 |
|
0,7 |
|
2 |
|
1,8 |
|
2,5 |
|
||||||
|
|
|
|
|
|
||||||||||
|
4 |
|
0,8 |
|
1 |
|
1,0 |
|
1,8 |
|
|||||
|
5 |
|
0,9 |
|
0 |
|
0 |
|
0,9 |
|
|||||
|
0 |
|
0 |
|
6 |
|
2,4 |
|
2,4 |
|
|||||
|
|
1 |
|
|
0,5 |
|
|
5 |
|
|
2,3 |
|
|
2,8 |
|
|
2 |
|
0,6 |
|
4 |
|
2,1 |
|
2,7 |
|
|||||
6 |
3 |
|
0,7 |
|
3 |
|
1,9 |
|
2,6 |
|
|||||
|
4 |
|
0,8 |
|
2 |
|
1,8 |
|
2,6 |
|
|||||
|
5 |
|
0,9 |
|
1 |
|
1,0 |
|
1,9 |
|
|||||
|
6 |
|
0,9 |
|
0 |
|
0 |
|
0,9 |
|
|||||
|
0 |
|
0 |
|
7 |
|
2,5 |
|
2,5 |
|
|||||
|
|
1 |
|
|
0,5 |
|
|
6 |
|
|
2,4 |
|
|
2,9 |
|
|
|
2 |
|
|
0,6 |
|
|
5 |
|
|
2,3 |
|
|
2,9 |
|
7 |
3 |
|
0,7 |
|
4 |
|
2,1 |
|
2,8 |
|
|||||
4 |
|
0,8 |
|
3 |
|
1,9 |
|
2,7 |
|
||||||
|
|
|
|
|
|
||||||||||
|
5 |
|
0,9 |
|
2 |
|
1,8 |
|
2,7 |
|
|||||
|
6 |
|
0,9 |
|
1 |
|
1,0 |
|
1,9 |
|
|||||
|
7 |
|
1,0 |
|
0 |
|
0 |
|
1 |
|
|||||
Ответ: X = {4,1,1,1} доход 3.1
5