数学Ch目标规划课件

Chapter4目标规划GoalProgramming

运筹学OperationsResearch4.1

目标规划数学模型

MathematicalModelofGP4.2

目标规划的图解法ThegraphicalmethodofGP4.3

SimplexMethod7/26/20234.1目标规划数学模型MathematicalModelofGP7/26/2023线性规划模型的特征是在满足一组约束条件下，寻求一个目标的最优解（最大值或最小值）。

而在现实生活中最优只是相对的，或者说没有绝对意义下的最优，只有相对意义下的满意。

1978年诺贝尔经济学奖获得者.西蒙(H.A.Simon-美国卡内基-梅隆大学,1916-)教授提出“满意行为模型要比最大化行为模型丰富得多”，否定了企业的决策者是“经济人”概念和“最大化”行为准则，提出了“管理人”的概念和“令人满意”的行为准则，对现代企业管理的决策科学进行了开创性的研究

4.1目标规划的数学模型MathematicalModelofGP7/26/2023【例4-1】某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源、每件产品利润如表4－1所示。已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤；假定市场需求无限制。使企业在计划期内总利润最大的线性规划模型为：产品

资源甲乙丙现有资源设备A312200设备B224200材料C451360材料D235300利润（元/件）403050表4-14.1.1引例4.1目标规划的数学模型MathematicalModelofGP7/26/2023最优解X＝（50，30，10），Z＝34004.1目标规划的数学模型MathematicalModelofGP7/26/2023

现在决策者根据企业的实际情况和市场需求，需要重新制定经营目标，其目标的优先顺序是：（1）利润不少于3200元（2）产品甲与产品乙的产量比例尽量不超过1.5（3）提高产品丙的产量使之达到30件（4）设备加工能力不足可以加班解决，能不加班最好不加班（5）受到资金的限制，只能使用现有材料不能再购进问企业如何安排生产计划才能到达经营目标。【解】设甲、乙、丙产品的产量分别为x1、x2、x3。如果按线性规划建模思路，最优解实质是求下列一组不等式的解4.1目标规划的数学模型MathematicalModelofGP7/26/2023通过计算不等式无解，即使设备加班10小时仍然无解．在实际生产过程中生产方案总是存在的，无解只能说明在现有资源条件下，不可能完全满足所有经营目标．目标规划是按事先制定的目标顺序逐项检查，尽可能使得结果达到预定目标，即使不能达到目标也使得离目标的差距最小，这就是目标规划的求解思路，对应的解称为满意解．下面建立例4-1的目标规划数学模型．4.1目标规划的数学模型MathematicalModelofGP7/26/2023设d－为未达到目标值的差值，称为负偏差变量（negativedeviationvariable）d+为超过目标值的差值，称为正偏差变量（positivedeviationvariable）,d－≥0、d＋≥0．设d1－未达到利润目标的差值,d1+为超过目标的差值当利润小于3200时,d1－＞０且d1＋＝0,有40x1+30x2+50x3+d1－=3200成立当利润大于3200时，d1＋＞０且d1－＝０，有40x1+30x2+50x3-d1+=3200成立当利润恰好等于3200时，d1－=０且d1+=0,有40x1+30x2+50x3=3200成立实际利润只有上述三种情形之一发生，因而可以将三个等式写成一个等式40x1+30x2+50x3+d1－－d1+=32004.1目标规划的数学模型MathematicalModelofGP7/26/2023（2）设分别为未达到和超过产品比例要求的偏差变量,则产量比例尽量不超过1.5的数学表达式为：

（3）设d3ˉ、d３＋分别为品丙的产量未达到和超过30件的偏差变量，则产量丙的产量尽可能达到30件的数学表达式为：利润不少于3200理解为达到或超过3200，即使不能达到也要尽可能接近3200,可以表达成目标函数｛d1－｝取最小值，则有4.1目标规划的数学模型MathematicalModelofGP7/26/2023（4）

设d4ˉ

、d4+为设备A的使用时间偏差变量,d5ˉ、d5+为设备B的使用时间偏差变量，最好不加班的含义是d4+和d5+同时取最小值，等价于d4++d5+取最小值，则设备的目标函数和约束为：（5）材料不能购进表示不允许有正偏差，约束条件为小于等于约束．由于目标是有序的并且四个目标函数非负，因此目标函数可以表达成一个函数：4.1目标规划的数学模型MathematicalModelofGP7/26/2023式中：Pj（j=1,2,3,4）称为目标的优先因子，第一目标优于第二目标，第二目标优于第三目标等等，其含义是按P1、P2、…的次序分别求后面函数的最小值.则问题的目标规划数学模型为：4.1目标规划的数学模型MathematicalModelofGP7/26/2023约束实际偏差目标1C13220=32002C2－2=03C330=304C4164=2005C5216=2006C6242－118<=3607C7266－34<=3001X1282X2203X3304d1-05d1+206d2-27d2+08d3-09d3+010d4-3611d4+012d5-013d5+16满意解：约束分析：4.1目标规划的数学模型MathematicalModelofGP7/26/2023（1）目标规划数学模型的形式有：线性模型、非线性模型、整数模型、交互作用模型等（2）一个目标中的两个偏差变量di-、di+至少一个等于零，偏差变量向量的叉积等于零：d－×d＋=0（3）一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值，按多个目标的重要性，确定优先等级，顺序求最小值（4）按决策者的意愿，事先给定所要达到的目标值当期望结果不超过目标值时，目标函数求正偏差变量最小;当期望结果不低于目标值时，目标函数求负偏差变量最小;当期望结果恰好等于目标值时，目标函数求正负偏差变量之和最小。4.1.2数学模型4.1目标规划的数学模型MathematicalModelofGP7/26/2023（5）由目标构成的约束称为目标约束，目标约束具有更大的弹性，允许结果与所制定的目标值存在正或负的偏差，如例4-1中的5个等式约束；如果决策者要求结果一定不能有正或负的偏差，这种约束称为系统约束，如例4-1的材料约束；（6）目标的排序问题。多个目标之间有相互冲突时，决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方法，构造各目标的权系数，依据权系数的大小确定目标顺序；（7）合理的确定目标数。目标规划的目标函数中包含了多个目标，决策者对于具有相同重要性的目标可以合并为一个目标，如果同一目标中还想分出先后次序，可以赋予不同的权系数，按系数大小再排序。例如，在例4-1中要求设备B的加班时间不超过设备A的时间，目标函数可以表达为,表示尽可能优先设备A加班。如果要求设备B的加班时间是设备A的时间的二分之一，则令w4=1，w5=2。

4.1目标规划的数学模型MathematicalModelofGP7/26/2023（8）多目标决策问题．多目标决策研究的范围比较广泛，在决策中，可能同时要求多个目标达到最优．例如，企业在对多个项目投资时期望收益率尽可能最大，投资风险尽可能最小，属于多目标决策问题，本章的目标规划尽管包含有多个目标，但还是按单个目标求偏差变量的最小值，目标函数中不含有决策变量，目标规划只是多目标决策的一种特殊情形．本章不讨论多目标规划的求解方法，只给出WinQSB软件求解线性多目标规划的操作步骤，参看例4-3和例4-9．4.1目标规划的数学模型MathematicalModelofGP7/26/2023（9）目标规划的一般模型．设xj（j=1,2,…,n）为决策变量4.1目标规划的数学模型MathematicalModelofGP

