天津大學(xué)運(yùn)籌學(xué)考研歷年試題分類.doc

《天津大學(xué)運(yùn)籌學(xué)考研歷年試題分類.doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《天津大學(xué)運(yùn)籌學(xué)考研歷年試題分類.doc（87頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、一、線性規(guī)劃二、運(yùn)輸問題三、多目標(biāo)規(guī)劃四、動(dòng)態(tài)規(guī)劃五、圖論六、網(wǎng)絡(luò)計(jì)劃技術(shù)七、決策論八、存儲(chǔ)論九、排隊(duì)論十、對(duì)策論十一、模擬技術(shù)一、線性規(guī)劃（一）選擇填空題 （二）線性規(guī)劃建模 （三）互補(bǔ)松弛應(yīng)用 （四）靈敏度分析 （五）證明題（一）選擇填空題1下面給出某線性規(guī)劃問題的單純形初表和終表（Min型）：CB XB B-1b0 1 -3 0 2 0 x1 x2 x3 x4 x5 x60 x1 70 x4 120 x6 101 3 -1 0 2 00 -2 4 1 0 00 -4 3 0 8 1 j CB XB B-1bx1 x2 x3 x4 x5 x6 x2 x6 2/5 0 1/10 01/5 1

2、 3/10 01 0 -1/2 1 j (1)初表的出基變量為，進(jìn)基變量為。(3)填完終表。(6)若原問題增加一個(gè)新的非負(fù)變量，則對(duì)偶問題的最優(yōu)目標(biāo)值將（變大、不變、變?。?。（2007）解：1(1)出基變量為x4；進(jìn)基變量為x3。 (2)。(3)CB XB B-1bx1 x2 x3 x4 x5 x61 x2 4-3 x3 5 0 x6 112/5 1 0 1/10 4/5 01/5 0 1 3/10 2/5 01 0 0 -1/2 10 1 j1/5 0 0 4/5 12/5 0 (4) (5) (6) 變小1用圖解法解線性規(guī)劃時(shí)，以下幾種情況中不可能出現(xiàn)的是（ ）。A可行域（約束集合）有界，

3、無有限最優(yōu)解（或稱無解界） B可行域（約束集合）無界，有唯一最優(yōu)解C可行域（約束集合）是空集，無可行解D可行域（約束集合）有界，有多重最優(yōu)解 （2006） 解：1 A2根據(jù)線性規(guī)劃的互補(bǔ)松弛定理，安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本一定（ ）利潤。 A 小于 B 等于 C 大于 D 大于等于 （2006）解：2 B1用大M法求解Max型線形規(guī)劃時(shí)，人工變量在目標(biāo)函數(shù)中的系數(shù)均為_，若最優(yōu)解的_中含有人工變量，則原問題無解。（2005）解：1、-M 基變量1. 設(shè)線性規(guī)劃問題有最優(yōu)解和影子價(jià)格,則線性規(guī)劃問題的最優(yōu)解= ，影子價(jià)格= 。（2004）解：1. x* 2y*3. 某工程公司擬從1、2、3、4四個(gè)項(xiàng)

4、目中選擇若干項(xiàng)目。若令請(qǐng)用的線性表達(dá)式表示下列要求：（1）若項(xiàng)目2被選中，則項(xiàng)目4不能被選中： （2）只有項(xiàng)目1被選中，項(xiàng)目3才能被選中： 。（2004）解：3. 一、簡(jiǎn)答（18%） （1）請(qǐng)簡(jiǎn)述影子價(jià)格的定義。 （2）在使用單純型表求解型線性規(guī)劃時(shí)，資源的影子價(jià)格在單純型表的什么位置上？ （3）寫出影子價(jià)格的數(shù)學(xué)表達(dá)式并用其定義加以驗(yàn)證 （4）試述運(yùn)輸問題中檢驗(yàn)數(shù)的經(jīng)濟(jì)意義（2003）解：一、簡(jiǎn)答當(dāng)各資源增加一單位時(shí)引起的總收入的增量，影子價(jià)格大于零的資源一定沒有剩余，有剩余一定為零。松弛變量檢驗(yàn)數(shù)的負(fù)值，對(duì)偶問題的最優(yōu)解。CBB-1B是原問題maxz=CXAXb,X0最優(yōu)基Z*= CBB-

5、1b=Y*bZ*=y1*b1+y2*b2ym*bm=y3*表明增加一個(gè)單位的運(yùn)量會(huì)引起總運(yùn)輸費(fèi)用的變化1 線性規(guī)劃原問題中約束的個(gè)數(shù)與其對(duì)偶問題中的 變量 個(gè)數(shù)相等。若原問題第j個(gè)約束為等式，則對(duì)偶問題第j個(gè) 變量 自由。（2002）解：2 設(shè)線性規(guī)劃問題max:cx|Axbx0有最優(yōu)解，且最優(yōu)解值z(mì)0；如果c和b分別被v1所乘，則改變后的問題 也有 （也有、不一定有）最優(yōu)解；若有最優(yōu)解，其最優(yōu)解 大于 (大于、小于、等于)z。（2002）1下列數(shù)學(xué)模型中 a 是線性規(guī)劃模型。(2001)解：2下列圖形（陰影部分）中 b 是凸集。(2001) （a） （b） （c）解：3標(biāo)準(zhǔn)形式的線性規(guī)劃問題

