运筹学教材习题答案

教材习题答案

部分有图形的答案附在各章PPT文档的后面，请留意。

第1章线性规划

第2章线性规划的对偶理论 第3章整数规划 第4章目标规划

第5章运输与指派问题 第6章网络模型 第7章网络计划 第8章动态规划 第9章排队论 第10章存储论 第11章决策论 第12章对策论

习题一

1.1 讨论下列问题：

（1）在例1.1中，假定企业一周内工作5天，每天8小时，企业设备A有5台，利用率为0.8,设备B有7台，利用率为0.85,其它条件不变，数学模型怎样变化．

（2）在例1.2中，如果设xj(j=1，2，…，7)为工作了5天后星期一到星期日开始休息的营业员，该模型如何变化．

（3）在例1.3中，能否将约束条件改为等式；如果要求余料最少，数学模型如何变化；简述板材下料的思路．

（4）在例1.4中，若允许含有少量杂质，但杂质含量不超过1％，模型如何变化．

（5）在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化．

1.2 工厂每月生产A、B、C三种产品 ,单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如表1－22所示．

310和130.试建立该问题的数学模型,使每月利润最大．

【解】设x1、x2、x3分别为产品A、B、C的产量，则数学模型为

maxZ 10x1 14x2 12x3 1.5x1 1.2x2 4x3 2500 3x 1.6x 1.2x 1400

23 1

150 x1 250

260 x2 310 120 x3 130 x1,x2,x3 0

1.3 建筑公司需要用6m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格

及数量如表1－23所示：

【解

设xj（j=1,2,…，14）为第j种方案使用原材料的根数，则 （1）用料最少数学模型为

minZ xj

j 1

14

2x1 x2 x3 x4 300

x2 3x5 2x6 2x7 x8 x9 x10 450

x3 x6 2x8 x9 3x11 2x12 x13 400

x x 2x x x 3x 2x 3x 4x 600

47910121314

23 xj 0,j 1,2, ,14

用单纯形法求解得到两个基本最优解

