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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


контрольная работа Застосування методу динамчного програмування до детермнованих задач

Информация:

Тип работы: контрольная работа. Добавлен: 26.04.2012. Сдан: 2011. Страниц: 4. Уникальность по antiplagiat.ru: < 30%

Описание (план):


Тема: Застосування методу динамічного програмування до детермінованих задач. 

Мета: Навчитися розв’язувати задачі динамічного програмування, аналізувати результати, робити висновки. 

Теоретичні відомості
    Моделі  динамічного програмування
    Якщо  деяка управлінська система S знаходиться у початковому стані і з плином часу її стан змінюється таким чином, що система переходить у кінцевий стан, який описується критерієм W, то необхідно так організувати процес, щоб даний критерій досягнув оптимального значення.
    Наприклад, випуск продукції на промисловому підприємстві визначається зміною з часом величини залучених у виробництво ресурсів. Сукупність рішень, що приймаються на початку кожного періоду для забезпечення підприємства сировиною, паливом і т.п. є управлінням. Якщо забезпечити підприємство вказаними ресурсами у повному обсязі, то це призведе до максимального завантаження виробничої потужності. Але такий підхід вірний тільки з точки зору фіксованого періоду часу. Якщо протягом більш тривалого періоду підтримувати максимальну завантаженість виробничої потужності, то це призведе до швидкого виходу з ладу обладнання, що у майбутньому викличе зменшення обсягів виробництва продукції. Таким чином, економічний процес випуску продукції можна вважати таким, що складається з декількох етапів (кроків), на кожному з яких здійснюється вплив на його розвиток. Початком етапу є момент прийняття рішення про зміну одного з параметрів, яке зазвичай вибирається із множини деяких альтернатив.
    Позначимо множину можливих управлінь через U. Тоді задача полягає в тому, щоб із множини можливих управлінь U знайти таке управління U*, яке дасть змогу перевести систему S із початкового стану в кінцевий таким чином, щоб критерій W(U) досягнув оптимального значення W*(U). Стан економічної системи S можна описати числовими параметрами, як правило техніко-економічними та іншими показниками, які у методах динамічного програмування отримали термін “координати системи”. Тоді, перехід системи S із одного стану S1 в інший S2 можна виразити деякою траєкторією точки S. Управління U означає вибір певної траєкторії переміщення S, тобто визначення закону руху S. Сукупність станів, у які може переходити система , називають областю можливих станів. Суть задачі динамічного програмування зводиться до того, щоб з області можливих станів системи вибрати таку, на якій критерій W приймає оптимальне значення.
    Динамічне програмування являє собою поетапне планування багатокрокового процесу. Починають планувати із останнього k-го кроку і поступово переходять до (k-1)-го, (k-2)-го і т.д., поки не прийдуть до початкового стану системи S0. Для того, щоб спланувати k-ий крок, необхідно знати стан системи на (k-1)-му кроці. Якщо цей стан не відомий, то роблять різні припущення про можливий стан системи на цьому кроці. Позначимо стани системи на цьому кроці як точки Sk-1,1, Sk-1,2, …, Sk-1,r. На останньому кроці знайдемо для кожного з них оптимальне управління . При цьому критерій має відповідати оптимальному з множини . Таким чином k-ий крок спланований. На (k-1)-му кроці потрібно знати стани системи на (k-2)-му кроці і т.д., поки не прийдемо у початковий стан системи. Для цього стану вибираємо оптимальні управління таким чином, щоб досягнути оптимальної суми критеріїв W* на двох попередніх кроках . Якщо тепер взяти остаточне значення критерію оптимальності на нульовому кроці, то цей критерій повинен мати властивість адитивності, тобто , де – кількість кроків процесу.
    Р. Беллман запропонував метод знаходження оптимального розв’язання задач динамічного програмування за допомогою так званих функціональних рівнянь. Застосування методу функціональних рівнянь дає змогу звести розв’язок однієї N-мірної задачі до послідовності розв’язків для N одномірних задач. Враховуючи, що в динамічному програмуванні процес розглядається від закінчення до початку, то типове функціональне рівняння, яке описує дискретний процес, буде мати вигляд
    
, (2.2.1)

    де  f – критерій задачі (доход, витрати і т.п.); N – кількість етапів, які ще необхідно пройти в процесі розрахунку; х – змінна, яка характеризує стан системи на N-ному етапі; – сумарне значення критерію, яке може бути отримане за N етапів до закінчення процесу розрахунку, починаючи із стану х; – деяка управлінська змінна; – величина критерію, отримана на N-ному етапі при оптимальному виборі в межах від 0 до х; – сумарне значення критерію, яке знаходиться після проходження (- 1) етапів до закінчення процесу розрахунку, починаючи із стану .
    За  допомогою методу функціональних рівнянь  розв’язуються задачі розподілу ресурсів, заміни обладнання і т.п.
    Розглянемо  одну із типових задач – задачу розподілу ресурсів.
    Вісім умовних одиниць певного ресурсу (наприклад, мільйонів гривень) можуть бути інвестовані (вкладені) у розвиток трьох підприємств (k = 1,2 3). Позначимо через gk(x), k = 1,2,3 прибуток в тих же умовних одиницях, що отримується від k-го підприємства, якщо в його розвиток інвестовано x одиниць ресурсу. Величини прибутків gk(x), k = 1,2,3 для різних можливих значень x наведені в таблиці 1. Зауважимо, що ця ж таблиця містить інші дані, зміст яких пояснюється далі.
    Таблиця 1
