Найважливішою з усіх проблем є вибір змінних. Тепер ми призначимо наші змінні харчовим продуктам, і значенням змінної буде кількість споживаної їжі (порційно). Позначте x 1 кількість порцій вівсяної каші, x 2 курка, x 3 яйця, x 4 молоко, x 5 вишневий пиріг, x 6 кількість порцій зі свининою! Дієта повинна відповідати наступним умовам: Доза/день за обмеженням Добова потреба 0 x 1 4 0 x 2 3 0 x 3 2 0 x 4 8 0 x 5 2 0 x 6 2 110x 1 + 205x 2 + 160x 3 + 160x 4 + 420x 5 + 260x 6 2000 4x 1 + 32x 2 + 13x 3 + 8x 4 + 4x 5 + 14x 6 55 2x 1 + 12x 2 + 54x 3 + 285x 4 + 22x 5 + 80x 6 800 Тут ми врахували, що ми не повинні споживати негативну кількість або занадто багато їжі, або ми підсумували харчову цінність у них. Нарешті, вартість дієти може бути виражена введеними змінними та заданими константами: 3x 1 + 24x 2 + 13x 3 + 9x 4 + 20x 5 + 19x 6 Після цього математичний опис проблеми дієти такий: min 3x 1 + 24x 2 + 13x 3 + 9x 4 + 20x 5 + 19x 6 110x 1 + 205x 2 + 160x 3 + 160x 4 + 420x 5 + 260x 6 2000 4x 1 + 32x 2 + 13x 3 + 8x 4 + 4x 5 + 14x 6 55 2x 1 + 12x 2 + 54x 3 + 285x 4 + 22x 5 + 80x 6 800 x 1 4 x 2 3 x 3 2 x 4 8 x 5 2 x 6 2 x 1, x 2, x 3, x 4, x 5, x 6 0 3

можливе рішення

2.2. Подвійність Розгляньте наступний стандартний LP! макс. 4x 1 + x 2 + 5x 3 + 3x 4 x 1 x 2 x 3 + 3x 4 1 (1) 5x 1 + x 2 + 3x 3 + 8x 4 55 (2) x 1 + 2x 2 + 3x 3 5x 4 3 (3) x 1, x 2, x 3, x 4 0 Замість вирішення задачі дайте верхню оцінку значення z цільової функції. Помноживши нерівність (2) на 5/3, вийде верхня межа на z. 5 3 (5x 1 + x 2 + 3x 3 + 8x 4 55) 4x 1 + x 2 + 5x 3 + 3x 4 25 3 x 1 + 5 3 x 2 + 5x 3 + 40 3 x 4 275 3 z 275 3 A (2) + (3) дає праву верхню межу: 5x 1 + x 2 + 3x 3 + 8x 4 55 x 1 + 2x 2 + 3x 3 5x 4 3 4x 1 + 3x 2 + 6x 3 + 3x 4 58 4x 1 + x 2 + 5x 3 + 3x 4 4x 1 + 3x 2 + 6x 3 + 3x 4 58 z 58 Продовжуючи ідею, візьмемо невід’ємну лінійну комбінацію нерівностей, тобто помножимо першу на y 1, а другу на y 2, третій з y 3, потім складіть їх! (Очевидно, що остаточна нерівність виконується, якщо y 1, y 2, y 3 невід’ємне.) (Y 1 + 5y 2 y 3) x 1 + (y 1 + y 2 + 2y 3) x 2 + (y 1 + 3y 2 + 3y 3) x 3 + + (3y 1 + 8y 2 5y 3) x 4 y 1 + 55y 2 + 3y 3 4

Якщо виконуються наступні умови, то y 1 + 55y 2 + 3y 3 дає верхню межу значення цільової функції: Якщо вищезазначене виконується, отримуємо: y 1 + 5y 2 y 3 4 y 1 + y 2 + 2y 3 1 y 1 + 3y 2 3y 3 5 3y 1 + 8y 2 5y 3 3 4x 1 + x 2 + 5x 3 + 3x 4 y 1 + 55y 2 + 3y 3 zy 1 + 55y 2 + 3y 3: min y 1 + 55y 2 + y 3 y 1 + 5y 2 y 3 4 y 1 + y 2 + 2y 3 1 y 1 + 3y 2 3y 3 5 3y 1 + 8y 2 5y 3 3 y 1, y 2, y 3 0 The Оригінальна проблема є первинною, а отримана вище називається подвійним або подвійним завданням. LP у стандартній формі та його дуал загалом: Primary Dual max c j x j j = 1 min m b i y i a ij x j b i i = 1. m j = 1 m a ij y i c j j = 1. n x j 0 j = 1. n y i 0 i = 1. m 1. Теорема. (Слабка подвійність) Якщо (x 1. x n) - можливе рішення первинної задачі, а (y 1. y m) - можливе рішення подвійної задачі, то m c j x j b i y i j = 1 5

