Линейное программирование: графический метод решения

Что такое линейное программирование?

Линейное программирование — это математический метод поиска наилучшего решения в задачах с ограничениями. Представьте, что вы управляете фабрикой и хотите максимизировать прибыль, но у вас ограниченное количество ресурсов — именно здесь на помощь приходит ЛП!

💡 Ключевые компоненты любой задачи ЛП: • Целевая функция — что мы хотим максимизировать или минимизировать (прибыль, затраты) • Ограничения — условия, которые нельзя нарушить (ресурсы, время, мощности) • Неотрицательные переменные — обычно количество товаров не может быть отрицательным

Графический метод: когда и зачем

Графический метод — это наглядный способ решения задач линейного программирования с двумя переменными. Мы будем строить графики на плоскости и находить оптимальное решение визуально!

🎯 Графический метод идеален для: • Понимания основ оптимизации • Задач с двумя переменными (например, производство двух видов продукции) • Визуализации допустимой области и целевой функции

Шаг за шагом: алгоритм решения

📘 Шаг 1: Постановка задачи

Рассмотрим классический пример:

Фабрика производит стулья (x) и столы (y). Прибыль от стула — 3 у.е., от стола — 5 у.е. Ограничения:
• Дерево: 2x + 4y ≤ 20
• Трудозатраты: 3x + 2y ≤ 18
• Неотрицательность: x ≥ 0, y ≥ 0

Целевая функция: P = 3x + 5y → max

📐 Шаг 2: Построение ограничений

Преобразуем неравенства в уравнения для построения прямых:

2x + 4y = 20 → y = 5 - 0.5x
3x + 2y = 18 → y = 9 - 1.5x

Нарисуем эти прямые на координатной плоскости. Область, удовлетворяющая всем ограничениям, будет находиться ниже обеих прямых (так как у нас неравенства "≤") и в первой четверти (x≥0, y≥0).

🔺 Шаг 3: Нахождение допустимой области

Допустимая область — это многоугольник, образованный пересечением всех ограничений. В нашем случае это четырехугольник с вершинами:

Точка	Координаты (x;y)	Как найдена
A	(0;0)	Пересечение x=0 и y=0
B	(0;5)	Пересечение x=0 и первой прямой
C	(4;3)	Пересечение двух прямых
D	(6;0)	Пересечение y=0 и второй прямой

🎯 Шаг 4: Поиск оптимального решения

Оптимальное решение всегда находится в одной из вершин допустимой области! Подставим координаты каждой вершины в целевую функцию:

Точка	Расчет	Прибыль (P)
A (0;0)	3×0 + 5×0	0
B (0;5)	3×0 + 5×5	25
C (4;3)	3×4 + 5×3	27
D (6;0)	3×6 + 5×0	18

Максимальная прибыль 27 у.е. достигается в точке C(4;3) — производим 4 стула и 3 стола!

💡 Совет: Для проверки можно построить линию целевой функции и двигать ее параллельно до последнего касания с допустимой областью — это и будет оптимальная точка!

Практическая задача

Решим вместе еще одну задачу для закрепления метода!

Условие:

Предприятие производит два вида краски: для внутренних (x) и наружных (y) работ. Прибыль: 1 у.е./кг для внутренней, 2 у.е./кг для наружной. Ограничения:
• Сырье A: 2x + y ≤ 10
• Сырье B: x + 2y ≤ 12
• Спрос: y ≤ 5
• x ≥ 0, y ≥ 0

Целевая функция: P = x + 2y → max

Решение:

Строим прямые:
- 2x + y = 10 → y = 10 - 2x
- x + 2y = 12 → y = 6 - 0.5x
- y = 5 (горизонтальная прямая)
Находим вершины допустимой области:
- A(0;0) — пересечение x=0, y=0
- B(0;5) — пересечение x=0 и y=5
- C(2;5) — пересечение y=5 и первой прямой
- D(4;4) — пересечение первой и второй прямой
- E(6;0) — пересечение y=0 и второй прямой
Вычисляем прибыль в каждой точке:
- A: 0 + 2×0 = 0
- B: 0 + 2×5 = 10
- C: 2 + 2×5 = 12
- D: 4 + 2×4 = 12
- E: 6 + 2×0 = 6

Максимальная прибыль 12 у.е. достигается в точках C(2;5) и D(4;4) — это значит, что у нас есть альтернативные оптимальные решения!

✨ Интересный факт: Если целевая функция параллельна одной из сторон многоугольника, оптимальных решений будет бесконечно много вдоль этой стороны!

Типичные случаи и особенности

Неограниченное решение — если допустимая область не ограничена сверху/снизу
Отсутствие решения — когда ограничения противоречивы и допустимая область пуста
Вырожденное решение — когда более двух ограничений пересекаются в одной точке
Альтернативные оптимумы — как в нашей второй задаче