管理运筹学(第四版)第十一章习题答案

第一篇：管理运筹学(第四版)第十一章习题答案

11.1解：

4人/小时，60410人/小时，0.4，属于M/M/1排队模型。610

（1）仓库管理员空闲的概率，即为P0110.40.6

（2）仓库内有4个工人的概率即为P41410.40.440.01536（3）至少有2个工人的概率为1P0P110.60.240.16（4）领工具的工人平均数Ls440.6667人

1046（5）排队等待领工具工人的平均数Lq0.441.60.2667人 1046（6）平均排队时间Wq（7）待定

11.2解：

0.40.40.0667小时4分钟

1046606033人/小时，4人/小时，0.75，属于M/M/1排队模型。20154

（1）不必等待概率，即为P0110.750.25

（2）不少于3个顾客排队等待的概率，即系统中有大于等于4个（或大于3个）顾客的概率，为

1P0P1P2P310.250.18750.14060.10550.3164

（3）顾客平均数Ls333人 431（4）平均逗留时间Ws111小时 43（5）1.5小时Ws11人/小时。平均到达率超过3.333人，即3.3334时，店主才会考虑增加设备或理发员。

11.3解： 4人/小时，60410人/小时，0.4，属于M/M/1/3排队模型。610

（1）仓库内没有人领工具的概率，即为P0110.40.6158 N14110.4（2）工人到达必须排队等待的概率，即为仓库内有1个、2个和3个工人的概率和

P1P2P323110.4230.40.40.40.3842

1N110.44（3）新到工人离去的概率为P33110.430.40.0394 N14110.4（4）领工具的工人平均数Ls1N1N11N10.440.44 410.410.4（5）排队等待领工具工人的平均数Lq0.441.60.2667人 1046（6）平均排队时间Wq

0.40.40.0667小时4分钟

1046

第二篇：运筹学黄皮版课后习题答案详解

ijcij(uivj)i1,2,m;j1,2,,ncij(uivj)0i1,2,m;j1,2,,n

4、对于产销平衡的运输问题，所有的约束都取等式。

3.2 运输问题的基可行解应满足什么条件？将其填入运输表中时有什么体现？并说明在迭代计算过程中对它的要求。

解：运输问题基可行解的要求是基变量的个数等于m+n-1。填入表格时体现在数字格的个数也应该等于m+n-1。在迭代过程中，要始终保持数字格的个数不变。

3.3 试对给出运输问题初始基可行解的西北角法、最小元素法和Vogel法进行比较，分析给出的解之质量不同的原因。

解：用西北角法可以快速得到初始解，但是由于没有考虑运输价格，效果不好；最小元素法从最小的运输价格入手，一开始效果很好，但是到了最后因选择余地较少效果不好； Vogel法从产地和销地运价的级差来考虑问题，总体效果很好，但是方法较复杂。

3.4 详细说明用位势法(对偶变量法)求检验数的原理。

解：原问题的检验数也可以利用对偶变量来计算 ：

其中，ui和vj就是原问题约束对应的对偶变量。由于原问题的基变量的个数等于m+n-1。所以相应的检验数就应该等于0。即有：

由于方程有m+n-1个，而变量有m+n个。所以上面的方程有无穷多个解。任意确定一个变量的值都可以通过方程求出一个解。然后再利用这个解就可以求出非基变量的检验数了。

3.5 用表上作业法求解运输问题时，在什么情况下会出现退化解？当出现退化解时应如何处理？ 解：当数字格的数量小于m+n-1时，相应的解就是退化解。如果出现了退化解，首先找到同时划去的行和列，然后在同时划去的行和列中的某个空格中填入数字0。只要数字格的数量保持在m+n-1个的水平即可。

3.6 一般线性规划问题具备什么特征才能将其转化为运输问题求解，请举例说明。

解：如果线性规划问题有“供”和“需”的关系，并且有相应的“费用”，就可以考虑将线性规划问题转成运输问题求解。例如，生产满足需求的问题。3.7 试判断表3-30和表3-31中给出的调运方案可否作为表上作业法迭代时的基可行解?为什么?

答：都不是。数字格的数量不等于m+n-1。

3.8 表3-32和表3-33分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。

3.9 试求出表3-34给出的产销不平衡运输问题的最优解。

3.10 某市有三个面粉厂，它们供给三个面食加工厂所需的面粉。各面粉厂的产量、各面食加工厂加工面粉的能力、各面食加工厂和各面粉厂之间的单位运价，均表示于表3-35中。假定在第1，2和3面食加工厂制作单位面粉食品的利润分别为12元、16元和11元，试确定使总效益最大的面粉分配计划(假定面粉厂和面食加工厂都属于同一个主管单位)。

3.11 表3-36示出一个运输问题及它的一个解：

试问：

(1)表中给出的解是否为最优解？请用位势法进行检验。答：是最优解。(2)如价值系数c24由1变为3，所给的解是否仍为最优解？若不是，请求出最优解。答：

原来的解不是最优解。新的最优解是： x12=3,x13=5,x21=8,x22=2,x33=1,x34=3，其他变量为0。

(3)若所有价值系数均增加1，最优解是否改变？为什么? 答：不会改变。因为检验数不变。

(4)若所有价值系数均乘以2，最优解是否改变？为什么? 答：最优解不变。因为检验数不变。

(5)写出该运输问题的对偶问题，并给出其对偶问题的最优解。

3.12 1，2，3三个城市每年需分别供应电力320，250和350单位，由I，Ⅱ两个电站提供，它们的最大供电量分别为400个单位和450个单位，单位费用如表3—37所示。由于需要量大于可供量，决定城市1的供应量可减少0～30单位，城市2的供应量不变，城市3的供应量不能少于270单位，试求总费用最低的分配方案(将可供电量用完)。

解：对偶问题如下：maxZaiuibjvji1j1mnuivjciji1,2,m;j1,2,,nui,vj无约束,i1,2,m;j1,2,,n最优解是：u11,u20,u30,v11,v22,v35,v41

第三篇：运筹学习题解答

3.3写出下列线性规划问题的对偶问题，再写出对偶问题的对偶，并验证其即为原问题对偶。

本题没有单纯形法。

5.3 没有答案

第四篇：《管理运筹学》第三版习题答案(韩伯棠教授版)

第2章

1、解：

x2 6

线性规划的图解法

A 1 O 0 1 B

C3 6

x1

a.可行域为 OABC。

b.等值线为图中虚线所示。

c.由图可知，最优解为 B 点，最优解： x1 = 69。

2、解： a

x2

1215

x2 =，最优目标函数值：

0.6

0.1 O

0.1

0.6

x1

x1 = 0.2

有唯一解 b 无可行解 c 无界解 d 无可行解 e 无穷多解 x 2 = 0.6 函数值为 3.6 20 x1 = 923 f 有唯一解函数值为

x2 = 3

3、解：

a 标准形式：

max f = 3x1 + 2 x 2 + 0s1 + 0 s 2 + 0s 3 x1 + 2 x 2 + s1 = 30 3x1 + 2 x 2 + s 2 = 13 2 x1 + 2 x 2 + s3 = 9 x1 , x 2 , s1 , s 2 , s3 ≥ 0

b 标准形式：

max f = −4 x1 − 6 x3 − 0s1 − 0s2

3x1 − x 2 − s1 = 6 x1 + 2 x 2 + s 2 = 10 7 x1 − 6 x 2 = 4 x1 , x 2 , s1 , s 2 ≥ 0

c 标准形式：

max f = − x1' + 2 x2 − x2 − 0s1 − 0s2 '''

− 3x1 + 5 x 2 − 5 x 2'

+ s1 = 70 ''2 x1' − 5 x 2 + 5 x 2' = 50

''3x1' + 2 x 2 − 2 x 2' − s 2 = 30

''x1' , x 2 , x 2' , s1 , s 2 ≥ 0

''4、解：

标准形式： max z = 10 x1 + 5 x 2 + 0 s1 + 0 s 2

3x1 + 4 x 2 + s1 = 9 x1 + 2 x 2 + s 2 = 8 x1 , x 2 , s1 , s 2 ≥ 0

s1 = 2, s2 = 0 5、解：

标准形式： min f = 11x1 + 8 x 2 + 0s1 + 0s 2 + 0s3 x1 + 2 x 2 − s1 = 20 3x1 + 3x 2 − s 2 = 18 4 x1 + 9 x 2 − s3 = 36

x1 , x 2 , s1 , s 2 , s3 ≥ 0

s1 = 0, s2 = 0, s3 = 13 6、解：

b 1 ≤ c1 ≤ 3 c 2 ≤ c2 ≤ 6 x1 = 6 d x2 = 4

e x1 ∈ [4,8] x 2 = 16 − 2 x1 f 变化。原斜率从 −

7、解：

模型：

变为 − 1 3

max z = 500 x1 + 400 x 2 x1 ≤ 300 3x2 ≤ 540 x1 + 2 x2 ≤ 440 1.2 x1 + 1.5 x2 ≤ 300 x1 , x2 ≥ 0

a x1 = 150 x 2 = 70 即目标函数最优值是 103000 b 2，4 有剩余，分别是 330，15。均为松弛变量 c 50，0，200，0额外利润 250 d 在 [0,500] 变化，最优解不变。e 在 400 到正无穷变化，最优解不变。f 不变 8、解：

a 模型： min f = 8 x a + 3 xb

x a + 100 xb ≤ 1200000 5 x a + 4 xb ≥ 60000 100 xb ≥ 300000 x a , xb ≥ 0

基金 a,b 分别为 4000，10000。回报率：60000

b 模型变为： max z = 5 x a + 4 xb

x a + 100 xb ≤ 1200000 100 xb ≥ 300000 x a , xb ≥ 0

推导出： x1 = 18000 x 2 = 3000

故基金 a 投资 90 万，基金 b 投资 30 万。第3章

1、解： a x1 = 150 x 2 = 70

线性规划问题的计算机求解

目标函数最优值 103000

b 1，3 使用完 2，4 没用完0，330，0，15 c 50，0，200，0

含义： 1 车间每增加 1 工时，总利润增加 50 元车间每增加 1 工时，总利润增加 200 元2、4 车间每增加 1 工时，总利润不增加。d 3 车间，因为增加的利润最大

e 在 400 到正无穷的范围内变化，最优产品的组合不变 f 不变 因为在 [0,500] 的范围内

g 所谓的上限和下限值指当约束条件的右边值在给定范围内变化时，约束条

件 1 的右边值在 [200,440]变化，对偶价格仍为 50（同理解释其他约束条件）h 100×50=5000 对偶价格不变

i能

j 不发生变化 允许增加的百分比与允许减少的百分比之和没有超出 100% k 发生变化

2、解：

a 4000 1000062000

b 约束条件 1：总投资额增加 1 个单位，风险系数则降低 0.057

约束条件 2：年回报额增加 1 个单位，风险系数升高 2.167 c 约束条件 1 的松弛变量是 0，约束条件 2 的剩余变量是 0

约束条件 3 为大于等于，故其剩余变量为 700000

d 当 c 2 不变时，c1 在 3.75 到正无穷的范围内变化，最优解不变

当 c1 不变时，c 2 在负无穷到 6.4 的范围内变化，最优解不变

e 约束条件 1 的右边值在 [780000,1500000] 变化，对偶价格仍为 0.057（其他

同理）

f 不能，理由见百分之一百法则二 3、解：

a 18000 3000 102000 153000

b 总投资额的松弛变量为 0 基金 b 的投资额的剩余变量为 0 c 总投资额每增加 1 个单位，回报额增加 0.1

基金 b 的投资额每增加 1 个单位，回报额下降 0.06 d c1 不变时，c 2 在负无穷到 10 的范围内变化，其最优解不变 c 2 不变时，c1 在 2 到正无穷的范围内变化，其最优解不变 e 约束条件 1 的右边值在 300000 到正无穷的范围内变化，对偶价格仍为 0.1约束条件 2 的右边值在 0 到 1200000 的范围内变化，对偶价格仍为-0.06

600000 300000

f+= 100% 故对偶价格不变

900000 900000

4、解：

a x1 = 8.5 x 2 = 1.5x 3 = 0 x4 = 1 最优目标函数 18.5

对偶价格为 2 和 3.5b 约束条件 2 和 3 c 选择约束条件 3，最优目标函数值 22

d 在负无穷到 5.5 的范围内变化，其最优解不变，但此时最优目标函数值变化

e 在 0 到正无穷的范围内变化，其最优解不变，但此时最优目标函数值变化

5、解：

a 约束条件 2 的右边值增加 1 个单位，目标函数值将增加 3.622 b x 2 产品的利润提高到 0.703,才有可能大于零或生产 c 根据百分之一百法则判定，最优解不变

1565

d 因为我们不能判定+> 100 % 根据百分之一百法则二，− 9.189 111.25 − 1

5其对偶价格是否有变化 第4章 线性规划在工商管理中的应用

1、解：为了用最少的原材料得到 10 台锅炉，需要混合使用 14 种下料方案

方案 规格 2640 1770 1651 1440 合计 剩余

方案 规格 2640 1770 1651 1440 合计 剩余 1 2 0 0 0 5280 220 8 1 1 0 0 4410 1090 9 1 0 1 0 4291 1209 10 1 0 0 1 4080 1420 11 0 3 0 0 5310 190 12 0 2 1 0 5191 309 13 0 2 0 1 4980 520 14

0 1 2 0 5072 428 0 1 1 1 4861 639 0 1 0 2 4650 850 0 0 3 0 4953 547 0 0 2 1 4742 758 0 0 1 2 4531 969 0 0 0 3 4320 1180

设按 14 种方案下料的原材料的根数分别为 x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11，x12，x13，x14，则可列出下面的数学模型：

min f＝x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14 s．t． 2x1＋x2＋x3＋x4 ≥ 80

x2＋3x5＋2x6＋2x7＋x8＋x9＋x10 ≥ 350 x3＋x6＋2x8＋x9＋3x11＋x12＋x13 ≥ 420 x4＋x7＋x9＋2x10＋x12＋2x13＋3x14 ≥ 10

x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11，x12，x13，x14≥ 0

用管理运筹学软件我们可以求得此问题的解为：

x1＝40，x2＝0，x3＝0，x4＝0，x5＝116.667，x6＝0，x7＝0，x8＝0，x9＝0，x10＝0，x11＝140，x12＝0，x13＝0，x14＝3.33

3最优值为 300。

2、解：从上午 11 时到下午 10 时分成 11 个班次，设 xi 表示第 i 班次安排的临时

工的人数，则可列出下面的数学模型：

min f＝16（x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11）

s．t． x1＋1 ≥ 9 x1＋x2＋1 ≥ 9 x1＋x2＋x3＋2 ≥ 9 x1＋x2＋x3＋x4＋2 ≥ 3 x2＋x3＋x4＋x5＋1 ≥ 3 x3＋x4＋x5＋x6＋2 ≥ 3 x4＋x5＋x6＋x7＋1 ≥ 6 x5＋x6＋x7＋x8＋2 ≥ 12 x6＋x7＋x8＋x9＋2 ≥ 12 x7＋x8＋x9＋x10＋1 ≥ 7 x8＋x9＋x10＋x11＋1 ≥ 7

x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11≥ 0 用管理运筹学软件我们可以求得此问题的解为：

x1＝8，x2＝0，x3＝1，x4＝1，x5＝0，x6＝4，x7＝0，x8＝6，x9＝0，x10＝0，x11＝0 最优值为 320。

a、在满足对职工需求的条件下，在 10 时安排 8 个临时工，12 时新安排

1个临时工，13 时新安排 1 个临时工，15 时新安排 4 个临时工，17 时新

安排 6 个临时工可使临时工的总成本最小。

b、这时付给临时工的工资总额为 80 元，一共需要安排 20 个临时工的班

次。

约束-------1 2 3 4 5 6 7 8 9 10 1

1松弛/剩余变量

对偶价格

0-4 0 0 2 0 9 0 0-4 5 0 0 0 0 0 0-4 0 0 0 0

根据剩余变量的数字分析可知，可以让 11 时安排的 8 个人工作 3 小时，13

时安排的 1 个人工作 3 小时，可使得总成本更小。

C、设在 11：00-12：00 这段时间内有 x1 个班是 4 小时，y1 个班是 3 小时； 设在 12：00-13：00 这段时间内有 x 2 个班是 4 小时，y 2 个班是 3 小时；其他时 段也类似。

则：由题意可得如下式子： 11

min z = 16∑ x1 + 12∑ y1

i =1 i =1 S．T

x1 + y1 + 1 ≥ 9

x1 + y1 + x2 + y2 + 1 ≥ 9

x1 + y1 + x2 + y2 + x3 + y3 + 1 + 1 ≥ 9 x1 + x2 + y2 + x3 + y3 + x4 + y4 + 1 + 1 ≥ 3

x2 + x3 + y3 + x4 + y4 + x5 + y5 + 1 ≥ 3 x3 + x4 + y4 + x5 + y5 + x6 + y6 + 1 + 1 ≥ 3 x4 + x5 + y5 + x6 + y6 + x7 + y7 + 1 ≥ 6 x5 + x6 + y6 + x7 + y7 + x8 + y8 + 1 + 1 ≥ 12 x6 + x7 + y7 + x8 + y8 + x9 + y9 + 1 + 1 ≥ 12 x7 + x8 + y8 + x9 + y9 + x10 + y10 + 1 ≥ 7 x8 + x9 + y9 + x10 + y10 + x11 + y11 + 1 ≥ 7 xi ≥ 0, yi ≥ 0 i=1,2,…,11

稍微变形后，用管理运筹学软件求解可得：总成本最小为 264 元。

安排如下：y1=8（即在此时间段安排 8 个 3 小时的班）3=1，y5=1，y7=4，x8=6，y 这样能比第一问节省：320-264=56 元。

3、解：设生产 A、B、C 三种产品的数量分别为 x1，x2，x3，则可列出下面的数学模型：

max z＝10 x1＋12 x2＋14 x

2s．t． x1＋1.5x2＋4x3 ≤ 2000 2x1＋1.2x2＋x3 ≤ 1000 x1 ≤ 200 x2 ≤ 250 x3 ≤ 100

x1，x2，x3≥ 0

用管理运筹学软件我们可以求得此问题的解为：

x1＝200，x2＝250，x3＝100

最优值为 6400。

a、在资源数量及市场容量允许的条件下，生产 A 200 件，B 250 件，C 100

件，可使生产获利最多。

b、A、B、C 的市场容量的对偶价格分别为 10 元，12 元，14 元。材料、台

时的对偶价格均为 0。说明 A 的市场容量增加一件就可使总利润增加 10

元，B 的市场容量增加一件就可使总利润增加 12 元，C 的市场容量增加

一件就可使总利润增加 14 元。但增加一千克的材料或增加一个台时数都

不能使总利润增加。如果要开拓市场应当首先开拓 C 产品的市场，如果

要增加资源，则应在 975 到正无穷上增加材料数量，在 800 到正无穷上

增加机器台时数。

4、解：设白天调查的有孩子的家庭的户数为 x11，白天调查的无孩子的家庭的户 数为 x12，晚上调查的有孩子的家庭的户数为 x21，晚上调查的无孩子的家庭 的户数为 x22，则可建立下面的数学模型： min f＝25x11＋20x12＋30x21＋24x22 s．t． x11＋x12＋x21＋x22 ≥ 2000 x11＋x12 ＝ x21＋x2

2x11＋x21 ≥ 700 x12＋x22 ≥ 450

x11, x12, x21, x22 ≥ 0

用管理运筹学软件我们可以求得此问题的解为：

x11＝700，x12＝300，x21＝0，x22＝1000

最优值为 47500。

白天调查的无孩子的家庭的户a、白天调查的有孩子的家庭的户数为 700 户，数为 300 户，晚上调查的有孩子的家庭的户数为 0，晚上调查的无孩子的家庭的户数为 1000 户，可使总调查费用最小。

总调查费用不会变化；b、白天调查的有孩子的家庭的费用在 20－26 元之间，总调查费用不会变化；白天调查的无孩子的家庭的费用在 19－25 元之间，晚上调查的有孩子的家庭的费用在 29－无穷之间，总调查费用不会变化；

晚上调查的无孩子的家庭的费用在－20－25 元之间，总调查费用不会变

化。

c、调查的总户数在 1400－无穷之间，总调查费用不会变化；

有孩子家庭的最少调查数在 0－1000 之间，总调查费用不会变化；

无孩子家庭的最少调查数在负无穷－1300 之间，总调查费用不会变化。