式中pk为第k级优先因子,k=1、2、……K；wkl-、wkl+，为分别赋予第l个目标约束的正负偏差变量的权系数；gl为目标的预期目标值，l=1,…L．(4-1b)为系统约束,（4-1c）为目标约束7/26/2023【例4-2】某企业集团计划用1000万元对下属5个企业进行技术改造，各企业单位的投资额已知，考虑2种市场需求变化、现有竞争对手、替代品的威胁等影响收益的4个因素，技术改造完成后预测单位投资收益率(（单位投资获得利润/单位投资额）×100％)如表4－2所示．4.1目标规划的数学模型MathematicalModelofGP集团制定的目标是：（1）希望完成总投资额又不超过预算；（2）总期望收益率达到总投资的30%；（3）投资风险尽可能最小；（4）保证企业5的投资额占20%左右．集团应如何作出投资决策．7/26/2023企业1企业2企业3企业4企业5单位投资额(万元)1210151320单位投资收益率预测rij市场需求14.3255.845.26.56市场需求23.523.045.084.26.24现有竞争对手3.162.23.563.284.08替代品的威胁2.243.122.62.23.24期望(平均)收益率％3.313.344.273.725.03表4－24.1目标规划的数学模型MathematicalModelofGP7/26/2023【解】设xj（j=1,2,…,5）为集团对第j个企业投资的单位数．

（1）总投资约束：4.1目标规划的数学模型MathematicalModelofGP（2）期望利润率约束：整理得7/26/2023