6、，其可行解 b 是基本可行解，最優(yōu)解 a 是可行解，最優(yōu)解 a 能在可行域的某頂點(diǎn)達(dá)到。(2001)（a）一定 （b）不一定 （c）一定不解：4目標(biāo)函數(shù)取極小（min Z）的線性規(guī)劃問題可以轉(zhuǎn)化為目標(biāo)函數(shù)取極大 b 的線性規(guī)劃問題求解，原問題的目標(biāo)函數(shù)值等于 c 。(2001)（a）max Z （b）max（-Z） （c）-max（-Z） （d）-max Z（a）最小元素法 （b）比回路法1. 線性規(guī)劃單純形算法的基本步驟是：（1） （2） (3) 每次迭代保持解的 ，改善解值的 。對(duì)偶單純形法每次迭代保持解的 ，改善解值的 。（2000）解：確定一個(gè)初始基可行解；檢驗(yàn)一個(gè)基可行解是否為最優(yōu)解

7、；尋找一個(gè)更好基可行解；可行性；最優(yōu)性。2. 設(shè)有線性規(guī)劃問題，有一可行基B（為A中的前m列），記相應(yīng)基變量為，價(jià)格系數(shù)為CB，相應(yīng)于非基變量為XN，價(jià)格系數(shù)為CN，則相應(yīng)于B的基本可行解為X= ；用非基變量來表示基變量的表達(dá)式為XB= ；用非基變量表示目標(biāo)函數(shù)的表達(dá)式為f= ，B為最優(yōu)基的條件是 。（2000）解：3. 線性規(guī)劃（Min型）問題有多重最優(yōu)解時(shí)，其最優(yōu)單純形表上的特征為： （2000）解：6. 某足球隊(duì)要從1，2，3，4，5號(hào)五名隊(duì)員中挑選若干名上場(chǎng)。令請(qǐng)用xi的線性表達(dá)式表示下列要求：（1）從1，2，3中至多選2名： （2）如果2號(hào)和3號(hào)都上場(chǎng)，則5號(hào)不上場(chǎng)： （3）只有4號(hào)

8、上場(chǎng),1號(hào)才上場(chǎng)：(2000)解：1某工程公司擬從四個(gè)項(xiàng)目中選擇若干項(xiàng)目，若令請(qǐng)用xi的線性表達(dá)式表示下列要求：（1）從1，2，3項(xiàng)目中至少選擇一個(gè)： ，（2）只有項(xiàng)目2被選中，項(xiàng)目4才能被選中 。（1999）解：1、x1+x2+x31 x2x42考慮線形規(guī)劃問題用單純型法求解，得其終表如下：Cj5 12 4 0 -MCB XB B-1bx1 x2 x3 x4 x512 x2 8/55 x1 9/50 1 -1/5 2/5 -1/51 0 7/5 1/5 2/5j0 0 -3/5 -29/5 -M+其中x4位松弛變量，x5為人工變量。（1）上述模型的對(duì)偶模型為 ，（2）對(duì)偶模型的最優(yōu)解為 ，（

9、3）當(dāng)兩種資源分別單獨(dú)增加一個(gè)單位時(shí)，目標(biāo)函數(shù)值分別增加 和 ，（4）最優(yōu)基的逆矩陣（5）如果原問題增加一個(gè)變量，則對(duì)偶問題的可行域?qū)⒖赡茏兇筮€是變?。浚?999）解：2（1）（2）Y*=（，-）（3），-（4）（5）變小1下面給出某線形規(guī)劃的單純形初表（表1）與某一中間表（表2）（Min型）： 表1CB XB B-1b 0 1 -3 0 2 0 x1 x2 x3 x4 x5 x60 x1 70 x4 120 x6 10 1 3 -1 0 2 0 0 -2 4 1 0 0 0 -4 3 0 8 1 表2 x2 x62/5 0 1/10 4/5 1/5 1 3/10 2/5 1 0 -1/2 1

10、01) 初表的出基變量為_，進(jìn)基變量為_。2) 填完表2，該表是否是終表?_。若是，最優(yōu)值_3) 此線形規(guī)劃對(duì)偶問題的最優(yōu)解_(1998)解：1.下面給出某線形規(guī)劃的單純形初表（表1）與某一中間表（表2）（Min型）： 表1CB XB B-1b 0 1 -3 0 2 0 x1 x2 x3 x4 x5 x60 x1 70 x4 120 x6 10 1 3 -1 0 2 0 0 -2 4 1 0 0 0 -4 3 0 8 1 0 1 -3 0 2 0 表21 x2 4-3 x3 50 x6 112/5 1 0 1/10 4/5 01/5 0 1 3/10 2/5 01 0 0 -1/2 10 1

11、1/5 0 0 4/5 12/5 04) 初表的出基變量為_x4_，進(jìn)基變量為_x3_。5) 填完表2，該表是否是終表?_是_。若是，最優(yōu)值_-11_此線形規(guī)劃對(duì)偶問題的最優(yōu)解解：解：解：解：解：解：（二）線性規(guī)劃建模二（20分）、某化學(xué)制藥廠有m種有害副產(chǎn)品，它們的數(shù)量為bi（i=1，m）。按照規(guī)定，必須經(jīng)過處理，制成n種無害物后才能廢棄。設(shè)aij為每制成一單位第j（j=1，n）種無害物可以處理掉第i種有害物的數(shù)量，cj為制成一單位第j種無害物的費(fèi)用。1 現(xiàn)欲求各無害物的產(chǎn)量xj以使總的處理費(fèi)用為最小，請(qǐng)寫出此問題的線性規(guī)劃模型；2 寫出此問題的對(duì)偶規(guī)劃模型，并解釋對(duì)偶規(guī)劃模型的經(jīng)濟(jì)意義。（

