Лекція 10. Верифікація оптимізаційних розв’язків: статус, нев’язка і числовий допуск

Коротко про лекцію

Лекція вчить не довіряти одному повідомленню solver-а. Ви навчитеся перевіряти статус, допустимість, нев’язки, цільову функцію та числовий допуск, щоб відрізняти справжній розв’язок від чисельно або змістовно помилкового.

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

Постановка та базові поняття

1. Чому повідомлення про успіх ще не завершує задачу

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

Навіть за правильної моделі чисельні обчислення мають похибки з рухомою комою. Значення, яке теоретично дорівнює нулю, може зберігатися як \(10^{-12}\) або \(-10^{-10}\).

Тому фінальний результат повинен містити дві частини: повідомлення чисельного розв’язувача та незалежний математичний аудит.

1.1. Що означають статус, нев’язка і числовий допуск

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

Нев’язка вимірює, наскільки числовий результат не виконує математичну умову після підстановки. Наприклад, для рівняння \(Ax=b\) природна нев’язка пов’язана з різницею \(Ax-b\).

Комп’ютер працює з наближеними числами, тому точну рівність нулю часто замінюють перевіркою в межах числового допуску. Допуск — це заздалегідь вибрана мала величина, з якою порівнюють нев’язку. Ці три поняття відповідають на різні питання й не повинні підміняти одне одного.

2. Що означає верифікація

Верифікація — перевірка того, що отриманий вектор задовольняє математичний контракт задачі.

Для LP цей контракт включає:

1. межі змінних змінних;
2. нерівності;
3. рівності;
4. значення цілі;
5. статус чисельного розв’язувача.

Для MILP додається цілочисельність. Для двоїстої пари додається розрив двоїстості. Для нелінійної безумовної оптимізації пізніше з’явиться норма градієнта.

3. Наскрізна ресурсна задача

Повернемося до моделі бетонних плит:

\[ \max Z=50x_1+40x_2 \]

за умов:

\[ 2x_1+5x_2\le20 \]

\[ 8x_1+5x_2\le40 \]

\[ 5x_1+6x_2\le30 \]

\[ x_1,x_2\ge0 \]

Матрично:

\[ Ax\le b \]

де:

\[ A= \begin{pmatrix} 2 & 5\\ 8 & 5\\ 5 & 6 \end{pmatrix} \]

\[ b= \begin{pmatrix} 20\\ 40\\ 30 \end{pmatrix} \]

Один оптимальний неперервний план:

\[ \begin{aligned} x^* &= \begin{pmatrix} 90/23\\ 40/23 \end{pmatrix}\\ &\approx \begin{pmatrix} 3.91304348\\ 1.73913043 \end{pmatrix} \end{aligned} \]

4. Перша перевірка — межі змінних

Для поточної задачі маємо нижні межі:

\[ x_1\ge0,\qquad x_2\ge0 \]

Тому перша перевірка дуже проста:

\[ \min_i x_i\ge-\varepsilon \]

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

5. Що таке нев’язка для нерівності

Для обмежень виду:

\[ Ax\le b \]

зручно визначити знаковий нев’язка:

\[ r=Ax-b \]

Якщо \(r_i<0\), маємо запас. Якщо \(r_i=0\), обмеження активне. Якщо \(r_i>0\), обмеження порушене.

Тому величина порушення:

\[ v_i=\max(r_i,0) \]

Максимальне порушення:

\[ v_{\max}=\max_i v_i \]

План вважаємо чисельно допустимим, якщо:

\[ v_{\max}\le\varepsilon \]

6. Перевіряємо оптимальний план

Для \(x^*\):

\[ \begin{aligned} Ax^* &= \begin{pmatrix} 380/23\\ 40\\ 30 \end{pmatrix}\\ &\approx \begin{pmatrix} 16.52173913\\ 40\\ 30 \end{pmatrix} \end{aligned} \]

Нев’язка:

\[ r=Ax^*-b \]

