Динамічне програмування (завдання про завантаження)

АННОТАЦИЯ.

Пояснювальна записка курсової роботи «Рішення завдання із завантаженням (завдання про рюкзаку), використовую рекуррентные співвідношення» містить загальні інформацію про завданнях динамічного програмування, про методи їх решения.

|ВВЕДЕНИЕ… |6 | |1 ДИНАМІЧНИЙ ПРОГРАМУВАННЯ… |8 | |Завдання динамічного програмування… |8 | |Приклади завдань динамічного програмування… |12 | |Загальна структура динамічного програмування… |16 | |2 ЗАВДАННЯ Про ЗАГРУЗКЕ… |18 | |2.1 Загальні відомості… |18 | |2.2 Рекуррентные співвідношення для процедур прямий і зворотної | | |прогонки… |19 | |2.3 Рішення завдання із завантаженням… |22 | |2.4 Аналіз чутливості рішення… |25 | |СПИСОК ВИКОРИСТАНИХ ИСТОЧНИКОВ… |27 | |ДОДАТОК А… |28 | |ДОДАТОК Б… |36 | |ДОДАТОК У… |40 |.

Робота над даним курсовим проектом дозволяє закріпити знання з предмета «Математичні методи дослідження операций».

Нині наука приділяє все велику увагу питанням організації та управління, усе веде до потреби аналізу складних цілеспрямованих процесів під кутом зору їх структури та організації. Потреби практики покликали до життя спеціальні методи, які зручно об'єднувати під назвою «дослідження операцій». Під цим терміном розуміється застосування математичних, кількісних методів для обгрунтування рішень переважають у всіх областях цілеспрямованої людської деятельности.

Метою дослідження операцій є виявлення найкращого способу дії при виконання чи іншого завдання. Головна роль у своїй відводиться математичному моделюванню. Для побудови математичну модель необхідно мати суворе уявлення про мету функціонування досліджуваної системи та мати інформацію про обмеження, які визначають область допустимих значень. Мету й обмеження мають представлені в вигляді функций.

У моделях дослідження операцій перемінні, від яких залежить обмеження і цільова функція, може бути дискретними (найчастіше целочисленными) і континуальными (безперервними). Натомість, обмеження і цільова функція діляться на лінійні і нелинейные. Існують різні на методи вирішення даних моделей, найвідомішими і ефективними є методи лінійного програмування, коли цільова функція і все обмеження лінійні. Аби вирішити математичних моделей інших типів призначені методи динамічного програмування, целочисленного програмування, нелінійного програмування, многокритериальной оптимізації та фізичні методи мережевих моделей.

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

Итерационная природа алгоритмів зазвичай призводить до об'ємним однотипним обчисленням. У цьому полягає причина те, що ці алгоритми розробляються, переважно, для реалізації з допомогою обчислювальної техники.

1 ДИНАМІЧНИЙ ПРОГРАММИРОВАНИЕ.

1. Завдання динамічного программирования.

Більшість методів дослідження операцій пов’язано першу чергу, з завданнями цілком певного змісту. Класичний апарат математики виявився малопридатним на вирішення багатьох завдань оптимізації, які включають велика кількість змінних і/або обмежень у вигляді нерівностей. Незаперечна ідеї розбивки завдання великий розмірності на подзадачи меншою розмірності, які включають лише кількох змінних, і наступного рішення спільної справи частинами. На цієї ідеї грунтується метод динамічного программирования.

Динамічний програмування (ДП) є математичний метод, заслуга створення та розвитку належить передусім Беллману. Метод можна використовуватиме рішення дуже кола завдань, включаючи завдання розподілу ресурсів, заміни та управління запасами, завдання із завантаженням. Характерним для динамічного програмування є підхід до вирішення завдання етапах, з кожним із яких асоціюється одна керована змінна. Набір рекуррентных обчислювальних процедур, що пов’язують різні етапи, забезпечує отримання припустимого оптимального виконання завдання загалом під час досягнення останнього этапа.

Походження назви динамічний програмування, мабуть, пов’язано з методів ДП в завданнях прийняття рішень через фіксовані часові відтинки (наприклад, в завданнях управління запасами). Проте методи ДП успішно застосовуються також і вирішення завдань, у яких чинник часу не враховується. Через це кращим представляється термін многоэтапное програмування, який відбиває пошаговый характер процесу рішення задачи.

Фундаментальним принципом, що пасує основою теорії ДП, є принцип оптимальності. Фактично, він визначає порядок поетапного рішення допускає декомпозицію завдання (це як прийнятний шлях, ніж безпосереднє вирішення завдання в вихідної постановці) з допомогою рекуррентных обчислювальних процедур.

Динамічний програмування дозволяє здійснювати оптимальне планування керованих процесів. Під «керованими» розуміються процеси, перебіг яких ми можемо у тому або інший ступеня влиять.

Нехай передбачається для реалізації деяке захід чи серія заходів («операція»), яка має певну мета. Питається: як потрібно організувати (спланувати) операцію у тому, щоб у неї найефективнішою? А, щоб поставлена завдання придбала кількісний, математичний характер, необхідно провести в розгляд певний чисельний критерій W, яких ми будемо характеризувати якість, успішність, ефективність операції. Критерій ефективності у кожному конкретному випадки вибирається з цільової спрямованості операції, і завдання дослідження (який елемент управління оптимізується й у чего).

Сформулюємо загальний принцип, лежить у його основі всіх завдань динамічного програмування («принцип оптимальности»):

«Яке було стан системи P. S перед черговим кроком, треба вибрати управління у цьому кроці те щоб виграш цьому кроці плюс оптимальний виграш усім наступні кроки був максимальным».

Динамічний програмування — це поетапне планування многошагового процесу, у якому кожному етапі оптимізується лише крок. Управління кожному кроці має вибиратися з урахуванням інтересів усіх його наслідків в будущем.

При постановці завдань динамічного програмування слід керуватися такими принципами:

1. Вибрати параметри (фазові координати), що характеризують стан P. S керованої системи перед кожним шагом.

2. Розчленувати операцію на етапи (шаги).

3. З’ясувати набір шаговых управлінь xi кожному за кроку та що накладалися ними ограничения.

4. Визначити який виграш приносить на i кроці управління xi, якщо які були систему було може P. S, тобто. записати «функцію выигрыша»:

[pic].

5. Визначити, як змінюється стан P. S системи P. S під впливом управління xi на i кроці: воно перетворюється на нове состояние.

[pic]. (1.1).

6. Записати основне рекуррентное рівняння динамічного програмування, лист про умовний оптимальний виграш Wi (S).

(починаючи з i-го кроку та остаточно) через відому функцию.

Wi+1(S):

[pic]. (1.2).

Цьому виграшу відповідає умовне оптимальне управління на 1-му кроці xi (S) (причому у вже відому функцію Wi+1(S) треба замість P. S підставити змінений стан [pic]).

7. Виробити умовну оптимізацію останнього (m-го) кроку, переймаючись гамою станів P. S, із яких за крок дістатися кінцевого стану, вираховуючи кожного з них умовний оптимальний виграш за такою формулою [pic].

8. Виробити умовну оптимізацію (m-1)-го, (m-2)-го тощо. кроків із формулі (1.2), вважаючи у ній i=(m-1); INSERT INTO `ref` (`id_predmet`, `name_predmet`, `id_ref`, `name_ref`, `text_ref`) VALUES (m-2),…, й у кожного з кроків вказати умовне оптимальне управління xi (S), у якому максимум достигается.

Зауважимо, що й стан системи в початковий момент відомо (але це зазвичай буває), то, на перший крок варіювати стан системи не потрібно — прямо знаходимо оптимальний виграш для даного початкового стану S0. Це і оптимальний виграш за операцию.

[pic].

9. Виробити безумовну оптимізацію управління, «читаючи» відповідні рекомендації кожному кроці. Взяти знайдене оптимальне управління першою кроці [pic]; змінити стан системи з формулі (1.1); для знову знайденого стану знайти оптимальне управління другою кроці х2* тощо. до конца.

Дані етапи розглядалися для аддитивных завдань, у яких виграш за всю операцію дорівнює сумі виграшів на окремих кроках. Метод динамічного програмування застосуємо також завданням з так званим «мультипликативным» критерієм, у яких вид произведения:

[pic].

(за умови що виграші wi позитивні). Ці завдання вирішуються точно так ж, як завдання з аддитивным критерієм, з тим єдиною різницею, що у основному рівнянні (1.2) замість знака «плюс» ставиться знак «множення»: [pic].

1.2 Приклади завдань динамічного программирования.

Завдання планування робочої силы:

За виконання деяких проектів кількість робітників, необхідні виконання будь-якого проекту, регулюється шляхом їх наймання та звільнення. Оскільки як наймання, і звільнення робочих пов’язані з додатковими витратами, необхідно визначити, як повинна регулюватися чисельність робітників у період реалізації проекта.

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

Якщо xi — кількість працівників протягом i-го тижня, можливі витрати два види: 1) С1(xibi)-затраты, пов’язані із необхідністю утримувати надлишок xi — bi робочої сили й 2) С2(xixi-1)-затраты, пов’язані із необхідністю додаткового найму (xixi-1) рабочих.

Елементи моделі динамічного програмування визначаються наступним образом:

1. Етап й представляється порядковим номером тижня й, і=1,2,…n.

2. Варіантами рішення на і-ом етапі є значення xi — кількість працівників протягом і недели.

3. Станом на і-м етапі є xi-1 — кількість працівників протягом (і-1) -і тижня (этапа).

Рекуррентное рівняння динамічного програмування представляється в виде.

[pic] де [pic].

Обчислення розпочинаються з етапу n при xn=bn і закінчуються на етапі 1.

Завдання заміни оборудования:

І чим довше механізм експлуатується, то вище видатки його обслуговування може й нижче його продуктивність. Коли термін експлуатації механізму сягає певного рівня, може виявитися більш вигідною його заміна. Завдання заміни устаткування, в такий спосіб, зводиться до визначенню оптимального терміну експлуатації механизма.

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

Означимо через r (t) і c (t) прибуток за експлуатації t-летнего механізму протягом року й видатки його обслуговування цей самий період. Далі нехай s (t) — вартість продажу механізму, який експлуатувався t років. Вартість придбання нового механізму залишається незмінною протягом всіх років і дорівнює l.

Елементи моделі динамічного програмування таковы:

1. Етап й представляється порядковим номером року й, і=1,2,…n.

2. Варіантами рішення на і-м етапі (тобто. для і-ого року) є альтернативи: продовжити експлуатацію чи замінити механізм на початку і-ого года.

3. Станом на і-м етапі є термін експлуатації t (вік) механізму до початку і-ого года.

Нехай fi (t)-максимальная прибуток, отримувана упродовж свого від й до n при умови, що спочатку і-ого року є механізм t-летнего возраста.

Рекуррентное рівняння має наступний вид:

[pic].

(1)-если експлуатувати механизм,.

(2)-если замінити механизм.

Завдання инвестирования:

Припустимо, що спочатку кожного з таких n років необхідно зробити інвестиції P1, P2,…, Pn відповідно. Ви маєте можливість вкласти капітал удвічі банку: перший банк виплачує річний складний відсоток r1, а другий — r2. Для заохочення депозитів обидва банки виплачують нові інвестори премії як відсотка від вкладеною суммы.

Преміальні змінюються у рік до року, й у і-ого року рівні qi1 і qi2 в першому та другому банках відповідно. Вони виплачуються під кінець року, на протязі якого зроблено внесок, і може бути інвестовано одного з двох банків наступного року. Це означає, що лише зазначені відсотки, й нові гроші не можуть бути інвестовано одного з двох банків. Розміщений у банку внесок повинен перебуває до кінця аналізованого періоду. Необхідно розробити стратегію інвестиції ми такі n лет.

Елементи моделі динамічного програмування следующие:

1. Етап й представляється порядковим номером року й, і=1,2,…n.

2. Варіантами рішення на і-м етапі (для і-ого року) є суми li и[pic]инвестиций уперше і другий банк соответственно.

3. Станом xi на і-м етапі є сума грошей початку і-ого року, які можна инветсированы.

Зауважимо, що у визначенню [pic]=xi-li. Следовательно,.

[pic] де і=2,3,…n, x1=P1. Сума грошей xi, які можна інвестовано, включає лише нові гроші й преміальні відсотки інвестиції, зроблені протягом (і-1)-го года.

Нехай fi (xi) — оптимальна сума іноземних інвестицій для інтервалу від і-го до nго року за умови, що спочатку і-го року є грошова сума xi. Далі позначимо через si накопичену суму до кінця n-го року за умови, що li і (xi-li)-объемы інвестицій протягом і-го року у не перший і другий банк відповідно. Позначаючи [pic], і=1,2, ми можемо сформулювати завдання наступному виде.

Максимізувати z=s1+s2+…+sn, где.

[pic].

Оскільки преміальні за енну кількість рік є частиною накопиченої грошової суми від інвестицій, в висловлювання для sn додано qn1 і qn2.

Отже, у разі рекуррентное рівняння для зворотної прогонки в алгоритмі динамічного програмування має вид.

[pic] де xi+1 виражається через xi відповідно до наведеної вище формулою, а fn+1(xn+1)=0.

1.3 Загальна структура динамічного программирования.

Відшукування оптимальної стратегії прийняття набору послідовних рішень, переважно випадках, виробляється так: спочатку здійснюється вибір останнього у часі рішення, потім під час руху в напрямі, зворотному перебігу часу, вибираються й інші рішення до исходного.

Задля реалізації такого методу необхідно з’ясувати все ситуації, в яких може статися вибір останнього рішення. Зазвичай умови, в яких приймають рішення, називають «станом» системи. Стан системи — це опис системи, що дозволяє, враховуючи майбутні рішення, б його поведінка. Не треба з’ясовувати, як виникло то мул іншу сутність чи які були попередні рішення. Це дозволяє послідовно вибирати лише одному рішенню у кожний час. Незалежно від цього, відшукують оптимальні рішення з допомогою табличного методу і наступного пошуку чи аналітичним шляхом, зазвичай швидше, і вигідніше виробляти вибір за одним рішенню водночас часу, переходячи потім ось до чого моменту тощо. На жаль, в такий спосіб можна досліджувати в усіх процеси прийняття рішень. Необхідною умовою застосування методу динамічного програмування є аддитивность цін всіх рішень, і навіть незалежність майбутніх результатів від передісторії того чи іншого состояния.

Якщо рішень дуже велике, можна побудувати відносні оцінки станів те щоб оцінки, відповідальні кожної парі послідовних рішень, різнилися одне від друга на постійну величину, представляє собою середній «дохід» влади на рішення. Можна виконувати дисконтирование доходів з майбутніх рішень. Необхідність у тому іноді з’являється у тому разі, коли рішення приймаються рідко, скажімо разів на рік. Тоді не потрібно розглядати послідовно 1,2,3…решения, щоб домогтися рішення з великим номером. Натомість можна безпосередньо оперувати функціональним рівнянням, що, зазвичай, дає істотну вигоду з погляду скорочення обсягу вычислений.

2 ЗАВДАННЯ Про ЗАГРУЗКЕ.

2.1 Загальні сведения.

Завдання із завантаженням — це завдання про раціональної завантаженні судна (літака, автомашини тощо.), що має обмеження з обсягу чи вантажопідйомності. Кожен поміщений на судно вантаж приносить певну прибуток. Завдання у визначенні завантаження судна такими вантажами, які приносять найбільшу сумарну прибыль.

Рекуррентное рівняння процедури зворотної прогонки виводиться задля спільної завдання завантаження судна вантажністю W предметів (вантажів) n найменувань. Нехай mi-количество предметів і-го найменування, які підлягають завантаженні, ri-прибыль, яку приносить один завантажений предмет і-го найменування, wi-вес одного предмета і-го найменування. Загальна завдання має вид наступній целочисленной завдання лінійного программирования.

Максимізувати z=r1m1+r2m2+…+rnmn. за умови, що w1m1+w2m2+…+wnmn [pic] W, m1, m2,…, mn [pic] 0 і целые.

