天大97-08試題分類

一、線性規(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型

01-3020

CB'b

BXBX]X2X3X4X5X6

0X|713-1020

0x4120-24100

0x6100-43081

°.i

CXB'b

BBXix2x3x4x5x6

x22/501/100

1/513/100

X610-1/21

°.i

（1）初表的出基變量為,進(jìn)基變量為。

（2）最優(yōu)基逆丁一,=[]

（3）填完終表。

（4）最優(yōu)解X*=

⑸對(duì)偶問題最優(yōu)解y*=

⑹若原問題增加一個(gè)新的非負(fù)變量，則對(duì)偶問題的最優(yōu)目標(biāo)值將（變大、不變、變

?。＃?007）

解：1.（1）出基變量為X4：進(jìn)基變量為X3。

⑶

BBB'b

CXXjx2X3x4X5X6

1X242/5101/104/50

-3X351/5013/102/50

0X611100-1/2101

°j1/5004/512/50

⑷X*=(45ID

4

⑸Y=(-0)

5

(6)變小

1.用圖解法解線性規(guī)劃時(shí)，以下兒種情況中不可能出現(xiàn)的是（）o

A.可行域（約束集合）有界，無有限最優(yōu)解（或稱無解界）

B.可行域（約束集合）無界，有唯一最優(yōu)解

C.可行域（約束集合）是空集，無可行解

D.可行域（約束集合）有界，有多重最優(yōu)解（2006）

解：1.A

2.根據(jù)線性規(guī)劃的互補(bǔ)松弛定理，安排生產(chǎn)的產(chǎn)品機(jī)會(huì)成本一定（）利潤(rùn)。

A.小于B.等于C.大于D.大于等于（2006）

解：2.B

1.用大M法求解Max型線形規(guī)劃時(shí)，人工變量在目標(biāo)函數(shù)中的系數(shù)均為,

若最優(yōu)解的中含有人工變量，則原問題無解。（2005）

解：1、-M基變量

I.設(shè)線性規(guī)劃問題max{cx|Ax=bx2o}有最優(yōu)解x*和影子價(jià)格y*,則線性規(guī)劃問題

11^{2閡4￥="20}的最優(yōu)解=,影子價(jià)格=o

（2004）

解：1.x*2y*

3.某工程公司擬從1、2、3、4四個(gè)項(xiàng)目中選擇若干項(xiàng)目。若令

1，第i個(gè)項(xiàng)目被選中

0,第i個(gè)項(xiàng)目未選中'

清用七的線性表達(dá)式表示下列要求：（1）若項(xiàng)目2被選中，則項(xiàng)目4不能被選中：

（2）只有項(xiàng)目1被選中，項(xiàng)目3才能被選中：o（2004）

解：3.x2+x4<1,%,-x3<0

一、簡(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"

B是原問題｛maxz=CXIAXWb,X）0｝最優(yōu)基

Z"=CBB'b=Y*b

Z*=yJb?+y2*bz…y-h

炎*

------=y3*

8b

（4）表明增加?個(gè)單位的運(yùn)量會(huì)引起總運(yùn)輸費(fèi)用的變化

1.線性規(guī)劃原問題中約束的個(gè)數(shù)與其對(duì)偶問題中的變量個(gè)數(shù)相等。若原問題第j個(gè)約束

為等式，則對(duì)偶問題第i個(gè)變量自由（2002）

解：

2.設(shè)線性規(guī)劃問題max:｛cxlAxWbx20｝有最優(yōu)解，且最優(yōu)解值z(mì)>0；4操c和b分別被v>l

所乘，則改變后的問題.也有（也有、不一定有）最優(yōu)解；若有最優(yōu)解，其最優(yōu)解&

于（大于、小于、等于）z。（2002）

1.下列數(shù)學(xué)模型中a是線性規(guī)劃模型。（2001）

(6)maxZ=min<區(qū)+6：+815$+9；2+2當(dāng)

(a)maxZ=4xt+2x2+3x3

7X]+3X2+6X3<1505x}+5X2+3X3<300

)與<