\[ r\approx \begin{pmatrix} -3.47826087\\ 0\\ 0 \end{pmatrix} \]

Тому:

\[ v_{\max}=0 \]

План допустимий.

7. Помилковий план із кращою ціллю

Розглянемо:

\[ x_{bad}= \begin{pmatrix} 4\\ 2 \end{pmatrix} \]

Його ціль:

\[ Z_{bad}=50\cdot4+40\cdot2=280 \]

Число 280 вище за оптимальну допустиму ціль приблизно 265.22. Це вже сигнал для перевірки.

Обчислюємо ресурси:

\[ Ax_{bad}= \begin{pmatrix} 18\\ 42\\ 32 \end{pmatrix} \]

Нев’язка:

\[ r_{bad}= \begin{pmatrix} -2\\ 2\\ 2 \end{pmatrix} \]

Тому:

\[ v_{\max}=2 \]

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

Математична логіка

8. Нев’язка для рівностей

Для системи:

\[ A_{eq}x=b_{eq} \]

визначаємо:

\[ r_{eq}=A_{eq}x-b_{eq} \]

Для одного числа можна перевірити абсолютне відхилення.

Для вектора зручно використовувати норму:

\[ \|r_{eq}\|\le\varepsilon \]

Норма перетворює набір відхилень на одне невід’ємне число.

9. Що таке числовий допуск

Числовий допуск — числовий допуск, який визначає, яке мале відхилення ми приймаємо як наслідок чисельної арифметики.

Наприклад:

\[ \varepsilon=10^{-6}=0.000001 \]

Перевірка:

\[ |r|\le10^{-6} \]

означає, що абсолютне відхилення не перевищує одну мільйонну.

Числовий допуск повинен відповідати масштабу задачі та сенсу перевірки.

10. Чому точне порівняння чисел небезпечне

У з рухомою комою арифметиці два теоретично однакові результати можуть відрізнятися в останніх бітах.

Тому перевірка:

# Показуємо небезпечне точне порівняння чисел з рухомою комою; далі замінимо його перевіркою з допуском.
value == expected

може повернути False для чисел, які математично достатньо близькі.

Для чисельних результатів використовують допуск:

\[ |value-expected|\le\varepsilon \]

11. Абсолютний і відносний масштаб

Абсолютний числовий допуск добре працює, коли величини мають подібний масштаб.

Якщо одна задача працює з числами порядку \(10^{-3}\), а інша — \(10^9\), один фіксований поріг може бути невдалим.

Тому часто використовують комбінацію абсолютної та відносної точності:

\[ |a-b|\le \varepsilon_{abs}+ \varepsilon_{rel}\max(|a|,|b|) \]

Цей запис збільшує допустиме абсолютне відхилення для великих чисел.

12. Перевірка цільової функції

Чисельний розв’язувач повертає значення цілі, але його варто обчислити повторно з початкових коефіцієнтів.

Для LP:

\[ f(x)=c^Tx \]

Перевірка:

\[ r_f=|f_{reported}-c^Tx| \]

і:

\[ r_f\le\varepsilon \]

Такий контроль ловить помилки знака при переході від максимізації до мінімізація API.

13. Перевірка цілочисельність

Для цілочисельної змінної перевіряємо відстань до найближчого цілого:

\[ r_{int,i}=|x_i-\operatorname{round}(x_i)| \]

Максимальна інтегральна похибка:

\[ r_{int}=\max_i r_{int,i} \]

У чисельному вивід чисельного розв’язувача можуть з’являтися значення типу 0.9999999998. Малий числовий допуск дозволяє правильно інтерпретувати таке число.

14. Перевірка двоїстості

Для прямої та двоїстої LP перевіряємо:

\[ g=|f_{primal}-f_{dual}| \]

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

Один розрив без перевірки допустимості недостатній.

15. Статус чисельного розв’язувача

Статус пояснює, чому чисельний розв’язувач завершив роботу.

Типові стани можуть означати:

1. знайдений оптимум;
2. задача недопустима;
3. задача необмежена;
4. досягнуто ліміт;
5. виникла чисельна проблема.

