Новые калькуляторы

Графический метод решения ЗЛП

В линейном программировании используется графический метод, с помощью которого определяют выпуклые множества (многогранник решений). Если основная задача линейного программирования имеет оптимальный план, то целевая функция принимает значение в одной из вершин многогранника решений (см. рисунок).

Назначение сервиса. С помощью данного сервиса можно в онлайн режиме решить задачу линейного программирования геометрическим методом, а также получить решение двойственной задачи (оценить оптимальность использования ресурсов). Дополнительно создается шаблон решения в Excel.

Инструкция. Выберите количество строк (количество ограничений).

Количество ограничений
Если количество переменных больше двух, необходимо систему привести к СЗЛП (см. пример и пример №2). Если ограничение двойное, например, 1 ≤ x1 ≤ 4, то оно разбивается на два: x1 ≥ 1, x1 ≤ 4 (т.е. количество строк увеличивается на 1).

Решение задачи линейного программирования графическим методом включает следующие этапы:

  1. На плоскости X10X2 строят прямые.
  2. Определяются полуплоскости.
  3. Определяют многоугольник решений;
  4. Строят вектор N(c1,c2), который указывает направление целевой функции;
  5. Передвигают прямую целевую функцию c1x2 + c2x2 = 0 в направлении вектора N до крайней точки многоугольника решений.
  6. Вычисляют координаты точки и значение целевой функции в этой точке.
Линейное программирование. Графический метод

При этом могут возникать следующие ситуации:
  1. Целевая функция принимает экстремальное (минимальное или максимальное) значение в единственной точке А.
  2. Целевая функция принимает экстремальное значение в любой точке отрезка АВ.
  3. Целевая функция не ограничена сверху (при поиске на максимум) или снизу (на минимум)
  4. Система ограничений задачи несовместна

Пример. Компания изготавливает два вида продукции – П1 и П2. Для производства продукции используются два вида сырья – С1 и С2. Оптовые цены единицы продукции равна: 5 д.е. для П1 и 4 д.е. для П2. Расход сырья на единицу продукции вида П1 и вида П2 дан в таблице.
Таблица – Расход сырья на производство продукции

Сырье Расход сырья на 1 ед. продукции Максимальный запас сырья, ед.
П1 П2
М1 6 4 24
М2 1 2 6

Установлены ограничения на спрос продукции: ежедневный объем производства продукции П2 не должен превышать ежедневный объем производства продукции П1 не более чем на 1 тонну; максимальный ежедневный объем производства П2 не должен превышать 2 т.
Требуется определить:
Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?
  1. Сформулировать математическую модель задачи линейного программирования.
  2. Решить задачу линейного программирования графическим способом (для двух переменных).

Решение.
Сформулируем математическую модель задачи линейного программирования.
x1 – производство продукции П1, ед.
x2 – производство продукции П2, ед.
x1, x2 ≥ 0

Ограничения по ресурсам
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6

Ограничения по спросу
x1 +1 ≥  x2
x2 ≤ 2

Целевая функция
5x1 + 4x2 → max

Тогда получаем следующую ЗЛП:
6x1 + 4x2 ≤ 24
x1 + 2x2 ≤ 6
x2 - x1 ≤  1
x2 ≤ 2
x1, x2 ≥ 0
5x1 + 4x2 → max