一章六节_线性目标规划

线性目标规划(Goalprogramming)目标规划的图解法目标规划的单纯形法目标规划概述及其模型目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。2、线性规划求最优解；目标规划是找到一个满意解。1、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。第一节目标规划概述及其模型（一）目标规划与线性规划的比较4、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。3、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。目前，目标规划已经在经济计划、生产管理、物流管理、市场分析、财务管理等方面得到了广泛的应用。例1:某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲单位产品资源消耗（二）目标规划的基本概念设：甲产品x1，乙产品x2一般有：maxZ=70x1+120x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1，x2≥0同时：maxZ1=70x1+120x2minZ2=x1maxZ3=x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1，x2≥0显然，这是一个多目标规划问题，用线性规划方法很难找到最优解。目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。目标值：是指预先给定的某个目标的一个期望值。实现值或决策值：是指当决策变量xj选定以后，目标函数的对应值。偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异,记为d。正偏差变量：表示实现值超过目标值的部分，记为d＋。负偏差变量：表示实现值未达到目标值的部分，记为d－。1、目标值和偏差变量当完成或超额完成规定的指标则表示：d＋≥0,d－＝0当未完成规定的指标则表示：d＋＝0,d－≥0当恰好完成指标时则表示：d＋＝0,d－＝0∴d＋×d－＝0成立。引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。目标约束既可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。在一次决策中，实现值不可能既超过目标值又未达到目标值，故有d＋×d－＝0,并规定d＋≥0,d－≥02、目标约束和绝对约束绝对约束（系统约束）是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。例如：在例一中，规定Z1的目标值为50000,正、负偏差为d＋、d－,则目标函数可以转换为目标约束，既70x1+120x2＋＝50000，同样，若规定Z2＝200，Z3＝250则有11dd200221ddx250332ddx)3.2.1(0,jddjj若规定3600的钢材必须用完，原式9x1+4x2≤3600则变为0,360049444421ddddxx达成函数是一个使总偏差量为最小的目标函数，记为minZ=f（d＋、d－）。一般说来，有以下三种情况，但只能出现其中之一：⑴.要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ=f（d＋＋d－）。⑵.要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ=f（d＋）。⑶.要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ=f（d－）。3、达成函数（即目标规划中的目标函数）优先因子Pk是将决策目标按其重要程度排序并表示出来。P1P2…PkPk+1…PK，k=1.2…K。权系数ωk区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。4、优先因子（优先等级）与优先权系数5、满意解（具有层次意义的解）若在例一中提出下列要求：1、超额完成利润指标50000元；2、产品甲不超过200件，产品乙不低于250件；3、现有钢材3600吨必须用完。试建立目标规划模型。分析：题目有三个目标层次，包含四个目标值。第一目标：第二目标：有两个要求即甲，乙，两者具有相同的优先因子，为区分两者的差别（或重要程度），需要确定权系数。本题可用单件利润比作为权系数即70:120，化简为7:12。11dP32dd)127(322ddP例2:第三目标：)(443ddP)4.3.2.1(0.,030001032000543600492502005000012070)()127(min2121214421332221112144332211jddxxxxxddxxddxddxddxxddPddPdPZjj目标规划模型为：某厂生产Ⅰ、Ⅱ两种产品，有关数据如表所示。试求获利最大的生产方案？ⅠⅡ拥有量原材料2111设备(台时)1210单件利润810在此基础上考虑：1、产品Ⅱ的产量不低于产品Ⅰ的产量；2、充分利用设备有效台时，不加班；3、利润不小于56元。解:分析第一目标：即产品Ⅰ的产量不大于Ⅱ的产量。第二目标：11dP)(222ddP例3：第三目标：33dP规划模型：)3.2.1(0.,0112561081020)(min21213321222111213322211jddxxxddxxddxxddxxdPddPdPZjj（三）目标规划数学模型1、目标规划数学模型的一般形式)2.1(0.n)1.2(j0)2.1().()2.1()(min1111KkddxmibxaKkgddxcddPZkkjnjijijnjkkkjkjLlKkklkklkl达成函数目标约束其中：gk为第k个目标约束的预期目标值，和为pl优先因子对应各目标的权系数。lklk2、建模的步骤（1）根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束。klkl和（4）对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。（3）给各目标赋予相应的优先因子Pk（k=1.2…K）。（2）可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。（5）根据决策者的要求，按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。minZ=f()ddmin()Zfdmin()Zfd1.恰好达到目标值，即取正、负偏差变量都要尽可能地小，这时2.要求超过目标值，即超过量不限，但必须是负偏量要尽可能小，这时3.要求不超过目标值，即允许达不到目标函数值，即正偏量要尽可能小，这时3、小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,xsxaxixsxad约束条件绝对约束目标约束绝对约束解最优最满意第二节目标规划图解法目标规划的图解法：适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。图解法解题步骤：1.将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量，令其等于0）的直线方程分别标示于坐标平面上。2.确定系统约束的可行域。3.在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向。目标规划的图解法•4.求满足最高优先等级目标的解•5.转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解•6.重复5，直到所有优先等级的目标都已审查完毕为止，确定最优解和满意解。目标规划的图解法•例4用图解法求解下列目标规划问题112223334412121112221233124412min)3()416(4.1)412(4.1)2312(4.1)0(4.1)2212(4.1)28(4.1),,,0(1,,4)iizPdPddPddPdxaxbxxddcxxdddxxddexxddfxxddi（目标规划的图解法(a)(b)(c)(d)x2x1(e)(f)d1-d1+d2+d2-d3-d3+d4-d4+满意解(3,3)12121112221233124412416(4.1)412(4.1)2312(4.1)0(4.1)2212(4.1)28(4.1),,,0(1,,4)iixaxbxxddcxxdddxxddexxddfxxddi4433322211)()mindPddPddPdPz（046834622目标规划的图解法11222331212111222123312min)211()0()210()81056(),,,0(1,2,3)iizPdPddPdxxaxxddbxxddcxxdddxxddi＋－＋（x1x2(a)(b)d1+d1-(c)d2-d2+(d)d3-d3+GD满意解是线段GD上任意点其中G点X＝(2,4),D点X＝(10/3,10/3)05.51055.6112,410/3,10/35107例5目标规划的图解分析法)4,,1(0,,,)(30)(24)(50)(40)2(min21442331222111214332211iddxxdddxcddxbddxxaddxxddPdPdPzii＋Ox1x22040605020406050abd1-d1+d2-d2+cdd3-d3+d4-d4+(24,26)满意解X=(24，26)例6目标规划应用举例•例7已知一个生产计划的线性规划模型如下，其中目标函数为总利润，x1,x2为产品A、B产量。0)(100)(60)(14021230max21212121xxxxxxxZ丙资源乙资源甲资源现有下列目标：1.要求总利润必须超过2500元；2.考虑产品受市场影响，为避免积压，A、B的生产量不超过60件和100件；3.由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。目标规划应用举例解：以产品A,B的单件利润比2.5:1为权系数，模型如下：)4.3.2.1(0,,010060100601402250012305.2min21214423312221112123423211lddxxxddxddxddxxddxxdPdPdPdPZll目标规划应用举例0x20⑴x11401201008060402020406080100⑵⑶⑷2d2d1d1d3d3d4d4dABCD)4.3.2.1(0,,010060100601402250012305.2min21214423312221112123423211ld