目标规划数学模型.pptx

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