（4）企业5占20%的投资的目标函数为,约束条件即4.1目标规划的数学模型MathematicalModelofGP(3）投资风险约束．投资风险值的大小一般用期望收益率的方差表示，但方差是x的非线性函数．这里用离差（rij－E(rj)）近似表示风险值，例如，集团投资5个企业后对于市场需求变化第一情形的风险是：则4种因素风险最小的目标函数为：，约束条件为7/26/20234.1目标规划的数学模型MathematicalModelofGP根据目标重要性依次写出目标函数，整理后得到投资决策的目标规划数学模型：7/26/2023

x1x2x3x4x5合计满意解(投资单位)3050

7

投资额360500

1401000收益99.3167

35.21301.514.1目标规划的数学模型MathematicalModelofGP用WinQSB软件求非负整数解得到下表结果。求解过程参看教材例4-8。7/26/2023【例4-3】车间计划生产I、II两种产品，每种产品均需经过A、B两道工序加工．工艺资料如表4－3所示．产品工序产品甲产品乙每天加工能力(小时)A22120B12100C2.20.890产品售价(元/件)5070产品利润(元/件)108（1）车间如何安排生产计划，使产值和利润都尽可能高（2）如果认为利润比产值重要，怎样决策表4－34.1目标规划的数学模型MathematicalModelofGP7/26/2023【解】设x1、x2分别为产品甲和产品乙的日产量，得到线性多目标规划模型：4.1目标规划的数学模型MathematicalModelofGP7/26/2023（1）将模型化为目标规划问题．首先，通过分别求产值最大和利润最大的线性规划最优解．产值最大的最优解：X(1)＝（20，40），Z1＝3800利润最大的最优解：X(2)＝（30，30），Z2＝540目标确定为产值和利润尽可能达到3800和540，得到目标规划数学模型：4.1目标规划的数学模型MathematicalModelofGP7/26/2023．4.1目标规划的数学模型MathematicalModelofGP（2）给d2-赋予一个比d1-的系数大的权系数,如，约束条件不变.权系数的大小依据重要程度给定，或者根据同一优先级的偏差变量的关系给定，例如，当利润d2-减少一个单位时，产值d1-减少3个单位，则赋予d2-权系数3，则目标函数为7/26/2023本节介绍了如何建立目标规划的数学模型及有关概念1.目标规划由哪些要素构成，与线性规划有哪些不同之处2.偏差变量的含义及其作用3.目标函数的表达方法4.优先级别的含义4.1目标规划的数学模型MathematicalModelofGP作业:教材习题4.1，4.2，4.4下一节：目标规划的图解法7/26/20234.2目标规划的图解法ThegraphicalmethodofGP7/26/20234.2目标规划的图解法ThegraphicalmethodofGP当目标规划模型中只含两个决策变量（不包含偏差变量）时，可以用图解法求出满意解．【例4-4】企业计划生产I

、II两种产品，这些产品需要使用两种材料，要在两种不同设备上加工．工艺资料如表4－4所示．产品资源产品甲产品乙现有资源材料I3012(kg)材料II0414(kg)设备A2212(h)设备B5315(h)产品利润(元/件)2040表4－47/26/2023【解】设x1、x2分别为产品甲和产品乙的产量，目标规划数学模型为：企业怎样安排生产计划，尽可能满足下列目标：(1)力求使利润指标不低于80元(2)考虑到市场需求,Ｉ、II两种产品的生产量需保持1:1的比例(3)设备A既要求充分利用，又尽可能不加班(4)设备B必要时可以加班，但加班时间尽可能少(5)材料不能超用。4.2目标规划的图解法ThegraphicalmethodofGP7/26/2023(2)(1)(3)(4

)x2x1(6)(5)o464622图4－1ABC满意解C(3,3)满意解X＝(3,3)7/26/2023(3)x1x22040608010020406080100(2)(1)(4)图4－2BC满意解是线段上任意点，端点的解是B(100/3，80/3)，C(60，0)．决策者根据实际情形进行二次选择．A例4-5（1）7/26/2023(3)x1x22040608010020406080100(2)(1)(4)图4－3满意解是点D，X=(80/9，560/9)A(20,40)D(80/9,560/9)注：线段DA是第二目标函数的组合，点A对应的偏差：d2-=100,d3＋=0点D对应的偏差：d2-=0,2d3＋=2×200/9=400/9例4-5（2）7/26/2023(3)x1x22040608010020406080100(2)(1)(4)图4－4BC满意解是点B，X=(100/3，80/3)A例4-5（3）7/26/2023本节介绍了目标规划的图解法1.画出系统约束和目标约束直线2.标明偏差变量大于零的变量X的取值区域3.按优先次序分别求各目标的最小值4.仔细体会例4-5（2）的计算要领作业:教材习题4.3下一节：单纯形法4.2目标规划的图解法ThegraphicalmethodofGP7/26/20234.3单纯形法SimplexMethod7/26/2023单纯形法求解目标规划可参照第一章的步骤，只是目标规划的检验要按优先级顺序逐级进行，不同的是：（1）首先使得检验数中P1的系数非负，再使得P2的系数非负，依次进行；（2）当P1、P2、…、Pk对应的系数全部非负时得到满意解；（3）如果P1，…，Pi行系数非负，而Pi+1行存在负数，并且负数所在列上面P1，…，Pi行中存在正数时，得到满意解，计算结束．4.3单纯形法SimplexMethod7/26/2023【例4-6】用单纯形法求解下述目标规划问题【解】以d1－、d2－、d3－为基变量，求出检验数，将检验数中优先因子分离出来，每一优先级做一行，列出初始单纯形表4-5．4.3单纯形法SimplexMethod7/26/2023Cj00P100P1P20bCB基x1x2d1－d1+d2－d2+d3－d3+P1d1－1[2]1－150→0d2－211－140P2d3－221－180Cj－ZjP1－1－211P2－2－21表4－54.3单纯形法SimplexMethod7/26/2023表4－5中，P1行中(－2)最小，则x2进基，求最小比值易知d1－出基，将第二列主元素化为1，其余元素化为零，得到表4-6．Cj00P100P1P20bCB基x1x2d1－d1+d2－d2+d3－d3+0x21/211/2－1/2250d2－[3/2]1/21－115→P2d3－111－130Cj－ZjP111P2－11－11表4－64.3单纯形法SimplexMethod7/26/2023表4-6中P1行全部检验数非负，表明第一目标已经得到优化．P2行存在负数，x1的检验数为－P2<0，选x1进基（也可以选d1+进基），则d3－出基，迭代得到表4-7．Cj00P100P1P20bCB基x1x2d1－d1+d2－d2+d3－d3+0x212/3－2/31/3200x11[1/3]2/310→P2d3－2/32/31－120Cj－ZjP111P22/3-2/32/3-2/314.3单纯形法SimplexMethod

表4-7在表4-7中，P1行的系数全部非负，P2行存在负数，d1+的检验数－2/3P2<0，选d1+进基，则x1出基，迭代得到表4-8．应当注意，表4-7中不能选d2+进基，检验数P1－2/3P2应理解为“大于零”，P1、P2是优先级别的比较，而不是“数”的比较．例如，－3P2+5P3理解为小于零，2P2－4P4理解为大于零等等．7/26/2023Cj→00P100P1P20bCB基x1x2d1－d1+d2－d2+d3－d3+0x2211－1400d1+3－112－230P2d3－－2－221－10Cj－ZjP111P222－21表4－84.3单纯形法SimplexMethod表4-8中P2行的（－2）小于零，但（－2）列上面P1行存在正数1，检验数P1－2P2>0,所有检验数非负，得到满意解X＝（0，40）7/26/2023【例4-7】用单纯形法求解例4-5(1)、4-5(2)【解】（1）4.3单纯形法SimplexMethod初始单纯形表见表4-9，最终单纯形表见表4-12．满意解X＝(100/3，80/3)T，对应于图4-2点B(教材图4-6）．不难看出有多重解，将d4－进基x2出基，得到另一满意解X＝(60，0)T，对应于图4-2点C，见表4-137/26/2023Cj00P100P1P2P20P3bCB基x1x2d1－d1+d2－d2+d3－d3+d4－d4+P1d1－[10]51－1400→0d2－781－1560P2d3－221－11200d4－12.51－1100Cj－ZjP1－10－511P2－2－22P31表4-94.3单纯形法SimplexMethod7/26/2023Cj00P100P1P2P20P3bCB基x1x2d1－d1+d2－d2+d3－d3+d4－d4+0x111/21/10－1/10400d2－9/2-7/107/101－1280P2d3－1－1/51/51－1400d4－[2]-1/101/101－160→Cj－ZjP111P2-1↑1/5－1/52P31表4-104.3单纯形法SimplexMethod7/26/2023Cj00P100P1P2P20P3bCB基x1x2d1－d1+d2－d2+d3－d3+d4－d4+0x115/40－5/40－1/41/4250d2－-19/4019/401－1－9/49/4145P2d3－－3/20[3/20]1－1－1/21/210→0x21－1/201/201/2－1/230Cj－ZjP11P23/20－3/20↑21/2－1/2P31表4－114.3单纯形法SimplexMethod7/26/2023Cj00P100P1P2P20P3bCB基x1x2d1－d1+d2－d2+d3－d3+d4－d4+0x115/6－5/6－2/32/3100/30d2－1－1－19/619/6－2/32/3340/30d1+－1120/3－20/3－10/310/3200/3→0x21－1/31/3[2/3]－2/380/3Cj－ZjP11P211P31表4-124.3单纯形法SimplexMethod7/26/2023Cj00P100P1P2P20P3bCB基x1x2d1－d1+d2－d2+d3－d3+d4－d4+0x1111/2－1/2600d2－11－1－7/27/21400d1+5－115－52000d4－3/2－1/21/21－3/440Cj－ZjP11P211P31表4－134.3单纯形法SimplexMethod7/26/202300P1P1P2002P20P3bx1x2d1－d1+d2－d2+d3－d3+d4－d4+x115/6－5/6－2/32/3100/3d21－1－19/619/6－2/32/3340/3d1+－1120/3－20/3－10/3[10/3]200/3→x21－1/31/32/3－2/380/3P12－20/320/310/3－10/3↑P219/6－7/632/－2/3P311表4-14转下表4.3单纯形法SimplexMethod等价于第2章灵敏度分析，在表4-12中求新的检验数，其它数据不变，单纯形法计算如表4-14所示（2）目标函数变为7/26/202300P1P1P2002P20P3bx1x2d1－d1+d2－d2+d3－d3+d4－d4+x118/45－8/45－1/91/980/9d3+2/45－2/452/9－2/9－11200/9d4+－19/9019/904/9－4/9－11580/9x21－7/457/452/9－2/9560/9P111P2－4/454/455/94/92P319/90－19/90－4/94/91最终表：满意解X＝(80/9，560/9)T，d3+＝200/9而d2－＝0，d4+＝580/9，Z=108.887/26/2023如果将目标函数改写成以表4-12为基础，计算过程见表4-15表4-15Cj00P1P1P300P20P4bCB基x1x2d1－d1+d2－d2+d3－d3+d4－d4+0x115/6－5/6－2/32/310