Алгебра · объяснение и практика

Как решить ограниченную линейную задачу по вершинам

Найти максимум линейной функции двух непрерывных переменных на пересечении полуплоскостей и явного конечного прямоугольника.

Неизвестное x показывает найденное значение — пять.

Вузовский уровень · Все вузовские темы

В теме Неравенства и промежутки · Учебная карта

Главная мысль

В двумерной ограниченной линейной задаче достаточно проверить допустимые вершины многоугольника. Явные верхние границы вместе с неотрицательностью делают область конечной; пустую область нужно отличать от неограниченной задачи и от нескольких оптимальных решений.

Метод и условия

Запишите каждое ограничение в одном направлении: 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. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться