高等运筹第七讲课件

高等运筹学大连海事大学刘巍整理课件高等运筹学大连海事大学整理课件1第二篇运筹学中的数学规划第四章线性规划第五章非线性规划第六章锥规划、矩阵规划及变分不等式第七章整数规划第八章动态规划第九章向量优化（多目标优化）整理课件第二篇运筹学中的数学规划第四章线性规划整理课件2第七讲内容第九章向量优化

（多目标规划）整理课件第七讲内容第九章向量优化整理课件3第九章向量优化

（多目标规划）整理课件第九章向量优化

（多目标规划）整理课件4近几十年来向量优化(亦称多目标优化)理论研究有了迅猛发展，在各种解的存在性、稳定性以及最优性条件等方面获得了丰富的结果，并创造性地建立了向量优化问题解集的结构定理、连通性定理和稠密性定理，被应用到经济问题中。通过向量广义凸性的研究，很好地处理了一大类非线性向量优化问题;通过提出向量变分不等式模型，开拓了研究向量优化间题的新方向。整理课件近几十年来向量优化(亦称多目标优化)理论研究有了迅猛发展，在5由于向量优化中衡量向量“大小”的是不完全的偏序，致使大量的向量优化问题没有解，甚至在向量目标函数光滑并有下界的情况下没有数值优化意义下的近似解。由于任何优化间题算法每一步获得的迭代项都是该优化问题的一个近似解，因此研究向量优化问题近似解的存在性以及拉格朗日和卡罗青一库恩一塔克等优化性条件仍然是具有基础性作用的主要问题也是求解算法的有力保障。整理课件由于向量优化中衡量向量“大小”的是不完全的偏序，致使大量的向6分式向量优化问题是具有重要经济意义的数学模型，关于这类模型的求解问题，也是今后向量优化问题研究的重点.利用次微分，使用变分分析技术和方法研究非光滑向量优化问题，就变分分析和向量优化进行交叉研究仍将是未来很有生命力的方向.整理课件分式向量优化问题是具有重要经济意义的数学模型，关于这类模型的79.1基本概念解的概念

劣解：可淘汰的解。非劣解：没有其它解可以淘汰它们，但又非绝对最优解。单目标中：任何两个解都可以比较优劣，是完全有序的。多目标中：任何两个解不一定都可以比较出其优劣，因此只能是半序的。多目标优化的几类方法化多目标为单目标引进次序法直接求非劣解法f2(体重)●12●10●13●9●11●8●4●7●3●6●1●5●2

f1(身高)图3-1整理课件89.1基本概念解的概念f2(体重)整理课件8从线性规划问题可看出：线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度（即优先顺序）也不相同，有些目标之间往往相互发生矛盾。整理课件从线性规划问题可看出：整理课件9线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。整理课件线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际10求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。整理课件求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，11为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。整理课件为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛12