12、2007）解：12經(jīng)濟(jì)意義：為第i種有害副產(chǎn)品不經(jīng)處理直接廢棄的費(fèi)用。二（10%）、某大型企業(yè)每年需要進(jìn)行多種類型的員工培訓(xùn)。假設(shè)共有需要培訓(xùn)的需求（如技術(shù)類、管理類）為6種，每種需求的最低培訓(xùn)人數(shù)為ai，i=1,6, 可供選擇的培訓(xùn)方式（如內(nèi)部自行培訓(xùn)、外部與高校合作培訓(xùn)）有5種，每種的最高培訓(xùn)人數(shù)為bj, j=1,5。又設(shè)若選擇了第1種培訓(xùn)方式，則第3種培訓(xùn)方式也要選擇。記xij為第i種需求由第j方式培訓(xùn)的人員數(shù)量，z為培訓(xùn)總費(fèi)用。費(fèi)用的構(gòu)成包括固定費(fèi)用和可變費(fèi)用，第j種方式的固定費(fèi)用為hj（與人數(shù)無關(guān)），與人數(shù)xij相應(yīng)的可變費(fèi)用為cij（表示第j方式培訓(xùn)第i種需求類型的單位費(fèi)用）。如果

13、以成本費(fèi)用為優(yōu)化目標(biāo)，請(qǐng)建立該培訓(xùn)問題的結(jié)構(gòu)優(yōu)化模型（不解）。（2006）解：二、1.某廠使用A、B兩種原料生產(chǎn)甲、乙、丙三種產(chǎn)品，有關(guān)數(shù)據(jù)見下表： A B 生產(chǎn)成本（萬元/噸）銷售價(jià)格（萬元/噸） 甲 乙 丙1.0 0.50.4 0.60.6 0.5 8 5 18 30 20 35原料成本（萬元/噸）5 7原料可用數(shù)量（噸）350 460（1）請(qǐng)寫出使總銷售利潤最大的線性規(guī)劃模型（其中甲、乙、丙產(chǎn)產(chǎn)量分別記為x1,x2,x3,約束依A,B原料次序）: (2)寫出此問題的對(duì)偶規(guī)劃模型（2003）解：maxz=30 x1+20 x2+35x3-8x1-5x2-18x3-5(x1+0.4x2+0.

14、6x3)-7(0.5x1+0.6x2+0.5x3)目標(biāo)函數(shù)maxz=13.5x1+8.8x2+10.5x3約束條件 x1+0.4x2+0.6x3350 0.5x1+0.6x2+0.5x3460 x10,x20,x30 對(duì)偶規(guī)劃模型目標(biāo)函數(shù) minw=350y1+460y2約束條件y1+0.5y213.5 0.4y1+0.6y28.8 0.6y1+0.5y210.5 y10,y20三、（10%）某服裝廠制造大、中、小三種尺寸的防寒服，所用資源有尼龍綢、尼龍棉、勞動(dòng)力和縫紉設(shè)備?？p制一件防寒服所需各種資源的數(shù)量如表（單位已適當(dāng)給定）。不考慮固定費(fèi)用，則每種防寒服售出一件所得利潤分別為10、12、1

15、3元，可用資源分別為：尼龍綢1500米，尼龍棉1000米，勞動(dòng)力4000，設(shè)備3000小時(shí)。此外，每種防寒服不管縫制多少件，只要做都要支付一定的固定費(fèi)用：小號(hào)為100元，中號(hào)為150元，大號(hào)為200元?，F(xiàn)欲制定一生產(chǎn)計(jì)劃使獲得的利潤為最大，請(qǐng)寫出其數(shù)學(xué)模型（不解）。(2002) 型號(hào)資源小中大尼龍綢161819尼龍棉131516勞動(dòng)力4455縫紉設(shè)備283842解：三、解：設(shè)三種防寒服分別生產(chǎn)x1,x2,x3件。z表示獲得的利潤,y1,y2,y3分別表示0-1變量，yi=1表示做第xi種防寒服（i=1,2,3）（三）互補(bǔ)松弛應(yīng)用二（8%）、線性規(guī)劃問題已知其最優(yōu)解x1，x2 0，而第1，4兩種

16、資源（相應(yīng)于第1，4兩約束）均有余量，應(yīng)用互補(bǔ)松弛定理求出原問題和對(duì)偶問題的最優(yōu)解。（2005）解：二 對(duì)偶問題 （*） 代入（*）式， 由綜上，原問題最優(yōu)解 對(duì)偶問題最優(yōu)解（四）靈敏度分析三（25%）、派公司是一個(gè)生產(chǎn)高爾夫器材的小型公司，近期推出了高、中價(jià)位的高爾夫袋新產(chǎn)品（標(biāo)準(zhǔn)袋和高檔袋），經(jīng)銷商對(duì)此產(chǎn)品十分感興趣，并訂購了派公司下3個(gè)月的全部產(chǎn)品。該高爾夫袋的生產(chǎn)過程主要包括4道工序：切割并印染原材料、縫合、成型（插入支撐架和球棒分離裝置等）、檢驗(yàn)和包裝。有關(guān)數(shù)據(jù)如表1。派公司須決定標(biāo)準(zhǔn)袋和高檔袋各生產(chǎn)多少可使公司的總利潤最大。表1時(shí)間單耗 產(chǎn)品 （小時(shí)）工序標(biāo)準(zhǔn)袋 高檔袋3個(gè)月內(nèi)最大

