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

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

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

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

Целевая функция — величина, которую требуется максимизировать или минимизировать; в линейной задаче она имеет вид F = a₁x₁ + … + aₙxₙ. Коэффициенты показывают вклад каждой переменной в итоговый результат. Сравнение значений функции позволяет выбрать лучший допустимый вариант.

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

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

Ограничения вида a₁x₁ + … + aₙxₙ ≤ b задают полупространства: каждое неравенство оставляет одну сторону от граничной плоскости. Пересечение таких полупространств и условий на переменные, например x ≥ 0, образует допустимую область. Она может быть пустой, ограниченной или уходить бесконечно далеко, поэтому её свойства нужно проверить до поиска ответа.

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

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

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

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

Сопоставление задачи и геометрии

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

Разбор задач

Задача. Найдите максимум и минимум функции F = 2x + 3y при условиях x ≥ 0, y ≥ 0, x + y ≤ 4, 2x + y ≤ 6. Здесь переменные неотрицательны, а два последних неравенства ограничивают суммарные значения. Геометрически область лежит в первой четверти и находится ниже обеих прямых.

1. Найдём вершины области. Границы x = 0 и y = 0 дают точку (0, 0); при y = 0 ограничение 2x ≤ 6 даёт крайнюю точку (3, 0). При x = 0 условие x + y ≤ 4 даёт (0, 4).

2. Найдём пересечение двух наклонных границ: x + y = 4 и 2x + y = 6. Вычитая первое уравнение из второго, получаем x = 2, затем y = 2. Точка (2, 2) удовлетворяет неотрицательности и обоим исходным ограничениям.

3. Убедимся, что перечислены все вершины. Граничные прямые могут пересекаться и в других точках, но, например, пересечение 2x + y = 6 с осью x уже даёт (3, 0), а пересечение x + y = 4 с осью y — (0, 4). Остальные пересечения с осями либо совпадают с найденными, либо не лежат в допустимой области.

4. Вычислим функцию в каждой вершине: F(0, 0) = 0, F(3, 0) = 6, F(2, 2) = 10, F(0, 4) = 12. Сравнение показывает, что наибольшее значение равно 12, а наименьшее — 0. Это сравнение достаточно, поскольку область ограничена и функция линейная.

Ответ: максимум F = 12 достигается при (x, y) = (0, 4), минимум F = 0 — при (x, y) = (0, 0). Если переменные обозначают количество продукции, найденные координаты задают соответствующие планы, а значение F — итоговый показатель. В прикладной задаче дополнительно учитывают смысл переменных и единицы измерения.

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

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

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

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

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

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

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

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

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

• Система линейных неравенств задаёт допустимую область как пересечение полупространств.

• Для ограниченного многогранника линейная целевая функция достигает максимума и минимума хотя бы в одной вершине.

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

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

• Если область не ограничена, существование конечного экстремума проверяют отдельно.