大連理工大學(xué)運(yùn)籌學(xué)習(xí)題與答案

線性規(guī)劃習(xí)題一

1.1試述LP模型的要素、組成部分及特征。判斷下述模型是否LP模型并簡(jiǎn)述理由。(式中x,y為變量；0

為參數(shù)；a,b,c,d,e為常數(shù)。)

(1)maxZ=2X-X2-3X3

玉+x2+x3=1

3%j-x2+5X3<8

s.t.<

2Xj-4X2+3X3>5

%>0,x2<0

(2)minz=

k=\

fa/kNbi，i=T2??,m

s-<k=\

xk>0,k=1,2…，相

(3)minz=aiXi+

/=1j=l

■

xi<cpz=1,2,…，相

s.t.<y.<dj=l,2,...n

為+1

n

(4)maxz=7CX

JJ

J=1

s.t.>=i

Xj>0,j=l,2,...n

L2試建立下列問(wèn)題的數(shù)學(xué)模型：

(1)設(shè)備配購(gòu)問(wèn)題

某農(nóng)場(chǎng)要購(gòu)買(mǎi)一批拖拉機(jī)以完成每年三季的工作量：春種330公頃，夏管130公頃，秋收470公頃。可供選

擇的拖拉機(jī)型號(hào)、單臺(tái)投資額及工作能力如下表所示。

拖拉機(jī)型號(hào)單臺(tái)投資單臺(tái)工作能力(公頃)

(元)春種夏管秋收

東方紅5000301741

豐收4500291443

躍進(jìn)4400321642

勝利5200311844

間配購(gòu)哪幾種拖拉機(jī)各幾臺(tái)，才能完成上述每年工作量且使總投資最??？

(2)物資調(diào)運(yùn)問(wèn)題

甲乙兩煤礦供給A,B,C三個(gè)城市的用煤。各礦產(chǎn)量和各市需求如下表所示:

煤礦日產(chǎn)量（噸）城市日需求量（噸）

甲200A100

B150

乙250C200

各礦與各市之間的運(yùn)輸價(jià)格如下表示:

\城

運(yùn)價(jià)（元/噸）

\

ABC

煤礦\

甲9070100

乙806580

問(wèn)應(yīng)如何調(diào)運(yùn)，才能既滿足城市用煤需求，又使運(yùn)輸?shù)目傎M(fèi)用鼓少？

（3）食譜問(wèn)題

某療養(yǎng)院營(yíng)養(yǎng)師要為某類(lèi)病人擬訂本周菜單?可供選擇的蔬菜及其費(fèi)用和所含營(yíng)養(yǎng)成分的數(shù)量，以及這類(lèi)病

人每周所需各種養(yǎng)分的最低數(shù)量如下表所示：

每份所含養(yǎng)分?jǐn)?shù)量（毫克）每份的費(fèi)用（元）

蔬菜、鐵磷維生素A維生素C煙酸

青豆0.451041580.30.15

胡蘿卜0.4528906530.350.15

花菜1.05502550530.60.24

卷心菜0.42575270.150.06

甜菜0.5221550.250.18

土豆0.57523580.80.10

每周養(yǎng)分6.0325175002455.0

最低需求量

另外為了口味的需求，規(guī)定一周內(nèi)所用的卷心菜不多于2份，其它蔬菜不多于4份。若病人每周需14份蔬菜,

問(wèn)選用每種蔬菜各多少份？

（4）下料問(wèn)題

某鋼筋車(chē)間要用一批長(zhǎng)度為10米的鋼筋下料制作長(zhǎng)度為三米的鋼筋90根和長(zhǎng)度為四米的鋼筋60根，問(wèn)怎樣

下料最?。?/p>

用圖解法求解下列LP問(wèn)題：

（1）minZ=6XI+4X2

+x2>1

s.t.3xj+4X2>1.5

%1>0,x2>0

（2）maxz=2.5x）+x2

3%+5X2<15

s.t.+2X2<10

x,>0,x2>0

(3)maxZ=2XI+2X2

—%2—1

s.t.

一0.5%+x2<2

Xj>0,x2>0

(4)maxz=xj+x2

-x2>0

s.t.v3%一%2——3

x,>0,x2>0

(5)minZ=2XI-10X2

%一x2>0

s.t.

<%—5x2——5

Xj>0,x2>0

(6)minz=-10xi-l1x2

3%+4X2<10

5x.+2x?<8

s.t."

玉-

2X2<2

Xj>0,x2>0

1.4把1.3題的(3)-(6)化成標(biāo)準(zhǔn)形.

1.5把下列LP問(wèn)題化成標(biāo)準(zhǔn)形。

(1)minZ=2XI+3X2+5X.3

%1-x?-%32一5

-6%j+7X2-9X3=15

s.t.?

19Xj+7X2+5X3<13

Xj>0,x2<0

(2)minZ=3XI+4X2+2X3+XI

x

3%+X2+3<7

>6

—X]—/+退+=-4

>1,x2>0

1.6證明下述LP問(wèn)題的可行域是一個(gè)空集:

minz=xi-2x2+2x3+x.i

玉+%2+&+Z=4

s.t.ix}+x2-x3-x4=6

Xj,x2,x3,x4>0

1.7已知LP問(wèn)題如下：

