Методические указания

ДЯ.

АГ

И ИИ

Пп п

Ии 7


Складаємо характеристичне рівняння матриці С:


с„- Л

11 1

с

с

ИІ


с

222

;

и2

с


 

In

С

2п

С

;

с-Я


 


0.


3 цього рівняння визначаємо вектор характеристичних коренів:

А = (А1,А2,...,\).

Теорема. Квадратична форма є додатно (від’ємно) визначеною тільки тоді, коли всі компоненти вектора характеристичних коренів є додатними (від’ємними).

Якщо власні числа мають різні знаки, то квадратична форма є невизначеною.

Задача квадратичного програмування - це задача виду

f{xx, х2,..., хп) = £ djXj + X Z cijxixj -^ extr

y=i

i=i j=i

при обмеженнях

n

Ifl.x <b.,i = l,m; x >0, j = l,n,

n n

де YsYscijxixj - додатно (від’ємно) напіввизначена квадратична

і'=1 7=1

форма.

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


__ о

 

__0


+ v. =o,j = l,n:

w =0,i = 1, m:


x°y.=0,j = l,n;

• Xwt=0,i = l,m;

x° >0Д° >0,v>0,w >0.

j ' j '

I.

Теорема. Х°є оптимальным розв’язком задачі квадратичного програмування тільки тоді, коли існують такі w-вимірні вектори Л° >0, w > 0 і я-вимірний вектор V>0, для яких виконуються умови: дЬ(Х°;А°)

дх°

1 J ?

II. v.x°=0, j = l,n.

dL(X°;A°) —

III. -w.=0.i = l,m.

IV. wl°= Ол'= 1, w.

7.3. Прикладне використання методу множників Лагранжа

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

Z = f(xl,x2,..., хп) -»max

qi(xl,x2,...,xn)<bi, i = l,m,

x.>0, j = 1, п.

Головною метою виробництва продукції є отримання найбільшого прибутку від 'п'реалізації, тому цільовою функцією Z задачі є прибуток від реалізації продукції обсягом Х=(хh х2,...хn) одиниць. Зауважимо, що функщя/хь хъ ...х„) - нелінійна.

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

qi(xl,x2,...,xn)<bi, (i = l,m) у вигляді

di(X) = bi -g.(x1;x2,...,xj>0, (i = l,m). Тобто, якщо qi(xl,x2,...,xn) - обсяг сировини i-ro виду, що

використовується для виробництва всієї продукції, то dj(X) - залишок цього ресурсу після ЇЇ виробництва. Якщо ф(Х)=0, то сировина використана повністю; якщо dj(X)>0, то на виробництво продукції використана не вся сировина; якщо dt{X) <0, то наявної сировини не вистачає для виробництва продукції.

Розглянемо функцію Лагранжа для описуваної задачі:

т

L(x, A, b) = f{x) + X Л(Яі(х) ~ ^і) ■

і=\

Очевидно, що ; = Я., тобто ця похідна показує, як

dbi

змінюється значения цільової функції залежно від обмежень. Множники Лагранжа є двоїстими змінними задачі про використання ресурсів. Вони можуть бути ціною, за якою на ринку продається чи купується одиниця і-го виду сировини. Якщо Аг > 0 і djiX)>0, то

можна продати залишки сировини і отримати додатковий прибуток в розмірі ЯД.(Х). Якщо ж djiX)<0, то можна купити потрібну кількість,

витративши ЯД.(Х) грошових одиниць і забезпечити виробництво

продукції обсягом Х=iхh хъ...хп). Функцію Лагранжа можна трактувати як загальний прибуток від виробництва, який містить прибуток від реалізації виготовленої продукції fix) та прибуток від продажу залишків сировини (або витрати на придбання потрібної

т

кількості сировини) Х^ДС^О-

 

ТЕМА 8. ДИНАМІЧЕ ПРОГРАМУВАННЯ

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

8.2 Методи розв’язування задач динамічного програмування.

8.3 Прикладні моделі динамічного програмування.

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

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

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

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

Позначимо через xkeUk керування на к-му кроці (к= 1,п), де Uk - множина допустимих керувань на к-му кроці.

Нехай х = (х1,х2,...,хп) - керування, яке переводить систему з

стану S0 в Sn. Позначимо через Sk стан системи після к-го кроку керування. Отримуємо послідовність станів S0,S1,...,Sk_1,Sk,Sk+1,...,Sn

(рис.7.1.1).

 

Рисунок 8.1. Схематичне зображення процесу керування

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

Z = F(S0,x). (8.1)

Власне, задача динамічного програмування формулюється

таким чином: знайти таке значения керованої змінної х\ яке переводить систему з початкового стану S0 в кінцевий S„, при якому цільова функція (7.1) набуває найбільшого (найменшого) значения.

