第七章-目标规划

第七章目标规划什么是多目标规划？对于许多规划问题，常常需要考虑多个目标，比如经济效益目标、生态效益目标、社会效益目标等等，这样的规划问题就称为多目标规划问题某公司的人力资源部经理，为了预测未来一定时期公司四类人力资源需求数量，他召集员工主管张某、薪酬主管李某、培训主管陈某，研究如何科学预测未来三年的人力资源需求。同时需要考虑完成利润最大化、人工成本最小化、人力资源结构最优化、产业结构优化、培训费用最小化等多个目标，而这些目标有着本质的差别。什么是多目标规划？任何多目标规划问题，都由两个基本部分组成：(1)两个以上的目标函数；(2)若干个约束条件。什么是多目标规划？对于多目标规划问题，可以将其数学模型一般地描写为如下形式)(max(min))(max(min))(max(min))(21XfXfXfXFZkmmgggGXXXX2121)()()()(什么是多目标规划？对于多目标规划问题，求解就意味着需要做出如下的复合选择：每一个目标函数取什么值，原问题可以得到最满意的解决？多目标规划问题的求解不能只追求一个目标的最优化（最大或最小），而不顾其他目标。求解多目标规划的方法大体上有以下几种：一种是化多为少的方法，即把多目标化为比较容易求解的单目标或双目标，如主要目标法、线性加权法、理想点法等另一种叫分层序列法，即把目标按其重要性给出一个序列，每次都在前一目标最优解集内求下一个目标最优解，直到求出共同的最优解。什么是目标规划？目标规划方法是解决多目标规划问题的重要技术之一这一方法是美国学者查恩斯（A.Charnes）和库伯（W.W.Cooper）于1961年在线性规划的基础上提出来的。后来，查斯基莱恩（U.Jaashelainen）和李（S.Lee）等人，进一步给出了求解目标规划问题的一般性方法——单纯形方法。什么是目标规划？基本思想：给定若干目标以及实现这些目标的优先顺序，在有限的资源条件下，使总的偏离理想目标值的偏差最小。第七章目标规划7.1目标规划模型7.2目标规划的几何意义与图解法7.3求解目标规划的单纯形方法7.1目标规划模型例1某纺织厂生产甲、乙两种布料，平均生产能力都是1千米/小时，工厂正常生产能力是80小时/周。又甲种布料每千米获利2500元，乙种布料每千米获利1500元。已知甲、乙两种布料每周的市场需要量最多分别是70千米和45千米。工厂现想要达到的目标及目标次序为7.1目标规划模型第1目标：避免开工不足，职工正常就业；第2目标：加班时间不超过10小时；第3目标：努力达到最大销售量，既甲料70千米，乙料45千米；第4目标：尽可能的减少加班时间。7.1目标规划模型目标规划模型的基本概念下面引入与建立目标规划数学模型有关的概念．（1）、正、负偏差变量d+，d-我们用正偏差变量d+表示决策值超过目标值的部分；负偏差变量d-表示决策值不足目标值的部分。因决策值不可能既超过目标值同时又末达到目标值，故恒有d+d-＝0．7.1目标规划模型目标规划模型的基本概念(2)优先因子与权系数．对于多目标问题，设有k个目标函数f1,f2,,fk,决策者在要求达到这些目标时，一般有主次之分。为此，我们引入优先因子Pi，i=1,2,,k.无妨设预期的目标函数优先顺序为f1,f2,,fk,我们把要求第一位达到的目标赋于优先因子P1，次位的目标赋于优先因子P2、…，并规定PiPi+1，i=1,2,,k-1.7.1目标规划模型目标规划模型的基本概念即在计算过程中,首先保证P1级目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的，以此类推。当需要区别具有相同优先因子的若干个目标的差别时，可分别赋于它们不同的权系数wj。优先因子及权系数的值，均由决策者按具体情况来确定．目标规划模型的基本概念（4）、目标规划的目标函效．目标规划的目标函数是通过各目标约束的正、负偏差变量和赋于相应的优先等级来构造的．7.1目标规划模型对例1，给定工厂的目标和目标次序（P152），按以上概念可建立目标规划模型对于第一目标，我们引入d1+和d1-表示不足和超过80小时的偏差量x1+x2+d1--d1+=80目标要求：7.1目标规划模型min1d对于第二目标，我们引入d2+和d2-表示不足和超过90小时的偏差量x1+x2+d2--d2+=90目标要求：min2d对于第三目标，我们引入d3-，d3+和d4+，d4-表示达不到目标而造成的负偏差量x1+d3--d3+=70目标要求：x2+d4--d4+=45目标要求：7.1目标规划模型对于第四目标，偏差量d1+即是加班时间目标要求：min4dmin3dmin1d对于属于同一个优先级的多个目标，可按其重要程度赋予权系数。对于同属P3优先级的d3-和d4+可赋予权系数分别为5和3，既是7.1目标规划模型min3543dd可得目标规划（GP）的目标函数为])35(min[min144332211dPddPdPdPS该问题的(GP)模型为7.1目标规划模型0)4,3,2,1(,,,45709080])35(min[min221423111211121144332211iddxxdxdxddxxddxxdPddPdPdPSi7.1目标规划模型目标规划模型的基本概念绝对约束是指必须严格满足的等式约束和不等式约束；如在线性规划问题中考虑的约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。目标约束是目标规划特有的，我们可以把约束右端项看作要努力追求的目标值，但允许发生正负偏差，用在约束中加入正、负偏差变量来表示，于是称它们是软约束。§7.1目标规划模型决策者的要求是尽可能从某个方向缩小偏离目标的数值。于是，目标规划的目标函数应该是求极小：minf＝f（d+，d-)．其基本形式有三种：①要求恰好达到目标值，即使相应目标约束的正、负偏差变量都要尽可能地小。这时取min（d++d-)；§7.1目标规划模型②要求不超过目标值，即使相应目标约束的正偏差变量要尽可能地小。这时取min（d+)；③要求不低于目标值，即使相应目标约束的负偏差变量要尽可能地小。这时取min（d-)；某一个企业利用某种原材料和现有设备可生产甲、乙两种产品，其中，甲、乙两种产品的单价分别为8元和10元；生产单位甲、乙两种产品需要消耗的原材料分别为2个单位和1个单位，需要占用的设备分别为1台时和2台时；原材料拥有量为11个单位；可利用的设备总台时为10台时。如果决策者在原材料供应受严格控制的基础上考虑：首先是甲种产品的产量不超过乙种产品的产量；其次是充分利用设备的有限台时，不加班；再次是产值不小于56万元。试建立该问题的目标规划模型。解：根据题意，这一决策问题的目标规划模型是3322211)(mindpddpdpZ11221xx01121ddxx1022221ddxx561083321ddxx)3,2,1(0,,,21iddxxii练习：P159(1)§7.2目标规划的几何意义及图解法用图解法来求解例1我们先在平面直角坐标系的第一象限内，作出与各约束条件对应的直线，然后在这些直线旁分别标上G-i，i=1，2，3，4。图中x，y分别表示x1和x2；各直线移动使di+,di-变大的方向用+、-表示.§7.2目标规划的图解法458090X2X1908070+-G-1+-G-2+-G-4+-G-3图7-1BCDFE当目标函数处于冲突状态时，不会存在使所有目标函数同时达到最大或最小值的最优解，于是我们只能寻求次最优解（满意解）。§7.2目标规划的图解法§7.3求解目标规划的单纯形方法线性目标规划的数学模型,特别是约束的结构与线性规划模型没有本质的区别，只是它的目标不止是一个,虽然其利用优先因子和权系数把目标写成一个函数的形式,但在计算中无法按单目标处理,所以可用单纯形法进行适当改进后求解。§7.3求解目标规划的单纯形方法在构造算法时，我们要考虑目标规划的数学模型一些特点，作以下规定：目标规划问题的目标函数都是求最小化目标规划问题的单纯形法的计算步骤(1)建立初始单纯形表．在表中将检验数行按优先因子个数分别列成K行。§7.3求解目标规划的单纯形方法例1：§7.3求解目标规划的单纯形方法0)4,3,2,1(,,,45709080])35(min[min221423111211121144332211iddxxdxdxddxxddxxdPddPdPdPSi通过计算可得§7.3求解目标规划的单纯形方法3148580PbCbBCBB),,0,0,0,0,3,5(24131311PPPPPPPCABCB按优先等级可得四行的检验矩阵　０　　　　　　　　０　　　　　　　　　　0100000000000354851000000000100001180X1X2d1-d2-d3-d4-d1+d2+P1-80-1-1000010P2000000001P3-485-5-3000001P4000000010d1+80111000-10d2-901101000-1d3-7010001000d4-4501000100初始单纯形表检验数的最优准则与线性规划是相同的§7.3求解目标规划的单纯形方法1、如各优先级Pi，i=1,2,,k的全体检验数非负，则相应的单纯形表的解是最优解。2、如前Pi，i=1,2,,r的全体检验数非负，但是第Pr+1行的检验数中有负数，而且该行所有负检验数所在列均存在正检验数，则问题已经获得次最优解，运算结束。3、Pr行存在负检验数，且该负检验数所在列上面行中的检验数均为0，但该列以下的运算系数全部为正，则该问题无解，停止运算。§7.3求解目标规划的单纯形方法4、若无以上的情况，则当前问题非优，进行迭代。三、选取主元，换基迭代1.按优先等级选取主列，即从第一级优先行开始。在单纯形表的上半部中依行取第一个为负的检验数，将此检验数所在列定位主列。2.在主列上，用与(LP)相同的方法在单纯形表的下半部确定主元，并用方框作上记号，进行换基迭代。3.重复第二步，直到找出最优解。