Конкретні коди та назви залежать від бібліотеки. Їх потрібно читати разом із документацією чисельного розв’язувача.

16. Недопустима задача

Недопустимий означає, що всі обмеження неможливо виконати одночасно.

Простий приклад:

\[ x\le1 \]

\[ x\ge2 \]

Жодне дійсне \(x\) не задовольняє обидві умови.

У прикладній моделі недопустимий часто означає суперечливі вимоги, надто малий ресурс або помилку формалізації.

17. Необмежена задача

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

Наприклад:

\[ \max x \]

за умови:

\[ x\ge0 \]

не має скінченного максимуму.

У прикладній моделі такий статус часто вказує на пропущене обмеження.

18. Чисельне масштабування

Навіть математично коректна модель може бути чисельно незручною.

Наприклад, один коефіцієнт має порядок \(10^{-9}\), а інший — \(10^9\).

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

19. Чому статус і нев’язка відповідають на різні питання

Статус описує завершення алгоритму.

Нев’язка описує виконання конкретної математичної умови знайденими числами.

Тому успішний статус і малий нев’язка доповнюють одне одного.

Алгоритм і покроковий розбір

20. Послідовність аудиту LP

Практичний аудит зручно виконувати в стабільному порядку:

1. прочитати статус;
2. перевірити розмір вектора \(x\);
3. перевірити межі змінних;
4. обчислити нерівність нев’язки;
5. обчислити рівність нев’язки;
6. повторно обчислити ціль;
7. перевірити цілочисельність, якщо вона потрібна;
8. перевірити розрив двоїстості, якщо доступна двоїста пара;
9. інтерпретувати результат предметною мовою.

Цей порядок відокремлює математичні перевірки від довіри до одного поля результату.

21. Візуальний контракт перевірки

flowchart TD
    A[Solver result] --> B[Status]
    B --> C[Bounds]
    C --> D[Constraint residuals]
    D --> E[Objective recomputation]
    E --> F[Integrality or duality checks]
    F --> G[Interpretation]

Кожний блок відповідає окремому типу помилки.

22. Порівняння нев’язка з числовий допуск

Графік показує різницю між числовим шумом порядку \(10^{-12}\), допустимим відхиленням поблизу \(10^{-6}\) та явним порушенням порядку \(10^{-3}\) або більше.

Програмна реалізація та перевірка

23. Python-функція для нерівність нев’язка

# Імпортуємо NumPy для обчислень, розв’язання моделі та її перевірки.
import numpy as np


# Описуємо функцію нев’язки, щоб перевірка не залежала від внутрішнього результату бібліотеки.
def inequality_residual(
    constraint_matrix,
    constraint_limits,
    solution,
):
    return (
        constraint_matrix
        @ solution
        - constraint_limits
    )


# Виносимо окрему математичну операцію в допоміжну функцію, щоб її було легко перевірити.
def maximum_violation(residual):
    return float(
        np.max(
            np.maximum(residual, 0.0)
        )
    )

# Мінімальний приклад показує, як функції виявляють порушення нерівностей.
probe_matrix = np.array([
    [1.0, 1.0],
    [-1.0, 0.0],
])
probe_limits = np.array([
    3.0,
    0.0,
])
probe_solution = np.array([
    2.5,
    1.0,
])
probe_residual = inequality_residual(
    probe_matrix,
    probe_limits,
    probe_solution,
)
print("Residual:", probe_residual)
print("Max violation:", maximum_violation(probe_residual))

Перша функція повертає знаковий нев’язка. Друга залишає тільки позитивні порушення.

24. Перевірка оптимального плану

# Задаємо матрицю коефіцієнтів; порядок рядків і стовпців має збігатися з математичною моделлю.
constraint_matrix = np.array([
    [2.0, 5.0],
    [8.0, 5.0],
    [5.0, 6.0],
])

