天大97-08试题分类

一、线性规划

二、运输问题

三、多目标规划

四、动态规划

五、图论

六、网络计划技术

七、决策论

八、存储论

九、排队论

十、对策论

十一、模拟技术

一、线性规划

（一）选择填空题（二）线性规划建模（三）互补松弛应用（四）灵敏度分析（五）

证明题

（-）选择填空题

1.下面给出某线，性规划问题的单纯形初表和终表（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）初表的出基变量为,进基变量为。

（2）最优基逆丁一,=[]

（3）填完终表。

（4）最优解X*=

⑸对偶问题最优解y*=

⑹若原问题增加一个新的非负变量，则对偶问题的最优目标值将（变大、不变、变

小）。（2007）

解：1.（1）出基变量为X4：进基变量为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.用图解法解线性规划时，以下儿种情况中不可能出现的是（）o

A.可行域（约束集合）有界，无有限最优解（或称无解界）

B.可行域（约束集合）无界，有唯一最优解

C.可行域（约束集合）是空集，无可行解

D.可行域（约束集合）有界，有多重最优解（2006）

解：1.A

2.根据线性规划的互补松弛定理，安排生产的产品机会成本一定（）利润。

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

解：2.B

1.用大M法求解Max型线形规划时，人工变量在目标函数中的系数均为,

若最优解的中含有人工变量，则原问题无解。（2005）

解：1、-M基变量

I.设线性规划问题max{cx|Ax=bx2o}有最优解x*和影子价格y*,则线性规划问题