minw=xi+2x2-3x3+4x.t

5X2+七+3X4=5

s.t.〈M+4X2+/+犬4=7

x,,x2,x3,x4>0

TTTTT

判斷下述各點(diǎn)：X尸(8,2,7,-4),X2=(l,0,2,1)1X3=(2,0,5,0)X產(chǎn)(0,0,-1,2),XF(3,1,0,0),X,=(2,1/2,1,1/2)

是不是該LP問(wèn)題的可行解、基本解、基本可行解？試從中找出一個(gè)較優(yōu)解。

1.8設(shè)某線性規(guī)劃問(wèn)題的可行域如下：

2x1+x2-x3=25

'玉+3X-x=30

*24

4Al+7龍2-九3-2尤4-光5=85

xt,x2,x3,x4,x5>0

試判斷下述各點(diǎn)：

T

X,=(5,15,0,20,0)X2=(9,7,0,0,8)X3=(15,5,10,0,0)

是否為該可行域的極點(diǎn)并說(shuō)明理由。

1.9設(shè)一標(biāo)準(zhǔn)形LP問(wèn)題的系數(shù)陣為

一102

A=

_316

%=(1,2,1)'是一可行解。試按性質(zhì)4證明中的方法，構(gòu)造出另一個(gè)可行解。

1.10試證明：若LP問(wèn)題有兩個(gè)不同的最優(yōu)基本解，則必有無(wú)窮多個(gè)最優(yōu)解。

1.11設(shè)R“R?UE”為凸集,則

(1)R,+R2={Z|Z=X+Y,XeR,,YSR2}

(2)R,-R2={Z|Z=X-Y,XGRI,YERsl

(3)AR,={Z|Z=xx,XeRl(XeE'}

均為凸集。

1.12設(shè)R,UE”為凸集，i=l,2,…，則R=C&

也為凸集。

1.13試舉出下述某一類(lèi)型的LP問(wèn)題的實(shí)例：產(chǎn)品配比問(wèn)題，配料問(wèn)題，物資調(diào)運(yùn)問(wèn)題，食譜問(wèn)題，下料問(wèn)題

及其它LP問(wèn)題，然后建模并化標(biāo)準(zhǔn)形，再設(shè)法找出一個(gè)基本可行解。

1.14用枚舉法求解下述LP問(wèn)題：

(1)minw=%+4x2+

2王-2尤2+x3=4

s.t.<X|-x3=1

%>0,x2>0,x3>0

(2)minw=Xj—2%+3天

—2X]+*2+——2

s.t.2xt+3X2+4X3=10

xt>0,x2>0,x3>0

（3）1.3題之（2）

（4）1.3題之（6）

1.15某農(nóng)戶年初承包了40畝土地，并備有生產(chǎn)專用資金2500元。該戶勞動(dòng)力情況為：春夏季4000工時(shí)，秋冬季

3500工時(shí)。若有閑余工時(shí)則將為別的農(nóng)戶幫工，其收入為：春夏季0.5.元/工時(shí)，0.40元/工時(shí)。該戶承包的地塊

只適宜種植大豆、玉米、小麥，為此已備齊各種生產(chǎn)資料，因此不必動(dòng)用現(xiàn)金。另外，該農(nóng)戶還飼養(yǎng)奶牛和雞。每

年每頭奶牛需投資400元，每只雞需投資3元。每頭奶牛需用地1.5畝種植飼草，并占用勞動(dòng)力：春夏季0.3工時(shí)

和秋冬季0.6工時(shí)，每年凈收入10元。該農(nóng)戶現(xiàn)有雞舍最多能容納300只雞，牛棚最多能容納8頭奶牛。三種農(nóng)作

物?年需要的勞動(dòng)力及收入情況如下表所示。問(wèn)該農(nóng)戶應(yīng)如何擬訂經(jīng)營(yíng)方案才能使當(dāng)年凈收入最大？試建立該問(wèn)題

的數(shù)學(xué)模型。

大豆玉米小麥

春夏季需工時(shí)/畝203510

秋冬季需工時(shí)/畝507540

凈收入（元/畝）508040

1.16某罐頭食品長(zhǎng)用A,B兩個(gè)等級(jí)的西紅柿加工成整番茄、番茄汁、番茄醬三種罐頭。A,B原料質(zhì)量評(píng)分分別

為90,50分。為保證產(chǎn)品質(zhì)量，該廠規(guī)定三種罐頭的品格（所用原料的質(zhì)量平均分）如下表所示：

罐頭品名整番茄番茄汁番茄醬

品格（分）>80>60

>50

該廠現(xiàn)以0.5公斤6分的價(jià)格購(gòu)進(jìn)1500噸西紅柿，其中可挑出A等西紅柿20%,其余為B等。據(jù)市場(chǎng)預(yù)測(cè)，三

種罐頭的最大需求量為：整番茄800萬(wàn)罐，番茄汁50萬(wàn)罐，番茄醬80萬(wàn)罐。原料耗量為：整番茄0.75公斤/

罐，番茄汁1.0公斤/罐，番茄醬1.25公斤/罐。三種罐頭的價(jià)格及生產(chǎn)費(fèi)用（其中不包括西紅柿原料費(fèi)）如下表

所示。問(wèn)該廠應(yīng)如何擬訂西紅柿罐頭的生產(chǎn)計(jì)劃才能獲利最大？試建立數(shù)學(xué)模型。

（元/罐）

整番茄番茄汁番茄醬

價(jià)格0.860.900.76

加工費(fèi)0.2360.2640.108

其它費(fèi)用0.3510.3840.317

1.17某廠生產(chǎn)甲、乙兩種產(chǎn)品，每種產(chǎn)品都要在A,B兩道工序加工。其中B工序可由或B?完成，但乙產(chǎn)品不

能用以加工。生產(chǎn)這兩種產(chǎn)品都需要C,D,E三種原材料，有關(guān)數(shù)據(jù)如下表所示。又據(jù)市場(chǎng)預(yù)測(cè)，甲產(chǎn)品每天銷(xiāo)

售不超過(guò)30件。問(wèn)應(yīng)如何安排生產(chǎn)才能獲利最大？試建立數(shù)學(xué)模型。

產(chǎn)品單耗日供應(yīng)量單位成本

甲乙數(shù);/單位數(shù)量單位

工A2180工時(shí)6元/工時(shí)

Bi360工時(shí)2元/工時(shí)

序B?1470工時(shí)5元/工時(shí)

原C312300米2元冰

材D53100件1元/件

料E41.515()公斤4元/公斤

其他費(fèi)用（元/件）2629

單價(jià)（元/件）80100

1.18制造某機(jī)床需要A,B,C三種軸，其規(guī)格、需要量如下表所示。各種軸都用長(zhǎng)7.4米的圓鋼來(lái)截毛坯。如果

制造100臺(tái)機(jī)床，問(wèn)最少要用多少根圓鋼？試建立數(shù)學(xué)模型。

軸件規(guī)格：長(zhǎng)度（米）每臺(tái)機(jī)床所需軸件數(shù)量

A2.91

B2.11

C1.21

1.19某木材公司經(jīng)營(yíng)的木材儲(chǔ)存在倉(cāng)庫(kù)中，最大貯存量為20萬(wàn)米3。由于木材價(jià)格隨季節(jié)變化，該公司于每季

初購(gòu)進(jìn)木材，一部分當(dāng)季售出，一部分貯存以后出售。貯存費(fèi)為a+bu,其中a=7元/米=b=10元/米3/季，u為

貯存的季度數(shù)。由于木材久貯易損，因此當(dāng)年所有庫(kù)存木材應(yīng)于秋末售完。各季度木材單價(jià)及銷(xiāo)量如下表所示。

為獲全年最大利潤(rùn)，該公司各季應(yīng)分別購(gòu)銷(xiāo)多少木材？試建立數(shù)學(xué)模型。

季購(gòu)時(shí)價(jià)（元冰3）售出價(jià)（元冰3）最大銷(xiāo)售量（萬(wàn)米b

冬31032110

春32533314

夏34835220

秋34034416

單純型法習(xí)題二

2.1分別用圖解法和單純形法求解下述LP問(wèn)題，并指出單純形法迭代中每一基本可行解跟圖解法可行域中哪一極點(diǎn)

相互對(duì)應(yīng)。

（1）maxz=10Xj+5x2

3x,+4X2<9

s.t.

<5Xj+2X2<8

X,>0,x2>0

(2)maxZ=2XI+X2

5X2<15

6xj+2X2<24

再+x2<5

>0,x2>0

2.2用單純形法求解1.7題。

2.3用單純形法求解下述LP問(wèn)題:

(1)maxz=X[+2X2+3X3+4X4

%+￡+￡+=1

S.t.〈

內(nèi),工2，0了420

(2)第一章例4

(3)maxz=X1+X2+X3+X4

玉+/+工3+工4=6

S.t.{%一％+退一%4=2

%,工2，工3，%42。

(4)minw=x2-3x3+2x5+2x6

—2X2+4X3+X4=12

%+3&+2X5=7

$.t.V

-4X2+3X3+8X5+/=1。

Xj>0,J=1,2,...,6

2.4用單純形法求解下述LP問(wèn)題:

(1)maxZ=2XI+2X2

X(-%2——1

s.t.<一0.5%+X2<2

X)>0,X2>0

(2)maxz=IOx1+5x2

—Xj+421

s.t.4%]-x2>2

X,>0,x2>0

(3)maxz=5xi+3x2+2x3+4x4

5%j+x2+x3+8X4=10

s.t.<2%+4X2+3X3+2X4=10

xpx2,x3,x4>0

(4)minw=2x|+3x2+x3

4X+2X>8

x}+23

32+2X2>6

Xj,x2,x3>0

(5)minw=2x1+x2-x3-x4

X,-x+2X

23-x4=2

2%j+x2-3X3+x4=6

西+12+x3+x4=7

工],工2，x3，142

(6)maxz=10x1+15xz+l2x3

5X1+3%+X3<9

一5%+6X2+15X3<15

2xj+x2+x3>5

X),x2,x3>0

(7)minz=3xr4x2+X3-2x4

2%+x2+2X3+x4=10

x3+2X4<10

,%,-x2+x4>-5

5<+3X2+x3+x4<20

xpx2,x3>0