多目标规划问题多目标规划问题的提出在实际问题中，可能会同时考虑几个方面都达到最优：产量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。多目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。目标规划可根据实际情况，分主次地、轻重缓急地考虑问题。整理课件多目标规划问题整理课件13例9-1：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？整理课件例9-1：一个企业需要同一种原材料生产甲乙两种产品，它们的单14如何安排生产，使利润达到最大。用单纯形法求得最优解=（20，20）最优值=200（百元）整理课件如何安排生产，使利润达到最大。整理课件15问题：该厂提出如下目标（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；如何安排生产？整理课件问题：该厂提出如下目标整理课件16例9-2：某车间有A、B两条设备相同的生产线，它们生产同一种产品。A生产线每小时可制造2件产品，B生产线每小时可制造1.5件产品。如果每周正常工作时数为45小时，要求制定完成下列目标的生产计划：整理课件例9-2：某车间有A、B两条设备相同的生产线，它们生产同一种17（1）生产量达到210件/周；（2）A生产线加班时间限制在15小时内；（3）充分利用工时指标，并依A、B产量的比例确定重要性。整理课件（1）生产量达到210件/周；整理课件18例9-3：某电器公司经营的唱机和录音机均有车间A、B流水作业组装。数据见下表。要求按以下目标制订月生产计划：（1）库存费用不超过4600元；（2）每月销售唱机不少于80台；整理课件例9-3：某电器公司经营的唱机和录音机均有车间A、B流水作业19（3）不使A、B车间停工（权数由生产费用确定）；（4）A车间加班时间限制在20小时内；（5）每月销售录音机为100台；（6）两车间加班时数总和要尽可能小（权数由生产费用确定）；整理课件（3）不使A、B车间停工（权数由生产费用确定）；整理课件20整理课件整理课件21多目标优先级先将目标等级化：将目标按重要性的程度不同依次分成一级目标、二级目标…..。最次要的目标放在次要的等级中。整理课件多目标优先级整理课件22目标优先级作如下约定：对同一个目标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。整理课件目标优先级作如下约定：整理课件23目标优先级作如下约定：不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别的目标上的收获都不可弥补。所以在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。整理课件目标优先级作如下约定：整理课件24目标优先级作如下约定：同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可有其余目标的适当收获来弥补。整理课件目标优先级作如下约定：整理课件25多目标规划解的概念：若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解；若解只能满足部分目标，就称该解为多目标规划的次优解；若找不到满足任何一个目标的解，就称该问题为无解。整理课件多目标规划解的概念：整理课件26例9-4：（例9-1）一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？整理课件例9-4：（例9-1）一个企业需要同一种原材料生产甲乙两种产27如何安排生产，使利润达到最大。前面已经求得最优解=（20，20）最优值=200（百元）整理课件如何安排生产，使利润达到最大。整理课件28问题：该厂提出如下目标（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；如何安排生产？整理课件问题：该厂提出如下目标整理课件29对例4-1的问题，设超过一吨钢材与超过5个工时的损失相同。现有四个方案进行比较优劣？整理课件对例4-1的问题，设超过一吨钢材与超过5个工时的损失相同。现30目标：（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；对于（1），只有方案4没有完成。排除方案4。对于（2），只有方案2达到了，因此方案2是最优。整理课件目标：（1）利润达到280百元；（2）钢材不超过100吨，工31目标：（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；方案1与方案3都达到了（1），又没达到（2）方案1与（2）的差距：工时损失=（110-100）*5+（130-120）*1=60整理课件目标：（1）利润达到280百元；（2）钢材不超过100吨，工32方案3与（2）的差距：工时损失=0*5+（190-120）*1=70方案1优于方案3。方案2优于方案1优于方案3优于方案4整理课件方案3与（2）的差距：整理课件33例9-4：继续上例整理课件例9-4：继续上例整理课件34目标：（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；对于（1），三个方案都没有完成。但方案3离目标最远，方案3最差。方案1与（2）的差距：工时损失=（108-100）*5+（130-120）*1=50整理课件目标：（1）利润达到280百元；（2）钢材不超过100吨，工35方案2与（2）的差距：工时损失=0*5+（160-120）*1=40方案2优于方案1方案2优于方案1优于方案3整理课件方案2与（2）的差距：整理课件369-2多目标规划问题的数学模型多目标的处理为了将不同级别的目标的重要性用数量表示，引进P1，P2，….,用它表示一级目标，二级目标，….，的重要程度，规定P1》P2》

P3》….。称P1，P2，….,为级别系数。整理课件9-2多目标规划问题的数学模型整理课件37约束方程的处理差异变量：决策变量x超过目标值b的部分记d+决策变量x不足目标值b的部分记d-d+0,d-0且x-d++

d-=b整理课件约束方程的处理整理课件38多目标的综合若决策目标中规定xb,当d+=0时目标才算达到。整理课件多目标的综合整理课件39多目标的综合若决策目标中规定xb,当b+=0时目标才算达到。若决策目标中规定xb,当d-=0时目标才算达到。整理课件多目标的综合整理课件40多目标的综合若决策目标中规定xb,当b+=0时目标才算达到。若决策目标中规定xb,当b-=0时目标才算达到。若决策目标中规定x=b,当d+=d-=0时目标才算达到。整理课件多目标的综合整理课件41例9-5（例9-4)解：引进级别系数P1：（1）利润达到280百元；P2：（2）钢材不超过100吨，工时不超过120小时；（权数之比5：1）整理课件例9-5（例9-4)整理课件42数学模型：目标函数：MinS=P1d1-+P2(5d2++d3+)约束方程：

6X1+4X2+d1--d1+=2802X1+3X2+d2--d2+=1004X1+2X2+d3--d3+=120X1,X2,di-,di+0(i=1,2,3)整理课件数学模型：整理课件43例9-6（例9-2)

某车间有A、B两条设备相同的生产线，它们生产同一种产品。A生产线每小时可制造2件产品，B生产线每小时可制造1.5件产品。如果每周正常工作时数为45小时，要求制定完成下列目标的生产计划：整理课件例9-6（例9-2)某车间有A、B两条设备相同的生产线，它44（1）生产量达到210件/周；（2）A生产线加班时间限制在15小时内；（3）充分利用工时指标，并依A、B产量的比例确定重要性。整理课件（1）生产量达到210件/周；整理课件45解：设A，B生产线每周工作时间为X1，X2。A，B的产量比例2：1.5=4:3目标函数：MinS=P1d1-+P2d2++4

P3d3-+3P3d4-约束方程：2X1+1.5X2+d1--d1+=210

（生产量达到210件/周）

X1+d2--d2+=60（A生产线加班时间限制在15小时内）

整理课件解：设A，B生产线每周工作时间为X1，X2。A，B的产量比例46X1+d3--d3+=45

（充分利用A的工时指标）

X2+d4--d4+=45

（充分利用B的工时指标）

