线性目标规划

一、目标规划概述二、目标规划的数学模型三、目标规划的图解法四、目标规划的单纯形法第5章线性目标规划(GoalProgramming)一、目标规划概述•线性规划在实践中得到广泛应用，但有两个方面不足：一是不能处理多目标的优化问题；二是其约束条件过于刚性化，不允许约束资源有丝毫超差。•目标规划是为了解决这一不足而创建的一类数学模型。•线性规划是在一组线性约束条件下，寻求某一项目标的最优值，而实际问题往往要考虑多个目标的决策问题。•如核电站的设计问题，传统的单目标规划只允许设定一个目标，那么单一目标选择什么？电站建设费用最低，安全运行的可靠性最高，电能输出最大，对周围环境的影响最小。显然，上述目标都很重要，且又互相矛盾。这是一个多目标决策问题，普通的线性规划是无能为力的。1、问题的提出例1：工厂生产两种产品，受到原材料供应和设备工时的限制。在单件利润等有关数据已知的条件下，要求制订一个获利最大的生产计划，具体数据见下表。产品ⅠⅡ限量原材料(kg/件)51060设备工时(h/件)4440利润(元/件)68目标规划问题实例设产品Ⅰ、Ⅱ的产量分别为，建立线性规划模型：解得最优生产计划为件，件，利润为元。81x22x64maxz21,xx0,404460105..86max21212121xxxxxxtsxxZ如果工厂作决策时可能还需根据市场和工厂实际情况，考虑其它问题，如：（1）由于产品Ⅱ销售疲软，故希望产品Ⅱ的产量不超过产品Ⅰ的一半；（2）原材料严重短缺，原料数量只有60；（3）最好能节约4小时设备工时；（4）计划利润不少于48元。2、目标规划的基本概念（1）目标值和正、负偏差变量目标规划通过引入目标值和正、负偏差变量。所谓目标值是预先给定的某个目标的一个期望值。实际值（或决策值）是当决策变量x1、x2、…、xn选定以后目标函数的对应值。显然，实际值和目标值之间会有一定的差异，这种差异称为偏差变量(事先无法确定的未知量)，用d＋和d－表示。d＋——超出目标值的差值，称正偏差变量；d－——未达到目标值的差值，称负偏差变量；•当实际值超出目标值时，有d－＝0，d＋＞0；•当实际值未达到目标值时，有d＋＝0，d－＞0；•当实际值同目标值恰好一致时，d＋＝d－＝0。。即至少有一个为零中注意0,,,:dddd（2）绝对约束与目标约束绝对约束又称系统约束，是指必须严格满足的等式和不等式约束，如线性规划问题的所有约束都是绝对约束，不满足这些约束条件的解称为非可行解，所以它们是硬约束。目标约束是目标规划特有的，可把约束右端看做要追求的目标。在达到此目标值时允许发生正偏差或负偏差，因此在这些约束中加入正、负偏差变量，是软约束。6010521xx原材料严重短缺，原料数量只有60；①目标函数变为目标约束线性规划问题的目标函数，在给定目标值和偏差变量后可变换为目标约束。这样就将目标函数则转化为目标约束。比如：计划利润不少于48元。2186xx488621ddxx②绝对约束变为目标约束该约束的右端项看作目标值，再引入正、负偏差变量即可。1221xx或0221xx此为系统约束在达到此目标值时允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束，在给定目标值和加入正、负偏差变量之后，可以将绝对约束转化为目标约束。0221ddxx（3）优先因子（优先等级）与权系数在一个规划问题中，决策者在要求达到这些目标时，是有轻重缓急的，称这些目标是属于不同层次的优先等级。优先等级层次的高低可分别通过优先因子P1，P2，…表示，并规定Pk＞＞Pk＋1，符号“＞＞”表示“远大于”，表示Pk与Pk＋1，不是同一各级别的量，即Pk与Pk＋1有更大的优先权。对属于同一层次优先等级的不同目标，按其重要程度可分别乘上不同的权系数。权系数是一个个具体数字，乘上的权系数越大，表明该目标越重要。（4）目标规划的目标函数－－准则函数从决策者的要求分析：总希望得到的结果与规定的目标值间的偏差愈小愈好，由此决策者可根据自己的要求构造一个使总偏差量为最小的目标函数，这就是目标规划的目标函数称为准则函数，记为即目标函数是正、负偏变量的函数。ddfZ,min一般来说，可能提出的要求只能是以下三种情况之一，对应每种要求，可分别构造目标函数：构造目标函数的方法•如希望产品Ⅰ产量恰好等于产品Ⅱ的产量，即正、负偏变量都要尽可能地小，这时目标函数是：•如希望产品Ⅰ产量低于产品Ⅱ的产量，即允许达不到目标值，正偏差变量要尽可能地小,这时目标函数是：•如希望产品Ⅰ产量不低于产品Ⅱ的产量，即要求超过目标值，不得低于目标值，负偏差变量尽可能地小，这时目标函数是：021ddxx)(minddfz)(mindfz)(mindfz例1中目标函数的构成希望产品Ⅱ产量不超过产品Ⅰ产量的一半，即正偏差变量要尽可能地小，不希望上式中的d＋＞0，这时目标函数是：0221ddxxdmin364421ddxx希望能节约4小时设备工时，即正偏差变量要尽可能小，不希望上式中的d＋＞0，这时目标函数是：dmin488621ddxx希望计划利润不少于48元，即负偏差变量尽可能小，不希望上式中的d－＞0，这时目标函数是：dmin（5）满意解目标规划问题的求解是分级进行的，首先要求满足P1级目标的解；然后再保证P1级目标不被破坏的前提下，再要求满足P2级目标的解；…依次类推。总之，是在不破坏上一级目标的前提下，实现下一级目标的最优。因此，这样最后求出的解就不是通常意义下的最优解，我们称它为满意解。之所以叫满意解，是因为前面的目标是可以保证实现或部分实现的，后面的目标就不一定能保证实现。满意解这一概念的提出是对最优化概念的一种突破，显然它更切合实际，更便于运用，因而受到广大实际工作者的欢迎而被广泛采用。3、目标规划的数学模型在例1中若工厂提出的管理目标按优先级排列如下：级目标：希望产品Ⅱ的产量不超过产品Ⅰ的一半；级目标：最好能节约4小时设备工时；级目标：希望计划利润不小于48元；由于原材料严重短缺，故原材料约束作为绝对约束。试建立目标规划模型。1P2P3P021121ddxx36442221ddxx48863321ddxx)3,2,1(,iddii解：引入偏差变量目标约束：按优先级确定目标函数，级目标要求；级目标要求；级目标要求该问题的目标规划模型为：1P1mind2P2mind3P3mind其中①为绝对约束，②、③、④为目标约束。332211mindPdPdPz6010521xx021121ddxx36442221ddxx48863321ddxx3,2,10,,,21iddxxiis.t.而把级目标要求设为，其余依次后退优先级，得：1P0mind该问题也可以这样处理，把绝对约束①化为目标约束。601050021ddxx34231201mindPdPdPdPz601050021ddxx021121ddxx36442221ddxx48863321ddxx3,2,1,00,,,21iddxxiis.t.1、模型的一般形式),,2,1(0,n),1,2,(j0)2,1(),()2,1()(min1111LlddxmibxaLlqddxcddPZlljnjijijnjllljkjKkLllkllklk二、目标规划的数学模型（4）对同一优先等级中的各偏差变量，若需要可按其重要程度的不同，赋予相应的权系数2、目标规划问题的建模步骤（1）根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；klkl和（3）给各目标赋予相应的优先因子Pk(k=1,2,…,K)；（2）可根据决策者的需要，将某些或全部绝对约束转化为目标约束。这时只需要给绝对约束加上负偏差变量和减去正偏差变量即可；（5）根据决策者的要求，按下列情况之一构造一个由优先因子和权系数相对应的偏差变量组成的，要求实现极小化的目标函数。llddldld恰好达到目标值，取。允许超过目标值，取。不允许超过目标值，取。例3：某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲单位产品资源消耗若提出下列要求：（1）完成或超额完成利润指标50000元；（2）产品甲不超过200件，产品乙不低于250件；（3）现有钢材3600吨正好用完。试建立目标规划模型。分析：题目有三个目标层次，包含四个目标值。11dP)127(322ddP第三目标：)(443ddP32dd第二目标：有两个要求即甲，乙，但两个具有相同的优先因子，因此需要确定权系数。本题可用单件利润比作为权系数即70:120，化简为7:12。第一目标：规定利润的目标值为50000，正、负偏差为d＋、d－，则目标函数可以转换为目标约束，既70x1+120x2＋＝50000，同样，规定x2＝200，x3＝250则有11dd200221ddx250332ddx)3.2.1(0,jddjj规定3600的钢材正好用完，原式9x1+4x2≤3600则变为0,360049444421ddddxx)4,3,2,1(0,030001032000543600492502005000012070)()127(min2,121214421332221112144332211jddxxxxxddxxddxddxddxxddPddPdPZjj目标规划模型为：例4：某工艺品厂手工生产两种工艺品A、B，已知生产一件产品A需要耗费人力2工时，生产一件产品B需要耗费人力3工时。A、B产品单位利润分别为250元和125元。为了最大效率利用人力资源，确定生产首要任务是保证人员高负荷生产，要求每周总耗费人力资源不能低于600工时，但也不能超过680工时的极限；次要任务是要求每周的利润超过70000元；在前两个任务的前提下，为了保证库存需要，要求每周产品A和B的产量分别不低于200和120件，因为B产品比A产品更重要，不妨假设B完成最低产量120件的重要性是A完成200件的重要性的1倍。试求如何安排生产？解：本问题中有3个不同优先权的目标，不妨用P1、P2、P3表示从高至低的优先权。P1有两个目标：每周总耗费人力资源不能低于600工时，也不能超过680工时；P2有一个目标：每周利润超过70000元；P3有两个目标：每周产品A和B的产量分别不低于200和120件。采用简化模式，最终得到目标线性规划如下：)5,4,3,2,1(0,,0120d-200700001252506803260032..)2(min2,15524413321222111215343322111jddxdxddxddxxddxxddxxtsdPdPdPdPdPZjj某厂生产Ⅰ、Ⅱ两种产品，有关数据如表所示。试求获利最大的生产方案？ⅠⅡ拥有量原材料2111设备(台时)1210单件利润810在此基础上考虑：（1）产品Ⅱ的产量不低于产品Ⅰ的产量；（2）充分利用设备有效台时，不加班；（3）利润不小于56元。解:第一目标：即产品Ⅰ的产量不