WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Задачі динамічного програмування - Реферат

Задачі динамічного програмування - Реферат

і-го підприємства складають I (xi) тис. грн.
Знайти такий варіант розподілу централізованого фонду розвитку виробництва між підприємствами об єднання, при якому загальний прибуток, отриманий за N років, є максимальним.
5. Для здійснення своєї ефективної діяльності виробничі об єднання і підприємства мають періодично проводити заміну обладнання, що використовується. При цій заміні враховуються продуктивність цього обладнання, затрати, пов язані з утриманням і ремонтом обладнання, ціна замінного обладнання і обладнання, що купується. Припустимо, що на початок запланованого періоду на підприємстві встановлено нове обладнання, яке дозволяє за r-ий рік випустити готової продукції на суму R (r) грн., а щорічні витрати, пов язані з утриманням та ремонтом обладнання дорівнюють Z (r) грн. В r-ий рік обладнання може бути продано за S (r) грн. та закуплено нове за Pr грн. З урахуванням всіх цих факторів знайти оптимальний план заміни обладнання, тобто план, який забезпечує максимальний прибуток від заміни обладнання протягом N років.
6. Деталі n вигляду можуть оброблятись на двох станках. Час обробки і-ої деталі (i = 1, n) на першому станку дорівнює ai хвилин, а час обробки тої ж самої деталі на другому станку дорівнює bi хвилин. Черговість обробки деталей однакова: спочатку деталь обробляється на першому станку, а потім на другому. Потрібно вибрати таку послідовність обробки деталей, при якій час виготовлення всіх деталей буде мінімальним.
7. На склад ємністю W м3 потрібно вмістити n різноманітних типів обладнання. Об єм однієї одиниці і-го типу обладнання (і = 1, n) дорівнює Vi м3 , ціна одиниці даного типу обладнання дорівнює Сі грн. Визначити, скільки обладнання кожного типу слід помістити на склад так, щоб загальна ціна обладнання на складі була максимальною.
8. Виробничі об'єднання, які випускають товари народного призначення, виготовляють їх окремими партіями. Чим більший розмір цих партій, тим це більше вигідно для виробничих об єднань. Тому кожне об'єднання зацікавлене в окремі місяці випускати більше виробів, чим це потрібно для задоволення попиту, а залишок зберігати на складі для їх реалізації в наступні місяці. Однак зберігання виробів на складі супроводжується відповідними затратами.
Будемо рахувати, що підприємство намагається знайти оптимальний план виробництва продукції протягом N місяців, в кожному з яких необхідно ai (i = 1, N) одиниць продукції. Запаси на початок запланованого періоду дорівнюють b виробам, а в кожному з запланованих місяців підприємство може виготовити не більше di одиниць продукції. Одночасно на складі може зберігатись не більше ніж A виробів. Витрати, пов язані з виробництвом ai (j = 1, k) виробів, складають cj грн., а витрати, пов язані зі зберіганням протягом місяця одного виробу, складають грн. Визначити такий план випуску продукції, при якому загальна сума витрат на виробництво і зберігання її була б мінімальна, а попит на необхідні вироби був би задоволений повністю і своєчасно.
Розв'язування задач динамічного програмування.
Задача. Знайти розв'язок задачі,якщо S=700 тис.грн. n=3, а значення і наведені в таблиці 1.
Таблиця 1.
Об'єм капіталовкладень (тис.грн.) Приріст випуску продукції в залежності від об'єму капіталовкладень (тис. грн.)
Підприємство1 Підприємство2 Підприємство3
0 0 0 0
100 30 50 40
200 50 80 50
300 90 90 110
400 110 150 120
500 170 190 180
600 180 210 220
700 210 220 240
Розв'язування. Для розв'язування даної задачі динамічного програмування необхідно зіставити рекуррентне співвідношення Беллмана. В розглядаючому випадку це співвідношення приводить до наступних функціональних рівнянь:
........................................
Тут функції визначають максимальний приріст випуску продукції при відповідному розподілі Х тис. грн. капіталовкладень між і підприємствами. Тому значення функції вираховується лише для одного значення , так як об'єм капіталовкладень, виділяючих для всіх n підприємств, дорівнює S тис. грн.
Використовуючи тепер рекурентне співвідношення і вихідні дані табл.1, приступаємо до знаходження розв'язку задачі, тобто до визначення спочатку умовно оптимальних, а потім і оптимальних розподілів капіталовкладень між підприємствами.
Починаємо з визначення умовно оптимальних капіталовкладень, виділяючих для розвитку першого підприємства. Для цього знаходимо значення для кожного Х, приймаючого значення 0, 100, 200, 300, 400, 500, 600 і 700.
Нехай ;тоді . Візьмемо тепер . Тоді, використовуючи табл.1, дістанемо
.
Тут перший рядок відповідає розв'язку , а другий рядок - розв'язку . Так як першому розв'язку приріст випуску продукції не забезпечується, а при другому дорівнює 30 тис. грн., то умовно оптимальним розв'язком являється .
Аналогічно знаходимо умовно оптимальний розв'язок для інших значень :
;
;
;
;
;
Результати обчислень і одержані відповідні умовно оптимальні розв'язки записуємо в табл.2.
Таблиця 2.
Об'єм капіталовкладень Х, виділених першому підприємству (тис.грн.) Максимальний приріст випуску продукції (тис. грн.) Умовно оптимальний об'єм капіталовкладень , виділених першому підприємству (тис. грн.)
0 0 0
100 30 100
200 50 200
300 90 300
400 110 400
500 170 500
600 180 600
700 210 700
Використовуючи тепер дані табл.2 і 1, визначимо умовно оптимальні об'єми капіталовкладень, виділених другому підприємству. Знайдемо
для кожного із допустимих значень Х, рівних 0, 100, 200, 300, 400, 500, 600 і 700:
, ;
;
;
;
;
;
;
.
Одержані результати і найдені умовно оптимальні об'єми капіталовкладень, виділених другому підприємству, записуємо в табл.3.
Таблиця 3.
Об'єм капіталовкладень Х, виділених двом підприємствам (тис.грн.) Максимальний приріст випуску продукції (тис.грн.) Умовно оптимальний об'єм капіталовкладень ,виділених другому підприємству (тис.грн.)
0 0 0
100 50 100
200 80 100
300 110 200
400 150 400
500 190 500
600 220 100
700 250 200
Переходимо до знаходження значень
,
використовуючи для цього відповідні дані табл.3 і 1.
Так як в даному випадку число підприємств дорівнює 3 то проводимо обчислення лише для одного значення :
.
Відповідно, максимальний приріст випуску продукції складає 270 тис.грн. Це має місце тоді, коли третьому підприємству виділяється 600 тис.грн., а першому і другому підприємствам - 100 тис.грн. Тоді, як бачимо з табл.3, другому підприємству необхідно виділити 100 тис. грн.
Отже, ми одержали оптимальний план розподілу капіталовкладень між підприємствами, згідно якому забезпечується максимальний приріст випуску продукції.
Література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти) "Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л. Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.292-296-300.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с.
Loading...

 
 

Цікаве