《清华大学-运筹学-第四章目标规划课件.ppt》由会员分享，可在线阅读，更多相关《清华大学-运筹学-第四章目标规划课件.ppt（139页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、统计教研室统计教研室 刘莲花刘莲花引引 言言 前面介绍的线性规划问题，研究前面介绍的线性规划问题，研究的都是只有一个目标函数，若干个约束条的都是只有一个目标函数，若干个约束条件的最优决策问题然而现实生活中，衡件的最优决策问题然而现实生活中，衡量一个方案的好坏标准往往不止一个，而量一个方案的好坏标准往往不止一个，而且这些标准之间往往不协调，甚至是相互且这些标准之间往往不协调，甚至是相互冲突的例如，在资源的最优利用问题中冲突的例如，在资源的最优利用问题中，除了考虑所得的利润最大，还要考虑使，除了考虑所得的利润最大，还要考虑使生产的产品质量好，劳动生产率高，对市生产的产品质量好，劳动生产率高，对市场
2、的适应性强等等场的适应性强等等统计教研室统计教研室 刘莲花刘莲花 目标规划正是在线性规划的基础上为目标规划正是在线性规划的基础上为适应这种复杂的多目标最优决策的需要，而适应这种复杂的多目标最优决策的需要，而发展起来的发展起来的统计教研室统计教研室 刘莲花刘莲花 统计教研室统计教研室 刘莲花刘莲花第第4页页 为了具体说明目标规划与线性规划在处理问题为了具体说明目标规划与线性规划在处理问题方法上的区别，首先通过例子来介绍目标规划的概方法上的区别，首先通过例子来介绍目标规划的概念及数学模型。念及数学模型。统计教研室统计教研室 刘莲花刘莲花第第5页页例例1： 某工厂生产某工厂生产 I、II 两种产品，
3、已知有关数据两种产品，已知有关数据如下表所示。试求获利最大的生产方案。如下表所示。试求获利最大的生产方案。原材料（原材料（kg）设备（设备（h）利润（元利润（元/件）件）I218II1210拥有量拥有量1110统计教研室统计教研室 刘莲花刘莲花第第6页页解：设解：设 x1、x2 分别表示产品分别表示产品 I、II 的产量，则建立的产量，则建立问题的线性规划模型为：问题的线性规划模型为：0,102 11 2 .108 max21212121xxxxxxtsxxz用图解法求得最优决策方案为：用图解法求得最优决策方案为： x1=4，x2 =3，z=62。统计教研室统计教研室 刘莲花刘莲花第第7页页假
4、设要求决策人员制定生产方案时考虑如下意见：假设要求决策人员制定生产方案时考虑如下意见：1、由于产品、由于产品 I 销售有下降趋势，故销售有下降趋势，故希望希望产品产品 I 的产的产 量量尽量尽量不超过产品不超过产品 II 的产量的产量。2、超过计划供应的原材料时要高价采购，会使成、超过计划供应的原材料时要高价采购，会使成 本增加本增加。3、尽可能尽可能充分利用设备台时，但充分利用设备台时，但不希望不希望加班加班。4、尽可能达到尽可能达到并并超过超过计划利润指标计划利润指标56元。元。统计教研室统计教研室 刘莲花刘莲花第第8页页 类似上述这样存在多个目标的多目标决策问题，类似上述这样存在多个目标
5、的多目标决策问题，称为称为目标规划问题目标规划问题。统计教研室统计教研室 刘莲花刘莲花 对于多目标问题，线性规划很难为其找到最优对于多目标问题，线性规划很难为其找到最优方案极有可能出现：方案极有可能出现：就是说很难找到一个方案使所有目标同就是说很难找到一个方案使所有目标同时达到最优，特别当约束条件中有矛盾方程时，线时达到最优，特别当约束条件中有矛盾方程时，线性规划方法是无法解决的实践中，人们转而采取性规划方法是无法解决的实践中，人们转而采取“不求最好，但求不求最好，但求满意满意”的策略，在线性规划的基的策略，在线性规划的基础上建立一种新的数学规划方法础上建立一种新的数学规划方法目标规划目标规划
6、 统计教研室统计教研室 刘莲花刘莲花第第10页页1. 偏差变量偏差变量正偏差变量：表示决策值超过目标值的部分，记为正偏差变量：表示决策值超过目标值的部分，记为 d+ ；负偏差变量：表示决策值未达到目标值的部分，记为负偏差变量：表示决策值未达到目标值的部分，记为d- 。二二. .目标规划数学模型的基本概念目标规划数学模型的基本概念统计教研室统计教研室 刘莲花刘莲花第第11页页因为决策值不可能既超过目标值，同时又未达到目因为决策值不可能既超过目标值，同时又未达到目标值，所以标值，所以 d+ 和和 d- 存在如下关系：存在如下关系：（1）d+ 0，d - = 0（决策值超过目标值）（决策值超过目标值
7、）（2） d - 0，d + = 0（决策值未达到目标值）（决策值未达到目标值）（3） d + = d - = 0（决策值等于目标值）（决策值等于目标值）统计教研室统计教研室 刘莲花刘莲花第第12页页2. 绝对约束和目标约束绝对约束和目标约束（1）绝对约束绝对约束：必须严格满足的约束条件。：必须严格满足的约束条件。绝对约束是硬约束，不能满足这些约束条件的解为非绝对约束是硬约束，不能满足这些约束条件的解为非可行解。可行解。如：线性规划问题中的所有约束条件都是如：线性规划问题中的所有约束条件都是绝对约束绝对约束。统计教研室统计教研室 刘莲花刘莲花第第13页页（2）目标约束目标约束：目标约束是目标规
8、划特有的。：目标约束是目标规划特有的。目标约束是软约束，在达到此目标值时允许发生正目标约束是软约束，在达到此目标值时允许发生正偏差或负偏差，因此在这些约束的左端要加入正偏偏差或负偏差，因此在这些约束的左端要加入正偏差、负偏差变量；其约束右端项是要追求的目标值。差、负偏差变量；其约束右端项是要追求的目标值。Page 14统计教研室统计教研室 刘莲花刘莲花 对有严格限制的资源使用建立绝对约束，数学形对有严格限制的资源使用建立绝对约束，数学形式同线性规划中的约束条件式同线性规划中的约束条件12416 , 412xx 对不严格限制的资源，可通过目标约束来表达。对不严格限制的资源，可通过目标约束来表达。
9、对于前例中的原材料，若用绝对约束则有：对于前例中的原材料，若用绝对约束则有：122 11xx若用目标约束则有：若用目标约束则有：122 11xxdd统计教研室统计教研室 刘莲花刘莲花第第15页页3. 优先因子优先因子(优先等级优先等级)和权系数和权系数一个规划问题常常有若干个目标，决策者要求达到一个规划问题常常有若干个目标，决策者要求达到这些目标时，有主次或轻重缓急的不同。这些目标时，有主次或轻重缓急的不同。这种不同目标的主次轻重差别有两种：这种不同目标的主次轻重差别有两种：绝对的差别：绝对的差别：优先因子优先因子不同不同相对的差别：相对的差别：权系数不同权系数不同统计教研室统计教研室 刘莲花
10、刘莲花第第16页页（1 1）优先因子）优先因子优先因子用优先因子用 Pk 来表示。来表示。只有在高级优先因子对应的目标已满足的基础上，只有在高级优先因子对应的目标已满足的基础上，才能考虑低级优先因子对应的目标；才能考虑低级优先因子对应的目标；在考虑低级优先因子对应的目标时，绝对不允许违在考虑低级优先因子对应的目标时，绝对不允许违背已经满足的高级优先因子对应的目标。背已经满足的高级优先因子对应的目标。统计教研室统计教研室 刘莲花刘莲花第第17页页优先因子间的关系为：优先因子间的关系为： Pk Pk+1Pk 对应的目标比对应的目标比 Pk+1 对应的目标具有绝对的优先性对应的目标具有绝对的优先性.
11、注意：注意：目标规划问题中，通常把绝对约束作为最高优目标规划问题中，通常把绝对约束作为最高优先级来考虑先级来考虑。统计教研室统计教研室 刘莲花刘莲花第第18页页（2）权系数）权系数权系数用权系数用 j 来表示。来表示。多个目标具有相同的优先因子时，它们的重要性可多个目标具有相同的优先因子时，它们的重要性可用权系数的不同来表示。用权系数的不同来表示。权系数的确定由决策者按具体情况而定。权系数的确定由决策者按具体情况而定。统计教研室统计教研室 刘莲花刘莲花第第19页页4. 目标规划的目标函数目标规划的目标函数目标规划的目标函数又称为目标规划的目标函数又称为准则函数准则函数或或达成函数达成函数。目标
12、规划的目标函数由各目标约束的偏差变量、各目标规划的目标函数由各目标约束的偏差变量、各目标约束相应的优先因子、各目标约束相应的权系目标约束相应的优先因子、各目标约束相应的权系数共同构成。数共同构成。统计教研室统计教研室 刘莲花刘莲花第第20页页当每一目标值确定后，决策者要求尽可能缩小偏离当每一目标值确定后，决策者要求尽可能缩小偏离目标值，所以目标规划的目标函数只能是极小化，目标值，所以目标规划的目标函数只能是极小化，其基本形式有三种：其基本形式有三种：统计教研室统计教研室 刘莲花刘莲花第第21页页（1）希望希望恰好达到目标值。恰好达到目标值。这时，决策值超过目标值或不足目标值都是不希望这时，决策
13、值超过目标值或不足目标值都是不希望的，即正、负偏差变量都要尽可能地小：的，即正、负偏差变量都要尽可能地小：)( min ddfz统计教研室统计教研室 刘莲花刘莲花第第22页页（2）希望希望不超过目标值。不超过目标值。这时，允许达不到目标值，但不希望超过目标值，这时，允许达不到目标值，但不希望超过目标值，即正偏差变量要尽可能地小：即正偏差变量要尽可能地小：)( min dfz统计教研室统计教研室 刘莲花刘莲花第第23页页（3）希望希望不低于目标值。不低于目标值。这时，允许超过目标值，但不希望低于目标值，即这时，允许超过目标值，但不希望低于目标值，即负偏差变量要尽可能地小：负偏差变量要尽可能地小：
14、)( min dfz统计教研室统计教研室 刘莲花刘莲花第第24页页例例2：在例：在例1中原材料供应受严格限制的基础上考虑：中原材料供应受严格限制的基础上考虑：1. 首先首先由于产品由于产品 I 销售疲软，故希望产品销售疲软，故希望产品 I 的产量的产量 不超过不超过产品产品 II 的产量；的产量；3. 其次其次尽可能尽可能充分利用充分利用设备台时，但不加班设备台时，但不加班4. 再次再次利润额利润额不小于不小于56 元。元。统计教研室统计教研室 刘莲花刘莲花第第25页页 原材料供应严格限制；原材料供应严格限制；11221 xx统计教研室统计教研室 刘莲花刘莲花第第26页页1. 由于产品由于产品
15、 I 销售疲软，故希望产品销售疲软，故希望产品 I 的产量的产量不超不超过过产品产品 II 的产量；的产量；01121 ddxx 11mindPz统计教研室统计教研室 刘莲花刘莲花第第27页页2、尽可能、尽可能充分利用充分利用设备台时设备台时，但不加班；但不加班；1022221 ddxx)(min222 ddPz统计教研室统计教研室 刘莲花刘莲花第第28页页3. 利润额利润额不小于不小于 56 元。元。 33mindPz561083321 ddxx统计教研室统计教研室 刘莲花刘莲花第第29页页从而建立问题的模型如下：从而建立问题的模型如下： 3,2,1,0,5610810 2 0 11 2 .
16、)(min21332122211121213322211iddxxddxxddxxddxxxxtsdPddPdPzii统计教研室统计教研室 刘莲花刘莲花第第30页页模型亦可表述为：模型亦可表述为： 3,2,1,0,5610810 2 0 11 2 .),(,min21332122211121213322211iddxxddxxddxxddxxxxtsdPddPdPii统计教研室统计教研室 刘莲花刘莲花31甲产品甲产品乙产品乙产品可利用资源可利用资源原材料原材料2 23 3100 100 吨吨加工时间加工时间4 42 2120120时时单位利润单位利润6 64 4百元百元 练习练习：某企业生产甲
17、、乙两种产品，数据见下表某企业生产甲、乙两种产品，数据见下表：1P利利润润尽尽量量达达到到280280百百元元；PP2 23 3钢钢材材不不超超过过100100吨吨 工工时时不不超超过过120120小小时时应应如如何何安安排排生生产产？统计教研室统计教研室 刘莲花刘莲花32甲产品甲产品乙产品乙产品可利用资源可利用资源原材料原材料2 23 3100 100 吨吨加工时间加工时间4 42 2120120时时单位利润单位利润6 64 4百元百元 例例2：某企业生产甲、乙两种产品，数据见下表某企业生产甲、乙两种产品，数据见下表：1P利利润润达达280280百百元元；P2 2钢钢材材不不超超过过1001
18、00吨吨，工工时时不不超超过过120120小小时时。（权权数数之之比比5 5：1)1)应应如如何何安安排排生生产产？统计教研室统计教研室 刘莲花刘莲花331P利利润润达达280280百百元元；P2 2钢钢材材不不超超过过100100吨吨，工工时时不不超超过过120120小小时时。（权权数数之之比比5 5：1)1)iixxddxxddxxddxxddi 12111222123312642802310042120,0(1,2,3)约束方程11223min(5)zPdPdd目目标标函函数数：10d 20d 30d 依依权权数数综综合合目目标标得得：解：设生产甲、乙产品各解：设生产甲、乙产品各12,x
19、 x 件件统计教研室统计教研室 刘莲花刘莲花第第34页页目标规划的一般数学模型为：目标规划的一般数学模型为： KkddxbxaKkgddxctsddPzkkjinjjijknjkkjkjKkklkklkLll,.,1,0,0),(,.,1, .)(min1111 统计教研室统计教研室 刘莲花刘莲花1） 列出全部的约束条件列出全部的约束条件2） 把要达到指标的约束不等式加上正、负偏差变把要达到指标的约束不等式加上正、负偏差变量后化为目标约束等式量后化为目标约束等式3） 对目标赋予相应的优先因子对目标赋予相应的优先因子4） 对同一级优先因子中的各偏差变量，若重要程对同一级优先因子中的各偏差变量，若
20、重要程度不同时，可赋予不同的加权系数度不同时，可赋予不同的加权系数5） 构造一个按优先因子及加权系数和对应的目标构造一个按优先因子及加权系数和对应的目标偏差变量所要实现最小化的目标函数偏差变量所要实现最小化的目标函数统计教研室统计教研室 刘莲花刘莲花第第36页页 对于具有对于具有两个决策变量两个决策变量的目标规划的数学模型的目标规划的数学模型可以用图解法来分析求解。可以用图解法来分析求解。1. 在平面直角坐标系内画出由在平面直角坐标系内画出由绝对约束绝对约束和和非负条件非负条件所组成的公共取值范围。所组成的公共取值范围。统计教研室统计教研室 刘莲花刘莲花第第37页页2. 按优先因子的高低，依次
21、在平面直角坐标系内画出按优先因子的高低，依次在平面直角坐标系内画出目标约束目标约束所组成的公共取值范围：所组成的公共取值范围：（1）令正负偏差变量等于）令正负偏差变量等于0，画出所有的约束直线；，画出所有的约束直线；（2）在直线旁标出正、负偏差变量所示方向。）在直线旁标出正、负偏差变量所示方向。（3）正负偏差变量表示直线可以沿正、负偏差变量）正负偏差变量表示直线可以沿正、负偏差变量所示方向平移。所示方向平移。3. 根据目标函数中的优先因子来分析求解。根据目标函数中的优先因子来分析求解。统计教研室统计教研室 刘莲花刘莲花第第38页页 3,2,1,0,56108102 0 11 2 .)(min2
22、1332122211121213322211iddxxddxxddxxddxxxxtsdPddPdPzii统计教研室统计教研室 刘莲花刘莲花第第39页页解：解：x2x11. 画出画出绝对约束绝对约束和和非负条件非负条件所围成的取值范围。所围成的取值范围。O11221 xxAB统计教研室统计教研室 刘莲花刘莲花第第40页页2. 画出目标约束所围成的取值范围。画出目标约束所围成的取值范围。01121 ddxx 1112ddxxx2 轴上的截距轴上的截距统计教研室统计教研室 刘莲花刘莲花第第41页页x2x1O 1d 1dBAC 偏差变量在画直线取为偏差变量在画直线取为0，直线画好后，在该直线，直线画
23、好后，在该直线上标上标出目标函数中与该直线相关的偏差变量增大时直线的平移方向出目标函数中与该直线相关的偏差变量增大时直线的平移方向（用垂直于直线的箭头来反映）（用垂直于直线的箭头来反映）统计教研室统计教研室 刘莲花刘莲花第第42页页1022221 ddxx 22122121521ddxxx2 轴上的截距轴上的截距统计教研室统计教研室 刘莲花刘莲花第第43页页x2x1O 1d 1d 2d 2dABECD统计教研室统计教研室 刘莲花刘莲花第第44页页561083321 ddxx 331210110152854ddxxx2 轴上的截距轴上的截距统计教研室统计教研室 刘莲花刘莲花第第45页页x2x1O
24、 1d 1d 2d 2d 3d 3dBACEDFGJ统计教研室统计教研室 刘莲花刘莲花第第46页页3. 根据目标函数中的优先因子来分析求解。根据目标函数中的优先因子来分析求解。 11mindPz表示直线表示直线 左上角的部分，左上角的部分，此时满足此时满足021 xx从而公共取值范围为：从而公共取值范围为：OBC（1）01 d统计教研室统计教研室 刘莲花刘莲花第第47页页x2x1O 1d 1d 2d 2d 3d 3dBACEDFGJ统计教研室统计教研室 刘莲花刘莲花第第48页页)(min222 ddPz表示直线表示直线 上的部分，上的部分，此时满足此时满足10221 xx从而公共取值范围为：线
25、段从而公共取值范围为：线段 E D（2）022 dd统计教研室统计教研室 刘莲花刘莲花第第49页页x2x1O 1d 1d 2d 2d 3d 3dBACEDFGJ统计教研室统计教研室 刘莲花刘莲花第第50页页 33mindPz（3）表示直线表示直线 的右上角部分，的右上角部分，此时满足此时满足5610821 xx从而公共取值范围为：线段从而公共取值范围为：线段 G D03 d统计教研室统计教研室 刘莲花刘莲花第第51页页x2x1O 1d 1d 2d 2d 3d 3dBACEDFGJ统计教研室统计教研室 刘莲花刘莲花第第52页页可求得：可求得：G 的坐标为的坐标为：（：（2，4）D 的坐标为的坐标
26、为：（：（10/3，10/3）G 和和 D 的凸组合均是目标规划问题的解。的凸组合均是目标规划问题的解。统计教研室统计教研室 刘莲花刘莲花第第53页页在本例中，依次先后次序满足了：在本例中，依次先后次序满足了：03 d01 d022 dd因而因而 z * = 0 ，问题的最终解是最优解。，问题的最终解是最优解。 但在大多数问题中并非如此，会出现某些约但在大多数问题中并非如此，会出现某些约束得不到满足，故将目标规划问题的最优解称为束得不到满足，故将目标规划问题的最优解称为满意解。满意解。所所有有目目标标都都达达到到的的方方案案称称为为最最优优方方案案, ,否否则则, ,称称为为次次优优或或满满意
27、意方方案案。统计教研室统计教研室 刘莲花刘莲花由决策变量绘画所有约束条件的直线图形，偏差由决策变量绘画所有约束条件的直线图形，偏差 变量以平移直线的方法加以考虑变量以平移直线的方法加以考虑 重复第重复第3、4步过程，直到解区域步过程，直到解区域Ri 减少到一点或减少到一点或 满足了所有满足了所有k个级别的目标为止，此时个级别的目标为止，此时Rk 即为最即为最 优解区域，其中的任何一点均为目标规划满意解优解区域，其中的任何一点均为目标规划满意解 对对P1级的各目标，确定解区域级的各目标，确定解区域R1对下一个优先级别对下一个优先级别Pi 级各目标，确定它的最优解级各目标，确定它的最优解 空间空间
28、Ri ，但必须是，但必须是Ri Ri-1 ( i = 2, 3, ) 在这个过程中，如果某解区域在这个过程中，如果某解区域Ri 减小到一点，则减小到一点，则 结束，因为此时没有进一步改进的可能结束，因为此时没有进一步改进的可能统计教研室统计教研室 刘莲花刘莲花知知识识回回顾顾1、目目标标规规划划的的数数学学模模型型的的建建立立正正负负偏偏差差变变量量、目目标标约约束束、优优先先因因子子和和权权系系数数目目标标规规划划的的目目标标函函数数2、目目标标规规划划的的数数学学模模型型的的图图解解法法最最优优解解、满满意意解解统计教研室统计教研室 刘莲花刘莲花第第56页页例例3：某电视机厂装配黑白和彩色
29、两种电视机。：某电视机厂装配黑白和彩色两种电视机。每周市场的黑白电视机销量为每周市场的黑白电视机销量为 30 台，每台可获利台，每台可获利 40元；元；每周市场的彩色电视机销量为每周市场的彩色电视机销量为 24 台，每台可获利台，每台可获利 80元。元。每装配一台电视机需占用装配线每装配一台电视机需占用装配线 1 小时，装配线每小时，装配线每周计划开动周计划开动 40 小时。小时。统计教研室统计教研室 刘莲花刘莲花第第57页页该厂确定的目标为：该厂确定的目标为：第一优先级：第一优先级：充分利用充分利用装配线每周计划开动时间装配线每周计划开动时间 40 小时；小时；第二优先级：允许装配线加班，但
30、加班时间每周尽第二优先级：允许装配线加班，但加班时间每周尽量量不超过不超过 10 小时；小时；第三优先级：装配电视机数量第三优先级：装配电视机数量尽量满足尽量满足市场需求量。市场需求量。因彩色电视机利润高，取其权系数为因彩色电视机利润高，取其权系数为 2 。建立问题模型，并求解黑白和彩色电机机产量？建立问题模型，并求解黑白和彩色电机机产量？统计教研室统计教研室 刘莲花刘莲花第第58页页1. 充分利用充分利用装配线每周计划开动时间装配线每周计划开动时间 40 小时：小时：401121 ddxx 11mindPz解：解：设设 x1、x2 分别表示彩色和黑白电视机产量。分别表示彩色和黑白电视机产量。
31、统计教研室统计教研室 刘莲花刘莲花第第59页页2. 允许装配线加班，但加班时间每周尽量允许装配线加班，但加班时间每周尽量不超过不超过 10 小时：小时：502221 ddxx 22mindPz统计教研室统计教研室 刘莲花刘莲花第第60页页3. 装配彩色电视机数量装配彩色电视机数量尽量满足尽量满足市场需求量，且市场需求量，且权系数为权系数为 2 ：24331 ddx)2(min33 dPz统计教研室统计教研室 刘莲花刘莲花第第61页页 43mindPz4. 装配黑白电视机数量装配黑白电视机数量尽量满足尽量满足市场需求量，且市场需求量，且权系数为权系数为 1 ：30442 ddx统计教研室统计教研
32、室 刘莲花刘莲花第第62页页从而建立问题的模型如下：从而建立问题的模型如下： 4,3,2,1,0,30 24 5040 .)2(min21442331222111214332211iddxxddxddxddxxddxxtsddPdPdPzii统计教研室统计教研室 刘莲花刘莲花第第63页页 1d 1dx2x1 2d 2dABCDO5040 min222111212211 ddxxddxxdPdPz120,0dd统计教研室统计教研室 刘莲花刘莲花第第64页页 1d 1dx2x1 2d 2dABCDO24)2( min33133 ddxdPz 3d 3dEF123000ddd 统计教研室统计教研室
33、刘莲花刘莲花第第65页页 1d 1dx2x1 2d 2dABCDO 4d 4d 3d 3dGHEF30)( min44243 ddxdPz统计教研室统计教研室 刘莲花刘莲花第第66页页在在 ABEF 中无法满足：中无法满足：04 d所以只能在所以只能在 ABEF 中取一点，使中取一点，使 尽可能小。尽可能小。 4d在在 ABEF 中只有取中只有取 E 点才可使点才可使 最小。最小。 4d故故 E 点为为满意解，点为为满意解，E =（24，26）。）。统计教研室统计教研室 刘莲花刘莲花第第67页页 1d 1dx2x1 2d 2dABCDO 4d 4d 3d 3dGHEF统计教研室统计教研室 刘莲
34、花刘莲花第第68页页分析：分析：此例中约束此例中约束)( min43 dPz没有得到满足。没有得到满足。问题的最终解只是满意解而不是最优解。问题的最终解只是满意解而不是最优解。30442 ddx统计教研室统计教研室 刘莲花刘莲花6911223341211122213324412min()510100214610,0,(1,2,3,4)iizPdP dP ddxxddxxddxddxddx x ddi 图图解解下下列列目目标标练练习习1 1：规规划划问问题题统计教研室统计教研室 刘莲花刘莲花70101401x2x1d 2d 2d 3d 4d 7201d 64d 3d 图图（1 1）1211122
35、2133244510100214610 xxddxxddxddxdd 1min0d 2min0d 3min0d 4min0d 1122334min()zPdP dP dd可可行行域域在在第第象象限限统计教研室统计教研室 刘莲花刘莲花71101401x2x1d 2d 2d 3d 4d 7201d 64d 3d 图图（2）2）1min0d 2d P1 1满满足足 目目标标的的可可行行域域在在阴阴影影部部分分1122334min()zPdP dP dd统计教研室统计教研室 刘莲花刘莲花72101401x2x2d 2d 3d 4d 7201d 64d 3d 图图（3）3）2d P2 2再再满满足足 目
36、目标标的的可可行行域域在在阴阴影影部部分分2min0d 1min0d 1122334min()zPdP dP dd统计教研室统计教研室 刘莲花刘莲花73101401x2x2d 3d 4d 7201d 64d 3d 图图（4）4）2min0d 1min0d 4min0d 4d d 3min0于于是是原原问问题题有有无无穷穷次次优优解解：3min0d 若若强强调调 ，则则无无最最优优解解。三三个个顶顶点点的的线线性性组组合合P3 3再再满满足足部部分分目目标标的的可可行行域域在在阴阴影影部部分分1122334min()zPdP dP dd统计教研室统计教研室 刘莲花刘莲花7412111222123
37、312642802310042120,0(1,2,3)iixxddxxddxxddxxddi 约约束束方方程程11223min(5)zPdPdd目目标标函函数数：图图解解目目标标规规练练习习2 2：划划问问题题：统计教研室统计教研室 刘莲花刘莲花7510036001x2x1d 2d 2d 3d 50301d 14033d 70图图（1 1）121112221233642802310042120 xxddxxddxxdd 可可行行域域在在第第象象限限11223min(5)zPdPdd10d - -P1 1满满足足 目目标标的的可可行行域域在在阴阴影影部部分分统计教研室统计教研室 刘莲花刘莲花76
38、10036001x2x2d 3d 50301d 14033d 70(44,4)P第第二二个个目目标标要要求求：2300dd，权权数数5/15/13(44,2) ,64.TXd 无无最最优优，但但有有满满意意解解：其其实实有有无无穷穷次次优优解解。图图（2 2）P2 2满满足足部部分分目目标标的的可可行行域域在在阴阴影影11223min(5)zPdPdd20d +30d +统计教研室统计教研室 刘莲花刘莲花77 3,2,1,0,56108102 0 11 2 .)(min21332122211121213322211iddxxddxxddxxddxxxxtsdPddPdPzii目目标标规规划划的
39、的数数学学模模型型统计教研室统计教研室 刘莲花刘莲花783第第 节节解解目目标标规规划划的的单单纯纯形形法法 目目标标规规划划与与线线性性规规划划数数学学模模型型没没有有本本质质的的区区别别, ,所所以以可可以以用用单单纯纯形形方方法法解解决决目目标标规规划划问问题题。j0min 注注意意事事项项：（1 1）目目标标函函数数为为问问题题，则则最最优优准准则则为为；123.PPP（2 2）目目标标函函数数中中非非基基变变量量的的检检验验数数（系系数数）含含有有优优先先因因子子，应应考考虑虑因因素素。统计教研室统计教研室 刘莲花刘莲花79解解目目标标规规划划问问题题的的单单纯纯形形法法的的计计算算
40、步步骤骤：Kk=11 1、建建立立初初始始单单纯纯形形表表，在在表表中中将将检检验验数数行行按按优优先先因因子子 个个数数分分别别列列成成行行，置置k-12 2、检检查查该该行行中中是是否否存存在在负负数数，且且对对应应的的前前行行的的系系数数 是是0 0，若若有有负负数数取取其其中中最最小小者者对对应应的的变变量量为为换换入入变变量量， 转转(3),(3),若若无无负负数数，则则转转(5)(5)3 3、按按最最小小比比值值规规则则确确定定换换出出变变量量，当当存存在在两两个个和和两两个个 以以上上的的最最小小比比值值时时选选取取具具有有较较高高优优先先等等级级的的变变量量为为 换换出出变变量
41、量。4 4、按按单单纯纯形形法法进进行行基基变变换换运运算算，建建立立新新的的表表，返返回回(2)(2)k=k+1(2)5 5、当当k=Kk=K时时，计计算算结结束束，表表中中的的解解即即为为满满意意解解，否否则则置置 ，返返回回统计教研室统计教研室 刘莲花刘莲花8012121112221233122110.21081056,0,(1,2,3)iixxxxdds txxddxxddxxddi 1122233min()zPdP ddP dSx对对第第一一个个方方程程引引入入松松弛弛变变量量后后，列列初初始始单单纯纯形形表表：用用单单纯纯形形法法解解下下列列目目标标规规例例4 4划划问问题题：统计
42、教研室统计教研室 刘莲花刘莲花81122312112233122331230000001121100000000110110000101200011005681000000110000100001200002008100000001jBBSSCPPPPCXbxxxddddddxdPdPdPPP 1BC CB A jjC z 11110 256 10表表4-14-11122233min()zPdP ddP d统计教研室统计教研室 刘莲花刘莲花82122312112233123312300000063 201001 21 200053 200111 21 200051 210001 21 2006
43、300005511000010000000001100300005501jBBSSCPPPPCXbxxxddddddxdxPdPPP 1BC CB A jjCz 表表 4 4- -2 2410 3102统计教研室统计教研室 刘莲花刘莲花83122312112233121123000000300100221 21 260200011331 21 2404010004 34 31 61 62402100005 35 31 31 3000010000000001100000000010jBBSSCPPPPCXbxxxddddddxdxxPPP 1BCC B A jjCz 表表 4 4- -3 31(
44、2,4,3) ,2TXd此此表表为为最最优优表表：，利利润润5656百百元元。所所有有的的目目标标都都已已达达到到。 甲甲产产品品的的产产量量小小于于乙乙产产品品2 2个个单单位位。统计教研室统计教研室 刘莲花刘莲花84判判断断迭迭代代是是否否停停止止的的准准侧侧：11,kPP、检检验验数数行行的的所所有有值值都都是是非非负负1ii+122,PPPP、若若行行所所有有检检验验数数为为非非负负，第第行行仍仍存存在在 负负的的检检验验数数，但但负负的的检检验验数数所所在在列列的的上上面面行行中中 有有正正的的检检验验数数。即即：从从行行起起，虽虽然然在在某某一一行行存存在在负负的的检检验验数数，但
45、但该该负负检检验验数数同同列列较较高高优优先先级级的的行行中中存存在在有有正正的的检检验验数数，计计算算就就停停止止。85123121122331223312300000010111100006012211001602100011000100000122010003100001jBBCPPPCXbxxddddddxPdPdPPP 1BCC B A -表表 4 4 4 4统计教研室统计教研室 刘莲花刘莲花第第86页页 目标规划的灵敏度分析方法与线性规划相似，目标规划的灵敏度分析方法与线性规划相似，除了分析各项系数的变化之外，还有优先因子和权除了分析各项系数的变化之外，还有优先因子和权系数的变化问
46、题。系数的变化问题。统计教研室统计教研室 刘莲花刘莲花第第87页页例：已知目标规划问题例：已知目标规划问题 4 , 3 , 2 , 1, 0,10 45 70 80 .)53()35(min2144133222111213234334211iddxxdddddxddxddxxtsddPddPdPdPzii统计教研室统计教研室 刘莲花刘莲花第第88页页最终单纯形表为最终单纯形表为cj00P105P33P33P35P30P2CBXBbx1x20 x2450100001-1000 x17010001-1000003500-111-11-100010000000001-1c j z jP1001000
47、0000P20000000001P30000533500 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d统计教研室统计教研室 刘莲花刘莲花第第89页页若第一个目标约束的右端项变为若第一个目标约束的右端项变为 120 ，原满意解发生，原满意解发生什么样的变化？什么样的变化？统计教研室统计教研室 刘莲花刘莲花第第90页页解：解： 10000111001001001B 00040b 040001bB统计教研室统计教研室 刘莲花刘莲花第第91页页 bBb1 10570450400010357045将其反映到最终单纯形表中：将其反映到最终单纯形表中： 统计教研室统计教研室 刘莲花刘莲花第第9
48、2页页cj00P105P33P33P35P30P2CBXBbx1x20 x2450100001-1000 x17010001-100000-500-111-11-100010000000001-1c j z jP10010000000P20000000001P30000533500 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d即出现了第三种情况（原问题不可行，对偶问题可行），利即出现了第三种情况（原问题不可行，对偶问题可行），利用对偶单纯形法求解：用对偶单纯形法求解： 统计教研室统计教研室 刘莲花刘莲花第第93页页cj00P105P33P33P35P30P2CBXBbx1x20
49、x2450100001-1000 x17010001-100000-500-111-11-100010000000001-1c j z jP10010000000P20000000001P30000533500 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d333133135,3,min15,13,1minPPPPPPP 统计教研室统计教研室 刘莲花刘莲花第第94页页cj00P105P33P33P35P30P2CBXBbx1x20 x2450100001-1000 x17010001-100000-500-111-11-100010000000001-1c j z jP100100
50、00000P20000000001P30000533500 1d 1d 2d 2d 3d 3d 4d 4d 1d 4d统计教研室统计教研室 刘莲花刘莲花第第95页页cj00P105P33P33P35P30P2CBXBbx1x20 x2450100001-1000 x175101-100-11003P35001-1-11-1100010000000001-1c j z jP10010100000P20000000001P300-33806200 1d 1d 2d 2d 3d 3d 4d 4d 4d 2d统计教研室统计教研室 刘莲花刘莲花第第96页页得到问题的满意解为：得到问题的满意解为：)45,