Три елемента моделі динамічного програмування визначаються наступним образом:

1. Етап й ставлять у відповідність предмета і-го найменування, і=1,2,…n.

2. Варіанти рішення на етапі й описуються кількістю mi предметів і-го найменування, які підлягають завантаженні. Відповідна прибуток дорівнює rimi. Значення mi укладено не більше від 0 до [W/wi], где.

[W/wi] - ціла частина числа W/wi.

3. Стан xi на етапі й висловлює сумарна вага предметів, рішення про навантаженні яких ухвалені етапах і,і+1,…n. Цю ухвалу відбиває те що, що обмеження з вазі єдиний, яке пов’язує n етапів вместе.

Нехай fi (xi)-максимальная сумарна прибуток за етапів і,і+1,…, n при заданому стані xi. Найпростіше рекуррентное рівняння визначається за допомогою наступній двухшаговой процедуры.

Крок 1. Висловимо fi (xi) як функцію fi+1(xi+1) в виде.

[pic] де fn+1(xn+1)=0.

Крок 2. Висловимо xi+1 як функцію xi для гарантії те, що ліва частина останнього рівняння є функцією лише xi. За визначенням xi-xi+1 є вагу, завантажений на етапі й, тобто. xi-xi+1=wimi чи xi+1=xi-wimi. Отже, рекуррентное рівняння набуває наступний вид:

[pic].

2.2 Рекуррентные співвідношення для процедур прямий і зворотної прогонки.

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

Цей надзвичайно простий приклад наводиться у тому, щоб наочно продемонструвати переваги алгоритму зворотної прогонки проти алгоритмом прямий прогонки. Обчислювальні схеми процедур прямий і зворотної прогонки мають різної ефективністю у разі, коли етапи моделі нумеруються у певній спеціальному порядку. Така ситуація має місце у приводимом прикладі, де етап j ставлять у відповідність року j, т. е. етапи розглядати в хронологічному порядке.

спочатку побудуємо рекуррентные співвідношення для процедур прямий і зворотної прогонки, та був проведемо порівняння двох обчислювальних схем. Важливе різницю між двома формулюваннями безпосередньо випливає з визначення состояния.

Означимо кількості залишених і проданих в j-м року овець через xj і yj, відповідно. Поклавши Zj,=xj+yj. З умов завдання слід, що z1=2×0=2k,.

zj=2xj-1,j=l, 2, …, n.

Стан на етапі j можна описати з допомогою перемінної zj, яка висловлює кількість наявних до кінця етапу j овець задля розподілення на етапах j+1, j+2, …, n, чи з допомогою перемінної xj, яка висловлює кількість наявних до початку етапу j+1 овець, обумовлене прийнятими на етапах 1,2,…, j рішеннями. Перше визначення орієнтоване на побудова рекуррентного соотношения для процедури зворотної прогонки, тоді як друге визначення призводить до використанню алгоритму прямий прогонки.

Алгоритм зворотної прогонки.

Означимо через fi (zi) максимальну прибуток, отримувану на етапах j, j+1,…, n, при заданому zj. Рекуррентное співвідношення має наступний вид:

[pic].

Зауважимо, що yj і zj — неотрицательные цілі числа. З іншого боку, уj (кількість овець, проданих наприкінці періоду j) має менше або дорівнює zj. Верхній кордоном для значень zj, є величина 2jk (де kвихідний розмір стада), що відповідає відсутності продажи.

Алгоритм прямий прогонки.

Означимо через gj (xj) максимальну прибуток, отримувану на етапах 1,2,…, j при заданому xj, (де xj— розмір стада до початку етапу J+1). Рекуррентное співвідношення записується наступного виде:

[pic].

[pic] - целое.

Порівняння двох формулювань показує, що вистава xj-1 через xj створює суттєвіші перепони на шляху обчислень, ніж уявлення zj+1 через zj.

Заміни xj-1=(xj+yj)/2 мається на увазі целочисленность правій частині, тоді як у рівність zj+1=2(zj-yj) таку вимогу не накладається. У такий спосіб разі процедури прямий прогонки значення yj і xj, пов’язані неравенством.

Yj.