X(1)=( 50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534 X(2)=( 0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534 （2）余料最少数学模型为

minZ 0.6x1 0.3x3 0.7x4 0.4x13 0.8x14 2x1 x2 x3 x4 300

x2 3x5 2x6 2x7 x8 x9 x10 450

x3 x6 2x8 x9 3x11 2x12 x13 400

x x 2x x x 3x 2x 3x 4x 600

47910121314

23 xj 0,j 1,2, ,14

用单纯形法求解得到两个基本最优解

X(1)=( 0 ,300 ,0 ,0,50 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料550根 X(2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料650根 显然用料最少的方案最优。

1.4 A、B两种产品，都需要经过前后两道工序加工，每一个单位产品A需要前道工序1小时和后道工序2小时，每一个单位产品B需要前道工序2小时和后道工序3小时．可供利用的前道工序有11小时，后道工序有17小时．

每加工一个单位产品B的同时，会产生两个单位的副产品C，且不需要任何费用，产品C一部分可出售赢利，其余的只能加以销毁．

出售单位产品A、B、C的利润分别为3、7、2元，每单位产品C的销毁费为1元．预测表明，产品C最多只能售出13个单位．试建立总利润最大的生产计划数学模型．

【解】设x1,x2分别为产品A、B的产量，x3为副产品C的销售量,x4为副产品C的销毁量，有x3+x4=2x2,Z为总利润，则数学模型为

maxZ=3x1+7x2+2x3 x4 x1 2x2 11 2x 3x 1712

2x2 x3 x4 0 x 13 3 xj 0,j 1,2, ,4

1.5 某投资人现有下列四种投资机会, 三年内每年年初都有3万元（不计利息）可供投资： 方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20％，下一年可继续将本息投入获利；

方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50％，下一年可继续将本息投入获利，这种投资最多不超过2万元；

方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率是60％，这种投资最多不超过1.5万元；

方案四：在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30％，这种投资最多不超过1万元．

投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型. 【解】是设x

为第i年投入第j项目的资金数，变量表如下

maxZ 0.2x11 0.2x21 0.2x31 0.5x12 0.6x23 0.3x34 x11 x12 30000

1.2x11 x21 x23 30000

1.5x12 1.2x21 x31 x34 30000

x12 20000 x 15000 23

x34 10000 xij 0,i 1, ,3;j 1, 4

最优解X=(30000，0，66000，0，109200，0)；Z＝84720

1.6 IV发展公司是商务房地产开发项目的投资商．公司有机会在三个建设项目中投资：高层办公楼、宾馆及购物中心，各项目不同年份所需资金和净现值见表1－24．三个项目的投资方案是：投资公司现在预付项目所需资金的百分比数，那么以后三年每年必须按此比例追加项目所需资金，也获得同样比例的净现值．例如，公司按10％投资项目1，现在必须支付400万，今后三年分别投入600万、900万和100万，获得净现值450万．

公司目前和预计今后三年可用于三个项目的投资金额是：现有2500万，一年后2000万，两年后2000万，三年后1500万．当年没有用完的资金可以转入下一年继续使用．

IV公司管理层希望设计一个组合投资方案，在每个项目中投资多少百分比，使其投资获得的净现值最大．

【解】以1％为单位，计算累计投资比例和可用累计投资额，见表（2）。

表（2）

设xj为j项目投资比例，则数学模型：

maxZ 45x1 70x2 50x3 40x1 80x2 900x3 2500

100x1 160x2 140x3 4500

190x1 240x2 160x3 6500 200x 310x 220x 8000

123

xj 0,j 1,2,3

最优解X＝（0，16.5049，13.1067）；Z=1810.68万元

1.7 图解下列线性规划并指出解的形式：

maxZ 2x1 x2

x1 x2 1 (1)

x1 3x2 1 x,x 0 12

【解】最优解X＝（1/2，1/2）；最优值Z=－1/2

minZ x1 3x2

(2)

2x1 x2 2

2x1 3x2 12 x 0,x 0

2 1

【解】最优解X＝（3/4，7/2）；最优值Z=－45/4

minZ 3x1 2x2 x1 2x2 11 x 4x 10

12

(3)

2x1 x2 7 x 3x 1

2

1 x1,x2 0

【解】最优解X＝（4，1）；最优值Z=－

10

maxZ x1 x2

3x1 8x2 12 (4) x1 x2 2

2x1 3 x1,x2 0

【解】最优解X＝（3/2，1/4）；最优值Z=7/4

minZ x1 2x2

x1 x2 2 (5) x1 3

x2 6 x1,x2 0

【解】最优解X＝（3，0）；最优值Z=3

运筹学习题答案

8

maxZ x1 2x2

x1 x2 2 (6) x1 3

x2 6 x1,x2 0

【解】无界解。

minZ 2x1 5x2

x1 2x2 6(7)

x1 x2 2 x,x 0 12

【解】无可行解。

maxZ 2.5x1 2x2

2x1 x2 8

(8) 0.5x1 1.5

x1 2x2 10 x1,x2 0

【解】最优解X＝（2，4）；最优值

Z=13

1.8将下列线性规划化为标准形式 maxZ x1 4x2 x3 2x1 x2 3x3 20 (1)

5x1 7x2 4x3 3

10x1 3x2 6x3 5 x1 0,x2 0,x3无限制

'''【解】（1）令x3 x3 x3,x4,x5,x6为松驰变量，则标准形式为 '''maxZ x1 4x2 x3 x3

''' 2x1 x2 3x3 3x3 x4 20 '''

5x1 7x2 4x3 4x3 x5 3 '''

10x1 3x2 6x3 6x3 x6 5

''' x1,x2,x3,x3,x4,x5,x6 0minZ 9x1 3x2 5x3

|6x1 7x2 4x3| 20

(2) x1 5

x1 8x2 8 x1 0,x2 0,x3 0

【解】（2）将绝对值化为两个不等式，则标准形式为

maxZ 9x1 3x2 5x3 6x1 7x2 4x3 x4 20 6x 7x 4x x 20

1235 x x 5 16

x 8x 8

2

1 x1,x2,x3,x4,x5,x6 0

maxZ 2x1 3x2 1 x1 5

(3)

x1 x2 1 x 0,x 0

2 1

【解】方法1：

maxZ 2x1 3x2

x1 x3 1

x x 5

14

x1 x2 1 x1,x2,x3,x4 0

x1 1,有x1＝x1 1,x1 5 1 4 方法2：令x1

1) 3x2maxZ 2(x1

4 x1

1) x2 1 (x1

x,x 0 12

则标准型为

3x2maxZ 2 2x1 x3 4 x1

x2 0 x1

x ,x,x 0 123

maxZ min(3x1 4x2,x1 x2 x3)

x1 2x2 x3 30

(4) 4x1 x2 2x3 15

9x1 x2 6x3 5 x1无约束,x2、x3 0

【解】令y 3x1 4x2,y x1 x2 x3,x1 x1 x1 ，线性规划模型变为

maxZ y

x1 ) 4x2 y 3(x1

y x x x x

1123 x1 2x2 x3 30 x1

x1 ) x2 2x3 15 4(x1

9(x1 x1 ) x2 6x3 5 ,x1 ,x2、x3 0 x1

标准型为

maxZ y

3x1 4x2 x4 0 y 3x1

y x x x x x 0

11235 x1 2x2 x3 x6 30 x1

4x1 x2 2x3 x7 15 4x1 9x1 9x1 x2 6x3 x8 5 ,x1 ,x2,x3,x4,x5,x6,x7,x8 0 x1

1.9设线性规划

maxZ 5x1 2x2 2x1 3x2 x3 50

4x 2x x 60 124

x 0,j 1, ,4 j

21 20

取基B1 (P1，P3) 分别指出B1和B2对应的基变量和非基变量， 、B2＝ 41 ，40 求出基本解，并说明B1、B2是不是可行基．

【解】B1：x1，x3为基变量，x2，x4为非基变量,基本解为X=（15，0，20，0）T，B1是可行基。B2：x1,x4是基变量，x2,x3为非基变量，基本解X=（25，0，0，－40）T，B2不是可行基。 1.10分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点．

maxZ x1 3x2

(1)

2x1 x2 2

2x 3x 12 12 x,x 0 12

【解】图解法

最优解X (,),Z

424

minZ 3x1 5x2

x1 2x2 6 (2) x1 4x2 10

x1 x2 4 x1 0,x2 0

【解】图解法

该题是退化基本可行解，5个基本可行解对应4个极点。

1.11用单纯形法求解下列线性规划

maxZ 3x1 4x2 x3

2x1 3x2 x3 1(1)

x1 2x2 2x3 3 x 0,j 1,2,3 j

maxZ 2x1 x2 3x3 5x4

x1 5x2 3x3 7x4 30

(2) 3x1 x2 x3 x4 10

2x1 6x2 x3 4x4 20 xj 0,j 1, ,4

【解】单纯形表：

因为λ7＝3>0并且ai7<0(i=1,2,3)，故原问题具有无界解，即无最优解。

maxZ 3x1 2x2 18x3 x1 2x2 3x3 4 (3) 4x1 2x3 12

3x1 8x2 4x3 10 x1,x2,x3 0

原问题具有多重解。 基本最优解X

(1)

1273427237 (3,,0,,0)及X(2) (,0,,,0)T;Z ,最优解的通解可表

841111114