17、生產(chǎn)能力（小時(shí)）切割印染7/10 1630縫合 1/2 5/6 600成型 1 2/3 708檢驗(yàn)包裝 1/10 1/4 135產(chǎn)品單位利潤（美元） 10 9 (1) 寫出此問題的線性規(guī)劃模型，約束依表1中次序；(2) 引入松弛變量（依約束次序）后用單純形法計(jì)算得某單純形表如表2，請(qǐng)?zhí)钔瓯碇锌瞻?，并判斷其是否終表，如果是，請(qǐng)寫出最優(yōu)生產(chǎn)計(jì)劃、最大利潤和資源剩余；表2CB XB B-1b10 9 0 0 0 0 x1 x2 x3 x4 x5 x6 9 x2 252 0 x4 12010 x1 540 0 x6 181 1.875 0 -1.3125 00 -0.9375 1 0.15625 00

18、 -1.25 0 1.875 00 -0.34375 0 0.140625 1 -6.9375(3) 寫出此問題的對(duì)偶問題的模型，及對(duì)偶的最優(yōu)解與最優(yōu)值；(4) 寫出成型時(shí)間的影子價(jià)格，求使該影子價(jià)格不變的成型時(shí)間的變化范圍；(5) 若標(biāo)準(zhǔn)袋的利潤可能發(fā)生變化，則其在何范圍內(nèi)變化時(shí)，可使原最優(yōu)計(jì)劃不改變？圖示說明其幾何意義。（2005）解：三 設(shè)標(biāo)準(zhǔn)袋生產(chǎn),高檔袋生產(chǎn) （1） （2）10 9 0 0 0 0 9 x2 2520 x4 12010 x1 5400 x6 180 1 1.875 0 -1.3125 00 0 -0.9375 1 0.15625 01 0 -1.25 0 1.875

19、00 0 -0.34375 0 0.140625 1 0 0 -4.375 0 -6.9375 0 是終表最優(yōu)生產(chǎn)計(jì)劃，即普通袋540個(gè)，高檔袋252個(gè)最大利潤Z (美元)（3）對(duì)偶問題模型：對(duì)偶問題最優(yōu)解：由對(duì)偶問題的強(qiáng)對(duì)偶性知，對(duì)偶問題與原問題的最優(yōu)值相同W*=Z*=7668 (美元)（4）成型時(shí)間影子價(jià)格為6.9375（5）變化，可能影響檢驗(yàn)數(shù)，故令二（23%）、某公司生產(chǎn)家用的清潔產(chǎn)品，為了在高度的市場(chǎng)競(jìng)爭(zhēng)中增加市場(chǎng)份額，公司決定進(jìn)行一次大規(guī)模的廣告行動(dòng)。表1給出了公司準(zhǔn)備做廣告的三種產(chǎn)品名稱、估計(jì)每做一單位廣告（一個(gè)廣告標(biāo)準(zhǔn)批量）使每種產(chǎn)品的市場(chǎng)份額增加量、公司擬定的廣告后每種產(chǎn)品市

20、場(chǎng)份額增加量的最低目標(biāo)和兩種可選的廣告方式的單價(jià)。表1單位增量 廣告種類產(chǎn)品電視印刷媒體廣告后市場(chǎng)份額最低增量去污劑0%1%3%液體洗滌劑3%2%18%洗衣粉-1%4%4%廣告單位成本（萬元）100200其中洗衣粉的市場(chǎng)份額出現(xiàn)負(fù)值是由于液體洗滌劑的份額增加會(huì)造成洗衣粉份額的減少?，F(xiàn)公司需擬定使廣告總費(fèi)用最少的廣告計(jì)劃，即決定電視和印刷媒體的廣告數(shù)量（分別記為x1和x2）。1. 請(qǐng)寫出此問題的線性規(guī)劃模型（約束依表1中產(chǎn)品的次序），并將模型化為標(biāo)準(zhǔn)型。2. 用（Min型）單純形法求解此問題，得單純形終表如表2.表2CBXBB-1b100200000MMMx1x2x3x4x5x6x7x80 x5

21、41/3114/3-1/3-1100 x14-1/30-2/31/30200 x2300100j400/3100/3M-400/3M-100/3M（1）請(qǐng)?zhí)钔瓯碇锌瞻?；?）由表指出最優(yōu)廣告計(jì)劃并求出相應(yīng)的最低廣告費(fèi)用，此最優(yōu)計(jì)劃使每種產(chǎn)品的市場(chǎng)份額最低增量目標(biāo)達(dá)成情況如何？3. 寫出此問題的對(duì)偶問題模型，由表2求出對(duì)偶最優(yōu)解Y*,并解釋Y*的實(shí)際意義。（2004）1.min Z=100 x1+200 x2 標(biāo)準(zhǔn)型：2.(1)CBXBB-1b100200000MMMx1x2x3x4x5x6x7x80 x5400-14/31/3114/3-1/3-1100 x14102/3-1/30-2/31/