11^{2阂4¥="20}的最优解=,影子价格=o

（2004）

解：1.x*2y*

3.某工程公司拟从1、2、3、4四个项目中选择若干项目。若令

1，第i个项目被选中

0,第i个项目未选中'

清用七的线性表达式表示下列要求：（1）若项目2被选中，则项目4不能被选中：

（2）只有项目1被选中，项目3才能被选中：o（2004）

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

一、简答（18%）

（1）请简述影子价格的定义。

（2）在使用单纯型表求解型线性规划时，资源的影子价格在单纯型表的什么位置上？

（3）写出影子价格的数学表达式并用其定义加以验证

（4）试述运输问题中检验数的经济意义（2003）

解：一、简答

⑴当各资源增加一单位时引起的总收入的增量，影子价格大于零的资源一定没有剩余，有剩

余一定为零。

⑵松弛变量检验数的负值，对偶问题的最优解。

⑶CBB"

B是原问题｛maxz=CXIAXWb,X）0｝最优基

Z"=CBB'b=Y*b

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

炎*

------=y3*

8b

（4）表明增加•个单位的运量会引起总运输费用的变化

1.线性规划原问题中约束的个数与其对偶问题中的变量个数相等。若原问题第j个约束

为等式，则对偶问题第i个变量自由（2002）

解：

2.设线性规划问题max:｛cxlAxWbx20｝有最优解，且最优解值z>0；4操c和b分别被v>l

所乘，则改变后的问题.也有（也有、不一定有）最优解；若有最优解，其最优解&

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

1.下列数学模型中a是线性规划模型。（2001）

(6)maxZ=min<区+6：+815$+9；2+2当

(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.标准形式的线性规划问题，其可行解b是基本可行解,最优解a是可行解,最优

解a能在可行域的某顶点达到。(2001)

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

解：

4.目标函数取极小(minZ)的线性规划问题可以转化为目标函数取极大的线性规划

问题求解，原问题的目标函数值等于(2001)

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

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

1.线性规划单纯形算法的基本步骤是：(1)(2)

(3)每次迭代保持解的,改善解值的。对偶单纯

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

解：确定一个初始基可行解；检验一个基可行解是否为最优解；寻找一个更好基可行解；可

行性；最优性。

2.设有线性规划问题\min\f=CX,XeR={X\AX=b,X>0),有一可行基B(为A

中的前m列)，记相应基变量为X.,价格系数为CB，相应于非基变量为XN，价格系数为

CN，则相应于B的基本可行解为*=；用非基变量来表示基变量的表达式为

XB=；用非基变量表示目标函数的表达式为£=,B为最优基的条件

是<,(2000)

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

、0/

3.线性规划(Min型)问题有多重最优解时，其最优单纯形表上的特征为：

(2000)

解：所有检验数可某0,•个非基变量检验数4=0.

6.某足球队要从I,2,3,4,5号五名队员中挑选若干名上场。令

J1第i号上场

七一jo第i号不上场，i=1,2,3,4,5

请用％的线性表达式表示下列要求：(1)从1,2,3中至多选2名：(2)如果

2号和3号都上场，则5号不上场：(3)只有4号上场,1号才上场：(2000)

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

1.某工程公司拟从四个项目中选择若干项目，若令

J1,第介项目被选中

Xi~[o,第泠项目末被选中"''’.

请用Xi的线性表达式表示下列要求：

(1)从1,2,3项目中至少选择一个：,

(2)只有项目2被选中，项目4才能被选中o(1999)

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

2.考虑线形规划问题

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)上述模型的对偶模型为,

(2)对偶模型的最优解为,

(3)当两种资源分别单独增加一个单位时，目标函数值分别增加

和,

(4)最优基的逆矩阵员:

(5)如果原问题增加一个变量，则对偶问题的可行域将可能变大还是变小？

(1999)

解：2.(1)

minW=5yl+2y2

y,+2%N5

(2y1-y2>12

%+3%"

JNO,为无符号限制

292

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

55

⑶以一2

55

2_r

(4)55

12

J5>

(5)变小

1.下面给出某线形规划的单纯形初表(表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）初表的出基变量为，进基变量为o

2）填完表2,该表是否是终表?o若是，最优值Z*=

3）此线形规划对偶问题的最优解片=

（1998）

解：1.下面给出某线形规划的单纯形初表（表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，进基变量为—X3o

5）填完表2,该表是否是终表?—是。若是，最优值Z*=_-ll

此线形规划对偶问题的最优解y*上-2,0

55

解:

解:

解:

解:

解:

（-）线性规划建模

二（20分）、某化学制药厂有m种有害副产品，它们的数量为bi（i=l,…，m）。按照规定,

必须经过处理，制成n种无害物后才能废弃。设aij为每制成一单位第j（j=l,…，n）种无

害物可以处理掉第i种有害物的数量，cj为制成一单位第j种无害物的费用。

1.现欲求各无害物的产量xj以使总的处理费用为最小，请写出此问题的线性规划模型；

2.写出此问题的对偶规划模型，并解释对偶规划模型的经济意义。（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+…+册2*,2

—+"2+…+3”小“

.%，上，…，Xn20

经济意义：为第i种有害副产品不经处理直接废弃的费用。

二（10%）、某大型企业每年需要进行多种类型的员工培训。假设共有需要

培训的需求（如技术类、管理类）为6种，每种需求的最低培训人数为a”i=l,…,6,

可供选择的培训方式（如内部自行培训、外部与高校合作培训）有5种，每种的

最高培训人数为bj,j=l,…,5。又设若选择了第1种培训方式，则第3种培训方

式也要选择。记Xij为第i种需求由第j方式培训的人员数量，z为培训总费用。

费用的构成包括固定费用和可变费用，第j种方式的固定费用为hj（与人数无关）,

与人数Xij相应的可变费用为Cij（表示第j方式培训第i种需求类型的单位费用）。

如果以成本费用为优化目标，请建立该培训问题的结构优化模型（不解）。（2006）

解：二、

设其第种需求由第种药式培训的人员数量，匕=，『训方式

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两种原料生产甲、乙、丙三种产品，有关数据见下表:

AB生产成本（万元/吨）销售价格（万元/吨）

甲1.00.5830

乙0.40.6520

丙0.60.51835

原料成本（万元/吨）57

原料可用数量（吨）350460

（1）请写出使总销售利润最大的线性规划模型（其中甲、乙、丙产产量分别记为x,,x2,x3,

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

（2）写出此问题的对偶规划模型（2003）

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

目标函数maxz=13.5XI+8.8X2+10.5X3

约束条%X1+0.4X2+0.6X3W350

J0.5XI+0.6X2+0.5X3W460

X]20,X220,X320

I

②对偶规划模型

目标函数minw=350yi+460y2

约束条件伍+0.5y2e13.5

0.4yi+0.6y228.8

《0.6yi+0.5y2210.5

yi20,y2与0

三（10%）某服装厂制造大、中、小三种尺寸的防寒服，所用资源有尼龙绸、尼龙棉、劳动

力和缝纫设备。缝制一件防寒服所需各种资源的数量如表（单位已适当给定）。不考虑固定

费用，则每种防寒服售出一件所得利润分别为10、12、13元，可用资源分别为：尼龙绸1500

米，尼龙棉1000米，劳动力4000,设备3000小时。此外，每种防寒服不管缝制多少件，

只要做都要支付一定的固定费用：小号为100元，中号为150元，大号为200元。现欲制定

-生产计划使获得的利润为最大，请写出其数学模型（不解）。（2002）

^号

小中大

资源

尼龙绸1.61.81.9

尼龙棉1.31.51.6

劳动力44.55

缝纫设备2.83.84.2

解：三、解：设三种防寒服分别生产XI,X2,X3件。Z表示获得的利润,力》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

（三）互补松弛应用

maxz=2%]+3x2

2X1+2X2<12

Xj+2x2<8

二（8%）、线性规划问题

4x1<16

4X2<12

x2>0

已知其最优解为，初＞0,而第1,4两种资源（相应于第1,4两约束）均有余量，应用互

补松弛定理求出原问题和对偶问题的最优解。（2005）

解：二对偶问题

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

‘2%+%+4月22

<2必+2y2+4y4>3

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

vx,>0,x2>0,其对偶问题取严格等式-月+乃+4%=2（*）

.2%+2y2+4汽=3

•.•第1俩种资源有剩余，即原问题约束。腑r格不等式

对应对偶问题变量乂=0,%=0

13

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

o2

-0■

%

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

%

0

z=w=14

由修+%=8#=4

4玉=16x2=2

综上，原问题最优解x=[421,Z*=14

31

oo

对偶问题最优解y=2-8-，卬*=14

（四）灵敏度分析

三（25%）、派公司是一个生产高尔夫器材的小型公司，近期推出了高、中价位的高尔

夫袋新产品（标准袋和高档袋），经销商对此产品十分感兴趣，并订购了派公司下3个月的

全部产品。

该高尔夫袋的生产过程主要包括4道工序：切割并印染原材料、缝合、成型（插入支

撑架和球棒分离装置等）、检验和包装。有关数据如表1。派公司须决定标准袋和高档袋各

生产多少可使公司的总利润最大。

表1

单耗7"品

标准袋高档袋3个月内最大生产能力(小时)

工序

切割印染7/101630

缝合1/25/6600

成型12/3708

检验包装1/101/4135

产品单位利润(美元)109

(1)写出此问题的线性规划模型，约束依表1中次序；

(2)引入松弛变量(依约束次序)后用单纯形法计算得某单纯形表如表2,请填完表中

空白，并判断其是否终表，如果是，请写出最优生产计划、最大利润和资源剩余;

表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)写出此问题的对偶问题的模型，及对偶的最优解与最优值；

(4)写出成型时间的影子价格，求使该影子价格不变的成型时间的变化范围；

(5)若标准袋的利润可能发生变化，则其在何范围内变化时，可使原最优计划不改变?

图示说明其几何意义。(2005)

解：三设标准袋生产吃,高档袋生产乙

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

・•.是终表

最优生产计划x=[5402520120018],即普通袋540个，高档袋252个

,*i「540]

・•.最大利润Z=[r109]252=7668(美元)

因为松弛变量%3*0%=120x5=0x6=18

所以第2科资源有剩余，分别为,12X)18

