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

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

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

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

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

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