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

Размещено на http://www.allbest.ru

Зміст

Вступ

РОЗДІЛ 1. Динамічне програмування

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

1.2Метод динамічного програмування

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

РОЗДІЛ 2. Задача ОПТИМАЛЬНОГО завантаження

2.1 Загальні відомості

2.2 Постановка задачі оптимального завантаження

2.3 Приклад розв'язку задачі про завантаження

Висновки

Список використаних джерел

Додаток 1

Додаток 2

Додаток 3

моделювання динамічне програмування вантаж

ВСТУП

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

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

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

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

Задача про завантаження є класичним представником методу динамічного програмування, в якій обмежений ресурс розподіляється між кінцевим числом видів (економічної) діяльності. При цьому метою є максимізація відповідної функції прибутку. У таких моделях визначається стан на кожному: станом на етапі і є сумарна кількість ресурсів, що розподіляється на етапах і,і+1,…,n.

Об'єкт дослідження - математичне моделювання засобами динамічного програмування.

Предмет дослідження - дослідження задачі оптимального завантаження.

Мета - дослідити можливості оптимізації економічних процесів і явищ засобами динамічного програмування.

Основні завдання:

1. вивчити основні поняття динамічного програмування;

2. виконати постановку задачі динамічного програмування;

3. виконати постановку задачі оптимального завантаження;

4. навести приклади розв'язування задач економічного змісту.

Методологічна основа дослідження - праці Є. С Вентцеля, Ю.Н.Кузнецова, Р.Беллмана, Т.Таха та інших.

Методи дослідження - аналіз спеціалізованої літератури, методи математичного моделювання, методи оптимізації.

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

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

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



розділ 1.Динамічне програмування

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

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

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

Означення 1. Процес називається керованим, якщо можна в деякій мірі

впливати на його хід.

Означення 2. Керуванням називається сукупність рішень, які приймаються на кожному етапі процесу [1, с.271].

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

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

Є деяка керована операція (цілеспрямована дія), що розподіляється (природно або штучно) на m кроків - етапів. На кожному кроці здійснюється розподіл і перерозподіл, які беруть участь в операції з метою поліпшення її результату в цілому. Ці розподіли в динамічному програмуванні називаються управліннями операцією і позначаються буквою . Ефективність операції в цілому оцінюється тим же показником, що і ефективність її управління .

При цьому ефективність управління залежить від усієї сукупності управлінь на кожному кроці операції:

(1.1)

Управління, при якому показник досягає максимуму, називається оптимальним управлінням. Оптимальне управління позначається буквою .

Оптимальне управління багатокрокового процесу складається із сукупності оптимальних крокових управлінь:

(1.2)

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

У більшості практичних задач показник ефективності операції в цілому являє собою суму ефективності дій на всіх етапах (кроках) операції:

де - ефективність операції на -му кроці. При цьому у випадку оптимального управління

Суть розв'язання задач динамічного програмування полягає в наступному:

- Оптимізація проводиться методом послідовних наближень (ітерацій) в два кола; спочатку від останнього кроку операції до першого, а потім навпаки - від першого до останнього;

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

- Так триває до першого кроку, але оскільки перший крок не має попереднього, то отримане для нього умовне оптимальне управління втрачає свій умовний характер і стає просто оптимальним управлінням, яке ми шукаємо;

- Друге коло оптимізації починається з першого кроку, для якого оптимальне управління відомо.

Маючи для всіх кроків після другого кола умовні оптимальні управління, знаємо, що необхідно робити на кожному наступному кроці. Це дає нам можливість послідовно переходити від умовних до оптимальних управлінням для всіх наступних кроків, що забезпечує оптимальність операції в цілому [10, с.104].

1.2 Метод динамічного програмування

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

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

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

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

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

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

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

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

Динамічне програмування - це поетапне планування багатокрокового процесу, при якому на кожному етапі оптимізується тільки один крок [8, с.11]. Управління на кожному кроці має вибиратися з урахуванням усіх його наслідків у майбутньому.

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

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

2. Розділити операцію на етапи (кроки).

3. З'ясувати набір крокових управлінь для кожного кроку і як накладаються на них обмеження.

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

. (1.5)

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

. (1.6)

