261#——管理運籌學

1、年級；層次；專業(yè)；姓名復習資料，僅供參考，補充整理打印，試后上交山東大學管理運籌學課程試卷試卷一一、名詞解釋1. 可行解：滿足所有約束條件的解。2. 指標函數(shù)：衡量全過程策略或k子過程策略優(yōu)劣的數(shù)量指標。3. 支撐子圖：圖G=（V,E）和G=（V；E，）,若V=V'且E'匸E，則稱G'為G的支撐子圖。4. 增廣鏈：f為一可行流，u為v至vt的鏈，令u+=正向弧，u-=反向弧。若u+中弧皆非飽，且u-中弧皆非零，則稱u為關(guān)于f的一條增廣鏈。5 最優(yōu)解6 非劣解二、判斷題1. 可行解是滿足約束方程和非負條件的解。（）2.線性規(guī)劃問題的最優(yōu)解如果存在一定是唯一的。（）3. 狀

2、態(tài)變量滿足無后效性是指系統(tǒng)從某階段往后的發(fā)展，完全由本階段所處的狀態(tài)及其之后的決策決定，與系統(tǒng)以前的狀態(tài)和決策無關(guān)。（）4. 決策樹是一種由結(jié)點和分支構(gòu)成的由左向右展開的樹狀圖形。（）三、選擇題1. 判斷線性規(guī)劃模型是否有最優(yōu)解主要是根據(jù)（）A.非基變量的檢驗數(shù)是否大于0B.基變量的檢驗數(shù)是否大于0C.非基變量的檢驗數(shù)是否小于等于0D.基變量的檢驗數(shù)是否小于等于02. 目標規(guī)劃的目標函數(shù)的基本形式是（）A.minz=f（d+,d-）B.minz=f（d+）C.minz=f（d-）D.maxz=f（d+,d-）3. 目標規(guī)劃的解是（）A.非劣解B.最優(yōu)解C.滿意解D.可行解4. 整數(shù)規(guī)劃解的特點

3、是（）A.最優(yōu)解不一定在頂點上達到B.最優(yōu)解不一定是松弛問題最優(yōu)解的鄰近整數(shù)解C. 整數(shù)規(guī)劃的最大函數(shù)值小于或等于相應的線性規(guī)劃的最大目標函數(shù)值D. 整數(shù)規(guī)劃的最小目標函數(shù)值大于或等于相應的線性規(guī)劃的最小目標函數(shù)值二、簡答題1. 簡述單純形法的基本步驟；答：（1）把一般線形規(guī)劃模型轉(zhuǎn)換成標準型；（2）確定初始基可行解；（3）利用檢驗數(shù)b對初始基可行解進行最優(yōu)性檢驗，若W0，則求得最優(yōu)解,jj否則，進行基變換；（4）基變換找新的可行基，通過確定入基變量和出基變量，求得新的基本可行解；（5）重復步驟（3）、（4）直至b<0，求得最優(yōu)j解為止。年級；層次；專業(yè)；姓名復習資料，僅供參考，補充整理

4、打印，試后上交復習資料，僅供參考，補充整理打印，試后上交1. 簡述整數(shù)規(guī)劃解的特點；2. 簡述動態(tài)規(guī)劃的基本方程；答：對于n階段的動態(tài)規(guī)劃問題，在求子過程上的最優(yōu)指標函數(shù)時，k子過程與k+1過程有如下遞推關(guān)系：對于可加性指標函數(shù)，基本方程可以寫為f(s)=OPtr(s,x)+f(s)k=1,2,nkkkkkk+1k+1xwD(s)終端條件：fn+1(sn+1)=0對于可乘性指標函數(shù)，基本方程可以寫為f(s)=optr(s,x)Xf(s)k=1,2,nkkkkkk+1k+1xkwDk(sk)終端條件：fn+1(sn+1)=13. 如何找計劃網(wǎng)絡圖的關(guān)鍵路線？答：(1)繪制計劃網(wǎng)絡圖；(2)從網(wǎng)絡

5、的始點開始，按順序計算出每個工序的最早開始時間(ES)和最早結(jié)束時間(EF)；(3)從網(wǎng)絡的終點開始，計算出在不影響整個工程最早結(jié)束時間的情況下，各個工序的最晚開始時間(縮寫為LS)和最晚結(jié)束時間(縮寫為LF)；(4)計算出每一個工序的時差TS；(5)時差等于零的工序為關(guān)鍵工序。把關(guān)鍵工序依次從始點到終點連接成的路線確定為關(guān)鍵線路。三、計算題1. 解：(1)加入松弛變量x,x得到該線形規(guī)劃問題的標準型34maxz二2x+x123x+5x+x二15123<6x+2x+x二24124x,x,x,x>012342)利用單純形表逐步迭代Cj2100比值CBXBbx1X2X3X40X3153

