目标规划求解方法PPT讲稿.ppt

《目标规划求解方法PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《目标规划求解方法PPT讲稿.ppt（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、目标规划求解方法第1页，共33页，编辑于2022年，星期日1.1.序列法序列法n序列法的基本思想和方法序列法的基本思想和方法n序列法的迭代步骤序列法的迭代步骤n序列法的评价序列法的评价 二二.线性目标规划的求解方法：线性目标规划的求解方法：第六章第六章 多目标规划多目标规划第2页，共33页，编辑于2022年，星期日1.1.序列法序列法基本思想：基本思想：n目标规划通过引入偏差变量将各级目标转化成目标约束，目标规划通过引入偏差变量将各级目标转化成目标约束，再极小化偏差变量来实现各级目标。当偏差变量达到极小再极小化偏差变量来实现各级目标。当偏差变量达到极小值值0时，该级目标被完全实现。时，该级目标

2、被完全实现。n序列法序列法是按照是按照优先级别优先级别去极小化各级目标的偏差变量去极小化各级目标的偏差变量的，即极小化该级目标偏差变量是在的，即极小化该级目标偏差变量是在不破坏上级目标不破坏上级目标已经达到的最优值已经达到的最优值的前提下进行的，所以该级目标的偏的前提下进行的，所以该级目标的偏差变量未必能达到极小值差变量未必能达到极小值0。那么该级目标偏差变量极小。那么该级目标偏差变量极小化的程度就是该级目标在不破坏前级目标最优值的前提下化的程度就是该级目标在不破坏前级目标最优值的前提下被实现的程度。被实现的程度。多目标规划6-4第3页，共33页，编辑于2022年，星期日例例6-76-7具体方

3、法：具体方法：序列法按照目标函数中各目标的序列法按照目标函数中各目标的优先级别优先级别,顺序将目标规划分解为一顺序将目标规划分解为一系列单目标的线性规划系列单目标的线性规划,用单纯形法逐一求解用单纯形法逐一求解.在求解过程中确定进基在求解过程中确定进基变量变量,离基变量及主元的原则与线性规划的单纯形法相同离基变量及主元的原则与线性规划的单纯形法相同,不同的是不同的是要要以不影响较高级目标的最优值以不影响较高级目标的最优值为前提求解较低级目标的最优值为前提求解较低级目标的最优值.如如此反复迭代此反复迭代,直到进行到最低级目标的目标函数达到最优为止直到进行到最低级目标的目标函数达到最优为止.301

4、11=-+-ddx多目标规划6-4第4页，共33页，编辑于2022年，星期日1.1.序列法序列法n序列法的基本思想和方法序列法的基本思想和方法n序列法的迭代步骤序列法的迭代步骤n序列法的评价序列法的评价 二二.线性目标规划的求解方法：线性目标规划的求解方法：第六章第六章 多目标规划多目标规划第5页，共33页，编辑于2022年，星期日例例6-76-7迭代步骤迭代步骤:30111=-+-ddx(1)建立建立 P1 级目标的单目标线性规划：级目标的单目标线性规划：多目标规划6-4第6页，共33页，编辑于2022年，星期日例例6-76-7(1)建立建立P1 级的单目标线性规划：级的单目标线性规划：用单

5、纯形法求解：用单纯形法求解：对对 P1 级目标而言已是最优表。级目标而言已是最优表。所以所以 P1 级目标已被完全实现。级目标已被完全实现。多目标规划6-4第7页，共33页，编辑于2022年，星期日例例6-76-7迭代步骤迭代步骤:30111=-+-ddx(2)建立建立 P2 级目标的单目标线性规划：级目标的单目标线性规划：多目标规划6-4第8页，共33页，编辑于2022年，星期日例例6-76-7化简化简:(2)建立建立 P2 级目标的单目标线性规划：级目标的单目标线性规划：多目标规划6-4第9页，共33页，编辑于2022年，星期日例例6-76-7(2)建立建立P2 级的单目标线性规划：级的单

6、目标线性规划：用单纯形法求解：用单纯形法求解：对对 P2 级目标而言还未达到最优。级目标而言还未达到最优。经过两次单纯形法的迭代，可得最优表。经过两次单纯形法的迭代，可得最优表。多目标规划6-4第10页，共33页，编辑于2022年，星期日例例6-76-7最优表最优表4-5(2)建立建立P2 级的单目标线性规划：级的单目标线性规划：此时对此时对P2 级目标而言已达到最优。级目标而言已达到最优。所以所以P2 级目标未被完全实现，还差级目标未被完全实现，还差580。多目标规划6-4第11页，共33页，编辑于2022年，星期日例例6-76-7迭代步骤迭代步骤:30111=-+-ddx(3)建立建立 P

7、3 级目标的单目标线性规划：级目标的单目标线性规划：多目标规划6-4第12页，共33页，编辑于2022年，星期日例例6-76-7化简：化简：(3)建立建立 P3 级目标的单目标线性规划：级目标的单目标线性规划：由由P2 级目标的最优表级目标的最优表4-5，多目标规划6-4第13页，共33页，编辑于2022年，星期日例例6-76-7最优表最优表4-5(2)建立建立P2 级的单目标线性规划：级的单目标线性规划：基变量将会使基变量将会使P2 级目标已得的最优值级目标已得的最优值 minZ2=580的检验数的检验数分别是分别是8,12,1 0所以如果它们进基做所以如果它们进基做为了不使为了不使必须令这

