管理运筹学-管理科学方法.ppt

管理运筹学 -管理科学方法,谢家平 博士 教授 博士生导师 研究领域：管理科学、运营管理、供应链管理 讲授课程：管理运筹学-管理科学方法、管理系统工程、 运营管理、 供应链管理、ERP、国际物流、 企业物流管理、管理决策模型与方法 单 位：上海财经大学工商学院 物流管理系 E-mail：jiapingmail.shufe.edu.cn,2,教材与参考书籍,教材： 谢家平编著.管理运筹学：管理科学方法， 中国人民大学出版社，2010 参考书： David et al. 数据、模型与决策，机械工业出版社，2004 费雷德里克. 数据、模型与决策，中国财政经济出版社，2004 James et al. 数据、模型与决策，中国人民大学出版社，2006,3,32课时讲授提纲,绪 论 第一章 线性规划 第二章 线性规划讨论 第三章 对偶规划 静态规划 第四章 整数规划 第五章 目标规划 第六章 动态规划 动态优化 第七章 网络分析 第八章 网络计划 第九章 决策分析 第十章 方案排序 第十一章 库存控制 第十二章 排队理论,离散优化,随机优化,淡化数学算法 LINDO求解,4,考核方式,结课考试： 笔试（开卷 or 闭卷？） 每章一题 80% 案例研究： 选择合适方法结合企业实际进行应用 20%,5,管理运筹学的称谓,管理运筹学是一门研究如何最优安排的学科。 Operations Research 日本译作“运用学” 香港、台湾译为“作业研究” 我国译作“运筹学” 源于古语“运筹帷幄之中，决胜千里之外” 取“运筹”二字，体现运心筹谋、策略取胜 Management Science 管理科学 运用数学、统计学和运筹学中的量化分析原理和方法，建立数学模型/计算机仿真，给管理决策提供科学依据。,6,绪 论,一、发展历史 二、学科作用 三、学科性质 四、工作程序 五、学科体系 六、学习要求,7,一、发展历史,1. 早期的运筹思想 齐王赛马 渭修皇宫 沈括运军粮 科学管理 2. 军事运筹学阶段 20世纪40年代诞生于英美 1940年，英国为对付德国空军的空袭，使用了雷达，但没有科学布局，效果不好。为解决这个问题，成立运筹学小组，称Operational Research，意为作战研究。 美国和加拿大也在军队设立运筹学小组，称Operations Research，协助指挥官研究战略及战术问题。 3. 管理运筹学阶段 战后许多从事运筹学研究的科学家转向了民用问题的研究，使运筹学在企业管理方面的应用得到了长足进展。,8,企业的成功要素中： 观念意识更新 47 人文文化 35 技术优势 18 决策意识的科学性 成功决策 正确决策,二、学科作用,理念的重要性,？,9,二、学科作用,1. 量化管理的重要性 管理科学是对与定量因素有关的管理问题通过应用科学的方法进行辅助管理决策的一门学科。 目的：用科学方法分析管理问题，为管理者决策提供依据 目标：在企业经营内外环境的限制下，实现资源效用最大,量化管理是第一步,它导致控制,并最终实现改进 如果不能量化某些事情，那么就不能理解它 如果不能理解它，那么就不能控制它 如果不能控制它，那么就不能改进它 H. James Harrington,定性到定量分析，数量界限的重要性：量变引起质变,10,听一场音乐会：网络订票的票价500元，不去可退票 情况1：在你马上要出发的时候，发现你把最近的价值500元的电话卡弄丢了。你是否还会去听这场音乐会？ 情况2：假设昨天花500元钱买一张今晚的音乐会取票单。在你出发时，发现把票单丢了。如果去听音乐会，就必须再花500元钱买张票，去还会不去？,二、学科作用,2. 量化思考使人理性 冰淇淋实验： 一杯A有70克，装在50克的杯子里，看上去要溢出了 一杯B是80克，装在100克的杯子里，看上去还没装满,单独凭经验判断时，在相同的价格上，人们普遍选择A,实验表明，大部分的回答者仍旧会去听,结果却是，大部分人回答说不去了,11,二、学科作用,3. 量化分析辅助决策 盈亏平衡分析,利润：I = ( P Cm Ch ) Q - F 策略1 差异化，领先者战略 策略2 规模化，大规模市场 策略3 机械化，第一利润源 策略4 技能化，第二利润源 策略5 信息化，第三利润源,12,二、学科作用,量化辅助决策案例：盈亏平衡分析 例：某企业 总销售额 1100万元 物料成本 700万元 员工工资 200万元 管理费用 100万元 现在利润=100万元，目标利润150万元,利润实现的方法有： 将销售收入增加100% 将员工工资减少 25% 将管理费用减少 50% 将物料成本减少 7.1%,13,二、学科作用,4. 决策意识的重要性 生产计划决策,一星期工作5天, 每天正常工作8小时 一周作业费用：11000 (直接人工成本与间接费用) 直接人工成本：10/1h (一台机器需一位作业人员) 间接费用：人工成本2.5倍,14,二、学科作用,甲产品产量40, 乙产品 80, 丙产品 40 利润=40×66+80×89+40×70=12560 人员有限如何实现?采取什么薪酬制度? 计件工资制，让员工自愿加班,决策的科学性？方案 一,15,二、学科作用,甲产品产量 40, 乙产品 80, 丙产品 40 总收入=40×173+80×233+40×170=32360 原料成本=40×65+80×95+40×65=12800 营运费用=11000 总利润=32360-12800-11000=8560 人员有限如何实现?采取什么薪酬制度? 岗位工资制（定岗定员），让员工自觉加班,决策的科学性？方案 二,16,二、学科作用,决策的科学性？产能符合计算,乙与丙哪一个产品比较赚钱?,E是瓶颈,17,二、学科作用,方案 三：计时工资，且以单位利润率高低为决策意识。 乙比较赚钱, 假如80个全部生产 需用E产能2400分钟，但是E只有2400分钟可用 因此只能生产80个乙 (2400/30)，而丙无法生产,方案：甲产品 40个，乙产品80个，丙产品0个 总收入=40×173+80×233+0×170=25560 原料=40×65+80×95+0×65=10200 ，营运费用=11000 利润=25560-10200-11000=4360,方案 四：计时工资，但以占用瓶颈资源大小为决策意识。 丙比较赚钱, 优先生产40个 需用E产能600(4015)分钟 剩下1800分钟, 可生产60个乙 (1800/30),方案：甲产品 40个，乙产品 60个，丙产品 40个 总收入=40×173+60×233+40×170=27700 原材料=40×65+60×95+40×6540=10900 ，营运费用=11000 利润=27700-10900-11000=5800,18,三、学科性质,1. 研究对象 经济和管理活动中能用“数量关系”描述的 如运营、规划与组织管理问题 解决的理论模型和优化方法实践 2. 学科特点 强调科学性和定量分析 强调应用性和实践性 强调从整体上进行把握,19,四、工作程序,20,五、学科体系,1. 管理问题,21,五、学科体系,2. 学科内容,22,五、学科体系,3. 学科应用 管理既是科学又是艺术 低层管理的科学成分较多，高层管理的艺术成分较多 运营管理需较多管理科学，人力资源管理需较多管理艺术 例行管理需要较多管理科学，例外管理需要较多管理艺术,M: 管理决策问题,MC: 定量解决方法,方案选择依据,问题导向,技术支持,战略决策 营销决策 生产安排 财务分析 人力资源 方案优选 ,应用统计 线性规划 整数规划 目标规划 网络计划 网络分析 决策分析 动态规划 ,管理科学：运用合理的分析来改善决策的制定,管理者: 制定决策,23,六、学习要求,1. 学科地位,24,六、学习要求,经济学,企业战略、公司治理,会计学 财务管理,人力资源管理组织行为学,管理 科学 方法 支持,25,六、学习要求,2. 如何学习,重点在结合实际的应用 发挥自己管理实践经验丰富和理论联系实际的能力 强化结合实际问题建立管理优化模型的能力 强化解决问题的方案或模型的解的分析与应用能力 充分借用管理运筹学教学软件,26,第1 章 线性规划,Sub title,内容提要,第一节 线性规划的一般模型 一、线性规划的三个要素 二、线性规划模型的特征 三、线性规划的图解方法 四、线性规划解的可能性 第二节 线性规划的单纯形法 一、线性规划的标准型式 二、线性规划之解的概念 三、单纯形法的基本原理,27,一、线性规划的三个要素,第一节 线性规划的一般模型,决策变量 决策问题待定的量值 取值要求非负 约束条件 任何管理决策问题都是限定在一定的条件下求解 把各种限制条件表示为一组等式或不等式称约束条件 约束条件是决策方案可行的保障 约束条件是决策变量的线性函数 目标函数 衡量决策优劣的准则，如时间最省、利润最大、成本最低 目标函数是决策变量的线性函数 有的目标要实现极大，有的则要求极小,28,二、线性规划模型的举例,第一节 线性规划的一般模型,1、生产计划问题,例. 某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利润为最大。 据市场分析，单位甲乙产品的销售价格分别为73和75元，试确定获利最大的产品生产计划。,29,第一节 线性规划的一般模型,(1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。 (2)约束条件：生产受设备能力制约，能力需求不能突破有效供给量。 设备A的约束条件表达为 2 x1 16 同理，设备B的加工能力约束条件表达为 2x2 10 设备C的装配能力也有限，其约束条件为 3x1+ 4x2 32 (3)目标函数：目标是企业利润最大化 max Z= 3x1 +5x2 (4)非负约束：甲乙产品的产量为非负 x1 0， x2 0,综上的LP模型：,30,二、线性规划模型的举例,第一节 线性规划的一般模型,2、物资运输问题,例：某产品商有三个供货源A1、A2、A3，其经销商有4个（需求市场）B1、B2、B3、B4。已知各厂的产量、各经销商的销售量及从Ai 到Bj 的单位运费为Cij。为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。,31,第一节 线性规划的一般模型,(1)决策变量：设从Ai到Bj的运输量为xij， (2)目标函数：运费最小的目标函数为 minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34 (3)约束条件：产量之和等于销量之和,故要满足： 供应平衡条件,x11+x12+x13+x14=50 x21+x22+x23+x24=20 x31+x32+x33+x34 =30,销售平衡条件,x11+x21+x31=20 x12+x22+x32=30 x13+x23+x33=10 x14+x24+x34=40,非负性约束 xij0 (i=1,2,3；j=1,2,3,4),32,二、线性规划模型的举例,第一节 线性规划的一般模型,3、产品配比问题,例：用浓度45%和92%的硫酸配置100吨浓度80%的硫酸。,决策变量：取45%和92%的硫酸分别为 x1 和 x2 吨 约束条件：,求解二元一次方程组得解,非负约束： x1 0， x2 0,33,第一节 线性规划的一般模型,若有5种不同浓度的硫酸可选(30%,45%,73%,85%,92%)会如何呢？,取这5种硫酸分别为 x1、x2、x3、x4、x5 ，有,有多少种配比方案？ 何为最好？,若5种硫酸价格分别为400, 700, 1400, 1900, 2500元/t，则：,34,三、线性规划模型的特征,第一节 线性规划的一般模型,1、模型隐含假定,（1）线性化假定 函数关系式f(x)= c1x1+c2x2+ +cnxn，称线性函数。 建模技巧：将非线性的函数进行分段线性化。 （2）同比例假定 决策变量变化引起目标函数和约束方程的改变量比例。 （3）可加性假定 决策变量对目标函数和约束方程的影响是独立于其他变量的。 目标函数值是决策变量对目标函数贡献的总和。 （4）连续性假定 决策变量取值连续。 （5）确定性假定 所有参数都是确定的，不包含随机因素。,35,三、线性规划模型的特征,第一节 线性规划的一般模型,2、一般数学模型,用一组非负决策变量表示的一个决策问题； 存在一组等式或不等式的线性约束条件； 有一个希望达到的目标，可表示成决策变量的极值线性函数。,36,四、线性规划的图解方法,第一节 线性规划的一般模型,1、线性规划的可行域,可行域：满足所有约束条件的解的集合， 即所有约束条件共同围城的区域。,maxZ= 3x1 +5 x2 2 x1 16 2x2 10 3x1 +4 x2 32 x1 0, x2 0,S.t.,37,四、线性规划的图解方法,第一节 线性规划的一般模型,2、线性规划的最优解,目标函数 Z= 3x1 +5 x2 代表以 Z 为参数的一族平行线。,38,四、线性规划的图解方法,第一节 线性规划的一般模型,3、线性规划解的特性,由线性不等式组成的可行域是凸多边形(凸多边形是凸集) 凸集定义：集合内部任意两点连线上的点都属于这个集合,可行域有有限个顶点。 目标函数最优值一定在可行域的边界达到，而不可能在其区域的内部。,39,五、线性规划解的可能性,第一节 线性规划的一般模型,1、唯一最优解：只有一个最优点,2、多重最优解：无穷多个最优解,当市场价格下降到74元，其数学模型变为,40,五、线性规划解的可能性,第一节 线性规划的一般模型,3、无界解：可行域无界，目标值无限增大 (缺乏必要约束),41,五、线性规划解的可能性,第一节 线性规划的一般模型,4、没有可行解：线性规划问题的可行域是空集 (约束条件相互矛盾),42,一、线性规划的标准型式,第二节 线性规划的一般模型,1、标准型表达方式,(1)代数式,(2)向量式,(3)矩阵式,A：技术系数矩阵，简称系数矩阵； B：可用的资源量，称资源向量； C：决策变量对目标的贡献，称价值向量； X：决策向量。,43,一、线性规划的标准型式,第二节 线性规划的一般模型,2、标准型转换方法,(1)如果极小化原问题minZ=CX，则令 Z'=-Z，转为求 maxZ'=-CX (2)若某个bi0，则以1乘该约束两端，使之满足非负性的要求。 (3)对于型约束，则在左端加上一个非负松弛变量，使其为等式。 (4)对于型约束，则在左端减去一个非负剩余变量，使其为等式。 (5)若某决策变量xk无非负约束，令xk=x'k-x“k ，(x'k0,x“k 0) 。,44,二、线性规划之解的概念,第二节 线性规划的一般模型,基矩阵：一个非奇异的子矩阵（线性无关）。 矩阵A中任意m列的线性无关子矩阵B ，称为一个基。 组成基B的列为基向量，用Pj表示(j=1,2,n) 。 基变量： 与基向量Pj 相对应的m个变量xj称为基变量 其余的n - m个变量为非基变量,1、线性规划解之关系,基解：令所有非基变量等于零，得出基变量的唯一解 。,基变量是x3, x4, x5 非基变量是x1, x2 令非基变量x1=x2=0，得到一个基解 x3=16，x4=10， x5=32,45,二、线性规划之解的概念,第二节 线性规划的一般模型,1、线性规划解之关系,可行解：满足约束条件AX=b, X0的解。 可行基：可行解对应的基矩阵。 基可行解：满足非负性约束的基解称为基可行解。 最优解：使目标函数最优的可行解，称为最优解。 最优基：最优解对应的基矩阵，称为最优基。,46,二、线性规划之解的概念,第二节 线性规划的一般模型,2、线性规划基本原理,定理1. 若线性规划问题存在可行域，则其可行域一定是凸集。 定理2. 线性规划问题的基可行解对应可行域的顶点。 定理3. 若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。 定理4. 线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。,47,二、线性规划之解的概念,第二节 线性规划的一般模型,3、线性规划解题思路,先找到一个初始基可行解，也就是找到一个初始可行基，想办法判断这个基可行解是不是最优解。 如果是最优解，就得到这个线性规划问题的最优解； 如果判断出不是最优解，就想法由这个可行基按一定规则变化到下一个可行基，然后再判断新得到的基可行解是不是最优解； 如果还不是，再接着进行下一个可行基变化，直到得到最优解。,48,三、单纯形法的基本原理,第二节 线性规划的一般模型,maxZ=3x1 +5 x2 +0x3 +0x4+0x5 =0 2x1 + x3 =16 2x2 + x4 =10 3x1 +4 x2 + x5 =32,49,三、单纯形法的基本原理,第二节 线性规划的一般模型,最优解 :X*=(4,5,8,0,0)T，Z*=37,50,三、单纯形法的基本原理,第二节 线性规划的一般模型,单纯形的管理启示,2x1=16,X0=(0,0,10,10,32)T,X1=(0,5,10,0,12)T,X1=(4,5,8,0,0)T,企业管理过程也是如此，把现有方案作为初始方案，找到最急需要改进的某个问题和改进方向，一次做好某个主要问题的解决与改进；一次只解决和改进一个问题的难度最小；解决之后，再寻求可以改进的其它地方，再次改进，不断地追求完美。,51,第2 章 线性规划讨论,Sub title,内容提要,第一节 目标函数的描述技巧 计件工资 岗位工资 计时工资 第二节 线性规划的适用层次 第三节 线性规划的典型案例 第四节 线性规划灵敏度分析 价值系数的变动分析 资源数量的变动分析,52,计件工资体系，目标是企业利润最大化：,第一节 目标函数的描述技巧,一、计件工资,计件工资制薪酬体系下，工作时间不会完全受每天8小时工作时间约束，但有产品市场需求约束，如下：,经Lindo软件求解，得到最优解为Z=12560，产品甲x1=40，产品乙x2=80，产品丙x3=40。,53,第一节 目标函数的描述技巧,二、岗位工资,岗位工资制薪酬体系，以计时工资制为基础，实行定岗定员。 总收入=173x1+233x2+170x3， 原料成本=65x1+95x2+65x3，营运费用=11000， 则目标函数为maxZ= 108x1+138x2+105x3-11000 岗位工资制薪酬体系下，工作时间也不会完全受每天8小时工作时间约束，但有产品市场需求约束，如下：,经Lindo软件求解，得到最优解为Z=8560,x1=40,x2=80,x3=40。,54,第一节 目标函数的描述技巧,三、计时工资,目标函数为,经Lindo软件求解，得到最优解为Z=5800,x1=40,x2=60,x3=40。,市场需求约束,设备能力约束,55,第二节 线性规划的适用层次,计划链的层次,产值计划 或 利润计划 绝对数量 或 增长幅度 期限:年度 单位:万元,大类产品销售收入或台套 产品品种和数量如何确定 期限:年度 单位:万台,具体产品在具体 时段的出产计划 合同订单和预测 转换为生产任务,将产品出产计划转换成物料需求表,大类产品年度生产计划 确定产品的品种和数量 期限:年度 单位:万台,56,第三节 线性规划的典型案例,配送中心选择,例：某企业存在两个供货源（产地），已知原有供货源每月的供货能力是5万台产品，新增供货源的生产能力可以满足产品的需求，且两个货源的价格相同。 有三个区域目标市场（销地或销售商），各销地每月的市场需求量为5万台、10万台、5万台。 在分销渠道中，拟定在2个地点中选址设立分销中心，执行产品的转运任务。各地之间的单位运输物流成本（由距离和运输方式决定）,57,第三节 线性规划的典型案例,决策变量：设从供货源到分销中心的运输量为 ，从分销中心到需求市场的运输量为 。选址规划在于二者的实际取值。 如果 ，则不设置分销中心； 反之，则设置,其规模为 如果 ，则不设置分销中心； 反之，则设置，其规模为 目标函数：各条路段上的实际运输量乘以物流运输的单位费用之总和最小，即 存在供应能力约束、市场需求约束、配送中转约束，如下：,58,第三节 线性规划的典型案例,供应能力平衡约束： 市场需求平衡约束 配送中心不存留产品 所有变量大于等于零,59,第四节 线性规划灵敏度分析,一、灵敏度分析的必要性,线性规划研究的是一定条件下的最优化问题 资源环境和技术条件是可变的 基础数据往往是测算估计的数值 灵敏度分析的概念 灵敏度分析又称敏感性分析或优化后分析 研究基础数据发生波动后对最优解的影响 最优解对数据变化的敏感程度 在多大的范围内波动才不影响最优基 灵敏度分析解决的问题： 参数在什么范围变化而最优基不变 已知参数的变化范围，考察最优解(最优基)是否改变,60,第四节 线性规划灵敏度分析,一、价值系数的变动分析,非基变量Cj的变化范围 非基变量Cj变化，只影响它自己的检验数,参数Cj的变化范围：价值系数Cj变化影响检验数,61,第四节 线性规划灵敏度分析,一、价值系数的变动分析,基变量CBl的变化范围,62,第四节 线性规划灵敏度分析,二、右端常量的变动分析,参数bi的变化范围 第r个约束的右端项为br，增量br，其它数据不变。新的基解为,只要X'B0 ，则可保持最优基不变。,63,第3 章 对偶规划,Sub title,内容提要,第一节 对偶规划的数学模型 对偶问题的提出 对偶规划的性质 第二节 对偶规划的经济解释 影子价值的内涵 影子价值的应用 第三节 资源定价的决策案例,64,第一节 对偶规划的数学模型,一、对偶问题的提出,若例1中该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。 在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题： 合理安排生产能取得多大利润? 为保持利润水平不降低，资源转让的最低价格是多少？ 问题 的最优解：x1=4，x2=5，Z*=37。,65,第一节 对偶规划的数学模型,一、对偶问题的提出,出让定价,假设出让A、B、C设备所得利润分别为y1、y2、y3 原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有 2y1+0y2+3y3 3 同理，对乙产品而言，则有 0y1+2y2+4y3 5 设备台时出让的收益（希望出让的收益最少值） min 16y1+10y2+32y3 显然还有 y1，y2，y30,66,第一节 对偶规划的数学模型,一、对偶问题的提出,例1的对偶问题的数学模型,对偶问题的最优解： y1=0，y2=1/2，y3=1，W* =37 两个问题的目标函数值相等并非偶然 前者称为线性规划原问题，则后者为对偶问题，反之亦然。 对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。,67,第一节 对偶规划的数学模型,二、对偶规划的性质,1、对称性定理 对偶问题的对偶问题是原问题。 根据对偶规划，很容易写出对偶问题的对偶问题模型。 2、 最优性定理 设 ， 分别为原问题和对偶问题的可行解，且 则 ， 分别为各自的最优解。 3. 对偶性定理 若原问题有最优解，那么对偶问题也有最优解，而且 两者的目标函数值相等。 4. 互补松弛性 最优解的充分必要条件是 ，,68,第二节 对偶规划的经济解释,一、影子价值的内涵,左边是资源bi每增加一个单位对目标函数Z的贡献； 对偶变量 yi在经济上表示原问题第i种资源的边际价值。 对偶变量的值 yi*表示第i种资源的边际价值，称为影子价值。 若原问题价值系数Cj表示单位产值，则yi 称为影子价格。 若原问题价值系数Cj表示单位利润，则yi 称为影子利润。 影子价格=资源成本+影子利润,69,第二节 对偶规划的经济解释,一、影子价值的内涵,影子价格不是资源的实际价格，反映了资源配置结构， 其它数据固定，某资源增加一单位导致目标函数的增量。 对资源i总存量的评估：购进 or 出让 对资源i当前分配量的评估：增加 or 减少 第一，影子利润说明增加哪种资源对经济效益最有利 第二，影子价格告知以怎样的代价去取得紧缺资源 第三，影子价格是机会成本，提示资源出租/转让的基价 第四，利用影子价格分析新品的资源效果：定价决策 第五，利用影子价格分析现有产品价格变动的资源紧性 第六，可以帮助分析工艺改变后对资源节约的收益 第七，可以预知哪些资源是稀缺资源而哪些资源不稀缺,70,第三节 资源定价的决策方案,例：某厂生产甲乙产品，（1）如何安排每周的利润为最大? （2）如果企业可以不生产，那资源出让如何定价？,一、最优生产决策,71,第三节 资源定价的决策方案,二、资源获利决策,如果决策者考虑自己不生产甲乙两种产品，而把原拟用于生产这两种产品的原材料、设备工时、电量资源全部出售给外单位，或者做代加工，则应如何确定这三种资源的价格。,设原材料的单位出让获利为y1，设备工时的单位出让获利为y3，电量的单位出让获利为y2 。 出让决策的线性规划模型：,72,第4 章 整数规划,Sub title,内容提要,第一节 整数规划问题 纯整数规划 0-1规划 混合整数规划 第二节 整数规划求解 分枝定界法 第三节 整数规划应用,73,第一节 整数规划问题,线性规划的决策变量取值可以是任意非负实数，但许多实际问题中，只有当决策变量的取值为整数时才有意义 例如，产品的件数、机器的台数、装货的车数、完成工作的人数等，分数或小数解显然是不合理的。 要求全部或部分决策变量的取值为整数的线性规划问题，称为整数规划(Integer Programming)。 全部决策变量的取值都为整数，则称为全整数规划(All IP) 仅要求部分决策变量的取值为整数，则称为混合整数规划(Mixed IP) 要求决策变量只取0或1值，则称0-1规划(0-1 Programming),74,第一节 整数规划问题,一、纯整数规划,例：某企业利用材料和设备生产甲乙产品，其工艺消耗系数和单台产品的获利能力如下表所示：,问如何安排甲、乙两产品的产量，使利润为最大。,解：设x1为甲产品的台数，x2为乙产品的台数。 maxZ= 6x1 +5 x2 2x1 + x2 9 5x1 +7 x2 35 x1, x2 0 x1, x2 取整数,75,第一节 整数规划问题,二、0-1规划,登山队员可携带最大重量为25公斤。问都带哪些物品的重要性最大。,解：对于每一种物品无非有两种状态，带或者不带，不妨设,0-1规划的模型：,76,第一节 整数规划问题,三、混合整数规划,例：某产品有n个区域市场，各区域市场的需求量为 bj吨/月；现拟在m个地点中选址建生产厂，一个地方最多只能建一家工厂；若选 i地建厂，生产能力为 ai吨/月，其运营固定费用为F元/月；已知址i至j区域市场的运价为cij元/吨。如何选址和安排调运，可使总费用最小？,解：选址建厂与否是个0-1型决策变量， 假设 yi =1，选择第 i 址建厂， yi=0，不选择第 i 址建厂； 计划从 i 址至区域市场 j 的运输 运量xij为实数型决策变量。,77,第二节 整数规划求解,一、舍入化整法,为了满足整数解的要求，自然想到“舍入”或“截尾”处理，以得到与最优解相近的整数解。 这样做除少数情况外，一般不可行，因为化整后的解有可能超出了可行域，成为非可行解；或者虽是可行解，却不是最优解。,不考虑整数约束则是一个LP问题,称为原整数规划的松弛问题 对于例1的数学模型，不考虑整数约束的最优解： x1 *=28/9， x2 * =25/9，Z * =293/9,舍入化整 x1 =3， x2 =3，Z =33，不满足约束条件5x1 +7 x2 35，非可行解； x1 =3， x2 =2，Z =28，满足约束条件，是可行解，但不是最优解； x1 =4， x2 =1，Z =29，满足约束条件，才是最优解。,78,第二节 整数规划求解,二、穷举整数法,对于决策变量少，可行的整数解又较少时，这种穷举法有时是可行的，并且也是有效的。 但对于大型的整数规划问题，可行的整数解数量很多，用穷举法求解是不可能的。例如，指派问题 。, (3,3),79,第二节 整数规划求解,三、分支定界法,不考虑整数限制，先求出相应线性规划 的最优解， 若求得的最优解符合整数要求，则是原IP的最优解； 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。 依次在缩小的可行域中求解新构造的线性规划的最优解，直到获得原整数规划的最优解。 定界的含义： IP是在相应的LP基础上增加整数约束 IP的最优解不会优于相应LP的最优解 对MaxZ，相应LP的Z*是原IP的上界,80,第二节 整数规划求解,三、分支定界法,x13,x1 4,x22,x2 3,x12,x1 3,x23,x2 4,81,第三节 整数规划应用,一、生产基地规划,例：某公司拟建设A、B两种类型的生产基地若干个，两种类型的生产基地每个占地面积，所需经费，建成后生产能力及现有资源情况如下表所示。问A、B类型基地各建设多少个，可使总生产能力最大？,解：设A、B两类基地各建设 x1,x2 个，则其模型为：,82,第三节 整数规划应用,二、人员安排规划,某服务部门各时段(每2小时为一时段)需要的服务人数如表：,解：设第j 时段开始时上班的服务员人数为xj 第 j 时段来上班的服务员将在第j+3 时段结束时下班，故决策变量有x1,x2,x3,x4,x5 。,按规定，服务员连续工作8小时(4个时段)为一班。请安排服务员的工作时间，使服务员总数最少.,83,第三节 整数规划应用,三、项目投资选择,有600万元投资5个项目，收益如表，求利润最大的方案？,84,第三节 整数规划应用,四、互斥约束问题,例如关于煤资源的限制，其约束条件为： 企业也可以考虑采用天然气进行加热处理： 这两个条件是互相排斥的。引入01变量y，令 互斥问题可由下述的条件来代替，其中M是充分大的数。,85,第三节 整数规划应用,五、租赁生产问题,服装公司租用生产线拟生产T恤、衬衫和裤子。 每年可用劳动力8200h，布料8800m2。,假设：yj=1，要租用生产线j yi=0，不租用生产线j 第j 种服装生产量xj,86,第三节 整数规划应用,六、任务指派问题,甲乙丙丁四个人，ABCD四项任务，如何指派总时间最短？,解： 引入0-1变量xij ， xij =1：任务j指派人员i去完成 xij =0：任务j不派人员i去完成,一项任务只由一个人完成 一人只能完成一项任务,87,第三节 整数规划应用,七、设施选址问题,拟定在2个地点中选址设立分销中心，执行产品的仓储和转运，一个分销中心拟定设立一个仓库W1、W2。 若设立仓库W1，建设成本为10万元，最大库容为20万台，单位产品的月库存成本为2元； 若设立仓库W2建造成本为20万元，最大库容为25万台，单位产品的月库存成本为3元。 如何选址和安排调运，建造费用+运输费用+仓储费用为最小？,解：设从供货源Si到分销中心Wj的运输量为xij，从分销中心 到需求市场Rk的运输量为yjk。仓库选址决策引入0-1变量wj ：,88,第三节 整数规划应用,七、设施选址问题,供应能力平衡约束： 市场需求平衡约束： 仓储能力限制约束： 分销中心不存留产品： 所有变量大于等于零：,89,第5 章 目标规划,Sub title,内容提要,第一节 多目标规划问题 第二节 目标规划数学模型 目标的期望值 正负偏差变量 目标达成函数 目标优先级别 第三节 目标规划的图解法 第四节 目标规划单纯形法 第五节 目标规划应用案例,90,第一节 多目标规划问题,一、线性规划的局限性,线性规划的局限性 只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题 实际决策中，衡量方案优劣考虑多个目标 生产计划决策，通常考虑产值、利润、满足市场需求等 生产布局决策，考虑运费、投资、供应、市场、污染等 这些目标中，有主要的，也有次要的；有最大的，有最小的；有定量的，有定性的；有互相补充的，有互相对立的，LP则无能为力 目标规划（Goal Programming） 多目标线性规划 含有多个优化目标的线性规划,91,第一节 多目标规划问题,二、多目标规划的提出,例：甲乙产品的最优生产计划。,解：线规划模型： maxZ=3x1+5x2 2x1 16 2x2 10 3x1+4x2 32 x1，x2 0,根据市场需求/合同规定： 希望尽量扩大甲产品 减少乙产品产量。 又增加二个目标：,maxZ1=3x1+5x2 maxZ2=x1 minZ3=x2 2x1 16 2x2 10 3x1+4x2 32 x1，x2 0,这些目标之间相互矛盾，一般的线性规划方法不能求解,92,第一节 多目标规划问题,三、多目标规划的解法,加权系数法： 为每一目标赋一权数，把多目标转化成单目标。 但权系数难以科学确定。 优先等级法： 各目标按重要性归不同优先级而化为单目标。 有效解法： 寻求能照顾到各目标而使决策者感到满意的解。 但可行域大时难以列出所有有效解的组合。 目标规划法： 对每一个目标函数引入正的或负的偏差变量； 引入目标的优先等级和加权系数。,93,第二节 目标规划的数学模型,一、目标期望值,每一个目标希望达到的期望值(或目标值、理想值)。 根据历史资料、市场需求或上级部门的布置等来确定。,二、偏差变量,目标约束,目标的实际值和期望值之间可能存在正的或负的偏差。 正偏差变量dk+ 表示第k个目标超过期望值的数值； 负偏差变量dk- 表示第k个目标未达到期望值的数值。 同一目标的dk+ 和dk- 中至少有一个必须为零。,引入正负偏差变量，对各个目标建立目标约束(软约束),94,第二节 目标规划的数学模型,上例中要求： 目标一是利润最大，拟定利润目标是30； 目标二是减少乙产品产量但希望不低于4件； 目标三是甲产品产量希望不少于6件 ； 对各目标引入正、负偏差变量： 3x1+5x2 +d1- d1+ = 30 x2 +d2- - d2+ =4 x1 +d3 -d3+ = 6,95,第二节 目标规划的数学模型,三、目标达成函数,目标达成函数：偏差变量之和为最小值。 若要求尽可能达到规定的目标值 正负偏差变量dk+ , dk- 都尽可能小，即minSk=dk+dk- 若希望尽可能不低于期望值(允许超过) 负偏差变量dk- 尽可能小,不关心超出量dk+ ：minSk= dk- 若允许某个目标低于期望值，但希望不超过 正偏差变量dk+尽可能小,不关心低于量dk- ：minSk= dk+,四、优先等级权数,目标重要度不同，用优先等级因子Pk 表示第k等级目标。 优先等级因子Pk 是正的常数， Pk P