最佳化問題

有關此主題的更廣泛資訊，請參見：數學最佳化。

數學、工程學、電腦科學和經濟學領域中，最佳化問題​（英語：Optimization problem）是指從所有可行解中找到最佳良的解的問題。

根據變數是連續的或離散的，可將最佳化問題分為兩類：

• 具有離散變數的最佳化問題稱為離散最佳化，其中必須找到可數集合中的整數、排列或圖等對象。
• 具有連續變數的最佳化問題稱為連續最佳化，其中必須找到連續函式的最佳值。它們可以包括約束問題和多模態問題。

最佳化問題和決定性問題（Decision problem）、功能性問題（Function problem）不同，最佳化問題是：從問題的多個解中，求出最佳解。像背包問題（考慮不同價格和重量的物品，以及可承載一定重量的背包，如何選擇物品，使背包中的物品的總價最高）即屬於最佳化問題。

連續最佳化問題

連續最佳化問題的規範形是 $${\begin{aligned}&{\underset {x}{\operatorname {minimize} }}&&f(x)\\&\operatorname {subject\;to} &&g_{i}(x)\leq 0,\quad i=1,\dots ,m\\&&&h_{j}(x)=0,\quad j=1,\dots ,p\end{aligned}}$$ 其中

• $f:\ \mathbb {R} ^{n}\to \mathbb {R}$是n元向量x的目標函式，其值需要最小化；
• $g_{i}(x)\leq 0$稱作不等式約束；
• $h_{j}(x)=0$稱作等式約束；
• $m\geq 0,\ p\geq 0$。

若$m=p=0$，則問題就是無約束最佳化問題。按照慣例，標準形定義了最小化問題。最大化問題可通過將目標函式取逆得到。

組合最佳化問題

主條目：組合最佳化

組合最佳化問題A是四元組$(I,\ f,\ m,\ g)$，其中

• I是可行值集合；
• 給定可行值$x\in I,\ f(x)$是可行解集；
• 給定可行值x、對應的可行解y，$m(x,\ y)$表示y的測度，一般是正實數。
• g是目標函式，且須取極值。

我們的目標是為某可行值x找到最佳解，即可行解y，且滿足 $$m(x,y)=g\left\{m(x,y'):y'\in f(x)\right\}.$$

對每個組合最佳化問題，有相應的決策問題：對某特定測度$m_{0}$，是否存在可行解。例如，若有包含頂點u、v的圖G，最佳化問題可能是「找到u到v使用最少邊的路徑」，答案可能是4；相應的決策問題是「是否有u到v的路徑使用了少於10的邊數」，可以用簡單的「是否」回答。

近似演算法領域中，演算法是為問題找到近似最佳解。因此，通常的決策的定義是不充分的，因為其只指定了可行解。雖然可以引入合適的決策問題，但描述為最佳化問題更自然。

另見

• 計數問題
• 設計最佳化
• 艾克蘭德變分原理

• 函式問題

• 運籌學
• 滿意原則
• 搜尋問題
• 半無限規劃

外部連結

• How Traffic Shaping Optimizes Network Bandwidth. IPC. 2016-07-12 [2017-02-13].