5、解：设第 i 个月签订的合同打算租用 j 个月的面积为 xij，则需要建立下面的数学模型：

min f＝2800（x11＋x21＋x31＋x41）＋4500（x12＋x22＋x32）＋6000（x13＋x23）

＋7300 x14

s．t．x11＋x12＋x13＋x14 ≥ 15

x12＋x13＋x14＋x21＋x22＋x23 ≥ 10 x13＋x14＋x22＋x23＋x31＋x32≥ 20 x14＋x23＋x32＋x41≥ 12

xij ≥ 0，i，j＝1，2，3，4

用管理运筹学软件我们可以求得此问题的解为：

x11＝5，x12＝0，x13＝10，x14＝0，x21＝0，x22＝0，x23＝0，x31＝10，x32＝0，x41＝0

最优值为 102000。

即：在一月份租用 500平方米一个月，租用 1000平方米三个月；在三月

份租用 1000平方米一个月，可使所付的租借费最小。

6、解：设 xij 表示第 i 种类型的鸡需要第 j 种饲料的量，可建立下面的数学模型：

max z＝9（x11＋x12＋x13）＋7（x21＋x22＋x23）＋8（x31＋x32＋x33）－5.5（x11＋x21＋x31）－4（x12＋x22＋x32）－5（x13＋x23＋x33）

s．t． x11 ≥ 0.5（x11＋x12＋x13）x12 ≤ 0.2（x11＋x12＋x13）

x21 ≥0.3（x21＋x22＋x23）

x23 ≤ 0.3（x21＋x22＋x23）

x33 ≥ 0.5（x31＋x32＋x33）

x11＋x21＋x31 ≤ 30 x12＋x22＋x32 ≤ 30 x13＋x23＋x33 ≤30

xij ≥ 0，i，j＝1，2，3

用管理运筹学软件我们可以求得此问题的解为：

x11＝30，x12＝10，x13＝10，x21＝0，x22＝0，x23＝0，x31＝0，x32＝20，x33＝20 最优值为 365。

即：生产雏鸡饲料 50 吨，不生产蛋鸡饲料，生产肉鸡饲料 40 吨。

7、设 Xi——第 i 个月生产的产品 I 数量

Yi——第 i 个月生产的产品 II 数量

Zi，Wi 分别为第 i 个月末产品 I、II 库存数

。则S1i，S2i 分别为用于第（i+1）个月库存的自有及租借的仓库容积（立方米）

可建立如下模型：

12

min z = ∑(5 xi + 8 y i)+ ∑(4.5 xi + 7 y i)+ ∑ i =1 i =6 i =1(s1i + 1.5s 2i)5s.t.X1-10000=Z1 X2+Z1-10000=Z2 X3+Z2-10000=Z3 X4+Z3-10000=Z4 X5+Z4-30000=Z5 X6+Z5-30000=Z6 X7+Z6-30000=Z7 X8+Z7-30000=Z8 X9+Z8-30000=Z9 X10+Z9-100000=Z10 X11+Z10-100000=Z11 X12+Z11-100000=Z12 Y1-50000=W1 Y2+W1-50000=W2 Y3+W2-15000=W3 Y4+W3-15000=W4 Y5+W4-15000=W5 Y6+W5-15000=W6 Y7+W6-15000=W7 Y8+W7-15000=W8 Y9+W8-15000=W9 Y10+W9-50000=W10 Y11+W10-50000=W11 Y12+W11-50000=W12 S1i≤15000 1≤i≤12 Xi+Yi≤120000 1≤i≤12

0.2Zi+0.4Wi=S1i+S2i 1≤i≤12

Xi≥0, Yi≥0, Zi≥0, Wi≥0, S1i≥0, S2i≥0 用管理运筹学软件我们可以求得此问题的解为： 最优值= 4910500

X1=10000, X2=10000, X3=10000, X4=10000, X5=30000, X6=30000, X7=30000, X8=45000, X9=105000, X10=70000, X11=70000, X12=70000;Y1= 50000, Y2=50000, Y3=15000, Y4=15000, Y5=15000, Y6=15000, Y7=15000, Y8=15000, Y9=15000, Y10=50000, Y11=50000, Y12=50000;Z8=15000, Z9=90000, Z10 =60000, Z1=30000;S18=3000, S19=15000, S110=12000, S111=6000;S28=3000;

其余变量都等于 0

8、解：设第 i 个车间生产第 j 种型号产品的数量为 xij，可建立下面的数学模型：

max z＝25（x11＋x21＋x31＋x41＋x51）＋20（x12＋x32＋x42＋x52）＋17（x1

3＋x23＋x43＋x53）＋11（x14＋x24＋x44）

s．t． x11＋x21＋x31＋x41＋x51 ≤ 1400 x12＋x32＋x42＋x52 ≥ 300 x12＋x32＋x42＋x52 ≤ 800 x13＋x23＋x43＋x53 ≤ 8000 x14＋x24＋x44 ≥ 700

5x11＋7x12＋6x13+5x14 ≤ 18000 6x21＋3x23＋3x24 ≤ 15000 4x31＋3x32 ≤ 14000

3x41＋2x42＋4x43＋2x44 ≤ 12000 2x51＋4x52＋5x53 ≤ 10000

xij ≥ 0，i＝1，2，3，4，5 j＝1，2，3，4用管理运筹学软件我们可以求得此问题的解为：

x11＝0，x12＝0，x13＝1000，x14＝2400，x21＝0，x23＝5000，x24＝0，x31＝1400，x32＝800，x41＝0，x42＝0，x43＝0，x44＝6000，x51＝0，x52＝0，x53＝2000

最优值为 279400

9、解：设第一个月正常生产 x1，加班生产 x2，库存 x3；第二个月正常生产 x4，加班生产 x5，库存 x6；第三个月正常生产 x7，加班生产 x8，库存 x9；第四个月正常生产 x10，加班生产 x11，可建立下面的数学模型：

min f ＝ 200（x1＋x4＋x7＋x10）＋300（x2＋x5＋x8＋x11）＋60（x3＋x6

＋x9）s．t．

x1≤4000 x4≤4000 x7≤4000 x10≤4000 x3≤1000 x6≤1000 x9≤1000 x2≤1000 x5≤1000 x8≤1000 x11≤1000

x1+ x2-x3=4500

x3+ x4+ x5-x6=3000 x6+ x7+ x8-x9=5500 x9+ x10+ x11=4500

x1，x2，x3，x4，x5，x6，x7，x8，x9，x10，x11≥0

计算结果是：

minf= 3710000 元

x1＝4000 吨，x2=500 吨，x3＝0 吨，x4=4000 吨，x5＝0 吨，x6＝1000 吨，x7＝4000 吨，x8＝500 吨，x9＝0 吨，x10＝4000 吨，x11＝500 吨。

第 5 章 单纯形法

1、解：表中 a、c、e、f 是可行解，a、b、f 是基本解，a、f 是基本可行解。

2、解：a、该线性规划的标准型为： max 5 x1＋9 x2

s．t．0.5 x1＋x2＋s1＝8

x1＋x2－s2＝10

0.25 x1＋0.5 x2－s3＝6

x1，x2，s1，s2，s3 ≥0.b、有两个变量的值取零，因为有三个基变量、两个非基变量，非基变量 取零。

（4，6，0，0，－2）c、（0，10，－2，0，－1）d、e、不是。因为基本可行解要求基变量的值全部非负。

3、解：a、迭代次数 基变量 s1 s2 s3 xj cj－xj

cB 0 0 0 0

x1 6 3 0 2 0 6 x2 30 1 2 [1] 0 30*

x3 25 0 1 － 25

x4 0 1 0 0 0 0 x5 0 0 1 0 0 0 x6 0 0 0 1 0 0

b 40 50 20 0

b、线性规划模型为：

max 6 x1＋30 x2＋25 x3 s．t．3 x1＋x2＋s1 = 40 2 x1＋x3＋s2= 50 2 x1＋x2－x3＋s3＝20

x1，x2，x3，s1，s2，s3 ≥0

，初始解为（0，0，0，40，50，20），c、初始解的基为（s1，s2，s3）

对应的目标函数值为 0。

d、第一次迭代时，入基变量是 x2，出基变量为 s3。

，最优值为 9。

4、解：最优解为（2.25，0）X2

X1

，最优值为 84。

5、解：a、最优解为（2，5，4），最优值为－4。b、最优解为（0，0，4）

6、解：a、有无界解

，最优值为－2.144。b、最优解为（0.714，2.143，0）

7、解：a、无可行解

，最优值为 28。b、最优解为（4，4）c、有无界解

，最优值为 8。d、最优解为（4，0，0）第6章

a． c1≤24 b． c2≥6 c． cs2≤8 2

a.c1≥-0.5 b.-2≤c3≤0 c.cs2≤0.5 3

a.b1≥150

b.0≤b2≤83.333 c.0≤b3≤150

单纯形法的灵敏度分析与对偶

a.b1≥-4 b.0≤b2≤300 c.b3≥4

a.利润变动范围 c1≤3，故当 c1=2 时最优解不变 b.根据材料的对偶价格为 1 判断，此做法不利 c.d.0≤b2≤45

e.最优解不变，故不需要修改生产计划

此时生产计划不需要修改，因为新的产品计算的检验数为-12 小于零，对原生 产计划没有影响。

均为唯一最优解，根据从计算机输出的结果看出，如果松弛或剩余变量为零且对 应的对偶价格也为零，或者存在取值为零的决策变量并且其相差值也为零时，可 知此线性规划有无穷多组解。7

a.min f= 10y1+20y2.s.t.y1+y2≥2,y1+5y2≥1,y1+y2≥1,y1, y2≥0.b.max z= 100 y1+200 y2.s.t.1/2 y1+4 y2≤4,y1+6 y2≤4, 2 y1+3 y2≤2, y1, y2≥0.8.a.min f=-10 y1+50 y2+20 y3-20 y4.s.t.-2 y1+3 y2+ y3-y2≥1，≥2,3 y1+ y2 y1-y2+ y3≤2,y1-2 y2-y3≤3,y1, y2, y3≥0 目标函数最优值为: 10

最优解: x1=6, x2=2, x3=0

第 7 章 运输问题

1.（1）此问题为产销平衡问题

甲乙 分厂2117 2 分厂1015 3 分厂2321 销量400250

