運籌試題可編輯

實用文檔一、回答下面問題(每小題3分)1.在單純形法計算中,如果不按最小比值規(guī)則確定換基變量,則在下一個解中一定會出現(xiàn)。2.原問題無界時，其對偶問題，反之，當對偶問題無可行解時，原問題。3．已知y0為線性規(guī)劃的對偶問題的最優(yōu)解，若y0>0，說明在最優(yōu)生產計劃中對應的資源。4．已知y0為線性規(guī)劃的對偶問題的最優(yōu)解，若y0=0，說明在最優(yōu)生產計劃中對應的資源。5．已知線形規(guī)劃問題的原問題有無窮多最優(yōu)解，則其對偶問題的最優(yōu)解一定是。6．m個產地n個銷地的產銷平衡運輸問題的模型其決策變量的個數是個；基變量的個數是個；決策變量的系數列向量的特點是。7．用位勢法求解運輸問題，位勢的含義是；行位勢與列位勢中有一個的取值是任意的，這是因為。8.用割平面法求解整數規(guī)劃，割平面割去了；但未割去。9．按教材中的符號寫出最大流問題的數學模型。10．什么是截集，何謂最小截集？二、（10分）下表是用單純形法計算到某一步的表格，已知該線性規(guī)劃的目標函數值為z=14表1cjx1x2x3x4x3x12acd0e101/51σjb-1fg（1）求a—g的值；（8分）（2）表中給出的解是否為最優(yōu)解。（2分）三、（每小題6分共12分）車間為全廠生產一種零件，其生產準備費是100元，存貯費是0.05元／天·個，需求量為每天30個，而且要保證供應。（1）設車間生產所需零件的時間很短（即看成瞬時供應）；（2）設車間生產零件的生產率是50個／天。要求在（1）（2）條件下的最優(yōu)生產批量Q*，生產間隔期t*和每天的總費用C*。四、（18分）某公司下屬甲、乙兩個廠，有A原料360斤，B原料640斤。甲廠用A、B兩種原料生產x1,x2兩種產品，乙廠也用A、B兩種原料生產x3,x4兩種產品。每種單位產品所消耗各種原料的數量及產值、分配等如下工廠甲分配原料乙分配原料產品x1x2x3x4原料AB8461016033058104200310產值（百元）43341．求各廠最優(yōu)生產計劃；（12分）2．問公司能否制定新的資源分配方案使產值更高？（6分）五、（10分）已知有六個村莊，相互間道路的距離如圖所示，已知各村莊的小學生數為：A村50人，B村40人，C村40人，D村60人，E村50人，F(xiàn)村90人。現(xiàn)六村決定合建一所小學，問小學應建在哪村，才能使學生上學所走的總路最短？程六、（8分）A、B、C、D、E、F分別代表陸地和島嶼，1、2、3……14表示橋梁及其編號。若河兩岸分別敵對的雙方部隊占領，問至少應切幾座橋梁（具體指出編號）才能達到阻止對方部隊過河的目的，試用圖論方法進行分析。（提示：以陸地為點，橋梁為弧，兩點之間的橋梁數為弧的容量。）七、（12分）設有三個化肥廠供應四個地區(qū)的農用化肥。各化肥的年產量，各地區(qū)的需求量，化肥的運價如下表所示，請寫出產銷平衡運輸表。B1B2B3B4產量A11613221650A21214181560A3192123…50最低要求3070010最高要求457030不限運籌學試卷（2）一、填空（15×2分）1、在線性規(guī)劃問題的約束方程AX=b,X≥0中，對于選定的基B，令非基變量XN=0，得到的解X=；若，則稱此基本解為基本可行解；若，則稱此基本可行解為退化的解；若，則此基可行解為最優(yōu)解。2、用對偶單純形法求解線性規(guī)劃問題時，根據br確定xr為出基變量；根據最小比值法則θ=，確定xk為進基變量。3、在單純形法的相鄰兩次迭代中，迭代前的可行基B和迭代后的可行基的逆矩陣存在關系：-1=ErkB-1其中Erk=。4、已知y*為某線形規(guī)劃問題的對偶問題的最優(yōu)解，若y*>0，說明在最優(yōu)化生產計劃中對應的資源。5、平衡運輸問題（m個產地，n個銷地）的基可行解中基變量共有個；其中決策變量xij所對應的列向量pij=.。6、對于Max型整數規(guī)劃問題，若其松弛問題的最優(yōu)單純形表中有一行數據為：XBbx1x2x3x4x23/4017/4-11/4則對應的割平面方程為。7、用匈牙利法解分配問題時，當則找到了分配問題的最優(yōu)解；稱此時獨立零元素對應的效益矩陣為。8、將網絡D=（V，A，C）的頂點集合V分割成兩個非空集合V1和V1，使VS∈V1，Vt∈V1，則弧集成為分割VS和Vt的截集；稱為截集的容量。二、問答題（2×5分）1．材寫出目標規(guī)劃的一般模型；2．試敘動態(tài)規(guī)劃的最優(yōu)性原理。三、已知某線性規(guī)劃問題的目標函數為max=5x1+3x2,約束形式為“≤”。設x3,x4為松弛變量，用單純形法計算是某一步的表格如下所示：（15分）Cj5300CBXBbx1x2x3x40x3c011/55x1de01-Z-10b-1fg（1）求a~g的值；（2）表中給出的解是否為最優(yōu)解，并求出最優(yōu)解。四、已知某線性規(guī)劃問題，其初始及最優(yōu)單純形表如下：（15分）Cj12000CBXBbX1x2x3x4x50x312221000x49300110x5802001σj12000最優(yōu)解表Cj12000CBXBBx1x2x3x4x51x12101/20-1/20x4300-3/213/22x2401001/2σj00-1/20-1/2(1)求出對偶問題的最優(yōu)解;(2)求C1的變化范圍,使最優(yōu)基不變;(3)如果b1由12變?yōu)?6,求最優(yōu)解.五、種機器可以在高低兩種不同的負荷下生產,高負荷生產時,產品的年產量g與投資的機器數量x的關系為:g(x)=8x,這時機器的年完好率a=0.7;在低負荷下生產時產品的年產量h和投入的機器數量y的關系為:h(x)=5y,這時機器的年完好率b=0.7。假定開始生產時的完好機器數量s1=1000臺，試制定一個5年計劃，確定每年投入高、低兩種負荷下生產的完好機器數量，使5年內產品的總產品量最大，并且5年末完好的機器數量是500臺。（1）寫出階段變量、狀態(tài)變量、決策變量；（6分）（2）寫出第k階段的決策集合與狀態(tài)轉移方程；（9分）（3）寫出遞推方程，并規(guī)范化求解。（選作10分）五、如圖所示是某地區(qū)交通運輸示意圖，s是起點t終點，弧旁數字為cij(fij)。（15分）（1）寫出此交通運輸規(guī)劃的線性規(guī)劃數學模型；（2）用標號法求出從s到t最大流及其流量；（3）寫出該網絡的最小割集。運籌學試卷(3)一、填空(11×3分)1、在線性規(guī)劃問題的約束方程AX=b,X≥0中，對于選定的基B，令非基變量XN=0，得到的解X=；若，則稱此基本解為基本可行解；若，則稱此基本可行解為退化的解。2、用單純形法求解線性規(guī)劃問題的迭代步驟中，根據σK=確定xk為進基變量；根據最小比值法則=，確定xr為出基變量。3、平衡運輸問題（m個產地，n個銷地）的基可行解中基變量共有個。4、對于Max型整數規(guī)劃問題，若其松弛問題的最優(yōu)單純形表中有一行數據為：XBbx1xxxx23/4017/4-11/4則對應的割平面方程為。5、用匈牙利法解分配問題時，當則找到了分配問題的最優(yōu)解；稱此時獨立零元素對應的效益矩陣為。6、將網絡D=(V,A,C)的頂點集合V分割成兩個非空集合V1和，使VS∈V1,Vt∈，則弧集成為分割VS和Vt的截集；稱為截集的容量。二、單項選擇題（3×5分）1、含有兩個變量的線性規(guī)劃問題若有可行解，則可行域是（）（A）全平面（B）多平面（C）凸多平面（D）凹多平面2、在目標線性規(guī)劃問題中，敘述正確的選項為（）（A）正偏差變量取正值，負偏差變量取負值；（B）目標規(guī)劃模型中，若模型有解，則一定有最優(yōu)解；（C）目標函數中的優(yōu)先級P1，P2，P3，……之間表明數量上的重要型差別，如：P1比P2級重要10倍或20倍等；（D）描寫可以含系統(tǒng)約束（剛性約束），也可以不含。3、下列敘述中，有關樹G（V，E）性質不正確的選項為（）（A）無圈且不連通；（B）n個頂點的樹必有n-1條邊；（C）樹中任意兩點，恰有一條初等鏈；（D）樹無回路，但不相鄰頂點連一條邊，恰得一回路。三、已知某線性規(guī)劃問題的目標函數為maxZ=5x1+3x2,約束形式為“≤”。設x3,x4為松弛變量，用單純形法計算是某一步的表如下所示：（15分）Cj5300CBXBBx1x2x3x40x32c011/55x1ade01Z-10b-1fg（1）求a~g的值；（2）表中給出的解是否為最優(yōu)解，并求出最優(yōu)解。四、已知某線性規(guī)劃問題，其初始及最優(yōu)單純形表如下：（15分）Cj12345CBXBbx1x2x3x4x50x312221000x49300100x5802001σj12000最優(yōu)解表Cj12000CBXBbx1x2x3x4x51x12101/20-1/20x4300-3/213/22x2401001/2σj00-1/20-1/2（1）求對偶問題的最優(yōu)解；（2）求C1的變化范圍，使最優(yōu)基不變；（3）如果b1由12變?yōu)?6，求最優(yōu)解。五、如圖所示是某地區(qū)交通運輸示意圖。VS是起點，Vt是終點。（12分）（1）求出從VS到Vt的最短距徑；（2）用雙箭頭在圖上標明。六、某物資每月需供應50箱，每次訂貨費為60元，每月每箱的存貯費為40元。（10分）（1）若不允許缺貨，且一訂貨就可以提貨，試問每隔多少時間訂購一次，每次應訂購多少箱？（2）若一個周期中缺一箱的缺貨損失費為40元，缺貨不補，問每隔多少時間訂購一次，每次應訂購多少箱？運籌學習題(4)一、知線性規(guī)劃問題（本題14分）minz=-5x1-6x2-7x3要求：（1）化為標準形式（7分）（2）列出用兩階段法求解時第一階段的初始單純形表（7分）。二、已知下表是某極大化線性規(guī)劃問題的初始單純形表和迭代計算中某一步的單純形表，試求出表中未知數a~l的值（每個1.5分，共18分）。x1x2x3x4x5x6X5205-413(b)10X68(j)-1(k)(c)01cj-zj16-7(a)00┇┇x3(d)-1/701-3/7(5)4/7X2(e)(l)10-3/7-5/7(g)cj-zj72/70011/7(k)(i)三、已知某一運輸問題的產銷平衡表、單位運價表如下表所示，且表中給出一個最優(yōu)調運方案（16分）。問：（1）從A2→B2的單位運價c22在什么范圍內變化時，上述最優(yōu)調運方案不變（8分）。（2）A2→B4的單位運價c24變?yōu)楹沃禃r，該運輸問題有無窮多最優(yōu)調運方案。（4分）除表中給出的方案外，至少再給出另兩個不同的最優(yōu)的方案。（4分）四、有十名研究生參加六門課程考試，由于每人研究方向不同，所選課程也不一樣，已知每名研究生要參加考試的課程如下表所示（表中打√的為參加考試的課程）（16分）?？荚嚢才旁?月18~20日連續(xù)三天，上、下午各考一門。每名研究生都要提出希望自己每天最多只參加一門課程考試。已知要求C課程安排在19日上午，D課程必須安排在下午考，F(xiàn)課的考試必須安排在B、E考試之后。要求排出一張滿足上述所有要求的考試日程表。上午下午1月18日1月19日1月20日五、見以下有向圖，圖中數字為兩點間距離（16分）。要求：（1）用動態(tài)規(guī)劃的方法求出A→D的最短路（8分）（2）若f2(B1)為從B1出發(fā)至D點的最短距離，寫出f2(B1)的動態(tài)規(guī)劃遞推方程的一般表達式，并具體說明遞推方程中每個符號的意義（8分）。六、選擇填充題（每題4分，共20分）（1）線性規(guī)劃問題minz=3x1+5x2已知其最優(yōu)解為x1=2,x2=6,z*=36,則其對偶問題的最優(yōu)解為.。.（①y1=3,y2=2,y3=0;②y1=0,y2=3/2,y3=1;③y1=0,y2=1,y3=4/3;④y1=3,y2=1,y3=2/3）（2）已知某個含10個節(jié)點的樹圖，其中9個節(jié)點的次（線度）為，1，1，3，1，1，1，3，1，3，則另一節(jié)點的次為。（①1；②4；③3；④2）（3）用標號法尋找網絡最大流時，發(fā)生標號中斷。這時若用V表示已標號的節(jié)點集合，用表示未標號的節(jié)點集合，則在網絡中所有V→方向的弧上有，→V方向的弧上有。（①f≥0;②f≤c;③f=c;④f=0）注：f為流量，c為弧的容量。運籌學習題(5)一、某投資者有30000元可供為期四年的投資?，F(xiàn)有下列五項投資機會可供選擇：A：四年內，投資者可在每年年初投資，每年每元投資可獲到0.2元，每年獲利后將本利重新投資。B：在四年內，投資者應在第一年年初或第三年年初投資，每兩年每元投資可獲利潤0.5元，兩年后獲利。然后可將本利再重新投資。C：在四年內，投資者應在第一年年初投資，三年后每元投資可獲利0.8元。獲利后可將本利重新投資。這項投資最多不超過20000元。D：在四年內，投資者應在第二年年初投資，兩年后每元投資可獲利0.6元。獲利后可將本利重新投資。這項投資最多不超過15000元。E：在四年內，投資者應在第一年年初投資，四年后每元投資可獲利1.7元。這項投資最多不超過20000元。投資者在四年內應如何投資，使他在四年后所獲利潤最大？寫出這個問題的線性規(guī)劃模型，不用求解。二、現(xiàn)要在五個工人中確定四個人來分別完成四項工作中的一項工作。由于每個工人的技術特長不同，他們完成各項工作所需的工時也不同。每個工人完成每項工作所需的工時如下表所示：試找出一個工作分配方案，使總工時最小。三、采用變量代換，試把非線形0-1整數規(guī)劃轉換成一個線形0-1整數規(guī)劃。五、設某公司擬將五臺設備分配給下屬的甲、乙、丙三個工廠。各工廠獲得這種設備后，可以為公司帶來的盈利如下表所示：問分配給各工廠多少臺這種設備，可以為公司帶來盈利的總和為最大。用動態(tài)規(guī)劃方法求解。（平分標準：每題都為20分）運籌學習題(6)一、多重選擇判斷（共5小題，每小題4分，共20分）下面5小題，每題有（a）(b)(c)(d)四項，你認為正確的打√，不正確的打×。答對者記1分，答錯者扣1分，不答者不記分。以小題為單位，每小題最高四分，最低0分，不記負分。1.形法求解標準型的線性規(guī)劃問題時(a)當所有檢驗數cj-zj≤0時，即可判定表中解即為最優(yōu)解；(b)為使目標函數值最快增長，必須選取與最大正檢驗數（ck-zk）對應變量xk為換為基的變量；(c)按最小比值原則確定換出基的變量是為了保證迭代計算后的解仍為基本可行解；(d)若存在σj=cj-zj>0，且該列系數PJ≤0，則線形問題最優(yōu)解不存在（無界解）2.線性規(guī)劃的原問題與其對偶問題之間存在如下關系(a)對偶問題的對偶問題是原問題；(b)原問題存在可行解，其對偶問題必存在可行解；(c)原問題可行解，其對偶問題必無可行解；(d)原問題有無窮多最優(yōu)解，其對偶問題也有無窮多最優(yōu)解。3.已知線性規(guī)劃問題則有（A）、（B）的兩對偶問題，各自最優(yōu)解y*z*與y′*,z′*間關系(a)y*=y′*,z*=z′*(b)y′*=2y*,z′*=z*(c)y′*=y*,z′*=2z*(d)(a)(b)(c)以外其他關系4.滿足下面條件的簡單圖G（V，E）是樹圖（a）無圈且連通；（b）有n個點和恰好（n-1）條邊；（c）圖中任意兩點間存在唯一的鏈；（d）G無圈，但只要加一條邊即得唯一的圈。5．在目標線性規(guī)劃問題中（a）正偏差變量取正值，負偏差變量取負值；（b）目標函數可以是求min。也可以求max；（c）目標函數中的優(yōu)先級P1，P2，P3…之間表明數量上的重要性差別，如P1比P2級重要10倍或20倍等；（d）模型可以含系統(tǒng)約束（剛性約束），也可以不含。6．判斷下列說法是否正確：（a）線性規(guī)劃問題的基本解對應可行域的頂點；（b）若X1，X2是某線性規(guī)劃問題的可行解，則X=λ1X1+λ2X2（其中λ1+λ2=1）也必是該問題的可行解；（c）線性規(guī)劃問題若存在可行解，其可行解集合為凸集；（d）若X1，X2是某線性規(guī)劃問題的最優(yōu)解，則X=λ1X1+（1+λ）X2(0≤λ≤1)也是該問題的最優(yōu)解。三、形規(guī)劃問題(本題20分，每小題5分)要求（a）以x1,x2為基變量，列出單純形表（當λ=0時）（b）若x1,x2為最優(yōu)基，確定問題最優(yōu)解不變時c3,c4的變化范圍；（c）保持最優(yōu)基不變時的λ的變化范圍；（d）增加一個新變量，其約束條件中系數量為（2,3）轉置，目標函數中系數為ck，求問題最優(yōu)解不變時ck取值范圍。四、已知運輸問題的產銷平衡表、單位運價表及某一調運方案如下（20分）產銷平衡表及調運方案要求：（a）以該調運方案對應的變量x11、x12、x23、x31、x33為基變量，列出該運輸問題用單純形法求解時的單純形表（8分）。（b）在單純形表上判斷方案是否最優(yōu)？若否，用單純形法繼續(xù)迭代求出最優(yōu)（8分）。（c）利用單純形表判斷A3→B3運費c33在什么范圍內變化，最優(yōu)解不變（4分）。解：增廣矩陣為五、由800萬元，分別用于3個項目的投資，按規(guī)定每個項目至少投資200萬元，最多投資400萬元，各項目得到不同投資時的預期效益如下表所示，要求確定使投資效益最大的各項目投資數（20分）。要求：（a）建立動態(tài)規(guī)劃模型，列出遞推關系式（基本方程），并說明方程中各符號的意義（10分）；（b）建立網絡模型，畫出網絡圖，簡要說明圖中點、線和權術的意義（10分）。運籌學習題（7）一、將下列線性規(guī)劃問題化為標準型（8分）minz=x1+2x2二、生產一項產品，其加工的某道工序可有兩種方案：采用設備A，平均加工時間為4分鐘，指數分布，設備費用為每小時2元；采用設備B，加工時間恰好為5分鐘，設備費用為每小時1.8元。產品以每小時8件的速度達到這一工序。產品在加工過程中每延誤一小時，對工廠將有3元的損失，問應選哪一種設備？（8分）三、某高架工程的作業(yè)明細表及有關資料如下表，試計算最低成本日程。工序代號緊前工序正常進度趕工進度每趕工一天需要的費用（元/天）工序時間（天）直接費用（元）工序時間（天）直接費用（元）a3101184ba7153191ca4122204dc51824242間接費用為每天4.5元。（10分）四、某產品的需要量為每周650單位，且均勻領出。訂購費為25元。每件產品的單位成本為3元，存貨保存成本為每單位每周0.05元。1）假定不允許缺貨，求多久訂購一次與每次應訂購數量。2）設缺貨成本每單位每周2元，求多久訂購一次與每次應訂購數量。3）可允許缺貨且設送貨延遲為一周，求多久訂購一次與每次應訂購數量。（共12分）五、見下圖，現(xiàn)準備在v1,v2,…,v7七個居民點中設置一工商銀行，各點之間的距離由附圖給出。問工商銀行設在哪個點，可使最大的服務距離為最??？若要設置兩個銀行，問設在哪兩個點。七、用三種固定要素（土地、勞動、機器）生產一產品M。已知該產品M價格每噸10美元，采用三種方法進行生產，每種方法的單位水平收入為1000美元。其投入系數與資源利用情況如下：問：1）求解此線性規(guī)劃問題。（5分）2）對所求解進行解釋。（5分）3）對其對偶解進行經濟解釋。（5分）4）證明勞動和土地之間的替代率（產量固定）等于要素價格比率。（7分）運籌學試卷（8）一、已知某線性規(guī)劃問題，其初始及最優(yōu)單純形表如下。（15分）初始表CBxB12000bx1x2x3x4x50x322100120x43001090x5020018σj12000最優(yōu)表1x1101/20-1/220x400-3/213/232x201001/24σj00-1/20-1/21.在求出對偶問題的最優(yōu)解。2.求出c1的變化范圍，使最優(yōu)基不變。3.如b1由12變?yōu)?6，求最優(yōu)解。二.、產品今后四周的需求量分別為300、700、900、600件，必須得到滿足。已知每件產品的成本在起初兩周是10元，以后兩周是15元，工廠每周能生產這種產品700件，且在第二、三周能加班生產。加班后，每周可增產200件產品，但成本每件增加5元。產品如不能在本周交貨，則每件每周存貯費是3元。問如何安排生產計劃，使總成本最小》（要求建立運輸問題數學模型，但不需求解）。（15分）三、一塊用堤埂粉腸很多小塊的水稻田，如附圖所示。為了即灌溉方便，需要挖開一些堤埂。問怎樣挖堤埂，才能使挖開處最少，又能使水流入每一小塊水稻田中？（15分）四、汽車按普拉阿松分布到達某高速公路收費口，平均每小時90輛。每輛車通過收費口平均需時35秒，服從負指數分布。為縮短收費等待時間，管理部門考慮采用自動收款裝置，這樣可使收費時間縮短到30秒。但采用的條件是原收費口平均等待車輛超過6輛，且新裝置的利用率不會低于75%。問新裝置能否被采用？（15分）五、已知標準的M/M/3隨機服務系統(tǒng)，平均每分鐘到達顧客約數為0.9人，每位顧客的平均服務時間約為2.5分鐘。求系統(tǒng)的服務強度ρ，并簡述其意義。（15分）六、假使某商品市場由A、B二家公司壟斷，競爭中一方所得為另一方的所失。二家公司分別制訂了五種未來經營策略。A公司的策略αi(i=1,2,…,5)、B公司的策略βj(j=1,2,…,5)以及A公司的預期的盈利矩陣A=（aij）,如下表所示。（15分）βjaijαiβ1β2β3β4β5α11310-2α244530α3-3320-2α450321α541443求雙方的最優(yōu)經營策略及競爭結果。七、用圖解法解目標規(guī)劃(10分)運籌學試卷（9）一、參數線性規(guī)劃問題（20分）maxz（θ1,θ2）=（5+2θ1）x1+(2-θ1)x2+(3+θ1)x3+0x4-Mx5-Mx6當θ1=θ2=0時，用單純形法求解，得最終單純形表如下x1x2x3x4x5x6x210312001x45-1021-11cj-zj-10-10-M-M-2要求：1.分析當θ2=0時，θ1在[0，∞]范圍內變化時最優(yōu)解的變化（8分）；2.分析當θ1=0時，θ2在[0，1]范圍內變化時最優(yōu)解的變化（8分）；3.將上述1、2的分析結果畫兩張圖，第一張以θ1為橫坐標，z(θ1)為縱坐標，第二張以θ2為橫坐標，z(θ2)為縱坐標，用以表示目標函數值隨參數θ1、θ2分別變化的規(guī)律（4分）。二、已知4種化工品A、B、C、D擬存放于7個庫房內，已知各化工品需存放量（噸），各庫存最大允許存放量（噸）及存放費用（元/噸·年）如下表所示。存放費用↘倉庫需存放量1234567化工品A122345575B233115550C443215525D11