(数学建模教材)21第二十一章目标规划.doc

第二十一章目标规划1 引言1．线性规划的局限性 只能解决一组线性约束条件下，某一目标只能是一个目标的最大或最小值的问题 2．实际决策中，衡量方案优劣考虑多个目标 这些目标中，有主要的，也有次要的；有最大值的，也有最小值的；有定量的，也有定性的；有相互补充的，也有相互对立的，线性规划则无能为力3．目标规划（Goal Programming）美国经济学家查恩斯（A. Charnes）和库柏（W. W. Cooper）在 1961 年出版的《管 理模型及线性规划的工业应用》一书中，首先提出的4．求解思路（1）加权系数法 为每一目标赋一个权系数，把多目标模型转化成单一目标的模型但困难是要确定合理的权系数，以反映不同目标之间的重要程度2）优先等级法 将各目标按其重要程度不同的优先等级，转化为单目标模型3）有效解法 寻求能够照顾到各个目标，并使决策者感到满意的解由决策者来确定选取哪一个解，即得到一个满意解但有效解的数目太多而难以将其一一求出2 目标规划的数学模型为了具体说明目标规划与线性规划在处理问题的方法上的区别，先通过例子来介绍 目标规划的有关概念及数学模型例1 某工厂生产 I，II 两种产品，已知有关数据见表 1，试求获利最大的生产方案。

表 1解 这是一个单目标的规划问题设生产产品 I，II 的量分别为 x1 , x2 时获利最大， 建立如下线性规划模型：maxz = 8x1 + 10x2⎧2x1 + x2 11⎪⎨x1 + 2x2 10⎩x1 , x2 0⎪最优决策方案为： x* = 4, x* = 3, z* = 62 元12但实际上工厂在作决策方案时，要考虑市场等一系列其它条件如（i）根据市场信息，产品 I 的销售量有下降的趋势，故考虑产品 I 的产量不大于 产品 IIii）超过计划供应的原材料，需要高价采购，这就使成本增加iii）应尽可能充分利用设备，但不希望加班395-III拥有量原材料 kg2111设 备 hr1210利润 元/件810（iv）应尽可能达到并超过计划利润指标 56 元这样在考虑产品决策时，便为多目标决策问题目标规划方法是解决这类决策问题 的方法之一下面引入与建立目标规划数学模型有关的概念1. 正、负偏差变量设 d 为决策变量的函数，正偏差变量 d = max{d - d0 ,0} 表示决策值超过目标值 的部分，负偏差变量 d = - min{d - d0 ,0} 表示决策值未达到目标值的部分，这里 d0 表 示 d 的目标 值 。

因 决 策 值 不 可 能 既 超 过 目 标 值 同 时 又 未 达 到 目 标 值，即恒 有 d + d - = 0 2.绝对（刚性）约束和目标约束绝对约束是指必须严格满足的等式约束和不等式约束；如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束目标约束是目标 规划特有的，可把约束右端项看作要追求的目标值在达到此目标值时允许发生正或负 偏差，因此在这些约束中加入正、负偏差变量，它们是软约束线性规划问题的目标函 数，在给定目标值和加入正、负偏差变量后可变换为目标约束也可根据问题的需要将 绝对约束变换为目标约束如：例 1 的目标函数 z = 8x1 + 10x2 可变换为目标约束-+8x + 10x + d - d = 56 绝 对约束 2x1 + x2 11 可 变换为 目 标约束 12 1 1-+2x + x + d - d = 11 1 2 2 23. 优先因子（优先等级）与权系数 一个规划问题常常有若干目标但决策者在要求达到这些目标时，是有主次或轻重缓急的不同凡要求第一位达到的目标赋于优先因子 P1 ，次位的目标赋于优先因子 P2 ,L，并规定 Pk >> Pk +1 , k = 1,2,L, q 。

表示 Pk 比 Pk +1 有更大的优先权以此类推， 若要区别具有相同优先因子的两个目标的差别，这时可分别赋于它们不同的权系数 wj ， 这些都由决策者按具体情况而定4. 目标规划的目标函数 目标规划的目标函数（准则函数）是按各目标约束的正、负偏差变量和赋于相应的优先因子而构造的当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值因z = f (d + , d - ) 其基本形式有三种：此目标规划的目标函数只能是 min（1）要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时min z = f (d + + d - )（2）要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小， 这时z = f (d + )min（3）要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时z = f (d - )min对每一个具体目标规划问题，可根据决策者的要求和赋于各目标的优先因子来构造目标函数，以下用例子说明例 2 例 1 的决策者在原材料供应受严格限制的基础上考虑：首先是产品 II 的产 量不低于产品 I 的产量；其次是充分利用设备有效台时，不加班；再次是利润额不小于 56 元。

