Лекція 01. Оптимізаційне моделювання: від прикладної задачі до математичної моделі

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

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

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

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

1. З чого починається задача оптимізації

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

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

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

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

1.1. Звідки беруться слова «оптимізація», «ціль» і «обмеження»

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

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

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

2. Що називають моделлю

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

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

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

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

3. Що означає моделювання

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

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

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

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

4. Які моделі зустрічаються в прикладних задачах

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

1. Фізична модель відтворює об’єкт матеріально в іншому масштабі.
2. Абстрактна модель описує суттєві властивості через символи та правила.
3. Функціональна модель зосереджується на поведінці системи та зв’язку входів із виходами.
4. Комп’ютерна модель має програмну реалізацію для обчислювального дослідження.

Математична модель належить до абстрактних моделей. Її можна реалізувати програмно та перетворити на комп’ютерну модель.

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

5. Що означає адекватність моделі

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

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

Інша помилка виникає через одиниці вимірювання. Один коефіцієнт записано в кілограмах, а запас — у тоннах. Формула виконується, проте її числовий зміст спотворений.

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

6. Наскрізний приклад: виробництво бетонних плит

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

Вихідні дані подамо таблицею.

Ресурс	Плита 1	Плита 2	Запас
цемент	2	5	20
гравій	8	5	40
пісок	5	6	30
прибуток	50	40	—

Перший рядок читається словами. Одна плита першого виду використовує 2 одиниці цементу. Одна плита другого виду використовує 5 одиниць. На складі є 20 одиниць цементу.

Так само читаються рядки гравію та піску. Останній рядок описує прибуток від одиниці продукції.

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

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

7. Дані та змінні рішення

У задачі є числа двох різних типів. Частина чисел відома до розв’язування. Інші значення потрібно вибрати.

Запас цементу 20 — відоме число. Витрата 2 одиниці цементу на першу плиту також відома. Такі числа називатимемо даними або параметрами моделі.

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

\[ x_1=\text{кількість плит першого виду} \]

\[ x_2=\text{кількість плит другого виду} \]

Індекс 1 пов’язує змінну з першим видом продукції. Індекс 2 пов’язує змінну з другим видом.

Конкретні значення змінних утворюють план. Наприклад, \(x_1=2\) і \(x_2=3\) означають випуск двох плит першого виду та трьох другого.

8. Як із предметного правила виникає обмеження

Почнемо з цементу. Одна плита першого виду потребує 2 одиниці цементу. Для \(x_1\) плит потрібно:

\[ 2x_1 \]

Одна плита другого виду потребує 5 одиниць. Для \(x_2\) плит потрібно:

\[ 5x_2 \]

Загальна витрата цементу дорівнює сумі двох внесків.

\[ 2x_1+5x_2 \]

Запас цементу становить 20. Фактична витрата повинна вкладатися в запас.

\[ 2x_1+5x_2\le20 \]

Ліва частина — потреба вибраного плану. Права частина — доступна межа.

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

9. Обмеження гравію та піску

Для гравію маємо витрати 8 і 5 одиниць на одну плиту.

\[ 8x_1+5x_2\le40 \]

Для піску витрати становлять 5 і 6 одиниць.

\[ 5x_1+6x_2\le30 \]

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

Знак \(\le\) читається як «менше або дорівнює». Він відображає верхню межу доступного ресурсу.

10. Звідки беруться умови невід’ємності

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

Тому:

\[ x_1\ge0 \]

\[ x_2\ge0 \]

Такі умови називають умовами невід’ємності.

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

Тип змінної належить до математичної моделі. Його визначають з умови задачі.

11. Для чого потрібна цільова функція

Обмеження відповідають на запитання «які плани дозволені?». Допустимих планів може бути багато.

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

Одна плита першого виду дає 50 одиниць прибутку. Для \(x_1\) плит внесок становить:

\[ 50x_1 \]

Одна плита другого виду дає 40 одиниць. Для \(x_2\) плит маємо:

\[ 40x_2 \]

Загальний прибуток:

\[ Z=50x_1+40x_2 \]

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

\[ Z\rightarrow\max \]

Функцію \(Z\) називають цільовою функцією. Вона перетворює кожний план на число, яке можна порівнювати.

12. Допустиме рішення та оптимальне рішення

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

Перевіримо план:

\[ x_1=2,\qquad x_2=3 \]

Для цементу:

\[ 2\cdot2+5\cdot3=19\le20 \]

Для гравію:

\[ 8\cdot2+5\cdot3=31\le40 \]

Для піску:

\[ 5\cdot2+6\cdot3=28\le30 \]

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

\[ Z=50\cdot2+40\cdot3=220 \]

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

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

13. Загальна математична модель оптимізаційної задачі

Конкретна задача містить дві змінні. Загальна модель може мати \(n\) змінних.

Зберемо їх у вектор.

\[ x= \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} \]

Символ \(n\) означає кількість змінних рішення.

Цільову функцію позначимо через \(f(x)\). Вона оцінює рішення одним числом.

