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

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

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

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

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

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

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

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

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

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

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

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

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

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

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