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