Нерівності позначимо через \(g_i(x)\). Рівності позначимо через \(h_j(x)\).

Загальна задача мінімізації має форму:

\[ \min_x f(x) \]

за умов:

\[ g_i(x)\le0 \]

\[ h_j(x)=0 \]

Індекс \(i\) нумерує нерівності. Індекс \(j\) нумерує рівності.

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

14. Що таке математичне програмування

Математичне програмування вивчає екстремальні задачі та методи їх розв’язування. У цьому курсі використовуватимемо ширше слово «оптимізація» як основне.

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

Основні класи, які зустрінуться в курсі:

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

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

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

14.1. Три типові схеми прикладного моделювання

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

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

Типове ресурсне обмеження має форму:

\[ a_{i1}x_1+a_{i2}x_2+\dots+a_{in}x_n\le b_i \]

Тут \(b_i\) означає доступний запас \(i\)-го ресурсу.

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

Типове обмеження має інший напрям:

\[ a_{i1}x_1+a_{i2}x_2+\dots+a_{in}x_n\ge b_i \]

Тут \(b_i\) задає мінімальну потребу.

Схема 3. Розкрій матеріалу. Існує кілька способів розкрою. Кожний спосіб дає певну кількість деталей. Потрібно отримати задану кількість деталей і контролювати відходи.

Для точної потреби природною може бути рівність:

\[ a_{i1}x_1+a_{i2}x_2+\dots+a_{in}x_n=b_i \]

Три схеми показують важливу закономірність. Знак обмеження походить із предметного правила. Верхня межа веде до \(\le\). Мінімальна потреба веде до \(\ge\). Точний баланс веде до рівності.

14.2. Як вибрати правильний знак обмеження

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

Спочатку сформулюйте правило словами.

Фраза «витрата не перевищує запас» означає:

\[ \text{витрата}\le\text{запас} \]

Фраза «поживність має бути щонайменше 100 одиниць» означає:

\[ \text{поживність}\ge100 \]

Фраза «потрібно виготовити рівно 500 деталей» означає:

\[ \text{кількість деталей}=500 \]

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

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

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

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

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

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

Коротка самоперевірка 1

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

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

15. Етап 1. Вивчення предметної області

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

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

На цьому етапі корисно перевірити одиниці вимірювання. Усі витрати цементу повинні використовувати ту саму одиницю, що й запас цементу.

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

16. Етап 2. Словесна постановка

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

Для нашого прикладу:

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

Такий запис містить три ключові елементи: вибір, критерій і межі.

Словесна постановка допомагає перевіряти знаки майбутніх нерівностей. Фраза «витрати повинні вкладатися у запас» природно веде до верхньої межі.

17. Етап 3. Вибір змінних рішення

Потрібно визначити числа, які система має вибрати.

У задачі плит це \(x_1\) і \(x_2\).

Вибір змінних впливає на всі наступні формули. Змінна повинна мати предметний зміст, одиницю вимірювання та допустимий діапазон.

Погано визначена змінна створює неоднозначні обмеження. Тому цей етап потребує особливої уваги.

18. Етап 4. Формалізація обмежень

Кожне реальне правило перетворюється на математичну умову.

Для ресурсу виконується одна схема:

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

Для цементу цей маршрут дає:

\[ 2x_1+5x_2\le20 \]

Така формалізація прозора. Кожний коефіцієнт має конкретне походження.

19. Етап 5. Формування критерію

Критерій повинен відповідати предметній меті.

У нашому прикладі мета — максимальний прибуток.

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

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

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

20. Етап 6. Вибір класу задачі та методу

Після запису моделі потрібно розпізнати її структуру.

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

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

Для нелінійної функції потрібен інший інструментарій. Тому метод обирають після моделі.

21. Етап 7. Обчислення

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

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

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

Це одна з головних причин незалежної перевірки.

22. Етап 8. Математична перевірка

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

Для ресурсної моделі перевіряють:

1. межі змінних;
2. кожне ресурсне обмеження;
3. значення цільової функції.

Нехай алгоритм повернув план \((2,3)\). Ми вже перевірили три ресурси та отримали прибуток 220.

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

23. Етап 9. Предметна інтерпретація

Фінальний вектор потрібно повернути до мови предметної області.

Запис:

\[ x= \begin{pmatrix} 2 \\ 3 \end{pmatrix} \]

означає дві плити першого виду та три другого.

Вектор сам по собі не є управлінським висновком. Потрібно вказати використання ресурсів, прибуток і важливі припущення моделі.

Інтерпретація завершує цикл моделювання.

24. Повний цикл моделювання

Узагальнений маршрут можна подати схемою.

flowchart TD
    A[Предметна проблема] --> B[Словесна постановка]
    B --> C[Змінні та дані]
    C --> D[Ціль і обмеження]
    D --> E[Клас математичної задачі]
    E --> F[Метод та обчислення]
    F --> G[Математична перевірка]
    G --> H[Предметна інтерпретація]
    H --> I{Модель достатньо адекватна?}
    I -->|так| J[Використання результату]
    I -->|потрібне уточнення| B

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

