Моклячук М.П., Ямненко Р.Є. Лекції з теорії вибору та прийняття рішень (на укр. языке)

Подождите немного. Документ загружается.

М.П. Моклячук

Р.Є. Ямненко

ЛЕКЦIЇ З ТЕОРIЇ ВИБОРУ

ТА ПРИЙНЯТТЯ РIШЕНЬ.

Київ

2007

ЗМIСТ

Передмова........................................................................5

Роздiл I. Задачi лiнiйного програмування........................................6

1.1.Приклади задач лiнiйного програмування...................................6

1.1.1. Задача про розподiл ресурсiв..........................................6

1.1.2. Задача про перевезення (транспортна задача)..........................8

1.1.3. Задача про харчовий рацiон (задача про дiєту)........................8

1.2.Задача лiнiйного програмування у загальнiй формi.........................9

1.3.Властивостi допустимої областi............................................10

1.3.1. Опуклi множини......................................................10

1.3.2. Проекцiя точки на множину..........................................14

1.3.3. Роздiляючi та опорнi гiперплощини...................................16

1.3.4. Крайнi точки опуклої множини.......................................18

1.4.Геометрична iнтерпретацiя задач лiнiйного програмування................20

1.4.1. Задача про розподiл ресурсiв.........................................23

1.4.2. Задача про перевезення...............................................26

1.4.3. Задача про харчовий рацiон..........................................28

1.4.4. Контрольнi запитання i задачi для самостiйної роботи................29

1.5.Стандартна форма задачi лiнiйного програмування........................39

1.6.Канонiчна форма задачi лiнiйного програмування.........................43

1.7.Симплекс-метод. Критерiй оптимальностi..................................46

1.8.Приклади розв’язування задач симплекс-методом..........................51

1.8.1. Задача про розподiл ресурсiв.........................................51

1.8.2. Задача про перевезення...............................................54

1.8.3. М-метод..............................................................56

1.8.4. Контрольнi запитання i задачi для самостiйної роботи................59

1.9.Двоїстi задачi лiнiйного програмування...................................64

1.10.Двоїстий критерiй оптимальностi..........................................67

1.11.Економiчна iнтерпретацiя двоїстої задачi..................................67

1.11.1. Приклад двоїстої задачi лiнiйного програмування...................69

1.11.2. Контрольнi запитання i задачi для самостiйної роботи..............72

1.12.Транспортна задача лiнiйного програмування..............................75

1.13.Двоїстий критерiй оптимальностi для транспортної задачi.................83

1.14.Транспортна задача з промiжними пунктами перевезення.................87

1.14.1. Контрольнi запитання i задачi для самостiйної роботи..............92

Роздiл II. Елементи теорiї iгор..................................................97

2.1.Матричнi iгри.............................................................97

2.2.Матричнi iгри з сiдловими точками.......................................98

2.2.1. Контрольнi запитання i задачi для самостiйної роботи..............105

2.3.Основна теорема матричних iгор.........................................108

2.4.Властивостi оптимальних стратегiй гри..................................115

2.5.Спрощення матричних iгор...............................................117

2.6.Графiчний метод розв’язування матричних iгор...........................121

2.6.1. Контрольнi запитання i задачi для самостiйної роботи..............123

2.7.Матричнi iгри та лiнiйне програмування.................................125

2.7.1. Контрольнi запитання i задачi для самостiйної роботи...............129

2.8.Множина всiх розв’язкiв гри.............................................131

2.8.1. Контрольнi запитання i задачi для самостiйної роботи..............138

2.9.Бiматричнi iгри...........................................................139

2.9.1. Контрольнi запитання i задачi для самостiйної роботи..............156

2.10.Позицiйнi iгри............................................................158

2.10.1. Контрольнi запитання i задачi для самостiйної роботи.............168

Роздiл III. Оптимальнi cтатистичнi рiшення ...................................173

3.1.Вступ.....................................................................173

3.2.Байєсiвський ризик i байєсiвськi рiшення................................174

3.3.Рандомiзацiя i змiшанi рiшення..........................................176

3.4. Задачi зi скiнченними просторами ........................................178

3.5. Процедури прийняття рiшень в умовах невизначеностi ...................181

3.5.1. Контрольнi запитання i задачi для самостiйної роботи..............187

3.6.Задачi зi спостереженнями...............................................189

3.7.Побудова байєсiвских функцiй...........................................191

3.8.Цiна спостереження......................................................194

3.9.Cпостереження в кiлька етапiв...........................................199

3.9.1. Задачi для самостiйної роботи.......................................200

Роздiл IV. Спряженi апрiорнi розподiли........................................207

