рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Основне рекурентне співвідношення

Основне рекурентне співвідношення - раздел Философия, ЗАГАЛЬНА ХАРАКТЕРИСТИКА ДИНАМІЧНОГО ПРОГРАМУВАННЯ Оскільки ...

Оскільки і задані ( = 0 ), вибір напрямку прогонки в цьому випадку довільний. Застосуємо алгоритм прямої прогонки.

Нехай мінімальні витрати протягом перших періодів (з першого по k-й включно), за умови, що запас на кінець -ого періоду (на початок (+1)-ого) дорівнює . І нехай в -ому періоді здійснюється поставка в розмірі . (Ми вже з'ясували, що () може приймати значення рівні попиту за ціле число періодів). Це означає, що на кінець (-1)-ого періоду був запас . Тоді вартість поточного кроку складає , а величина

(20)

являє собою мінімальні витрати за періоди від 1-го до включно, за умови, що на кінець -ого періоду є одиниць продукції, а в -ому періоді здійснюється поставка в об'ємі . Вираз (20) – умовно мінімальні витрати для стану при поставці в -ому періоді. Мінімізуємо (20) по всіх можливих значеннях , одержимо рекурентне співвідношення:

(21)

причому ==+-, .

Мета задачі – знайти .

Може здатися, що (як і раніше) на цьому можна зупинитися. Це не так. Розглянемо, як при виборі допустимих значень змінних враховується співвідношення (19). Оскільки =0, то мінімум (21) у силу опуклості вверх j досягається в одній із крайніх точок

= s +(max) або =0 (min)

(= 0) (min) (> 0) (max).

 

 

Тому

 

 

; (22)

 

Розглянемо тепер величину – мінімальні витрати протягом перших () періодів, за умови, що запас на кінець ()-го періоду дорівнює . Для періоду () виконується рівність =0, при цьому об'єм поставки може приймати або мінімально можливе значення (=0) або максимально можливе (= ++). При цьому ==+.

 

. (23)

Підставивши вираз (23) в (22), одержимо:

 
 

 


.

 

 


Аналогічно визначається співвідношення для :

.

Позначимо через мінімальні витрати за перші k періодів за умови, що остання поставка була виконана на початку періоду j і на кінець k-го періоду запас дорівнює :

. (24)

       
 
   
 

 

 


Записавши вирази, аналогічні (22), для , одержимо

(25)

Особлива структура (у розрахунках використовуються тільки величиниз нульовими аргументами) і той факт, що і , дозволяють зробити висновок, що на кожному кроці досить визначати тільки . Значить ОРС (25) набуває такого вигляду:

Розглянемо окремий випадок вигляду функції виробничих витрат . Нехай

Тоді витрати за перші k періодів за умови, що остання поставка була виконана на початку періоду j і на кінець k-го періоду запас дорівнює , визначаються співвідношенням:

 

 


Подальше спрощення в обчислювальній схемі може бути отримано, якщо врахувати наступну обставину. Якщо при обчисленні виявилося, що поставка, за допомогою якої задовольнявся попит (k-1)-ого періоду, надходить у періоді , то й поставка, що задовольняє попит k-го періоду, повинна надійти не раніше періоду . Отже, при обчисленні досить розглядати

,

де має обговорений раніше зміст.

– Конец работы –

Эта тема принадлежит разделу:

ЗАГАЛЬНА ХАРАКТЕРИСТИКА ДИНАМІЧНОГО ПРОГРАМУВАННЯ

ЗАГАЛЬНА ХАРАКТЕРИСТИКА ДИНАМІЧНОГО ПРОГРАМУВАННЯ... Геометрична інтерпретація задач ДП... Приклад багатоетапної операції...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Основне рекурентне співвідношення

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Геометрична інтерпретація задач ДП
  Припустимо, що стан системи характеризується деякою точкою в просторі . Ця

Приклад багатоетапної операції
Керівництво концерну, що складається з k підприємств, складає план інвестицій на n років. На початку цього періоду концерн має у своєму розпорядженні суму в розмірі K од. вартості. Ці кошти на поча

Етап 1. Планування кроку .
Робимо припущення про те, чим може закінчитися крок . Позначимо їх

Етап . Планування кроку 1.
Зазвичай відомо, у якому стані система може перебувати на початку кроку 1. Тому ніяких припущень про це не треба робити (рис. 6). Враховуючи те, що всі останні кроки вже умовно сплановані, управлін

ЗАДАЧА ПРО НАЙКОРОТШИЙ ШЛЯХ
Кожен багатокроковий процес прийняття рішень може бути зведений до задачі знаходження найкоротшого шляху (ЗЗНШ) у спрямованій ациклічній слоїстій мережі (САСМ). Саме з такої точки зору і буд

Приклад застосування алгоритму АЗП по дугах, що виходять
Використовуючи алгоритм зворотньої прогонки по дугах, що виходять, знайти найкоротший шлях з вершини 1 у вершину 10 (рис. 10).  

Завдання для самостійної роботи
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.n=3, = 4 млн. одиниць вартості. Проект

Контрольні завдання
  Розв’язати задачу про оптимальне використання капіталовкладень. Кількість підприємств, сумарний об'єм капіталовкладень і відповідних величин

Постановка задачі
Підприємцеві потрібно визначити число працівників у кожному з наступних періодів. Виробничі завдання для кожного пер

Теоретичне обґрунтування алгоритму зворотньої прогонки для розв’язку задачі про найм робочої сили
Оскільки маємо задачу з фіксованим початком, то рекомендується застосовувати алгоритм зворотньої прогонки. Нехай

Алгоритм ПП розв’язку задачі
Визначимо основні елементи моделі динамічного програмування. Ø Етап відповідає

Приклад розв’язання ЗВРС
Розв’яжемо таку ЗВРС: число місяців =3. Необхідна кількість працівників по місяцях:

Контрольні завдання
Розв’язати задачу про використання робочої сили. Вихідні дані наведені в табл. 8. Таблиця 8 Варі-ант Склад-ність

Адитивність цільової функції і етапи задачі
У задачах ДП цільова функція (ЦФ) повинна мати властивість адитивності: значення критерію, досягнуте за весь

Принцип занурення
У ЗЗНШ потрібно було визначити (якщо застосовується АЗП) - довжину найкоротшого шляху від вершини 1 до вершини

Принцип оптимальності Белмана
Введемо поняття підшляху для спрямованої мережі. Шлях є підшляхом шляху

Постановка задачі
Розглянемо задачу зі скінченною кількістю періодів, нестаціонарним детермінованим попитом, миттєвою поставкою і миттєвим споживанням. Змістовна постановка задачі Нехай маєм

Варіанти розв’язків
Варіантами розв’язків є можливі значення об'ємів поставок ,

Планування кроку 1.
На цьому етапі ми визначаємо мінімальні витрати для першого періоду за умови, що на його кінець запаси повинні бути рівними нулю. Оскільки

Планування кроку 2.
На цьому етапі ми визначаємо мінімальні витрати для перших двох періодів за умови, що на кінець другого запаси повинні бути рівні нулю. У цьому випадку можливі два варіанти розв’язку: - по

Контрольні завдання
Розв’язати задачу управління запасами. Вихідні дані наведені в табл. 11 .Після одержання розв’язку виконати перевірку. Таблиця 11 Ва- рі-

Елементи динамічної моделі
Етап. Етапу ставиться у відповідність планування складу компоненти

Основне рекурентне співвідношення
Нехай – максимальна величина надійності перших

Приклад розв’язання задачі
Нехай прилад складається з компонент,

Контрольні завдання
Розв’язати задачу про надійність. Вихідні дані наведені в табл. 15 .Після одержання розв’язку виконати його перевірку. Таблиця 15 Ва-рі-ант

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги