konspect_2010

Являє інтерес класифікація задач стохастичного програмування, що виникають за умов ризику та невизначеності за показником якості (ефективності) розв'язку.

Природно розглядати наступні показники якості розв'язку стохастичних задач, зокрема лінійних:

•математичне сподівання величини лінійної форми;

•дисперсія лінійної форми;

•лінійна комбінація математичного сподівання та дисперсії лінійної форми;

•ймовірність перевищення лінійною формою певної фіксованої

межи;

•математичне сподівання корисності лінійної форми;

•максимін лінійної форми (причому максимум береться з множини планів X , а мінімум – за допустимими значеннями набору параметрів, що визначають реалізацію випадкових елементів умов задачі тощо.

1.7.2 Класифікація задач стохастичного програмування

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

Для того, щоб задача стохастичного програмування мала сенс, необхідно відповісти на наступні три запитання:

1 Як розуміти вектор x ? Чи повинен він також бути випадковим (тобто кожному відповідає своє рішення x( ) , що

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

1Як розуміти максимізацію цільової функції? Як максимізацію абсолютну, для усіх , чи максимізацію її математичного сподівання, чи максимізацію деякої іншої її імовірнісної характеристики?

2Як розуміти виконання обмежень: аб солютно для всіх , чи у середньому, чи допускати їх порушення з малою ймовірністю тощо?

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

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

70

x( )

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

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

f (x, ) min (max)	(97)
при врахуванні обмежень
qi (x, ) 0,i 1,..., m ,	(98)
а також умов
x X .	(99)

Лінійну одноетапну модель стохастичного програмування можна подати у матрично-векторній формі:

C( )x min (max); A( )x b( ); x X .

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

1)рішення – спостереження – рішення –... – спостереження –

рішення;

2)спостереження – рішення – спостереження – ... – спостереження – рішення.

Низка рішень називається N -етапною, якщо слово «рішення» зустрічається N разів.

Якщо рішення х детерміноване і приймається перед тим, як спостерігається стан середовища , то співвідношенням (97)...(99) треба надати певний імовірнісний зміст, бо для фіксованого х для одних співвідношення (98) можуть виконуватися, і х виявиться допустимим розв'язком, а для інших можуть не виконуватися. У більшості

випадків є сенс у максимізації (мінімізації) математичного сподівання f (x, ) , тобто, необхідно відшукати такий вектор х, за якого досягається екстремум функції Mf (x, ) :

F 0 (x) Mf (x, ) f (x, )d ( ) min (max)	(100)

71

за умов

	F i (x) Mq (x, ) 0,i 1,..., m ;	(101)
	i
	x X .	(102)
Функцію	F 0 (x) називають функцією ризику, а	функціями
F i (x),i 1,..., m – регресії; ( ) – щільність розподілу.
Як вже	відзначалося, математичне сподівання функції	f (x, ) не

єдина імовірнісна характеристика. Розглядають також дисперсію функції

f (x, ) , чи моменти вищих порядків випадкової величини		f (x, ) , їх
алгебраїчні суми зважені за допомогою деяких коефіцієнтів, зокрема
F 0 (x) Mf (x, ) kDf (x, ) ,		(103)
ще k – ціна ризику
Приклад. Вибір запасів. Потрібно зробити	запас з n	товарів у
кількості (x1 , x2 ,..., xn ) , на які є випадковий попит	( 1 ,..., n ) . Нестача

запасених товарів штрафується з коефіцієнтами (c1 ,..., cn ) c , а затрати на

зберігання одиниці продукції, яку не вдалося збути, задаються вектором (d1 ,..., dn ) d .

Розв'язання. Функція збитків, що відповідає розв'язку х, має вид

n		j .
f (x, ) c j max( 0, j	x j ) d j max( 0, x j		(104)

j1

1.7.3Прийняття рішень за умов ризику. Зона невизначеності

Зоною невизначеності називається сукупність оптимальних планів,

залежних від випадкової ситуації , тобто зона			невизначеності	– це
x* ( ) /	[9]. Вона може бути апроксимована скінченною кількістю
оптимальних	планів	xs x( s ) / s 1,...n , яку	одержують на	базі

статистичного моделювання за методом Монте-Карло та числового розв'язку для кожного s задачі:

max (c( ), x) / A( )x b( ), x 0	(105)
.
x
Розв'язок цієї задачі позначимо через x( ) , тобто
x( ) arg max x( ), x / A( )x b( ), x 0 .	(106)
x

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

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

72

1,..., n

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

коригується за допомогою наперед визначеної множини адаптивних

технологій D( ) , шляхом вибору				їх інтенсивностей,		що	описуються
вектором у.
Адаптивність		—	це	здатність	економічної		системи
пристосовуватися до змін внутрішніх і зовнішніх умов.
Якщо d ( ) – вектори (стовпчики) питомих ефективних технологій
матриці D( ) ,	то при	фіксованих		х та доцільно обрати			план у як
розв'язок задачі:
			(d ( ), y) max				(107)
				y
за умов
		D( ) y b( ) A( )x; y 0 .					(108)
Розв'язок	задачі	(107-108)		позначають	через	y(x, ) . Звужена

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

x1 , y(x1 , 1 ), y(x1 , 2 ),..., y(x1 , k ), x2 , y(x 2 , 1 ), y(x 2 , 2 ),..., y(x 2 , k ),

...........................................................,	(109)
xk , y(x k1 , 1 ), y(x k , 2 ),..., y(x k , k ), де k n.

При виборі найкращого (раціонального) плану береться до уваги не лише ефективність основного плану x s , але й ефективність відповідної адаптації при різних .

Даний метод має такі особливості:

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

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

3)здійснюється найбільш ефективна адаптація для кожної реалізації випадкових ситуацій.

