數學工程學電腦科學經濟學領域中,最佳化問題​(英語: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]

另見

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

參考文獻

外部連結

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.