數(shù)學(xué)建模教程 第一章 線性規(guī)劃

目錄線性規(guī)劃整數(shù)規(guī)劃非線性規(guī)劃動(dòng)態(tài)規(guī)劃圖與網(wǎng)絡(luò)初等數(shù)學(xué)方法建模變分法層次分析法差分法模糊數(shù)學(xué)Matlab教程第一章線性規(guī)劃§1線性規(guī)劃在人們的生產(chǎn)實(shí)踐中，經(jīng)常會(huì)遇到如何利用現(xiàn)有資源來安排生產(chǎn)，以取得最大經(jīng)濟(jì)效益的問題。此類問題構(gòu)成了運(yùn)籌學(xué)的一個(gè)重要分支—數(shù)學(xué)規(guī)劃，而線性規(guī)劃(LinearProgramming簡(jiǎn)記LP)則是數(shù)學(xué)規(guī)劃的一個(gè)重要分支。自從1947年G.B.Dantzig提出求解線性規(guī)劃的單純形方法以來，線性規(guī)劃在理論上趨向成熟，在實(shí)用中日益廣泛與深入。特別是在計(jì)算機(jī)能處理成千上萬個(gè)約束條件和決策變量的線性規(guī)劃問題之后，線性規(guī)劃的適用領(lǐng)域更為廣泛了，已成為現(xiàn)代管理中經(jīng)常采用的基本方法之一。1.1線性規(guī)劃的實(shí)例與定義例1某機(jī)床廠生產(chǎn)甲、乙兩種機(jī)床，每臺(tái)銷售后的利潤(rùn)分別為4000元與3000元。生產(chǎn)甲機(jī)床需用機(jī)器加工，加工時(shí)間分別為每臺(tái)2小時(shí)和1小時(shí)；生產(chǎn)乙機(jī)床需用三種機(jī)器加工，加工時(shí)間為每臺(tái)各一小時(shí)。若每天可用于加工的機(jī)器時(shí)數(shù)分別為機(jī)器10小時(shí)、機(jī)器8小時(shí)和機(jī)器7小時(shí)，問該廠應(yīng)生產(chǎn)甲、乙機(jī)床各幾臺(tái)，才能使總利潤(rùn)最大？上述問題的數(shù)學(xué)模型：設(shè)該廠生產(chǎn)臺(tái)甲機(jī)床和乙機(jī)床時(shí)總利潤(rùn)最大，則應(yīng)滿足（目標(biāo)函數(shù)）(1)s.t.（約束條件）（2）這里變量稱之為決策變量，（1）式被稱為問題的目標(biāo)函數(shù)，（2）中的幾個(gè)不等式是問題的約束條件，記為s.t.(即subjectto)。上述即為一規(guī)劃問題數(shù)學(xué)模型的三個(gè)要素。由于上面的目標(biāo)函數(shù)及約束條件均為線性函數(shù)，故被稱為線性規(guī)劃問題?？傊?，線性規(guī)劃問題是在一組線性約束條件的限制下，求一線性目標(biāo)函數(shù)最大或最小的問題。在解決實(shí)際問題時(shí)，把問題歸結(jié)成一個(gè)線性規(guī)劃數(shù)學(xué)模型是很重要的一步，但往往也是困難的一步，模型建立得是否恰當(dāng)，直接影響到求解。而選取適當(dāng)?shù)臎Q策變量，是我們建立有效模型的關(guān)鍵之一。線性規(guī)劃的Matlab標(biāo)準(zhǔn)形式線性規(guī)劃的目標(biāo)函數(shù)可以是求最大值，也可以是求最小值，約束條件的不等號(hào)可以是小于號(hào)也可以是大于號(hào)。為了避免這種形式多樣性帶來的不便，Matlab中規(guī)定線性規(guī)劃的標(biāo)準(zhǔn)形式為其中和為維列向量，為維列向量，為矩陣。例如線性規(guī)劃的Matlab標(biāo)準(zhǔn)型為1.3線性規(guī)劃問題的解的概念一般線性規(guī)劃問題的標(biāo)準(zhǔn)型為(3)(4)可行解滿足約束條件（4）的解，稱為線性規(guī)劃問題的可行解，而使目標(biāo)函數(shù)（3）達(dá)到最小值的可行解叫最優(yōu)解?？尚杏蛩锌尚薪鈽?gòu)成的集合稱為問題的可行域，記為。1.4線性規(guī)劃的圖解法圖解法簡(jiǎn)單直觀，有助于了解線性規(guī)劃問題求解的基本原理。我們先應(yīng)用圖解法來求解例1。如上圖所示，陰影區(qū)域即為L(zhǎng)P問題的可行域R。對(duì)于每一固定的值，使目標(biāo)函數(shù)值等于的點(diǎn)構(gòu)成的直線稱為目標(biāo)函數(shù)等位線，當(dāng)變動(dòng)時(shí)，我們得到一族平行直線。讓等位線沿目標(biāo)函數(shù)值減小的方向移動(dòng)，直到等位線與可行域有交點(diǎn)的最后位置，此時(shí)的交點(diǎn)（一個(gè)或多個(gè)）即為L(zhǎng)P的最優(yōu)解。對(duì)于例1，顯然等位線越趨于右上方，其上的點(diǎn)具有越大的目標(biāo)函數(shù)值。不難看出，本例的最優(yōu)解為，最優(yōu)目標(biāo)值。從上面的圖解過程可以看出并不難證明以下斷言：（1）可行域可能會(huì)出現(xiàn)多種情況?？赡苁强占部赡苁欠强占?，當(dāng)非空時(shí)，它必定是若干個(gè)半平面的交集（除非遇到空間維數(shù)的退化）。既可能是有界區(qū)域，也可能是無界區(qū)域。（2）在非空時(shí)，線性規(guī)劃既可以存在有限最優(yōu)解，也可以不存在有限最優(yōu)解（其目標(biāo)函數(shù)值無界）。（3）R非空且LP有有限最優(yōu)解時(shí)，最優(yōu)解可以唯一或有無窮多個(gè)。（4）若線性規(guī)劃存在有限最優(yōu)解，則必可找到具有最優(yōu)目標(biāo)函數(shù)值的可行域的“頂點(diǎn)”。上述論斷可以推廣到一般的線性規(guī)劃問題，區(qū)別只在于空間的維數(shù)。在一般的維空間中，滿足一線性等式的點(diǎn)集被稱為一個(gè)超平面，而滿足一線性不等式（或）的點(diǎn)集被稱為一個(gè)半空間（其中為一維行向量，為一實(shí)數(shù)）。有限個(gè)半空間的交集被稱為多胞形，有界的多胞形又被稱為多面體。易見，線性規(guī)劃的可行域必為多胞形（為統(tǒng)一起見，空集也被視為多胞形）。在一般維空間中，要直接得出多胞形“頂點(diǎn)”概念還有一些困難。二維空間中的頂點(diǎn)可以看成為邊界直線的交點(diǎn)，但這一幾何概念的推廣在一般維空間中的幾何意義并不十分直觀。為此，我們將采用另一途徑來定義它。定義1稱維空間中的區(qū)域?yàn)橐煌辜艏?，有。定義2設(shè)為維空間中的一個(gè)凸集，中的點(diǎn)被稱為的一個(gè)極點(diǎn)，若不存在及，使得。定義1說明凸集中任意兩點(diǎn)的連線必在此凸集中；而定義2說明，若是凸集的一個(gè)極點(diǎn)，則不能位于中任意兩點(diǎn)的連線上。不難證明，多胞形必為凸集。同樣也不難證明，二維空間中可行域的頂點(diǎn)均為的極點(diǎn)（也沒有其它的極點(diǎn)）。1.5求解線性規(guī)劃的Matlab解法單純形法是求解線性規(guī)劃問題的最常用、最有效的算法之一。單純形法是首先由GeorgeDantzig于1947年提出的，近60年來，雖有許多變形體已被開發(fā)，但卻保持著同樣的基本觀念。由于有如下結(jié)論：若線性規(guī)劃問題有有限最優(yōu)解，則一定有某個(gè)最優(yōu)解是可行區(qū)域的一個(gè)極點(diǎn)?；诖耍瑔渭冃畏ǖ幕舅悸肥牵合日页隹尚杏虻囊粋€(gè)極點(diǎn)，據(jù)一定規(guī)則判斷其是否最優(yōu)；若否，則轉(zhuǎn)換到與之相鄰的另一極點(diǎn)，并使目標(biāo)函數(shù)值更優(yōu)；如此下去，直到找到某一最優(yōu)解為止。這里我們不再詳細(xì)介紹單純形法，有興趣的讀者可以參看其它線性規(guī)劃書籍。下面我們介紹線性規(guī)劃的Matlab解法。Matlab5.3中線性規(guī)劃的標(biāo)準(zhǔn)型為基本函數(shù)形式為linprog(c,A,b)，它的返回值是向量的值。還有其它的一些函數(shù)調(diào)用形式（在Matlab指令窗運(yùn)行helplinprog可以看到所有的函數(shù)調(diào)用形式），如：[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)這里fval返回目標(biāo)函數(shù)的值，Aeq和beq對(duì)應(yīng)等式約束，LB和UB分別是變量的下界和上界，是的初始值，OPTIONS是控制參數(shù)。例2求解下列線性規(guī)劃問題解（=1\*romani）編寫M文件c=[2;3;-5];a=[-2,5,-1];b=-10;aeq=[1,1,1];beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1))value=c'*x（=2\*romanii）將M文件存盤，并命名為example1.m。（=3\*romaniii）在Matlab指令窗運(yùn)行example1即可得所求結(jié)果。求解線性規(guī)劃問題解編寫Matlab程序如下：c=[2;3;1];a=[1,4,2;3,2,0];b=[8;6];[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))1.6可以轉(zhuǎn)化為線性規(guī)劃的問題很多看起來不是線性規(guī)劃的問題也可以通過變換變成線性規(guī)劃問題來解決。如：?jiǎn)栴}為其中，和為相應(yīng)維數(shù)的矩陣和向量。要把上面的問題變換成線性規(guī)劃問題，只要注意到事實(shí)：對(duì)任意的，存在滿足，事實(shí)上，我們只要取，就可以滿足上面的條件。這樣，記，，從而我們可以把上面的問題變成§2運(yùn)輸問題(產(chǎn)銷平衡)例5某商品有個(gè)產(chǎn)地、個(gè)銷地，各產(chǎn)地的產(chǎn)量分別為，各銷地的需求量分別為。若該商品由產(chǎn)地運(yùn)到銷地的單位運(yùn)價(jià)為，問應(yīng)該如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最??？解：引入變量，其取值為由產(chǎn)地運(yùn)往銷地的該商品數(shù)量，數(shù)學(xué)模型為s.t.顯然是一個(gè)線性規(guī)劃問題，當(dāng)然可以用單純形法求解。對(duì)產(chǎn)銷平衡的運(yùn)輸問題，由于有以下關(guān)系式存在：其約束條件的系數(shù)矩陣相當(dāng)特殊，可用比較簡(jiǎn)單的計(jì)算方法，習(xí)慣上稱為表上作業(yè)法（由康托洛維奇和希奇柯克兩人獨(dú)立地提出，簡(jiǎn)稱康—希表上作業(yè)法）。表上作業(yè)法是單純形法在求解運(yùn)輸問題時(shí)的一種簡(jiǎn)化方法，其求解工作在運(yùn)輸表上進(jìn)行逐步迭代如下：先按某一規(guī)則找出一個(gè)初始解（初始調(diào)運(yùn)方案）；再對(duì)現(xiàn)行解作最優(yōu)性判斷；若這個(gè)解不是最優(yōu)的，就在運(yùn)輸表上對(duì)它進(jìn)行調(diào)整改進(jìn)，得一新解；再判斷，再改進(jìn)，直到得到最優(yōu)解?！?指派問題（又稱分配問題AssignmentProblem）3.1指派問題的數(shù)學(xué)模型例6擬分配人去干項(xiàng)工作，每人干且僅干一項(xiàng)工作，若分配第人去干第項(xiàng)工作，需花費(fèi)單位時(shí)間，問應(yīng)如何分配工作才能使工人花費(fèi)的總時(shí)間最少？容易看出，要給出一個(gè)指派問題的實(shí)例，只需給出矩陣，被稱為指派問題的系數(shù)矩陣。引入變量，若分配干工作，則取，否則取。上述指派問題的數(shù)學(xué)模型為s.t.(5)(5)的可行解既可以用一個(gè)矩陣(稱為解矩陣)表示，其每行每列均有且只有一個(gè)元素為1，其余元素均為0，也可以用中的一個(gè)置換表示。(5)的變量只能取0或1，從而是一個(gè)0-1規(guī)劃問題。一般的0-1規(guī)劃問題求解極為困難。但指派問題并不難解，其約束方程組的系數(shù)矩陣十分特殊（被稱為全單位模矩陣，其各階非零子式均為），其非負(fù)可行解的分量只能取0或1，故約束可改寫為而不改變其解。此時(shí)，指派問題被轉(zhuǎn)化為一個(gè)特殊的運(yùn)輸問題，其中，。3.2求解指派問題的匈牙利算法由于指派問題的特殊性，又存在著由匈牙利數(shù)學(xué)家D.Konig提出的更為簡(jiǎn)便的解法—匈牙利算法。算法主要依據(jù)以下事實(shí)：如果系數(shù)矩陣一行（或一列）中每一元素都加上或減去同一個(gè)數(shù)，得到一個(gè)新矩陣

