清华大学 运筹学 第四章《目标规划》课件.ppt

第1页,第一节目标规划的数学模型第二节目标规划的图解法第三节目标规划的单纯形法第五节目标规划的应用举例,第四章目标规划,引言,前面介绍的线性规划问题，研究的都是只有一个目标函数，若干个约束条件的最优决策问题然而现实生活中，衡量一个方案的好坏标准往往不止一个，而且这些标准之间往往不协调，甚至是相互冲突的例如，在资源的最优利用问题中，除了考虑所得的利润最大，还要考虑使生产的产品质量好，劳动生产率高，对市场的适应性强等等,目标规划正是在线性规划的基础上为适应这种复杂的多目标最优决策的需要，而发展起来的它对众多的目标分别确定一个希望实现的目标值，然后按目标的重要程度（级别）依次进行考虑与计算，以求得最接近各目标预定数值的方案,第一节：目标规划的数学模型,一、问题的提出,二、目标规划的基本概念,1决策变量与偏差变量,目标约束与绝对约束,目标规划的目标函数(达成函数),优先因子与权系数,三、目标规划的数学模型,建立目标规划模型的步骤,第5页,为了具体说明目标规划与线性规划在处理问题方法上的区别，首先通过例子来介绍目标规划的概念及数学模型。,一、目标规划问题的提出,第6页,例1：某工厂生产I、II两种产品，已知有关数据如下表所示。试求获利最大的生产方案。,第7页,解：设x1、x2分别表示产品I、II的产量，则建立问题的线性规划模型为：,用图解法求得最优决策方案为：x1=4，x2=3，z=62。,第8页,假设要求决策人员制定生产方案时考虑如下意见：1、由于产品I销售有下降趋势，故希望产品I的产量尽量不超过产品II的产量。2、超过计划供应的原材料时要高价采购，会使成本增加。3、尽可能充分利用设备台时，但不希望加班。4、尽可能达到并超过计划利润指标56元。,第9页,类似上述这样存在多个目标的多目标决策问题，称为目标规划问题。,对于多目标问题，线性规划很难为其找到最优方案极有可能出现：第一个方案使第一目标的结果优于第二方案，而对于第二目标，第二方案优于第一方案就是说很难找到一个方案使所有目标同时达到最优，特别当约束条件中有矛盾方程时，线性规划方法是无法解决的实践中，人们转而采取“不求最好，但求满意”的策略，在线性规划的基础上建立一种新的数学规划方法目标规划,第11页,1.偏差变量正偏差变量：表示决策值超过目标值的部分，记为d+；负偏差变量：表示决策值未达到目标值的部分，记为d-。,二.目标规划数学模型的基本概念,第12页,因为决策值不可能既超过目标值，同时又未达到目标值，所以d+和d-存在如下关系：（1）d+0，d-=0（决策值超过目标值）（2）d-0，d+=0（决策值未达到目标值）（3）d+=d-=0（决策值等于目标值）,第13页,2.绝对约束和目标约束（1）绝对约束：必须严格满足的约束条件。绝对约束是硬约束，不能满足这些约束条件的解为非可行解。如：线性规划问题中的所有约束条件都是绝对约束。,第14页,（2）目标约束：目标约束是目标规划特有的。目标约束是软约束，在达到此目标值时允许发生正偏差或负偏差，因此在这些约束的左端要加入正偏差、负偏差变量；其约束右端项是要追求的目标值。,目标规划问题的基本概念,对有严格限制的资源使用建立绝对约束，数学形式同线性规划中的约束条件,对不严格限制的资源，可通过目标约束来表达。,对于前例中的原材料，若用绝对约束则有：,若用目标约束则有：,第16页,3.优先因子(优先等级)和权系数一个规划问题常常有若干个目标，决策者要求达到这些目标时，有主次或轻重缓急的不同。这种不同目标的主次轻重差别有两种：绝对的差别：优先因子不同相对的差别：权系数不同,第17页,（1）优先因子优先因子用Pk来表示。只有在高级优先因子对应的目标已满足的基础上，才能考虑低级优先因子对应的目标；在考虑低级优先因子对应的目标时，绝对不允许违背已经满足的高级优先因子对应的目标。,第18页,优先因子间的关系为：PkPk+1Pk对应的目标比Pk+1对应的目标具有绝对的优先性.注意：目标规划问题中，通常把绝对约束作为最高优先级来考虑。,第19页,（2）权系数权系数用j来表示。多个目标具有相同的优先因子时，它们的重要性可用权系数的不同来表示。权系数的确定由决策者按具体情况而定。,第20页,4.目标规划的目标函数目标规划的目标函数又称为准则函数或达成函数。目标规划的目标函数由各目标约束的偏差变量、各目标约束相应的优先因子、各目标约束相应的权系数共同构成。,第21页,当每一目标值确定后，决策者要求尽可能缩小偏离目标值，所以目标规划的目标函数只能是极小化，其基本形式有三种：,第22页,（1）希望恰好达到目标值。这时，决策值超过目标值或不足目标值都是不希望的，即正、负偏差变量都要尽可能地小：,第23页,（2）希望不超过目标值。这时，允许达不到目标值，但不希望超过目标值，即正偏差变量要尽可能地小：,第24页,（3）希望不低于目标值。这时，允许超过目标值，但不希望低于目标值，即负偏差变量要尽可能地小：,第25页,三、目标规划的数学模型,例2：在例1中原材料供应受严格限制的基础上考虑：1.首先由于产品I销售疲软，故希望产品I的产量不超过产品II的产量；3.其次尽可能充分利用设备台时，但不加班4.再次利润额不小于56元。,第26页,原材料供应严格限制；,第27页,1.由于产品I销售疲软，故希望产品I的产量不超过产品II的产量；,第28页,2、尽可能充分利用设备台时，但不加班；,第29页,3.利润额不小于56元。,第30页,从而建立问题的模型如下：,第31页,模型亦可表述为：,32,练习：某企业生产甲、乙两种产品，数据见下表：,33,例2：某企业生产甲、乙两种产品，数据见下表：,34,解：设生产甲、乙产品各,第35页,目标规划的一般数学模型为：,建立目标规划模型的步骤,1）列出全部的约束条件,2）把要达到指标的约束不等式加上正、负偏差变量后化为目标约束等式,3）对目标赋予相应的优先因子,4）对同一级优先因子中的各偏差变量，若重要程度不同时，可赋予不同的加权系数,5）构造一个按优先因子及加权系数和对应的目标偏差变量所要实现最小化的目标函数,第37页,第二节解目标规划的图解法,对于具有两个决策变量的目标规划的数学模型可以用图解法来分析求解。,一、图解法的步骤,1.在平面直角坐标系内画出由绝对约束和非负条件所组成的公共取值范围。,第38页,2.按优先因子的高低，依次在平面直角坐标系内画出目标约束所组成的公共取值范围：（1）令正负偏差变量等于0，画出所有的约束直线；（2）在直线旁标出正、负偏差变量所示方向。（3）正负偏差变量表示直线可以沿正、负偏差变量所示方向平移。3.根据目标函数中的优先因子来分析求解。,第39页,二、最终解是最优解的情况,第40页,解：,x2,x1,1.画出绝对约束和非负条件所围成的取值范围。,O,A,B,第41页,2.画出目标约束所围成的取值范围。,x2轴上的截距,第42页,x2,x1,O,B,A,C,偏差变量在画直线取为0，直线画好后，在该直线上标出目标函数中与该直线相关的偏差变量增大时直线的平移方向（用垂直于直线的箭头来反映）,第43页,x2轴上的截距,第44页,x2,x1,O,A,B,E,C,D,第45页,x2轴上的截距,第46页,x2,x1,O,B,A,C,E,D,F,G,J,第47页,3.根据目标函数中的优先因子来分析求解。,表示直线左上角的部分，此时满足,从而公共取值范围为：OBC,（1）,第48页,x2,x1,O,B,A,C,E,D,F,G,J,第49页,表示直线上的部分，此时满足,从而公共取值范围为：线段ED,（2）,第50页,x2,x1,O,B,A,C,E,D,F,G,J,第51页,（3）,表示直线的右上角部分，此时满足,从而公共取值范围为：线段GD,第52页,x2,x1,O,B,A,C,E,D,F,G,J,第53页,可求得：G的坐标为：（2，4）D的坐标为：（10/3，10/3）G和D的凸组合均是目标规划问题的解。,第54页,在本例中，依次先后次序满足了：,因而z*=0，问题的最终解是最优解。,但在大多数问题中并非如此，会出现某些约束得不到满足，故将目标规划问题的最优解称为满意解。,目标规划图解法的具体演算过程,第1步：由决策变量绘画所有约束条件的直线图形，偏差变量以平移直线的方法加以考虑,第5步：重复第3、4步过程，直到解区域Ri减少到一点或满足了所有k个级别的目标为止，此时Rk即为最优解区域，其中的任何一点均为目标规划满意解,第2步：对P1级的各目标，确定解区域R1,第3步：对下一个优先级别Pi级各目标，确定它的最优解空间Ri，但必须是RiRi-1(i=2,3,),第4步：在这个过程中，如果某解区域Ri减小到一点，则结束，因为此时没有进一步改进的可能,第57页,例3：某电视机厂装配黑白和彩色两种电视机。每周市场的黑白电视机销量为30台，每台可获利40元；每周市场的彩色电视机销量为24台，每台可获利80元。每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。,三、最终解是满意解的情况,第58页,该厂确定的目标为：第一优先级：充分利用装配线每周计划开动时间40小时；第二优先级：允许装配线加班，但加班时间每周尽量不超过10小时；第三优先级：装配电视机数量尽量满足市场需求量。因彩色电视机利润高，取其权系数为2。建立问题模型，并求解黑白和彩色电机机产量？,第59页,1.充分利用装配线每周计划开动时间40小时：,解：,设x1、x2分别表示彩色和黑白电视机产量。,第60页,2.允许装配线加班，但加班时间每周尽量不超过10小时：,第61页,3.装配彩色电视机数量尽量满足市场需求量，且权系数为2：,第62页,4.装配黑白电视机数量尽量满足市场需求量，且权系数为1：,第63页,从而建立问题的模型如下：,第64页,x2,x1,第65页,x2,x1,第66页,x2,x1,第67页,在ABEF中无法满足：,所以只能在ABEF中取一点，使尽可能小。,在ABEF中只有取E点才可使最小。,故E点为为满意解，E=（24，26）。,第68页,x2,x1,第69页,分析：此例中约束,没有得到满足。,问题的最终解只是满意解而不是最优解。,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,第87页,目标规划的灵敏度分析方法与线性规划相似，除了分析各项系数的变化之外，还有优先因子和权系数的变化问题。,第五节目标规划的灵敏度分析,第88页,一、右端常数的影响分析,例：已知目标规划问题,第89页,最终单纯形表为,第90页,若第一个目标约束的右端项变为120，原满意解发生什么样的变化？,第91页,解：,第92页,将其反映到最终单纯形表中：,第93页,即出现了第三种情况（原问题不可行，对偶问题可行），利用对偶单纯形法求解：,第94页,第95页,第96页,第97页,得到问题的满意解为：,第98页,二、优先因子位置变化的影响分析,例：已知目标规划问题,第99页,最终单纯形表为,第100页,求：目标函数变为,后问题的满意解。,解：,第101页,目标函数的变化仅影响各变量的检验数。因此，只需考察检验数的变化即可。分析：变化后的目标函数只是将原目标函数的P3和P4优先因子顺序改变了一下。处理方法：将原目标规划的最终单纯形表的目标函数行（cj行）做出相应调整，并重新计算检验数。,第102页,最终单纯形表转变为,第103页,换入，换出，得到新的单纯形表：,第104页,得到问题的满意解为：,第105页,三、权系数变化的影响分析,例：已知目标规划问题,第106页,最终单纯形表为,第107页,求：目标函数变为,后问题的满意解。,解：,第108页,目标函数的变化仅影响各变量的检验数。因此，只需考察检验数的变化即可。分析：变化后的目标函数只是将原目标函数的P3优先因子中两目标的权系数改变了一下。处理方法：将原目标规划的最终单纯形表的目标函数行（cj行）做出相应调整，并重新计算检验数。,第109页,最终单纯形表为,第110页,分析：,：原解不变。,：利用单纯形法继续求解。,第5节应用举例,例6:某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：(1)不超过年工资总额60000元；(2)每级的人数不超过定编规定的人数；(3)，级的升级面尽可能达到现有人数的20%，且无越级提升；(4)级不足编制的人数可录用新职工，又级的职工中有10%要退休。,有关资料汇总于表中，问该领导应如何拟订一个满意的方案。,解：设x1、x2、x3分别表示提升到、级和录用到级的新职工人数。对各目标确定的优先因子为：P1不超过年工资总额60000元；P2每级的人数不超过定编规定的人数；P3、级的升级面尽可能达到现有人数的20%。,先分别建立各目标约束,2000(10-100.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+d-1-d1+=60000,2、每级的人数不超过定编规定的人数对级有10-100.1+x1+d2-_d2+=12对级有12-x1+x2+d3-_d3+=15对级有15-x2+x3+d4-_d4+=153、，级的升级面尽可能达到现有人数的20%对级有x1+d5-_d5+=120.2对级有x2+d6-_d6+=150.2目标函数：minz=P1d1+P2(d2+d3+d4+)+P3(d5-+d6-),1、年工资总额不超过60000元,以上目标规划模型可用单纯形法求解，可得到多重解。现将这些解汇总于表4-9，这单位的领导再按具体情况，从表4-9中选一个执行方案,第116页