大连理工大学运筹学习题与答案

线性规划习题一

1.1试述LP模型的要素、组成部分及特征。判断下述模型是否LP模型并简述理由。(式中x,y为变量；0

为参数；a,b,c,d,e为常数。)

(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试建立下列问题的数学模型：

(1)设备配购问题

某农场要购买一批拖拉机以完成每年三季的工作量：春种330公顷，夏管130公顷，秋收470公顷。可供选

择的拖拉机型号、单台投资额及工作能力如下表所示。

拖拉机型号单台投资单台工作能力(公顷)

(元)春种夏管秋收

东方红5000301741

丰收4500291443

跃进4400321642

胜利5200311844

间配购哪几种拖拉机各几台，才能完成上述每年工作量且使总投资最小？

(2)物资调运问题

甲乙两煤矿供给A,B,C三个城市的用煤。各矿产量和各市需求如下表所示:

煤矿日产量（吨）城市日需求量（吨）

甲200A100

B150

乙250C200

各矿与各市之间的运输价格如下表示:

\城

运价（元/吨）

\

ABC

煤矿\

甲9070100

乙806580

问应如何调运，才能既满足城市用煤需求，又使运输的总费用鼓少？

（3）食谱问题

某疗养院营养师要为某类病人拟订本周菜单•可供选择的蔬菜及其费用和所含营养成分的数量，以及这类病

人每周所需各种养分的最低数量如下表所示：

每份所含养分数量（毫克）每份的费用（元）

蔬菜、铁磷维生素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

每周养分6.0325175002455.0

最低需求量

另外为了口味的需求，规定一周内所用的卷心菜不多于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)化成标准形.

1.5把下列LP问题化成标准形。

