规划数学(运筹学)第三版课后习题答案 习 题 1(1)

习 题 1

1 用图解法求解下列线性规划问题，并指出问题具有唯一最优解、无穷最优解、无界解还是无可行解。

(a)minz 2x1 3x2 4x1 6x2 6

4x1 2x2 4 x，x 0

2 1

(b)maxz 3x1 2x2

2x1 x2 2

3x1 4x2 12 x,x 0

12

(d)maxz 5x1 6x2 2x1 x2 2

2x1 3x2 2 x,x 0

12

(c)maxz x1 x2

6x1 10x2 120

5 x 10 1

3 x 8

2

答案： (a)唯一解X* (0.75,0.5)(c)唯一解X* (10,6)

T

T

,z* 3); (b)无可行解;

,z* 16); (d)无界解）

2 用单纯形法求解下列线性规划问题。

(a)maxz 10x1 5x2 3x1 5x1 x, 1

4x2 2x2x2

(b)maxz 2x1 x2

15 24

50

5x2

9 6x1 2x2 8

x1 x2

x2 x1,

T

答案：

(a)唯一解X* (1,1.5)

T

对偶问题Y* (0.357,1.786),w* 17.5; ,z* 17.5)，T

T

，Y* (0,0.25,0.5),w* 8.5 ,z* 8.5）

(b)唯一解X* (3.5,1.5)

3 用大M法和两阶段法求解下列线性规划问题，并指出属于哪一类解。

(a)maxz 2x1 x2 2x3 x1

2x1 x1,

答案：

(a)无界解；(b)唯一解X* (0.8,1.8,0)

T

x22x2x2,

x3 x3 x3x3

x

2 1

3x1

0 x,

1

0

6

(b)minz 2x1 3x2 x3

4x2 2x2x2,

x3 2x3

8 6 0

,z* 8)，对偶问题Y* (1,0)T,w* 8

4已知线性规划问题的初始单纯形表（如表1-54所示）和用单纯形法迭代后得到的表（如表1-55所示）如下，试求括弧中未知数a～l的值。

表1-54 初始单纯形表

表1-55 单纯形法迭代后的表

'

表1-55基变量x1列向量p ，所以g=1,h=0

0 1

pj, （2）初始表 b,

某步表B

1

b,

1

B 1pj

1/20

有已知表查出B 1/21

f 1/20 6 f 1

Bb 4 1/21 1 4 f 3,

1 1/20 b 1 1

Bp1 0 1/21 1 0 b 2

2 1/20 c 2 1

Bp2 i 1/21 3 i c 4,i 5

1 1/20 d 1 1

Bp3 1 1/21 e 1 d 2,e 2

（3）初始表主元行×（-主元检验数/主元）加到检验数行得下一步表的检

验数行。

表1-54第一行系数×（-a/b）+表1-54检验数行=表1-54检验数行

1

即： 2a 1 7,a 2 j,k a,l 0

2

故：a

3

3,j 5,k ,l 0。

2

5某厂生产Ⅰ、Ⅱ、Ⅲ三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1或A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品Ⅰ可在A、B任何一种设备上加工；产品Ⅱ可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品Ⅲ只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据见下表1-56，试安排最优生产计划，使该厂获利最大。

6 一家糖果商店出售三种不同品牌的果仁糖，每个品牌含有不同比例的杏仁、核桃仁、胡桃仁。为了维护商店的质量信誉，每个品牌中所含有的果仁的最大、最小比例是必须满足的，如下表1-57所示：

表1-57 每个品牌中所含有的果仁的比例表

商店希望确定每周购进杏仁、核桃仁、腰果仁、胡桃仁的数量，使周利润最大。建立数学模型，帮助该商店管理人员解决果仁混合的问题。 7 写出下列线性规划问题的对偶问题。

(a)minz 2x1 2x2 4x3 x1 3x2 2x

1 x2

x1 4x2 x1,x2 0,

4x3 3x33x3

n

2

3 5

x3无约束

(b)maxz cjxj

j 1