X1,X2,di-,di+0(i=1,2,3,4)整理课件X1+d3--d3+47A，B的产量比例2：1.5=4:3目标函数：

MinS=P1d1-+P2d2++4

P3d3-+3P3d4-约束方程：2X1+1.5X2+d1--d1+=210X1+d2--d2+=60X1+d3--d3+=45X2

+d4--d4+=45X1,X2,di-,di+0(i=1,2,3,4)整理课件A，B的产量比例2：1.5=4:3整理课件48例9-7(例9-3)：(1)库存费用不超过4600元；(2)每月销售唱机不少于80台；(3)不使A、B车间停工（权数由生产费用确定）；(4)A车间加班时间限制在20小时内；整理课件例9-7(例9-3)：整理课件49（5）每月销售录音机为100台；（6）两车间加班时数总和要尽可能小（权数由生产费用确定）；解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1整理课件（5）每月销售录音机为100台；整理课件50目标函数：MinS=P1d1++P2d2-+2

P3d4-+P3d5-+P4d41++P5d3-+P5d3++2P6d4++P6d5+约束方程：50X1+30X2+d1--d1+=4600

（库存费用不超过4600元）

X1+d2--d2+=80

（每月销售唱机不少于80台）整理课件目标函数：整理课件51

X2+d3--d3+=100

（每月销售录音机为100台）

2X1+X2+d4--d4+=180

（不使A车间停工）

X1+3X2+d5--d5+=200

（不使B车间停工）

d4++d41--d41+=20

（A车间加班时间限制在20小时内）

X1,X2,di-,di+,d41-,d41+0(i=1,2,3,4,5)整理课件X2+d3--d3+=100整理52目标函数：MinS=P1d1++P2d2-+2

P3d4-+P3d5-+P4d41++P5d3-+P5d3++2P6d4++P6d5+约束方程：50X1+30X2+d1--d1+=4600X1+d2--d2+=80X2+d3--d3+=1002X1+X2+d4--d4+=180X1+3X2+d5--d5+=200d4++d41--d41+=20X1,X2,di-,di+,d41-,d41+0(i=1,2,3,4,5)整理课件目标函数：MinS=P1d1++P2d2-+2P3d453目标规划的一般数学模型为

为权系数。

整理课件54目标规划的一般数学模型为

为权系9-3多目标规划问题的求解多目标规划问题的图解法例4-8MinS=d1+X1+2X2+d1--d1+=10X1+2X26X1+X24X1,X2,d1-,d1+0整理课件9-3多目标规划问题的求解整理课件55x1x204681021342X1+2X26整理课件x1x204681021342X1+2X26整理课件56x1x204681021342X1+X24整理课件x1x204681021342X1+X24整理课件57x1x204681021342整理课件x1x204681021342整理课件58x1x204681021342整理课件x1x204681021342整理课件59x1x204681021342x1+2x2=105d1+d1-AB(2,2)整理课件x1x204681021342x1+2x2=105d1+d160x1x204681021342x1+2x2=105d1+d1-AB(2,2)当MinS=d1+达到时d1+=0整理课件x1x204681021342x1+2x2=105d1+d161x1x204681021342x1+2x2=105d1-AB(2,2)当MinS=d1+达到时d1+=0整理课件x1x204681021342x1+2x2=105d1-AB62x1x204681021342x1+2x2+d1-=10d1-=25d1-AB(2,2)当MinS=d1+达到时d1+=0整理课件x1x204681021342x1+2x2+d1-=1063x1x204681021342x1+2x2+d1-=10d1-=45d1-AB(2,2)有无穷多解：点（0，3）和点（2，2）连线上的点都是最优解。(0,3)整理课件x1x204681021342x1+2x2+d1-=1064x1x204681021342x1+2x2+d1-=10d1-=65d1-AB(2,2)有无穷多解：点（4，0）和点（0，2）连线上的点都是最优解。(0,3)(4,0)(0,2)整理课件x1x204681021342x1+2x2+d1-=1065x1x204681021342x1+2x2+d1-=10d1-=75d1-AB(2,2)有无穷多解：点（1，1）和点（0，3/2）（3，0）连线上的点都是最优解。(0,3)(4,0)(1,1)整理课件x1x204681021342x1+2x2+d1-=1066例9-9MinS=P1d1-+P2d2++5

P3d3-+P3d1+X1+X2+d1--d1+=40X1+X2+d2--d2+=50X1+d3-=30X2+d4-=30X1,X2,dI-,dI+0(I=1,2,3,4)整理课件例9-9整理课件67x1x2020304050101030402050d1-d1+X1+X2=40整理课件x1x2020304050101030402050d1-d168x1x2020304050101030402050d1-d1+d2+d2-X1+X2=50整理课件x1x2020304050101030402050d1-d169x1x2020304050101030402050d1-d1+d2+d2-d3-X1=30整理课件x1x2020304050101030402050d1-d170x1x2020304050101030402050d1-d1+d2+d2-d3-d4-X2=30整理课件x1x2020304050101030402050d1-d171x1x2020304050101030402050d1+d2+d2-d3-d4-Mind1-=0可行域如图整理课件x1x2020304050101030402050d1+d272x1x2020304050101030402050d1+d2-d3-d4-Mind2+=0可行域如图整理课件x1x2020304050101030402050d1+d273x1x2020304050101030402050d1+d2-d4-Mind3-=0线段AB是可行域AB整理课件x1x2020304050101030402050d1+d274x1x2020304050101030402050d2-d4-Mind1+=0P=(30,10)唯一最优解。

