天大運(yùn)籌學(xué)考研歷年試題分類(lèi)(共18頁(yè))

1、精選優(yōu)質(zhì)文檔-傾情為你奉上（一）選擇填空題1下面給出某線(xiàn)性規(guī)劃問(wèn)題的單純形初表和終表（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 1 j CB XB B-1bx1 x2 x3 x4 x5 x6 x2 x6 2/5 0 1/10 01/5 1 3/10 01 0 -1/2 1 j (1)初表的出基變量為，進(jìn)基變量為。(3)填完終表。(6)若原問(wèn)題增加一個(gè)新的非負(fù)變量，則對(duì)偶問(wèn)題的最優(yōu)目標(biāo)值將（變大、不變、變小）。（2007）1用圖解法解線(xiàn)性規(guī)

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

3、四個(gè)項(xiàng)目中選擇若干項(xiàng)目。若令請(qǐng)用的線(xiàn)性表達(dá)式表示下列要求：（1）若項(xiàng)目2被選中，則項(xiàng)目4不能被選中： （2）只有項(xiàng)目1被選中，項(xiàng)目3才能被選中： 。（2004）一、簡(jiǎn)答（18%） （1）請(qǐng)簡(jiǎn)述影子價(jià)格的定義。 （2）在使用單純型表求解型線(xiàn)性規(guī)劃時(shí)，資源的影子價(jià)格在單純型表的什么位置上？ （3）寫(xiě)出影子價(jià)格的數(shù)學(xué)表達(dá)式并用其定義加以驗(yàn)證 （4）試述運(yùn)輸問(wèn)題中檢驗(yàn)數(shù)的經(jīng)濟(jì)意義（2003）線(xiàn)性規(guī)劃原問(wèn)題中約束的個(gè)數(shù)與其對(duì)偶問(wèn)題中的 個(gè)數(shù)相等。若原問(wèn)題第j個(gè)約束為等式，則對(duì)偶問(wèn)題第j個(gè) 自由。（2002）1 設(shè)線(xiàn)性規(guī)劃問(wèn)題max:cx|Axbx0有最優(yōu)解，且最優(yōu)解值z(mì)>0；如果c和b分別被v&g

4、t;1所乘，則改變后的問(wèn)題 （也有、不一定有）最優(yōu)解；若有最優(yōu)解，其最優(yōu)解 (大于、小于、等于)z。（2002）1下列數(shù)學(xué)模型中 是線(xiàn)性規(guī)劃模型。(2001)2下列圖形（陰影部分）中 是凸集。(2001) （a） （b） （c）3標(biāo)準(zhǔn)形式的線(xiàn)性規(guī)劃問(wèn)題，其可行解 是基本可行解，最優(yōu)解 是可行解，最優(yōu)解 能在可行域的某頂點(diǎn)達(dá)到。(2001)（a）一定 （b）不一定 （c）一定不4目標(biāo)函數(shù)取極?。╩in Z）的線(xiàn)性規(guī)劃問(wèn)題可以轉(zhuǎn)化為目標(biāo)函數(shù)取極大 b 的線(xiàn)性規(guī)劃問(wèn)題求解，原問(wèn)題的目標(biāo)函數(shù)值等于 。(2001)（a）max Z （b）max（-Z） （c）-max（-Z） （d）-max Z（a）最

5、小元素法 （b）比回路法1. 線(xiàn)性規(guī)劃單純形算法的基本步驟是：（1） （2） (3) 每次迭代保持解的 ，改善解值的 。對(duì)偶單純形法每次迭代保持解的 ，改善解值的 。（2000）2. 設(shè)有線(xiàn)性規(guī)劃問(wèn)題，有一可行基B（為A中的前m列），記相應(yīng)基變量為，價(jià)格系數(shù)為CB，相應(yīng)于非基變量為XN，價(jià)格系數(shù)為CN，則相應(yīng)于B的基本可行解為X= ；用非基變量來(lái)表示基變量的表達(dá)式為XB= ；用非基變量表示目標(biāo)函數(shù)的表達(dá)式為f= ，B為最優(yōu)基的條件是 。（2000）3. 線(xiàn)性規(guī)劃（Min型）問(wèn)題有多重最優(yōu)解時(shí)，其最優(yōu)單純形表上的特征為： （2000）6. 某足球隊(duì)要從1，2，3，4，5號(hào)五名隊(duì)員中挑選若干名上場(chǎng)

