运筹学各章的作业题答案

----复习思考题及作业题

第一章 绪论

复习思考题

1、从运筹学产生的背景认识本学科研究的内容和意义。

2、了解运筹学的内容和特点，结合自己的理解思考学习的方法和途径。 3、体会运筹学的学习特征和应用领域。

第二章 线性规划建模及单纯形法

复习思考题

1、线性规划问题的一般形式有何特征？

2、建立一个实际问题的数学模型一般要几步？

3、两个变量的线性规划问题的图解法的一般步骤是什么？

4、求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？

5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。

6、试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。

7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。

8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？

9、大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？

10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？

作业题:

1、把以下线性规划问题化为标准形式：

(1) max z= x1 -2x2 +x3 s.t.

(2) min z= -2x1 -x2 +3x3 -5x4 s.t

x1 +2x2 +4x3 -x4 ≥ 6 2x1 +3x2 -x3 +x4 ＝12 x1 +x3 +x4 ≤ 4 x1, x2,

x4 ≥ 0

x1 +x2 +x3 ≤12 2x1 +x2 -x3 ≥ 6 -x1 +3x2 ＝ 9 x1, x2, x3 ≥ 0

(3) max z= x1 +3x2 +4x3

s.t.

3x1 +2x2

2x1 x1,

≤13

x2 +3x3 ≤17 +x2 +x3 =13 x3 ≥0

2、用图解法求解以下线性规划问题

(1)

(2)

min z= x1 -3x2 s.t.

max z= s.t.

x1 +3x2

x1 +x2 ≤10 -2x1 +2x2 ≤12 x1 x1,

≤

7

x2 ≥0

≤4 ≥3

2x1 -x2 x1 +x2 x1 x1,

x2 ≤5 ≤4 x2 ≥0

3、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解。

max s.t.

z= 2x1 +x2 -x3

x1 + x2 +2x3 ≤6 x1 +4x2 -x3 ≤4 x1, x2, x3 ≥0

4、用单纯形表求解以下线性规划问题

(1) max z= x1 -2x2 +x3 s.t.

(2) min z= -2x1 -x2 +3x3 -5x4 s.t

2

x1 +x2 +x3 ≤12 2x1 +x2 -x3 ≤ 6

-x1 +3x2 ≤ 9 x1, x2, x3 ≥ 0

x1 +2x2 +4x3 -x4 ≤ 6 2x1 +3x2 -x3 +x4 ≤12

x1 +x3 +x4 ≤ 4 x1, x2, x3,

x4 ≥ 0

5、用大M法和两阶段法求解以下线性规划问题

(1) Max z= x1 +3x2 +4x3 s.t.

(2) max z= 2x1 -x2 +x3 s.t.

3x1 +2x2

2x1 x1,

≤13

x2 +3x3 ≤17 +x2 +x3 =13 x2,

x3

≥0

x1 +x2 -2x3 ≤8

4x1 -x2 +x3 ≤2 2x1 +3x2 -x3 ≥4 x1, x2,

x3 ≥0

6、某饲养场饲养动物，设每头动物每天至少需要700克蛋白质、30克矿物质、100毫克维生素。现有五种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示：

饲料 1 2 3 4 5

蛋白质（克） 矿物质（克） 3 2 1 6 12 1 0．5 0．2 2 0．5 维生素（毫克） 0．5 1．0 0．2 2 0．8 价格（元/公斤） 0．2 0．7 0．4 0．3 0．8 要求确定既满足动物生长的营养要求，又使费用最省的选择饲料的方案。 7、某工厂生产Ⅰ、Ⅱ、Ⅲ、Ⅳ四种产品，产品Ⅰ需依次经过A、B两种机器加工，产品Ⅱ需依次经过A、C两种机器加工，产品Ⅲ需依次经过B、C两种机器加工，产品Ⅳ需依次经过A、B机器加工。。有关数据如表所示，请为该厂制定一个最优生产计划。

产 品 Ⅰ Ⅱ Ⅲ Ⅳ 机器成本（元／小时） 每 周 可 用 小时 数 机器生产率（件/小时） Ａ 10 20 20 200 150 Ｂ 20 10 10 150 120 Ｃ 10 15 225 70 原料成本（元） 16 25 12 18 产品价格（元） 65 80 50 70

第三章 线性规划问题的对偶及灵敏度分析

复习思考题

1、对偶问题和它的经济意义是什么？

2、简述对偶单纯形法的计算步骤。它与单纯形法的异同之处是什么？ 3、什么是资源的影子价格？它和相应的市场价格之间有什么区别？

3

4、如何根据原问题和对偶问题之间的对应关系，找出两个问题变量之间、解及检验数之间的关系？

