Оптимальний розподіл коштів на розширення виробництва

Курсова робота

Оптимальний розподіл коштів на розширення виробництва

Зміст

Введення

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

1.1 Принцип оптимальності Беллмана

1.2 Обчислювальна схема

2. Рішення задачі оптимального розподілу коштів на розширення виробництва

2.1 Рішення задачі оптимального розподілу коштів на розширення виробництва ручним способом

2.2 Рішення задачі оптимального розподілу коштів на розширення виробництва в середовищі Microsoft Exсel

Висновок

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

Введення

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

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

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

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

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

Курсова робота складається з 2-ух частин. У першому розділі розглянуто теоретичні основи завдань динамічного програмування. У другому розділі наведено приклад розв'язання задачі оптимального розподілу коштів на розширення виробництва.

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

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

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

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

Нехай є вантаж, що складається з неподільних предметів різних типів, який потрібно занурити в літак вантажопідйомністю Р. Вартість і маса кожного предмета j-г o типу відомі і становлять відповідно c j, і pj одиниць ( ). Потрібно визначити, скільки предметів кожного типу треба завантажити в літак, щоб сумарна вартість вантажу була найбільшою, а маса не перевищувала вантажопідйомності літака.

Математично задача записується таким чином: знайти такі цілі невід'ємні значення х j ( ), Які б максимізувати функцію:

(1.1)

при обмеженні

(1.2)

де xj - Кількість вантажу j-г o типу, що дозволяє досягти max .

Процес вирішення даної задачі не є багатоетапним. Вона відноситься до класу задач цілочислового лінійного програмування. Однак її можна вирішити методом динамічного програмування. Для цього весь процес рішення буде потрібно розбити на етапи штучно. На першому етапі розглядають різні варіанти завантаження літака предметами першого типу і серед них знаходять оптимальний. На другому етапі визначають варіант завантаження літака предметами першого і другого типів і т.д. Процес рішення задачі продовжується до тих пір, поки не буде знайдений оптимальний варіант завантаження літака предметами n типів. [1, с 241]

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

1.1 Принцип оптимальності Беллмана

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

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

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

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

(1.3)

де - Оптимальне значення ефекту, що досягається за кроків; n - кількість кроків (етапів); - Стан системи на - М кроці; - Рішення (управління), обраний на - Му кроці; - Безпосередній ефект, що досягається на - Му кроці.

"Optimum" у виразі (1.3) означає максимум або мінімум в залежності від умови задачі. Усі обчислення, що дають можливість знайти оптимальне значення ефекту, що досягається за n кроків, | n (So), проводяться за формулою (1.3), яка носить назву основного функціонального рівняння Белмана або рекурентного співвідношення. Дійсно, при обчисленні чергового значення функції використовуються значення функції , Отримане на попередньому кроці, і безпосереднє значення ефекту , Що досягається в результаті вибору рішення при заданому стані системи . Процес обчислення значень функції здійснюється при природному початковому умови , яке означає, що за межами кінцевого стану системи ефект дорівнює нулю. [1, с 243]

1.2 Обчислювальна схема

Оптимальне рішення задачі методом динамічного програмування знаходиться на основі функціонального рівняння (1.3). Щоб визначити його, необхідно:

1. Записати функціональне рівняння для останнього стану процесу (йому відповідає ):

; (1.4)

2. Знайти з дискретного набору його значень при деяких фіксованих і з відповідних допустимих областей (так як , То ). У результаті після першого кроку відоме рішення і відповідне значення функції ;

3. Зменшити значення на одиницю і записати відповідне функціональне рівняння. При воно має вигляд:

; (1.5)

4. Знайти умовно-оптимальне рішення на основі виразу (1.5);

5. Перевірити, чому одно значення . Якщо розрахунок умовно-оптимальних рішень закінчений, при цьому знайдено оптимальне рішення задачі для першого стану процесу. Якщо перейти до виконання п. 3;

6. Обчислити оптимальне рішення задачі для кожного наступного кроку процесу, рухаючись від кінця розрахунків до початку. [1, с 244]

2. Рішення задачі оптимального розподілу коштів на розширення виробництва

2.1 Рішення задачі оптимального розподілу коштів на розширення виробництва ручним способом

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

Виробничому об'єднанню з чотирьох підприємств виділяється банківський кредит у сумі 60 млн. ден. од. для реконструкції і модернізації виробництва з метою збільшення випуску продукції. Значення додаткового доходу, отримуваного на підприємствах об'єднання залежно від виділеної суми xi, наведені в табл. 2.1. Розподілити виділений кредит між підприємствами так, щоб додатковий дохід об'єднання був максимальним. [1, с 261]

Таблиця 2.1 - Значення додаткового доходу

30