运筹学-3、目标规划

运筹学运筹学OperationsResearchChapter4目标规划GoalProgramming运筹学OperationsResearch4.1目标规划数学模型MathematicalModelofGP4.2目标规划的图解法ThegraphicalmethodofGP4.3单纯形法SimplexMethod4.1目标规划数学模型MathematicalModelofGP线性规划模型的特征是在满足一组约束条件下，寻求一个目标的最优解（最大值或最小值）。而在现实生活中最优只是相对的，或者说没有绝对意义下的最优，只有相对意义下的满意。1978年诺贝尔经济学奖获得者.西蒙(H.A.Simon-美国卡内基-梅隆大学,1916-)教授提出“满意行为模型要比最大化行为模型丰富得多”，否定了企业的决策者是“经济人”概念和“最大化”行为准则，提出了“管理人”的概念和“令人满意”的行为准则，对现代企业管理的决策科学进行了开创性的研究4.1目标规划的数学模型MathematicalModelofGP【例4.１】考虑例1.1．资源消耗如表4-1所示。x1、x2、x3分别为甲、乙、丙的产量。使企业在计划期内总利润最大的线性规划模型为：产品资源甲乙丙现有资源设备A312200设备B224200材料C451360材料D235300利润（元/件）403050表4-14.1.1引例4.1目标规划的数学模型MathematicalModelofGP321503040maxxxxZ0003005323605420042220023321321321321321xxxxxxxxxxxxxxx，，最优解X＝（50，30，10），Z＝34004.1目标规划的数学模型MathematicalModelofGP现在决策者根据企业的实际情况和市场需求，需要重新制定经营目标，其目标的优先顺序是：（1）利润不少于3200元（2）产品甲与产品乙的产量比例尽量不超过1.5（3）提高产品丙的产量使之达到30件（4）设备加工能力不足可以加班解决，能不加班最好不加班（5）受到资金的限制，只能使用现有材料不能再购进【解】设甲、乙、丙产品的产量分别为x1、x2、x3。如果按线性规划建模思路，最优解实质是求下列一组不等式的解4.1目标规划的数学模型MathematicalModelofGP00030053236054200422200233005.13200503040321321321321321321321xxxxxxxxxxxxxxxxxxxxx，，－通过计算不等式无解，即使设备加班10小时仍然无解．在实际生产过程中生产方案总是存在的，无解只能说明在现有资源条件下，不可能完全满足所有经营目标．这种情形是按事先制定的目标顺序逐项检查，尽可能使得结果达到预定目标，即使不能达到目标也使得离目标的差距最小，这就是目标规划的求解思路，对应的解称为满意解．下面建立例4.1的目标规划数学模型．4.1目标规划的数学模型MathematicalModelofGP设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目标规划的数学模型MathematicalModelofGP3200503040min113211ddxxxd（2）设分别为未达到和超过产品比例要求的偏差变量,则产量比例尽量不超过1.5的数学表达式为：22dd、05.1min22212ddxxd（3）设d3ˉ、d３＋分别为品丙的产量未达到和超过30件的偏差变量，则产量丙的产量尽可能达到30件的数学表达式为：30min3333ddxd利润不少于3200理解为达到或超过3200，即使不能达到也要尽可能接近3200,可以表达成目标函数｛d1－｝取最小值，则有4.1目标规划的数学模型MathematicalModelofGP（4）设d4ˉ、d4+为设备A的使用时间偏差变量,d5ˉ、d5+为设备B的使用时间偏差变量，最好不加班的含义是d4+和d5+同时取最小值，等价于d4++d5+取最小值，则设备的目标函数和约束为：20042220023min553214432154ddxxxddxxxdd（5）材料不能购进表示不允许有正偏差，约束条件为小于等于约束．由于目标是有序的并且四个目标函数非负，因此目标函数可以表达成一个函数：4.1目标规划的数学模型MathematicalModelofGP)(min544332211ddPdPdPdPz式中：Pj（j=1,2,3,4）称为目标的优先因子，第一目标优于第二目标，第二目标优于第三目标等等，其含义是按P1、P2、…的次序分别求后面函数的最小值.则问题的目标规划数学模型为：5,2,1,0,0,0,030053236054200422200233005.13200503040)(min3213213215532144321333222111321544332211jddxxxxxxxxxddxxxddxxxddxddxxddxxxddPdPdPdPzjj、且为整数－4.1目标规划的数学模型MathematicalModelofGP约束实际偏差目标1C13220=32002C2－2=03C330=304C4164=2005C5216=2006C6242－118=3607C7266－34=3001X1282X2203X3304d1-05d1+206d2-27d2+08d3-09d3+010d4-3611d4+012d5-013d5+16满意解：约束分析：4.1目标规划的数学模型MathematicalModelofGP120d22d436d516d（1）目标规划数学模型的形式有：线性模型、非线性模型、整数模型、交互作用模型等（2）一个目标中的两个偏差变量di-、di+至少一个等于零，偏差变量向量的叉积等于零：d－×d＋=0（3）一般目标规划是将多个目标函数写成一个由偏差变量构成的函数求最小值，按多个目标的重要性，确定优先等级，顺序求最小值（4）按决策者的意愿，事先给定所要达到的目标值当期望结果不超过目标值时，目标函数求正偏差变量最小;当期望结果不低于目标值时，目标函数求负偏差变量最小;当期望结果恰好等于目标值时，目标函数求正负偏差变量之和最小4.1.2数学模型4.1目标规划的数学模型MathematicalModelofGP（5）由目标构成的约束称为目标约束，目标约束具有更大的弹性，允许结果与所制定的目标值存在正或负的偏差，如例4.1中的5个等式约束；如果决策者要求结果一定不能有正或负的偏差，这种约束称为系统约束，如例4.1的材料约束；（6）目标的排序问题。多个目标之间有相互冲突时，决策者首先必须对目标排序。排序的方法有两两比较法、专家评分等方法，构造各目标的权系数，依据权系数的大小确定目标顺序；（7）合理的确定目标数。目标规划的目标函数中包含了多个目标，决策者对于具有相同重要性的目标可以合并为一个目标，如果同一目标中还想分出先后次序，可以赋予不同的权系数，按系数大小再排序。例如，在例4.1中要求设备B的加班时间不超过设备A的时间，目标函数可以表达为,表示在中先求最小再求最小。542dd54dd、5d4d4.1目标规划的数学模型MathematicalModelofGP（8）多目标决策问题．多目标决策研究的范围比较广泛，在决策中，可能同时要求多个目标达到最优．例如，企业在对多个项目投资时期望收益率尽可能最大，投资风险尽可能最小，属于多目标决策问题，本章的目标规划尽管包含有多个目标，但还是按单个目标求偏差变量的最小值，目标函数中不含有决策变量，目标规划只是多目标决策的一种特殊情形．本章不讨论多目标规划的求解方法，只给出WinQSB软件求解线性多目标规划的操作步骤，参看例4.3和4.9．4.1目标规划的数学模型MathematicalModelofGP（9）目标规划的一般模型．设xj（j=1,2,…,n）为决策变量)1.4(),,1(0,)1.4(),,1(0)1.4(),,1()1.4(),,1(),()1.4()(min1111eLldddnjxcLlgddxcbmibxaadwdwPzlljnjllljljnjijijLllkllklKkk4.1目标规划的数学模型MathematicalModelofGP式中pk为第k级优先因子,k=1、2、……K；wkl-、wkl+，为分别赋予第l个目标约束的正负偏差变量的权系数；gl为目标的预期目标值，l=1,…L．(4.1b)为系统约束,（4.1c）为目标约束【例4.2】某企业集团计划用1000万元对下属5个企业进行技术改造，各企业单位的投资额已知，考虑2种市场需求变化、现有竞争对手、替代品的威胁等影响收益的4个因素，技术改造完成后预测单位投资收益率(（单位投资获得利润/单位投资额）×100％)如表4－2所示．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.162.23.563.284.08替代品的威胁2.243.122.62.23.24期望(平均)收益率％3.313.344.273.725.03表4－24.1目标规划的数学模型MathematicalModelofGP【解】设xj（j=1,2,…,5）为集团对第j个企业投资的单位数．100020131510121154321ddxxxxx（1）总投资约束：4.1目标规划的数学模型MathematicalModelofGP（2）期望利润率约束：)2013151012(3.003.572.327.434.331.3543212254321xxxxxddxxxxx整理得097.018.023.034.029.02254321＝ddxxxxx079.152.167.122.007.1095.044.071.014.115.0021.148.081.03.021.0053.148.157.166.101.16654321555432144543213354321ddxxxxxddxxxxxddxxxxxddxxxxx（4）企业5占20%的投资的目标函数为,约束条件