5、利用对偶单纯形法计算时，如何判断原问题有最优解或无可行解？

6、在线性规划的最优单纯形表中，松弛变量（或剩余变量）xnk0，其经济意义是什么？

7、在线性规划的最优单纯形表中，松弛变量xnk的检验数nk0，其经济意义是什么？ 8、关于aij,cj,bi单个变化对线性规划问题的最优方案及有关因素将会产生什么影响？有多少种不同情况？如何去处理？

9、线性规划问题增加一个变量，对它原问题的最优方案及有关因素将会产生什么影响？如何去处理？

10、线性规划问题增加一个约束，对它原问题的最优方案及有关因素将会产生什么影响？如何去处理？

作业题

1、写出以下问题的对偶问题

(1) min z= 2x1 +3x2 +5x3 +6x4 s.t.

(2) min z= 2x1 +3x2 -5x3 s.t.

x1 +x2 2x1

+x3

-x3 +x4 ≥5

≤4

=6

-2x1 x1,

-x2 x2,

x1 +2x2 +3x3 +x4 ≥2

-x3 +3x4 ≤-3 x3, x4 ≥0

x2 +x3 +x4

x1≤0, x2≥0, x3≥0, x4无符号限制

2、已知如下线性规划问题

Max s.t.

z=

6x1 -2x2 +10x3 3x1 x1,

x2 + 2x3 -x2 + x3 x2,

x3

≤5 ≤10 ≥0

其最优单纯形表为

b 10 6 -z x3 x1 5/2 5/2 -40 6 x1 0 1 0 -2 x2 1/2 -1/2 -4 10 x3 1 0 0 0 x4 1/2 -1/6 -4 0 x5 0 1/3 -2 -1

（1）写出原始问题的最优解、最优值、最优基 B 及其逆 B。

（2）写出原始问题的对偶问题，并从上表中直接求出对偶问题的最优解。

4

3、用对偶单纯形法求解以下问题

(1) min z= 4x1 +6x2 +18x3 s.t.

(2) min z= 10x1 +6x2 s.t.

2x1 x1,

x1 +x2 ≥2

-x2 ≥6 x2 ≥0

x1

x2

+3x3 ≥3 +2x3 ≥5

x1, x2, x3≥0

4、已知以下线性规划问题

max s.t.

z= 2x1

x1 -x1 x1,

+x2 +2x2 +x2

-x3

+x3 ≤8 -2x3 ≤4

x2, x3≥0

及其最优单纯形表如下：

2 0 -z x1 x6 b 8 12 -16 2 x1 1 0 0 1 x2 2 3 -3 -1 x3 1 -1 -3 0 x4 1 1 -2 0 x5 0 1 0

(1) 求使最优基保持不变的c2=1的变化范围。如果c2从1变成5，最优基是否变化，如果变化，求出新的最优基和最优解。

(2) 对c1=2进行灵敏度分析，求出c1由2变为4时的最优基和最优解。

(3) 对第二个约束中的右端项 b2 = 4 进行灵敏度分析，求出 b2 从 4 变为 1 时新的最优基和最优解。

(4) 增加一个新的变量x6，它在目标函数中的系数 c6 = 4，在约束条件中的系数向

1量为a6， 求新的最优基和最优解。

2 (5) 增加一个新的约束x2+x32，求新的最优基和最优解。

5

5、某工厂用甲、乙、丙三种原料生产A、B、C、D四种产品，每种产品消耗原料定额以及三种原料的数量如下表所示:

产 品 对原料甲的单耗(吨/万件) 对原料乙的消耗(吨/万件) 对原料丙的消耗(吨/万件) 单位产品的利润(万元/万件) A 3 2 1 25 B 2 － 3 12 C 1 2 － 14 D 4 3 2 15 原料数量（吨）2400 3200 1800 求使总利润最大的生产计划和按最优生产计划生产时三种原料的耗用量和剩余（1）量。

（2）求四种产品的利润在什么范围内变化，最优生产计划不会变化。 （3）求三种原料的影子价格。

（4）在最优生产计划下，哪一种原料更为紧缺?如果甲原料增加120吨，这时紧缺程

度是否有变化?

第四章 运输问题

复习思考题

1、运输问题的数学模型具有什么特征？为什么其约束方程的系数矩阵的秩最多等

于mn1？

2、用西北角法确定运输问题的初始基本可行解的基本步骤是什么？

3、最小元素法的基本思想是什么？为什么在一般情况下不可能用它直接得到运输问题的最优方案？

4、试述用闭回路法检验给定的调运方案是否最优的原理，其检验数的经济意义是什么？

5、用闭回路法检验给定的调运方案时，如何从任意空格出发去寻找一条闭回路？这闭回路是否是唯一的？

