1、运 筹 学Operations ResearchOperations ResearchChapter4目标规划GoalProgramming运筹学OperationsResearch4.1目标规划数学模型Mathematical Model of GP4.2目标规划的图解法The graphical method of GP4.3单纯形法Simplex Method4.1目标规划数学模型Mathematical Model of GP线性规划模型的特征是在满足一组约束条件下，寻求一个目标的最优解（最大值或最小值）。而在现实生活中最优只是相对的，或者说没有绝对意义下的最优，只有相对意义下的满意。
2、1978年诺贝尔经济学奖获得者.西蒙(H.A.Simon-美国卡内基-梅隆大学,1916-)教授提出“满意行为模型要比最大化行为模型丰富得多”，否定了企业的决策者是“经济人”概念和“最大化”行为准则，提出了“管理人”的概念和“令人满意”的行为准则，对现代企业管理的决策科学进行了开创性的研究 4.1目标规划的数学模型MathematicalModelofGP【例4.】考虑例1.1资源消耗如表4-1所示。x1、x2、x3分别为甲、乙、丙的产量。使企业在计划期内总利润最大的线性规划模型为： 产品 资源甲乙丙现有资源设备A312200设备B224200材料C451360材料D235300利润（元/件）
3、403050表4-14.1.1引例4.1目标规划的数学模型MathematicalModelofGP最优解X（50，30，10），Z34004.1目标规划的数学模型MathematicalModelofGP 现在决策者根据企业的实际情况和市场需求，需要重新制定经营目标，其目标的优先顺序是：（1）利润不少于3200元（2）产品甲与产品乙的产量比例尽量不超过1.5（3）提高产品丙的产量使之达到30件（4）设备加工能力不足可以加班解决，能不加班最好不加班（5）受到资金的限制，只能使用现有材料不能再购进【解】设甲、乙、丙产品的产量分别为x1、x2、x3。如果按线性规划建模思路，最优解实质是求下列一组不
4、等式的解4.1目标规划的数学模型MathematicalModelofGP通过计算不等式无解，即使设备加班10小时仍然无解在实际生产过程中生产方案总是存在的，无解只能说明在现有资源条件下，不可能完全满足所有经营目标这种情形是按事先制定的目标顺序逐项检查，尽可能使得结果达到预定目标，即使不能达到目标也使得离目标的差距最小，这就是目标规划的求解思路，对应的解称为满意解下面建立例4.1的目标规划数学模型4.1目标规划的数学模型MathematicalModelofGP设d为未达到目标值的差值，称为负偏差变量（negativedeviationvariable）d+为超过目标值的差值，称为正偏差变量（
5、positivedeviationvariable）, d0、d0设d1-未达到利润目标的差值,d1+为超过目标的差值当利润小于3200时,d1且d10,有40 x1+30 x2+50 x3+d1=3200成立当利润大于3200时，d1且d1，有40 x1+30 x2+50 x3-d1+=3200成立当利润恰好等于3200时，d1=且d1+=0,有40 x1+30 x2+50 x3=3200成立实际利润只有上述三种情形之一发生，因而可以将三个等式写成一个等式40 x1+30 x2+50 x3+d1d1+=32004.1目标规划的数学模型MathematicalModelofGP（2）设分别为未
6、达到和超过产品比例要求的偏差变量,则产量比例尽量不超过1.5的数学表达式为：（3）设d3、d分别为品丙的产量未达到和超过30件的偏差变量，则产量丙的产量尽可能达到30件的数学表达式为：利润不少于3200理解为达到或超过3200，即使不能达到也要尽可能接近3200,可以表达成目标函数d1取最小值，则有4.1目标规划的数学模型MathematicalModelofGP（4）设d4 、d4+为设备A的使用时间偏差变量,d5、d5+为设备B的使用时间偏差变量，最好不加班的含义是d4+和d5+同时取最小值，等价于d4+d5+取最小值，则设备的目标函数和约束为：（5）材料不能购进表示不允许有正偏差，约束条
7、件为小于等于约束由于目标是有序的并且四个目标函数非负，因此目标函数可以表达成一个函数：4.1目标规划的数学模型MathematicalModelofGP式中：Pj（j=1,2,3,4）称为目标的优先因子，第一目标优于第二目标，第二目标优于第三目标等等，其含义是按P1、P2、的次序分别求后面函数的最小值.则问题的目标规划数学模型为：4.1目标规划的数学模型MathematicalModelofGP约束实际 偏差目标1 C13220=32002 C22=03 C330=304 C4164=2005 C5216=2006 C6242118=3607 C726634=3001X1282X2203X33
8、04d1-05d1+206d2-27d2+08d3-09d3+010d4-3611d4+012d5-013d5+16满意解：约束分析：4.1目标规划的数学模型MathematicalModelofGP（1）目标规划数学模型的形式有：线性模型、非线性模型、整数模型、交互作用模型等（2）一个目标中的两个偏差变量di-、di+至少一个等于零，偏差变量向量的叉积等于零：dd=0（3）一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值，按多个目标的重要性，确定优先等级，顺序求最小值（4）按决策者的意愿，事先给定所要达到的目标值当期望结果不超过目标值时，目标函数求正偏差变量最小;当期望结果不
9、低于目标值时，目标函数求负偏差变量最小;当期望结果恰好等于目标值时，目标函数求正负偏差变量之和最小4.1.2数学模型4.1目标规划的数学模型MathematicalModelofGP（5）由目标构成的约束称为目标约束，目标约束具有更大的弹性，允许结果与所制定的目标值存在正或负的偏差，如例4.1中的5个等式约束；如果决策者要求结果一定不能有正或负的偏差，这种约束称为系统约束，如例4.1的材料约束；（6）目标的排序问题。多个目标之间有相互冲突时，决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方法，构造各目标的权系数，依据权系数的大小确定目标顺序；（7）合理的确定目标数。目标规划的目标
10、函数中包含了多个目标，决策者对于具有相同重要性的目标可以合并为一个目标，如果同一目标中还想分出先后次序，可以赋予不同的权系数，按系数大小再排序。例如，在例4.1中要求设备B的加班时间不超过设备A的时间，目标函数可以表达为,表示在中先求最小再求最小。4.1目标规划的数学模型MathematicalModelofGP（8）多目标决策问题多目标决策研究的范围比较广泛，在决策中，可能同时要求多个目标达到最优例如，企业在对多个项目投资时期望收益率尽可能最大，投资风险尽可能最小，属于多目标决策问题，本章的目标规划尽管包含有多个目标，但还是按单个目标求偏差变量的最小值，目标函数中不含有决策变量，目标规划只是
11、多目标决策的一种特殊情形本章不讨论多目标规划的求解方法，只给出WinQSB软件求解线性多目标规划的操作步骤，参看例4.3和4.94.1目标规划的数学模型MathematicalModelofGP（9）目标规划的一般模型设xj（j=1,2,n）为决策变量4.1目标规划的数学模型MathematicalModelofGP式中p k为第k级优先因子,k=1、2、K；wkl-、wkl+，为分别赋予第l个目标约束的正负偏差变量的权系数；gl为目标的预期目标值，l=1,L(4.1b)为系统约束,（4.1c）为目标约束【例4.2】某企业集团计划用1000万元对下属5个企业进行技术改造，各企业单位的投资额已知
12、，考虑2种市场需求变化、现有竞争对手、替代品的威胁等影响收益的4个因素，技术改造完成后预测单位投资收益率(（单位投资获得利润/单位投资额）100)如表42所示4.1目标规划的数学模型MathematicalModelofGP集团制定的目标是：（1）希望完成总投资额又不超过预算；（2）总期望收益率达到总投资的30%；（3）投资风险尽可能最小；（4）保证企业5的投资额占20%左右集团应如何作出投资决策企业1企业2企业3企业4企业5单位投资额(万元)1210151320单位投资收益率预测rij市场需求14.3255.845.26.56市场需求23.523.045.084.26.24现有竞争对手3.1
13、62.23.563.284.08替代品的威胁2.243.122.62.23.24期望(平均)收益率3.313.344.273.725.03表424.1目标规划的数学模型MathematicalModelofGP【解】设xj（j=1,2,5）为集团对第j 个企业投资的单位数（1）总投资约束：4.1目标规划的数学模型MathematicalModelofGP（2）期望利润率约束：整理得（4）企业5占20%的投资的目标函数为,约束条件即4.1目标规划的数学模型MathematicalModelofGP(3）投资风险约束投资风险值的大小一般用期望收益率的方差表示，但方差是x的非线性函数这里用离差（ri
14、jE(rj)）近似表示风险值，例如，集团投资5个企业后对于市场需求变化第一情形的风险是：则4种因素风险最小的目标函数为：，约束条件为4.1目标规划的数学模型MathematicalModelofGP根据目标重要性依次写出目标函数，整理后得到投资决策的目标规划数学模型：【例4.3】车间计划生产I、II两种产品，每种产品均需经过A、B两道工序加工工艺资料如表43所示 产品工序产品甲产品乙每天加工能力(小时)A22120B12100C2.20.890产品售价(元/件)5070产品利润(元/件)108（1）车间如何安排生产计划，使产值和利润都尽可能高（2）如果认为利润比产值重要，怎样决策表434.1目
15、标规划的数学模型MathematicalModelofGP【解】设x1、x2分别为产品甲和产品乙的日产量，得到线性多目标规划模型：4.1目标规划的数学模型MathematicalModelofGP（1）将模型化为目标规划问题首先，通过分别求产值最大和利润最大的线性规划最优解产值最大的最优解：X(1)（20，40），Z13800利润最大的最优解：X(2)（30，30），Z2540目标确定为产值和利润尽可能达到3800和540，得到目标规划数学模型：4.1目标规划的数学模型MathematicalModelofGP4.1目标规划的数学模型MathematicalModelofGP,等价于（2）给d
16、2-赋予一个比d1-的系数大的权系数,如，约束条件不变.权系数的大小依据重要程度给定，或者根据同一优先级的偏差变量的关系给定，例如，当利润d2-减少一个单位时，产值d1-减少3个单位，则赋予d2-权系数3，则目标函数为本节介绍了如何建立目标规划的数学模型及有关概念1.目标规划由哪些要素构成，与线性规划有哪些不同之处2.偏差变量的含义及其作用3.目标函数的表达方法4.优先级别的含义4.1目标规划的数学模型MathematicalModelofGP4.2目标规划的图解法The graphical method of GP4.2目标规划的图解法ThegraphicalmethodofGP当目标规划模
17、型中只含两个决策变量（不包含偏差变量）时，可以用图解法求出满意解【例4.4】企业计划生产I 、 II 两种产品，这些产品需要使用两种材料，要在两种不同设备上加工工艺资料如表44所示产品 资源产品甲产品乙现有资源材料I3012(kg)材料II0414(kg)设备A2212(h)设备B5315(h)产品利润(元/件)2040表44【解】设x1、x2分别为产品甲和产品乙的产量，目标规划数学模型为：企业怎样安排生产计划，尽可能满足下列目标：(1)力求使利润指标不低于80元(2)考虑到市场需求,、II两种产品的生产量需保持1:1的比例(3)设备A既要求充分利用，又尽可能不加班(4)设备B必要时可以加班，
18、但加班时间尽可能少(5)材料不能超用。4.2目标规划的图解法ThegraphicalmethodofGP(2)(1)(3)(4 )x2x1(6)(5)o464622图41ABC满意解C(3,3)满意解X(3,3)(3)x1x22040608010020406080100(2)(1)(4)图53BC满意解是线段上任意点，端点的解是B(100/3，80/3)，C(60，0)决策者根据实际情形进行二次选择A(3)x1x22040608010020406080100(2)(1)(4)图53BC满意解是点B，X=(100/3，80/3)A(3)x1x22040608010020406080100(2)(
19、1)(4)图53满意解是点A，X=(20，40)A本节介绍了目标规划的图解法1.画出系统约束和目标约束直线2.标明偏差变量大于零的变量X的取值区域3.按优先次序分别求各目标的最小值4.2目标规划的图解法ThegraphicalmethodofGP4.3单纯形法SimplexMethod单纯形法求解目标规划可参照第一章的步骤，只是目标规划的检验要按优先级顺序逐级进行，不同的是：（1）首先使得检验数中P1的系数非负，再使得P2的系数非负，依次进行；（2）当P1、P2、Pk对应的系数全部非负时得到满意解；（3）如果P1，Pi行系数非负，而Pi+1行存在负数，并且负数所在列上面P1，Pi行中存在正数时
20、，得到满意解，计算结束4.3单纯形法SimplexMethod【例4.6】用单纯形法求解下述目标规划问题【解】以d1、d2、d3为基变量，求出检验数，将检验数中优先因子分离出来，每一优先级做一行，列出初始单纯形表4-54.3单纯形法SimplexMethodCj00P100P1P20bCB基x1x2d1d1+d2d2+d3d3+P1d11211500d2211140P2d3221180CjZjP112 11P2221表454.3单纯形法SimplexMethod表45中，P1行中(2)最小，则x2进基，求最小比值易知d1出基，将第二列主元素化为1，其余元素化为零，得到表4-6Cj00P100P
21、1P20bCB基x1x2d1d1+d2d2+d3d3+0 x21/211/21/2250d23/21/21115P2d3111130CjZjP111P21111表464.3单纯形法SimplexMethod表4-6中P1行全部检验数非负，表明第一目标已经得到优化P2行存在负数，x1的检验数为P20，选x1进基（也可以选d1+进基），则d3出基，迭代得到表4-7Cj00P100P1P20bCB基x1x2d1d1+d2d2+d3d3+0 x212/32/31/3200 x111/32/310P2d32/32/31120CjZjP111P22/3-2/32/3-2/314.3单纯形法SimplexM
22、ethod 表4-7在表4-7中，P1行的系数全部非负，P2行存在负数，d1+的检验数2/3P20,所有检验数非负，得到满意解X（0，40）【例4.7】(1)用单纯形法求解例4.5（2）当目标函数变为【解】（1）初始单纯形表见表4-9，最终单纯形表见表4-12满意解X(100/3，80/3)T，对应于图4-6点B不难看出有多重解，将d4进基x2出基，得到另一满意解X(60，0)T，对应于图4-6点C，见表4-134.3单纯形法SimplexMethod求满意解Cj00P100P1P2P20P3bCB基x1x2d1d1+d2d2+d3d3+d4d4+P1d1105114000d27811560P
23、2d322111200d412.511100CjZjP1 11P222P31表4-94.3单纯形法SimplexMethodCj00P100P1P2P20P3bCB基x1x2d1d1+d2d2+d3d3+d4d4+0 x111/21/101/10400d29/2-7/107/1011280P2d311/51/511400d42-1/101/101160CjZjP111P2-11/51/52P31表4-104.3单纯形法SimplexMethodCj00P100P1P2P20P3bCB基x1x2d1d1+d2d2+d3d3+d4d4+0 x115/405/401/41/4250d2-19/401
24、9/40119/49/4145P2d33/203/20111/21/2100 x211/201/201/21/230CjZjP11P23/203/2021/21/2P31表4114.3单纯形法SimplexMethodCj00P100P1P2P20P3bCB基x1x2d1d1+d2d2+d3d3+d4d4+0 x115/65/62/32/3100/30d21119/619/62/32/3340/30d1+1120/320/310/310/3200/30 x211/31/32/32/3CjZjP11P211P31表4-124.3单纯形法SimplexMethodCj00P100P1P2P20P3
25、bCB基x1x2d1d1+d2d2+d3d3+d4d4+0 x1111/21/2600d21117/27/21400d1+511552000d43/21/21/213/440CjZjP11P211P31表4134.3单纯形法SimplexMethod（2）将目标函数改写成以表4-12为基础，计算出检验数得到表4-14表4-14Cj00P1P1P300P20P4bCB基x1x2d1d1+d2d2+d3d3+d4d4+0 x115/65/62/32/3100/3P3d211-19/619/62/32/3340/3 P1d1+1120/3-20/3-10/310/3200/30 x211/31/32
26、/32/380/3CjZjP12-20/320/310/3-10/3P219/67/62/32/3P3119/61P414.3单纯形法SimplexMethodCj 00P1P1P300P20P4bCB基x1x2d1d1+d2d2+d3d3+d4d4+0 x111/81/81/41/425P3d219/4019/401-19/49/4145 0d33/203/201-11/21/2100 x211/201/201/21/230CjZjP111P21P319/4019/4019/49/4P41表4-154.3单纯形法SimplexMethodCj00P1P1P300P20P4bCB基x1x2d1
27、d1+d2d2+d3d3+d4d4+0 x111/51/51/21/220P3d21/51/5119/29/2100 P4d4+3/103/102211200 x211/51/51140CjZjP111P21P31/51/519/29/2P43/103/1021表4-16用单纯形法求解得到最终表4-16，满意解X(20，40)T，对应于图4-6中点A在（2）中如果按求解，单纯形法计算如表4-17所示4.3单纯形法SimplexMethod00P1P1P2002P20P3bx1x2d1d1+d2d2+d3d3+d4d4+x115/65/62/32/3100/3d21119/619/62/32/3
28、340/3d1+1120/320/310/310/3200/3x211/31/32/32/380/3P1220/320/310/310/3P219/67/632/2/3P311表4-17 转下表4.3单纯形法SimplexMethod00P1P1P2002P20P3bx1x2d1d1+d2d2+d3d3+d4d4+x118/458/451/91/980/9d3+2/452/452/92/911200/9d4+19/9019/904/94/911580/9x217/457/452/92/9560/9P111P24/454/455/94/92P319/9019/904/94/91最终表：4.3单纯形法SimplexMethod满意解X(80/9，560/9)T，d3+200/9而d20，与目标要求相悖，还可以从图4-6说明这个结果是错误的例4.7（2）是在原问题中作了部分变动后再求解，等价于第二章的灵敏度分析，求解原理基本相同4.2目标规划的图解法ThegraphicalmethodofGP目标规划的单纯形法与线性规划比较主要有两点不同。第一，目标规划是按优先次序顺序求解，逐个满足最优（检验数大于等于零）；第二，不一定所有检验数都能满足大于等于零，如果某个检验数小于零，所在列存在检验数大于零时，则认为得到满意解。计算方法和基本原理与线性规划类似。
