运筹学清华第四版答案

运筹学清华第四版答案

【篇一：清华_第三版_运筹学教程_课后答案~(_第一章

_第五章部分)】

文字]

运筹学教程

1. 某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg

维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如表1所示。表1

要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。

解：设总费用为z。i=1,2,3,4,5代表5种饲料。xi表示满足动物生长的营养需要时，第i种饲料所需的数量。则有：

minz?0.2x1?0.7x

2?0.4x3?0.3x4?0.8x5?3x1?2x2?x3?6x4?8x5?700?

?x1?0.5x2?0.2x3?2x4?0.5x5?30s.t.?

?0.5x1?x2?0.2x3?2x4?0.8x5?100?x?0,i?1,2,3,4,5?i

2. 某医院护士值班班次、每班工作时间及各班所需护士数如表2所示。每班护士值班

开始时间向病房报道，试决定：

（1）若护士上班后连续工作8h，该医院最少需要多少名护士，以满足轮班需要；（2）若除22:00上班的护士连续工作8h外（取消第6班），其他班次护士由医院

排定上1～4班的其中两个班，则该医院又需要多少名护士满足轮班需要。

表2

6

2:00～6:00 30

解：（1）设x第i班开始上班的人数，i=1,2,3,4,5,6

minz?x1?x2?x3?x4?x5?x6?x1

??x1?x2?s.t.?x3

?x?4?x5??xi

?x6?60?x2?70?x3?60?x4?50?x5?20?x6?30

?0,i?1,2,3,4,5,6且为整数

解：（2）在题设情况下，可知第五班一定要30个人才能满足轮班需要。则设设xi第i班开始上班的人数，i=1,2,3,4。

minz?x1?x2?x3?x4?30

?y11x1?y21x2?y31x3?y41x4?60，第一班约束

?

?y11?1,y11?y12?y13?y14?2

?yx?yx?yx?yx?70，第二班约束121222323424?

?y22?1，y21?y22?y23?y24?2?

s.t.?y13x1?y23x2?y33x3?y43x4?60，第三班约束?y?1，

y?y?y?y?2

31323334

?33

?y14x1?y24x2?y34x3?y44x4?50，第四班约束?

?y44?1，y41?y42?y43?y44?2

?x?0，y是0—1变量，i,j?1,2,3,4

ij?i

3. 要在长度为l的一根圆钢上截取不同长度的零件毛坯，毛坯长度有n种，分别为aj

（j=1,2，…n）。问每种毛坯应当截取多少根，才能使圆钢残料最少，试建立本问题的数学模型。

解：设xi表示各种毛坯的数量，i=1,2,…n。

n

maxz?

?a

i?1

i

xi

?n

??aixi?1?i?1

?x是整数?i

4. 一艘货轮分前、中、后三个舱位，它们的与最大允许载重量如表3.1所示。现有三

种

货物待运，已知有相关数据列于表3.2。表3.1

表3.2

又为了航海安全，前、中、后舱实际载重量大体保持各舱最大允许载重量的比例关系。具体要求：前、后舱分别与中舱之间载重量比

例的偏差不超过15%，前、后舱之间不超过10%。问该货轮应该载a,b,c各多少件运费收入才最大？试建立这个问题的线性规划模型。解：设xij表示第i件商品在舱j的装载量，i,j=1,2,3

maxz?1000(x11?x12?x13)?700(x21?x22?x23)?600(x31?x32?x3 3)

1) 商品的数量约束：

?x11?x12?x13?600

?

?x21?x22?x23?1000 ?x?x?x?800

3233?31

2) 商品的容积约束：

?10x11?5x21?7x31?4000?

?10x12?5x22?7x32?5400 ?10x?5x?7x?1500

132333?

3) 最大载重量约束：

?8x11?6x21?5x31?2000?

?8x12?6x22?5x32?3000 ?8x?6x?5x?1500

2333?13

4) 重量比例偏差的约束：

?

?8x11??8x?11??8x

13???8x

13???8x13???8x13?

?6x21?5x31??6x21?5x31??6x23?5x33??6x23?5x33??6x23?5x 33??6x23?5x33?

232312123434

(1?0.15)(8x12?6x22?5x32)(1?0.15)(8x12?6x22?5x32)(1?0.15)(8x 12?6x22?5x32)

(1?0.15)(8x12?6x22?5x32)(1?0.1)(8x11?6x21?5x31)(1?0.1)(8x11 ?6x21?5x31)

5. 篮球队需要选择5名队员组成出场阵容参加比赛。8名队员的身高及擅长位置见表

5. 表5

出场阵容应满足以下条件：（1）只能有一名中锋上场；（2）至少一名后卫；

（3）如1号和4号均上场，则6号不出场；（4） 2号和8号至少有一个不出场。

问应当选择哪5名队员上场，才能使出场队员平均身高最高，试建立数学模型。解：设xi?1表示第i个队员出场，i=1,2…8.

maxz?

1

8

i

x?5

i?1

?8

??xi?5

?i?1

?

?x1?x2?1，x6?x7?x8?1?x?x?1，x?x?x?2

8146

?2??xi是0—1变量

