天津大學運籌學考研歷年試題分類

1、二、運輸問題三、多目標規(guī)劃四、動態(tài)規(guī)劃五、圖論六、網(wǎng)絡計劃技術(shù)七、決策論八、存儲論九、排隊論十、對策論十一、模擬技術(shù)一、線性規(guī)劃（一）選擇填空題 （二）線性規(guī)劃建模 （三）互補松弛應用 （四）靈敏度分析 （五）證明題（一）選擇填空題1下面給出某線性規(guī)劃問題的單純形初表和終表（Min型）：CB XB B-1b0 1 -3 0 2 0x1 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 1jCB XB B-1bx1 x2 x3 x4 x5 x6 x2 x62/5 0 1/10 01/5 1 3/10 01 0

2、 -1/2 1j (1)初表的出基變量為，進基變量為。(3)填完終表。(6)若原問題增加一個新的非負變量，則對偶問題的最優(yōu)目標值將（變大、不變、變小）。（2007）解：1(1)出基變量為x4；進基變量為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 1j1/5 0 0 4/5 12/5 0 (4) (5) (6) 變小1用圖解法解線性規(guī)劃時，以下幾種情況中不可能出現(xiàn)的是（ ）。A可行域（約束集合）有界，無有限最優(yōu)解（或稱無解界

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

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

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

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

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

8、項目中選擇若干項目，若令請用xi的線性表達式表示下列要求：（1）從1，2，3項目中至少選擇一個：，（2）只有項目2被選中，項目4才能被選中。（1999）解：1、x1+x2+x31x2x42考慮線形規(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）上述模型的對偶模型為，（2）對偶模型的最優(yōu)解為，（3）當兩種資源分別單獨增加一個單位時，目標函數(shù)值分別增加和，（4

9、）最優(yōu)基的逆矩陣（5）如果原問題增加一個變量，則對偶問題的可行域?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 101) 初表的出基變量為_，進基變量為_。2) 填完表2，該表是否是終

10、表?_。若是，最優(yōu)值_3) 此線形規(guī)劃對偶問題的最優(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-3x350 x6112/5 1 0 1/10 4/5 01/5 0 1 3/10 2/5 01 0 0 -1/2 10 11/5 00 4/5 12/5 04) 初表的出基變量為_x4_，進基變量為_x

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

12、、某大型企業(yè)每年需要進行多種類型的員工培訓。假設(shè)共有需要培訓的需求（如技術(shù)類、管理類）為6種，每種需求的最低培訓人數(shù)為ai，i=1,6, 可供選擇的培訓方式（如內(nèi)部自行培訓、外部與高校合作培訓）有5種，每種的最高培訓人數(shù)為bj, j=1,5。又設(shè)若選擇了第1種培訓方式，則第3種培訓方式也要選擇。記xij為第i種需求由第j方式培訓的人員數(shù)量，z為培訓總費用。費用的構(gòu)成包括固定費用和可變費用，第j種方式的固定費用為hj（與人數(shù)無關(guān)），與人數(shù)xij相應的可變費用為cij（表示第j方式培訓第i種需求類型的單位費用）。如果以成本費用為優(yōu)化目標，請建立該培訓問題的結(jié)構(gòu)優(yōu)化模型（不解）。（2006）解：二、

13、1.某廠使用A、B兩種原料生產(chǎn)甲、乙、丙三種產(chǎn)品，有關(guān)數(shù)據(jù)見下表：  A B 生產(chǎn)成本（萬元/噸）銷售價格（萬元/噸）甲乙丙 8 5 18 30 20 35原料成本（萬元/噸）5 7  原料可用數(shù)量（噸）350 460  （1）請寫出使總銷售利潤最大的線性規(guī)劃模型（其中甲、乙、丙產(chǎn)產(chǎn)量分別記為x1,x2,x3,約束依A,B原料次序）: (2)寫出此問題的對偶規(guī)劃模型（2003）解：maxz=30x1+20x2+35x3-8x1-5x2-18x3-5(x123123)123約束條件 x123350123460 x10,x20,x30對偶規(guī)劃模型目