4.1.Деякi найбiльш типовi розподiли.........................................207

4.2.Спряженi сiмейства розподiлiв...........................................213

4.3.Спряженi сiмейства для вибiрок iз стандартних розподiлiв...............214

4.4.Спряженi сiмейства для вибiрок з нормального розподiлу................216

4.5.Вибiрка з рiвномiрного розподiлу.........................................220

4.6.Вибiрка з мультиномiального розподiлу..................................222

4.7.1. Задачi для самостiйної роботи.......................................223

Роздiл V. Оцiнювання. ........................................................227

5.1.Оцiнювання параметра...................................................227

5.2.Квадратична функцiя втрат..............................................228

5.3.Втрати пропорцiйнi абсолютнiй величинi похибки........................230

5.4.Оцiнювання векторного параметра.......................................232

5.4.1. Задачi для самостiйної роботи.......................................234

Роздiл VI. Динамiчне програмування..........................................238

6.1.Метод рекурентних спiввiдношень. Принцип оптимальностi.............238

6.2.Аналiз динамiчних процесiв. Задача керування запасами................241

6.3.Задача про оптимальнi iнвестицiї ........................................249

6.3.1. Задачi для самостiйної роботи.......................................252

Список рекомендованої лiтератури.............................................257

Передмова

Навчальний посiбник написаний на основi лекцiй з курсу “Теорiя

вибору та прийняття рiшень”, якi читаються студентам третього курсу

механiко-математичного факультету Київського нацiонального унiверси-

тету iменi Тараса Шевченка протягом останнiх 10 рокiв.

В першому роздiлi “Задачi лiнiйного програмування” детально ви-

кладенi основнi поняття, теореми i результати лiнiйного програмування,

наведено основнi методи розв’язування задач такi, як симплекс-метод та

метод потенцiалiв. Детально описанi та вивчаються основнi задачi лiнiй-

ного програмування такi, як задача про використання сировини, задача

про оптимальний рацiон харчування, транспортна задача.

У другому роздiлi “Елементи теорiї iгор” висвiтленi основнi теореми

та методи теорiї iгор. Основну увагу придiлено матричним та позицiй-

ним iграм. Доведено основну теорему теорiї антагонiстичних iгор. Ви-

вчаються властивостi оптимальних стратегiй гравцiв. Висвiтленi основнi

поняття, теореми i результати бiматричних iгор.

Третий роздiл “Оптимальнi cтатистичнi рiшення” посiбника мiстить

основнi результати теорiї статистичних рiшень. Основну увагу придiлено

байесiвському пiдходу до прийняття рiшень.

У четвертому роздiлi “Спряженi апрiорнi розподiли” описанi основ-

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

невiдомих параметрiв. Цим задачам присвячений пятий роздiл “Оцiню-

вання”, в якому описаний байесiвський пiдхiд до задач оцiнювання не-

вiдомих параметрiв. Основну увагу придiлено оцiнкам, що мiнiмiзують

середньоквадратичнi та абсолютнi похибки.

У шостому роздiлi “Динамiчне програмування” описаний метод ди-

намiчного програмування Беллмана та його застосування до розвязання

задач мiкроекономiки таких як задача керування запасами, задача про

оптимальнi iнвестицiї.

В посiбнику наведено цiлий ряд прикладiв розв’язання задач лiнiйно-

го та динамiчного програмування, теорiї iгор, знаходження оптимальних

статистичних рiшень. Велика кiлькiсть задач запропонована для само-

стiйного розв’язання.

Навчальний посiбник пiдготовлений та виданий за пiдтримки програ-

ми Tempus у рамках проекту TEMPUS PROJECT IB-JET-25054-2004.

Автори користується нагодою щоб висловити подяку за пiдтримку ко-

ординаторам проекту професору Сiльвестрову Дмитру Сергiйовичу та

Сiльвестровiй Евелiнi Дмитрiвнi (Малардаленський унiверситет, Шве-

цiя).

Роздiл I

Задачi лiнiйного програмування

Вперше постановка задачi лiнiйного програмування та один iз методiв

її розв’язання були запропонованi Л. В. Канторовичем у роботi “Матема-

тические методы организации и планирования производства” у 1939 роцi.

У 1947 роцi Дж. Данцiг розробив симплексний метод (симплекс-метод)

– один iз основних методiв розв’язування задач лiнiйного програмуван-

ня. Вiн першим ввiв термiн “лiнiйне програмування” (linear programmi-

ng), що означає в даному випадку “планування”. З-помiж економiстiв,

якi займалися такими задачами, слiд вiдмiтити перш за все Т. Купман-

са. За роботи в областi лiнiйного програмування Л. В. Канторовичу та

Т. Купмансу в 1975 р. була присуджена Нобелiвська премiя з економi-

ки. Вiдтодi теорiя лiнiйного програмування бурхливо розвивалася i нинi

носить цiлiсний i, в основному, закiнчений характер. Загальна теорiя

лiнiйного програмування створена колективом математикiв, серед яких

слiд вiдзначити Г. Куна, А. Таккера, Дж. фон Неймана. Зауважимо, що

на її розвиток суттєво впливало можливiсть застосування до розв’язува-

ння (з широким використанням ЕОМ) прикладних задач, пов’язаних з

оптимальним плануванням, органiзацiєю та управлiнням у рiзноманiтних

сферах людської дiяльностi. Знайомство з теорiєю лiнiйного програму-

вання розпочнемо з розгляду типових прикладiв.

1.1. ПРИКЛАДИ ЗАДАЧ ЛIНIЙНОГО ПРОГРАМУВАННЯ

1.1.1. Задача про розподiл ресурсiв

Пiдприємство може реалiзувати n виробничо-технологiчних процесiв

,...,P

,використовуючидляцьогоресурсиR

,..., R

.Вiдомо,що:

а) пiдприємство має

одиниць ресурсу R

,i =1,...,m;

б) витрати ресурсу

на одиницю продукцiї, що виготовляється за

технологiєю

, дорiвнюють a

;

в) реалiзацiя одиницi продукцiї, виготовленої за технологiєю

,при-

носить пiдприємству прибуток

Задача полягає у визначеннi об’єму

виробництва продукцiї за те-

хнологiєю

,j =1,...,n, що максимiзує за вказаних умов прибуток

пiдприємства.

Сформульована задача формально зводиться до знаходження вектора

x =(x

,...,x

), який максимiзує функцiю



j=1

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



j=1

≤ b

,i=1,...,m;

≥ 0,j=1,...,n.

Табл.1.1.1

Види Запаси Види продукцiї

сировини сировини P

19 2 3

13 2 1

15 0 3

18 3 0

Прибуток 7 5

Розглянемо числовий приклад такої задачi (див. таблицю 1.1.1).

Припустимо, що пiдприємство випускає

одиниць продукцiї виду P

та x

одиниць продукцiї виду P

. Для цього потрiбнi 2x

+3x

одиниць

сировини

.Оскiлькивнаявностiєвсього19 одиниць сировини R

то повинна виконуватися нерiвнiсть

+3x

≤ 19.Нерiвнiсть(ане

точна рiвнiсть) з’являється через те, що максимальний прибуток може

досягатися пiдприємством i у тому випадку, коли запаси сировини виду

використовуються не повнiстю.

Аналогiчнi мiркування щодо iнших видiв сировини дозволяють запи-

сати наступнi нерiвностi:

+ x

