最優(yōu)化方法教案--東北大學(xué)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第一章 最優(yōu)化問(wèn)題與數(shù)學(xué)預(yù)備知識(shí)最優(yōu)化分支：線性規(guī)劃，整數(shù)規(guī)劃，幾何規(guī)劃，非線性規(guī)劃，動(dòng)態(tài)規(guī)劃。又稱規(guī)劃論。應(yīng)用最優(yōu)化方法解決問(wèn)題時(shí)一般有以下幾個(gè)特點(diǎn)：1. 實(shí)用性強(qiáng)2. 采用定量分析的科學(xué)手段3. 計(jì)算量大，必須借助于計(jì)算機(jī)4. 理論涉及面廣應(yīng)用領(lǐng)域：工業(yè)，農(nóng)業(yè)，交通運(yùn)輸，能源開發(fā)，經(jīng)濟(jì)計(jì)劃，企業(yè)管理，軍事作戰(zhàn)。§1.1 最優(yōu)化問(wèn)題實(shí)例最優(yōu)化問(wèn)題：追求最優(yōu)目標(biāo)的數(shù)學(xué)問(wèn)題。經(jīng)典最優(yōu)化理論：（1） 無(wú)約束極值問(wèn)題： （或）其中，是定義在n維空間上的可微函數(shù)。解法（求極值點(diǎn)）：求駐點(diǎn)，即滿足并驗(yàn)證這些駐點(diǎn)是否極值點(diǎn)。（2） 約束極值問(wèn)題：s.t. 解法：采用La

2、grange乘子法，即將問(wèn)題轉(zhuǎn)化為求Lagrange函數(shù)的無(wú)約束極值問(wèn)題。近代最優(yōu)化理論的實(shí)例：例1 (生產(chǎn)計(jì)劃問(wèn)題) 設(shè)某工廠有3種資源B1，B2，B3，數(shù)量各為b1，b2，b3，要生產(chǎn)10種產(chǎn)品A1，A10 。每生產(chǎn)一個(gè)單位的Aj需要消耗Bi的量為aij，根據(jù)合同規(guī)定，產(chǎn)品Aj的量不少于dj，再設(shè)Aj的單價(jià)為cj 。問(wèn)如何安排生產(chǎn)計(jì)劃，才能既完成合同，又使總收入最多？（線性規(guī)劃問(wèn)題）數(shù)學(xué)模型：設(shè)Aj的計(jì)劃產(chǎn)量為，z為總收入。目標(biāo)函數(shù)：約束條件： 線性規(guī)劃問(wèn)題通常采用單純形法來(lái)求解。例2 (工廠設(shè)址問(wèn)題) 要在m個(gè)不同地點(diǎn)計(jì)劃修建m個(gè)規(guī)模不完全相同的工廠，他們的生產(chǎn)能力分別是（為簡(jiǎn)便起見，假

3、設(shè)生產(chǎn)同一種產(chǎn)品），第i個(gè)工廠的建設(shè)費(fèi)用。又有n個(gè)零售商店銷售這種產(chǎn)品，對(duì)這種產(chǎn)品的需求量分別為，從第i個(gè)工廠運(yùn)送一個(gè)單位產(chǎn)品到第j個(gè)零售商店的運(yùn)費(fèi)為cij。試決定應(yīng)修建哪個(gè)工廠，使得既滿足零售商店的需求，又使建設(shè)工廠和運(yùn)輸?shù)目傎M(fèi)用最小。（混合整數(shù)規(guī)劃問(wèn)題）數(shù)學(xué)模型： 設(shè)第i個(gè)工廠運(yùn)往第j個(gè)零售商店的產(chǎn)品數(shù)量為xij（i=1，m；j=1，n），且目標(biāo)函數(shù)：約束條件：整數(shù)規(guī)劃問(wèn)題通?？捎梅种Χń绶ɑ蚋钇矫娣▉?lái)求解。例3 (投資計(jì)劃問(wèn)題) 假設(shè)某一個(gè)生產(chǎn)部門在一段時(shí)間內(nèi)可用于投資的總金額為億元，可供選擇的項(xiàng)目總共有n個(gè)，分別記為1，2，n。并且已知對(duì)第j個(gè)項(xiàng)目的投資總數(shù)為億元，而收益額總數(shù)為億元。