丙 23 30 20 350 丁 25 19 22 200 产量 300 400 500 1200

最优解如下

******************************************** 起至 销点 发点12

------------------10250 24000 300

此运输问题的成本或收益为: 19800

3-----0 0 350 4-----50 0 150

此问题的另外的解如下：

起至 销点 发点12

------------------10250 24000 300

此运输问题的成本或收益为: 19800

3-----50 0 300 4-----0 0 200

（2）如果 2 分厂产量提高到 600，则为产销不平衡问题

最优解如下

******************************************** 起 发点

--------1 2 3 至 销点

----------0250 4000 00

3-----0 0 350 4-----0 200 0 此运输问题的成本或收益为: 注释：总供应量多出总需求量 第 1 个产地剩余 50 第 3 个产地剩余 150

19050 200

（3）销地甲的需求提高后，也变为产销不平衡问题

最优解如下

********************************************

起至 销点 发点12

------------------150250 24000 300

此运输问题的成本或收益为: 19600

3-----0 0 350 4-----0 0 150

注释：总需求量多出总供应量150 第 1 个销地未被满足，缺少 100 第 4 个销地未被满足，缺少 50

2． 本题运输模型如下：

ⅰⅱ 甲0.30.4 乙0.30.1 丙0.050.05 丁-0.20.3 300250

ⅲ 0.3-0.4 0.15 0.1 350

ⅳ 0.4 0.2 0.05-0.1 200 ⅴ 0.1-0.2-0.05-0.1 250 VI 0.9 0.6 0.55 0.1 150

300 500 400 100

最优解如下

********************************************

起 发点--------1 2 3 4 5 至 销点 1-----0 0 0 0 150 2-----0 0 50 100 0-----100 0 0 0 50-----0 0 100 0 0-----0 350 0 0 0-----200 0 0 0 0-----0 0 250 0 0-----0 150 0 0 0

此运输问题的成本或收益为: 1.050013E+07 3． 建立的运输模型如下：

123

1600600+60600+60

1’600+600 10% 600+600 10%+60 600+600 2700700+60

2’700+700 10%700+700 3650

3’650+650 356

最优解如下

********************************************起至 销点 发点1

-------------2 3

12----------21 0 0 30 1 1 40 0 0 50 4 0 60 0 0 70

0 2 0 此运输问题的成本或收益为:

8465

此问题的另外的解如下： 起至 销点 发点1

-------------2

12----------21 0 0 30 2 0 40 0 0 50 3 1 60 0 0 70

0 2 0

此运输问题的成本或收益为:

8465

10%+60 2 3 4 10%+602 2 10%3

4-----0 0 3 0 2 0 0

4-----0 0 3 0 2 0 0

4． 甲 乙 A B C D 甲 0 80 150 200 180 240 1100 乙 100 0 80 210 60 170 1100

A 150 80 0 70 110 90 1400

B 200 210 60 0 130 50 1300

C 180 60 110 140 0 85 1600

D 240 170 80 50 90 0 1200

1600 1700 1100 1100 1100 1100

最优解如下

********************************************

起 至 销点 发点 1 2 3 4 5 6--------------------------------------1 1100 0 300 200 0 0 2 0 1100 0 0 600 0 3 0 0 1100 0 0 0 4 0 0 0 1100 0 0 5 0 0 0 0 1000 100 6 0 0 0

0

0

1100

此运输问题的成本或收益为: 130000

5．建立的运输模型如下

min f = 500x1+300 x2+550 x3+650 x4.s.t.54 x1+49 x2+52 x3+64 x4≤1100,57 x1+73 x2+69 x3+65 x4≤1000,x1, x2, x3, x4≥0.A5449 B5773 3 4 500300 52 64 69

550

650

最优解如下

********************************************

起

至 销点

发点

------------------3 4 1 250300----------2 2500

550 0 0 650 1100 1000

5-----0 100 此运输问题的成本或收益为: 113300

6.a.最小元素法的初始解如下：

甲 8 7

乙

丙

0 0

销量 20

0 10 0

b.最优解如下

******************************************** 起至 销点

发点1

-------------2 3 10----------220 0 15 30

0 此运输问题的成本或收益为:

5

145

c.该运输问题只有一个最优解，因为其检验数均不为零

最优解如下d.******************************************** 起至 销点

发点12

------------------3 100-----2250 0

此运输问题的成本或收益为: 135 5

0 5

0

产量 0 15 5 0

0

第 8 章 整数规划

1． 求解下列整数规划问题

a.max z=5x1 +8x 2

s.t.x1 +x 2 ≤ 6, 5x1 +9x 2 ≤ 45, x1 ,x 2 ≥ 0,且为整数

目标函数最优解为 : x1*=0,x 2 *=5,z*=40。

b.max z=3x1 +2x 2

s.t.2x1 +3x 2 ≤ 14, 2x1 +x 2 ≤ 9，x1,x2 ≥ 0,且x1为整数。

目标函数最优解为 : x1*=3,x 2 *=2.6667,z*=14.3334。

c.max z=7x1 +9x 2 +3x 3

s.t.-x1 +3x 2 +x 3 ≤ 7, 7x1 +x 2 +x 3 ≤ 38，x1 ,x 2 ,x 3 ≥ 0,且x1为整数，x 3为0-1变量。

目标函数最优解为 : x1*=5,x 2 *=3,x 3 *=0,z*=62。

2．解：设 xi 为装到船上的第 i 种货物的件数，i=1,2,3,4,5。则该船装载的货 物取得最大价值目标函数的数学模型可写为：

max z=5x1 +10x 2 +15x 3 +18x 4 +25x 5 s.t.20x1 +5x 2 +10x 3 +12x 4 +25x 5 ≤ 400000, x1 +2x 2 +3x 3 +4x 4 +5x 5 ≤ 50000, x1 +4x 4 ≤ 10000

0.1x1 +0.2x 2 +0.4x 3 +0.1x 4 +0.2x 5 ≤ 750, x i ≥ 0, 且为整数，i=1，。2345

目标函数最优解为

: x1*=0,x 2 *=0,x 3 *=0,x 4 *=2500,x

*=2500,z*=107500.3．解：设 xi 为第 i 项工程，i=1,2,3,4,5,且 xi 为 0-1 变量，并规定，⎧1, 当第i项工程被选定时，xi = ⎨

⎩0，当第i项工程没被选定时。

根据给定条件，使三年后总收入最大的目标函数的数学模型为： max z = 20x1 + 40x 2 + 20x 3 + 15x 4 + 30x 5

s.t.5x1 +4x 2 +3x 3 +7x 4 +8x 5 ≤ 25，x1 +7x 2 +9x 3 +4x 4 +6x 5 ≤ 25，8x1 +10x 2 +2x 3 +x 4 +10x 5 ≤ 25，x i为0-1变量，i=1，。2345

目标函数最优解为

: x1*=1,x

*=0,z*=95

*=1,x

*=1,x

*=1,x 4．解：这是一个混合整数规划问题

设 x1、x2、x3 分别为利用 A、B、C 设备生产的产品的件数，生产准备费

只有在利用该设备时才投入，为了说明固定费用的性质，设

⎧1，当利用第i种设备生产时，即x i >0, yi = ⎨

⎩0，当不利用第i种设备生产时，即x i =0。故其目标函数为：

min z = 100y1 +300y 2 +200y3 +7x1 +2x 2 +5x 3

为了避免没有投入生产准备费就使用该设备生产，必须加以下的约束条件，M 为充分大的数。

x1 ≤ y1M，x 2 ≤ y 2 M，x 3 ≤ y3 M，设 M=1000000

a.该目标函数的数学模型为： min z=100y1 +300y 2 +200y3 +7x1 +2x 2 +5x 3 s.t.x1 +x 2 +x 3 =2000，0.5x1 +1.8x 2 +1.0x 3 ≤ 2000，x1 ≤ 800，x 2 ≤ 1200，x 3 ≤ 1400，x1 ≤ y1M，x 2 ≤ y 2 M，x 3 ≤ y3M，x1，x 2，x 3 ≥ 0，且为整数，y1，y 2，y3为0-1变量。

目标函数最优解为

: x1*=370,x 2

*=231,x

*=1399,y1 =1,y

=1,z*=10647

b.该目标函数的数学模型为：

min z=100y1 +300y 2 +200y3 +7x1 +2x 2 +5x 3 s.t.x1 +x 2 +x 3 =2000，0.5x1 +1.8x 2 +1.0x 3 ≤ 2500，x1 ≤ 800，x 2 ≤ 1200，x 3 ≤ 1400，x1 ≤ y1M，x 2 ≤ y 2 M，x 3 ≤ y3M，x1，x 2，x 3 ≥ 0，且为整数，y1，y 2，y3为0-1变量。目标函数最优解为

: x1*=0,x 2 *=625,x

*=1375,y1 =0,y

=1,z*=8625

=1,y3

=1,y3 c.该目标函数的数学模型为：

min z=100y1 +300y 2 +200y3 +7x1 +2x 2 +5x 3 s.t.x1 +x 2 +x 3 =2000，0.5x1 +1.8x 2 +1.0x 3 ≤ 2800，x1 ≤ 800，x 2 ≤ 1200，x 3 ≤ 1400，x1 ≤ y1M，x 2 ≤ y 2 M，x 3 ≤ y3M，x1，x 2，x 3 ≥ 0，且为整数，y1，y 2，y3为0-1变量。目标函数最优解为

: x1*=0,x =1,z*=7500

*=1000,x

*=1000,y1 =0,y

=1,y3 d.该目标函数的数学模型为：

min z=100y1 +300y 2 +200y3 +7x1 +2x 2 +5x 3 s.t.x1 +x 2 +x 3 =2000，x1 ≤ 800，x 2 ≤ 1200，x 3 ≤ 1400，x1 ≤ y1M，x 2 ≤ y 2 M，x 3 ≤ y3M，x1，x 2，x 3 ≥ 0，且为整数，y1，y 2，y3为0-1变量。

目标函数最优解为 : x1*=0,x 2 *=1200,x 3 *=800,y1 =0,y 2 =1,y3 =1,z*=6900 5．解：设 xij 为从 Di 地运往 Ri 地的运输量，i=1，2，3，4，j=1，2，3 分别 代表从北京、上海、广州、武汉运往华北、华中、华南的货物件数，并规定，⎧1，当i地被选设库房，yi = ⎨