6. Записати основне рекурентне рівняння динамічного програмування, що виражає умовний оптимальний виграш (починаючи з i-го кроку і до кінця) через вже відому функцію:

. (1.7)

Цьому виграшу відповідає умовне оптимальне керування на i-му кроці (причому у вже відому функцію треба замість S підставити змінений стан )

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

(1.8)

8. Здійснити умовну оптимізацію -го, -го і т.д. кроків за формулою (1.7), коли і для кожного з кроків вказати умовне оптимальне управління , при якому максимум досягається.

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

(1.9)

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

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

(1.10)

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

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

Обчислення в ДП виконуються рекуррентно в тому сенсі, що оптимальний розв'язок однієї підзадачі використовується в якості вихідних даних наступної. Розв'язавши останню підзадачу, ми отримаємо оптимальний розв'язок початкової задачі. Спосіб виконання рекурентних обчислень залежить від того, як виконується декомпозиція початкової задачі. Зокрема, підзадачі зазвичай пов'язані між собою деякими загальними обмеженнями. Якщо здійснюється перехід від однієї підзадачі до іншої, то повинні враховуватися ці обмеження [5, с.412].

Покажемо це на прикладі задачі про найкоротший шлях.

Припустимо, необхідно вибрати найкоротший шлях між двома містами. Мережа доріг, показана на мал. 1, показує можливі маршрути між початковим містом, що перебуває у вузлі 1, і кінцевим пунктом, який знаходиться у вузлі 7. Маршрути проходять через проміжні міста, позначені на мережі вузлами з номерами 2-6.



Малюнок 1

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

Щоб розв'язати цю задачу за допомогою методів динамічного програмування, спочатку розділимо її на етапи. Вертикальні пунктирні лінії на мал.2 окреслюють три етапи задачі. Далі виконуються обчислення для кожного етапу окремо.

Малюнок 2

Спільна задача полягає в обчисленні найкоротших (поступово накопичуваних) відстаней до всіх вершин етапу з подальшим використанням цих відстаней в якості початкових даних для наступного етапу. Розглядаючи вузли, що відносяться до першого етапу, помічаємо, що кожен з вузлів 2,3,4 пов'язаний з початковим вузлом 1 єдиною дугою (мал.2). Отже, для першого етапу маємо наступне.

Етап 1. Результати.

Найкоротший шлях до вузла 2 дорівнює 7 км (з вузла 1);

Найкоротший шлях до вузла 3 дорівнює 8 км (з вузла 1);

Найкоротший шлях до вузла 4 дорівнює 5 км (з вузла 1).

Далі переходимо до другого етапу для обчислення найкоротших (накопичених) відстаней до вузлів 5 і 6. Розглядаючи вузол 5 першим. з мал.2 помічаємо, що є три можливих маршрути, за якими можна досягти вузла 5, а саме (2,5), (3,5) і (4,5). Ця інформація разом з найкоротшими відстанями до вузлів 2,3,4 визначає найкоротший (накопичену) відстань до вузла 5 таким чином.

Аналогічно для вузла 6 маємо:

Етап 2. Результати.

Найкоротший шлях до вузла 5 дорівнює 12 км (з вузла 4);

Найкоротший шлях до вузла 6 дорівнює 17 км (з вузла 3).

Останнім кроком є третій етап. Кінцевого вузла 7 можна досягти як із вузла 5, так і 6. Використовуючи результати етапу 2 і відстані від вузла 5 і 6 до вузла 7, отримуємо наступне.

Етап 3. Результати.

Найкоротший шлях до вузла 7 дорівнює 21 км (з вузла 5).

Наведені обчислення показують, що найкоротша відстань між вузлами 1 і 7 дорівнює 21 км. міста, через які проходить найкоротший маршрут, визначаються наступні чином. З готових результатів третього етапу слід, що вузол 7 зв'язується з вузлом 5. Далі з готових результатів другого етапу слід, що вузол 4 зв'язується з вузлом 5. Нарешті, з готових результатів першого етапу слід, що вузол 4 зв'язується з вузлом 1. Отже, оптимальним маршрутом є послідовність 1-4-5-7.

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

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

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