，則以或?yàn)橄禂?shù)矩陣的指派問題具有相同的最優(yōu)指派。利用上述性質(zhì)，可將原系數(shù)陣C變換為含零元素較多的新系數(shù)陣B，而最優(yōu)解不變。若能在B中找出n個(gè)位于不同行不同列的零元素，令解矩陣中相應(yīng)位置的元素取值為1，其它元素取值為零，則所得該解是以B為系數(shù)陣的指派問題的最優(yōu)解，從而也是原問題的最優(yōu)解。由C到B的轉(zhuǎn)換可通過先讓矩陣C的每行元素均減去其所在行的最小元素得矩陣D，D的每列元素再減去其所在列的最小元素得以實(shí)現(xiàn)。下面通過一例子來說明該算法。例7求解指派問題，其系數(shù)矩陣為解將第一行元素減去此行中的最小元素15，同樣，第二行元素減去17，第三行元素減去17，最后一行的元素減去16，得再將第3列元素各減去1，得以為系數(shù)矩陣的指派問題有最優(yōu)指派由等價(jià)性，它也是例7的最優(yōu)指派。有時(shí)問題會(huì)稍復(fù)雜一些。例8求解系數(shù)矩陣的指派問題解：先作等價(jià)變換如下容易看出，從變換后的矩陣中只能選出四個(gè)位于不同行不同列的零元素，但，最優(yōu)指派還無法看出。此時(shí)等價(jià)變換還可進(jìn)行下去。步驟如下：對(duì)未選出0元素的行打；對(duì)行中0元素所在列打；對(duì)列中選中的0元素所在行打；重復(fù)（2）、（3）直到無法再打?yàn)橹??？梢宰C明，若用直線劃沒有打的行與打的列，就得到了能夠覆蓋住矩陣中所有零元素的最少條數(shù)的直線集合，找出未覆蓋的元素中的最小者，令行元素減去此數(shù)，列元素加上此數(shù)，則原先選中的0元素不變，而未覆蓋元素中至少有一個(gè)已轉(zhuǎn)變?yōu)?，且新矩陣的指派問題與原問題也等價(jià)。上述過程可反復(fù)采用，直到能選取出足夠的0元素為止。例如，對(duì)例5變換后的矩陣再變換，第三行、第五行元素減去2，第一列元素加上2，得現(xiàn)在已可看出，最優(yōu)指派為。§4對(duì)偶理論與靈敏度分析4.1原始問題和對(duì)偶問題考慮下列一對(duì)線性規(guī)劃模型：s.t.(P)和s.t.(D)稱（P）為原始問題，（D）為它的對(duì)偶問題。不太嚴(yán)謹(jǐn)?shù)卣f，對(duì)偶問題可被看作是原始問題的“行列轉(zhuǎn)置”：原始問題約束條件中的第列系數(shù)與其對(duì)偶問題約束條件中的第行的系數(shù)相同；原始目標(biāo)函數(shù)的系數(shù)行與其對(duì)偶問題右側(cè)的常數(shù)列相同；原始問題右側(cè)的常數(shù)列與其對(duì)偶目標(biāo)函數(shù)的系數(shù)行相同；在這一對(duì)問題中，除非負(fù)約束外的約束不等式方向和優(yōu)化方向相反。考慮線性規(guī)劃：把其中的等式約束變成不等式約束，可得它的對(duì)偶問題是其中和分別表示對(duì)應(yīng)于約束和的對(duì)偶變量組。令，則上式又可寫成原問題和對(duì)偶的對(duì)偶問題約束之間的關(guān)系：對(duì)偶問題的基本性質(zhì)1o對(duì)稱性：對(duì)偶問題的對(duì)偶是原問題。2o弱對(duì)偶性：若是原問題的可行解，是對(duì)偶問題的可行解。則恒有：。3o無界性：若原問題（對(duì)偶問題）為無界解，則其對(duì)偶問題（原問題）無可行解。4o可行解是最優(yōu)解時(shí)的性質(zhì)：設(shè)是原問題的可行解，是對(duì)偶問題的可行解，當(dāng)時(shí)，是最優(yōu)解。5o對(duì)偶定理：若原問題有有限最優(yōu)解，那么對(duì)偶問題也有最優(yōu)解；且目標(biāo)函數(shù)值相同。6o互補(bǔ)松弛性：若分別是原問題和對(duì)偶問題的最優(yōu)解，則由上述性質(zhì)可知，對(duì)任一LP問題(P)，若它的對(duì)偶問題(D)可能的話，我們總可以通過求解（D）來討論原問題（P）：若(D)無界，則(P)無可行解；若(D)有有限最優(yōu)解，最優(yōu)值，則利用互補(bǔ)松弛性可求得(P)的所有最優(yōu)解，且(P)的最優(yōu)值為。例如對(duì)只有兩個(gè)行約束的LP，其對(duì)偶問題只有兩個(gè)變量，總可用圖解法來求解。例9已知線性規(guī)劃問題已知其對(duì)偶問題的最優(yōu)解為，最優(yōu)值為。試用對(duì)偶理論找出原問題的最優(yōu)解。解先寫出它的對(duì)偶問題s.t.=1\*GB3① =2\*GB3②=3\*GB3③=4\*GB3④=5\*GB3⑤將的值代入約束條件，得=2\*GB3②，=3\*GB3③，=4\*GB3④為嚴(yán)格不等式；設(shè)原問題的最優(yōu)解為，由互補(bǔ)松弛性得。因；原問題的兩個(gè)約束條件應(yīng)取等式，故有求解后得到；故原問題的最優(yōu)解為；最優(yōu)值為。4.3靈敏度分析靈敏度分析是指對(duì)系統(tǒng)或周圍事物因周圍條件變化顯示出來的敏感程度的分析。在以前討論線性規(guī)劃問題時(shí)，假定都是常數(shù)。但實(shí)際上這些系數(shù)往往是估計(jì)值和預(yù)測(cè)值。如市場(chǎng)條件一變，值就會(huì)變化；往往是因工藝條件的改變而改變；是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決策選擇。因此提出這樣兩個(gè)問題：當(dāng)這些參數(shù)有一個(gè)或幾個(gè)發(fā)生變化時(shí)，已求得的線性規(guī)劃問題的最優(yōu)解會(huì)有什么變化；或者這些參數(shù)在什么范圍內(nèi)變化時(shí)，線性規(guī)劃問題的最優(yōu)解不變。這里我們就不討論了。參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃是研究這些參數(shù)中某一參數(shù)連續(xù)變化時(shí)，使最優(yōu)解發(fā)生變化的各臨界點(diǎn)的值。即把某一參數(shù)作為參變量，而目標(biāo)函數(shù)在某區(qū)間內(nèi)是這參變量的線性函數(shù)，含這參變量的約束條件是線性等式或不等式。因此仍可用單純形法和對(duì)偶單純形法進(jìn)行分析參數(shù)線性規(guī)劃問題。習(xí)題一1.某廠生產(chǎn)三種產(chǎn)品=1\*ROMANI，=2\*ROMANII，=3\*ROMANIII。每種產(chǎn)品要經(jīng)過兩道工序加工。設(shè)該廠有兩種規(guī)格的設(shè)備能完成工序，它們以表示；有三種規(guī)格的設(shè)備能完成工序，它們以表示。產(chǎn)品=1\*ROMANI可在任何一種規(guī)格設(shè)備上加工。產(chǎn)品=2\*ROMANII可在任何規(guī)格的設(shè)備上加工，但完成工序時(shí)，只能在設(shè)備上加工；產(chǎn)品=3\*ROMANIII只能在與設(shè)備上加工。已知在各種機(jī)床設(shè)備的單件工時(shí)，原材料費(fèi)，產(chǎn)品銷售價(jià)格，各種設(shè)備有效臺(tái)時(shí)以及滿負(fù)荷操作時(shí)機(jī)床設(shè)備的費(fèi)用如下表，要求安排最優(yōu)的生產(chǎn)計(jì)劃，使該廠利潤(rùn)最大。設(shè)備產(chǎn)品設(shè)備有效臺(tái)時(shí)滿負(fù)荷時(shí)的設(shè)備費(fèi)用(元)=1\*ROMANI=2\*ROMANII=3\*ROMANIII5764710981211600010000400070004000300321250783200原料費(fèi)(元/件)單價(jià)(元/件)0.251.250.352.000.502.802.有四個(gè)工人，要指派他們分別完成4項(xiàng)工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表：工作工人甲乙丙丁15192619182317212122162324181917問指派哪個(gè)人去完成哪項(xiàng)工作，可使總的消耗時(shí)間為最??？3.某戰(zhàn)略轟炸機(jī)群奉命摧毀敵人軍事目標(biāo)。已知該目標(biāo)有四個(gè)要害部位，只要摧毀其中之一即可達(dá)到目的。為完成此項(xiàng)任務(wù)的汽油消耗量限制為48000升、重型炸彈48枚、輕型炸彈32枚。飛機(jī)攜帶重型炸彈時(shí)每升汽油可飛行2千米，帶輕型炸彈時(shí)每升汽油可飛行3千米。又知每架飛機(jī)每次只能裝載一枚炸彈，每出發(fā)轟炸一次除來回路程汽油消耗（空載時(shí)每升汽油可飛行4千米）外，起飛和降落每次各消耗100升。有關(guān)數(shù)據(jù)如表所示。要害部位離機(jī)場(chǎng)距離（千米）摧毀可能性每枚重型彈每枚輕型彈12344504805406000.100.200.150.250.080.160.120.20為了使摧毀敵方軍事目標(biāo)的可能性最大，應(yīng)如何確定飛機(jī)轟炸的方案，要求建立這個(gè)問題的線性規(guī)劃模型。第二章整數(shù)規(guī)劃§1概論1.1定義規(guī)劃中的變量（部分或全部）限制為整數(shù)時(shí)，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。整數(shù)規(guī)劃的分類如不加特殊說明，一般指整數(shù)線性規(guī)劃。對(duì)于整數(shù)線性規(guī)劃模型大致可分為兩類：1o變量全限制為整數(shù)時(shí)，稱純（完全）整數(shù)規(guī)劃。2o變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。3o變量只能取0或1時(shí)，稱之為0-1整數(shù)規(guī)劃。整數(shù)規(guī)劃特點(diǎn)（=1\*romani）原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況：=1\*GB3①原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。=2\*GB3②整數(shù)規(guī)劃無可行解。例1原線性規(guī)劃為s.t.其最優(yōu)實(shí)數(shù)解為：。=3\*GB3③有可行解（當(dāng)然就存在最優(yōu)解），但最優(yōu)解值一定不會(huì)優(yōu)于原線性規(guī)劃的最優(yōu)值。例2原線性規(guī)劃為s.t.其最優(yōu)實(shí)數(shù)解為：。若限制整數(shù)得：。（=2\*romanii）整數(shù)規(guī)劃最優(yōu)解不能按照實(shí)數(shù)最優(yōu)解簡(jiǎn)單取整而獲得。1.3求解方法分類：（=1\*romani）分枝定界法—可求純或混合整數(shù)線性規(guī)劃。（=2\*romanii）割平面法—可求純或混合整數(shù)線性規(guī)劃。（=3\*romaniii）隱枚舉法—求解“0-1”整數(shù)規(guī)劃：=1\*GB3①過濾隱枚舉法；=2\*GB3②分枝隱枚舉法。（=4\*romaniv）匈牙利法—解決指派問題（“0-1”規(guī)劃特殊情形）。（=5\*romanv）蒙特卡洛法—求解各種類型規(guī)劃。下面將簡(jiǎn)要介紹常用的幾種求解整數(shù)規(guī)劃的方法?！?分枝定界法對(duì)有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）的可行解空間恰當(dāng)?shù)剡M(jìn)行系統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可行解空間反復(fù)地分割為越來越小的子集，稱為分枝；并且對(duì)每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(biāo)下界（對(duì)于最小值問題），這稱為定界。在每次分枝后，凡是界限不優(yōu)于已知可行解集目標(biāo)值的那些子集不再進(jìn)一步分枝，這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。分枝定界法可用于解純整數(shù)或混合的整數(shù)規(guī)劃問題。在二十世紀(jì)六十年代初由LandDoig和Dakin等人提出。由于這方法靈活且便于用計(jì)算機(jī)求解，所以現(xiàn)在它已是解整數(shù)規(guī)劃的重要方法。目前已成功地應(yīng)用于求解生產(chǎn)進(jìn)度問題、旅行推銷員問題、工廠選址問題、背包問題及分配問題等。設(shè)有最大化的整數(shù)規(guī)劃問題，與它相應(yīng)的線性規(guī)劃為問題，從解問題開始，若其最優(yōu)解不符合的整數(shù)條件，那么的最優(yōu)目標(biāo)函數(shù)必是的最優(yōu)目標(biāo)函數(shù)的上界，記作；而的任意可行解的目標(biāo)函數(shù)值將是的一個(gè)下界。分枝定界法就是將的可行域分成子區(qū)域再求其最大值的方法。逐步減小和增大，最終求到?，F(xiàn)用下例來說明：例3求解下述整數(shù)規(guī)劃s.t.解（=1\*romani）先不考慮整數(shù)限制，即解相應(yīng)的線性規(guī)劃，得最優(yōu)解為：可見它不符合整數(shù)條件。這時(shí)是問題的最優(yōu)目標(biāo)函數(shù)值的上界，記作。而顯然是問題的一個(gè)整數(shù)可行解，這時(shí)，是的一個(gè)下界，記作，即。（=2\*romanii）因?yàn)楫?dāng)前均為非整數(shù)，故不滿足整數(shù)要求，任選一個(gè)進(jìn)行分枝。設(shè)選進(jìn)行分枝，把可行集分成2個(gè)子集：，因?yàn)?與5之間無整數(shù)，故這兩個(gè)子集內(nèi)的整數(shù)解必與原可行集合整數(shù)解一致。這一步稱為分枝。這兩個(gè)子集的規(guī)劃及求解如下：?jiǎn)栴}：s.t.最優(yōu)解為：。問題：s.t.最優(yōu)解為：。再定界：。（=3\*romaniii）對(duì)問題再進(jìn)行分枝得問題和，它們的最優(yōu)解為再定界：，并將剪枝。（=4\*romaniv）對(duì)問題再進(jìn)行分枝得問題和，它們的最優(yōu)解為無可行解。將剪枝。于是可以斷定原問題的最優(yōu)解為：從以上解題過程可得用分枝定界法求解整數(shù)規(guī)劃（最大化）問題的步驟為：開始，將要求解的整數(shù)規(guī)劃問題稱為問題，將與它相應(yīng)的線性規(guī)劃問題稱為問題。（=1\*romani）解問題可能得到以下情況之一：（a）沒有可行解，這時(shí)也沒有可行解，則停止．（b）有最優(yōu)解，并符合問題的整數(shù)條件，的最優(yōu)解即為的最優(yōu)解，則停止。（c）有最優(yōu)解，但不符合問題的整數(shù)條件，記它的目標(biāo)函數(shù)值為。（=2\*romanii）用觀察法找問題的一個(gè)整數(shù)可行解，一般可取，試探，求得其目標(biāo)函數(shù)值，并記作。以表示問題的最優(yōu)目標(biāo)函數(shù)值；這時(shí)有進(jìn)行迭代。第一步：分枝，在的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量，其值為，以表示小于的最大整數(shù)。構(gòu)造兩個(gè)約束條件和將這兩個(gè)約束條件，分別加入問題，求兩個(gè)后繼規(guī)劃問題和。不考慮整數(shù)條件求解這兩個(gè)后繼問題。定界，以每個(gè)后繼問題為一分枝標(biāo)明求解的結(jié)果，與其它問題的解的結(jié)果中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界。從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值為最大者作為新的下界，若無作用。第二步：比較與剪枝，各分枝的最優(yōu)目標(biāo)函數(shù)中若有小于者，則剪掉這枝，即以后不再考慮了。若大于，且不符合整數(shù)條件，則重復(fù)第一步驟。一直到最后得到為止。得最優(yōu)整數(shù)解?！?型整數(shù)規(guī)劃型整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變量?jī)H取值0或1。這時(shí)稱為變量，或稱二進(jìn)制變量。僅取值0或1這個(gè)條件可由下述約束條件：，整數(shù)所代替，是和一般整數(shù)規(guī)劃的約束條件形式一致的。在實(shí)際問題中，如果引入變量，就可以把有各種情況需要分別討論的線性規(guī)劃問題統(tǒng)一在一個(gè)問題中討論了。我們先介紹引入變量的實(shí)際問題，再研究解法。3.1引入變量的實(shí)際問題3.1.1投資場(chǎng)所的選定——相互排斥的計(jì)劃例4某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個(gè)位置（點(diǎn)）可供選擇。規(guī)定在東區(qū)：由三個(gè)點(diǎn)中至多選兩個(gè)；在西區(qū)：由兩個(gè)點(diǎn)中至少選一個(gè)；在南區(qū)：由兩個(gè)點(diǎn)中至少選一個(gè)。如選用點(diǎn)，設(shè)備投資估計(jì)為元，每年可獲利潤(rùn)估計(jì)為元，但投資總額不能超過元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大？解題時(shí)先引入變量令.于是問題可列寫成：s.t.3.1.2相互排斥的約束條件①有兩個(gè)相互排斥的約束條件或。為了統(tǒng)一在一個(gè)問題中，引入變量，則上述約束條件可改寫為：其中是充分大的數(shù)。②約束條件或可改寫為③如果有個(gè)互相排斥的約束條件：為了保證這個(gè)約束條件只有一個(gè)起作用，我們引入個(gè)變量和一個(gè)充分大的常數(shù)，而下面這一組個(gè)約束條件（1）（2）就合于上述的要求。這是因?yàn)?，由于?），個(gè)中只有一個(gè)能取0值，設(shè)，代入（1），就只有的約束條件起作用，而別的式子都是多余的。3.1.3關(guān)于固定費(fèi)用的問題（FixedCostProblem）在討論線性規(guī)劃時(shí)，有些問題是要求使成本為最小。那時(shí)總設(shè)固定成本為常數(shù)，并在線性規(guī)劃的模型中不必明顯列出。但有些固定費(fèi)用（固定成本）的問題不能用一般線性規(guī)劃來描述，但可改變?yōu)榛旌险麛?shù)規(guī)劃來解決，見下例。例5某工廠為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定的生產(chǎn)方式投資高（選購自動(dòng)化程度高的設(shè)備），由于產(chǎn)量大，因而分配到每件產(chǎn)品的變動(dòng)成本就降低；反之，如選定的生產(chǎn)方式投資低，將來分配到每件產(chǎn)品的變動(dòng)成本可能增加。所以必須全面考慮。今設(shè)有三種方式可供選擇，令表示采用第種方式時(shí)的產(chǎn)量；表示采用第種方式時(shí)每件產(chǎn)品的變動(dòng)成本；表示采用第種方式時(shí)的固定成本。為了說明成本的特點(diǎn)，暫不考慮其它約束條件。采用各種生產(chǎn)方式的總成本分別為.在構(gòu)成目標(biāo)函數(shù)時(shí)，為了統(tǒng)一在一個(gè)問題中討論，現(xiàn)引入變量，令（3）于是目標(biāo)函數(shù)（3）式這個(gè)規(guī)定可表為下述3個(gè)線性約束條件：（4）其中是個(gè)充分大的常數(shù)。（4）式說明，當(dāng)時(shí)必須為1；當(dāng)時(shí)只有為0時(shí)才有意義，所以（4）式完全可以代替（3）式。3.2型整數(shù)規(guī)劃解法之一（過濾隱枚舉法）解型整數(shù)規(guī)劃最容易想到的方法，和一般整數(shù)規(guī)劃的情形一樣，就是窮舉法，即檢查變量取值為0或1的每一種組合，比較目標(biāo)函數(shù)值以求得最優(yōu)解，這就需要檢查變量取值的個(gè)組合。對(duì)于變量個(gè)數(shù)較大（例如），這幾乎是不可能的。因此常設(shè)計(jì)一些方法，只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解。這樣的方法稱為隱枚舉法（ImplicitEnumeration），分枝定界法也是一種隱枚舉法。當(dāng)然，對(duì)有些問題隱枚舉法并不適用，所以有時(shí)窮舉法還是必要的。下面舉例說明一種解型整數(shù)規(guī)劃的隱枚舉法。例6s.t.求解思路及改進(jìn)措施：（=1\*romani）先試探性求一個(gè)可行解，易看出滿足約束條件，故為一個(gè)可行解，且相應(yīng)的目標(biāo)函數(shù)值為。（=2\*romanii）因?yàn)槭乔髽O大值問題，故求最優(yōu)解時(shí)，凡是目標(biāo)值的解不必檢驗(yàn)是否滿足約束條件即可刪除，因它肯定不是最優(yōu)解，于是應(yīng)增加一個(gè)約束條件（目標(biāo)值下界）：，稱該條件為過濾條件(FilteringContraint)。從而原問題等價(jià)于：s.t.若用全部枚舉法，3個(gè)變量共有8種可能的組合，我們將這8種組合依次檢驗(yàn)它是否滿足條件(a)—(e)，對(duì)某個(gè)組合，若它不滿足(a)，即不滿足過濾條件，則(b)—(e)即可行性條件不必再檢驗(yàn)；若它滿足(a)—(e)且相應(yīng)的目標(biāo)值嚴(yán)格大于3，則進(jìn)行（=3\*romaniii）。（=3\*romaniii）改進(jìn)過濾條件。（=4\*romaniv）由于對(duì)每個(gè)組合首先計(jì)算目標(biāo)值以驗(yàn)證過濾條件，故應(yīng)優(yōu)先計(jì)算目標(biāo)值大的組合，這樣可提前抬高過濾門檻，以減少計(jì)算量。按上述思路與方法，例6的求解過程可由下表來表示：目標(biāo)值約束條件過濾條件abcde03√√√√√-25√√√√√18√√√√√63從而得最優(yōu)解，最優(yōu)值。§4蒙特卡洛法（隨機(jī)取樣法）前面介紹的常用的整數(shù)規(guī)劃求解方法，主要是針對(duì)線性整數(shù)規(guī)劃而言，而對(duì)于非線性整數(shù)規(guī)劃目前尚未有一種成熟而有效的求解方法，因?yàn)榉蔷€性規(guī)劃本身的通用有效解法尚未找到，更何況是非線性整數(shù)規(guī)劃。然而，盡管整數(shù)規(guī)劃由于限制變量為整數(shù)而增加了難度；然而又由于整數(shù)解是有限個(gè)，于是為枚舉法提供了方便。當(dāng)然，當(dāng)自變量維數(shù)很大和取值范圍很寬情況下，企圖用顯枚舉法（即窮舉法）計(jì)算出最優(yōu)值是不現(xiàn)實(shí)的，但是應(yīng)用概率理論可以證明，在一定的計(jì)算量的情況下，完全可以得出一個(gè)滿意解。例7已知非線性整數(shù)規(guī)劃為：s.t.對(duì)該題，目前尚無有效方法求出準(zhǔn)確解。如果用顯枚舉法試探，共需計(jì)算個(gè)點(diǎn)，其計(jì)算量非常之大。然而應(yīng)用蒙特卡洛去隨機(jī)計(jì)算個(gè)點(diǎn)，便可找到滿意解，那么這種方法的可信度究竟怎樣呢？下面就分析隨機(jī)取樣采集個(gè)點(diǎn)計(jì)算時(shí)，應(yīng)用概率理論來估計(jì)一下可信度。不失一般性，假定一個(gè)整數(shù)規(guī)劃的最優(yōu)點(diǎn)不是孤立的奇點(diǎn)。假設(shè)目標(biāo)函數(shù)落在高值區(qū)的概率分別為0.01，0.00001，則當(dāng)計(jì)算個(gè)點(diǎn)后，有任一個(gè)點(diǎn)能落在高值區(qū)的概率分別為，。解（=1\*romani）首先編寫M文件mente.m定義目標(biāo)函數(shù)f和約束向量函數(shù)g，程序如下：function[f,g]=mengte(x);f=x(1)^2+x(2)^2+3*x(3)^2+4*x(4)^2+2*x(5)-8*x(1)-2*x(2)-3*x(3)...-x(4)-2*x(5);g(1)=sum(x)-400;g(2)=x(1)+2*x(2)+2*x(3)+x(4)+6*x(5)-800;g(3)=2*x(1)+x(2)+6*x(3)-200;g(4)=x(3)+x(4)+5*x(5)-200;（=2\*romanii）編寫如下程序求問題的解：rand('state',sum(clock));p0=0;ticfori=1:10^5x=99*rand(5,1);x1=floor(x);x2=ceil(x);[f,g]=mengte(x1);ifsum(g<=0)==4ifp0<=fx0=x1;p0=f;endend[f,g]=mengte(x2);ifsum(g<=0)==4ifp0<=fx0=x2;p0=f;endendendx0,p0toc§5整數(shù)規(guī)劃的計(jì)算機(jī)解法整數(shù)規(guī)劃問題的求解可以使用Lingo等專用軟件。對(duì)于一般的整數(shù)規(guī)劃規(guī)劃問題，無法直接利用Matlab的函數(shù)，必須利用Matlab編程實(shí)現(xiàn)分枝定界解法和割平面解法。但對(duì)于指派問題等特殊的整數(shù)規(guī)劃問題或約束矩陣是幺模矩陣時(shí)，有時(shí)可以直接利用Matlab的函數(shù)linprog。例8求解下列指派問題，已知指派矩陣為解：編寫Matlab程序如下：c=[382103;87297;6427584235;9106910];c=c(:);a=zeros(10,25);fori=1:5a(i,(i-1)*5+1:5*i)=1;a(5+i,i:5:25)=1;endb=ones(10,1);[x,y]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1))求得最優(yōu)指派方案為，最優(yōu)值為21。習(xí)題二用分枝定界法解：s.t.2.試將下述非線性的規(guī)劃問題轉(zhuǎn)換成線性的規(guī)劃問題s.t.3.某鉆井隊(duì)要從以下10個(gè)可供選擇的井位中確定5個(gè)鉆井探油，使總的鉆探費(fèi)用為最小。若10個(gè)井位的代號(hào)為，相應(yīng)的鉆探費(fèi)用為，并且井位選擇上要滿足下列限制條件：或選擇和，或選擇鉆探；選擇了或就不能選，或反過來也一樣；在中最多只能選兩個(gè)；試建立這個(gè)問題的整數(shù)規(guī)劃模型。第三章非線性規(guī)劃§1非線性規(guī)劃1.1非線性規(guī)劃的實(shí)例與定義如果目標(biāo)函數(shù)或約束條件中包含非線性函數(shù)，就稱這種規(guī)劃問題為非線性規(guī)劃問題。一般說來，解非線性規(guī)劃要比解線性規(guī)劃問題困難得多。而且，也不象線性規(guī)劃有單純形法這一通用方法，非線性規(guī)劃目前還沒有適于各種問題的一般算法，各個(gè)方法都有自己特定的適用范圍。下面通過實(shí)例歸納出非線性規(guī)劃數(shù)學(xué)模型的一般形式，介紹有關(guān)非線性規(guī)劃的基本概念。例1（投資決策問題）某企業(yè)有個(gè)項(xiàng)目可供選擇投資，并且至少要對(duì)其中一個(gè)項(xiàng)目投資。已知該企業(yè)擁有總資金元，投資于第個(gè)項(xiàng)目需花資金元，并預(yù)計(jì)可收益元。試選擇最佳投資方案。解設(shè)投資決策變量為，，則投資總額為，投資總收益為。因?yàn)樵摴局辽僖獙?duì)一個(gè)項(xiàng)目投資，并且總的投資金額不能超過總資金，故有限制條件另外，由于只取值0或1，所以還有最佳投資方案應(yīng)是投資額最小而總收益最大的方案，所以這個(gè)最佳投資決策問題歸結(jié)為總資金以及決策變量（取0或1）的限制條件下，極大化總收益和總投資之比。因此，其數(shù)學(xué)模型為：s.t.上面例題是在一組等式或不等式的約束下，求一個(gè)函數(shù)的最大值（或最小值）問題，其中目標(biāo)函數(shù)或約束條件中至少有一個(gè)非線性函數(shù)，這類問題稱之為非線性規(guī)劃問題，簡(jiǎn)記為（NP）?？筛爬橐话阈问?NP)其中稱為模型（NP）的決策變量，稱為目標(biāo)函數(shù)，和稱為約束函數(shù)。另外，稱為等式約束，稱為不等式約束。對(duì)于一個(gè)實(shí)際問題，在把它歸結(jié)成非線性規(guī)劃問題時(shí)，一般要注意如下幾點(diǎn)：（=1\*romani）確定供選方案：首先要收集同問題有關(guān)的資料和數(shù)據(jù)，在全面熟悉問題的基礎(chǔ)上，確認(rèn)什么是問題的可供選擇的方案，并用一組變量來表示它們。（=2\*romanii）提出追求目標(biāo)：經(jīng)過資料分析，根據(jù)實(shí)際需要和可能，提出要追求極小化或極大化的目標(biāo)。并且，運(yùn)用各種科學(xué)和技術(shù)原理，把它表示成數(shù)學(xué)關(guān)系式。（=3\*romaniii）給出價(jià)值標(biāo)準(zhǔn)：在提出要追求的目標(biāo)之后，要確立所考慮目標(biāo)的“好”或“壞”的價(jià)值標(biāo)準(zhǔn)，并用某種數(shù)量形式來描述它。（=4\*romaniv）尋求限制條件：由于所追求的目標(biāo)一般都要在一定的條件下取得極小化或極大化效果，因此還需要尋找出問題的所有限制條件，這些條件通常用變量之間的一些不等式或等式來表示。1.2線性規(guī)劃與非線性規(guī)劃的區(qū)別如果線性規(guī)劃的最優(yōu)解存在，其最優(yōu)解只能在其可行域的邊界上達(dá)到（特別是可行域的頂點(diǎn)上達(dá)到）；而非線性規(guī)劃的最優(yōu)解（如果最優(yōu)解存在）則可能在其可行域的任意一點(diǎn)達(dá)到。1.3非線性規(guī)劃的Matlab解法Matlab中非線性規(guī)劃的數(shù)學(xué)模型寫成以下形式,其中是標(biāo)量函數(shù)，是相應(yīng)維數(shù)的矩陣和向量，是非線性向量函數(shù)。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)它的返回值是向量，其中FUN是用M文件定義的函數(shù)；X0是的初始值；A,B,Aeq,Beq定義了線性約束，如果沒有等式約束，則A=[],B=[],Aeq=[],Beq=[]；LB和UB是變量的下界和上界，如果上界和下界沒有約束，則LB=[]，UB=[]，如果無下界，則LB=-inf，如果無上界，則UB=inf；NONLCON是用M文件定義的非線性向量函數(shù)；OPTIONS定義了優(yōu)化參數(shù)，可以使用Matlab缺省的參數(shù)設(shè)置。例2求下列非線性規(guī)劃問題（=1\*romani）編寫M文件fun1.mfunctionf=fun1(x);f=x(1)^2+x(2)^2+8;和M文件fun2.mfunction[g,h]=fun2(x);g=-x(1)^2+x(2);h=-x(1)-x(2)^2+2;%等式約束（=2\*romanii）在Matlab的命令窗口依次輸入options=optimset;[x,y]=fmincon('fun1',rand(2,1),[],[],[],[],zeros(2,1),[],...'fun2',options)就可以求得當(dāng)時(shí)，最小值。1.4求解非線性規(guī)劃的基本迭代格式記（NP）的可行域?yàn)?。若，并且則稱是（NP）的整體最優(yōu)解，是(NP)的整體最優(yōu)值。如果有則稱是（NP）的嚴(yán)格整體最優(yōu)解，是(NP)的嚴(yán)格整體最優(yōu)值。若，并且存在的鄰域，使，則稱是（NP）的局部最優(yōu)解，是(NP)的局部最優(yōu)值。如果有則稱是（NP）的嚴(yán)格局部最優(yōu)解，是(NP)的嚴(yán)格局部最優(yōu)值。由于線性規(guī)劃的目標(biāo)函數(shù)為線性函數(shù)，可行域?yàn)橥辜蚨蟪龅淖顑?yōu)解就是整個(gè)可行域上的全局最優(yōu)解。非線性規(guī)劃卻不然，有時(shí)求出的某個(gè)解雖是一部分可行域上的極值點(diǎn)，但并不一定是整個(gè)可行域上的全局最優(yōu)解。對(duì)于非線性規(guī)劃模型(NP)，可以采用迭代方法求它的最優(yōu)解。迭代方法的基本思想是：從一個(gè)選定的初始點(diǎn)出發(fā)，按照某一特定的迭代規(guī)則產(chǎn)生一個(gè)點(diǎn)列，使得當(dāng)是有窮點(diǎn)列時(shí)，其最后一個(gè)點(diǎn)是(NP)的最優(yōu)解；當(dāng)是無窮點(diǎn)列時(shí)，它有極限點(diǎn)，并且其極限點(diǎn)是(NP)的最優(yōu)解。設(shè)是某迭代方法的第輪迭代點(diǎn)，是第輪迭代點(diǎn)，記（1）這里，顯然是由點(diǎn)與點(diǎn)確定的方向。式（1）就是求解非線性規(guī)劃模型(NP)的基本迭代格式。通常，我們把基本迭代格式（1）中的稱為第輪搜索方向，為沿方向的步長(zhǎng)，使用迭代方法求解(NP)的關(guān)鍵在于，如何構(gòu)造每一輪的搜索方向和確定適當(dāng)?shù)牟介L(zhǎng)。設(shè)，若存在，使，稱向量是在點(diǎn)處的下降方向。設(shè)，若存在，使，稱向量是點(diǎn)處關(guān)于的可行方向。一個(gè)向量，若既是函數(shù)在點(diǎn)處的下降方向，又是該點(diǎn)關(guān)于區(qū)域的可行方向，則稱之為函數(shù)在點(diǎn)處關(guān)于的可行下降方向。現(xiàn)在，我們給出用基本迭代格式（1）求解(NP)的一般步驟如下：0°選取初始點(diǎn)，令。1°構(gòu)造搜索方向，依照一定規(guī)則，構(gòu)造在點(diǎn)處關(guān)于的可行下降方向作為搜索方向。2°尋求搜索步長(zhǎng)。以為起點(diǎn)沿搜索方向?qū)で筮m當(dāng)?shù)牟介L(zhǎng)，使目標(biāo)函數(shù)值有某種意義的下降。3°求出下一個(gè)迭代點(diǎn)。按迭代格式（1）求出。若已滿足某種終止條件，停止迭代。4°以代替，回到1°步。1.5凸函數(shù)、凸規(guī)劃設(shè)為定義在維歐氏空間中某個(gè)凸集上的函數(shù)，若對(duì)任何實(shí)數(shù)以及中的任意兩點(diǎn)和，恒有則稱為定義在上的凸函數(shù)。若對(duì)每一個(gè)和恒有則稱為定義在上的嚴(yán)格凸函數(shù)?？紤]非線性規(guī)劃假定其中為凸函數(shù)，為凸函數(shù)，這樣的非線性規(guī)劃稱為凸規(guī)劃?？梢宰C明，凸規(guī)劃的可行域?yàn)橥辜?，其局部最?yōu)解即為全局最優(yōu)解，而且其最優(yōu)解的集合形成一個(gè)凸集。當(dāng)凸規(guī)劃的目標(biāo)函數(shù)為嚴(yán)格凸函數(shù)時(shí)，其最優(yōu)解必定唯一（假定最優(yōu)解存在）。由此可見，凸規(guī)劃是一類比較簡(jiǎn)單而又具有重要理論意義的非線性規(guī)劃?！?無約束問題2.1一維搜索方法當(dāng)用迭代法求函數(shù)的極小點(diǎn)時(shí)，常常用到一維搜索，即沿某一已知方向求目標(biāo)函數(shù)的極小點(diǎn)。一維搜索的方法很多，常用的有：（1）試探法（“成功—失敗”，斐波那契法，0.618法等）；插值法（拋物線插值法，三次插值法等）；（3）微積分中的求根法（切線法，二分法等）?？紤]一維極小化問題（2）若是區(qū)間上的下單峰函數(shù)，我們介紹通過不斷地縮短的長(zhǎng)度，來搜索得（2）的近似最優(yōu)解的兩個(gè)方法。為了縮短區(qū)間，逐步搜索得（2）的最優(yōu)解的近似值，我們可以采用以下途徑：在中任取兩個(gè)關(guān)于是對(duì)稱的點(diǎn)和（不妨設(shè)，并把它們叫做搜索點(diǎn)），計(jì)算和并比較它們的大小。對(duì)于單峰函數(shù)，若，則必有，因而是縮短了的單峰區(qū)間；若，則有，故是縮短了的單峰區(qū)間；若，則和都是縮短了的單峰。因此通過兩個(gè)搜索點(diǎn)處目標(biāo)函數(shù)值大小的比較，總可以獲得縮短了的單峰區(qū)間。對(duì)于新的單峰區(qū)間重復(fù)上述做法，顯然又可獲得更短的單峰區(qū)間。如此進(jìn)行，在單峰區(qū)間縮短到充分小時(shí)，我們可以取最后的搜索點(diǎn)作為（2）最優(yōu)解的近似值。應(yīng)該按照怎樣的規(guī)則來選取探索點(diǎn)，使給定的單峰區(qū)間的長(zhǎng)度能盡快地縮短？Fibonacci法若數(shù)列{}滿足關(guān)系：則稱為Fibonacci數(shù)列，稱為第個(gè)Fibonacci數(shù)，稱相鄰兩個(gè)Fibonacci數(shù)之比為Fibonacci分?jǐn)?shù)。當(dāng)用斐波那契法以個(gè)探索點(diǎn)來縮短某一區(qū)間時(shí)，區(qū)間長(zhǎng)度的第一次縮短率為，其后各次分別為。由此，若和是單峰區(qū)間中第1個(gè)和第2個(gè)探索點(diǎn)的話，那么應(yīng)有比例關(guān)系，從而，（3）它們關(guān)于確是對(duì)稱的點(diǎn)。如果要求經(jīng)過一系列探索點(diǎn)搜索之后，使最后的探索點(diǎn)和最優(yōu)解之間的距離不超過精度，這就要求最后區(qū)間的長(zhǎng)度不超過，即（4）據(jù)此，我們應(yīng)按照預(yù)先給定的精度，確定使（4）成立的最小整數(shù)作為搜索次數(shù)，直到進(jìn)行到第個(gè)探索點(diǎn)時(shí)停止。用上述不斷縮短函數(shù)的單峰區(qū)間的辦法，來求得問題（2）的近似解，是Kiefer(1953年)提出的，叫做Finbonacci法，具體步驟如下：1°選取初始數(shù)據(jù)，確定單峰區(qū)間，給出搜索精度，由（4）確定搜索次數(shù)。2°，計(jì)算最初兩個(gè)搜索點(diǎn)，按（3）計(jì)算和。3°whileifelseendend4°當(dāng)進(jìn)行至?xí)r，這就無法借比較函數(shù)值和的大小確定最終區(qū)間，為此，取其中為任意小的數(shù)。在和這兩點(diǎn)中，以函數(shù)值較小者為近似極小點(diǎn)，相應(yīng)的函數(shù)值為近似極小值。并得最終區(qū)間或。由上述分析可知，斐波那契法使用對(duì)稱搜索的方法，逐步縮短所考察的區(qū)間，它能以盡量少的函數(shù)求值次數(shù)，達(dá)到預(yù)定的某一縮短率。例3試用斐波那契法求函數(shù)的近似極小點(diǎn)，要求縮短后的區(qū)間不大于區(qū)間的0.08倍。程序留作習(xí)題。2.1.20.618法若，滿足比例關(guān)系稱之為黃金分割數(shù)，其值為。黃金分割數(shù)和Fibonacci分?jǐn)?shù)之間有著重要的關(guān)系，它們是1°，為偶數(shù)，，為奇數(shù)。2°?，F(xiàn)用不變的區(qū)間縮短率0.618，代替斐波那契法每次不同的縮短率，就得到了黃金分割法（0.618法）。這個(gè)方法可以看成是斐波那契法的近似，實(shí)現(xiàn)起來比較容易，效果也相當(dāng)好，因而易于為人們所接受。用0.618法求解，從第2個(gè)探索點(diǎn)開始每增加一個(gè)探索點(diǎn)作一輪迭代以后，原單峰區(qū)間要縮短0.618倍。計(jì)算個(gè)探索點(diǎn)的函數(shù)值可以把原區(qū)間連續(xù)縮短次，因?yàn)槊看蔚目s短率均為，故最后的區(qū)間長(zhǎng)度為這就是說，當(dāng)已知縮短的相對(duì)精度為時(shí)，可用下式計(jì)算探索點(diǎn)個(gè)數(shù)：當(dāng)然，也可以不預(yù)先計(jì)算探索點(diǎn)的數(shù)目，而在計(jì)算過程中逐次加以判斷，看是否已滿足了提出的精度要求。0.618法是一種等速對(duì)稱進(jìn)行試探的方法，每次的探索點(diǎn)均取在區(qū)間長(zhǎng)度的0.618倍和0.382倍處。2.2二次插值法對(duì)極小化問題（2），當(dāng)在上連續(xù)時(shí)，可以考慮用多項(xiàng)式插值來進(jìn)行一維搜索。它的基本思想是：在搜索區(qū)間中，不斷用低次（通常不超過三次）多項(xiàng)式來近似目標(biāo)函數(shù)，并逐步用插值多項(xiàng)式的極小點(diǎn)來逼近（2）的最優(yōu)解。

