第二十一章目标规划 §1引言 线性规划的局限性 只能解决一组线性约束条件下,某一目标只能是一个目标的最大或最小值的问题。 2.实际决策中,衡量方案优劣考虑多个目标 这些目标中,有主要的,也有次要的:有最大值的,也有最小值的;有定量的, 也有定性的;有相互补充的,也有相互对立的,LP则无能为力。 3.目标规划( Goal programming) 美国经济学家查恩斯( A Charnes)和库柏(w. w. Cooper)在1961年出版的《管 理模型及线性规划的工业应用》一书中,首先提出的。 4.求解思路 (1)加权系数法 为每一目标赋一个权系数,把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数,以反映不同目标之间的重要程度。 (2)优先等级法 将各目标按其重要程度不同的优先等级,转化为单目标模型 (3)有效解法 寻求能够照顾到各个目标,并使决策者感到满意的解。由决策者来确定选取哪一个 解,即得到一个满意解。但有效解的数目太多而难以将其一一求出。 §2目标规划的数学模型 为了具体说明目标规划与线性规划在处理问题的方法上的区别,先通过例子来介绍 目标规划的有关概念及数学模型 例1某工厂生产I,Ⅱ两种产品,已知有关数据见下表 I 拥有量 原材料k 2 设备hr 利润元/件 试求获利最大的生产方案。 解这是一个单目标的规划问题,用线性规划模型表述为 max =8x,+10x x1+2x2≤10 ≥0 最优决策方案为:x1=4,x2=3,=62元。 但实际上工厂在作决策方案时,要考虑市场等一系列其它条件。如 (i)根据市场信息,产品I的销售量有下降的趋势,故考虑产品I的产量不大于 品Ⅲ。 (ⅱi)超过计划供应的原材料,需要高价采购,这就使成本增加。 (i)应尽可能充分利用设备,但不希望加班
-253- 第二十一章 目标规划 §1 引言 1．线性规划的局限性 只能解决一组线性约束条件下，某一目标只能是一个目标的最大或最小值的问题。 2．实际决策中，衡量方案优劣考虑多个目标 这些目标中，有主要的，也有次要的；有最大值的，也有最小值的；有定量的， 也有定性的；有相互补充的，也有相互对立的，LP 则无能为力。 3．目标规划（Goal Programming） 美国经济学家查恩斯（A. Charnes）和库柏（W. W. Cooper）在 1961 年出版的《管 理模型及线性规划的工业应用》一书中，首先提出的。 4．求解思路 （1）加权系数法 为每一目标赋一个权系数，把多目标模型转化成单一目标的模型。但困难是要确 定合理的权系数，以反映不同目标之间的重要程度。 （2）优先等级法 将各目标按其重要程度不同的优先等级，转化为单目标模型。 （3）有效解法 寻求能够照顾到各个目标，并使决策者感到满意的解。由决策者来确定选取哪一个 解，即得到一个满意解。但有效解的数目太多而难以将其一一求出。 §2 目标规划的数学模型 为了具体说明目标规划与线性规划在处理问题的方法上的区别，先通过例子来介绍 目标规划的有关概念及数学模型。 例1 某工厂生产 I，II 两种产品，已知有关数据见下表 I II 拥有量 原材料 kg 2 1 11 设 备 hr 1 2 10 利润 元/件 8 10 试求获利最大的生产方案。 解 这是一个单目标的规划问题，用线性规划模型表述为： 1 2 max z = 8x +10x ⎪ ⎩ ⎪ ⎨ ⎧ ≥ + ≤ + ≤ , 0 2 10 2 11 1 2 1 2 1 2 x x x x x x 最优决策方案为： 4, 3, 62 * * 2 * x1 = x = z = 元。 但实际上工厂在作决策方案时，要考虑市场等一系列其它条件。如 （i）根据市场信息，产品 I 的销售量有下降的趋势，故考虑产品 I 的产量不大于 产品 II。 （ii）超过计划供应的原材料，需要高价采购，这就使成本增加。 （iii）应尽可能充分利用设备，但不希望加班
(iv)应尽可能达到并超过计划利润指标56元 这样在考虑产品决策时,便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。 1.正、负偏差变量 设d为决策变量的函数,正偏差变量d=max{d-d00}表示决策值超过目标值 的部分,负偏差变量d=-min{d-d00}表示决策值未达到目标值的部分,这里d0表 示d的目标值。因决策值不可能既超过目标值同时又未达到目标值,即恒有 2.绝对(刚性)约束和目标约束 绝对约束是指必须严格满足的等式约束和不等式约束;如线性规划问题的所有约束 条件,不能满足这些约束条件的解称为非可行解,所以它们是硬约束。目标约束是目标 规划特有的,可把约束右端项看作要追求的目标值。在达到此目标值时允许发生正或负 偏差,因此在这些约束中加入正、负偏差变量,它们是软约束。线性规划问题的目标函 数,在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需要将 绝对约束变换为目标约束。如:例1的目标函数二=8x1+10x2可变换为目标约束 8x1+10x2+d1-d=56。绝对约東2x1+x2≤11可变换为目标约束 2x1+x2+d2-d2=11。 3.优先因子(优先等级)与权系数 个规划问题常常有若干目标。但决策者在要求达到这些目标时,是有主次或轻重 缓急的不同。凡要求第一位达到的目标赋于优先因子P1,次位的目标赋于优先因子 P2…,并规定P>>P1k=1,2,…,q。表示P比P+1有更大的优先权。以此类推, 若要区别具有相同优先因子的两个目标的差别,这时可分别赋于它们不同的权系数 这些都由决策者按具体情况而定 4.目标规划的目标函数 目标规划的目标函数(准则函数)是按各目标约束的正、负偏差变量和赋于相应的 优先因子而构造的。当每一目标值确定后,决策者的要求是尽可能缩小偏离目标值。因 此目标规划的目标函数只能是minz=f(d*,d-)。其基本形式有三种 (1)要求恰好达到目标值,即正、负偏差变量都要尽可能地小,这时 =f(d+d (2)要求不超过目标值,即允许达不到目标值,就是正偏差变量要尽可能地小, 这时 nin ==f(d) (3)要求超过目标值,即超过量不限,但必须是负偏差变量要尽可能地小,这时 min ==f(d) 对每一个具体目标规划问题,可根据决策者的要求和赋于各目标的优先因子来构造目标 函数,以下用例子说明 例2例1的决策者在原材料供应受严格限制的基础上考虑:首先是产品Ⅱ的产 量不低于产品I的产量;其次是充分利用设备有效台时,不加班:再次是利润额不小于 56元。求决策方案。 解按决策者所要求的,分别赋于这三个目标PP2B优先因子。这问题的数学 254
-254- （iv）应尽可能达到并超过计划利润指标 56 元。 这样在考虑产品决策时，便为多目标决策问题。目标规划方法是解决这类决策问题 的方法之一。下面引入与建立目标规划数学模型有关的概念。 1. 正、负偏差变量 设d 为决策变量的函数，正偏差变量 max{ ,0} d = d − d0 + 表示决策值超过目标值 的部分，负偏差变量 min{ ,0} d = − d − d0 − 表示决策值未达到目标值的部分，这里d0 表 示 d 的目标值。因决策值不可能既超过目标值同时又未达到目标值，即恒有 × = 0 + − d d 。 2. 绝对（刚性）约束和目标约束 绝对约束是指必须严格满足的等式约束和不等式约束；如线性规划问题的所有约束 条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。目标约束是目标 规划特有的，可把约束右端项看作要追求的目标值。在达到此目标值时允许发生正或负 偏差，因此在这些约束中加入正、负偏差变量，它们是软约束。线性规划问题的目标函 数，在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需要将 绝对约束变换为目标约束。如：例 1 的目标函数 1 2 z = 8x +10x 可变换为目标约束 8 1 +10 2 + 1 − 1 = 56 − + x x d d 。绝对约束 2 11 x1 + x2 ≤ 可变换为目标约束 2 1 + 2 + 2 − 2 = 11 − + x x d d 。 3. 优先因子（优先等级）与权系数 一个规划问题常常有若干目标。但决策者在要求达到这些目标时，是有主次或轻重 缓急的不同。凡要求第一位达到的目标赋于优先因子 P1 ，次位的目标赋于优先因子 P2 ,L，并规定 Pk >> Pk+1 , k = 1,2,L,q 。表示 Pk 比 Pk +1有更大的优先权。以此类推， 若要区别具有相同优先因子的两个目标的差别，这时可分别赋于它们不同的权系数 wj ， 这些都由决策者按具体情况而定。 4. 目标规划的目标函数 目标规划的目标函数（准则函数）是按各目标约束的正、负偏差变量和赋于相应的 优先因子而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因 此目标规划的目标函数只能是 min ( , ) + − z = f d d 。其基本形式有三种： （1）要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时 min ( ) + − z = f d + d （2）要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小， 这时 min ( ) + z = f d （3）要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时 min ( ) − z = f d 对每一个具体目标规划问题，可根据决策者的要求和赋于各目标的优先因子来构造目标 函数，以下用例子说明。 例 2 例 1 的决策者在原材料供应受严格限制的基础上考虑：首先是产品 II 的产 量不低于产品 I 的产量；其次是充分利用设备有效台时，不加班；再次是利润额不小于 56 元。求决策方案。 解 按决策者所要求的，分别赋于这三个目标 1 2 3 P ,P ,P 优先因子。这问题的数学
模型是 min Pdf +p2(d2 +d2)+Pd x1+x2 x1+2x2+d2-d2=10 8x1+10x2+d3-dt=56 x1,x2,d1,d≥0,1=1,23 5.目标规划的一般数学模型 设x;(j=1,2…,n)是目标规划的决策变量,共有m个约束是刚性约束, 可能是等式约束,也可能是不等式约束。设有1个柔性目标约束,其目标规划约束的偏 差为d,d(i=12…,)。设有q个优先级别,分别为P,P2…,P。在同一个优先 级P中,有不同的权重,分别记为w,v(=12,…1)。因此目标规划模型的一般 数学表达式为 mn:=l|∑n;+vad ∑ax≤(=2),1=1…,m x≥0,j=12,…,n d,d≥0,i=1,2,…,l 建立目标规划的数学模型时,需要确定目标值、优先等级、权系数等,它都具有一 定的主观性和模糊性,可以用专家评定法给以量化。 §3求解目标规划的序贯式算法 序贯式算法是求解目标规划的一种早期算法,其核心是根据优先级的先后次序, 将目标规划问题分解成一系列的单目标规划问题,然后再依次求解。 求解目标规划的序贯算法 对于k=1,2,…,q,求解单目标规划 min=∑(d+wtd) (1) ax≤(=,2 (2) ∑cnx1+d7-d"=g,=12,,l (3)
-255- 模型是 + − + − 1 1 + 2 2 + 2 + 3 3 min Pd P (d d ) P d ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ = + + − = + + − = − + − = + ≤ − + − + − + − + , , , 0, 1,2,3. 8 10 56 2 10 0 2 11 1 2 1 2 3 3 1 2 2 2 1 2 1 1 1 2 x x d d i x x d d x x d d x x d d x x i i 5．目标规划的一般数学模型 设 j x （ j = 1,2,L,n ）是目标规划的决策变量，共有 m 个约束是刚性约束， 可能是等式约束，也可能是不等式约束。设有l 个柔性目标约束，其目标规划约束的偏 差为 + − di di , （i = 1,2,L,l ）。设有 q 个优先级别，分别为 P P Pq , , , 1 2 L 。在同一个优先 级 Pk 中，有不同的权重，分别记为 w ,w ( j 1,2, ,l) kj + kj − = L 。因此目标规划模型的一般 数学表达式为 ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎝ ⎛ = ∑ ∑ + = − − + + = l j kj j kj j q k z Pk w d w d 1 1 min ⎪ ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ = ≥ = + − = = ≤ = ≥ = − + = − + = ∑ ∑ d d i l x j n c x d d g i l a x b i m i i j n j ij j i i i n j ij j i , 0, 1,2, , 0, 1,2, , , 1,2, , ( , ) , 1, , 1 1 L L L L 建立目标规划的数学模型时，需要确定目标值、优先等级、权系数等，它都具有一 定的主观性和模糊性，可以用专家评定法给以量化。 §3 求解目标规划的序贯式算法 序贯式算法是求解目标规划的一种早期算法，其核心是根据优先级的先后次序， 将目标规划问题分解成一系列的单目标规划问题，然后再依次求解。 求解目标规划的序贯算法 对于 k = 1,2,L, q ，求解单目标规划 ∑= − − + + = + l j kj j kj j z w d w d 1 min ( ) （1） s.t. ∑= ≤ = ≥ = n j aij x j bi i m 1 ( , ) , 1,L, （2） ∑= − + + − = = n j ij j i i i c x d d g i l 1 , 1,2,L, （3）
∑(vnd+v2d)≤;,s=12,…k-1 (4) d,d≥0,t=1,2…,l (6) 其最优目标值为=,当k=1时,约束(4)为空约束。当k=q时,二所对应的解x为 目标规划的最优解。 注此时最优解的概念与线性规划最优解的概念已有所不同,但为方便起见,仍 称为最优解。 例3某企业生产甲、乙两种产品,需要用到A,B,C三种设备,关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产,才能达到下列目标 设备的生产能力(h) A(h件) B(h件) C(h件) 赢利(元/件) 300 (1)力求使利润指标不低于1500元; (2)考虑到市场需求,甲、乙两种产品的产量比应尽量保持12 (3)设备A为贵重设备,严格禁止超时使用 (4)设备C可以适当加班,但要控制:设备B既要求充分利用,又尽可能不加班 在重要性上,设备B是设备C的3倍。 建立相应的目标规划模型并求解。 解设备A是刚性约束,其余是柔性约束。首先,最重要的指标是企业的利润 因此,将它的优先级列为第一级;其次,甲、乙两种产品的产量保持12的比例,列为 第二级:再次,设备C,B的工作时间要有所控制,列为第三级。在第三级中,设备B的 重要性是设备C的三倍,因此,它们的权重不一样,设备B前的系数是设备C前系数 的3倍。由此得到相应的目标规划模型 min ==Pd, +P(d2 +d2)+P(3d3+3d3+d4) (7) st.2x1+2x2≤12 (8) 200x1+300x2+d1-d=1500 (9) 2x1-x2+d2-d2=0 (10) 5x2+d4-d4=15 (12) x1,x2,d,d≥0,i=1,234 (13) 序贯算法中每个单目标问题都是一个线性规划问题,可以使用 LINGO软件进行求 解。 求第一级目标。 LINGO程序如下 model sets variable/1.2/: x 256-
-256- * 1 ( ) s l j sj j sj j ∑ w d + w d ≤ z = − − + + ，s =1,2,L, k −1， （4） xj ≥ 0, j =1,2,L,n （5） d d i l i i , ≥ 0, =1,2,L, − + （6） 其最优目标值为 * k z ，当 k = 1时，约束（4）为空约束。当 k = q 时， * q z 所对应的解 * x 为 目标规划的最优解。 注 此时最优解的概念与线性规划最优解的概念已有所不同，但为方便起见，仍 称为最优解。 例 3 某企业生产甲、乙两种产品，需要用到 A, B,C 三种设备，关于产品的赢利 与使用设备的工时及限制如下表所示。问该企业应如何安排生产，才能达到下列目标： 甲 乙 设备的生产能力（h） A (h/件) 2 2 12 B (h/件) 4 0 16 C (h/件) 0 5 15 赢利（元/件） 200 300 （1）力求使利润指标不低于 1500 元； （2）考虑到市场需求，甲、乙两种产品的产量比应尽量保持 1:2； （3）设备 A 为贵重设备，严格禁止超时使用； （4）设备C 可以适当加班，但要控制；设备 B 既要求充分利用，又尽可能不加班。 在重要性上，设备 B 是设备C 的 3 倍。 建立相应的目标规划模型并求解。 解 设备 A 是刚性约束，其余是柔性约束。首先，最重要的指标是企业的利润， 因此，将它的优先级列为第一级；其次，甲、乙两种产品的产量保持 1:2 的比例，列为 第二级；再次，设备C, B 的工作时间要有所控制，列为第三级。在第三级中，设备 B 的 重要性是设备C 的三倍，因此，它们的权重不一样，设备 B 前的系数是设备C 前系数 的 3 倍。由此得到相应的目标规划模型。 min ( ) (3 3 ) 1 1 2 2 2 3 3 3 4 − + − + − + z = Pd + P d + d + P d + d + d （7） s.t. 2 2 12 x1 + x2 ≤ （8） 200 1 + 300 2 + 1 − 1 = 1500 − + x x d d （9） 2 1 − 2 + 2 − 2 = 0 − + x x d d （10） 4 1 + 3 − 3 =16 − + x d d （11） 5 2 + 4 − 4 =15 − + x d d （12） 1, 2 , , ≥ 0 − + di di x x ，i =1,2,3,4 （13） 序贯算法中每个单目标问题都是一个线性规划问题，可以使用 LINGO 软件进行求 解。 求第一级目标。LINGO 程序如下： model: sets: variable/1..2/:x;
S Con Num/1.4/: g, dplus, minus s con(s Con Num, Variable): c noses g=150001615 c=2003002-14005; enddat min=minus(1) 2*x(1)+2*x(2)<12; @for(s Con Num(i): Gsum(Variable(3):c(i,3)*x(3))+minus (i)-dplus(i )=g(i)); 求得 dominus(1)=0,即目标函数的最优值为0,第一级偏差为0 求第二级目标, LINGO程序如下 model variable/1.2/: xi S Con Num/1.4: g, dplus, mint s con(s Con Num, Variable):c endsets data g=150001615; C=2003002-14005 min=dplus(2)+minus(2)i 二级目标函数 2*x(1)+2*x(2)<12 @for(s Con Num(i): @sum(Variable(]):c(1,3)*x(]))+minus(i)-dplus(i g(i)) minus(1)=0;!一级目标约束 @for(variable: @gin(x)) 求得目标函数的最优值为0,即第二级的偏差仍为0。 求第三级目标, LINGO程序如下: variable/1. 2/: x S Con Num/1.4/: g, dplus, dminu s con(s Con Num, Variable): c c=2003002-14005 enddata min=3*dp1us(3)+3* minus(3)+dp1us(4);!三级目标函数; (1)+2*x(2)<1 @for(s Con Num(i): sum(Variable(3): c(i,3)*x(3))+minus(i)-dplus(i )=g(i)) minus(1)=0;!一级目标约束 dp1us(2)+ minus(2)=0;!二级目标约束 end 目标函数的最优值为29,即第三级偏差为29
-257- S_Con_Num/1..4/:g,dplus,dminus; S_con(S_Con_Num,Variable):c; endsets data: g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; enddata min=dminus(1); 2*x(1)+2*x(2)<12; @for(S_Con_Num(i):@sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); end 求得 dminus(1)=0，即目标函数的最优值为 0，第一级偏差为 0。 求第二级目标，LINGO 程序如下： model: sets: variable/1..2/:x; S_Con_Num/1..4/:g,dplus,dminus; S_con(S_Con_Num,Variable):c; endsets data: g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; enddata min=dplus(2)+dminus(2); !二级目标函数; 2*x(1)+2*x(2)<12; @for(S_Con_Num(i):@sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); dminus(1)=0;!一级目标约束; @for(variable:@gin(x)); end 求得目标函数的最优值为 0，即第二级的偏差仍为 0。 求第三级目标，LINGO 程序如下： model: sets: variable/1..2/:x; S_Con_Num/1..4/:g,dplus,dminus; S_con(S_Con_Num,Variable):c; endsets data: g=1500 0 16 15; c=200 300 2 -1 4 0 0 5; enddata min=3*dplus(3)+3*dminus(3)+dplus(4); !三级目标函数; 2*x(1)+2*x(2)<12; @for(S_Con_Num(i):@sum(Variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); dminus(1)=0;!一级目标约束; dplus(2)+dminus(2)=0;!二级目标约束; end 目标函数的最优值为29，即第三级偏差为29
分析计算结果,x1=2,x2=4,d1=100,因此,目标规划的最优解为x=(2,4) 最优利润为1600。 上述过程虽然给出了目标规划问题的最优解,但需要连续编几个程序,这样在使 用时不方便,下面用 LINGO软件,编写一个通用的程序,在程序中用到数据段未知数 据的编程方法。 例4(续例3)按照序贯式算法,编写求解例3的通用 LINGO程序。 variable/1.2/: x: h con num/1.1/: b s con num/1.4/: g, plus, minus; h con(h con num, variable):ai ob](level, s con num)/1 1,2 2,3 3,3 4/: plus, wminus i endsets data ctr=?i goa1=??0; b=12 g=150001615 a=22 c=2003002-14005 plus=0 1 3 1 wminus=1 13 0 enddata min=Gsum (level:p*z)i p(ctr)=li @for (level(i)li#ne#ctr: p(1)=0) @for (level(1):z()=@sum(obj(i,3): plus(i, j)*dplus(3)+minus (i, j) minus(]))) @for(h con num(i): Gsum(variable(3):a(i,j)*x(1))<b(i))i @for(s con num(i): sum(variable(3):c(i,j)*x(]))+minus (i)-dplus )=g(1)); @for (level (i)Ii #lt# @size (level): @bnd (0, z(1), goal(1))) 当程序运行时,会出现一个对话框。 在做第一级目标计算时,ctr输入1,goal(1)和gol(2)输入两个较大的值,表明这 两项约束不起作用。求得第一级的最优偏差为0,进行第二轮计算。 在第二级目标的运算中,c输入2。由于第一级的偏差为0,因此goal(1)的输入值 为0,goa(2)输入一个较大的值。求得第二级的最优偏差仍为0,进行第三级计算。 在第三级的计算中,ct输入3。由于第一级、第二级的偏差均是O,因此,goal(1) 和goa(2)的输入值也均是0。最终结果是:x1=2,x2=4,最优利润是1600元,第 级的最优偏差为29。 §4多标规划的 Matlab解法 多目标规划可以归结为
-258- 分析计算结果， 2 x1 = ， 4 x2 = ， 1 = 100 + d ，因此，目标规划的最优解为 (2,4) * x = ， 最优利润为1600。 上述过程虽然给出了目标规划问题的最优解，但需要连续编几个程序，这样在使 用时不方便，下面用 LINGO 软件，编写一个通用的程序，在程序中用到数据段未知数 据的编程方法。 例 4（续例 3） 按照序贯式算法，编写求解例 3 的通用 LINGO 程序。 model: sets: level/1..3/:p,z,goal; variable/1..2/:x; h_con_num/1..1/:b; s_con_num/1..4/:g,dplus,dminus; h_con(h_con_num,variable):a; s_con(s_con_num,variable):c; obj(level,s_con_num)/1 1,2 2,3 3,3 4/:wplus,wminus; endsets data: ctr=?; goal=? ? 0; b=12; g=1500 0 16 15; a=2 2; c=200 300 2 -1 4 0 0 5; wplus=0 1 3 1; wminus=1 1 3 0; enddata min=@sum(level:p*z); p(ctr)=1; @for(level(i)|i#ne#ctr:p(i)=0); @for(level(i):z(i)=@sum(obj(i,j):wplus(i,j)*dplus(j)+wminus(i,j)* dminus(j))); @for(h_con_num(i):@sum(variable(j):a(i,j)*x(j))<b(i)); @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i )=g(i)); @for(level(i)|i #lt# @size(level):@bnd(0,z(i),goal(i))); end 当程序运行时，会出现一个对话框。 在做第一级目标计算时，ctr 输入 1，goal(1)和 goal(2)输入两个较大的值，表明这 两项约束不起作用。求得第一级的最优偏差为 0，进行第二轮计算。 在第二级目标的运算中，ctr 输入 2。由于第一级的偏差为 0，因此 goal(1)的输入值 为 0，goal(2)输入一个较大的值。求得第二级的最优偏差仍为 0，进行第三级计算。 在第三级的计算中，ctr 输入 3。由于第一级、第二级的偏差均是 0，因此，goal(1) 和 goal(2)的输入值也均是 0。最终结果是： 2 x1 = ， 4 x2 = ，最优利润是 1600 元，第 三级的最优偏差为 29。 §4 多标规划的 Matlab 解法 多目标规划可以归结为
min y 使得 F(x)- weight:y≤goal A·x≤b,Ae q c(x)≤0,ceq(x)=0 1b<x≤bb 其中x, weight,goal,b,beq,lb和mb是向量,A和Aeq是矩阵;c(x),ceq(x)和F(x) 是向量函数,他们可以是非线性函数。F(x)是所考虑的目标函数,goal是欲达到的 目标,多目标规划的 Matlab函数 fgoalattain的用法为 Lx, fval]=fgoalattain('fun, xo, goal, weight) Lx, fval]=fgoalattain('fun, xo, goal, weight, A, b) Lx, fval]=fgoalattain('fun, Xo, goal, weight, A, b, Aeq, beq Lx, fval]=fgoalattain('fun, Xo, goal, weight, A, b, Aeq, beq, I b, ub, nonlcon) 其中fun是用M文件定义的目标向量函数,x是初值, weight是权重。Ab定义不等 式约束A*x≤b, Aeq, beq定义等式约束Acq*x=Beq, nonion是用M文件定义的非线性 约束c(x)≤0,ceq(x)=0。返回值fva是目标向量函数的值。 要完整掌握其用法,请用 help fgoalattain或 type fgoalattain查询相关的帮助。 例5求解多目标线性规划问题 z1=100x1+90x2+80x3+70 inZ,=3x,+2 x3+x4 3x1+ 3x,+2x4≤48 x≥0 解(i)编写M函数Fun function F=Fun(x) F(1)=-100+x(1)-90*x(2)-80*x(2)-70*x(4 (2)=3*x(2)+2+x(4) i)编写M文件 3020 0302] b=[-30-3012048]!; c1=[-100-90-80-70] x1,g1]=1 inprog(c1,a,b,[],[], zeros(4,1))暑求第一个目标函数的目标值 x2,q2]=1 Improg(c2,a,b,[],[], zeros(4,1))求第二个目标函数的目标值 g3=[g1;g2]号目标goa1的值 [x, fval]=fgoalattain(' Fun, rand(4, 1),g3, abs(g3),a,b,[l,[], zeros (4
-259- γ γ , min x 使得 F(x) − weight ⋅ γ ≤ goal A⋅ x ≤ b, Aeq ⋅ x = beq c(x) ≤ 0, ceq(x) = 0 lb ≤ x ≤ ub 其中 x,weight, goal,b,beq,lb和ub 是向量，A 和 Aeq 是矩阵；c(x), ceq(x) 和 F(x) 是向量函数，他们可以是非线性函数。 F(x) 是所考虑的目标函数， goal 是欲达到的 目标，多目标规划的 Matlab 函数 fgoalattain 的用法为 ［x,fval］= fgoalattain('fun',x0,goal,weight) ［x,fval］= fgoalattain('fun',x0,goal,weight,A,b) ［x,fval］= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq) ［x,fval］= fgoalattain('fun',x0,goal,weight,A,b,Aeq,beq,lb,ub,nonlcon) 其中 fun 是用 M 文件定义的目标向量函数，x0是初值，weight 是权重。A,b 定义不等 式约束 A*x ≤ b，Aeq,beq 定义等式约束 Aeq*x=Beq，nonlcon 是用 M 文件定义的非线性 约束 c(x)≤0，ceq(x)=0。返回值 fval 是目标向量函数的值。 要完整掌握其用法，请用 help fgoalattain 或 type fgoalattain 查询相关的帮助。 例 5 求解多目标线性规划问题 2 2 4 1 1 2 3 4 min 3 2 max 100 90 80 70 Z x x Z x x x x = + = + + + ⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ = + ≤ + ≤ + ≥ + ≥ 0, 1, ,4 3 2 48 3 2 120 30 30 2 4 1 3 3 4 1 2 x i L x x x x x x x x i 解 （i）编写 M 函数 Fun.m: function F=Fun(x); F(1)=-100*x(1)-90*x(2)-80*x(2)-70*x(4); F(2)=3*x(2)+2*x(4); （ii）编写 M 文件 a=[-1 -1 0 0 0 0 -1 -1 3 0 2 0 0 3 0 2]; b=[-30 -30 120 48]'; c1=[-100 -90 -80 -70]; c2=[0 3 0 2]; [x1,g1]=linprog(c1,a,b,[],[],zeros(4,1)) %求第一个目标函数的目标值 [x2,g2]=linprog(c2,a,b,[],[],zeros(4,1)) %求第二个目标函数的目标值 g3=[g1;g2] %目标goal的值 [x,fval]=fgoalattain('Fun',rand(4,1),g3,abs(g3),a,b,[],[],zeros(4 ,1))
号这里权重 weight=目标goa1的绝对值 就可求得问题的解 §5目标规划模型的实例 前面介绍了目标规划的求解方法,这里再介绍几个目标规划模型的模型,帮助我 们进一步了解目标规划模型的建立和求解过程。 例6某计算机公司生产三种型号的笔记本电脑A,B,C。这三种笔记本电脑需要 在复杂的装配线上生产,生产1台A,B,C型号的笔记本电脑分别需要5,8,12(h)。公 司装配线正常的生产时间是每月170h公司营业部门估计A,B,C三种笔记本电脑的利 润分别是每台1000,1440,2520(元),而公司预测这个月生产的笔记本电脑能够全部 售出。公司经理考虑以下目标: 第一目标:充分利用正常的生产能力,避免开工不足 第二目标:优先满足老客户的需求,A,B,C三种型号的电脑50,50,80(台), 同时根据三种电脑的纯利润分配不同的权因子 第三目标:限制装配线加班时间,最好不要超过200h 第四目标:满足各种型号电脑的销售目标,A,B,C型号分别为100,120,100(台), 再根据三种电脑的纯利润分配不同的权因子 第五目标:装配线的加班时间尽可能少。 请列出相应的目标规划模型,并用 LINGO软件求解。 解建立目标约束。 (1)装配线正常生产 设生产A,B,C型号的电脑为x12x2,x3(台),d1为装配线正常生产时间未利用数 d为装配线加班时间,希望装配线正常生产,避免开工不足,因此装配线目标约束为 min dii (14) 5x1+8x2+12x3+d1-d1=1700 (2)销售目标 优先满足老客户的需求,并根据三种电脑的纯利润分配不同的权因子,A,B,C三 种型号的电脑每小时的利润是 100014402520 5812,因此,老客户的销售目标约束为 min{20d2+18a3+2ld4} 再考虑一般销售。类似上面的讨论,得到 min (20d5 +18d5+21d7j x1+d5-d5=100 x2+d6-d6=120 d-d+=100 (3)加班限制 260
-260- %这里权重weight=目标goal的绝对值 就可求得问题的解。 §5 目标规划模型的实例 前面介绍了目标规划的求解方法，这里再介绍几个目标规划模型的模型，帮助我 们进一步了解目标规划模型的建立和求解过程。 例6 某计算机公司生产三种型号的笔记本电脑 A, B,C 。这三种笔记本电脑需要 在复杂的装配线上生产，生产1台 A, B,C 型号的笔记本电脑分别需要5，8，12（h）。公 司装配线正常的生产时间是每月1700h。公司营业部门估计 A, B,C 三种笔记本电脑的利 润分别是每台1000，1440，2520（元），而公司预测这个月生产的笔记本电脑能够全部 售出。公司经理考虑以下目标： 第一目标：充分利用正常的生产能力，避免开工不足； 第二目标：优先满足老客户的需求， A, B,C 三种型号的电脑50，50，80（台）， 同时根据三种电脑的纯利润分配不同的权因子； 第三目标：限制装配线加班时间，最好不要超过200h； 第四目标：满足各种型号电脑的销售目标，A, B,C 型号分别为100，120，100（台）， 再根据三种电脑的纯利润分配不同的权因子； 第五目标：装配线的加班时间尽可能少。 请列出相应的目标规划模型，并用LINGO软件求解。 解 建立目标约束。 （1）装配线正常生产 设生产 A, B,C 型号的电脑为 1 2 3 x , x , x（台）， − d1 为装配线正常生产时间未利用数， + d1 为装配线加班时间，希望装配线正常生产，避免开工不足，因此装配线目标约束为 ⎪⎩ ⎪ ⎨ ⎧ + + + − = − + − 5 8 12 1700 min { } 1 2 3 1 1 1 x x x d d d （14） （2）销售目标 优先满足老客户的需求，并根据三种电脑的纯利润分配不同的权因子， A, B,C 三 种型号的电脑每小时的利润是 12 2520 , 8 1440 , 5 1000 ，因此，老客户的销售目标约束为 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ + − = + − = + − = + + − + − + − + − − − 80 50 50 min {20 18 21 } 3 4 4 2 3 3 1 2 2 2 3 4 x d d x d d x d d d d d （15） 再考虑一般销售。类似上面的讨论，得到 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ + − = + − = + − = + + − + − + − + − − − 100 120 100 min {20 18 21 } 3 7 7 2 6 6 1 5 5 5 6 7 x d d x d d x d d d d d （16） （3）加班限制
首先是限制装配线加班时间,不允许超过200h,因此得到 Imin(ds) 12x3+d-d=1900 其次装配线的加班时间尽可能少,即 5x1+8x2+12x1+d1-d=1700 写出目标规划的数学模型 min=Pd1+P(20d2+18d3+2ld4)+P?d3 P(20d5+18d6+2ld7)+Psdi t.5x1+8x2+12x3+d-d1=1700 x,+dl7-d+=50 x2+d3-d3 x3+d4-d4=80 x1+d5-a5=100 d-d=120 d7-d7=100 5x1+8x2+12x3+d3-d=1900 x1,x2,d,d≥0,i=1,2,…8 写出相应的 LINGO程序如下 moae 1eve1/1..5/:p,z,goa1 variable/1.3/: x s con num/1.8/: g, dpls, minus con(s con num, variable): ci o(1eve, s con num)/11,22,23,24,38,45,46,47,5 / plus, minus endsets data g=17005050801001201001900; c=58121000100011000100015812; plus=000010001 miNus=120182102018210; enddata min=@sum (level: p*z)i p(ctr)=1 @for(level(i)li#ne#ctr: p(1)=0) @for (level(1):z(i)=@sum(obj(i,3): plus(,j)*dplus(])+wminus(i, 3)* dominus(3)))i for(sconnum(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dp1us(i
-261- 首先是限制装配线加班时间，不允许超过200h，因此得到 ⎪⎩ ⎪ ⎨ ⎧ + + + − = − + − 5 8 12 1900 min { } 1 2 3 8 8 8 x x x d d d （17） 其次装配线的加班时间尽可能少，即 ⎪⎩ ⎪ ⎨ ⎧ + + + − = − + + 5 8 12 1700 min { } 1 2 3 1 1 1 x x x d d d （18） 写出目标规划的数学模型 − − − + − − − − + + + + + = + + + + 4 5 6 7 5 1 1 1 2 2 3 4 3 8 (20 18 21 ) min (20 18 21 ) P d d d P d z Pd P d d d P d s.t. 5 1 +8 2 +12 3 + 1 − 1 =1700 − + x x x d d 80 50 50 3 4 4 2 3 3 1 2 2 + − = + − = + − = − + − + − + x d d x d d x d d 100 120 100 3 7 7 2 6 6 1 5 5 + − = + − = + − = − + − + − + x d d x d d x d d 5 1 +8 2 +12 3 + 8 − 8 =1900 − + x x x d d 1, 2 , , ≥ 0 − + di di x x ，i =1,2,L,8 写出相应的LINGO程序如下： model: sets: level/1..5/:p,z,goal; variable/1..3/:x; s_con_num/1..8/:g,dplus,dminus; s_con(s_con_num,variable):c; obj(level,s_con_num)/1 1,2 2,2 3,2 4,3 8,4 5,4 6,4 7,5 1/:wplus,wminus; endsets data: ctr=?; goal=? ? ? ? 0; g=1700 50 50 80 100 120 100 1900; c=5 8 12 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 5 8 12; wplus=0 0 0 0 1 0 0 0 1; wminus=1 20 18 21 0 20 18 21 0; enddata min=@sum(level:p*z); p(ctr)=1; @for(level(i)|i#ne#ctr:p(i)=0); @for(level(i):z(i)=@sum(obj(i,j):wplus(i,j)*dplus(j)+wminus(i,j)* dminus(j))); @for(s_con_num(i):@sum(variable(j):c(i,j)*x(j))+dminus(i)-dplus(i
)=g(1)) @for (level (i)Ii #lt# size(level): @bnd(o, z(i), goal)) End 经5次计算得到x1=100,x2=55,x3=80。装配线生产时间为1900h,满足装配 线加班不超过200h的要求。能够满足老客户的需求,但未能达到销售目标。销售总利润为 100×1000+55×1440+80×2520=380800(元) 例7已知三个工厂生产的产品供应给四个客户,各工厂生产量、用户需求量及从 各工厂到用户的单位产品的运输费用如下表所示,其中总生产量小于总需求量。 生产量 厂1 2255 3642 工厂3 4 400 需求量 200 100 (1)求总运费最小的运输问题的调度方案 (2)上级部门经研究后,制定了调配方案的8项指标,并规定了重要性的次序。 第一目标:用户4为重要部门,需求量必须全部满足 第二目标:供应用户1的产品中,工厂3的产品不少于100个单位; 第三目标:每个用户的满足率不低于80% 第四目标:应尽量满足各用户的需求 第五目标:新方案的总运费不超过原运输问题的调度方案的10% 第六目标:因道路限制,工厂2到用户4的路线应尽量避免运输任务 第七目标:用户1和用户3的满足率应尽量保持平衡 第八目标:力求减少总运费。 请列出相应的目标规划模型,并用 LINGO程序求解 解(1)求解原运输问题 由于总生产量小于总需求量,虚设工厂4,生产量为100个单位,到各个用户间的运 费单价为0。用 LINGO软件求解,得到总运费是2950元,运输方案如下表所示 200 250 工厂4 100 需求量 450 (2)下面按照目标的重要性的等级列出目标规划的约束和目标函数。 设x为工厂(=1,2,3)调配给用户j(=1234)的运量,cn表示从工厂i到用户j 的单位产品的运输费用,a,(=1,2,34)表示第j个用户的需求量,b(=1,2,3)表示第i 个工厂的生产量。 i)供应约束应严格满足,即 ii)供应用户1的产品中,工厂3的产品不少于100个单位,即 x31+d1-d1=100 iii)需求约束。各用户的满足率不低于80%,即
-262- )=g(i)); @for(level(i)|i #lt# @size(level):@bnd(0,z(i),goal)); End 经5次计算得到 100 x1 = ， 55 x2 = ， x3 = 80 。装配线生产时间为1900h，满足装配 线加班不超过200h的要求。能够满足老客户的需求，但未能达到销售目标。销售总利润为 100×1000 + 55×1440 + 80× 2520 = 380800 （元） 例7 已知三个工厂生产的产品供应给四个客户，各工厂生产量、用户需求量及从 各工厂到用户的单位产品的运输费用如下表所示，其中总生产量小于总需求量。 用 户 1 2 3 4 生产量 工厂1 5 2 6 7 300 工厂2 3 5 4 6 200 工厂3 4 5 2 3 400 需求量 200 100 450 250 （1）求总运费最小的运输问题的调度方案。 （2）上级部门经研究后，制定了调配方案的8项指标，并规定了重要性的次序。 第一目标：用户4为重要部门，需求量必须全部满足； 第二目标：供应用户1的产品中，工厂3的产品不少于100个单位； 第三目标：每个用户的满足率不低于80％； 第四目标：应尽量满足各用户的需求； 第五目标：新方案的总运费不超过原运输问题的调度方案的10％； 第六目标：因道路限制，工厂2到用户4的路线应尽量避免运输任务； 第七目标：用户1和用户3的满足率应尽量保持平衡； 第八目标：力求减少总运费。 请列出相应的目标规划模型，并用LINGO程序求解。 解 （1）求解原运输问题 由于总生产量小于总需求量，虚设工厂4，生产量为100个单位，到各个用户间的运 费单价为0。用LINGO软件求解，得到总运费是2950元，运输方案如下表所示。 用 户 1 2 3 4 生产量 工厂1 100 200 300 工厂2 200 200 工厂3 250 150 400 工厂4 100 100 需求量 200 100 450 250 （2）下面按照目标的重要性的等级列出目标规划的约束和目标函数。 设 ij x 为工厂i(i =1,2,3) 调配给用户 j( j = 1,2,3,4) 的运量， ij c 表示从工厂i 到用户 j 的单位产品的运输费用，a ( j = 1,2,3,4) j 表示第 j 个用户的需求量，b (i =1,2,3) i 表示第i 个工厂的生产量。 i）供应约束应严格满足，即 i j ∑xij ≤ b = 4 1 ii）供应用户1的产品中，工厂3的产品不少于100个单位，即 31 + 1 − 1 =100 − + x d d iii）需求约束。各用户的满足率不低于80％，即