Застосування принципу оптимальності демонструється обчисленнями з прикладу задачі про найкоротший шлях. Наприклад, на етапі 3 ми використовуємо найкоротші шляхи до вузлів 5 і 6 і не цікавимося, як ці вузли були досягнуті з вузла 1.

В розглянутій вище задачі, стан системи на будь-якому етапі описувався єдиною змінною. Наприклад, в задачі оптимального завантаження (див. Додаток 1) вага предмета є єдиним обмеженням, яке враховується при його завантаженні. Разом з цим обсяг судна також може бути обмежувальною величиною. У цьому випадку кажуть, що стан системи є двомірним, так як формується двома змінними: вагою і об'ємом.

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



Розділ 2. Задача про завантаження

2.1 Загальні відомості

Задача про завантаження - це задача про раціональне завантаження судна (літака, автомобіля, тощо), яке має обмеження за обсягом або вантажо-підйомністю. Кожен поміщений на судно вантаж приносить певний прибуток. Завдання полягає у завантаженні судна такими вантажами, які приносять найбільший сумарний прибуток [5, с.418].

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

Максимізувати .

За умови, що , і цілі.

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

1 . Етап i ставиться відповідно до предмету і-го найменування,

2. Варіанти розв'язку на етапі i описуються кількістю предметів і-го найменування, що підлягають завантаженню. Відповідний прибуток дорівнює . Значення замкнено в межах від 0 до, де - ціла частина числа .

3. Стан на етапі i виражає сумарну вагу предметів, рішення про завантаження яких прийняті на етапах Це визначення відображає той факт, що обмеження за вагою є єдиним, яке пов'язує n етапів разом.

Нехай - максимальний сумарний прибуток від етапів і, і +1 , ... n при заданому стані . Найпростіше рекурентне рівняння визначається за допомогою наступної двокрокової процедури [5, с.419].

Крок 1. Виразимо як функцію у вигляді

 , (2.1)

де

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

.

Отже, рекурентне рівняння набуває вигляду:

  (2.2)

2.2 Постановка задачі оптимального завантаження

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



(2.3)

Відомі маси предметів-гo типу та їх вартість . Необхідно завантажити транспортний засіб таким чином, щоб загальна цінність вантажу була максимальною:

де - число предметів вантажу -гo типу, що завантажуються в транспортний засіб; виступає в якості управління ).

Обмежуючими умовами є:

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

Приклад наведений у Додатку 2.

2.3 Приклад розв'язання задачі оптимального завантаження

Нехай літак потрібно завантажити 4 видами предметів, щоб ефект від цих предметів (наприклад, вартість) був максимальним. Вантажопідйомність літака дорівнює ; - вага одиниці i-го виду предметів; - вартість одиниці i-го виду; - кількість i-го виду предметів, взятих на борт літака [11, с.189]

Розв'язання. Знайдемо максимум цільової функції задачі:

.

Обмеження записується таким чином:

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

Для чисельного розв'язання припустимо, що

відповідних одиниць.

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

Перший етап буде містити чотири кроки.

Крок 1. Спочатку знайдемо можливі оптимальні варіанти завантаження літака тільки предметами першого виду. Необхідно знайти і запам'ятати значення і відповідну їм максимальну вартість вантажу при різних можливих значеннях . У цьому випадку максимальна вартість вантажу визначиться наступним чином:

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

.

Задамо деякі значення і знайдемо для них і . Очевидно, якщо вантажопідйомність літака менше 24 одиниць, то жодного предмета першого виду завантажити не можна. При вантажопідйомності від 24 до 47 одиниць можна завантажити 1 одиницю предмета першого виду і так далі. Результати представимо у вигляді таблиць. Значення , і наведені в табл. 1. В таблицях прийнято більш широка межа значень для - від 0 до 87 од.

Таблиця 1

Перший крок оптимізації

0 - 23	0	0
24 - 47	96	1
48 -71	192	2
72 -87	288	3

Крок 2. Проведемо оптимізацію цільової функції за умови, що літак завантажують предметами першого і другого видів. Необхідно знайти вартість вантажу в цьому випадку, максимальну ефективність завантаження позначимо через . Якщо предметів другого виду взято , то вага предметів першого виду повинна бути не більше, ніж . Максимальна вартість предметів першого виду виразиться формулою =,

а загальна вартість вантажу - формулою .

Тоді , (20)