(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产(0,0,-1,2),XF(3,1,0,0),X,=(2,1/2,1,1/2)

是不是该LP问题的可行解、基本解、基本可行解？试从中找出一个较优解。

1.8设某线性规划问题的可行域如下：

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设一标准形LP问题的系数阵为

一102

A=

_316

%=(1,2,1)'是一可行解。试按性质4证明中的方法，构造出另一个可行解。

1.10试证明：若LP问题有两个不同的最优基本解，则必有无穷多个最优解。

1.11设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设R,UE”为凸集，i=l,2,…，则R=C&

也为凸集。

1.13试举出下述某一类型的LP问题的实例：产品配比问题，配料问题，物资调运问题，食谱问题，下料问题

及其它LP问题，然后建模并化标准形，再设法找出一个基本可行解。

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某农户年初承包了40亩土地，并备有生产专用资金2500元。该户劳动力情况为：春夏季4000工时，秋冬季

3500工时。若有闲余工时则将为别的农户帮工，其收入为：春夏季0.5.元/工时，0.40元/工时。该户承包的地块

只适宜种植大豆、玉米、小麦，为此已备齐各种生产资料，因此不必动用现金。另外，该农户还饲养奶牛和鸡。每

年每头奶牛需投资400元，每只鸡需投资3元。每头奶牛需用地1.5亩种植饲草，并占用劳动力：春夏季0.3工时

和秋冬季0.6工时，每年净收入10元。该农户现有鸡舍最多能容纳300只鸡，牛棚最多能容纳8头奶牛。三种农作

物•年需要的劳动力及收入情况如下表所示。问该农户应如何拟订经营方案才能使当年净收入最大？试建立该问题

的数学模型。

大豆玉米小麦

春夏季需工时/亩203510

秋冬季需工时/亩507540

净收入（元/亩）508040

1.16某罐头食品长用A,B两个等级的西红柿加工成整番茄、番茄汁、番茄酱三种罐头。A,B原料质量评分分别

为90,50分。为保证产品质量，该厂规定三种罐头的品格（所用原料的质量平均分）如下表所示：

罐头品名整番茄番茄汁番茄酱

品格（分）>80>60

>50

该厂现以0.5公斤6分的价格购进1500吨西红柿，其中可挑出A等西红柿20%,其余为B等。据市场预测，三

种罐头的最大需求量为：整番茄800万罐，番茄汁50万罐，番茄酱80万罐。原料耗量为：整番茄0.75公斤/

罐，番茄汁1.0公斤/罐，番茄酱1.25公斤/罐。三种罐头的价格及生产费用（其中不包括西红柿原料费）如下表

所示。问该厂应如何拟订西红柿罐头的生产计划才能获利最大？试建立数学模型。

（元/罐）

整番茄番茄汁番茄酱

价格0.860.900.76

加工费0.2360.2640.108

其它费用0.3510.3840.317

1.17某厂生产甲、乙两种产品，每种产品都要在A,B两道工序加工。其中B工序可由或B?完成，但乙产品不

能用以加工。生产这两种产品都需要C,D,E三种原材料，有关数据如下表所示。又据市场预测，甲产品每天销

售不超过30件。问应如何安排生产才能获利最大？试建立数学模型。

产品单耗日供应量单位成本

甲乙数;/单位数量单位

工A2180工时6元/工时

Bi360工时2元/工时

序B?1470工时5元/工时

原C312300米2元冰

材D53100件1元/件

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

其他费用（元/件）2629

单价（元/件）80100

1.18制造某机床需要A,B,C三种轴，其规格、需要量如下表所示。各种轴都用长7.4米的圆钢来截毛坯。如果

制造100台机床，问最少要用多少根圆钢？试建立数学模型。

轴件规格：长度（米）每台机床所需轴件数量

A2.91

B2.11

C1.21

1.19某木材公司经营的木材储存在仓库中，最大贮存量为20万米3。由于木材价格随季节变化，该公司于每季

初购进木材，一部分当季售出，一部分贮存以后出售。贮存费为a+bu,其中a=7元/米=b=10元/米3/季，u为

贮存的季度数。由于木材久贮易损，因此当年所有库存木材应于秋末售完。各季度木材单价及销量如下表所示。

为获全年最大利润，该公司各季应分别购销多少木材？试建立数学模型。

季购时价（元冰3）售出价（元冰3）最大销售量（万米b

冬31032110

春32533314

夏34835220

秋34034416

单纯型法习题二

2.1分别用图解法和单纯形法求解下述LP问题，并指出单纯形法迭代中每一基本可行解跟图解法可行域中哪一极点

相互对应。

（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.〈

内,工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）为例，具体说明当目标函数中变量的系数怎样改变时，能够：（1）分别使每个极点成为最优点;

（2）使该LP问题有多重最优解。

2.6分别举出符合下述情况的LP问题之例：（1）多重最优解；（2）最优解为退化的基本可行解；（3）最优解无界；

（8）无可行解。

2.7求解1.18题。

2.8在一块地上种植某种农作物，据以往经验，在其生长过程中至少需要氮32公斤，磷恰以24公斤为宜，钾不得超

过42公斤。现有四种肥料，其单价及氮磷钾含量（％）如右表所示。问在该地块上施用这四种肥料各多少公斤，才

能满足该农作物对氮磷钾的需要，又使施肥的总成本最低？

成分

含量(%m甲乙丙T

氮330015

磷502010

钾14007

单价（元/公斤）0.040.150.100.13

2.9试用矩阵形式的单纯形法解答下列问题:

（1）已知用单纯形法求解某LP问题所得到的初始单纯形表及最末单纯形表如下，试将表中空白处填上适当字符。

G325000

基解凡

X.x2x3X4X5

43121100

46302010

42140001

检验行

1/2-1/40

01/20

-211

检验行

⑵已知用单纯形法求解某LP问题，中间某两次迭代的单纯形表如下，试将表中空白处填上适当字符。

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

对偶原理习题三

3.1试建立下述LP问题的对偶关系表，并写出其对偶问题：

(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产/〈如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问题的最优解。

3.6已知LP问题：

maxz=X|+2X2

Xj-x2>2

-x]+x2>1

%,>0,x2>0

（1）试证明它与其对偶问题均无可行解。

（2）试构造一个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,…,〃

其中为，白，占均为已知常数。

设z；,Z；分别为(I),(11)的最优值，y；(i=l,2，…,m)为(I)的对偶问题的最优解，求证：

?=|

3.8不用单纯形法，利用对偶性质和其它简便方法求解下述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

⑴写出它的对偶问题。

⑵用图解发求解原始、对偶问题。识别两个问题的所有极点解。

(3)用单纯形法求解原始问题。在每个单纯形表中，识别此问题的基本可行解及对偶问题的互补基本解。指出它们相

应于图解法中哪个极点。

(4)按表3-8的格式，列出该问题的全部互补基本解。

(5)用对偶单纯形法求解对偶问题，并将结果与(3)中结果进行对比。

(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某厂拟生产甲、乙、丙三种产品，都需要在A,B两种设备上加工，有关数据如下表所示:

、\^产品

单耗（台时/件）设备有效台时

设广、

甲乙丙

A12I400

B212500

产值（千元/件）321

（1）如何充分发挥设备能力，使产品总产值最大？

（2）若为了提高产量，以每台时350元租金租用外厂A设备，问是否合算？

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题。

灵敏度分析习题四

4.1试就3.11题解答下列问题：

（1）试分别确定甲产品单位产值、B设备供量各自的影响范围。

（2）若每月能以39万元租金租用外厂B设备300台时，则应否租用？为什么？

（3）若每月A设备提供量减少200台时，B设备供量增加100台时，，试问最优解与影子价格有何变化？

4.2已知LP问题

maxZ=5XI+2X2+3X3

%1+5X2+2X3<瓦

s.t.

xx-5X2-6X3<b2

%>0,x2>0,x3>0

对于给定的常数4和人2,其最优单纯形表是:

Cj52300

基解X|x2x3x4x5

5X|301X)210

0X5100入2-8-11

检验行15()0人37入4入5

其中X”X2,入3，入4，入5是常数。试求:

(1)b1和b2的值。

(2)对偶问题的最优解。

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

(4)参数C1,C2,C3的影响范围。

(5)参数b1,b?的影响范围。

(6)参数/2，43，％3的影响范围。

(7)参数的影响范围。

4.3已知LP问题

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

xt+x2+3刍<20

玉+

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

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

试用单纯形法求出最优解，然后分别对下述情况进行灵敏度分析:

(1)分别确定参数C1,乙，。22的影响范围。

(2)参数b1从20变为30。

(3)参数b?从90变为70。

(4)参数C3从13变为8。

(5)X1的系数变为

(6)X2的系数变为

(7)增加一个约束条件2XI+3X2+5X3《50

(8)把约束条件2变为IOX1+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后，用单纯形法求得其最优方程组如下:

z+x2+x3+2X5=20

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

X1+4%2-x3+/=10

试对下述情况分别进行灵敏度分析:

(1)b1减少20,同时b2增加10.

-2

(2)改变X3的系数为二3

2

(3)

(4)的新变x6.

(5)改变目标函数为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后，用单纯形法求得其最优方程组如下:

z+2X3+/+/=18

x2+5X3+/+3/=24

2刍+/+*6=7

%+4X3+x4+2X5=21

试对下述情况分别进行灵敏度分析：

(1)分别确定参数自也，'出的影响范围。

(2)改变右端为

(3)改变目标函数中X3的系数为C3=2.

(4)改变目标函数中X1的系数为c『3.

4

阳3

(5)改变X3的系数为

2

(6)同时改变XI和X2的系数为:

(7)改变目标函数为z=5xi+x2+3x3.

(8)改变约束条件1为2X「X2+4X3W12.

(9)增加一个约束条件2X1+X2+2X3W6O.

运输模型习题五

5.1某公司有三个工厂生产某种商品并运往四个调拨站。工厂1,2,3每月分别生产12,17,11批商品，而每一调

拨站每月均需接受10批商品。各厂至调拨站的运输距离(公里)如下表所示。已知每批商品的运费是100元加上每

公里0.50元。问应如何调运能使总运费最少？

(1)拨站I234

18001300400700

2110014006001000

36001200800900

试构成该问题的表式运输模型;

(2)试建立该问题的LP式运输模型；

(3)试用最小元素法和最大差额法分别确定初始方案；

(4)试用位势法和闭回路法分别检验(3)中的一个方案;

(5)分别从(4)中方案开始，求出最优方案。

5.2甲，乙两煤矿日产煤量依次是200,250吨，供应A.B,C三个城市。三个城市日需求量依次是100,150,200吨。

各矿与各市间的运价(元/吨)如下表所示。应如何调运才能既满足各市用煤需求又使运输的总费用最少？

XABC

甲9070100

乙806580

(1)试用最小元素法与最大差额法分别确定初始方案；

(2)试用位势法与闭回路法分别检验(1)中的一个方案;

(3)分别从(2)中方案开始，求出最优方案。

5.3考虑下表所示的运输问题。

地III产量

产好、

1642

2854

销量33

(1)用表上作业法求解;

(2)用单纯形法求解，并比较两种方法的计算时间。

5.4考虑下述运输问题。

销地B1B：产量

B2

产

B4

A.48757

35433

A2

54966

A3

销量4433

试用下述两种方法分别求解，并比较迭代次数:

(1)最小元素法一位势法一闭回路法；

(2)最大差额法-闭回路法。

5.5求解下述运输问题:

销地B,B产量

2B3B4

产By

A\7526415

4973620

A2

5285715

A3

销量2020151015

5.6求解前进拖拉机厂的生产调度问题(见§3例6)

5.7某公司经营的一种产品拥有四个客户，由于公司所辖三个工厂生产，每月产量分别为3000,5000,4000件。该

公司已承诺下月出售4000件给客户1,出售3000件给客户2以及至少1000件给客户3。客户3与4都想尽可能多

购剩下的件数。已知各厂运销一件产品给客户可得到的净利润如下表所示。问公司应如何拟订运销方案，才能在履

行诺言的前提下获利最多？

x1234

165636264

268676562

363605960

5.8某食品公司所辖F1,F?,F3三个工厂每天分别生产20,22,4吨糖果，运

往的库存量分别为21,25吨。各地之间的运价(元/吨)如下表所示。试求总运费最少的调运方案。

终点FiF二W,

始“、

w2

Fi566

667

F2

1899

F3

W(91010

5.9某肉食品加工厂按合同要在今后两个月内为某个肉蛋禽联营商店加工某种熟肉制品14500公斤。其中第一个月需

交货8000公斤，若未交够，不足的部分可由第二个月补交，但补交的数量须回扣给商店0.1元/公斤。全部加工任务

必须在第二个月末前完成，否则将重金赔偿商店损失。另若加工好的肉制品当月不交货，则每贮存一个月需花冷藏

费0.05元/公斤。该厂的加工能力及加工费用如下表所示。试为该项目合同拟订•个总费用最少的生产调度方案。

\月份

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

1212

生产方鼠

正常生产550060000.600.60

加班生产200025000.750.70

外协生产200020000.850.80

5.10某造船厂根据合同要在今，明，后年各提供三艘规格型号相同的货轮。已知该厂这三年内生产这种货轮的能力

及成本如下表所示。其中加班生产的成本比正常生产高出70万元/艘。若造好的货轮当年不交货，没积压一年将损失

40万元/艘。该厂目前已积压两艘该型号货轮，并且希望后来未完成合同后还能储备一艘。该厂应如何安排生产，使

总的生产费用最少？

年度正常生产能力加班生产能力正常生产的成本

（艘）（艘）（万元/艘）

今23500

明42600

后13550

整数规划习题六

6.1下述IP问题能否通过LP解的圆整而得最优？

(1)maxZ=3XI+2X2

2xl+3%2414

2%,+X2<9

s.t.《

x,>0,x2>0

不马为整数

(2)maxZ=3XI+2X2

-4%j+3x2<6

否

34-2X2<18

s.t.《

x,>0,x2>0

々为整数

6.2试用分支定界法求解下述IP问题。

(1)maxZ=5X|+8X2

+x2<6

5x,+9X2<45

s.t.«

%1>0,x2>0

内,马为整数

(2)maxz=Xj+x2

I4xi+9X2<51

-6X]+3X2<1

s.t.<

%]>0,x2>0

X]，W为整数

(3)maxz=x1+2x2

-2Xj+4X2<I

2X1+4X2>3

s.t.v

2x}+x2<3

斗巧为整数

(4)maxz=xr2x2

-5Xj+5X2<4

一3玉+3X2>1

%1>0

X1,冗2为整数

(5)maxZ=3X]+2X2

2x,-4X2+2X3=5

4%+2X2+2X4=3

s.t.

xpx2,x3,x4>0

々，当为整数

6.3试用割平面法求解下述IP问题。

(1)6.2题之(1)；

(2)maxz=X]+x2

2x,+x2<6

4X[+5X2<20

%1>0,x2>0

为整数

(3)maxZ=3XI+X2

2xl+x2<5

2xl-x2>2

>0,x2>0

小々为整数

6.4试建立下述问题的数学模型：

(1)设有m台同--类型的机床，有n(>m)种零件各一个要在这些机床上加工，加工一个第j种零件需要印机时。应

如何分配加工任务，才能使各机床的负荷尽可能均衡。

(2)某省外贸局拟从下列应试者中招聘四名工作人员，希望所招四人平均业务能力评分最高，且满足下述要求：①

专业不得相同；②女性最多不超过二人；③至少有一名精通日语者：④精通英语者最多入选一人。

姓名性别专业精通语种业务能力评分

戴胜春男纺织英95

杨光女机械英93

马跃男化工德87

李玉芬女电子法87

康平男机械日83

姜洁女食品日73

（3）某厂为生产某种新产品设计了三种生产方案，如下表所示:

方案一次性投资生产费用生产能力

（万元）（元/件）（万件）

I1058

II16414

11125322

该产品销价为每件10元。据市场调研，在该产品生命周期内的需求量为30万见。应如何拟订生产计划能使经济效

益最佳？

（4）某石油化学工业公司的某项产品售价为每公升1.20元，产量随生产过程中温度的升高而增加，其数量关系如图

6-15所示。假定产品成本与生产中的温度成正比，每提高一度的费用为30元，则应生产多少公升该项产品，才能使

利润为最大？

图6-15

（5）考虑1.2题之（2）.假定预计明年A.B,C三市用煤量分别增加8,10,12万吨。计划部门为了使产销平衡，打

算增加一套年产30万吨煤的成套设备，这套设备安放到甲，乙煤矿，年产30万吨煤所增加的生产费用分别为20,

25万元。应讲设备拨给哪个煤矿，能使增加的总费用（包括生产与运输两部分）为最低？

（6）某人要去A市探亲，由于他已领取了个体经营（干鲜水果）的执照，因此打算顺便贩运本地产的橘子，香蕉两

种鲜果。橘子，香蕉在本地的购价分别为每箱4,5元，每箱毛重分别为8,12公斤。由于春节将临，因此他考虑两

种贩运方式：若乘飞机，能在除夕前赶到，从而能卖高价，且能保证果品无损；若乘轮船，则在初四赶到，只能卖

中高价格，且因途中果品会有损伤而使每箱收入减少10%,有关数据如下表所示。另外，他已决定要用相当于毛重

各为半箱数量的橘子，香蕉馈赠亲友，而且途中要携带2公斤的生活日用品。问他应乘坐哪种交通工具且携带两种

果品各多少箱，才能使这次贩运预计盈利最高。

贩运方式单程票价免费携重超重收费限重限容A市时价（元/箱）

（元）（公斤）（元/公斤）（公斤）（箱数）

橘子香蕉

飞机450101.005052428

轮船60300.40100102023

6.5考虑下述数学模型

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

试把此模型化为一个混合整数规划模型。

6.6试用异序枚举法求解下述0-1规划：

(1)maxz=3xr2x2+5x3

X]+2X2-x3<2

%+4X2+x3<4

x1+x2