Вправи. 1 Лінійні програми

(b) (c) (d) zx 1 x 2 s 1 s 2 RHS 1 0 1 0 2 20 0 0 0 1 2 5 0 1 2 0 3 6 zx 1 x 2 s 1 s 2 RHS 1 2 0 0 1 8 0 3 1 0 2 4 0 2 0 1 1 0 zx 1 x 2 s 1 s 2 RHS 1 0 0 2 0 5 0 0 1 1 1 4 0 1 1 1 0 4 Вправа 11. Нехай лінійна програма max x 1, x 2, x 3 5x 1 + 3x 2 + x 3: x 1 + x 2 + x 3 6, 5x 1 + 3x 2 + 6x 3 15 x 1 0, x 2 0, x 2 0 та відповідний масив zx 1 x 2 x 3 s 1 s 2 RHS 1 0 0 5 0 1 15 0 0 2/5 1/5 1 1/5 3 0 1 3/5 6/5 0 1/5 3 (a) Яке основне рішення ця таблиця представляє? Чи є це рішення оптимальним? Обґрунтуйте свою відповідь. (b) Чи ця таблиця представляє єдиний оптимум? В іншому випадку знайдіть альтернативне оптимальне рішення. Вправа 12. Використовуючи симплексний алгоритм та x 1, x 4 як вихідну точку, розв’яжіть наступний LP: 2x 2 2x 3 + 4x 4 = 5 max x 1. x 4 5x 1 x 2 x 3 + x 4: 2x 1 + 3x 2 x 3 = 2; x 1, x 2, x 3, x 4 0 Якщо ви знайшли оптимальне рішення, вкажіть значення змінних рішення та мету. Якщо ні, поясніть, на якому етапі не вдався симплексний алгоритм, і висновок щодо типу проблеми. Вправа 13. Завод може виготовити п’ять виробів P 1, P 2, P 3, P 4 і P 5. Фабрика має дві робочі зони: майстерню А1 та зону складання А2. Час, необхідний для 4

оптимальне рішення

5. 6. 7. 8. 9. 10. 11. Вправа 26. Перевірте опуклі функції у списку нижче: f (x) 1 на R f (x) = x на R f (x) = x на R f (x) = x на R f (x) = x на R + = exp на R exp на R exp < x 2 >на R exp < x 2 >на вправі 27. Переконайтесь, що такі функції опуклі в зазначених областях: x2 y на 0> ln (exp + exp) на R 2 Дуалізм Лагранжа Вправа 28. Знайдіть аналітичний вираз функцій [1. f (z) = min x R n 1 2 xt xz T x] [2. f (z) = min x R n 1 2 xt BT Bx z T x], причому B такий, що BTB є оберненим. Вправа 29. Нехай A R n і G R n - опуклі та замкнуті. Ми називаємо x = π G (a) (евклідову) проекцію y на G, якщо x є оптимальним рішенням задачі min< a x 2: x G>. x Обчисліть проекції в таких випадках: G = G = G = G = 9

Вправа 30. Нехай min x - задача лінійної оптимізації з матрицею A m n і нехай x - оптимальне рішення. Це означає, що x є мінімізатором опуклої та диференційованої функції f (x) = c T x за опуклих та диференційованих обмежень Ax b. Таким чином, необхідні та достатні умови Каруш-Кун-Таккера виконуються при x. Що ці умови означають з точки зору A, b, c? Вправа 31. Знайдіть мінімум лінійної функції f (x) = c T x над множиною n B p =; де p, 1 0. Розв’яжіть задачу оптимізації < n a i min x x 2: x >0,> x i 1 i = 1 i i Вправа 33. 1. Розглянемо задачу найменших квадратів за обмеження норми l 1: min x < 1 2 (Ax b)t (Ax b): x 1 r >(LS C), де r> 0 - параметр. Напишіть подвійну задачу (LS C) (для простоти будемо вважати, що A T A обернене). 2. Нехай min x [1 2 (Ax b) t (Ax b) + κ x 1] (LS P) Ми запишемо (LS P) в еквівалентній формі, вводячи додаткову змінну: < min 1 (Ax x,v 2 b)t (Ax b) + κv: x 1 v 0 >(LS P) Напишіть подвійну задачу (LS P), порівняйте її з подвійною (LS C). 10