nax b(i 1, ,m1 m)ijji j 1 n aijxj bi(i m1 1, ,m) j 1

xj 0(j 1, ,n1 n) x无约束(j n1 1, ,n) j

答案： （a）

max 2y1 3y2 5y3 y1 2y2 3y

1 y2

4y1 3y2 x1,x2 0,

（b）

m1

y3 4y3 3x3

2

2 4

x3无约束

m

min biui bivi

i 1

i m1 1

m m1

aijui aijvi cj(j 1, ,n1 n) i 1i m1 1 m1

m

au av c(j n1 1,...,n)j i 1ijii m 1iji

1

(i 1, ,m1 n) ui 0

v无约束(i m1 1, ,m) i

8 已知线性规划问题：

maxz x1 x2

x1 x2 x3

2x1 x2 x3 x，x，x 0

3 12

答案：显然X

2 1

试应用对偶理论证明上述线性规划问题最优解为无界。

(0,0,0)T为该问题的可行解，

其对偶问题为：

min 2y1 y2 y1 2y2 1

y y2 11

y2 0 y1

y，y 0 12

显然第一个约束与变量非负要求矛盾，故对偶问题无可行解。由无界性该问题最优解

为无界。

9 已知线性规划问题：

maxz 2x1 4x2 x3 x4 x4 x1 3x2

2x x21

x2 x3 x4

x x2 x31 xj 0(j 1, ,4)

8

(1)(2)(3)(4)

6 6 9

要求：（1）写出其对偶问题；（2）已知原问题最优解为X*=(2,2,4,0)T，试根据对偶理论求出

对偶问题最优解。 答案： 对偶问题

min 8y1 6y2 6y3 9y4 y4 y1 2y2

3y y2 y3 y41

y3 y4

y y3 1 yj 0(j 1, ,4)

设对偶问题的最优解为Y

*

2 4 1 1

(1)(2)(3)(4)

****

(y1,y2,y3,y4)

将X*=(2,2,4,0)T代入原问题，约束（4）为严格不等式（即x*S1，x*S2，x*S3）0），由互补松

弛性，y*4=0。

又因为x1 =2,x2 =2,x3 =4

*

*

*

都大于0，由互补松弛性，对偶问题对应（1）--（3）

约束为等式，（即y*S1= y*S2 =y*S3=0）

y*

1

*故有 3y1

2y*2 y*2

y*

3 y*

3

*

2 4 1

(1)(2)， (3)

解得对偶问题的最优解为Y10 已知线性规划问题：

(4/5,y3/5,1,0)。

maxz 2x1 x2 x3

1

x1

x

x2 x3 2x2

6 4

x1,x2,x3 0

先用单纯形法求出最优解，再分析在下列条件单独变化的情况最优解的变化。 （1）目标函数变为maxz 2x1 3x2 x3； （2）约束右端项由 变为 ；

（3）增添一个新的约束条件： x1 2x3 2。

6 4 3 4

答案：

T

该问题的最优解X* (6,0,0,0,10)，最优值z* 2 6 12 对偶问题的最优解Y* (2,0,3,1,2)，最优值 * 6 2 12 （1）目标函数中非基变量x2的系数c2由-1变为3 重新计算x2的检验数 2

1

2 c2 CBp 3 (20) 3 1 0

'j

最优解发生变化，将x2的检验数 2

解之，见下表

1，系数c2 3代入最终表，用单纯形法求

T

该问题的最优解X* (8/3,10/3,0,0,0)，最优值z* 2

81046 3 333

3

3

对偶问题的最优解Y* (7/3,1/3,0,0,4/3),最优值 * 6 7 4 1 46

3

2

1

（2）Bb' 3

1 31 2 3

3 3 0，故最优基不变

1 7 4 3 3

2725

最优解为X* (2/3,7/3,0,0,0)，最优值z* 2 3

333

T

（3）最优解X* (6,0,0,0,10)不满足新加的约束 将约束化为等式，选松弛变量作为基变量得x1

T

2x3 x6 -2