x 0 1 2 3 4 5 6 7 8
g1(x) 0 5 15 40 80 90 95 98 100
g2(x) 0 5 15 40 60 70 73 74 75
g3(x) 0 4 26 40 45 50 51 52 53
    При цьому ми вважаємо, що ресурс вимірюється  лише в цілих числах і прибутки від підприємств є незалежними при будь-якому розподілі ресурсу. Потрібно так розподілити наявні ресурси між підприємствами, щоб загальний прибуток від них був максимальним.
    Нехай xk, k=1,2,3 – об’єм інвестицій у k-е підприємство. Тоді формальна постановка задачі така: шукається вектор x=(x1,x2,x3):
    

    Оскільки  цільова функція є адитивною, застосуємо метод динамічного програмування  до розв’язання цієї задачі. Отже, розглядаємо  трьохетапний процес планування, кожен з 3-х етапів якого є виділення ресурсу відповідному підприємству. Зауважимо, що оптимальний розв’язок задачі не залежить від того, в якому порядку перенумеровані підприємства. Розглядаємо останній (3-й) етап планування і нехай на перших двох етапах не використана жодна одиниця ресурсу, тобто до третього етапу ми прийшли, маючи 8 одиниць ресурсу. Тоді для отримання максимального прибутку потрібно всі 8 одиниць інвестувати в розвиток третього підприємства, тому що g3(x) – зростаюча функція (див. табл. 1). При цьому максимальний прибуток від інвестування f3(8)=g3(8)=53 одиниць і для цього потрібно вкласти в розвиток третього підприємства d3(8)=8 одиниць ресурсу. Для розв’язання задачі методом динамічного програмування потрібні також значення f3(x), d3(x) при x=0,1,2,…7. Вони знаходяться аналогічно і наведені в табл.2. Отже, ми зробили всі можливі припущення відносно закінчення передостаннього (2-го) етапу планування і отримали відповідні умовні оптимальні рішення для 3-го кроку.
    Таблиця 2
x 0 1 2 3 4 5 6 7 8
g1(x) 0 5 15 40 80 90 95 98 100
g2(x) 0 5 15 40 60 70 73 74 75
g3(x) 0 4 26 40 45 50 51 52 53
f3(x) 0 4 26 40 45 50 51 52 53
d3(x) 0 1 2 3 4 5 6 7 8
    Нехай тепер 8 одиниць ресурсу розподіляються між другим та третім підприємствами і z – об’єм інвестування в друге підприємство. Використовуючи значення f3(x) з таблиці 2, легко підраховуємо:
    

    тобто за цих умов у розвиток другого  підприємства потрібно вкласти d2(8)=5 одиниць ресурсу. Аналогічно знаходяться f2(x) та d2(x) при x=0,1,2,…,7 (табл.3). Отже, ми отримали умовні величини прибутків для 2-го та 3-го етапів (f2(x)) та умовний оптимальний об’єм інвестування в друге підприємство (d2(x)) за умови різних закінчень 1-го етапу. 

    Таблиця 3
x 0 1 2 3 4 5 6 7 8
g1(x) 0 5 15 40 80 90 95 98 100
g2(x) 0 5 15 40 60 70 73 74 75
g3(x) 0 4 26 40 45 50 51 52 53
f3(x) 0 4 26 40 45 50 51 52 53
d3(x) 0 1 2 3 4 5 6 7 8
f2(x) 0 5 26 40 60 70 86 100 110
d2(x) 0 1 0 0 4 5 4 4 5
    Розгляд першого етапу планування еквівалентний  розв’язанню вихідної задачі. Нехай з 8 одиниць ресурсу z одиниць інвестується у перше підприємство, (8-z) – у друге та третє. Використовуючи значення f2(x) з таблиці 3, знаходимо
    
    Тобто d1(8)=4. Отже, максимальний прибуток в 140 одиниць отримується при такому розподілі інвестицій: d1(8)=4 одиниці в перше підприємство, d2(4)=4 в друге та d3(0)=0 одиниць в третє.
    Отже, загальний вид розглянутих функціональних рівнянь для розподілу ресурсів між трьома об’єктами такий:
    
    де  fi(x) – максимальний прибуток від інвестування x одиниць ресурсу в підприємства i,i+1,…,3, di(x) – оптимальне інвестування в i-те підприємство, якщо в підприємства i,i+1,…,3 інвестується x одиниць ресурсу. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Задание: Найти оптимальное распределение средств между 5 предприятиями при условии, что прибыль f(x), полученная от каждого предприятия, является функцией от вложенных в него средств х. Выписать все оптимальные управления.
     Исходные  данные. 

f1 f2 f3 xi
0 0 0 0
11 8 7 1
26 23 20 2
60 54 53 3
98 91 89 4
 
 
 
I этап. Условная оптимизация.
1-ый шаг. k = 3. 

e2 u3 e3 = e2 - u3 f3(u3) F*3(e3) u3(e3)
1 0 1 0      
   1 0 7 7 1
2 0 2 0      
   1 1 7      
   2 0 20 20 2
3 0 3 0      
   1 2 7      
   2 1 20      
   3 0 53 53 3
4 0 4 0      
   1 3 7      
   2 2 20      
   3 1 53      
   4 0 89 89 4
 
 
 
2-ый шаг. k = 2. 

e1 u2 e2 = e1 - u2 f2(u2) F*2(e1) F1
и т.д.................


Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.