2.3無約束極值問題的解法無約束極值問題可表述為（5）求解問題（5）的迭代法大體上分為兩種：一是用到函數(shù)的一階導(dǎo)數(shù)或二階導(dǎo)數(shù)，稱為解析法。另一是僅用到函數(shù)值，稱為直接法。2.3.1解析法2.3.1.1梯度法（最速下降法）對(duì)基本迭代格式（6）我們總是考慮從點(diǎn)出發(fā)沿哪一個(gè)方向，使目標(biāo)函數(shù)下降得最快。微積分的知識(shí)告訴我們，點(diǎn)的負(fù)梯度方向，是從點(diǎn)出發(fā)使下降最快的方向。為此，稱負(fù)梯度方向?yàn)樵邳c(diǎn)處的最速下降方向。按基本迭代格式（6），每一輪從點(diǎn)出發(fā)沿最速下降方向作一維搜索，來建立求解無約束極值問題的方法，稱之為最速下降法。這個(gè)方法的特點(diǎn)是，每輪的搜索方向都是目標(biāo)函數(shù)在當(dāng)前點(diǎn)下降最快的方向。同時(shí)，用或作為停止條件。其具體步驟如下：1°選取初始數(shù)據(jù)。選取初始點(diǎn)，給定終止誤差，令。2°求梯度向量。計(jì)算，若，停止迭代，輸出。否則，進(jìn)行3°。3°構(gòu)造負(fù)梯度方向。取.4°進(jìn)行一維搜索。求，使得令轉(zhuǎn)2°。例4用最速下降法求解無約束非線性規(guī)劃問題其中，要求選取初始點(diǎn)，終止誤差。解：（=1\*romani）編寫M文件detaf.m如下function[f,df]=detaf(x);f=x(1)^2+25*x(2)^2;df(1)=2*x(1);df(2)=50*x(2);（=2\*romanii）編寫M文件zuisu.mclcx=[2;2];[f0,g]=detaf(x);whilenorm(g)>0.000001p=-g'/norm(g);t=1.0;f=detaf(x+t*p);whilef>f0t=t/2;f=detaf(x+t*p);endx=x+t*p[f0,g]=detaf(x)end2.3.1.2Newton法考慮目標(biāo)函數(shù)在點(diǎn)處的二次逼近式假定Hesse陣正定。由于正定，函數(shù)的穩(wěn)定點(diǎn)是的最小點(diǎn)。為求此最小點(diǎn)，令，即可解得.對(duì)照基本迭代格式（1），可知從點(diǎn)出發(fā)沿搜索方向。并取步長(zhǎng)即可得的最小點(diǎn)。通常，把方向叫做從點(diǎn)出發(fā)的Newton方向。從一初始點(diǎn)開始，每一輪從當(dāng)前迭代點(diǎn)出發(fā)，沿Newton方向并取步長(zhǎng)為1的求解方法，稱之為Newton法。其具體步驟如下：1°選取初始數(shù)據(jù)。選取初始點(diǎn)，給定終止誤差，令。2°求梯度向量。計(jì)算，若，停止迭代，輸出。否則，進(jìn)行3°。3°構(gòu)造Newton方向。計(jì)算，取.4°求下一迭代點(diǎn)。令，轉(zhuǎn)2°。例5用Newton法求解，選取，。解：（=1\*romani）編寫M文件nwfun.m如下：function[f,df,d2f]=nwfun(x);f=x(1)^4+25*x(2)^4+x(1)^2*x(2)^2;df(1)=4*x(1)^3+2*x(1)*x(2)^2;df(2)=100*x(2)^3+2*x(1)^2*x(2);d2f(1,1)=12*x(1)^2+2*x(2)^2;d2f(1,2)=4*x(1)*x(2);d2f(2,1)=d2f(1,2);d2f(2,2)=300*x(2)^2+4*x(1)*x(2);（=2\*romanii）編寫M文件：clcx=[2;2];[f0,g1,g2]=nwfun(x)whilenorm(g1)>0.00001%deadloop,fori=1:3p=-inv(g2)*g1',p=p/norm(p)t=1.0,f=detaf(x+t*p)whilef>f0t=t/2,f=detaf(x+t*p),endx=x+t*p[f0,g1,g2]=nwfun(x)end如果目標(biāo)函數(shù)是非二次函數(shù)，一般地說，用Newton法通過有限輪迭代并不能保證可求得其最優(yōu)解。Newton法的優(yōu)點(diǎn)是收斂速度快；缺點(diǎn)是有時(shí)不好用而需采取改進(jìn)措施，此外，當(dāng)維數(shù)較高時(shí)，計(jì)算的工作量很大。2.3.1.3變尺度法變尺度法（VariableMetricAlgorithm）是近20多年來發(fā)展起來的，它不僅是求解無約束極值問題非常有效的算法，而且也已被推廣用來求解約束極值問題。由于它既避免了計(jì)算二階導(dǎo)數(shù)矩陣及其求逆過程，又比梯度法的收斂速度快，特別是對(duì)高維問題具有顯著的優(yōu)越性，因而使變尺度法獲得了很高的聲譽(yù)。下面我們就來簡(jiǎn)要地介紹一種變尺度法—DFP法的基本原理及其計(jì)算過程。這一方法首先由Davidon在1959年提出，后經(jīng)Fletcher和Powell加以改進(jìn)。我們已經(jīng)知道，牛頓法的搜索方向是，為了不計(jì)算二階導(dǎo)數(shù)矩陣及其逆陣，我們?cè)O(shè)法構(gòu)造另一個(gè)矩陣，用它來逼近二階導(dǎo)數(shù)矩陣的逆陣，這一類方法也稱擬牛頓法（Quasi-NewtonMethod）。下面研究如何構(gòu)造這樣的近似矩陣，并將它記為。我們要求：每一步都能以現(xiàn)有的信息來確定下一個(gè)搜索方向；每做一次選代，目標(biāo)函數(shù)值均有所下降；這些近似矩陣最后應(yīng)收斂于解點(diǎn)處的Hesse陣的逆陣。當(dāng)是二次函數(shù)時(shí)，其Hesse陣為常數(shù)陣，任兩點(diǎn)和處的梯度之差為或?qū)τ诜嵌魏瘮?shù)，仿照二次函數(shù)的情形，要求其Hesse陣的逆陣的第次近似矩陣滿足關(guān)系式（7）這就是常說的擬Newton條件。若令（8）則式（7）變?yōu)椋?）現(xiàn)假定已知，用下式求（設(shè)和均為對(duì)稱正定陣）；（10）其中稱為第次校正矩陣。顯然，應(yīng)滿足擬Newton條件（9），即要求或（11）由此可以設(shè)想，的一種比較簡(jiǎn)單的形式是(12)其中和為兩個(gè)待定列向量。將式（12）中的代入（11），得這說明，應(yīng)使（13）考慮到應(yīng)為對(duì)稱陣，最簡(jiǎn)單的辦法就是?。?4）由式（13）得（15）若和不等于零，則有（16）于是，得校正矩陣(17)從而得到（18）上述矩陣稱為尺度矩陣。通常，我們?nèi)〉谝粋€(gè)尺度矩陣為單位陣，以后的尺度矩陣按式（18）逐步形成?？梢宰C明：（=1\*romani）當(dāng)不是極小點(diǎn)且正定時(shí)，式（17）右端兩項(xiàng)的分母不為零，從而可按式（18）產(chǎn)生下一個(gè)尺度矩陣；（=2\*romanii）若為對(duì)稱正定陣，則由式（18）產(chǎn)生的也是對(duì)稱正定陣；（=3\*romaniii）由此推出DFP法的搜索方向?yàn)橄陆捣较颉，F(xiàn)將DFP變尺度法的計(jì)算步驟總結(jié)如下。1°給定初始點(diǎn)及梯度允許誤差。2°若，則即為近似極小點(diǎn)，停止迭代，否則，轉(zhuǎn)向下一步。3°令（單位矩陣），在方向進(jìn)行一維搜索，確定最佳步長(zhǎng)：如此可得下一個(gè)近似點(diǎn)4°一般地，設(shè)已得到近似點(diǎn)，算出，若則即為所求的近似解，停止迭代；否則，計(jì)算：并令，在方向上進(jìn)行一維搜索，得，從而可得下一個(gè)近似點(diǎn)5°若滿足精度要求，則即為所求的近似解，否則，轉(zhuǎn)回4°，直到求出某點(diǎn)滿足精度要求為止。2.3.2直接法在無約束非線性規(guī)劃方法中，遇到問題的目標(biāo)函數(shù)不可導(dǎo)或?qū)Ш瘮?shù)的解析式難以表示時(shí)，人們一般需要使用直接搜索方法。同時(shí)，由于這些方法一般都比較直觀和易于理解，因而在實(shí)際應(yīng)用中常為人們所采用。下面我們介紹Powell方法。這個(gè)方法主要由所謂基本搜索、加速搜索和調(diào)整搜索方向三部分組成，具體步驟如下：1°選取初始數(shù)據(jù)。選取初始點(diǎn)，個(gè)線性無關(guān)初始方向，組成初搜索方向組。給定終止誤差，令。2°進(jìn)行基本搜索。令，依次沿中的方向進(jìn)行一維搜索。對(duì)應(yīng)地得到輔助迭代點(diǎn)，即3°構(gòu)造加速方向。令，若，停止迭代，輸出。否則進(jìn)行4°。4°確定調(diào)整方向。按下式找出。若成立，進(jìn)行5°。否則，進(jìn)行6°。5°調(diào)整搜索方向組。令.同時(shí)，令，，轉(zhuǎn)2°。6°不調(diào)整搜索方向組。令，轉(zhuǎn)2°。2.4Matlab求函數(shù)的極小值和函數(shù)的零點(diǎn)2.4.1求單變量有界非線性函數(shù)在區(qū)間上的極小值Matlab的命令為[X,FVAL]=FMINBND(FUN,x1,x2,OPTIONS)，它的返回值是極小點(diǎn)和函數(shù)的極小值。這里fun是用M文件定義的函數(shù)或Matlab中的單變量數(shù)學(xué)函數(shù)。例6求函數(shù)的最小值。解編寫M文件fun1.mfunctionf=fun1(x);f=(x-3)^2-1;在Matlab的命令窗口輸入[x,y]=fminbnd('fun1',0,5)即可求得極小點(diǎn)和極小值。求多變量函數(shù)的極小值其中是一個(gè)向量，是一個(gè)標(biāo)量函數(shù)。Matlab中的基本命令是[X,FVAL]=FMINUNC(FUN,X0,OPTIONS,P1,P2,...)它的返回值是向量的值和函數(shù)的極小值。FUN是一個(gè)M文件，當(dāng)FUN只有一個(gè)返回值時(shí)，它的返回值是函數(shù)；當(dāng)FUN有兩個(gè)返回值時(shí)，它的第二個(gè)返回值是的一階導(dǎo)數(shù)行向量；當(dāng)FUN有三個(gè)返回值時(shí)，它的第三個(gè)返回值是的二階導(dǎo)數(shù)陣（Hessian陣）。X0是向量的初始值，OPTIONS是優(yōu)化參數(shù)，使用確省參數(shù)時(shí)，OPTIONS為空矩陣。P1，P2是可以傳遞給FUN的一些參數(shù)。例7求函數(shù)的最小值。解：編寫M文件fun2.m如下：function[f,g]=fun2(x);f=100*(x(2)-x(1)^2)^2+(1-x(1))^2;g=[-400*x(1)*(x(2)-x(1)^2)-2(1-x(1))200*(x(2)-x(1)^2)];在Matlab命令窗口輸入fminunc('fun2',rand(1,2))即可求得函數(shù)的極小值。求多元函數(shù)的極值也可以使用Matlab的命令[X,FVAL]=FMINSEARCH(FUN,X0,OPTIONS,P1,P2,...)?！?約束極值問題帶有約束條件的極值問題稱為約束極值問題，也叫約束規(guī)劃問題。求解約束極值問題要比求解無約束極值問題困難得多。為了簡(jiǎn)化其優(yōu)化工作，可采用以下方法：將約束問題化為無約束問題；將非線性規(guī)劃問題化為線性規(guī)劃問題，以及能將復(fù)雜問題變換為較簡(jiǎn)單問題的其它方法。最優(yōu)性條件庫恩—塔克條件是非線性規(guī)劃領(lǐng)域中最重要的理論成果之一，是確定某點(diǎn)為最優(yōu)點(diǎn)的必要條件，但一般說它并不是充分條件（對(duì)于凸規(guī)劃，它既是最優(yōu)點(diǎn)存在的必要條件，同時(shí)也是充分條件）。二次規(guī)劃若某非線性規(guī)劃的目標(biāo)函數(shù)為自變量的二次函數(shù)，約束條件又全是線性的，就稱這種規(guī)劃為二次規(guī)劃。Matlab中二次規(guī)劃的數(shù)學(xué)模型可表述如下：這里是實(shí)對(duì)稱矩陣，是列向量，是相應(yīng)維數(shù)的矩陣。Matlab中求解二次規(guī)劃的命令是[X,FVAL]=QUADPROG(H,f,A,b,Aeq,beq,LB,UB,X0,OPTIONS)X的返回值是向量，F(xiàn)VAL的返回值是目標(biāo)函數(shù)在X處的值。（具體細(xì)節(jié)可以參看在Matlab指令中運(yùn)行helpquadprog后的幫助）。例8求解二次規(guī)劃解編寫如下程序：h=[4,-4;-4,8];f=[-6;-3];a=[1,1;4,1];b=[3;9];[x,value]=quadprog(h,f,a,b,[],[],zeros(2,1))求得。罰函數(shù)法利用罰函數(shù)法，可將非線性規(guī)劃問題的求解，轉(zhuǎn)化為求解一系列無約束極值問題，因而也稱這種方法為序列無約束最小化技術(shù)，簡(jiǎn)記為