4、問(wèn)如何使用資金億元，才能使單位投資獲得的收益最大。（非線性規(guī)劃問(wèn)題）數(shù)學(xué)模型：設(shè)目標(biāo)函數(shù)：約束條件： 非線性規(guī)劃問(wèn)題的求解方法很多，是本課的重點(diǎn)。動(dòng)態(tài)規(guī)劃是解決“多階段決策過(guò)程”的最優(yōu)化問(wèn)題的一種方法，基于“Bellman最優(yōu)性原理”，例如：資源分配問(wèn)題，生產(chǎn)與存儲(chǔ)問(wèn)題。例4 (多參數(shù)曲線擬合問(wèn)題)已知熱敏電阻依賴于溫度的函數(shù)關(guān)系為 （*）其中，是待定的參數(shù)，通過(guò)實(shí)驗(yàn)測(cè)得和的15組數(shù)據(jù)列表如下，如何確定參數(shù)？i12345678505560657075808534.7828.6123.6519.6316.3713.7211.549.744i9101112131415909510010511011

5、51208.2617.036.0055.1474.4273.823.307建立數(shù)學(xué)模型：測(cè)量點(diǎn)與曲線對(duì)應(yīng)的點(diǎn)產(chǎn)生“偏差”，即得如下無(wú)約束最優(yōu)化問(wèn)題：通常采用最小二乘法。§1.2 最優(yōu)化問(wèn)題的數(shù)學(xué)模型一、 最優(yōu)化問(wèn)題的數(shù)學(xué)模型1. 定義1：設(shè)向量.若，則記或；若，則記或。2一般模型： ， （1）s.t. 其中，；，是關(guān)于變量的實(shí)值連續(xù)函數(shù)，一般可假定它們具有二階連續(xù)偏導(dǎo)數(shù)。3向量模型： ， （1）s.t. 其中，稱為目標(biāo)函數(shù)；，稱為約束函數(shù)；滿足約束條件（2），（3）的點(diǎn)稱為容許解或容許點(diǎn)（或可行解）；可行解的全體稱為容許域（或可行域），記為R；滿足（1）的容許點(diǎn)稱為最優(yōu)點(diǎn)或最優(yōu)解（或

6、極?。ù螅c(diǎn)），記為；稱為最優(yōu)值；不帶約束的問(wèn)題稱為無(wú)約束問(wèn)題，帶約束的問(wèn)題稱為約束問(wèn)題；若目標(biāo)函數(shù)，約束函數(shù)，都是線性函數(shù)，則稱為線性規(guī)劃；若其中存在非線性函數(shù)，則稱為非線性規(guī)劃；若變量只取整數(shù)，稱為整數(shù)規(guī)劃；若變量只取0，1，稱為01規(guī)劃。注：因，則最優(yōu)化問(wèn)題一般可寫成二、 最優(yōu)化問(wèn)題的分類§1.3 二維問(wèn)題的圖解法例1. 解：1. 由全部約束條件作圖，求出可行域R：凸多邊形OABC2. 作出一條目標(biāo)函數(shù)的等值線：設(shè)，作該直線即為一條目標(biāo)函數(shù)的等值線，并確定在可行域內(nèi)，這條等值線向哪個(gè)方向平移可使值增大。3. 平移目標(biāo)函數(shù)等值線，做圖求解最優(yōu)點(diǎn)，再算出最優(yōu)值。頂點(diǎn)是最優(yōu)點(diǎn)，即最優(yōu)