# Задаємо праві частини, запаси або спостереження у порядку, узгодженому з рядками матриці.
constraint_limits = np.array([
    20.0,
    40.0,
    30.0,
])

# Задаємо конкретну точку, план або множники, для яких далі виконаємо математичну перевірку.
solution = np.array([
    90.0 / 23.0,
    40.0 / 23.0,
])

# Обчислюємо діагностичну величину для незалежного аудиту розв’язку.
tolerance = 1e-6

# Обчислюємо нев’язку або запас безпосередньо з початкових формул для незалежної перевірки.
residual = inequality_residual(
    constraint_matrix,
    constraint_limits,
    solution,
)

# Незалежно перевіряємо допустимість: обчислюємо значення обмежень і максимальне порушення.
violation = maximum_violation(
    residual
)

# Незалежно перевіряємо допустимість: обчислюємо значення обмежень і максимальне порушення.
is_feasible = violation <= tolerance

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Residual:", residual)
print("Max violation:", violation)
print("Feasible:", is_feasible)

Очікуємо від’ємний нев’язка для цементу, нулі для двох активних ресурсів і True.

25. Перевірка помилкового плану

# Задаємо конкретну точку, план або множники, для яких далі виконаємо математичну перевірку.
bad_solution = np.array([
    4.0,
    2.0,
])

# Обчислюємо нев’язку або запас безпосередньо з початкових формул для незалежної перевірки.
bad_residual = inequality_residual(
    constraint_matrix,
    constraint_limits,
    bad_solution,
)

# Незалежно перевіряємо допустимість: обчислюємо значення обмежень і максимальне порушення.
bad_violation = maximum_violation(
    bad_residual
)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Residual:", bad_residual)
print("Max violation:", bad_violation)

Очікувано:

Residual: [-2.  2.  2.]
Max violation: 2.0

Тому план відхиляється незалежно від високого значення цілі.

26. Чому не потрібно порівнювати тільки з еталонним вектором

Оптимізаційна задача може мати кілька оптимальних розв’язків.

Автоматична перевірка виду:

\[ \|x-x_{reference}\|\le\varepsilon \]

може відхилити інший правильний оптимум.

Надійніша перевірка оцінює:

1. допустимість;
2. значення цілі;
3. потрібний оптимальність сертифікат.

Для задачі з множинним оптимумом студент може подати інший вектор, але з тим самим оптимальним значенням.

27. Машиночитаний контракт результату

Практичний звіт можна завершувати структурованими полями:

STATUS
X
OBJECTIVE
MAX_CONSTRAINT_VIOLATION
RESIDUAL
DUALITY_GAP
ITERATIONS

Не кожна задача потребує всіх полів. Набір залежить від математичного класу.

Цей формат допомагає відокремити число від доказу його коректності.

Інтерпретація, межі та підсумок

28. Як вибирати числовий допуск

Числовий допуск не повинен бути випадковим декоративним числом.

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

Для навчальних прикладів з коефіцієнтами порядку одиниць або десятків \(10^{-6}\) є зручним стартовим абсолютним допуском. Для інших масштабів потрібна окрема оцінка.

29. Чому надто великий числовий допуск небезпечний

Якщо взяти:

\[ \varepsilon=5 \]

то помилковий план з порушенням 2 формально пройде перевірку.

Тому числовий допуск повинен відокремлювати числовий шум від предметно значущого порушення.

30. Чому надто малий числовий допуск також небезпечний

Поріг порядку \(10^{-15}\) може бути надмірно строгим для типових з рухомою комою обчислень.

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

Практична перевірка повинна бути строгою математично й реалістичною чисельно.

31. Типова помилка

Типова помилка. result.success=True сприймають як повний доказ правильності. Після статус потрібно незалежно перевірити межі змінних, нев’язки і цільову функцію.

Межі змінних нев’язка як окрема перевірка

Межі змінних часто записують окремо від матриці обмежень. Тому їх потрібно перевіряти окремим нев’язка.

Для нижньої межі \(l_i\):

\[ r_i^{lower}=l_i-x_i \]

