建模目标规划

1《运筹学》第四章目标规划目标规划(Goalprogramming)2.目标规划的图解法3.目标规划的单纯形法1.目标规划概述5.Lingo求解4.应用问题举例2《运筹学》第四章目标规划•引例1某工厂生产Ⅰ，Ⅱ两种产品，已知有关数据见下表。试求获利最大的生产方案。•解：这是求获利最大的单目标的规划问题，用x1，x2分别表示Ⅰ，Ⅱ产品的产量，其线性规划模型表述为：ⅠⅡ拥有量原材料(kg)设备(hr)21121110利润(元/件)8100,102112108max21212121xxxxxxxxz满足约束条件：目标函数：3《运筹学》第四章目标规划•用图解法求得最优决策方案为：x1*=4,x2*=3,z*=62(元)。(4,3)0,102112108max21212121xxxxxxxxz满足约束条件：目标函数：4《运筹学》第四章目标规划(IV)应尽可能达到并超过计划利润指标：56元。这样的产品决策问题便构成了一个多目标决策问题，目标规划方法正是解这类决策问题的方法之一。实际上，工厂在作决策时，需要考虑包括市场因素在内等一系列条件。例如:(I)根据市场信息，产品Ⅰ的销售量有下降的趋势，因而希望产品Ⅰ的产量不应大于产品Ⅱ。(II)当超过计划供应原材料时，需用高价采购，会使成本大幅度增加。(III)应尽可能充分利用设备台时，但不希望加班。5《运筹学》第四章目标规划目标规划是在线性规划的基础上，为适应经济管理中多目标决策的需要而逐步发展起来的一个分支。1、线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。1目标规划概述（一）目标规划与线性规划的比较线性规划建模的局限性：•线性规划要求所有求解的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；6《运筹学》第四章目标规划2、线性规划求最优解；目标规划是找到一个满意解。•线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理。但在实际问题中，目标和约束好似可以相互转化的，处理时不一定要严格区分；•线性规划在处理问题时，将各个约束(也可看作目标)的地位看成同等重要，而在实际问题中，各个目标的重要性即有层次上的差别，也有在同一层次上不同权重的差别7《运筹学》第四章目标规划4、线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要（或更能满足需要）。3、线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。目前，已经在经济计划、生产管理、经营管理、市场分析、财务管理等方面得到了广泛的应用。8《运筹学》第四章目标规划•目标值和偏差变量•目标约束和绝对约束•达成函数（即目标规划中的目标函数）•优先因子（优先等级）与优先权系数•满意解（具有层次意义的解）（二）目标规划的基本概念9《运筹学》第四章目标规划目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。目标值：是指预先给定的某个目标的一个期望值。实现值或决策值：是指当决策变量xj选定以后，目标函数的对应值。偏差变量（事先无法确定的未知数）：是指实现值和目标值之间的差异,记为d。正偏差变量：表示实现值超过目标值的部分，记为d＋。负偏差变量：表示实现值未达到目标值的部分，记为d－。1、目标值和偏差变量10《运筹学》第四章目标规划当完成或超额完成规定的指标则表示：d＋≥0,d－＝0当未完成规定的指标则表示：d＋＝0,d－≥0当恰好完成指标时则表示：d＋＝0,d－＝0∴d＋×d－＝0成立。引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。目标约束即可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。在一次决策中，实现值不可能既超过目标值又未达到目标值，故有d＋×d－＝0,并规定d＋≥0,d－≥02、目标约束和绝对约束11《运筹学》第四章目标规划绝对约束（系统约束）是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需要将绝对约束变换为目标约束，例如：在引例1中，目标值目标函数可以转换为目标约束，既0,102112108max21212121xxxxxxxxz满足约束条件：目标函数：目标函数z=8x1+10x2变换为目标约束8x1+10x2+d1−−d1+=56约束条件2x1+x2≤11变换为目标约束2x1+x2+d2−−d2+=1112《运筹学》第四章目标规划达成函数是一个使总偏差量为最小的目标函数，记为minZ=f（d＋、d－）。一般说来，有以下三种情况，但只能出现其中之一：⑴.要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ=f（d＋＋d－）。⑵.要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ=f（d＋）。⑶.要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ=f（d－）。对于由绝对约束转化而来的目标函数，也照上述处理即可。3、达成函数（即目标规划中的目标函数）13《运筹学》第四章目标规划优先因子Pk是将决策目标按其重要程度排序并表示出来。P1P2…PkPk+1…PK，k=1.2…K。权系数ωk区别具有相同优先因子的两个目标的差别，决策者可视具体情况而定。对于这种解来说，前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现。4、优先因子（优先等级）与优先权系数5、满意解（具有层次意义的解）14《运筹学》第四章目标规划某厂生产Ⅰ、Ⅱ两种产品，有关数据如表所示。ⅠⅡ拥有量原材料2111设备(台时)1210单件利润810经研究提出下列要求：1、产品Ⅱ的产量不低于产品Ⅰ的产量；2、充分利用设备有效台时，不加班；3、利润不小于56元。例2：（三）目标规划的数学模型解：设x1，x2分别表示产品Ⅰ和产品Ⅱ的产量。di+,di-分别为第i个目标的正、负偏差变量建立目标约束：产品Ⅱ的产量不低于产品Ⅰ的产量:01121ddxx21xx15《运筹学》第四章目标规划1022221ddxx561083321ddxx11221xx充分利用设备有效台时:利润不小于56元:原材料约束:10221xx5610821xx优先等级:第一目标：即产品Ⅰ的产量不大于Ⅱ的产量。11dP第二目标：即充分利用设备有效台时，不加班)(222ddP第三目标：即利润不小于56元33dP16《运筹学》第四章目标规划达成函数：)3,2,1(0,,0,112561081020)(min21213321222111213322211iddxxxxddxxddxxddxxdPddPdPZii目标规划模型：3322211)(mindPddPdPZ17《运筹学》第四章目标规划)2.1(0.n)1.2(j0)2.1().()2.1()(min1111LlddxmibxaLlqddxcddPZlljnjijijnjllljkjKkLllkllklk目标规划模型一般形式18《运筹学》第四章目标规划建模的步骤1、根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；klkl和4、对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数。3、给各目标赋予相应的优先因子Pk（k=1.2…K）。2、可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可。19《运筹学》第四章目标规划5、根据决策者的要求，按下列情况之一llddldld⑴.恰好达到目标值，取。⑵.允许超过目标值，取。⑶.不允许超过目标值，取。构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数，即达成函数。20《运筹学》第四章目标规划小结线性规划LP目标规划GP目标函数min,max系数可正负min,偏差变量系数≥0变量xi,xsxaxixsxad约束条件系统约束（绝对约束）目标约束系统约束解最优最满意21《运筹学》第四章目标规划图解法同样适用两个变量的目标规划问题，但其操作简单，原理一目了然。同时，也有助于理解一般目标规划的求解原理和过程。图解法解题步骤如下：1、确定各约束条件的可行域，即将所有约束条件（包括目标约束和绝对约束，暂不考虑正负偏差变量）在坐标平面上表示出来；2目标规划的图解法2、在目标约束所代表的边界线上，用箭头标出正、负偏差变量值增大的方向；22《运筹学》第四章目标规划5、重复4，直到所有优先等级的目标都已审查完毕为止；3、求满足最高优先等级目标的解；4、转到下一个优先等级的目标，再不破坏所有较高优先等级目标的前提下，求出该优先等级目标的解；6、确定最优解和满意解。23《运筹学》第四章目标规划•某电视机厂装配黑白和彩色电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该企业决策者确定的目标为：•第一优先级：充分利用装配线每周计划开动40小时；•第二优先级：允许装配线加班；但加班时间每周尽量不超过10小时；•第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其权数为2。•试建立该问题的目标规划模型，并求解黑白和彩色电视机的产量。例324《运筹学》第四章目标规划⑴⑵⑶A01020304050607080102030405060x2x1B1d1d2d2dC3d3d⑷4d4dDEFHGE(24,26)为所求的满意解。)41(0,,0,30245040)2(min21442331222111214332211iddxxddxddxddxxddxxddPdPdPZii解：设x1，x2分别表示彩色和黑白电视机的产量。25《运筹学》第四章目标规划012345678123456⑴⑵⑶Ax2x1B1d1d2d2dCB(0.6250,4.6875)C(0,5.2083)，B、C线段上的所有点均是该问题的解（无穷多最优解）。)2.1(0,0,821025.621210)(min21212221112122111lddxxxxddxxddxxdPddPZll例4、用图解法求解目标规划问题26《运筹学》第四章目标规划例5、已知一个生产计划的线性规划模型为01006014021230max21212121xxxxxxxZ)()()(丙资源乙资源甲资源其中目标函数为总利润，x1,x2为产品A、B产量。现有下列目标：1、要求总利润必须超过2500元；2、考虑产品受市场影响，为避免积压，A、B的生产量不超过60件和100件；3、由于甲资源供应比较紧张，不要超过现有量140。试建立目标规划模型，并用图解法求解。27《运筹学》第四章目标规划解：以产品A、B的单件利润比2.5：1为权系数，模型如下：)4.3.2.1(0,,010060140225001230)5.2(min21442331222111212343211lddxddxddxddxxddxxdPddPdPZ