(3)对偶问题模型：

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

711

二H+—乃+乃+—>4210

10-210

5213

+2为+7%+共429

634

>0,y2>0

对偶问题最优解：y<=[4.37506.9675O]

由对偶问题的强对偶性知，对偶问题与原问题的最优值相同W=Z=7668（美元）

（4）成型时间影子价格为6.9375

使该影子价格不变的成型时间的变化范围应满足

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变化，可能影响检验数，故令

%，=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%）、某公司生产家用的清洁产品，为了在高度的市场竞争中增加市场份额，公司决

定进行一次大规模的广告行动。表1给出了公司准备做广告的三种产品名称、估计每做一单

位广告（一个广告标准批量）使每种产品的市场份额增加量、公司拟定的广告后每种产品市

场份额增加量的最低H标和两种可选的广告方式的单价。

表1

广告后市场份额最低增

、电视印刷媒体

量

产品

去污剂0%1%3%

液体洗涤剂3%2%18%

洗衣粉-1%4%4%

广告单位成本（万元）100200

其中洗衣粉的市场份额出现负值是由于液体洗涤剂的份额增加会造成洗衣粉份额的减

少。

现公司需拟定使广告总费用最少的广告计划，即决定电视和印刷媒体的广告数量（分别

记为X1和X2）。