SUMT(SequentialUnconstrainedMinimizationTechnique)。罰函數(shù)法求解非線性規(guī)劃問題的思想是，利用問題中的約束函數(shù)作出適當(dāng)?shù)牧P函數(shù)，由此構(gòu)造出帶參數(shù)的增廣目標(biāo)函數(shù)，把問題轉(zhuǎn)化為無約束非線性規(guī)劃問題。主要有兩種形式，一種叫外罰函數(shù)法，另一種叫內(nèi)罰函數(shù)法，下面介紹外罰函數(shù)法。考慮如下問題：s.t.取一個(gè)充分大的數(shù)，構(gòu)造函數(shù)（或這里，，，為適當(dāng)?shù)男邢蛄浚琈atlab中可以直接利用和函數(shù)。）則以增廣目標(biāo)函數(shù)為目標(biāo)函數(shù)的無約束極值問題的最優(yōu)解也是原問題的最優(yōu)解。例9求下列非線性規(guī)劃解(=1\*romani)編寫M文件test.mfunctiong=test(x);M=50000;f=x(1)^2+x(2)^2+8;g=f-M*min(x(1),0)-M*min(x(2),0)-M*min(x(1)^2-x(2),0)...+M*abs(-x(1)-x(2)^2+2);(=2\*romanii)在Matlab命令窗口輸入[x,y]=fminunc('test',rand(2,1))即可求得問題的解。§4飛行管理問題在約10，000m高空的某邊長(zhǎng)160km的正方形區(qū)域內(nèi)，經(jīng)常有若干架飛機(jī)作水平飛行。區(qū)域內(nèi)每架飛機(jī)的位置和速度向量均由計(jì)算機(jī)記錄其數(shù)據(jù)，以便進(jìn)行飛行管理。當(dāng)一架欲進(jìn)入該區(qū)域的飛機(jī)到達(dá)區(qū)域邊緣時(shí)，記錄其數(shù)據(jù)后，要立即計(jì)算并判斷是否會(huì)與區(qū)域內(nèi)的飛機(jī)發(fā)生碰撞。如果會(huì)碰撞，則應(yīng)計(jì)算如何調(diào)整各架（包括新進(jìn)入的）飛機(jī)飛行的方向角，以避免碰撞?，F(xiàn)假定條件如下：1）不碰撞的標(biāo)準(zhǔn)為任意兩架飛機(jī)的距離大于8km;2）飛機(jī)飛行方向角調(diào)整的幅度不應(yīng)超過30度；3）所有飛機(jī)飛行速度均為每小時(shí)800km;4）進(jìn)入該區(qū)域的飛機(jī)在到達(dá)區(qū)域邊緣時(shí)，與區(qū)域內(nèi)飛機(jī)的距離應(yīng)在60km以上；5）最多需考慮6架飛機(jī)；6）不必考慮飛機(jī)離開此區(qū)域后的狀況。請(qǐng)你對(duì)這個(gè)避免碰撞的飛行管理問題建立數(shù)學(xué)模型，列出計(jì)算步驟，對(duì)以下數(shù)據(jù)進(jìn)行計(jì)算（方向角誤差不超過0.01度），要求飛機(jī)飛行方向角調(diào)整的幅度盡量小。設(shè)該區(qū)域4個(gè)頂點(diǎn)的座標(biāo)為(0,0)，(160,0)，(160,160)，(0,160)。記錄數(shù)據(jù)為：飛機(jī)編號(hào)橫座標(biāo)縱座標(biāo)方向角（度）1150140243285852363150155220.54145501595130150230新進(jìn)入0052注：方向角指飛行方向與軸正向的夾角。試根據(jù)實(shí)際應(yīng)用背景對(duì)你的模型進(jìn)行評(píng)價(jià)與推廣。提示：，，其中為飛機(jī)的總架數(shù)，為時(shí)刻第架飛機(jī)的坐標(biāo)，分別表示第架飛機(jī)飛出正方形區(qū)域邊界的時(shí)刻。這里，，；，，；其中為飛機(jī)的速度，分別為第架飛機(jī)的初始方向角和調(diào)整后的方向角。令其中，則兩架飛機(jī)不碰撞的條件是。習(xí)題三1.用Matlab的非線性規(guī)劃命令fmincon求解飛行管理問題。2.用罰函數(shù)法求解飛行管理問題。3.某工廠向用戶提供發(fā)動(dòng)機(jī)，按合同規(guī)定，其交貨數(shù)量和日期是：第一季度末交40臺(tái)，第二季末交60臺(tái)，第三季末交80臺(tái)。工廠的最大生產(chǎn)能力為每季100臺(tái)，每季的生產(chǎn)費(fèi)用是（元），此處為該季生產(chǎn)發(fā)動(dòng)機(jī)的臺(tái)數(shù)。若工廠生產(chǎn)的多，多余的發(fā)動(dòng)機(jī)可移到下季向用戶交貨，這樣，工廠就需支付存貯費(fèi)，每臺(tái)發(fā)動(dòng)機(jī)每季的存貯費(fèi)為4元。問該廠每季應(yīng)生產(chǎn)多少臺(tái)發(fā)動(dòng)機(jī)，才能既滿足交貨合同，又使工廠所花費(fèi)的費(fèi)用最少（假定第一季度開始時(shí)發(fā)動(dòng)機(jī)無存貨）。第四章動(dòng)態(tài)規(guī)劃§1引言1.1動(dòng)態(tài)規(guī)劃的發(fā)展及研究?jī)?nèi)容動(dòng)態(tài)規(guī)劃（dynamicprogramming）是運(yùn)籌學(xué)的一個(gè)分支，是求解多階段決策問題的最優(yōu)化方法。20世紀(jì)50年代初R.E.Bellman等人在研究多階段決策過程(multistepdecisionprocess)的優(yōu)化問題時(shí)，提出了著名的最優(yōu)性原理（principleofoptimality），把多階段過程轉(zhuǎn)化為一系列單階段問題，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法—?jiǎng)討B(tài)規(guī)劃。1957年出版了他的名著《DynamicProgramming》，這是該領(lǐng)域的第一本著作。動(dòng)態(tài)規(guī)劃問世以來，在經(jīng)濟(jì)管理、生產(chǎn)調(diào)度、工程技術(shù)和最優(yōu)控制等方面得到了廣泛的應(yīng)用。例如最短路線、庫存管理、資源分配、設(shè)備更新、排序、裝載等問題，用動(dòng)態(tài)規(guī)劃方法比用其它方法求解更為方便。雖然動(dòng)態(tài)規(guī)劃主要用于求解以時(shí)間劃分階段的動(dòng)態(tài)過程的優(yōu)化問題，但是一些與時(shí)間無關(guān)的靜態(tài)規(guī)劃（如線性規(guī)劃、非線性規(guī)劃），只要人為地引進(jìn)時(shí)間因素，把它視為多階段決策過程，也可以用動(dòng)態(tài)規(guī)劃方法方便地求解。應(yīng)指出，動(dòng)態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種特殊算法（如線性規(guī)劃是一種算法）。因而，它不象線性規(guī)劃那樣有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確定義的一組規(guī)則，而必須對(duì)具體問題進(jìn)行具體分析處理。因此，在學(xué)習(xí)時(shí)，除了要對(duì)基本概念和方法正確理解外，應(yīng)以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。例1最短路線問題下面是一個(gè)線路網(wǎng)，連線上的數(shù)字表示兩點(diǎn)之間的距離（或費(fèi)用）。試尋求一條由到距離最短（或費(fèi)用最?。┑穆肪€。例2生產(chǎn)計(jì)劃問題工廠生產(chǎn)某種產(chǎn)品，每單位（千件）的成本為1（千元），每次開工的固定成本為3（千元），工廠每季度的最大生產(chǎn)能力為6（千件）。經(jīng)調(diào)查，市場(chǎng)對(duì)該產(chǎn)品的需求量第一、二、三、四季度分別為2，3，2，4（千件）。如果工廠在第一、二季度將全年的需求都生產(chǎn)出來，自然可以降低成本（少付固定成本費(fèi)），但是對(duì)于第三、四季度才能上市的產(chǎn)品需付存儲(chǔ)費(fèi)，每季每千件的存儲(chǔ)費(fèi)為0.5（千元）。還規(guī)定年初和年末這種產(chǎn)品均無庫存。試制定一個(gè)生產(chǎn)計(jì)劃，即安排每個(gè)季度的產(chǎn)量，使一年的總費(fèi)用（生產(chǎn)成本和存儲(chǔ)費(fèi)）最少。1.2決策過程的分類根據(jù)過程的時(shí)間變量是離散的還是連續(xù)的，分為離散時(shí)間決策過程（discrete-timedecisionprocess）和連續(xù)時(shí)間決策過程（continuous-timedecisionprocess）；根據(jù)過程的演變是確定的還是隨機(jī)的，分為確定性決策過程（deterministicdecisionprocess）和隨機(jī)性決策過程（stochasticdecisionprocess），其中應(yīng)用最廣的是確定性多階段決策過程?！?基本概念、基本方程和計(jì)算方法2.1動(dòng)態(tài)規(guī)劃的基本概念和基本方程一個(gè)多階段決策過程最優(yōu)化問題的動(dòng)態(tài)規(guī)劃模型通常包含以下要素。2.1.1階段階段(step)是對(duì)整個(gè)過程的自然劃分。通常根據(jù)時(shí)間順序或空間順序特征來劃分階段，以便按階段的次序解優(yōu)化問題。階段變量一般用表示。在例1中由出發(fā)為，由出發(fā)為，依此下去從出發(fā)為，共個(gè)階段。在例2中按照第一、二、三、四季度分為，共四個(gè)階段。2.1.2狀態(tài)狀態(tài)（state）表示每個(gè)階段開始時(shí)過程所處的自然狀況。它應(yīng)能描述過程的特征并且無后效性，即當(dāng)某階段的狀態(tài)變量給定時(shí)，這個(gè)階段以后過程的演變與該階段以前各階段的狀態(tài)無關(guān)。通常還要求狀態(tài)是直接或間接可以觀測(cè)的。描述狀態(tài)的變量稱狀態(tài)變量（statevariable）。變量允許取值的范圍稱允許狀態(tài)集合(setofadmissiblestates)。用表示第階段的狀態(tài)變量，它可以是一個(gè)數(shù)或一個(gè)向量。用表示第階段的允許狀態(tài)集合。在例1中可取，或?qū)⒍x為，則或，而。 個(gè)階段的決策過程有個(gè)狀態(tài)變量，表示演變的結(jié)果。在例1中取，或定義為，即。根據(jù)過程演變的具體情況，狀態(tài)變量可以是離散的或連續(xù)的。為了計(jì)算的方便有時(shí)將連續(xù)變量離散化；為了分析的方便有時(shí)又將離散變量視為連續(xù)的。狀態(tài)變量簡(jiǎn)稱為狀態(tài)。2.1.3決策當(dāng)一個(gè)階段的狀態(tài)確定后，可以作出各種選擇從而演變到下一階段的某個(gè)狀態(tài)，這種選擇手段稱為決策（decision），在最優(yōu)控制問題中也稱為控制（control）。描述決策的變量稱決策變量（decisionvariable），變量允許取值的范圍稱允許決策集合（setofadmissibledecisions）。用表示第階段處于狀態(tài)時(shí)的決策變量，它是的函數(shù)，用表示的允許決策集合。在例1中可取或，可記作，而。決策變量簡(jiǎn)稱決策。2.1.4策略決策組成的序列稱為策略（policy）。由