您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 管理学资料 > 11月5日运筹学讲义第5章目标规划
管理运筹学-管理科学方法中山大学南方学院工商管理系演讲:王甜源OR:SM2第5章目标规划Subtitle学习要点了解目标规划与线性规划的异同理解目标约束中的正负偏差变量思考目标约束与系统约束的差异理解目标的优先级和目标权系数了解目标规划图解法和单纯形法OR:SM3第一节多目标规划问题一、线性规划的局限性•线性规划的局限性只能解决一组线性约束条件下,某一目标而且只能是一个目标的最大或最小值的问题•实际决策中,衡量方案优劣考虑多个目标生产计划决策,通常考虑产值、利润、满足市场需求等生产布局决策,考虑运费、投资、供应、市场、污染等•这些目标中,有主要的,也有次要的;有最大的,有最小的;有定量的,有定性的;有互相补充的,有互相对立的,LP则无能为力•目标规划(GoalProgramming)多目标线性规划含有多个优化目标的线性规划OR:SM4问题的提出:•目标规划是在线性规划的基础上,为适应经济管理多目标决策的需要而由线性规划逐步发展起来的一个分支。•由于现代化企业内专业分工越来越细,组织机构日益复杂,为了统一协调企业各部门围绕一个整体的目标工作,产生了目标管理这种先进的管理技术。目标规划是实行目标管理的有效工具,它根据企业制定的经营目标以及这些目标的轻重缓急次序,考虑现有资源情况,分析如何达到规定目标或从总体上离规定目标的差距为最小。第5章目标规划OR:SM5第一节多目标规划问题二、多目标规划的提出例:甲乙产品的最优生产计划。产品资源甲乙现有资源设备A2016设备B0210设备C3432单位利润35解:线规划模型:maxZ=3x1+5x22x1≤162x2≤103x1+4x2≤32x1,x2≥0•根据市场需求/合同规定:希望尽量扩大甲产品减少乙产品产量。•又增加二个目标:maxZ1=3x1+5x2maxZ2=x1minZ3=x22x1≤162x2≤103x1+4x2≤32x1,x2≥0这些目标之间相互矛盾,一般的线性规划方法不能求解OR:SM6第一节多目标规划问题二、多目标规划的提出11111221221122221122ln11112211211222221122max(min)max(min)max(min)(,)(,)s.t.nnnnlllnnnnnmmGcxcxcxGcxcxcxGcxcxcxaxaxaxbaxaxaxbaxax12(,),,0mnnmnaxbxxx多目标线性规划模型的原始一般形式如下:n个决策变量,m个约束条件,L个目标函数。当L=1时,即为我们熟悉的单目标线性规划模型。OR:SM7•例:某企业计划生产甲,乙两种产品,这些产品分别要在A,B,C,D四种不同设备上加工。按工艺文件规定,如表所示。ABCD单件利润甲11402乙22043最大负荷1281612问该企业应如何安排计划,使得计划期内的总利润收入为最大?第一节多目标规划问题OR:SM8•解:设甲、乙产品的产量分别为x1,x2,建立线性规划模型:0,124164821222.32max2121212121xxxxxxxxtsxxz其最优解为x1=4,x2=2,z*=14元第一节多目标规划问题OR:SM9但企业的经营目标不仅仅是利润,而且要考虑多个方面,如:(1)力求使利润指标不低于12元;(2)考虑到市场需求,甲、乙两种产品的生产量需保持1:1的比例;(3)C和D为贵重设备,严格禁止超时使用;(4)设备B必要时可以加班,但加班时间要控制;设备A即要求充分利用,又尽可能不加班。要考虑上述多方面的目标,需要借助目标规划的方法。第一节多目标规划问题OR:SM10•线性规划模型存在的局限性:•1)要求问题的解必须满足全部约束条件,实际问题中并非所有约束都需要严格满足。•2)只能处理单目标的优化问题。实际问题中,目标和约束可以相互转化。•3)线性规划中各个约束条件都处于同等重要地位,但现实问题中,各目标的重要性即有层次上的差别,同一层次中又可以有权重上的区分。•4)线性规划寻求最优解,但很多实际问题中只需找出满意解就可以。第一节多目标规划问题OR:SM11第一节多目标规划问题三、多目标规划的解法•加权系数法:为每一目标赋一权数,把多目标转化成单目标。但权系数难以科学确定。•优先等级法:各目标按重要性归不同优先级而化为单目标。•有效解法:寻求能照顾到各目标而使决策者感到满意的解。但可行域大时难以列出所有有效解的组合。•目标规划法:对每一个目标函数引入正的或负的偏差变量;引入目标的优先等级和加权系数。OR:SM12•目标规划怎样解决前例线性规划模型建模中的局限性?1.设置偏差变量,用来表明实际值同目标值之间的差异。偏差变量用下列符号表示:d+——超出目标的偏差,称正偏差变量d-——未达到目标的偏差,称负偏差变量正负偏差变量两者必有一个为0。当实际值超出目标值时:d+0,d-=0;当实际值未达到目标值时:d+=0,d-0;当实际值同目标值恰好一致时:d+=0,d-=0;故恒有d+×d-=0第一节多目标规划问题OR:SM132.统一处理目标和约束。对有严格限制的资源使用建立系统约束,数学形式同线性规划中的约束条件。如C和D设备的使用限制。12416421xx对不严格限制的约束,连同原线性规划建模时的目标,均通过目标约束来表达。1)例如要求甲、乙两种产品保持1:1的比例,系统约束表达为:x1=x2。由于这个比例允许有偏差,当x1x2时,出现负偏差d-,即:x1+d-=x2或x1-x2+d-=0当x1x2时,出现正偏差d+,即:x1-d+=x2或x1-x2-d+=0第一节多目标规划问题OR:SM14•∵正负偏差不可能同时出现,故总有:•x1-x2+d--d+=00}min{21ddxxd若希望甲的产量不低于乙的产量,即不希望d-0,用目标约束可表为:若希望甲的产量低于乙的产量,即不希望d+0,用目标约束可表为:0}min{21ddxxd若希望甲的产量恰好等于乙的产量,即不希望d+0,也不希望d-0用目标约束可表为:0}min{21ddxxdd第一节多目标规划问题OR:SM15•3)设备B必要时可加班及加班时间要控制,目标约束表示为:82}min{21ddxxd•2)力求使利润指标不低于12元,目标约束表示为:1232}min{21ddxxd•4)设备A既要求充分利用,又尽可能不加班,目标约束表示为:1222}min{21ddxxdd第一节多目标规划问题OR:SM163.目标的优先级与权系数在一个目标规划的模型中,为达到某一目标可牺牲其他一些目标,称这些目标是属于不同层次的优先级。优先级层次的高低可分别通过优先因子P1,P2,…表示。对于同一层次优先级的不同目标,按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字,乘上的权系数越大,表明该目标越重要。现假定:第1优先级P1——企业利润;第2优先级P2——甲乙产品的产量保持1:1的比例第3优先级P3——设备A充分利用但尽量不超负荷工作,设备B尽量不超负荷工作。其中设备A的重要性比设备B大三倍。第一节多目标规划问题OR:SM17•上述目标规划模型可以表示为:)4,...,1(0,,,82122201232124164..)(3)(min214421332122211121214333322211iddxxddxxddxxddxxddxxxxtsdPddPddPdPzii第一节多目标规划问题OR:SM18目标规划数学模型的一般形式)2.1(0.n)1.2(j0)2.1().()2.1()(min1111KkddxmibxaKkgddxcddPZkkjnjijijnjkkkjkjLlKkklkklkl达成函数目标约束其中:gk为第k个目标约束的预期目标值,和为pl优先因子对应各目标的权系数。lklk第一节多目标规划问题OR:SM19目标规划问题及其数学模型总结:用目标规划求解问题的过程:明确问题,列出目标的优先级和权系数构造目标规划模型求出满意解满意否?分析各项目标完成情况据此制定出决策方案NYOR:SM20第二节目标规划的数学模型一、目标期望值每一个目标希望达到的期望值(或目标值、理想值)。根据历史资料、市场需求或上级部门的布置等来确定。二、偏差变量目标约束njkkjkjEddxc1*目标的实际值和期望值之间可能存在正的或负的偏差。正偏差变量dk+表示第k个目标超过期望值的数值;负偏差变量dk-表示第k个目标未达到期望值的数值。同一目标的dk+和dk-中至少有一个必须为零。引入正负偏差变量,对各个目标建立目标约束(软约束)总结:用目标规划求解问题的过程:OR:SM21第二节目标规划的数学模型若对PPT第5页例题做出如下要求:目标一是利润最大,拟定利润目标是30;目标二是减少乙产品产量但希望不低于4件;目标三是甲产品产量希望不少于6件;对各目标引入正、负偏差变量:3x1+5x2+d1--d1+=30x2+d2--d2+=4x1+d3–-d3+=6OR:SM22第二节目标规划的数学模型三、目标达成函数目标达成函数:偏差变量之和为最小值。若要求尽可能达到规定的目标值正负偏差变量dk+,dk-都尽可能小,即minSk=dk++dk-若希望尽可能不低于期望值(允许超过)负偏差变量dk-尽可能小,不关心超出量dk+:minSk=dk-若允许某个目标低于期望值,但希望不超过正偏差变量dk+尽可能小,不关心低于量dk-:minSk=dk+四、优先等级权数目标重要度不同,用优先等级因子Pk表示第k等级目标。优先等级因子Pk是正的常数,PkPk+1。同一优先等级下目标的相对重要性赋以不同权数w。总结:用目标规划求解问题的过程:OR:SM23第二节目标规划的数学模型对PPT第五页例题而言,若:P1级目标实现利润至少30元;P2级目标是甲乙产品的产量假设:乙产品产量不少于4件比甲产品产量不少于6件更重要,取其权重为2目标规划为:minG=P1d1-+P2(2d2-+d3-)3x1+5x2+d1--d1+=30x2+d2--d2+=4x1+d3--d3+=6x1,x2,dk-,dk+≥0(k=1,2,3)OR:SM24目标规划的图解法:适用两个变量的目标规划问题,但其操作简单,原理一目了然。同时,也有助于理解一般目标规划的求解原理和过程。图解法解题步骤:1.将所有约束条件(包括目标约束和绝对约束,暂不考虑正负偏差变量)的直线方程分别标示于坐标平面上。2.确定系统约束的可行域。3.在目标约束所代表的边界线上,用箭头标出正、负偏差变量值增大的方向第三节目标规划的图解法OR:SM25•3.求满足最高优先等级目标的解•4.转到下一个优先等级的目标,再不破坏所有较高优先等级目标的前提下,求出该优先等级目标的解•5.重复4,直到所有优先等级的目标都已审查完毕为止•6.确定最优解和满意解。第三节目标规划的图解法OR:SM26例2:装配两种型号的笔记本,每台需装备时间1小时,每周工作5天,计划开动8小时/天。预计每周销售型号I24台,利润80元/台,型号II30台,利润40元/台。该厂目标如下:充分利用装配线,避免开工不足允许装配线加班,但加班时间尽可能短,但不超过10小时尽量满足市场需求,重要性和利润成正比每周的利润5000以上请合理安排工作任务建立目标规划的模型:11223344512111222133244125512min(2)405024s.t.3080405000,0,0(
本文标题:11月5日运筹学讲义第5章目标规划
链接地址:https://www.777doc.com/doc-629597 .html