運籌學 試卷及答案 卷5

課程名稱:運籌學課程名稱:運籌學考試時間:第周星期(月日)題號一二三四五六七八九十總分得分評分人一、（15分）寫出下面線性規(guī)劃的標準形式和對偶線性規(guī)劃。二、（20分）已知線性規(guī)劃問題（1）用單純形法求出最優(yōu)解。（2）若C1=4時，最優(yōu)解如何改變。三、（15分）求解下列運輸問題，表格中間的數(shù)字為運價。產(chǎn)銷B1B2B3B4產(chǎn)量A1123410A2876520A391011930銷量8221218學院：專業(yè)：學號：姓名：裝訂線四、（15分）求解如下最小化指派問題。五、（20分）下圖為一網(wǎng)絡圖：若不考慮方向時，邊上數(shù)字為邊的長度，求該圖的最小支撐樹；（7分）若邊上數(shù)字為容量，求從頂點v1到頂點v8的最大流。（10分）求最小割（3分）VV1V2V4V3V5V7V6V85679446459754六、（15分）用動態(tài)規(guī)劃的方法求出從點A到點F的最短路。66435437519125796242851544AB111B2B3C1C2C3D1D2D3E1E2F課程名稱:運籌學考試時間:年月日(第周星期)一（15分）解：則標準形式為：設對偶變量分別為y1，y2，y3，則對偶規(guī)劃為：二（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）若C1=4時，代入最終單純型表：Cj→43100θCBXBbx1x2x3x4x54x12102/32/3-1/323x23011/31/3[1/3]3δj00-8/3-11/31/3（5分）4x151111020x5903111—δj0-1-3-40（3分）所以最優(yōu)解改變，X*=（5，0，0，0，9）T，Z*=20（2分）三（15分）解：方法一：（1）用最小元素法求得初始解，并計算檢驗數(shù)如下：B1B2B3B4產(chǎn)量uiA182（0）（2）100A2（4）（2）218203A3（0）2010（-1）308銷量8221218vj1232（初始方案5分，位勢2分，檢驗數(shù)2分）（2）因為σ34<0，所以此方案不是最優(yōu)方案，調(diào)整的新方案并計算新檢驗數(shù)：B1B2B3B4產(chǎn)量uiA182（1）（3）100A2（3）（1）128204A3（0）20（1）10308銷量8221218vj1221（新方案3分，位勢1分，檢驗數(shù)1分）因為所有σij≥0，所以此解為最優(yōu)解，又因為有非基變量檢驗數(shù)δ31＝0，所以，該問題有多個最優(yōu)解。其中一個最優(yōu)解為：A1-B1：8，A1-B2：2，A2-B3：12，A2-B4：8，A3-B2：20，A3-B4：10；最小運費z=8×1+2×2+12×6+8×5+20×10+10×9＝414。（1分）方法二：用沃格爾法（方法略），初始解即為最優(yōu)解。（評分標準：沃格爾法求得初始方案10分，檢驗數(shù)4分，結(jié)果1分）四（15分）解：矩陣變換（4分）矩陣變換（4分）（試指派4分，劃直線1分）調(diào)整（2分）所以（1分）調(diào)整（2分）（再指派2分）此時最大值W=33+19+41+35+19=147（1分）V1V2V1V2V4V3V5V7V6V85544454（6分）最小樹的權數(shù)為：5+5+5+4+4+4+4=31（1分）（2）增廣鏈流量調(diào)整量V1→V2→V4→V6→V84（3分）V1→V3→V5→V7→V86（3分）V1VV1V2V4V3V5V7V6V8(5,0)(6,6)(7,6)(9,6)(4,0)(4,0)(6,6)(4,4)(5,4)(9,4)(7,0)(5,0)(4,4)最大流量圖為：（3分）（3）最小割為：（3分）六（15分）：分54個階段，k=1,2,3,4,5K=5時，（1分）K=4時，（1分）（1分）（1分）K=3時，（1分）（1分）（1分）K=2時，（1分）（1分）