2.5以2.1題之（1）為例，具體說(shuō)明當(dāng)目標(biāo)函數(shù)中變量的系數(shù)怎樣改變時(shí)，能夠：（1）分別使每個(gè)極點(diǎn)成為最優(yōu)點(diǎn);

（2）使該LP問(wèn)題有多重最優(yōu)解。

2.6分別舉出符合下述情況的LP問(wèn)題之例：（1）多重最優(yōu)解；（2）最優(yōu)解為退化的基本可行解；（3）最優(yōu)解無(wú)界；

（8）無(wú)可行解。

2.7求解1.18題。

2.8在一塊地上種植某種農(nóng)作物，據(jù)以往經(jīng)驗(yàn)，在其生長(zhǎng)過(guò)程中至少需要氮32公斤，磷恰以24公斤為宜，鉀不得超

過(guò)42公斤?，F(xiàn)有四種肥料，其單價(jià)及氮磷鉀含量（％）如右表所示。問(wèn)在該地塊上施用這四種肥料各多少公斤，才

能滿足該農(nóng)作物對(duì)氮磷鉀的需要，又使施肥的總成本最低？

成分

含量(%m甲乙丙T

氮330015

磷502010

鉀14007

單價(jià)（元/公斤）0.040.150.100.13

2.9試用矩陣形式的單純形法解答下列問(wèn)題:

（1）已知用單純形法求解某LP問(wèn)題所得到的初始單純形表及最末單純形表如下，試將表中空白處填上適當(dāng)字符。

G325000

基解凡

X.x2x3X4X5

43121100

46302010

42140001

檢驗(yàn)行

1/2-1/40

01/20

-211

檢驗(yàn)行

⑵已知用單純形法求解某LP問(wèn)題，中間某兩次迭代的單純形表如下，試將表中空白處填上適當(dāng)字符。

Cj354000

基解

XiX2x3XiX5

2.10試用改進(jìn)單純形法求解下述LP問(wèn)題:

(1)maxz=10X1+15X2+12X3

2%+x2+<3

'玉+

2X2+3X3<5

2%+2X2+X3<6

x1,x2,x3>0

(2)maxw=10x?+7x2+4x3+3x4+x5

2M+6X2+x3<7

2%+3X+4X+x+x<8

<2345

%+2X2+3曰+x5<5

Xj20,J=1,2,3,4,5

對(duì)偶原理習(xí)題三

3.1試建立下述LP問(wèn)題的對(duì)偶關(guān)系表，并寫(xiě)出其對(duì)偶問(wèn)題：

(1)maxZ=4X1+3X2+6X3

3^+x2+x3<60

2x,+2X2+3X3<40

s.t.<

2%+2X2+x3<6

xx>0,x2>0,x3>0

(2)minw=60xX+10x2+20x3

3xj+x2+x3>2

%一々+九3——1

s.t.<

%+2X2-x3>1

%>0,x2>0,x3>0

(3)minw=5xr3x2

2%-w+4X3>2

%+工2-2工321

s.t.<

3x)-x2-x3>3

>0,x2>0,x3>0

(4)maxz=4x?+3X2+6X3

=10

x}+2X2+4X3

=15

s.t.{2xl+5X24-3X3

%>0,x2>0,x3>0

3.2試寫(xiě)出下述LP問(wèn)題的對(duì)偶問(wèn)題：

(1)1.1(1)題(2)1.5題(3)2.4(5)題(4)2.4(7)題

(5)minw=2x?+2x2+4x3

2%|+3X2+5X3>2

3X]+<3

x2+7X3

s.t.

%+4X2+6芻=5

x2<0,x3>0

(6)minw=2x1+3x2+6x3+x4

3Xj+4X2+4X3+7X4=21

2%+7X2+3X3+8X4>18

s.t.

x,-2X2+5X3-3X4<4

x]>0,x2<0,x4>0

3.3試證明LP問(wèn)題(P2)是(D2)的對(duì)偶，(P2)是(D2)的對(duì)偶。

3.4試寫(xiě)出下述LP問(wèn)題的對(duì)偶問(wèn)題：

(1)minw=CTX

AX=b

X>a(>0)

⑵minz=

/=1j=l

fx)=

j=i

=bj,j=1,2,…n

i=[

%20

⑶maxz=CjXj

j=i

4產(chǎn)/〈如i=1,2,…,r

s.t.<2_,atjxj=b*i=r+1,r+2,...,m

Xj20,/=l,2,...,s(<ri)

3.5已知LP問(wèn)題：

minz=5X]4-6X2+3X3

5%+5々+3與之50

x}+x2-x3>20

7%+6元2-9X3>30

+x2+x3>7

X

+4X2-153>10

6%j+5X2>45

x2-10x3>20

%>0,x2>0,x3>0

試通過(guò)求解其對(duì)偶問(wèn)題來(lái)確定該LP問(wèn)題的最優(yōu)解。

3.6已知LP問(wèn)題：

maxz=X|+2X2

Xj-x2>2

-x]+x2>1

%,>0,x2>0

（1）試證明它與其對(duì)偶問(wèn)題均無(wú)可行解。

（2）試構(gòu)造一個(gè)LP問(wèn)題，使其本身及其對(duì)偶問(wèn)題均無(wú)可行解。

