Алгебра · объяснение и практика
Как решить ограниченную линейную задачу по вершинам
Найти максимум линейной функции двух непрерывных переменных на пересечении полуплоскостей и явного конечного прямоугольника.

Вузовский уровень · Все вузовские темы
В теме Неравенства и промежутки · Учебная карта
Главная мысль
В двумерной ограниченной линейной задаче достаточно проверить допустимые вершины многоугольника. Явные верхние границы вместе с неотрицательностью делают область конечной; пустую область нужно отличать от неограниченной задачи и от нескольких оптимальных решений.
Метод и условия
Запишите каждое ограничение в одном направлении: 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. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Сумма расстояний до двух точек: откуда берётся целый отрезок решений
Находим минимум суммы двух расстояний на прямой, выводим её кусочную формулу и решаем уровневое уравнение с пустым, непрерывным или двухточечным ответом.
Открыть темуВложенные модули: почему ветви нужно раскрывать снаружи
Решаем уравнение с двумя вложенными модулями через промежуточную неотрицательную переменную и считаем число различных корней при слиянии ветвей.
Открыть темуКак перемножать оценки величин и не потерять знак
Получаем границы произведения по двум числовым отрезкам: проверяем четыре сочетания концов, знаки и достижимость при дополнительных связях.
Открыть тему