≤ 13 (сировина R

≤ 15 (сировина R

≤ 18 (сировина R

За цих умов прибуток F пiдприємства складе F =7x

+5x

Таким чином, математично задачу можна сформулювати так.

Дано систему

+3x

≤ 19,

+ x

≤ 13,

≤ 15,

≤ 18











чотирьох лiнiйних нерiвностей i лiнiйна форма

F =7x

+5x

Серед невiд’ємних розв’язкiв системи потрiбно вибрати такий, при якому

форма

F приймає найбiльше значення.

1.1.2. Задача про перевезення (транспортна задача)

УпунктахP

,i =1,...,m, виробляється деякий однорiдний продукт,

причому в пунктi

виробляється a

одиниць цього продукту. У пунктi

,j =1,...,n,споживаєтьсяb

одиниць цього ж продукту. Припустимо,

що виконується умова балансу



i=1



j=1

Нехай c

– собiвартiсть перевезення одиницi продукту з пункту виро-

бництва

у пункт споживання Q

(транспортнi витрати). Необхiдно

знайти план перевезень продукту таким чином, щоб задовольнити по-

треби всiх споживачiв i мiнiмiзувати при цьому загальнi транспортнi ви-

трати. Нехай

– кiлькiсть продукту, що планується для перевезення

в Q

. Тодi транспортна задача, яку прийнято називати транспорт-

ною задачею лiнiйного програмування (ТЗЛП), полягає у знаходженнi

матрицi перевезень

X = {x

}

j=1,...,n

i=1,...,m

, яка мiнiмiзує загальнi транспортнi

витрати



i=1



j=1

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



j=1

= a

,i=1,...,m;



i=1

= b

,j=1,...,n;

≥ 0,i=1,...,m; j =1,...,n.











(1.1.1)

1.1.3. Задача про харчовий рацiон (задача про дiєту)

Харчовий рацiон може складатися з продуктiв P

,...,P

(хлiб, ма-

сло, молоко i т. iн.). Вiдомо, що в одиницi продукту

мiститься a

,i =

1,...,m

, одиниць поживної речовини V

(бiлки, жири, вуглеводи i т. iн.)

Нехай

,j =1,...,n, – вартiсть одиницi продукту P

.Припускається,

що харчовий рацiон повинен мiстити не менше

одиниць речовини V

При вказаних обмеженнях потрiбно знайти рацiон, що мiнiмiзує вартiсть

спожитих продуктiв. Формалiзуємо задачу. Нехай x

,j =1,...,n,–кiль-

кiсть продукту

урацiонi.Тодiвекторx =(x

,...,x

) визначає деякий

рацiон вартiстю



j=1

Кiлькiсть поживної речовини V

урацiонix =(x

,...,x

) дорiвнює



j=1

Таким чином, задача про харчовий рацiон зводиться до мiнiмiзацiї фун-

кцiї

F =



j=1

(1.1.2)

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



j=1

≥ b

,i=1,...,m;

≥ 0,j=1,...,n.







(1.1.3)

Незважаючи на змiстовнi вiдмiнностi, усi поданi приклади мають ба-

гато спiльного. Це спiльне полягає у знаходженнi мiнiмуму (максимуму)

лiнiйної функцiї при лiнiйних обмеженнях (рiвностях або нерiвностях).

1.2. ЗАДАЧА ЛIНIЙНОГО ПРОГРАМУВАННЯ У

ЗАГАЛЬНIЙ ФОРМI

У прикладах, що розглядалися у попередньому параграфi, задача зво-

диться до такої: знайти сукупнiсть змiнних, що задовольняють системi

обмежень у формi лiнiйних рiвностей чи лiнiйних нерiвностей i мiнiмi-

зують (максимiзують) лiнiйну функцiю.

Означення 1.2.1. Задача лiнiйного програмування у загальнiй формi –

це така задача:

Знайти точку

x =(x

,...,x

) n-вимiрного простору R

, що задоволь-

няє системi обмежень:



j=1

= b

,i=1,...,r; (1.2.1)



j=1

≤ b

,i= r +1,...,l; (1.2.2)



j=1

≥ b

,i= l +1,...,m; (1.2.3)

≥ 0,j=1,...,k, k ≤ n, (1.2.4)

i мiнiмiзує (максимiзує) лiнiйну функцiю

f(x)=(c,x)=



j=1

. (1.2.5)

Означення 1.2.2. Множина точок, якi задовольняють обмеженням (1.2.1)–

(1.2.4), називається допустимою множиною iпозначаєтьсябуквою

Будь-яка точка допустимої множини називається допустимою точкою

(допустимим розв’язком). Лiнiйна функцiя

f(x)=(c,x) називається

функцiєю цiлi. Допустима точка, що мiнiмiзує (максимiзує) функцiю

цiлi, називається розв’язком задачi лiнiйного програмування.

Якщо система (1.2.1) – (1.2.4) має принаймнi один розв’язок, то вона

називається сумiсною,вiншомувипадку–несумiсною.Допустимамно-

жина задачi лiнiйного програмування непорожня, якщо система (1.2.1)

– (1.2.4) сумiсна.

Очевидно, що задача максимiзацiї функцiї

f(x)=(c,x) еквiвален-

тна задачi мiнiмiзацiї функцiї

g(x)=−(c,x).Томувбiльшостiвипадкiв

будемо розглядати задачу мiнiмiзацiї функцiї цiлi

f(x)=(c,x).

1.3. ВЛАСТИВОСТI ДОПУСТИМОЇ ОБЛАСТI

1.3.1. Опуклi множини

Означення 1.3.1.Вiдрiзком,щоз’єднуєточкиx

n-вимiрного про-

стору

, називається множина

]={x ∈ R

: x = λx

+(1−λ)x

, 0 ≤ λ ≤ 1}.

Означення 1.3.2. Непорожня множина X ⊂ R

називається опуклою,

якщо разом з будь-якими двома тoчками вона мiстить i вiдрiзок, що

з’єднує цi точки. Порожню множину

∅ будемо вважати опуклою.

Прикладами опуклих множин у просторi

є одноточковi множини,

iнтервали, пiвпрямi, прямi. Прикладами опуклої множини в просторi

є сам простiр, будь-який його пiдпростiр, одноточковi множини, куля,

вiдрiзок, а також: