АНОТАЦІЯ
Пояснювальна записка курсової роботи «гшення задачі про завантаження (Задача про рюкзаку), використовую рекурентні співвідношення В»містить загальні відомості про завдання динамічного програмування, про методи їх вирішення.
ЗМІСТ
1 динамічного програмування ...............................
1.1 Завдання динамічного програмування .............................
1.2 Приклади задач динамічного програмування ..................
1.3 Загальна структура динамічного програмування ...............
2 Задача про завантаження ............................................................
2.1 Загальні відомості ..................................................................
2.2 Рекурентні співвідношення для процедур прямої і зворотного
2.3 Рішення задачі про завантаження ....................................................
2.4 Аналіз чутливості рішення .........................................
СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ ............................
ДОДАТОК А .....................................................................
-->>
ДОДАТОК Б .....................................................................
ДОДАТОК В ......................................................................
6
8
8
12
16
18
18
19
22
25
27
28
36
40
ВСТУП
Робота над даним курсовим проектом дозволяє закріпити знання з предмета В«Математичні методи дослідження операційВ».
У наш час наука приділяє все велику увагу питанням організації і управління, це призводить до необхідності аналізу складних цілеспрямованих процесів під кутом зору їхньої структури й організації. Потреби практики викликали до життя спеціальні методи, які зручно поєднувати під назвою В«дослідження операційВ». Під цим терміном розуміється застосування математичних, кількісних методів для обгрунтування рішень у всіх областях цілеспрямованої людської діяльності.
Метою дослідження операцій є виявлення найкращого способу дії при вирішення тієї чи іншої задачі. Головна роль при цьому відводиться математичному моделюванню. Для побудови математичної моделі необхідно мати суворе уявлення про мету функціонування досліджуваної системи і мати інформацію про обмеження, які визначають область допустимих значень. Мета і обмеження повинні бути представлені у вигляді функцій.
В моделях дослідження операцій змінні, від яких залежать обмеження і цільова функція, можуть бути дискретними (найчастіше цілочисельними) і континуальних (безперервними). У свою чергу, обмеження та цільова функція діляться на лінійні і нелінійні. Існують різні методи вирішення даних моделей, найбільш відомими і ефективними з них є методи лінійного програмування, коли цільова функція і всі обмеження лінійні. Для розв'язання математичних моделей інших типів призначені методи динамічного програмування, цілочисельного програмування, нелінійного програмування, багатокритеріальної оптимізації та методи мережевих моделей.
Практично всі методи дослідження операцій породжують обчислювальні алгоритми, які є ітераційними за своєю природою. Це має на увазі, що завдання вирішується послідовно (ітераційно), коли на кожному кроці (Ітерації) одержуємо рішення, поступово сходяться до оптимального рішення.
Ітераційна природа алгоритмів звичайно приводить до об'ємних однотипним обчислень. У цьому і полягає причина того, що ці алгоритми розробляються, в основному, для реалізації за допомогою обчислювальної техніки.
1 ДИНАМІЧНЕ ПРОГРАМУВАННЯ
1.1 Завдання динамічного програмування
Більшість методів дослідження операцій пов'язано в першу чергу із завданнями цілком певного змісту. Класичний апарат математики виявився малопридатним для вирішення багатьох завдань оптимізації, включають велике число змінних і/або обмежень у вигляді нерівностей. Безсумнівна привабливість ідеї розбивки завдання великої розмірності на підзадачі меншої розмірності, що включають всього по декількох змінних, і подальшого вирішення загальної задачі по частинах. Саме на цій ідеї грунтується метод динамічного програмування.
Динамічне програмування (ДП) являє собою математичний метод, заслуга створення й розвитку якого належить насамперед всього Беллманом. Метод можна використовувати для вирішення дуже широкого кола завдань, включаючи задачі розподілу ресурсів, заміни та управління запасами, завдання про завантаження. Характерним для динамічного програмування є підхід до вирішення задачі по етапах, з кожним з яких асоційована одна керувала змінна. Набір рекурентних обчислювальних процедур, зв'язують різні етапи, забезпечує отримання допустимого оптимального рішення задачі в цілому при досягненні останнього етапу.
Походження назви динамічне програмування , ймовірно, пов'язано з використанням методів ДП вЂ‹вЂ‹в задачах прийняття рішень через фіксовані проміжки часу (наприклад, в задачах управління запасами). Однак методи ДП успішно застосовуються також для вирішення завдань, в яких фактор часу не враховується. З цієї причини більш вдалим видається термін багатоетапне програмування, відображає покроковий характер процесу рішення задачі.
Фундаментальним принципом, покладеним в основу теорії ДП, є принцип оптимальності. По суті, він визначає порядок поетапного вирішення допускає декомпозицію задачі (це більш прийнятний шлях, ніж безпосереднє рішення задачі у вихідній постановці) з допомогою рекурентних обчислювальних процедур.
Динамічне програмування дозволяє здійснювати оптимальне планування керованих процесів. Під В«керованимиВ» розуміються процеси, на хід яких ми можемо в тій чи іншій мірі впливати.
Нехай передбачається до здійснення деякий захід або серія заходів (В«операціяВ»), яка переслідує певну мету. Питається: як потрібно організувати (спланувати) операцію для того, щоб вона була найбільш ефективною? Для того, щоб поставлена ​​задача набула кількісний, математичний характер, необхідно ввести в розгляд деякий чисельний критерій W, яким ми будемо характеризувати якість, успішність, ефективність операції. Критерій ефективності в кожному конкретному випадки вибирається виходячи з цільової спрямованості операції і завдання дослідження (Який елемент управління оптимізується і для чого).
Сформулюємо загальний принцип, що лежить в основі розв'язання всіх задач динамічного програмування (В«принцип оптимальностіВ»):
В«Яке б не був стан системи S перед черговим кроком, треба вибрати керування на цьому кроці так, щоб виграш на даному кроці плюс оптимальний виграш на всіх наступних кроках був максимальним В».
Динамічне програмування - це поетапне планування багатокрокового процесу, при якому на кожному етапі оптимізується тільки один крок. Управління на кожному кроці повинне вибиратися з урахуванням всіх його наслідків в майбутньому.
При постановці завдань динамічного програмування слід керуватися такими принципами:
1. Вибрати параметри (фазові координати), що характеризують стан S керованої системи перед кожним кроком.
2. Розчленувати операцію на етапи (кроки).
3. З'ясувати набір крокових управлінь x i для кожного кроку і накладаються на них обмеження.
4. Визначити який виграш приносить на i-му кроці управління x i , якщо перед цим система була в стані S, тобто записати В«Функцію виграшуВ»:
.
5. Визначити, як змінюється стан S системи S під впливом управління x i на i-му кроці: воно переходить в новий стан
. (1.1)
6. Записа...