⎩0，当i地没被选设库房。该目标函数的数学模型为： min z = 45000y1 + 50000y 2 + 70000y3 + 40000y 4 + 200x11 + 400x12 + 500x13 +300x 21 + 250x 22 +400x 23 +600x 31 +350x 32 +300x 33 +350x 41 +150x 42 +350x 43 s.t.x11 +x 21 +x 31 +x 41 =500，x12 +x 22 +x 32 +x 42 =800，x13 +x 23 +x 33 +x 43 =700，x11 +x12 +x13 ≤ 1000y1，x 21 +x 22 +x 23 ≤ 1000y 2，x 31 +x 32 +x 33 ≤ 1000y3，x 41 +x 42 +x 43 ≤ 1000y 4，y2 ≤ y4，y1 +y 2 +y3 +y 4 ≤ 2，y3 +y 4 ≤ 1，x ij ≥ 0，且为整数，yi为0-1分量，i=1，。234 目标函数最优解为

x11*=500,x12 *=0,x13 *=500,x 21*=0,x 22 *=0,x 23 *=0,x 31*=0,x 32 *=0,x

: 33 *=0，x 41*=0,x 42 *=800,x 43 *=200,y1 =1,y 2 =0,y3 =0,y 4 =1,z*=625000

也就是说在北京和武汉建库房，北京向华北和华南各发货 500 件，武汉向华 中发货 800 件，向华南发货 200 件就能满足要求，即这就是最优解。

⎧1，当指派第i人去完成第j项工作时，6．解：引入 0-1 变量 xij，并令 x ij = ⎨

⎩0，当不指派第i人去完成第j项工作时。a.为使总消耗时间最少的目标函数的数学模型为：

min z = 20x11 + 19x12 + 20x13 + 28x14 + 18x 21 + 24x 22 + 27x 23 + 20x 24 +26x 31

+16x 32 +15x 33 +18x 34 +17x 41 +20x 42 +24x 43 +19x 44 s.t.x11 +x12 +x13 +x14 =1，x 21 +x 22 +x 23 +x 24 =1，x 31 +x 32 +x 33 +x 34 =1，x 41 +x 42 +x 43 +x 44 =1，x11 +x 21 +x 31 +x 41 =1，x12 +x 22 +x 32 +x 42 =1，x13 +x 23 +x 33 +x 43 =1，x14 +x 24 +x 34 +x 44 =1，x ij为0-1变量，i=1，，j=1，。234234 目标函数最优解为 :

x11*=0,x12 *=1,x13 *=0,x14 *=0,x 21*=1,x 22 *=0,x 23 *=0,x 24 *=0,x 31*=0,x 32 *=0,x 33 *=1，x 34 *=0,x 41*=0,x 42 *=0,x 43 *=0,x 44 *=1,z*=71

或

x11*=0,x12 *=1,x13 *=0,x14 *=0,x 21*=0,x 22 *=0,x 23 *=0,x 24 *=1,x 31*=0,x 32 *=0,x 33 *=1，x 34 *=0,x 41*=1,x 42 *=0,x 43 *=0,x 44 *=0,z*=71

即安排甲做 B 项工作，乙做 A 项工作，丙 C 项工作，丁 D 项工作，或者是 安排甲做 B 项工作，乙做 D 项工作，丙 C 项工作，丁 A 项工作，最少时间为 71 分钟。

b.为使总收益最大的目标函数的数学模型为： 将 a 中的目标函数改为求最大值即可。目标函数最优解为

:

x11*=0,x12 *=0,x13 *=0,x14 *=1,x 21*=0,x 22 *=1,x 23 *=0,x 24 *=0,x 31*=1,x 32 *=0,x 33 *=0，x 34 *=0,x 41*=0,x 42 *=0,x 43 *=1,x 44 *=0,z*=102

即安排甲做 D 项工作，乙做 C 项工作，丙 A 项工作，丁 B 项工作，最大收 益为 102。

c.由于工作多人少，我们假设有一个工人戊，他做各项工作的所需的时间均 为 0，该问题就变为安排 5 个人去做 5 项不同的工作的问题了，其目标函数的数 学模型为： min z = 20x11 + 19x12 + 20x13 + 28x14 + 17x15 + 18x 21 + 24x 22 + 27x 23 + 20x 24 +20x 25

+26x 31 +16x 32 +15x 33 +18x 34 +15x 35 +17x 41 +20x 42 +24x 43 +19x 44 +16x 45 s.t.x11 +x12 +x13 +x14 +x15 =1，x 21 +x 22 +x 23 +x 24 +x 25 =1，x 31 +x 32 +x 33 +x 34 +x 35 =1，x 41 +x 42 +x 43 +x 44 +x 45 =1，x 51 +x 52 +x 53 +x 54 +x 55 =1，x11 +x 21 +x 31 +x 41 +x 51 =1，x12 +x 22 +x 32 +x 42 +x 52 =1，x13 +x 23 +x 33 +x 43 +x 53 =1，x14 +x 24 +x 34 +x 44 +x 54 =1，x15 +x 25 +x 35 +x 45 +x 55 =1，x ij为0-1变量，i=1，，，j=1，。23452345

目标函数最优解为:

x11*=0,x12 *=1,x13 *=0,x14 *=0,x15 *=0,x 21*=1,x 22 *=0,x 23 *=0,x 24 *=0,x 25 *=0,x 31*=0，x 32 *=0,x 33 *=1,x 34 *=0,x 35 *=0,x 41*=0,x 42 *=0,x 43 *=0,x 44 *=0,x 45 *=1,z*=68

即安排甲做 B 项工作，乙做 A 项工作，丙做 C 项工作，丁做 E 项工作，最 少时间为 68 分钟。

d.该问题为人多任务少的问题，其目标函数的数学模型为： min z = 20x11 + 19x12 + 20x13 + 28x14 + 18x 21 + 24x 22 + 27x 23 + 20x 24 +26x 31 +16x 32

+15x 33 +18x 34 +17x 41 +20x 42 +24x 43 +19x 44 +16x 51 +17x 52 +20x 53 +21x 54

s.t.x11 +x12 +x13 +x14 ≤ 1，x 21 +x 22 +x 23 +x 24 ≤ 1，x 31 +x 32 +x 33 +x 34 ≤ 1，x 41 +x 42 +x 43 +x 44 ≤ 1，x 51 +x 52 +x 53 +x 54 ≤ 1，x11 +x 21 +x 31 +x 41 +x 51 =1，x12 +x 22 +x 32 +x 42 +x 52 =1，x13 +x 23 +x 33 +x 43 +x 53 =1，x14 +x 24 +x 34 +x 44 +x 54 =1，2345x ij为0-1变量，i=1，，j=1，。234

目标函数最优解为:

x11*=0,x12 *=0,x13 *=0,x14 *=0,x 21*=0,x 22 *=0,x 23 *=0,x 24 *=1,x 31*=0,x 32 *=0,x 33 *=1，x 34 *=0,x 41*=1,x 42 *=0,x 43 *=0,x 44 *=0,x 51*=0,x 52 *=1,x 53 *=0,x 54 *=0,z*=69 或

x11*=0,x12 *=0,x13 *=0,x14 *=0,x 21*=1,x 22 *=0,x 23 *=0,x 24 *=0,x 31*=0,x 32 *=0,x 33 *=1，x 34 *=0,x 41*=0,x 42 *=0,x 43 *=0,x 44 *=1,x 51*=0,x 52 *=1,x 53 *=0,x 54 *=0,z*=69 或

x11*=0,x12 *=1,x13 *=0,x14 *=0,x 21*=0,x 22 *=0,x 23 *=0,x 24 *=0,x 31*=0,x 32 *=0,x 33 *=1, x 34 *=0,x 41*=0,x 42 *=0,x 43 *=0,x 44 *=1,x 51*=1,x 52 *=0,x 53 *=0,x 54 *=0,z*=69

即安排乙做 D 项工作，丙做 C 项工作，丁做 A 项工作，戊做 B 项工作；或 安排乙做 A 项工作，丙做 C 项工作，丁做 D 项工作，戊做 B 项工作；或安排甲 做 B 项工作，丙做 C 项工作，丁做 D 项工作，戊做 A 项工作，最少时间为 69 分钟。

7.解：设飞机停留一小时的损失为 a 元，则停留两小时损失为 4a 元，停留 3 小时损失为 9 元，依次类推，对 A、B、C 三个城市建立的指派问题的效率矩阵 分别如下表所示：

城市

起 到

达 飞

A

4a 361a 225a 484a 196a

9a 400a 256a 529a 225a

64a 625a 441a 16a 400a

169a 36a 4a 81a 625a

225a 64a 16a 121a 9a 106 107 108 109 110 解得最优解为：

起 到

达 飞

0 0 0 0 1

1 0 0 0 0

0 0 0 1 0

0 1 0 0 0

0 0 1 0 0 106 107 108 109 110

城市

起 到

达 飞

B

256a 225a 100a 64a 256a

529a 484a 289a 225a 529a

9a 4a 441a 361a 9a

625a 576a 361a 289a 625a

36a 25a 576a 484a 36a 101 102 103 113 114 解得最优解为：

起 到

达 飞

0 1 0 0 0

0 0 1 0 0

1 0 0 0 0

0 0 0 1 0

0 0 0 0 1 106 107 108 109 110 或为：

起 到

达 飞

0 1 0 0 0

0 0 1 0 0

0 0 0 0 1

0 0 0 1 0

1 0 0 0 0 106 107 108 109 110

城市 C

起 到

达 飞

49a 25a 169a 64a

225a 169a 441a 256a

225a 169a 441a 256a

49a 25a 169a 64a 104 105 111 112 解得最优解为：

起 到

达 飞

0 0 1 0

1 0 0 0

0 1 0 0

0 0 0 1 104 105 111 112 或为：

起 到

达 飞

0 0 1 0

0 1 0 0

1 0 0 0

0 0 0 1 104 105 111 112 或为:

起 到

达 飞

0 0 0 1

1 0 0 0

0 1 0 0

0 0 1 0 104 105 111 112 或为：

起 到

达 飞

0 0 0 1

0 1 0 0

1 0 0 0

0 0 1 0 104 105 111 112

第 9 章 目标规划

1.某工厂试对产品 A、B 进行生产。市场需求并不是很稳定，因此对每种产

