运筹学 第3版 课件 07 目标规划

第7章目标规划第7章目标规划§7-1目标规划的数学模型

§7-2目标规划模型的图解法

§7-3目标规划模型的单纯形法

§7-4目标规划模型的灵敏度分析§7-5 应用举例§7-1目标规划的数学模型一、问题的提出二、目标规划的基本思想三、目标规划的数学模型例7-1：某工厂在计划期内要生产产品I和产品II两种产品，现有的资源及这两种产品的技术消耗系数、单位利润如下表，试确定计划期内的生产计划，使获得的利润最大，建立这个问题的基本模型。产品I产品II现有资源原材料2111设备（台时）1210单位产品利润（元）810解：设x1，x2分别表示产品I、产品II两种产品生产的件数，则得基本模型如下一、问题提出这就使例7－1变成了多目标决策问题。

假设，除上述目标之外，还要满足以下目标（1）

产品I的销量有下降的趋势，故产品I的产量不大于产品II；（2）

应尽可能充分利用设备台时，但不希望加班；（3）应尽可能达到并超过利润指标56元。

一、问题提出对于多目标规划的每一个目标引进一个期望值（理想值）。由于目标之间往往存在冲突，不易使全部目标达到期望值，对每个目标引入正负偏差变量，以描述目标偏离期望值的量。将所有原目标函数转化为约束方程（目标约束），并入原来约束方程中，组成新的约束条件。在这种新的约束下，寻找偏差达到最小的方案（目标规划的目标函数）。由于各个目标的重要程度不同，还可引入优先等级和权系数来限制和修饰各个目标的偏差变量。二、目标规划的基本思想将一个多目标线性规划模型转化为目标规划模型的具体方法步骤如下：

1、设立目标函数的期望值

对于多目标问题中的每一个目标函数Zi(i=1,2,…,k)，首先要确定一个希望能达到的理想值ei(i=1,2,…,k)。这些值的确定并不要求十分精确和严格，只要能够反映决策者的意愿即可，它可以根据以往的历史资料确定（例如：销量达到往年同期水平的110%），也可以根据市场的需求或上级部门的布置等来确定。显然，这样确定的目标期望值可能是互相矛盾的，而且一般不可能全部达到，但这对我们求解问题是无关紧要的。以后我们要做的事情就是寻找某个可行解，使这些目标函数的期望值如何最好地、最接近地得以实现。二、目标规划的基本思想2、引入正、负偏差变量

正、负偏差变量：从数量上描述各目标的期望值没有达到（实现）的程度。：表示第i个目标未达到期望值的数值。：表示第i个目标超出期望值的数值。例7-1的多目标线性规划加入目标期望值和正、负偏差变量。产品I与产品II的销量限制：设备台时：利润目标：目标约束（软约束）：由多目标规划问题的目标函数加入正负偏差变量和期望值后转化得来。假设，除上述目标之外，还要满足以下目标（1）

产品I的销量有下降的趋势，故产品I的产量不大于产品II；（2）

应尽可能充分利用设备台时，但不希望加班；（3）应尽可能达到并超过利润指标56元。

系统约束（硬约束）：必须严格满足的等式和不等式约束。目标规划问题的约束＝目标约束＋系统约束3、建立新的目标函数（或称达成函数）（1）要求尽可能准确地实现目标（2）要求尽可能不低于期望值，而允许超过期望值（3）要求不得超过期望值，但允许低于期望值例如：在例7-1中目标函数（1）产品I的产量不大于产品II（2）应尽可能充分利用设备台时，但不希望加班（3）应尽可能达到并超过利润指标56元

二、目标规划的基本思想4、目标的优先等级和权系数（1）优先等级：它是各目标优先次序的一种划分。某些目标的实现是另一些目标的前提，即决策者想在达到最重要目标的前提下，再来解决次要目标。为此，引进目标优先等级的概念，且用优先等级因子Pi（i=1,2,…,k）表示第i级别的目标的重要程度。具有双重意义：其二，它是一种特殊的正常数，且具有关系例如，例7－1中，优先等级依次为，则目标函数为：其一，它仅仅是一种记号，如偏差变量最为重要，则记为；为二级重要目标，则记为。二、目标规划的基本思想4、目标的优先等级和权系数（2）权系数：目标函数中各目标偏差变量的有限值系数称为权系数。如它表示了一目标相对于其它目标的重要程度。权系数对目标规划解的影响是很大的。不同的权系数会得出完全不同的最优解。因此，要想得到符合实际情况的最优方案，必须对各个目标确定适当的权系数。二、目标规划的基本思想例7－2在原材料严格受限的基础上，产品II的产量不低于I的产量；充分利用设备台时；利润不低于56。二、目标规划的基本思想1、模型的一般式目标约束系统约束三、目标规划的数学模型2、建立实际问题目标规划模型的基本步骤（1）根据要研究的问题所提出的各目标与条件，确定目标值，列出目标约束与绝对约束；（2）可根据决策者的需要将某些或全部绝对约束化为目标约束，这时只要给绝对约束加上负偏差变量或减去正偏差变量即可。（3）给各目标赋予相应的优先因子Pk（4）对同一优先等级中的各偏差变量，若需要，可按其重要程度不同，赋予相应的权系数（5）根据决策者的要求，按下列三种情况：①恰好得到目标值，取②允许超过目标值，取③不允许超过目标值，取

构造一个由优先因子和权系数相对应的偏差变量组成，要求实现极小化的目标函数三、目标规划的数学模型①③②2134567812340567891011910AB解：1、在第一象限内，作各约束条件：（1）绝对约束的做法与线性规划相同（2）目标约束：先令作直线，然后在直线旁标出2、求解：按优先等级确定最优解CDFG

最优解：在线段GD上，G点坐标为（2，4），D点坐标为（10/3，10/3）§7-2目标规划模型的图解法例7－3解：设x1，x2分别表示智能和液晶电视机的产量§7-2目标规划模型的图解法例7－4：生产智能和液晶电视机，装配一台电视机占用装配线1小时，装配线每周有40小时可用，预计市场每周智能电视机的销售量是24台，每台可获利800元，液晶电视机的销售量是30台，每台可获利400元，该厂确定目标为：

第一优先级：充分利用装配线每周40小时； 第二优先级：允许装配线加班，但加班时间每周尽量不超过10小时； 第三优先级：装配电视机的数量尽量满足市场需要，因智能电视利润高，取其权系数为2。 试建立这个问题的目标规划模型，并求解两种电视的产量。③②说明：绝对约束优先级最高必须满足，依次再满足具有P1，P2，P3优先因子的目标，有时在满足了P1，P2之后不能再满足具有P3优先因子的目标，这时得到的解为满意解。201030405001020304050①④ABCDEFABCD→ABEF→E在E点取得满意解，其坐标为（24，26）§7-2目标规划模型的图解法§7－3目标规划模型的单纯形法1121101－11－110121－1568101－11－1－221－10－811/1--10/256/10[2]例7－51121101－11－1101[2]1－1568101－11－1－22－8－10163/21－1/21/253/21－11/2－1/251/211/2－1/263－551－1111－35－51[3]410/310211/1--10/256/10例7-5（续）63/21－1/21/253/21－11/2－1/251/211/2－1/26[3]－551－1111－35－51312－2－1/21/221－13－3－1/21/2414/3－4/3－1/61/621－5/35/31/3－1/31111最优解：另一个最优解：410/3102例7-5（续）注意事项：1、判断进基变量时，检查所要判断的第k行中是否存在负数，且负数所在列对应的前k－1行的系数是否为零，如果是，则对应的变量作为进基变量，否则检验下一行。2、按最小θ规则确定出基变量时，当存在两个或两个以上的最小比值时，选取具有较高优先级别的变量作为出基变量。§7－3目标规划模型的单纯形法6111-11411-118-33-221-12-111-1233-32-211例7－6思考请思考下面的问题：该目标规划问题的解是最优解吗？6111-11411-118-33-221-12-111-1233-32-211单纯形法注意事项：1、判断进基变量时，检查所要判断的第k行中是否存在负数，且负数所在列对应的前k－1行的系数是否为零，如果是，则对应的变量作为进基变量，否则检验下一行。2、按最小θ规则确定出基变量时，当存在两个或两个以上的最小比值时，选取具有较高优先级别的变量作为出基变量。§7-4目标规划模型的灵敏度分析目标规划中灵敏度的分析同线性规划中灵敏度分析的区别，表现在其目标函数的变化上。在目标规划的目标函数是由体现各目标优先程度的优先因子组成的，而这些优先因子是相对而言的，所以其变化至少是两个或两个以上优先因子的变化。同线性规划一样，当这些优先因子调整后，仅仅影响其检验数；同线性规划不同之处，它虽能讨论系数变化对解的影响，但不能讨论目标系数的变化范围，而是讨论当目标的优先级发生变化后，当前解还是否为满意解，若不是，则进一步求得当前优先级下的满意解。6111-11411-118-33-221-12-111-1233-32-211例7－6§7-4目标规划模型的灵敏度分析611-1-11411-118-33-221-12-111-1233-32-21113-32-21第一种情况原目标函数新目标函数§7-4目标规划模型的灵敏度分析611-1-11411-118-33-221-12-111-1233-32-2113-32-2123------62［1］第二种情况：原目标函数新目标函数81-111-1411-112-221-1-332-111-122-2313-2-321[3]------4---121-5/35/31/3-1/3411-14-2/32/31/3-1/3-116-11-2/32/31/3-1/324/32/35/3-2/31-2/3-1/32/31/31满意解：§7-4目标规划模型的灵敏度分析§7-5应用举例例7－7某单位领导在考虑本单位职工升级调资方案时，依次遵守以下规定： （1）不超过月工资总额60万元； （2）每级的人数不超过定编规定的人数； （3）II、III级的升级面尽可能达到现有人数的20％； （4）III级不足编制的人数可录用新职工，又I级的职工中有10％要退休。等级工资额（万元/月）现有人数编制人数I21012II1.51215III11515合计3742请根据上述要求给出合理的升级调资方案。解：设x1，x2，x3，分别表示提升到I、II级和录用到III级的新职工人数（1）不超过月工资总额60万元；（2）每级的人数不超过定编规定的人数（3）II、III级的升级面尽可能达到现有人数的20％（4）III级不足编制的人数可录用新职工，又I级的职工中有10％要退休对各目标确定的优先因子为：P1：不超过月工资总额60万元P2：每级的人数不超过定编规定的人数P3：II、III级的升级面尽可能达到现有人数的20％目标函数为：例7-7（续）等级工资额（万元/月）现有人数编制人数I21012II1.51215III11515合计3742解：设x1，x2，x3，分别表示提升到I、II级和录用到III级的新职工人数例7-7（续）P1：B4是重点保证单位必须全部满足其需要P2：A3向B1提供的产量不少于100P3：每个销地的供应量不小于其需要量的80％P4：所定调运方案的总费用不超过最小运费调运方案的10％P5：因路段问题尽量避免安排将A2的产品运往B4P6：给B1和B3的供应率要相同P7：力求运费最省销地产地产量526730035462004523400销量200100450250900／1000例7－8已知三个产地给四个销地供应某种产品产销地之间的供需关系和单位运价见下表，有关部门在研究调运方案时依次考虑以下七个目标，并规定其相应的优先等级。§7-5应用举例销地产地产量526730035462004523400销量200100450250900/1000P1：B4是重点保证单位必须全部满足其需要P2：A3向B1提供的产量不少于100P3：每个销地的供应量不小于其需要量的80％P4：所定调运方案的总费用不超过最小运费调运方案的10％P5：因路段问题尽量避免安排将A2的产品运往B4P6：给B1和B3的供应率要相同P7：力求运费最省例7-8（续）P2：A3向B1提供的产量不少于100P3：每个销地的供应量不小于其需要量的80％；销地产地产量526730035462004523400销量200100450250900／1000例7-8（续）最小运费运输方案:运输费用：2950P4：所定调运方案的总费用不超过最小运费调运方案的10％目标约束例7-8（续）P5：因路段问题尽量避免安排将A2的产品运往B4P6：给B1和B3的供应率要相同P7：力求运费最省销地产地产量526730035462004523400销量200100450250900／1000例7-8（续）P7：力求运费最省P1：B4是重点保证单位必须全部满足其需要P2：A3向B1提供的产量不少于100P3：每个销地的供应量不小于其需要量的80％P4：所定调运方案的总费用不超过最小运费调运方案的10％P5：因路段问题尽量避免安排将A2的产品运往B4P6：给B1和B3的供应率要相同xij≥0,i=1,…,3；j=1,…,4解：设决策变量为xij，i=1,…,3；j=1,…,4例7-9某厂利用其三个分厂的剩余能力扩大三种新产品。三个厂都能生产。管理者的主要原则是赢利，希望将剩余能力尽可能地利用。问题是正常生产时，工人有富余，而解雇费用很大，管理者不愿意这样做。所以想平衡三个厂的剩余能力，公平地分配任务，减少下岗工人。分厂生产能力（台）运输能力M3175012,000230010,00034506,500产品所需运力（M3/台）利润（万元/台）销售量预测（台）A3015900B20181,000C1512700目标顺序：P1：目标