I.请写出此问题的线性规划模型（约束依表1中产品的次序），并将模型化为标准型。

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）请填完表中空白；（2）由表指出最优广告计划并求出相应的最低广告费用，此最优计

划使每种产品的市场份额最低增量目标达成情况如何？

3.写出此问题的对偶问题模型，由表2求出对偶最优解Y*,并解释Y*的实际意义。

(2004)

1.minZ=lOOxi+200x2

x2>3

<3玉+2X2>18

+4X2>4

标准型：

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）

最优广告计划x=（4,3）J即电视广告数量为4,印刷广告数量为3,最低费用：W=1000

达成情况为去污剂增加3%,恰好达标

洗衣剂增加18%,恰好达标

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

(3)

对偶模型为：

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

f3y2-y3<100

［乃+2%=4%4200

%>0,y2>0,y3>0

对偶最优解为：y=(400/3,100/3,0)

经济意义：乂代表三种产品的广告的投资，3,18,4为每种产品广告单位投资后的手机，

100,200代表用于电视及印刷品的投资额，故该模型的含义为用每种产品的头则使其在不

超过约束的条件下达到利润最大化。

(3)(30%)考虑线性规划问题

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

检验数

终表

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

45/21/1215/12-1/6

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

检验数

1.填完初表和终表中各空白,并说明所得最优解是否是唯一的，为什么?

1818

2.考虑当b变为5=13时，对最优解有什么影响?当b变为5=14时，对最优解是否有影

6060

响？

3.对偶问题最优解？(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

检验数00302010

①不唯一，因为存在非基变量检验数为零，则有多个最优解

(\

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%)已知线性规划问题

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

。1内+。12兀2+。13%3+%4=儿+3,2

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

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

当t产t2=0时，用单纯形法求得最终表如下:

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.当t2=0时，七在什么范围内变化上述最优解不变；

3.当3=0时，t2在什么范围内变化上述最优基不变。(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设<

又由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)

对应得到a1[=0,a[2=1抱13=2,a2i=3,a22=-l,a23=1

2.L变化，将影响各检验数的变化，检验各非基变量检验数，若6jW0,则最优解不变

^=-2-(106+外雅210

fl/2)

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

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

1/20

变化，要使最优基不变则B'b>O,因为

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分）某公司生产3种产品：花,乙，X3,需要3种资源：技术服务，动力和行政

管理，公司经理助理根据公司实际情况，建立了使总利润最大的产品产量的线性规

划模型，并

maxZ=10X1+6x2+4x3

x,+x2+x34100（技术服务约束）

s.410x,+4X2+5X3<600（劳动力约束）

X

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

采用单纯形法求得最优表格如下：

10640