《运筹学》5目标规划

1、 第五章第五章 目标规划目标规划第一节第一节 目标规划的数学模型目标规划的数学模型具具 体体 案案 例例例例1 某工厂生产某工厂生产，两种产品，已知有关两种产品，已知有关数据见下表。试求获利最大的生产方案。数据见下表。试求获利最大的生产方案。 拥有量 原材料(kg) 设备(hr) 2 1 1 2 11 10 利润(元/件) 8 10 解：解： 这是求获利最大的单目标的规划问题，这是求获利最大的单目标的规划问题，用用x1，x2分别表示分别表示，产品的产量，其线产品的产量，其线性规划模型表述为：性规划模型表述为： 0,102112108max21212121xxxxxxxxz满足约束条件：满足约束

2、条件：目标函数：目标函数： 0,102112108max21212121xxxxxxxxz满足约束条件：满足约束条件：目标函数：目标函数：用图解法求得最优决策方案为：x1*=4, x2*=3, z*=62(元)。 (4,3)实际上工厂在作决策时，要考虑市场等实际上工厂在作决策时，要考虑市场等一系列其他条件一系列其他条件 （1) 1) 根据市场信息，产品根据市场信息，产品的销售量有下降的趋的销售量有下降的趋势，故考虑产品势，故考虑产品的产量不大于产品的产量不大于产品。 (2) (2) 超过计划供应的原材料时，需用高价采购，超过计划供应的原材料时，需用高价采购，会使成本大幅度增加。会使成本大幅度增

3、加。 (3) (3) 应尽可能充分利用设备台时，但不希望加班。应尽可能充分利用设备台时，但不希望加班。 (4) 应尽可能达到并超过计划利润指标应尽可能达到并超过计划利润指标56元。元。 这样在考虑产品决策时，便为多目标决策问题。目这样在考虑产品决策时，便为多目标决策问题。目标规划方法是解这类决策问题的方法之一。下面引标规划方法是解这类决策问题的方法之一。下面引入与建立目标规划数学模型有关的概念。入与建立目标规划数学模型有关的概念。 1.设设x x1 1，x x2 2为决策变量，此外，引进为决策变量，此外，引进正、负偏差变量正、负偏差变量d d+ +，d d- - 。正偏差变量正偏差变量d d表

4、示决策值超过目标值的部分；表示决策值超过目标值的部分；负偏差变量负偏差变量d d- -表示决策值未达到目标值的表示决策值未达到目标值的部分。因决策值不可能既超过目标值同时部分。因决策值不可能既超过目标值同时又未达到目标值，即恒有又未达到目标值，即恒有d d+ +d d- -=0=0。2.2.绝对约束和目标约束绝对约束和目标约束 绝对约束是指必须严格满足的等式约束和不等式约绝对约束是指必须严格满足的等式约束和不等式约束；如线性规划问题的所有约束条件，不能满足这束；如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。些约束条件的解称为非可行解，所以它们是硬约束。

5、目标约束是目标规划特有的，可把约束右端项看作目标约束是目标规划特有的，可把约束右端项看作要追求的目标值。在达到此目标值时允许发生正或要追求的目标值。在达到此目标值时允许发生正或负偏差，因此在这些约束中加入正、负偏差变量，负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束。它们是软约束。 线性规划问题的目标函数，在给定目标值和加入正、线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的负偏差变量后可变换为目标约束。也可根据问题的需要将绝对约束变换为目标约束。如：例需要将绝对约束变换为目标约束。如：例1 1的目标的目标函数函数z=8xz=8x1 1+10

6、 x+10 x2 2可变换为目标约束可变换为目标约束8x8x1 1+10 x+10 x2 2+d+d1 1- - -d d1 1+ +=56=56。约束条件。约束条件2x2x1 1+x+x2 21111可变换为目标约束可变换为目标约束2x2x1 1+x+x2 2+d+d2 2-d d2 2+ +=11=11。3.3.优先因子优先因子( (优先等级优先等级) )与权系数与权系数 一个规划问题常常有若干目标。但决策者在要求达到一个规划问题常常有若干目标。但决策者在要求达到这些目标时，是有主次或轻重缓急的不同。要求第一这些目标时，是有主次或轻重缓急的不同。要求第一位达到的目标赋予优先因子位达到的目标

