目标规划new867103354-课件

某企业生产甲、乙两种产品，需要用到某企业生产甲、乙两种产品，需要用到A,B,C三种设备，关三种设备，关于产品的盈利与使用设备的工时及限制如下表所示。于产品的盈利与使用设备的工时及限制如下表所示。例例1 1 生产安排问题生产安排问题 问该企业应如何安排生产，使得在计划期内总利润最大？问该企业应如何安排生产，使得在计划期内总利润最大？1.线性规划建模线性规划建模设甲、乙产品的产量分别为设甲、乙产品的产量分别为x1,x2,建立线性规划模型：建立线性规划模型：用单纯形法求解用单纯形法求解,得到最优解得到最优解 2.目标规划建模目标规划建模在上例中，企业的经营目标不仅要考虑利润，还需要考虑在上例中，企业的经营目标不仅要考虑利润，还需要考虑多个方面，因此增加下列因素多个方面，因此增加下列因素(目标目标)：力求使利润指标不低于力求使利润指标不低于1500元元 考虑到市场需求考虑到市场需求,甲、乙两种产品的产量比应尽量保持甲、乙两种产品的产量比应尽量保持1:2 设备设备A为贵重设备，严格禁止超时使用为贵重设备，严格禁止超时使用 设备设备C可以加班；设备可以加班；设备B既要求充分利用，又尽可能不既要求充分利用，又尽可能不加班，在重要性上，设备加班，在重要性上，设备B是设备是设备C的的3倍倍从上述问题可以看出，仅用线性规划方法是不够的，需要从上述问题可以看出，仅用线性规划方法是不够的，需要借助于目标规划的方法进行建模求解借助于目标规划的方法进行建模求解某汽车销售公司委托一个广告公司在电视上为其做广告，汽某汽车销售公司委托一个广告公司在电视上为其做广告，汽车销售公司提出三个目标：车销售公司提出三个目标：例例2 汽车广告费问题汽车广告费问题 广告公司必须决定购买两种类型的电视广告展播各多少分钟？广告公司必须决定购买两种类型的电视广告展播各多少分钟？第一个目标，至少有第一个目标，至少有40万高收入的男性公民万高收入的男性公民(记为记为HIM)看到这个广告看到这个广告第二个目标，至少有第二个目标，至少有60万一般收入的公民万一般收入的公民(记为记为LIP)看到这个广告看到这个广告第三个目标，至少有第三个目标，至少有35万高收入的女性公民万高收入的女性公民(记为记为HIW)看到这个广告看到这个广告广告公司可以从电视台购买两种类型的广告展播：足球赛中广告公司可以从电视台购买两种类型的广告展播：足球赛中插播广告和电视系列剧插播广告。广告公司最多花费插播广告和电视系列剧插播广告。广告公司最多花费6060万元万元的电视广告费。每一类广告展播每分钟的花费及潜在的观众的电视广告费。每一类广告展播每分钟的花费及潜在的观众人数如下表所示人数如下表所示 3.尝试线性规划建模尝试线性规划建模设设x1,x2分别是足球赛和电视系列剧中插播的分钟数，按照分别是足球赛和电视系列剧中插播的分钟数，按照要求，可以列出相应的线性规划模型要求，可以列出相应的线性规划模型用单纯形法求解用单纯形法求解,会发现该问题不可行。会发现该问题不可行。4.线性规划建模局限性线性规划建模局限性 线性规划要求所求解的问题必须满足全部的约束，而实际线性规划要求所求解的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；问题中并非所有约束都需要严格的满足；线性规划只能处理单目标的优化问题，而对一些次目标只线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理。但在实际问题中，目标和约束是可以相能转化为约束处理。但在实际问题中，目标和约束是可以相互转化的，处理时不一定要严格区分；互转化的，处理时不一定要严格区分；线性规划在处理问题时，将各个约束线性规划在处理问题时，将各个约束(也可看作目标也可看作目标)的地的地位看成同等重要，而在实际问题中，各个目标的重要性即有位看成同等重要，而在实际问题中，各个目标的重要性即有层次上的差别，也有在同一层次上不同权重的差别层次上的差别，也有在同一层次上不同权重的差别 线性规划寻求最优解，而许多实际问题只需要找到满意解线性规划寻求最优解，而许多实际问题只需要找到满意解就可以了。就可以了。目标规划的数学模型目标规划的数学模型为了克服线性规划的局限性为了克服线性规划的局限性,目标规划采用如下手段：目标规划采用如下手段：1.设置偏差变量设置偏差变量;2.统一处理目标与约束统一处理目标与约束;3.目标的优先级与权系数。目标的优先级与权系数。目标规划的基本概念目标规划的基本概念目标值目标值(理想值理想值)决策者事先对每个目标给出的估计值决策者事先对每个目标给出的估计值.1.设置偏差变量设置偏差变量用偏差变量用偏差变量(Deviational variables)来表示实际值与目标值来表示实际值与目标值之间的差异，令之间的差异，令-超出目标的差值，称为正偏差变量超出目标的差值，称为正偏差变量-未达到目标的差值，称为负偏差变量未达到目标的差值，称为负偏差变量其中其中 与与 至少有一个为至少有一个为0 0约定如下：约定如下：当实际值超过目标值时，有当实际值超过目标值时，有当实际值未达到目标值时，有当实际值未达到目标值时，有当实际值与目标值一致时，有当实际值与目标值一致时，有 2.统一处理目标与约束统一处理目标与约束在目标规划中，约束可分两类，一类是对资源有严格限制在目标规划中，约束可分两类，一类是对资源有严格限制的，称为刚性约束的，称为刚性约束(Hard Constraint)（绝对约束）（绝对约束）；例如在；例如在用目标规划求解例用目标规划求解例1中设备中设备A禁止超时使用，则有刚性约束禁止超时使用，则有刚性约束另一类是可以不严格限制的，连同原线性规划的目标另一类是可以不严格限制的，连同原线性规划的目标,构构成柔性约束成柔性约束(Soft Constraint)（目标约束）（目标约束）.例如在求解例例如在求解例1中，我们希望利润不低于中，我们希望利润不低于1500元，则目标可表示为元，则目标可表示为求解例求解例1中甲、乙两种产品中甲、乙两种产品的产量尽量保持的产量尽量保持1:2的比例，的比例，则目标可表示为则目标可表示为设备设备C可以适当加班，可以适当加班，则目标可表示为则目标可表示为设备设备B既要求充分利用，又尽可能既要求充分利用，又尽可能不加班，则目标可表示为不加班，则目标可表示为从上面的分析可以看到：从上面的分析可以看到：如果希望不等式保持大于等于，则极小化负偏差；如果希望不等式保持大于等于，则极小化负偏差；如果希望不等式保持小于等于，则极小化正偏差；如果希望不等式保持小于等于，则极小化正偏差；如果希望保持等式，则同时极小化正、负偏差如果希望保持等式，则同时极小化正、负偏差 3.目标的优先级与权系数目标的优先级与权系数在目标规划模型中，目标的优先分为两个层次，第一个在目标规划模型中，目标的优先分为两个层次，第一个层次是目标分成不同的优先级，在计算目标规划时，必层次是目标分成不同的优先级，在计算目标规划时，必须先优化高优先级的目标，然后再优化低优先级的目标。须先优化高优先级的目标，然后再优化低优先级的目标。通常以通常以P1,P2,.表示不同的因子表示不同的因子,并规定并规定PkPk+1，第二个，第二个层次是目标处于同一优先级，但两个目标的权重不一样，层次是目标处于同一优先级，但两个目标的权重不一样，因此两目标同时优化，用权系数的大小来表示目标重要因此两目标同时优化，用权系数的大小来表示目标重要性的差别。性的差别。4.目标规划的目标函数目标规划的目标函数由各目标约束的正、负偏差变量及其相应的优先因子、由各目标约束的正、负偏差变量及其相应的优先因子、权系数组成（不含决策变量权系数组成（不含决策变量xi），当每一目标值确定），当每一目标值确定后，决策者的要求是尽可能缩小偏差，所以目标规划后，决策者的要求是尽可能缩小偏差，所以目标规划的目标函数总是极小化。的目标函数总是极小化。目标线性规划的一般模型目标线性规划的一般模型目标线性规划模型的一般数学表达式为：目标线性规划模型的一般数学表达式为：解在例解在例1 1中中设备设备A是是刚性约束，刚性约束，其余是柔性约束首先，最重要其余是柔性约束首先，最重要的指标是企业的利润，将它的优的指标是企业的利润，将它的优先级列为第一级；其次，甲、乙先级列为第一级；其次，甲、乙两种产品的产量保持两种产品的产量保持1:2的比例，的比例，列为第二级；再次，列为第二级；再次，设备设备 B和和C的工作时间要有所控制，列为第的工作时间要有所控制，列为第三级，设备三级，设备B的重要性是设备的重要性是设备C的三倍，因此它们的权重不一样。的三倍，因此它们的权重不一样。由此可以得到相应的目标规划模由此可以得到相应的目标规划模型。型。目标规划模型的建立目标规划模型的建立 用目标规划方法求解例用目标规划方法求解例 1 练习题练习题某彩电组装厂生产某彩电组装厂生产A、B、C三种规格电视机，装配工作在三种规格电视机，装配工作在同一生产线上完成。三种产品装配时的工时消耗分别为同一生产线上完成。三种产品装配时的工时消耗分别为6小时、小时、8小时和小时和10小时。生产线每月正常工作时间为小时。生产线每月正常工作时间为200小时，三种小时，三种产品销售后，每台可获利分别为产品销售后，每台可获利分别为500元，元，650元和元和800元，每月元，每月销售量预计为销售量预计为12台、台、10台、台、6台。该厂经营目标如下：台。该厂经营目标如下：P1：利润指标为每月：利润指标为每月16000元；元；P2：充分利用生产能力；：充分利用生产能力；P3：加班时间不超过：加班时间不超过24小时；小时；P4；产量以预计销量为标准；产量以预计销量为标准；为确定生产计划，请建立该问题的目标规划模型。为确定生产计划，请建立该问题的目标规划模型。第二节第二节 目标规划的求解方法目标规划的求解方法一、图解法一、图解法x1x2l1l2OCBAl3Dl41、l1与与l2形成的可行域形成的可行域OABC2、先满足、先满足P1，OD线段线段E3、再满足、再满足P2，ED线段（满意解）线段（满意解）E(500/11,500/11),D(360/7,360/7),1505010050100150 x1x2l1l2OCBAl3DEFl41、绝对约束，可行域、绝对约束，可行域OABD2、满足、满足P1，三角形，三角形ABF3、考虑、考虑P2，ABF与与OD 的最接的最接 近点近点F（满意解）（满意解）F（40，200/3）5010015050100150l1l2l3l4ADCBFE线性目标规划的序贯式算法线性目标规划的序贯式算法基本思想：将目标规划模型按照各目标的优先基本思想：将目标规划模型按照各目标的优先等级次序，将原目标规划问题依次分解为一系列等级次序，将原目标规划问题依次分解为一系列单目标规划问题分别求其最优解。单目标规划问题分别求其最优解。要求：在求解某一优先级单目标规划问题时，以要求：在求解某一优先级单目标规划问题时，以不破坏所有比它优先的、已满足了的目标为前提。不破坏所有比它优先的、已满足了的目标为前提。为此，把每一优先级求得的目标值作为新的约束加为此，把每一优先级求得的目标值作为新的约束加到优先级在它之后的每一个单目标问题中。到优先级在它之后的每一个单目标问题中。步骤：步骤：第第1步：令步：令i=1(i表示当前正在考虑的优先级别表示当前正在考虑的优先级别)。建。建立仅含立仅含Pi级目标的线性规划单目标模型：级目标的线性规划单目标模型：i P1是指仅考虑与是指仅考虑与P1级目标有关的约束条件。级目标有关的约束条件。第第2步：用单纯形法步：用单纯形法(或其他合适的求解方法或其他合适的求解方法)，求解，求解第第i级单目标规划，得到级单目标规划，得到min zi=zi*为原目标规划中为原目标规划中Pi级目标所能达到的最优解。级目标所能达到的最优解。第第3步：置步：置i:=i+1，若，若ik0(k0为优先级别总数为优先级别总数)，则，则转第转第6步，否则转第步，否则转第4步。步。第第4步：建立相应于下一个优先级别步：建立相应于下一个优先级别Pi的单目标规的单目标规划模型：划模型：第第5步：转第步：转第2步。步。第第6步：最后一个单目标规划的解是原目标规划模型步：最后一个单目标规划的解是原目标规划模型的解，并且向量的解，并且向量 反映了各目标反映了各目标实现的程度，称之为达成向量，又称实现的程度，称之为达成向量，又称zi*为达成解。为达成解。用序贯式算法解下列目标规划：用序贯式算法解下列目标规划：解：建立解：建立P1级目标构成的单目标线性规划：级目标构成的单目标线性规划：建立建立P2级目标构成的单目标线性规划模型：级目标构成的单目标线性规划模型：最优表为最优表为P2级目标没有被完全满足。级目标没有被完全满足。建立建立P3级目标构成的单目标线性规划模型：级目标构成的单目标线性规划模型：消列准则：当得到第消列准则：当得到第k优先级单目标模型的最优单优先级单目标模型的最优单纯形表时，该表检验数行中具有负值检验数的非基纯形表时，该表检验数行中具有负值检验数的非基变量都可以在以后的问题中消除，其相应的列也从变量都可以在以后的问题中消除，其相应的列也从表中消除表中消除(即在以后各优先级的求解中不再出现即在以后各优先级的求解中不再出现)。得到最优表得到最优表P3级目标没有被完全满足。级目标没有被完全满足。建立并求解建立并求解P4级目标所对应的单目标模型级目标所对应的单目标模型P1级与级与P4级目标已完全实现，但级目标已完全实现，但P2级与级与P3级没有级没有完全实现。完全实现。缺点：计算量大。缺点：计算量大。解目标规划的单纯形法解目标规划的单纯形法作以下规定：作以下规定：(1)以检验数小于等于以检验数小于等于0为最优准则。为最优准则。步骤：步骤：（1）建立初始单纯形表，在表中将检验数行按优先因子）建立初始单纯形表，在表中将检验数行按优先因子个数分别列成个数分别列成K行行,置置k=1.（2）检查该行中是否存在正数，）检查该行中是否存在正数，且对应的前且对应的前k-1行的系数行的系数 为为0，若有取其中最大者对应的变量为进基变量，转，若有取其中最大者对应的变量为进基变量，转 （3），否则转（），否则转（5）。）。（3）按最小比值规则确定离基变量，当存在两个或两个）按最小比值规则确定离基变量，当存在两个或两个 以上相同的最小比值时，选取具有较高优先级别的以上相同的最小比值时，选取具有较高优先级别的 变量为离基变量。变量为离基变量。（4）按单纯形法建立新的计算表，返回（）按单纯形法建立新的计算表，返回（2）。）。（5）当）当k=K时，计算结束，表中的解为满意解；否则置时，计算结束，表中的解为满意解；否则置k=k+1,返回（返回（2）。）。求解下列目标规划问题求解下列目标规划问题1111灵敏度分析灵敏度分析改变目标优先等级的分析改变目标优先等级的分析最优表为：最优表为：新的最优表为：新的最优表为：满意解不变。满意解不变。最优表为：最优表为：在原最优表中将在原最优表中将P1行与行与P3行交换得：行交换得：13应用举例应用举例某厂计划生产某厂计划生产A、B、C三种产品，有关资三种产品，有关资源消耗与产品库存费用如下表：源消耗与产品库存费用如下表：根据市场预测，各个阶段每种产品的市场需求量为：根据市场预测，各个阶段每种产品的市场需求量为：现工厂领导确定了以下现工厂领导确定了以下五个优先等级的目标五个优先等级的目标：P1-及时供货，保证需及时供货，保证需求，并且求，并且C产品及时供货产品及时供货的重要性相当于的重要性相当于A、B产品产品的的1.2倍；倍；P2-尽量使加工设备的负荷均衡；尽量使加工设备的负荷均衡；P3-流动资金占用量不超过限额；流动资金占用量不超过限额；P4-稀有材料消耗量不超过限额；稀有材料消耗量不超过限额；P5-产品的库存费用不超过限额。产品的库存费用不超过限额。假设计划初期及期末各种产品的库存量均为假设计划初期及期末各种产品的库存量均为0，试用，试用目标规划编制各阶段每种产品生产数量的生产计划目标规划编制各阶段每种产品生产数量的生产计划设立决策变量设立决策变量约束条件约束条件（1）及时供货，保证需求）及时供货，保证需求第一阶段第一阶段第二阶段第二阶段第三阶段第三阶段（2）各阶段设备负荷均衡）各阶段设备负荷均衡（3）各阶段流动资金占用不超过限额）各阶段流动资金占用不超过限额（4）各阶段稀有材料消耗）各阶段稀有材料消耗（5）各阶段库存费用）各阶段库存费用目标函数目标函数P1-及时供货，保证需求，并且及时供货，保证需求，并且C产品及时供货的产品及时供货的重要性相当于重要性相当于A、B产品的产品的1.2倍；倍；P2-尽量使加工设备的负荷均衡；尽量使加工设备的负荷均衡；P3-流动资金占用量不超过限额流动资金占用量不超过限额；P4-稀有材料消耗量不超过限额；稀有材料消耗量不超过限额；P5-产品的库存费用不超过限额产品的库存费用不超过限额满意解满意解某零售店的职工，除了某零售店的职工，除了1名经理外，还雇有名经理外，还雇有1名管理名管理员，员，2名全日售货员和名全日售货员和1名半日售货员，根据统计名半日售货员，根据统计资料，资料，5名职工每人工作名职工每人工作1小时的贡献及本月的工小时的贡献及本月的工作时间如下表，为鼓励销售，对管理员和两位全日作时间如下表，为鼓励销售，对管理员和两位全日售货员，以他们各自完成销售额的售货员，以他们各自完成销售额的5.5%作为工资作为工资收入，为保持一定的工作效率，应限制职工的收入，为保持一定的工作效率，应限制职工的 加加班时间，各职工每月不许超过的加班时间也列如下班时间，各职工每月不许超过的加班时间也列如下表：表：经理初步确定了如下经理初步确定了如下6个目标个目标P1-每月销售额每月销售额14500元；元；P2-保证全体职工正常工作时间；保证全体职工正常工作时间；P3-管理员每月至少收入管理员每月至少收入170元；元；P4-经理、管理员和全日售货员甲的加班时间经理、管理员和全日售货员甲的加班时间不超过规定时间；不超过规定时间；P5-全日售货员乙和半日售货员的加班时间全日售货员乙和半日售货员的加班时间不超过规定时间；不超过规定时间；P6-保证两位全日售货员每月收入分别为保证两位全日售货员每月收入分别为87元和元和52元元问题是为了实现商店目标，怎样合理安排工作时间。问题是为了实现商店目标，怎样合理安排工作时间。设立决策变量设立决策变量约束条件约束条件（1）全月销售额达到）全月销售额达到14500元元（2）保证职工正常工作时间）保证职工正常工作时间（3）保证管理员、全日售货员甲和乙的收入）保证管理员、全日售货员甲和乙的收入（4）加班时间限制）加班时间限制目标函数目标函数P1-每月销售额每月销售额14500元；元；P2-保证全体职工正常工作时间；保证全体职工正常工作时间；P3-管理员每月至少收入管理员每月至少收入170元；元；P4-经理、管理员和全日售货员甲的加班时间经理、管理员和全日售货员甲的加班时间不超过规定时间；不超过规定时间；P5-全日售货员乙和半日售货员的加班时间全日售货员乙和半日售货员的加班时间不超过规定时间；不超过规定时间；P6-保证两位全日售货员每月收入分别为保证两位全日售货员每月收入分别为87元和元和52元元求解结果与分析求解结果与分析重新规划重新规划通过分析，经理决定降低销售额目标，由通过分析，经理决定降低销售额目标，由于去年的销售额为于去年的销售额为11000元，又预计今年销元，又预计今年销售量能增加售量能增加9%，故决定至少应完成，故决定至少应完成12000元，根据过去经验，在报纸或电台上登广元，根据过去经验，在报纸或电台上登广告，每增加告，每增加100元广告费，销售额可增加元广告费，销售额可增加2%，这个广告效应指标在广告费不超过，这个广告效应指标在广告费不超过500元时相对不变，超过后将急剧下降。元时相对不变，超过后将急剧下降。经理提出以下新的目标：经理提出以下新的目标：P2-至少完成销售额至少完成销售额12000元；元；P1-保证全体职工正常工作时间；保证全体职工正常工作时间；P3-管理员每月至少收入管理员每月至少收入170元；元；P5-全体职工加班不超过规定时间；全体职工加班不超过规定时间；P6-力争增加销售额力争增加销售额11%，即，即1320元；元；P7-保证两位全日售货员每月收入分别为保证两位全日售货员每月收入分别为87元和元和52元元问题是为了实现商店目标，怎样合理安排工作时间。问题是为了实现商店目标，怎样合理安排工作时间。P4-广告费不超过广告费不超过450元；元；（1）全月销售额达到）全月销售额达到12000元元力争增加销售额力争增加销售额11%，即，即1320元；元；1元广告费元广告费的贡献的贡献（2）保证职工正常工作时间）保证职工正常工作时间广告费不超过广告费不超过450元元（3）保证管理员、全日售货员甲和乙的收入）保证管理员、全日售货员甲和乙的收入（4）加班时间限制）加班时间限制求解结果与分析求解结果与分析由于重新确立目标，且提供了由于重新确立目标，且提供了450元的广告费，使元的广告费，使主要目标达到。虽然销售额力争增加主要目标达到。虽然销售额力争增加11%的目标没有的目标没有达到，但目标规划允许为实现较高等级目标的需要而达到，但目标规划允许为实现较高等级目标的需要而放弃较低等级的目标，故上述求解结果及目标结构均放弃较低等级的目标，故上述求解结果及目标结构均是合理的。是合理的。END