Максимум цього виразу визначають тільки за . Однак ми не знаємо, яку частину ваги можуть займати предмети другого виду . Тому ми повинні розглянути вираз (20) для будь-яких значень від 0 до 83 одиниць. При обчисленні скористаємося отриманими результатами (див. табл.1)

Наприклад, нехай . Величина може приймати значення 0,1,2; відповідна вартість предметів другого виду дорівнює 0;85;170 одиниць, а для предметів першого виду складе 46,24,2 одиниць.

З табл.1 для .; 24; 2 од. знаходимо Підсумовуємо відповідні значення:

і вибираємо найбільше з них: 181 од. Воно отримано для . Для заносимо в Табл.2 . Оптимальні результати обчислення і наведені в табл.2.

Таблиця 2

Другий крок оптимізації

0-21	0	0
22-23	85	1
24-43	96	0
44-45	170	2
46-47	181	1
48-65	192	0
66-67	255	3
68-69	266	2
70-71	277	1
72-87	288	0

З табл.2 випливає, що при вантажопідйомності транспортного засобу до 21 од. нічого в нього завантажити не можна, при вантажопідйомності 22 ... 23 од. можна завантажити тільки один предмет другого виду, при вантажопідйомності 24 ... 43 од. - або один предмет першого виду, або один предмет другого виду. Максимальна вартість вантажу буде при завантаженні предмета першого виду. При вантажопідйомності 44 ... 45 од. можна загрузити або один предмет першого виду, або два предмети другого виду. Більша вартість вантажу буде в останньому випадку. При вантажопідйомності 46 ... 47 од. можна загрузити один предмет першого виду, два предмети другого виду або по одному предмету першого і другого видів. Вартість вантажу в останньому варіанті - максимальна. Далі аналогічно.

Крок 3. Проведемо оптимізацію цільової функції за умови, що літак завантажують предметами перших трьох видів . Потрібно максимізувати по функцію

, .

Задаємо значення і для кожного такого значення отримуємо максимум по . Значення беремо в табл.2. Наприклад, нехай . Можливе значення , і відповідна вартість предметів третього виду дорівнює . На предмети першого і другого видів залишається відповідна вага 38; 22; 6 од. За табл.2 знаходимо . Сумарна вартість дорівнюватиме 96;135;100 од. Максимальне значення вартості при . дорівнює 135 од. при . Далі аналогічно. Результати розрахунків поміщені в табл.3.



Таблиця 3.

Третій крок оптимізації

0-15	0	0
16-21	50	1
22-23	85	0
24-31	96	0
32-37	100	2
38-39	135	1
40-43	146	1
44-45	170	0
46-47	181	0
48-63	192	0
64-69	242	1
70-71	277	0
72-87	288	0

Крок 4. Отримаємо оптимальну вагу вантажу , яку може підняти літак.

Задамо значення , яке може бути зайнято четвертим вантажем, і обчислимо (табл.4).

Таблиця 4.

Четвертий крок оптимізації

0-9	0	0
10-15	20	1
16-21	50	0
22-23	85	0
24-33	96	0
34-37	116	1
38-39	135	0
40-45	146	0
46-47	181	0
48-57	192	0
58-63	212	1
64-69	242	0
70-71	277	0
72-81	288	0
82-87	308	1

Другий етап розв'язання задачі полягає у знаходженні оптимального розв'язку. Максимальне значення визначає відповідне значення аргументу - кількість вантажу четвертого виду, який візьме літак ). При маємо

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

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

З табл.1-4 бачимо, що вони містять "заготовки" для оптимізації завантаження літака будь-якої вантажопідйомності до вказаними предметами. Таким чином, ми вирішили не тільки поставлену задачу, але і ряд споріднених задач. При цьому в пам'яті комп'ютера необхідно тримати табл.1- 4: стовпці протягом наступного кроку, а стовпці і відповідні їм - протягом розв'язання всієї задачі. Для складних задач остання обставина має суттєве значення і обмежує можливості вирішення завдань розглянутим методом .

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



ВИСНОВКИ

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

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

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

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

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

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

1. вивчені основні поняття динамічного програмування;

2. виконана постановка задачі динамічного програмування;

3. виконана постановка задачі оптимального завантаження;