Прийняття адаптивних рішень за умов ризику

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

73

y(x, )

Програмна частина обирається з урахуванням того, що необхідно створювати найкращі умови для майбутньої адаптації і розрахована на ймовірні зміни випадкових ситуацій. Адаптивна частина реалізується після спостереження, тобто враховується вплив реалізації випадкового стану економічного середовища (ситуації). Використовуючи позначення: х - програмна частина плану, – параметри випадкової ситуації, у – адаптивна частина плану, схему можна подати у виді

x y(x, ) .		(110)
Нехай (х, у) — план певної економічної системи, що обирається з
допустимої множини планів X ( ) ), де	– випадкова	ситуація
(елементарна подія певного імовірнісного простору ( , A, P) ).		Суб'єкт

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

вектор-функція f (x, y, ) ( f1(x, y, ),..., fm (x, y, )) .					x1, y1	та	x2 , y2 , суб'єкт
Припустимо, що для будь-якої пари планів
керування	може	надати	перевагу	одному		з	розподілів

L( f , x1, y1, , P), L( f , x2 , y2 , , P) , або визначити їх еквівалентність, тобто на множині розподілів задано відношення пріоритетності ( – не гірше ніж). Тут через L( f , x, y, , P) , позначений розподіл f (x, y, ) , який залежить від х, у на множині елементарних подій та ймовірнісній мірі Р.

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

	(x, y) X ( ) та(x, y) (x, z) z (x, z) X ( ) .
Введемо	позначення	розв'язку	задачі	знаходження
найефективнішої адаптації [59]:
	(x, y) pref ,(x, y) X ( ) .			(111)
		y

Розв'язок (111) залежить як від обраного раніше (на попередній стадії) х, так і від , тобто y y(x, ) .

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

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

суб'єкта	управління.	Тобто,	необхідно	знайти
x* X x / зімовірністю1існує y X ( ) , при якому
	L( f , x*, y(x*, ), , P) L( f , x, y(x, ), , P) x X .			(112)

74

f 1(x, )

q(x)

Задачу знаходження x* позначають так:

L( f , x, y(x, ), , P) pref .

(113)

x X

Одноетапні статичні задачі управління виробництвом

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

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

Рішення за цих умов є детермінованим.

Розглянемо виробничо-економічну систему з певною потужністю (тут термін «потужність» можна замінити допустимим обсягом виготовлюваної продукції за одиницю часу), в якій треба визначити рівень (обсяг) виробництва деяких продуктів (набору продуктів) х, попит на які на ринку (у споживача) заздалегідь не відомий і вважається випадковою величиною . Позначимо через — величину загальних витрат при виробництві продукції. Позначимо також через

збитки, яких зазнає виробництво від недовипуску продукції, коли

x , а через	f 2 (x, )	— збитки, які виникають у тому разі, коли
виробництво перевищує		величину випадкового	попиту, тобто, коли
x . Ці випадки відображує функція виду
		f 1 (x, ), x ,
		f (x, )
		f 2 (x, ), x.
Нехай функції f 1		та f 2 при кожному	є опуклими вниз та

неперервно диференційованими за х.

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

F(x) q(x) Mf (x, ) min	(114)
при обмеженнях
x X ,	(115)

75

де X — деяка множина n -мірного простору, яка може бути утворена обмеженням, пов’язаним з потужністю підприємства, обсягами продукції. У випадку, коли максимізується прибуток від реалізації продукції, що виробляється

F(x) q(x) Mf (x, ) max .

Типові труднощі, що виникають при розв’язуванні одностайної задачі (114), (115), полягають у складності (або неможливості) точного обчислення значень функції сподіваних витрат F (x) та її градієнта, що пов’язане з обчисленням інтегралу виду

F (x) q(x) f (x, )d ( ) ,

де ( ) – функція розподілу випадкового параметру.

1.8Системи підтримки прийняття рішень [1, 8–9]

1.8.1 Сутність і загальна характеристика СППР

Термін СППР (DSS-Decision Support System) виник у 70-х роках ХХ століття і належить Горрі та Мортону. Оскільки СППР першого покоління мало чим відрізнялися від традиційних управлінських інформаційних систем, замість СППР часто застосовувався термін «системи управлінських рішень».

