《运筹学》第四章 目标规划

目标规划(Goalprogramming)目标规划的图解法目标规划的单纯形法目标规划应用举例目标规划问题及其数学模型目标规划的方法是在1961年由查恩斯(A.Charnes)和库伯(W.W.Cooper)提出的它是在线性规划的基础上，适应企业经营管理中多目标决策的需要而逐步发展起来的。目标规划是在企业决策者所规定的若干指标值及要求实现这些指标的先后顺序后，并在给定有限资源条件下，求得总的偏离指标值为最小的方案，称这方案为满意方案。目标规划处理多种目标的关系，求得更切合实际要求的解只能处理一个目标目标规划线性规划可以在相互矛盾的约束条件下找到满意解满足所有约束条件的可行解找到的最优解是指尽可能地达到或接近一个或若干个已给定的指标值约束条件同等重要可根据实际需要给予轻重缓急或主次之分的考虑可以认为目标规划更能确切地描述和解决经营管理中的许多实际问题一种简单、实用的处理多目标决策问题的方法。在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。一、目标规划问题及其数学模型（一）目标规划问题的提出单一目标问题例1解：可用线性规划的模型来描述产品ⅠⅡ限量原材料（kg/件）51060设备工时（h/件）4440利润（元/件）68目标函数：maxz=6x1+8x2约束条件：5x1+10x2≤604x1+4x2≤40x1，x2≥0最优解：x1=8件，x2=2件，maxz=64元（二）目标规划的数学模型实际上工厂在做决策时，要考虑市场等其他条件：1、根据市场信息，产品Ⅱ的销售量已有下降的趋势，故考虑产品Ⅱ的产量最好不大于产品Ⅰ的一半；2、由于原材料严重短缺，生产中应避免过量消耗；3、最好能节约设备工时（4h）；4、应尽可能达到并超过预计利润指标（48元）。工厂现在的生产、经营问题——多目标决策问题。引入与建立目标规划数学模型有关的概念：1、引入一种新的变量——正、负偏差变量d+、d-，d+:可能实现值超过规定目标值的偏差量，d+≥0。d-:可能实现值未达到规定目标值的偏差量，d-≥0d+•d-=02、约束条件—绝对（硬）约束、目标（软）约束3、优先因子（优先等级）P1，P2，…，规定PlPl+1，l=1，2，…。表示Pl比Pl+1有更大的优先权。这意味着当目标与目标之间发生冲突时应按其优先等级来实现。具有相同优先因子的目标，其重要程度用不同的权系数表示。4、目标规划的目标函数当完成或超额完成规定的指标则表示：d＋≥0,d－＝0当未完成规定的指标则表示：d＋＝0,d－≥0当恰好完成指标时则表示：d＋＝0,d－＝0∴d＋×d－＝0成立。在一次决策中，实现值不可能既超过目标值又未达到目标值，故有d＋×d－＝0,并规定d＋≥0,d－≥01、引入一种新的变量——正、负偏差变量d+、d-引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。目标约束是目标规划中特有的，是软约束。2、约束条件—绝对（硬）约束、目标（软）约束绝对约束是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。①要求恰好达到目标值，即正、负偏差变量尽可能地小minZ=f（d++d-）minZ=f（d+）minZ=f（d-）③要求超过目标值，即要实现负偏差变量为零或最小②要求不超过目标值，即要使正偏差变量为零或最小（实现最少或为零）4、目标规划的目标函数由各目标约束的正、负偏差变量及相应的优先因子和权系数构成。使总偏差量为最小化的目标函数minZ=f（d+，d-）对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。5、满意解例题1，分析：由于原材料严重短缺，生产中应避免过量消耗受到严格限制的基础上按顺序考虑其他目标的实现目标优先等级：1、P1—产品Ⅱ的产量最好不大于产品Ⅰ的一半2、P2—最好能节约设备工时4h。3、P3—总利润尽可能达到并超过48元。由此，可以如下建立该问题的最优化模型——决策变量：x1——产品Ⅰ的产量，x2——产品Ⅱ的产量。偏差变量：P1等级：正、负偏差变量——d1+、d1-P2等级：正、负偏差变量——d2+、d2-P3等级：正、负偏差变量——d3+、d3-x1、x2、d1+、d1-、d2+、d2-、d3+、d3-≥0约束条件：绝对约束：5x1+10x2≤60目标约束：x1-2x2+d1--d1+=0（P1）4x1+4x2+d2--d2+=36（P2）6x1+8x2+d3--d3+=48（P3）目标函数：minZ=P1d1-+P2d2++P3d3-某厂生产Ⅰ、Ⅱ两种产品，有关数据如表所示。试求获利最大的生产方案？ⅠⅡ拥有量原材料2111设备(台时)1210单件利润810在此基础上考虑：1、产品Ⅱ的产量不低于产品Ⅰ的产量；2、充分利用设备有效台时，不加班；3、利润不小于56元。解:分析第一目标：即产品Ⅰ的产量不大于Ⅱ的产量。第二目标：11dP)(222ddP例2：第三目标：33dP规划模型：)3.2.1(0.,0112561081020..)(min21213321222111213322211jddxxxddxxddxxddxxtsdPddPdPZjj),2,1(0,n),1,2(j0),2,1(),(),2,1(..),2,1(,)(min111KkddxmibxaKkgddxctsLldWdWPZkkjnjijijnjkkkjkjKkllkllkl目标规划数学模型的一般形式权系数优先因子对应各目标的为和值，个目标约束的预期目标为第llk-lkkWWgPk建模的步骤1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；lklkWW和4、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。3、给各目标赋予相应的优先因子Pl（l=1.2…L）。2、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。5、根据决策者的要求，按下列情况之一：llddldld⑴恰好达到目标值，取。⑵允许超过目标值，取。⑶不允许超过目标值，取。构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数。小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,xsxaxixsxad约束条件绝对约束目标约束、绝对约束解最优最满意图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。图解法解题步骤如下：1、确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来；2、在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；二、目标规划的图解法3、求满足最高优先等级目标的解；4、转到下一个优先等级的目标，在不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；5、重复4，直到所有优先等级的目标都已审查完毕为止；6、确定最优解和满意解。)3.2.1(0.,0112561081020..)(min21213321222111213322211jddxxxddxxddxxddxxtsdPddPdPZjj例3用图解法求解例2的目标规划问题⑴⑵⑶⑷CD2d2d1d3d结论：有无穷多最优解C（2，4）、D（10/3，10/3）)..j(d.d,xxxddxxddxxddxxdP)dd(PdPZminjj3210011256108102021213321222111213322211例4：用图解法求下列目标规划问题minZ=P1d1-+P2d2++P3（2d3-+1d4-）x1+x2+d1--d1+=40x1+x2+d2--d2+=40+10=50x1+d3--d3+=24x2+d4--d4+=30x1、x2、di-、di+-≥0i=1,2,3,4d3-d1-d3+d4+d2+d1+d4-d2-x2x1x1+x2=40x1+x2=50x1=24x2=30满意解（24，26）minZ=P1d1-+P2d2++P3（2d3-+1d4-）s.t.x1+x2+d1--d1+=40x1+x2+d2--d2+=40+10=50x1+d3--d3+=24x2+d4--d4+=30x1、x2、di-、di+-≥0i=1,2,3,4例5：某车间计划生产两种产品。考虑:①充分利用供电部门分配的电量限额指标62.5kw/日;②考虑完成与超额完成利润指标10元/日。每日可给车间供应所需原料8t。其他有关数据汇总于下表。应当如何确定产品A、B的产量。产品耗电量（kw/件）材料（t/件）利润（元/件）AB10122112)2.1(0,0821025.621210..)(min21212221112122111lddxxxddxxddxxtsdPddPZll解：目标规划模型012345678123456⑴⑵⑶Ax2x1B1d1d2d2dCB(0.6250,4.6875)、C(0,5.2083)，B、C线段上的所有点均是该问题的解（无穷多最优解）。)2.1(0,0821025.621210)(min21212221112122111lddxxxddxxddxxdPddPZll例6、已知一个生产计划的线性规划模型为01006014021230max21212121xxxxxxxZ)()()(丙资源乙资源甲资源其中目标函数为总利润，x1,x2为产品A、B产量。现有下列目标：1、要求总利润必须超过2500元；2、考虑产品受市场影响，为避免积压，A、B的生产量不超过60件和100件；3、由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。解：以产品A、B的单件利润比2.5：1为权系数，模型如下：)4.3.2.1(0,,010060140225001230)5.2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll0x20⑴x11401201008060402020406080100⑵⑶⑷2d2d1d1d3d3d4d4dABCD结论：C(60,58.3)为所求的满意解。作图：)4.3.2.1(0,,010060140225001230)5.2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZll检验：将上述结果带入模型，因＝＝0；＝＝0；＝0，存在；＝0，存在。所以：minZ=P32d2d1d1d3d3d4d4d2d将x1＝60，x2＝58.3带入约束条件，得30×60＋12×58.3＝2499.6≈2500；2×60+58.3=178.3140；1×60＝601×58.3＝58.3100由上可知：若A、B的计划产量为60件和58.3件时，所需甲资源数量将超过现有库存。在现有条件下，此解为非可行解。为此，企业必须采取措施降低A、B产品对甲资源的消耗量，