4. наведені приклади розв'язування задач економічного змісту.

Список використаних джерел

1. Кузнецов Ю. Н. Математическое программирование: Учеб. пособие для вузов/ Ю.Н. Кузнецов, В.И. Кузубов, А.Б.Волощенко - М.: издательство «Высшая школа», 1976. - 352 с.

2. Степанюк В.В. Методи математичного програмування/ Степанюк В.В. - К.: Видавниче об'єднання «Вища школа», 1977. - 272с.

3. Акулич, И.Л Динамическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. Вузов/ И.Л. Акулич. - М.: Высш. шк., 1986. - 319 с.

4. Математичне програмування. Навчально-методичний посібник. Частина 2/ Укл. І.П.Лусте, І.Д. Пукальський. - Чернівці: Рута,2005. - 79с.

5. Таха Х. Введение в исследование операций.: Пер.с англ./ Таха Х. - М.: Издательский дом «Вильямс», 2001. - 912 с.

6. Вентцель Е. С. Исследование операций: задачи, принципы,

Методология/ Вентцель Е. С. - М.: Наука. Гл. ред. физ.-мат. лит.,1988. - 208с.

7. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования/ Беллман Р., Дрейфус С. - М.: Наука,1965.

8. Вентцель Е. С. Элементы динамического программирования/ Вентцель Е. С - М.: Наука, 1964. - 176 с.

9. Карманов В. Г. Математическое программирование: Учеб. Пособие/ Карманов В. Г. - М.: ФИЗМАТЛИТ, 2004. - 264 с.

10. Абчук В.А. Экономико-математические методы: Элементарная математика и логика. Методы исследования операций/ Абчук В.А. - СПб.: Союз, 1999. - 320 с.



ДОДАТОК 1

Літак, ємністю 4 тони, завантажують предметами 3-х найменувань. Дані про вагу одного предмету  в тонах і прибутки  в умовних грошових одиницях, від перевезення одиниці вантажу і-го найменування приведені у таблиці:

предмет і
1	2	31
2	3	47
3	1	14

Яким чином потрібно завантажити літак, щоб отримати максимальний прибуток?

Розв'язання.

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

Етап 3. Точна вага вантажу на 3 етапі (предмет 3 найменування), наперед невідома, але вона повинна бути в межах від 0 до 4 тон, так як W = 4 тони.

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

Так як вага одного предмета третього типу рівна 1 тоні, то максимальна кількість одиниць цього типу буде: Це означає, що можливі значення стану x₃ будуть 0, 1, 2, 3, 4. Розв'язок  буде допустимим лише при такій умові: . Тобто усі недопустимі альтернативи (ті, для яких ) виключені.

Основою для порівняння допустимих рішень на етапі 3 буде рівняння Беллмана:

У таблиці 5. записано порівняння альтернатив для кожного значення _.

Таблиця 5.

		Оптимальний розв'язок
0	0	-	-	-	-	0	0
1	0	14	-	-	-	14	1
2	0	14	28	-	-	28	2
3	0	14	28	42	-	42	3
4	0	14	28	42	56	56	4

Етап 2. 
У таблиці 6. запишемо вибір альтернатив для

Таблиця 6.

		Оптимальний розв'язок
0	0+0=0	-	0	0
1	0+14=14	-	14	0
2	0+28=28	-	28	0
3	0+42=42	47+0=47	47	1
4	0+56=56	47+14=61	61	1

Етап 1. 
У таблицю 7. запишемо вибір альтернатив для x_1.

Таблиця 7.

	=	Оптимальний розв'язок
0	0 + 0= 0	-	-	0	0
1	0 + 14 =14	-	-	14	0
2	0 + 28 = 28	31 + 0 = 31	-	31	1
3	0 + 47 = 47	31 + 14 = 45	-	47	0
4	0 + 61 = 61	31 + 28 = 59	62 + 0 = 62	62	2

ІІ. Безумовна оптимізація. Оптимальний розв'язок визначається наступним чином. З умови задачі W = 4 випливає, що перший етап розв'язання задачі при  дає оптимальний розв'язок =2, який означає, що два предмета першого найменування будуть завантажені у літак. Тоді для предмету другого найменування змінна стану приймає значення

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