3.7已知（I）（H）兩個(gè)LP問(wèn)題：

(I)maxZ|=

j=i

<b^i=1,2,...,m

S.t.J=I

XjNO,/=1,2,...,〃

(II)maxz2=CjX.

j=i

j=i

Xj20,/=1,2,…,〃

其中為，白，占均為已知常數(shù)。

設(shè)z；,Z；分別為(I),(11)的最優(yōu)值，y；(i=l,2，…,m)為(I)的對(duì)偶問(wèn)題的最優(yōu)解，求證：

?=|

3.8不用單純形法，利用對(duì)偶性質(zhì)和其它簡(jiǎn)便方法求解下述LP問(wèn)題：

(1)maxW=4XI+3X2+6X3

3再+%+3%3<30

s.t.<2x+4-3X

]2X23<40

x]>0,x2>0,>0

(2)maxz=X|-x2+xj

-N4

<-x2+2/>3

M>0,x2>0,x3>0

3.9已知LP問(wèn)題：maxz=6x|+8x2

5%j+2X2<20

s.t.〈再+

2X2<10

x]>0,x2>0

⑴寫(xiě)出它的對(duì)偶問(wèn)題。

⑵用圖解發(fā)求解原始、對(duì)偶問(wèn)題。識(shí)別兩個(gè)問(wèn)題的所有極點(diǎn)解。

(3)用單純形法求解原始問(wèn)題。在每個(gè)單純形表中，識(shí)別此問(wèn)題的基本可行解及對(duì)偶問(wèn)題的互補(bǔ)基本解。指出它們相

應(yīng)于圖解法中哪個(gè)極點(diǎn)。

(4)按表3-8的格式，列出該問(wèn)題的全部互補(bǔ)基本解。

(5)用對(duì)偶單純形法求解對(duì)偶問(wèn)題，并將結(jié)果與(3)中結(jié)果進(jìn)行對(duì)比。

(6)該問(wèn)題是否滿足互補(bǔ)松弛性？為什么？

3.10用對(duì)偶單純形法求解下述LP問(wèn)題:

(l)minz=Xj+x2

x1+2X2>4

xy<5

3%+x2>6

,Tj>0,x2>0

(2)minz=3XI+2X2+X3

玉+X2+X3<6

Xx-X3>4

X2-X3>3

x]>0,x2>0,>0

(3)2.4(4)題

3.11某廠擬生產(chǎn)甲、乙、丙三種產(chǎn)品，都需要在A,B兩種設(shè)備上加工，有關(guān)數(shù)據(jù)如下表所示:

、\^產(chǎn)品

單耗（臺(tái)時(shí)/件）設(shè)備有效臺(tái)時(shí)

設(shè)廣、

甲乙丙

A12I400

B212500

產(chǎn)值（千元/件）321

（1）如何充分發(fā)揮設(shè)備能力，使產(chǎn)品總產(chǎn)值最大？

（2）若為了提高產(chǎn)量，以每臺(tái)時(shí)350元租金租用外廠A設(shè)備，問(wèn)是否合算？

3.12用對(duì)偶單純形法求解下述LP問(wèn)題：

(1)maxz=3xr2x2-X3

4

玉一馬-X3=

x2+2x3<8

s.t.v

x2->2

X),x2,>0

(2)maxz=2xrx2+2x3

Xj+x2+x3>6

-2Xj+x3>6

s.t.<

2X2->0

xpx2,x3>0

(3)maxz=5xi-8x2-x3+4x4-llx5

2x,-9々-7七+2X4-1lx5>5

%—6X2-6X3+2X4-9X5<3

s.t.?

x,-7X2-8X3+3X4-12X5>4

x15x2,x3,x4,x5>0

3.13用交替單純形法求解3.12題。

靈敏度分析習(xí)題四

4.1試就3.11題解答下列問(wèn)題：

（1）試分別確定甲產(chǎn)品單位產(chǎn)值、B設(shè)備供量各自的影響范圍。

（2）若每月能以39萬(wàn)元租金租用外廠B設(shè)備300臺(tái)時(shí)，則應(yīng)否租用？為什么？

（3）若每月A設(shè)備提供量減少200臺(tái)時(shí)，B設(shè)備供量增加100臺(tái)時(shí)，，試問(wèn)最優(yōu)解與影子價(jià)格有何變化？

4.2已知LP問(wèn)題

maxZ=5XI+2X2+3X3

%1+5X2+2X3<瓦

s.t.

xx-5X2-6X3<b2

%>0,x2>0,x3>0

對(duì)于給定的常數(shù)4和人2,其最優(yōu)單純形表是:

Cj52300

基解X|x2x3x4x5

5X|301X)210

0X5100入2-8-11

檢驗(yàn)行15()0人37入4入5

其中X”X2,入3，入4，入5是常數(shù)。試求:

(1)b1和b2的值。

(2)對(duì)偶問(wèn)題的最優(yōu)解。

(3)X,.x2,入3的值。

(4)參數(shù)C1,C2,C3的影響范圍。

(5)參數(shù)b1,b?的影響范圍。

(6)參數(shù)/2，43，％3的影響范圍。

(7)參數(shù)的影響范圍。

4.3已知LP問(wèn)題

maxZ=-5X|+5X2+13X3

