Калькулятор графического метода (ЛП с 2 переменными)

Решение и визуализация задач линейного программирования с 2 переменными: интерактивные прямые ограничений, вершины многоугольника решений и оптимум.

Целевая функция (Z)

Z =
x
+
y

Constraints

#1
x
+
y
#2
x
+
y
#3
x
+
y
4.28.312.516.620.824.929.133.237.441.54.69.213.818.423.027.632.236.841.446.0

Оптимальное решение

Z = 33.0000
x = 3.0000
y = 12.0000

Принцип работы

Алгоритм графического метода вычисляет все возможные точки пересечения прямых ограничений с осями координат (x = 0, y = 0).

Каждая вершина-кандидат строго проверяется на удовлетворение исходным неравенствам. Поскольку алгебраическая оценка использует исходные коэффициенты напрямую (val = a · x + b · y), алгоритм корректно обрабатывает отрицательные коэффициенты и изменения знаков неравенств без необходимости ручного преобразования.

Исследование операций и геометрическая оптимизация

Академическое руководство по графическому методу линейного программирования

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

1. Какую задачу решает графический метод?

Графический метод — это наглядный геометрический способ решения задач линейного программирования (ЛП) с двумя переменными (x₁ и x₂). Каждое линейное ограничение задает полуплоскость, границей которой служит прямая линия. Пересечение этих полуплоскостей образует выпуклый многоугольник допустимых решений. Фундаментальная теорема ЛП гарантирует, что если оптимальное решение существует, оно обязательно достигается как минимум в одной из вершин (крайних точек) этого многоугольника.

2. Пошаговый алгоритм графического метода

Шаг 1: Построение граничных прямых

Замените знаки неравенств на равенства (ax₁ + bx₂ = c) и найдите точки пересечения с координатными осями.

Шаг 2: Определение допустимых полуплоскостей

Подставьте контрольную точку (0, 0) в исходное неравенство, чтобы определить допустимую сторону прямой. Учтите неотрицательность (x₁ ≥ 0, x₂ ≥ 0).

Шаг 3: Построение области допустимых решений

Определите общую область пересечения всех полуплоскостей (многоугольник допустимых решений).

Шаг 4: Расчет координат вершин

Решите системы линейных уравнений 2×2 для каждой пары пересекающихся граничных прямых, формирующих вершины.

Шаг 5: Вычисление целевой функции Z

Подставьте координаты каждой допустимой вершины в Z = c₁x₁ + c₂x₂. Вершина с наибольшим (для максимизации) значением дает оптимум.

3. Полный числовой пример с расчетом

Классическая задача производственного планирования с двумя переменными:

Максимизировать Z = 3x₁ + 2x₂
2x₁ + x₂ ≤ 18 (Ограничение 1: Механическая обработка)
2x₁ + 3x₂ ≤ 42 (Ограничение 2: Сборка)
3x₁ + x₂ ≤ 24 (Ограничение 3: Финишная отделка)
x₁ ≥ 0, x₂ ≥ 0 (Условия неотрицательности)

Уравнения граничных прямых

Прямая 1: (0, 18) и (9, 0). Прямая 2: (0, 14) и (21, 0). Прямая 3: (0, 24) и (8, 0).

Вершины допустимой области и расчет Z

Пересечения формируют 5 допустимых вершин:

VertexCoordinates (x₁, x₂)Objective Value ZStatus
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) нарушают другие неравенства и лежат вне допустимой области.

⚠

Игнорирование неограниченности

При минимизации с ограничениями ≥ без верхних пределов область может быть открытой.