Задача линейного программирования

Решим задачу методом подстановки и анализа ограничений.

1️⃣ Запишем целевую функцию:
$L = x_1 + x_2 \to min$

2️⃣ Система ограничений:
* $y_1 = -8 + 4x_1 + x_2 \geq 0$
* $y_2 = -7 + 3x_1 + x_2 \geq 0$
* $y_3 = -10 + x_1 + 8x_2 \geq 0$
* $x_1, x_2, y_1, y_2, y_3 \geq 0$

3️⃣ Преобразуем ограничения относительно $x_2$:
* $x_2 \geq 8 - 4x_1$ (из первого неравенства)
* $x_2 \geq 7 - 3x_1$ (из второго неравенства)
* $x_2 \geq \frac{10 - x_1}{8}$ (из третьего неравенства)

4️⃣ Поскольку $x_2$ должно удовлетворять всем неравенствам одновременно, выбираем максимальное значение из правых частей:
$x_2 \geq max{8 - 4x_1, 7 - 3x_1, \frac{10 - x_1}{8}}$

5️⃣ Так как целевая функция $L = x_1 + x_2$ минимизируется, то $x_2$ должно принимать минимально возможное значение, удовлетворяющее всем ограничениям.

6️⃣ Анализируя графики функций, находим точку минимума в пересечении линий $x_2 = 8 - 4x_1$ и $x_2 = 7 - 3x_1$:

$8 - 4x_1 = 7 - 3x_1$
$8 - 7 = 4x_1 - 3x_1$
$1 = x_1$

Подставляя $x_1 = 1$ в любое из уравнений:
$x_2 = 8 - 4(1) = 4$

7️⃣ Проверяем третье ограничение:
$-10 + 1 + 8(4) \geq 0$
$-10 + 1 + 32 = 23 \geq 0$ - условие выполняется

Ответ: Минимум достигается в точке $(x_1, x_2) = (1, 4)$, минимальное значение целевой функции $L_{min} = 1 + 4 = 5$

Задача линейного программирования

Решим задачу графическим методом.

1️⃣ Запишем систему ограничений в привычном виде:
* $4x_1 + x_2 \geq 8$ (из $y_1 \geq 0$)
* $3x_1 + x_2 \geq 7$ (из $y_2 \geq 0$)
* $x_1 + 8x_2 \geq 10$ (из $y_3 \geq 0$)
* $x_1 \geq 0, x_2 \geq 0$

2️⃣ Целевая функция: $L = x_1 + x_2 \to min$

3️⃣ На графике построены все ограничения:
* Красная линия: $4x_1 + x_2 = 8$
* Синяя линия: $3x_1 + x_2 = 7$
* Зеленая линия: $x_1 + 8x_2 = 10$

4️⃣ Область допустимых решений - это пересечение всех полуплоскостей, определяемых неравенствами. На графике это выпуклая область.

5️⃣ Так как целевая функция $L = x_1 + x_2$ линейна, её минимум достигается в одной из угловых точек области допустимых решений.

6️⃣ Точка минимума находится на пересечении прямых $4x_1 + x_2 = 8$ и $3x_1 + x_2 = 7$:
* $4x_1 + x_2 = 8$
* $3x_1 + x_2 = 7$
* Вычитая уравнения: $x_1 = 1$
* Подставляя обратно: $x_2 = 4$

Ответ: Минимум достигается в точке $(x_1, x_2) = (1, 4)$, минимальное значение целевой функции $L_{min} = 1 + 4 = 5$