d2-=10

d4-=20P整理课件x1x2020304050101030402050d2-d475例9-10

MinS=P1d1-+P2d2++

P3d3-+P3d4-5X1+10X2+d1--d1+=1002X1+X2+d2--d2+=14X1+d3--d3+=6X2+d4--d4+=10X1,X2,di-,di+0(i=1,2,3,4)整理课件例9-10整理课件76x1x20101520255515201025d1+d1-5X1+10X2=100整理课件x1x20101520255515201025d1+d1-577x1x20101520255515201025d1+d1-d2+d2-2X1+X2=14整理课件x1x20101520255515201025d1+d1-d78x1x20101520255515201025d1+d1-d2+d2-d3+d3-X1=6整理课件x1x20101520255515201025d1+d1-d79x1x20101520255515201025d1+d1-d2+d2-d3+d3-d4+d4-X2=10整理课件x1x20101520255515201025d1+d1-d80x1x20101520255515201025d1+d2+d2-d3+d3-d4+d4-Mind1-=0整理课件x1x20101520255515201025d1+d2+d81x1x20101520255515201025d1+d2-d3+d3-d4+d4-Mind2+=0可行域如图整理课件x1x20101520255515201025d1+d2-d82x1x20101520255515201025d1+d2-d3+d4+d4-Mind3-=0可行域为空如图整理课件x1x20101520255515201025d1+d2-d83x1x20101520255515201025d1+d2-d3+d4+Mind3-0Mind4-=0可行域如图d3-(2,10)整理课件x1x20101520255515201025d1+d2-d84x1x20101520255515201025d1+d2-d3+d4+Mind3-=0Mind4-0可行域为空如图d4-整理课件x1x20101520255515201025d1+d2-d85对于目标P1与目标P2很容易达到。目标P3的两个指标不能同时满足，否则无解。又因为P3中的两个目标同样重要，要讨论（1）Mind3-=0Mind4-0原问题无解。（2）Mind3-0Mind4-=0原问题(2,10)是次优解。整理课件对于目标P1与目标P2很容易达到。目标P3的两个指标不能同时86例9-11

MinS=P1d1-+P1d2-X1+d1--d1+=154X1+5X2+d2--d2+=2003X1+4X2120X1-2X215X1,X2,di-,di+0(i=1,2)整理课件例9-11整理课件87x1x2020304050101030402050d1+d1-X1=15整理课件x1x2020304050101030402050d1+d188x1x2020304050101030402050d1+d1-d2+d2-4X1+5X2=200整理课件x1x2020304050101030402050d1+d189x1x2020304050101030402050d1+d1-d2+d2-3X1+4X2120整理课件x1x2020304050101030402050d1+d190x1x2020304050101030402050d1+d1-d2+d2-X1-2X2

15整理课件x1x2020304050101030402050d1+d191x1x2020304050101030402050d1+d1-d2+d2-整理课件x1x2020304050101030402050d1+d192x1x2020304050101030402050d1+d2+同时考虑d1-=0,d2-=0

原问题无解。整理课件x1x2020304050101030402050d1+d29311.4层次分析法（AHP）1.问题的提出

例3.5设某企业拥有一笔资金，现有三种可能的投资去向：办实业、购买股票和存入银行．由于不同去向所冒风险大小不等，资金利润率不一样，资金周转快慢也不同．问如何选择投资去向才能得到最佳投资效益？

目标层G

准则层C

方案层P

权重

w1w2w3

投资效益风险C1

利润C2

周转C3

存款P3

股票P2

实业P1

整理课件9411.4层次分析法（AHP）1.问题的提出投资效益风险2.层次分析法的基本原理

以特征向量方法为基础的数学原理．设有n件物体A1,A2,…,An；它们的重量分别为w1,w2,…,wn．若将它们两两地比较重量，其比值可构成nn阶矩阵A．若用重量向量右乘矩阵A，得到

整理课件952.层次分析法的基本原理若用重量向量即AW=nW．

由正矩阵的有关理论可知，W为矩阵A的特征向量，n为矩阵A的特征值．

AHP法的基本思路：有一组与某一目标有关的因素，需要知道它们对目标影响程度，就可以把这些因素成对比较，构成比较判断矩阵，通过求解判断矩阵的最大特征值及其对应的特征向量，即可得到这些因素对目标影响的程度——权重．整理课件96整理课件96根据正矩阵理论，可以证明若矩阵A（设aij=wi/wj）具有以下特点：