Порушення нижньої межі:

\[ v_i^{lower}=\max(r_i^{lower},0) \]

Для верхньої межі \(u_i\):

\[ r_i^{upper}=x_i-u_i \]

Порушення:

\[ v_i^{upper}=\max(r_i^{upper},0) \]

Максимальна межа-помилка:

\[ v_{bounds}=\max_i \left( v_i^{lower},v_i^{upper} \right) \]

Це корисно для MILP, де бінарні змінні мають межі змінних 0 і 1, та для задач із фізичними лімітами виробництва.

Чому знаковий нев’язка і порушення — різні величини

Для нерівності \(Ax\le b\) знаковий нев’язка зберігає інформацію про напрям:

\[ r_i=(Ax-b)_i \]

Значення \(-3.48\) означає запас приблизно 3.48. Значення \(2\) означає перевищення на 2.

Порушення відкидає допустимий запас:

\[ v_i=\max(r_i,0) \]

Тому для діагностики корисно зберігати обидва вектори. Нев’язка пояснює, що відбувається з кожним обмеженням. Порушення дає компактний критерій «пройдено / не пройдено».

Запас як альтернативний знак

Деякі API чисельного розв’язувача повертають запас:

\[ s=b-Ax \]

Для допустимого обмеження запас невід’ємний. Активна межа має:

\[ s_i=0 \]

знаковий нев’язка, який використовується в лекції, має протилежний знак:

\[ r=-s \]

Обидва записи математично еквівалентні. Важливо зафіксувати домовленість і не змішувати знаки в одному перевіряльник-і.

Числовий приклад абсолютного числовий допуск

Припустимо, рівність теоретично повинна дати 30, але програма повернула:

\[ 29.9999998 \]

Абсолютний нев’язка:

\[ |29.9999998-30|=2\cdot10^{-7} \]

За числовий допуск:

\[ \varepsilon=10^{-6} \]

маємо:

\[ 2\cdot10^{-7}<10^{-6} \]

Тому відхилення приймається як чисельно допустиме.

Якщо результат дорівнює 29.99, нев’язка дорівнює 0.01. Це вже значно перевищує заданий числовий допуск.

Відносна похибка на великому масштабі

Нехай очікуване значення дорівнює:

\[ 10^9 \]

а обчислене:

\[ 10^9+0.1 \]

Абсолютна похибка 0.1 здається великою порівняно з \(10^{-6}\). Відносно масштабу \(10^9\) вона дуже мала:

\[ \frac{0.1}{10^9}=10^{-10} \]

Тому для великих величин корисна комбінована перевірка:

\[ |a-b|\le \varepsilon_{abs}+ \varepsilon_{rel}\max(|a|,|b|) \]

Цей критерій одночасно захищає числа поблизу нуля та великі значення.

Масштабування одиниць

Модель може бути математично правильною, але використовувати незручні одиниці.

Наприклад, один ресурс вимірюється в міліграмах з числами порядку \(10^8\), а інший — у тоннах з коефіцієнтами порядку \(10^{-4}\).

Перехід до грамів або кілограмів може зменшити різницю масштабів.

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

Перевірка цілі при зміні знака

SciPy linprog мінімізує передану функцію. Для задачі максимізації ми часто передаємо:

\[ -c \]

Тоді поле result.fun відповідає:

\[ -c^Tx^* \]

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

\[ Z^*=-\text{result.fun} \]

Незалежна перевірка:

\[ Z_{check}=c^Tx^* \]

і:

\[ |Z^*-Z_{check}|\le\varepsilon \]

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

Верифікація транспортної задачі

Для транспортного плану матриця нев’язка має особливу структуру.

Рядковий нев’язка:

\[ r_i^{supply}=\sum_jx_{ij}-a_i \]

Стовпчиковий нев’язка:

\[ r_j^{demand}=\sum_ix_{ij}-b_j \]

Після цього можна обчислити один показник:

\[ r_{transport}= \max \left( \max_i|r_i^{supply}|, \max_j|r_j^{demand}| \right) \]