22、30200 x2301-100100j00400/3100/30M-400/3M-100/3M(2)最優(yōu)廣告計(jì)劃，即電視廣告數(shù)量為4，印刷廣告數(shù)量為3，最低費(fèi)用：W=1000達(dá)成情況為去污劑增加3%，恰好達(dá)標(biāo)洗衣劑增加18%，恰好達(dá)標(biāo)洗衣粉增加8%，超額4%完成(3)對(duì)偶模型為：對(duì)偶最優(yōu)解為：y=(400/3,100/3,0)經(jīng)濟(jì)意義：yi代表三種產(chǎn)品的廣告的投資，3，18，4為每種產(chǎn)品廣告單位投資后的手機(jī)，100，200代表用于電視及印刷品的投資額，故該模型的含義為用每種產(chǎn)品的頭則使其在不超過約束的條件下達(dá)到利潤最大化。(3)(30%)考慮線性規(guī)劃問題 Min z=-4x1+x2+30 x3

23、-11x4-2x5+3x6+10 x7 -2x1+6x3+2x4-3x6+x7=20 -4x1+x2+7x3+x4-x6=10 -5x3+3x4+x5-x6=60 Xj0(j=1,2,7) 用單純型法求解,初表及終表如下: 初表CB XB B-1b-4 1 30 -11 -2 3 10X1 x2 x3 x4 x5 x6 x7-2 0 6 2 0 -3 1-4 1 7 1 0 -1 00 0 -5 3 1 -1 0 檢驗(yàn)數(shù)終表-4 x1 5/4 45/23 x6 15/2-7/24 0 1/24 1/121/12 1 5/12 -1/61/4 0 1/4 -1/2 檢驗(yàn)數(shù)1.填完初表和終表中各空

24、白,并說明所得最優(yōu)解是否是唯一的,為什么?2.考慮當(dāng)b變?yōu)闀r(shí),對(duì)最優(yōu)解有什么影響?當(dāng)b變?yōu)闀r(shí),對(duì)最優(yōu)解是否有影響?3.對(duì)偶問題最優(yōu)解?（2003）解：CB XB B-1b-4 1 30 -11 -2 3 10X1 x2 x3 x4 x5 x6 x710 x7 201 x2 10-2 x5 60-2 0 6 2 0 -3 1-4 1 7 1 0 -1 00 0 -5 3 1 -1 0 檢驗(yàn)數(shù)20 0 -47 -26 0 32 0=Cj-CBB-1Pj =-4-(10 1 -2) =-4+24=20 =3=(10 1 -2)=32=30-(10 1 -2)=-47 =-11-(10 1 -2)=-

25、26-4 x1 5/4-11 x4 45/23 x6 15/21 -7/24 -7/4 0 1/24 0 1/12 0 1/12 -5/2 1 5/12 0 -1/6 0 1/4 -5/2 0 1/4 1 -1/2 檢驗(yàn)數(shù)0 0 3 0 2 0 10B-1=B-1AN= B-1P3=1-(-4 -11 3)=0不唯一，因?yàn)榇嬖诜腔兞繖z驗(yàn)數(shù)為零，則有多個(gè)最優(yōu)解B-1b=0 無影響B(tài)-1b=0 有影響CBB-1=（-4 -11 3）=（3 1 -4）Y=（3 1 -4）二、（17%）已知線性規(guī)劃問題 max z = (c1+t1) x1 + c2x2 + c3x3 + 0 x4 + 0 x5 當(dāng)

26、t1=t2=0時(shí)，用單純形法求得最終表如下：X1X2X3X4X5X3 5/201/211/20X4 5/211/201/61/3Cj-Zj04042要求：1.確定c1,c2,c3,b1,b2,a11,a12,a13,a21,a22,a23的值； 2當(dāng)t2=0時(shí)，t1在什么范圍內(nèi)變化上述最優(yōu)解不變； 3當(dāng)t1=0時(shí)，t2在什么范圍內(nèi)變化上述最優(yōu)基不變。(2002)解：二、1又由j=Cj-CBB-1Pj，設(shè) 對(duì)應(yīng)得到a11=0,a12=1,a13=2,a21=3,a22=-1,a23=12t1變化，將影響各檢驗(yàn)數(shù)的變化，檢驗(yàn)各非基變量檢驗(yàn)數(shù)，若j 0，則最優(yōu)解不變3t2變化即b變化，要使最優(yōu)基不變

27、則B-1b0，因?yàn)?，所以采用單純形法求得最?yōu)表格如下：C8X8 C8 b X81064000QjX1X2X3X4X5X66X2400/6015/610/6-1/6010X1200/6101/6-4/61/600X5100004-201-Z4400/600-8/3-10/3-2/30qj在向總經(jīng)理匯報(bào)時(shí)，總經(jīng)理提出以下問題：1 公司3中資源的影子價(jià)格各是多少？2 若要現(xiàn)行解保持最優(yōu)，則產(chǎn)品X 1的單位利潤不得低于何值？3 若產(chǎn)品X3值得生產(chǎn)的話，它的單位利潤應(yīng)是多少？4 制造部門提出要生產(chǎn)一種新產(chǎn)品，該單位產(chǎn)品要技術(shù)服務(wù)1小時(shí)，勞動(dòng)力4小時(shí)，行政管理3小時(shí)。銷售部門預(yù)測(cè)這種產(chǎn)品出售時(shí)可獲8元的單

28、位利潤，管理部門是否考慮應(yīng)將此新產(chǎn)品投產(chǎn)？現(xiàn)請(qǐng)幫助經(jīng)理助理回答以上問題。（2001）二（20） 解 1 0 3 -1 0 1 -1 1 12 0 0 -3 -1 -8 設(shè) 為引入的松弛變量。得到最優(yōu)單純形表如上表，要求： （1）利用最優(yōu)解求c1,c2. （2）利用最優(yōu)解求b1,b2 （3） 能變化多少而不至影響最優(yōu)解；當(dāng) 時(shí)求最優(yōu)解； （4）假定用b+代替b,其中,求出使最優(yōu)基保持不變的的范圍. （5）求出各資源的剩余量和影子價(jià)格。(1997) 解：二 解103-1101-11200-3-1-8（1） (2) (3) 的變化影響檢驗(yàn)數(shù)，設(shè)的變化量為 即 當(dāng)=1時(shí) 2 1 0 0 2 1 1 2

29、 1 0 3 -10 1 -1 1 0 0 -5 1 2 3 0 21 1 2 0 0 1 -1 1 0 -1 -4 0 （4） （5） 第一種資源剩余為0 第二種資源剩余為0影子價(jià)格分別為-3，-1解：解：解：解：（五）證明題三（15分）、考慮下面兩個(gè)線性規(guī)劃：（2007）解：三、三（11%）、考慮線性規(guī)劃問題（P）1若X1,X2均為（P）的可行解，證明也是（P）的可行解；2寫出（P）的對(duì)偶模型（仍用矩陣式表示）。（2006）三、1證明：令，若是（P）的可行解，則應(yīng)滿足 2對(duì)偶模型三（10%）、證明線性規(guī)劃中的互補(bǔ)松弛定理：設(shè)（P）maxz=CX,XX|AXb,X0,(D)minu=Yb,Y

30、YAb,Y0,若分別是（P）（D）的可行解，分別是其相應(yīng)的松弛變量，則是（P），（D）的最優(yōu)解的充要條件是：；并解釋互補(bǔ)松弛定理的經(jīng)濟(jì)意義。（2004）解：三、互補(bǔ)松弛定理的經(jīng)濟(jì)意義是：資源有剩余，則其影子價(jià)格為0，反之，影子價(jià)格為0說明資源恰好用完。四、(21%)試證明線性規(guī)劃原問題中第J個(gè)約束擴(kuò)大K倍,其對(duì)偶規(guī)劃最優(yōu)解中第J個(gè)變量將縮小K倍（2003）解：四、設(shè)原問題為maxZ=CX AX=b對(duì)偶J=(kaj1,kaj2,kajn) =從而得出結(jié)論二、（12%）有三個(gè)線性規(guī)劃： 已知：，試證：（1）；（2）。（2000）解：(1)(2)2.在使用單純形法求解線性規(guī)劃問題時(shí)，設(shè)當(dāng)前基證明：若

31、為某非基變量，檢驗(yàn)數(shù)，由此確定為進(jìn)基變量，則能保證新的基本可行解的目標(biāo)值得以改善。(1998)2.一（14） （1）請(qǐng)用數(shù)學(xué)方法證明，當(dāng)所有非基變量檢驗(yàn)數(shù)時(shí)，當(dāng)前基本可行解為最優(yōu)。（2）請(qǐng)從經(jīng)濟(jì)含義的角度出發(fā)，說明上述判斷的正確性。(1997)解：一 （一）確定換出基的變量 因?yàn)榭偞嬖?的，令=,其對(duì)應(yīng)變量為換出基的變量基b10001000100（二）確定換入基變量 （1）為了使下一個(gè)表中第r行基變量為正值，因而只有對(duì)應(yīng)0的非基變量才可以考慮作為換入基的變量 （2）為了使下一個(gè)表中對(duì)偶問題的解仍為可行解，令稱為主元素，為換入基的變量設(shè)下一表中的檢驗(yàn)數(shù)為（a）對(duì)時(shí)，因 故 有因?yàn)橹髟?所以 所

32、以（b）對(duì) 因 故解：解：解：解：解：解：解：解：解：二、運(yùn)輸問題將非平衡運(yùn)輸問題化為平衡運(yùn)輸問題，在表上相當(dāng)于增加一個(gè)虛設(shè)的，在模型中相當(dāng)于增加若干個(gè)變量。（2007）（2004）解：2產(chǎn)地或銷地；松弛。9運(yùn)用表上作業(yè)法求解運(yùn)輸問題時(shí)，計(jì)算檢驗(yàn)數(shù)可以用 b ，確定初始方案可以用 a 。（a）最小元素法 （b）比回路法4. 用表上作業(yè)法求解m個(gè)發(fā)點(diǎn)和n個(gè)收點(diǎn)的平衡運(yùn)輸問題，其方案表上有數(shù)格的個(gè)數(shù)為 ，空格的個(gè)數(shù)為 ；若從檢驗(yàn)數(shù)為-2的某空格調(diào)整，調(diào)量為2，則調(diào)后可使總運(yùn)費(fèi)下降 。(2000)解：m+n-1, (m-1)(n-1), 4.3用表上作業(yè)法求解某運(yùn)輸問題，若已計(jì)算出某空格的檢驗(yàn)數(shù)為-

33、2，則其經(jīng)濟(jì)意義是 ，若從該空格出發(fā)進(jìn)行調(diào)整，該調(diào)整量為2，則調(diào)后可使總運(yùn)費(fèi)下降 。（1999）解：3、該處每增運(yùn)一個(gè)單位，將使總成本降低2二、（13%）用表上作業(yè)法求解下面的平衡運(yùn)輸問題時(shí)，計(jì)算某方案的空格i,j檢驗(yàn)數(shù)ij可采用位勢(shì)法，其主要步驟如下：（1）建立線形方程組Ui+Vj=Cij,其中Cij為所有有數(shù)個(gè)的運(yùn)價(jià)，Ui，Vj分別稱發(fā)地i和收地j的位勢(shì)。（2）令U1=0，求解得位勢(shì)值Ui，Vj，i=1，m, j=1,n（3）ij= Cij-(Ui+Vj)試證明該方法的正確性，即證明空格i,j的檢驗(yàn)數(shù)為ij= Cij-(Ui+Vj)（1999）解：解：解：解：解：解：三、多目標(biāo)規(guī)劃2目標(biāo)規(guī)

34、劃模型的一個(gè)主要特點(diǎn)是引入了_變量，模型的目標(biāo)就是這些變量的極_（大還是小）化，模型的約束中也要包括用這些變量表示的_約束。（2005）解：2、偏差 小 目標(biāo)（軟）3 目標(biāo)規(guī)劃模型的一個(gè)主要特點(diǎn)是引入了偏差變量，模型的目標(biāo)就是這些變量的極 小 （大還是小化），模型的約束中也要包括用這些變量表示的目標(biāo)約束。(2002)1. 目標(biāo)規(guī)劃模型的特點(diǎn)是引入了 變量，模型的目標(biāo)函數(shù)是這些變量的極 （大還是小）化，模型的約束中也含有用這種變量表示的 約束。(2000)解：偏差變量；極??；目標(biāo)（軟）.解：解：解：解：四、動(dòng)態(tài)規(guī)劃四（25分）、某投資者擬對(duì)A與B兩種基金進(jìn)行投資，投資期限5年。該投資的收益有兩部

35、分：一是長(zhǎng)期的至第5年末的紅利收入，年利率分別為IA=0.06和IB=0.04，計(jì)復(fù)利且5年間利率不變（例如，第1年初投入A基金1元，5年后紅利收入（1+0.06）5元）；二是短期的每年利息收入，兩種基金在不同年份的利率iAK和iBK見下表（例如，第1年初投入A基金1元，除5年后的紅利收入外，一年后還有0.02元的利息收入）。年份基金 12345A0.0200.0230.0240.0260.030B0.0500.0500.0550.0450.055 該投資者第1年初投入資金50000元，以后第2至5年初每年還再投入10000元（不包括已投資的利息收入），收益計(jì)算方法相同（如第2年初投入A基金1

36、元，第5年末紅利收入（1+0.06）4元，同時(shí)第2至5年末還有年利息）。所有投入基金的資金（包括年利息）在第5年末之前不得支取?，F(xiàn)投資者需決定每年初的資金（當(dāng)年投入資金加已投資金的短期年利息）對(duì)基金A和B的分配額，以使第5年末總收入最大。 擬用動(dòng)態(tài)規(guī)劃方法解決此問題（按逆序遞推），設(shè)：狀態(tài)變量Sk為第k年初可分配的資金總量：決策變量xk為第k年初分配給基金A的資金量。1 寫出：（1）狀態(tài)轉(zhuǎn)移方程；（2）階段指標(biāo)（提示：第5年的階段指標(biāo)因年末短期年利息收入不再投入需單獨(dú)表示）；（3）基本（遞推）方程。2 求出最優(yōu)指標(biāo)f5(s5)和f4(s4)以及相應(yīng)的最優(yōu)決策x*5(s5)和x*4(s4)。（2

37、007）四、解: 1 2四（18%）、某工廠生產(chǎn)N種產(chǎn)品，它們都要使用某種原材料，現(xiàn)該原材料共有a噸，若分配xj噸原材料給第j種產(chǎn)品，則可產(chǎn)生的收益為gj（xj），j=1，N?，F(xiàn)工廠需擬定使總收益最大的原材料分配方案，試就以下1、2兩小題選答一題。1、（1）寫出此問題的數(shù)學(xué)規(guī)劃模型； （2）擬用動(dòng)態(tài)規(guī)劃方法求解，請(qǐng)寫出此問題的階段變量，狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移、階段指標(biāo)、指標(biāo)函數(shù)、基本方程（不解）。2、若工廠生產(chǎn)N=3種產(chǎn)品（分別稱為A、B、C），共有原材料a=3噸，各種產(chǎn)品被分配該原材料后產(chǎn)生的收益見表1，請(qǐng)用動(dòng)態(tài)規(guī)劃方法求解使總收益最大的分配方案。 （2006） 表1產(chǎn)品分配量(噸)

38、A B C00001106821717113201811解：四 2 階段變量k=1，2，3 表示給3種產(chǎn)品分配原材料的過程狀態(tài)變量sk，表示給第k種產(chǎn)品分配原料時(shí)擁有的資源數(shù)決策變量xk，表給第k中產(chǎn)品分配的原料量狀態(tài)轉(zhuǎn)移方程：階段指標(biāo)：vk為離散型，見下表 基本方程kskxkvkvk+fk+1(sK+1)fk(sK)pkn30000+000111010+0101221717+0172332020+020320000+000-01000+10100-1166+02000+17170-2或2-0166+1021717+03000+20272-1166+1721717+1031818+013000

39、+27270-2-1188+1721111+1031111+0最大收益27，分配方案0-2-1，即給A分配0噸，B分配2噸，C分配1噸。四（9%）、考慮下面的非線性整數(shù)規(guī)劃 其中 現(xiàn)擬用動(dòng)態(tài)規(guī)劃方法解此問題（用通常的逆推解法），要求：(1) 寫出以下表達(dá)式或集合的具體內(nèi)容：本問題的狀態(tài)轉(zhuǎn)移方程遞推方程 第1階段的狀態(tài)集合第2階段狀態(tài)為5時(shí)的允許決策的集合= ；(2) 計(jì)算第2階段狀態(tài)為12時(shí)的最優(yōu)指標(biāo)函數(shù)值及相應(yīng)的最優(yōu)決策。（2005）解：四 （1） （2） 第2階段k=12,則3段k=8 2kSkxkvkVkfk+1(Sk+1)Fk(Sk)pnk21200030121113322236333

40、39444312555315666318777321888324999327101010330111111333121212336 四（15%）、某工廠購進(jìn)100臺(tái)機(jī)器，準(zhǔn)備用于生產(chǎn)A，B兩種產(chǎn)品。若生產(chǎn)產(chǎn)品A，每臺(tái)機(jī)器每年可收入45萬，損壞率為65%，若生產(chǎn)產(chǎn)品B每臺(tái)機(jī)器年收入35萬，損壞率為35%，估計(jì)三年后將有新的機(jī)器出現(xiàn)，舊的機(jī)器將全部淘汰。請(qǐng)?jiān)谙铝袃蓡栔腥芜x一問：1、 試問每年就如何生產(chǎn)，使三年內(nèi)的收入最多？運(yùn)用動(dòng)態(tài)規(guī)劃方法具體計(jì)算求解。2、 寫出用動(dòng)態(tài)規(guī)劃方法求解時(shí)的階段變量、狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移、階段指標(biāo)、指標(biāo)函數(shù)、基本方程（遞推公式），不必具體計(jì)算。但請(qǐng)簡(jiǎn)要說明當(dāng)不能肯

41、定三年后將有新的機(jī)器出現(xiàn)，而要求到第三年末保留一定數(shù)量的舊機(jī)器時(shí)求解過程將做何調(diào)整。（2004）解：四、階段變量K=1,2,3表第K年，狀態(tài)變量SK表第K年初的好機(jī)器數(shù)目，決策變量XK，表示第K年決定把XK臺(tái)機(jī)器投入A產(chǎn)品的生產(chǎn)，狀態(tài)轉(zhuǎn)移方程SK+1=0.35XK+0.65（SK-XK）階段指標(biāo)，VK=45XK+35（SK-XK）遞推方程：具體計(jì)算如下：k=3時(shí)：k=2時(shí)： k=1時(shí)：生產(chǎn)計(jì)劃如下：即前兩年把所有機(jī)器投入B產(chǎn)品，最后一年全部投入A產(chǎn)品最大收入：=7676.25元2.某工廠考慮設(shè)備n年的更新計(jì)劃,在每年初需作出設(shè)備是更新還是繼續(xù)使用的決策,設(shè)備使用一年產(chǎn)生的利潤,設(shè)備使用一年的維

42、修費(fèi),以及設(shè)備的更新費(fèi)用都與設(shè)備已使用的年數(shù)(設(shè)備年齡t)有關(guān).設(shè)r(t)為t年齡設(shè)備使用一年的利潤 u(t)為t年齡設(shè)備使用一年的維修費(fèi)用 c(t)為t年齡設(shè)備當(dāng)年更新的費(fèi)用用動(dòng)態(tài)規(guī)劃方法求出n年內(nèi)每年的最佳決策而使n年總利潤最大.試引入0-1變量表示決策變量,并由此統(tǒng)一表示動(dòng)態(tài)規(guī)劃有關(guān)的概念和式子(不必求解):階段,狀態(tài)變量,決策變量,狀態(tài)轉(zhuǎn)移,階段指標(biāo).（2003）解：設(shè)階段變量k=1,2n,狀態(tài)變量表示k年初設(shè)備的年齡 決策變量表示更新，表示繼續(xù)使用 狀態(tài)轉(zhuǎn)移方程階段指標(biāo)遞推方程 五、（10%）某廠計(jì)劃用220萬資金，購買生產(chǎn)同一種產(chǎn)品的四種型號(hào)的設(shè)備A、B、C、D，這四種型號(hào)的設(shè)備設(shè)計(jì)生產(chǎn)能力和價(jià)格如下表所示。每種型號(hào)的設(shè)備應(yīng)購買過少臺(tái)，使總生產(chǎn)能力最大。設(shè)備型號(hào)ABCD設(shè)計(jì)生產(chǎn)能力Ki（噸/臺(tái)）150180200210價(jià)格Pi（萬元/臺(tái)）70758085 建立該問題的動(dòng)態(tài)規(guī)劃模型：列出階段變量、狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移方程、階段指標(biāo)、遞推方程（不解）。(2002)解：五、階段變量k=1,2,3,4 分別表示A,B,C,D四種型號(hào)的設(shè)備狀態(tài)變量：Sk表示在第