6、51050X42462014oj21000X33041-1/23/42X1411/301/612oj01/30-1/31X23/4011/4-1/82X115/410-1/125/24j00-1/12-7/24最優(yōu)解X*二(15/4,3/4,0,0)T,Z*=33/4管理運籌學試卷二一、名詞解釋1. 最優(yōu)解：在可行域中使目標函數(shù)達到最優(yōu)的可行解。2. 策略：一個按時間或空間次序排列的決策序列的集合。5. 連通圖：任何兩點之間至少存在一條鏈的圖稱為連通圖。6. 增廣鏈：f為一可行流，u為vs至vt的鏈，令u+=正向弧，u-=反向弧。若u+中弧皆非飽，且u-中弧皆非零，則稱u為關(guān)于f的一條增廣鏈。

7、7. 指標函數(shù)8.非劣解二、判斷題1. 目標規(guī)劃中的解一定是最優(yōu)解。()2.線性規(guī)劃問題的最優(yōu)解如果存在一定是唯一的。()3. 狀態(tài)變量滿足無后效性是指系統(tǒng)從某階段往后的發(fā)展，完全由本階段所處的狀態(tài)及其之后的決策決定，與系統(tǒng)以前的狀態(tài)和決策無關(guān)。()4. 決策樹是一種由結(jié)點和分支構(gòu)成的由左向右展開的樹狀圖形。()三、選擇題1. 判斷線性規(guī)劃模型是否有最優(yōu)解主要是根據(jù)()A.非基變量的檢驗數(shù)是否大于0B.基變量的檢驗數(shù)是否大于0C.非基變量的檢驗數(shù)是否小于等于0D.基變量的檢驗數(shù)是否小于等于02. 目標規(guī)劃的目標函數(shù)的基本形式是()A.minz=f(d+,d-)B.minz=f(d+)C.min

8、z=f(d-)D.maxz=f(d+,d-)3. 目標規(guī)劃的解是()A.非劣解B.最優(yōu)解C.滿意解D.可行解4. 整數(shù)規(guī)劃解的特點是()A.最優(yōu)解不一定在頂點上達到B.最優(yōu)解不一定是松弛問題最優(yōu)解的鄰近整數(shù)解C. 整數(shù)規(guī)劃的最大函數(shù)值小于或等于相應的線性規(guī)劃的最大目標函數(shù)值D. 整數(shù)規(guī)劃的最小目標函數(shù)值大于或等于相應的線性規(guī)劃的最小目標函數(shù)值復習資料，僅供參考，補充整理打印，試后上交二、簡答題1. 答：（1）把一般線形規(guī)劃模型轉(zhuǎn)換成標準型；（2）確定初始基可行解；（3）利用檢驗數(shù)b對初始基可行解進行最優(yōu)性檢驗，若W0，則求得最優(yōu)解,jj否則，進行基變換；（4）基變換找新的可行基，通過確定入基變

9、量和出基變量，求得新的基本可行解；（5）重復步驟（3）、（4）直至b<0，求得最優(yōu)j解為止。2. 簡述分枝定界法的基本思想。答：分枝定界法是先求解整數(shù)規(guī)劃的線性規(guī)劃問題。如果其最優(yōu)解不符合整數(shù)條件，則求出整數(shù)規(guī)劃的上下界，用增加約束條件的辦法，把相應的線性規(guī)劃的可行域分成子區(qū)域（稱為分枝），再求解這些子區(qū)域上的線性規(guī)劃問題，不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃的最優(yōu)解。3. 簡述動態(tài)規(guī)劃的基本方程答：對于n階段的動態(tài)規(guī)劃問題，在求子過程上的最優(yōu)指標函數(shù)時，k子過程與k+1過程有如下遞推關(guān)系：對于可加性指標函數(shù)，基本方程可以寫為f（s）=OPtr（s,x）+f（s）k=1,2,n

10、kkkkkk+1k+1xgD（s）終端條件：fn+1（sn+1）=0對于可乘性指標函數(shù)，基本方程可以寫為f（s）=optr（s,x）Xf（s）k=1,2,nkkkkkk+1k+1xkgDk（sk）終端條件：fn+1（sn+1）=14答：（1）繪制計劃網(wǎng)絡圖；（2）從網(wǎng)絡的始點開始，按順序計算出每個工序的最早開始時間（ES）和最早結(jié)束時間（EF）；（3）從網(wǎng)絡的終點開始，計算出在不影響整個工程最早結(jié)束時間的情況下，各個工序的最晚開始時間（縮寫為LS）和最晚結(jié)束時間（縮寫為LF）；（4）計算出每一個工序的時差TS；（5）時差等于零的工序為關(guān)鍵工序。把關(guān)鍵工序依次從始點到終點連接成的路線確定為關(guān)鍵線

11、路。三、計算題1.解：（1）加入松弛變量x,x,x得到該線形規(guī)劃問題的標準型345maxz二2x+5x12x+x=4132 x+x=12243 x+2x+x=18125x,x,x,x12342）利用單純形表逐步迭代Cj25000比值CBXBbx1X2X3X4X50X3410100-0X4120201060X518320019j250000X341010045X260101/20-0X56300-112j200-5/200X320011/3-1/35X260101/202X12100-1/31/3oj000-11/6-2/3管理運籌學試卷三一、名詞解釋1. 可行域：所有可行解的集合。2. 策略：