6、试述用位势法求检验数的原理、步骤和方法。 7、试给出运输问题的对偶问题（对产销平衡问题）。

8、如何把一个产销不平衡的运输问题（产大于销或销大于产）转化为产销平衡的运输问题。

9、一般线性规划问题应具备什么特征才可以转化为运输问题的数学模型？

作业题

1、求解下列产销平衡的运输问题，下表中列出的为产地到销地之间的运价。 （1） 用西北角法、最小元素法求初始基本可行解；

6

（2） 由上面所得的初始方案出发，应用表上作业法求最优方案，并比较初始方案需要的迭代次数。 销 地 甲 产 地 1 2 3 销 量

10 8 9 15 乙 5 2 3 20 丙 6 7 4 30 丁 7 6 8 35 产 量 25 25 50 100 2、用表上作业法求下列产销平衡的运输问题的最优解：（表上数字为产地到销地的运价，M为任意大的正数，表示不可能有运输通道）

（1）

销 地 甲 产 地 1 2 3 销 量

（2） 产地 销地 1 2 3 4 产 量

甲 7 4 5 8 10 乙 2 6 7 8 15 丙 1 7 M 6 12 丁 6 M 3 2 10 戊 7 6 7 6 18 销 量 20 20 10 15 65 7 3 4 10 乙 9 5 3 15 丙 5 8 10 20 丁 2 6 4 10 产 量 17 15 23 55 3、用表上作业法求下列产销不平衡的运输问题的最优解：（表上数字为产地到销地的里程，M为任意大的正数，表示不可能有运输通道）。

（1） 产地 销地 1 2 3 产 量 （2） 产地 销地 1 2 3

甲 10 7 8 50 乙 4 M 5 40 丙 10 4 12 30 丁 7 4 6 60 戊 5 7 8 20 销 量 80 40 60 甲 7 4 6 乙 3 2 8 丙 9 5 12 丁 4 6 2 7

戊 11 10 5 销 量 30 24 36 产 量

12 18 21 14 15 4、某农民承包了5块土地共206亩，打算小麦、玉米和蔬菜三种农作物，各种农作物的计划播种面积（亩）以及每块土地种植各种不同的农作物的亩产数量（公斤）见下表，试问怎样安排种植计划可使总产量达到最高？ 土地块别 作物种类 1 2 3 土地亩数 甲 500 850 1000 36 乙 600 800 950 48 丙 650 700 850 44 丁 戊 计划播种面积 86 70 50 1050 800 900 950 550 700 32 46 提示：为了把问题化为求最小的问题，可用一个足够大的数（如1200）减去每一个

亩产量，得到新的求最小的运输表，再进行计算。得到求解的结果后，再通过逆运算得到原问题的解。（想一想为什么？）

第五章 动态规划

思考题

主要概念及内容：

多阶段决策过程；阶段及阶段变量；状态、状态变量及可能的状态集合；决策、决策变量及允许的决策集合；策略、策略集合及最优策略；状态转移方程；K－子过程；阶段指标函数、过程指标函数及最优值函数；边界条件、递推方程及动态规划基本方程；最优性原理；逆序法、顺序法。

复习思考题：

1、试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。 2、动态规划的阶段如何划分？

3、试述用动态规划求解最短路问题的方法和步骤。

4、试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值函数、边界条件等概念。

5、试述建立动态规划模型的基本方法。

6、试述动态规划方法的基本思想、动态规划的基本方程的结构及正确写出动态规划基本方程的关键步骤。 作业题

1、用动态规划求解以下网络从A到G的最短路径。

B13654B2327B3

13C1254C227D189D2711D398

10E112FE213A3

2、某公司有5台设备，分配给所属A,B,C三个工厂。各工厂获得不同的设备台数所能产生效益（万元）的情况如下表。求最优分配方案，使总效益最大。

台数 A B C

0 0 5 7 1 10 17 12 2 15 20 15 3 20 22 18 4 23 23 20 5 25 24 23 3、用动态规划求解以下非线性规划问题： max z = x1 • 2 x2 ·3 x3 s.t. x1+3x2+2x3 ≤12 x1 , x2 , x3 ≥0

4、某企业生产某种产品，每月月初按订货单发货，生产的产品随时入库，由于空间的限制，仓库最多能够贮存产品90000件。在上半年（1至6月）其生产成本（万元／千件）和产品订单的需求数量情况如下表： 月份(k) 成本与需求 生产成本(ck)（万元／千件） 需求量(rk)（千件） 1 2.1 35 2 2.8 63 3 2.3 50 4 2.7 32 5 2.0 67 6 2.5 44 已知上一年底库存量为40千件，要求6月底库存量仍能够保持40千件。