Цей приклад показує, що загальна ідея нев’язка адаптується до структури конкретної моделі.

Верифікація найкоротший шлях

У графовій задачі нев’язка не обов’язково є матричним вектором.

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

1. правильне джерело;
2. правильна ціль;
3. існування кожного ребра;
4. повторна сума ваг;
5. збіг з оптимальною довжиною.

Тому «математичний контракт» є ширшим поняттям, ніж одна формула \(Ax-b\).

Верифікація MILP

Для дискретної задачі потрібно об’єднати неперервні та дискретні критерії.

Спочатку перевіряємо лінійні обмеження і межі змінних.

Потім:

\[ r_{int}=\max_i |x_i-\operatorname{round}(x_i)| \]

Для бінарних змінних також перевіряємо межі змінних \(0\le x_i\le1\).

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

Як будувати повторно використовуваний перевіряльник

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

Зручний інтерфейс може приймати:

• x;
• A_ub, b_ub;
• A_eq, b_eq;
• нижня і верхня межаs;
• c;
• reported_objective;
• tolerance.

Функція повертає логічний результат True або False разом із числовими діагностиками.

Наприклад:

MAX_CONSTRAINT_VIOLATION = 0.0
MAX_EQUALITY_RESIDUAL = 2.1e-10
BOUND_VIOLATION = 0.0
OBJECTIVE_RESIDUAL = 0.0

Такий формат допомагає студенту побачити причину помилки.

Чому повідомлення «неправильно» недостатньо

Навчальний перевіряльник повинен давати локальну діагностику.

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

Наприклад:

Обмеження 2: 42 <= 40 — порушення 2

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

Еталонний результат і математичний сертифікат

Для задачі з унікальним оптимумом точне порівняння з еталонним \(x^*\) може бути додатковою перевіркою.

Основним критерієм все одно залишається математичний контракт.

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

Тому автоматична оцінка повинна відділяти «розв’язок дорівнює моєму прикладу» від «розв’язок математично правильний».

Фінальний чекліст чисельного аудиту

Перед прийняттям результату поставте конкретні запитання.

1. Який статус чисельного розв’язувача?
2. Чи має \(x\) правильну розмірність?
3. Чи виконані межі змінних?
4. Яке максимальне порушення нерівностей?
5. Яка норма рівність нев’язка?
6. Чи збігається повторно обчислена ціль?
7. Чи виконана цілочисельність?
8. Чи малий розрив двоїстості, якщо він доступний?
9. Чи має результат предметний зміст?

Цей список утворює універсальний каркас для всього подальшого курсу.

Приклад повної автоматичної діагностики

Нехай перевіряльник отримав кандидатний план \(x=(4,2)^T\). Він не повинен завершуватися одним словом False.

Спочатку обчислюються всі ліві частини:

\[ Ax= \begin{pmatrix} 18\\ 42\\ 32 \end{pmatrix} \]

Потім формується знаковий нев’язка:

\[ r= \begin{pmatrix} -2\\ 2\\ 2 \end{pmatrix} \]

Далі формується порушення:

\[ v= \begin{pmatrix} 0\\ 2\\ 2 \end{pmatrix} \]

Звіт може сказати, що перше обмеження має запас 2, а друге й третє порушені на 2. Така діагностика одразу вказує студенту, де шукати проблему.

Відтворюваність перевірки

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

Тому всі параметри перевірки потрібно фіксувати явно. Наприклад, числовий допуск не варто приховувати всередині випадкового допоміжний-а.

У звіті достатньо вказати:

TOLERANCE = 1e-6

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

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

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

Перед числовими операціями корисно перевірити розмір.

Для LP з \(m\) обмеженнями і \(n\) змінними очікуємо:

\[ A\in\mathbb{R}^{m\times n} \]

\[ x\in\mathbb{R}^{n} \]

\[ b\in\mathbb{R}^{m} \]

Якщо вектор \(b\) має іншу довжину, модель структурно некоректна.

