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

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

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

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

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

1. Чому неперервного LP інколи недостатньо

У неперервному LP змінна може мати дробове значення. Для літрів або тонн це природно. Для кількості автомобілів, працівників або вибору проєкту дробове значення не має предметного змісту.

Наприклад, значення \(x=3.7\) може описувати 3.7 тонни матеріалу. Воно не може означати 3.7 автомобіля в звичайному плані закупівлі.

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

1.1. MILP, лінійна релаксація та метод гілок і меж

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

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

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

У браузерному курсі чисельний маршрут один: scipy.optimize.milp. Функція підтримує цілочисельність, межі змінних і лінійні обмеження.

2. Цілочисельна змінна

Цілочисельна змінна належить множині цілих чисел:

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

Для невід’ємної кількості використовують:

\[ x_i\in\mathbb{Z}_{\ge0} \]

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

3. Бінарна змінна

Бінарна змінна має тільки два значення:

\[ x_i\in\{0,1\} \]

Зміст часто читається так:

\[ x_i=1 \]

означає «варіант обрано», а:

\[ x_i=0 \]

означає «варіант не обрано».

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

4. Наскрізна задача вибору проєктів

Компанія розглядає три проєкти.

Проєкт	Витрати	Користь
1	5	8
2	4	6
3	3	5

Доступний бюджет:

\[ B=7 \]

Потрібно вибрати набір проєктів із максимальною сумарною користю.

5. Вводимо бінарні змінні

\[ x_1= \begin{cases} 1, & \text{проєкт 1 обрано},\\ 0, & \text{проєкт 1 не обрано} \end{cases} \]

Аналогічно вводимо \(x_2\) та \(x_3\).

Усі змінні мають домен:

\[ x_i\in\{0,1\} \]

6. Цільова функція

Сумарна користь:

\[ Z=8x_1+6x_2+5x_3 \]

Потрібно максимізувати:

\[ Z\rightarrow\max \]

7. Бюджетне обмеження

Сумарні витрати:

\[ 5x_1+4x_2+3x_3 \]

Вони не повинні перевищувати бюджет:

\[ 5x_1+4x_2+3x_3\le7 \]

Повна модель:

\[ \max 8x_1+6x_2+5x_3 \]

за умов:

\[ 5x_1+4x_2+3x_3\le7 \]

\[ x_1,x_2,x_3\in\{0,1\} \]

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

8. Повний перебір маленького прикладу

Три бінарні змінні дають:

\[ 2^3=8 \]

можливих комбінацій.

\(x_1\)	\(x_2\)	\(x_3\)	Витрати	Користь	Допустимість
0	0	0	0	0	так
1	0	0	5	8	так
0	1	0	4	6	так
0	0	1	3	5	так
1	1	0	9	14	ні
1	0	1	8	13	ні
0	1	1	7	11	так
1	1	1	12	19	ні

Найкращий допустимий варіант:

\[ x^*= \begin{pmatrix} 0\\ 1\\ 1 \end{pmatrix} \]

Його користь:

\[ Z^*=11 \]

9. LP-релаксація

Якщо прибрати цілочисельність і дозволити:

\[ 0\le x_i\le1 \]

отримаємо LP-релаксацію.

Для нашої задачі один оптимум релаксації:

\[ x^{LP}= \begin{pmatrix} 0.8\\ 0\\ 1 \end{pmatrix} \]

Перевірка бюджету:

\[ 5\cdot0.8+3\cdot1=7 \]

Користь:

\[ 8\cdot0.8+5=11.4 \]

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

10. Чому округлення релаксації не є методом

Округлимо \(0.8\) до 1:

\[ (1,0,1) \]

Витрати:

\[ 5+3=8 \]

Але бюджет дорівнює 7:

\[ 8>7 \]

Отже, округлення створило недопустимий план.

Округлення вниз дає \((0,0,1)\) з користю 5, хоча допустимий план \((0,1,1)\) має користь 11.

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

11. Загальна MILP-модель

Змішане цілочисельне лінійне програмування (MILP, змішане цілочисельне лінійне програмування) має лінійну ціль і лінійні обмеження, але частина змінних повинна бути цілою.

Загальна форма:

\[ \min c^Tx \]

за умов:

\[ b_l\le Ax\le b_u \]

\[ l\le x\le u \]

Для частини індексів:

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

12. Ідея метод гілок і меж

Метод гілок і меж використовує LP-релаксацію як джерело межі.

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

Якщо змінна дробова, наприклад:

\[ x_1=0.8 \]

простір розділяють на гілки. Для бінарної змінної це природно:

\[ x_1=0 \]

і:

\[ x_1=1 \]

Кожна гілка породжує нову підзадачу.

13. Для чого потрібна межа

LP-релаксація задачі максимізації дає верхню межу для цілочисельної цілі.

У нашому прикладі:

\[ Z_{LP}=11.4 \]

Будь-який бінарний план має:

\[ Z_{IP}\le11.4 \]

Знайдений допустимий бінарний план з \(Z=11\) дає нижню межу.

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

14. Що таке MIP розрив

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

Конкретна формула може залежати від чисельного розв’язувача, тому в навчальному аудиті важливо читати документацію інструмента.

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

15. Логічні зв’язки через бінарні змінні

Бінарна змінна може активувати інше рішення.

Наприклад, якщо проєкт 3 дозволено тільки разом із проєктом 2:

\[ x_3\le x_2 \]

Якщо \(x_3=1\), нерівність змушує \(x_2=1\).

Якщо можна вибрати не більше одного з двох проєктів:

\[ x_1+x_2\le1 \]

Такі конструкції перетворюють словесну логіку на лінійні обмеження.

16. Задача призначення

Бінарна змінна \(x_{ij}\) може означати призначення працівника \(i\) на завдання \(j\).

Для кожного працівника:

\[ \sum_j x_{ij}=1 \]

Для кожного завдання:

\[ \sum_i x_{ij}=1 \]

Ціль може мінімізувати сумарний час або вартість.

Це одна з найпоширеніших структур дискретної оптимізації.

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

17. Робочий маршрут дискретної моделі

Для прикладної задачі дійте так:

1. визначте, які рішення справді дискретні;
2. оберіть домен кожної змінної;
3. запишіть лінійну ціль;
4. формалізуйте ресурсні й логічні обмеження;
5. перевірте маленький ручний приклад;
6. розв’яжіть модель чисельним розв’язувачем;
7. перевірте цілочисельність та всі обмеження;
8. інтерпретуйте статус і розрив.

18. Візуальне порівняння релаксації та бінарного рішення

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

Бінарний оптимум вибирає проєкти 2 і 3 та точно використовує бюджет 7.

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

19. MILP через SciPy

SciPy milp мінімізує передану ціль. Тому для максимізації користі використовуємо від’ємні коефіцієнти.

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


# Задаємо коефіцієнти цільової функції в тому самому порядку, що й компоненти вектора змінних.
benefit = np.array([
    8.0,
    6.0,
    5.0,
])

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
cost = np.array([
    5.0,
    4.0,
    3.0,
])

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
budget = 7.0

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
constraints = LinearConstraint(
    cost,
    -np.inf,
    budget,
)

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
bounds = Bounds(
    lb=np.zeros(3),
    ub=np.ones(3),
)

# Обчислюємо дискретний план або перевіряємо цілочисельний кандидат.
integrality = np.ones(3)

# Запускаємо MILP-розв’язувач і явно передаємо ціль, цілочисельність, межі та лінійні обмеження.
result = milp(
    c=-benefit,
    integrality=integrality,
    bounds=bounds,
    constraints=constraints,
)

# Перевіряємо статус розв’язувача до читання числового плану; невдалий запуск не є розв’язком.
if not result.success:
    raise RuntimeError(result.message)

# Зчитуємо числовий результат розв’язувача, але ще не вважаємо його перевіреним розв’язком.
selection = np.rint(result.x).astype(int)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Вибір:", selection)
print("Користь:", benefit @ selection)
print("Витрати:", cost @ selection)

Очікувано:

Вибір: [0 1 1]
Користь: 11.0
Витрати: 7.0

integrality=1 означає, що відповідна змінна повинна бути цілою.

20. Бінарна логіка через SciPy milp

