Калькулятор графического метода (ЛП с 2 переменными)
Решение и визуализация задач линейного программирования с 2 переменными: интерактивные прямые ограничений, вершины многоугольника решений и оптимум.
Целевая функция (Z)
Constraints
Оптимальное решение
Принцип работы
Алгоритм графического метода вычисляет все возможные точки пересечения прямых ограничений с осями координат (x = 0, y = 0).
Каждая вершина-кандидат строго проверяется на удовлетворение исходным неравенствам. Поскольку алгебраическая оценка использует исходные коэффициенты напрямую (val = a · x + b · y), алгоритм корректно обрабатывает отрицательные коэффициенты и изменения знаков неравенств без необходимости ручного преобразования.
Академическое руководство по графическому методу линейного программирования
Изучите, как графический метод определяет область допустимых решений, находит вершины многоугольника и визуализирует оптимум.
1. Какую задачу решает графический метод?
Графический метод — это наглядный геометрический способ решения задач линейного программирования (ЛП) с двумя переменными (x₁ и x₂). Каждое линейное ограничение задает полуплоскость, границей которой служит прямая линия. Пересечение этих полуплоскостей образует выпуклый многоугольник допустимых решений. Фундаментальная теорема ЛП гарантирует, что если оптимальное решение существует, оно обязательно достигается как минимум в одной из вершин (крайних точек) этого многоугольника.
2. Пошаговый алгоритм графического метода
Замените знаки неравенств на равенства (ax₁ + bx₂ = c) и найдите точки пересечения с координатными осями.
Подставьте контрольную точку (0, 0) в исходное неравенство, чтобы определить допустимую сторону прямой. Учтите неотрицательность (x₁ ≥ 0, x₂ ≥ 0).
Определите общую область пересечения всех полуплоскостей (многоугольник допустимых решений).
Решите системы линейных уравнений 2×2 для каждой пары пересекающихся граничных прямых, формирующих вершины.
Подставьте координаты каждой допустимой вершины в Z = c₁x₁ + c₂x₂. Вершина с наибольшим (для максимизации) значением дает оптимум.
3. Полный числовой пример с расчетом
Классическая задача производственного планирования с двумя переменными:
Уравнения граничных прямых
Прямая 1: (0, 18) и (9, 0). Прямая 2: (0, 14) и (21, 0). Прямая 3: (0, 24) и (8, 0).
Вершины допустимой области и расчет Z
Пересечения формируют 5 допустимых вершин:
| Vertex | Coordinates (x₁, x₂) | Objective Value Z | Status |
|---|---|---|---|
| A (Начало координат) | (0, 0) | Z = 3(0) + 2(0) = 0 | Допустимая |
| B (Ось x₁) | (8, 0) | Z = 3(8) + 2(0) = 24 | Допустимая |
| C (Прямые 1 и 3) | (6, 6) | Z = 3(6) + 2(6) = 30 | Допустимая |
| D (Прямые 1 и 2) | (3, 12) | Z = 3(3) + 2(12) = 33 | Оптимальная вершина |
| E (Ось x₂) | (0, 14) | Z = 3(0) + 2(14) = 28 | Допустимая |
4. Результат и экономическая интерпретация
Оптимальный план: (x₁*, x₂*) = (3, 12) с максимальным значением Z* = 33. Ресурсы 1 и 2 израсходованы полностью (активные ограничения). По ресурсу 3 остается запас в 3 единицы (3(3)+12=21 < 24).
5. Типичные ошибки студентов
Неверный выбор полуплоскости
Всегда проверяйте знак через контрольную точку (0, 0).
Учет недопустимых точек пересечения
Точки вроде (9, 0) или (0, 18) нарушают другие неравенства и лежат вне допустимой области.
Игнорирование неограниченности
При минимизации с ограничениями ≥ без верхних пределов область может быть открытой.