Навіть коли NumPy дозволяє автоматичне узгодження розмірів масивів, такий автоматичний механізм не повинен приховувати помилку математичної форми.

Перевірка скінченності чисел

Перед нев’язка-аналізом потрібно переконатися, що результат не містить NaN або нескінченності.

Математичний критерій можна сформулювати так:

\[ x_i\in\mathbb{R} \]

для кожної компоненти.

У Python практична перевірка використовує np.isfinite.

Якщо хоча б одна компонента не є скінченним числом, подальше порівняння з числовий допуск втрачає сенс.

Перевірка після округлення для звіту

Іноді студент друкує розв’язок з малою кількістю десяткових знаків. Наприклад, точне чисельне значення \(3.91304348\) записується як 3.91.

Такий округлений вектор може мати більший нев’язка, ніж внутрішній розв’язок чисельного розв’язувача.

Тому для математичної перевірки потрібно використовувати достатню точність чисел. Форматований короткий запис підходить для пояснення, але перевіряльник повинен отримувати точніший результат.

Це особливо важливо для активних обмежень, де невелике округлення може створити помітне порушення.

Верифікація як частина методу, а не фінальна формальність

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

Якщо цільова функція нев’язка великий, варто перевірити знак цілі та порядок коефіцієнтів.

Якщо цілочисельність нев’язка великий, потрібно перевірити тип змінної та використаний чисельний розв’язувач.

Тому верифікація є діагностичним механізмом. Вона показує, який шар розв’язання потребує виправлення.

Мінімальний звіт студента

Для більшості лабораторних робіт достатньо короткого завершального блоку з числовими доказами.

Наприклад:

STATUS = optimal
X = [3.91304348, 1.73913043]
OBJECTIVE = 265.21739130
MAX_CONSTRAINT_VIOLATION = 0.0
TOLERANCE = 1e-6

Якщо задача має рівності, додається MAX_EQUALITY_RESIDUAL. Для MILP додається INTEGRALITY_RESIDUAL. Для двоїстої пари додається DUALITY_GAP.

Такий блок не замінює пояснення, але робить перевірку прозорою та відтворюваною.

Що робити, якщо перевірка не проходить

Порядок діагностики повинен бути конкретним.

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

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

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

Чому верифікація потрібна навіть для маленьких задач

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

Розмір задачі змінює спосіб обчислення, але не змінює логіку математичного контракту.

Фінальна інтерпретація нев’язка

Нев’язка варто перекладати предметною мовою. Значення 2 у другому ресурсному обмеженні означає перевищення запасу на 2 одиниці ресурсу. Значення \(-3.478\) у першому означає невикористаний запас приблизно 3.478 одиниці.

Такий переклад завершує аудит: число стає зрозумілим наслідком для реальної задачі.

Верифікація як універсальна навичка курсу

У наступних темах змінюватиметься критерій оптимальності, але структура аудиту залишиться знайомою. Для градієнт методи з’явиться норма градієнта, для KKT — стаціонарність і комплементарність, для найменших квадратів — норма нев’язки. Тому ця лекція формує спільну мову перевірки для всього курсу.

Перевірка структури перед арифметикою

До обчислення нев’язка потрібно переконатися, що всі масиви мають очікувані розміри. Матриця з \(m\) обмеженнями та \(n\) змінними повинна мати розмір \((m,n)\), вектор \(x\) — довжину \(n\), а \(b\) — довжину \(m\). Такий структурний контроль часто знаходить помилку раніше за числовий нев’язка.

Інтерактивна самоперевірка лекції

Пройдіть 10 коротких питань. Після кожної відповіді ви побачите пояснення, а за потреби — підказку й повний розбір.

32. Підсумок

Чисельний результат стає корисним лише після перевірки його математичного змісту. Статус пояснює, як завершився алгоритм, нев’язка вимірює виконання конкретної умови, а числовий допуск визначає, яке відхилення вважається прийнятним. Ці три поняття потрібно читати разом.

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

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