xt+x2+3芻<20

玉+

s.t,<124X2+10X3<90

%>0,x2>0,%3>0

試用單純形法求出最優(yōu)解，然后分別對(duì)下述情況進(jìn)行靈敏度分析:

(1)分別確定參數(shù)C1,乙，。22的影響范圍。

(2)參數(shù)b1從20變?yōu)?0。

(3)參數(shù)b?從90變?yōu)?0。

(4)參數(shù)C3從13變?yōu)?。

(5)X1的系數(shù)變?yōu)?/p>

(6)X2的系數(shù)變?yōu)?/p>

(7)增加一個(gè)約束條件2XI+3X2+5X3《50

(8)把約束條件2變?yōu)镮OX1+5X2+IOX3WIOO

4.4已知LP問(wèn)題

maxZ=2XI+7X2-3X3

X]+3X2+4X3<30

s.t.{X]+4X2-X3<10

x]>0,x2>0,x3>0

給它引進(jìn)松弛變量X4,X5后，用單純形法求得其最優(yōu)方程組如下:

z+x2+x3+2X5=20

<—x2+5X3+x4-x5-20

X1+4%2-x3+/=10

試對(duì)下述情況分別進(jìn)行靈敏度分析:

(1)b1減少20,同時(shí)b2增加10.

-2

(2)改變X3的系數(shù)為二3

2

(3)

(4)的新變x6.

(5)改變目標(biāo)函數(shù)為Z=X|+5X2-2X3.

(6)增加-一個(gè)約束條件3XI+2X2+3X3W25.

(7)改變約束條件2為XI+2X2+2X3^40.

(8)改變約束條件I為2X]+2X2+X3W20,同時(shí)增加一個(gè)約束條件X]+2X2+X3=20.

4.5已知LP問(wèn)題

maxZ=2X|-X2+X3

%一

32X2+2X3<15

-x+x+x<3

s.t.〈123

Xj-x2+x3<4

Xj>0,x2>0,x3>0

給它引進(jìn)松弛變量X4，X5,X6后，用單純形法求得其最優(yōu)方程組如下:

z+2X3+/+/=18

x2+5X3+/+3/=24

2芻+/+*6=7

%+4X3+x4+2X5=21

試對(duì)下述情況分別進(jìn)行靈敏度分析：

(1)分別確定參數(shù)自也，'出的影響范圍。

(2)改變右端為

(3)改變目標(biāo)函數(shù)中X3的系數(shù)為C3=2.

(4)改變目標(biāo)函數(shù)中X1的系數(shù)為c『3.

4

陽(yáng)3

(5)改變X3的系數(shù)為

2

(6)同時(shí)改變XI和X2的系數(shù)為:

(7)改變目標(biāo)函數(shù)為z=5xi+x2+3x3.

(8)改變約束條件1為2X「X2+4X3W12.

(9)增加一個(gè)約束條件2X1+X2+2X3W6O.

運(yùn)輸模型習(xí)題五

5.1某公司有三個(gè)工廠生產(chǎn)某種商品并運(yùn)往四個(gè)調(diào)撥站。工廠1,2,3每月分別生產(chǎn)12,17,11批商品，而每一調(diào)

撥站每月均需接受10批商品。各廠至調(diào)撥站的運(yùn)輸距離(公里)如下表所示。已知每批商品的運(yùn)費(fèi)是100元加上每

公里0.50元。問(wèn)應(yīng)如何調(diào)運(yùn)能使總運(yùn)費(fèi)最少？

(1)撥站I234

18001300400700

2110014006001000

36001200800900

試構(gòu)成該問(wèn)題的表式運(yùn)輸模型;

(2)試建立該問(wèn)題的LP式運(yùn)輸模型；

(3)試用最小元素法和最大差額法分別確定初始方案；

(4)試用位勢(shì)法和閉回路法分別檢驗(yàn)(3)中的一個(gè)方案;

(5)分別從(4)中方案開(kāi)始，求出最優(yōu)方案。

5.2甲，乙兩煤礦日產(chǎn)煤量依次是200,250噸，供應(yīng)A.B,C三個(gè)城市。三個(gè)城市日需求量依次是100,150,200噸。

各礦與各市間的運(yùn)價(jià)(元/噸)如下表所示。應(yīng)如何調(diào)運(yùn)才能既滿足各市用煤需求又使運(yùn)輸?shù)目傎M(fèi)用最少？

XABC

甲9070100

乙806580

(1)試用最小元素法與最大差額法分別確定初始方案；

(2)試用位勢(shì)法與閉回路法分別檢驗(yàn)(1)中的一個(gè)方案;

(3)分別從(2)中方案開(kāi)始，求出最優(yōu)方案。

5.3考慮下表所示的運(yùn)輸問(wèn)題。

地III產(chǎn)量

產(chǎn)好、

1642

2854

銷(xiāo)量33

(1)用表上作業(yè)法求解;

(2)用單純形法求解，并比較兩種方法的計(jì)算時(shí)間。

5.4考慮下述運(yùn)輸問(wèn)題。

銷(xiāo)地B1B：產(chǎn)量

B2

產(chǎn)

B4

A.48757

35433

A2

54966

A3

銷(xiāo)量4433

