运筹学第4章目标规划

1Chapter4目标规划(Goalprogramming)目标规划问题的数学模型目标规划的图解分析法目标规划的单纯形法灵敏度分析本章主要内容：2/42第1节目标规划的数学模型3/42线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。线性规划求最优解；目标规划是找到一个满意解线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。一、目标规划与线性规划的比较4/42例1：某工厂生产I、II两种产品，数据如下表，试求获利最大的生产方案？III拥有量原材料（kg）设备（hr）21121110利润(元/件)81012121212max810211s.t.210x,0zxxxxxxx从数据到模型为了具体形象地阐述目标规划与线性规划在处理问题的方法上的一些差异，我们这里通过一个例子来简介多目标规划的相关概念及数学模型。5/42但企业的经营目标不仅仅是利润，而且要考虑多个方面，如：(1)产品Ⅰ产量不大于产品Ⅱ；(2)考超过计划供应原材料时，需高价采购，这使成本增加；(3)应尽可能充分利用设备工时，但不希望加班；(4)利润不少于56元。要考虑上述多方面的目标，需要借助目标规划的方法。为此引入与建立目标规划数学模型有关的概念。6/42目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。目标值：是指预先给定的某个目标的一个期望值。实现值或决策值：是指当决策变量xj选定以后，目标函数的对应值。偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异,记为d。正偏差变量：表示实现值超过目标值的部分，记为d＋。负偏差变量：表示实现值未达到目标值的部分，记为d－。1、目标值和偏差变量二、目标规划的基本概念7/42•当完成或超额完成规定的指标则表示：d＋≥0,d－＝0•当未完成规定的指标则表示：d＋＝0,d－≥0•当恰好完成指标时则表示：d＋＝0,d－＝0∴d＋×d－＝0成立。在一次决策中，实现值不可能既超过目标值又未达到目标值，故有d＋×d－＝0,并规定d＋≥0,d－≥0绝对约束（系统约束）：是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。目标约束:是指希望达到的目标。目标约束是目标规划中特有的，是软约束。2、绝对约束和目标约束8/42例如要求I、II两种产品保持1:1的比例，即x1=x2。由于这个比例允许有偏差，当x1x2时，出现负偏差d-，即：x1+d-=x2或x1－x2+d-=0当x1x2时，出现正偏差d+，即：x1-d+=x2或x1－x2-d+=0∵正负偏差不可能同时出现，故目标约束为：0ddxx219/420}min{21ddxxd若希望I的产量不低于II的产量，即不希望d-0,用目标约束可表为:若希望I的产量低于II的产量，即不希望d＋0,用目标约束可表为:0}min{21ddxxd若希望I的产量恰好等于II的产量，即不希望d＋0,也不希望d-0用目标约束可表为:0}min{21ddxxdd10/4210ddx2x}dmin{2156ddx10x8}dmin{2110ddx2x}ddmin{21力求使利润指标不低于56元，目标约束表示为：设备必要时可加班及加班时间要控制，目标约束表示为：设备既要求充分利用，又尽可能不加班，目标约束表示为：11/42优先因子Pk是将决策目标按其重要程度排序并表示出来P1P2…PlPl+1…PL，l=1.2…L。必须“满足”第一级才能“满足”第二级，依次类推。权系数ωlk：区别具有相同优先因子的两个目标的重要性差别，决策者可视具体情况而定。（优先因子和权系数的大小具有主观性和模糊性，它不是运筹学本身的问题，主要是决策人自身的经验，可用专家评定法给以量化。）对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。3、优先因子（优先等级）与优先权系数4、满意解（具有层次意义的解）12/42目标函数：由各目标约束的正、负偏差变量及相应的优先因子和权系数构成。从决策者的要求来分析，总希望得到的结果与规定的指标值之间的偏差量愈小愈好。由此可构造一个使总偏差量为最小化的目标函数，minZ=f（d＋、d－）。一般说来，有以下三种情况，但只能出现其中之一：⑴要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ=f（d＋＋d－）。⑵要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ=f（d＋）。⑶要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ=f（d－）。5、目标规划中的目标函数13/42目标规划建模的步骤1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；3、给各目标赋予相应的优先因子Pl（l=1.2…L）。2、根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。4、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。lklk和5、根据决策者的要求，按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数。⑴恰好达到目标值，取lldd⑵允许超过目标值，取ld(3)不允许超过目标值，取ld14/42解：确定优先因子后得数学模型：minZ=P1d1++P2(d2-+d2+)+P3d3-2x1+x2≤11（在绝对约束基础上进行目标规划）x1-x2+d1--d1+=0(要求：d1+尽可能小，最好是0才能满足≤)x1+2x2+d2--d2+=10（要求：d2-和d2+都尽可能小，最好等于0）8x1+10x2+d3--d3+=56（要求：d3-尽可能小，最好是0才能满足≥）x1,x2,di-,di+≥0例1：要求：1）超过计划供应原材料时，需高价采购，这使成本增加。2）产品Ⅰ产量不大于产品Ⅱ。3）应尽可能充分利用设备工时，但不希望加班。4）利润不少于56元。2x1+x2≤11x1-x2≤0x1+2x2=108x1+10x2≥5615/42)3.2.1(0.,0112561081020)(min21213321222111213322211jddxxxddxxddxxddxxdPddPdPZjj规划模型：16/42练习1：某电视机厂装配黑白、彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标为：第一优先级：充分利用装配线；第二优先级：加班时间不超过10小时；第三优先级：满足市场需求，因彩色电视机的利润高，取其权系数为2。)dd2(pdpdpzmin4332211401121ddxx502221ddxx24331ddx30442ddx4,3,2,1,0,,,21iddxxii解：设x1和x2分别为彩色电视机和黑百电视机的产量，于是有：17/42目标规划模型的一般形式1111min()(1.2)(.)(1.2)0(j1.2n).0(1.2)LKllkklkklknkjjkkkjnijjijjkkZPddcxddgkKaxbimxddkK优先因子负偏差权系数正偏差权系数目标约束系统约束变量非负18/42求解目标规划问题常用的两种方法：图解法特点：形象直观，但只适用于只有两个决策变量。单纯形法目标规划的数学模型与线性规划的数学模型本质上是一致的，故可以利用单纯形方法求解目标规划问题第二节解目标规划的图解法19/421.将所有约束条件（包括绝对约束和目标约束，此时令目标约束的正负偏差变量均为零）的直线方程分别标示于坐标平面上。然后在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向2.确定系统约束的可行域。3.从第一个目标（最重要目标）起，分析半个平面的取舍并结合系统约束，确定满足第一目标的可行区域并确定达成目标的函数（1）要求不低于目标值：min{f(d-)}（2）要求不超过目标值：min{f(d+)}（3）要求恰好达到目标值：min{f(d-+d+)}4.第二目标在第一目标确定区域内选择,依此类推图解法的步骤：20/42)3,2,1(0,,,)4(56108)3(102)2(0)1(112)min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii＋－＋（x1x2(1)(2)d1+d1-(3)d2-d2+(4)d3-d3+GD满意解是线段GD上任意点其中G点X＝(2,4),D点X＝(10/3,10/3)05.51055.6112,410/3,10/35107例5.321/42)4,,1(0,,,)(30)(24)(50)(40)2(min21442331222111214332211iddxxdddxcddxbddxxaddxxddPdPdPzii＋Ox1x22040605020406050abd1-d1+d2-d2+cdd3-d3+d4-d4+(24,26)满意解X=(24，26)例322/42(a)(b)(c)(d)x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解(3,3))4,,1(0,,)1.4(82)1.4(1222)1.4(0)1.4(1232)1.4(124)1.4(16421442133212221112121iddxxfddxxeddxxdddxxcddxxbxaxii4433322211)()mindPddPddPdPz（046834622例423/42一、目标规划的特点：1．目标函数：min2．最优性判断：σj≥0时为最优3．非基变量检验数的特殊性：非基变量检验数中含有不同等级的优先因子，即因P1P2P3…Pk，所以检验数的正负首先取决于P1的系数的正负，若P1的系数为0，再由P2的系数的正负决定检验数的正负，然后依次类推。第三节目标规划的单纯形法pakkjj24/421.列出初始单纯形表。按照传统单纯形法求解检验数，此时由于检验数中必然会含有优先因子，按照优先因子的优先程度，将检验数分成多行，每行输入检验数中对应的优先因子的系数，则每个变量对应的总检验数即为∑（行系数*优先因子）；2.从最优先因子开始，检查其系数，观察其系数是否为非负，如非负，则完成。如含有负系数，则需要进行变量的替代；3.确定换入变量：从最优先因子开始，选择其负检验数中最小值所对应的变量为换入变量；（选择绝对值最大的负检验数）4.确定换出变量：按单纯形法中的最小比值规则确定，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。5.按单纯形法进行基变换运算，建立新的单纯形表，（注意：要对所有的行进行转轴运算）返回(1)；6.迭代运算停止的准则：（1）检验数p1，p2