求决策方案解 按决策者所要求的，分别赋于这三个目标 P1 , P2 , P3 优先因子这问题的数学-396-模型是min Pd + + P (d - + d + ) + P d -1 1 2 2 2 3 3⎧2x1 + x2 11⎪-+x - x + d - d = 0⎪1 2 1 1⎪⎨-+x + 2x + d - d = 101 2 2 2⎪-+8x + 10x + d - d = 56⎪12 3 3⎪⎩x, x , d - , d + 0, i = 1,2,3.12 i i5．目标规划的一般数学模型设 x j （ j = 1,2,L, n ）是目标规划的决策变量，共有 m 个约束是刚性约束，可能 是等式约束，也可能是不等式约束设有 l 个柔性目标约束，其目标规划约束的偏差为+-di , d （ i = 1,2,L, l ）设有 q 个优先级别，分别为 P , P ,L, P 在同一个优先级 Pi1 2qk+-中，有不同的权重，分别记为 w , w ( j = 1,2,L, l) 因此目标规划模型的一般数学表kj kj达式为q⎛⎞lz = P⎜ wkj d j j =1- -+ + ⎟min+wkj d j⎜⎟k⎝⎠k =1n⎧⎪ aij x j⎪ j=1 (=, )bi , i = 1,L, m⎪⎪n ij-+c x + d - d = gi , i = 1,2,L, l⎨jii⎪ j=1⎪xj 0,j = 1,2,L, n⎪-+⎪d , d 0, i = 1,2,L, l⎩ i i建立目标规划的数学模型时，需要确定目标值、优先等级、权系数等，它们都具有一定的主观性和模糊性，可以用专家评定法给以量化。

3 求解目标规划的序贯式算法序贯式算法是求解目标规划的一种早期算法，其核心是根据优先级的先后次序， 将目标规划问题分解成一系列的单目标规划问题，然后再依次求解求解目标规划的序贯算法对于 k = 1,2,L, q ，求解单目标规划l- -+ +min z = (w d + w d )（1）kj jkj jj=1n aij x j (=, )bi , i = 1,L, m（2）s.t.j =1nc x + d - - d + = g , i = 1,2,L, l（3）ij j i i ij =1-397-l(w d + w d ) z ， s = 1,2,L, k -1 ，- -+ +*（4）sj jsj jsj=1x j 0,（5）（6）j = 1,2,L, n-+di , di 0, i = 1,2,L, l其最优目标值为 z* ，当 k = 1时，约束（4）为空约束当 k = q 时，z* 所对应的解 x* 为k目标规划的最优解q注 此时最优解的概念与线性规划最优解的概念已有所不同，但为方便起见，仍称为最优解。

例 3 某企业生产甲、乙两种产品，需要用到 A, B, C 三种设备，关于产品的赢利 与使用设备的工时及限制如表 2 所示问该企业应如何安排生产，才能达到下列目标：表 2甲乙设备的生产能力（h）A (h/件)B (h/件)C (h/件)赢利（元/件）240200205300121615（1）力求使利润指标不低于 1500 元；（2）考虑到市场需求，甲、乙两种产品的产量比应尽量保持 1:2；（3）设备 A 为贵重设备，严格禁止超时使用；（4）设备 C 可以适当加班，但要控制；设备 B 既要求充分利用，又尽可能不加班 在重要性上，设备 B 是设备 C 的 3 倍建立相应的目标规划模型并求解解 设备 A 是刚性约束，其余是柔性约束首先，最重要的指标是企业的利润， 因此，将它的优先级列为第一级；其次，甲、乙两种产品的产量保持 1:2 的比例，列为 第二级；再次，设备 C, B 的工作时间要有所控制，列为第三级在第三级中，设备 B 的 重要性是设备 C 的三倍，因此，它们的权重不一样，设备 B 前的系数是设备 C 前系数 的 3 倍设生产甲乙两种产品的件数分别为 x1 , x2 ，相应的目标规划模型为-+-+-3+min z = Pd + P (d + d ) + P (3d+ 3d+ d )（7）（8）（9）（10）（11）（12）（13）1 1 2 2 2 3 34s.t. 2x1 + 2x2 12-+200x + 300x + d - d= 150012 1 1-+2x - x + d - d = 01 2 2 2-+4x + d - d = 161 3 3-+5x + d - d = 152 4 4-+x1 , x2 , di , d 0 ， i = 1,2,3,4i序贯算法中每个单目标问题都是一个线性规划问题，可以使用 LINGO 软件进行求解。

求第一级目标LINGO 程序如下：model: sets:-398-variable/1..。