12、一個按時間或空間次序排列的決策序列的集合。3. 連通圖：任何兩點之間至少存在一條鏈的圖稱為連通圖。4.截量：截集上的容量和稱為截量，記為C(V1,V2)。5、指標函數(shù)6、非劣解二、判斷題1.目標規(guī)劃中的解一定是最優(yōu)解。()2.線性規(guī)劃問題的最優(yōu)解如果存在一定是唯一的。()3. 狀態(tài)變量滿足無后效性是指系統(tǒng)從某階段往后的發(fā)展，完全由本階段所處的狀態(tài)及其之后的決策決定，與系統(tǒng)以前的狀態(tài)和決策無關(guān)。()4. 決策樹是一種由結(jié)點和分支構(gòu)成的由左向右展開的樹狀圖形。()三、選擇題1. 判斷線性規(guī)劃模型是否有最優(yōu)解主要是根據(jù)()A.非基變量的檢驗數(shù)是否大于0B.基變量的檢驗數(shù)是否大于0C.非基變量的檢驗數(shù)

13、是否小于等于0D.基變量的檢驗數(shù)是否小于等于02. 目標規(guī)劃的目標函數(shù)的基本形式是()A.minz=f(d+,d-)B.minz=f(d+)C.minz=f(d-)D.maxz=f(d+,d-)3. 目標規(guī)劃的解是()A.非劣解B.最優(yōu)解C.滿意解D.可行解4. 整數(shù)規(guī)劃解的特點是()A.最優(yōu)解不一定在頂點上達到B.最優(yōu)解不一定是松弛問題最優(yōu)解的鄰近整數(shù)年級；層次；專業(yè)；姓名復習資料，僅供參考，補充整理打印，試后上交解C. 整數(shù)規(guī)劃的最大函數(shù)值小于或等于相應的線性規(guī)劃的最大目標函數(shù)值D. 整數(shù)規(guī)劃的最小目標函數(shù)值大于或等于相應的線性規(guī)劃的最小目標函數(shù)值二、簡答題1.簡述單純形法的基本步驟答：（

14、1）把一般線形規(guī)劃模型轉(zhuǎn)換成標準型；（2）確定初始基可行解；（3）利用檢驗數(shù)b對初始基可行解進行最優(yōu)性檢驗，若Q<0，則求得最優(yōu)解,jj否則，進行基變換；（4）基變換找新的可行基，通過確定入基變量和出基變量，求得新的基本可行解；（5）重復步驟（3）、（4）直至b<0，求得最優(yōu)j解為止。2. 簡述分枝定界法的基本思想。答：分枝定界法是先求解整數(shù)規(guī)劃的線性規(guī)劃問題。如果其最優(yōu)解不符合整數(shù)條件，則求出整數(shù)規(guī)劃的上下界，用增加約束條件的辦法，把相應的線性規(guī)劃的可行域分成子區(qū)域（稱為分枝），再求解這些子區(qū)域上的線性規(guī)劃問題，不斷縮小整數(shù)規(guī)劃的上下界的距離，最后得整數(shù)規(guī)劃的最優(yōu)解。3. 答：（

15、1）最優(yōu)解不一定在頂點上達到；（2）最優(yōu)解不一定是松弛問題最優(yōu)解的鄰近整數(shù)解；（3）整數(shù)可行解遠多余于頂點，枚舉法不可?。唬?）整數(shù)規(guī)劃的最大函數(shù)值小于或等于相應的線性規(guī)劃的最大目標函數(shù)值；（5）整數(shù)規(guī)劃的最小目標函數(shù)值大于或等于相應的線性規(guī)劃的最小目標函數(shù)值。4答：（1）繪制計劃網(wǎng)絡圖；（2）從網(wǎng)絡的始點開始，按順序計算出每個工序的最早開始時間（ES）和最早結(jié)束時間（EF）；（3）從網(wǎng)絡的終點開始，計算出在不影響整個工程最早結(jié)束時間的情況下，各個工序的最晚開始時間（縮寫為LS）和最晚結(jié)束時間（縮寫為LF）；（4）計算出每一個工序的時差TS；（5）時差等于零的工序為關(guān)鍵工序。把關(guān)鍵工序依次從始點到終點連接成的路線確定為關(guān)鍵線路。三、計算題1.解：(1)加入人工變量x,x，減去剩余變量x得到該線形規(guī)劃問題的標準465型maxz=2x+3x一5x一Mx-Mx12346x+x+x+x=71234<2x一5x+x一x+x=1012356x,x,x,x,x,x>0123456(2)利用單純形表逐步迭代年級；層次；專業(yè)；姓名復習資料，僅供參考，補充整理打印，試后上交C.j23-5-M0-M比值CBXBbX1X2X3X4X5X6-MX471111007-MX6102-510-115oj3M+23-4M2M-50-M0-MX4207/