品分别预测了在销售良好和销售较差时的预期利润。这两种产品都经过甲、乙两 台设备加工。已知产品 A 和 B 分别在甲和乙设备上的单位加工时间，甲、乙设备 的可用加工时间以及预期利润如下表所示，要求首先是保证在销售较差时，预期 利润不少于 5 千元，其次是要求销售良好时，预期利润尽量达到 1 万元。试建立 多目标规划模型并求解。

单位加工时间 设备

产品

A 4 2 8 5

B 3 5 6 5

可用时间 45 30 100 50 甲

乙

销售良好时的预期利润(百元／件)

销售较差时的预期利润(百元／件)

1、解：设工厂生产 A 产品 x1 件，生产 B 产品 x2 件。按照生产要求，建立如下目 标规划模型： min −P(d1−)+ P2(d 2)1

⎧4 x1 + 3 x2 ≤ 45 ⎪

⎪2 x1 + 5 x2 ≤ 30

⎪+−⎨5 x1 + 5 x2 − d1 + d1 = 50 ⎪+8 x1 + 6 x2 − d 2 + d 2− = 100 ⎪

⎪ x1 , x2 , di+ , di− ≥ 0, i = 1, 2⎩

由管理运筹学软件先求解得： x1 = 11.25, x2 = 0, d1− = 0, d 2− = 10, d1+ = 6.25, d 2 = 0

由图解法或进一步计算可知，本题在求解结果未要求整数解的情况下，满意解有 +无穷多个，为线段 α(135 /14,15 / 7)+(1 − α)(45 / 4, 0), α ∈ [0,1] 上的任一点。

2、解：设食品厂商在电视上发布广告 x1 次，在报纸上发布广告 x2 次，在广播中 发布广告 x3 次。目标规划模型为：

P(d1−)+ P2(d 2−)+ P3(d3+)+ P4(d 4)1 ⎧ x1 ≤ 10 ⎪ x ≤ 20 ⎪2

⎪ x3 ≤ 15 ⎪

+−⎪20 x1 + 10 x2 + 5 x3 − d1 + d1 = 400 ⎪

⎨+−⎪0.7 x1 − 0.3x2 − 0.3x3 − d 2 + d 2 = 0

⎪−0.3x − 0.3x + 0.7 x − d + + d − = 012333⎪

⎪2.5 x1 + 0.5 x2 + 0.3x3 − d 4+ + d 4− = 20

用管理运筹学软件先求下述问题：⎪+−⎪ x1 , x2 , x3 , di , d i ≥ 0, i = 1, 2,3, 4⎩ min d1− min +⎧ x1 ≤ 10

⎪ x ≤ 20 ⎪2

⎪ x3 ≤ 15 ⎪

+−⎪20 x1 + 10 x2 + 5 x3 − d1 + d1 = 400 ⎪

⎨−0.7 x1 − 0.3x2 − 0.3x3 − d 2+ + d 2 = 0 ⎪

⎪−0.3x − 0.3x + 0.7 x − d + + d − = 012333⎪

⎪2.5 x1 + 0.5 x2 + 0.3x3 − d 4+ + d 4−

，将其作为约束条件求解下述问题： 得： = 20d1− = 0 ⎪+−⎪ x1 , x2 , x3 , di , di ≥ 0, i = 1, 2,3, 4⎩ min d 2− ⎧ x1 ≤ 10

⎪

⎪ x2 ≤ 20 ⎪ x ≤ 15 ⎪3

⎪20 x1 + 10 x2 + 5 x3 − d1+ + d1− = 400 ⎪

+−⎨0.7 x1 − 0.3x2 − 0.3x3 − d 2 + d 2 = 0 ⎪

−0.3x1 − 0.3x2 + 0.7 x3 − d3+ + d3− = 0 ⎪

⎪2.5 x + 0.5 x + 0.3x − d + + d − = 2012344⎪ ⎪d1− = 0

−得最优值 d 2 = 0，将其作为约束条件计算下述问题： ⎪+−⎩ x1 , x2 , x3 , di , di ≥ 0, i = 1, 2,3, 4 min d3+

⎧ x1 ≤ 10 ⎪ x ≤ 20 ⎪2

⎪ x3 ≤ 15 ⎪

+−⎪20 x1 + 10 x2 + 5 x3 − d1 + d1 = 400

⎪+−⎪0.7 x1 − 0.3x2 − 0.3x3 − d 2 + d 2 = 0 ⎨

−0.3x1 − 0.3x2 + 0.7 x3 − d3+ + d3− = 0 ⎪

⎪2.5 x + 0.5 x + 0.3x − d + + d − = 2012344 ⎪

⎪d1− = 0 ⎪− ⎪d 2 = 0，将其作为约束条件计算下述问题： 得最优值d3+ = 0 ⎪ x , x , x , d + , d − ≥ 0, i = 1, 2,3, 4 min d 4+ ⎩1 2 3 i i

⎧ x1 ≤ 10

⎪

⎪ x2 ≤ 20 ⎪ x ≤ 15 ⎪3

⎪20 x1 + 10 x2 + 5 x3 − d1+ + d1− = 400 ⎪

+−⎪0.7 x1 − 0.3 x2 − 0.3 x3 − d 2 + d 2 = 0

⎪+−⎨−0.3x1 − 0.3 x2 + 0.7 x3 − d3 + d3 = 0 ⎪

2.5 x1 + 0.5 x2 + 0.3 x3 − d 4+ + d 4− = 20 ⎪

⎪d − = 0 ⎪ 1−

⎪d 2 = 0 得： ⎪+

⎪d3 = 0

+−x1 = 9.474, x2 = 20, x3 = 2.105, d1+ = 0, ⎪ x , x , x , d + , d − ≥ 0, i = 1, d1− = 0, d 2 = 8.387, d 2 = 0, d3+ = 0, d3− = 7.368，2,3, 4− d 4+ = 14.316, ⎩1 2 3 i id 4 = 0，所以食品厂商为了依次达到 4 个活动目标，需在电视上发布广告 9.474 次，报纸

（管理运筹学 2.0 可一次求解上述上发布广告 20 次，广播中发布广告 2.105 次。问题）

（a）设该化工厂生产 x1 升粘合剂 A 和 x2 升粘合剂 B。则根据工厂要求，3、解： 建立以下目标规划模型：

P(d1− + d 2+)+ P2(d3− + d 4)+ P3(d5−)1 5⎧1

x1 + x2 − d1+ + d1− = 80 ⎪312 ⎪

⎪ 1 x + 5 x − d + + d − = 10022 ⎪ 3 1 12 2 ⎪

⎨ x1 − d3+ + d3− = 100 ⎪

+−⎪ x2 − d 4 + d 4 = 120 ⎪−+⎪ x1 + x2 − d5 + d 5 = 300

⎪ x , x , x , d + , d − ≥ 0, i = 1, 2,3, 4,5（b）⎩ 1 2 3 i i min −300 d5 +

d4

200

d3

+

A

d1

+

d

2d3 d2

+

d

图1 200

图解法求解

300

图解法求解如图 1：目标 1，2 可以达到，目标 3 达不到，所以有满意解为 A 点

。（150，120）

4、解：设该汽车装配厂为达到目标要求生产产品 A x1 件，生产产品 B x2 件。

min

+

P(d1+ + d 2)+ P2

（a）目标规划模型为：

(d3−)1

1⎧1

x1 + x2 − d1+ + d1− = 60 ⎪66 ⎪

⎪ 1 x + 5 x − d + + d − = 18022 ⎨3 1 6 2 ⎪

+−⎪4 x1 + 3 x2 − d3 + d3 = 1300

⎪+−⎩ x1 , x2 , x3 , di , di ≥ 0, i = 1, 2,3 用图解法求解：

500 400 300 200 100 0 d d2-+2d1-d1+

d3+

B

d3-

A

DC

200

300

400

500

600

如图所示，所示解为区域 ABCD，有无穷多解。

（b）由上图可知，如果不考虑目标 1 和目标 2，仅仅把它们加工时间的最大限 度分别为 60 和 180 小时作为约束条件，而以利润最大化为目标，那么最优解为 C 点（360，0），即生产产品 A360 件，最大利润为 1420 元。结果与（a）是不相 同的，原因是追求利润最大化而不仅仅是要求利润不少于 1300 元。

（c）如果设目标 3 的优先权为 P1，目标 1 和目标 2 的优先权为 P2，则由上图可 知，满意解的区域依然是 ABCD，有无穷多解，与（a）的解是相同的，原因是（a）和（c）所设定的目标只是优先级别不同，但都能够依次达到。

5．在环境污染日益得到重视的今天，越来越多的企业开始注重工业废水污

水排污。某纸张制造厂生产一般类型纸张的利润为 300 元／吨，每吨纸产生的工 业废水的处理费用为 30 元；生产某种特种纸张的利润为 500 元／吨，每吨特种 纸产生的工业废水的处理费用为 40 元。

该纸张制造厂近期目标如下：

目标 1：纸张利润不少于 15 万；

目标 2：工业废水的处理费用不超过 1 万元。

a.设目标 1 的优先权为 P1，目标 2 的优先权为 P2，P1>P2，建立目标规划模型 并用图解法求解。

b.若目标 2 的优先权为 P1，目标 1 的优先权为 P2，建立目标规划模型并求解。所得的解是否与 a 中的解相同？

c.若目标 2 的罚数权重为 5，目标 1 的罚数权重为 2，建立加权目标规划模 型求解。

5、解：设该纸张制造厂需要生产一般类型纸张 x1 吨，生产特种纸张 x2 吨。（a）、目标规划模型为： + P2(d 2)1

⎧300 x1 + 500 x2 − d1+ + d1− = 150000 ⎪

+−⎨30 x1 + 40 x2 − d 2 + d 2 = 10000 ⎪

x1 , x2 , di+ , di− ≥ 0, i = 1, 2 ⎩ −+图解法略，求解得 x1 = 0, x2 = 300, d1− = 0, d 2 = 0, d1+ = 0, d 2 = 200(b)、目标规划模型为： min P(d 2+)+ P2(d1−)1

⎧300 x1 + 500 x2 − d1+ + d1− = 150000 ⎪

+−⎨30 x1 + 40 x2 − d 2 + d 2 = 10000

⎪+−⎩ x1 , x2 , di , di ≥ 0, i = 1, 2

图解法略，求解得 x1 = 0, x2 = 250, d1− = 250, d 2 = 0, d1+ = 0, d 2 = 0

由此可见，所得结果与(a)中的解是不相同的。(c)、加权目标规划模型为： −+min +P(d1−)P(5d 2 + 2d1−)1

⎧300 x1 + 500 x2 − d1+ + d1− = 150000 ⎪

+−⎨30 x1 + 40 x2 − d 2 + d 2 = 10000 ⎪

x1 , x2 , di+ , di− ≥ 0, i = 1, 2 ⎩

−+求解得 x1 = 0, x2 = 300, d1− = 250, d 2 = 0, d1+ = 0, d 2 = 12000 min +

第 10 章 动态规划

1、最优解：A―B2―C1―D1―E；A―B3―C1―D1―E；A―B3―C2―D2―E

最优值：13

2、最优解：项目 A：300 万元、项目 B：0 万元、项目 C：100 万元、最优值：Z=71+49+70=190 万元

3、设每个月的产量是 Xi 百台（i=1、2、3、4）

最优解：X1=

4、X2＝0、X3＝

4、X4＝3

即第一个月生产 4 台，第一个月生产 0 台，第一个月生产 4 台，第一个月生 产 3 台。

最优值：Z=252000 元

4、最优解：运送第一种产品 5 件

最优值：Z=500 元

5．最大利润 2790 万元。最优安排如下表：

年初完好设备高负荷工作设备低负荷工作设备

数数

11250125 21000100 380080 464640 532320

6．最优解（0，200，300，100）或（200，100，200，100）或者（100，100，300，100）或（200，200，0，200）。总利润最大增长额为 134 万。

7．在区 1 建 3 个分店，在区 2 建 2 个分店，不在区 3 建立分店。最大总利润 22。8．最优解为：第一年继续使用，第二年继续使用，第三年更新，第四年继续使 用，第五年继续使用，总成本＝4500 元。

9．最优解为第一年购买的设备到第二、三、四年初各更新一组，用到第 5 年末，其总收入为 17 万元。

10．最优解为第一批投产 3 台，如果无合格品，第二批再投产 3 台，如果仍全部 不合格，第三批投产 4 台。总研制费用最小为 796 元。11．

月份采购量待销数量

10200 29000 3900900 40900

最大利润为 14000。12．

最优策略为（1,2,3）或者（2,1,3），即该厂应订购 6 套设备，可分别分给三个厂 1,2,3 套或者 2,1,3 套。每年利润最大为 18 万元。

第 11 章 图与网络模型

习题 1

解：这是一个最短路问题，要求我们求出从 v1 到 v 7 配送的最短距离。用 Dijkstra 算法求解可得到这问题的解为 27。我们也可以用此书附带的管理运筹学 软件进行计算而得出最终结果为：

从节点 1 到节点 7 的最短路

************************* 起点终点距离

------------124 2312 356 575

此问题的解为:27

即：配送路线为： v1 → v 2 → v3 → v5 → v7

习题 2

解：这是一个最短路的问题，用 Dijkstra 算法求解可得到这问题的解为 4.8，即在 4 年内购买、更换及运行维修最小的总费用为：4.8 万元。

最优更新策略为：第一年末不更新

第二年末更新

第三年末不更新

第四年末处理机器

我们也可以用此书附带的管理运筹学软件进行求解，结果也可以得出此问题 的解为 4.8。

习题 3

解：此题是一个求解最小生成树的问题，根据题意可知它要求出连接 v1 到 v8 的最小生成树。解此题可以得出结果为 18。也可以使用管理运筹学软件，得出 如下结果：

此问题的最小生成树如下：

*************************

起点终点距离

------------132 342 124 252 573 78 76

此问题的解为:18 3

习题 4

解：此题是一个求解最大流的问题，根据题意可知它要求出连接 v1 到 v6 的最 大流量。解此题可以得出最大流量为 22。使用管理运筹学软件，我们也可以得 出结果为：

v1 从节点 1 到节点 6 的最大流

*************************

起点终点距离

------------126 146 1310 240 256 345 365 455 466 5611

此问题的解为:22

即从 v1 到 v6 的最大流量为：22

习题 5

解：此题是一个求解最小费用最大流的问题，根据题意可知它要求出连接 v1 到 v6 的最小费用最大流量。解此问题可以得出最大流为 5，最小费用为 39。使用 管理运筹学软件，我们也可以得出结果如下： 从节点 1 到节点 6 的最大流 ************************* 起点终点流量费用

----------------1213 1341 2424 3211 3533 4624 5 6 3 2

此问题的最大流为:5 此问题的最小费用为:39

第 12 章 排序与统筹方法

习题 1

p1 + 5 p2 + 4 p3 + 3 p4 + 2 p5 + p1 解：各零件的平均停留时间为：6

由此公式可知，要让停留的平均时间最短，应该让加工时间越少的零件 排在越前面，加工时间越多的零件排在后面。所以，此题的加工顺序为：3，7，6，4，1，2，5

习题 2

解：此题为两台机器，n 个零件模型，这种模型加工思路为：钻床上加工时 间越短的零件越早加工，同时把在磨床上加工时间越短的零件越晚加工。根据以上思路，则加工顺序为：2，3，7，5，1，6，4。

钻床 2 1

磨床 3 1 64 8 12 16 20 24 28 32 36 40

钻床的停工时间是：40.1。磨床的停工时间是：42.6。习题 3

解：a.工序 j 在绘制上有错，应该加一个虚拟工序来避免 v3 和 v4 有两个直接 相连的工序。

b.工序中出现了缺口，应在 v6 和 v7 之间加一个虚拟工序避免缺口。c.工序 v1、v2、v3 和 v4 之间存在了闭合回路。

习题 4 解：

v3

a

d

c

v4

f

v1

b

e

v5

v2

g

v6

习题 5

解：这是一个已知工序时间的关键路径问题，由管理运筹学软件可得出如下 结果：

工序安排

工序 最早开始时间

最迟开始时间

最早完成时间

最迟完成时间

时差

是否关键工序

-A 0 0 2 2 2---B C D E F G 0 4 4 4 9 8

0 5 4 5 10 8 9 8 7 11 12 10 8 8 12 12

0 1 0 1 1 0

YES---YES------YES

本问题关键路径是：B--D--G 本工程完成时间是：12

习题 6

解：这是一个不确定工序时间的关键路径问题，由管理运筹学软件可得出如 下结果：

工序期望时间方差----------------A2.08.07 B4.17.26 C4.92.18 D4.08.18 E3.08.07 F2.17.26 G3.83.26

工序安排

工序 最早开始时间

最迟开始时间

最早完成时间

最迟完成时间 时差

是否关键工序--------------------A 0 0 2.08 2.08 2.08 B C D E F G 0 4.17 4.17 4.17 9.08 8.25

0 5 4.17 5.17 9.92 8.25

4.17 9.08 8.25 7.25 11.25 12.08

4.17 9.92 8.25 8.25 12.08 12.08

0.83 0 1.83 0

---YES---YES------YES

本问题关键路径是：B--D--G 本工程完成时间是：12.08

这个正态分布的均值 E(T)=12.08 2 2 其方差为： σ 2 ＝ σ b ＋ σ d ＋ σ g ＝０.70 则σ ＝０.84

当以９８％的概率来保证工作如期完成时，即： φ(u)= 0.98，所以 u=2.05 此时提前开始工作的时间Ｔ满足： 所以Ｔ＝13.8 ≈ 14

习题 7

解：最短的施工工时仍为４＋５＋６＝１５

具体的施工措施如下：

工序 最早开始时间 最迟开始时间

最早完成时间

最迟完成时间

时差

是否关键工序

--------------------A 0 0 1 1 B C D E F G H I J K 0 7 0 1 3 3 4 10 7 9

0 7 0 2 3 6 4 10 9 9 10 4 3 7 6 9 15 13 15 10 4 4 7 9 9 15 15 15

T − 12.08

=2.05 0.84

0 0 0 0 1 0 3 0 0 2 0

---------YES------YES------YES

本问题关键路径是：D--H--K 本工程最短完成时间是：15

经过这样调整后，任意一时间所需要的人力数都不超过 15 人。习题 8

解：此题的网络图如下： v1 a

v2

c

b

v4

d

v3

设第 Vi 发生的时间为 xi，(Vi, Vj)间的工序提前完工的时间为 yij，目标函数 min f = 4.5(x4 − x1)+ 4 y12 + y24 + 4 y23 + 2 y34

s.t.x2 − x1 ≥ 3 − y12

x3 − x2 ≥ 4 − y23 x4 − x2 ≥ 7 − y24 x4 − x3 ≥ 5 − y34 x1 = 0 y12 ≤ 2 y23 ≤ 2 y24 ≤ 4 y34 ≤ 3

xi ≥ 0, yij ≥ 0

以上 i=1，2，3，4； j=1，2，3，4

用管理运筹学软件中的线性规划部分求解，得到如下结果： minf=46.5

x1=0,x2=1, x3=5,x4=7, y12 = 2 y23 = 0 y24 = 1 y34 = 3

第 13 章 存贮论

1．运用经济定购批量存贮模型，可以得到

a.经济订货批量 Q* = Dc32 × 4800 × 350

=≈ 579.66 件

c140 × 25%

b.由于需要提前 5 天订货，因此仓库中需要留有 5 天的余量，故再订货点

4800 ×

5为= 96 件

250

4800250

c.订货次数为≈ 8.28 次，故两次订货的间隔时间为≈ 30.19 工作

579.78.28

日

1D

c3 ≈ 5796.55 元d.每年订货与存贮的总费用 TC = Q * c1 +

Q*2（使用管理运筹学软件，可以得到同样的结果。）2．运用经济定购批量存贮模型，可以得到

a.经济订货批量 Q* = Dc32 × 14400 × 1800

=≈ 1314.53 吨

c11500 × 2%

b.由于需要提前 7 天订货，因此仓库中需要留有 7 天的余量，故再订货点

14400 × 7

为≈ 276.16 吨

365

14400365

c.订货次数为故两次订货的间隔时间为≈ 10.95 次，≈ 33.32 天

1314.5310.95 1D

c3 ≈ 39436.02 元d.每年订货与存贮的总费用 TC = Q * c1 +

Q*2（使用管理运筹学软件，可以得到同样的结果。）3．运用经济定购批量存贮模型，可知

a.经济订货批量 Q* = Dc3

= c1

Dc3

= 8000，其中 p 为产品单价，p × 22%

变换可得 2 Dc3

= 80002 × 22%，当存贮成本率为 27％时，p

Dc3 2 Dc380002 × 22%

=≈ 7221 箱 =Q *' =

c1 '

27%p × 27% b.存贮成本率为 i 时，经济订货批量 Q* =

单价，变换可得 Dc32 Dc3

，其中 p 为产品= c1p×i Dc3

= Q *2 ⋅ i，当存贮成本率变为 i ' 时，p

Dc32 Dc3Q *2 ⋅ i ==Q *' = c1 'p×i 'i'

4．运用经济生产批量模型，可知

a.最优经济生产批量 Q* =

Dc32 ×18000 × 1600

=≈ 2309.4 套

d18000

(1 −)c1(1 −)× 150 ×18% p30000

18000

b.每年生产次数为 ≈ 7.79 次

2309.4 250

c.两次生产间隔时间为≈ 32.08 工作日

7.79

250 × 2309.4

d.每次生产所需时间为≈ 19.25 工作日

30000 d

e.最大存贮水平为(1 −)Q* ≈ 923.76 套

p

1dD

c3 ≈ 24941.53 元f.生产和存贮的全年总成本为 TC =(1 −)Q * c1 + pQ*2g.由于生产准备需要天，因此仓库中需要留有 10 天的余量，故再订货

18000 × 10

点为= 720 套

250

（使用管理运筹学软件，可以得到同样的结果。）5．运用经济生产批量模型，可知

a.最优经济生产批量 Q* =

Dc32 × 30000 × 1000

=≈ 2344.04 d30000

(1 −)c1(1 −)×130 × 21% p50000

件

30000

b.每年生产次数为 ≈ 12.8 次

2344.04 250

c.两次生产间隔时间为≈ 19.53 工作日

12.8 d.每次生产所需时间为

250 × 2344.04

≈ 11.72 工作日

50000

d

e.最大存贮水平为(1 −)Q* ≈ 937.62 件

p

1dD

c3 ≈ 25596.88 元f.生产和存贮的全年总成本为 TC =(1 −)Q * c1 + pQ*2g.由于生产准备需要天，因此仓库中需要留有 5 天的余量，故再订货点

30000 × 5

为= 600 件

250

（使用管理运筹学软件，可以得到同样的结果。）6．运用允许缺货的经济定购批量模型，可以得到

a.最优订货批量 Q* = Dc3(c1 + c2)2 × 4800 × 350(10 + 25)

=≈ 685.86 件

c1c210 × 25

Dc3c12 × 4800 × 350 ×10

b.最大缺货量 S * =

=≈ 195.96 件，另外由于

c2(c1 + c2)25 ×(10 + 25)

需要提前 5 天订货，因此仓库中需要留有 5 天的余量，即在习题 1 中所

求出的 96 件，故再订货点为－195.96 + 96 = －99.96 件

4800250

c.订货次数为≈ 7.0 次，故两次订货的间隔时间为≈ 35.7 工作日

685.867

d.每 年 订 货、存 贮 与 缺 货 的 总 费 用

(Q * − S *)2DS *2 TC =c1 +c3 +c2 ≈ 4898.98 元

2Q *2Q *Q*

e.显然，在允许缺货的情况下，总花费最小。因为在允许缺货时，企业可

以利用这个宽松条件，支付一些缺货费，少付一些存贮费和订货费，从

而可以在总费用上有所节省。

（使用管理运筹学软件，可以得到同样的结果。）

7．运用允许缺货的经济生产批量模型，可知 Dc3(c1 + c2)2 × 30000 × 1000(27.3 + 30)a.最 优 经 济 生 产 批 量 Q* =

=≈

d30000

(1 −)c1c2(1 −)× 27.3 × 30 p50000

3239.52 件 d

300002 Dc3c1(1 −)2 × 30000 × 27.3 ×1000 ×(1 −)p

50000 617.37 ≈=b.最 大 件，另外由于需要缺 货 量 S * =天来准备生产，因此要留有 5 天的余量，即 c2(c1 + c2)30 ×(27.3 + 30)

第五篇：运筹学期末试卷及答案

一、判断题（21分）

1、可行解是基本可行解的充要条件是它的正分量所对应的A中列向量线性无关（）；

2、如果一个LP问题有最优解，则它的对偶问题也有最优解，且它们的最优解相等（）；

3、若线性规划问题有最优解，则一定有唯一的最优解（）；

4、若一个原始线性规划问题无界，则它的对偶问题也无界（）；

5、设f:RnR1在点xRn处的Hesse矩阵2f(x)存在，若2f(x)0，并且2f(x)正定，则x是（UMP）的严格局部最优解（）；

6、若f:RnR1是S上的凸函数，任意实数0则f是S上的凸函数（）；

7、设SRn是非空开凸集，f:RnR1二阶连续可导，则f是S上的严格凸函数的充要条件是f的Hesse矩阵2f(x)在 S上是正定的（）.二、1.将下面的线性规划问题化成标准形（7分）

2，写出下面线性规划的对偶规划（7分）

maxz4x15x26x3

minzx14x23x3

2x13x24x3105x2x8x20123 s.t

x12x25x39x1,x30,x2无约束.2x13x25x32xxx4123 s.t3x1x26x31x10,x30,x2为自由变量.三、证明题（10分）

设f:RnR1在点xRn处可微.若x是（UMP）的局部最优解，则f(x)0.四、用对偶单纯形法求解下列线性规划问题（10分）

minz15x124x25x3 6x2x32s.t5x2xx1231

xj0,j1,2,3

五、把线性规划问题（18分）

minZ2x1x2x3 x1x2x36s.tx2x4 记为（P）

12x1,x2,x30求（1）用单纯形算法解（p）；（2）c2由1变为(3)； 由64变为34 

六、用分枝定界法解下述ILP问题（10分）

maxzx1x2

2x1x25s.t4x1x22 x1,x20,且为整数

七、求以下无约束非线性规划问题的最优解（8分）

minf(xx221,2)x1x26x1x1x24x27

八、验证下列非线性规划为凸规划（9分）

minf(x)x2214x29x13x1x211 s.tg1(x)5x17x290gx)2x22x22(12x1x24x270

一、判断题（20分）

1.V;

2.X;

3.X;

4.X;

5.X ；

6.V 。

3）b

7.X（二、1.解：对自由变量x2用x4x5代替;对第一个不等式约束添加松弛变量x6,对第二个不等式约束添加剩余变量x7,再用zz代替原来的目标函数,便得到了标准形式的LP问题（2分）

minz4x15(x4x5)6x3

（4分）

s.t

2x13(x4x5)4x3105x2(xx)8xx2014536 x2(xx)5xx945371xj0,j1,3,4,5,6,7（8分）

2．解：这里c(1,4,3)T,b(2,4,1)T,根据定义，其对偶问题是

（2分）

max(21423)

（4分）

s.t

21233134123 56323110,30,2无约束（7分）

三、证明题（10分）

证：用反证法，若 f(x)0，现令Pf(x)，则有

（2分）

f(x)Pf(x)f(x)f(x)0（5分）

由定理，必存在0，使当t(0,)时，有

f(xtP)f(x)（8分）T2

成立

但这与假设矛盾.因此必有

f(x)0

（10分）

四、解：引进非负的剩余变量x40,x50,将不等式约束化为等式约束 6x2x3x42 5x12x2x3x51

x0,j1,,5j将等式两端同乘以（-1），就直接得到原问题一个基本（不可行）解和对偶问题的一个可行解（检验数向量0）其对应的单纯形标如下

1r161r2r13r04r13r221r1r243r0r22zx4x5152450005620z150051102x21011x511162034081106311133（6分）

1573170022225111x210444415131x3012222（8分）z

1117此时，b0,故原问题的最优解为x(0，)T，其最优值为。

422（10分）

五、解：（1）在约束条件中加入松弛变量x4,x5得

minz2x1x2x3

x1x2x3x46 s.tx12x2x5它的初始表

x1,,5j（2分）

z211000x4x511211060014r2r1rz2r1

1zx1x5031201210131111016（5分）100)其,最优值为z012。

此时检验数向量0,故最优解为x(6,0,T（6分）

(2)x1是非基变量11(c1c1)1（8分）

zx1x5011112012111101101r231r1r231rzr23

zx2004/37/31/346/310012/31/32/31/31/31/38/310/36x1

03（10分）,此时检验数向量0,故最优解为x(8/3,10/3,T0)其最优值为z046。（12分）3T(3)原问题的最优解为x(6,0,0),所对应的可行基B=A110 B1, 11

10A5=，1110331ccb6  故 bBb z1501147（16分）

从而新问题对应的单纯形表为

z x1x503120610131111013 7T,其0最优值为z06。由于b0，故最优解为x(3,0（18分）

六、解：用图解法解求ILP问题的松弛问题的最优解为(,)T,最优值为z0（2分）

它的最优解不符合整数的要求,可任选一个变量,如选择x17[]1,（4分）6786323。67进行分枝.由于6引进两个约束x11和x12生成两个子问题

maxzx1x2 maxzx1x2

s.t

2x1x254xx212x11x1,x20,且整数

(p1)

和

2x1x254xx212s.t(p2)（6分）

x21x1,x20,且整数ILP问题(p1)的松弛LP问题的最优解x1(1,2)T,最优值z3。(p2)的松弛LP问题的最优解

x2(2,1)T,最优值z3。

（8分）

由于33,故ILP问题的最优解x1(1,2)T,x2(2,1)T,最优值z3。

（10分）

2x1x26

七、解：目标函数的梯度向量为 f(x)，x2x412（2分）

令f(x)0，求得f的驻点

x(8/T3。

（4分）

21，2fx的一、二阶顺序主子式分别为 f的Hesse矩阵为fx122 20，211230（6分）

对xRn,2fx为正定矩阵，因而f是Rn上的凸函数。故（8分）x(8/3,2T/为它的整体最优解。3

八、解：

f的Hesse矩阵为

232fx38，（2分）

2fx的一、二阶顺序主子式本别为

20，233870，因而2fx为正定矩阵，f是严格凸函数.（4分）

4－1而g2x=，它也是一个正定矩阵，因而g2x也是严格凸函数，－142（7分）

其它的不等是约束为线性的。由定理知，该非线性规划是一个凸规划。

（9分）