7、解，最優(yōu)值。分析： 線性規(guī)劃問(wèn)題解的幾種情況（1） 有唯一最優(yōu)解（上例）；（2） 有無(wú)窮多組最優(yōu)解：目標(biāo)函數(shù)改為（3） 無(wú)可行解：增加約束，則。（4） 無(wú)有限最優(yōu)解（無(wú)界解）：例 結(jié)論：（1）線性規(guī)劃問(wèn)題的可行域?yàn)橥辜厥馇闆r下為無(wú)界域或空集。（2）線性規(guī)劃問(wèn)題若有最優(yōu)解，一定可在其可行域的頂點(diǎn)上得到。例2. 解：目標(biāo)函數(shù)等值線：C為最優(yōu)點(diǎn)，得定義2：在三維及三維以上的空間中，使目標(biāo)函數(shù)取同一常數(shù)的點(diǎn)集稱為等值面。§1.4 預(yù)備知識(shí)（一） 線性代數(shù)一、 n維向量空間1. 向量的內(nèi)積：設(shè)，則內(nèi)積為2. 向量的范數(shù)（或長(zhǎng)度或模）：設(shè)，若實(shí)數(shù)具有以下性質(zhì)：（1）當(dāng)且僅當(dāng)時(shí)；（2）；（3）

8、.則稱為上的向量的范數(shù)，簡(jiǎn)記為。規(guī)定了向量范數(shù)的線性空間稱為線性賦范空間,記為.3. 常見的向量范數(shù)向量的范數(shù)：，三個(gè)重要的向量范數(shù)：，注：若無(wú)特殊說(shuō)明，本書中的指的是。4. 間的距離：5. 與正交：若非零向量組，的向量?jī)蓛烧?，稱它們是正交向量組。6. 標(biāo)準(zhǔn)正交基：，是n個(gè)正交的單位向量，即二、 特征值和特征向量定義：設(shè)為n階方陣，存在數(shù)和非零向量，使，則稱為矩陣的特征值，非零向量為矩陣屬于特征值的特征向量。三、 正定矩陣定義：設(shè)為n階實(shí)對(duì)稱方陣，若對(duì)任意非零向量，均有，則稱為正定二次型，為正定矩陣，記；若，半正定二次型，為半正定矩陣，記。類似有負(fù)定（半負(fù)定）二次型，負(fù)定（半負(fù)定）矩陣的概念

9、。性質(zhì)：實(shí)對(duì)稱方陣為正定矩陣（負(fù)）的特征值均為正（負(fù)）的各階順序主子式均為正（奇數(shù)階為負(fù)，偶數(shù)階為正）實(shí)對(duì)稱方陣為半正定矩陣的特征值均非負(fù)的各階順序主子式均為非負(fù)（二） 數(shù)學(xué)分析一、 梯度和海色（Hesse）矩陣1. 多元函數(shù)的可微性可微定義：設(shè)，若存在維向量，對(duì)，總有 （1）則稱函數(shù)在點(diǎn)處可微。式（1）等價(jià)于 （2）其中，是的高階無(wú)窮小。 定理1：（可微的必要條件）若函數(shù)在點(diǎn)處可微，則在該點(diǎn)關(guān)于各個(gè)變量的偏導(dǎo)數(shù)存在，且2. 梯度（1）概念梯度：令則稱為n元函數(shù)在處的梯度（或記為）。又稱為關(guān)于的一階導(dǎo)數(shù)。注：式（2）等價(jià)于 （3）等值面：在三維和三維以上的空間中，使目標(biāo)函數(shù)取同一數(shù)值的點(diǎn)集稱為