s.t.<4x,+4X2+5X3<1206x+9X2+8500

xi,x2,x3>0x19x2,x3>0

解:

2.下列圖形(陰影部分)中b是凸第。(2001)

解：

3.標(biāo)準(zhǔn)形式的線性規(guī)劃問題，其可行解b是基本可行解,最優(yōu)解a是可行解,最優(yōu)

解a能在可行域的某頂點(diǎn)達(dá)到。(2001)

(a)一定(b)不一定(c)一定不

解：

4.目標(biāo)函數(shù)取極小(minZ)的線性規(guī)劃問題可以轉(zhuǎn)化為目標(biāo)函數(shù)取極大的線性規(guī)劃

問題求解，原問題的目標(biāo)函數(shù)值等于(2001)

(a)maxZ(b)max(-Z)(c)-max(-Z)(d)-maxZ

(a)最小元素法(b)比回路法

1.線性規(guī)劃單純形算法的基本步驟是：(1)(2)

(3)每次迭代保持解的,改善解值的。對(duì)偶單純

形法每次迭代保持解的.改善解值的。(2000)

解：確定一個(gè)初始基可行解；檢驗(yàn)一個(gè)基可行解是否為最優(yōu)解；尋找一個(gè)更好基可行解；可

行性；最優(yōu)性。

2.設(shè)有線性規(guī)劃問題\min\f=CX,XeR={X\AX=b,X>0),有一可行基B(為A

中的前m列)，記相應(yīng)基變量為X.,價(jià)格系數(shù)為CB，相應(yīng)于非基變量為XN，價(jià)格系數(shù)為

CN，則相應(yīng)于B的基本可行解為*=；用非基變量來表示基變量的表達(dá)式為

XB=；用非基變量表示目標(biāo)函數(shù)的表達(dá)式為￡=,B為最優(yōu)基的條件

是<,(2000)

解：，B'b-B-'NXN,。握為+(『—C*W)XN，CN-CBB-NNO

、0/

3.線性規(guī)劃(Min型)問題有多重最優(yōu)解時(shí)，其最優(yōu)單純形表上的特征為：

(2000)

解：所有檢驗(yàn)數(shù)可某0,?個(gè)非基變量檢驗(yàn)數(shù)4=0.

6.某足球隊(duì)要從I,2,3,4,5號(hào)五名隊(duì)員中挑選若干名上場(chǎng)。令

J1第i號(hào)上場(chǎng)

七一jo第i號(hào)不上場(chǎng)，i=1,2,3,4,5

請(qǐng)用％的線性表達(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)

解：xl+x2+x3>2,x4-x5>0,x,+x4<1.

1.某工程公司擬從四個(gè)項(xiàng)目中選擇若干項(xiàng)目，若令

J1,第介項(xiàng)目被選中

Xi~[o,第泠項(xiàng)目末被選中"''’.

請(qǐng)用Xi的線性表達(dá)式表示下列要求：

(1)從1,2,3項(xiàng)目中至少選擇一個(gè)：,

(2)只有項(xiàng)目2被選中，項(xiàng)目4才能被選中o(1999)

解：1、X|+X2+X3s：lx2^x4

2.考慮線形規(guī)劃問題

maxZ=5Xj+12x2+4x3

x,+2X2+x3<5

s.tA2x1-x2+3x3=2

xpx2,x3>0

用單純型法求解，得其終表如下:

q51240-M

CB'b

BXBXlX2X3X4X5

12X28/501-1/52/5-1/5

5Xl9/5107/51/52/5

2

bj00-3/5-29/5-Md--

5

其中X4位松弛變量，X5為人工變量。

(1)上述模型的對(duì)偶模型為,

(2)對(duì)偶模型的最優(yōu)解為,

(3)當(dāng)兩種資源分別單獨(dú)增加一個(gè)單位時(shí)，目標(biāo)函數(shù)值分別增加

和,

(4)最優(yōu)基的逆矩陣員:

(5)如果原問題增加一個(gè)變量，則對(duì)偶問題的可行域?qū)⒖赡茏兇筮€是變??？