将其添加到最终表得过渡表，然后将第一行乘-1加到第三行将基变量x1的系数列向

量化为单位向量

新的最优解X* (10/3,0,8/3,0,22/3)T，最优值z* 2 28

333

11 用分支定界法求解下列整数规划问题：

maxz 2x1 3x2

5x1 7x2 35(1)

4x1 9x2 36

x，x 0，且为整数

2 1

maxz x1 x2

2x1 5x2 16

(2)

6x 5x 30 12

x,x 0,且为整数 12

12 用隐枚举法求解下列0-1规划问题：

maxz 3x1 2x2 5x3 2x4 3x5

x1 x2 x3 2x4 x5 4 7x 3x3-4x4 3x5 8 1

3x4 5x5 3 11x1 6x2

xj 0或1(j 1, ,5)

xj=0 或1，j = 1，2，3，4，5

13 某航运公司承担六个港口城市A、B、C、D、E、F的四条固定航线的物资运输任务已知各条航线的起点、终点城市及每天航班数见表1-59。假定各条航线使用相同型号的船只，

又各城市之间的航程天数见表1-60。又知每条船只每次装卸货物的时间各需1天，则该航运公司至少应配备多少条船,才能满足所有航线的运货需求? 建立模型并用软件求解。

表1-60 各城市之间的航程天数表

14设某公司有五个人可以完成五项工作，每人做每项工作的用时如表1-61所示。每人仅做一项工作，每项工作仅一人做。如何安排是用时最少？建立数学模型并用软件求解

表1-61 每人完成任务的用时表 单位：天

15 思考题

（1） 线性规划问题在数学模型的形式、可行域的组成和最优点的位置等方面与非线性规

划问题有什么不同？

（2） 如何理解线性规划问题的求解其实就是可行域顶点的转换方法？ （3） 线性规划的基解、基可行解和最优解之间有什么关系？

（4） 在解得转换中，如何保证从一个基可行解转换得到的仍然是一个基可行解？ （5） 在解的转换中，如何保证目标函数的值不仅下降，而且下降得最多？ （6） 在单纯形算法中，如何选择主元？主元可以是负的吗？

（7） 线性规划问题的约束条件是等式约束时，如何通过建立辅助规划问题的一个初始基

本可行解？

（9） 简述对偶单纯形法的优点、适用条件和求解步骤。 (10) 试从经济上解释对偶问题和对偶变量的含义。 （11）分支定界法求解极大化问题时，任何一个可行解的目标函数是否都是该问题目标函数

值的下界？ 16 案例练习

题目：木材的储存和收购售出最优化问题

问题背景：在实际的销售模型中，往往会碰到一类由于每个时期的需求和供给量不同，而需要囤积货物在后期高价出售的问题，由于受到储存的成本，储存的空间，每个时期的销量等各方面的限制，使这个问题显得愈加复杂。

目标：要求就一个实际的木材的储存和收购售出的问题，简化该模型，使用线性规划的方法对其进行求解，并对各个参数进行灵敏度分析，最后给出合理的方案。 问题提出：江苏省某木材储运公司有一个非常大的仓库以用来存储和出售木材，由于木材的每季度价格不同，该公司计划在每季度初购入木材，根据实际的市场需求，一部分用于出售，另一部分则存储起来，等待以后出售。

已知该公司的仓库的最大存储量为200万立方米，储存费用为(a+bu)元/万立方米，其中a=7万，b=10万，u为存储的时间（季度数）。已知每季度的买进卖出价格以及预计的销售量如表1-62所示。由于木材不适宜长期存储，所有的库存木材应该于每年的秋天末售完。

需解决的问题：

①怎么样能获得最大的利润，并给出具体的策划方案。

②若由于市场的变化导致某个或几个季度的预计销售量变化该怎么应对？ ③公司为了扩张规模，将改建仓库扩大容量，在该表的情况下该如何规划？ ④对该问题和模型尝试进行改进。

本文来源：https://www.bwwdw.com/article/q4ri.html