運籌學 試卷B一、名詞解釋〔3×5=15〕1.可行基 2.階段變量 3.決策變量 4.時差 5.偏差變量二、推斷題〔1×10=10〕線性規劃問題的根本解對應可行域的頂點。假設 、 是某線性規劃問題的最優解，則 也是該問題的最優解。用單純形法求解標準型的線性規劃問題時，假設存在界解〕。

，且該列系數 ，則線性問題最優解不存在〔無假設線性規劃的可行域是空集，則說明存在沖突的約束條件。

時，即可判定表中的解為最優解。用大M法處理人工變量時，假設最終單純形表上基變量中仍含人工變量，則原問題無可行解。線性規劃原問題的對偶問題是原問題。線性規劃原問題無可行解，其對偶問題必無可行解。線性規劃原問題存在可行解，其對偶問題必定存在可行解。在目標線性規劃問題中，正偏差變量取正值，負偏差變量取負值。三、線性規劃問題(10某線性規劃問題的初始單純行表〔見表1〕和用單純形法迭代后得到的表〔見表2〕如下，試求括弧中未知數1

的值。xxbi6101-13012200xbi〔f〕xbi〔f〕2-11/20411/21-7四、線性規劃的最終單純形表〔3〕〔10〕3250101/21/2131000103001-1/23/2〔1〕寫出其對偶問題。000-1-2解出對偶問題最優解。寫出最優基矩陣及其逆矩陣 。五、線性規劃問題〔20〕用單純形法求得最優解的單純形表〔見表4〕。試分析在以下各種條件單獨消滅的狀況下，最優解將如何變化。424/3012/3-1/300310/310-1/32/3000300-111002/300-2/31/30100-1/3-4/300第①、②兩個約束條件的右端項分別由6784；增加一個變量 ,其在目標函數中系數 =4，在約束方程中的系數列向量為 ;增加一個的約束條件 。六、求解以下運輸問題使總運費最低〔方框內數字為運價〕〔10分〕七、目標規劃問題〔10〕用圖解法找出以下目標規劃問題的滿足解八、網絡圖計算〔15〕工序緊前工序工序時間〔天〕工序緊前工序工序時間〔天〕a—10hf10b—8if4ca,b6jg12db16kh,i,j16ec24lc8fd,e4mｌ24gf4nk,m4要求：繪制網絡圖。計算各工序的最早開工時間、最早完工時間、最遲開工時間、最遲完工時間。計算各工序的總時差。確定關鍵路線。一、名詞解釋〔5×3=15〕可行基：對應于基可行解的基稱為可行基。階段變量：動態規劃中，按時間段或空間特征分解成假設干相互聯系的階段，表示階段的變量稱為階段變量。決策變量：在動態規劃中，表示決策的變量叫做決策變量。時差：網絡規劃中，工作的機動時間或富有時間叫做時差，分為總時差和單時差。偏差變量：在目標規劃中，對于每一個決策目標，引入的正、負變量d+、d-稱為偏差變量。二、推斷題〔10×1=10〕123.45.678910．錯三、線性規劃問題(10解：此題目雖然沒有給出目標函數中各個變量的系數，但由于題目不涉及求目標函數值，故可以認為此問12〔2〕〔3〕〔2〕由以上等式得出一個線性方程組。留意到表中是基變量的檢驗數，而向量，所以=0，h=0。解此方程組，得到：〔3〕

是第一個基變量 的系數四、線性規劃的最終單純形表〔3〕〔10〕對偶規劃為：〔4〕對偶問題最優解為：〔4〕〔3〕 〔2〕五、線性規劃問題〔20〕由于：所以：最終單純形表變為：210/3012/3-1/30031/310-1/32/3000-200[-1]1100-4/300-2/31/30100-1/3-4/300220101/32/30311001/3-1/3002001-1-1000000-1/3-2/31000-5/3-1/30最優解為： 。〔7分〕在最終表中的檢驗數為：而故最終單純形表為24/3012/3-1/3000310/310-1/32/30010300-1110402/300-2/31/301[2]00-1/3-4/300124/3012/3-1/3000331001/20-1/2005/3001/3-1/31-2041/300-1/31/601/21000-3/20-1/20此時題目有無窮多最優解，其中之一為 。〔8分〕原問題的最優解滿足增加的約束條件 ,所以最優解不變，仍舊為 〔5分〕六、運輸問題〔10〕由表可知產量=銷量，供需平衡。用最小元素法確定的初始調運方案為：承受閉回路法進展計算，得出確定值最大的負檢驗數為 ,沿著閉回路動身進展調整后的表為：即當

是唯一的檢驗數，然后沿著閉回路動身進展調整，調整后的表為：時為最優，最小費用為155個單位。七、目標規劃問題〔10〕系統約束確定的范圍為第一象限，第一優先級目標優化后得區域直線①、OX2、OX1所圍成的開區域，其次優先級目標優化后得凸集OABC，第三級優化后得到凸集OABED，此凸集內的點均為滿足解。〔2〕八、網絡計算〔15〕〔1〕畫出網絡圖如下圖：〔8〕〔2〕〔3〕表上計算：〔6〕最早開最早完最遲開最遲完工序a工時間0工時間10工時間0工時間10總時差0b082102c101610160d824244016e164016400f404440440g44484