求解最優(yōu)化問題的方法(經(jīng)典組合優(yōu)化問題的一般求解方法)

1.經(jīng)典組合優(yōu)化問題的一般求解方法有哪些

組合最優(yōu)化方法（combinatorial optimizationmethod ）求解組合最優(yōu)化問題的方法一般地，對于不同類的組合最優(yōu)化問題，對應著不同的求解方法.判定一個組合最優(yōu)化方法好壞的主要標準是運算次數(shù).用n表示某一組合最優(yōu)化問題的規(guī)模p(n)表示在對方法影響最壞的情況下所需的運算次數(shù).若p(n)是n的多項式函數(shù)，則稱該方法是多項式算法.凡能用多項式算法求解的問題都稱為P問題.有一類問題稱為NP完全問題，若這類組合最優(yōu)化問題具有如下特點：1.它們都未找到多項式算法.2.如果對其中某一問題存在多項式算法，那么此類中的所有問題也都有多項式算法.已發(fā)現(xiàn)有成千的組合最優(yōu)化問題屬于NP完成問題.為求解該類中的問題，人們往往采用“啟發(fā)式”方法.這些方法一般地，不能保證求得問題的最優(yōu)解，但常能得到較好的近似解。

2.解決經(jīng)濟分析的最優(yōu)化問題的基本步驟是什么

從數(shù)學角度看，最優(yōu)化問題可以分為無約束最優(yōu)化和約束最優(yōu)化。所謂無約束最優(yōu)化問題是比較簡單的微分問題，可用微分求解。

管理決策問題往往也就是最優(yōu)化問題，而比較常用和方便的方法就是邊際分析法。

所謂“無約束”，即產(chǎn)品產(chǎn)量、資源投入量、價格和廣告費的支出等都不受限制。在這種情況下，最優(yōu)化的原則是：邊際收入等于邊際成本，也就是邊際利潤為零時，利潤最大，此時的業(yè)務量為最優(yōu)業(yè)務量。管理決策中的諸多最優(yōu)化問題，比如投入要素之間如何組合才能使成本最低；企業(yè)的產(chǎn)量多大，才能實現(xiàn)利潤最大，當因變量為自變量的連續(xù)函數(shù)時，經(jīng)濟學與數(shù)學意義是統(tǒng)一的，可用邊際分析法解決；而在處理離散數(shù)列的最優(yōu)化問題時則可以用統(tǒng)計的方法先將離散數(shù)列擬合成連續(xù)函數(shù)，求得最優(yōu)點，然后在原離散數(shù)列中找到離擬合曲線最優(yōu)點最近的前后兩點，比較其值及其投入量，既而求得最優(yōu)點。

有約束條件的最優(yōu)化包括一個或幾個貨幣、時間、生產(chǎn)能力或其他方面的限制，當存在不等式約束條件時，可以采用線性規(guī)劃。大多數(shù)情況下，管理者知道某些約束是連在一起的，即它們是同樣的約束條件，可以采用拉格朗日乘數(shù)法解決這些問題。

從數(shù)學上比較一般的觀點來看，所謂最優(yōu)化問題可以概括為一種數(shù)學模型：結合一個函數(shù)F(x)以及自變量 應滿足一定的條件，求X 為怎樣的值時，F(xiàn)(x)取得其最大值或最小值。通常，稱F(x)為目標函數(shù)，X 應滿足的條件為約束條件。求目標函數(shù)F(x)

在約束條件X 下的最大值或最小值問題，就是一般最優(yōu)問題的數(shù)學模型，可以用數(shù)學符號簡潔地表示為MinF(x)或MaxF(x)。解決最優(yōu)化問題地關鍵步驟是如何把實際問題，抽象成數(shù)學模型，也就是構造出目標函數(shù)與約束條件，一旦這一步完成，對于簡單問題，可借助圖形或微積分來解決，遇到比較復雜地課題，可利用現(xiàn)有地數(shù)學軟件或最優(yōu)化軟件，比如Matlab, Mathematica, Lindo,Lingo 等來計算。下面舉例說明如何計算有約束條件地最優(yōu)化問題。

例 設某種產(chǎn)品的產(chǎn)量是勞動力x和原料y(t)的函數(shù)，f(x),y=60X 3y 2，假定每單位勞動力費用100元，每單位原料費用200元，現(xiàn)有2萬元資金用于生產(chǎn)，為了得到最多的產(chǎn)品，應如何安排勞動力和原料。

解：依題意，可歸結為求函數(shù)f(x,y)=60x 3y 2在約束條件100x+200y=20000下的最大值，故可用拉格朗日乘數(shù)法求解。

3.目前對于優(yōu)化控制問題有哪些求解方法

最優(yōu)控制理論（optimal control theory），是現(xiàn)代控制理論的一個主要分支，著重于研究使控制系統(tǒng)的性能指標實現(xiàn)最優(yōu)化的基本條件和綜合方法。 最優(yōu)控制理論是研究和解決從一切可能的控制方案中尋找最優(yōu)解的一門學科。它是現(xiàn)代控制理論的重要組成部分。

為了解決最優(yōu)控制問題，必須建立描述受控運動過程的運動方程，給出控制變量的允許取值范圍，指定運動過程的初始狀態(tài)和目標狀態(tài)，并且規(guī)定一個評價運動過程品質優(yōu)劣的性能指標。通常，性能指標的好壞取決于所選擇的控制函數(shù)和相應的運動狀態(tài)。系統(tǒng)的運動狀態(tài)受到運動方程的約束，而控制函數(shù)只能在允許的范圍內選取。因此，從數(shù)學上看，確定最優(yōu)控制問題可以表述為：在運動方程和允許控制范圍的約束下，對以控制函數(shù)和運動狀態(tài)為變量的性能指標函數(shù)（稱為泛函）求取極值（極大值或極小值）。解決最優(yōu)控制問題的主要方法有古典變分法、極大值原理和動態(tài)規(guī)劃。