目标规划数学模型公开课一等奖优质课大赛微课获奖课件.pptx

第六章第六章 多目的规划多目的规划n前面讨论线性规划、整数规划都只有一个目的函数。前面讨论线性规划、整数规划都只有一个目的函数。n但实际问题中往往需要考虑多个目的，并且在诸多目的中尚但实际问题中往往需要考虑多个目的，并且在诸多目的中尚有主、次之分，有互相补充，有互相对立。有主、次之分，有互相补充，有互相对立。n问题是如何处理复杂甚至互相矛盾多个目的，即在一定约束问题是如何处理复杂甚至互相矛盾多个目的，即在一定约束条件下，要从众多方案中选择一个或几种较好方案，使多个条件下，要从众多方案中选择一个或几种较好方案，使多个目的都能达到满意结果。目的都能达到满意结果。n比如，设计一个新产品工艺过程，希望产量高、成本低、质比如，设计一个新产品工艺过程，希望产量高、成本低、质量好、利润大。由于需要同时考虑多个目的，这类问题比单量好、利润大。由于需要同时考虑多个目的，这类问题比单目的问题要复杂得多。目的问题要复杂得多。n多目的规划是上个世纪多目的规划是上个世纪6060年代初发展起来运筹学一个分支。年代初发展起来运筹学一个分支。第1页第1页n6.1 多目的规划数学模型多目的规划数学模型n6.2 多目的规划解集和象集多目的规划解集和象集n6.3 处理多目的规划一些办法处理多目的规划一些办法n6.4 目的规划目的规划第六章第六章 多目的规划多目的规划第2页第2页例例6-16-1建立数学模型：建立数学模型：对第对第i个公司投资个公司投资对第对第i个公司不投资个公司不投资设总投资为设总投资为总收益为总收益为第3页第3页n6.1 多目的规划数学模型多目的规划数学模型n6.2 多目的规划解集和象集多目的规划解集和象集n6.3 处理多目的规划一些办法处理多目的规划一些办法n6.4 目的规划目的规划第六章第六章 多目的规划多目的规划第4页第4页第四节第四节 目的规划目的规划n目的规划办法是当前处理多目的规划问题成功办目的规划办法是当前处理多目的规划问题成功办法之一，它是在法之一，它是在(LP)基础上发展起来。基础上发展起来。n这种办法这种办法基本思想基本思想是：对每一个目的函数，预先是：对每一个目的函数，预先给定一个盼望值给定一个盼望值(目的值目的值)，在既有约束条件下，这，在既有约束条件下，这组盼望值也许能够达到，也许达不到。我们任务组盼望值也许能够达到，也许达不到。我们任务是求出尽量靠近这组预定盼望值解。是求出尽量靠近这组预定盼望值解。第六章第六章 多目的规划多目的规划多目的规划6-4第5页第5页第四节第四节 目的规划目的规划n线性目的规划数学模型线性目的规划数学模型n线性目的规划求解办法线性目的规划求解办法 n序列法序列法n多阶段法多阶段法n单纯形法单纯形法 第六章第六章 多目的规划多目的规划第6页第6页 某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要在设备A,B上加工,需要消耗材料C,D，单件产品在不同设备上加工工时、所需要材料及现有资源、可得利润以下表所表示。建立使企业总利润最大线性规划模型。例例1 1产品产品甲甲乙乙丙丙资源资源设备设备A312200工时工时设备设备B224200工时工时材料材料C451360公斤材料材料D235300公斤利润利润(元元/件件)403050设甲乙丙三种产品产量为设甲乙丙三种产品产量为 件，则数学模型为：件，则数学模型为：一一.线性目的规划数学模型：线性目的规划数学模型：多目的规划6-4第7页第7页例例1 1产品产品甲甲乙乙丙丙资源资源设备设备A312200工时工时设备设备B224200工时工时材料材料C451360公斤材料材料D235300公斤利润利润(元元/件件)403050 现在公司决议者依据实际情况和市场需求，需要重现在公司决议者依据实际情况和市场需求，需要重新制定经营目的，目的优先顺序下列：新制定经营目的，目的优先顺序下列：(1)(1)利润不少于利润不少于32003200元；元；(2)产品甲乙产量百分比尽也许不超出1.5；(3)(3)丙产量达到丙产量达到3030件；件；(4)(4)最好不加班；最好不加班；(5)(5)受到资金限制，只能使用既有材料而不能再购进。受到资金限制，只能使用既有材料而不能再购进。问公司如何安排生产计问公司如何安排生产计划才干达到经营目的？划才干达到经营目的？多目的规划6-4第8页第8页例例1 1产品产品甲甲乙乙丙丙资源资源设备设备A312200工时工时设备设备B224200工时工时材料材料C451360公斤材料材料D235300公斤利润利润(元元/件件)403050(1)(1)利润不少于利润不少于32003200元；元；(2)产品甲乙产量百分比尽也许不超出1.5；(3)(3)丙产量达到丙产量达到3030件；件；(4)(4)最好不加班；最好不加班；(5)(5)受到资金限制，只能使用既有材料而不能再购进。受到资金限制，只能使用既有材料而不能再购进。解：解：最优解是求下列一组不等式解最优解是求下列一组不等式解:多目的规划6-4第9页第9页例例1 1(1)(1)利润不少于利润不少于32003200元；元；(2)产品甲乙产量百分比尽也许不超出1.5；(3)(3)丙产量达到丙产量达到3030件；件；(4)(4)最好不加班；最好不加班；(5)(5)受到资金限制，只能使用既有材料而不能再购进。受到资金限制，只能使用既有材料而不能再购进。解：解：通过计算不等式无解。但在实际问题中，生产方案总是存通过计算不等式无解。但在实际问题中，生产方案总是存在，无解只能阐明在既有资源条件下，不也许完全满足在，无解只能阐明在既有资源条件下，不也许完全满足5 5个个经营目的。经营目的。目标规划是按事先制订目标次序逐项检验，尽也许使得结果达到预定目标，即使不能达到目标，也要使得结果离目标差距为最小。这就是目标规划求解思绪。对应解称为满意解。最优解是求下列一组不等式解。最优解是求下列一组不等式解。多目的规划6-4第10页第10页例例1 1(1)(1)利润不少于利润不少于32003200元；元；(2)产品甲乙产量百分比尽也许不超出1.5；(3)(3)丙产量达到丙产量达到3030件；件；(4)(4)最好不加班；最好不加班；(5)(5)受到资金限制，只能使用既有材料而不能再购进。受到资金限制，只能使用既有材料而不能再购进。解：解：下面建立下面建立目的规划数学模型目的规划数学模型：建立目的规划数学模型办法：建立目的规划数学模型办法：1.1.引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；2.2.极小化偏差变量实现目的。极小化偏差变量实现目的。多目的规划6-4第11页第11页例例1 1(1)(1)利润不少于利润不少于32003200元；元；解：解：引入一对偏差变量：引入一对偏差变量：负偏差变量负偏差变量d1-=利润不足目的值差额值利润不足目的值差额值正偏差变量正偏差变量d1+=利润超出目的值超出值利润超出目的值超出值当利润当利润0且且d1+=0，有，有3200利润利润当利润当利润 3200时，时，d1+0且且d1-=0，有，有3200利润利润当利润当利润=3200时，时，d1+=0且且d1-=0，有，有实际情况只有一个情况发生，因此将实际情况只有一个情况发生，因此将三式合并为一个等式：三式合并为一个等式：目的约束：目的约束：含有更大弹性，允许结果与所含有更大弹性，允许结果与所制定目的值存在正或负偏差。制定目的值存在正或负偏差。多目的规划6-4第12页第12页例例1 1(1)(1)利润不少于利润不少于32003200元；元；解：解：分析：分析：1.1.1.1.引入偏差变量将目引入偏差变量将目引入偏差变量将目引入偏差变量将目的转化为目的约束；的转化为目的约束；的转化为目的约束；的转化为目的约束；2.2.2.2.极小化偏差变量实极小化偏差变量实极小化偏差变量实极小化偏差变量实现目的。现目的。现目的。现目的。目的约束目的约束性能指标性能指标目的值目的值(盼望值盼望值)多目的规划6-4第13页第13页(2)甲乙产量百分比尽也许不超出1.5；例例1 1负偏差变量负偏差变量d2-=不足产品百分比要求差额值不足产品百分比要求差额值正偏差变量正偏差变量d2+=超出产品百分比要求超出值超出产品百分比要求超出值分析：分析：1.1.1.1.引入偏差变量将目的转引入偏差变量将目的转引入偏差变量将目的转引入偏差变量将目的转2.2.2.2.极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。化为目的约束；化为目的约束；化为目的约束；化为目的约束；性能指标性能指标目的值目的值(盼望值盼望值)多目的规划6-4第14页第14页(3)(3)丙产量达到丙产量达到3030件；件；例例1 1负偏差变量负偏差变量d3-=丙产量不足目的值丙产量不足目的值3030件差额值件差额值正偏差变量正偏差变量d3+=丙产量超出目的值丙产量超出目的值3030件超出值件超出值分析：分析：1.1.1.1.引入偏差变量将目引入偏差变量将目引入偏差变量将目引入偏差变量将目2.2.2.2.极小化偏差变量实极小化偏差变量实极小化偏差变量实极小化偏差变量实标转化为目的约束；标转化为目的约束；标转化为目的约束；标转化为目的约束；现目的。现目的。现目的。现目的。性能指标性能指标目的值目的值(盼望值盼望值)多目的规划6-4第15页第15页多目的规划6-4目的值目的值(盼望值盼望值)(4)(4)最好不加班；最好不加班；例例1 1产品产品甲甲乙乙丙丙资源资源设备设备A312200工时工时设备设备B224200工时工时材料材料C451360公斤材料材料D235300公斤负偏差变量负偏差变量d4-=设备设备A工作时间不足目的值工作时间不足目的值200200工时差额值工时差额值正偏差变量正偏差变量d4+=设备设备A工作时间超出目的值工作时间超出目的值200200工时超出值工时超出值1.1.1.1.引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；2.2.2.2.极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。负偏差变量负偏差变量d5-=设备设备B工作时间不足目的值工作时间不足目的值200200工时差额值工时差额值正偏差变量正偏差变量d5+=设备设备B工作时间超出目的值工作时间超出目的值200200工时超出值工时超出值工作时间不超出额定工时数工作时间不超出额定工时数性能指标性能指标第16页第16页目的值目的值(盼望值盼望值)(4)(4)最好不加班；最好不加班；例例1 1负偏差变量负偏差变量d4-=设备设备A工作时间不足目的值工作时间不足目的值200200工时差额值工时差额值正偏差变量正偏差变量d4+=设备设备A工作时间超出目的值工作时间超出目的值200200工时超出值工时超出值1.1.1.1.引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；2.2.2.2.极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。负偏差变量负偏差变量d5-=设备设备B工作时间不足目的值工作时间不足目的值200200工时差额值工时差额值正偏差变量正偏差变量d5+=设备设备B工作时间超出目的值工作时间超出目的值200200工时超出值工时超出值工作时间不超出额定工时数工作时间不超出额定工时数性能指标性能指标多目的规划6-4第17页第17页多目的规划6-4例例1 1产品产品甲甲乙乙丙丙资源资源设备设备A312200工时工时设备设备B224200工时工时材料材料C451360公斤材料材料D235300公斤负偏差变量负偏差变量d6-=材料材料C消耗量消耗量不足目的值不足目的值360360公斤差额值公斤差额值正偏差变量正偏差变量d6+=材料材料C消耗量消耗量超出目的值超出目的值360360公斤超出值公斤超出值1.1.1.1.引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；2.2.2.2.极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。负偏差变量负偏差变量d7-=材料材料D消耗量消耗量不足目的值不足目的值300300公斤差额值公斤差额值正偏差变量正偏差变量d7+=材料材料D消耗量消耗量超出目的值超出目的值300300公斤超出值公斤超出值(5)(5)材料不再购进材料不再购进第18页第18页例例1 1负偏差变量负偏差变量d6-=所使用材料所使用材料C不足目的值不足目的值360360公斤差额值公斤差额值正偏差变量正偏差变量d6+=所使用材料所使用材料C超出目的值超出目的值360360公斤超出值公斤超出值1.1.1.1.引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；2.2.2.2.极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。负偏差变量负偏差变量d7-=所使用材料所使用材料D不足目的值不足目的值300300公斤差额值公斤差额值正偏差变量正偏差变量d7+=所使用材料所使用材料D超出目的值超出目的值300300公斤超出值公斤超出值(5)(5)材料不再购进材料不再购进多目的规划6-4第19页第19页例例1 1目的规划数学模型目的规划数学模型：称为目的优先因子称为目的优先因子表示目的优先顺序，表示目的优先顺序，其含义是依次求目的最其含义是依次求目的最小值。小值。首先求首先求 最小值，最小值，在此基础上求在此基础上求 最小值，最小值，最后求最后求 最小值。最小值。多目的规划6-4第20页第20页多目的规划6-4将例将例1中建立数学模型办法推广到普通：中建立数学模型办法推广到普通：将该目的转化成目的约束：将该目的转化成目的约束：1.1.1.1.引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；2.2.2.2.极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。假设性能指标假设性能指标 目的值为目的值为引入一对偏差变量：引入一对偏差变量：d-=性能指标性能指标 f(X)不足不足 f0 差额值差额值d+=性能指标性能指标 f(X)超出超出 f0 超出值超出值一一.线性目的规划数学模型：线性目的规划数学模型：第21页第21页多目的规划6-4目的规划有下列五种形式目的函数：目的规划有下列五种形式目的函数：1.1.单目的目的规划数学模型：单目的目的规划数学模型：1.1.1.1.引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；引入偏差变量将目的转化为目的约束；2.2.2.2.极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。极小化偏差变量实现目的。1.若要求若要求 ，则目的函数为，则目的函数为 min(d-+d+)2.若要求若要求 ，则目的函数为，则目的函数为 min d-3.若要求若要求 ，则目的函数为，则目的函数为 min d+4.若要求若要求 ，则目的函数为，则目的函数为 min(d+-d-)第22页第22页目的规划有下列五种形式目的函数：目的规划有下列五种形式目的函数：1.1.单目的目的规划数学模型：单目的目的规划数学模型：1.若要求若要求 ，则目的函数为，则目的函数为 min(d-+d+)2.若要求若要求 ，则目的函数为，则目的函数为 min d-3.若要求若要求 ，则目的函数为，则目的函数为 min d+4.若要求若要求 ，则目的函数为，则目的函数为 min(d+-d-)5.若要求若要求 ，则目的函数为，则目的函数为 min(d-d+)多目的规划6-4第23页第23页例例2 2某厂生产两种型号产品：产品甲和乙某厂生产两种型号产品：产品甲和乙,产品信息下列表：产品信息下列表：产品产品工时工时(小时小时/件件)产值产值(元元/件件)计划产量计划产量(件件/周周)甲甲0.18030乙乙0.212015在制定最优生产计划时有下列在制定最优生产计划时有下列 4 级目的：级目的：第一级目的第一级目的尽也许达到计划产值4000元/周；第二级目的第二级目的第三级目的第三级目的第四级目的第四级目的避免加班；避免加班；产量不要低于计划值产量不要低于计划值(产品乙为新型号产品乙为新型号,更含有竞更含有竞争力争力,故主要程度比为甲故主要程度比为甲:乙乙=1:2)；又知该厂又知该厂工作时间为工作时间为40小时小时/周周5小时小时/周。周。假如提前完毕任务假如提前完毕任务,早下班时间也不要多于早下班时间也不要多于多目的规划6-4第24页第24页设甲乙一周产量为设甲乙一周产量为例例2 2产品产品 工时工时 产值产值 计划值计划值甲甲0.18030乙乙0.212015第一级目的第一级目的尽也许达到计划产值4000元/周第二级目的第二级目的第三级目的第三级目的第四级目的第四级目的避免加班避免加班产品数量不要低于计划值产品数量不要低于计划值5小时小时/周周早下班时间不要多于早下班时间不要多于甲甲:乙乙=1:2性能指标性能指标目的值目的值4040早下班时间超出早下班时间超出5超出值超出值早下班时间不足早下班时间不足5差额值差额值乙产量超出乙产量超出1 15超出值超出值乙产量不足乙产量不足1 15差额值差额值甲产量超出甲产量超出3030超出值超出值甲产量不足甲产量不足3030差额值差额值工作时间超出工作时间超出4040超出值超出值工作时间不足工作时间不足4040差额值差额值产值超出产值超出40004000超出值超出值产值不足产值不足40004000差额值差额值甲产量甲产量 x1乙产量乙产量 x2早下班时间早下班时间工作时间工作时间产值产值多目的规划6-4第25页第25页例例2 2产品产品 工时工时 产值产值 计划值计划值甲甲0.18030乙乙0.212015第一级目的第一级目的尽也许达到计划产值4000元/周第二级目的第二级目的第三级目的第三级目的第四级目的第四级目的避免加班避免加班产品数量不要低于计划值产品数量不要低于计划值5小时小时/周周早下班时间不要多于早下班时间不要多于甲:乙=1:2设甲乙一周产量为设甲乙一周产量为多目的规划6-4第26页第26页例例2 2产品产品 工时工时 产值产值 计划值计划值甲甲0.18030乙乙0.212015第一级目的第一级目的尽也许达到计划产值4000元/周第二级目的第二级目的第三级目的第三级目的第四级目的第四级目的避免加班避免加班产品数量不要低于计划值产品数量不要低于计划值5小时小时/周周早下班时间不要多于早下班时间不要多于甲:乙=1:2设甲乙一周产量为设甲乙一周产量为多目的规划6-4第27页第27页设甲乙一周产量为设甲乙一周产量为例例2 2产品产品 工时工时 产值产值 计划值计划值甲甲0.18030乙乙0.212015第一级目的第一级目的尽也许达到计划产值4000元/周第二级目的第二级目的第三级目的第三级目的第四级目的第四级目的避免加班避免加班产品数量不要低于计划值产品数量不要低于计划值5小时小时/周周早下班时间不要多于早下班时间不要多于甲甲:乙乙=1:2性能指标性能指标目的值目的值甲产量甲产量 x1乙产量乙产量 x2早下班时间早下班时间工作时间工作时间产值产值四级目的四级目的目的规划数学模型目的规划数学模型多目的规划6-4第28页第28页设甲乙一周产量为设甲乙一周产量为例例2 2第一级目的第一级目的尽也许达到计划产值4000元/周第二级目的第二级目的第三级目的第三级目的第四级目的第四级目的避免加班避免加班产品数量不要低于计划值产品数量不要低于计划值5小时小时/周周早下班时间不要多于早下班时间不要多于甲甲:乙乙=1:2注释注释:若各级目的偏差变量能达到若各级目的偏差变量能达到极小值极小值0,0,则各级目的被完全则各级目的被完全实现实现.但多目的规划中但多目的规划中,由于由于各级目的之间也许是互补各级目的之间也许是互补,也也许是矛盾也也许是矛盾.因此在既有因此在既有约束条件下各级目的也许能约束条件下各级目的也许能达到达到,也许不能达到也许不能达到.我们任我们任务是使各级目的偏差变量达务是使各级目的偏差变量达到最小到最小.各级目的偏差变量各级目的偏差变量极小化程度反应了各级目的极小化程度反应了各级目的被实现程度被实现程度.四级目的四级目的目的规划数学模型目的规划数学模型多目的规划6-4第29页第29页例例6-116-11 已知三个工厂生产产品供应四个用户需要已知三个工厂生产产品供应四个用户需要,各工厂各工厂产量产量,用户需求量及从各工厂到各用户单位产品运价用户需求量及从各工厂到各用户单位产品运价下列表下列表:1234产量产量130022003400销量销量200 100 450 25012341300220034004100200100450250最优调运方案最优调运方案上述方案只考虑了总运费最小上述方案只考虑了总运费最小.但在实际问题中但在实际问题中,在制定最优调在制定最优调运方案时运方案时,所追求目的及受到客观限制往往是多方面。比如考所追求目的及受到客观限制往往是多方面。比如考虑下列虑下列7 7个目的：个目的：总产量总产量=900总需求量总需求量=1000多目的规划6-4第30页第30页目的目的1性能指标性能指标目的值目的值1234产量产量130022003400销量销量 200 100450250用户用户4是主要部门是主要部门,需求量必须满足需求量必须满足目的目的2供应用户供应用户1产量中产量中,工厂工厂3产量不少于产量不少于100目的目的3为兼顾普通为兼顾普通,每个用户需求量满足率每个用户需求量满足率不低于不低于80%80%16080360200多目的规划6-4第31页第31页目的目的4性能指标性能指标目的值目的值新方案总运费不超出原方案新方案总运费不超出原方案10%目的目的5因道路限制,从工厂2到用户4路线应尽也许避免运输任务目的目的6用户1和用户3需求量满足率尽也许保持平衡1234产量产量130022003400销量销量200 100 450 250多目的规划6-4第32页第32页目的目的7性能指标性能指标目的值目的值1234产量产量130022003400销量销量 200 100450250力争减少新方案总费用力争减少新方案总费用多目的规划6-4第33页第33页性能指标性能指标目的值目的值目的目的2目的目的1目的目的3目的目的5目的目的6目的目的7目的目的4多目的规划6-4第34页第34页目的目的7性能指标性能指标目的值目的值1234产量产量130022003400销量销量 200 100450250力争减少新方案总费用力争减少新方案总费用多目的规划6-4第35页第35页性能指标性能指标目的值目的值目的目的2目的目的1目的目的3目的目的5目的目的6目的目的700目的目的40多目的规划6-4第36页第36页性能指标性能指标目的值目的值目的目的2目的目的1目的目的3目的目的5目的目的6目的目的7000目的目的4多目的规划6-4第37页第37页性能指标性能指标目的值目的值目的目的2目的目的1目的目的3目的目的5目的目的6目的目的7000目的目的4多目的规划6-4第38页第38页0 00 00 01234产量产量130022003400销量销量 200 100450250多目的规划6-4第39页第39页第四节第四节 目的规划目的规划n线性目的规划数学模型线性目的规划数学模型n线性目的规划求解办法线性目的规划求解办法 n序列法序列法n多阶段法多阶段法n单纯形法单纯形法 第六章第六章 多目的规划多目的规划作业：作业：P295 7 8P295 7 8作业：作业：P241 7 8P241 7 8第40页第40页