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

管理运筹学-管理科学方法,谢家平 博士 教授博士生导师研究领域：管理科学、运营管理、供应链管理讲授课程：管理运筹学-管理科学方法、管理系统工程、运营管理、供应链管理、ERP、国际物流、企业物流管理、管理决策模型与方法单 位：上海财经大学工商学院 物流管理系 E-mail：,2,教材与参考书籍,教材：谢家平编著.管理运筹学：管理科学方法，中国人民大学出版社，2010参考书：David et al.数据、模型与决策，机械工业出版社，2004费雷德里克.数据、模型与决策，中国财政经济出版社，2004James 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利润=4066+8089+4070=12560 人员有限如何实现?采取什么薪酬制度?计件工资制，让员工自愿加班,决策的科学性？方案 一,15,二、学科作用,甲产品产量 40,乙产品 80,丙产品 40总收入=40173+80233+40170=32360原料成本=4065+8095+4065=12800营运费用=11000总利润=32360-12800-11000=8560人员有限如何实现?采取什么薪酬制度?岗位工资制（定岗定员），让员工自觉加班,决策的科学性？方案 二,16,二、学科作用,决策的科学性？产能符合计算,乙与丙哪一个产品比较赚钱?,E是瓶颈,17,二、学科作用,方案 三：计时工资，且以单位利润率高低为决策意识。乙比较赚钱,假如80个全部生产需用E产能2400分钟，但是E只有2400分钟可用因此只能生产80个乙(2400/30)，而丙无法生产,方案：甲产品 40个，乙产品80个，丙产品0个总收入=40173+80233+0170=25560 原料=4065+8095+065=10200，营运费用=11000利润=25560-10200-11000=4360,方案 四：计时工资，但以占用瓶颈资源大小为决策意识。丙比较赚钱,优先生产40个需用E产能600(4015)分钟剩下1800分钟,可生产60个乙(1800/30),方案：甲产品 40个，乙产品 60个，丙产品 40个总收入=40173+60233+40170=27700原材料=4065+6095+406540=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=xk-xk，(xk0,xk 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+0 x3+0 x4+0 x5=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+170 x3，原料成本=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，其它数据不变。新的基解为,只要XB0，则可保持最优基不变。,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=x1minZ3=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 Pk+1。同一优先等级下目标的相对重要性赋以不同权数w。,96,第二节 目标规划的数学模型,例如P1 级目标实现利润至少30元；P2级目标是甲乙产品的产量 假设：乙产品产量不少于4件比甲产品产量不少于6件更重要，取其权重为2 minG=P1 d1-+P2(2d2-+d3+)3x1+5x2+d1-d1+=30 x2+d2-d2+=4 x1+d3-d3+=6 x1,x2,dk-,dk+0(k=1,2,3),97,第三节 目标规划的图解法,目标规划的图解法首先，按照绝对约束画出可行域，其次，不考虑正负偏差变量，画出目标约束的边界线，最后。按优先级别和权重依次分析各级目标。,F,G,H,x1=5,x2=4,98,第四节 目标规划的应用案例,一、无穷多满意解,解：设x1,x2表示A、B产品的产量。两个等级的目标：P1：充分利用电量限额，正负偏差之和为最小 目标达成函数 目标约束条件 P2：利润额希望不能低于100元，负偏差最小 目标达成函数 目标约束条件,计划生产两种产品，首先要充分利用设备工时而不加班；然后考虑利润不低于100元。问应如何制定产品A、B的产量。,99,第四节 目标规划的应用案例,一、无穷多满意解,由于材料供应限量为8单位，所以有系统约束条件，如下,该问题的目标规划模型如下，图解法求解如图,C,G,100,第四节 目标规划的应用案例,二、加班时间问题,例：某音像店有5名全职售货员和4名兼职售货员，全职售货员每月工作160小时，兼职售货员每月工作80小时。根据记录，全职每小时销售CD25张，平均每小时工资15元，加班工资每小时22.5元。兼职售货员每小时销售CD10张，平均工资每小时10元，加班工资每小时10元。现在预测下月CD销售量为27500张，商店每周开门营业6天，所以可能要加班。每出售一张CD盈利1.5元。商店经理认为，保持稳定的就业水平加上必要的加班，比不加班就业水平要好，但全职销售员如果加班过多，就会因为疲劳过度而造成效率下降，因此不允许每月加班超过100小时，建立相应的目标规划模型。,101,第四节 目标规划的应用案例,二、加班时间问题,首先，确定目标约束的优先级。如下：P1：下月的CD销售量达到27500张；P2：全职售货员加班时间不超过100小时；P3：保持全体售货员充分就业，对全职的要比兼职的加倍优先考虑；P4：尽量减少加班时间，对两种售货员区别对待，权重由他们对利润的贡献而定。其次，建立目标约束函数（1）销售目标约束，设全体全职售货员下月的工作时间x1，全体兼职售货员下月的工作时间 x2