Област на допустимите решения

Област на допустимите решения (ОДР) (също множество от допустими решения, англ. 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)

Вижте също

• Изследване на операциите
• Оптимизация
• Математически модел
• Ограничения
• Допустимо решение
• Оптимално решение
• Целева функция
• Линейно програмиране
• Изпъкнало множество