问：如何安排这6个月的生产量，使既能满足各月的定单需求，同时生产成本最低。

第六章 排队论

复习思考题

1、排队论主要研究的问题是什么？

2、试述排队模型的种类及各部分的特征；

3、Kendall符号X/Y/Z/A/B/C中的各字母分别代表什么意义；

4、理解平均到达率、平均离去率、平均服务时间和顾客到达间隔时间等概念； 5、分别写出泊松分布、负指数分布的密度函数，说明这些分布的主要性质； 6、试述队长和排队长；等待时间和逗留时间；忙期和闲期等概念及他们之间的联系与区别。

7、讨论求解排队论问题的过程？

8、熟悉状态转移速度图的绘制；掌握利用状态转移速度图寻找各状态发生概率之间的关系，导出各状态发生概率与P0的关系的方法，进而计算有关的各个量。

9

9、如何对排队系统进行优化（服务率，服务台数量）？

作业题

1、某修理店只有一个修理工，来修理的顾客到达的人数服从Poisson分布，平均每小时4人；修理时间服从负指数分布，每次服务平均需要6分钟。求： （1）修理店空闲的概率； （2）店内有三个顾客的概率； （3）店内至少有一个顾客的概率； （4）在店内平均顾客数；

（5）顾客在店内的平均逗留时间； （6）等待服务的平均顾客数； （7）平均等待修理的时间；

2、一个理发店有3名理发员，顾客到达服从Poisson分布，平均到达时间间隔为15秒钟；理发时间服从负指数分布，平均理发时间为0.5分钟。求： （1）理发店内无顾客的概率；

（2）有n个顾客在理发店内的概率；

（3）理发店内顾客的平均数和排队等待的平均顾客数； （4）顾客在理发店内的平均逗留时间和平均等待时间；

3、某修理部有一名电视修理工，来此修理电视的顾客到达为泊松流，平均间隔时间为20分钟，修理时间服从负指数分布，平均时间为15分钟。求： （1）顾客不需要等待的概率；

（2）修理部内要求维修电视的平均顾客数； （3）要求维修电视的顾客的平均逗留时间；

（4）如果顾客逗留时间超过1.5小时，则需要增加维修人员或设备。问顾客到达率超过多少时，需要考虑此问题？

4、某公用电话亭只有一台电话机，来打电话的顾客为泊松流，平均每小时到达20人。当电话亭中已有n 人时，新到来打电话的顾客将有 n/4 人不愿等待而自动离去。已知顾客打电话的时间服从负指数分布，平均用时3分钟。 （1）画出此排队系统的状态转移速度图；

（2）导出此排队系统各状态发生概率之间的关系式，并求出各状态发生的概率； （3）求打电话顾客的平均逗留时间。

5、某工厂有大量同一型号的机床，其损坏率是服从泊松分布的随机变量，平均每天损坏 2 台，机床损坏时每台每天的损失费用为 400 元。已知机修车间的修理时间服从负指数分布，平均每台损坏机床的维修时间为 1/ 天。又知  与车间的年开支费用 K （K>1900元）的关系如下：

( K ) = 0.1 + 0.001 K ；

试决定是该厂生产最经济的 K 及  的值。

10

作业题的参考解： 第二章

1、把以下线性规划问题化为标准形式：

(1) max z = x1 -2x2 +x3 s.t.

(2) Max f= s.t

(3) max z= x1 +3x’2 -3x”2 +4x3

s.t.

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

＝12

-x5 ＝ 6 ＝ 9

x1, x2, x3, x4, x5 ≥ 0 2x1 +x2 -3x’3 +3x”3 +5x4 x1 +2x2 +4x’3 2x1 +3x2 x1

x5,

-4x”3 -x4 -x5 +x”3 +x4 -x”3 +x4 x\"3, x4,

+x4 x4,

＝ 6 ＝12 +x6 ＝ 4 x6 ≥ 0

-x’3 +x’3 x'3,

x1, x2,

3x1 +2x’2 -2x”2

＝13 +x5 ＝17 ＝13 x5

≥0

x'2 -x”2 +3x3

2x1 +x’2 -x”2 +x3 x1, x'2, x\"2, x3

2、(1) x* = (2, 8)T , z* = 26；(2) x* = (0, 5)T , z* = -15 。

3、在以下问题中，列出所有的基，指出其中的可行基，基础可行解以及最优解。

max s.t.

z= 2x1 +x2 -x3

x1 + x2 +2x3 ≤6 x1 +4x2 -x3 ≤4

x2,

x3 ≥0

x1,

Aa1a2a3a411210a5

14101（1）B1a1a2114/31/31,B11/31/3 14x30x14/31/3620/31XBB1b,X42/3Nx40

