【正文】 數(shù)學(xué)規(guī)劃的理論與方法 1. 線(xiàn)性規(guī)劃理論與方法 2. 目標(biāo)規(guī)劃的理論與方法 3. 整數(shù)規(guī)劃的理論與方法 4. 非線(xiàn)性規(guī)劃的理論與方法 5. 動(dòng)態(tài)規(guī)劃 6. 最優(yōu)控制理論 y 一 .線(xiàn)性規(guī)劃的理論與方法 線(xiàn)性規(guī)劃是指目標(biāo)函數(shù)是由線(xiàn)性函數(shù)給出，約束條件由線(xiàn)性等式或者不等式給出的優(yōu)化問(wèn)題。 最早提出線(xiàn)性規(guī)劃問(wèn)題并進(jìn)行專(zhuān)門(mén)研究的學(xué)者 —康托洛維奇 。 康托洛維奇在 20世紀(jì) 30年代就提出了求解線(xiàn)性規(guī)劃問(wèn)題的“解乘數(shù)法”。 自從 1947年美國(guó)學(xué)者丹青格提出求解線(xiàn)性規(guī)劃問(wèn)題的一般方法 —單純形方法 后，才使線(xiàn)性規(guī)劃的理論和方法日臻成熟。 （ 1）由決策變量構(gòu)成，反映決策的目標(biāo)是線(xiàn)性函數(shù)。 （ 2）一組由決策變量的線(xiàn)性等式或不等式構(gòu)成約束 條件。 （ 3）對(duì)決策變量取值范圍加以限制的非負(fù)約束。 線(xiàn)性規(guī)劃模型的特征 例 1：某工廠生產(chǎn)甲、乙兩種產(chǎn)品，每件產(chǎn)品的利潤(rùn)、 所消耗的材料、工時(shí)及每天的材料限額和工時(shí)限額， 如表 。試問(wèn)如何安排生產(chǎn)，使每天所得的利潤(rùn)為最大？ 表 甲 乙 限額 材料 2 3 24 工時(shí) 3 2 26 利潤(rùn) (元 /件 ) 4 3 設(shè)每天生產(chǎn)甲、乙兩種產(chǎn)品分別為 x1 , x2 則該問(wèn)題可描述為由如下數(shù)學(xué)模型： ????????????0,26232432 .34m a x 21212121xxxxxxtsxxZ 線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型 如下形式的線(xiàn)性規(guī)劃模型被稱(chēng)作 標(biāo)準(zhǔn)型 : ??????????????),2,1( 0 ),2,1( .m a x11njxmibxatsxcZjnjijijnjjj??也可用矩陣形式描述 : ?????? 0 bAX .m a xXtsCXZA:資源消耗系數(shù)矩陣 b: 資源限量向量 C:價(jià)格向量 X:決策變量向量 同時(shí)我們對(duì)標(biāo)準(zhǔn)型作如下假定 : . 1 , 0 ,0 )2(. , ,)( )1(即可乘以個(gè)約束方程兩邊同時(shí)則可對(duì)第若有沒(méi)有多余方程彼此獨(dú)立即標(biāo)準(zhǔn)型中的約束方程?????ibbnmAr a n ki 一般的線(xiàn)性規(guī)劃問(wèn)題通過(guò)變換可化成標(biāo)準(zhǔn)型 , 變 換方式可以歸結(jié)為 : . ) m a x ( ) m a x () m i n ( :, )1(即可這樣我們只要討論問(wèn)題可以通過(guò)以下方式得到如果目標(biāo)函數(shù)是極小化???????. 0 ,0 , )3()0( , .)0( , .. , )2(????????????kkkkkkzyzyxxba其中則可令無(wú)非負(fù)性限制如果變量該松弛變量右端某松弛變量不等式左端則如果約束條件為該松弛變量右端某松弛變量不等式左端則如果約束條件為變量來(lái)得到我們可以通過(guò)引進(jìn)松弛如果約束方程為不等式 線(xiàn)性規(guī)劃問(wèn)題解的概念 對(duì)于線(xiàn)性規(guī)劃問(wèn)題 ??????????????)( ),2,1( 0 )( ),2,1( .)( m a x11njxmibxatsxcZjnjijijnjjj??. )( : . ),( )( )( : 21的可行解稱(chēng)為最優(yōu)解滿(mǎn)足最優(yōu)解稱(chēng)為可行解的解和滿(mǎn)足約束條件可行解 TxxX ??題的一個(gè)基。是線(xiàn)性規(guī)劃問(wèn)則稱(chēng)階非奇異子矩陣中的一個(gè)是矩陣如果基：設(shè) , )0|(| , )( BBmmABmAr a n k nm????個(gè)非基向量。有中共，之外各列即為非基向量中除矩陣，中的列向量稱(chēng)為基向量基向量與非基向量：基 mnABAB?基變量。為基變量；否則稱(chēng)為非稱(chēng)對(duì)應(yīng)的變量基向量基變量與非基變量：與 jj xP稱(chēng)為基解。的解，求出的滿(mǎn)足為基解：令所有非基變量 )( 0 )( mnC?? 基解的數(shù)目解的數(shù)目基可行為可行基。顯然，對(duì)應(yīng)基可行解的基，稱(chēng)的基解稱(chēng)為基可行解。足基可行解與可行基：滿(mǎn)優(yōu)基。為最對(duì)應(yīng)基本最優(yōu)解的基稱(chēng)優(yōu)解，的基可行解稱(chēng)為基本最滿(mǎn)足基本最優(yōu)解與最優(yōu)基： )( 可行解 基解 基可行解 線(xiàn)性規(guī)劃問(wèn)題的圖解法 下面結(jié)合例 1的求解來(lái)說(shuō)明圖解法步驟。 ????????????0,26232432 .34m a x 21212121xxxxxxtsxxZ例 1 第一步： 在直角坐標(biāo)系中分 別作出各種約束條件，求出 可行域（圖中陰影部分）。 x2 Q2(6,4) x1 3x1+2x2=26 2x1+3x2=24 Z O Q1(26/3,0) Q3(6,4) 為則稱(chēng)點(diǎn)連線(xiàn)上的一切任意兩點(diǎn)中的一個(gè)點(diǎn)集，若維歐氏空間是設(shè)定義，先介紹兩個(gè)概念。為介紹基本定理的需要 , )10( )1( )(, )2()1()2()1()2()1(KKXXXXXKXXEnKn???????????第二步： 作出一條目標(biāo)函數(shù)等值線(xiàn)，并確定 Z 值增大的方向。 第三步： 沿 Z 值增大方向移動(dòng)，當(dāng)移至 Q2(6,4) 點(diǎn)時(shí)， Z 值為最大， Z*=36 . 基本定理 . 凸集., 域必為凸集則其可行空可行域若線(xiàn)性規(guī)劃問(wèn)題存在非定理的一個(gè)為則稱(chēng)的線(xiàn)性組合表示為點(diǎn)若不能用兩個(gè)不同的是凸集，設(shè)定義 , )10( )1( , 。 )2()1()2()1(KXKXXXKXKXKXK????????????. 極點(diǎn)., 可行域的極點(diǎn)上達(dá)到數(shù)最優(yōu)值一定可以在其則其目標(biāo)函域有界若線(xiàn)性規(guī)劃問(wèn)題的可行定理. 的極點(diǎn)對(duì)應(yīng)于可行域解線(xiàn)性規(guī)劃問(wèn)題的基可行定理 X 從理論上來(lái)講 ,采用“枚舉法”找出所有基可行解 ,并 求解 線(xiàn)性規(guī)劃問(wèn)題的單純形方法 一一比較 ,一定會(huì)找到最優(yōu)解。但當(dāng) m, n 較大時(shí) ,這種方法是不經(jīng)濟(jì)和不可取的。 下面介紹求解線(xiàn)性規(guī)劃問(wèn)題的有效方法 ——單純形方法。 單純形法的實(shí)質(zhì)是從一個(gè)基可行解向另一個(gè)基可行解（極點(diǎn)到極點(diǎn)）的迭代方法。 以下通過(guò)例 1的求解過(guò)程說(shuō)明單純形方法的基本步驟。 ????????????0,26232432 .34m a x 21212121xxxxxxtsxxZ例 1： 第一步： 引進(jìn)松馳變量 x3 , x4 將原問(wèn)題化為標(biāo)準(zhǔn)型。 ????????????????0,26 2324 32 . 0034m a x 43214213214321xxxxxxxxxxtsxxxxZ標(biāo)準(zhǔn)型 第二步： 找出初始可行基，建立初始單純形表。 見(jiàn)下表 。 cj 4 3 0 0 CB XB b x1 x2 x3 x4 0 0 x3 x4 24 26 2 3 1 0 3 2 0 1 Z 0 4 3 0 0 表 bBbIPPB 10430 ),( ???? 則本例中，初始可行基第三步： 最優(yōu)性檢驗(yàn)。 可能有下面三種情況： 的檢驗(yàn)數(shù)檢驗(yàn)各非基變量 , jjx ?i?j?行換基迭代。四步，進(jìn)不是最優(yōu)基，須轉(zhuǎn)入第則基分量，所對(duì)應(yīng)的列向量有正若有某個(gè)負(fù)檢驗(yàn)數(shù)，停止計(jì)算。函數(shù)無(wú)上界，即無(wú)界解標(biāo)則該線(xiàn)性規(guī)劃問(wèn)題的目（部分量它所對(duì)應(yīng)的列向量的全若有某，停止計(jì)算?？尚薪饧礊榛咀顑?yōu)解為最優(yōu)基，相應(yīng)的基則基若所有的 B 0 )3( , 0), , 0 )2( , 0 )1(21????jmssssjaaaB????量。所在的列變?yōu)閱挝涣邢蚣窗鸦兞窟M(jìn)行初等行變換，為主元，在單純形表中以為主元。為出基變量，其中確定＝元按最小比值原則求出主確定換出變量取確定換入變量 )3( ,}0|{m i n : )2(. }0 ,0|m i n { : )1(srsrsrrsrisisiirjsxaaxabaabxnjjsx????????第四步： 換基迭代。 的單純形表。，得到新的可行基和新?lián)Q為中的同時(shí)將 srB xxX有無(wú)界解，計(jì)算終止。出至獲得最優(yōu)解，或判斷重復(fù)第三、第四步，直 所在行的交叉處所在列和換出基變量，并以為確定，＝為換入變量。所以，因?yàn)閬?lái)說(shuō)，對(duì)于表針對(duì)例 326}326,224{}0|{m i n 1}3,4|m i n {: 1 414121xxxaabxjsisisiii??????????????元素為主元進(jìn)行迭代。 cj 4 3 0 0 CB XB b x1 x2 x3 x4 0 0 x3 x4 24 26 2 3 1 0 [3] 2 0 1 12 26/3 Z 0 4 3 0 0 0 4 x3 x1 20/3 26/3 0 [5/3] 1 2/3 1 2/3 0 1/3 4 13 Z 104/3 0 1/3 0 4/3 表 i?j?j?同理，確定 x2 換入， x3 換出，繼續(xù)迭代得表 cj 4 3 0 0 CB XB b x1 x2 x3 x4 3 4 x2 x1 4 6 0 1 3/5 2/5 1 0 2/5 3/5 Z 36 0 0 1/5