Розглянемо характерні особливості математичної моделі динамічного програмування:

1) задача оптимізації формулюється як скінчений багатокроковий процес управління;

2) цільова функція (7.1) є адитивною від показника ефективності кожного кроку, тобто виграш від всієї операції складається з виграшів, отриманих на кожному кроці.

п

Z = F(S0,x) = YJFk(Sk_l,xk), (8.2)

к=\

де Fk(Sk_l9xk) = Zk- показник ефективності на к-му кроці;

3) вибір керування хкна кожному кроці залежить тільки від стану системи до цього кроку і не впливає на попередні кроки (немає зворотного зв’язку);

4) стан системи Sk після кожного кроку керування залежить тільки від попереднього стану системи Sk.j iкеруючої дії хk на &-му кроці та не залежить від попередніх станів системи і керувань (відсутність післядії):

Sk=<pk(Sk_l,xk), к= 1,п,(8.3)

де (рк - оператор переходу;

5) на кожному кроці керування хкзалежить від скінченого числа керованих змінних, а стан системи Sk залежить від скінченого числа параметрів;

6) оптимальним керуванням є вектор х , який знаходиться шляхом послідовних оптимальних покрокових керувань:

х* =(xl,x*2,...,x*k,...,x*n), кількість яких і визначає число кроків

задачі.

8.2. Методи розв’язування задач динамічного програмування

Нехай процес оптимізації розбитий на п кроків. На кожному кроці потрібно визначити два типи змінних - змінну стану S та змінну керування х. Змінна стану S визначає, в яких станах може бути система на к-му кроці. Залежно від S на цьому кроці можна використати деякі керування, які характеризуються змінною х. Використання керування х на к-му кроці дає деякий результат fk(S,xk) iпереводить систему в деякий новий стан S'(S,xk). Для

кожного можливого стану на к-му кроці (з усіх можливих керувань) вибирається таке керування хк, щоб результат, якии отримаємо з к-то

по п-ии крок був оптимальним. Числова характеристика цього результату називається функцією Белмана Fk(S) та залежить від

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

Весь розв’язок задачі розбивається на два етапи. На першому етапі знаходять функцію Белмана й оптимальне керування для всіх можливих станів на кожному кроці, починаючи з першого. На останньому п-му кроці знайти оптимальне керування і значения функції Белмана Fn(S) нескладно, оскільки Fn(S) = max{fk(S,xn)}, де

максимум знаходять за всіма можливими значениями х„.

Подальші розрахунки проводять згідно з рекурентним співвідношенням, яке пов’язує функцію Белмана на кожному кроці з тією ж функцією, обчисленою на попередньому кроці:

Fk(S) = max{fk(S,,xk) + Fk_l(S,xk)}. (7.4)

Цей максимум (чи мінімум) знаходиться за всіма можливими для к iS значениями керованої змінної хk.

Після того, як функція Белмана і відповідне оптимальне керування знайдені для всіх кроків з першого до п-то (на першому кроці k=l стан системи рівний її початковому стану So), виконуємо другий етап розв’язання задачі згідно з алгоритмом зворотної прогонки. Знаючи оптимальне керування на и-му кроці хп, ми можемо шукати оптимальне керування на (п-\) кроці доти, доки не дійдемо до першого.

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

8.3. Прикладні моделі динамічного програмування

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

8.3.1. Модель оптимального розподілу фінансових ресурсів між інвестиційними проектами

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

Позначимо через xі - розмір інвестицій, виділених під і-ий проект (/'= \,п\, де і - індекс проекту. Отже, має місце рівність:

хх +х2 +... + хп=х. (8.5)

На основі попереднього аналізу встановлено, що приріст продукції внаслідок реалізації і-го проекту задається функцією Дх.).

Тоді сумарний приріст продукції фірми становитиме:

п

F(x1,x2,...xn) = Yifi(xi). (8.6)

і=\

Отже, наша задача полягає у заходженні таких значень х. >0(і= 1,гі), які задовольняють (7.5) і забезпечують максимум функції (7.6).

Позначимо максимальний сумарний приріст продукції, одержаний при розподілі інвестицій розміром х для перших к проектів, через Fk(x), причому

х = х1 +х2 +... + хк, х. >0, i = l,k. Для визначення функцій Fk(x) побудуємо рекурентне рівняння за допомогою кількох етапів.

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

Fx(x) = maxj_fi (*)]= Л(х).

Переходимо до другого етапу розрахунків. Нам необхідно знайти оптимальний варіант розподілу інвестицій розміром х за умови, що вони виділені першому та другому проекту. Тут слід враховувати отриману найкращу ефективність для першого проекту. Припустимо, що на другий проект виділені інвестиції розміром х2, які дають fiiхi) приросту продукції, а залишок (х-х2) виділяється першому проекту, який дає Fi(х-х2) приросту. Тоді максимальний приріст продукції, отриманий від оптимального розподілу всіх інвестицій між першим і другим проектами буде:

F2 (х) = max Г/2 (х2) + Fx(х- х2)].

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

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

Наявний залишок (х-х3) надамо першому та другому проектам, які

при оптимальному розподілі дають приріст F2(x-x3) грошових

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

F3(x) = max[f3(x3) + F2(x-x3)].

Розглянемо загальний випадок розподілу інвестицій для перших к проектів. Нехай к-му проекту виділено хк одиниць інвестицій, які забезпечать йому приріст продукції розміром fk(хk). Залишок інвестицій (х-хk) віддамо першим (1-1) проектам і вони при оптимальному розподілі принесуть фірмі Fk_i(х-хk) приросту продукції. При цьому фірма отримає сумарний приріст продукції рівний:

Fk(x)=max fk(xk) +Fk_l[x-xk)j. (8.7)

0<x<x

Отже, ми отримали рекурентне співвідношення (8.7), яке представляє собою рівняння Белмана для задачі (8.5) – (8.6).

ЗМІСТ

Вступ ТЕМА 1. ПРЕДМЕТ, МЕТОД І ЗАДАЧІ КУРСУ 1.5 Основні дефініції математичного моделювання. 1.6 Моделювання в економіці та його використання в розвитку та формалізації економічної теорії. 1.7 Теоретичні основи математичного моделювання та класифікація моделей. 1.8 Математична модель та її основні елементи. 1.9 Принципи та етапи побудови моделей.   ТЕМА 2. ФУНКЦІЇ І ГРАФІКИ В ЕКОМІЧНОМУ МОДЕЛЮВАННІ 2.1 Поняття функціональної залежності. 2.2 Способи завдання та дослідження функцій. 2.3. Основні елементарні функції.   ТЕМА 3. МОДЕЛІ ЗАДАЧ ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА МЕТОДИ ЇХ РОЗВ'ЯЗУВАННЯ 3.1 Постановка задач лінійного програмування, їх моделі та основні форми. 3.2 Графічний метод розв'язування задач лінійного програмування. 3.3 Симплексний метод розв'язування задач лінійного програмування.   ТЕМА 4. ТЕОРІЯ ДВОЇСТОСТІ ТА КІЛЬКІСНИЙ АНАЛІЗ ОПТИМІЗАЦІЙНИХ РОЗРАХУКІВ 4.1 Двоїстість у задачах лінійного програмування. 4.2 Основні теореми двоїстості. 4.3 Двоїстий симплекс-метод. 4.4 Економіко-математичний аналіз оптимальних розрахунків. ТЕМА 5. ТРАНСПОРТНА ЗАДАЧА 5.1 Постановка транспортної задачі та її математична модель. 5.2 Методи побудови початкового опорного плану. 5.3 Метод потенціалів. 5.4 Практичне застосування транспортної задачі. Модель оптимального розподілу фінансових ресурсів банку. Модель оптимізації штатного розпису фірми. ТЕМА 6. ЗАДАЧІ ЦІЛОЧИСЛОВОГО ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА МЕТОДИ ЇХ РОЗВ'ЯЗАННЯ 6.1 Постановка задачі цілочислового лінійного програмування. 6.2 Методи розв'язування задач цілочислового лінійного програмування. 6.3 Прикладні моделі задач цілочислового лінійного програмування. ТЕМА 7. НЕЛІНІЙНІ ОПТИМІЗАЦІЙНІ МОДЕЛІ ЕКОНОМІЧНИХ СИСТЕМ 7.1 Постановка задачі нелінійного програмування та її характерні особливості. 7.2 Основні види задач нелінійного програмування. Прикладне використання методу множників Лагранжа.   ТЕМА 8. ДИНАМІЧЕ ПРОГРАМУВАННЯ 8.1 Постановка задачі динамічного програмування. 8.2 Методи розв’язування задач динамічного програмування. 8.3 Прикладні моделі динамічного програмування.  

 

3.РЕКОМЕНДОВАНА ЛІТЕРАТУРА

Законодавчі та нормативно-правові документи

1. Закон України «Про електронні документи та електронний документообіг» від 31.05.2005 року.

2. Закон України «Про захист інформації в автоматизованих системах» від 05.07.1994 року. Про захист інформації в інформаційно-телекомунікаційних системах(Відомості Верховної Ради України (ВВР), 1994, N 31, ст.286 ). Із змінами, внесеними згідно із Законом N 1703-IV (1703-15) від 11.05.2004, ВВР, 2004, N 32, ст.394. В редакції Закону N 2594-IV (2594-15) від 31.05.2005, ВВР, 2005, N 26, ст.34. Із змінами, внесеними згідно із Законами N 879-VI (879-17) від 15.01.2009, ВВР, 2009, N 24, ст.296 N 1180-VI (1180-17) від 19.03.2009, ВВР, 2009, N 32-33, ст.485).

