261#——管理運(yùn)籌學(xué)

1、年級(jí)；層次；專業(yè)；姓名復(fù)習(xí)資料，僅供參考，補(bǔ)充整理打印，試后上交山東大學(xué)管理運(yùn)籌學(xué)課程試卷試卷一一、名詞解釋1. 可行解：滿足所有約束條件的解。2. 指標(biāo)函數(shù)：衡量全過(guò)程策略或k子過(guò)程策略優(yōu)劣的數(shù)量指標(biāo)。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. 可行解是滿足約束方程和非負(fù)條件的解。（）2.線性規(guī)劃問(wèn)題的最優(yōu)解如果存在一定是唯一的。（）3. 狀

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

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

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

5、的始點(diǎn)開(kāi)始，按順序計(jì)算出每個(gè)工序的最早開(kāi)始時(shí)間(ES)和最早結(jié)束時(shí)間(EF)；(3)從網(wǎng)絡(luò)的終點(diǎn)開(kāi)始，計(jì)算出在不影響整個(gè)工程最早結(jié)束時(shí)間的情況下，各個(gè)工序的最晚開(kāi)始時(shí)間(縮寫(xiě)為L(zhǎng)S)和最晚結(jié)束時(shí)間(縮寫(xiě)為L(zhǎng)F)；(4)計(jì)算出每一個(gè)工序的時(shí)差TS；(5)時(shí)差等于零的工序?yàn)殛P(guān)鍵工序。把關(guān)鍵工序依次從始點(diǎn)到終點(diǎn)連接成的路線確定為關(guān)鍵線路。三、計(jì)算題1. 解：(1)加入松弛變量x,x得到該線形規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型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管理運(yùn)籌學(xué)試卷二一、名詞解釋1. 最優(yōu)解：在可行域中使目標(biāo)函數(shù)達(dá)到最優(yōu)的可行解。2. 策略：一個(gè)按時(shí)間或空間次序排列的決策序列的集合。5. 連通圖：任何兩點(diǎn)之間至少存在一條鏈的圖稱為連通圖。6. 增廣鏈：f為一可行流，u為vs至vt的鏈，令u+=正向弧，u-=反向弧。若u+中弧皆非飽，且u-中弧皆非零，則稱u為關(guān)于f的一條增廣鏈。

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

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

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

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

11、路。三、計(jì)算題1.解：（1）加入松弛變量x,x,x得到該線形規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型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管理運(yùn)籌學(xué)試卷三一、名詞解釋1. 可行域：所有可行解的集合。2. 策略：

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

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

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

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