数学模型-第07章(第五版).pptx

案例主要取自决策、排序、分配等方面的问题.,第七章离散模型,连续模型,离散模型,微分方程,线性、非线性规划,差分方程,整数规划,经济、社会等领域,科学、技术等领域,从应用角度只涉及代数、几何和图的一点知识.,7.1汽车选购7.2职员晋升7.3厂房新建还是改建7.4循环比赛的名次7.5公平的席位分配7.6存在公平的选举吗7.7价格指数7.8钢管的订购和运输,第七章离散模型,对待选汽车作出综合评价,为选购确定决策.,考虑的因素：经济适用、性能良好、款式新颖.,对3个因素在汽车选购中的重要性有大致比较.,对待选汽车在每一因素中的优劣程度有基本判断.,7.1汽车选购,人们在日常生活中常常碰到类似的决策问题：选择旅游目的地，选择学校上学，选择工作岗位.,从事各种职业的人在工作中经常面对决策：购买哪种设备；选择研究课题；选拔秘书；对经济、环境、交通、居住等方面的发展做出规划.,汽车选购等决策问题的共同特点,什么是多属性决策,为一特定目的在备选方案中确定一个最优的(或给出优劣排序、优劣数值),而方案的优劣由若干属性(准则、特征、性能)给以定量或定性的表述.,考虑的因素常涉及经济、社会等领域，对它们的重要性、影响力作比较、评价时缺乏客观的标准.,待选对象对于这些因素的优劣程度常难以量化.,多属性决策是处理这类决策问题的常用方法.,要素：1.决策目标、备选方案与属性集合2.决策矩阵3.属性权重4.综合方法.,1.确定属性集合的一般原则：,全面考虑,选取影响力(或重要性)强的.,属性间尽量独立(至少相关性不太强),不选难以辨别方案优劣的(即使影响力很强).,若数量太多(如大于7个),应将它们分层.,尽量选可量化的,定性的也要能明确区分档次.,多属性决策的要素,2.决策矩阵,以方案为行、属性为列、每一方案对每一属性的取值为元素构成的矩阵.,表示方案对属性的优劣(或偏好)程度.,可以定量的属性,只能定性的属性,3.属性权重,对目标影响力(或重要性)的权重分配,将决策矩阵与属性权重加以综合,得到最终决策的数学方法.,4.综合方法,要素：1.决策目标、备选方案与属性集合2.决策矩阵3.属性权重4.综合方法.,3个属性为选购准则价格X1,性能X2,款式X3,3个方案供决策选购的汽车型号A1,A2,A3,dijAi对Xj的取值(原始权重),3种汽车价格(万元):25,18,12,3种汽车性能(打分,10分满分):9,7,5,3种汽车款式:7,7,5,以汽车选购为例说明如何确定决策矩阵、属性权重以及利用综合方法得到决策结果.,1）决策矩阵及其标准化,m个备选方案A1,A2,Am,决策矩阵,dijAi对Xj的取值,决策矩阵的获取,调查、量测各方案对属性的取值(定量,偏于客观).,决策者打分评定或用层次分析法的成对比较得到(定性,偏于主观).,n个属性X1,X2,Xn,汽车选购,1）决策矩阵及其标准化,决策矩阵D的列各方案对某属性的取值(属性值).,各属性物理意义(包括量纲)不同,效益型属性,对费用型的属性值dij作倒数变换将全部属性统一为效益型.,性能X2,款式X3,费用型属性,标准化第1步：区分,价格X1,R的列最大值为1最大化,R的列和为1归一化,R的列模为1模一化,1）决策矩阵及其标准化,标准化第2步：对dij作比例尺度变换,当且仅当dij=0时才有rij=0,R标准化的决策矩阵,比例变换假定:属性的重要性随属性值线性变化.,2）属性权重的确定,w1,w2,wn属性X1,X2,Xn的权重,，,用层次分析法的成对比较得到.,偏于主观,根据决策目的和经验先验地给出.,信息熵法,偏于客观,熵信息论中衡量不确定性的指标，信息量的(概率)分布越一致，不确定性越大.,R归一化的每一列,各方案对Xj信息量的(概率)分布.,2）属性权重的确定,方案关于属性Xj的熵,rij=1/m时Ej=1.,属性Xj对于方案的区分度,rij只有一个1其余为0时Ej=0,rij(i=1,2,m)相差越大,Ej越小,Xj越能辨别优劣.,Xj的权重(归一化的区分度),汽车选购,2）属性权重的确定,3种汽车价格X1取值相差最大,款式X3取值相差最小.,w1最大,rij(i=1,2,m)的均方差可作为区分度Fj(m较大时).,w3最小,方案对目标的权重（综合取值）,1.简单加权和法(SAW,SimpleAdditiveWeighting),方案Ai对n个属性的综合取值为,对决策矩阵采用不同的标准化,得到的结果会不同.,3）主要的综合方法,2.加权积法（WP,WeightedProduct）,可直接用方案对属性的原始值dij,不需要标准化.,若效益型属性的权重取正值，则费用型属性的权重应取负值.,将SAW的算术加权平均改为几何加权平均：,3.接近理想解的偏好排序法(TOPSIS,TechniqueforOrderPreferencebySimilaritytoIdealSolution）,n个属性、m个方案视为n维空间中m个点的几何系统,每个点的坐标由各方案标准化的加权属性值确定.,决策矩阵模一化,以便在空间定义欧氏距离.,正理想解(最优方案)由所有最优加权属性值构成.,负理想解由所有最劣加权属性值构成.,定义距正、负理想解距离的数量指标:相对接近度.,按照相对接近度确定备选方案的优劣顺序.,汽车选购,统一为效益型的决策矩阵,用3种综合方法确定3种汽车的优劣顺序,属性权重取信息熵法结果:w=(0.5330,0.3293,0.1377)T,1.简单加权和法(SAW),2.加权积法(WP),v=(0.3162,0.3277,0.3562)T,v=(0.4847,0.5316,0.5639)T,v=(0.3067,0.3364,0.3569)T,汽车选购,用3种综合方法确定3种汽车的优劣顺序,3.理想解法(TOPSIS）,R模一化,vij=rijwj,正理想解,负理想解,Ai与v+距离,Ai与v-距离,S+=(0.2141,0.1470,0.1087),S-=(0.1087,0.0966,0.2141),相对接近度,C+=(0.3368,0.3966,0.6633),汽车选购,用3种综合方法确定3种汽车的优劣顺序,SAW(R归一化,最大化),WP结果差别很小,TOPSIS结果差别稍大.,优劣顺序均为A3,A2,A1,简单、直观的加权和法(SAW)是人们的首选.,SAW的前提属性之间相互独立,并且具有互补性.,多属性决策应用的步骤,1.确定决策目标、备选方案与属性集合；,2.用量测、调查等手段确定决策矩阵和属性权重,推荐用信息熵法由决策矩阵得出属性权重；,3.将全部属性统一(如效益型)，并采用归一化、最大化或模一化对决策矩阵标准化；,4.选用加权和、加权积、TOPSIS等综合方法计算方案对目标的权重，作为决策的依据.,1.比例尺度变换的归一化和最大化,归一化分配模式(DistributiveMode),某一方案属性值改变引起其他方案属性值随之改变.,最大化理想模式(IdealMode),任一方案的属性值独立于最优方案外的其他方案.,列最大值为1:各方案与占资源1的最优方案比较.,列和为1:各方案分配总量固定(1单位)的资源.,多属性决策应用中的几个问题,方案的优劣排序大体上一致(方案数量不多时).,两种模式计算的结果数值上一般不会相同.,在实际应用中究竟应该采用哪种模式?,分配模式决策者关心每个方案相对于其他方案的占优程度;需要对候选方案的优劣给出定量评价;特别用于资源分配问题.,理想模式决策者关心每个方案相对于基准指标的优劣;从众多候选方案中只选一个最优者.,比例尺度变换的理想模式和分配模式,2.区间尺度变换使用中的问题,但区间尺度变换dij最小值(对每个j)都变为rij=0.,区间尺度变换对原始权重dij作伸缩与平移变换,两种变换dij最大值(对每个j)都变为rij=1.,对比比例尺度变换的最大化,虚拟一个极端的例子说明,某些实际问题适于采用比例尺度变换归一化,用最大化会出现较大谬误,而用区间尺度变换将得到极不合理的结果.,常识：教学0.5万平分,科研0.5万给B.,与常识一致,与常识有别,区间尺度,严重不妥!,区间尺度变换使用中的问题,例.奖金1万元按教学和科研并重原则分配给A,B.,理想模式(最大化),分配模式(归一化),把非常接近的教学原始分51和49分别变成1和0,为什么？,3.方案的排序保持与排序逆转,若各准则对目标的权重和原有方案对属性的权重都不变，当有新方案加入或旧方案退出时，原有方案的优劣排序是保持还是会逆转？,用理想模式和分配模式可能会得到不同的结果.,例.工作选择(训练题15),两种模式排序都是A1,A2,A3,理想模式保持排序A1,A2,分配模式逆转.,在一定条件下理想模式保持排序A1,A2.,新方案加入时,只要它对每个准则的权重都不超过原方案,用理想模式计算原方案的排序保持不变,用分配模式计算原方案的排序可能逆转.,方案的排序保持与排序逆转,分配模式各方案对每一准则权重rij对i之和恒为1,新方案加入导致原来rij减少,稀释了原有资源,资源的重新分配可能导致原方案排序逆转.,理想模式各方案对每一准则权重rij对i最大值为1,新方案加入只要不改变原来的最大值,就不会稀释原有资源,原方案排序将保持不变.,小结与评注,决策矩阵标准化的不同或综合方法的不同对最终决策的影响，远小于属性集合的不同及属性权重的不同对最终决策的影响.所以不要过度注意前者,而应对后者多些关注.,实际应用中对于从众多候选方案中只选一个最优者的情况，多用理想模式；而那些需要对候选方案的优劣给出定量比较时，或者对资源按照候选方案的优劣进行分配时，多用分配模式.,简单易行、具有一定合理性的办法,订立全面评价一位职员的几条准则，如工作年限、教育程度、工作能力、道德品质等;,确定各条准则在目标(职员晋升)中所占的权重;,按照每一准则对各位申报者进行比较和评判;,将准则的权重与按准则评判的结果加以综合,得到各位申报者的排序,作为职员晋升的决策.,7.2职员晋升,职员晋升与汽车选购是有相同特点的决策问题，用多属性决策方法可以类似地加以解决.,层次分析法(AHP,AnalyticHierarchyProcess）,针对经济、社会领域作比较判断时主观因素作用较大,准则和方案的重要性难以量化的情况.,Saaty于20世纪70年代提出(稍晚于多属性决策)的定性与定量相结合的,系统化、层次化的分析方法.,在实际应用领域、处理问题类型、具体计算方法等方面,与多属性决策有不少类似和相通之处.,职员晋升,职员晋升问题建模的另一种常用方法.,将决策问题自上而下地分为目标、准则、方案3个层次,直观地用一个层次结构图表示.,二者综合得到方案对目标的权重.,确定各准则对目标的权重.,确定各方案对每一准则的权重.,1.层次结构图,层次分析法(AHP)的几个要素,确定n个准则X1,X2,X4对目标Y的权重.,A成对比较阵,工作年限X1,教育程度X2,工作能力X3,道德品质X4对汽车选购Y的成对比较阵:,正互反阵,n个准则两两对比:aijXi和Xj对Y的重要性之比,对比采用相对尺度,2.成对比较矩阵和特征向量,A=112131221121321221121,2.成对比较矩阵和特征向量,成对比较的一致性,n个元素需做n(n1)/2次成对比较,要求全部一致是不现实、也不必要的.,AHP容许成对比较存在不一致，并确定了这种不一致的容许范围.,a12=1/2X1与X2重要性之比是1:2,X1与X3重要性之比应是1:4,a23=1/2X2与X3重要性之比是1:2,A=112131221121321221121,成对比较完全一致,2.成对比较矩阵和特征向量,假定X1,X2,Xn对Y的重要性之比已精确测定为w1:w2:wn,令aij=wi/wj,成对比较阵A满足,一致阵的各列均相差一个比例因子,一致阵A的代数性质：,任一列向量都是对应于n的特征向量.,秩为1,唯一非零特征根为n.,设,2.成对比较矩阵和特征向量,取权向量为w=(w1,w2,wn)T,一致阵A的任一列向量都是对应于n的特征向量.,如果成对比较阵A不一致(但在容许范围内),3.一致性指标和一致性检验,Saaty定义一致性指标:,界定成对比较阵(正互反阵)A不一致的范围.,n阶正互反阵A的最大特征根n，A是一致阵的充要条件为=n.,CI=0时A是一致阵,CI越大A越不一致.,比n大得越多,A与一致阵相差越大,用特征向量作为权向量引起的判断误差越大.,定义一致性比率CR=CIRI,当CRE(1)=240,决策1选择改建厂房经营3年.,小结与评注,风险性决策决策中每个备选方案的后果至少存在两种状态,且各种状态的概率是可以估计的.,决策树是求解风险性决策(特别是多次决策)常用的手段,具有直观、简便、逻辑关系清晰等优点.,贝叶斯决策是解决这个问题的一种办法，参见拓展阅读7-3.,多数实际问题属于一次性而非多次重复的决策，采用期望值准则可能会冒较大的风险，特别是几个随机状态出现的概率相差不大的情况.,7.4循环比赛的名次,n支球队单循环赛，每场比赛只计胜负，没有平局.,根据比赛结果排出各队名次.,常用方法：按得分排序1,(2,3),(4,5),6,6支球队比赛结果(+行队胜列队),3队胜2队,4队胜5队,合理吗?,单循环比赛的名次,312456,146325,竞赛图（Tournament）,竞赛图的性质,必存在完全路径（按箭头方向通过全部顶点的路径）,若存在唯一的完全路径，则由它确定的顶点顺序与按得分排列的顺序一致,每对顶点有且仅有一条有向边相连,单循环比赛的名次,以下只考虑双向连通图,竞赛图（Tournament）,不具有唯一的完全路径时：,双向连通图从任一顶点出发，至少存在一条有向路径到达另外任一顶点,其他：不易给出所有队的排名,双向连通竞赛图的排名,邻接矩阵,得分向量,s=(4,3,3,2,2,1),=s(1)(1级得分),(2级得分),存在i到j的有向弧否则,双向连通竞赛图的排名,对于n(3)个顶点的双向连通竞赛图，存在正整数r，使邻接矩阵A满足Ar0，A称素阵.,双向连通竞赛图的排名,排名次序为1，3，2，5，4，6,32,45,排名132456?,1:4分;2,3:3分;4,5:2分;6:1分.,每10年，美国联邦政府进行一次全国人口普查,各州在联邦众议院的代表名额也据此重新确定.,公平的席位分配问题（apportionment）,2000年人口普查后，犹他州向联邦政府提出控诉，说分配给北卡罗莱纳州的名额应该是他们的.,问题的数学本质是什么？,事实上，过去200年来，美国国会在名额分配上打过多起法律官司，曾有过长期争论并使用过4种分配方案.,7.5公平的席位分配,一个简单例子,问题,三个系学生共200名(甲100，乙60，丙40)，代表会议共20席，按比例分配，三个系分别为10,6,4席.,因学生转系,三系人数为103,63,34,如何分配20席?,若代表会议增加1席，如何分配21席?,比例加惯例,对丙系公平吗？,模型,已知:m方人数分别为p1,p2,pm,记总人数为P=p1+p2+pm,待分配的总席位为N.,各方先分配qi的整数部分qi,总余额为,记ri=qi-qi,则第i方的分配名额ni为,要求,已知份额向量q=(q1,qm)0,找一个非负整数分配向量n=(n1,nm),使n与q最接近,且n1+nm=N.,比例加惯例法,记qi=Npi/P,称为第i方的份额(i=1,2,m),背景,Hamilton(比例加惯例)方法,A.Hamilton提出的这种办法1792年被美国国会否决1850-1900年被美国国会采用(称为Vinton法)又称为最大剩余法（GR:GreatestRemainders）或最大分数法（LF:LargestFractions），等等,席位悖论总席位增加反而可能导致某州席位减少1880年Alabama州曾遇到，又称Alabama悖论,该方法的另一个重大缺陷：（下页给例子）人口悖论某州人口增加较多反而可能该州席位减少,Hamilton方法的不公平性,1.p1,p2,pm不变,N的增加会使某个ni减少(上例).,2.N不变,pi比pj的增长率大,会使ni减少nj增加(下例).,“公平”分配方法,衡量公平分配的数量指标,当p1/n1=p2/n2时，分配公平,p1/n1p2/n2对A的绝对不公平度,p1=150,n1=10,p1/n1=15p2=100,n2=10,p2/n2=10,p1=1050,n1=10,p1/n1=105p2=1000,n2=10,p2/n2=100,p1/n1p2/n2=5,但后者对A的不公平程度已大大降低!,虽二者的绝对不公平度相同,若p1/n1p2/n2，对不公平,A,p1/n1p2/n2=5,公平分配方案应使rA,rB尽量小,设A,B已分别有n1,n2席,若增加1席,问应分给A,还是B?,不妨设分配开始时p1/n1p2/n2，即对A不公平.,对A的相对不公平度,将绝对度量改为相对度量,类似地定义rB(n1,n2),将一次性的席位分配转化为动态的席位分配,即,“公平”分配方法,若p1/n1p2/n2，定义,1）若p1/(n1+1)p2/n2，,则这席应给A,2）若p1/(n1+1)p2/(n2+1)，,应计算rB(n1+1,n2),应计算rA(n1,n2+1),若rB(n1+1,n2)p2/n2,问：,p1/n1rA(n1,n2+1),则这席应给B,当rB(n1+1,n2)0,1.价格单调性：一种商品涨价，其他不降，则I应上升,价格指数的公理化,p,q,p0,q00,I(p,q|p0,q0)0,2.权重不变性：所有商品价格不变，则I应不变,3.价格齐次性：所有商品涨价k倍，则I应上升k倍,4.I应位于单种商品价格比值的最小、最大值之间,5.货币单位独立性：I应与货币单位的选取无关,价格指数的公理化,p,q,p0,q00,I(p,q|p0,q0)0,6.计量单位独立性：I应与商品计量单位的选取无关,7.两年的价格指数之比与基年选取无关,8.价格指数不因某种商品被淘汰失去意义,I1,I2,I5不满足公理7,该定理没有涉及公理1,4,5,为什么?,I6,I7,I8不满足公理8,I3不满足公理2,I4不满足公理6,I满足公理1,2,3I满足公理4,I满足公理2,3,7I满足公理5,目前常用的价格指数:I1,I2,I1,I2满足除公理7外的所有公理，且计算简单.,价格指数的公理化,定理不存在同时满足公理2,3,6,7,8的价格指数,证明思路:满足2,3,6,7,8的价格指数I必不满足公理8,记e=(1,1,1)T,C=Diagc1,c2,cn,ci0D=Diagd1,d2,dn,di0,(*),证明,证明,记i=Diag1,1(第i位置元素0，其余为1),(*),(*),定理不存在同时满足公理2,3,6,7,8的价格指数,与公理矛盾！,当0时,s0,存在某个i,当0时,证毕,证明,定理不存在同时满足公理2,3,6,7,8的价格指数,