(1999)

解：2.(1)

minW=5yl+2y2

y,+2%N5

(2y1-y2>12

%+3%"

JNO,為無符號(hào)限制

292

(2)Y*=(—,--)

55

⑶以一2

55

2_r

(4)55

12

J5>

(5)變小

1.下面給出某線形規(guī)劃的單純形初表(表1)與某一中間表(表2)(Min型：

表1

01-3020

B'b

CBXBXlX2X3X4X5X6

0X1713-1020

0120-24100

X4

0100-43081

X6

Oj

表2

X22/501/104/5

1/513/102/5

X610-1/210

Oj

1）初表的出基變量為，進(jìn)基變量為o

2）填完表2,該表是否是終表?o若是，最優(yōu)值Z*=

3）此線形規(guī)劃對(duì)偶問題的最優(yōu)解片=

（1998）

解：1.下面給出某線形規(guī)劃的單純形初表（表1）與某一中間表（表2）（Min型：

表1

01-3020

CBXBB'bXiX2x3x4x5x6

0X)713-1020

0X4120-24100

0x6100-43081

Oj01-3020

表2

2/501/104/5

1x2410

-3x351/5013/102/50

0x611100-1/2101

Oj1/5004/512/50

4）初表的出基變量為X4，進(jìn)基變量為—X3o

5）填完表2,該表是否是終表?—是。若是，最優(yōu)值Z*=_-ll

此線形規(guī)劃對(duì)偶問題的最優(yōu)解y*上-2,0

55

解:

解:

解:

解:

解:

（-）線性規(guī)劃建模

二（20分）、某化學(xué)制藥廠有m種有害副產(chǎn)品，它們的數(shù)量為bi（i=l,…，m）。按照規(guī)定,

必須經(jīng)過處理，制成n種無害物后才能廢棄。設(shè)aij為每制成一單位第j（j=l,…，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ì)意義。（2007）

解：1.

II

minz=ZgXj

j=i

%+ai2X2+???+a\nXn24

??

a21Xj+a22x2+.+a2nxn>b2

。，"抑|+4，,2々+一?+。，",，瑞Nb‘

xpx2,...,xn>0

maxz=2

《2)1+022y2+…+冊(cè)2*,2

—+"2+…+3”小“

.%，上，…，Xn20

經(jīng)濟(jì)意義：為第i種有害副產(chǎn)品不經(jīng)處理直接廢棄的費(fèi)用。

二（10%）、某大型企業(yè)每年需要進(jìn)行多種類型的員工培訓(xùn)。假設(shè)共有需要

培訓(xùn)的需求（如技術(shù)類、管理類）為6種，每種需求的最低培訓(xùn)人數(shù)為a”i=l,…,6,

可供選擇的培訓(xùn)方式（如內(nèi)部自行培訓(xùn)、外部與高校合作培訓(xùn)）有5種，每種的

最高培訓(xùn)人數(shù)為bj,j=l,…,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)用）。

如果以成本費(fèi)用為優(yōu)化目標(biāo)，請(qǐng)建立該培訓(xùn)問題的結(jié)構(gòu)優(yōu)化模型（不解）。（2006）

解：二、

設(shè)其第種需求由第種藥式培訓(xùn)的人員數(shù)量，匕=，『訓(xùn)方式

565

minz=Zyjhj+ZZ

j=lf=lJ=1

z/（i=l,2,…,5）

2囪2《（i=l,2,…,6）

,多一%?0

x,7>0（i=l,…6,j=1,2,…,5）

匕=0或10=1,2,…,5）

1.某廠使用A、B兩種原料生產(chǎn)甲、乙、丙三種產(chǎn)品，有關(guān)數(shù)據(jù)見下表:

AB生產(chǎn)成本（萬元/噸）銷售價(jià)格（萬元/噸）

甲1.00.5830

乙0.40.6520

丙0.60.51835

原料成本（萬元/噸）57

原料可用數(shù)量（噸）350460

