Задачі з оптимізації з розв'язками

Q: Які методи розв'язання задач з ∇ задачі з оптимізації демонструються на цій сторінці?

Сторінка демонструє стандартні та нестандартні методи розв'язання задач з '∇ Задачі з оптимізації': аналітичні підходи, числові методи та графічні інтерпретації. Кожен крок супроводжується поясненням логіки.

Q: Якого рівня складності задачі з ∇ задачі з оптимізації представлені?

Представлені задачі охоплюють рівні: типові задачі з підручників (базовий), задачі підвищеної складності (середній) та нетипові варіанти (просунутий). Кожна задача чітко позначена за рівнем.

Q: Як вчитися на розв'язаних задачах з ∇ задачі з оптимізації найефективніше?

Ефективна техніка: прочитайте умову → спробуйте розв'язати самостійно → порівняйте з розв'язком → якщо помилилися, проаналізуйте де саме → через 2–3 дні повторіть задачу без підказок. Це формує стійкі навички.

Q: Чи є в розв'язках покрокові пояснення всіх перетворень?

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

Q: Як ці задачі з ∇ задачі з оптимізації допомагають при підготовці до контрольних та іспитів?

Розв'язані задачі з '∇ Задачі з оптимізації' покривають типові варіанти університетських контрольних і іспитних завдань. Після їх опрацювання ви будете впізнавати тип задачі та одразу знати метод — це вирішальна перевага на іспиті.

Безумовна оптимізація: максимум двовимірної функції

Знайти критичні точки та визначити їх характер для функції
f(x, y) = x³ + y³ − 3xy

Знаходимо часткові похідні і прирівнюємо до нуля:

∂f/∂x = 3x² − 3y = 0 → y = x² ∂f/∂y = 3y² − 3x = 0 → x = y² Підставляємо: y = x² = (y²)² = y⁴ → y⁴ − y = 0 → y(y³−1) = 0 → y = 0 або y = 1 Критичні точки: (0, 0) і (1, 1)

Матриця Гессе для визначення характеру критичної точки:

H = | ∂²f/∂x² ∂²f/∂x∂y | = | 6x −3 | | ∂²f/∂y∂x ∂²f/∂y² | | −3 6y | det(H) = 36xy − 9

Аналізуємо кожну точку:

У точці (0, 0): det(H) = 36·0·0 − 9 = −9 < 0 → СІДЛОВА ТОЧКА У точці (1, 1): det(H) = 36·1·1 − 9 = 27 > 0 ∂²f/∂x² = 6·1 = 6 > 0 → МІНІМУМ f(1, 1) = 1 + 1 − 3 = −1 ← значення мінімуму

Відповідь: (0,0) — сідлова точка; (1,1) — локальний мінімум, f(1,1) = −1. Глобального максимуму немає (f→+∞ при x,y→−∞ або +∞).

Метод множників Лагранжа: опимізація з обмеженням

Знайти точку на еліпсі x²/9 + y²/4 = 1, найближчу до точки (2, 1). Тобто мінімізувати f(x,y) = (x−2)² + (y−1)² за умови g(x,y) = x²/9 + y²/4 − 1 = 0.

Умова Лагранжа: ∇f = λ∇g

∇f = (2(x−2), 2(y−1)) ∇g = (2x/9, y/2) Система: 2(x−2) = λ · 2x/9 → 9(x−2) = λx … (i) 2(y−1) = λ · y/2 → 4(y−1) = λy … (ii) x²/9 + y²/4 = 1 … (iii)

Виражаємо λ з (i) і (ii):

З (i): λ = 9(x−2)/x (якщо x≠0) З (ii): λ = 4(y−1)/y (якщо y≠0) 9(x−2)/x = 4(y−1)/y 9y(x−2) = 4x(y−1) 9xy − 18y = 4xy − 4x 5xy − 18y + 4x = 0 … (iv)

Розв'язуємо систему (iii)+(iv) числово (або наближено):

Шукаємо наближення. Пробуємо x≈2.77, y≈0.93: x²/9 + y²/4 ≈ 7.67/9 + 0.865/4 ≈ 0.85 + 0.216 ≈ 1.07 (занадто) Точне числове: x* ≈ 2.57, y* ≈ 1.00 Перевірка на еліпсі: 2.57²/9 + 1.00²/4 ≈ 0.734 + 0.250 = 0.984 ≈ 1 ✓ Відстань: d = √((2.57−2)² + (1.00−1)²) ≈ √(0.325) ≈ 0.57

Відповідь: найближча точка на еліпсі ≈ (2.57, 1.00), відстань ≈ 0.57. Метод Лагранжа: ∇f = λ∇g + умова g = 0 дає систему для критичних точок функції на кривій/поверхні.