Досі немає єдиного визначення СППР. Наприклад, деякі автори під СППР розуміють «інтерактивну прикладну систему, що забезпечує кінцевим користувачам, які приймають рішення, легкий і зручний доступ до даних і моделей з метою прийняття рішень у напівструктурованих і неструктурованих ситуаціях з різних галузей людської діяльності». Відомі й інші означення, наприклад: «СППР — це такі системи, які грунтуються на використанні моделей і процедур з обробки даних та думок, що допомагають керівникові приймати рішення»; «СППР — інтерактивні автоматизовані системи, що допомагають особам, які приймають рішення, використовувати дані й моделі, щоб вирішувати неструктуровані та слабоструктуровані проблеми»; «СППР — комп’ю- терна інформаційна система, використовувана для підтримки різних видів діяльності під час прийняття рішень у ситуаціях, коли неможливо або небажано мати автоматичну систему, яка повністю виконує весь процес рішень». Нарешті, існує твердження, згідно з яким СППР являє собою специфічний і добре описуваний клас систем на базі персональних комп’ютерів.

76

Таке розмаїття означень систем підтримки прийняття рішень відбиває широкий діапазон різних форм, розмірів, типів СППР. Але практично всі види цих комп’ютерних систем характеризуються чіткою структурою, яка містить три головні компоненти: підсистему інтерфейсу користувача; підсистему управління базою даних і підсистему управління базою моделей (рис. 14). Ці три компоненти становлять основу класичної структури СППР, завдяки якій останні відрізняються від інших типів інформаційних систем, зокрема інформаційних систем, що грунтуються на використанні сховищ даних і мають таку саму англомовну абревіатуру

— DSS (про це йшлося в розд. 2). Останнім часом з розвитком мережі Інтернет до СППР додають новий компонент — систему управління поштою (повідомленнями) — СУП (див. рис. 14).

	База даних							База моделей

СУБД СУБМ Вивід

Інтерфейс

користувача

Рис. 14 – Класична структура СППР (СУБД — система управління базою даних; СУБМ — система управління базою моделей)

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

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

77

інтерактивності необхідна для дослідження нових проблем і ситуацій, під час адаптивного проектування прикладних СППР.

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

Потужність СППР означає здатність системи відповідати на найістотніші запитання.

Доступність СППР — це здатність забезпечувати видачу відповідей на запити користувача в потрібній формі і в необхідний час.

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

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

Робасність (robustness) СППР — це ступінь здатності системи відновлюватися в разі виникнення помилкових ситуацій як зовнішнього, так і внутрішнього походження. Наприклад, у робасній системі допускаються помилки у вхідній інформації або несправності апаратних засобів. Хоча між надійністю та робасністю може існувати певний зв’язок, ці дві характеристики системи різні: система, яка ніколи не поновлюватиметься в разі настання помилкових ситуацій, може бути надійною, не будучи робасною; система з високим рівнем робасності, яка може відновлюватися й продовжувати роботу в багатьох помилкових ситуаціях, може бути водночас віднесена до ненадійних, оскільки вона не здатна заздалегідь, до пошкодження виконати необхідні службові процедури.

Керованість СППР означає, що користувач може контролювати дії системи, втручаючись у хід розв’язування задачі.

Аналізуючи еволюцію систем підтримки прийняття рішень, можна вирізнити два покоління СППР: перше покоління розроблялося в період 1970 — 1980 років, друге — з початку 1980 року й донині (розробка нових типів триває).

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

управління даними — велика кількість інформації, внутрішні і зовнішні банки даних, обробка й оцінювання даних;

управління обчисленнями (моделювання) — моделі, розроблені спеціалістами в галузі інформатики для спеціальних проблем;

користувацький інтерфейс (мова спілкування) — мови програмування, створені для великих ЕОМ, які використовуються виключно програмістами.

СППР другого покоління уже мають принципово нові ознаки:

78

управління даними — необхідна і достатня кількість інформації про факти згідно зі сприйняттям ОПР, що охоплює приховані припущення, інтереси та якісні оцінки;

управління обчисленням і моделюванням — гнучкі моделі, які відтворюють спосіб мислення ОПР у процесі прийняття рішень;

користувацький інтерфейс — програмні засоби, «дружні» користувачеві, звичайна мова, безпосередня робота кінцевого користувача.

Мету і призначення СППР другого покоління можна визначити так:

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

допомога в розв’язуванні задачі: генерування і вибір моделей та методів, збір і підготовка даних, виконання обчислень, оформлення і видача результатів;

допомога щодо аналізу розв’язків, тобто проведення аналізу типу «Що ... коли ...?» і т.ін., пояснення ходу розв’язування, пошук і видача аналогічних рішень у минулому та їх наслідків.

Дружні людині СППР дають їй змогу вести рівноправний діалог із ПЕОМ, використовуючи звичні мови спілкування. Системи можуть «персоналізувати» користувача, підстроюватися під його стиль мислення, рівень знань і професійної підготовки, а також засоби роботи.

Сучасні комп’ютерні системи підтримки прийняття рішень мають такі характеристики:

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

2.СППР підтримує і посилює (але не замінює і не відміняє) міркування та оцінки керівника. Контроль лишається за людиною. Користувач «почуває себе комфортно» і «як удома» у системі, а не зазнає «залякування» з боку системи.

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

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

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

79