8、些非基变量的取值永远为必须令这些非基变量的取值永远为 0多目标规划6-4第14页，共33页，编辑于2022年，星期日例例6-76-7化简：化简：(3)建立建立P3 级的单目标线性规划：级的单目标线性规划：由由P2 级目标的最优表级目标的最优表4-5，所以所以P3 级目标未被级目标未被完全实现。完全实现。多目标规划6-4第15页，共33页，编辑于2022年，星期日例例6-76-7迭代步骤迭代步骤30111=-+-ddx(4)建立建立 P4 级目标的单目标线性规划：级目标的单目标线性规划：所以所以P4 级目标已级目标已被完全实现。被完全实现。多目标规划6-4第16页，共33页，编辑于2022年，星

9、期日例例6-76-7最优解：最优解：最优值向量：最优值向量：结论：结论：P1,P4级目标已被完全实现级目标已被完全实现,P2,P3级目标未被完全实现。级目标未被完全实现。多目标规划6-4第17页，共33页，编辑于2022年，星期日1.1.序列法序列法n序列法的基本思想和方法序列法的基本思想和方法n序列法的迭代步骤序列法的迭代步骤n序列法的评价序列法的评价 二二.线性目标规划的求解方法：线性目标规划的求解方法：第六章第六章 多目标规划多目标规划第18页，共33页，编辑于2022年，星期日1.1.序列法序列法优点：优点：求解思路清晰，在整个求解过程中仅用到了我求解思路清晰，在整个求解过程中仅用到了

10、我们所熟悉的单纯形方法们所熟悉的单纯形方法.缺点：缺点：需要对每一级目标构造一个相应的单目标线性需要对每一级目标构造一个相应的单目标线性规划，然后去求解。对于级别较多的模型，迭规划，然后去求解。对于级别较多的模型，迭代次数多，计算量大。代次数多，计算量大。多目标规划6-4第19页，共33页，编辑于2022年，星期日第四节第四节 目标规划目标规划n线性目标规划的数学模型线性目标规划的数学模型n线性目标规划的求解方法线性目标规划的求解方法 n序列法序列法n多阶段法多阶段法n单纯形法单纯形法 第六章第六章 多目标规划多目标规划第20页，共33页，编辑于2022年，星期日2.2.单纯形法单纯形法n单纯

11、形法的基本思想单纯形法的基本思想n单纯形法的迭代步骤单纯形法的迭代步骤 二二.线性目标规划的求解方法：线性目标规划的求解方法：第六章第六章 多目标规划多目标规划第21页，共33页，编辑于2022年，星期日2.2.单纯形法单纯形法基本思想：基本思想：把目标中优先因子把目标中优先因子Pj 理解为一种特殊意义下的正常数，理解为一种特殊意义下的正常数，用用Pj 取代取代(LP)中的成本系数中的成本系数 cj,从而目标规划可以理解从而目标规划可以理解为一个标准的为一个标准的(LP)，然后用单纯形法求出它的最优解。，然后用单纯形法求出它的最优解。多目标规划6-4第22页，共33页，编辑于2022年，星期日

12、2.2.单纯形法单纯形法n单纯形法的基本思想单纯形法的基本思想n单纯形法的迭代步骤单纯形法的迭代步骤 二二.线性目标规划的求解方法：线性目标规划的求解方法：第六章第六章 多目标规划多目标规划第23页，共33页，编辑于2022年，星期日例例6-76-7多目标规划6-4第24页，共33页，编辑于2022年，星期日例例6-76-7表表1 1多目标规划6-4第25页，共33页，编辑于2022年，星期日例例6-76-7表表1 1P1 行检验数都行检验数都 当前的基本可行解对当前的基本可行解对P1级目标级目标已达最优，故检查已达最优，故检查P2行检验数。行检验数。所以所以 P1 级目标已被完全实现。级目标

13、已被完全实现。多目标规划6-4第26页，共33页，编辑于2022年，星期日表表1 1例例6-76-7P2 行有检验数行有检验数 当前的基本可行解对当前的基本可行解对P2级目标不级目标不是最优的。是最优的。x1 进基，进基，离基。离基。多目标规划6-4第27页，共33页，编辑于2022年，星期日表表2 2例例6-76-7P2 行检验数行检验数-12 0 所以所以 x2 进基，进基，离基。离基。P2行检验数行检验数-8 0不能进基。不能进基。多目标规划6-4第28页，共33页，编辑于2022年，星期日表表3 3例例6-76-7P2 行检验数行检验数-2 0，但，但P1 行相应的检验数为行相应的检验

14、数为1，不能进基。不能进基。P2 行检验数行检验数-6 0，进基进基,离基。离基。多目标规划6-4第29页，共33页，编辑于2022年，星期日表表4 4最优表最优表例例6-76-7当前基本可行解对当前基本可行解对 P2，P3，P4 级目标都已达到最优，所以级目标都已达到最优，所以是最优解。是最优解。多目标规划6-4第30页，共33页，编辑于2022年，星期日表表4 4最优表最优表最优解：最优解：最优目标值向量：最优目标值向量：例例6-76-7多目标规划6-4第31页，共33页，编辑于2022年，星期日2.2.单纯形法单纯形法n单纯形法的基本思想单纯形法的基本思想n单纯形法的迭代步骤单纯形法的迭代步骤 二二.线性目标规划的求解方法：线性目标规划的求解方法：第六章第六章 多目标规划多目标规划第32页，共33页，编辑于2022年，星期日第四节第四节 目标规划目标规划n线性目标规划的数学模型线性目标规划的数学模型n线性目标规划的求解方法线性目标规划的求解方法 n序列法序列法n多阶段法多阶段法n单纯形法单纯形法 第六章第六章 多目标规划多目标规划作业：作业：P296 9(2)P296 9(2)作业：作业：P242 9(2)P242 9(2)第33页，共33页，编辑于2022年，星期日