Логічні правила для бінарних змінних можна записати лінійними нерівностями. Наприклад, умова «A потребує B» має форму \(x_A\le x_B\).

import numpy as np
from scipy.optimize import Bounds, LinearConstraint, milp

benefit = np.array([8.0, 6.0, 5.0])
cost = np.array([5.0, 4.0, 3.0])

# Рядки описують бюджет, імплікацію A -> B та несумісність B і C.
constraint_matrix = np.array([
    [5.0, 4.0, 3.0],
    [1.0, -1.0, 0.0],
    [0.0, 1.0, 1.0],
])
lower = np.array([-np.inf, -np.inf, -np.inf])
upper = np.array([9.0, 0.0, 1.0])

result = milp(
    c=-benefit,
    integrality=np.ones(3),
    bounds=Bounds(0.0, 1.0),
    constraints=LinearConstraint(constraint_matrix, lower, upper),
)

if not result.success:
    raise RuntimeError(result.message)

selection = np.rint(result.x).astype(int)
print("Вибір:", selection)
print("Користь:", float(benefit @ selection))
print("Витрати:", float(cost @ selection))

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

21. Незалежна перевірка результату

Для \(x=(0,1,1)^T\):

\[ 5\cdot0+4\cdot1+3\cdot1=7\le7 \]

Цілочисельність:

\[ x_i\in\{0,1\} \]

Ціль:

\[ 8\cdot0+6\cdot1+5\cdot1=11 \]

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

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

22. Коли обирати MILP

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

Приклади: вибір інвестицій, виробничі партії, відкриття об’єктів, логістичні рішення.

23. Коли бінарна модель достатня

Бінарні змінні виражають вибір, взаємне виключення та залежності між рішеннями. Лінійні правила перетворюються на рядки LinearConstraint, тому весь приклад залишається в одному SciPy API.

Складні задачі розкладу можуть потребувати спеціалізованих чисельних розв’язувачів. Вони виходять за межі цієї лекції та лабораторних робіт курсу.

24. Статус має точний зміст

scipy.optimize.milp повертає OptimizeResult. Поле success показує, чи завершився виклик успішно за критеріями чисельного розв’язувача.

Поле status уточнює причину завершення. Для навчальної задачі очікуємо оптимальне рішення, а потім незалежно перевіряємо домен, обмеження та ціль.

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

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

25.1. Чому дискретна допустима множина має іншу геометрію

У неперервному LP допустима множина містить усі точки всередині многокутника або багатовимірного многогранника.

Після введення цілочисельність частина цих точок зникає. Для бінарних змінних залишаються тільки вершини гіперкуба з координатами 0 або 1.

У задачі трьох проєктів неперервна релаксація дозволяє точку:

\[ (0.8,0,1) \]

Бінарна модель її відкидає. Тому оптимум дискретної задачі може лежати далеко від оптимуму релаксації.

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

25.2. Розрив цілочисельності

Різниця між найкращим значенням LP-релаксації та найкращим цілочисельним значенням називається розрив цілочисельності у широкому навчальному сенсі.

Для нашої максимізації:

\[ Z_{LP}=11.4 \]

\[ Z_{IP}=11 \]

Абсолютна різниця:

\[ 11.4-11=0.4 \]

Релаксація дає верхню межу, але ця межа не обов’язково досяжна дискретним планом.

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

25.3. Метод гілок і меж на нашому прикладі

Розглянемо дробову змінну \(x_1=0.8\) у LP-релаксації. Розгалуження для бінарної змінної створює два випадки.

Перша гілка:

\[ x_1=0 \]

Тоді залишаються проєкти 2 і 3. Обидва разом коштують:

\[ 4+3=7 \]

і дають користь:

\[ 6+5=11 \]

Отже, гілка дає допустимий цілочисельний план із ціллю 11.

Друга гілка:

\[ x_1=1 \]

Після вибору першого проєкту залишається бюджет:

\[ 7-5=2 \]

Проєкти 2 і 3 коштують 4 та 3, тому жоден з них уже не поміщається. Найкращий план гілки має користь 8.

Порівняння гілок одразу доводить, що \((0,1,1)\) є кращим.

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

25.4. Найкращий знайдений цілочисельний розв’язок і межа

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

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

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

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

