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

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

1.1試述LP模型的要素、組成部分及特征。判斷下述模型是否LP模型并簡述理由。(式中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試建立下列問題的數(shù)學(xué)模型：

(1)設(shè)備配購問題

某農(nóng)場要購買一批拖拉機以完成每年三季的工作量：春種330公頃，夏管130公頃，秋收470公頃?？晒┻x

擇的拖拉機型號、單臺投資額及工作能力如下表所示。

拖拉機型號單臺投資單臺工作能力(公頃)

(元)春種夏管秋收

東方紅5000301741

豐收4500291443

躍進4400321642

勝利5200311844

間配購哪幾種拖拉機各幾臺，才能完成上述每年工作量且使總投資最??？

(2)物資調(diào)運問題

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

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

甲200A100

B150

乙250C200

各礦與各市之間的運輸價格如下表示:

\城

運價（元/噸）

\

ABC

煤礦\

甲9070100

乙806580

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

（3）食譜問題

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

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

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

蔬菜、鐵磷維生素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份蔬菜,

問選用每種蔬菜各多少份？

（4）下料問題

某鋼筋車間要用一批長度為10米的鋼筋下料制作長度為三米的鋼筋90根和長度為四米的鋼筋60根，問怎樣

下料最??？

用圖解法求解下列LP問題：

（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問題化成標(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問題的可行域是一個空集:

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

玉+%2+&+Z=4

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

Xj,x2,x3,x4>0

1.7已知LP問題如下：

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

5X2+七+3X4=5

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

x,,x2,x3,x4>0

TTTTT

判斷下述各點：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問題的可行解、基本解、基本可行解？試從中找出一個較優(yōu)解。

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

2x1+x2-x3=25

'玉+3X-x=30

*24

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

xt,x2,x3,x4,x5>0

試判斷下述各點：

T

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

是否為該可行域的極點并說明理由。

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

一102

A=

_316

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

1.10試證明：若LP問題有兩個不同的最優(yōu)基本解，則必有無窮多個最優(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試舉出下述某一類型的LP問題的實例：產(chǎn)品配比問題，配料問題，物資調(diào)運問題，食譜問題，下料問題

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

1.14用枚舉法求解下述LP問題：

(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元。該戶勞動力情況為：春夏季4000工時，秋冬季

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

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

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

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

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

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

大豆玉米小麥

春夏季需工時/畝203510

秋冬季需工時/畝507540

凈收入（元/畝）508040

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

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

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

品格（分）>80>60

>50

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

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

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

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

（元/罐）

整番茄番茄汁番茄醬

價格0.860.900.76

加工費0.2360.2640.108

其它費用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ù)市場預(yù)測，甲產(chǎn)品每天銷

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

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

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

工A2180工時6元/工時

Bi360工時2元/工時

序B?1470工時5元/工時

原C312300米2元冰

材D53100件1元/件

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

其他費用（元/件）2629

單價（元/件）80100

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

制造100臺機床，問最少要用多少根圓鋼？試建立數(shù)學(xué)模型。

軸件規(guī)格：長度（米）每臺機床所需軸件數(shù)量

A2.91

B2.11

C1.21

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

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

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

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

季購時價（元冰3）售出價（元冰3）最大銷售量（萬米b

冬31032110

春32533314

夏34835220

秋34034416

單純型法習(xí)題二

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

相互對應(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問題:

(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問題:

(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）為例，具體說明當(dāng)目標(biāo)函數(shù)中變量的系數(shù)怎樣改變時，能夠：（1）分別使每個極點成為最優(yōu)點;

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

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

（8）無可行解。

2.7求解1.18題。

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

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

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

成分

含量(%m甲乙丙T

氮330015

磷502010

鉀14007

單價（元/公斤）0.040.150.100.13

2.9試用矩陣形式的單純形法解答下列問題:

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

G325000

基解凡

X.x2x3X4X5

43121100

46302010

42140001

檢驗行

1/2-1/40

01/20

-211

檢驗行

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

Cj354000

基解

XiX2x3XiX5

2.10試用改進單純形法求解下述LP問題:

(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

對偶原理習(xí)題三

3.1試建立下述LP問題的對偶關(guā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試寫出下述LP問題的對偶問題：

(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問題(P2)是(D2)的對偶，(P2)是(D2)的對偶。

3.4試寫出下述LP問題的對偶問題：

(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問題：

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

試通過求解其對偶問題來確定該LP問題的最優(yōu)解。

3.6已知LP問題：

maxz=X|+2X2

Xj-x2>2

-x]+x2>1

%,>0,x2>0

（1）試證明它與其對偶問題均無可行解。

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

3.7已知（I）（H）兩個LP問題：

(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)的對偶問題的最優(yōu)解，求證：

?=|

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

(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問題：maxz=6x|+8x2

5%j+2X2<20

s.t.〈再+

2X2<10

x]>0,x2>0

⑴寫出它的對偶問題。

⑵用圖解發(fā)求解原始、對偶問題。識別兩個問題的所有極點解。

(3)用單純形法求解原始問題。在每個單純形表中，識別此問題的基本可行解及對偶問題的互補基本解。指出它們相

應(yīng)于圖解法中哪個極點。

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

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

(6)該問題是否滿足互補松弛性？為什么？

3.10用對偶單純形法求解下述LP問題:

(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)品

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

設(shè)廣、

甲乙丙

A12I400

B212500

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

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

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

3.12用對偶單純形法求解下述LP問題：

(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題解答下列問題：

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

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

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

4.2已知LP問題

maxZ=5XI+2X2+3X3

%1+5X2+2X3<瓦

s.t.

xx-5X2-6X3<b2

%>0,x2>0,x3>0

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

Cj52300

基解X|x2x3x4x5

5X|301X)210

0X5100入2-8-11

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

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

(1)b1和b2的值。

(2)對偶問題的最優(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問題

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

xt+x2+3芻<20

玉+

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

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

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

(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)增加一個約束條件2XI+3X2+5X3《50

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

4.4已知LP問題

maxZ=2XI+7X2-3X3

X]+3X2+4X3<30

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

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

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

z+x2+x3+2X5=20

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

X1+4%2-x3+/=10

試對下述情況分別進行靈敏度分析:

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

-2

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

2

(3)

(4)的新變x6.

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

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

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

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

4.5已知LP問題

maxZ=2X|-X2+X3

%一

32X2+2X3<15

-x+x+x<3

s.t.〈123

Xj-x2+x3<4

Xj>0,x2>0,x3>0

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

z+2X3+/+/=18

x2+5X3+/+3/=24

2芻+/+*6=7

%+4X3+x4+2X5=21

試對下述情況分別進行靈敏度分析：

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

(2)改變右端為

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

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

4

陽3

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

2

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

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

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

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

運輸模型習(xí)題五

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

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

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

(1)撥站I234

18001300400700

2110014006001000

36001200800900

試構(gòu)成該問題的表式運輸模型;

(2)試建立該問題的LP式運輸模型；

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

(4)試用位勢法和閉回路法分別檢驗(3)中的一個方案;

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

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

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

XABC

甲9070100

乙806580

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

(2)試用位勢法與閉回路法分別檢驗(1)中的一個方案;

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

5.3考慮下表所示的運輸問題。

地III產(chǎn)量

產(chǎn)好、

1642

2854

銷量33

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

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

5.4考慮下述運輸問題。

銷地B1B：產(chǎn)量

B2

產(chǎn)

B4

A.48757

35433

A2

54966

A3

銷量4433

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

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

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

5.5求解下述運輸問題:

銷地B,B產(chǎn)量

2B3B4

產(chǎn)By

A\7526415

4973620

A2

5285715

A3

銷量2020151015

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

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

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

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

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

x1234

165636264

268676562

363605960

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

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

終點FiF二W,

始“、

w2

Fi566

667

F2

1899

F3

W(91010

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

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

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

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

\月份

加工能力（公斤）加工費（而公斤）

1212

生產(chǎn)方鼠

正常生產(chǎn)550060000.600.60

加班生產(chǎn)200025000.750.70

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

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

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

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

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

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

（艘）（艘）（萬元/艘）

今23500

明42600

后13550

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

6.1下述IP問題能否通過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問題。

(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問題。

(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試建立下述問題的數(shù)學(xué)模型：

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

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

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

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

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

戴勝春男紡織英95

楊光女機械英93

馬躍男化工德87

李玉芬女電子法87

康平男機械日83

姜潔女食品日73

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

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

（萬元）（元/件）（萬件）

I1058

II16414

11125322

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

益最佳？

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

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

利潤為最大？

圖6-15

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

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

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

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

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

種販運方式：若乘飛機，能在除夕前趕到，從而能賣高價，且能保證果品無損；若乘輪船，則在初四趕到，只能賣

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

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

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

販運方式單程票價免費攜重超重收費限重限容A市時價（元/箱）

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

橘子香蕉

飛機450101.005052428

輪船60300.40100102023

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

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

滿足下述約束條件：

(1)非X210即％2210；

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

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

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

20+5%,冗]>0

其中：/(斗)=?

0,Xj=0

12+6X,X>0

/(不)=〈22

0,x2=0

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

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

(1)maxz=3xr2x2+5x3

X]+2X2-x3<2

%+4X2+x3<4

x1+x2