7.3某厂每月生产某种产品最多600件，当月生产的产品若未销出，就需贮存（刚入库的产品下月不付存储费）月初就已存储的产品需支付存储费，每100件每月1000元。已知每100件产品的生产费为5千元，在进行生产的月份工厂支出经营费4千元，市场需求如表7-19所示，假定1月初及4月底库存量为零，试问每月应生产多少产品，才能在满足需求条件下， 解： 设阶段变量：k=1,2,3 状态变量：k x 第k 个月初的库存量 决策变量：k d 第k 个月的生产量 状态转移方程：1k k k k x x r d 阶段指标：(,)k k k k v x d c d 由于在4月末，仓库存量为0，所以对于k=4阶段来说有两种决策： 5+4=9 40x 4()f x = 1 41x 对K=3 334()54()f x x f x K=2
解得：第一个月生产500份，第二个月生产600份，第三个月生产0份，第四个月生产0份。 7.4某公司有资金4万元，可向A ，B ，C 三个项目投资，已知各项目不同投资额的相应效益值如表7-20所示，问如何分配资金可使总效益最大。 表 7-20 解： 设阶段变量k ，{ }4,3,2,1∈k ，每一个项目表示一个阶段;
状态变量S k，表示可用于第k阶段及其以后阶段的投资金额； 决策变量Ｕk，表示在第k阶段状态为S k下决定投资的投资额； 决策允许集合：0≤Ｕk≤S k 状态转移方程：S k+1=S k-Ｕk; 阶段指标函数：V k(S kＵk)； 最优指标函数：f k(S k)=max{ V k(S kＵk)+ f k+1(S k+1)} 终端条件：f4(x4)=0； K=4, f4(x4)=0 k=3, 0≤Ｕ3≤S3 k=2, 0≤Ｕ2≤S2 k=1, 0≤Ｕ1≤S1 所以根据以上计算，可以得到获得总效益最大的资金分配方案为（1，2，1）.
习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）： （1） 用逆推解法；2用标号法。 7.2 用动态规划方法求解下列问题 （1） max z ＝x 12x 2 x 33 x 1＋x 2＋x 3 ≤6 x j ≥0 （j ＝1,2,3） （2）min z ＝ 3x 12＋4x 22 ＋x 32 x 1x 2 x 3 ≥ 9 x j ≥0 （j ＝1,2,3） 7.3 利用动态规划方法证明平均值不等式： n n n x x x n x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。 7.4 考虑一个有m 个产地和n 个销地的运输问题。设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。 7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。 投 资 回 收 概 率 A 0 0.4 2000 0.6 B 1000 0.9 2000 0.1 7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大?
7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。 7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。 货物代号重量（吨）容积（立方米）价值（千元） 1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6 若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。 7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。 巡逻队数预期事故次数仓库 1 2 3 4 2 18 38 14 34 3 16 36 12 31 4 12 30 11 25 7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。 季度j生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨） 1 30 15.6 20 2 40 14.0 25 3 25 15.3 30 4 10 14.8 15 （1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。（均不用求解）
某厂每月生产某种产品最多600件，当月生产的产品若未销出，就需贮存（刚入库的产品下月不付存储费）月初就已存储的产品需支付存储费，每100件每月1000元。已知每100件产品的生产费为5千元，在进行生产的月份工厂支出经营费4千元，市场需求如表7-19所示，假定1月初及4月底库存量为零，试问每月应生产多少产品，才能在满足需求条件下， 解： 设阶段变量：k=1,2,3 状态变量：k x 第k 个月初的库存量 决策变量：k d 第k 个月的生产量 状态转移方程：1 k k k k x x r d 阶段指标：(,)k k k k v x d c d 由于在4月末，仓库存量为0，所以对于k=4阶段来说有两种决策： 5+4=9 40x 4()f x = 1 41x 对K=3 334()54()f x x f x K=2
K=1时 d 5 解得：第一个月生产500份，第二个月生产600份，第三个月生产0份，第四个月生产0份。 某公司有资金4万元，可向A ，B ，C 三个项目投资，已知各项目不同投资额的相应效益值如表7-20所示，问如何分配资金可使总效益最大。 表 7-20
解： 设阶段变量k ，{ }4,3,2,1∈k ，每一个项目表示一个阶段; 状态变量S k ，表示可用于第k 阶段及其以后阶段的投资金额； 决策变量Ｕk ，表示在第k 阶段状态为S k 下决定投资的投资额； 决策允许集合：0≤Ｕk ≤S k 状态转移方程：S k+1=S k -Ｕk ; 阶段指标函数：V k (S k Ｕk )； 最优指标函数：f k (S k )=max{ V k (S k Ｕk )+ f k+1(S k+1)} 终端条件：f 4(x 4)=0； K=4, f 4(x 4)=0 k=3, 0≤Ｕ3≤S 3 k=2, 0≤Ｕ2≤S 2 k=1, 0≤Ｕ1≤S 1
§4.2 凸函数和凸规划 1、凸函数及其性质 定义 4.2.1 设n R S ?是非空凸集，R S f α:，如果对任意的)1,0(∈α有 )()1()())1((2121x f x f x x f αααα-+≤-+，S x x ∈?21, 则称f 是 S 上的凸函数，或 f 在 S 上是凸的。如果对于任意的)1,0(∈α有 )()1()())1((2121x f x f x x f αααα-+<-+，21x x ≠ 则称f 是S 上的严格凸函数，或f 在S 上是严格凸的。若 f -是S 上的（严格）凸函数，则称f 是S 上的（严格）凹函数，或f 在S 上是（严格）凹的。 例 4.2.1 线性函数既是凸函数，又是凹函数 定理 4.2.1 设n R S ?是非空凸集。 （1）若R R f n α:是S 上的凸函数，0≥α，则f α是S 上的凸函数； （2）若R R f f n α:,21都是S 上的凸函数，则21f f +是S 上的凸函数。 定理 4.2.2 设n R S ?是非空凸集，R R f n α:是凸函数，R c ∈，则集合 }{c x f S x c f H S ≤∈=)(),( 是凸集。（称集合),(c f H S 为函数 f 在集合 S 上关于数 c 的水平集） 证：任取),,(,21c f H x x S ∈ 则有S x S x ∈∈21,以及 c x f c x f ≤≤)(,)(21 因为S 是凸集，所以对于任意的)1,0(∈α有 S x x ∈-+21)1(αα 又因为f 是S 上的凸函数，因此有 c c c x f x f x x f =-+≤-+≤-+)1()()1()())1((2121αααααα
《运筹学》第五章习题及答案 《运筹学》第五章习题 1．思考题 （1）试述动态规划的“最优化原理”及它同动态规划基本方程之间的关系。（2）动态规划的阶段如何划分？ （3）试述用动态规划求解最短路问题的方法和步骤。 （4）试解释状态、决策、策略、最优策略、状态转移方程、指标函数、最优值函数、边界函数等概念。 （5）试述建立动态规划模型的基本方法。 （6）试述动态规划方法的基本思想、动态规划的基本方程的结构及正确写出动态规划基本方程的关键步骤。 2．判断下列说法是否正确 （1）动态规划分为线性动态规划和非线性动态规划。 （2）动态规划只是用来解决和时间有关的问题。 （3）对于一个动态规划问题，应用顺推法和逆推法可能会得到不同的最优解。 （4）在用动态规划的解题时，定义状态时应保证各个阶段中所做的决策的相互独立性。 （5）在动态规划模型中，问题的阶段等于问题的子问题的数目。（6）动态规划计算中的“维数障碍”，主要是由于问题中阶段数的急剧增加
而引起的。 3．计算下图所示的从A到E的最短路问题 4．计算下图所示的从A到E的最短路问题 5．计算从A到B、C、D的最短路线。已知各线段的长度如下图所示。 6．设某油田要向一炼油厂用管道供应油料，管道铺设途中要经过八个城镇，各 城镇间的路程如下图所示，选择怎样的路线铺设，才使总路程最短？
7．用动态规划求解下列各题 （1）．2 22211295m a x x x x x z-+-=； ?? ?≥≤+0,52 121x x x x； （2）． 3 3 221m a x x x x z= ?? ?≥≤++0,,6321 321x x x x x x； 8．某人外出旅游，需将3种物品装入背包，但背包重量有限制，总重量不超过 10千克。物品重量及其价值等数据见下表。试问每种物品装多少件，使整个背包的价值最大？ 913千克。物品重量及其价值的关系如表所示。试问如何装这些物品，使整个背包价值最大？
１８９ 习题七7.1计算如图所示的从A 到E 的最短路线及其长度（单位：km ）： （1） 用逆推解法；2用标号法。 7.2 用动态规划方法求解下列问题 （1） max z ＝x 12x 2 x 33 x 1＋x 2＋x 3 ≤6 x j ≥0 （j ＝1,2,3） （2）min z ＝ 3x 12＋4x 22 ＋x 32 x 1x 2 x 3 ≥ 9 x j ≥0 （j ＝1,2,3） 7.3 利用动态规划方法证明平均值不等式： n n n x x x n x x x 12121)()( ≥+++ 设x i ≥0，i ＝1，2，…，n 。 7.4 考虑一个有m 个产地和n 个销地的运输问题。设a i （i ＝1，2，…，m ）为产地i 可发运的物资数，b j （j ＝1，2，…，n ）为销地j 所需要的物资数。又从产地i 到销地j 发运x ij 单位物资所需的费用为h ij （x ij ），试将此问题建立动态规划的模型。 7.5 某公司在今后三年的每一年的开头将资金投入A 或B 项工程，年末的回收及其概率如下表所示。每年至多做一项投资，每次只能投入1000万元。求出三年后所拥有的期望金额达到最大的投资方案。 投 资 回 收 概 率 A 0 0.4 2000 0.6 B 1000 0.9 2000 0.1 7.6 某公司有三个工厂，它们都可以考虑改造扩建。每个工厂都有若干种方案可供选择，各种方案的投资及所能取得的收益如下表所示(单位：千万元)。现公司有资金5千万元，问应如何分配投资使公司的总收益最大?
7.7 某厂准备连续3个月生产A种产品，每月初开始生产。A的生产成本费用为x2，其中x是A产品当月的生产数量。仓库存货成本费是每月每单位为1元。估计3个月的需求量分别为d1＝100，d2＝110，d3＝120。现设开始时第一个月月初存货s0＝0，第三个月的月末存货s3＝0。试问：每月的生产数量应是多少才使总的生产和存货费用为最小。 7.8 设有一辆载重卡车，现有4种货物均可用此车运输。已知这4种货物的重量、容积及价值关系如下表所示。 货物代号重量（吨）容积（立方米）价值（千元） 1 2 2 3 2 3 2 4 3 4 2 5 4 5 3 6 若该卡车的最大载重为15吨，最大允许装载容积为10立方米，在许可的条件下，每车装载每一种货物的件数不限。问应如何搭配这四种货物，才能使每车装载货物的价值最大。 7.9 某警卫部门有12支巡逻队负责4个仓库的巡逻。按规定对每个仓库可分别派2－4支队伍巡逻。由于所派队伍数量上的差别，各仓库一年内预期发生事故的次数如下表所示。试应用动态规划的方法确定派往各仓库的巡逻队数，使预期事故的总次数为最少。 巡逻队数预期事故次数仓库 1 2 3 4 2 18 38 14 34 3 16 36 12 31 4 12 30 11 25 7.10 （生产计划问题）根据合同，某厂明年每个季度末应向销售公司提供产品，有关信息见下表。若产品过多，季末有积压，则一个季度每积压一吨产品需支付存贮费0.2万元。现需找出明年的最优生产方案，使该厂能在完成合同的情况下使全年的生产费用最低。 季度j生产能力a j（吨）生产成本d j（万元/吨）需求量b j（吨） 1 30 15.6 20 2 40 14.0 25 3 25 15.3 30 4 10 14.8 15 （1）请建立此问题的线性规划模型。（提示：设第j季度工厂生产产品x j吨，第j季度初存贮的产品为y j吨，显然y1＝0）（2）请建立此问题的动态规划模型。（均不用求解） １９０
《运筹学》各章的作业 ----复习思考题及作业题 第一章绪论 复习思考题 1、从运筹学产生的背景认识本学科研究的内容和意义。 2、了解运筹学的内容和特点，结合自己的理解思考学习的方法和途径。 3、体会运筹学的学习特征和应用领域。 第二章线性规划建模及单纯形法 复习思考题 1、线性规划问题的一般形式有何特征？ 2、建立一个实际问题的数学模型一般要几步？ 3、两个变量的线性规划问题的图解法的一般步骤是什么？ 4、求解线性规划问题时可能出现几种结果，那种结果反映建模时有错误？ 5、什么是线性规划的标准型，如何把一个非标准形式的线性规划问题转化成标准形式。 6、试述线性规划问题的可行解、基础解、基础可行解、最优解、最优基础解的概念及它们之间的相互关系。 7、试述单纯形法的计算步骤，如何在单纯形表上判别问题具有唯一最优解、有无穷多个最优解、无界解或无可行解。 8、在什么样的情况下采用人工变量法，人工变量法包括哪两种解法？ 9、大M 法中，M 的作用是什么？对最小化问题，在目标函数中人工变量的系数取什么？最大化问题呢？ 10、什么是单纯形法的两阶段法？两阶段法的第一段是为了解决什么问题？在怎样的情况下，继续第二阶段？ 作业题: 1、把以下线性规划问题化为标准形式： (1) max z= x1-2x2+x3 s.t. x1+x2+x3≤12 2x1+x2-x3≥ 6 -x1+3x2＝9 x1, x2, x3≥0 (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
第1讲数学与系统科学学院 优化理论第1讲凸集与凸函数 凸集与凸函数 数学与系统科学学院 优化理论第1讲凸集与凸函数 凸集 称中的集合C 是凸的(convex)，如果对每个个 ，点. 数学与系统科学学院优化理论第1讲凸集与凸函数 称集合C 是锥(cone)，如果蕴含着对所有有. 若锥C 还是凸的，称为凸锥(convex cone). 一些重要的凸集 有限个闭半空间的交集 超平面(hyperplane):数学与系统科学学院 优化理论第1讲凸集与凸函数 推 广 平面上：多边形 注：线性规划问题的可行集是多面集！ 几何上：数学与系统科学学院 优化理论第1讲凸集与凸函数 极点即不能位于连接该集合中其它两点的开线段上的点 定义称凸集C 中的点x 是C 的极点，如果存在C 中的点y, z 和某，有则必有y=z. 重要应用：线性规划的基本性质！ 线性规划解的几何特征 数学与系统科学学院 优化理论第1讲凸集与凸函数 可以在极点取到极值！
数学与系统科学学院优化理论第1讲凸集与凸函数 无(下)界 无解(-1, -1)一条边( 1, 0)一条边 ( 0, 1) 惟一的顶点 ( 1, 1)解的几何特征 x* c 11(,0), 0 ≥x x (0, 0) 22(0, ), [0, 1]∈x x 点与闭凸集的分离定理及应用 给定中的向量 令分离定理.存在超平面 分离闭凸集C 和非零向量. 数学与系统科学学院 优化理论第1讲凸集与凸函数 Farkas 引理.集合 是空集当且仅当存在 使得 给定中的向量 . 推论.集合 数学与系统科学学院 优化理论第1讲凸集与凸函数 是空集当且仅当存在使得 数学与系统科学学院 优化理论第1讲凸集与凸函数 定 义定义 相关定义：严格凸函数、凹函数/严格凹函数 数学与系统科学学院 优化理论第1讲凸集与凸函数 Jensen 不等式：见作业1.10 命题. 若f i (x), i =1,…,m ，是凸集K 上的凸函数，则它们的非 负线性组合仍然是K 上的凸函数.定理1. 凸函数在凸集上的局部极小点是全局极小点. f 是凸集K 上的可微实值函数，对所有的，有定理f f 可微凸，则f 的稳定点是它的全局极小点数学与系统科学学院 优化理论第1讲凸集与凸函数 设f 是开凸集K 上的二次连续可微实值函数，则f 凸当且仅当对K 中的每个x 而言，是半正定的.