Область допустимых решений
Область допустимых решений (ОДР) (также множество допустимых решений, англ. Feasible region, feasible set) — в исследовании операций, оптимизации и математическом моделировании это множество всех возможных решений (наборов значений переменных), которые удовлетворяют всем ограничениям, наложенным на задачу.
ОДР представляет собой подпространство, в котором ведется поиск оптимального решения. Любое решение, находящееся вне этой области, является недопустимым.
Определение и формирование
Область допустимых решений формируется как пересечение множеств, определяемых каждым отдельным ограничением задачи. Ограничения могут быть представлены в виде:
- Неравенств: Устанавливают верхние или нижние границы для значений переменных или их комбинаций (например, "расход ресурса А не должен превышать 100 единиц", "количество произведенной продукции должно быть не менее 50 штук").
- Равенств: Требуют точного выполнения условия (например, "суммарный объем перевозок должен быть равен 1000 тонн", "баланс входящих и исходящих потоков равен нулю").
- Условий на знак переменных: Часто переменные должны быть неотрицательными, целочисленными или принадлежать определенному дискретному множеству.
Точка (или вектор значений переменных) принадлежит ОДР тогда и только тогда, когда она одновременно удовлетворяет всем этим ограничениям.
Геометрическая интерпретация
ОДР часто имеет наглядную геометрическую интерпретацию, особенно в задачах с небольшим числом переменных:
- В двумерном пространстве (2 переменные): Каждое линейное ограничение-неравенство задает полуплоскость. ОДР представляет собой пересечение этих полуплоскостей — выпуклый многоугольник (возможно, неограниченный или пустой).
- В трехмерном пространстве (3 переменные): Каждое линейное ограничение-неравенство задает полупространство. ОДР является пересечением этих полупространств — выпуклым многогранником (полиэдром).
- В многомерном пространстве: ОДР, определяемая линейными ограничениями, является выпуклым многогранником (политопом).
В случае нелинейных ограничений ОДР может иметь более сложную форму и не быть выпуклой.
Роль в оптимизации
Область допустимых решений играет фундаментальную роль в оптимизации:
1. Определение пространства поиска: Оптимальное решение задачи (если оно существует) всегда находится внутри ОДР или на её границе. Алгоритмы оптимизации ищут экстремум целевой функции именно в этой области. 2. Проверка существования решений: Если ОДР является пустым множеством (т.е. ограничения противоречат друг другу), то задача не имеет допустимых решений, а следовательно, и оптимального решения. 3. Влияние на оптимальное решение: Форма и размер ОДР напрямую влияют на возможность достижения экстремума целевой функции и на значение этого экстремума.
Свойства ОДР (в задачах линейного программирования)
В задачах линейного программирования (ЛП), где все ограничения и целевая функция линейны, ОДР обладает важными свойствами:
- Выпуклость: Если две точки принадлежат ОДР, то и весь отрезок, соединяющий эти точки, также принадлежит ОДР. Это свойство гарантирует, что оптимальное решение (если оно существует и единственно) будет находиться в одной из вершин многогранника ОДР.
- Замкнутость: ОДР включает свои границы (из-за нестрогих неравенств ≤, ≥ и равенств).
ОДР может быть:
- Ограниченной: Имеет конечные размеры.
- Неограниченной: Простирается бесконечно в одном или нескольких направлениях.
- Пустой: Не содержит ни одной точки.
Литература
- Вентцель Е. С. Исследование операций: задачи, принципы, методология. — М.: Наука, 1988.
- Акоф Р., Сасиени М. Основы исследования операций. — М.: Мир, 1971.
- Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
- Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)