Лекція 02. Лінійна алгебра для оптимізації: вектори, матриці та системи

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

Лекція пояснює вектори, матриці та системи рівнянь через задачі оптимізації. Ви навчитеся читати запис \(Ax=b\), працювати з рангом і нев’язкою та розуміти, коли система містить достатньо незалежної інформації.

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

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

1. Навіщо оптимізації потрібні вектори та матриці

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

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

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

Причинно-наслідковий ланцюг має такий вигляд:

flowchart LR
    A[Є багато пов’язаних чисел] --> B[Фіксуємо їхній порядок]
    B --> C[Збираємо числа у вектор]
    C --> D[Коефіцієнти залежностей збираємо у матрицю]
    D --> E[Одна операція описує багато обчислень]
    E --> F[Модель легко перевірити та передати програмі]

Ця лекція пояснює кожний крок окремо. Формули з’являтимуться після змістового пояснення.

1.1. Чому з’являються вектори, матриці та нев’язка

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

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

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

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

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

Вихідні дані зручно подати таблицею:

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

Прочитаємо таблицю словами. Для однієї плити першого виду потрібно 2 одиниці цементу. Для однієї плити другого виду потрібно 5 одиниць цементу. Загальний запас цементу дорівнює 20 одиницям.

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

Третій рядок описує пісок. Перша плита потребує 5 одиниць. Друга плита потребує 6 одиниць. Доступний запас дорівнює 30.

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

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

Позначимо їх:

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

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

Символи \(x_1\) і \(x_2\) — назви математичних змінних. Індекс показує, до якого виду продукції належить число.

3. Що означає «змінна рішення»

Змінна рішення — число, значення якого визначаємо під час розв’язування задачі. Її зміст задає предметна постановка.

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

Пара чисел

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

задає конкретний виробничий план. Інша пара задасть інший план.

Наприклад:

\[ x_1=1, \qquad x_2=4. \]

Це вже інше рішення. Воно матиме інші витрати ресурсів і інший прибуток.

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

4. Чому два числа об’єднують у вектор

Записувати \(x_1\) і \(x_2\) окремо можна. Для двох змінних це ще зручно. Для двадцяти змінних такий запис швидко стає громіздким.

Тому вводять вектор:

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

Вектор \(x\) — впорядкований набір змінних рішення: перша позиція має зміст \(x_1\), а друга — \(x_2\).

Для плану з двох і трьох плит маємо:

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

Порядок компонент принциповий. Вектор

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

описує дві плити першого виду та три другого. Вектор

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

описує вже три плити першого виду та дві другого.

Математична структура однакова. Прикладний зміст різний.

4.1. Вектор на координатній площині

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

Початок стрілки розташований у точці \((0,0)\), а кінець — у точці \((2,3)\). Тому координати кінця повторюють компоненти вектора.

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

5. Як читати належність вектора до простору

Запис

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

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

Символ \(\mathbb{R}\) означає множину дійсних чисел. До неї належать звичайні числа, з якими працюємо в обчисленнях.

Наприклад:

\[ -2, \qquad 0, \qquad 3.5, \qquad \sqrt{2}. \]

Символ \(n\) означає кількість компонент вектора. Запис \(\mathbb{R}^n\) описує всі вектори з \(n\) дійсних компонент.

Символ \(\in\) читається як «належить». Тому весь запис читаємо словами:

\(x\in\mathbb{R}^n\) — вектор \(x\) має \(n\) дійсних компонент.

У нашій задачі змінних дві. Тому можна записати:

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

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

6. Що таке матриця і навіщо вона потрібна

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

Ці коефіцієнти можна зібрати у матрицю:

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

Матриця — прямокутна таблиця чисел із фіксованим порядком рядків і стовпців.

У нашій моделі діє проста домовленість:

1. рядок відповідає одному ресурсу;
2. стовпець відповідає одній змінній рішення.

Тому перший рядок

\[ (2,5) \]

описує цемент. Перший стовпець

\[ \begin{pmatrix} 2 \\ 8 \\ 5 \end{pmatrix} \]

описує ресурси для плити першого виду.

Матриця \(A\) має три рядки та два стовпці. Її розмір записують так:

\[ 3\times2. \]

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

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

Загальний запис має вигляд:

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

Він означає матрицю з \(m\) рядків і \(n\) стовпців. У задачах оптимізації \(m\) часто відповідає кількості обмежень. Число \(n\) часто відповідає кількості змінних.

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

\[ m=3, \qquad n=2. \]

Тому:

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

Елемент матриці позначають як \(a_{ij}\). Індекс \(i\) задає номер рядка. Індекс \(j\) задає номер стовпця.

Наприклад:

\[ a_{12}=5. \]

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

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

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

8. Звідки береться матричний добуток

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

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

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

Тобто плануємо дві плити першого виду та три другого.

8.1. Цемент

Одна плита першого виду потребує 2 одиниці цементу. Дві такі плити потребують:

\[ 2\cdot2=4. \]

Одна плита другого виду потребує 5 одиниць. Три такі плити потребують:

\[ 5\cdot3=15. \]

Загальна витрата цементу:

\[ 4+15=19. \]

Той самий розрахунок записуємо коротше:

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

8.2. Гравій

Для гравію використовуємо другий рядок матриці:

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

Отже, план витратить 31 одиницю гравію.

8.3. Пісок

Для піску використовуємо третій рядок:

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

Отже, план витратить 28 одиниць піску.

Три результати знову утворюють вектор:

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

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

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

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

9. Як матричне множення працює технічно

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

Загальна формула для \(i\)-го рядка:

\[ (Ax)_i=\sum_{j=1}^{n}a_{ij}x_j. \]

Цей запис теж варто розібрати по частинах.

Символ \((Ax)_i\) означає \(i\)-ту компоненту результату. Символ \(\sum\) означає суму. Індекс \(j\) проходить усі змінні від 1 до \(n\).

Для першого рядка нашої матриці маємо:

\[ (Ax)_1=a_{11}x_1+a_{12}x_2. \]

Після підстановки чисел:

\[ (Ax)_1=2\cdot2+5\cdot3=19. \]

Для другого рядка:

\[ (Ax)_2=8\cdot2+5\cdot3=31. \]

Для третього рядка:

\[ (Ax)_3=5\cdot2+6\cdot3=28. \]

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

10. Навіщо перевіряти розмірності

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

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

\[ A\in\mathbb{R}^{3\times2}, \qquad x\in\mathbb{R}^{2}. \]

Матриця має два стовпці. Вектор має дві компоненти. Множення визначене коректно.

Результат матиме три компоненти:

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

Це відповідає кількості ресурсів.

Схематично:

\[ (3\times2)(2\times1)=(3\times1). \]

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

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

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

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

Його порядок збігається з порядком рядків матриці \(A\).

Перша компонента \(b_1=20\) відповідає цементу. Друга компонента \(b_2=40\) відповідає гравію. Третя компонента \(b_3=30\) відповідає піску.

Порядок створює зв’язок між \(A\) та \(b\). Перший рядок \(A\) завжди порівнюється з першою компонентою \(b\).

12. Звідки береться матрична нерівність

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

Для плану \(x=(2,3)^T\) ми отримали:

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

Запаси мають вигляд:

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

Порівнюємо компоненти з однаковими позиціями:

\[ 19\le20, \]

\[ 31\le40, \]

\[ 28\le30. \]

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

Три нерівності записують компактно:

\[ Ax\le b. \]

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

13. Що означає «допустимий план»

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

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

\[ x= \begin{pmatrix} 4 \\ 3 \end{pmatrix} . \]

Для нього:

\[ Ax= \begin{pmatrix} 23 \\ 47 \\ 38 \end{pmatrix} . \]

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

\[ 23>20, \qquad 47>40, \qquad 38>30. \]

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

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

14. Чому змінні мають бути невід’ємними

У нашій моделі \(x_1\) і \(x_2\) описують кількість продукції. Від’ємна кількість плит не має предметного змісту.

Тому вводимо нижні межі:

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

Компактний запис:

\[ x\ge0. \]

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

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

Отже, межі змінних завжди випливають із предметного змісту.

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

Перед цільовою функцією перевірте, чи впевнено читаєте розмір матриці та одну компоненту добутку \(Ax\).

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

15. Як з’являється цільова функція

Обмеження відповідають на запитання: які плани дозволені? Цільова функція відповідає на інше запитання: який допустимий план кращий?

У нашій задачі критерієм є прибуток.

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

\[ 50x_1. \]

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

\[ 40x_2. \]

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

\[ 50x_1+40x_2. \]

Задача вимагає найбільшого можливого прибутку. Тому пишемо:

\[ \max\; (50x_1+40x_2). \]

Цей вираз називається цільовою функцією.

16. Вектор коефіцієнтів цільової функції

Коефіцієнти 50 і 40 теж зручно зберегти одним вектором:

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

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

Перша компонента \(c_1\) описує внесок першої змінної. Друга компонента \(c_2\) описує внесок другої змінної.

Для плану

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

загальний прибуток дорівнює:

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

17. Що означає скалярний запис цільової функції

Запис

\[ c^Tx \]

є компактною формою тієї самої суми.

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

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

Після транспонування отримуємо рядок:

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

Тепер можна виконати множення:

\[ c^Tx= \begin{pmatrix} 50 & 40 \end{pmatrix} \begin{pmatrix} 2\\ 3 \end{pmatrix} \]

Отримуємо одне число:

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

Тому \(c^Tx\) — числова оцінка плану. У нашій задачі це прибуток.

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

18. Повна модель у розгорнутому вигляді

Тепер усі частини мають зрозуміле походження.

Змінні:

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

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

Ціль:

\[ \max\; 50x_1+40x_2. \]

Обмеження за цементом:

\[ 2x_1+5x_2\le20. \]

Обмеження за гравієм:

\[ 8x_1+5x_2\le40. \]

Обмеження за піском:

\[ 5x_1+6x_2\le30. \]

Межі змінних:

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

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

19. Та сама модель у матричному вигляді

Введемо:

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

Тоді повна модель має вигляд:

\[ \begin{aligned} \max\quad & c^Tx, \\ \text{за умов}\quad & Ax\le b, \\ & x\ge0. \end{aligned} \]

Цей короткий запис не створює нового змісту. Він стискає вже побудовані залежності.

Для двох змінних розгорнута форма дуже наочна. Для великої задачі матрична форма значно зручніша.

20. Що таке система лінійних рівнянь

Оптимізація містить нерівності, але всередині алгоритмів часто виникають рівняння. Тому потрібно впевнено читати запис \(Ax=b\).

Розглянемо систему:

\[ \begin{cases} 2x_1+x_2=7, \\ x_1-x_2=2. \end{cases} \]

Перше рівняння вимагає, щоб комбінація \(2x_1+x_2\) дорівнювала 7. Друге рівняння задає іншу умову для тих самих змінних.

Розв’язок системи — набір значень, який виконує всі рівняння одночасно.

Перевіримо точку:

\[ x_1=3, \qquad x_2=1. \]

Перше рівняння:

\[ 2\cdot3+1=7. \]

Друге рівняння:

\[ 3-1=2. \]

Обидві рівності виконуються. Тому \((3,1)\) є розв’язком системи.

20.1. Система рівнянь як перетин прямих

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

Розглянемо систему:

\[ \begin{cases} 2x+y=7\\ x-y=2 \end{cases} \]

Графік показує точку \((3,1)\). Підстановка підтверджує результат:

\[ 2\cdot3+1=7 \]

\[ 3-1=2 \]

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

21. Матричний запис системи рівнянь

Ту саму систему можна записати так:

\[ A= \begin{pmatrix} 2 & 1\\ 1 & -1 \end{pmatrix} \]

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

\[ b= \begin{pmatrix} 7\\ 2 \end{pmatrix} \]

Тоді:

\[ Ax=b. \]

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

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

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

Перед Python переконайтеся, що система \(Ax=b\) і нев’язка вже читаються як конкретна перевірка, а не як абстрактні символи.

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

22. Чому відповідь потрібно перевіряти

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

Для системи \(Ax=b\) перевірка дуже проста. Підставляємо знайдений вектор у початкову систему.

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

\[ Ax=b. \]

Зручно перенести праву частину вліво:

\[ Ax-b=0. \]

Вектор

\[ r=Ax-b \]

називають нев’язкою.

23. Нев’язка без формальної «магії»

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

Уявімо, що програма повернула приблизний результат:

\[ x= \begin{pmatrix} 3.000000001 \\ 0.999999999 \end{pmatrix} . \]

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

Тому перевіряють розмір нев’язки:

\[ \lVert Ax-b\rVert\le\varepsilon. \]

Символ \(\lVert\cdot\rVert\) означає норму. У цьому випадку норма вимірює загальний розмір помилки.

Число \(\varepsilon\) задає допустиму похибку. Його називають допуском (числовий допуск).

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

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

24. Чому цей принцип важливий для всього курсу

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

Далі з’являться інші перевірки:

1. для ресурсних обмежень перевірятимемо порушення \(Ax\le b\);
2. для безумовного мінімуму перевірятимемо норму градієнта;
3. для двоїстих задач перевірятимемо розрив двоїстості;
4. для задач з обмеженнями перевірятимемо умови Каруша — Куна — Таккера.

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

25. Мінімальне поняття базису

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

На площині візьмемо два вектори:

\[ e_1= \begin{pmatrix} 1\\ 0 \end{pmatrix} \]

\[ e_2= \begin{pmatrix} 0\\ 1 \end{pmatrix} \]

Вектор

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

можна скласти з них:

\[ v=3e_1+2e_2. \]

Вектори \(e_1\) і \(e_2\) дають координатну основу площини. Коефіцієнти 3 і 2 показують внесок кожного базисного вектора.

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

26. Як математика переходить у Python

У Python вектор і матриця природно подаються масивами NumPy.

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

Математичний запис	Змінна Python	Зміст
\(A\)	resource_usage_per_unit	витрати ресурсів на одиницю продукції
\(x\)	production_plan	кількість продукції кожного виду
\(b\)	available_resources	доступні запаси ресурсів
\(c\)	profit_per_unit	прибуток від одиниці продукції

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

# Матриця витрат ресурсів на одну одиницю продукції.
# Рядки відповідають ресурсам у фіксованому порядку:
# цемент, гравій, пісок.
#
# Стовпці відповідають видам продукції:
# плита 1, плита 2.
#
# Наприклад, число 2.0 у першому рядку означає:
# одна плита першого виду потребує 2 одиниці цементу.
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,
])

# Прибуток від однієї одиниці кожного виду продукції.
# Перший елемент стосується плити 1, другий — плити 2.
profit_per_unit = np.array([
    50.0,
    40.0,
])

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

# Матричний добуток A @ x обчислює загальні витрати ресурсів.
#
# Для цього плану:
# цемент: 2 * 2 + 5 * 3 = 19;
# гравій: 8 * 2 + 5 * 3 = 31;
# пісок:  5 * 2 + 6 * 3 = 28.
used_resources = resource_usage_per_unit @ production_plan

# Скалярний добуток c @ x обчислює сумарний прибуток:
# 50 * 2 + 40 * 3 = 220.
total_profit = profit_per_unit @ production_plan

# План допустимий, коли кожне ресурсне обмеження виконується.
# Порівняння створює логічний масив:
# [19 <= 20, 31 <= 40, 28 <= 30].
#
# np.all(...) повертає True лише тоді, коли всі умови істинні.
is_feasible = np.all(used_resources <= available_resources)

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

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

Оператор @ виконує матричне множення. Рядок

# resource_matrix має форму «ресурси × види продукції», а plan — по одному числу на кожний вид.
# Матричний добуток повертає вектор загальних витрат ресурсів у порядку рядків матриці.
resource_use = resource_matrix @ plan

відповідає математичному запису:

\[ Ax. \]

Рядок

# profit_per_unit і plan мають однаковий порядок видів продукції.
# Скалярний добуток підсумовує «прибуток за одиницю × кількість» для всіх видів.
profit = profit_per_unit @ plan

відповідає запису:

\[ c^Tx. \]

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

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

Результат читається по рядках. План використовує 19 одиниць цементу з доступних 20. Гравію потрібно 31 одиницю з 40.

Піску потрібно 28 одиниць з 30. Жоден запас не перевищено. Тому is_feasible має значення True.

Число 220.0 — сумарний прибуток для плану \((2,3)^T\). Воно відповідає ручному обчисленню \(50\cdot2+40\cdot3=220\).

27. Перевірка системи рівнянь у Python

Для квадратної системи можна використати numpy.linalg.solve.

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

# Коефіцієнти системи:
# 2x + y = 7
# x - y = 2
coefficient_matrix = np.array([
    [2.0, 1.0],
    [1.0, -1.0],
])

# Праві частини рівнянь у тому самому порядку.
right_side = np.array([
    7.0,
    2.0,
])

# NumPy знаходить вектор x, для якого A @ x = b.
solution = np.linalg.solve(coefficient_matrix, right_side)

# Нев’язка показує, наскільки знайдений розв’язок
# виконує початкову систему після числових обчислень.
residual = coefficient_matrix @ solution - right_side
residual_norm = np.linalg.norm(residual)

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Розв’язок:", solution)
print("Нев’язка:", residual)
print("Норма нев’язки:", residual_norm)

Програма поверне розв’язок, близький до \((3,1)^T\). Норма нев’язки буде дуже малою.

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

28. Як читати компактну оптимізаційну модель

Розглянемо запис:

\[ \begin{aligned} \max\quad & c^Tx, \\ \text{за умов}\quad & Ax\le b, \\ & x\ge0. \end{aligned} \]

Його потрібно читати послідовно.

1. \(x\) — вектор чисел, які потрібно вибрати.
2. \(c\) — внесок кожної змінної у цільову функцію.
3. \(c^Tx\) — числова оцінка вибраного плану.
4. \(A\) — коефіцієнти ресурсних обмежень.
5. \(Ax\) — фактичне використання ресурсів вибраним планом.
6. \(b\) — доступні запаси або межі.
7. \(Ax\le b\) — усі ресурсні обмеження виконуються.
8. \(x\ge0\) — змінні мають допустимі нижні межі.

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

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

29. Повна логіка переходу від задачі до формули

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

flowchart TD
    A[Що треба обрати?] --> B[Змінні рішення x]
    B --> C[Що обмежує вибір?]
    C --> D[Коефіцієнти A і межі b]
    D --> E[Фактичні витрати Ax]
    E --> F[Перевірка Ax ≤ b]
    B --> G[Як оцінити рішення?]
    G --> H[Коефіцієнти c]
    H --> I[Ціль cᵀx]
    F --> J[Допустимий план]
    I --> K[Порівняння допустимих планів]

Ця схема стане основою наступної лабораторної роботи.

30. Типові місця, де виникає плутанина

30.1. Символи починають жити без змісту

Проблема виникає, коли студент одразу пише \(A\), \(b\), \(c\). Спочатку потрібно визначити прикладний зміст кожного об’єкта.

30.2. Порядок змінних змінюється посеред моделі

Якщо \(x_1\) означає перший продукт, перший стовпець \(A\) теж описує перший продукт. Перша компонента \(c\) дотримується того самого порядку.

30.3. Рядок матриці не відповідає правій частині

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

30.4. Векторна нерівність сприймається як одна умова

Запис \(Ax\le b\) представляє систему нерівностей. Кожна компонента повинна пройти перевірку.

30.5. Число з програми приймається без математичної перевірки

Для рівнянь перевіряйте нев’язку. Для ресурсної моделі перевіряйте кожне обмеження.

31. Практична перевірка теми

Після опрацювання матеріалу студент повинен пояснити такі записи словами:

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

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

\[ Ax, \]

\[ Ax\le b, \]

\[ c^Tx, \]

\[ Ax=b, \]

\[ r=Ax-b. \]

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

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

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

32. Підготовка до лабораторної роботи 01

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

До початку роботи потрібно вміти:

1. пояснити, що означають рядки й стовпці матриці;
2. прочитати систему \(Ax=b\) словами;
3. розуміти, навіщо потрібні незалежні рівняння;
4. перевірити розв’язок через \(Ax-b\);
5. порівняти нев’язку з числовим допуском;
6. знайти найбільше абсолютне відхилення серед кількох контролів.

33. Підсумок

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

Лінійна система \(Ax=b\) показує, як алгебра пов’язує невідомі з умовами моделі. Під час чисельної роботи важливо перевіряти розмірності, ранг і нев’язку \(Ax-b\), а не покладатися лише на факт успішного завершення обчислення. Для маленького прикладу ручний розрахунок допомагає зрозуміти операцію, після чого бібліотека виконує рутинну арифметику.

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