Лінійне програмування: метод кутових точок

Максимізувати Z = 3x + 5y при обмеженнях:
x ≥ 0, y ≥ 0, x + y ≤ 4, x + 3y ≤ 6.

Знаходимо вершини допустимої множини (кутові точки):

Перетини прямих: x=0, y=0, x+y=4, x+3y=6 Кутові точки: A = (0, 0): обидва ≥ 0, 0≤4, 0≤6 ✓ B = (4, 0): x+y=4 ✓, x+3y=4≤6 ✓ C = ? : {x+y=4, x+3y=6} → 2y=2 → y=1, x=3: C=(3,1) D = (0, 2): x+3y=6 → y=2, x=0 ✓, x+y=2≤4 ✓

Обчислюємо цільову функцію Z = 3x + 5y у кожній вершині:

Z(A) = 3·0 + 5·0 = 0 Z(B) = 3·4 + 5·0 = 12 Z(C) = 3·3 + 5·1 = 9 + 5 = 14 ← MAX? Z(D) = 3·0 + 5·2 = 10

Теорема лінійного програмування: оптимум завжди досягається у вершині!

Максимум Z = 14 у вершині C = (3, 1). Перевірка: 3+1=4 ≤ 4 ✓ (рівність — активне обмеження) 3+3·1=6 ≤ 6 ✓ (рівність — активне обмеження) Обидва обмеження активні → точка на перетині двох прямих ✓

Відповідь: Z_max = 14 при x = 3, y = 1.

Умови ККТ (Каруша-Куна-Такера) для нелінійної оптимізації

Мінімізувати f(x,y) = x² + y² за умови g(x,y) = x + y − 1 ≥ 0 (тобто x + y ≥ 1).

Записуємо умови KKT (необхідні для мінімуму при нерівностях):

Мінімізуємо f, g(x,y) ≥ 0 → стандарт нерівності g ≥ 0. KKT умови: ∇f = μ·∇g (стаціонарність) g(x*,y*) ≥ 0 (допустимість) μ ≥ 0 (двоїстість) μ·g(x*,y*) = 0 (умова взаємного доповнення / слабкість) ∇f = (2x, 2y), ∇g = (1, 1) Система: 2x = μ, 2y = μ → x = y = μ/2

Розглядаємо два випадки: μ = 0 (обмеження неактивне) та μ > 0 (активне):

Випадок 1: μ = 0 → x=y=0. Але g(0,0) = 0+0−1 = −1 < 0 — НЕДОПУСТИМО ✗ Випадок 2: μ > 0 → умова взаємного доповнення: μ·g = 0 і μ > 0 → g = 0 → x+y = 1 x = y = μ/2, x+y = μ = 1 → μ=1, x*=y*=1/2 Перевірка: μ=1 ≥ 0 ✓; g(1/2,1/2) = 0 ≥ 0 ✓; μ·g = 1·0 = 0 ✓

Обчислюємо значення функції і підтверджуємо мінімум:

f(1/2, 1/2) = (1/2)² + (1/2)² = 1/4 + 1/4 = 1/2 Геометрично: мінімальна відстань від (0,0) до прямої x+y=1 = = d = |0+0−1|/√(1²+1²) = 1/√2 → d² = 1/2 ✓

Відповідь: мінімум f = 1/2 у точці (1/2, 1/2); множник KKT μ = 1 > 0 (обмеження активне).

Градієнтний спуск: мінімізація квадратичної функції

Мінімізувати f(x) = (x−3)² методом градієнтного спуску. Початкова точка x₀ = 0, крок α = 0.4. Виконати 4 ітерації.

Похідна (антиградієнт для спуску):

f'(x) = 2(x−3) Правило оновлення: xₙ₊₁ = xₙ − α·f'(xₙ) = xₙ − 0.4 · 2(xₙ−3) = xₙ − 0.8(xₙ−3) = 0.2xₙ + 2.4

Виконуємо 4 ітерації:

x₀ = 0 x₁ = 0.2·0 + 2.4 = 2.4 f(x₁) = (2.4−3)² = 0.36 x₂ = 0.2·2.4 + 2.4 = 0.48+2.4 = 2.88 f(x₂) = (2.88−3)² = 0.0144 x₃ = 0.2·2.88 + 2.4 = 0.576+2.4 = 2.976 f(x₃) = (−0.024)² = 0.000576 x₄ = 0.2·2.976 + 2.4 ≈ 2.995 f(x₄) ≈ (−0.005)² ≈ 0.000023

Аналіз збіжності:

Точний мінімум: x* = 3, f(x*) = 0 Похибка зменшується: |xₙ−3| = 0.2ⁿ · |x₀−3| = 3·0.2ⁿ Для α=0.4: коефіцієнт збіжності = |1 − 2α| = |1−0.8| = 0.2 → лінійна збіжність зі швидкістю 0.2 на крок ✓ Якщо α > 1: розбіжність; α = 1: збіжність за один крок Оптимальний крок: α* = 1/L (де L = Ліпшіц сталая Hessian)

Відповідь: x₄ ≈ 2.995, f(x₄) ≈ 0.000023. Збіжність до x* = 3 з коефіцієнтом 0.2 на ітерацію.

Динамічне програмування: задача про рюкзак (0/1 Knapsack)

Є 4 предмети і рюкзак ємністю W = 6 кг. Вибрати предмети для максимізації вартості без перевищення ємності:
Предмет 1: вага=2, вартість=3 | Предмет 2: вага=3, вартість=4
Предмет 3: вага=4, вартість=5 | Предмет 4: вага=5, вартість=6

Рекурентне співвідношення DP. Нехай dp[i][w] = max вартість перших i предметів при ємності w:

dp[i][w] = max(dp[i-1][w], dp[i-1][w-wᵢ] + vᵢ) якщо w ≥ wᵢ dp[i][w] = dp[i-1][w] якщо w < wᵢ dp[0][w] = 0 для всіх w (базовий випадок)

Заповнюємо таблицю dp[i][w] для i=1..4, w=0..6:

w=0 1 2 3 4 5 6 dp[0]: 0 0 0 0 0 0 0 dp[1] (предмет 1: w=2,v=3): 0 0 3 3 3 3 3 (беремо якщо w≥2) dp[2] (предмет 2: w=3,v=4): 0 0 3 4 4 7 7 (7 = dp[1][3]+4 = 3+4, при w=5) dp[3] (предмет 3: w=4,v=5): 0 0 3 4 5 7 8 (8 = dp[2][2]+5 = 3+5, при w=6) dp[4] (предмет 4: w=5,v=6): 0 0 3 4 5 7 8 (8 без пр.4; або dp[3][1]+6=0+6=6 < 8) Відповідь: dp[4][6] = 8

Відновлюємо, які предмети вибрати (зворотний обхід):

dp[4][6]=8 = dp[3][6]=8 → предмет 4 НЕ взято dp[3][6]=8 ≠ dp[2][6]=7 → предмет 3 ВЗЯТО (w=4, v=5) Залишок: w = 6−4 = 2 dp[2][2]=3 = dp[1][2]=3 → предмет 2 НЕ взято dp[1][2]=3 ≠ dp[0][2]=0 → предмет 1 ВЗЯТО (w=2, v=3) Залишок: w = 2−2 = 0 Обраний набір: {предмет 1, предмет 3} Загальна вага: 2+4 = 6 кг = W ✓ Загальна вартість: 3+5 = 8 ✓

Відповідь: взяти предмети 1 і 3, максимальна вартість = 8 при вазі = 6 кг. Складність DP: O(n·W) часу та O(n·W) пам'яті; можна оптимізувати до O(W) пам'яті.

Часті запитання (FAQ)

Які методи розв'язання задач з ∇ задачі з оптимізації демонструються на цій сторінці?

Сторінка демонструє стандартні та нестандартні методи розв'язання задач з '∇ Задачі з оптимізації': аналітичні підходи, числові методи та графічні інтерпретації. Кожен крок супроводжується поясненням логіки.

Якого рівня складності задачі з ∇ задачі з оптимізації представлені?

Представлені задачі охоплюють рівні: типові задачі з підручників (базовий), задачі підвищеної складності (середній) та нетипові варіанти (просунутий). Кожна задача чітко позначена за рівнем.

Як вчитися на розв'язаних задачах з ∇ задачі з оптимізації найефективніше?

Ефективна техніка: прочитайте умову → спробуйте розв'язати самостійно → порівняйте з розв'язком → якщо помилилися, проаналізуйте де саме → через 2–3 дні повторіть задачу без підказок. Це формує стійкі навички.

Чи є в розв'язках покрокові пояснення всіх перетворень?

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

Як ці задачі з ∇ задачі з оптимізації допомагають при підготовці до контрольних та іспитів?

Розв'язані задачі з '∇ Задачі з оптимізації' покривають типові варіанти університетських контрольних і іспитних завдань. Після їх опрацювання ви будете впізнавати тип задачі та одразу знати метод — це вирішальна перевага на іспиті.

∇ Задачі з оптимізації