試用下述兩種方法分別求解，并比較迭代次數(shù):

(1)最小元素法一位勢(shì)法一閉回路法；

(2)最大差額法-閉回路法。

5.5求解下述運(yùn)輸問(wèn)題:

銷(xiāo)地B,B產(chǎn)量

2B3B4

產(chǎn)By

A\7526415

4973620

A2

5285715

A3

銷(xiāo)量2020151015

5.6求解前進(jìn)拖拉機(jī)廠的生產(chǎn)調(diào)度問(wèn)題(見(jiàn)§3例6)

5.7某公司經(jīng)營(yíng)的一種產(chǎn)品擁有四個(gè)客戶，由于公司所轄三個(gè)工廠生產(chǎn)，每月產(chǎn)量分別為3000,5000,4000件。該

公司已承諾下月出售4000件給客戶1,出售3000件給客戶2以及至少1000件給客戶3?？蛻?與4都想盡可能多

購(gòu)剩下的件數(shù)。已知各廠運(yùn)銷(xiāo)一件產(chǎn)品給客戶可得到的凈利潤(rùn)如下表所示。問(wèn)公司應(yīng)如何擬訂運(yùn)銷(xiāo)方案，才能在履

行諾言的前提下獲利最多？

x1234

165636264

268676562

363605960

5.8某食品公司所轄F1,F?,F3三個(gè)工廠每天分別生產(chǎn)20,22,4噸糖果，運(yùn)

往的庫(kù)存量分別為21,25噸。各地之間的運(yùn)價(jià)(元/噸)如下表所示。試求總運(yùn)費(fèi)最少的調(diào)運(yùn)方案。

終點(diǎn)FiF二W,

始“、

w2

Fi566

667

F2

1899

F3

W(91010

5.9某肉食品加工廠按合同要在今后兩個(gè)月內(nèi)為某個(gè)肉蛋禽聯(lián)營(yíng)商店加工某種熟肉制品14500公斤。其中第一個(gè)月需

交貨8000公斤，若未交夠，不足的部分可由第二個(gè)月補(bǔ)交，但補(bǔ)交的數(shù)量須回扣給商店0.1元/公斤。全部加工任務(wù)

必須在第二個(gè)月末前完成，否則將重金賠償商店損失。另若加工好的肉制品當(dāng)月不交貨，則每貯存一個(gè)月需花冷藏

費(fèi)0.05元/公斤。該廠的加工能力及加工費(fèi)用如下表所示。試為該項(xiàng)目合同擬訂?個(gè)總費(fèi)用最少的生產(chǎn)調(diào)度方案。

\月份

加工能力（公斤）加工費(fèi)（而公斤）

1212

生產(chǎn)方鼠

正常生產(chǎn)550060000.600.60

加班生產(chǎn)200025000.750.70

外協(xié)生產(chǎn)200020000.850.80

5.10某造船廠根據(jù)合同要在今，明，后年各提供三艘規(guī)格型號(hào)相同的貨輪。已知該廠這三年內(nèi)生產(chǎn)這種貨輪的能力

及成本如下表所示。其中加班生產(chǎn)的成本比正常生產(chǎn)高出70萬(wàn)元/艘。若造好的貨輪當(dāng)年不交貨，沒(méi)積壓一年將損失

40萬(wàn)元/艘。該廠目前已積壓兩艘該型號(hào)貨輪，并且希望后來(lái)未完成合同后還能儲(chǔ)備一艘。該廠應(yīng)如何安排生產(chǎn)，使

總的生產(chǎn)費(fèi)用最少？

年度正常生產(chǎn)能力加班生產(chǎn)能力正常生產(chǎn)的成本

（艘）（艘）（萬(wàn)元/艘）

今23500

明42600

后13550

整數(shù)規(guī)劃習(xí)題六

6.1下述IP問(wèn)題能否通過(guò)LP解的圓整而得最優(yōu)？

(1)maxZ=3XI+2X2

2xl+3%2414

2%,+X2<9

s.t.《

x,>0,x2>0

不馬為整數(shù)

(2)maxZ=3XI+2X2

-4%j+3x2<6

否

34-2X2<18

s.t.《

x,>0,x2>0

々為整數(shù)

6.2試用分支定界法求解下述IP問(wèn)題。

(1)maxZ=5X|+8X2

+x2<6

5x,+9X2<45

s.t.?

%1>0,x2>0

內(nèi),馬為整數(shù)

(2)maxz=Xj+x2

I4xi+9X2<51

-6X]+3X2<1

s.t.<

%]>0,x2>0

X]，W為整數(shù)

(3)maxz=x1+2x2

-2Xj+4X2<I

2X1+4X2>3

s.t.v

2x}+x2<3

斗巧為整數(shù)

(4)maxz=xr2x2

-5Xj+5X2<4

一3玉+3X2>1

%1>0

X1,冗2為整數(shù)

(5)maxZ=3X]+2X2

2x,-4X2+2X3=5

4%+2X2+2X4=3

s.t.

xpx2,x3,x4>0

々，當(dāng)為整數(shù)

6.3試用割平面法求解下述IP問(wèn)題。

(1)6.2題之(1)；

(2)maxz=X]+x2

2x,+x2<6

