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

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

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

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

從數學(xué)角度看，最優(yōu)化問(wèn)題可以分為無(wú)約束最優(yōu)化和約束最優(yōu)化。所謂無(wú)約束最優(yōu)化問(wèn)題是比較簡(jiǎn)單的微分問(wèn)題，可用微分求解。

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

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

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

從數學(xué)上比較一般的觀(guān)點(diǎn)來(lái)看，所謂最優(yōu)化問(wèn)題可以概括為一種數學(xué)模型：結合一個(gè)函數F(x)以及自變量 應滿(mǎn)足一定的條件，求X 為怎樣的值時(shí)，F(x)取得其最大值或最小值。通常，稱(chēng)F(x)為目標函數，X 應滿(mǎn)足的條件為約束條件。求目標函數F(x)

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

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

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

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

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

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