§ 51. Многогранники в задачах оптимизации

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

Многогранник допустимых решений — множество точек, координаты которых одновременно удовлетворяют всем ограничениям задачи. Например, условия x ≥ 0, y ≥ 0 и x + y ≤ 6 задают область на координатной плоскости. Это понятие нужно, чтобы отделить разрешённые варианты от тех, которые нарушают хотя бы одно условие.

Линейная целевая функция — выражение вида ax + by + c или ax + by + cz + d, значение которого требуется сделать наибольшим или наименьшим. Коэффициенты при переменных задают, как изменение каждой координаты влияет на результат. Такая функция описывает, например, прибыль или затраты, которые зависят от количества произведённых товаров.

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

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

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

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

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

Если зафиксировать значение целевой функции ax + by + c, постоянную часть можно перенести и получить уравнение ax + by = k. Для разных k получаются параллельные прямые, потому что коэффициенты a и b не меняются. В трёх переменных уравнение ax + by + cz = k задаёт семейство параллельных плоскостей. Значит, изменение значения функции можно представить как сдвиг прямой или плоскости уровня.

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

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

Геометрическая модель задачи оптимизации

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

Разбор задач

1. Наибольшее значение функции 2x + y

При условиях x ≥ 0, y ≥ 0, x + y ≤ 6 найти наибольшее значение функции 2x + y.

1. Условия x ≥ 0 и y ≥ 0 оставляют первую четверть, а x + y ≤ 6 — точки под прямой x + y = 6. Получается треугольник с вершинами (0; 0), (6; 0) и (0; 6).
2. Подставим координаты каждой вершины в целевую функцию. В точках получаем 0, 12 и 6 соответственно.
3. Сравним результаты: наибольшее значение равно 12 и достигается в вершине (6; 0). Это согласуется с коэффициентами: при заданном ограничении выгодно направить весь допустимый ресурс x в переменную с большим коэффициентом.

Ответ: 12.

2. Наименьшее и наибольшее значения функции 3x + 2y

При условиях x ≥ 0, y ≥ 0, x + y ≤ 8, 2x + y ≤ 12 найти наименьшее и наибольшее значения функции 3x + 2y.

1. На границе x + y = 8 и 2x + y = 12 вычтем первое уравнение из второго: x = 4, откуда y = 4. Вместе с ограничениями на неотрицательность получаем вершины (0; 0), (6; 0), (4; 4) и (0; 8).
2. Вычислим функцию в этих точках: 0, 18, 20 и 16 соответственно. Нулевая точка допустима, поэтому минимум равен 0.
3. Сравнение показывает, что максимум равен 20 и достигается в точке пересечения двух граничных прямых. Проверка этой вершины необходима: она не лежит на осях и легко теряется, если смотреть только на пересечения с ними.

Ответ: минимум 0, максимум 20.

3. Наибольшее значение функции 3x + 2y + z

При условиях x ≥ 0, y ≥ 0, z ≥ 0, x + y + z ≤ 10 найти наибольшее значение функции 3x + 2y + z.

1. Допустимая область — часть пространства в первом октанте под плоскостью x + y + z = 10. Её вершины: (0; 0; 0), (10; 0; 0), (0; 10; 0), (0; 0; 10).
2. Подставим координаты вершин в целевую функцию. Получаем соответственно 0, 30, 20 и 10.
3. Наибольшее значение равно 30 в точке (10; 0; 0). Коэффициент при x наибольший, поэтому при общем ограничении сумма ресурсов даёт больший результат, если её целиком отнести к x.

Ответ: 30.

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

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

Забывают ограничения неотрицательности переменных. Без условий x ≥ 0 или y ≥ 0 к области добавляются точки, которые не разрешены задачей. Часто эти ограничения пропускают, потому что они не записаны в виде отдельной наклонной прямой. Перед поиском вершин выпишите все условия и убедитесь, что область лежит в нужных координатных полуплоскостях.

Проверяют не все вершины, особенно пересечения граничных линий. В таком случае экстремум может быть пропущен, ведь он нередко находится именно на пересечении двух ограничений. Обычно это происходит, если находят только пересечения с осями или не решают систему уравнений для граничных прямых. Составьте список всех углов области и проверьте, что координаты каждого удовлетворяют всем ограничениям.

Считают, что экстремум всегда достигается только в одной вершине. Если прямая уровня параллельна ребру, одинаковое крайнее значение может быть на всём ребре; в пространстве оно может заполнить грань. Это заблуждение появляется, когда проверяют только координаты вершин и не рассматривают направление линий уровня. Сравните наклон прямой уровня с направлением ребра: при совпадении оптимальных точек может быть несколько.

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

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

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

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

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

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