4X[+5X2<20

%1>0,x2>0

為整數(shù)

(3)maxZ=3XI+X2

2xl+x2<5

2xl-x2>2

>0,x2>0

小々為整數(shù)

6.4試建立下述問(wèn)題的數(shù)學(xué)模型：

(1)設(shè)有m臺(tái)同--類(lèi)型的機(jī)床，有n(>m)種零件各一個(gè)要在這些機(jī)床上加工，加工一個(gè)第j種零件需要印機(jī)時(shí)。應(yīng)

如何分配加工任務(wù)，才能使各機(jī)床的負(fù)荷盡可能均衡。

(2)某省外貿(mào)局?jǐn)M從下列應(yīng)試者中招聘四名工作人員，希望所招四人平均業(yè)務(wù)能力評(píng)分最高，且滿足下述要求：①

專業(yè)不得相同；②女性最多不超過(guò)二人；③至少有一名精通日語(yǔ)者：④精通英語(yǔ)者最多入選一人。

姓名性別專業(yè)精通語(yǔ)種業(yè)務(wù)能力評(píng)分

戴勝春男紡織英95

楊光女機(jī)械英93

馬躍男化工德87

李玉芬女電子法87

康平男機(jī)械日83

姜潔女食品日73

（3）某廠為生產(chǎn)某種新產(chǎn)品設(shè)計(jì)了三種生產(chǎn)方案，如下表所示:

方案一次性投資生產(chǎn)費(fèi)用生產(chǎn)能力

（萬(wàn)元）（元/件）（萬(wàn)件）

I1058

II16414

11125322

該產(chǎn)品銷(xiāo)價(jià)為每件10元。據(jù)市場(chǎng)調(diào)研，在該產(chǎn)品生命周期內(nèi)的需求量為30萬(wàn)見(jiàn)。應(yīng)如何擬訂生產(chǎn)計(jì)劃能使經(jīng)濟(jì)效

益最佳？

（4）某石油化學(xué)工業(yè)公司的某項(xiàng)產(chǎn)品售價(jià)為每公升1.20元，產(chǎn)量隨生產(chǎn)過(guò)程中溫度的升高而增加，其數(shù)量關(guān)系如圖

6-15所示。假定產(chǎn)品成本與生產(chǎn)中的溫度成正比，每提高一度的費(fèi)用為30元，則應(yīng)生產(chǎn)多少公升該項(xiàng)產(chǎn)品，才能使

利潤(rùn)為最大？

圖6-15

（5）考慮1.2題之（2）.假定預(yù)計(jì)明年A.B,C三市用煤量分別增加8,10,12萬(wàn)噸。計(jì)劃部門(mén)為了使產(chǎn)銷(xiāo)平衡，打

算增加一套年產(chǎn)30萬(wàn)噸煤的成套設(shè)備，這套設(shè)備安放到甲，乙煤礦，年產(chǎn)30萬(wàn)噸煤所增加的生產(chǎn)費(fèi)用分別為20,

25萬(wàn)元。應(yīng)講設(shè)備撥給哪個(gè)煤礦，能使增加的總費(fèi)用（包括生產(chǎn)與運(yùn)輸兩部分）為最低？

（6）某人要去A市探親，由于他已領(lǐng)取了個(gè)體經(jīng)營(yíng)（干鮮水果）的執(zhí)照，因此打算順便販運(yùn)本地產(chǎn)的橘子，香蕉兩

種鮮果。橘子，香蕉在本地的購(gòu)價(jià)分別為每箱4,5元，每箱毛重分別為8,12公斤。由于春節(jié)將臨，因此他考慮兩

種販運(yùn)方式：若乘飛機(jī)，能在除夕前趕到，從而能賣(mài)高價(jià)，且能保證果品無(wú)損；若乘輪船，則在初四趕到，只能賣(mài)

中高價(jià)格，且因途中果品會(huì)有損傷而使每箱收入減少10%,有關(guān)數(shù)據(jù)如下表所示。另外，他已決定要用相當(dāng)于毛重

各為半箱數(shù)量的橘子，香蕉饋贈(zèng)親友，而且途中要攜帶2公斤的生活日用品。問(wèn)他應(yīng)乘坐哪種交通工具且攜帶兩種

果品各多少箱，才能使這次販運(yùn)預(yù)計(jì)盈利最高。

販運(yùn)方式單程票價(jià)免費(fèi)攜重超重收費(fèi)限重限容A市時(shí)價(jià)（元/箱）

（元）（公斤）（元/公斤）（公斤）（箱數(shù)）

橘子香蕉

飛機(jī)450101.005052428

輪船60300.40100102023

6.5考慮下述數(shù)學(xué)模型

min2=工(3)+〉(%2)

滿足下述約束條件：

(1)非X210即％2210；

(2)下列不等式至少有一個(gè)成立:

(3),一看|=0獲5,或10；

(4)%,>0,x2>0：

20+5%,冗]>0

其中：/(斗)=?

0,Xj=0

12+6X,X>0

/(不)=〈22

0,x2=0

試把此模型化為一個(gè)混合整數(shù)規(guī)劃模型。

6.6試用異序枚舉法求解下述0-1規(guī)劃：

(1)maxz=3xr2x2+5x3

X]+2X2-x3<2

%+4X2+x3<4

x1+x2