6. 时代服装公司生产一款新的时装，据预测今后6个月的需求量如表4所示，每件时

装用工2h和10元原材料费，售价40元。该公司1月初有4名工人，每人每月可工作200h，月薪2000元。该公司可于任一个月初新雇工人，但每雇1人需一次性额外支出1500元，也可辞退工人，但每辞退1人需补偿1000元。如当月生产数超过需求，可留到后面月份销售，但需付库存费每件每月5元，当供不应求时，短缺数不需补上。试帮组该公司决策，如何使用6个月的总利润最大。

表4单位：件

解：设xi1为第i月现有工人人数，xi2为新雇工人人数，xi3为辞退工人人数，yi为每月的需求。i=1,2，…，6。则有：

6

maxz?

?(40?10)?

i?1

2002

66j

(xi1?xi2)?

?(2000

i?1

xi1?3500xi2?1000xi3)?5??(n

i

?yi)f(ni?yi)

j?1k?1

?1，x?0

其中f(x)??

?0，x?0

?x11?4?

2，?，5?xi1?xi3?xi1?xi2，i?1，

s.t.?

?ni?200?(xi1?xi2)?2?x?0，i?1，2，,?，6；k?1，2?ik

7. 童心玩具厂下一年度的现金流（万元）如表6所示，表中负号表

示该月现金流出大

于流入，为此该厂需借款。借款有两种方式：一是于上一年末借一

年期贷款，一次得全部贷款额，从1月底起每月还息1%，于12月

归还本金和最后一次利息；二是得到短期贷款，每月初获得，于月

底归还，月息1.5%。当该厂有多余现金时，可短期

【篇二：运筹学习题及答案】

章（39页）

1.1用图解法求解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解。（1）max z?x1?x2

5x1+10x2?50

x1+x2?1 x2?4 x1，x2?0

（2）min z=x1+1.5x2

x1+3x2?3 x1+x2?2 x1，x2?0

（3）max z=2x1+2x2

x1-x2?-1

-0.5x1+x2?2

x1，x2?0

（4）max z=x1+x2

x1-x2?0

3x1-x2?-3

x1，x2?0

解：（1）（图略）有唯一可行解，max z=14 （2）（图略）有唯

一可行解，min z=9/4 （3）（图略）无界解（4）（图略）无可行

解

1.2将下列线性规划问题变换成标准型，并列出初始单纯形表。

（1）min z=-3x1+4x2-2x3+5x4 4x1-x2+2x3-x4=-2

x1+x2+3x3-x4?14

-2x1+3x2-x3+2x4?2

x1，x2，x3?0，x4无约束

（2）max s?

n

m

zk

pk

zk???aikxik

i?1k?1

??x

k?1

m

ik

??1(i?1,...,n)

xik?0 (i=1…n; k=1,…,m)

（1）解：设z=-z?,x4=x5-x6, x5,x6?0 标准型：

max z?=3x1-4x2+2x3-5(x5-x6)+0x7+0x8-mx9-mx10 s. t .

-4x1+x2-2x3+x5-x6+x10=2

x1+x2+3x3-x5+x6+x7=14

-2x1+3x2-x3+2x5-2x6-x8+x9=2

x1,x2,x3,x5,x6,x7,x8,x9,x10?0

(2)解：加入人工变量x1，x2，x3，…xn，得： max s=(1/pk)?

i?1n

?

k?1

m

?ikxik-mx1-mx2-…..-mxn

s.t.

xi??xik?1 (i=1,2,3…,n)

k?1m

xik?0, xi?0, (i=1,2,3…n; k=1,2….,m)

m是任意正整数

1.3在下面的线性规划问题中找出满足约束条件的所有基解。指出哪些是基可行解，并代入目标函数，确定最优解。（1）max

z=2x1+3x2+4x3+7x4 2x1+3x2-x3-4x4=8 x1-2x2+6x3-7x4=-3

x1,x2,x3,x4?0

(2)max z=5x1-2x2+3x3-6x4

x1+2x2+3x3+4x4=7

2x1+x2+x3+2x4=3

x1x2x3x4?0

（1）解：

系数矩阵a是：

?23?1?4??1?26?7? ??

令a=(p1，p2，p3，p4)

p1与p2线形无关，以（p1，p2）为基，x1，x2为基变量。

有2x1+3x2=8+x3+4x4x1-2x2=-3-6x3+7x4 令非基变量x3，x4=0 解得：x1=1；x2=2

基解x(1)=（1，2，0，0)t为可行解

z1=8

同理，以（p1，p3）为基，基解x(2)=（45/13，0，-14/13，0)t是非可行解；以（p1，p4）为基，基解x(3)=（34/5，0，0，7/5)t是可行解，z3=117/5；以（p2，p3）为基，基解x(4)=（0，45/16，7/16，0)t是可行解，z4=163/16；以（p2，p4）为基，基解x(5)=（0，68/29，0，-7/29)t是非可行解；以（p4，p3）为基，基解

x(6)=（0，0，-68/31，-45/31)t是非可行解；最大值为z3=117/5；最优解x(3)=（34/5，0，0，7/5)t。（2）解：

系数矩阵a是：

