运筹学目标规划

第5章目标规划(Goalprogramming)第1节目标规划的数学模型第2节目标规划的图解法第3节目标规划的单纯形法目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。线性规划只研究在满足一定条件下，单一目标函数取得最优解，在实际问题中，可能会同时考虑几个方面都达到最优：产量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。第1节目标规划的数学模型一、目标规划概述目标规划举例•例1.某工厂生产I、II两种产品，已知有关数据如表。试求获利最大的生产方案。产品I产品II拥有量原材料(kg)2111设备(hr)1210利润(元/件)810•实际上，工厂在作决策时，要考虑一系列因素：•(1)产品I的产量不大于产品II；•(2)原材料超过时，采购成本增加；•(3)设备台时尽量用完；•(4)尽可能达到并超过计划利润指标56元。1)线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。2)线性规划求最优解；目标规划是找到一个满意解。（一）、目标规划与线性规划的比较4)线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只求得满意解，就能满足需要（或更能满足需要）。3)线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。（二）、目标规划的基本概念•例1.某工厂生产I、II两种产品，已知有关数据如表。试求获利最大的生产方案。产品I产品II拥有量原材料(kg)2111设备(hr)1210利润(元/件)810•实际上，工厂在作决策时，要考虑一系列因素：•(1)产品I的产量不大于产品II；•(2)原材料超过时，采购成本增加；•(3)设备台时充分用完，不加班；•(4)尽可能达到并超过计划利润指标56元。x1≤x2，即x1-x2≤0；2x1+x2≤11；x1+2x2=10；8x1+10x2≥56；目标规划通过引入目标值g和偏差变量d，可以将目标函数转化为目标约束。目标值gk：是指预先给定的某个目标的一个期望值。实现值或决策值fk(xj)：是指当决策变量xj选定以后，目标函数的对应值。偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异，记为d。单词deviation的首字母。正偏差变量，记为d+：表示实现值超过目标值的部分。负偏差变量，记为d-：表示实现值未达到目标值的部分。1、决策变量xj和正、负偏差变量d+，d-在一次决策中，实现值不可能既超过目标值又未达到目标值，故有d＋×d－＝0，并规定d＋≥0，d－≥0绝对约束（系统约束）是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。引入目标值g、正偏差变量d+、负偏差变量d-后，就对某一问题有了新的限制，即目标约束。目标约束既可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。2、目标约束和绝对约束一般表示为：f(xj)=g+d+-d-思考：下列三种情形下，如何才算达到目标？•若决策目标中规定f(xj)g，则目标中d+=0；•若决策目标中规定f(xj)g，则目标中d-=0；•若决策目标中规定f(xj)=g，则目标中d+=d-=0.准则函数是一个使总偏差量为最小的目标函数，记为minz=f(d＋,d-)。对应一个目标约束，有以下三种情况，但只能出现其中之一：⑴.恰好达到规定的目标值，即f(xj)=g，正、负偏差变量d＋、d-都要尽可能小，则minz=f(d＋＋d-)。⑵.不超过目标值，即f(xj)g，正偏差变量d＋尽可能小，则minz=f(d＋)。⑶.超过目标值，即f(xj)g，负偏差变量d-尽可能小，则minz=f(d-)。3、准则函数（即目标规划中的目标函数）为了将不同级别的目标的重要性用数量表示，引进P1,P2,….，用它表示一级目标，二级目标，….的重要程度，规定P1P2P3…，称P1，P2，….,为级别系数。优先因子Pk是将决策目标按其重要程度排序并表示出来。P1P2…PkPk+1，k=1,2,…,K。例如，四个决策目标用四个优先因子排序的准则函数：权系数ωk区别具有同一个优先因子的两个目标的差别的情况。例如，目标i和目标j具有相同的优先因子Pk准则函数：4、优先因子(优先等级)Pk与优先权系数ωk)(zminjjiikddP443332211)(mindPddPdPdPz)127(322ddP譬如：对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。5、满意解（具有层次意义的解）•例1.产品I产品II拥有量原材料(kg)2111设备(hr)1210利润(元/件)810•(1)产品I的产量不大于产品II；•(2)原材料超过时，采购成本增加；•(3)设备台时充分用完，不加班；•(4)尽可能达到并超过计划利润指标56元。x1≤x2，即x1-x2≤0；2x1+x2≤11；x1+2x2=10；8x1+10x2≥56；•引入优先因子•P1：x1-x2≤0；•P2：2x1+x2≤11；•P3：x1+2x2=10；•P4：8x1+10x2≥56；•目标约束：•x1-x2=0+d1+-d1-；•2x1+x2=11+d2+-d2-；•x1+2x2=10+d3+-d3-；•8x1+10x2=56+d4+-d4-；•例1.产品I产品II拥有量原材料(kg)2111设备(hr)1210利润(元/件)810•(1)产品I的产量不大于产品II；•(2)原材料超过时，采购成本增加；•(3)设备台时尽量用完；•(4)尽可能达到并超过计划利润指标56元。x1≤x2，即x1-x2≤0；2x1+x2≤11；x1+2x2=10；8x1+10x2≥56；目标函数minP1d1+；minP2d2+；minP3(d3++d3-)；minP4d4-；minz=P1d1++P2d2++P3(d3++d3-)+P4d4-•目标约束：•x1-x2=0+d1+-d1-；•2x1+x2=11+d2+-d2-；•x1+2x2=10+d3+-d3-；•8x1+10x2=56+d4+-d4-；例a.某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的目标规划模型。12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲单位产品资源消耗若在例a中提出下列要求：(1)首先完成或超额完成利润指标50000元；(2)其次，产品甲不超过200件，产品乙不低于250件；(3)再次，现有钢材3600吨必须用完。若在例a中提出下列要求：(1)首先，完成或超额完成利润指标50000元；(2)其次，产品甲不超过200件，产品乙不低于250件；(3)再次，现有钢材3600吨必须用完。试建立目标规划模型。分析：本例引入3个优先因子P1,P2,P3；分析：题目有三个目标层次，包含四个目标值。第一目标：第二目标：有两个要求即甲，乙，但两个具有相同的优先因子P2，因此需要确定权系数。本题可用单件利润比作为权系数即70:120，化简为7:12。11dP32dd)127(322ddP第三目标：)(443ddP)4,3,2,1(0,,030001032000543600492502005000012070)()127(min2121214421332221112144332211jddxxxxxddxxddxddxddxxddPddPdPZjj目标规划模型为：12070利润3000103台时200054煤炭360049钢材资源乙甲某厂生产Ⅰ、Ⅱ两种产品，有关数据如表所示。试求获利最大的生产方案？ⅠⅡ拥有量原材料2111设备(台时)1210单件利润810在此基础上考虑：(1)产品Ⅱ的产量不低于产品Ⅰ的产量；(2)充分利用设备有效台时，不加班；(3)利润不小于56元。解:分析第一目标：minz1=第二目标：minz2=11dP)(222ddP例2：第三目标：minz3=33dPx1≤x2，即x1-x2≤0；x1+2x2=10；8x1+10x2≥56；规划模型：)3,2,1(0,,0561081020112)(min2,1332122211121213322211jddxddxxddxxddxxxxdPddPdPZjj（一）、模型的一般形式),,2,1(0,n),1,2,(j0),,2,1(),(),,2,1()(min1111KkddxmibxaKkgddxcddPZkkjnjijijnjkkkjkjLlKkklkklkl二、目标规划的数学模型其中，gk为目标约束的目标值；bi为绝对约束的资源值。约束目标函数目标约束资源约束（二）、建模的步骤1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；klkl和4、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。3、给各目标赋予相应的优先因子Pl(l=1,2,…,L)。2、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。5、根据决策者的要求，按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即准则函数。kkddkdkd⑴.恰好达到目标值，取。⑵.允许超过目标值，取。⑶.不允许超过目标值，取。练习1：1.已知条件如表所示工序型号每周最大加工能力ABⅠ（小时/台）Ⅱ（小时/台）436215070利润（元/台）300450如果工厂经营目标的期望值和优先等级如下：P1:每周总利润不得低于10000元；P2:因合同要求，A型机每周至少生产10台，B型机每周至少生产15台；P3:希望工序Ⅰ的每周生产时间正好为150小时，工序Ⅱ的生产时间最好用足，甚至可适当加班。试建立这个问题的目标规划模型。5,4,3,2,10,,,702315064151010000450300)()32(min21552144213322211121544332211iddxxddxxddxxddxddxddxxdddpddpdpfii练习2、已知一个生产计划的线性规划模型为01006014021230max21212121xxxxxxxZ)()()(丙资源乙资源甲资源其中目标函数为总利润，x1,x2为产品A、B产量。现有下列目标：1、要求总利润必须超过2500元；2、由于甲资源供应比较紧张，不要超过现有量140；3、考虑产品受市场影响，为避免积压，A、B的生产量不超过60件和100件。试建立目标规划模型。解：以产品A、B的单件利润比2.5：1为权系数，模型如下：)4,3,2,1(0,,010060140225001230)5.2(min21442331222111214332211kddxddxddxddxxddxxddPdPdPZkk（三）、小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量x