Оптимальним розв'язком задачі буде такий план завантаження літака в тонах: , що забезпечує прибуток 62 умовні грошові одиниці.

В таблиці для першого етапу нам, по суті, необхідно отримати оптимальний розв'язок лише для , так як це останній етап, який розгядаємо. Однак в таблицю включені також обчислення для які дозволяють провести аналіз чутливості розв'язку. Наприклад, що відбудеться, якщо максимальна вантажопідйомність літака буде 3 тонни замість 4? Новий оптимальний розв'язок може бути визначено, починаючи з на першому етапі і продовжуючи так, як ми робили при .

.



Додаток 2

Літак вантажопідйомністю G = 83 умовних одиниці вантажу передбачається завантажити чотирма типами вантажу (т = 4). Маси і вартість предметів -гo типу в умовних одиницях задані в табл. 1.

Необхідно завантажити літак таким чином, щоб загальна цінність вантажу була максимальною.

Таблиця 1

Показник, у. од.	Тип предметів вантажу,
	1	2	3	4
	10	16	22	24
	20	50	85	96

Розв'язання.

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

Послідовність розрахунків при цьому буде наступною.

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

(2.7)

при умовах, що випливають з умов (2.5) і (2.6),

З першої умови випливає, що

З другої умови випливає, що може бути тільки цілим числом, тому береться як ціла частина отриманого дробу:

Це і є умовне оптимальне управління на останньому, четвертому кроці:

Максимальна цінність вантажу при такому завантаженні визначається

за формулою (2.7):

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

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

. Максимальна цінність вантажу, що складається з предметів четвертого і третього типів, визначиться за формулою, яка випливає з формули (2.4), з обмеженнями (2.5) і (2.6):

(2.8)

при . (2.9)

Обчислення за формулою (2.8) виконується таким чином.

З обмеження (2.9) слідує

Це означає , що може набувати значення не більше:

.

Для кожного з цих чотирьох значень обчислюється величина, яка

стоїть у фігурних дужках формули (2.8), причому обчислюється

за формулою (2.7):

0
1
2
3

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

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

Далі переходимо до попереднього, другого кроку - до завантаження

предметів другого типу - і для нього аналогічним шляхом знаходимо

і відповідне : .

Так само, для першого кроку і .

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

Починається другий круг оптимізації від першого кроку до останнього.

Оскільки нам відомо, що оптимальне управління на першому кроці потребує однієї одиниці вантажу першого типу, то надалі розподіляється тільки те, що залишається на інші типи вантажу, а саме:

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

Оптимальне управління забезпечує наступну

максимальну загальну цінність вантажу, що розраховується за формулою (3.68):

.

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



ДОДАТОК 3

Розглянемо застосування методу динамічного програмування на прикладі розподілення вантажів між 4-ма торговими суднами. Нехай загальна місткість торговельних суден становить не більше 500 тонн. На основі техніко-економічних розрахунків встановимо вартість перевезення кожним судном певної кількості вантажу, яка наведена в таблиці 2.1. Необхідно визначити оптимальний розподіл вантажів між суднами, що забезпечує мінімізацію витрат підприємств. Таким чином, у цій оптимізаційній задачі використовується критерій - сумарна вартість завантаження.

Таблиця 2.1

	Місткість торгових суден (тонн)
№ торгового судна	0	100	200	300	400	500
	Вартість перевезення (тис. грн.)
1	400	500	550	700	750	1000
2	4000	4200	4300	4500	4600	4700
3	0	100	400	800	850	900
4	600	750	900	950	1100	1200

Нехай - місткість відповідно першого, другого, третього і четвертого судна, .

Позначимо функції - зміни вартості перевезен-ня першого, другого, третього і четвертого підприємства при завантаженні х тис.тонн. Цим функціям відповідають рядки 1, 2, 3, 4 в табл.2.1.

Визначимо мінімум функції мети

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

тис.тонн.

Для розв'язання цієї задачі застосуємо принцип оптимальності.

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

Виділимо в нашій задачі 3 кроки:

1) А тис. тонн завантажуються в перше, друге судно одночасно;

2) А тис. тонн завантажуються в перше, друге, третє судно разом;

3) А млн. тонн завантажуються в чотири судна одночасно.

