Лекція 03. Лінійне програмування: модель і форми подання

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

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

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

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

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

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

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

Наприклад, одна плита використовує 2 одиниці цементу. Дві плити використовують 4 одиниці. Три плити використовують 6 одиниць. Витрата зростає пропорційно кількості.

Такий зв’язок записується виразом \(2x\). Коефіцієнт 2 не залежить від самого \(x\).

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

2. Що означає слово «лінійний»

Розглянемо вираз:

\[ 50x_1+40x_2 \]

Змінні \(x_1\) і \(x_2\) входять у першому степені. Коефіцієнти 50 і 40 є сталими числами.

Лінійними також є вирази:

\[ 2x_1+5x_2 \]

\[ 8x_1+5x_2 \]

\[ 5x_1+6x_2 \]

Кожний член має форму «сталий коефіцієнт, помножений на одну змінну».

Вираз із квадратом змінної має іншу структуру:

\[ x_1^2 \]

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

\[ x_1x_2 \]

Корінь від змінної теж задає нелінійний зв’язок:

\[ \sqrt{x_1} \]

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

3. Наскрізний приклад: бетонні плити

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

Вихідні дані:

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

Позначимо кількість плит першого виду через \(x_1\). Кількість плит другого виду позначимо через \(x_2\).

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

\[ Z=50x_1+40x_2 \]

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

\[ Z\rightarrow\max \]

Ресурсні обмеження мають вигляд:

\[ 2x_1+5x_2\le20 \]

\[ 8x_1+5x_2\le40 \]

\[ 5x_1+6x_2\le30 \]

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

\[ x_1\ge0 \]

\[ x_2\ge0 \]

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

4. Що називають планом

План — конкретний набір значень змінних рішення.

Наприклад:

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

У векторній формі:

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

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

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

5. Що називають допустимим планом

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

Для плану \((2,3)\) перевіримо цемент:

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

Маємо:

\[ 19\le20 \]

Для гравію:

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

Тому:

\[ 31\le40 \]

Для піску:

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

Отримуємо:

\[ 28\le30 \]

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

6. Що називають оптимальним планом

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

Для плану \((2,3)\):

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

Число 220 є значенням цілі для одного допустимого плану.

Оптимальний план має найбільше значення \(Z\) для максимізації. Для задачі мінімізації відповідно шукають найменше значення цілі.

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

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

7. Розгорнута форма задачі

Розгорнута форма показує всі коефіцієнти без скорочень.

Для \(n\) змінних лінійна цільова функція має вигляд:

\[ Z= c_1x_1+ c_2x_2+ \dots+ c_nx_n \]

Коефіцієнт \(c_j\) показує внесок змінної \(x_j\) у цільову функцію.

Одне лінійне обмеження записують так:

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

Індекс \(i\) задає номер обмеження. Індекс \(j\) задає номер змінної.

Коефіцієнт \(a_{ij}\) показує внесок змінної \(x_j\) у \(i\)-те обмеження. Число \(b_i\) задає праву частину цього обмеження.

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

8. Вектор змінних рішення

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

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

Вектор має \(n\) компонент. Кожна компонента відповідає одній змінній рішення.

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

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

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

9. Вектор коефіцієнтів цілі

Коефіцієнти цільової функції теж можна зібрати у вектор.

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

Тоді скалярний добуток \(c^Tx\) повторює звичайний ручний розрахунок.

Для плану:

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

маємо:

\[ c^Tx= 50\cdot2+ 40\cdot3 \]

Отже:

\[ c^Tx=220 \]

Символ \(T\) означає транспонування. Він перетворює вектор-стовпець \(c\) у вектор-рядок для скалярного добутку.

10. Матриця обмежень

Коефіцієнти трьох ресурсних обмежень зберемо у матрицю.

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

Рядки відповідають ресурсам. Стовпці відповідають змінним.

Перший рядок описує цемент. Другий рядок описує гравій. Третій рядок описує пісок.

Матриця має три рядки й два стовпці.

\[ A\in\mathbb{R}^{3\times2} \]

Загалом для \(m\) обмежень і \(n\) змінних:

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

11. Вектор правих частин

Запаси ресурсів утворюють вектор:

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

Порядок компонент \(b\) повинен збігатися з порядком рядків \(A\).

Добуток \(Ax\) дає фактичне використання ресурсів.

Для плану \((2,3)\):

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

Тому три ресурсні умови можна записати одним виразом:

\[ Ax\le b \]

Векторна нерівність читається покомпонентно.

12. Матрична форма лінійної задачі

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

\[ \max_x c^Tx \]

за умов:

\[ Ax\le b \]

\[ x\ge0 \]

Короткий запис містить ту саму інформацію, що й три розгорнуті нерівності.

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

13. Запис через знак сумування

Ще одна компактна форма використовує знак суми.

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

\[ Z= \sum_{j=1}^{n} c_jx_j \]

Для \(i\)-го обмеження:

\[ \sum_{j=1}^{n}a_{ij}x_j\le b_i \]

де:

\[ i=1,\dots,m \]

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

14. Три форми задачі в цьому курсі

Для подальших тем зафіксуємо терміни.

Канонічна форма використовує рівності в основних обмеженнях і невід’ємні змінні.

\[ Ax=b \]

\[ x\ge0 \]

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

Для задачі максимізації природний запис:

\[ Ax\le b \]

\[ x\ge0 \]

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

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

14.1. Що потрібно зрозуміти перед канонічною формою

Нерівність на кшталт \(2x_1+5x_2\le20\) каже лише, що використання ресурсу не перевищує запас. Вона приховує ще одну корисну величину — скільки ресурсу залишилося. Якщо використано 17 одиниць із 20, залишок дорівнює 3.

Тому вводять додаткову змінну запасу. Вона не додає нового фізичного ресурсу й не змінює допустимі виробничі плани. Вона лише робить прихований залишок явним. Після цього баланс можна записати рівністю: «використано + залишок = доступно».

Рівності потрібні для подальшої базисної логіки. У системі рівнянь можна вибрати частину змінних, значення яких визначаються системою, а решту тимчасово покласти рівними нулю. Такий вибір називають базисом. На цій ідеї побудований симплекс-метод, який докладно розбиратиметься в окремій лекції.

15. Навіщо переводити нерівність у рівність

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

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

Розглянемо обмеження цементу.

\[ 2x_1+5x_2\le20 \]

Ліва частина може бути меншою за 20. Різниця означає невикористаний запас.

Введемо додаткову змінну \(s_1\).

\[ s_1= 20- 2x_1- 5x_2 \]

Оскільки ресурсний залишок не може бути від’ємним:

\[ s_1\ge0 \]

Тепер нерівність переходить у рівність:

\[ 2x_1+5x_2+s_1=20 \]

16. Додаткові змінні для всіх ресурсів

Для гравію введемо \(s_2\).

\[ 8x_1+5x_2+s_2=40 \]

Для піску введемо \(s_3\).

\[ 5x_1+6x_2+s_3=30 \]

Додаткові змінні мають простий зміст. Вони показують залишок відповідного ресурсу.

Для плану \((2,3)\):

\[ s_1=20-19=1 \]

\[ s_2=40-31=9 \]

\[ s_3=30-28=2 \]

Вектор залишків:

\[ s= \begin{pmatrix} 1 \\ 9 \\ 2 \end{pmatrix} \]

17. Загальний перехід до канонічної форми

Для стандартної ресурсної задачі:

\[ Ax\le b \]

вводиться вектор додаткових змінних \(s\).

\[ s\ge0 \]

Отримуємо:

\[ Ax+s=b \]

Ця формула має прямий зміст.

\(Ax\) — використані ресурси. \(s\) — невикористані ресурси. \(b\) — повний доступний запас.

Тому для кожного ресурсу виконується баланс:

використано + залишок = доступно.

Цей запис підготує базисну логіку симплекс-методу.

18. Попереднє знайомство з опорним планом

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

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

На цьому етапі достатньо знати зв’язок:

вершина допустимої області ↔ опорний допустимий план.

19. Чому виродження поки лише позначаємо

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

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

19.1. Приклад обмеження з нижньою межею

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

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

Нехай потрібно отримати щонайменше 12 одиниць речовини.

Якщо \(x_1\) та \(x_2\) позначають кількість компонентів, умова має вигляд:

\[ 3x_1+2x_2\ge12 \]

Фраза «щонайменше 12» визначає знак \(\ge\).

Цей приклад пояснює загальну форму LP. Система може містити ресурсні верхні межі та вимоги мінімального рівня.

19.2. Приклад рівності

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

Нехай два способи виробництва дають 2 та 5 деталей певного виду. Потрібно отримати рівно 20 деталей.

Тоді:

\[ 2x_1+5x_2=20 \]

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

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

19.3. Вільна змінна та її подання через невід’ємні змінні

У стандартних і канонічних формах часто зручно працювати з невід’ємними змінними.

Іноді предметна змінна може мати обидва знаки. Наприклад, \(y\) може описувати відхилення від базового рівня.

Таку змінну можна подати різницею двох невід’ємних змінних:

\[ y=y^+-y^- \]

де:

\[ y^+\ge0 \]

\[ y^-\ge0 \]

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

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

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

20. Повний перехід від таблиці даних до LP

Побудуємо модель послідовно.

Крок 1. Вибираємо змінні.

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

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

Крок 2. Записуємо ціль.

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

Крок 3. Записуємо ресурсні обмеження.

\[ 2x_1+5x_2\le20 \]

\[ 8x_1+5x_2\le40 \]

\[ 5x_1+6x_2\le30 \]

Крок 4. Додаємо умови невід’ємності.

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

Крок 5. Формуємо матрицю \(A\), вектори \(b\) і \(c\).

\[ 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} \]

Крок 6. Записуємо компактну модель.

\[ \max_x c^Tx \]

\[ Ax\le b \]

\[ x\ge0 \]

21. Перевірка тестового плану

Візьмемо:

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

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

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

Порівнюємо з запасами:

\[ \begin{aligned} \begin{pmatrix} 19\\ 31\\ 28 \end{pmatrix} &\le \begin{pmatrix} 20\\ 40\\ 30 \end{pmatrix} \end{aligned} \]

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

Ціль:

\[ c^Tx=220 \]

Тестовий план допустимий. Значення цілі дорівнює 220.

22. Перехід тестового плану до канонічної форми

Для того самого плану знайдемо залишки.

\[ s= b-Ax \]

Підставимо числа.

\[ \begin{aligned} s &= \begin{pmatrix} 20\\ 40\\ 30 \end{pmatrix}\\ &\quad- \begin{pmatrix} 19\\ 31\\ 28 \end{pmatrix} \end{aligned} \]

Отримуємо:

\[ s= \begin{pmatrix} 1 \\ 9 \\ 2 \end{pmatrix} \]

Перевірка канонічного балансу:

\[ Ax+s=b \]

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

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

flowchart LR
    A[Таблиця даних] --> B[Змінні x]
    B --> C[Матриця A та вектори b, c]
    C --> D[LP-модель]
    D --> E[Solver]
    E --> F[Кандидат x*]
    F --> G[Перевірка Ax* <= b]
    G --> H[Перевірка c^T x*]

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

23. Що означає активне ресурсне обмеження

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

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

\[ s_i=0 \]

Якщо \(s_i>0\), відповідний ресурс має залишок.

Для плану \((2,3)\) усі три залишки додатні. Тому жоден ресурс не використано повністю.

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

24. Як зміна форми впливає на зміст

Алгебраїчне перетворення повинно зберігати допустимі рішення початкової задачі.

Наприклад, система:

\[ Ax\le b \]

і система:

\[ Ax+s=b,\qquad s\ge0 \]

описують ті самі значення \(x\), якщо \(s\) визначено як невикористаний запас.

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

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

24.1. Як читати розміри матриць

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

Для трьох ресурсів і двох змінних:

\[ A\in\mathbb{R}^{3\times2} \]

Вектор плану:

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

Тому:

\[ Ax\in\mathbb{R}^{3} \]

Результат має три компоненти, бо ресурсів три.

Вектор запасів також має три компоненти:

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

Отже, нерівність \(Ax\le b\) структурно узгоджена.

Для цілі:

\[ c\in\mathbb{R}^{2} \]

Тому скалярний добуток:

\[ c^Tx \]

дає одне число.

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

24.2. Чому форма моделі важлива для алгоритму

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

Геометричний метод природно працює з нерівностями на площині.

Симплекс-логіка потребує системи рівнянь і базису.

Програмний API може мати окремі параметри для нерівностей, рівностей і межі змінних.

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

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

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

25. Як математична модель переходить у SciPy

Функція scipy.optimize.linprog розв’язує задачу мінімізації.

Її базова ціль має форму:

\[ \min_x c^Tx \]

Наша задача максимізує:

\[ 50x_1+40x_2 \]

Для використання linprog змінюємо знак цільових коефіцієнтів.

\[ \max_x c^Tx \quad\Longleftrightarrow\quad \min_x (-c)^Tx \]

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

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

Математика	SciPy / Python	Зміст
\(-c\)	objective	ціль для мінімізації
\(A\)	A_ub	коефіцієнти нерівностей
\(b\)	b_ub	праві частини нерівностей
\(x\ge0\)	bounds=(0, None)	нижні межі
\(x^*\)	result.x	знайдений план
\(Z^*\)	-result.fun	максимум початкової цілі

Позначення ub походить від верхня межа, тобто верхньої межі.

Умова A_ub @ x <= b_ub відповідає нашій ресурсній системі.

27. Програмний розв’язок

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


# Початкова задача максимізує прибуток.
# linprog мінімізує, тому змінюємо знак коефіцієнтів.
objective = np.array([
    -50.0,
    -40.0,
])

# Рядки відповідають цементу, гравію та піску.
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,
])

# Запускаємо linprog: ціль, матрицю нерівностей, праві частини та межі передаємо у фіксованому порядку.
result = linprog(
    c=objective,
    A_ub=constraint_matrix,
    b_ub=constraint_limits,
    bounds=(0.0, None),
    method="highs",
)

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