7、赋予优先因子P1，次位的目标赋予优先，次位的目标赋予优先因子因子P2，并规定，并规定PkPk+1,k=1,2,，K。表示。表示Pk比比Pk+1有更大的优先权。即首先保证有更大的优先权。即首先保证P1级目标的实现，级目标的实现，这时可不考虑次级目标；而这时可不考虑次级目标；而P2级目标是在实现级目标是在实现P1级目级目标的基础上考虑的；依此类推。标的基础上考虑的；依此类推。 若要区别具有相同优先因子的两个目标的差别，这时若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数可分别赋予它们不同的权系数j,这些都由决策者按具这些都由决策者按具体情况而定。体情况而定。 4.4.目标规

8、划的目标函数目标规划的目标函数 目标规划的目标函数目标规划的目标函数(准则函数准则函数)是按各目标是按各目标约束的正、负偏差变量和赋予相应的优先因约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。当每一目标值确定后，子及权系数而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是此目标规划的目标函数只能是 min z=f(d+,d-)。其基本形式有三种：其基本形式有三种： (1) (1) 要求恰好达到目标值，即正、负偏差变量都要要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时尽可能地小，这时 min

9、z=f(dmin z=f(d+ +d+d- -) ) (2) (2) 要求不超过目标值，即允许达不到目标值，就要求不超过目标值，即允许达不到目标值，就是正偏差变量要尽可能地小。这时是正偏差变量要尽可能地小。这时min z=f(dmin z=f(d+ +) ) (3) (3) 要求超过目标值，即超过量不限，但必须是负要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时偏差变量要尽可能地小，这时min z=f(dmin z=f(d- -) ) 对每一个具体目标规划问题，可根据决策者的要求对每一个具体目标规划问题，可根据决策者的要求和赋予各目标的优先因子来构造目标函数，以下用和赋予各目