?1234??2112? ??

令a=(p1，p2，p3，p4)

p1，p2线性无关，以（p1，p2）为基，有： x1+2x2=7-3x3-4x4 2x1+x2=3-x3-2x4 令 x3，x4=0得

x1=-1/3，x2=11/3

基解x(1)=（-1/3，11/3，0，0)t为非可行解；

同理，以（p1，p3）为基，基解x(2)=（2/5，0，11/5，0)t是可行解z2=43/5；以（p1，p4）为基，基解x(3)=（-1/3，0，0，11/6)t 是非可行解；以（p2，p3）为基，基解x(4)=（0，2，1，0)t是可行解，z4=-1；以（p4，p3）为基，基解x(6)=（0，0，1，1)t是

z6=-3；最大值为z2=43/5；最优解为x(2)=（2/5，0，11/5，0)t。

1.4分别用图解法和单纯形法求解下列线性规划问题，并指出单纯形迭代每一步相当于图形的哪一点。

（1）max z=2x1+x23x1+5x2?156x1+2x2?24

x1，x2?0

（2）max z=2x1+5x2

2x2?12 3x1+2x2?18

x1，x2?0

【篇三：运筹学(清华大学第三版)习题集】

ax z?2x1?3x2

?x1?2x2?x3?8?

?4x1?x4?16

s.t. ?

?4x2?x5?12

?xj?0,j?1,2,?,5?

解：依据单纯形理论，有以下计算：

（1）令x3,x4,x5为基变量、x1,x2为非基变量，可得

?x1?

2100??x2??8??x3?8?x1?2x2

???

，代入目标函数，得z?0?2x1?3x2。 0010??x3???16?，解得?x4?16?4x1

?????

?x?12?4x4001?2?5??x4???12??

??x5??

?1

?4???0

此时得到的解为x?(0,0,8,16,12)t，z?0。由

?z?x1

?2?0、

?z?x2

?3?0可知，x1,x2取正值可使z增大。

?x3?8?2x2?0

?x2?4?

若令x2取正值且x1仍为0，由?x4?16?0，可得?，这说明x2最大可以达到3，此

x?3?2?x?12?4x?0

2?5

时x5将变为0，成为非变量。

（2）令x2,x3,x4为基变量、x1,x5为非基变量，可得

?x1?

?1/2??x2??2??x2?3?x5/4

0??x3???16?，解得?x3?2?x1?x5/2，目标函数变为

z?9?2x1?x5。 ?????4?x?16?4x??1/4?x31?4??4???

??x5??

?1010

?4001???0100

此时得到的解为x?(0,3,2,16,0)t，z?9。由

?z?x1

?2?0可知，x1取正值可使z增大。

?x2?3?0

?x1?2?

若令x1取正值且x5仍为0，由?x3?2?x1?0，可得?，这说明x1最大可以达到2，此

x?4?1?x?16?4x?0

?41

时x3将变为0，成为非基本变量。

（3）令x1,x2,x4为基变量、x3,x5为非基变量，可得解

x?(2,3,0,8,0)t，z?13。此时z?13?2x3?

14

x5，可知此时应让x5取正值，即进入基变量。

经过类似检查，可知应让x4变成非基变量。

（4）令x1,x2,x5为基变量，x3,x4为非基变量，可得解

x?(4,2,0,4,0)t，此时z?14?32x3?

18

x4，达到最优点。

上述过程可以编制表格计算，这就是单纯形法。

z?14。

例1.9 分别用图解法、单纯形法求解例1.8的lp问题，并指出单纯形法迭代的每一步相当于图形上的哪个顶点。

max z?2x1?3x2

?x1?2x2?x3?8?

s.t. ?4x?

1?x4?16

?4x2?x5?12

??xj?0,j?1,2,?,5解：原问题可等价转化为：

max z?2x1?3x2?x1?2x2?8?

s.t. ?4x1?16

?

?4x2?12

??xj?0,j?1,2图解如下：

可知，目标函数在b(4, 2)处取得最大值，故原问题的最优解为

x*?(4,2)t，目标函数最大值为z*?2*4?3*2?14。

用单纯形法求解原问题时，单纯形表如下：

原问题的最优解为x*?(4,2,0,0,4)t，目标函数最大值为

z*?2*4?3*2?14。单纯形法的寻找路径为：

x(1)?(0,0,8,16,12)→x(2)?(0,3,2,16,0)→

x(3)?(2,3,0,8,0) → x(4)?(4,2,0,0,4)

与图解法对照，寻找相当于o(0, 0) → d(0, 3) → c(2, 3) → b(4, 2)。例1：用单纯形法求解下述lp问题。

max z?3x1?4x2?2x1?x2?40

， ?

s.t. ?x1?3x2?30

?x,x?0?12

解：首先将原问题转化为线性规划的标准型，引入松弛变量x3、x4，可得：

max z?3x1?4x2?2x1?x2?x3?40

?

s.t. ?x1?3x2?x4?30

?x,x,x,x?0?1234

构造单纯形表，计算如下：

由此可得，最优解为x*?(18, 4, 0, 0)t，目标函数值为

z*?3*18?4*4?70。