2012年運(yùn)籌學(xué)期末考試復(fù)習(xí)題(含答案)

1、第一章 線性規(guī)劃問題及單純形法（書11面）例1.美佳公司計(jì)劃制造、兩種家電產(chǎn)品。已知各制造一件時(shí)分別占用的設(shè)備A、B的臺(tái)時(shí)、調(diào)試工序及每天可用于這兩種家電的能力、各售出一件時(shí)的獲利情況，如下表。問該公司應(yīng)制造兩種家電各多少件，使獲取的利潤為最大。項(xiàng)目每天可用能力設(shè)備A0515設(shè)備B6224調(diào)試工序115利潤21問題1 用變量x1和x2分別表示美佳公司制造家電和的數(shù)量。（書11面）例2.捷運(yùn)公司在下一年度的14月的4個(gè)月內(nèi)擬租用倉庫堆放物資。已知各月份所需倉庫面積列于下表。倉庫租借費(fèi)用隨合同期而定，期限越長，折扣越大，具體數(shù)字見表。租界倉庫的合同每月初都可以辦理，每份合同具體規(guī)定租用面積和期限。

2、因此該廠課根據(jù)需要，在任何一個(gè)月初辦理租借合同。每次辦理時(shí)可簽一份合同，也可簽若干份租用面積和租借期限不同的合同，試確定該公司簽訂租借合同的最優(yōu)決策，目的是使所付租借費(fèi)用最小。（單位：100m2）月份1234所需倉庫面積15102012合同租借期限1個(gè)月2個(gè)月3個(gè)月4個(gè)月合同期內(nèi)的租費(fèi)2800450060007300問題2 用變量xij分別表示捷運(yùn)公司在第i個(gè)月初簽訂的租借期為j個(gè)月的倉庫面積的合同。例3.工廠A1和A2生產(chǎn)某種物資。由于該種物資供不應(yīng)求，故需要再建一家工廠。相應(yīng)的建廠方案有A3和A4兩個(gè)。這種物資的需求地有B1，B2，B3和B4四個(gè)。各工廠年生產(chǎn)能力、各地年需求量、各廠至各地

3、的單位物資運(yùn)費(fèi)cij見下表。工廠A3或A4開工后，每年的生產(chǎn)費(fèi)用估計(jì)分別為1200萬元或1500萬元?，F(xiàn)要決定應(yīng)該建設(shè)工廠A3還是A4，才能使今后每年的總費(fèi)用最少。B1B2B3B4生產(chǎn)能力A12934400A28357600A37612200A44525200需求量350400300150（書15面）例4. 例5. 例6. 例7.固定費(fèi)用問題有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件可變費(fèi)用及售價(jià)、資源單耗量及組織三種產(chǎn)品生產(chǎn)的固定費(fèi)用見表。要求制定一個(gè)生產(chǎn)計(jì)劃，使得總收益最大。 資源量 A 2 4 8 500 B 2 3 4 300 C 1 2 3 100單件可變費(fèi)用 4 5 6 固定費(fèi)

4、用 100 150 200 單件售價(jià) 8 10 12松弛問題 ： max z = x1+x2 -x1+x2+x3 =1 s.t. 3x1+x2+x4=4 x1, x2,x3,x40 XB X1 X2 X3 X4 bX1 1 0 1/4 1/4 3/4X2 0 1 3/4 1/4 7/4r 0 0 1/2 1/2割平面:-3/4X3-1/4x4-3/4例8.max z =3x1-2x2+5x3 X1 X2 X3 Z a b c d x1+2x2-x32 0 0 0 0 0 x1+4x2+x34 0 1 0 -2 s.t. x1+x23 0 1 1 3 4x2+x36 0 0 1 5 5 x1,x2,x3=0或1 1 0 0 3 1 1 0 1 1 1 1 6 1 0 1 8 8 X1=1 X2=0 X3=1 Z=8例9.min z =3 x1+7x2-x3+x4 2x1-x2+x3-x41 x1-x2+6x3+4x48 s.t. 5x1+3x2+x45 x1,x2,x3,x4=0或1例10.一筆畫問題FGHFEHIDCBEDBAF例11.哪些是歐拉圖例12.求最小生成樹例13.狄克斯特拉算法例14.求最短路徑V1V4V5V7 25V1V4V5 21V1V3V6 20V1V2 11V1V3 9V1V4 10例1