第4章 目标规划-第1,2节

1、第1节 目标规划的数学模型第2节 解目标规划的图解法钱颂迪制作运筹学（第三版）运筹学教材编写 组第4章 目标规划清华大学出版社第4章 目标规划v第1节 目标规划的数学模型v第2节 解目标规划的图解法v第3节 解目标规划的单纯形法v第4节 灵敏度分析v第5节 应用举例第1节 目标规划的数学模型v为了具体说明目标规划与线性规划在处理问题方法上的区别，先通过例子来介绍目标规划的有关概念及数学模型。 例1 某工厂生产，两种产品，已知有关数据见下表。试求获利最大的生产方案。 拥有量 原材料(kg) 设备(hr) 2 1 1 2 11 10 利润(元/件) 8 10 解： 这是求获利最大的单目标的规划问题

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

3、润指标56元。 这样在考虑产品决策时，便为多目标决策问题。目标规划方法是解这类决策问题的方法之一。下面引入与建立目标规划数学模型有关的概念。 v1.设x1，x2为决策变量，此外，引进正、负偏差变量d+，d- 。正偏差变量d表示决策值超过目标值的部分；负偏差变量d-表示决策值未达到目标值的部分。因决策值不可能既超过目标值同时又未达到目标值，即恒有d+d-=0。2.绝对约束和目标约束v绝对约束是指必须严格满足的等式约束和不等式约束；如线性规划问题的所有约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。目标约束是目标规划特有的，可把约束右端项看作要追求的目标值。在达到此目标值时允许发

4、生正或负偏差，因此在这些约束中加入正、负偏差变量，它们是软约束。线性规划问题的目标函数，在给定目标值和加入正、负偏差变量后可变换为目标约束。也可根据问题的需要将绝对约束变换为目标约束。如：例1的目标函数z=8x1+10 x2可变换为目标约束8x1+10 x2+d1-d1+=56。约束条件2x1+x211可变换为目标约束2x1+x2+d2-d2+=11。3.优先因子(优先等级)与权系数v一个规划问题常常有若干目标。但决策者在要求达到这些目标时，是有主次或轻重缓急的不同。要求第一位达到的目标赋予优先因子P1，次位的目标赋予优先因子P2，并规定PkPk+1,k=1,2,，K。表示Pk比Pk+1有更大

5、的优先权。即首先保证P1级目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的；依此类推。若要区别具有相同优先因子的两个目标的差别，这时可分别赋予它们不同的权系数j,这些都由决策者按具体情况而定。 4.目标规划的目标函数v目标规划的目标函数(准则函数)是按各目标约束的正、负偏差变量和赋予相应的优先因子及权系数而构造的。当每一目标值确定后，决策者的要求是尽可能缩小偏离目标值。因此目标规划的目标函数只能是vmin z=f(d+,d-)。其基本形式有三种： v(1) 要求恰好达到目标值，即正、负偏差变量都要尽可能地小，这时vmin z=f(d+d-)v(2) 要求不超过目标

6、值，即允许达不到目标值，就是正偏差变量要尽可能地小。这时min z=f(d+)v(3) 要求超过目标值，即超过量不限，但必须是负偏差变量要尽可能地小，这时min z=f(d-)v对每一个具体目标规划问题，可根据决策者的要求和赋予各目标的优先因子来构造目标函数，以下用例子说明。 v例例2 例1的决策者在原材料供应受严格限制的基础上考虑：首先是产品的产量不低于产品的产量；其次是充分利用设备有效台时，不加班；再次是利润额不小于56元。求决策方案 。解解 按决策者所要求的，分别赋予这三个目标P1，P2，P3优先因子。这问题的数学模型是： 3 , 2 , 1, 0,561081020112)(min21

7、332122211121213322211iddxxddxxddxxddxxxxdPddPdPzii满足约束条件：目标函数：目标规划的一般数学模型为)54(3 , 2 , 1, 0,)44(, 1, 0) 34(, 1,),()24(, 1,) 14()(min1111kddnjxmibxaKkgddxcddPzkkjijnjijkkkjnjkjklkkKklkLll满足约束条件：目标函数： 为权系数。 lklk, 第第2节节 解目标规划的图解法解目标规划的图解法v对只具有两个决策变量的目标规划的数学模型，可以用图解法来分析求解。用例2来说明（图4-1） 。3 , 2 , 1, 0,56108

8、1020112)(min21332122211121213322211iddxxddxxddxxddxxxxdPddPdPziiv注意目标规划问题求解时，把绝对约束作最高优先级考虑。在本例中能依先后次序都满足d1+=1，d2+d2-=0，d3-=0，因而z*=0。但在大多数问题中并非如此，会出现某些约束得不到满足，故将目标规划问题的最优解称为满意解。 3d3d3d例3 某电视机厂装配黑白和彩色两种电视机，每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。预计市场每周彩色电视机的销量是24台，每台可获利80元；黑白电视机的销量是30台，每台可获利40元。该厂确定的目标为：v第一优先

9、级：充分利用装配线每周计划开动40小时；v第二优先级：允许装配线加班；但加班时间每周尽量不超过10小时；v第三优先级：装配电视机的数量尽量满足市场需要。因彩色电视机的利润高，取其权系数为2。v试建立这问题的目标规划模型，并求解黑白和彩色电视机的产量。 解 设x1，x2分别表示黑白和彩色电视机的产量。这个问题的目标规划模型为4 , 3 , 2 , 1, 0,30245040)2(min21442331222111214332211iddxxddxddxddxxddxxddPdPdPzii满足约束条件：目标函数：用图解法求解，见图4.2。从图4.2中看到v在考虑具有P1、P2的目标实现后，x1、x

10、2的取值范围为ABCD。考虑P3的目标要求时，因d3的权系数大于d4，故先考虑min d3；这时x1、x2的取值范围缩小为ABEF区域。然后考虑d4。在ABEF中无法满足d4=0，因此只能在ABEF中取一点，使d4尽可能小，这就是E点。故E点为满意解。其坐标为(24，26)，即该厂每周应装配彩色电视机24台，黑白电视机26台。第第3节节 解目标规划的单纯形法解目标规划的单纯形法 目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以可用单纯形法求解。但要考虑目标规划的数学模型一些特点，作以下规定：v(1) 因目标规划问题的目标函数都是求最小化，所以以cj-zj0，j=1,2,

11、，n为最优准则。v(2) 因非基变量的检验数中含有不同等级的优先因子，即v因P1P2PK；从每个检验数的整体来看：检验数的正、负首先决定于P1的系数1j的正、负。若1j=0，这时此检验数的正、负就决定于P2的系数2j的正、负，下面可依此类推。 解目标规划问题的单纯形法的计算步骤：v(1) 建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K行，置k=1。v(2) 检查该行中是否存在负数，且对应的前k-1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转(3)。若无负数，则转(5)。v(3) 按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变

12、量为换出变量。v(4) 按单纯形法进行基变换运算，建立新的计算表，返回(2)。v(5) 当k=K时，计算结束。表中的解即为满意解。否则置k=k+1，返回到(2)。例例4 4 试用单纯形法来求解例2。将例2的数学模型化为标准型： 3 , 2 , 1, 0,561081020112)(min21332122211121213322211iddxxxddxxddxxddxxxxxdPddPdPziiss满足约束条件：目标函数： 取xs，d1-，d2-，d3-为初始基变量，列初始单纯形表，见表4-1。 cj P1 P2 P3 P4 CB XB b x1 x2 xs d1- d1+ d2- d2+ d3

13、- d3+ P2 P3 xs d1- d2- d3- 11 0 10 56 2 1 1 8 1 -1 2 10 1 1 -1 1 -1 1 -1 11/1 / 10/2 56/10 cj-zj P1 P2 P3 -1 -8 -2 -10 1 2 1 取k=1，检查检验数的P1行，因该行无负检验数，故转(5)。 因k(=2)K(=3)，置k=k+1=3，返回到(2)。 查出检验数P2行中有-1、-2；取min(-1,-2)=-2。 它对应的变量x2为换入变量， 转入(3)。在表4-1上计算最小比值=min(11/1，0，10/2，56/10)=10/2它对应的变量d2-为换出变量，转入(4)计算结果见表4-2。v友谊农场有3万亩农田，欲种植玉米、大豆和小麦三种农作物。各种农作物每亩施肥量分别为0.12、0.20、0.15t。预计秋后玉米每亩可收获500kg，售价为0.24元/公斤，大豆每亩可收获200kg，售价为1.20元/公斤，小麦每亩可收获300kg，售价为0.70元/公斤。农场年初规划时考虑如下目标：v1.年终收益不低于350万元；2.总产量不低于12500公斤；v3.小麦产量以5000公斤为宜；4.大豆产量不低于2000公斤；v5.玉米产量不超过6000公斤；6.、农场现能提供5000t化肥；若不够，需高价购买，所以高价采购量越少越好。v试建立数学模型。v某市准备在下