运筹学-目标规划

1第5章目标规划Subtitle学习要点了解目标规划与线性规划的异同理解目标约束中的正负偏差变量思考目标约束与系统约束的差异理解目标的优先级和目标权系数了解目标规划图解法和单纯形法目标规划本章内容重点目标规划模型目标规划的几何意义目标规划的单纯形方法问题的提出•线性规划的局限性•线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度(即优先顺序)也不相同，有些目标之间往往相互发生矛盾。•线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。•线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。•求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。•为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。问题的提出5第一节多目标规划问题一、线性规划的局限性•线性规划的局限性只能解决一组线性约束条件下，某一目标而且只能是一个目标的最大或最小值的问题•实际决策中，衡量方案优劣考虑多个目标生产计划决策，通常考虑产值、利润、满足市场需求等生产布局决策，考虑运费、投资、供应、市场、污染等•这些目标中，有主要的，也有次要的；有最大的，有最小的；有定量的，有定性的；有互相补充的，有互相对立的，LP则无能为力•目标规划（GoalProgramming）多目标线性规划含有多个优化目标的线性规划目标规划与线性规划的比较•线性规划只讨论一个线性目标函数在一组线性约束条件下的极值问题；而目标规划是多个目标决策，可求得更切合实际的解。•线性规划求最优解；目标规划是找到一个满意解。•线性规划中的约束条件是同等重要的，是硬约束；而目标规划中有轻重缓急和主次之分，即有优先权。•线性规划的最优解是绝对意义下的最优，但需花去大量的人力、物力、财力才能得到；实际过程中，只要求得满意解，就能满足需要(或更能满足需要)。目标规划与线性规划的比较例5-1：某厂计划在下一个生产周期内生产甲、乙两种产品，已知资料如表所示。试制定生产计划，使获得的利润最大？同时，根据市场预测，甲的销路不是太好，应尽可能少生产；乙的销路较好，可以扩大生产。试建立此问题的数学模型。12070单件利润3000103设备台时200054煤炭360049钢材资源限制乙甲单位产品资源消耗目标规划数学模型设：甲产品x1，乙产品x2根据市场预测：maxZ=70x1+120x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1，x2≥0maxZ1=70x1+120x2minZ2=x1maxZ3=x29x1+4x2≤36004x1+5x2≤20003x1+10x2≤3000x1，x2≥0这些目标之间相互矛盾，一般的线性规划方法不能求解9第一节多目标规划问题二、多目标规划的提出11111221221122221122ln11112211211222221122max(min)max(min)max(min)(,)(,)s.t.nnnnlllnnnnnmmGcxcxcxGcxcxcxGcxcxcxaxaxaxbaxaxaxbaxax12(,),,0mnnmnaxbxxx多目标线性规划模型的原始一般形式如下：n个决策变量，m个约束条件，L个目标函数。当L=1时，即为我们熟悉的单目标线性规划模型。OR:SM10二、多目标规划的提出OR:SM11OR:SM12OR:SM13OR:SM14上述OR:SM15OR:SM16OR:SM17OR:SM18OR:SM19OR:SM20OR:SM21OR:SM22第一节多目标规划问题三、多目标的处理方法•加权系数法：为每一目标赋一权数，把多目标转化成单目标。但权系数难以科学确定。•优先等级法：各目标按重要性归不同优先级而化为单目标。•有效解法：寻求能照顾到各目标而使决策者感到满意的解。但可行域大时难以列出所有有效解的组合。•目标规划法：对每一个目标函数引入正的或负的偏差变量；引入目标的优先等级和加权系数。OR:SM23第二节目标规划的数学模型1.目标期望值每一个目标希望达到的期望值(或目标值、理想值)。根据历史资料、市场需求或上级部门的布置等来确定。一、目标值和偏差变量目标规划通过引入目标值和偏差变量，可以将目标函数转化为目标约束。实现值或决策值：是指当决策变量xj选定以后，目标函数的对应值。24第二节目标规划的数学模型2、偏差变量正偏差变量dk+表示第k个目标超过期望值的数值；负偏差变量dk-表示第k个目标未达到期望值的数值。同一目标的dk+和dk-中至少有一个必须为零。偏差变量(事先无法确定的未知数)：是指实现值和目标值之间的差异,记为d。偏差可能存在正的或负的。正偏差变量:表示实现值超过目标值的部分，记为d＋。负偏差变量:表示实现值未达到目标值的部分，记为d－。目标规划的数学模型在一次决策中，实现值不可能既超过目标值又未达到目标值，故有d＋×d－＝0,并规定d＋≥0,d－≥0当完成或超额完成规定的指标则表示：d＋≥0,d－＝0当未完成规定的指标则表示：d＋＝0,d－≥0当恰好完成指标时则表示：d＋＝0,d－＝0目标规划的数学模型二.目标约束和绝对约束引入了目标值和正、负偏差变量后，就对某一问题有了新的限制，既目标约束。目标约束即可对原目标函数起作用，也可对原约束起作用。目标约束是目标规划中特有的，是软约束。绝对约束(系统约束)是指必须严格满足的等式或不等式约束。如线性规划中的所有约束条件都是绝对约束，否则无可行解。所以，绝对约束是硬约束。目标规划的数学模型例如：在例一中，规定Z1的目标值为50000,正、负偏差为d＋、d－,则目标函数可以转换为目标约束，既:50000120701121--ddxx若规定3600的钢材必须用完，原式9x1+4x2≤3600变为3600494421--ddxx28第二节目标规划的数学模型--njkkjkjEddxc1*引入正负偏差变量，对各个目标建立目标约束(软约束)1.目标约束表示29例：甲乙产品的最优生产计划。产品资源甲乙现有资源设备A2016设备B0210设备C3432单位利润35•根据市场需求/合同规定：希望尽量扩大甲产品减少乙产品产量。•又增加二个目标：maxZ1=3x1+5x2maxZ2=x1minZ3=x22x1≤162x2≤103x1+4x2≤32x1，x2≥030第二节目标规划的数学模型要求：目标一是利润最大，拟定利润目标是30；目标二是减少乙产品产量但希望不低于4件；目标三是甲产品产量希望不少于6件；对各目标引入正、负偏差变量：3x1+5x2+d1--d1+=30x2+d2--d2+=4x1+d3–-d3+=6目标规划的数学模型三.优先因子(优先等级)与优先权系数目标等级化:将目标按重要性程度不同依次分成一级目标、二级目标…..。最次要的目标放在次要的等级中。(1)对同一目标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。(2)不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别目标上的收获不可弥补。故在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。(3)同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可有其余目标的适当收获来弥补。目标规划的数学模型三.优先因子(优先等级)与优先权系数优先因子Pk是将决策目标按其重要程度排序并表示出来。P1P2…PkPk+1…PK，k=1,2…,K。表示Pk比Pk+1有更大的优先权。即首先保证P1级目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的；依此类推。若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数ωj,这些都由决策者按具体情况而定。目标规划的数学模型四.达成函数(即目标规划中的目标函数)目标规划的目标函数(准则函数)是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是minZ=f(d＋、d－)。一般说来，有以下三种情况，但只能出现其中之一：(1)要求恰好达到规定的目标值，即正、负偏差变量要尽可能小，则minZ=f(d＋＋d－)。(2)要求不超过目标值，即允许达不到目标值，也就是正偏差变量尽可能小，则minZ=f(d＋)。(3)要求超过目标值，即超过量不限，但不低于目标值，也就是负偏差变量尽可能小，则minZ=f(d－)。对由绝对约束转化而来的目标函数，也照上述处理即可。34例：甲乙产品的最优生产计划。产品资源甲乙现有资源设备A2016设备B0210设备C3432单位利润35•根据市场需求/合同规定：希望尽量扩大甲产品减少乙产品产量。•又增加二个目标：maxZ1=3x1+5x2maxZ2=x1minZ3=x22x1≤162x2≤103x1+4x2≤32x1，x2≥035第二节目标规划的数学模型例如P1级目标实现利润至少30元；P2级目标是甲乙产品的产量假设：乙产品产量不少于4件比甲产品产量不少于6件更重要，取其权重为2minG=P1d1-+P2(2d2-+d3-)3x1+5x2+d1--d1+=30x2+d2--d2+=4x1+d3--d3+=6x1,x2,dk-,dk+≥0(k=1,2,3)目标规划的数学模型五.多目标规划的解(1)若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解；(2)若解只能满足部分目标，就称该解为多目标规划的次优解；(3)若找不到满足任何一个目标的解，就称该问题为无解。(4)前面的目标可以保证实现或部分实现，而后面的目标就不一定能保证实现或部分实现，有些可能就不能实现，就称该解为多目标规划的满意解(具有层次意义的解)单目标规划例5-2:某工厂生产A，B两种产品，有关数据如下。实现目标利润为140万元的最优生产方案AB可用量设备(台时)4260原材料(KG)2448利润(万元)86从决策者的角度看，他希望超过利润目标值，若达不到，也希望尽可能接近，即负偏差最小-0,,0,21ddxx484221xx602421xx--1406821ddxxst-mindZ级别相等的多目标规划例5-3：若上例中假设决策者根据市场预测，产品A的销售量有下降的趋势，故考虑实现下列两个目标：(1)实现利润目标122万元(2)产品A的产量不多于10分析:两个目标级别相等，即两个目标的重要程度一样，不存在谁优先的问题设d＋，d-分别为超过目标值的部分，以及未完成目标值的部分，于是两个目标可以等价表示为：10122681211121----ddxddxx级别相等的多目标规划x1=10，x2=7，d－1＝0，d+2＝0，利润为122，两个目标均已经实现-------0,,,,,4842602410122682211212121221112121ddddxxxxxxddxddxxstddMinZ具有优先级别的多目标规划对于多个目标，如果有一定的优先顺序，即第一位重要的目标，其优先因子为P1，第二位重要的目标，其优先因子为P2，并规定P1P2优先保