Системи нерівностей

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

Область допустимих значень

📐Визначення — Система нерівностей та область допустимих значень

Система нерівностей — це сукупність двох або більше нерівностей з тими самими змінними. Точка $(x, y)$ є розв’язком, якщо вона задовольняє кожну нерівність системи одночасно.

Область допустимих значень (або множина розв’язків) — це перетин усіх окремих півплощин, тобто множина всіх точок, що задовольняють усі нерівності одразу.

Область допустимих значень може мати три форми:

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

Метод побудови графіка системи

⚡Теорема — Побудова графіка системи нерівностей

Побудуйте кожну нерівність окремо: накресліть граничну пряму та заштрихуйте відповідну півплощину.
Визначте перетин — область допустимих значень знаходиться там, де всі заштриховані області перетинаються.
Якщо область допустимих значень обмежена, знайдіть кутові точки (вершини), розв’язавши пари рівнянь граничних прямих.

Розв’язаний приклад

✎Приклад — Знаходження області допустимих значень

Знайдіть і опишіть область допустимих значень системи:

$\begin{cases} x + y \leq 4 \\ x - y \geq -2 \\ x \geq 0 \end{cases}$

Розв’язання.

Крок 1. Побудуємо кожну нерівність:

$x + y \leq 4$ : межа $x + y = 4$ (суцільна). Перевірка $(0,0)$ : $0 \leq 4$ ✓. Штрихуємо нижче-лівіше.
$x - y \geq -2$ , тобто $y \leq x + 2$ : межа $x - y = -2$ (суцільна). Перевірка $(0,0)$ : $0 \geq -2$ ✓. Штрихуємо нижче.
$x \geq 0$ : штрихуємо праворуч від осі $y$ .

Крок 2. Область допустимих значень — це перетин усіх трьох заштрихованих областей.

Крок 3. Знаходимо кутові точки, розв’язуючи пари рівнянь граничних прямих:

$x + y = 4$ і $x - y = -2$ : додаємо рівняння, $2x = 2$ , отже $x = 1$ , $y = 3$ . Кутова точка: $(1, 3)$ .
$x + y = 4$ і $x = 0$ : $y = 4$ . Кутова точка: $(0, 4)$ .
$x - y = -2$ і $x = 0$ : $y = 2$ . Кутова точка: $(0, 2)$ .

Область допустимих значень — це трикутник з вершинами $(0, 2)$ , $(0, 4)$ і $(1, 3)$ .

Кутові точки та лінійне програмування

⚡Теорема — Теорема про кутову точку

Якщо лінійну цільову функцію $z = ax + by$ потрібно максимізувати або мінімізувати на обмеженій області допустимих значень (многокутнику), то оптимальне значення досягається у вершині (кутовій точці) цієї області.

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

Для трикутника вище, щоб максимізувати $z = 2x + y$ :

У точці $(0, 2)$ : $z = 0 + 2 = 2$
У точці $(0, 4)$ : $z = 0 + 4 = 4$
У точці $(1, 3)$ : $z = 2 + 3 = 5$ ← максимум

Максимальне значення $z = 2x + y$ на цій області допустимих значень дорівнює $5$ і досягається в точці $(1, 3)$ .

Практика

✏Вправа — Знайдіть область допустимих значень

Знайдіть область допустимих значень та її кутові точки для системи:

$\begin{cases} 2x + y \leq 6 \\ x + 2y \leq 6 \\ x \geq 0 \\ y \geq 0 \end{cases}$

Потім знайдіть максимум $z = 3x + 2y$ на цій області.