x1/31/32x50x30x120/3,XB1不是可行基，XBNx40不是基础可行解。

x2/32x50

11

（2）B2a1a31211/32/3,B21/31/3 11x20x40 x50x11/32/3614/31XBB2b42/3,XNx1/31/33x2x114/3,XNx4B2是可行基，XBx32/3x500是基础可行解，目标函数值为： 0zCBbc1TB12x114/3c32126/3

x2/33（3）B3a1a411011 ,B31011

x1B3是基础可行解，XBx442,XNx20x30是基础可行解，目标函数值为： x50zCBbc1TB13x14c4208 x42（4）B4a110110a5,B411

11x11XBB4bx5106114x206,X2Nx30 x40x1B4不是可行基，XBx5x206,X2Nx30不是基础可行解。 x40（5）B5a2a31211/92/9,B54/91/9 41 12

x10x21/92/9614/91XBB5b,XNx40 x34/91/9420/9x50x2B5是可行基，XBx3x114/9,X20/9Nx4x500是基础可行解，目标函数值为： 01zCTBB5bc2x214/9c3116/92/3

x20/93（6）B6a2a411101/4,B611/4 40x10x201/4611XBB6b,X45Nx30

x11/44x50x2B6是可行基，XBx4x101,X5Nx30是基础可行解，目标函数值为： x501zCTBB6bc2x21c4101 x45（7）B7a2a510110,B741 41

x1x26B7不是可行基，XB,XNx3x52x4（8）B8a300不是基础可行解。 0a421101,B812 1000 0x1x301641XBB8b,XNx2x412414x5 13

B8不是可行基，

不是基础可行解。

（9）B9a3a52011/20,B91/21 1100 0x1x31/20631XBB9b,XNx2x51/2147x4x3B9是可行基，XBx5x13,X7Nx2x400是基础可行解，目标函数值为： 01zCTBB9bc3x33c5103 x57（10）

x410661XBB10b44,XNx015x4B10是基础可行解，XBx564,XNx10x20 x3000目标函数值为： 0x1x2x3zCBbc4TB110x46c5000 x54在可行基B2、B3、B5、B6、B9、B10中，最优基为B2，最优解为：

x20x11/32/3614/31XBB2b,XNx40 x31/31/342/3x50是基础可行解，目标函数值为：

4、(1) x* =（0, 0, 12, 0, 18, 9 ）T ， z* = 12；

或 x* =（6, 0, 6, 0, 0, 15 ）T ， z* = 12 。

14

（2） x* = (0, 8/3, 0, 4, 14/3, 0, 0)T ， z* = -68/3

5、(1) 原问题的最优解：x* = (3, 2, 5 )T， z * = 29

(2) 原问题的最优解：x* = (0, 3, 5, 15, 0, 0)T， z* = 2。

6、解：设五种饲料分别选取x1,x2,x3,x4,x5 公斤，则得下面的数学模型：

minZ0.2x10.7x20.4x30.3x40.8x5

3x12x2x36x412x5700x0.5x0.2x2x0.5x3012345  ；

0.5xx0.2x2x0.8x10012345xj0(j1,2,3,4,5) 7、解：设xj

(j1,2,3,4)为第j种产品的生产数量，则有

maxZ49x155x238x352x427.5x132.5x229.6x325x4

x1x2x4102020150xxx134120 201010

x2x3701015x1,x2,x3,x40其中：49=65-16 ；27.5=200/20 + 150/10 ，依次类推。

第三章

1、写出以下问题的对偶问题

(1) min z= 2x1 +3x2 +5x3 +6x4 s.t.

对偶问题为

max

s.t.

x1 +2x2 +3x3 +x4 ≥2

-x2 x2,

-x3 +3x4 ≤-3 x3, x4 ≥0

-2x1 x1,

y=

2w1 w1 2w1 3w1 w1 w1≥0

+3w2 +2w2 +w2 +w2 -3w2 w2≥0

≤2 ≤3 ≤5 ≤6

15

(2) min z= 2x1 +3x2 -5x3 s.t.

对偶问题为

max s.t.

T

2、（1）原问题的最优解 x* = (5/2, 0, 5/2)、最优值 z* = 40，

x1 +x2

-x3 +x4 ≥5

≤4

=6

2x1 +x3

x2 +x3 +x4

x1≤0, x2≥0, x3≥0, x4无符号限制

y=

5w1 w1 w1 -w1 w1 w1≥0 - 4w2 - 2w2

- w2

w2≥0 +6w3

≥2 +w3 ≤3 +w3 ≤-5 +w3 =0 w3无符号限制

2 0 1/2 0 最优基 B = 及其逆 B-1 =