24.1. Перевірка одиниць як частина математичної логіки

Коефіцієнт у формулі завжди має фізичний або економічний зміст.

Нехай 2 означає дві тонни цементу на одну плиту. Тоді добуток:

\[ 2x_1 \]

має одиницю «тонни цементу», якщо \(x_1\) вимірюється у плитах.

Права частина:

\[ 20 \]

повинна бути записана в тих самих одиницях цементу.

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

Для цільової функції діє та сама логіка. Коефіцієнт 50 має одиницю «прибуток на одну плиту». Добуток \(50x_1\) має одиницю загального прибутку.

24.2. Контрольний приклад із помилковим порядком даних

Припустимо, матриця витрат зберігає ресурси в порядку:

1. цемент;
2. гравій;
3. пісок.

Вектор запасів випадково записано так:

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

Другий і третій запаси переплутані.

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

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

Коротка самоперевірка 2

Перед переходом до Python перевірте, чи ви вмієте помічати помилки моделі, які програма сама не вважає технічною помилкою.

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

25. Для чого код потрібен уже на етапі моделювання

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

Візьмемо план:

\[ x= \begin{pmatrix} 2 \\ 3 \end{pmatrix} \]

Ручний розрахунок дав використання ресурсів:

\[ \begin{pmatrix} 19 \\ 31 \\ 28 \end{pmatrix} \]

і прибуток 220.

Тепер повторимо ці обчислення в Python.

26. Відповідність математики та Python

Математичний об’єкт	Python	Зміст
\(x\)	production_plan	кількість плит
\(A\)	resource_usage_per_unit	витрати ресурсів
\(b\)	available_resources	запаси
\(c\)	profit_per_unit	прибуток від одиниці
\(Ax\)	used_resources	фактична витрата ресурсів
\(c^Tx\)	total_profit	сумарний прибуток

Матриця витрат має три рядки. Рядки відповідають цементу, гравію та піску.

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

Вектор запасів:

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

Вектор прибутку:

\[ c= \begin{pmatrix} 50 \\ 40 \end{pmatrix} \]

27. Навчальний Python-код

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


# Рядки відповідають ресурсам:
# цемент, гравій, пісок.
# Стовпці відповідають двом видам плит.
resource_usage_per_unit = np.array([
    [2.0, 5.0],
    [8.0, 5.0],
    [5.0, 6.0],
])

# Запаси мають той самий порядок,
# що й рядки матриці витрат.
available_resources = np.array([
    20.0,
    40.0,
    30.0,
])

# Прибуток має той самий порядок,
# що й компоненти виробничого плану.
profit_per_unit = np.array([
    50.0,
    40.0,
])

# Перевіряємо конкретний план:
# 2 плити першого виду і 3 другого.
production_plan = np.array([
    2.0,
    3.0,
])

# Оператор @ виконує матричне множення.
# Кожний рядок матриці дає витрату одного ресурсу.
used_resources = (
    resource_usage_per_unit
    @ production_plan
)

# Добуток двох векторів дає сумарний прибуток.
total_profit = (
    profit_per_unit
    @ production_plan
)

# np.all повертає True, коли всі три
# ресурсні нерівності виконуються.
is_feasible = np.all(
    used_resources <= available_resources
)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Використано ресурсів:", used_resources)
print("Доступні ресурси:", available_resources)
print("Сумарний прибуток:", total_profit)
print("План допустимий:", is_feasible)

Очікуваний результат:

Використано ресурсів: [19. 31. 28.]
Доступні ресурси: [20. 40. 30.]
Сумарний прибуток: 220.0
План допустимий: True

Рядок [19. 31. 28.] повторює ручний розрахунок. Значення True означає виконання всіх трьох ресурсних меж.

27.1. Візуальна перевірка ресурсів

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

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

28. Що код ще не робить

Наведений код перевіряє один план. Він не шукає найкращий план.

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

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

У наступних лекціях з’являться відповідні алгоритми для лінійної моделі.

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

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

Навіть коротка модель містить припущення. Їх потрібно робити видимими.

Для нашого прикладу модель припускає:

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

Зміна одного припущення може змінити клас задачі.

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

30. Детермінована та стохастична постановка

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

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

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

31. Неперервні, цілочисельні та бінарні рішення

Неперервна змінна допускає дробові значення.

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

Цілочисельна змінна допускає тільки цілі значення.

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

Бінарна змінна має два значення.

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

Бінарна змінна зручно описує рішення типу «обрати» або «відхилити».

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

32. Як виявляти помилки моделі

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

1. Чи кожна змінна має предметний зміст?
2. Чи відомі одиниці всіх коефіцієнтів?
3. Чи знак кожного обмеження відповідає словесному правилу?
4. Чи порядок коефіцієнтів збігається з порядком змінних?
5. Чи тестовий план дає очікувані ручні значення?
6. Чи цільова функція вимірює потрібний результат?
7. Чи правильно задано тип кожної змінної?

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

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

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

33. Підсумок

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

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

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