- •3 Задача про найкоротший шлях 8
- •7.2.3 Стани 50
- •7.2.4 Основне рекурентне співвідношення 51
- •1 Загальна характеристика динамічного програмування
- •1.1 Геометрична інтерпретація задач дп
- •1.2 Приклад багатоетапної операції
- •2 Основні положення поетапного оптимального управліНня
- •2.1 Загальна схема алгоритму динамічного планування n-крокової операції
- •3 Задача про найкоротший шлях
- •3.1 Схема алгоритму зворотньої прогонки (азп) по дугах, що виходять
- •3.2 Приклад застосування алгоритму азп по дугах, що виходять
- •3.3 Завдання для самостійної роботи
- •3.4 Схема алгоритму прямої прогонки (апп) по дугах, що входять
- •3.5 Приклад застосування алгоритму апп по дуга, що входять х
- •3.6. Завдання для самостійної роботи
- •3.7 Схема алгоритму зворотної прогонки (азп) по дугах, що входять
- •3.8 Відмінності алгоритмів прямої і зворотної прогонок
- •3.9 Контрольні завдання
- •4. Задача про оптимальне використання ресурсу
- •4.1 Змістовна інтерпретація задачі про оптимальне використання ресурсу
- •4.2 Побудова рекурентного співвідношення задачі 4.1.1
- •4.3 Побудова рекурентного співвідношення задачі 4.1.2
- •4.4 Схема апп для зовк
- •4.5 Приклад розв’язання зовк
- •4.6 Завдання для самостійної роботи
- •4.7 Контрольні завдання
- •5 Задача про використання робочої сили
- •5.1 Постановка задачі
- •5.2 Теоретичне обґрунтування алгоритму зворотньої прогонки для розв’язку задачі про найм робочої сили
- •5.3 Алгоритм пп розв’язку задачі
- •5.4 Приклад розв’язання зврс
- •5.5 Контрольні завдання
- •6 Основні елементи і принципи динамічного програмування
- •6.1 Адитивність цільової функції і етапи задачі
- •6.2 Принцип занурення
- •6.3 Основне рекурентне співвідношення
- •6.4 Стани
- •6.5 Умова марковості (відсутність післядії)
- •6.6 Принцип оптимальності Белмана
- •6.7 Загальна схема застосування алгоритму дп
- •7 Задача управліНня запасами
- •7.1 Постановка задачі
- •7.2 Елементи динамічної моделі
- •7.2.1 Етапи
- •7.2.2 Варіанти розв’язків
- •7.2.3 Стани
- •7.2.4 Основне рекурентне співвідношення
- •7.3 Приклади розв’язання зуз
- •7.4 Контрольні завдання
- •8 Задача про надійність
- •8.1 Змістовна постановка задачі
- •8.2 Математична модель задачі
- •8.3 Елементи динамічної моделі
- •Основне рекурентне співвідношення
- •8.4 Приклад розв’язання задачі
- •8.5 Контрольні завдання
- •Список літератури
4.7 Контрольні завдання
Розв’язати задачу про оптимальне використання капіталовкладень. Кількість підприємств, сумарний об'єм капіталовкладень і відповідних величин і представлені в табл. 6. Прочерки в клітинках означають, що на відповідних підприємствах проект D не пропонується до розгляду.
Таблиця 6.
Варіант |
Проект |
Підприємство |
|
|||||||
1 |
2 |
3 |
4 |
|||||||
|
|
|
|
|
|
|
|
|||
1 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
B |
1 |
3 |
1 |
2 |
2 |
3 |
3 |
5 |
||
C |
2 |
5 |
3 |
5 |
3 |
6 |
3 |
6 |
||
D |
4 |
7 |
4 |
8 |
-- |
-- |
4 |
7 |
||
2 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
B |
1 |
3 |
1 |
4 |
1 |
4 |
2 |
3 |
||
C |
3 |
4 |
2 |
5 |
2 |
5 |
4 |
5 |
||
D |
4 |
5 |
-- |
-- |
3 |
6 |
5 |
7 |
||
3 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
B |
1 |
3 |
1 |
2 |
1 |
2 |
2 |
4 |
||
C |
2 |
4 |
2 |
6 |
2 |
5 |
3 |
5 |
||
D |
3 |
7 |
4 |
7 |
4 |
6 |
6 |
8 |
||
4 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
B |
1 |
5 |
2 |
4 |
1 |
2 |
1 |
3 |
||
C |
2 |
7 |
3 |
6 |
2 |
5 |
3 |
6 |
||
D |
4 |
9 |
4 |
10 |
3 |
6 |
4 |
8 |
||
5 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
B |
1 |
2 |
2 |
3 |
1 |
3 |
2 |
3 |
||
C |
2 |
5 |
3 |
5 |
3 |
5 |
3 |
5 |
||
D |
4 |
6 |
-- |
-- |
-- |
-- |
4 |
6 |
||
6 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
B |
1 |
4 |
2 |
5 |
1 |
3 |
2 |
5 |
||
C |
3 |
5 |
3 |
6 |
3 |
5 |
4 |
7 |
||
D |
4 |
7 |
-- |
-- |
-- |
-- |
-- |
-- |
||
7 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
8 |
B |
1 |
4 |
4 |
7 |
3 |
5 |
1 |
3 |
||
C |
2 |
5 |
5 |
9 |
4 |
6 |
2 |
5 |
||
D |
3 |
5 |
-- |
-- |
-- |
-- |
-- |
-- |
||
8 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
B |
1 |
2 |
2 |
3 |
1 |
3 |
3 |
4 |
||
C |
2 |
4 |
4 |
6 |
3 |
4 |
5 |
6 |
||
D |
3 |
5 |
5 |
6 |
4 |
6 |
6 |
8 |
||
9 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
B |
1 |
5 |
1 |
2 |
1 |
3 |
2 |
4 |
||
C |
2 |
7 |
3 |
5 |
2 |
5 |
4 |
7 |
||
D |
3 |
8 |
5 |
7 |
4 |
6 |
7 |
9 |
||
10 |
3 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
B |
1 |
4 |
1 |
2 |
2 |
3 |
3 |
5 |
||
C |
3 |
5 |
2 |
4 |
3 |
5 |
4 |
6 |
||
D |
4 |
6 |
5 |
6 |
4 |
7 |
5 |
7 |
||
11 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
B |
1 |
4 |
2 |
5 |
1 |
3 |
1 |
3 |
||
C |
3 |
5 |
3 |
6 |
3 |
5 |
2 |
5 |
||
D |
4 |
7 |
4 |
7 |
4 |
7 |
5 |
6 |
||
12 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
B |
1 |
5 |
2 |
4 |
1 |
3 |
2 |
3 |
||
C |
2 |
6 |
3 |
7 |
4 |
6 |
5 |
10 |
||
D |
4 |
6 |
-- |
-- |
-- |
-- |
-- |
-- |
||
13 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
B |
1 |
3 |
1 |
2 |
2 |
3 |
2 |
3 |
||
C |
3 |
5 |
2 |
5 |
3 |
5 |
3 |
5 |
||
D |
4 |
8 |
4 |
7 |
-- |
-- |
-- |
-- |
||
14 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
B |
1 |
2 |
1 |
3 |
2 |
4 |
2 |
5 |
||
C |
2 |
5 |
3 |
7 |
3 |
6 |
3 |
8 |
||
D |
4 |
10 |
-- |
-- |
4 |
10 |
-- |
-- |
||
15 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
B |
1 |
3 |
2 |
4 |
1 |
2 |
1 |
2 |
||
C |
3 |
6 |
4 |
9 |
2 |
3 |
3 |
7 |
||
D |
-- |
-- |
-- |
-- |
4 |
8 |
4 |
9 |
||
16 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
B |
2 |
5 |
5 |
9 |
1 |
2 |
2 |
4 |
||
C |
3 |
7 |
-- |
-- |
3 |
6 |
4 |
9 |
||
D |
4 |
8 |
-- |
-- |
5 |
10 |
-- |
-- |
||
17 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
B |
1 |
2 |
1 |
3 |
2 |
3 |
1 |
2 |
||
C |
2 |
5 |
2 |
4 |
3 |
8 |
3 |
7 |
||
D |
3 |
6 |
3 |
6 |
-- |
-- |
-- |
-- |
||
18 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
8 |
B |
1 |
2 |
2 |
4 |
1 |
3 |
1 |
3 |
||
C |
2 |
3 |
3 |
6 |
3 |
7 |
4 |
8 |
||
D |
3 |
5 |
5 |
8 |
5 |
9 |
5 |
10 |
||
19 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
8 |
B |
1 |
3 |
1 |
2 |
1 |
4 |
1 |
3 |
||
C |
3 |
5 |
4 |
6 |
2 |
5 |
2 |
4 |
||
D |
-- |
-- |
-- |
-- |
4 |
8 |
5 |
10 |
||
20 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
B |
2 |
3 |
1 |
3 |
3 |
6 |
1 |
2 |
||
C |
3 |
7 |
-- |
-- |
4 |
7 |
2 |
4 |
||
D |
5 |
8 |
-- |
-- |
-- |
-- |
5 |
7 |
||
21 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
5 |
B |
1 |
2 |
2 |
6 |
1 |
5 |
1 |
3 |
||
C |
3 |
5 |
-- |
-- |
2 |
7 |
2 |
7 |
||
D |
4 |
7 |
-- |
-- |
3 |
8 |
4 |
10 |
||
22 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
4 |
B |
1 |
3 |
1 |
2 |
1 |
4 |
1 |
3 |
||
C |
2 |
6 |
2 |
5 |
-- |
-- |
2 |
5 |
||
D |
-- |
-- |
3 |
7 |
-- |
-- |
-- |
-- |
||
23 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
6 |
B |
3 |
5 |
2 |
4 |
2 |
3 |
1 |
3 |
||
C |
-- |
-- |
3 |
8 |
4 |
5 |
2 |
5 |
||
D |
-- |
-- |
5 |
10 |
5 |
6 |
-- |
-- |
||
24 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
7 |
B |
1 |
2 |
2 |
4 |
1 |
3 |
3 |
7 |
||
C |
3 |
8 |
4 |
9 |
4 |
8 |
-- |
-- |
||
D |
-- |
-- |
6 |
14 |
5 |
11 |
-- |
-- |
||
25 |
A |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
8 |
B |
2 |
4 |
1 |
3 |
3 |
7 |
1 |
2 |
||
C |
4 |
8 |
6 |
14 |
4 |
9 |
4 |
9 |
||
D |
5 |
11 |
4 |
10 |
5 |
10 |
6 |
13 |
||