(1)aii=1(i=1,2,...,n)

(2)aij=1/aji(i,j=1,2,...,n,i

j)

(3)aij=aik/ajk(或aik·akj)(i,j=1,2,...,n,i

j)

则该矩阵一定存在唯一的不为零的最大特征值max，且max=n．

若求解时所构造的完全具备上述三个特性，称矩阵完全满足一致性．但在实际问题中，在两两比较时，不可能做到判断的完全一致性而存在估计误差．必然导致特征值及特征向量也有偏差，变成

整理课件97根据正矩阵理论，可以证明若矩阵A（设aij=wi/wj为了避免使误差过大，需要检验的一致性．可用一致性比例指标CR来检验的一致性，其中，当max=n

时，CI=0，为完全一致；RI的值如下：当CR

0.1时，认为判断矩阵一致性是可以接受的．阶数123456789RI0.000.000.580.901.121.241.321.411.46整理课件98为了避免使误差过大，需要检验的一致性．阶数123456783.AHP法的基本步骤(1)建立递阶层次结构模型需要达到的目标类；判断好坏的准则类；解决问题的方案措施类．

(2)构造判断矩阵

判断同一层次的元素对上一级某一元素的影响程度，并将其定量化．元素aij表示对于元素Cs，Pi比Pj的相对重要程度的标度，即两两比较的比率的赋值．

Cs

P1P2...Pn

P1P2...Pn

a11a12...a1na21a22...a2n............an1an2...ann

整理课件99CsP1P2...PnP1a111~9标度法：一个递阶层次结构，可以构建若干个判断矩阵，其数目是图中除最低一层以外的所有各层的元素之和．

在建立判断矩阵时，通常只遵守aii=1和aij=1/aji两个条件，再按一致性检验方法进行检验．标度

aij

定义135792,4,6,8上列各数的倒数

同等重要略微重要明显重要强烈重要极端重要上述两相邻判断的中值反比较整理课件1001~9标度法：标度aij定义1同等重要整理课件10(3)层次单排序及其一致性检验层次单排序：把本层所有各元素对相邻上一层元素来说排出一个权重次序，即求判断矩阵的特征向量

根据判断矩阵进行层次单排序的方根法：①先求判断矩阵中每行元素之积Mi：

②再求Mi的n次方根，得③然后对向量进行归一化，得得到特征向量．整理课件101(3)层次单排序及其一致性检验整理课件101层次单排序的一致性检验：①计算判断矩阵的最大特征根（值）：②计算③计算若判断矩阵不满足一致性条件（<0.1），则需修改．整理课件102层次单排序的一致性检验：整理课件102(4)层次总排序及其一致性检验层次总排序：利用层次单排序的计算结果，进一步综合计算出对更上一层（或总目标层）的权重次序．

C层

P层

单排序元素及单排序

P层总排序

C1

C2…Cm

P1P2Pn

整理课件103(4)层次总排序及其一致性检验层次总排序的一致性检验：当CR<0.10时，认为层次总排序结果具有满意的一致性，否则需要重新调整判断矩阵的元素取值．整理课件104层次总排序的一致性检验：整理课件1044.实例分析某企业拟引进一台新设备，希望设备的功能强、价格低、维修容易，现有P1、P2、P3三种型号的设备可供选择，试运用层次分析法进行决策分析．(1)建立递阶层次结构模型目标层G

准则层C

方案层P

权重

w1w2w3

引进一台满意设备功能强C1

价格低C2

易维修C3

型号P3

型号P2

型号P1

整理课件1054.实例分析引进一台满意设备功能强C1价格低C2易维修C(2)构造判断矩阵

G-C判断矩阵对于总目标（G）来说，假设准则层（C）的优先次序是首先考虑要功能强（C1），其次要求易维修（C3），再次才考虑价格低（C2）．G

C1C2

C3

C1C2C3

1531/511/31/331Cs-P判断矩阵:

已知三种备选设备中的功能、价格和维修情况如下：整理课件106(2)构造判断矩阵GC1C2C3可分别构造C1-P、C2-P和C3-P判断矩阵：

功能价格维修P1P2P3

较好一般一般最好较贵一般差便宜易C1

P1P2

P3

P1P2P3

11/424181/21/81C2

P1P2

P3

P1P2P3

141/31/411/8381C3

P1P2

P3

P1P2P3

111/3111/5351整理课件107功能价格维修P1较好(3)层次单排序及一致性检验以G-C判断矩阵为例：G

C1C2

C3

C1C2C31531/511/31/331153=150.0671.0w1=2.446/3.872=0.637w2=0.406/3.872=0.105w3=1/3.872=0.258

整理课件108(3)层次单排序及一致性检验GC1C2查表，n=3时，得RI=0.58，于是可见，判断矩阵G-C具有满意的一致性．