1 3 - 1/6 1/3 （2）写出原始问题的对偶问题，并从上表中直接求出对偶问题的最优解。 对偶问题为

Min s.t.

y=

5w1

w1 2w1 w1 ,

+10w2 +2w2 ≤6 - w2 ≤-2 +w2 ≤10

w2≥0

它的解为：w* = (4 , 2 )T y* = 40

3、(1) 最优解：x* = (0，3，1)T， z* = 36

(2) 最优解：x* = (3，0)T， z* = 30

4、(1) 使最优基保持不变的c2=1的变化范围：3-≥0，≤3，即c2≤4。

当c2=5，即=4，新的最优解为x* = (0，4，0)T， z* = 20； (2) 对于 c1=2，当  ≥ -3/2 时，即 c1 ≥1/2 时，最优基保持不变。

当 c1 = 4 时， = 4-2 = 2，最优基保持不变，最优解的目标函数制为 z=16+8 =32。 (3) 右端项 b2 = 4 ，当 b2 ≥ -12，即 b2 ≥ -8 时，最优基不变。 因此，b2 从4 变为 1 时，最优基不变，而新的最优解也不变。 (4) 新的最优基为 p1 ，p6

新的最优解为 x* = (4，0，0，0，0，4)T， z* = 24。 (5) 新的最优基为 p1，p2

新的最优解为 x* = (4，2，0，0，6，0)T， z* = 10。

16

5、 (1) 利润最大化的线性规划模型为：

max s.t.

z=

25x1 +12x2 3x1 2x1 x1

+2x2

+3x2

+14x3 +x3 +2x3

+15x4 +4x4 +3x4 +2x4

≤2400 ≤3200 ≤1800

≥0 x1, x2, x3, x4

最优解为：x* = (0，400，1600，0，0，0，600)T， z* = 27200。即最优生产计划为：产品A不生产；产品B生产400万件；产品C生产1600万件；产品D不生产，最大利润：27200万元。 这里，原料甲耗用2400吨没有剩余；原料乙耗用3200吨没有剩余；原料丙耗用了1200吨剩余600吨。

(2) 产品A利润变化范围：-1-≤0，≥-1，-c1’=-c1+≥-25-1=-26，即c1’≤26（万元/万件）； 产品B利润变化范围：

101215/4084/5，，故 -1≤≤12， -13≤-c2’≤0，即：0≤c2’≤13； 61/201241/4016 产品C利润的变化范围：

101213/20，14，故 -1≤≤8， -15≤-c3’≤-6，即：6≤c3’≤15； 41/208 产品D的变化范围：-21-≤0，≥-21，-15+≥-36，-c4’≥-36，即c4’≤36。

（3）原料甲、乙、丙的影子价格分别为：6万元/吨、4万元/吨、0万元/吨。

（4）在最优解中，原料甲的影子价格（6万元/吨）最大，因此这种原料最紧缺。如果原料A增加120吨，最优单纯形表的右边常数成为：

1/21/4024001204006001000B1b01/2032001600016000

3/23/411800600180420因此最优基保持不变，影子价格不变，原料的紧缺程度不变。

第四章

1、求解下列产销平衡的运输问题，下表中列出的为产地到销地之间的运价。 （1） 用西北角法、最小元素法求初始基本可行解；

西北角法： 销 地 甲 产 地 1 2 3

乙 10 10 丙 15 15 丁 35 17

产 量 25 25 50 15 销 量 15 20 30 35 100

最小元素法： 销 地 甲 产 地 1 2 3 销 量 15 15 乙 20 20 丙 30 30 丁 25 5 5 35 产 量 25 25 50 100

（2）最优方案： 最小费用 535 销 地 甲 产 地 1 2 3 销 量

15 15 乙 15 5 20 丙 30 30 丁 25 10 35 产 量 25 25 50 100 2、

（1）最优方案： 最小费用 226 销 地 甲 产 地 1 2 3 销 量 10 10 乙 15 15 丙 15 5 20 丁 2 8 10 产 量 17 15 23 55

（2）最优方案： 最小费用 248 （有多解） 产地 销地 1 2 3 4 产 量

甲 10 10 乙 8 7 15 丙 12 12 丁 10 10 戊 10 3 5 18 销 量 20 20 10 15 65 3、

（1）最优方案： 最小费用 980 产地 销地 1 2

甲 乙 40 丙 30 丁 20 10 18

戊 20 销 量 80 40 3 4 产 量 产地 销地 1 2 3 产 量

30 20 50 40 30 30 60 20 60 20 （2）最优方案： 最小费用 330 甲 2 3 7 12 乙 18 18 丙 21 21 丁 14 14 戊 15 15 己 10 10 销 量 30 24 36 4、最优方案： 最高总产量 kg 土地块别 作物种类 1 2 3 土地亩数 甲 36 36 乙 34 14 48 丙 44 44 丁 32 32 戊 10 36 46 计划播种面积 86 70 50