Позначимо: - відповідно оптимальні розподіли вантажів для першого, другого і третього кроків.

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

Перший етап включає наступні кроки:

1 ) Обчислення максимуму критерію оптимізації для різних значень за обсягами завантаження , які використовуються тільки для суден 1 і 2. Обчислимо за формулою:

Результати обчислень представлені в табл. 2.2

Таблиця 2.2

		0	100	200	300	400	500
		4000	4200	4300	4500	4600	4700
0	400	4400	4600	4700	4900	5000	5100
100	500	4500	4700	4800	5000	5100
200	550	4550	4750	4850	5050
300	700	4700	4900	5000
400	750	4750	4950
500	1000	5000

Наприклад, для того, щоб визначити потрібно знайти

Найменше з отриманих значень буде 4400. Решта отримуються як найменше значення кожної діагоналі в таблиці (ці значення в таблиці підкреслені):

2)Обчислення мінімуму критерію оптимізації для різних значень за обсягами завантаження , які використовуються тільки для торговельних суден 1,2 і 3.

Обчислюємо за формулою

Результати обчислень записуємо у таблицю 2.3, яка аналогічна табл.2.2, тільки замість в ній вкажемо значення , а замінимо на .

Таблиця 2.3

		0	100	200	300	400	500
		0	100	400	800	850	900
0	4400	4400	4500	4800	5200	5250	5300
100	4500	4500	4600	4900	5300	5350
200	4550	4550	4650	4950	5350
300	4700	4700	4800	5100
400	4750	4750	4850
500	4950	4950

Обчисливши, отримуємо значення :

3) Обчислення мінімуму критерію оптимізації щодо обсягів завантаження , які використовуються для всіх торгових суден.

Обчислюємо за формулою:



Результати обчислень записуємо у таблицю 2.4.

Таблиця 2.4

		0	100	200	300	400	500
		600	750	900	950	1100	1200
0	4400	5000	5150	5300	5350	5500	5600
100	4500	5100	5250	5400	5450	5600
200	4550	5150	5300	5450	5500
300	4650	5250	5400	5550
400	4750	5350	5500
500	4850	5450

В результаті обчислень отримуємо значення :

На цьому перший етап розв'язання задачі динамічного програмування закінчується.

Перейдемо до другого етапу розв'язання задачі динамічного програмування - безумовної оптимізації. На цьому етапі використовуються табл.2.4, 2.3, 2.2. Визначимо оптимальні обсяги завантаження суден для . Для цього виконаємо наступні обчислення.

1 ) Нехай обсяг завантаження всіх суден становить тис. тонн. Визначимо обсяг завантаження четвертого судна. Для цього використовуємо табл. 2.4. Виберемо на ній діагональ, відповідну - це значення 5450, 5500, 5550, 5500, 5600, 5600. З цих чисел візьмемо мінімальне тис. грн. Відмічаємо стовпець, в якому стоїть ця величина. Далі визначаємо у відміченому стовпці обсяг завантаження четвертого судна .

На завантаження першого, другого і третього судна залишається

тис. тонн.

2 ) Знайдемо обсяг, виділений на завантаження третього судна. Для цього використовуємо табл. 2.3. Виберемо в цій таблиці діагональ, відповідну - це значення 4950, 4850, 5100, 5350, 5350, 5300. Обираємо стовпець, в якому стоїть мінімальна величина вартості тис. грн. Визначаємо значення тис. тон. у зазначеному стовпці.

3 ) На завантаження першого і другого судна залишається сума

тис. тонн.

Визначимо обсяг завантаження другого судна. Використовуємо для цього табл.2.2. Виберемо в таблиці діагональ, відповідну - це значення 4750, 4900, 4850, 5000, 5000. Обираємо стовпець з мінімальною величиною вартості тис. грн. Тоді в цьому стовпці тис. тонн.4 ) Визначимо обсяг завантаження першого судна. тис. тонн.Таким чином, для обсягу вантажу в тис. тонн. оптимальним є завантаження першого судна на 400 тис. тон, а третього на 100 тис. тон. Отже, завантажувати друге і четверте судно економічно не вигідно,оскільки при цьому сумарна вартість завантаження буде 750 +100 = 850 тис. т.

Размещено на Allbest.ru