10、等值面（曲面）。方向?qū)?shù)：設(shè)在點(diǎn)處可微，向量，是方向上的單位向量，則極限稱為函數(shù)在點(diǎn)處沿方向的方向?qū)?shù)，記作。方向?qū)?shù)的幾何解釋：方向?qū)?shù)表示函數(shù)在點(diǎn)處沿方向的的變化率。函數(shù)的下降（上升）方向：設(shè)是連續(xù)函數(shù)，點(diǎn)，為一方向，若存在，對(duì)于，都有（）則稱方向是函數(shù)在點(diǎn)處的下降（上升）方向；結(jié)論1：若方向?qū)?shù)，則方向是在點(diǎn)處的下降方向；若方向?qū)?shù)，則方向是在點(diǎn)處的上升方向；（2）性質(zhì)【性質(zhì)1】：梯度為等值面在點(diǎn)處的切平面的法矢（向）量?！拘再|(zhì)2】：梯度方向是函數(shù)具有最大變化率的方向。定理2：設(shè)在點(diǎn)處可微，則方向?qū)?shù)其中，是方向上的單位向量，為梯度與的夾角。結(jié)論2：1）與梯度方向成銳角的方向是上升方向；

11、與梯度方向成鈍角的方向是下降方向；2）梯度方向是函數(shù)值上升最快的方向，稱為最速上升方向；負(fù)梯度方向是函數(shù)值下降最快的方向，稱為最速下降方向。（3）幾種特殊函數(shù)的梯度公式（1），為常數(shù)；（2），其中；（3）；（4）若是對(duì)稱方陣，則.例3. 泰勒（Taylor）公式與Hesse矩陣性質(zhì)1：設(shè)具有一階連續(xù)偏導(dǎo)數(shù)，則 （*）其中，即介于與之間。性質(zhì)2：設(shè)具有二階連續(xù)偏導(dǎo)數(shù)，則 （* ）其中為函數(shù)關(guān)于的二階導(dǎo)數(shù)，稱為的海色（Hesse）矩陣。結(jié)論1：當(dāng)時(shí)，（即海色矩陣對(duì)稱）。注1：1) 設(shè)向量函數(shù)時(shí)，稱為向量函數(shù)在點(diǎn)處的導(dǎo)數(shù)（梯度）。2) 向量函數(shù)在點(diǎn)處可微是指所有分量都在點(diǎn)處可微。關(guān)于向量函

12、數(shù)常見的梯度：（1），；（2），；（3）（4）設(shè)，其中，則，例：（三） 極小點(diǎn)的判定條件（求）一、 基本概念1. 點(diǎn)的鄰域：2. 局部極小點(diǎn)：設(shè). 若存在點(diǎn)和數(shù)，對(duì) 都有，則稱為在上的（非嚴(yán)格）局部極小點(diǎn)；若（），則稱為在上的嚴(yán)格局部極小點(diǎn)。3. 全局極小點(diǎn)：設(shè). 若存在點(diǎn)，對(duì)于 都有，則稱為在上的（非嚴(yán)格）全局極小點(diǎn)；若（），則稱為在上的嚴(yán)格全局極小點(diǎn)。 性質(zhì)：全局極小點(diǎn)必是局部極小點(diǎn)；但局部極小點(diǎn)不一定是全局極小點(diǎn)。類似有極大點(diǎn)的概念。因，本書主要給出極小問(wèn)題。4. 駐點(diǎn)：設(shè)可微，若，則稱點(diǎn)為的駐點(diǎn)或臨界點(diǎn)。 二、 極值的條件定理1（一階必要條件）設(shè)具有一階連續(xù)偏導(dǎo)數(shù)，是的內(nèi)點(diǎn)，若是的局部

13、極小點(diǎn)，則定理2（二階必要條件）設(shè)具有二階連續(xù)偏導(dǎo)數(shù)，若是的內(nèi)點(diǎn)且為的局部極小點(diǎn)，則是半正定的，即對(duì)恒有例定理3（二階充分條件）設(shè)具有二階連續(xù)偏導(dǎo)數(shù)，為的內(nèi)點(diǎn)，且，若正定，則為的嚴(yán)格局部極小點(diǎn)。（四）凸函數(shù)與凸規(guī)劃一、凸集1. 凸集的定義：一個(gè)n維向量空間的點(diǎn)集中任意兩點(diǎn)的連線仍屬于這個(gè)集合，即對(duì)，有則稱該點(diǎn)集為凸集。2. 凸集的性質(zhì)：（1）凸集的交集仍是凸集；（2）數(shù)乘凸集仍是凸集；（3）凸集的和集仍是凸集特別規(guī)定，空集是凸集。3. 超平面：設(shè)且，則集合稱為中的超平面，稱為該超平面的法向量，即；（是凸集）半空間：集合稱為中的一個(gè)半空間。超球：。4. 凸組合：設(shè)為中的個(gè)點(diǎn)，若存在且，使得則稱為

