中國石油大學(xué)運籌學(xué)期末試題B

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

，且該列系數(shù) ，則線性問題最優(yōu)解不存在〔無假設(shè)線性規(guī)劃的可行域是空集，則說明存在沖突的約束條件。

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

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

是第一個基變量 的系數(shù)四、線性規(guī)劃的最終單純形表〔3〕〔10〕對偶規(guī)劃為：〔4〕對偶問題最優(yōu)解為：〔4〕〔3〕 〔2〕五、線性規(guī)劃問題〔20〕由于：所以：最終單純形表變?yōu)椋?10/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最優(yōu)解為： ?！?分〕在最終表中的檢驗數(shù)為：而故最終單純形表為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此時題目有無窮多最優(yōu)解，其中之一為 ?！?分〕原問題的最優(yōu)解滿足增加的約束條件 ,所以最優(yōu)解不變，仍舊為 〔5分〕六、運輸問題〔10〕由表可知產(chǎn)量=銷量，供需平衡。用最小元素法確定的初始調(diào)運方案為：承受閉回路法進(jìn)展計算，得出確定值最大的負(fù)檢驗數(shù)為 ,沿著閉回路動身進(jìn)展調(diào)整后的表為：即當(dāng)

是唯一的檢驗數(shù)，然后沿著閉回路動身進(jìn)展調(diào)整，調(diào)整后的表為：時為最優(yōu)，最小費用為155個單位。七、目標(biāo)規(guī)劃問題〔10〕系統(tǒng)約束確定的范圍為第一象限，第一優(yōu)先級目標(biāo)優(yōu)化后得區(qū)域直線①、OX2、OX1所圍成的開區(qū)域，其次優(yōu)先級目標(biāo)優(yōu)化后得凸集OABC，第三級優(yōu)化后得到凸集OABED，此凸集內(nèi)的點均為滿足解?！?〕八、網(wǎng)絡(luò)計算〔15〕〔1〕畫出網(wǎng)絡(luò)圖如下圖：〔8〕〔2〕〔3〕表上計算：〔6〕最早開最早完最遲開最遲完工序a工時間0工時間10工時間0工時間10總時差0b082102c101610160d824244016e164016400f404440440g44484