单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学演示课件,第 五 章,1,问题的提出与目标规划的数学模型,一、问题的提出,为了具体说明目标规划与线性规划在处理问题方法上的区别，先通过例子来介绍目标规划的有关概念及数学模型。,例 某机器厂生产,、,两种产品，这两种产品都需要在,A,、,B,、,C,三种不同设备上加工，三种设备在计划期内可提供的机时分别为,12h,、,16h,、,15h,。按工艺资料规定，生产每件产品,需占用三设备分别为,2h,、,4h,、,0h,生产每件产品,，需占用各设备分别为,2h,、,0h,、,5h.,又生产生产,、,两种产品各一件的利润分别为,2,元与,3,元，问企业如何安排两种产品生产数量使总利润最大,。,第五章 目标规划,解：设两种产品分别安排为 与,可求出最优解,企业的经营目标不仅仅是利润，且作多方面考虑：,（,1,）力求是利润不低于,15,元；,（,2,）考虑到市场需求，,，,两种产品的生产量,须保持,12,的比例。,（,3,）,A,为贵重设备，严格禁止超时使用。,（,4,）设备,C,可以适当加班，但要控制，设备,B,既,要求充分利用，又尽可能不加班，又在重要性上设,备,B,是设备,C,的,3,倍。,这样，在考虑产品生产决策时，不再是单纯追求利润最大，而是同时要考虑多个目标，这样的问题一般的线性规划方法已无法解决，需引入一种新的数学模型,目标规划。,线性规划模型的局限性,(1),全部约束条件过于刚性，不能违背，否则无解。,与实际脱节。,（,2,）,只能处理单目标的优化问题，因此线性规划模型认为地将一些次要目标转为约束。而实际问题中，目标和约束可以互相转化，处理时不一定严格区分,；,（,3,）,线性规划中各个约束条件都处于同等重要的地位，但实际问题中，各目标的重要性是有差别的；,（,4,）,线性规划寻求最优解，但很多实际问题中只需找出满意解就可以了,。,二、目标规划模型的建立,1.,偏差变量,用来表示实际值与目标值之间的差异。,d,+,超出目标的差值，称为,正偏差变量,。,d,-,未达到目标的差值，称为,负偏差变量,。,因实际决策值不可能既超过目标值又低于目标值，故最终结果中恒有,d,+,d,-,=0,(,即两者至少有一个为,0),。,目标规划中，一般有多个目标值，每个目标值都相应有一对偏差变量。,2.,绝对约束和目标约束,绝对约束,是指必须严格满足的等式约束或不等式约束；如线性规划问题的所有约束条件，不能满足这些条件的解称为非可行解，所以绝对约束是,硬约束,。,目标约束,是目标规划所特有的一种约束，它把要追求的目标值作为右端常数项，在追求此目标值时允许发生正偏差和负偏差。因此，目标约束是由决策变量，正、负偏差变量和要追求的目标值组成的,软约束,。,目标约束不会不满足，但可能偏差过大,。,绝对约束,：问题中的目标,3,，在原料供应受严格限制的基础上考虑，可写成绝对约束为,假设问题中甲、乙两产品的产量分别为,x,1,和,x,2,。,目标约束,：问题中的目标,1,可写成目标约束为,化为标准形式是：,线性目标约束的一般形式是：,其中：,3.,优先因子和权系数,目标规划中，当决策者要求实现多个目标时，这些目标之间是有主次区别的。,凡要求第一位达到的目标，赋于,优先因子,p,1,，,要求第二位达到的目标，赋于优先因子,p,2,并规定,p,k+,1,p,k,，,表示,p,k,比,p,k+,1,有绝对优先权。因此，不同的优先因子代表着不同的优先等级。,若要区别具有相同优先因子的多个目标，可分别赋予它们不同的,权系数,k,。,越重要的目标，其权系数的值越大。,在实现多个目标时，首先保证,p,1,级目标的实现，这时可不考虑其它级目标，而,p,2,级目标是在保证,p,1,级目标值不变的前提下考虑的，以此类推。,4.,目标函数,目标规划的目标函数是由各目标约束的正、负偏差变量及相应的优先因子、权系数构成的，其中不含决策变量。因为决策者的愿望总是尽可能缩小偏差，实现目标。故总是将目标函数极小化，其基本形式有三种。,对于第,i,个目标,:,(1),若要求,决策值超过目标值,，则相应的负偏差变量要尽可能地小，而对正偏差变量不加限制，目标函数的形式为：,(2),允许,达不到目标值,，就是相应的正偏差变量要尽可能地小，目标函数的形式为：,(3),恰好达到目标,，则相应的正、负偏差变量都要尽可能地小，目标函数的形式为：,加入优先因子和权系数后，建立目标函数，其一般形式为：,前述问题的规划模型可以写为：,2,目标规划的图解分析法,对于只有两个决策变量的线性目标规划的数学模型，可以用图解法来分析求解。传统的线性规划一般只是寻求一个点，在这个点上得到单目标的最优值，目标规划一般是寻求一个区域，这个区域提供了相互矛盾的目标集的折衷方案。,步骤,1,建立直角坐标系，令各偏差变量为,0,，作出所有的约束直线。满足所有绝对约束条件的区域，用阴影标出。,步骤,2,作图表示差变量增减对约束直线的影响,在所有目标约束直线旁标上,d,+,，,d,-,，,如图所示。这表明目标约束直线可以沿,d,+,，,d,-,，,所示的方向平移。,步骤,3,根据目标函数中的优先因子次序，逐步分析求解。,根据目标函数中的优先因子次序，首先考虑具有优先因子,p,1,的目标的实现。目标函数要求实现,min,d,1,+,，,从图中可见，可以满足,d,1,+,=0,，,这时，只能在三角形,OBC,的区域上取值；,考察具有优先因子,p,2,的目标，此时可在线段,ED,上取值；,考察优先因子,p,3,的目标，这就使取值范围缩小到线段,GD,上，该线段上所有点的坐标，都是问题的解。,多目标规划问题的另一类表示方法,买糖,问题,设,商店有甲、乙、丙三种糖果，单价分别为,4,元,/kg,，,2.80,元,/kg,和,2.40,元,/kg,。,今要筹办一次节日茶话会，要求用于买糖的钱数不超过,20,元，糖的总量不少于,6kg,，,甲、乙两种糖的总和不少于,3kg,，,问应如何确定最好的买糖方案。,解,：设购买甲,乙,丙三种糖果的斤数分别为,x,1,x,2,x,3,用于买糖所花的钱数为,y,1,，,所买糖的总斤数为,y,2,。,我们希望,y,1,取最小值，,y,2,取最大值。,约束条件可以写为：,这是含有两个目标的线性规划问题，这里可以将求,y,2,的最大值转化为求（,-,y,2,）,的最小值，这时目标函数可以写为：,其中：,3,用单纯形法求解目标规划,目标规划的数学模型与线性规划的数学模型基本相同，因此利用单纯形法求解步骤也基本相同，但是需要尤其注意它们之间的区别。,线性规划的单纯形法求解过程：,1.,建立初始单纯形表，计算出所有变量的检验数。,2.,在非基变量检验数中找到最大的正数,j,，,它所对应的变量,x,j,作为换入基的变量。,3.,对于所有,a,ij,0,计算,b,i,/,a,ij,，,其中最小的元素,所对应的基变量,x,i,作为换出基的变量。,4.,建立新单纯形表，重复上述步骤,2,、,3,，直到所有检验数都小于等于零。,由于目标规划的目标函数都是求极小化问题，而线性规划问题的标准型中目标函数都是求极大化问题，因此在用单纯形法求解时要注意一些重要的的差别。,用,单纯形法求解下述目标规划问题,：,第一步：,列出初始单纯形表，并计算检验数。,将表格中最后一行检验数按优先级改写为：,（这是与线性规划单纯形法的,第一个差别,）,对,两行检验数需分别进行处理。,第二步：,确定换入基的变量。,在负检验数中，选择最小的一个,j,所对应的变量,x,j,作为换入基的变量。在这个问题中第一优先级,P,1,所的检验数中,1,是最小的，因此,x,1,为换入基的变量。,这是与线性规划单纯形法的,第二个差别,，在线性规划中是将大于零的检验数中较大的一个对应的变量换入基。这是仅仅因为目标函数取值有极大和极小的差别，对于目标函数取极小的线性规划问题也可以同样进行处理。,第三步：,确定换出基的变量。,对于所有,a,ij,0,计算,b,i,/,a,ij,其中最小的元素,所对应的基变量,x,i,作为换出基的变量。（这与线性规划相同,）,在,这个问题中,min,b,i,/,a,ij,=10,，,因此,d,1,-,为换出变量。,换入、换出基的变量确定过程如下表：,第四步：,用换入变量替换换出变量，进行单纯形法迭代运算，直至优先级,P,1,所对应的检验数全为非负。,本例,中，第一优先级计算后得：,由于优先级,P,2,的,检验数仍然有负值，因此可以继续优化，重复上述步骤,24,。,确定换入、换出变量：,第一点说明：,目标函数按优先级顺序进行优化，当,P,1,行,所有检验数非负时，说明第一级已经优化，可以转入下一级，考察,P,2,行,检验数，依此类推。,第二点说明：,从,考察,P,2,行,检验数开始，注意应包括更高级别的优先因子在内。如上述问题的进一步单纯形表如下：,对应的检验数为,P,1,+(3/2),P,2,0,对应的检验数为,P,1,P,2,0,对应的检验数为,P,1,2,P,2,0,因此上述三种情况都不能选为换入基的变量，这其实与线性规划相同。,判别迭代计算停止的准则：,(1),检验数,P,1,P,2,P,k,行的,所有值均为非负；,(2),若,P,1,P,2,P,i,行的所有检验数为非负，而,P,i,+1,行存在负检验数，但在负检验数所在列的上面行中有正检验数（不一定是相邻行，只要在起上方即可）。,4,求解目标规划的层次算法,求解目标规划是从高优先级到低优先级逐层优化的，求解目标规划的层次算法就是根据这样的思想构造的。,层次算法步骤：,第一步：,对目标函数中的,P,1,层次进行优化，建立第一层次的线性规划模型,LP,1,并求解。,LP,1,的目标函数为,LP,1,的约束条件含原目标规划的所有约束。,第二步：,对,P,2,层次进行优化。,由于下一层次的优化应在前面各层次优化的基础上进行，若第一层次目标函数最优值为,z,1,*,，,则构建的,P,2,层次的线性规划模型,LP,2,，其目标函数为,约束条件除含有原目标规划的所有约束条件之外，由于这一步优化是在前一步优化的基础上进行的，所以前一步优化的结果应成为一个新的约束条件，即约束条件增加了一个式子：,小于等于使得上一步的最优值在计算后不会发生改变,第三步：,依此类推得到第,P,s,(,s,2),层次进行优化时建立的线性规划模型,LP,s,为：,当,进行到,s,=,K,时，对,P,k,层次建立的线性规划模型,LP,k,的最优解即为目标规划问题的满意解。,K,是某一步。,例,.,用层次算法求解下述目标规划。,解：,第一层次的优化模型,LP,1,为：,利用线性规划的单纯形法对其求解，得：,因为,z,1,*,=0,，,因此在第二层次的优化模型中加上约束条件,=0(,因为 最小就只能是,0,，因此不用写小于号,).,求解后所得最优值与最优解与,LP,1,相同，即,z,2,*,=0,。,由于,z,2,*,=0,，故对,第三层次进行优化的时候，在,LP,2,的基础上加上约束 ，得,LP,3,：,求解,LP,3,得：,到,此时，所有各层次的优化都已经完成，而最后一个层次的最优值,z,3,*,=29.0,，因此并没有取得最优解，这个值只是该目标规划问题的满意解，这个解与用图解法求出的解相同，就是图中,F,点。,工序,每周生产时间最好恰好为,150h,工序,生产时间可适当超过其能力。试建立这个问题的,数学模型。,