14、的凸組合。若均為正，則稱為嚴(yán)格凸組合。5. 頂點(diǎn)（或極點(diǎn)）：設(shè)是凸集，若不能用內(nèi)不同兩點(diǎn)和的凸組合表示，即，則稱為的頂點(diǎn)。二、凸函數(shù)1. 凸函數(shù)：設(shè)，是凸集，若對(duì)及，都有則稱為凸集上的凸函數(shù)；若則稱為凸集上的嚴(yán)格凸函數(shù)。類似有凹函數(shù)的定義。2.幾何意義：函數(shù)圖形上連接任意兩點(diǎn)的線段處處都在函數(shù)圖形的上方。3. 性質(zhì)性質(zhì)1：為凸集上的凸函數(shù)，則也為上的凸函數(shù)。性質(zhì)2：兩個(gè)凸函數(shù)的和仍是凸函數(shù)。推論1：凸集上有限個(gè)凸函數(shù)的非負(fù)線性組合仍為上的凸函數(shù)。性質(zhì)3：若為凸集上的凸函數(shù)，則對(duì)，的水平集是凸集。性質(zhì)4：為凸集上的凹函數(shù)為凸集上的凸函數(shù)。4. 凸函數(shù)的充分必要條件定理1（一階條件）設(shè)可微，是凸集

15、，則（1）為凸函數(shù)對(duì)，恒有（2）為嚴(yán)格凸函數(shù)對(duì)，恒有定理2（二階條件）設(shè)具有二階連續(xù)偏導(dǎo)數(shù)，為開凸集，則 （1）在內(nèi)為凸函數(shù)對(duì)，是半正定的；（2）若正定，則在內(nèi)為嚴(yán)格凸函數(shù)。特殊地，元二次函數(shù)為（為對(duì)稱矩陣）；若正定，則稱為正定二次函數(shù)。性質(zhì)：正定二次函數(shù)是嚴(yán)格凸函數(shù)。（因?yàn)椋?. 凸函數(shù)的極值定理3 設(shè)為凸集上的凸函數(shù)，則（1）的任一局部極小點(diǎn)為全局極小點(diǎn)；（2）若具有二階連續(xù)偏導(dǎo)數(shù)，且存在，使，則為在上的全局極小點(diǎn)；（3）若為嚴(yán)格凸函數(shù)，且全局極小點(diǎn)存在，則必唯一。特殊：對(duì)于正定二次函數(shù)，有，得唯一駐點(diǎn)為唯一的全局極小點(diǎn)。6. 凸規(guī)劃問(wèn)題：非空凸集上的凸函數(shù)的極小化問(wèn)題。考慮凸規(guī)劃問(wèn)題：，

16、 (1)s.t. 其中，為上的凹函數(shù)，為上的線性函數(shù)，為凸集，為上的凸函數(shù)。注：線性函數(shù)既可視為凸函數(shù)，又可視為凹函數(shù)。二次規(guī)劃： s.t. 其中，半正定或正定。 （五）下降迭代算法1. 下降迭代算法的步驟（1）選擇一個(gè)初始點(diǎn)，令k：=0（2）檢驗(yàn)是否最優(yōu)？若是，則停止迭代；若不是，則（3）確定一個(gè)下降方向：存在，對(duì)，使得（4）從點(diǎn)出發(fā)，沿方向進(jìn)行直線搜索（一維搜索），即求步長(zhǎng)使（5）計(jì)算，令k：=k+1，轉(zhuǎn)（2）2. 直線搜索及其性質(zhì)（1）簡(jiǎn)記： 表示從點(diǎn)出發(fā)，沿方向進(jìn)行直線搜索，得到極小點(diǎn)。（2）定理：設(shè)目標(biāo)函數(shù)具有一階連續(xù)偏導(dǎo)數(shù)，若，則證明：（反正法）設(shè)，則1），此時(shí)是點(diǎn)的下降方向；2）

17、，此時(shí)是點(diǎn)的下降方向；與矛盾。3. 收斂速度定義1：設(shè)序列是線性賦范空間中的點(diǎn)列，若則稱序列收斂于，記為。定義2：設(shè)向量函數(shù)，若當(dāng)時(shí)，總有，則稱在點(diǎn)連續(xù)；若在內(nèi)每一點(diǎn)都連續(xù)，則稱在內(nèi)連續(xù)。特別地，m=1時(shí)，為數(shù)量函數(shù)，則定義3：設(shè)序列收斂于，若存在與無(wú)關(guān)的數(shù)和，使得當(dāng)從某個(gè)開始，都有則稱序列收斂的階為，或?yàn)殡A收斂。當(dāng)，且時(shí)，稱線性收斂或一階收斂；當(dāng)時(shí)，稱二階收斂；當(dāng)時(shí)，稱超線性收斂。4. 計(jì)算終止準(zhǔn)則計(jì)算終止準(zhǔn)則根據(jù)相繼兩次迭代的結(jié)果a. 根據(jù)相繼兩次迭代的絕對(duì)誤差（不常用），b. 根據(jù)相繼兩次迭代的相對(duì)誤差，c. 根據(jù)目標(biāo)函數(shù)梯度的模足夠小為給定的足夠小的正數(shù)。以上準(zhǔn)則統(tǒng)稱為Himmelbl

18、au計(jì)算終止準(zhǔn)則，簡(jiǎn)稱H終止準(zhǔn)則。第二章 線性規(guī)劃§2.1 數(shù)學(xué)模型一、線性規(guī)劃的標(biāo)準(zhǔn)型1. 繁寫形式：s.t. 其中，（否則，等式兩端同乘以“-1”）。2. 縮寫形式：s.t. 3. 向量形式：s.t. 其中，。4. 矩陣形式：s.t. 其中，：約束條件的系數(shù)矩陣，一般地，；：限定向量，一般地，；：價(jià)值向量；：決策向量，；通常，為已知，未知。二、任一模型化為標(biāo)準(zhǔn)型1. 極大化目標(biāo)函數(shù)：令，則問(wèn)題轉(zhuǎn)化為2. 約束條件為不等式若約束為“”型，則“左端+松弛變量=右端”（松弛變量0）如：，引入松弛變量，化為若約束為“”型，則“左端-剩余變量=右端”（剩余變量0）如：，引入剩余變量，化為3

19、. 若存在無(wú)非負(fù)要求的變量（稱為自由變量）令，其中，代入目標(biāo)函數(shù)及約束條件即可。4. 某變量有上、下界若，即，令，有。用代替即可。若，即，令，有。用代替即可。例：§2.2 線性規(guī)劃解的性質(zhì)一、基本概念標(biāo)準(zhǔn)型（LP）： s.t. 可行解（容許解）：滿足約束（2）、（3）的解。最優(yōu)解：滿足（1）的容許解。基：設(shè)的秩為，若是中的階可逆矩陣，稱是線性規(guī)劃問(wèn)題（LP）的一個(gè)基?；蛄浚夯械囊涣校ǎ┘礊橐粋€(gè)基向量。（共個(gè)）非基向量：基之外的一列（）即為一個(gè)非基向量。（共個(gè)）基變量：與基向量相應(yīng)的變量。（共個(gè)）非基變量：與非基向量相應(yīng)的變量。（共個(gè)）基本解：令所有非基變量為0，求出的滿足約束（2

