運籌學 A 試卷答案2013級答案

1-2013級運籌學試卷（A卷）答案一、填空題(共10分，每空1分)1、線性規(guī)劃問題的3個要素是：決策變量、目標函數和約束條件。2、單純形法最優(yōu)性檢驗和解的判別，當所有的σj≤0現有頂點對應的基可行解是最優(yōu)解，當所有的σj≤0，某個非基變量xj-cjzj=0線性規(guī)劃問題有無窮多最優(yōu)解，當某個σj﹥0，Pj相量的所有分量aij≤0線性規(guī)劃問題存在無界解。4、連通圖的是指：在一個圖中，若每一對頂點之間至少存在一條鏈，稱這樣的圖為連通圖。5、樹圖指無圈的連通圖，最小樹是樹枝總長最小的部分樹。6、在產銷平衡運輸問題中，設產地為m個，銷地為n個，運輸問題的解中的基變量數為m+n-1。二、簡答題。簡算題。（共20分）1、已知線性規(guī)劃問題，如下：maxZ=7-2+5請寫出其對偶問題。（10分）解：minw=6y1s.t.2、已知整數規(guī)劃問題：在解除整數約束后的非整數最優(yōu)解為(x1,x2)=(1,1.5)，根據分支定界法，請選擇一個變量進行分支并寫出對應的2個子問題（不需求解）。（10分）解：選擇x2進行分支，得到以下2個子問題：maxz=10x1評分標準：以上2個子問題各5分，其中新加入的約束條件各3分。三、計算題（共70分）1、某廠用A1，A2兩種原料生產B1，B2，B3三種產品，工廠現有原料，每噸所需原料數量以及每噸產品可得利潤如下表。每噸商品所需原料（噸）原料商品現有原料（噸）B1B2B3A121030A202450每噸可得利潤（萬元）320.5在現有原料的條件下，應如何組織生產才能使該廠獲利最大？（共20分）(1)寫出該線性規(guī)劃問題的數學模型（4分）max（2）將上面的數學模型化為標準形式（2分）max（3）利用單純形法求解上述問題（14分，單純形表格已給出,如若不夠,可自行添加）（3）利用單純形法求解上述問題（14分，單純形表格已給出,如若不夠,可自行添加）cj320.500CBXBBx1x2x3x4x50x430[2]10100x55002401cj-zj320.5003x11510.500.500x55002[4]01cj-zj00.50.5-1.503x11510.500.500.5x312.50[0.5]100.25cj-zj00.250-1.5-0.1253x12.510-10.5-0.252x22501200.5cj-zj00-0.5-1.5-0.25X=（2.5,25,0,0,0）maxz=57.5（四個表每個3分，結論2分，共14分，按數字扣完為止）2、考慮下列運輸問題：B1B2B3產量A16424A28575銷量333請用表上作業(yè)法求解此問題，要求：使用Vogel法求初始解。若表格不夠可自行添加（15分）（1）使用Vogel法求初始解（7分）B1B2B3產量①②③A16/142/34226A28/25/375238銷量333①215②21③2（2）校驗數（7分）B1B2B3uiA116A238vj0-3-4當前調運方案：x11=1，x13=3，x21=2，x22=3，其余為零，為最優(yōu)方案。最優(yōu)值為6*1+2*3+8*2+5*3=43。（1分）3、有4臺機器都可以做A、B、C、D四種工作，都所需費用不同，其費用如下表所示。請用匈牙利法求總費用最小的分配方案。（10分）工作機器ABCDⅠ41075Ⅱ2763Ⅲ3344Ⅳ4663解：（1）（2）（3）（4）（5）括號對應的xij=1，最優(yōu)分配方案。最有效率值7+2+3+3=15（以上每步2分）4、某工廠內聯(lián)結6個車間的道路如下圖所示，已知每條道路的的距離，求沿部分道路架設6個車間的電話網，使電話線總距離最短。（10分，提示最小部分樹問題，采用避圈法或破圈法均可，但必須用圖或文字描述詳細步驟）解：方法1：避圈法（1）任選一個點，這里選擇V1點，令V1∈V，其余點屬于V’，V與V’間最短邊為(V1,V2)。邊(V1,V2)是最小樹內的邊。（2）令V∪V2V，V’\V2V’，V與V’間最短邊為(V2,V3)。邊(V2,V3)是最小樹內的邊。（3）令V∪V3V，V’\V3V’，V與V’間最短邊為(V3,V5)。邊(V3,V5)是最小樹內的邊。（4）令V∪V5V，V’\V5V’，V與V’間最短邊為(V5,V4)。邊(V5,V4)是最小樹內的邊。（5）令V∪V4V，V’\V4V’，V與V’間最短邊為(V4,V6)。邊(V4,V6)是最小樹內的邊。（或：V與V’間最短邊為(V5,V6)。邊(V5,V6)是最小樹內的邊）或沿最終圖中紅線標識的邊架設電話網，電話線總距離最短1+2+3+5+6=17。上述5個步驟（文字描述或繪圖均可）各的2分，若最終結論沒有給出或給錯扣1分。方法2：破圈法（1）從原圖中任取一回路，這里取(V1,V2,V3,V1)，去掉最大的一邊（V1,V3），得圖1圖1（2）從圖1中任取一回路，這里取(V2,V4,V3,V2)，去掉最大的一邊（V2,V4），得圖2圖2（3）從圖2中任取一回路，這里取(V3,V4,V5,V3)，去掉最大的一邊（V3,V4），得圖3圖3（4）從圖3中任取一回路，這里取(V4,V5,V6,V4)，去掉最大的一邊（V4,V6），得圖4（去掉最大的一邊（V5,V6），得圖4）.或圖4沿最終圖中的邊架設電話網，電話線總距離最短1+2+3+5+6=17。上述4個步驟（文字描述或繪圖均可）各的2.5分，若最終結論沒有給出或給錯扣1分。5、用Ford-Fulkerson標號算法求解下圖中VsVt的最大流量，并標出網絡的最小割集。（15分）vvsvtv2v1v4v3(3,3)(5,1)(1,1)(4,3)(1,1)(2,2)(3,0)(2,1)(5,3)標號法找增廣鏈vs-v1-v2-v4-vt前向弧+1，后向弧-1，得