14、標函數(shù) minw=350y1+460y2約束條件y121212 y10,y20三、（10%）某服裝廠制造大、中、小三種尺寸的防寒服，所用資源有尼龍綢、尼龍棉、勞動力和縫紉設(shè)備?？p制一件防寒服所需各種資源的數(shù)量如表（單位已適當給定）。不考慮固定費用，則每種防寒服售出一件所得利潤分別為10、12、13元，可用資源分別為：尼龍綢1500米，尼龍棉1000米，勞動力4000，設(shè)備3000小時。此外，每種防寒服不管縫制多少件，只要做都要支付一定的固定費用：小號為100元，中號為150元，大號為200元?，F(xiàn)欲制定一生產(chǎn)計劃使獲得的利潤為最大，請寫出其數(shù)學模型（不解）。(2002) 型號資源小中大尼龍綢16

15、1819尼龍棉131516勞動力4455縫紉設(shè)備283842解：三、解：設(shè)三種防寒服分別生產(chǎn)x1,x2,x3件。z表示獲得的利潤,y1,y2,y3分別表示0-1變量，yi=1表示做第xi種防寒服（i=1,2,3）（三）互補松弛應用二（8%）、線性規(guī)劃問題已知其最優(yōu)解x1，x2 0，而第1，4兩種資源（相應于第1，4兩約束）均有余量，應用互補松弛定理求出原問題和對偶問題的最優(yōu)解。（2005）解：二 對偶問題 （*） 代入（*）式， 由綜上，原問題最優(yōu)解 對偶問題最優(yōu)解（四）靈敏度分析三（25%）、派公司是一個生產(chǎn)高爾夫器材的小型公司，近期推出了高、中價位的高爾夫袋新產(chǎn)品（標準袋和高檔袋），經(jīng)銷商

16、對此產(chǎn)品十分感興趣，并訂購了派公司下3個月的全部產(chǎn)品。該高爾夫袋的生產(chǎn)過程主要包括4道工序：切割并印染原材料、縫合、成型（插入支撐架和球棒分離裝置等）、檢驗和包裝。有關(guān)數(shù)據(jù)如表1。派公司須決定標準袋和高檔袋各生產(chǎn)多少可使公司的總利潤最大。表1時間單耗 產(chǎn)品 （小時）工序標準袋 高檔袋3個月內(nèi)最大生產(chǎn)能力（小時）切割印染7/10 1630縫合 1/2 5/6600成型 1 2/3 708檢驗包裝 1/10 1/4135產(chǎn)品單位利潤（美元） 10 9(1) 寫出此問題的線性規(guī)劃模型，約束依表1中次序；(2) 引入松弛變量（依約束次序）后用單純形法計算得某單純形表如表2，請?zhí)钔瓯碇锌瞻?，并判斷其是?/p>

17、終表，如果是，請寫出最優(yōu)生產(chǎn)計劃、最大利潤和資源剩余；表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 -1.25 0 1.875 00 -0.34375 0 0.140625 1(3) 寫出此問題的對偶問題的模型，及對偶的最優(yōu)解與最優(yōu)值；(4) 寫出成型時間的影子價格，求使該影子價格不變的成型時間的變化范圍；(5) 若標準袋的利潤可能發(fā)生變化，則其在何范圍內(nèi)變化時，可使原最優(yōu)計劃不改變？圖示說明其幾何意義。

18、（2005）解：三 設(shè)標準袋生產(chǎn),高檔袋生產(chǎn) （1） （2）10 9 0 0 0 09 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 00 0 -0.34375 0 0.140625 10 0 -4.375 0 -6.9375 0是終表最優(yōu)生產(chǎn)計劃，即普通袋540個，高檔袋252個最大利潤Z (美元)（3）對偶問題模型：對偶問題最優(yōu)解：由對偶問題的強對偶性知，對偶問題與原問題的最優(yōu)值相同W*=Z*=7668 (美元)（5）變化，可能影響檢驗數(shù)，故令二（23%

19、）、某公司生產(chǎn)家用的清潔產(chǎn)品，為了在高度的市場競爭中增加市場份額，公司決定進行一次大規(guī)模的廣告行動。表1給出了公司準備做廣告的三種產(chǎn)品名稱、估計每做一單位廣告（一個廣告標準批量）使每種產(chǎn)品的市場份額增加量、公司擬定的廣告后每種產(chǎn)品市場份額增加量的最低目標和兩種可選的廣告方式的單價。表1單位增量 廣告種類產(chǎn)品電視印刷媒體廣告后市場份額最低增量去污劑0%1%3%液體洗滌劑3%2%18%洗衣粉-1%4%4%廣告單位成本（萬元）100200其中洗衣粉的市場份額出現(xiàn)負值是由于液體洗滌劑的份額增加會造成洗衣粉份額的減少?，F(xiàn)公司需擬定使廣告總費用最少的廣告計劃，即決定電視和印刷媒體的廣告數(shù)量（分別記為x1和

20、x2）。1. 請寫出此問題的線性規(guī)劃模型（約束依表1中產(chǎn)品的次序），并將模型化為標準型。2. 用（Min型）單純形法求解此問題，得單純形終表如表2.表2CBXBB-1b100200000MMMx1x2x3x4x5x6x7x80x541/3114/3-1/3-1100x14-1/30-2/31/30200x2300100j400/3100/3M-400/3M-100/3M（1）請?zhí)钔瓯碇锌瞻?；?）由表指出最優(yōu)廣告計劃并求出相應的最低廣告費用，此最優(yōu)計劃使每種產(chǎn)品的市場份額最低增量目標達成情況如何？3. 寫出此問題的對偶問題模型，由表2求出對偶最優(yōu)解Y*,并解釋Y*的實際意義。（2004）1.m

21、in Z=100x1+200x2標準型：2.(1)CBXBB-1b100200000MMMx1x2x3x4x5x6x7x80x5400-14/31/3114/3-1/3-1100x14102/3-1/30-2/31/30200x2301-100100j00400/3100/30M-400/3M-100/3M(2)最優(yōu)廣告計劃，即電視廣告數(shù)量為4，印刷廣告數(shù)量為3，最低費用：W=1000達成情況為去污劑增加3%，恰好達標洗衣劑增加18%，恰好達標洗衣粉增加8%，超額4%完成(3)對偶模型為：對偶最優(yōu)解為：y=(400/3,100/3,0)經(jīng)濟意義：yi代表三種產(chǎn)品的廣告的投資，3，18，4為每種

22、產(chǎn)品廣告單位投資后的手機，100，200代表用于電視及印刷品的投資額，故該模型的含義為用每種產(chǎn)品的頭則使其在不超過約束的條件下達到利潤最大化。(3)(30%)考慮線性規(guī)劃問題 Min z=-4x1+x2+30x3-11x4-2x5+3x6+10x7 -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

23、7 1 0 -1 00 0 -5 3 1 -1 0檢驗數(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檢驗數(shù) 1.填完初表和終表中各空白,并說明所得最優(yōu)解是否是唯一的,為什么?2.考慮當b變?yōu)闀r,對最優(yōu)解有什么影響?當b變?yōu)闀r,對最優(yōu)解是否有影響?3.對偶問題最優(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

24、-1 00 0 -5 3 1 -1 0 檢驗數(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)=-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 檢驗數(shù)0 0 3 0 2 0 10B-1=B-1AN=B-1P3=1-(-4 -11 3)=0不唯一，因為存在非基變量檢驗數(shù)為零，則

25、有多個最優(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+0x4+0x5當t1=t2=0時，用單純形法求得最終表如下：X1X2X3X4X5X3 5/201/211/20X4 5/211/201/61/3Cj-Zj040421,c2,c3,b1,b2,a11,a12,a13,a21,a22,a23的值； 2當t2=0時，t1在什么范圍內(nèi)變化上述最優(yōu)解不變； 3當t1=0時，t2在什么范圍內(nèi)變化上述最優(yōu)基不變。(2002)解：二、1又由j=Cj-C

26、BB-1Pj，設(shè)對應得到a11=0,a12=1,a13=2,a21=3,a22=-1,a23=12t1變化，將影響各檢驗數(shù)的變化，檢驗各非基變量檢驗數(shù)，若j0，則最優(yōu)解不變3t2變化即b變化，要使最優(yōu)基不變則B-1b0，因為，所以采用單純形法求得最優(yōu)表格如下：C8X8 C8b X81064000QjX1X2X3X4X5X66X2400/6015/610/6-1/6010X1200/6101/6-4/61/600X5100004-201-Z4400/600-8/3-10/3-2/30qj在向總經(jīng)理匯報時，總經(jīng)理提出以下問題：1 公司3中資源的影子價格各是多少？2 若要現(xiàn)行解保持最優(yōu)，則產(chǎn)品X 1

27、的單位利潤不得低于何值？3 若產(chǎn)品X3值得生產(chǎn)的話，它的單位利潤應是多少？4 制造部門提出要生產(chǎn)一種新產(chǎn)品，該單位產(chǎn)品要技術(shù)服務1小時，勞動力4小時，行政管理3小時。銷售部門預測這種產(chǎn)品出售時可獲8元的單位利潤，管理部門是否考慮應將此新產(chǎn)品投產(chǎn)？現(xiàn)請幫助經(jīng)理助理回答以上問題。（2001）二（20） 解 1 0 3 -10 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)解；當 時求最優(yōu)解； （4）假定用b+代替b,其中,求出使最優(yōu)基保持不變的的范圍.

28、（5）求出各資源的剩余量和影子價格。(1997) 解：二解103-1101-11200-3-1-8（1）(2) (3) 的變化影響檢驗數(shù)，設(shè)的變化量為 即 當=1時 2 1 0 02 1 1 21 0 3 -10 1 -1 1 0 0 -5 1 2 3 0 21 1 2 00 1 -1 1 0 -1 -4 0（4） （5） 第一種資源剩余為0 第二種資源剩余為0影子價格分別為-3，-1解：解：解：解：（五）證明題三（15分）、考慮下面兩個線性規(guī)劃：（2007）解：三、三（11%）、考慮線性規(guī)劃問題（P）1若X1,X2均為（P）的可行解，證明也是（P）的可行解；2寫出（P）的對偶模型（仍用矩陣式

29、表示）。（2006）三、1證明：令，若是（P）的可行解，則應滿足2對偶模型三（10%）、證明線性規(guī)劃中的互補松弛定理：設(shè)（P）maxz=CX,XX|AXb,X0,(D)minu=Yb,YYAb,Y0,若分別是（P）（D）的可行解，分別是其相應的松弛變量，則是（P），（D）的最優(yōu)解的充要條件是：；并解釋互補松弛定理的經(jīng)濟意義。（2004）解：三、互補松弛定理的經(jīng)濟意義是：資源有剩余，則其影子價格為0，反之，影子價格為0說明資源恰好用完。四、(21%)試證明線性規(guī)劃原問題中第J個約束擴大K倍,其對偶規(guī)劃最優(yōu)解中第J個變量將縮小K倍（2003）解：四、設(shè)原問題為maxZ=CX AX=b對偶J=(ka

30、j1,kaj2,kajn)=從而得出結(jié)論二、（12%）有三個線性規(guī)劃：已知：，試證：（1）；（2）。（2000）解：(1)(2)時，設(shè)當前基證明：若為某非基變量，檢驗數(shù)，由此確定為進基變量，則能保證新的基本可行解的目標值得以改善。(1998)2.一（14）（1）請用數(shù)學方法證明，當所有非基變量檢驗數(shù)時，當前基本可行解為最優(yōu)。（2）請從經(jīng)濟含義的角度出發(fā)，說明上述判斷的正確性。(1997)解：一 （一）確定換出基的變量 因為總存在<0的，令=,其對應變量為換出基的變量基b10001000100（二）確定換入基變量 （1）為了使下一個表中第r行基變量為正值，因而只有對應<0的非基變量才

31、可以考慮作為換入基的變量 （2）為了使下一個表中對偶問題的解仍為可行解，令稱為主元素，為換入基的變量設(shè)下一表中的檢驗數(shù)為（a）對時，因 故 有因為主元素 所以 所以（b）對 因 故解：解：解：解：解：解：解：解：解：二、運輸問題將非平衡運輸問題化為平衡運輸問題，在表上相當于增加一個虛設(shè)的，在模型中相當于增加若干個變量。（2007）（2004）解：2產(chǎn)地或銷地；松弛。9運用表上作業(yè)法求解運輸問題時，計算檢驗數(shù)可以用 b ，確定初始方案可以用 a 。（a）最小元素法 （b）比回路法4. 用表上作業(yè)法求解m個發(fā)點和n個收點的平衡運輸問題，其方案表上有數(shù)格的個數(shù)為，空格的個數(shù)為；若從檢驗數(shù)為-2的某空

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

33、-(Ui+Vj)試證明該方法的正確性，即證明空格i,j的檢驗數(shù)為ij= Cij-(Ui+Vj)（1999）解：解：解：解：解：解：三、多目標規(guī)劃2目標規(guī)劃模型的一個主要特點是引入了_變量，模型的目標就是這些變量的極_（大還是?。┗?，模型的約束中也要包括用這些變量表示的_約束。（2005）解：2、偏差 小 目標（軟）3 目標規(guī)劃模型的一個主要特點是引入了偏差變量，模型的目標就是這些變量的極 小 （大還是小化），模型的約束中也要包括用這些變量表示的目標約束。(2002)1. 目標規(guī)劃模型的特點是引入了變量，模型的目標函數(shù)是這些變量的極（大還是?。┗?，模型的約束中也含有用這種變量表示的約束。(200

34、0)解：偏差變量；極小；目標（軟）.解：解：解：解：四、動態(tài)規(guī)劃四（25分）、某投資者擬對A與B兩種基金進行投資，投資期限5年。該投資的收益有兩部分：一是長期的至第5年末的紅利收入，年利率分別為IAB=0.04，計復利且5年間利率不變（例如，第1年初投入A基金1元，5年后紅利收入（1+0.06）5元）；二是短期的每年利息收入，兩種基金在不同年份的利率iAK和iBK見下表（例如，第1年初投入A基金1元，除5年后的紅利收入外，一年后還有0.02元的利息收入）。年份基金 12345AB 該投資者第1年初投入資金50000元，以后第2至5年初每年還再投入10000元（不包括已投資的利息收入），收益計算

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

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

37、06） 表1產(chǎn)品分配量(噸) A B C00001106821717113201811解：四2 階段變量k=1，2，3 表示給3種產(chǎn)品分配原材料的過程狀態(tài)變量sk，表示給第k種產(chǎn)品分配原料時擁有的資源數(shù)決策變量xk，表給第k中產(chǎn)品分配的原料量狀態(tài)轉(zhuǎn)移方程：階段指標：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+

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

39、1332223633339444312555315666318777321888324999327101010330111111333121212336四（15%）、某工廠購進100臺機器，準備用于生產(chǎn)A，B兩種產(chǎn)品。若生產(chǎn)產(chǎn)品A，每臺機器每年可收入45萬，損壞率為65%，若生產(chǎn)產(chǎn)品B每臺機器年收入35萬，損壞率為35%，估計三年后將有新的機器出現(xiàn)，舊的機器將全部淘汰。請在下列兩問中任選一問：1、 試問每年就如何生產(chǎn)，使三年內(nèi)的收入最多？運用動態(tài)規(guī)劃方法具體計算求解。2、 寫出用動態(tài)規(guī)劃方法求解時的階段變量、狀態(tài)變量、決策變量、狀態(tài)轉(zhuǎn)移、階段指標、指標函數(shù)、基本方程（遞推公式），不必具體計算。

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

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