10、标的优先因子来构造目标函数，以下用例子说明。例子说明。 例例2 ： 例例1的决策者在原材料供应受严格限制的决策者在原材料供应受严格限制的基础上考虑：的基础上考虑：首先：产品首先：产品的产量不低于产品的产量不低于产品的产量；的产量；其次：充分利用设备有效台时，不加班；其次：充分利用设备有效台时，不加班；再次：利润额不小于再次：利润额不小于56元。元。求决策方案求决策方案 。解解 按决策者所要求的，分别赋予这三个目标按决策者所要求的，分别赋予这三个目标P1，P2，P3优先因子。这问题的数学模型是优先因子。这问题的数学模型是： 3 , 2 , 1, 0,561081020112)(min213321

11、22211121213322211iddxxddxxddxxddxxxxdPddPdPzii满满足足约约束束条条件件：目目标标函函数数：目标规划的一般数学模型为目标规划的一般数学模型为 )5(3 , 2 , 1, 0,)4(, 1, 0)3(, 1,),()2(, 1,)1()(min1111kddnjxmibxaKkgddxcddPzkkjijnjijkkkjnjkjklkkKklkLll满满足足约约束束条条件件：目目标标函函数数： 为权系数。为权系数。 lklk ,第二节第二节 目标规划的图解法目标规划的图解法例例 某电视机厂装配普通电视和等离子电视机，每装某电视机厂装配普通电视和等离子电

12、视机，每装配任何一台电视机需占用装配线配任何一台电视机需占用装配线1 1小时，装配线每周小时，装配线每周计划开动计划开动4040小时。预计市场每周等离子电视机的销量小时。预计市场每周等离子电视机的销量是是2424台，每台可获利台，每台可获利8080元；普通电视机的销量是元；普通电视机的销量是3030台，台，每台可获利每台可获利4040元。该厂确定的目标为：元。该厂确定的目标为： 第一优先级：充分利用装配线每周计划开动第一优先级：充分利用装配线每周计划开动4040小小时；时； 第二优先级：允许装配线加班；但加班时间每周第二优先级：允许装配线加班；但加班时间每周尽量不超过尽量不超过1010小时；小

13、时； 第三优先级：装配电视机的数量尽量满足市场需第三优先级：装配电视机的数量尽量满足市场需要。因等离子电视机的利润高，取其权系数为要。因等离子电视机的利润高，取其权系数为2 2。 试建立这问题的目标规划模型，并求解普通和等试建立这问题的目标规划模型，并求解普通和等离子电视机的产量。离子电视机的产量。 解解 设设x x1 1，x x2 2分别表示等离子和普通电视机的分别表示等离子和普通电视机的产量。这个问题的目标规划模型为产量。这个问题的目标规划模型为 4 , 3 , 2 , 1, 0,3024:50:)(40:)2(min21442331322212112114312211 idxxdddxc

14、ddxPbddxxPaddxxPddPdPdPi(d)0102030405060102030405060(a)(b)(c)(24, 26)满足满足P1, P2的可行域的可行域满足满足P1, P2, P3(c)的可行域的可行域目标规划目标规划的最优解的最优解d1+d2+d4+ 1d 4d 2d 3d 3d资源资源甲甲乙乙资源限制资源限制设备台时设备台时2 24 41212材料材料3 33 31212利润（万元利润（万元/单位）单位）43.2消耗定额消耗定额产品产品4 3d 3d43363.7521234 1d 1d0 x1x2 2d 2d硬约束围成区域内，满足硬约束围成区域内，满足第一等级目标的

15、区域。第一等级目标的区域。5满足第一、二等级目标的区域满足第一、二等级目标的区域内，能尽可能地满足第三等级内，能尽可能地满足第三等级目标的区域。这个区域仅包含目标的区域。这个区域仅包含点点(2.4, 1.6 ).满足第一等级目标的区满足第一等级目标的区域内，还满足第二等级域内，还满足第二等级目标的区域。这个区域目标的区域。这个区域是一条线段。是一条线段。 3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii满满足足约约束束条条件件：目目标标函函数数：例：前面的例例：前面的例2：满意解

16、为线段满意解为线段DGDG第第3节节 解目标规划的单纯形法解目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法型结构形式上没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型一些特点，作求解。但要考虑目标规划的数学模型一些特点，作以下规定：以下规定： (1) 因目标规划问题的目标函数都是求最小化，所因目标规划问题的目标函数都是求最小化，所以以以以cj-zj0，j=1,2,，n为最优准则。为最优准则。 (2) 因非基变量的检验数中含有不同等级的优先因因非基变量的检验数中含有不同等级的优先因子

17、，即子，即KknjPazckkjjj, 2 , 1;, 2 , 1 因因P1P2PK；从每个检验数的整体；从每个检验数的整体来看：检验数的正、负首先决定于来看：检验数的正、负首先决定于P1的系的系数数1j的正、负。若的正、负。若1j=0，这时此检验数，这时此检验数的正、负就决定于的正、负就决定于P2的系数的系数2j的正、负，的正、负，下面可依此类推。下面可依此类推。 解目标规划问题的单纯形法的计算步骤解目标规划问题的单纯形法的计算步骤： (1) (1) 建立初始单纯形表，在表中将检验数行按优建立初始单纯形表，在表中将检验数行按优先因子个数分别列成先因子个数分别列成K K行，置行，置k=1k=1

18、。 (2) (2) 检查该行中是否存在负数，且对应的前检查该行中是否存在负数，且对应的前k-1k-1行行的系数是零。若有负数取其中最小者对应的变量的系数是零。若有负数取其中最小者对应的变量为换入变量，转为换入变量，转(3)(3)。若无负数，则转。若无负数，则转(5)(5)。 (3) (3) 按最小比值规则确定换出变量，当存在两个按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量。先级别的变量为换出变量。 (4) (4) 按单纯形法进行基变换运算，建立新的计算按单纯形法进行基变换运算，建立新的计算表，返

19、回表，返回(2)(2)。 (5) (5) 当当k=Kk=K时，计算结束。表中的解即为满意解。时，计算结束。表中的解即为满意解。否则置否则置k=k+1k=k+1，返回到，返回到(2)(2)。例例: :试用单纯形法来求解例试用单纯形法来求解例2 2。将例将例2的数学模型化为标准型：的数学模型化为标准型： 3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxxddxxddxxddxxxxxdPddPdPziiss满满足足约约束束条条件件：目目标标函函数数： 取取xs，d1-，d2-，d3-为初始基变量，列初始为初始基变量，列初始单纯形表，见表。单纯形表，见表。 取取k=1k=1，检查，检查P P1 1行的检验数，因该行无负检验数，行的检验数，因该行无负检验数， 故转故转(5)(5)。 因因k(=1)k(=1)K(=3)K(=3)，置，置k=k+1=2k=k+1=2，返回到，返回到(2)(2)。 当当k=2时时,查出查出P2行检验数中有行检验数中有-1、-2； 取取min(-1,-2)=-2。 它对应的变量它对应的变量x2为换入变量，转入为换入变量，转入(3)。 在表上计算最小比值在表上计算最小比值它对应的变量它对应的变量d d2 2- -为换出变量，转入为换出变量，转入(4)(4)210)10