# Зчитуємо числовий результат розв’язувача, але ще не вважаємо його перевіреним розв’язком.
optimal_plan = result.x
maximum_profit = -result.fun

# Виконуємо матричний або скалярний добуток, який прямо відповідає формулі математичної моделі.
used_resources = (
    constraint_matrix
    @ optimal_plan
)

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

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Оптимальний план:", optimal_plan)
print("Максимальний прибуток:", maximum_profit)
print("Використано ресурсів:", used_resources)
print("Залишки ресурсів:", resource_slack)
print("Статус:", result.status)

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

Оптимальний план: [3.91304348 1.73913043]
Максимальний прибуток: 265.2173913043478
Використано ресурсів: [16.52173913 40.         30.        ]
Залишки ресурсів: [3.47826087 0.         0.        ]
Статус: 0

28. Як читати знайдений результат

Перший компонент плану:

\[ x_1^*\approx3.91304 \]

Другий компонент:

\[ x_2^*\approx1.73913 \]

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

Гравій і пісок використані повністю.

\[ s_2=0 \]

\[ s_3=0 \]

Цемент має залишок.

\[ s_1\approx3.47826 \]

Ці значення підготують геометричне поняття активних обмежень.

28.1. Візуальна перевірка активних ресурсів

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

Для цементу використаний обсяг нижчий за запас. Різниця відповідає додатковій змінній \(s_1\).

29. Математична перевірка розв’язку чисельного розв’язувача

Перший крок — перевірка допустимості.

\[ Ax^*\le b \]

Чисельно:

\[ Ax^*\approx \begin{pmatrix} 16.52174 \\ 40 \\ 30 \end{pmatrix} \]

Порівнюємо з:

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

Усі ресурсні межі виконуються.

Другий крок — повторне обчислення цілі.

\[ Z^*= 50x_1^*+ 40x_2^* \]

Отримуємо:

\[ Z^*\approx265.21739 \]

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

29.1. Як перевіряти рівності й нерівності в програмі

Для нерівностей виду:

\[ Ax\le b \]

зручно обчислити вектор запасів:

\[ s=b-Ax \]

Допустимий план має невід’ємні компоненти \(s\) з урахуванням числового допуску.

Для рівностей виду:

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

використовують нев’язку:

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

Її норму порівнюють із малим числовий допуск.

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

29.2. Чому округлення змінює математичну задачу

Неперервний чисельний розв’язувач знайшов:

\[ x_1^*\approx3.91304 \]

\[ x_2^*\approx1.73913 \]

Механічне округлення до \((4,2)\) дає новий план.

Перевіримо гравій:

\[ 8\cdot4+5\cdot2=42 \]

Запас дорівнює 40.

\[ 42>40 \]

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

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

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

30. Чому дробовий план потребує предметної оцінки

Математична модель вважає \(x_1\) і \(x_2\) неперервними змінними. Тому дробове значення допустиме математично.

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

Тоді потрібно змінити тип змінних.

\[ x_1,x_2\in\mathbb{Z}_{\ge0} \]

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

31. Які помилки найчастіше виникають у формі моделі

Перша група помилок пов’язана з порядком коефіцієнтів. Рядок матриці \(A\) повинен відповідати тій самій компоненті \(b\).

Друга група пов’язана зі знаком нерівності. Верхня ресурсна межа природно задається знаком \(\le\).

Третя група пов’язана з напрямом цілі. У linprog максимізація потребує зміни знака коефіцієнтів.

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

32. Що потрібно запам’ятати про форми LP

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

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

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

32.1. Які припущення стоять за лінійною моделлю

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

Перший принцип — пропорційність. Якщо одна плита потребує 2 одиниці цементу, дві плити потребують 4 одиниці за тієї самої технології.

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

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

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

32.2. Як зрозуміти, що LP уже недостатньо

Розглянемо кілька сигналів.

1. Витрата ресурсу залежить від квадрату обсягу.
2. Прибуток змінюється після певного порогу виробництва.
3. Рішення містить логіку «обрати або не обрати».
4. Змінні повинні бути цілими.
5. Коефіцієнти залежать від випадкового сценарію.

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

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

32.3. Чому LP зручне для перевірки

Лінійна модель має прозорий математичний контракт. Кожний рядок матриці відповідає окремому обмеженню. Кожна компонента вектора \(b\) задає конкретну межу.

Тому знайдений план легко перевірити незалежно від чисельного розв’язувача. Достатньо повторно обчислити \(Ax\), порівняти його з \(b\) та знайти \(c^Tx\).

Ця властивість робить LP хорошою першою моделлю для вивчення обчислювальної оптимізації.

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

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

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

33. Підсумок

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

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

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