运筹学1至6章习题参考答案

运筹学1至6章习题参考答案

第1章 线性规划

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

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.2 建筑公司需要用5m长的塑钢材料制作A、B两种型号的窗架．两种窗架所需材料规格

及数量如表1－24所示：

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

10

minZ xj

j 1

2x1 x2 x3 x4 800

x2 2x5 x6 x7 1200

x3 x6 2x8 x9 600 x 2x 2x 3x 900

7910

4 xj 0,j 1,2,,10

（2）余料最少数学模型为

minZ 0.5x2 0.5x3 x4 x5 x6 x8 0.5x10 2x1 x2 x3 x4 800

x2 2x5 x6 x7 1200

x3 x6 2x8 x9 600 x 2x 2x 3x 900

7910

4 xj 0,j 1,2,,10

1.3某企业需要制定1～6月份产品A的生产与销售计划。已知产品A每月底交货，市场需求没有限制，由于仓库容量有限，仓库最多库存产品A1000件，1月初仓库库存200件。1～6月份产品A的单件成本与售价如表1－25所示。

（2）当1月初库存量为零并且要求6月底需要库存200件时，模型如何变化。 【解】设xj、yj（j＝1，2， ，6）分别为1～6月份的生产量和销售量，则数学模型为

maxZ 300x1 350y1 330x2 340y2 320x3 350y3 360x4

420y4 360x5 410y5 300x6 340y6

x1 800

x1 y1 x2 800

x1 y1 x2 y2 x3 800

x1 y1 x2 y2 x3 y3 x4 800

x y x y x y x y x 800

233445

112

x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 x6 800（1） x1 y1 200

x y x y 200

2

112

x1 y1 x2 y2 x3 y3 200

x1 y1 x2 y2 x3 y3 x4 y4 200

x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 200

x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 x6 y6 200 x,y 0;j 1,2,,6 jj

（2）目标函数不变，前6个约束右端常数800改为1000，第7～11个约束右端常数200改为0，第12个约束“≤200”改为“＝－200”。

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

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

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

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

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

数学模型为

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.5 炼油厂计划生产三种成品油，不同的成品油由半成品油混合而成，例如高级汽油可以由中石脑油、重整汽油和裂化汽油混合，辛烷值不低于94，每桶利润5元，见表1－26。

表1－27

解 设xij为第i（i＝1,2,3,4）种成品油配第j(j=1,2, ,7)种半成品油的数量（桶）。 总利润：

Z 5(x11 x12 x13) 4.2(x21 x22 x23) 3(x34 x35 x36 x37) 1.5(x44 x45 x46 x47)

高级汽油和一般汽油的辛烷值约束

80x11 115x12 105x1380x21 115x22 105x23

94,84 94

x11 x12 x13x21 x22 x23

航空煤油蒸气压约束

x34 1.5x35 0.6x36＋0.05x37

1

x34 x35 x36＋x37

一般煤油比例约束

x44:x45:x46:x47 10:4:3:1

即

x4410x454x463 , , x454x463x471

半成品油供应量约束

x11 x21 2000x12 x22 1000x13 x23 1500x34 x44 1200 x35 x45 1000x36 x46 1000x37 x47 800

整理后得到

maxZ 5x11 5x12 5x13 4.2x21 4.2x22 4.2x23 3x34 3x35 3x36 3x37 1.5x44 1.5x45 1.5x46 1.5x47 14x11 21x12 11x13 0

14x21 21x22 11x23 0 4x21 31x22 21x23 0

0.5x35 0.4x36 0.95x37 0 4x 10x 0

45

44

3x45 4x46 0

x46 3x47 0

x11 x21 2000 x x 1000 1222

x13 x23 1500

x34 x44 1200 x35 x45 1000

x36 x46 1000 x x 800 3747 xij 0;i 1,2,3,4;j 1,2,,7

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

maxZ 5x1 2x2

2x1 x2 8

(1) x1 3

x2 5 x1,x2 0

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

maxZ x1 4x2

x1 4x2 5 (2) x1 3x2 2

x1 2x2 4 x1,x2 0

【解】有多重解。最优解X

（1）

＝（0，5/4）；X

（2）

＝（3，1/2）最优值

Z=5

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，有唯一最优解

minZ 4x1 6x2

x1 2x2 8 (4) x1 x2 8

x2 3 x1 0,x2 0

【解】最优解X＝（2，3）；最优值Z=26，有唯一最优解

maxZ x1 2x2

x1 x2 2 (5) x1 3

x2 6 x1,x2 0

【解】无界解。

minZ 2x1 5x2

(6)

x1 2x2 6

x1 x2 2 x,x 0 12

【解】无可行解。

1.7 将下列线性规划化为标准形式 minZ x1 6x2 x3 x1 x2 3x3 15 (1)

5x1 7x2 4x3 32

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

'''

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

''' x1 x2 3x3 3x3 x4 15 '''

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

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.8 设线性规划

maxZ 5x1 2x2 2x1 2x2 x3 40

4x 2x x 60 124

x 0,j 1,,4 j

21 20

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

【解】B1：x1、x3为基变量，x2、x4为非基变量,基本解为X=（15，0，10，0）T，B1是可行基。B2：x2、x4是基变量，x1、x3为非基变量，基本解X=（0，20，0，100）T，B2是可行基。

1.9分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点．

maxZ x1 3x2

(1)

2x1 x2 2

2x1 3x2 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.10用单纯形法求解下列线性规划

maxZ 3x1 4x2 x3

2x1 3x2 x3 4(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