19

第五章

1、

23

21

12 22

B1 1 3 D1 10 26 3 6 C1 8 E1 0

25 4 5 2 20 9 12 A 5 B2 D2 F 2 3 4 7 13 7 C2 2 11 E2 B3 3 22 7 D3 9 13 25 22

最短路径为A—B1—C1—D2—E2—F，长度为26。

2、阶段k：每分配一个工厂作为一个阶段；

状态变量xk：分配第k个工厂前剩余的设备台数； 决策变量dk：分配给第k个工厂的设备台数； 决策允许集合：0≤dk≤xk 状态转移方程：xk+1=xk-dk

阶段指标：vk(xk,dk)第k次分配产生的效益，见表中所示； 递推方程：fk(xk)=max{vk(xk,dk)+fk+1(xk+1)} 终端条件：f4(x4)=0 列表计算,可得到：

最优解为 x1 = 5，d1* = 3；x2 = x1-d1 = 2，d2* = 1；x3 = x2-d2* = 1，d3 = 1；x4 = x3-d3 = 0。即分配给工厂A设备3台，工厂B设备1台，工厂C设备1台，最大效益为49万元。 3、

阶段k：每一个变量作为一个阶段，k =1，2，3，4；

状态变量sk：考虑第k个变量时，允许的上界， s1 ＝12； 决策变量xk：第k个变量的取值；

决策允许集合： 0 ≤ xk ≤ sk /ak ，ak 为各变量的系数，分别为1、3、2； 状态转移方程：sk+1 = sk - ak xk

阶段指标：目标函数中关于xk 的表示式 vk(sk , xk) ＝ k xk； 递推方程：fk(sk ) = max { vk(sk , xk ) • f k+1 (sk+1) } 边界条件：f ( s4 )= 1 逆序法求解： k = 3 ：

f3(s3 ) = max { v3 (s3 , x3 ) • f 4 (s4) } = max { 3 x3 } 0 ≤ x3 ≤ s3 /2 ∴ x3 * = s3 /2， f3(s3 ) =（3／2）s3 ； k = 2 ：

f2(s2 ) = max { 2 x2 • f3 (s3 ) } = max { 2 x2• (s2 –3x2) } 0 ≤ x2 ≤ s2 /3 求导数为零的点，并验证二阶导数小于零，可得 ∴ x2 * = s2 /6， f2(s2 ) =（1／4）s22 ； k = 1 ：

20

f1(s1 ) = max { x1 • f2 (s2 ) } = max { x1• (12 –x1 )2／4 } 0 ≤ x1 ≤ s1＝12 求导数为零的点，并验证二阶导数小于零，可得 ∴ x1 * = 4， f1(s1 ) = 64 ； 于是通过计算,可得到：

最优解为 s1 = 12，x1* = 4；s2 = s1-x1 = 8，x2* = 4／3；s3 = s2-3x2* = 4，x3 = 2；最优值为64 。

4、解：

阶段k：月份，k=1,2,…,7；

状态变量xk：第k个月初（发货以前）的库存量； 决策变量dk：第k个月的生产量； 状态转移方程：xk+1=xk-rk+dk；

决策允许集合：Dk(xk)={dk | dk0, rk+1xk+1H} H＝90

={dk | dk0, rk+1xk-rk+dkH}；

阶段指标：vk(xk,dk)=ckdk； 终端条件：f7(x7)=0,

x7=40；

递推方程：fk(xk)=min{vk(xk,dk)+fk+1(xk+1)}

dkDk(xk)

=min{ckdk+fk+1(xk-rk+dk)}

dkDk(xk)

对于k=6 x6-r6+d6=x7=40 因此有 d6=x7+r6-x6=40+44-x6=84-x6 也是唯一的决策。因此递推方程为：

84-x6≥0

f6(x6) = min {c6d6+f7(x7)}

d6=84-x6

=2.5d6=2.5(84-x6)=210-2.5x6

对于k=5

f5(x5)=min{c5d5+f6(x6)}

d5D5(x5)

=min{2.0d5+210-2.5x6}

d5D5(x5)

=min{2.0d5+210-2.5(x5-r5+d5)}

d5D5(x5)

=min{-0.5d5-2.5x5+377.5}

d5D5(x5)

D5(x5)={d5| d50, r6x5-r5+d5H, 84- (x5-r5+d5)≥0 }

={d5|d50, r6+r5-x5d5H+r5-x5 , d5  84+67 - x5=151-x5}

21

={d5| d50, 111-x5d5151-x5} 递推方程成为