25.5. Логічне правило «якщо, то»

Бінарні змінні дозволяють формалізувати залежності.

Правило «якщо проєкт 3 обрано, то проєкт 2 теж обрано» записується:

\[ x_3\le x_2 \]

Перевіримо всі два можливі значення \(x_3\).

Якщо \(x_3=0\), нерівність не змушує \(x_2\) до конкретного значення.

Якщо \(x_3=1\), маємо:

\[ 1\le x_2 \]

а бінарний домен залишає тільки \(x_2=1\).

Ця коротка нерівність точно кодує словесну залежність.

25.6. Правило взаємного виключення

Якщо проєкти 1 і 2 конфліктують, можна записати:

\[ x_1+x_2\le1 \]

Допустимими залишаються комбінації \((0,0)\), \((1,0)\) та \((0,1)\).

Комбінація \((1,1)\) порушує нерівність.

Для вибору рівно одного варіанта використовують:

\[ x_1+x_2=1 \]

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

25.7. Умова активації через велику константу

Іноді бінарна змінна керує неперервною величиною.

Нехай \(q\) — обсяг виробництва, а \(y\) показує, чи відкрито виробничу лінію.

Зв’язок:

\[ 0\le q\le My \]

Якщо \(y=0\), отримуємо \(q=0\).

Якщо \(y=1\), обсяг може змінюватися до \(M\).

Константа \(M\) повинна мати реалістичну верхню межу. Надмірно велике \(M\) погіршує чисельні межі та може ускладнювати розв’язування.

25.8. Числова цілочисельність і допуск

MILP-розв’язувач повертає числа з плаваючою комою. Тому значення бінарної змінної може мати вигляд \(0.9999999998\).

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

25.9. MILP і повний перебір: модель та еталон

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

scipy.optimize.milp потрібний для загальної постановки. Кількість комбінацій швидко зростає, тому повний перебір перестає бути практичним.

25.10. Перевірка бінарності через нев’язка

Після чисельного розв’язувача можна обчислити:

\[ r_i^{bin}=\min(|x_i|,|x_i-1|) \]

Для правильного бінарного значення нев’язка дорівнює нулю.

У загальній цілочисельній моделі зручніше:

\[ r_i^{int}=|x_i-\operatorname{round}(x_i)| \]

Максимальна похибка:

\[ r_{int}=\max_i r_i^{int} \]

Чисельно приймаємо цілочисельність, якщо:

\[ r_{int}\le\varepsilon \]

25.11. Верифікація проєктного рішення

Для вектора:

\[ x=(0,1,1)^T \]

перевіряємо межі змінних:

\[ 0\le x_i\le1 \]

цілочисельність:

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

бюджет:

\[ 5x_1+4x_2+3x_3=7\le7 \]

і ціль:

\[ 8x_1+6x_2+5x_3=11 \]

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

25.12. Чому «допустимий» та «оптимальний» статус потрібно розрізняти

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

У такій ситуації він може мати хороший допустимий план і невідому кращу альтернативу.

Тому поле статус є частиною змісту результату.

У SciPy поле status відрізняє оптимальне завершення від ліміту часу або ітерацій, недопустимості та необмеженості. Тому числовий статус потрібно читати разом із повідомленням чисельного розв’язувача.

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

25.13. Практичний контракт дискретного результату

Для MILP корисно зберігати:

STATUS
X
OBJECTIVE
MAX_CONSTRAINT_VIOLATION
INTEGRALITY_RESIDUAL
BEST_BOUND
GAP

Конкретні поля BEST_BOUND і GAP залежать від API чисельного розв’язувача.

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

25.14. Межі маленького повного перебору

Повний перебір зручний для трьох бінарних змінних, бо маємо тільки 8 комбінацій.

Для 30 бінарних змінних кількість варіантів дорівнює:

\[ 2^{30}=1\,073\,741\,824 \]

Це вже понад мільярд комбінацій.

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

25.15. Перевірка всіх восьми комбінацій як навчальний еталон

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

Можна записати множину:

\[ \mathcal{X}=\{0,1\}^3 \]

Для кожного \(x\in\mathcal{X}\) обчислюємо бюджетну ліву частину:

