跳至內容

最佳化問題

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

數學工程學電腦科學經濟學領域中,最佳化問題​(英語:Optimization problem)是指從所有可行解英語feasible solution中找到最佳良的解的問題

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

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

連續最佳化問題

[編輯]

連續最佳化問題的規範形[1] 其中

  • n元向量x目標函數,其值需要最小化;
  • 稱作不等式約束
  • 稱作等式約束;

,則問題就是無約束最佳化問題。按照慣例,標準形定義了最小化問題最大化問題可通過將目標函數取逆得到。

組合最佳化問題

[編輯]

組合最佳化問題A是四元組,其中

  • I是可行值集合
  • 給定可行值是可行解集;
  • 給定可行值x、對應的可行解y表示y測度,一般是正實數。
  • g是目標函數,且須取極值

我們的目標是為某可行值x找到最佳解,即可行解y,且滿足

對每個組合最佳化問題,有相應的決策問題:對某特定測度,是否存在可行解。例如,若有包含頂點uvG,最佳化問題可能是「找到uv使用最少邊的路徑」,答案可能是4;相應的決策問題是「是否有uv的路徑使用了少於10的邊數」,可以用簡單的「是否」回答。

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

另見

[編輯]

參考文獻

[編輯]
  1. ^ Boyd, Stephen P.; Vandenberghe, Lieven. Convex Optimization (pdf). Cambridge University Press. 2004: 129 [2024-03-07]. ISBN 978-0-521-83378-3. (原始內容存檔 (PDF)於2021-05-09). 
  2. ^ Ausiello, Giorgio; et al, Complexity and Approximation Corrected, Springer, 2003, ISBN 978-3-540-65431-5 

外部連結

[編輯]