清华大学-运筹学-第四章目标规划课件

引言前面介绍的线性规划问题，研究的都是只有一个目标函数，若干个约束条件的最优决策问题．然而现实生活中，衡量一个方案的好坏标准往往不止一个，而且这些标准之间往往不协调，甚至是相互冲突的．例如，在资源的最优利用问题中，除了考虑所得的利润最大，还要考虑使生产的产品质量好，劳动生产率高，对市场的适应性强等等．引言前面介绍的线性规划问题，研究的都是只有

目标规划正是在线性规划的基础上为适应这种复杂的多目标最优决策的需要，而发展起来的．它对众多的目标分别确定一个希望实现的目标值，然后按目标的重要程度（级别）依次进行考虑与计算，以求得最接近各目标预定数值的方案．目标规划正是在线性规划的基础上为适应这种复杂的多第一节：目标规划的数学模型一、问题的提出二、目标规划的基本概念1．决策变量与偏差变量

２．目标约束与绝对约束３．目标规划的目标函数(达成函数)４．优先因子与权系数三、目标规划的数学模型建立目标规划模型的步骤第一节：目标规划的数学模型一、问题的提出二、目标规划的基本概为了具体说明目标规划与线性规划在处理问题方法上的区别，首先通过例子来介绍目标规划的概念及数学模型。一、目标规划问题的提出4为了具体说明目标规划与线性规划在处理问题方法例1：某工厂生产I、II两种产品，已知有关数据如下表所示。试求获利最大的生产方案。5例1：某工厂生产I、II两种产品，已知有关数据如下表所解：设x1、x2分别表示产品I、II的产量，则建立问题的线性规划模型为：用图解法求得最优决策方案为：

x1=4，x2=3，z=62。6解：设x1、x2分别表示产品I、II的产量，则建立问假设要求决策人员制定生产方案时考虑如下意见：1、由于产品I销售有下降趋势，故希望产品I的产量尽量不超过产品II的产量。2、超过计划供应的原材料时要高价采购，会使成本增加。3、尽可能充分利用设备台时，但不希望加班。4、尽可能达到并超过计划利润指标56元。7假设要求决策人员制定生产方案时考虑如下意见：7类似上述这样存在多个目标的多目标决策问题，称为目标规划问题。8类似上述这样存在多个目标的多目标决策问题，称为目标

对于多目标问题，线性规划很难为其找到最优方案．极有可能出现：第一个方案使第一目标的结果优于第二方案，而对于第二目标，第二方案优于第一方案．就是说很难找到一个方案使所有目标同时达到最优，特别当约束条件中有矛盾方程时，线性规划方法是无法解决的．实践中，人们转而采取“不求最好，但求满意”的策略，在线性规划的基础上建立一种新的数学规划方法——目标规划．

对于多目标问题，线性规划很难为其找到最优方案．极有可1.偏差变量正偏差变量：表示决策值超过目标值的部分，记为d+；负偏差变量：表示决策值未达到目标值的部分，记为d-。二.目标规划数学模型的基本概念101.偏差变量二.目标规划数学模型的基本概念10因为决策值不可能既超过目标值，同时又未达到目标值，所以d+和d-存在如下关系：（1）d+>0，d-=0（决策值超过目标值）（2）

d->0，d+=0（决策值未达到目标值）（3）

d+=d-=0（决策值等于目标值）11因为决策值不可能既超过目标值，同时又未达到目标值，所以d+2.绝对约束和目标约束（1）绝对约束：必须严格满足的约束条件。绝对约束是硬约束，不能满足这些约束条件的解为非可行解。如：线性规划问题中的所有约束条件都是绝对约束。122.绝对约束和目标约束12（2）目标约束：目标约束是目标规划特有的。目标约束是软约束，在达到此目标值时允许发生正偏差或负偏差，因此在这些约束的左端要加入正偏差、负偏差变量；其约束右端项是要追求的目标值。13（2）目标约束：目标约束是目标规划特有的。13目标规划问题的基本概念

对有严格限制的资源使用建立绝对约束，数学形式同线性规划中的约束条件

对不严格限制的资源，可通过目标约束来表达。对于前例中的原材料，若用绝对约束则有：若用目标约束则有：目标规划问题的基本概念对有严格限制的资源使用建立绝对约束3.优先因子(优先等级)和权系数一个规划问题常常有若干个目标，决策者要求达到这些目标时，有主次或轻重缓急的不同。这种不同目标的主次轻重差别有两种：绝对的差别：优先因子不同相对的差别：权系数不同153.优先因子(优先等级)和权系数15（1）优先因子优先因子用Pk来表示。只有在高级优先因子对应的目标已满足的基础上，才能考虑低级优先因子对应的目标；在考虑低级优先因子对应的目标时，绝对不允许违背已经满足的高级优先因子对应的目标。16（1）优先因子16优先因子间的关系为：Pk>>Pk+1Pk对应的目标比Pk+1对应的目标具有绝对的优先性.注意：目标规划问题中，通常把绝对约束作为最高优先级来考虑。17优先因子间的关系为：17（2）权系数权系数用ωj来表示。多个目标具有相同的优先因子时，它们的重要性可用权系数的不同来表示。权系数的确定由决策者按具体情况而定。18（2）权系数184.目标规划的目标函数目标规划的目标函数又称为准则函数或达成函数。目标规划的目标函数由各目标约束的偏差变量、各目标约束相应的优先因子、各目标约束相应的权系数共同构成。194.目标规划的目标函数19当每一目标值确定后，决策者要求尽可能缩小偏离目标值，所以目标规划的目标函数只能是极小化，其基本形式有三种：20当每一目标值确定后，决策者要求尽可能缩小偏离目标值，所以目标（1）希望恰好达到目标值。这时，决策值超过目标值或不足目标值都是不希望的，即正、负偏差变量都要尽可能地小：21（1）希望恰好达到目标值。21（2）希望不超过目标值。这时，允许达不到目标值，但不希望超过目标值，即正偏差变量要尽可能地小：22（2）希望不超过目标值。22（3）希望不低于目标值。这时，允许超过目标值，但不希望低于目标值，即负偏差变量要尽可能地小：23（3）希望不低于目标值。23三、目标规划的数学模型例2：在例1中原材料供应受严格限制的基础上考虑：1.首先由于产品I销售疲软，故希望产品I的产量

不超过产品II的产量；3.其次尽可能充分利用设备台时，但不加班4.再次利润额不小于56元。24三、目标规划的数学模型例2：在例1中原材料供应受严格限制的基原材料供应严格限制；25原材料供应严格限制；251.由于产品I销售疲软，故希望产品I的产量不超过产品II的产量；261.由于产品I销售疲软，故希望产品I的产量不超过产2、尽可能充分利用设备台时，但不加班；272、尽可能充分利用设备台时，但不加班；273.利润额不小于56元。283.利润额不小于56元。28从而建立问题的模型如下：29从而建立问题的模型如下：29模型亦可表述为：30模型亦可表述为：30

练习：某企业生产甲、乙两种产品，数据见下表：31练习：某企业生产甲、乙两种产品，数据见下表：

例2：某企业生产甲、乙两种产品，数据见下表：32例2：某企业生产甲、乙两种产品，数据见下表：解：设生产甲、乙产品各33解：设生产甲、乙产品各33目标规划的一般数学模型为：34目标规划的一般数学模型为：34建立目标规划模型的步骤1）列出全部的约束条件2）把要达到指标的约束不等式加上正、负偏差变量后化为目标约束等式3）对目标赋予相应的优先因子4）对同一级优先因子中的各偏差变量，若重要程度不同时，可赋予不同的加权系数5）构造一个按优先因子及加权系数和对应的目标偏差变量所要实现最小化的目标函数建立目标规划模型的步骤1）列出全部的约束条件2）把要达到第二节解目标规划的图解法

对于具有两个决策变量的目标规划的数学模型可以用图解法来分析求解。一、图解法的步骤1.在平面直角坐标系内画出由绝对约束和非负条件所组成的公共取值范围。36第二节解目标规划的图解法对于具有两个决策2.按优先因子的高低，依次在平面直角坐标系内画出目标约束所组成的公共取值范围：（1）令正负偏差变量等于0，画出所有的约束直线；（2）在直线旁标出正、负偏差变量所示方向。（3）正负偏差变量表示直线可以沿正、负偏差变量所示方向平移。3.根据目标函数中的优先因子来分析求解。372.按优先因子的高低，依次在平面直角坐标系内画出目标约束所二、最终解是最优解的情况38二、最终解是最优解的情况38解：x2x11.画出绝对约束和非负条件所围成的取值范围。OAB39解：x2x11.画出绝对约束和非负条件所围成的取值范围。O2.画出目标约束所围成的取值范围。x2轴上的截距402.画出目标约束所围成的取值范围。x2轴上的截距40x2x1OBAC

偏差变量在画直线取为0，直线画好后，在该直线上标出目标函数中与该直线相关的偏差变量增大时直线的平移方向（用垂直于直线的箭头来反映）．41x2x1OBAC偏差变量在画直线取为0，直线x2轴上的截距42x2轴上的截距42x2x1OABECD43x2x1OABECD43x2轴上的截距44x2轴上的截距44x2x1OBACEDFGJ45x2x1OBACEDFGJ453.根据目标函数中的优先因子来分析求解。表示直线左上角的部分，此时满足从而公共取值范围为：OBC（1）463.根据目标函数中的优先因子来分析求解。表示直线x2x1OBACEDFGJ47x2x1OBACEDFGJ47表示直线上的部分，此时满足从而公共取值范围为：线段ED（2）48表示直线x2x1OBACEDFGJ49x2x1OBACEDFGJ49（3）表示直线的右上角部分，此时满足从而公共取值范围为：线段GD50（3）表示直线x2x1OBACEDFGJ51x2x1OBACEDFGJ51可求得：G的坐标为：（2，4）D的坐标为：（10/3，10/3）G和D的凸组合均是目标规划问题的解。52可求得：52在本例中，依次先后次序满足了：因而z*=0，问题的最终解是最优解。但在大多数问题中并非如此，会出现某些约束得不到满足，故将目标规划问题的最优解称为满意解。53在本例中，依次先后次序满足了：因而z*=0，问题的目标规划图解法的具体演算过程第1步：由决策变量绘画所有约束条件的直线图形，偏差变量以平移直线的方法加以考虑．第5步：重复第3、4步过程，直到解区域Ri减少到一点或满足了所有k个级别的目标为止，此时Rk即为最优解区域，其中的任何一点均为目标规划满意解．第2步：对P1级的各目标，确定解区域R1．第3步：对下一个优先级别Pi级各目标，确定它的最优解空间Ri，但必须是Ri

Ri-1(i=2,3,…)．

第4步：在这个过程中，如果某解区域Ri减小到一点，则结束，因为此时没有进一步改进的可能．目标规划图解法的具体演算过程第1步：由决策变量绘画所有约束条清华大学-运筹学-第四章目标规划课件例3：某电视机厂装配黑白和彩色两种电视机。每周市场的黑白电视机销量为30台，每台可获利40元；每周市场的彩色电视机销量为24台，每台可获利80元。每装配一台电视机需占用装配线1小时，装配线每周计划开动40小时。三、最终解是满意解的情况56例3：某电视机厂装配黑白和彩色两种电视机。三、最终解是满意解该厂确定的目标为：第一优先级：充分利用装配线每周计划开动时间40小时；第二优先级：允许装配线加班，但加班时间每周尽量不超过

10小时；第三优先级：装配电视机数量尽量满足市场需求量。因彩色电视机利润高，取其权系数为2。建立问题模型，并求解黑白和彩色电机机产量？57该厂确定的目标为：571.充分利用装配线每周计划开动时间40小时：解：设x1、x2分别表示彩色和黑白电视机产量。581.充分利用装配线每周计划开动时间40小时：解：设x2.允许装配线加班，但加班时间每周尽量不超过10小时：592.允许装配线加班，但加班时间每周尽量不超过10小时：3.装配彩色电视机数量尽量满足市场需求量，且权系数为2：603.装配彩色电视机数量尽量满足市场需求量，且权系数为24.装配黑白电视机数量尽量满足市场需求量，且权系数为1：614.装配黑白电视机数量尽量满足市场需求量，且权系数为1从而建立问题的模型如下：62从而建立问题的模型如下：62x2x163x2x163x2x164x2x164x2x165x2x165在ABEF中无法满足：所以只能在ABEF中取一点，使尽可能小。在ABEF中只有取E点才可使最小。故E点为为满意解，E=（24，26）。66在ABEF中无法满足：所以只能在ABEF中取一点，使x2x167x2x167分析：此例中约束没有得到满足。问题的最终解只是满意解而不是最优解。68分析：没有得到满足。问题的最终解只是满意解而不是最优解。6869697070717172727373747475757676777778787979808081818282838384848585目标规划的灵敏度分析方法与线性规划相似，除了分析各项系数的变化之外，还有优先因子和权系数的变化问题。第五节目标规划的灵敏度分析

86目标规划的灵敏度分析方法与线性规划相似，除了一、右端常数的影响分析例：已知目标规划问题87一、右端常数的影响分析例：已知目标规划问题87最终单纯形表为88最终单纯形表为88若第一个目标约束的右端项变为120，原满意解发生什么样的变化？89若第一个目标约束的右端项变为120，原满意解发生什么样的解：90解：90将其反映到最终单纯形表中：91将其反映到最终单纯形表中：91即出现了第三种情况（原问题不可行，对偶问题可行），利用对偶单纯形法求解：92即出现了第三种情况（原问题不可行，对偶问题可行），利用对偶单939394949595得到问题的满意解为：96得到问题的满意解为：96二、优先因子位置变化的影响分析例：已知目标规划问题97二、优先因子位置变化的影响分析例：已知目标规划问题97最终单纯形表为98最终单纯形表为98求：目标函数变为后问题的满意解。解：99求：目标函数变为后问题的满意解。解：99目标函数的变化仅影响各变量的检验数。因此，只需考察检验数的变化即可。分析：变化后的目标函数只是将原目标函数的P3和P4优先因子顺序改变了一下。处理方法：将原目标规划的最终单纯形表的目标函数行（cj行）做出相应调整，并重新计算检验数。100目标函数的变化仅影响各变量的检验数。因此，只需考察检验数的变最终单纯形表转变为101最终单纯形表转变为101换入，换出，得到新的单纯形表：102换入，换出，得到新的单纯形表：1得到问题的满意解为：103得到问题的满意解为：103三、权系数变化的影响分析例：已知目标规划问题104三、权系数变化的影响分析例：已知目标规划问题104最终单纯形表为105最终单纯形表为105求：目标函数变为后问题的满意解。解：106求：目标函数变为后问题的满意解。解：106目标函数的变化仅影响各变量的检验数。因此，只需考察检验数的变化即可。分析：变化后的目标函数只是将原目标函数的P3优先因子中两目标的权系数改变了一下。处理方法：将原目标规划的最终单纯形表的目标函数行（cj行）做出相应调整，并重新计算检验数。107目标函数的变化仅影响各变量的检验数。因此，只需考察检验数的变最终单纯形表为108最终单纯形表为108分析：：原解不变。：利用单纯形法继续求解。109分析：：原解不变。：利用单纯形法继续求解。109

第5节应用举例例6:某单位领导在考虑本单位职工的升级调资方案时，依次遵守以下规定：(1)不超过年工资总额60000元；(2)每级的人数不超过定编规定的人数；(3)Ⅱ，Ⅲ级的升级面尽可能达到现有人数的20%，且无越级提升；(4)Ⅲ级不足编制的人数可录用新职工，又Ⅰ级的职工中有10%要退休。110第5节应用举例例6:某单位领导在考虑本单位职工的升级有关资料汇总于表中，问该领导应如何拟订一个满意的方案。有关资料汇总于表中，问该领导应如何拟订一个满意的方案。

解：设x1、x2、x3分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ级的新职工人数。对各目标确定的优先因子为：P1——不超过年工资总额60000元；P2——每级的人数不超过定编规定的人数；P3——Ⅱ、Ⅲ级的升级面尽可能达到现有人数的20%。解：设x1、x2、x3分别表示提升到Ⅰ、Ⅱ级和录用到Ⅲ先分别建立各目标约束2000(10-10×0.1+x1)+1500(12-x1+x2)+1000(15-x2+x3)+

d-1-d1+=60000

2、每级的人数不超过定编规定的人数

对Ⅰ级有10-10×0.1+x1+d2-_d2+=12对Ⅱ级有12-x1+x2+d3-_d3+=15对Ⅲ级有15-x2+x3+d4-_d4+=153、Ⅱ，Ⅲ级的升级面尽可能达到现有人数的20%对Ⅱ级有x1+d5-_d5+=12×0.2对Ⅲ级有x2+d6-_d6+=15×0.2目标函数：minz=P1d1++P2(d2++d3++d4+)+P3(d5-+d6-)1、年工资总额不超过60000元先分别建立各目标约束2000(10-10×0.1+x1)+1以上目标规划模型可用单纯形法求解，可得到多重解。现将这些解汇总于表4-9，这单位的领导再按具体情况，从表4-9中选一个执行方案以上目标规划模型可用单纯形法求解，可得到多重解。现将这些解汇例7：已知有三个产地给四个销地供应某种产品，产销地之间的供需量和单位运价如表所示。115例7：已知有三个产地给四个销地供应某种产品，产销地之间的供有关部门在研究调运方案时，依次考虑以下七项目标，并规定其相应的优先等级：P1：B4是重点保证单位，必须全部满足其需要；P2：A3向B1提供的产量不少于100；P3：每个销地