运筹学实用教程(宁宣熙).ppt

运营规划学实用教程(第二版)第二部分：目标规划、动态规划、制作部门：南京航空航天大学经济与管理学院制作人：宁工程师宁宣熙，2004年6月， 第二章目标计划2.1目标计划的数学模型目标计划的基本概念目标计划的数学模型目标优先级问题2.2目标计划的简单形式法目标计划简单形式法特征目标计划的简单形式法要点，第一节目标计划的数学模型，目标计划的基本概念目标计划的数学模型目标优先级问题，第一、目标计划的基本概念，管理工作中始终例如，图2-1，解决方法可以通过将一些约束条件(例如，后两个条件)看作管理目标来确定目标函数的目标直线a，修改定义目标偏差变量的目标函数以使得目标函数值不小于a，以及2，目标规划的数学模型在给定线性规划中具有m个目标函数以及偏差变量(可能是正的和负的) 与实例1-1相比，目标规划模型实例1-1的目标规划在汽车制造商的要求利润达到2600千元时，对应的目标规划在其它情况下进行处理，目标不相等，在尽可能超过目标时，偏差分别只取负偏差。 举例来说，如果在约束下为目标函数，那么所述其它处理在给定目标不等于给定目标且尽可能不超过给定目标时仅分别取正偏差。 举例来说，如果在约束条件下目标函数为真，那么其它处理仅分别取负偏差或正偏差(如果目标必须小于给定目标)。 例如，如果是制约条件下的目标函数，则进行其他情况下的处理，例如，如果是制约条件下的目标函数，则例1-1要求尽可能保证有效工时2500小时、三天、目标的优先级，在多个目标的重要度不同的情况下，能够以权重Pj表示各目标的优先级， 并且假定是将权重与偏差相乘来构成目标函数，则能够保证权重越大，越强制相应的偏差成为零，最初实现优先级高的目标。 例1-1的目标优先顺序如下，优先顺序依次降低：充分利用总利润为2600千元的轿车产量不超过300辆的保证有效工时2500小时，避免开工不足钢材的消费量超过库存量，采用相应的数学模型，第二节目标计划的简单形法， 目标计划单纯形法的特征目标计划的单纯形法目标计划单纯形法的要点之一，目标计划单纯形法的特征在于目标函数中只有偏差变量，它们和最小目标函数的“价值系数”一般是优先级的权重，因此检验常数不是一行，而是m行。 在m行的检查数中，从上到下，按照优先级从高到低的顺序排列。 求解时，首先满足优先级高的变量。 二、目标规划的简单形法、初始简单形表、第一次迭代、第三次迭代、最优解、非基变量的检验常数均小于零，因此得到最优解的只有第二目标值不完全满足，偏差为100，即大型车只生产200辆。 例2-1，某电视厂生产46厘米和51厘米两种电视机，平均生产能力为1台/小时，普通每天双班，每周80小时。 下周的最大销量是46厘米70台，51厘米35台。 每销售46厘米的收益250元，51厘米的150元，就会决定最佳的生产计划。 公司长安的重要程度规定了以下目标：避免开工不足，维持员工就业稳定，尽量减少加班，努力在每周10小时内加班达到预定销售量，给学生们写数学模型，第一个简单的表格，第一次反复，第二次反复，第三次反复，最优解，学生们上一步的检验数，最优解最佳答案：因此，加班10小时(加班不少)，51厘米的彩色电视机生产量少15台，未能达到预期的销售目标。 三、目标规划单纯形法的要点，约束方程的负偏差是初始基变量。检查数据用单纯的表现为行列形式，占有m行，按照优先顺序排列。 如果选择了转换变量，则在优先级最高的行中检索正检查数，如果最高检查数相同，则比较下一个最高检查数。 选择变换变量时，如果有多个最小正比，则选择优先级高的变量变换。 只要各变量的检验公式中最上位的权重系数小于零，就得到最佳解。 第一节动态规划的基本概念和方法，基本概念和名词解释优化原理和动态规划的基本方法，一、基本概念和名词解释，例3-1某公司想从城市a向城市e运输货物，如图所示哪条路线最好？ 图3-1，用名词解释，阶段，k表示。 状态变量用Sk表示，通常为集合决定变量，通常用uk或xk表示。 状态转移及其方程：过程和子过程策略：指标函数和最优值函数：二、优化原理和动态规划的基本方法、贝尔曼原理动态规划的基本方法逆序法顺序法、贝尔曼原理图、逆序法算例3-2、第二节动态规划建模和计算过程、动态规划模型的基本要求动态规划的某些问题逐步明显，某些问题不明显，分析后需要人为假设。 确定各阶段的状态变量，给出状态转移方程。 状态转移方程的形式必须与递归顺序一致。 状态变量必须满足事后的要求。 明确了指标函数，给出了最优函数的递归方程，递归方程的形式必须与递归顺序一致。 二、动态规划求解程序，准确划分阶段。 决定状态变量和决策变量，给出状态变量和决策变量的可行集合。 确定求解的递归顺序，给出状态转移方程。 阶段确定子过程(子策略)的指标函数，确定最优值函数的递归方程和边界条件。 递归求解。 求出与递归过程相反的最优策略(最优决定变量值系列)和最优状态变化路径。 第三节动态规划应用实例，价格问题资源分配问题生产记忆问题，一、价格问题，某公司考虑某新产品的价格，该产品的单价预计从各部件的5元、6元、7元和8元四项中选出一项，每年价格有1元幅度的变动，预计该产品将销售5年，不同价格下的年利润表3-2构建每年预期的利润额、数学模型，按年分级，k=1、2、5各阶段的状态变量为本年度(前年确定)的价格、状态变量的可执行集合sk=(5、6、7、8 )。 决策变量是每年根据当年价格在下年度决定价格的，问题决策变量的可能集合采用逆序算法，因此状态转移方程式是最佳值函数递归方程式，进行各阶段的计算，采用逆序法，k=5时，s5=(5，6，7，8 )从表3-1得到k=4时，s4=(5，6，7，8 ) 7、8 )是从递归方程式得到的，按照与求最佳值函数的方向相反的顺序求最佳状态路线：最佳决定变量。 也就是说，第一年度的单价应该是8元，往后推算。 第二年的价格是八元，第三年的价格是七元，第四年的价格是六元，第五年的价格是五元。 最大利润值为92万元。运用决策图求解，二、资源分配问题，某公司将5台加工中心分配给甲、乙、丙、丁四个工厂，各工厂和设备后可产生如表3-2所示的效益。 如何分配设备会使公司的总利润最大？ 建立数学模型，按工厂顺序划分阶段，k=1、2、3、4状态变量被分配给各阶段的设备总台数决定变量，当被分配给第k工厂的设备数为逆序算法、状态转移方程式的最佳值函数递归方程式、第4阶段的最佳解、k=4时，s4=(0、1、2、3、4、5 )，第3阶段的最佳解在k=3的情况下，S3=(0，1，2 )第三阶段的最佳解(续)，在k=3的情况下，S3=3，第三阶段的最佳解(续)，在k=3的情况下，S3=4，第三阶段的最佳解(续)，在k=3的情况下，S3=5，第二阶段的最佳解，在k=2的情况下，S2=(0，1， 2 )、第二阶段的最佳解(续)、k=2时S2=3、第二阶段的最佳解(续)、k=2时S2=4第二阶段的最佳解(续)、k=2时S2=5、第一阶段的最佳解(续)、k=1时S1=5、第四阶段的最佳解、k=4时s4=(0、1、2、3、4 ) 根据市场预测，今后4个月的市场需求量如表3-7所示。 众所周知，其他条件是产品生产成本为1000元，产品每批生产准备成本为3000元，每月只能生产1批，每批只能生产6件。 每件的保管成本为0.5千元，第一个月初没有库存，第四个月末的库存要求为零。 寻求最佳(最低成本的)生产和存储计划。 设第k月的产量uk、蓄积量Sk，总成本构筑数学模型，按月划分阶段，设k=1、2、3、4的各阶段的决定变量为该阶段的产量uk，状态变量为该阶段的蓄积量Sk。 若采用逆序算法，则状态转移方程式为最低成本递归式，在第四阶段最佳解、k=4的情况下，d4=4，土地的四阶段末端没有库存，因此s4=(0，1，2，3，4 )，在第三阶段的最佳解、k=3的情况下，第三阶段的需求量d3=2，s3=(0，1，2，3，4，5， 6 )、第三阶段最佳解：S3=1第三阶段最佳解：S3=2、第三阶段最佳解： s3=3，4、第三阶段最佳解3360 s3=5，6、第二阶段最佳解k=2时，因为d2=3、最佳能力为6、d1=2，所以s2=(0，1，2，3， 4 )、第二阶段优化解：S2=1、第二阶段优化解：S2=2、第二阶段优化解：S2=3、第二阶段优化解：S2=4、第一阶段优化解k=1时，从d1=2、S1=0、最佳解、第一阶段开始反向按压最佳路由进行汇总， 计划用它装载3种货物，各货物的单位重量和相应的单位价值如表313所示。 如何使总价值达到最大？ 试解动态规划方法。 表3-13，解：若将装载第I种货物件数设为(I=1，2，3 )，则该问题的整数线性规划方程式为：0，为整数(I=1，2，3 )。 根据、动态规划要求，确定以下参数，将装载问题分为3个货物，并分各阶段装载货物。 各阶段的状态参数为在各阶段也能装载的重量。 各阶段的决定变量为该阶段装载的货物数量。 决定变量的容许集合，状态迁移方程式：阶段指标函数：=边界条件， (1)设备更新问题今后每5年分为K=5个阶段。 (2)将各阶段的状态参数作为第k年的开始，设备使用的年数为= 0，1，2，3，4，5 。(3)每个阶段的决定变量为2个： (保留)或(更新) (4)状态转移方程式：(5)阶段指数函数： (6)最佳指标函数：以下，K=5，s5=(1，2，3，4 )，K=4，s4=(1，2，3 )， 表3-19第四阶段计算表3-20第三阶段计算表，K=3，s3=(1，2 )，表3-21第二阶段计算表，表3-22第一阶段计算表，6可靠性问题，某些电子系统串联连接，其中一个部件发生故障，系统整体发生故障。 为了提高系统整体的可靠性，各部件可以并联连接同一部件进行设计。 例如，部件1可以由多个元件并联连接而构成。 由此，部件1的可靠性提高，但同时成本也增加。 那么，在系统整体的成本为定额的情况下，如何设计并列方式(即各部件分别在几个相同的部件中并列)使系统整体的可靠性最大化是系统可靠性的优化的问题。 可以使用以下非线性规划模型来描述这种问题。表3-24在成本表、可靠性问题的非线性规划模型中，根据整数、i=1、2.n.动态规划要求确定以下参数，(1)根据构成系统的部件数量，动态规划有四个阶段，即k=4(2)每个阶段的状态参数是每个阶段可用的总成本换句话说，阶段k允许的总费用。 (3)各阶段的决定变量是第k个部件所采用的部件数。 (4)状态转移方程式进行(5)最优指数函数(6)边界条件、以下各段的计算时，k=4、表3-25第4阶段计算表k=4、表3-26第3阶段计算表k=3、表3-26第3阶段计算表k=3(续)、表3-27第2阶段计算表k=2， 表3-27第二阶段计算表k=2(接下来)表3-28由于第一阶段计算表k=1，所以优化决定：完，优化原理的图像，图3-2，例3-1的映射表记法，图3-3，表3-1，表3-2，例3-2决定图，图3-4，表3-4，表3-5，表3-6，表3-7，表3-7 表3-10，表3-11，表3-12， 图4-1图4-2、图4-3、图4-4、图4-5、图4-6、图4-7、图4-8、图4-9、图4-10、图4-11、图4-12、图4-13、图4-14、图4-15、图4-15、最小费用流程曲线、图4-16、f(0)=0时的网络图、图4-17、(r ) f(1)=5时的网络图4-18、f(2)=8时的网络图、图4-19、f(3)=9时的网络图、图4-20、哥白尼七桥问题、图4-21、奇偶校验图作业方法、图4-22、具有4个特点图的中国邮递员问题、图4-23、 图4-24、图4-25、图4-26、图4-27、图4-28、图4-29、图4-30， 图4-31图4-32、图4-33、表4-1、图4-34、图4-35、图4-36、图4-37、图4-38、图4-39、图4-40、表4-2、表4-3、图4-41、图4-42、图4-43、图4-44、表4-4、图4-45、图4-50 图4-53，图4-54，图4-55，图4-56，图4-57，图4-58，图4-59，图4-60，决策程序和相关技术，图5-1，图5-2，浴槽曲线，表