Линейная оптимизация двух переменных в прямоугольной области
Найти максимум cₓx+cᵧy при ваших линейных ограничениях и обязательных конечных границах x и y.
Ваш пример
Разбор примера
Максимум = 9
| x | y | Целевая функция |
|---|---|---|
| 0 | 0 | 0 |
| 5/2 | 0 | 15/2 |
| 0 | 4 | 8 |
| 1 | 3 | 9 |
- Проверены все попарные пересечения граничных прямых.
- Допустимых вершин: 4.
- При нескольких оптимальных вершинах весь соединяющий их допустимый отрезок также оптимален.
Метод и условия расчёта
Добавляем 0≤x≤Xmax, 0≤y≤Ymax.
Пересекаем пары граничных прямых, отбрасываем недопустимые вершины и сравниваем целевую функцию.
Теория к методу
В двумерной ограниченной линейной задаче достаточно проверить допустимые вершины многоугольника. Явные верхние границы вместе с неотрицательностью делают область конечной; пустую область нужно отличать от неограниченной задачи и от нескольких оптимальных решений.
Запишите каждое ограничение в одном направлении: ax+by не больше d. Неравенство с противоположным знаком сначала умножьте на минус единицу. Добавьте условия неотрицательности обеих переменных и реальные конечные верхние границы, которые входят в постановку. Их нельзя придумывать после расчёта только ради получения конечного ответа: такая добавка меняет допустимое множество.
Пример: Максимизируем 3x+2y при x+y≤4, 2x+y≤5 и 0≤x,y≤10. Пересечение двух наклонных границ даёт x=1, y=3.
Значение цели равно 9. На осях лучшие допустимые точки (0,4) и (5/2,0) дают 8 и 15/2, поэтому найденная вершина действительно лучше обеих.
Вопросы по теме
Зачем верхние границы?
Они делают область ограниченной. Этот интерфейс не маскирует неограниченную задачу искусственной большой константой.
Проверяются целые точки?
Нет. Это непрерывная линейная задача; дробная вершина допустима и не округляется до целого плана.
Неравенства и промежутки: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.