Приклад застосування алгоритму АЗП по дугах, що виходять
Приклад застосування алгоритму АЗП по дугах, що виходять - раздел Философия, ЗАГАЛЬНА ХАРАКТЕРИСТИКА ДИНАМІЧНОГО ПРОГРАМУВАННЯ Використовуючи Алгоритм Зворотньої Прогонки По Дугах, Що Виходять, Знайти Най...
Використовуючи алгоритм зворотньої прогонки по дугах, що виходять, знайти найкоротший шлях з вершини 1 у вершину 10 (рис. 10).
При застосуванні алгоритму зворотньої прогонки, першим планується крок 4 (останній крок). Вважаємо, що (довжина найкоротшого шляху від вершини 10 до самої себе).
Планування кроку 4. Виділимо всі можливі стани, які можуть мати місце на початку кроку 4, тобто визначимо множину : . Для цих вершин знайдемо умовні оптимальні розв’язки й відповідно, де – довжина найкоротшого шляху на кроці 4 (на кроках від 4-го до (= 4)-го включно), за умови, що на початку кроку 4 система перебуває в стані (вершині) 8. Аналогічно визначається . Відповідно до виразу (1) отримаємо:
; ;
; .
!
У цьому випадку, з кожної вершини виходить тільки по одній дузі (говоримо, що в кожному стані можливий тільки один варіант розв’язку). Тобто маємо “вибір без вибору”. Така ситуація завжди має місце, якщо в останньому слої є тільки одна вершина (у нас - вершина 10).
Заповнюємо таблицю таким чином:
Крок
Можливі стани на початку кроку (вершини )
Варіанти розв’язків
Вартість розв’язку
Умовний оптимальний розв’язок
Вихідна
дуга
Наступна
вершина
r
1+0=1
10
s
4+0=4
4
У стовпчику вказується вершина , перехід у яку з вершини забезпечує мінімум виразу (1). У стовпчику f* вказується значення цього мінімуму – довжина найкоротшого шляху з вершини до останньої вершини 10.
Планування кроку 3. На початку цього кроку система може перебувати в одному з трьох станів (вершин): 5, 6 й 7. Якщо система, наприклад, перебуває в стані (вершині) 5 , то з нього можна вийти по дугах і (і потрапимо у вершини 8 або 9 відповідно). Тоді для стану 5умовний оптимальний розв’язок знаходиться таким чином:
,
– тобто, якщо з вершини 5 перейти у вершину 8, то досягається мінімум виразу (1).
!
Згадаємо одне з основних положень ДП: „в процесі поетапного планування управління на кожному кроці повинно обиратися з урахуванням його майбутніх наслідків”. У нашому випадку це здійснюється через урахування величин і .
Для стану =5таблицю заповнюємо таким чином:
k
7+1=8
l
5+4=9
Отримали: = 8,=8.
Аналогічні дії виконуються і для випадків, коли на початку кроку 3 система перебуває в станах 6 або 7:
, .
, .
m
3+1=4
n
4+4=8
p
7+1=8
q
1+4=5
Аналогічно плануються кроки 2 і 1.
Повний процес розв’язку задачі наведено у таблиці 1:
Таблиця 1
Крок
Можливі стани на початку кроку (вершини )
Варіанти розв’язків
Вартість розв’язку
Умовний оптимальний розв’язок
Вихідна
дуга
Наступна
вершина
r
1+0=1
10
9
s
4+0=4
k
7+1=8
l
5+4=9
m
3+1=4
n
4+4=8
7
p
7+1=8
q
1+4=5
d
10+8=18
e
12+4=16
f
5+8=13
3
g
10+4=14
h
7+5=12
i
15+4=19
j
13+5=18
a
2 + 16=18
1
b
5 + 12=17
3
c
3 +18=21
Порядок формування відповіді (найкоротшого шляху) показаний стрілками.
Відповідь: найкоротший шлях: 1-3-7-9-10, довжина шляху 17.
Приклад багатоетапної операції
Керівництво концерну, що складається з k підприємств, складає план інвестицій на n років. На початку цього періоду концерн має у своєму розпорядженні суму в розмірі K од. вартості. Ці кошти на поча
Етап . Планування кроку 1.
Зазвичай відомо, у якому стані система може перебувати на початку кроку 1. Тому ніяких припущень про це не треба робити (рис. 6). Враховуючи те, що всі останні кроки вже умовно сплановані, управлін
ЗАДАЧА ПРО НАЙКОРОТШИЙ ШЛЯХ
Кожен багатокроковий процес прийняття рішень може бути зведений до задачі знаходження найкоротшого шляху (ЗЗНШ) у спрямованій ациклічній слоїстій мережі (САСМ). Саме з такої точки зору і буд
Завдання для самостійної роботи
1. Перетворити ациклічну мережу (рис. 11) до слоїстої. Розв’язати задачу, застосувавши алгоритм зворотної прогонки.
Планування кроку 1.
Виділимо всі можливі стани, які можуть мати місце наприкінці кроку 1, тобто визначимо множину :
Планування кроку 2.
Наприкінці цього кроку система може перебувати в одному з трьох станів (вершин): 5, 6 й 7. У стан 5 можна потрапити по дугах
Відмінності алгоритмів прямої і зворотної прогонок
Вибір того чи іншого напрямку розрахунків (що співпадає з напрямком мережі або є зворотнім до нього) залежить від постановки вихідної задачі ЗНШ. Розглянемо чотири можливі ситуації, що впливають на
Контрольні завдання
Розв’язати задачу знаходження найкоротшого шляху від вершини A до вершини N у спрямованій ациклічній мережі, зображеній на рис. 18. Довжини дуг наведені у табл. 3.
Побудова рекурентного співвідношення задачі 4.1.1
Дана задача, по суті, не є часовою. Але її можна звести до багатокрокового процесу прийняття рішень, якщо припустити, що різні продукти повинні вироблятися один за одним, тобто:
на першому
Побудова рекурентного співвідношення задачі 4.1.2
У даному випадку в якості ресурсу, що розподіляється, виступають кошти, що вкладаються в модернізацію. При такій змістовній інтерпретації задачу називають задачею про оптимальне використання кап
Приклад розв’язання ЗОВК
Нехай фірма має n=3 дочірніх підприємств, на модернізацію цих трьох підприємств виділено = 6 млн. одиниць вартості.
Планування кроку 1.
Вважається, що на цьому етапі приймається рішення про модернізацію першого підприємства. Для цього можуть бути використані кошти в кількості від 0 до 6 (оскільки в нашому випадку
Планування кроку 2.
На цьому кроці приймається рішення щодо модернізації підприємств 1 і 2. Для цього можуть бути використані кошти в кількості від 0 до
Планування кроку 3.
На цьому етапі приймається рішення про модернізацію всіх трьох підприємств (1, 2 і 3). Для цього фірма виділила кошти в кількості
Контрольні завдання
Розв’язати задачу про оптимальне використання капіталовкладень. Кількість підприємств, сумарний об'єм капіталовкладень і відповідних величин
Постановка задачі
Підприємцеві потрібно визначити число працівників у кожному з наступних періодів. Виробничі завдання для кожного пер
Планування кроку 1.
На цьому етапі ми визначаємо мінімальні витрати для першого періоду за умови, що на його кінець запаси повинні бути рівними нулю. Оскільки
Планування кроку 2.
На цьому етапі ми визначаємо мінімальні витрати для перших двох періодів за умови, що на кінець другого запаси повинні бути рівні нулю. У цьому випадку можливі два варіанти розв’язку:
- по
Контрольні завдання
Розв’язати задачу управління запасами. Вихідні дані наведені в табл. 11 .Після одержання розв’язку виконати перевірку.
Таблиця 11
Ва-
рі-
Контрольні завдання
Розв’язати задачу про надійність. Вихідні дані наведені в табл. 15 .Після одержання розв’язку виконати його перевірку.
Таблиця 15
Ва-рі-ант
Хотите получать на электронную почту самые свежие новости?
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
(довжина найкоротшого шляху від вершини 10 до самої себе).
: 
. Для цих вершин знайдемо умовні оптимальні розв’язки 
й 
відповідно, де 
= 4)-го включно), за умови, що на початку кроку 4 система перебуває в стані (вершині) 8. Аналогічно визначається 
; 
;
; 
(вершини 
)
10
4
вказується вершина 
, перехід у яку з вершини 
забезпечує мінімум виразу (1). У стовпчику f* вказується значення цього мінімуму – довжина найкоротшого шляху з вершини 
(і потрапимо у вершини 8 або 9 відповідно). Тоді для стану 5умовний оптимальний розв’язок знаходиться таким чином:
,
– тобто, якщо з вершини 5 перейти у вершину 8, то досягається мінімум виразу (1).
=8.
, 
, 
.
)
10
9
7
3
1
Новости и инфо для студентов