整理课件109整理课件109(4)层次总排序及其一致性检验经检验，总排序具有满意的一致性．根据上述计算结果，W=(w1,w2,w3)T=(0.190,0.511,0.298)T，故选择设备型号P2为最优．

C层

P层

单排序元素及单排序

P层总排序

C1

C2

C3

0.6730.1050.258P1P2P3

0.1820.2560.1850.7270.0730.1560.0910.6710.6590.6370.182+0.1050.256+0.2580.185=0.1900.5110.298

整理课件110(4)层次总排序及其一致性检验5.对层次分析法的几点评价

能将决策者的主观判断与偏好用数量形式表达和处理，是柔性运筹学的一项有代表性的方法.AHP是一种定性与定量相结合的方法.标度方法及一致性判断具有认知基础.

AHP运用过程中决策者偏好的合理性问题.

整理课件1115.对层次分析法的几点评价整理课件111数学规划小结第四章线性规划第五章非线性规划第六章锥规划、矩阵规划及变分不等式第七章整数规划第八章动态规划第九章向量优化（多目标优化）整理课件数学规划小结第四章线性规划整理课件112数学规划小结除了上面所介绍的八个分支外，数学规划在近些年来出现了若干新的分支。例如，近十年来国际上对鲁棒优化阁、微分方程所控制的优化、多项式优化、稀疏优化的研究相当重视，这些新方向的研究十分活跃。在2012年第21届国际数学规划大会上这些新兴的分支都安排了专题报告.我国数学规划工作者，特别是青年科技工作者要充分重视这些新的方向，力争在国际上刚刚起步的阶段参与研究，这样有可能很快取得国际制高点。整理课件数学规划小结除了上面所介绍的八个分支外，数学规划在近些年来出113第七讲结束整理课件第七讲结束整理课件114高等运筹学大连海事大学刘巍整理课件高等运筹学大连海事大学整理课件115第二篇运筹学中的数学规划第四章线性规划第五章非线性规划第六章锥规划、矩阵规划及变分不等式第七章整数规划第八章动态规划第九章向量优化（多目标优化）整理课件第二篇运筹学中的数学规划第四章线性规划整理课件116第七讲内容第九章向量优化

（多目标规划）整理课件第七讲内容第九章向量优化整理课件117第九章向量优化

（多目标规划）整理课件第九章向量优化

（多目标规划）整理课件118近几十年来向量优化(亦称多目标优化)理论研究有了迅猛发展，在各种解的存在性、稳定性以及最优性条件等方面获得了丰富的结果，并创造性地建立了向量优化问题解集的结构定理、连通性定理和稠密性定理，被应用到经济问题中。通过向量广义凸性的研究，很好地处理了一大类非线性向量优化问题;通过提出向量变分不等式模型，开拓了研究向量优化间题的新方向。整理课件近几十年来向量优化(亦称多目标优化)理论研究有了迅猛发展，在119由于向量优化中衡量向量“大小”的是不完全的偏序，致使大量的向量优化问题没有解，甚至在向量目标函数光滑并有下界的情况下没有数值优化意义下的近似解。由于任何优化间题算法每一步获得的迭代项都是该优化问题的一个近似解，因此研究向量优化问题近似解的存在性以及拉格朗日和卡罗青一库恩一塔克等优化性条件仍然是具有基础性作用的主要问题也是求解算法的有力保障。整理课件由于向量优化中衡量向量“大小”的是不完全的偏序，致使大量的向120分式向量优化问题是具有重要经济意义的数学模型，关于这类模型的求解问题，也是今后向量优化问题研究的重点.利用次微分，使用变分分析技术和方法研究非光滑向量优化问题，就变分分析和向量优化进行交叉研究仍将是未来很有生命力的方向.整理课件分式向量优化问题是具有重要经济意义的数学模型，关于这类模型的1219.1基本概念解的概念

劣解：可淘汰的解。非劣解：没有其它解可以淘汰它们，但又非绝对最优解。单目标中：任何两个解都可以比较优劣，是完全有序的。多目标中：任何两个解不一定都可以比较出其优劣，因此只能是半序的。多目标优化的几类方法化多目标为单目标引进次序法直接求非劣解法f2(体重)●12●10●13●9●11●8●4●7●3●6●1●5●2

f1(身高)图3-1整理课件1229.1基本概念解的概念f2(体重)整理课件8从线性规划问题可看出：线性规划只研究在满足一定条件下，单一目标函数取得最优解，而在企业管理中，经常遇到多目标决策问题，如拟订生产计划时，不仅考虑总产值，同时要考虑利润，产品质量和设备利用率等。这些指标之间的重要程度（即优先顺序）也不相同，有些目标之间往往相互发生矛盾。整理课件从线性规划问题可看出：整理课件123线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际的需要，很可能是以过分地消耗了约束条件中的某些资源作为代价。线性规划把各个约束条件的重要性都不分主次地等同看待，这也不符合实际情况。整理课件线性规划致力于某个目标函数的最优解，这个最优解若是超过了实际124求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，由于人力，设备等资源条件的限制，使约束条件之间出现了矛盾，就得不到问题的可行解，但生产还得继续进行，这将给人们进一步应用线性规划方法带来困难。整理课件求解线性规划问题，首先要求约束条件必须相容，如果约束条件中，125为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛盾，在线性规划基础上，建立目标规划方法，从而使一些线性规划无法解决的问题得到满意的解答。整理课件为了弥补线性规划问题的局限性，解决有限资源和计划指标之间的矛126

