Лекція 04. Геометрія лінійного програмування: допустима область і вершини

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

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

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

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

1. Навіщо лінійну задачу малювати

Матричний запис \(Ax\le b\) стискає багато нерівностей. Для двох змінних ту саму модель можна побачити на координатній площині.

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

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

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

Графічний метод працює переважно для двох змінних. Його головна цінність — розуміння геометрії лінійної оптимізації.

1.1. Чому виникають слова «опуклість», «вершина» і «лінія рівня»

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

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

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

2. Наскрізна задача

Використаємо модель виробництва бетонних плит.

\[ \max Z=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 \]

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

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

3. Координатна площина як простір планів

Горизонтальна вісь відповідає \(x_1\). Вертикальна вісь відповідає \(x_2\).

Точка:

\[ (2,3) \]

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

Точка:

\[ (5,0) \]

означає п’ять плит першого виду та жодної другої.

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

4. Як нерівність перетворюється на граничну пряму

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

\[ 2x_1+5x_2\le20 \]

Спочатку замінимо знак нерівності рівністю.

\[ 2x_1+5x_2=20 \]

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

Щоб побудувати пряму, достатньо знайти дві точки.

При \(x_1=0\):

\[ 5x_2=20 \]

Отже:

\[ x_2=4 \]

Перша точка:

\[ (0,4) \]

При \(x_2=0\):

\[ 2x_1=20 \]

Тому:

\[ x_1=10 \]

Друга точка:

\[ (10,0) \]

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

5. Чому пряма є тільки межею

Ресурсне обмеження містить знак \(\le\). Тому допустимі точки лежать з одного боку від граничної прямої.

Сама пряма описує повне використання цементу.

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

Тому після побудови прямої потрібно визначити правильну півплощину.

6. Як знайти допустиму півплощину

Найпростіший спосіб — тестова точка. Зручно перевірити початок координат \((0,0)\), якщо він не лежить на граничній прямій.

Підставляємо:

\[ 2\cdot0+5\cdot0=0 \]

Отримуємо:

\[ 0\le20 \]

Умова виконується. Тому допустима півплощина містить точку \((0,0)\).

Для кожного нового обмеження діємо так само.

7. Гранична пряма гравію

Друге ресурсне обмеження:

\[ 8x_1+5x_2\le40 \]

Гранична пряма:

\[ 8x_1+5x_2=40 \]

При \(x_1=0\):

\[ x_2=8 \]

При \(x_2=0\):

\[ x_1=5 \]

Пряма проходить через:

\[ (0,8) \]

і:

\[ (5,0) \]

Точка \((0,0)\) виконує нерівність. Тому потрібна півплощина з боку початку координат.

8. Гранична пряма піску

Третє обмеження:

\[ 5x_1+6x_2\le30 \]

Гранична пряма:

\[ 5x_1+6x_2=30 \]

При \(x_1=0\):

\[ x_2=5 \]

При \(x_2=0\):

\[ x_1=6 \]

Пряма проходить через точки \((0,5)\) та \((6,0)\).

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

9. Що роблять умови невід’ємності

Умова:

\[ x_1\ge0 \]

залишає праву половину площини.

Умова:

\[ x_2\ge0 \]

залишає верхню половину площини.

Разом вони обмежують пошук першим квадрантом.

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

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

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

Кожне обмеження задає півплощину. План повинен належати всім допустимим півплощинам одночасно.

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

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

Точка всередині допустимої множини виконує всі обмеження.

Точка поза нею порушує щонайменше одну умову.

11. Чому перетин обмежень потрібно будувати послідовно

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

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

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

flowchart LR
    A[Уся площина] --> B[Півплощина цементу]
    B --> C[Перетин з півплощиною гравію]
    C --> D[Перетин з півплощиною піску]
    D --> E[Перетин з x1 >= 0]
    E --> F[Перетин з x2 >= 0]
    F --> G[Допустимий многокутник]

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

12. Що означає опуклість

Допустима множина лінійної задачі є опуклою.

Візьмемо дві допустимі точки:

\[ x^{(1)} \]

та:

\[ x^{(2)} \]

Побудуємо проміжну точку:

\[ x(\lambda)= \lambda x^{(1)}+ (1-\lambda)x^{(2)} \]

де:

\[ 0\le\lambda\le1 \]

Коефіцієнт \(\lambda\) визначає положення точки на відрізку між двома кінцями.

Якщо обидві початкові точки допустимі:

\[ Ax^{(1)}\le b \]

і:

\[ Ax^{(2)}\le b \]

тоді:

\[ Ax(\lambda)= \lambda Ax^{(1)}+ (1-\lambda)Ax^{(2)} \]

Через невід’ємність коефіцієнтів \(\lambda\) та \(1-\lambda\) маємо:

\[ Ax(\lambda)\le b \]

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

13. Навіщо опуклість потрібна практично

Опукла область не має внутрішніх «дір» між допустимими точками.

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

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

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

14. Що таке вершина

Вершина — кутова точка допустимого многокутника.

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

Таке обмеження називають активним у даній точці.

Наприклад, якщо:

\[ 8x_1+5x_2=40 \]

то запас гравію використано повністю.

Якщо:

\[ 8x_1+5x_2<40 \]

то обмеження має запас.

15. Вершини на координатних осях

Початок координат:

\[ O=(0,0) \]

є допустимою вершиною.

На осі \(x_2\) діє \(x_1=0\). Найжорсткіше ресурсне обмеження дає:

\[ x_2\le4 \]

Тому отримуємо вершину:

\[ A=(0,4) \]

На осі \(x_1\) діє \(x_2=0\).

Маємо:

\[ x_1\le10 \]

за цементом,

\[ x_1\le5 \]

за гравієм,

і:

\[ x_1\le6 \]

за піском.

Найменша межа дорівнює 5. Тому:

\[ D=(5,0) \]

16. Перетин цементу та піску

Розв’яжемо систему:

\[ \begin{cases} 2x_1+5x_2=20 \\ 5x_1+6x_2=30 \end{cases} \]

Помножимо перше рівняння на 5.

\[ 10x_1+25x_2=100 \]

Помножимо друге рівняння на 2.

\[ 10x_1+12x_2=60 \]

Віднімаємо друге рівняння від першого.

\[ 13x_2=40 \]

Тому:

\[ x_2=\frac{40}{13}\approx3.07692 \]

Підставляємо у перше рівняння.

\[ 2x_1+5\cdot\frac{40}{13}=20 \]

Отримуємо:

\[ x_1=\frac{30}{13}\approx2.30769 \]

Позначимо вершину:

\[ B= \left( \frac{30}{13}, \frac{40}{13} \right) \]

17. Перевірка кандидатної вершини B

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

\[ 8\cdot\frac{30}{13}+5\cdot\frac{40}{13}=\frac{440}{13} \]

Чисельно:

\[ \frac{440}{13}\approx33.84615 \]

Маємо:

\[ 33.84615\le40 \]

Отже, точка \(B\) допустима.

18. Перетин гравію та піску

Розв’яжемо:

\[ \begin{cases} 8x_1+5x_2=40 \\ 5x_1+6x_2=30 \end{cases} \]

Помножимо перше рівняння на 6.

\[ 48x_1+30x_2=240 \]

Помножимо друге рівняння на 5.

\[ 25x_1+30x_2=150 \]

Віднімаємо.

\[ 23x_1=90 \]

Тому:

\[ x_1=\frac{90}{23}\approx3.91304 \]

Підставляємо у перше рівняння.

\[ x_2=\frac{40}{23}\approx1.73913 \]

Отримуємо вершину:

\[ C= \left( \frac{90}{23}, \frac{40}{23} \right) \]

19. Чому перетин цементу та гравію не є вершиною допустимої області

Розв’яжемо:

\[ \begin{cases} 2x_1+5x_2=20 \\ 8x_1+5x_2=40 \end{cases} \]

Віднімання дає:

\[ 6x_1=20 \]

Тому:

\[ x_1=\frac{10}{3} \]

Тоді:

\[ x_2=\frac{8}{3} \]

Перевіримо пісок.

\[ 5\cdot\frac{10}{3}+6\cdot\frac{8}{3}=\frac{98}{3} \]

Чисельно:

\[ \frac{98}{3}\approx32.66667 \]

Це перевищує запас 30.

\[ 32.66667>30 \]

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

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

19.1. Як перевірити всі попарні перетини системно

Три ресурсні прямі утворюють три попарні перетини.

Кандидатами є:

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

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

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

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

19.2. Чому вершина є перетином активних меж

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

У вершині свобода руху обмежена активними прямими.

Для точки \(C\) активні дві межі:

\[ 8x_1+5x_2=40 \]

\[ 5x_1+6x_2=30 \]

Їхній перетин фіксує обидві координати.

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

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

20. Повний набір допустимих вершин

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

Вершина	Координати
\(O\)	\((0,0)\)
\(A\)	\((0,4)\)
\(B\)	\(\left(\frac{30}{13},\frac{40}{13}\right)\)
\(C\)	\(\left(\frac{90}{23},\frac{40}{23}\right)\)
\(D\)	\((5,0)\)

Числові наближення:

\[ B\approx(2.30769,3.07692) \]

\[ C\approx(3.91304,1.73913) \]

Тепер потрібно використати цільову функцію.

20.1. Готова допустима область

Допустима область та її вершини

Заштрихована частина містить усі допустимі плани. Точки \(O\), \(A\), \(B\), \(C\) і \(D\) є вершинами цієї області.

Зірочка позначає вершину \(C\). Подальший аналіз цільової функції пояснить, чому ця вершина є оптимальною.

21. Що таке лінія рівня цільової функції

Ціль:

\[ Z=50x_1+40x_2 \]

Зафіксуємо конкретне значення \(Z\).

Наприклад:

\[ 50x_1+40x_2=200 \]

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

Для іншого значення:

\[ 50x_1+40x_2=240 \]

отримаємо іншу пряму.

Обидві прямі паралельні, бо коефіцієнти при \(x_1\) і \(x_2\) не змінюються.

Таку пряму називають лінією рівня цільової функції.

22. Нормальний вектор і напрям зростання

Для лінійної функції:

\[ Z=c_1x_1+c_2x_2 \]

вектор коефіцієнтів:

\[ c= \begin{pmatrix} c_1 \\ c_2 \end{pmatrix} \]

є нормальним до ліній рівня.

У нашій задачі:

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

Цей вектор вказує напрям зростання лінійної функції.

У подальшому такий вектор називатиметься градієнтом лінійної функції. Для поточної теми достатньо геометричного змісту: він перпендикулярний до ліній рівня та показує сторону зростання \(Z\).

23. Як знайти максимум переміщенням лінії рівня

Візьмемо одну лінію рівня. Переміщуємо її паралельно в напрямку вектора \(c\).

Значення \(Z\) під час такого переміщення зростає.

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

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

У нашій задачі контакт відбувається у вершині \(C\).

23.1. Як виглядає переміщення лінії рівня

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

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

Остання показана лінія торкається допустимої області у вершині \(C\). Тому рисунок узгоджується з подальшим перебором вершин.

24. Перевірка цілі у вершинах

Геометричний висновок корисно підтвердити арифметично.

Для \(O\):

\[ Z(O)=0 \]

Для \(A=(0,4)\):

\[ Z(A)=50\cdot0+40\cdot4=160 \]

Для \(B\):

\[ Z(B)=50\cdot\frac{30}{13}+40\cdot\frac{40}{13} \]

Отримуємо:

\[ Z(B)=\frac{3100}{13}\approx238.46154 \]

Для \(C\):

\[ Z(C)=50\cdot\frac{90}{23}+40\cdot\frac{40}{23} \]

Тому:

\[ Z(C)=\frac{6100}{23}\approx265.21739 \]

Для \(D=(5,0)\):

\[ Z(D)=250 \]

Найбільше значення має вершина \(C\).

25. Графічний алгоритм

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

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

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

26. Що означає опорна пряма

У джерельній термінології лінію рівня:

\[ c_1x_1+c_2x_2=0 \]

можна використати як початкову опорну пряму.

Її зручно переміщувати паралельно самій собі.

Для максимізації рух виконується в напрямку зростання цілі. Для мінімізації напрям змінюється.

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

26.1. Інший спосіб знайти оптимум — перебір вершин

Переміщення лінії рівня дає геометричне пояснення.

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

Для нашої задачі:

\[ Z(O)=0 \]

\[ Z(A)=160 \]

\[ Z(B)\approx238.46154 \]

\[ Z(C)\approx265.21739 \]

\[ Z(D)=250 \]

Максимум отримано у \(C\).

Обидва маршрути повинні дати однаковий висновок. Така подвійна перевірка корисна під час навчання.

26.2. Чому вершини достатні для лінійної цілі

Припустимо, оптимальна точка лежить усередині ребра між двома вершинами \(u\) та \(v\).

Будь-яка точка ребра має форму:

\[ x(\lambda)= \lambda u+ (1-\lambda)v \]

де:

\[ 0\le\lambda\le1 \]

Для лінійної цілі:

\[ c^Tx(\lambda)= \lambda c^Tu+ (1-\lambda)c^Tv \]

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

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

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

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

27. Побудова граничних прямих у Python

Для рисунка потрібно виразити \(x_2\) через \(x_1\).

Цемент:

\[ x_2= \frac{20-2x_1}{5} \]

Гравій:

\[ x_2= \frac{40-8x_1}{5} \]

Пісок:

\[ x_2= \frac{30-5x_1}{6} \]

Ці формули безпосередньо переходять у код.

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


# Значення x1 для побудови граничних прямих.
x1_values = np.linspace(
    0.0,
    6.0,
    400,
)

# Кожна формула отримана з відповідної
# граничної рівності.
cement_boundary = (
    20.0 - 2.0 * x1_values
) / 5.0

# Обчислюємо геометричну характеристику допустимої області або кандидатної вершини.
gravel_boundary = (
    40.0 - 8.0 * x1_values
) / 5.0

# Обчислюємо геометричну характеристику допустимої області або кандидатної вершини.
sand_boundary = (
    30.0 - 5.0 * x1_values
) / 6.0

# Допустимі вершини записані
# у порядку обходу многокутника.
vertices = np.array([
    [0.0, 0.0],
    [0.0, 4.0],
    [30.0 / 13.0, 40.0 / 13.0],
    [90.0 / 23.0, 40.0 / 23.0],
    [5.0, 0.0],
])

# Будуємо графік із тими самими числовими даними, що використовувалися в обчисленнях.
plt.plot(
    x1_values,
    cement_boundary,
    label="Цемент",
)

# Будуємо графік із тими самими числовими даними, що використовувалися в обчисленнях.
plt.plot(
    x1_values,
    gravel_boundary,
    label="Гравій",
)

# Будуємо графік із тими самими числовими даними, що використовувалися в обчисленнях.
plt.plot(
    x1_values,
    sand_boundary,
    label="Пісок",
)

# Заливка показує допустиму область.
plt.fill(
    vertices[:, 0],
    vertices[:, 1],
    alpha=0.2,
)

# Будуємо графік із тими самими числовими даними, що використовувалися в обчисленнях.
plt.xlabel("x1")
plt.ylabel("x2")
plt.xlim(0.0, 6.0)
plt.ylim(0.0, 5.0)
plt.grid()
plt.legend()
plt.show()

Графік повинен показати опуклий многокутник \(OABCD\).

28. Програмна перевірка вершин

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

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


# Задаємо допустимі вершини в порядку, зручному для обчислення цілі або побудови многокутника.
vertices = np.array([
    [0.0, 0.0],
    [0.0, 4.0],
    [30.0 / 13.0, 40.0 / 13.0],
    [90.0 / 23.0, 40.0 / 23.0],
    [5.0, 0.0],
])

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

# Кожний рядок vertices є окремим планом.
# Матричний добуток обчислює прибуток
# одразу для всіх кандидатних вершин.
objective_values = (
    vertices
    @ profit_per_unit
)

# Обчислюємо геометричну характеристику допустимої області або кандидатної вершини.
best_index = int(
    np.argmax(objective_values)
)

# Обчислюємо геометричну характеристику допустимої області або кандидатної вершини.
best_vertex = vertices[best_index]
best_value = objective_values[best_index]