3. Закон України «Про інформацію» від 06.04.2000 року.

4. Закон України «Про Концепцію Національної програми інформатизації» від 09.02.2006 року.

5. Закон України «Про науково-технічну інформацію» від 20.11.2003 року.

6. Закон України «Про національну програму інформатизації» від 13.09.2001 року. Із змінами, внесеними згідно із Законами N 2684-III (2684-14) від 13.09.2001, ВВР, 2002, N 1, ст.3 N 2289-VI (2289-17) від 01.06.2010, ВВР, 2010, N 33, ст.471 Базова література1. Боровик О.В., Боровик Л.В. Дослідження операцій в економіці. Навч. пос. / О.В.Боровик, Л.В.Боровик – К.: ЦУЛ, 2007. – 424 с.

2. Бугір М.К. Математика для економістів: Посібник. / М.К.Бугір – К.: ВЦ «Академія», 2003. – 520 с.

3. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування. / В.В.Вітлінський, С.І.Наконечний, Т.О.Терещенко -Київ, 2001.

4. Вовк В.М., Дрогомирецька З.Б. Основи системного аналізу. Навч. посібник. / В.М.Вовк., З.Б.Дрогомирецька – Львів : ВЦ ЛНУ ім. Івана Франка, 2002. – 248с.

5. Глушик М.М., Копич І.М., Пенцак О.С., Сороківський В.М. Математичне програмування: Навч. пос. / М.М.Глушик, І.М. Копич, О.С.Пенцак – Львів: «Новий світ-2000», 2006. – 216 с.

6. Дацко М.В., Карбовник М.М. Дослідження операцій. Навч. пос. / М.В. Дацко, М.М. Карбовник – Львів, 2009. – 288 с.

7. Економіко-математичне моделювання: Навчальний посібник / За ред. О.Т.Іващука – Тернопіль: ТНЕУ «Економічна думка», 2008. – 704 с.

8. Катренко А.В. Дослідження операцій: Підручник. / А.В.Катренко – Львів: «Магнолія Плюс», 2005. – 549 с.

9. Кігель В.Р. Математичні методи ринкової економіки: Навчальний посібник. / В.Р. Кігель. – К.: Кондор, 2003. – 158 с.

10. Карагодова О.О., Кігель В.Р., Рожок В.Д. Дослідження операцій: Навч. пос. / О.О.Карагодова, В.Р.Кігель, В.Д.Рожок – К.: ЦУЛ, 2007. – 256 с.

11. Крутовецький В.Я. Дослідження операцій. Навч. посібник. / В.Я.Крутовецький – К.: ВД «Професіонал», 2005. – 264 с.

12. Лавренчук В.П., Букатар М.І., Готинчан Т.І., Пасічник Г.С. Математичні методи дослідження операцій: Навч. пос. / В.П.Лавренчук, М.І. Букатар, Т.І.Готинчан – Чернівці, 2005. – 360 с.

13. Федоренко І.К., Черняк О.І. Дослідження операцій в економіці: Підручник / І.К.Федоренко, О.І.Черняк – К.: Знання, 2007. – 558 с.

14. Чемерис А. Методи оптимізації в економіці: Навчальний посібник. / А.Чемерис, Р.Юринець, О.Мищишин. – К.: Центр навчальної літератури, 2006. – 152 с.

Допоміжна література

1. Гладунський В.Н. Логіка для студентів економічних спеціальностей. / В.Н. Гладунський. – Львів, Афіша, 2002.

2. Грубер Й. Економетрія. Том 2. Економічні прогнозні та оптимізаційні моделі: Навчальний посібник. / Й.Грубер – К.: Нічлава, 2002. – 296 с.

3. Теория прогнозирования и принятия решений. /Под ред. С.А.Саркисяна. – М.: Высш. шк., 2002. – 351 с.

4. Электронный бизнес: эволюция и / или революция: Пер. с англ. - М.: Издательский дом “Вильямс”, 2001. – 752 с.

Інформаційні ресурси

1.http://buklib.net/

2. http://www.doclist.ru/ebooks/download_file/746091.html

3. http://www.flomaster.ua

4. http://institutiones.com/

5. http://intkonf.org/

6. http://library.iapm.edu.ua

7. http://library.if.ua/book/32/2133.html

8. http://www.manager.com.ua

9. http://www.manager-erp.com

10. http://osvita-ua.net/school/manage/299

11. http://www.allbest.ru/

12. http://www.management.com.ua/

13. http://ndipit.com.ua Науково-дослідний інститут прикладних інформаційних технологій