Доказ. Це очевидно з побудови подвійної проблеми. Формально: (m) mmcjxja ij yixj = a ij xjyibiyi, j = 1 j = 1 j = 1, оскільки сьогодні ij yicj, xj 0 (j = 1. n) і nj = 1 - це ij xjbi, yi 0 (i = 1 м). Перш ніж викласти і довести т. Зв. сильна теорема подвійності, розглянемо останній словник задачі LP. Можна помітити наступну дуже дивовижну особливість: Рішення подвійної задачі можна прочитати з останнього словника оригінальної задачі. Якщо вихідне рішення було оптимальним, нехай буде. Наприклад, якщо останнім словником основної задачі є: x 2 = 14 2x 1 4x 3 5x 5 3x 7 x 4 = 5 x 1 x 3 2x 5 x 7 x 6 = 1 + 5x 1 + 9x 3 + 21x 5 + 11x 7 z = 29 x 1 2x 3-11 x 5 + 0 x 6-6 x 7 x 5 y 1 y 1 = 11 x 6 y 2 y 2 = 0 x 7 y 3 y 3 = 6 Відповідність: подвійна змінні в якомусь сенсі можуть бути віднесені до штучних змінних оригінального LP. Значення подвійних змінних рівно в 1 рази перевищує коефіцієнти миттєвої цільової функції штучних змінних. Ця незабаром доведена властивість надзвичайно корисна як для доведення теореми подвійності, так і для вирішення практичних задач. Теорема 2. (Сильна подвійність) Якщо основна задача має оптимальне рішення (x 1. x n), то подвійна задача має оптимальне рішення (y 1. y m), для якого m c j x j = b i yi j = 1 6

Доказ. Через розглянуту раніше теорему про слабку двоїстість достатньо знайти можливе рішення (y1, y 2. y n) двоїстої задачі, для якої виконується рівняння nj = 1 c j x j = m b i yi. Вирішуючи первинну задачу, ми вводимо штучні змінні x n + i = b i a ij x j (i = 1. m) j = 1. Припустимо, ми дійшли до останнього словника: n + mz = z + ckxkk = 1 ck 0, (k = 1. n + m), z = cjxjj = 1 Як уже згадувалося, спробуйте yi = c n + i (i = 1. m ) заміщення! Ми стверджуємо, що це можливе рішення подвійного, справа лише в інших підрахунках. x n + i < >> < m z = c j x j = z + c j x j yi b i a ij x j j=1 j=1 j=1 ( ) ( ) m m c j x j = z b i yi + c j + a ij yi x j j=1 j=1 Ezt az egyenlőséget egyszerű algebrai manipulációval kaptuk az előzőből, azaz minden x 1, x 2. x n értékre igaznak kell lennie. Ebből adódnak a m z = b i yi, m c j = c j + a ij yi egyenlőségek. Mivel c k 0 minden k = 1. n + m esetén, így m a ij yi c j (j = 1. n) yi 0 (i = 1. m) 7

Отже, yi = c n + i (i = 1. m) - це можливе рішення дуалі, а m b i yi = n j = 1 c j x j, і з цим ми бачимо теорему. В математиці оператор називається дуалізацією, коли його застосовують двічі поспіль для повернення до початкової задачі. Легітимність нашого імені виправдовується тим, що дуал подвійного завдання є першочерговим завданням. Подвійна задача m max (bi) yim (a ij) yicj (j = 1. n) yi 0 (i = 1. m) Подвійна задача подвійної задачі min (cj) xjj = 1 (a ij) xjbi ( i = 1 m) j = 1 xj 0 (j = 1. n) Це, очевидно, еквівалентно первинній задачі: max cjxjj = 1 j = 1 a ij xjbi (i = 1. m) xj 0 (j = 1. н) між первинним та подвійним завданням Теорема подвійності показує, що первинне та подвійне завдання не можуть бути у жодному відношенні. Можливість різних варіацій (оптимальне, неможливе рішення, цільова функція не обмежена) узагальнено в таблиці нижче. 8

Середнє значення V - величина багатства людини, K - збиток, який може бути ймовірним p, d - страховий внесок, який відшкодовує його. Тоді незручність сплати збору: log (1 + V) + log (1 + V d) d V при одночасному (очікуваному) зменшенні корисності, спричиненому аварією () 1 + V p (log (1 + v) + log (1 + v K)) = p log 1 + VK Отже, варто оформити страховку, якщо (d V p log 1 + K 1 + VK (= p log 1 +).) K. 1 + VK Погляньмо на деякі особливі випадки: К в) продає газету за одиницю. Якщо ви купуєте x штук, тоді для ξ x, тоді як якщо ξ> x dξ cx = c (x ξ) + (d c) ξ, dx cx = (d c) (ξ x) + (d c) ξ буде корисним. Звичайно, значущої відповіді можна очікувати лише в тому випадку, якщо ми маємо певне припущення щодо розподілу попиту. Нехай цей розподіл спочатку буде дискретним, а імовірність події ξ = i позначимо через p i, тобто P r (ξ = i) = p i. Очікувані вигоди, таким чином, будуть такими:

(dc) eξ c (xi) pic) (ix) pi, ix (d, яка є максимальною, якщо сума c (xi) pi + (dc) (ix) piix є мінімальною, що можна трактувати як очікуване штраф, якщо поточне значення eltér відрізняється від x, c потрібно заплатити за ξ xf (x): = 2 (xi) λi e λ + (ix) λi e λ i! i! ix Вважати x неперервною змінною; et диференційоване ad dx f (x) 2 λi e λ λ тобто λ i! i! ix ми повинні знайти корінь рівняння для кожного дискретного розподілу ipi = 1, тому конкретно i = 0 λ тобто λ/i! = 1, тобто ix = 0 λ, тобто λ 5 Розподіл Пуассона з’являється у багатьох випадкових процесах, наприклад, в блуканнях чи телефонних дзвінках тощо, тому в цьому випадку це набагато природніше, ніж рівномірний розподіл (i!) . 18

обчислення n (n + 1)/2 елементів симетричної матриці C. (Це, звичайно, слід визначити з попередніх спостережень.) Обидві труднощі можна подолати, якщо замість мінімізації коваріації ми задовольняємося мінімізацією середнього абсолютного відхилення E [j (ξ j µ j) x j]. 8 Метод моделі MAD Конно-Ямадзакі, запропонований Конно та Ямадзакі в 1990 р., Слідує цьому і дозволяє уникнути обчислення очікуваних значень µ i та коефіцієнтів коваріації c ij; використовувати спостережувані дані безпосередньо. (Середнє абсолютне відхилення після англійської назви, середнє абсолютне відхилення, назва моделі - MAD.) Якщо раніше ми проводили спостереження T, r jt позначає рентабельність j-ї інвестиції при t-му спостереженні та rj = 1 TT r jt, jt = r jt rj, t = 1, то оптимізацію портфеля можна записати у такому вигляді: min 1 TT t = 1 nj = 1 a jt xj () rjxj ρ j = 1 xj = 1 xj 0 j = 1 . н. Проблема () не є LP, але подібно до ідеї, що використовується в матричних іграх, LP можна звести до задачі: min 1 TT ytt = 1 ytnj = 1 j = 1 a jt xtytt = 1. T rjxj ρ () xj = 1 xj 0 j = 1. n. Насправді, у найважливішому випадку для багатовимірного нормального розподілу два методи є еквівалентними. 23

За допомогою цієї моделі стає можливим вирішення досить великих реальних проблем. Однак ми не повинні забувати, що отримане рішення - це лише пропозиція: є багато інших аспектів, які слід враховувати при виборі фактичного портфеля. Напівбожевільна модель Ви можете подумати про модель MAD і трохи її змінити. Нагадаємо, що вираз n j = 1 a jt x j дає знакове відхилення від (передбачуваного) очікуваного прибутку в момент j. Очевидно, що ми не мінімізуємо суму їх абсолютних значень, а лише суму абсолютних значень тих членів, які є негативними. (Дійсно, оскільки якщо портфель працює краще, ніж очікувана прибутковість у момент j, це неприємна, а сприятлива подія.) Введення позначень x: = x, якщо x 0 та x: = 0, якщо x> 0, проблема приймає такий вигляд: max 1 TT nj = 1 a jt xjt = 1 rjxj ρ j = 1 xj = 1 xj 0 j = 1. n. Форму LP для цієї задачі легко визначити, а також простішу для моделі MAD: max 1 TT ytt = 1 a jt xtytt = 1. T j = 1 rjxj ρ j = 1 xj = 1 yt 0 t = 1 . T xj 0 j = 1. n. Примітка: Методи MAD та sem-mad приблизно еквівалентні, якщо розподіл прибутків оптимальних портфелів приблизно симетричний. 24

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

m x i = 1 () x i 0 (i = 1, 2. m) Найважливішим спостереженням є те, що, хоча ця проблема не є LP, вона еквівалентна LP. max zzma ij xi 0 (j = 1, 2. n) mxi = 1 () xi 0 (i = 1, 2. m) Дійсно, оптимальним рішенням задачі () для будь-якого z, x 1. xm є принаймні один za ij xi 0 задовольняє нерівність з рівністю, тому оптимум LP z = min дорівнює ij x j. Аналогічно, min max ia ij yj (i = 1, 2. m) j = 1 yj = 1 j = 1 yj 0 (j = 1, 2. n), що описує оптимальну стратегію гравця колони, еквівалентно min wwna ij yj 0 (i = 1, 2. m) j = 1 myj = 1 () yj 0 (j = 1, 2. n) із задачею LP. Зверніть увагу, що () та () є подвійними між собою, і обидва мають можливі рішення. Таким чином, згідно з теоремою подвійності, () має оптимальне рішення z, x 1. x m, а () має w, y1. оптимальне рішення y n таке, що z = w. Оскільки z = min y x Ay, w = max x xay, ми бачили теорему. 29