f5(x5)=min{-0.5d5-2.5x5+377.5}

111-x5d5157-x5

=-0.5(151-x5)-2.5x5+377.5 =302-2x5，

d5*=151-x5

对于k=4

f4(x4)=min{c4d4+f5(x5)}

d4D4(x4)

=min{2.7d4+302-2x5}

d4D4(x4)

=min{2.7d4+302-2(x4-r4+d4)}

d4D4(x4)

=min{0.7d4-2x4+366}

d4D4(x4)

D4(x4)={d4| d40, r5x4-r4+d4H}

={d4| d40, r5+r4-x4d4H+r4-x4}

={d4| d40, 99-x4d4122-x4} 因为 99-x4 > 0 ={d4| 99-x4 d4122-x4}

由于在f4(x4)的表达式中d4的系数是 0.7，因此d4在决策允许集合中应取集合中的最小值， 即 由此

d4=99-x4

f4(x4)= 0.7(99-x4)-2x4+366

= －2.7x4+435.3

对于k=3

f3(x3)=min {c3d3+f4(x4)}

d3D3(x3)

=min {2.3d3+435.3-2.7x4}

d3D3(x3)

=min {2.3d3+435.3-2.7(x3-r3+d3)}

d3D3(x3)

=min {-0.4d3-2.7x3+570.3)}

d3D3(x3)

D3(x3)={d3| d30,r4x3-r3+d3H}

={d3| d30,r4+r3-x3d3H+r3-x3} ={d3| d30,82-x3d3140-x3} ={d3| max[0,82-x3]d3140-x3}

22

由此

f3(x3)=-0.4(140-x3)-2.7x3+570.3

d3*=140-x3

= -2.3x3+514.3,

对于k=2

f2(x2)=min{c2d2+f3(x3)}

d2D2(x2)

=min{2.8d2+514.3-2.3x3}

d2D2(x2)

=min{2.8d2+514.3-2.3(x2-r2+d2)}

d2D2(x2)

=min{0.5d2-2.3x2+659.2}

d2D2(x2)

D2(x2)={d2|d20, r3x2-r2+d2H}

={d2|d20, r3+r2-x2d2H+r2-x2} ={d2|d20, 113-x2d2153-x2}

因为 所以 由此

113-x2>0

d2(x2)={d2|113-x2d2153-x2} f2(x2)=0.5(113-x2)-2.3x2+659.2

= -2.8x2+715.7,

d2*=113-x2

对于k=1

f1(x1)=min{c1d1+f2(x2)}

d1D1(x1)

=min{2.1d1+715.7-2.8x2}

d1D1(x1)

=min{2.1d1+715.7-2.8(x1-r1+d1)}

d1D1(x1)

=min{-0.7d1-2.8x1+813.7}

d1D1(x1)

D1(x1)={d1|d10, r2x1-r1+d1H}

={d1|d10, r2+r1-x1d1H+r1-x1} ={d1|d10, 98-x1d1125-x1} x1=40

D1(x1)={d1| 58  d1  85 } d1=85

f1(x1)= -0.7d1-2.8x1+813.7

=-0.7×85－2.8×40＋813.7

23

根据题意 所以 由此

=642.2

将以上结果总结成下表：

k ck rk xk dk

1 2.1 35 40 85 2 2.8 63 90 3 2.3 50 50 4 2.7 32 90 99-x4=9 5 2.0 67 67 151-x5=84 6 2.5 44 84 84-x6=0 113-x2=23 140-x3=90

第六章

1、(1) P0 ＝ 0.6 (2) P0 = 0.0384 (3) 1 - P0 = 0.4 (4) L = 0.667 (5) W = 10分钟 (6) Lq = 0.267 (7) Wq = 4分钟。

2、(1) P0 = 1/9 (2) P1 = 2/9, P2 = 1/9, P3 = 4/27 , n > 3 时， ＝ 0.5(2/3)n (3) L = 26/9 , Lq = 8/9 (4) W = 13/18 Wq = 2/9 。

3、(1) P0 = 0.25 (2) L = 3人 (3) W = 60分钟 (4)  > 0.55人／分。

4、(1)  =  = 20；

0.75 0.5 0.25 

0 1 2 3 4    

(2) Pn +1 = [( 1- n/4 )/]Pn , n = 0,1,2,3,4

P0 =0.311, P1 =0.311, P2 =0.233, P3 =0.117, P4 =0.028； (3) W = 0.088(小时)。

5、以一个月为期计算：

S = L  400  25.5（每月工作天数）＋ K／12（每月的车间开支） 其中 L =  ／ ＝  ／ (0.1-0.001K-)

通过求导数为0的点，得到K ＝ 17550元， ＝ 1765，S ＝ 2767元。

24