§ 3. Линейная функция на выпуклом многоугольнике

Определения и обозначения

Линейная функция двух переменных имеет вид f(x, y) = ax + by + c, где x и y — переменные, а a, b и c — числа. Коэффициенты a и b определяют, как значение функции зависит от каждой координаты, а c прибавляется к результату. Формула позволяет найти число, соответствующее любой точке (x, y).

Выпуклый многоугольник — многоугольник, который целиком лежит по одну сторону от каждой прямой, содержащей его сторону. Иначе говоря, отрезок между любыми двумя точками такого многоугольника не выходит за его пределы. Это свойство помогает понять, почему крайнее положение линии уровня приходится на вершину или сторону.

Максимум функции на многоугольнике — её наибольшее значение в точках этой фигуры, а минимум — наименьшее. Ищут именно значения f(x, y), а не наибольшие или наименьшие координаты. Эти понятия нужны, когда требуется выбрать лучшую или худшую точку среди допустимых.

Опорная прямая — прямая, которая касается выпуклого многоугольника и оставляет его целиком по одну сторону от себя. Она может проходить через одну вершину или совпасть с целой стороной. При поиске экстремума так ведёт себя линия уровня в крайнем положении.

Как это устроено

Многоугольник задаёт область допустимых точек (x, y): выбирать точки вне его нельзя. Линейная функция сопоставляет каждой разрешённой точке число ax + by + c, и задача сводится к сравнению этих чисел. Поэтому сначала устанавливают границы области, а уже затем ищут наилучшее значение внутри неё.

Линия уровня — множество точек, в которых функция имеет одно и то же значение k; её уравнение имеет вид ax + by + c = k. При изменении k меняется положение линии, но не её направление: коэффициенты a и b остаются прежними. Поэтому линии уровней параллельны, и их удобно представлять как одинаковые прямые, сдвигающиеся по плоскости.

Чтобы найти максимум, линию уровня сдвигают в ту сторону, где значения k растут; для минимума — туда, где они уменьшаются. Пока линия пересекает многоугольник, соответствующее значение функции достигается в его точках. В крайнем положении касание ещё сохраняется, а при дальнейшем сдвиге в этой области точек уже не будет.

Крайнее касание выпуклого многоугольника происходит в вершине или вдоль его стороны. Если линия уровня касается одной вершины, значение функции в ней является крайним. Если касание приходится на сторону, то значение одинаково во всех её точках, ведь каждая из них лежит на одной линии уровня.

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

Как определить экстремум линейной функции на выпуклом многоугольнике

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

Разбор задач

Прямоугольник

Найти наибольшее и наименьшее значения f(x, y) = 2x + y на прямоугольнике с вершинами (0, 0), (3, 0), (3, 2), (0, 2). Область задана четырьмя вершинами, поэтому сначала найдём значение функции в каждой из них. Сравним результаты, не выбирая вершину по одной координате.

1. В точке (0, 0): f = 2 · 0 + 0 = 0.
2. В точке (3, 0): f = 2 · 3 + 0 = 6.
3. В точке (3, 2): f = 2 · 3 + 2 = 8.
4. В точке (0, 2): f = 2 · 0 + 2 = 2. Из чисел 0, 6, 8 и 2 выбираем крайние.

Ответ: минимум равен 0 в точке (0, 0), максимум равен 8 в точке (3, 2). Проверки вершин достаточно по свойству линейной функции на выпуклом многоугольнике.

Треугольник

Найти максимум и минимум f(x, y) = x + 2y в треугольнике с вершинами (0, 0), (4, 0), (0, 3). Треугольник выпуклый, поэтому проверка его вершин охватывает всю область. Коэффициент при y равен 2, но это само по себе не позволяет сразу назвать нужную вершину: обе координаты участвуют в формуле.

1. В точке (0, 0): f = 0 + 2 · 0 = 0.
2. В точке (4, 0): f = 4 + 2 · 0 = 4.
3. В точке (0, 3): f = 0 + 2 · 3 = 6.
4. Сравниваем три значения: 0 < 4 < 6.

Ответ: минимум равен 0 в точке (0, 0), максимум равен 6 в точке (0, 3). На сторонах значения функции не выходят за значения в их концах, поэтому дополнительная проверка внутренних точек не нужна.

Экстремум на стороне

Определить экстремальные значения f(x, y) = 3x − 2y на многоугольнике с вершинами (0, 0), (2, 0), (3, 2), (1, 2), указав все точки, в которых они достигаются. Важно не только найти крайние числа, но и заметить, если одинаковое значение получается в концах стороны. Вычислим функцию последовательно для всех вершин.

1. В точке (0, 0): f = 0.
2. В точке (2, 0): f = 3 · 2 − 2 · 0 = 6.
3. В точке (3, 2): f = 9 − 4 = 5.
4. В точке (1, 2): f = 3 − 4 = −1. Сравнение даёт максимум 6 и минимум −1.

Ответ: максимум 6 достигается в вершине (2, 0), минимум −1 — в вершине (1, 2). Значения в концах каждой стороны различны, поэтому линейная функция не постоянна ни на одной стороне. В частности, в этой задаче экстремумы достигаются только в названных вершинах.

Типичные ошибки

Ошибка — проверять лишь одну или несколько удобных вершин. Кажется, что большая координата даст большой результат, но вклад координат зависит от коэффициентов функции, а экстремальная вершина заранее неизвестна. Подставьте координаты всех вершин и проверьте, что ни одна не пропущена.

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

Нельзя путать максимум функции с максимумом координат x или y. Например, вершина с наибольшим x не обязательно даёт наибольшее ax + by + c: знак и величина коэффициентов влияют на результат. Проверка проста: сравнивайте только числа, полученные подстановкой каждой пары координат в формулу.

Ещё одна ошибка — искать максимум на всей плоскости, забывая про многоугольник. На неограниченной плоскости функция может не иметь наибольшего или наименьшего значения, но в задаче допустимы только точки заданной фигуры. Перед вычислениями выпишите вершины и не рассматривайте точки вне многоугольника.

Связь с другими темами

Для решения нужно уметь подставлять координаты точки в формулу функции и выполнять вычисления с числами. Также важно знать координаты вершин многоугольника и понимать его выпуклость: она объясняет, почему крайнее касание линии уровня приходится на вершину или сторону. Метод используется в линейном программировании — задачах, где выбирают лучший вариант при заданных ограничениях. Например, ограничения задают допустимую область, а линейная функция показывает результат, который требуется увеличить или уменьшить.

Что запомнить

• Линейная функция двух переменных имеет вид f(x, y) = ax + by + c.
• Многоугольник задаёт область, в которой ищут экстремум.
• Линии уровня линейной функции параллельны.
• На выпуклом многоугольнике максимум и минимум достаточно искать среди вершин.
• Если крайняя линия уровня совпадает со стороной, экстремум достигается на всей этой стороне.
• Для сравнения кандидатов вычисляют значения функции, а не сравнивают координаты.