# Виводимо результат і діагностичні величини, щоб зіставити їх з очікуваними числами.
print("Значення цілі:", objective_values)
print("Найкраща вершина:", best_vertex)
print("Максимальний прибуток:", best_value)

Очікуваний максимум близький до 265.21739.

29. Незалежна перевірка оптимальної вершини

Візьмемо:

\[ x^*= \begin{pmatrix} 90/23 \\ 40/23 \end{pmatrix} \]

Перевіримо цемент.

\[ 2\cdot\frac{90}{23}+5\cdot\frac{40}{23}=\frac{380}{23} \]

Чисельно:

\[ \frac{380}{23}\approx16.52174 \]

Цемент має запас.

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

\[ 8\cdot\frac{90}{23}+5\cdot\frac{40}{23}=40 \]

Перевіримо пісок.

\[ 5\cdot\frac{90}{23}+6\cdot\frac{40}{23}=30 \]

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

30. Математичний зміст активних ресурсів

У точці \(C\) два ресурсні обмеження виконуються як рівності.

Гравій:

\[ 8x_1^*+5x_2^*=40 \]

Пісок:

\[ 5x_1^*+6x_2^*=30 \]

Ці ресурси формують вершину.

Цемент має запас:

\[ 20-\left(2x_1^*+5x_2^*\right)=\frac{80}{23} \]

Чисельно:

\[ \frac{80}{23}\approx3.47826 \]

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

30.1. Програмне знаходження перетину двох меж

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

Для вершини \(C\):

\[ \begin{aligned} \begin{pmatrix} 8 & 5\\ 5 & 6 \end{pmatrix} \begin{pmatrix} x_1\\ x_2 \end{pmatrix} &= \begin{pmatrix} 40\\ 30 \end{pmatrix} \end{aligned} \]

У NumPy це відповідає np.linalg.solve.

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


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

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

# Розв'язуємо дві активні граничні рівності.
candidate_vertex = np.linalg.solve(
    active_matrix,
    active_limits,
)

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

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

30.2. Числовий допуск під час перевірки вершини

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

Наприклад, теоретична рівність 40 може обчислитися як:

40.00000000000001

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

Нехай:

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

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

\[ Ax\le b+\varepsilon \]

Допуск захищає від помилкового відхилення точки через з рухомою комою арифметику. Його величина повинна відповідати масштабу задачі.

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

31. Порожня допустима множина

Іноді півплощини не мають спільної точки.

Тоді жоден план не виконує всі умови одночасно.

Такий випадок називають недопустимою задачею.

Графік робить проблему видимою. Обмеження буквально не перетинаються у спільній області.

32. Необмежена допустима область

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

Це ще не визначає поведінку цільової функції.

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

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

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

33. Множинні оптимальні розв’язки

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

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

Тоді задача має множину оптимальних планів.

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

34. Єдина допустима точка або відрізок

Система обмежень іноді стискає область до однієї точки.

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

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

Такі випадки допомагають зрозуміти, що «многокутник» у геометричній теорії може вироджуватися.

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

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

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

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

35.1. Практичний чекліст ручної побудови

Перед завершенням графічного розв’язання перевірте весь маршрут.

Кожна нерівність має граничну пряму.
Для кожної прямої знайдено дві зручні точки.
Допустима півплощина перевірена тестовою точкою.
Умови \(x_1\ge0\) та \(x_2\ge0\) враховані.
Кандидатні перетини перевірені за всіма обмеженнями.
Усі допустимі вершини записані в одному порядку.
Ціль обчислена в кожній вершині.
Геометричний висновок збігається з арифметикою.

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

35.2. Чому рисунок не є остаточною числовою відповіддю

Графік має обмежену точність. Координата, яка візуально виглядає як 3.9, може мати точне значення \(90/23\).

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

Після цього ціль повторно обчислюється формулою.

Для нашого прикладу точний запис:

\[ C= \left( \frac{90}{23}, \frac{40}{23} \right) \]

дає точне значення:

\[ Z(C)= \frac{6100}{23} \]

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

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

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

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

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

Ця мова повториться у двоїстості та KKT-умовах.

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

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

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

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

36. Підсумок

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

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

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