【正文】 ，構(gòu)造兩個約束條件和分別加到原整數(shù)規(guī)劃問題中，可得如下兩個新的分枝問題和：求解LP1，得到最優(yōu)解和最優(yōu)目標函數(shù)為； 求解LP2，得到最優(yōu)解和最優(yōu)目標函數(shù)為。由于，先對LP2繼續(xù)分支，構(gòu)造兩個約束條件和分別加到原規(guī)劃問題中，可得如下兩個新的分枝問題和：求解LP21，得到最優(yōu)解和最優(yōu)目標函數(shù)為；求解LP22，得到最優(yōu)解和最優(yōu)目標函數(shù)為。對于LP22，從圖解中看出，沒有可能的整數(shù)解使其目標函數(shù)值滿足，故結(jié)束該分支。對于LP21，構(gòu)造兩個約束條件和分別加到原規(guī)劃問題LP21中，可得如下兩個新的分枝問題和：LP211最優(yōu)解和最優(yōu)目標函數(shù)為：LP211最優(yōu)解和最優(yōu)目標函數(shù)為： 整數(shù)解，故無需對LP1進行分枝。所以，原整數(shù)規(guī)劃問題的最優(yōu)解為最優(yōu)目標函數(shù)值為。（2）暫不考慮整數(shù)約束，利用圖解法求解對應(yīng)的松弛問題LP，得到最優(yōu)解和最有目標函數(shù)值為針對這一非整數(shù)解進行分枝，構(gòu)造兩個約束條件和分別加到原整數(shù)規(guī)劃問題中，可得如下兩個新的分枝問題和：求解LP1，得到最優(yōu)解和最優(yōu)目標函數(shù)為； 求解LP2，得到最優(yōu)解和最優(yōu)目標函數(shù)為，已得到整數(shù)解，該分枝停止繼續(xù)計算。由于，對LP1繼續(xù)分支，構(gòu)造兩個約束條件和分別加到原規(guī)劃問題LP1中，可得如下兩個新的分枝問題和：求解LP11，得到最優(yōu)解和最優(yōu)目標函數(shù)為。由于得到整數(shù)解，該分枝停止計算。求解LP12，得到最優(yōu)解和最優(yōu)目標函數(shù)為。由于，該分枝已無必要繼續(xù)計算，剪掉改枝。由于，所以原整數(shù)規(guī)劃的最優(yōu)解最優(yōu)目標函數(shù)值為。解：（1）1100初始表06[2]11002045011100最終表15/3105/61/618/3012/31/3001/61/61) 將原線性規(guī)劃約束條件添加松弛變量，化為標準型，不考慮整數(shù)約束條件，用單純形法求解，計算結(jié)果如表41所示。表41因而最優(yōu)解為2) 選擇真分數(shù)部分max的基變量所在行為源行；本題中，兩者真分數(shù)相同，故任選一行作為源行。這里我們選第二行作為源行。3) 將約束條件系數(shù)分離：如是整數(shù)則不變；如是分數(shù)，寫成一個整數(shù)加一個正的真分數(shù)；4) 將真分數(shù)部分留在左邊，整數(shù)部分移動到右邊；5) 由此得到切割條件：6) 將切割條件系數(shù)整數(shù)化，即得到切割方程（*）；7) 將*添加到原最終表，得到非可行解，見表42。從表42中可以看出，得到的是非可行解，用對偶單純形表繼續(xù)進行計算。表42 添加切割方程后的單純形表11000015/3105/61/6018/3012/31/3002001[1]1001/61/601210101/61201101/3020011100001/6此時得到最優(yōu)解為，最優(yōu)目標函數(shù)值為。（2）1) 將原線性規(guī)劃約束條件添加松弛變量，化為標準型，不考慮整數(shù)約束條件，用單純形法求解，計算結(jié)果如表43所示。表43114000初始表04121000165201004[2]1001114000最終表040011/34/344/30102/95/9118/31001/92/900019/92/9因而最優(yōu)解為2) 選擇真分數(shù)部分max的基變量所在行為源行；本題中選第三行作為源行。3) 將約束條件系數(shù)分離：如是整數(shù)則不變；如是分數(shù)，寫成一個整數(shù)加一個正的真分數(shù)；得到切割條件為：4) 將切割條件系數(shù)整數(shù)化，即得到切割方程（*）；5) 將*添加到原最終表，得到非可行解，見表44。從表44中可以看出，得到的是非可行解，用對偶單純形表繼續(xù)進行計算。表44 添加切割方程后的單純形表1140000040011/34/3044/30102/95/90118/31001/92/90060001[2]100019/92/9000001102/3430101/205/18112100001/9030001/211/2000201/9由此得到最優(yōu)解為，最優(yōu)目標函數(shù)值為此時得到最優(yōu)解為，最優(yōu)目標函數(shù)值為。解：（1）將各約束條件編號如下：先通過試探法容易看出就是一個可行解，算出相應(yīng)的目標函數(shù)值。故增加約束條件 ◎?qū)?個約束條件按◎～③順序排好(如表45)，對每個解，依次代入約束條件左側(cè)，求出數(shù)值，看是否適合不等式條件，如某一條件不適合，同行以下各條件就不必再檢查。計算過程中，若產(chǎn)生劣于此時的過濾值，則不考慮，繼續(xù)下一個組合；若優(yōu)于此時的過濾值，則逐個考察是否滿足約束條件，只要有一個不滿足，則該組合為不可行解，繼續(xù)下一個組合；如果滿足所有約束，則產(chǎn)生新的過濾值，繼續(xù)下一個組合。表45條件滿足條件?是（√）否（）Z值◎①②③（0,0,0)0（0,0,1)2（0,1,0)3（0,1,1)5242√5（1,0,0)4240（1,0,1)65（1,1,0)7351√7（1,1,1)9082√9可見，最優(yōu)解為（2）將各約束條件編號如下：先通過試探法容易看出就是一個可行解，算出相應(yīng)的目標函數(shù)值。故增加約束條件 ◎?qū)?個約束條件按◎～④順序排好(如表46)，對每個解，依次代入約束條件左側(cè)，求出數(shù)值，看是否適合不等式條件，如某一條件不適合，同行以下各條件就不必再檢查。計算過程中，若產(chǎn)生劣于此時的過濾值，則不考慮，繼續(xù)下一個組合；若優(yōu)于此時的過濾值，則逐個考察是否滿足約束條件，只要有一個不滿足，則該組合為不可行解，繼續(xù)下一個組合；如果滿足所有約束，則產(chǎn)生新的過濾值，繼續(xù)下一個組合。表46條件滿足條件?是（√）否（）Z值◎①②③④（0,0,0)0（0,0,1)5（0,1,0)2（0,1,1)3（1,0,0)3（1,0,1)80211√8（1,1,0)1（1,1,1)6可見，最優(yōu)解為、小劉、小王、小張完成甲、乙、丙、丁四項工作。每人做各種工作消耗的時間如表419所示。問，如何安排任務(wù)，使總消耗時間最短？表419 每人完成各項工作消耗的時間工作人員甲乙丙丁小李33392538小劉45433049小王37543441小張30492344解：該問題是指派問題，用匈牙利法求解。1) 變換效率矩陣，使每行每列至少有一個零，變換后的矩陣記為；2) 進行試指派，尋求最優(yōu)解；?個數(shù)，轉(zhuǎn)下一步； 3) 作最少數(shù)目的直線，覆蓋所有0元素。目的是確定系數(shù)矩陣的下一個變換，可按下述方法進行；① 對沒有?的行打“252?！碧枺虎?在已打“252。”號的行中，對f所在列打“252?！?；③ 在已打“252?！碧柕牧兄校瑢?所在的行打“252?！碧枺虎?重復②、③，直到再也找不到可以打“252?！碧柕男谢蛄袨橹梗虎?對沒有打“252。”的行劃一橫線，對打“252?！钡牧袆澮豢v線，這樣就得到覆蓋所有0元素的最少直線數(shù)。此時。4) 變換矩陣以增加0元素；① 在未被直線覆蓋的元素中找出一個最小元素，② 然后在打“252?！毙懈髟刂卸紲p去這一元素，③ 而在打“252?！绷械母髟囟技由线@一最小元素，以保持原來0元素不變（為了消除負元素）；④ 得到新的系數(shù)矩陣。5) 重復步驟2）4）；此時，?個數(shù)，得到最優(yōu)解。該問題最優(yōu)方案為：小李→乙，小劉→丙，小王→丁，小張→甲。消耗時間最短為：。第五章 動態(tài)規(guī)劃習題答案，由后向前逐步推移至當k=4時，由到終點E只有一條路線，故,同理當k=3時，出發(fā)點有三個，若從出發(fā)，有兩個選擇，從走或從走其相應(yīng)的決策為同理得出發(fā)時當k=2時，出發(fā)點有,每個出發(fā)點有三種選擇相應(yīng)的決策為當k=1時，相應(yīng)的決策為因此最終決策可以：當原路徑中的狀態(tài)無法分割成階段時，可以增設(shè)虛擬狀態(tài)，如圖ABCD1D2D3EFG2030706040500040303040設(shè)階段n=1,2,3,4狀態(tài)集S1={A}，S2={B,C}，S3={D1,D2,D3}，S4={E,F}決策集D1(S1)={X1(A)}={B,C}=S2；D2(S2)={X2(B),X2(C)}={D1,D2,D3}=S3；D3(S3)={X3(D1),X3(D2),X3(D3)}={E,F}=S4；D4(S4)={X4(E),X4(F)}={G}狀態(tài)轉(zhuǎn)移方程：遞推方程：當n=4時，GE3030GF4040G當n=3時，EFD10+30——30ED240+3030+4070E或FD3——0+4040F當n=2時，D1D2D3B70+3060+70——100D1C——40+7050+4090D3當n=1時，BCA20+10030+90120B或C綜上所述，最優(yōu)路徑有兩條，分別是A→B→D1→E→G，A→B→D3→E→G。狀態(tài)變量表示第k個時期的初始庫存量，表示第四個時期末的庫存量由題設(shè)，==0根據(jù)各時期的需求量的分布可知， 0 0 0決策變量表示第k個時期的生產(chǎn)量狀態(tài)轉(zhuǎn)移方程 由由，得=從而 所以，允許決策集合））））階段指標（）表示第k個時期的初始庫存量為,生產(chǎn)量為時， 第k個時期的費用，則最優(yōu)值函數(shù)（）表示第k個時期的初始庫存量為時，從第k至第n個時期的最小費用。一維遞推關(guān)系式最優(yōu)生產(chǎn)計劃有兩個：（1）（2）狀態(tài)變量表示“分配給第塊糧田至第4塊糧田的施肥數(shù)量”決策變量表示“分配給第塊糧田的施肥數(shù)量”于是：表示“的肥料用于第塊糧田時的增產(chǎn)量”表示“個單位的肥料分配給第塊糧田到第四塊糧田的最大增產(chǎn)值”遞推關(guān)系式：其中可由得：第四階段，即=4，設(shè)將個單位（=0,1,2,3,4,5,6）的肥料全部分配給第4塊糧田時，則最大的增產(chǎn)值為：，其中0,1,2,3,4,5,6。因為此時只有一塊糧田，有多少肥料都將全部分配給第四塊糧田，所以它的增產(chǎn)值就是該階段最大增產(chǎn)值，其數(shù)值計算如表1：表1S4 X401234560000128281247472365653474744580805685856第三階段，=3，設(shè)將個單位重量（=0,1,2,3,4,5,6）的肥料分配給第3，4兩塊糧田時，對應(yīng)每個值，有一種最優(yōu)分配方案，使最大增產(chǎn)值為：其中=0,1,2,3,4,5,6因為給第3塊糧田分個單位重量的肥料，其增產(chǎn)量為，余下的個單位的肥料分給第4塊糧田，則最大增產(chǎn)值為。所以現(xiàn)在的問題是選擇，使得取得最大值，其數(shù)值計算如表2：S3 X3012345600001281828024