（1）請(qǐng)寫出使總銷售利潤(rùn)最大的線性規(guī)劃模型（其中甲、乙、丙產(chǎn)產(chǎn)量分別記為x,,x2,x3,

約束依A,B原料次序）：

（2）寫出此問題的對(duì)偶規(guī)劃模型（2003）

解：1.①maxz=30x?+20X2+35X3-8XJ-5x2-18x3-5(X|+0.4x2+0.6x3)-7(0.5xI+0.6X2+0.5X3)

目標(biāo)函數(shù)maxz=13.5XI+8.8X2+10.5X3

約束條%X1+0.4X2+0.6X3W350

J0.5XI+0.6X2+0.5X3W460

X]20,X220,X320

I

②對(duì)偶規(guī)劃模型

目標(biāo)函數(shù)minw=350yi+460y2

約束條件伍+0.5y2e13.5

0.4yi+0.6y228.8

《0.6yi+0.5y2210.5

yi20,y2與0

三（10%）某服裝廠制造大、中、小三種尺寸的防寒服，所用資源有尼龍綢、尼龍棉、勞動(dòng)

力和縫紉設(shè)備?？p制一件防寒服所需各種資源的數(shù)量如表（單位已適當(dāng)給定）。不考慮固定

費(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元。現(xiàn)欲制定

-生產(chǎn)計(jì)劃使獲得的利潤(rùn)為最大，請(qǐng)寫出其數(shù)學(xué)模型（不解）。（2002）

^號(hào)

小中大

資源

尼龍綢1.61.81.9

尼龍棉1.31.51.6

勞動(dòng)力44.55

縫紉設(shè)備2.83.84.2

解：三、解：設(shè)三種防寒服分別生產(chǎn)XI,X2,X3件。Z表示獲得的利潤(rùn),力》2,丫3分別表示0-1變

量，yi=l表示做第Xi種防寒服（i=l,2,3）

maxz=10x,+12x2+13x3-100^-150y2—200%

IE/+I.8X2+L9》3<1500

1.3/+1.5々+L6X341000

4x,+4.5X2+5X3<4000

2.8%+3.8%2+4.2x3<3000

X]<lOOOOy,

x2<10000y2

x3<10000%

xx,x2,x3>0

乃，為，%=°或1

（三）互補(bǔ)松弛應(yīng)用

maxz=2%]+3x2

2X1+2X2<12

Xj+2x2<8

二（8%）、線性規(guī)劃問題

4x1<16

4X2<12

x2>0

已知其最優(yōu)解為，初＞0,而第1,4兩種資源（相應(yīng)于第1,4兩約束）均有余量，應(yīng)用互

補(bǔ)松弛定理求出原問題和對(duì)偶問題的最優(yōu)解。（2005）

解：二對(duì)偶問題

minIV=12弘+8%+16%+12%

‘2%+%+4月22

<2必+2y2+4y4>3

y,>0,z=l,2,3,4

vx,>0,x2>0,其對(duì)偶問題取嚴(yán)格等式-月+乃+4%=2（*）

.2%+2y2+4汽=3

?.?第1倆種資源有剩余，即原問題約束。腑r格不等式

對(duì)應(yīng)對(duì)偶問題變量乂=0,%=0

13

代入（*）式，y2+4y3=2,2y2=3乃=$,乃=彳

o2

-0■

%

.?.w*=[1281612]/j=14

%

0

z=w=14

由修+%=8#=4

4玉=16x2=2

綜上，原問題最優(yōu)解x=[421,Z*=14

31

oo

對(duì)偶問題最優(yōu)解y=2-8-，卬*=14

（四）靈敏度分析

三（25%）、派公司是一個(gè)生產(chǎn)高爾夫器材的小型公司，近期推出了高、中價(jià)位的高爾

夫袋新產(chǎn)品（標(biāo)準(zhǔn)袋和高檔袋），經(jīng)銷商對(duì)此產(chǎn)品十分感興趣，并訂購(gòu)了派公司下3個(gè)月的

全部產(chǎn)品。

該高爾夫袋的生產(chǎn)過程主要包括4道工序：切割并印染原材料、縫合、成型（插入支

撐架和球棒分離裝置等）、檢驗(yàn)和包裝。有關(guān)數(shù)據(jù)如表1。派公司須決定標(biāo)準(zhǔn)袋和高檔袋各

生產(chǎn)多少可使公司的總利潤(rùn)最大。

表1

單耗7"品

標(biāo)準(zhǔn)袋高檔袋3個(gè)月內(nèi)最大生產(chǎn)能力(小時(shí))

工序

切割印染7/101630

縫合1/25/6600

成型12/3708

檢驗(yàn)包裝1/101/4135

產(chǎn)品單位利潤(rùn)(美元)109

(1)寫出此問題的線性規(guī)劃模型，約束依表1中次序；

(2)引入松弛變量(依約束次序)后用單純形法計(jì)算得某單純形表如表2,請(qǐng)?zhí)钔瓯碇?/p>

空白，并判斷其是否終表，如果是，請(qǐng)寫出最優(yōu)生產(chǎn)計(jì)劃、最大利潤(rùn)和資源剩余;

表2

1090000

CBXBB'bX|x2x3x4x5x6

9x225211.8750-1.31250

0x41200-0.937510.156250

10X]5400-1.2501.8750

0x6180-0.3437500.1406251

-6.9375

(3)寫出此問題的對(duì)偶問題的模型，及對(duì)偶的最優(yōu)解與最優(yōu)值；

(4)寫出成型時(shí)間的影子價(jià)格，求使該影子價(jià)格不變的成型時(shí)間的變化范圍；

(5)若標(biāo)準(zhǔn)袋的利潤(rùn)可能發(fā)生變化，則其在何范圍內(nèi)變化時(shí)，可使原最優(yōu)計(jì)劃不改變?

圖示說明其幾何意義。(2005)

解：三設(shè)標(biāo)準(zhǔn)袋生產(chǎn)吃,高檔袋生產(chǎn)乙

(1)maxZ=IO*]+9x,

7

+x<630

102

15

一,f_1_<、1A【八

q十-j"2-o

26

2

F+-*2708

115

王4--X<]13

io2

X”x2>0

o9oooo

cX%

BB-

為x

2X3X4X54

9X2252011.8750-1.31250

0勺12000-0.937510.156250

10Xi54010-1.2501.8750

0X61800-0.3437500.1406251

00-4.3750-6.93750

b-8y

1.875

_Q9375

:.%=。3-8-73=0-[90100]=-4.375

—1.25

_-0.34375_

vo-y<0(j=l,-,6)

??.是終表

最優(yōu)生產(chǎn)計(jì)劃x=[5402520120018],即普通袋540個(gè)，高檔袋252個(gè)

,*i「540]

??.最大利潤(rùn)Z=[r109]252=7668(美元)

因?yàn)樗沙谧兞?3*0%=120x5=0x6=18

所以第2科資源有剩余，分別為,12X)18

(3)對(duì)偶問題模型：

minW=630yl+600y2+708y3+135y4

711

二H+—乃+乃+—>4210

10-210

5213

+2為+7%+共429

634

>0,y2>0

對(duì)偶問題最優(yōu)解：y<=[4.37506.9675O]

由對(duì)偶問題的強(qiáng)對(duì)偶性知，對(duì)偶問題與原問題的最優(yōu)值相同W=Z=7668（美元）

（4）成型時(shí)間影子價(jià)格為6.9375

使該影子價(jià)格不變的成型時(shí)間的變化范圍應(yīng)滿足

1.8750-1.31250'630

-0.937510.156250600

>0

-1.2501.8750708+AZ?

-0.3437500.1406251135

即

1.875x630-1.3125x(708+A/?)>0

-0.9375x630+lx600-0.15625x(708+A&)>0

-1.25x630+1.875x(708+A/?)>0

-0.34375x630+0.140625x(708+Ab)+lxl35>0

（5）q變化，可能影響檢驗(yàn)數(shù)，故令

%，=C「CBB7P廠=J-[9010+AC0]B?

-1.875

,-0.9375

%二=0-[9010+AC0<0

」-1.25

-0.34375

--1.3125'

、0.15625

生二=C-CB-'P=0-[9010+AC0-<0

5B5」1.875

0.140625

由此得16.875—1.25x(10+AC)H0

-11.8125+1.875x(10+AC)>0

解得-3.75<AC<3.5

二（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)品市

場(chǎng)份額增加量的最低H標(biāo)和兩種可選的廣告方式的單價(jià)。

表1

廣告后市場(chǎng)份額最低增

、電視印刷媒體

量

產(chǎn)品

去污劑0%1%3%

液體洗滌劑3%2%18%

洗衣粉-1%4%4%

廣告單位成本（萬元）100200

其中洗衣粉的市場(chǎng)份額出現(xiàn)負(fù)值是由于液體洗滌劑的份額增加會(huì)造成洗衣粉份額的減

少。

現(xiàn)公司需擬定使廣告總費(fèi)用最少的廣告計(jì)劃，即決定電視和印刷媒體的廣告數(shù)量（分別

記為X1和X2）。

I.請(qǐng)寫出此問題的線性規(guī)劃模型（約束依表1中產(chǎn)品的次序），并將模型化為標(biāo)準(zhǔn)型。

2.用（Min型）單純形法求解此問題，得單純形終表如表2.

表2

100200000MMM

B'bx

CBXBX]2X3X4X5X6x7X8

0X541/3114/3-1/3-1

100X]4-1/30-2/31/30

200X2300100

400/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.minZ=lOOxi+200x2

x2>3

<3玉+2X2>18

+4X2>4

標(biāo)準(zhǔn)型：

x2-x3-3

<3xj+2X2—X4-18

—無1+4%2—%=4

X]>0,x2>0,x3>0,x4>0,x5>0

2.

⑴

100200000MMM

B'b

CBXBX1X2X3x4X5X6x7X8

0400-14/31/3114/3-1/3-1

x5

100X]4102/3-1/30-2/31/30

200X2301-100100

00400/3100/30M-400/3M-100/3M

（2）

最優(yōu)廣告計(jì)劃x=（4,3）J即電視廣告數(shù)量為4,印刷廣告數(shù)量為3,最低費(fèi)用：W=1000

達(dá)成情況為去污劑增加3%,恰好達(dá)標(biāo)

洗衣劑增加18%,恰好達(dá)標(biāo)

洗衣粉增加8%,超額4%完成

(3)

對(duì)偶模型為：

max/=3y,+18y2+4y3

f3y2-y3<100

［乃+2%=4%4200

%>0,y2>0,y3>0

對(duì)偶最優(yōu)解為：y=(400/3,100/3,0)

經(jīng)濟(jì)意義：乂代表三種產(chǎn)品的廣告的投資，3,18,4為每種產(chǎn)品廣告單位投資后的手機(jī)，

100,200代表用于電視及印刷品的投資額，故該模型的含義為用每種產(chǎn)品的頭則使其在不

超過約束的條件下達(dá)到利潤(rùn)最大化。

(3)(30%)考慮線性規(guī)劃問題

Minz=-4xi+X2+30X3-11X4-2X5+3X6+10X7

-2x1+6x3+2x4-3x6+x7=20

-4x1+x2+7x3+x4-x6=10

-5x3+3x4+x5-x6=60

Xj-0(j=12…7)

用單純型法求解，初表及終表如下：

初表

CBXBB'b■4130-11-2310

X|x2X3x4x5x6x7

-20620-31

-41710-10

00-531-10

檢驗(yàn)數(shù)

終表

-4Xl5/4-7/2401/241/12

45/21/1215/12-1/6

3X615/21/401/4-1/2

檢驗(yàn)數(shù)

1.填完初表和終表中各空白,并說明所得最優(yōu)解是否是唯一的，為什么?

1818

2.考慮當(dāng)b變?yōu)?=13時(shí)，對(duì)最優(yōu)解有什么影響?當(dāng)b變?yōu)?=14時(shí)，對(duì)最優(yōu)解是否有影

6060

響？

3.對(duì)偶問題最優(yōu)解？(2003)

解：3.

B'b-4130-11-2310

CBXB

X,x2X3X4X5X6X7

10X720-20620-31

1x210-41710-10

6、

63=30-(101-2)7=-4754=-11-(101-2)=-26

一5,1

-4X15/41-7/24-7/401/2401/12

-11X445/201/12-5/215/120-1/6

3X615/201/4-5/201/41-1/2

檢驗(yàn)數(shù)00302010

①不唯一，因?yàn)榇嬖诜腔兞繖z驗(yàn)數(shù)為零，則有多個(gè)最優(yōu)解

(\

5/24

'1/12-7/241/24、’18、

②B"b=-1/61/125/1213—23—20無影響

12

、-1/21/41/4,、60,

9-

\47

'1/12-7/241/24、'18、1-1/12、

K'b=-1/61/125/1214=-1/12<0有影響

「1/21/41/4,皿

"1/12-7/241/24、

③CBB(-4-113)-1/61/125/12=(31-4)

、—1/21/41/4?

Y=(31-4)

二(17%)已知線性規(guī)劃問題

maxz=(C|+t|)X|+C2X2+C3X3+Ox4+Ox5

。1內(nèi)+。12兀2+。13%3+%4=兒+3,2

S./.v+Cl22^0+。2313+=b)+

x.>0(j=1,…,5)

當(dāng)t產(chǎn)t2=0時(shí)，用單純形法求得最終表如下:

XiX2X3X.1X5

X35/201/211/20

X,5/211/201/61/3

CrZj04042

要求：1.確定Cl,C2,C3,bl,bz,311,312,313,821,322,823的值；

2.當(dāng)t2=0時(shí)，七在什么范圍內(nèi)變化上述最優(yōu)解不變；

3.當(dāng)3=0時(shí)，t2在什么范圍內(nèi)變化上述最優(yōu)基不變。(2002)

1/2‘5/2]J仇=5

解：二、1.B-'b

-1/6、5/2)=1%=10

"1/2、

-4=。2-(。36)

<-1/2,

G=6

(1/2

B設(shè)<

又由X-CB'P"一4=。-3-6=><C2=-2>

A=10.

(0\

一2=。5〃3

7

01/211/20、,0121

1-1/20-1/61/3,、6-30-13

1210]

初表:

-1101)

對(duì)應(yīng)得到a1[=0,a[2=1抱13=2,a2i=3,a22=-l,a23=1

2.L變化，將影響各檢驗(yàn)數(shù)的變化，檢驗(yàn)各非基變量檢驗(yàn)數(shù)，若6jW0,則最優(yōu)解不變

^=-2-(106+外雅210

fl/2)

<=0-(106+f“i/6J<0=>-6<z,<8

2=0—(106+z,)^/J<0

1/20

變化，要使最優(yōu)基不變則B'b>O,因?yàn)?/p>

3.t2變化即b，所以

-1/61/3

1/20\5+3t2)1/2(5+3r,)>0

B^'b=>0=><2=>-5/3<G<15

1/3110+f-l/6(5+3r)+l/3(10+f)>02

-1/62722

二、（18分）某公司生產(chǎn)3種產(chǎn)品：花,乙，X3,需要3種資源：技術(shù)服務(wù)，動(dòng)力和行政

管理，公司經(jīng)理助理根據(jù)公司實(shí)際情況，建立了使總利潤(rùn)最大的產(chǎn)品產(chǎn)量的線性規(guī)

劃模型，并

maxZ=10X1+6x2+4x3

x,+x2+x34100（技術(shù)服務(wù)約束）

s.410x,+4X2+5X3<600（勞動(dòng)力約束）

X

2x,+22+6X3<300（行政管理約束）

采用單純形法求得最優(yōu)表格如下：

10640