運籌學7卷答案

課程名稱:運籌學一（10分）解：則標準形式為：設對偶變量分別為y1，y2，y3，則對偶規(guī)劃為：二（15分）解：首先變成最小化指派問題。B=(7-Cij)5×53分列減1分行減2分列減1分行減2分指派5分所以2分指派5分即甲—5，乙—4，丙—2，丁—1，戊—3，最大生產(chǎn)能力為7+6+5+5+5+5=282分三（20分）解：此問題可分為三個階段，分別在地區(qū)A、B、C設銷售點，k=1,2,3；決策變量uk：表示在地區(qū)k可設置的銷售點數(shù)；狀態(tài)變量sk：表示k階段出可在第k到第c個地區(qū)設置銷售點的個數(shù)；狀態(tài)轉移方程：sk+1=sk-uk表示：4分因為此問題為離散確定性多階段決策，所以可用圖表示。圖形：8分000000000012121212101201012001032110103211017141722273147222020171717121212000171614016302504323244017141722273147222020171717121212000171614016302504323244此問題求總利潤最大，相當于求狀態(tài)s1到狀態(tài)s4的最長路，采用逆序法標號標號：6分則最長路徑為：4—2—1—0，最長路為47。即地區(qū)A設2個銷售點，地區(qū)B設1個銷售點，地區(qū)C設1個銷售點。結果：2分四（15分）解：由最小元素法得初始運輸方案如下表所示：（初始解5分，檢驗數(shù)4分）甲乙丙產(chǎn)量uiA48856056（-4）（4）B1624168212（0）4141C816247741661（16）銷量7210241Vj4124因為σ14＜0，所以該方案不是最優(yōu)方案。進行調整：（新方案3分，檢驗數(shù)2分）甲乙丙產(chǎn)量uiA488560（4）56（8）B1624168216（0）4141C81624778725（16）銷量7210241Vj080因為，所以該方案是最優(yōu)方案?？傔\費為2744。（1分）五（20分）解：（1）首先寫出線性規(guī)劃問題的標準形式（2分）Cj→23100θCBXBbx1x2x3x4x50x45111105/10x54-1[2]0014/2δj23100（2分）0x43[3/2]011-1/223x22-1/21001/2—δj5/2000-3/2（3分）2x12102/32/3-1/33x23011/31/31/3δj00-4/3-7/3-1/3（2分）此時，原問題得到最優(yōu)解為X*=(2，3，0，0，0)T，maxZ＝13（1分）（2）當右邊向量b變?yōu)?3,7)T時，（5分）代入最終單純型表繼續(xù)迭代：Cj→23100CBXBbx1x2x3x4x52x1-1/3102/32/3[-1/3[3x210/3011/31/31/3δj00-4/3-7/3-1/3（2分）0x51-30-2-213x2311110δj-10-2-30（2分）所以X*=（0，3，0，0，1）T，Z*=9（1分）六（20分）解：（1）用Dijkstra算法求頂點v1到頂點v7的最短路，標號見下表：由圖知v1到v7的最短路長為12，路徑為V1→V2→V5→V7（2分）VV24343101354278V1V31V4V5V6V7（4，4）5（7，4）（10，10）（3，3）（12，12）（8，8）（6分）（2）求最大流：增廣鏈流量調整量V1→V4→V6→V74V1→V2→V3→V5→V73V1→V2→V5→V71（4分）V1→V3→V6→V73V1→V4→V3→V6→V71V1→V4→V3→V5→V71V1→V4→V3→V6→V5→V71所以最大流量為：4+3+1+3+1+1+1=14（1分）最大流量圖為：VV2(4,4)(3,3)(4,3)(3,3)(10,7)(1,1)(3,3)(5,