多目标规划问题多目标规划问题的提出在实际问题中，可能会同时考虑几个方面都达到最优：产量最高，成本最低，质量最好，利润最大，环境达标，运输满足等。多目标规划能更好地兼顾统筹处理多种目标的关系，求得更切合实际要求的解。目标规划可根据实际情况，分主次地、轻重缓急地考虑问题。整理课件多目标规划问题整理课件127例9-1：一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？整理课件例9-1：一个企业需要同一种原材料生产甲乙两种产品，它们的单128如何安排生产，使利润达到最大。用单纯形法求得最优解=（20，20）最优值=200（百元）整理课件如何安排生产，使利润达到最大。整理课件129问题：该厂提出如下目标（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；如何安排生产？整理课件问题：该厂提出如下目标整理课件130例9-2：某车间有A、B两条设备相同的生产线，它们生产同一种产品。A生产线每小时可制造2件产品，B生产线每小时可制造1.5件产品。如果每周正常工作时数为45小时，要求制定完成下列目标的生产计划：整理课件例9-2：某车间有A、B两条设备相同的生产线，它们生产同一种131（1）生产量达到210件/周；（2）A生产线加班时间限制在15小时内；（3）充分利用工时指标，并依A、B产量的比例确定重要性。整理课件（1）生产量达到210件/周；整理课件132例9-3：某电器公司经营的唱机和录音机均有车间A、B流水作业组装。数据见下表。要求按以下目标制订月生产计划：（1）库存费用不超过4600元；（2）每月销售唱机不少于80台；整理课件例9-3：某电器公司经营的唱机和录音机均有车间A、B流水作业133（3）不使A、B车间停工（权数由生产费用确定）；（4）A车间加班时间限制在20小时内；（5）每月销售录音机为100台；（6）两车间加班时数总和要尽可能小（权数由生产费用确定）；整理课件（3）不使A、B车间停工（权数由生产费用确定）；整理课件134整理课件整理课件135多目标优先级先将目标等级化：将目标按重要性的程度不同依次分成一级目标、二级目标…..。最次要的目标放在次要的等级中。整理课件多目标优先级整理课件136目标优先级作如下约定：对同一个目标而言，若有几个决策方案都能使其达到，可认为这些方案就这个目标而言都是最优方案；若达不到，则与目标差距越小的越好。整理课件目标优先级作如下约定：整理课件137目标优先级作如下约定：不同级别的目标的重要性是不可比的。即较高级别的目标没有达到的损失，任何较低级别的目标上的收获都不可弥补。所以在判断最优方案时，首先从较高级别的目标达到的程度来决策，然后再其次级目标的判断。整理课件目标优先级作如下约定：整理课件138目标优先级作如下约定：同一级别的目标可以是多个。各自之间的重要程度可用数量（权数）来描述。因此，同一级别的目标的其中一个的损失，可有其余目标的适当收获来弥补。整理课件目标优先级作如下约定：整理课件139多目标规划解的概念：若多目标规划问题的解能使所有的目标都达到，就称该解为多目标规划的最优解；若解只能满足部分目标，就称该解为多目标规划的次优解；若找不到满足任何一个目标的解，就称该问题为无解。整理课件多目标规划解的概念：整理课件140例9-4：（例9-1）一个企业需要同一种原材料生产甲乙两种产品，它们的单位产品所需要的原材料的数量及所耗费的加工时间各不相同，从而获得的利润也不相同（如下表）。那么，该企业应如何安排生产计划，才能使获得的利润达到最大？整理课件例9-4：（例9-1）一个企业需要同一种原材料生产甲乙两种产141如何安排生产，使利润达到最大。前面已经求得最优解=（20，20）最优值=200（百元）整理课件如何安排生产，使利润达到最大。整理课件142问题：该厂提出如下目标（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；如何安排生产？整理课件问题：该厂提出如下目标整理课件143对例4-1的问题，设超过一吨钢材与超过5个工时的损失相同。现有四个方案进行比较优劣？整理课件对例4-1的问题，设超过一吨钢材与超过5个工时的损失相同。现144目标：（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；对于（1），只有方案4没有完成。排除方案4。对于（2），只有方案2达到了，因此方案2是最优。整理课件目标：（1）利润达到280百元；（2）钢材不超过100吨，工145目标：（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；方案1与方案3都达到了（1），又没达到（2）方案1与（2）的差距：工时损失=（110-100）*5+（130-120）*1=60整理课件目标：（1）利润达到280百元；（2）钢材不超过100吨，工146方案3与（2）的差距：工时损失=0*5+（190-120）*1=70方案1优于方案3。方案2优于方案1优于方案3优于方案4整理课件方案3与（2）的差距：整理课件147例9-4：继续上例整理课件例9-4：继续上例整理课件148目标：（1）利润达到280百元；（2）钢材不超过100吨，工时不超过120小时；对于（1），三个方案都没有完成。但方案3离目标最远，方案3最差。方案1与（2）的差距：工时损失=（108-100）*5+（130-120）*1=50整理课件目标：（1）利润达到280百元；（2）钢材不超过100吨，工149方案2与（2）的差距：工时损失=0*5+（160-120）*1=40方案2优于方案1方案2优于方案1优于方案3整理课件方案2与（2）的差距：整理课件1509-2多目标规划问题的数学模型多目标的处理为了将不同级别的目标的重要性用数量表示，引进P1，P2，….,用它表示一级目标，二级目标，….，的重要程度，规定P1》P2》