20、）的解?；救菰S解：滿足約束（3）的基本解。最優(yōu)基本容許解：滿足約束（1）的基本容許解。退化的基本解：若基本解中有基變量為0的基本解。退化的基本容許解：退化的最優(yōu)基本容許解：二、線性規(guī)劃問(wèn)題的基本定理定理1 若線性規(guī)劃問(wèn)題存在容許域，則其容許域是凸集。定理2 線性規(guī)劃問(wèn)題的基本容許解對(duì)應(yīng)于容許域的頂點(diǎn)。定理3 若線性規(guī)劃問(wèn)題存在有限最優(yōu)解，則其目標(biāo)函數(shù)最優(yōu)值一定可以在容許域的頂點(diǎn)達(dá)到。§2.3 單純形法一、單純形法原理單純形法的基本思路：根據(jù)問(wèn)題的標(biāo)準(zhǔn)型，從容許域的一個(gè)基本容許解（一個(gè)頂點(diǎn)）開始，轉(zhuǎn)移到另一個(gè)基本容許解（頂點(diǎn)），并且使目標(biāo)函數(shù)值逐步下降；當(dāng)目標(biāo)函數(shù)達(dá)到最小值時(shí)，問(wèn)題就

21、得到了最優(yōu)解。二、單純形法的步驟（以“大M法”為例）數(shù)學(xué)描述例（大M法）：s.t. 1. 構(gòu)造初始容許基初始容許基是一個(gè)單位矩陣，它相應(yīng)的基本解是容許的。1º引入附加變量，把數(shù)學(xué)模型化為標(biāo)準(zhǔn)型。2º若約束條件中附加變量系數(shù)為“-1”，或原約束即為等式，則一般須引入人工變量。3º目標(biāo)函數(shù)中，附加變量系數(shù)為0，而人工變量系數(shù)為M（很大的正數(shù)）。人工變量系數(shù)為大M：只要人工變量>0，使前后約束條件不等價(jià)，但由于目標(biāo)函數(shù)的修改，同時(shí)也使所求的目標(biāo)函數(shù)最小值是一個(gè)很大的數(shù)，也是對(duì)“篡改”約束條件的一種懲罰，因此，M叫做罰因子，大M法也叫做罰函數(shù)法。若對(duì)極大化問(wèn)題，目標(biāo)

22、函數(shù)中人工變量系數(shù)為（-M）。得到如下標(biāo)準(zhǔn)型：s.t. 其中，表示基變量；表示非基變量。2. 求出一個(gè)基本容許解1º用非基變量表示基變量和目標(biāo)函數(shù)。用非基變量表示基變量，即有用非基變量表示目標(biāo)函數(shù)，即其中，而稱為非基變量的檢驗(yàn)數(shù)。上式中，規(guī)定各基變量的檢驗(yàn)數(shù)為0。其中，是基變量的價(jià)值系數(shù)，隨基的改變而改變。2º求出一個(gè)基本容許解及相應(yīng)的目標(biāo)函數(shù)值。令非基變量=0即得初始基本容許解：，初始目標(biāo)函數(shù)值：3. 最優(yōu)性檢驗(yàn)1º檢驗(yàn)數(shù)：目標(biāo)函數(shù)式中，各非基變量的系數(shù)，即稱為各非基變量的檢驗(yàn)數(shù)。2º最優(yōu)解判別定理：若在極小化問(wèn)題中，對(duì)于某個(gè)基本容許解，所有檢驗(yàn)數(shù)，且人工變量為0，則該基本容許解是最優(yōu)解。3º無(wú)窮多最優(yōu)解判別定理：若在極小化問(wèn)題中，對(duì)于某個(gè)基本容許解，所有檢驗(yàn)數(shù)，又存在某個(gè)非基變量的檢驗(yàn)數(shù)為0，且人工變量為0，則該線性規(guī)劃問(wèn)題有無(wú)窮多最優(yōu)解。4º無(wú)容許解判別定理：若在極小化問(wèn)題中，對(duì)于某個(gè)基本容許解，所有檢驗(yàn)數(shù)，但人工變