运筹学第四章目标规划.ppt
第四章 目标规划,目标规划（Good Programming，简记为GP）是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个运筹学分支，是实行目标管理这种现代化管理技术的一个有效工具。,例4.1 某工厂生产两种产品，受到原材料供应和设备工时的限制.在单件利润等有关数据已知的条件下，要求制订一个获利最大的生产计划，具体数据见下表。,一、问题的提出,表4-1,4.1 目标规划的数学模型,设产品、的产量分别为,从线性规划的角度来看，问题似乎已经得到圆满的解，但实际上工厂作决策时可能还需根据市场和工厂实际情况，考虑其它问题，如：（1）由于产品销售疲软，故希望产品的产量不超过产品的一半；（2）原材料严重短缺，生产中应避免过量消耗；（3）最好能节约4小时设备工时；（4）计划利润不少于48元.这时，问题变成一个多目标问题，线性规划方法就很难处理。,St.,件，,解之得最优生产计划为,，建立线性规划模型,件，利润为,元。,目标规划问题的解决思路,目标规划：常用以解决多目标决策问题，其目标函数主要是追求偏离目标量的最小化。偏离目标量一般以偏离变量表示。这些目标分主次或轻重缓急，以限制式的方式进行说明，一般采用目标依据级别赋予表示优先级的权重值（优先权因子)来表示。采用目标规划技术时，必须了解如何订定目标的优先次序与权数。有时候可考虑将权数与优先次序合并使用。,二、目标规划的基本概念,1、目标值和偏差变量,目标规划通过引入目标值和正、负偏差变量，可以将目标函数转化为目标约束。,因为在一次决策中，决策值不可能既超过目标值，同时又未达到目标值，所以有。即 中有一个为0。,目标值是目标的期望值（预先给定）；决策值是目标函数在决策变量确定后的函数值；偏差变量用于表达二者之间的差异。,正偏差变量表示决策值超过目标值的数量，记为；负偏差变量表示决策值未达到目标值的数量，记为。显然有。,目标值,实际值,d,d,有：目标值实际值d+（此时d0）,1.当实际值目标值时 d0,2.当实际值目标值时d+0,有：目标值实际值d（此时d0）,故有：目标值实际值d d,实际值,目标值,2、目标约束和绝对约束,目标约束（软约束）是指在目标规划问题中目标值允许发生正、负偏差，在这些约束中加入正、负偏差变量的约束。,绝对约束（硬约束）是指必须严格满足的等式约束和不等式约束。,线性规划问题的目标函数在给定目标值和加入正、负偏差变量后，可变换为目标约束，也可根据问题的需要将绝对约束变换为目标约束。,区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数wj。,在实际问题中，决策者要求达到这些目标时，是有主次或轻重缓急的不同，凡要求第一位达到的目标赋予优先因子P1，次位的目标赋予优先因子P2，并规定：PkPk+1 表示Pk 比Pk+1有更大的优先权，即首先保证级P1目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的，以此类推。,3、优先因子（优先等级）与权系数,4、目标规划的目标函数,目标规划的目标函数（又称准则函数或达成函数），是由各目标约束的偏差变量及相应的优先因子和权系数构成，由于目标规划追求的是尽可能接近各既定目标值，也就是各有关偏差变量尽可能小，所以，其目标函数一定是极小化的。,（1）要求恰好达到目标值（目标：正负偏差为0）最好等于：,应用时，有三种基本表达式.,（2）要求不超过目标值（目标：正偏差为0）最好不大于：,（3）要求不低于目标值（目标：负偏差为0）最好不小于：,目标规划问题的求解是分级进行的，首先求满足P1级目标的解，然后在保证级目标不被破坏的前提下再求满足P2级目标的解，以此类推。总之，是在不破坏上一级目标的前提下，实现下一级目标的最优。因此，这样最后求出的解就不是通常意义下的最优解，称之为满意解。之所以叫满意解，是因为对于这种解来说，前面的目标是可以保证实现或部分实现的，后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。,5、满意解,实际问题决策经常面临的问题（多目标决策问题）：,方案优劣并不以单一准则为目标，而是以多重准则为目标。约束条件并不完全符合严格的刚性条件，具有一定的弹性。,可能的弹性约束：最好等于最好不大于最好不小于,三、目标规划的数学模型,目标值,实际值,d,d,有：目标值实际值d+（此时d0）,1.当实际值目标值时 d0,2.当实际值目标值时d+0,有：目标值实际值d（此时d0）,故有：目标值实际值d d,实际值,目标值,弹性约束的一般处理方法,实际量,d,d,+,=,目标值,负偏差变量,正偏差变量,最好等于：,最好不大于：,最好不小于：,d,d,实际值,目标值,实际值,问题：商家对顾客访问及销售策略,目标：,访问时间最好不超过680小时；访问时间最好不少于600小时；销售收入尽量不少于70,000；访问老顾客数最好不少于200个；访问新顾客数最好不少于120个。,数学模型顾客访问策略,设、分别为访问老顾客、新顾客的数量；（i1,2,3,4,5）为按优先级排列的管理目标（优先因子）。建立目标规划模型如下：,访问时间最好不超过680小时；访问时间最好不少于600小时；销售收入尽量不少于70,000；访问老顾客数最好不少于200个；访问新顾客数最好不少于120个。,4.2 目标规划的图解法,图解法只适用于两个决策变量的目标规划问题,用图解法解目标规划时，先在由决策变量x1，x2构成的平面直角坐标系的第一象限内作各约束条件。绝对约束条件的作图与线性规划相同，作目标约束时，先令d、d=0，作相应的直线，然后在这直线旁标上d，d增大的方向，在此基础上再按照优先级从高到低的顺序，逐个地考虑各个目标约束。,目标规划解的几何分析,P1,P2,P3,P4级目标均能够实现，但这些目标实现后，P5级目标无法实现。,目标规划的求解-序贯算法,4.3 目标规划的单纯形法,1.访问时间最好不超过680小时；2.访问时间最好不少于600小时；3.销售收入尽量不少于70,000；4.访问老顾客数最好不少于200个；5.访问新顾客数最好不少于120个。,第一级目标,1.访问时间最好不超过680小时；2.访问时间最好不少于600小时；3.销售收入尽量不少于70,000；4.访问老顾客数最好不少于200个；5.访问新顾客数最好不少于120个。,第二级目标,1.访问时间最好不超过680小时；2.访问时间最好不少于600小时；3.销售收入尽量不少于70,000；4.访问老顾客数最好不少于200个；5.访问新顾客数最好不少于120个。,第三级目标,1.访问时间最好不超过680小时；2.访问时间最好不少于600小时；3.销售收入尽量不少于70,000；4.访问老顾客数最好不少于200个；5.访问新顾客数最好不少于120个。,第四级目标,1.访问时间最好不超过680小时；2.访问时间最好不少于600小时；3.销售收入尽量不少于70,000；4.访问老顾客数最好不少于200个；5.访问新顾客数最好不少于120个。,第五级目标（无法实现）,1.访问时间最好不超过680小时；2.访问时间最好不少于600小时；3.销售收入尽量不少于70,000；4.访问老顾客数最好不少于200个；5.访问新顾客数最好不少于120个。,目标规划的求解-多阶段算法,1.访问时间最好不超过680小时；2.访问时间最好不少于600小时；3.销售收入尽量不少于70,000；4.访问老顾客数最好不少于200个；5.访问新顾客数最好不少于120个。,目标规划单纯形法的特点,目标函数中只有偏差变量，且求它们的和最小。目标函数中“价值系数”一般为优先级的权重，因此检验数不是一行，而是m行。在m行检验数中，从上到下，按优先级从高到低的顺序排列。求解时，首先满足优先级高的变量。,初始单纯形表,P1行中的检验数不小于0目标实现。P2行中的检验数小的对应的X2进基，离基，继续计算。,单纯形表运算,P1行中的检验数不小于0目标实现。P2行中的检验数小的对应的 进基，离基，继续计算。,单纯形表运算,P1、P2行中的检验数不小于0目标实现。P3行中的检验数小的对应的X1 进基，离基，继续计算.,单纯形表运算,P1、P2行中的检验数不小于0目标实现。P3行中的检验数小的对应的 进基，离基，继续计算.,单纯形表运算,P1、P2行中的检验数不小于0目标实现。P3行中的检验数小的对应的 进基，离基，继续计算.,End,THANK YOU.,