\[ B(x)=5x_1+4x_2+3x_3 \]

і користь:

\[ Z(x)=8x_1+6x_2+5x_3 \]

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

\[ B(x)\le7 \]

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

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

25.16. Чому бінарна змінна є математично сильнішою за текстову позначку

У звичайній таблиці можна написати «так/ні». Чисельний розв’язувач не розуміє цей текст як обмеження.

Бінарна змінна переводить рішення в арифметику. Тоді користь обраного проєкту автоматично дорівнює \(p_ix_i\), а витрата бюджету — \(c_ix_i\).

Якщо \(x_i=0\), обидва внески зникають. Якщо \(x_i=1\), вони включаються повністю.

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

25.17. Приклад вимоги «обрати щонайменше один»

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

Тоді додаємо:

\[ x_1+x_2+x_3\ge1 \]

Якщо дозволено рівно два:

\[ x_1+x_2+x_3=2 \]

Якщо дозволено не більше двох:

\[ x_1+x_2+x_3\le2 \]

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

25.18. Приклад альтернативи «або один, або інший»

Для взаємовиключних проєктів 1 і 2 можна вимагати рівно один вибір:

\[ x_1+x_2=1 \]

Якщо обидва можна пропустити, але разом їх брати заборонено:

\[ x_1+x_2\le1 \]

Ця різниця часто виникає у призначеннях, виборі технології або резервному плануванні.

25.19. Перевірка логічних обмеження після чисельного розв’язувача

Логічні обмеження потрібно перевіряти так само, як ресурсні.

Для правила:

\[ x_3\le x_2 \]

знаковий нев’язка можна визначити:

\[ r=x_3-x_2 \]

Порушення:

\[ v=\max(r,0) \]

Для взаємного виключення:

\[ x_1+x_2\le1 \]

перевіряємо:

\[ v=\max(x_1+x_2-1,0) \]

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

25.20. Що означає релаксація межа у максимізації

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

Тому максимум релаксації не може бути меншим за максимум бінарної задачі:

\[ Z_{LP}\ge Z_{IP} \]

У нашому прикладі:

\[ 11.4\ge11 \]

Ця нерівність пояснює роль LP-релаксація як верхньої межі в метод гілок і меж для максимізації.

Для мінімізації напрям змінюється: релаксація дає нижню межу.

25.21. Чому чисельний розв’язувач може працювати довше на дискретній задачі

Неперервна LP має опуклу геометрію, і сучасні алгоритми ефективно використовують цю структуру.

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

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

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

25.22. Практичне рішення при часовому ліміті

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

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

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

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

25.23. Модельна дисципліна перед milp

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

Наприклад:

\[ x_i\in\{0,1\} \]

\[ 5x_1+4x_2+3x_3\le7 \]

\[ \max 8x_1+6x_2+5x_3 \]

Після цього кожний рядок Bounds, LinearConstraint та вектора integrality має пряму математичну відповідність. Такий порядок спрощує перевірку моделі.

25.24. Перевірка домену до чисельного розв’язувача

Домен змінної варто записати до побудови коду. Для бінарного рішення це \(\{0,1\}\). Для кількості машин це можуть бути цілі значення від 0 до 20.

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

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

Якщо всі змінні неперервні, лінійну задачу зручно передати linprog. Якщо хоча б частина змінних повинна бути цілою, курс використовує milp.

В обох маршрутах результат завершується однаково: статус, допустимість і повторне обчислення цілі. Для MILP додатково перевіряємо цілочисельність.

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

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

25.27. Малий приклад як тест API чисельного розв’язувача

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

25.28. Перевірка цілі після SciPy milp

SciPy мінімізує переданий вектор коефіцієнтів. У задачі максимізації ми передаємо \(-c\), тому result.fun має протилежний знак до предметної користі. Після чисельного розв’язувача потрібно повторно обчислити \(c^Tx\) з початковими додатними коефіцієнтами.

Ця перевірка одночасно контролює знак цілі та порядок компонентів вектора рішення.

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

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

26. Підсумок

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

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

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

---

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

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

Лекція вчить не довіряти одному повідомленню 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. Підсумок

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

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

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