![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/0/06/IP_polytope_with_LP_relaxation.svg/langzh-hk-640px-IP_polytope_with_LP_relaxation.svg.png&w=640&q=50)
可行域
維基百科,自由的 encyclopedia
在最優化與計算機科學中,可行域(feasible region)、可行集(feasible set)或解空間(solution space)指滿足問題約束(可能包括不等式、等式和/或整數約束)的最優化問題的所有可能點(選擇變量的值集)的集合。[1]在候選解的範圍縮小之前,這是問題的初始候選解集。
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/0/06/IP_polytope_with_LP_relaxation.svg/320px-IP_polytope_with_LP_relaxation.svg.png)
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/e/ef/3dpoly.svg/640px-3dpoly.svg.png)
例如,考慮最小化關於變量x、y的函數之值的問題,且有約束
這裏的可行集是x的值在1到10之間、y的值在5到12之間的有序數對
組成的集合。問題的可行集與目標函數是分離的,後者是要優化的對象,上例中目標函數是
。
很多問題中,可行集反映了變量必須非負的約束。在整數規劃問題中,可行集是整數集(或其子集)。線性規劃問題中,可行集是凸多胞形,即多維空間中的一個區域,其邊界由超平面構成,四角是頂點。
約束滿足(Constraint satisfaction)是在可行域內找到一個點的過程。