目标规划数学模型省公共课一等奖全国赛课获奖课件.pptx

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