P3》….。称P1，P2，….,为级别系数。整理课件9-2多目标规划问题的数学模型整理课件151约束方程的处理差异变量：决策变量x超过目标值b的部分记d+决策变量x不足目标值b的部分记d-d+0,d-0且x-d++

d-=b整理课件约束方程的处理整理课件152多目标的综合若决策目标中规定xb,当d+=0时目标才算达到。整理课件多目标的综合整理课件153多目标的综合若决策目标中规定xb,当b+=0时目标才算达到。若决策目标中规定xb,当d-=0时目标才算达到。整理课件多目标的综合整理课件154多目标的综合若决策目标中规定xb,当b+=0时目标才算达到。若决策目标中规定xb,当b-=0时目标才算达到。若决策目标中规定x=b,当d+=d-=0时目标才算达到。整理课件多目标的综合整理课件155例9-5（例9-4)解：引进级别系数P1：（1）利润达到280百元；P2：（2）钢材不超过100吨，工时不超过120小时；（权数之比5：1）整理课件例9-5（例9-4)整理课件156数学模型：目标函数：MinS=P1d1-+P2(5d2++d3+)约束方程：

6X1+4X2+d1--d1+=2802X1+3X2+d2--d2+=1004X1+2X2+d3--d3+=120X1,X2,di-,di+0(i=1,2,3)整理课件数学模型：整理课件157例9-6（例9-2)

某车间有A、B两条设备相同的生产线，它们生产同一种产品。A生产线每小时可制造2件产品，B生产线每小时可制造1.5件产品。如果每周正常工作时数为45小时，要求制定完成下列目标的生产计划：整理课件例9-6（例9-2)某车间有A、B两条设备相同的生产线，它158（1）生产量达到210件/周；（2）A生产线加班时间限制在15小时内；（3）充分利用工时指标，并依A、B产量的比例确定重要性。整理课件（1）生产量达到210件/周；整理课件159解：设A，B生产线每周工作时间为X1，X2。A，B的产量比例2：1.5=4:3目标函数：MinS=P1d1-+P2d2++4

P3d3-+3P3d4-约束方程：2X1+1.5X2+d1--d1+=210

（生产量达到210件/周）

X1+d2--d2+=60（A生产线加班时间限制在15小时内）

整理课件解：设A，B生产线每周工作时间为X1，X2。A，B的产量比例160X1+d3--d3+=45

（充分利用A的工时指标）

X2+d4--d4+=45

（充分利用B的工时指标）

X1,X2,di-,di+0(i=1,2,3,4)整理课件X1+d3--d3+161A，B的产量比例2：1.5=4:3目标函数：

MinS=P1d1-+P2d2++4

P3d3-+3P3d4-约束方程：2X1+1.5X2+d1--d1+=210X1+d2--d2+=60X1+d3--d3+=45X2

+d4--d4+=45X1,X2,di-,di+0(i=1,2,3,4)整理课件A，B的产量比例2：1.5=4:3整理课件162例9-7(例9-3)：(1)库存费用不超过4600元；(2)每月销售唱机不少于80台；(3)不使A、B车间停工（权数由生产费用确定）；(4)A车间加班时间限制在20小时内；整理课件例9-7(例9-3)：整理课件163（5）每月销售录音机为100台；（6）两车间加班时数总和要尽可能小（权数由生产费用确定）；解：设每月生产唱机、录音机X1，X2台。且A、B的生产费用之比为100：50=2：1整理课件（5）每月销售录音机为100台；整理课件164目标函数：MinS=P1d1++P2d2-+2

P3d4-+P3d5-+P4d41++P5d3-+P5d3++2P6d4++P6d5+约束方程：50X1+30X2+d1--d1+=4600

（库存费用不超过4600元）

X1+d2--d2+=80

（每月销售唱机