6、。令請(qǐng)用xi的線(xiàn)性表達(dá)式表示下列要求：（1）從1，2，3中至多選2名： （2）如果2號(hào)和3號(hào)都上場(chǎng)，則5號(hào)不上場(chǎng)： （3）只有4號(hào)上場(chǎng),1號(hào)才上場(chǎng)：(2000) 1某工程公司擬從四個(gè)項(xiàng)目中選擇若干項(xiàng)目，若令請(qǐng)用xi的線(xiàn)性表達(dá)式表示下列要求：（1）從1，2，3項(xiàng)目中至少選擇一個(gè)： ，（2）只有項(xiàng)目2被選中，項(xiàng)目4才能被選中 。（1999）2考慮線(xiàn)形規(guī)劃問(wèn)題用單純型法求解，得其終表如下：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+其中

7、x4位松弛變量，x5為人工變量。（1）上述模型的對(duì)偶模型為 ，（2）對(duì)偶模型的最優(yōu)解為 ，（3）當(dāng)兩種資源分別單獨(dú)增加一個(gè)單位時(shí)，目標(biāo)函數(shù)值分別增加 和 ，（4）最優(yōu)基的逆矩陣（5）如果原問(wèn)題增加一個(gè)變量，則對(duì)偶問(wèn)題的可行域?qū)⒖赡茏兇筮€是變?。浚?999）1下面給出某線(xiàn)形規(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/

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

9、要進(jìn)行多種類(lèi)型的員工培訓(xùn)。假設(shè)共有需要培訓(xùn)的需求（如技術(shù)類(lèi)、管理類(lèi)）為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ù)無(wú)關(guān)），與人數(shù)xij相應(yīng)的可變費(fèi)用為cij（表示第j方式培訓(xùn)第i種需求類(lèi)型的單位費(fèi)用）。如果以成本費(fèi)用為優(yōu)化目標(biāo)，請(qǐng)建立該培訓(xùn)問(wèn)題的結(jié)構(gòu)優(yōu)化模型（不解）。（2006）1.某廠(chǎng)使用A、B兩種原料

10、生產(chǎn)甲、乙、丙三種產(chǎn)品，有關(guān)數(shù)據(jù)見(jiàn)下表：  A B 生產(chǎn)成本（萬(wàn)元/噸）銷(xiāo)售價(jià)格（萬(wàn)元/噸） 甲 乙 丙1.0 0.50.4 0.60.6 0.5 8 5 18 30 20 35原料成本（萬(wàn)元/噸）5 7  原料可用數(shù)量（噸）350 460  （1）請(qǐng)寫(xiě)出使總銷(xiāo)售利潤(rùn)最大的線(xiàn)性規(guī)劃模型（其中甲、乙、丙產(chǎn)產(chǎn)量分別記為x1,x2,x3,約束依A,B原料次序）: (2)寫(xiě)出此問(wèn)題的對(duì)偶規(guī)劃模型（2003）三、（10%）某服裝廠(chǎng)制造大、中、小三種尺寸的防寒服，所用資源有尼龍綢、尼龍棉、勞動(dòng)力和縫紉設(shè)備?？p制一件防寒服所需各種資源的數(shù)量如表（單位已適當(dāng)給

11、定）。不考慮固定費(fèi)用，則每種防寒服售出一件所得利潤(rùn)分別為10、12、13元，可用資源分別為：尼龍綢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ì)劃使獲得的利潤(rùn)為最大，請(qǐng)寫(xiě)出其數(shù)學(xué)模型（不解）。(2002) 型號(hào)資源小中大尼龍綢161819尼龍棉131516勞動(dòng)力4455縫紉設(shè)備283842（三）互補(bǔ)松弛應(yīng)用二（8%）、線(xiàn)性規(guī)劃問(wèn)題已知其最優(yōu)解x1，x2 0，而第1，4兩種資源（相應(yīng)于第1，4兩約束）均有余量，應(yīng)用互補(bǔ)松弛定理求出原問(wèn)題和對(duì)偶問(wèn)題的最優(yōu)解

12、。（2005）（四）靈敏度分析三（25%）、派公司是一個(gè)生產(chǎn)高爾夫器材的小型公司，近期推出了高、中價(jià)位的高爾夫袋新產(chǎn)品（標(biāo)準(zhǔn)袋和高檔袋），經(jīng)銷(xiāo)商對(duì)此產(chǎn)品十分感興趣，并訂購(gòu)了派公司下3個(gè)月的全部產(chǎn)品。該高爾夫袋的生產(chǎn)過(guò)程主要包括4道工序：切割并印染原材料、縫合、成型（插入支撐架和球棒分離裝置等）、檢驗(yàn)和包裝。有關(guān)數(shù)據(jù)如表1。派公司須決定標(biāo)準(zhǔn)袋和高檔袋各生產(chǎn)多少可使公司的總利潤(rùn)最大。表1時(shí)間單耗 產(chǎn)品 （小時(shí)）工序標(biāo)準(zhǔn)袋 高檔袋3個(gè)月內(nèi)最大生產(chǎn)能力（小時(shí)）切割印染7/10 1630縫合 1/2 5/6 600成型 1 2/3 708檢驗(yàn)包裝 1/10 1/4 135產(chǎn)品單位利潤(rùn)（美元） 10 9

13、(1) 寫(xiě)出此問(wèn)題的線(xiàn)性規(guī)劃模型，約束依表1中次序；(2) 引入松弛變量（依約束次序）后用單純形法計(jì)算得某單純形表如表2，請(qǐng)?zhí)钔瓯碇锌瞻?，并判斷其是否終表，如果是，請(qǐng)寫(xiě)出最優(yōu)生產(chǎn)計(jì)劃、最大利潤(rù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. 1 -6.9375(3) 寫(xiě)出此問(wèn)題的對(duì)偶問(wèn)題的模型，及對(duì)偶的最優(yōu)解與最優(yōu)值；(4) 寫(xiě)出成型時(shí)

14、間的影子價(jià)格，求使該影子價(jià)格不變的成型時(shí)間的變化范圍；(5) 若標(biāo)準(zhǔn)袋的利潤(rùn)可能發(fā)生變化，則其在何范圍內(nèi)變化時(shí)，可使原最優(yōu)計(jì)劃不改變？圖示說(shuō)明其幾何意義。（2005）二（23%）、某公司生產(chǎn)家用的清潔產(chǎn)品，為了在高度的市場(chǎng)競(jìng)爭(zhēng)中增加市場(chǎng)份額，公司決定進(jìn)行一次大規(guī)模的廣告行動(dòng)。表1給出了公司準(zhǔn)備做廣告的三種產(chǎn)品名稱(chēng)、估計(jì)每做一單位廣告（一個(gè)廣告標(biāo)準(zhǔn)批量）使每種產(chǎn)品的市場(chǎng)份額增加量、公司擬定的廣告后每種產(chǎn)品市場(chǎng)份額增加量的最低目標(biāo)和兩種可選的廣告方式的單價(jià)。表1單位增量 廣告種類(lèi)產(chǎn)品電視印刷媒體廣告后市場(chǎng)份額最低增量去污劑0%1%3%液體洗滌劑3%2%18%洗衣粉-1%4%4%廣告單位成本（萬(wàn)元）

15、100200其中洗衣粉的市場(chǎng)份額出現(xiàn)負(fù)值是由于液體洗滌劑的份額增加會(huì)造成洗衣粉份額的減少。現(xiàn)公司需擬定使廣告總費(fèi)用最少的廣告計(jì)劃，即決定電視和印刷媒體的廣告數(shù)量（分別記為x1和x2）。1. 請(qǐng)寫(xiě)出此問(wèn)題的線(xiàn)性規(guī)劃模型（約束依表1中產(chǎn)品的次序），并將模型化為標(biāo)準(zhǔn)型。2. 用（Min型）單純形法求解此問(wèn)題，得單純形終表如表2.表2CBXBB-1b100200000MMMx1x2x3x4x5x6x7x80x541/3114/3-1/3-1100x14-1/30-2/31/30200x2300100j400/3100/3M-400/3M-100/3M（1）請(qǐng)?zhí)钔瓯碇锌瞻?；?）由表指出最優(yōu)廣告計(jì)劃并求

16、出相應(yīng)的最低廣告費(fèi)用，此最優(yōu)計(jì)劃使每種產(chǎn)品的市場(chǎng)份額最低增量目標(biāo)達(dá)成情況如何？3. 寫(xiě)出此問(wèn)題的對(duì)偶問(wèn)題模型，由表2求出對(duì)偶最優(yōu)解Y*,并解釋Y*的實(shí)際意義。（2004） (3)考慮線(xiàn)性規(guī)劃問(wèn)題 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

17、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.填完初表和終表中各空白,并說(shuō)明所得最優(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ì)偶問(wèn)題最優(yōu)解?（2003）二、（17%）已知線(xiàn)性規(guī)劃問(wèn)題 max z = (c1+t1) x1 + c2x2 + c3x3 + 0x4 + 0x5 當(dāng)t1=t2=0時(shí)，用單純形法求得最終表如下：X1X

18、2X3X4X5X3 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)采用單純形法求得最優(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)理

19、提出以下問(wèn)題：1 公司3中資源的影子價(jià)格各是多少？2 若要現(xiàn)行解保持最優(yōu)，則產(chǎn)品X 1的單位利潤(rùn)不得低于何值？3 若產(chǎn)品X3值得生產(chǎn)的話(huà)，它的單位利潤(rùn)應(yīng)是多少？4 制造部門(mén)提出要生產(chǎn)一種新產(chǎn)品，該單位產(chǎn)品要技術(shù)服務(wù)1小時(shí)，勞動(dòng)力4小時(shí)，行政管理3小時(shí)。銷(xiāo)售部門(mén)預(yù)測(cè)這種產(chǎn)品出售時(shí)可獲8元的單位利潤(rùn)，管理部門(mén)是否考慮應(yīng)將此新產(chǎn)品投產(chǎn)？現(xiàn)請(qǐng)幫助經(jīng)理助理回答以上問(wèn)題。（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） 能變化多少而不至影

20、響最優(yōu)解；當(dāng) 時(shí)求最優(yōu)解； （4）假定用b+代替b,其中,求出使最優(yōu)基保持不變的的范圍. （5）求出各資源的剩余量和影子價(jià)格。(1997) （五）證明題三（15分）、考慮下面兩個(gè)線(xiàn)性規(guī)劃：（2007）三（11%）、考慮線(xiàn)性規(guī)劃問(wèn)題（P）1若X1,X2均為（P）的可行解，證明也是（P）的可行解；2寫(xiě)出（P）的對(duì)偶模型（仍用矩陣式表示）。（2006） 2對(duì)偶模型三（10%）、證明線(xiàn)性規(guī)劃中的互補(bǔ)松弛定理：設(shè)（P）maxz=CX,XX|AXb,X0,(D)minu=Yb,YYAb,Y0,若分別是（P）（D）的可行解，分別是其相應(yīng)的松弛變量，則是（P），（D）的最優(yōu)解的充要條件是：；并解釋互補(bǔ)松弛定理

21、的經(jīng)濟(jì)意義。（2004）四、(21%)試證明線(xiàn)性規(guī)劃原問(wèn)題中第J個(gè)約束擴(kuò)大K倍,其對(duì)偶規(guī)劃最優(yōu)解中第J個(gè)變量將縮小K倍（2003）二、（12%）有三個(gè)線(xiàn)性規(guī)劃： 已知：，試證：（1）；（2）。（2000）2.在使用單純形法求解線(xiàn)性規(guī)劃問(wèn)題時(shí)，設(shè)當(dāng)前基證明：若為某非基變量，檢驗(yàn)數(shù)，由此確定為進(jìn)基變量，則能保證新的基本可行解的目標(biāo)值得以改善。(1998) （1）請(qǐng)用數(shù)學(xué)方法證明，當(dāng)所有非基變量檢驗(yàn)數(shù)時(shí)，當(dāng)前基本可行解為最優(yōu)。（2）請(qǐng)從經(jīng)濟(jì)含義的角度出發(fā)，說(shuō)明上述判斷的正確性。(1997)二、運(yùn)輸問(wèn)題將非平衡運(yùn)輸問(wèn)題化為平衡運(yùn)輸問(wèn)題，在表上相當(dāng)于增加一個(gè)虛設(shè)的，在模型中相當(dāng)于增加若干個(gè)變量。（200

22、7）（2004）9運(yùn)用表上作業(yè)法求解運(yùn)輸問(wèn)題時(shí)，計(jì)算檢驗(yàn)數(shù)可以用 b ，確定初始方案可以用 a 。4. 用表上作業(yè)法求解m個(gè)發(fā)點(diǎn)和n個(gè)收點(diǎn)的平衡運(yùn)輸問(wèn)題，其方案表上有數(shù)格的個(gè)數(shù)為 ，空格的個(gè)數(shù)為 ；若從檢驗(yàn)數(shù)為-2的某空格調(diào)整，調(diào)量為2，則調(diào)后可使總運(yùn)費(fèi)下降 。(2000)3用表上作業(yè)法求解某運(yùn)輸問(wèn)題，若已計(jì)算出某空格的檢驗(yàn)數(shù)為-2，則其經(jīng)濟(jì)意義是 ，若從該空格出發(fā)進(jìn)行調(diào)整，該調(diào)整量為2，則調(diào)后可使總運(yùn)費(fèi)下降 。（1999）二、（13%）用表上作業(yè)法求解下面的平衡運(yùn)輸問(wèn)題時(shí)，計(jì)算某方案的空格i,j檢驗(yàn)數(shù)ij可采用位勢(shì)法，其主要步驟如下：（1）建立線(xiàn)形方程組Ui+Vj=Cij,其中Cij為所有有

23、數(shù)個(gè)的運(yùn)價(jià)，Ui，Vj分別稱(chēng)發(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）五、圖論3下圖中節(jié)點(diǎn)表示某廠(chǎng)各辦公樓或車(chē)間，虛線(xiàn)表示相應(yīng)兩樓或車(chē)間之間可以架設(shè)光纜，虛線(xiàn)旁的數(shù)字為架設(shè)這段光纜的費(fèi)用，現(xiàn)需確定一使各樓或車(chē)間都能經(jīng)光纜傳輸數(shù)據(jù)且總費(fèi)用最少的方案。該問(wèn)題可以看作一個(gè)（ ）。A最小費(fèi)用流問(wèn)題 B最短路問(wèn)題 C 最大流問(wèn)題 D最小支撐樹(shù)問(wèn)題 21111177434566251541685（2006）3用標(biāo)號(hào)法求解網(wǎng)絡(luò)最大流問(wèn)題，

24、當(dāng)求的最大流的同時(shí)，也得到了最小截集，它是由_點(diǎn)集和_點(diǎn)集構(gòu)成的點(diǎn)集切割中_（正還是反）向弧組成。（2005）5632353716V4V3V2V5V6V7V12 無(wú)權(quán)的連通圖稱(chēng)為樹(shù)。求出右圖網(wǎng)絡(luò)的最小部分樹(shù)（用粗線(xiàn)在圖上標(biāo)出），最小權(quán)和為 。(2002)四、（12%）過(guò)紐約ALBANY的北-南高速公路，路況通過(guò)能力如下圖所示，圖中弧上數(shù)字單位：千輛/小時(shí)。求（1）該路網(wǎng)能承受的北-南向最大流量；（2）若要擴(kuò)充通過(guò)能力，應(yīng)在哪一組路段上擴(kuò)充，說(shuō)明原因。(2002)進(jìn)入Albany（ 北 ）離開(kāi)Albany ( 南 )7網(wǎng)絡(luò)最大流問(wèn)題中，最大流的流量 是唯一的，最大流 是唯一的。（a）一定 （b）

25、不一定三、（14分）下圖為某地區(qū)的交通網(wǎng)絡(luò)圖，結(jié)點(diǎn)表示城市，箭桿邊的數(shù)字表示城市間的公路距離，現(xiàn)要求出從S城到T城的最短路線(xiàn)和最短距離。1 以選用哪些運(yùn)籌學(xué)方法求解此問(wèn)題？（至少舉出兩種方法）2 選用一種方法求解該問(wèn)題。（2001）S1234T255316263，11，47.請(qǐng)?jiān)谙聢D所示的最短路問(wèn)題求解過(guò)程中進(jìn)行一步：下一步給 節(jié)點(diǎn)標(biāo)號(hào)，標(biāo)號(hào)為 。2，4425342 610，632533，四、（10%）某地區(qū)有3個(gè)城鎮(zhèn)，各城鎮(zhèn)每天產(chǎn)生的垃圾要運(yùn)往該地區(qū)的4個(gè)垃圾處理廠(chǎng)處理，先考慮各城鎮(zhèn)到各處理廠(chǎng)的道路對(duì)各城鎮(zhèn)垃圾外運(yùn)的影響，假設(shè)各城鎮(zhèn)每日產(chǎn)生的垃圾量、各處理廠(chǎng)的日處理能力及各條道路（可供運(yùn)垃圾

26、部分）的容量（其中容量為0者表示無(wú)此直接道路）如有表所示，試用網(wǎng)絡(luò)流方法分析目前的道路狀況能否使所有垃圾都運(yùn)到處理廠(chǎng)得到處理，如果不能，應(yīng)首先拓寬哪條道路，請(qǐng)畫(huà)出相應(yīng)的網(wǎng)絡(luò)圖，并說(shuō)明分析的過(guò)程。（可不具體求解）（1999）1 2 3 4垃圾量12330 0 10 00 0 20 4050 40 20 50507080處理量60 40 90 30 二（15%）某工廠(chǎng)欲對(duì)一新購(gòu)置設(shè)備作一5年工作計(jì)劃，決定每年初是繼續(xù)使用還是更新該設(shè)備，以使5年的總收益最大。該設(shè)備工作的年收入，年維修費(fèi)，更新費(fèi)均與設(shè)備的年齡有關(guān)。設(shè)s表示設(shè)備年齡，R(s) ，U(s)和C(s)分別表示年收入，年維修費(fèi)和更新費(fèi)。1)

27、 用最短路模型來(lái)求解此問(wèn)題（列出模型，不解）四(10%).下圖網(wǎng)絡(luò)弧上的數(shù)字為容量，括弧內(nèi)的數(shù)字為該弧的流量。1) 在括號(hào)內(nèi)填上適當(dāng)?shù)臄?shù)字，使構(gòu)成一個(gè)可行流。2) 在下表中填出截集與截量。 、3) 用標(biāo)號(hào)法解此網(wǎng)絡(luò)最大流，并指出最小截集。四（15） 有三個(gè)發(fā)電站（節(jié)點(diǎn)1，2，3）它們的發(fā)電能力分別為15，10和40兆赫，經(jīng)輸電網(wǎng)可把電力送到8號(hào)地區(qū)（節(jié)點(diǎn)8），電網(wǎng)的運(yùn)輸電能力如下圖所示，求三個(gè)發(fā)電站輸?shù)竭@地區(qū)（節(jié)點(diǎn)8）的最大電力。（用最大流標(biāo)號(hào)法）(1997)45201530151040102（艘/周）。 51 4 3 6 7 8七、決策論六（25分）、某服裝廠(chǎng)設(shè)計(jì)了一款新式服裝準(zhǔn)備推向全國(guó)。

28、如直接大批生產(chǎn)與銷(xiāo)售，主觀估計(jì)成功與失敗的概率各為0.5，其分別的獲利為1200萬(wàn)元與-500萬(wàn)元，如取消生產(chǎn)銷(xiāo)售計(jì)劃，則損失設(shè)計(jì)與準(zhǔn)備費(fèi)用40萬(wàn)元。為穩(wěn)妥起見(jiàn)，可先小批生產(chǎn)試銷(xiāo)，試銷(xiāo)的投入需45萬(wàn)元，根據(jù)過(guò)去情況大批生產(chǎn)銷(xiāo)售為成功的例子中，試銷(xiāo)成功的占84%，大批生產(chǎn)的銷(xiāo)售失敗的事例中試銷(xiāo)成功的占36%。試根據(jù)期望值準(zhǔn)則決定是否要進(jìn)行試銷(xiāo)，如果試銷(xiāo)，在試銷(xiāo)成功與失敗兩種情況下的決策各為何？分析過(guò)程中要求畫(huà)出決策樹(shù)。（2007）5 對(duì)于一個(gè)多次重復(fù)且相互獨(dú)立的風(fēng)險(xiǎn)性決策問(wèn)題，應(yīng)用最大期望收益準(zhǔn)則得到一個(gè)方案。對(duì)此有如下看法，其中正確的是（ ）。A這一方案在任何情況下的收益都是最大的B這一方案的

29、平均收益是最大的C這一方案在任何情況下的收益都等于它的期望收益D這一方案是在充分考慮了決策者對(duì)風(fēng)險(xiǎn)的偏好情況下的最佳選擇（2006）4設(shè)風(fēng)險(xiǎn)型決策問(wèn)題中，相應(yīng)于狀態(tài)的概率為相應(yīng)于和決策的結(jié)局（利潤(rùn)）為則決策問(wèn)題的完全信息期望值EVPI=_，由于它與最小期望機(jī)會(huì)損失相等，因此，它的另一種表示形式是：EVPI=_。（2005） EVPI= ,由于它和最小期望機(jī)會(huì)損失相等，因此，它的另一種表示形式是： EVPI= 。（2004）（2）（10%）一軟件公司需要在自主開(kāi)發(fā)一種微機(jī)上使用的會(huì)計(jì)軟件和接受其他公司的委托進(jìn)行辦公自動(dòng)化軟件開(kāi)發(fā)之間進(jìn)行抉擇。如果選擇自主開(kāi)發(fā)，根據(jù)過(guò)去的開(kāi)發(fā)經(jīng)驗(yàn)，開(kāi)發(fā)一個(gè)會(huì)計(jì)軟件

30、需要20萬(wàn)元。如果軟件開(kāi)發(fā)得很成功（功能好于市場(chǎng)上已經(jīng)存在的任何類(lèi)似產(chǎn)品，概率為20%），他們開(kāi)發(fā)的軟件可能以100萬(wàn)的價(jià)格賣(mài)給一個(gè)大的軟件公司；如果比較成功（好于部分市場(chǎng)產(chǎn)品，概率為60%）價(jià)格降為50萬(wàn)元；如果不成功（概率為20%）則無(wú)法賣(mài)出該產(chǎn)品。公司若決策接受其他公司的委托開(kāi)發(fā)辦公自動(dòng)化軟件，則可獲得20萬(wàn)元的軟件開(kāi)發(fā)費(fèi)。 （1）根據(jù)最大收益期望原則求該軟件公司的最優(yōu)決策（畫(huà)出決策樹(shù)） （2）求出本問(wèn)題的完全信息期望值 （3）該軟件公司還可以出2萬(wàn)元聘請(qǐng)一個(gè)咨詢(xún)公司就該產(chǎn)品的開(kāi)發(fā)問(wèn)題進(jìn)行咨詢(xún)，根據(jù)以往的統(tǒng)計(jì)該咨詢(xún)公司咨詢(xún)準(zhǔn)確性的概率P如下表： 咨詢(xún)意見(jiàn) 成功狀態(tài)很成功 成功 不成功 可

31、以開(kāi)發(fā) 不可開(kāi)發(fā) 0.9 0.5 0.1 0.1 0.5 0.9問(wèn)該軟件公司是否需要咨詢(xún)？若咨詢(xún)，相應(yīng)于各種咨詢(xún)意見(jiàn)的最優(yōu)決策為何？（請(qǐng)畫(huà)出決策樹(shù)，寫(xiě)出計(jì)算過(guò)程）（2003）七、（18%）一計(jì)算機(jī)芯片廠(chǎng)生產(chǎn)的某種芯片是以10個(gè)芯片為一個(gè)批次通過(guò)兩道主要工序生產(chǎn)出來(lái)的。大量統(tǒng)一表明，一個(gè)批次的芯片經(jīng)過(guò)生產(chǎn)的第一道工序的一次加工后會(huì)有80%的批次的產(chǎn)品合格率為90%，有20%的批次的產(chǎn)品合格率為50%。合格率為90%的批次下一道工序的加工成本為1000元，而合格率為50%的批次的下一道工序的加工費(fèi)將高達(dá)4000元。為避免質(zhì)量差的批次進(jìn)入下一道工序，工廠(chǎng)還可以選擇以1000元的成本將芯片重新在第一個(gè)

32、工序中再加工一次。經(jīng)兩次加工后的產(chǎn)品的合格率將穩(wěn)定在90%。（1） 該廠(chǎng)希望每批次的加工成本最小的應(yīng)如何決策，畫(huà)出該問(wèn)題的決策樹(shù)。（2） 計(jì)算本問(wèn)題的完全信息期望值。（3） 芯片廠(chǎng)還有另外一種選擇，即從每批中抽檢一個(gè)產(chǎn)品，根據(jù)抽檢結(jié)果決定改批次是直接進(jìn)入下一道工序，還是在第一道工序中再加工一次，抽檢一個(gè)產(chǎn)品的檢查成本為100元。試決定芯片廠(chǎng)是否應(yīng)當(dāng)抽檢及相關(guān)決策。(2002)五、（20分）某公司投資證券市場(chǎng)，現(xiàn)有兩種方案。方案A1：投資股市，方案A2：投資證券。公司投資顧問(wèn)認(rèn)為：方案A 1在大盤(pán)走勢(shì)好（1）時(shí)可能獲利50萬(wàn)元，在大盤(pán)走勢(shì)弱（2）時(shí)可能損失10萬(wàn)元。方案A2投資證券基本上無(wú)風(fēng)險(xiǎn)，

33、可獲利10萬(wàn)元。先驗(yàn)估計(jì)P（1）=0.3，P（2）=0.7。投資顧問(wèn)認(rèn)為大盤(pán)走勢(shì)和國(guó)家宏觀經(jīng)濟(jì)形式密切相關(guān)。并建議請(qǐng)經(jīng)濟(jì)研究所進(jìn)行預(yù)測(cè)，預(yù)測(cè)費(fèi)用為1萬(wàn)元。根據(jù)統(tǒng)計(jì)資料，該所預(yù)測(cè)精度的條件概率如下： 其中S1表示國(guó)家宏觀經(jīng)濟(jì)形式良好，S2表示國(guó)家宏觀經(jīng)濟(jì)形式不好先驗(yàn)概率P（j）條件概率P（Si/j）P（S1/j）P（S2/j）P（1）=0.30.80.2P（2）=0.70.10.910.設(shè)風(fēng)險(xiǎn)型決策問(wèn)題中，相應(yīng)于狀態(tài)i的概率為P(i),i=1,2,m，相應(yīng)于結(jié)局（利潤(rùn)）為uij，i=1,2,m，j=1,2,n，則完全信息期望值EVPI= ，由于它與最小期望機(jī)會(huì)損失相等，因此，它的另一種表示形式是：EVP1= 。(2000)六（15%）在一臺(tái)機(jī)器上加工制造一批零件共1000個(gè)，如果加工完后即逐個(gè)進(jìn)行修整，則全部都可以合格