数学模型-第七章(第五版)课件

案例主要取自决策、排序、分配等方面的问题.第七章离散模型连续模型离散模型微分方程线性、非线性规划差分方程整数规划经济、社会等领域科学、技术等领域从应用角度只涉及代数、几何和图的一点知识.案例主要取自决策、排序、分配等方面的问题.第七章离散模型7.1 汽车选购7.2 职员晋升7.3 厂房新建还是改建7.4 循环比赛的名次7.5 公平的席位分配7.6 存在公平的选举吗7.7 价格指数7.8 钢管的订购和运输

第七章离散模型7.1 汽车选购第七章对待选汽车作出综合评价,为选购确定决策.考虑的因素：经济适用、性能良好、款式新颖.对3个因素在汽车选购中的重要性有大致比较.对待选汽车在每一因素中的优劣程度有基本判断.7.1 汽车选购

人们在日常生活中常常碰到类似的决策问题：选择旅游目的地，选择学校上学，选择工作岗位.

从事各种职业的人在工作中经常面对决策：购买哪种设备；选择研究课题；选拔秘书；对经济、环境、交通、居住等方面的发展做出规划.对待选汽车作出综合评价,为选购确定决策.考虑的因素：经济适汽车选购等决策问题的共同特点什么是多属性决策为一特定目的在备选方案中确定一个最优的(或给出优劣排序、优劣数值),而方案的优劣由若干属性(准则、特征、性能)给以定量或定性的表述.考虑的因素常涉及经济、社会等领域，对它们的重要性、影响力作比较、评价时缺乏客观的标准.待选对象对于这些因素的优劣程度常难以量化.多属性决策是处理这类决策问题的常用方法.汽车选购等决策问题的共同特点什么是多属性决策为一特定目的在备要素：1.决策目标、备选方案与属性集合2.决策矩阵

3.属性权重4.综合方法.

1.确定属性集合的一般原则：

全面考虑,选取影响力(或重要性)强的.

属性间尽量独立(至少相关性不太强)

不选难以辨别方案优劣的(即使影响力很强).

若数量太多(如大于7个),应将它们分层.

尽量选可量化的,定性的也要能明确区分档次.多属性决策的要素要素：1.决策目标、备选方案与属性集合1.确定属性集合的一2.决策矩阵

以方案为行、属性为列、每一方案对每一属性的取值为元素构成的矩阵.表示方案对属性的优劣(或偏好)程度.可以定量的属性只能定性的属性3.属性权重

对目标影响力(或重要性)的权重分配

将决策矩阵与属性权重加以综合,得到最终决策的数学方法.4.综合方法

要素：1.决策目标、备选方案与属性集合2.决策矩阵

3.属性权重4.综合方法.

2.决策矩阵以方案为行、属性为列、每一方案对每一属性的取值3个属性为选购准则~价格X1,性能X2,款式X33个方案供决策~选购的汽车型号A1,A2,A3

dij

X1

X2X3A12597A21877A31255dij~Ai对Xj的取值(原始权重)3种汽车价格(万元):25,18,123种汽车性能

(打分,10分满分):9,7,53种汽车款式:7,7,5以汽车选购为例说明如何确定决策矩阵、属性权重以及利用综合方法得到决策结果.3个属性为选购准则~价格X1,性能X2,款式X33个1）决策矩阵及其标准化m个备选方案A1,A2,…,Am~决策矩阵dij~Ai对Xj的取值决策矩阵的获取

调查、量测各方案对属性的取值(定量,偏于客观).决策者打分评定或用层次分析法的成对比较得到(定性,偏于主观).n个属性X1,X2,…,Xn

汽车选购

1）决策矩阵及其标准化m个备选方案A1,A2,…,Am~1）决策矩阵及其标准化决策矩阵D的列~各方案对某属性的取值(属性值).各属性物理意义(包括量纲)不同效益型属性对费用型的属性值dij作倒数变换——将全部属性统一为效益型.性能X2,款式X3费用型属性标准化第1步：区分价格X1决策矩阵标准化1）决策矩阵及其标准化决策矩阵D的列~各方案对某属性的取值(R的列最大值为1~最大化R的列和为1~归一化R的列模为1~模一化1）决策矩阵及其标准化标准化第2步：对dij作比例尺度变换当且仅当dij=0时才有rij=0R~标准化的决策矩阵比例变换假定:属性的重要性随属性值线性变化.R的列最大值为1~最大化R的列和为1~归一化R的列模为12）属性权重的确定w1,w2,

,wn~属性X1,X2,…,Xn的权重，

用层次分析法的成对比较得到.偏于主观

根据决策目的和经验先验地给出.

信息熵法偏于客观熵~信息论中衡量不确定性的指标，信息量的(概率)分布越一致，不确定性越大.R归一化的每一列

~各方案对Xj信息量的(概率)分布.

2）属性权重的确定w1,w2,,wn~属性X1,X2）属性权重的确定方案关于属性Xj的熵

rij=1/m时Ej=1.属性Xj对于方案的区分度

rij只有一个1其余为0时Ej=0rij(i=1,2,…,m)相差越大,Ej越小,Xj越能辨别优劣.Xj的权重(归一化的区分度)Xj对于辨别方案优劣不起作用.Xj最能辨别方案优劣.2）属性权重的确定方案关于属性Xj的熵rij=1/m时E汽车选购

2）属性权重的确定

X1X2X3

0.22360.42860.3684rij0.31060.33330.3684

0.46580.23810.26323种汽车价格X1取值相差最大,款式X3取值相差最小.w1最大rij(i=1,2,…,m)的均方差可作为区分度Fj

(m较大时).归一化Ej0.95940.97490.9895Fj0.04060.02510.0105wj0.53300.32930.1377w3最小汽车选购2）属性权重的确定

X1X2X3

0.22360.方案对目标的权重（综合取值）综合方法决策矩阵属性权重+1.简单加权和法(SAW,SimpleAdditiveWeighting)

方案Ai对n个属性的综合取值为对决策矩阵采用不同的标准化,得到的结果会不同.3）主要的综合方法方案对目标的权重（综合取值）综合方法决策矩阵属性权重+1.2.加权积法（WP,WeightedProduct）可直接用方案对属性的原始值dij,不需要标准化.

若效益型属性的权重取正值，则费用型属性的权重应取负值.将SAW的算术加权平均改为几何加权平均：2.加权积法（WP,WeightedProduct）3.接近理想解的偏好排序法(TOPSIS,TechniqueforOrderPreferencebySimilaritytoIdealSolution）n个属性、m个方案视为n维空间中m个点的几何系统

每个点的坐标由各方案标准化的加权属性值确定.

决策矩阵模一化,以便在空间定义欧氏距离.

正理想解(最优方案)由所有最优加权属性值构成.

负理想解由所有最劣加权属性值构成.

定义距正、负理想解距离的数量指标:相对接近度.

按照相对接近度确定备选方案的优劣顺序.3.接近理想解的偏好排序法(TOPSIS,Tech汽车选购

统一为效益型的决策矩阵用3种综合方法确定3种汽车的优劣顺序R最大化R归一化R模一化属性权重取信息熵法结果:w=(0.5330,0.3293,0.1377)T汽车选购统一为效益型的决策矩阵用3种综合方法确定3种汽车的1.简单加权和法(SAW)

v=(0.3110,0.3260,0.3629)TR归一化R最大化v=(0.7228,0.7492,0.8143)T2.加权积法(WP)

v=(0.3162,0.3277,0.3562)Tv归一化v=(0.4847,0.5316,0.5639)Tv=(0.3067,0.3364,0.3569)Tv归一化汽车选购

用3种综合方法确定3种汽车的优劣顺序1.简单加权和法(SAW)v=(0.3110,0.323.理想解法(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)C+=(0.2411,0.2840,0.4749)归一化3.理想解法(TOPSIS）R模一化vij=rijw

方法方案SAW(R归一化)SAW(R最大化)WPTOPSISA10.31100.31620.30670.2411A20.32600.32770.33640.2840A30.36290.35620.35690.4749汽车选购

用3种综合方法确定3种汽车的优劣顺序SAW(R归一化,最大化),WP结果差别很小,TOPSIS结果差别稍大.优劣顺序均为A3,A2,A1简单、直观的加权和法(SAW)是人们的首选.SAW的前提~属性之间相互独立,并且具有互补性.方法方案SAWSAWWPTOPSISA10.31100多属性决策应用的步骤1.确定决策目标、备选方案与属性集合；2.用量测、调查等手段确定决策矩阵和属性权重,

推荐用信息熵法由决策矩阵得出属性权重；3.将全部属性统一(如效益型)，并采用归一化、

最大化或模一化对决策矩阵标准化；4.选用加权和、加权积、TOPSIS等综合方法

计算方案对目标的权重，作为决策的依据.多属性决策应用的步骤1.确定决策目标、备选方案与属性集合；1.比例尺度变换的归一化和最大化归一化~分配模式(DistributiveMode)某一方案属性值改变引起其他方案属性值随之改变.最大化~理想模式(IdealMode)任一方案的属性值独立于最优方案外的其他方案.列最大值为1:各方案与占资源1的最优方案比较.列和为1:各方案分配总量固定(1单位)的资源.多属性决策应用中的几个问题1.比例尺度变换的归一化和最大化归一化~分配模式(D方案的优劣排序大体上一致(方案数量不多时).两种模式计算的结果数值上一般不会相同.在实际应用中究竟应该采用哪种模式?分配模式~决策者关心每个方案相对于其他方案的占优程度;需要对候选方案的优劣给出定量评价;特别用于资源分配问题.理想模式~决策者关心每个方案相对于基准指标的优劣;从众多候选方案中只选一个最优者.比例尺度变换的理想模式和分配模式方案的优劣排序大体上一致(方案数量不多时).两种模式计算的结2.区间尺度变换使用中的问题但区间尺度变换dij最小值(对每个j)都变为rij=0.区间尺度变换

~对原始权重dij作伸缩与平移变换两种变换dij最大值(对每个j)都变为rij=1.对比比例尺度变换的最大化虚拟一个极端的例子说明,某些实际问题适于采用比例尺度变换归一化,用最大化会出现较大谬误,而用区间尺度变换将得到极不合理的结果.2.区间尺度变换使用中的问题但区间尺度变换dij最小值(对常识：教学0.5万平分,科研0.5万给B.与常识一致与常识有别区间尺度严重不妥!区间尺度变换使用中的问题得分

教学X1(w1=0.5)科研X2(w2=0.5)教师A511教师B4999例.奖金1万元按教学和科研并重原则分配给A,B.理想模式(最大化)分配模式(归一化)A~0.25万元,B~0.75万元

把非常接近的教学原始分51和49分别变成1和0为什么？常识：教学0.5万平分,科研0.5万给B.与常识一致与常识3.方案的排序保持与排序逆转若各准则对目标的权重和原有方案对属性的权重都不变，当有新方案加入或旧方案退出时，原有方案的优劣排序是保持还是会逆转？用理想模式和分配模式可能会得到不同的结果.例.工作选择

(训练题15)

原始分

X1(w1=0.6)X2(w2=0.4)A141A215A322A441A4´61两种模式排序都是A1,A2,A3理想模式保持排序A1,A2,分配模式逆转.在一定条件下理想模式保持排序A1,A2.3.方案的排序保持与排序逆转若各准则对目标

新方案加入时,只要它对每个准则的权重都不超过原方案,用理想模式计算原方案的排序保持不变,用分配模式计算原方案的排序可能逆转.方案的排序保持与排序逆转分配模式~各方案对每一准则权重rij对i之和恒为1,新方案加入导致原来rij减少,稀释了原有资源,资源的重新分配可能导致原方案排序逆转.理想模式~各方案对每一准则权重rij对i最大值为1,新方案加入只要不改变原来的最大值,就不会稀释原有资源,原方案排序将保持不变.新方案加入时,只要它对每个准则的权重都不超过原方案小结与评注决策矩阵标准化的不同或综合方法的不同对最终决策的影响，远小于属性集合的不同及属性权重的不同对最终决策的影响.所以不要过度注意前者,而应对后者多些关注.实际应用中对于从众多候选方案中只选一个最优者的情况，多用理想模式；而那些需要对候选方案的优劣给出定量比较时，或者对资源按照候选方案的优劣进行分配时，多用分配模式.小结与评注决策矩阵标准化的不同或综合方法的不同对最终决策的影简单易行、具有一定合理性的办法订立全面评价一位职员的几条准则，如工作年限、教育程度、工作能力、道德品质等;确定各条准则在目标(职员晋升)中所占的权重;按照每一准则对各位申报者进行比较和评判;将准则的权重与按准则评判的结果加以综合,得到各位申报者的排序,作为职员晋升的决策.7.2 职员晋升职员晋升与汽车选购是有相同特点的决策问题，用多属性决策方法可以类似地加以解决.简单易行、具有一定合理性的办法订立全面评价一位职员的几条准则层次分析法(AHP,AnalyticHierarchyProcess）针对经济、社会领域作比较判断时主观因素作用较大,准则和方案的重要性难以量化的情况.Saaty于20世纪70年代提出(稍晚于多属性决策)的定性与定量相结合的,系统化、层次化的分析方法.在实际应用领域、处理问题类型、具体计算方法等方面,与多属性决策有不少类似和相通之处.职员晋升职员晋升问题建模的另一种常用方法.

层次分析法(AHP,AnalyticHierarch将决策问题自上而下地分为目标、准则、方案3个层次,直观地用一个层次结构图表示.二者综合得到方案对目标的权重.确定各准则

对目标的权重.确定各方案对每一准则的权重.1.层次结构图层次分析法(AHP)的几个要素将决策问题自上而下地分为目标、准则、方案3个层次,直观地用

确定n个准则X1,X2,…X4对目标Y的权重.A~成对比较阵工作年限X1,教育程度X2,工作能力X3,道德品质X4对汽车选购Y的成对比较阵:正互反阵

n个准则两两对比:aij~Xi和Xj对Y的重要性之比

对比采用相对尺度2.成对比较矩阵和特征向量

a12=1/2~X1与X2重要性之比是1:2Oa13=1/3~X1与X3重要性之比是1:3Oa23=1/2~X2与X3重要性之比是1:2O确定n个准则X1,X2,…X4对目标Y的权重.A~成对2.成对比较矩阵和特征向量

成对比较的一致性n个元素需做n(n1)/2次成对比较,要求全部一致是不现实、也不必要的.AHP容许成对比较存在不一致，并确定了这种不一致的容许范围.a12=1/2~X1与X2重要性之比是1:2X1与X3重要性之比应是1:4a23=1/2~X2与X3重要性之比是1:2

Oa13=1/3~成对比较不一致2.成对比较矩阵和特征向量成对比较的一致性n个元素需做成对比较完全一致2.成对比较矩阵和特征向量

假定X1,X2,…,Xn对Y的重要性之比已精确测定为w1:w2…:wn令aij=wi/wj成对比较阵A满足一致阵的各列均相差一个比例因子一致阵A的代数性质：任一列向量都是对应于n的特征向量.秩为1,唯一非零特征根为n.一致阵

成对比较完全一致2.成对比较矩阵和特征向量假定X1,2.成对比较矩阵和特征向量

取权向量为w=(w1,w2,,wn)T一致阵A的任一列向量都是对应于n的特征向量.如果成对比较阵A不一致(但在容许范围内)用对应于A最大特征根的特征向量(归一化后)为权向量w2.成对比较矩阵和特征向量取权向量为一致阵A的任3.一致性指标和一致性检验Saaty定义一致性指标:界定成对比较阵(正互反阵)A不一致的范围.n阶正互反阵A的最大特征根n，A是一致阵的充要条件为=n.CI=0时A是一致阵,CI越大A越不一致.用n的大小衡量A的不一致程度.比n大得越多,A与一致阵相差越大,用特征向量作为权向量引起的判断误差越大..3.一致性指标和一致性检验Saaty定义一致性指标:界定成对

当CR<0.1时通过一致性检验Saaty引入随机一致性指标RI——从1,2,…,9及1,1/2,…,1/9随机取值构成A,计算CI的平均值作为RI.3.一致性指标和一致性检验制定衡量CI

数值的标准，界定A不一致的范围.n345678910RI0.580.901.121.241.321.411.451.49Saaty给出应用时将n阶成对比较阵A的CI与同阶的RI比较.

当CR<0.1时通过一致性检验Saaty引入随机一致性指标准则对目标的成对比较阵计算最大特征根特征向量w及一致性指标CI.RI=0.90=4.0104CI=(-4)/(4-1)=0.0035归一化的w=(0.1223，0.2270，0.4236,0.2270)T

为权向量.CR=0.0035/0.90<0.1一致性检验通过

职员晋升准则对目标的成对比较阵计算最大特征根特征向量w及一致性指标4.综合权重3位职员对4个准则的成对比较阵

=(0.4505,0.3202,0.2292)T3位职员对晋升的综合权重

j1234w(2)

wj(3)0.13650.53960.40000.62500.12230.23850.29700.40000.23850.22700.62500.16340.20000.13650.4236

0.2270j3.01833.00923.00003.0183

CIj0.00920.004600.0092

Bj归一化得到wj(3)

W(3)=(w1(3),…,w4(3))CRj=CIj/RI<0.1,Bj通过一致性检验A归一化得到

w(2)3位职员的优劣顺序为A1,A2,A34.综合权重3位职员对4个准则的成对比较阵=(0.454.综合权重与多属性决策的简单加权和法比较:

W(3)~第3层(方案)对第2层(准则)的权向量构成的矩阵w(2)~第2层(准则)对第1层(目标)的权向量w(3)~第3层(方案)对第1层(目标)的权向量二者综合方法相同(矩阵W(3)和R的来源不同).wvRAHP推广到s层W(k)~第k层对第k1层的权向量构成的矩阵w(s)~最下层对第1层的权向量分层加权和法4.综合权重与多属性决策的简单加权和法5.1-9比较尺度Saaty提出1~9尺度:aij

=1,2,…,9及1,1/2,,…,1/9.尺度13579相同稍强强明显强绝对强aij=1,1/2,,…,1/9~Xi和Xj对Y重要性与上面相反

心理学家认为成对比较的因素不宜超过9个.

用1~3,1~5,…,1~17,…,1p~9p

(p=2,3,4,5),d+0.1~d+0.9(d=1,2,3,4)等27种比较尺度对若干实例构造成对比较阵，算出权向量，与实际对比发现，1~9尺度较优.

便于定性到定量的转化：Xi和Xj对Y重要性aij2468介于相邻数之间5.1-9比较尺度Saaty提出1~9尺度:aij=道德品质X4

工作能力X3

教育程度X2

工作年限X1

>10年X11

5~10年X12

2~5年X13

<2年X14

本科以上X21

本科X22

专科X23

中学X24

优X31

良X32

中X33

差X34

优X41

良X42

中X43

A1…A2…

Ak职员晋升Y每一准则分若干等级:工作年限、教育程度用入职时间和学历分级,工作能力、道德品质按照优、良、中划分.职员晋升问题的再讨论道德品质工作能力教育程度工作年限本科以上A1A2Ak职员晋升

w1=0.1223w2=0.2270w3=0.4236w4=0.2270总分

w11100w1280w1360w1430w11100w1290w1360w1430w11100w1280w1340w1410w11100w1280w1340

…工作4年、能力优秀、品质良好的本科毕业生Ak总分:

60×0.1223+90×0.2270+100×0.4236+80×0.2270=88.29每个申报者根据在准则中所处等级的位置对号入座.评定前确定标准分(如80),标准分以上才可以晋升.Ak

√

√

√

√

88.294个准则的权重仍为成对比较得到的w1,w2,w3,w4.每一准则中最高等级为100分，决定其他分数wij.

w1=0.1223w2=0.2270w3=0.4236w4建立由目标层、准则层、方案层等构成的层次结构.计算各个成对比较阵的特征根和特征向量，作一致性检验,通过后将特征向量取作权向量.构造下层各元素对上层每一元素的成对比较阵.对各层权向量进行综合，用分层加权和法计算最下层各元素对最上层元素的权重.层次分析法应用的步骤建立由目标层、准则层、方案层等构成的层次结构.计算各个成对比评注

~层次分析法与多属性决策的比较两种方法的重点都是确定准则对目标、方案对准则的权重，方法可分为相对量测和绝对量测;成对比较属于前者,用定量尺度来描述方案或准则的特征属于后者.

两种方法都用于解决决策问题，二者在步骤、方法上有很多相同之处，也有一些差别.对于尚无太多知识的新问题和模糊、抽象的准则,主要依赖相对量测;对已有充分了解的老问题和明确、具体的准则,应尽可能采用绝对量测.评注~层次分析法与多属性决策的比较两种方法的重点都是确定绝对量测的另一优点：新方案加入或老方案退出时原有方案的结果不会改变；用相对量测要重新做比较，原有方案的结果可能改变.一般来说，相对量测偏于主观、定性;绝对量测偏于客观、定量，应尽量采用绝对量测.应用中可将多属性决策和层次分析中的方法结合起来，如用成对比较阵来确定属性权重，用绝对量测确定决策矩阵.评注

~层次分析法与多属性决策的比较绝对量测的另一优点：新方案加入或老方案退出时原有方案的结果不某公司为增加产量,拓展市场拟制定10年规划,现有两种备选方案：新建厂房或改建厂房.问题据估计未来市场销路好与销路差的可能性之比是7:3.若投资400万元新建厂房，销路好时年收益100万元，销路差时年亏损20万元.若投资100万元改建厂房，销路好时年收益40万元，销路差时年收益10万元.从净利润最大化角度为公司确定决策.7.3 厂房新建还是改建某公司为增加产量,拓展市场拟制定10年规划,现有两种备选分析与

求解未来10年中有7年销路好、3年销路差.未来市场销路好与销路差的可能性之比是7:3.只需计算、比较两种方案10年的总利润,即可得到新建还是改建厂房的决策.新建厂房10年总利润：100⨉7-20⨉3-400=240,改建厂房10年总利润：40⨉7+10⨉3-100=210.未来10年销路好与销路差的概率分别是0.7与0.3.新建厂房10年总利润期望值:100⨉10⨉0.7-20⨉10⨉0.3-400=240，改建厂房10年总利润期望值:40⨉10⨉0.7+10⨉10⨉0.3-100=210以总利润期望值最大为目标的决策是新建厂房.分析与未来10年中有7年销路好、3年销路差.未来市场销路好与结果分析期望值看作随机事件多次重复出现的平均值，将期望值准则用于一次性决策会有较大风险.新建厂房比改建厂房虽然总利润期望值稍大,但是一次性风险大得多！

新建厂房总利润改建厂房总利润未来10年真的销路好100⨉10-400=60040⨉10-100=300新建厂房10年总利润期望值240万元改建厂房10年总利润期望值210万元未来10年真的销路差-20⨉10-400=-60010⨉10-100=0两种情况相差1200300结果分析期望值看作随机事件多次重复出现的平均值，将期望值准则对概率p的估计有多大变化就会导致决策的改变.结果分析新建厂房10年总利润的期望值E(1)=240改建厂房10年总利润的期望值E(2)=210p~未来10年销路好的概率(1-p~销路差的概率)

E(1)=10010p+(2010)(1p)400=1200p600

E(2)=4010p+1010(1p)100=300p令E(1)=E(2)若目前估计的概率p从0.7降到0.66(只下降约5%),按期望值准则决策将由新建厂房变为改建厂房.p=2/3当p<2/3时E(1)<E(2)决策对概率的变化相当敏感!对概率p的估计有多大变化就会导致决策的改变.结果分析新建厂房提出新方案~降低风险的折中方案如果3年销路好,未来7年销路仍好的概率将提高至0.9,若再投资200万元扩建,销路好时年收益为90万元,销路差时不盈不亏；若不扩建,年收益不变.如果3年销路差，未来7年预计销路一定也差，则不扩建，年收益也不变。先改建厂房经营3年，3年后视市场情况再定.第1次决策

~新建厂房还是改建厂房经营3年；第2次决策

~3年后扩建还是不扩建.第1次决策时为计算10年总利润期望值须对第2次决策的后果做出估计,即从全过程的终点向前推进.2次决策

提出新方案~降低风险的折中方案如果3年销路好,未来7年销决策树模型原问题决策树的构造原问题决策树的求解取最大值的方案为决策,砍掉其余分枝~决策节点,~状态节点,~结果节点.决策树模型原问题决策树的构造原问题决策树的求解取最大值的方案销路好p=0.9销路差p=0.1

加入新方案后决策树的构造决策树模型销路好加入新方案后决策树的构造决策树模型求解由结果节点开始，反向进行.=367=367=259//=270.9=270.9\\\\决策树模型E(3)1>E(3)2,决策2选择扩建,E=E(3)1=367,砍掉不扩建分支.E(3)=270.9>E(1)=240,决策1选择改建厂房经营3年.求解由结果节点开始，反向进行.=367=367=259//=小结与评注风险性决策

~决策中每个备选方案的后果至少存在两种状态,且各种状态的概率是可以估计的.决策树是求解风险性决策(特别是多次决策)常用的手段,具有直观、简便、逻辑关系清晰等优点.贝叶斯决策是解决这个问题的一种办法，参见拓展阅读7-3.多数实际问题属于一次性而非多次重复的决策，采用期望值准则可能会冒较大的风险，特别是几个随机状态出现的概率相差不大的情况.小结与评注风险性决策~决策中每个备选方案的后果至少存在两7.4循环比赛的名次

n支球队单循环赛，每场比赛只计胜负，没有平局.

根据比赛结果排出各队名次.常用方法：

按得分排序1,(2,3),(4,5),66支球队比赛结果(+~行队胜列队)3队胜2队排名132456

队号123456得分1/+-+++42-/-+++33++/+--34---/++25--+-/+26--+--/12,3队并列,4,5队并列，无法排名!4队胜5队OO合理吗?7.4循环比赛的名次n支球队单循环赛，每场比赛只计胜负单循环比赛的名次123456312456146325无法排名竞赛图（Tournament）……竞赛图的性质

必存在完全路径（按箭头方向通过全部顶点的路径）

若存在唯一的完全路径，则由它确定的顶点顺序与按得分排列的顺序一致每对顶点有且仅有一条有向边相连单循环比赛的名次123456312456146325无法排名单循环比赛的名次123456以下只考虑双向连通图竞赛图（Tournament）不具有唯一的完全路径时：

双向连通图——从任一顶点出发，至少存在一条有向路径到达另外任一顶点

其他：不易给出所有队的排名单循环比赛的名次123456以下只考虑双向连通图竞赛图（To双向连通竞赛图的排名123456邻接矩阵得分向量s=(4,3,3,2,2,1)=s(1)(1级得分)

(2级得分)存在i到j的有向弧否则

双向连通竞赛图的排名123456邻接矩阵得分向量s=(4,双向连通竞赛图的排名

对于n(>3)个顶点的双向连通竞赛图，存在正整数r，使邻接矩阵A满足Ar>0，A称素阵.用s*排名

素阵A的最大特征根为正单

根，对应正特征向量s，且s*eAkkk=¥®llim双向连通竞赛图的排名对于n(>3)个顶点的双向连通竞赛图，双向连通竞赛图的排名123456排名次序为{1，3，2，5，4，6}32,45排名132456?1:4分;2,3:3分;4,5:2分;6:1分.双向连通竞赛图的排名123456排名次序为{1，3，2，5每10年，美国联邦政府进行一次全国人口普查,各州在联邦众议院的代表名额也据此重新确定.公平的席位分配问题（apportionment）2000年人口普查后，犹他州向联邦政府提出控诉，说分配给北卡罗莱纳州的名额应该是他们的.问题的数学本质是什么？事实上，过去200年来，美国国会在名额分配上打过多起法律官司，曾有过长期争论并使用过4种分配方案.7.5 公平的席位分配每10年，美国联邦政府进行一次全国人口普查,各州在联邦众议一个简单例子系别学生比例20席的分配人数（%）比例结果甲10351.5

乙6331.5

丙3417.0总和200100.020.02021席的分配比例结果10.8156.6153.57021.00021问题三个系学生共200名(甲100，乙60，丙40)，代表会议共20席，按比例分配，三个系分别为10,6,4席.因学生转系,三系人数为103,63,34,如何分配20席?若代表会议增加1席，如何分配21席?比例加惯例对丙系公平吗？系别学生比例20席的分配人数（%）比例结果甲10351.510.3

乙6331.56.3

丙3417.03.4总和200100.020.020系别学生比例20席的分配人数（%）比例结果甲10351.510.310

乙6331.56.36

丙3417.03.44总和200100.020.02021席的分配比例结果10.815116.61573.570321.00021一个简单例子系别学生比例20席的分配2模型已知: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)模型已知:m方人数分别为p1,p2,…,pm,记总背景Hamilton(比例加惯例)方法A.Hamilton提出的这种办法1792年被美国国会否决

1850-1900年被美国国会采用(称为Vinton法)

又称为最大剩余法（GR:GreatestRemainders）或最大分数法（LF:LargestFractions），等等

席位悖论—总席位增加反而可能导致某州席位减少

1880年Alabama州曾遇到，又称Alabama悖论

该方法的另一个重大缺陷：（下页给例子）

人口悖论—某州人口增加较多反而可能该州席位减少

背景Hamilton(比例加惯例)方法A.HamilHamilton方法的不公平性1.p1,p2,…,

pm不变,N的增加会使某个ni减少(上例).2.N不变,pi比pj的增长率大,会使ni减少nj增加(下例).pinii=110311i=2637i=3343和20021pi1146434212ni116421pini1031063634420020pi114(+10.6%)6338(+11.8%)215ni116320Hamilton方法的不公平性1.p1,p2,…,p“公平”分配方法衡量公平分配的数量指标人数席位A方p1

n1B方p2n2当p1/n1=p2/n2

时，分配公平

p1/n1–p2/n2~对A的绝对不公平度p1=150,n1=10,p1/n1=15p2=100,n2=10,p2/n2=10p1=1050,n1=10,p1/n1=105p2=1000,n2=10,p2/n2=100p1/n1–p2/n2=5但后者对A的不公平程度已大大降低!虽二者的绝对不公平度相同若p1/n1>p2/n2

，对不公平A

p1/n1–p2/n2=5“公平”分配方法衡量公平分配的数量指标人数公平分配方案应使rA

,rB

尽量小设A,B已分别有n1,n2席,若增加1席,问应分给A,还是B?不妨设分配开始时p1/n1>p2/n2

，即对A不公平.~对A的相对不公平度将绝对度量改为相对度量类似地定义rB(n1,n2)

将一次性的席位分配转化为动态的席位分配,即“公平”分配方法若p1/n1>p2/n2

，定义公平分配方案应使rA,rB尽量小设A,B已分别有n1）若p1/(n1+1)>p2/n2

，则这席应给A2）若p1/(n1+1)<p2/n2

，3）若p1/n1>p2/(n2+1)，应计算rB(n1+1,n2)应计算rA(n1,n2+1)若rB(n1+1,n2)<rA(n1,n2+1),则这席应给讨论以下几种情况设初始p1/n1>p2/n2

问：p1/n1<p2/(n2+1)

是否会出现？A否!若rB(n1+1,n2)>rA(n1,n2+1),则这席应给B1）若p1/(n1+1)>p2/n2，则这席应给A2当rB(n1+1,n2)<rA(n1,n2+1),该席给ArA,rB的定义该席给A否则,该席给B

定义该席给Q值较大的一方推广到m方分配席位该席给Q值最大的一方相等比例法,即EP法(Huntington,1921)计算，当rB(n1+1,n2)<rA(n1,n2+1),三系用EP方法重新分配21个席位一席一席地将前19席分配完毕后的结果甲系：p1=103,n1=10乙系：p2=63,n2=6丙系：p3=34,n3=3与Hamilton法结果相同第20席第21席同上Q3最大，第21席给丙系甲系11席,乙系6席,丙系4席EP方法分配结果公平吗？Q1最大，第20席给甲系三系用EP方法重新分配21个席位一席一席地将前19席分配完20世纪20年代哈佛大学E.V.Huntington做了系统研究.EP法每增加1席地计算，不会出现席位悖论和人口悖论.

有没有其他的不公平度衡量指标？

当总席位为s时第i方分配的席位记作fi(p,s),fi(p,0)=0除数法（Huntington，1921）

对于非负整数n定义一个非负单调增函数d(n)

让s每次1席地递增至N，按照以下准则分配:

记ni=fi(p,s)，若则令fk(p,s+1)=nk+1,fi(p,s+1)=ni(i≠k)20世纪20年代哈佛大学E.V.Huntington做了５种除数法Huntington除数法除数d(n)不公平度的度量指标（设pi/ni≥pj/nj）以人名命名的称谓最大除数法（GD：Greatestdivisors)n+1njpi/pj-niJefferson;Seaton;d΄Hondt主要分数法（MF：Majorfraction)n+1/2nj/pj-ni/piWebster相等比例法（EP：Equalproportions)njpi/nipj-1Hill调和平均法（HM：Harmonicmean)2n(n+1)/

(2n+1)pi/ni-pj/njDean最小除数法（SD：Smallestdivisors)nnj-nipj/piAdamsEP(几何平均)MF(算术平均)HM(调和平均)５种除数法Huntington除数法除数d(n)不公平度的度5种除数法：一个数值例子

piqiGDMFEPHMSDA90619.061109999B71797.17978777C52595.25955655D33193.31933343E11821.18211112总和26000262626262626一般情况下，偏向程度也按照表中的顺序：

GD偏向人数pi较大的一方

SD偏向人数pi较小的一方5种除数法：一个数值例子piqiGDMFEPHMSDA90公平的席位分配：优化模型MF法：

最大剩余法(GR)实际上解决了以下优化问题：你能证明这些结论吗？任意lt范数(t≥1),如：1,2,∞范数EP法：公平的席位分配：优化模型MF法：最大剩余法(GR)实际上模型的公理化研究关键性质2)fi

(p,s)fi

(p,s+1)

~席位单调性~人口单调性3)若pi'

/pj'

≥

pi/pj,则fi(p',s)

≥

fi(p,s),

或fj(p',s)

fj(p,s)模型的公理化研究EP方法比最大剩余法(GR)更公平吗？已知总席位数s,人口向量p=(p1,p2,…,pm),P=Σpi份额向量q

=

(q1,…,qm)，qi=spi/Pni＝fi(p,s)表示人数为p、总席位为s时分配给第i方席位(参见教材注释)

1)

~份额性模型的公理化研究关键性质2)fi(p,s)fiGR方法满足性质1，但不满足性质2,3.

除数方法满足性质2,3,但不满足性质1.模型的公理化研究ipiqiGDMFEPHMSDGR19149091.49949390898892216601.66122222314601.46112222414501.45112221514401.44112221614001.40111221711001.10111121100000100100100100100100100GR方法满足性质1，但不满足性质2,3.除数方法满模型的公理化研究可以找到同时满足份额性和席位单调性的方法.已经证明：对于m≥4,N≥m+3,不存在满足3条性质(份额性、席位单调性、人口单调性)的分配方法.关于席位分配问题的历史发展状况、数学研究方法的完整叙述：M.L.Balinski&H.P.Young,FiarRepresentation2001年第2版模型的公理化研究可以找到同时满足份额性和席位单调性的方法.已席位分配问题评述

建立“公平分配席位”模型的关键是建立衡量公平程度的数量指标.

对各种方法违反某条公理的概率也有研究（仿真）

如果采用公理化方法——提出公平分配席位的理想化原则，那么该问题尚未彻底解决——已证明不存在满足一组公理的席位分配方法.

人们提出过上百种方法，还研究、比较过方法的相容性、稳定性、无偏性等.MF无偏！

上述讨论可推广到m变化的情形、有上下限的情形等.席位分配问题评述建立“公平分配席位”模型的关键是建立衡量历史资料及权力指标

美国国会实际采用过的方法：1830年前采用GD1840年采用MF1850-1900年采用GR（有时辅以调整）1910年采用MF1920年没有重新分配席位1930年后采用EP相关问题：得到席位，就意味着有权力吗？投票规则；权力指标计量政治学历史资料及权力指标美国国会实际采用过的方法：1830年前采7.6 存在公平的选举吗在公众生活和政治活动中,靠投票选举决定的事情众多：人们都希望公平、公正的选举.国际奥委会一轮又一轮投票选出奥运会举办城市推选班长、队长竞选市长、总统评选最佳影片、优秀运动员推举旅游胜地、宜居城市什么是真正的公平？世界上存在公平的选举吗？7.6 存在公平的选举吗在公众生活和政治活动中,靠投票选举决对投票选举的表述和约定每位选民对所有候选人按照偏爱程度所作的排序称为一次投票.根据全体选民的投票确定哪位候选人是获胜者的规则称为选举方法.按照公认的民主法则和选民的理性行为对选举的公平、公正做出的一些规定，称为公平性准则.

介绍几种选举方法和几条公平性准则讨论是否存在满足全部公平性准则的选举方法不可能性定理应用实例对投票选举的表述和约定每位选民对所有候选人按照偏爱程度所作的

例.一个班30名学生从A,B,C,D共4支球队中投票选举喜爱的球队,每个学生将球队从第1名排到第4名.票数11109第1名BCA第2名DDD第3名CAC第4名ABBB是获胜者吗？但是近2/3投票人将B排到最后一名.C是获胜者！因为不仅没有人将C排到最后，而且把C排在第1名的只比把B排在第1名的少1人.D是获胜者！因为没有人把D排到第2名以后.怎么确定获胜者呢？例.一个班30名学生从A,B,C,D共4支球5种选举方法票数11109第1名BCA第2名DDD第3名CAC第4名ABB1.简单多数法：得到第1名票数最多的候选人为获胜者.优点：易于实施.按照简单多数法获胜者是B！缺点：没有考虑除投票人把哪位候选人排在第1名以外的全部排序信息.好的投票方法应该考虑更多的排序信息.选举喜爱球队5种选举方法票数11109第1名BCA第2名DDD第3名CA2.单轮决胜法：得到第1名票数最多和次多的两位候选人进入决胜投票，由简单多数法确定决胜投票的获胜者，并定为整个选举的获胜者.票数11109第1名BCA第2名DDD第3名CAC第4名ABB票数11109第1名BCC第2名CBB假设所有投票人对B,C的偏爱不改变.按照单轮决胜法获胜者是C！以下均做此假设.得到第1名票数最多和次多的B,C进入决胜投票.2.单轮决胜法：得到第1名票数最多和次多的两位候选人进入决胜3.系列决胜法：进行多轮决胜投票,每轮只淘汰得第1名票数最少的候选人,当剩下两位候选人时,由简单多数法决定获胜者,并定为整个选举的获胜者.票数11109第1名BCA第2名DDD第3名CAC第4名ABB票数11109第1名BCA第2名CAC第3名ABB票数11109第1名BCC第2名CBB淘汰D,进入第2轮投票淘汰A,进入第3轮投票按照系列决胜法获胜者是C！3.系列决胜法：进行多轮决胜投票,每轮只淘汰得第1名票数最少4.Coombs法：与系列决胜法的多轮投票类似，但每轮只淘汰倒数第1名票数最多的候选人.票数11109第1名DCA第2名CDD第3名AAC票数11109第1名DCD第2名CDC按照Coombs法获胜者是D！票数11109第1名BCA第2名DDD第3名CAC第4名ABB淘汰B,进入第2轮投票淘汰A,进入第3轮投票4.Coombs法：与系列决胜法的多轮投票类似，但每轮只5.Borda计数法：对每一张选票,排倒数第1名的候选人得1分,排倒数第2名的得2分,依此下去,排第1名的得分是候选人的总数。将全部选票中各位候选人的得分求和,总分最高的为获胜者.按照Borda计数法获胜者是D！A：第1名9票，第3名10票，第4名11票，

A总分:9×4+10×2+11×1=67C总分:10×4+20×2=80B总分:11×4+19×1=63票数11109第1名BCA第2名DDD第3名CAC第4名ABBD总分:30×3=

905.Borda计数法：对每一张选票,排倒数第1名的候选人选举方法获胜者简单多数法B单轮决胜法C系列决胜法CCoombs法DBorda计数法D在投票者对候选人同样的偏爱下，不同的选举方法会导致不同的结果!票数11109第1名BCA第2名DDD第3名CAC第4名ABB5种选举方法的结果(选举喜爱球队)一个既有趣又令人不安的现象！选举方法获胜者简单多数法B单轮决胜法C系列决胜法CCoomb选举中的公平性准则换一个角度思考:在公认的民主法则和选民的理性行为下,选举方法应该满足哪些公平性准则?5种选举方法满足或者违反了其中哪些准则?自然提出的问题：哪一种选举办法才是公平的？哪位候选人是获胜者不仅取决于选民的偏爱,而且与采用的选举方法有关.选举中的公平性准则换一个角度思考:在公认的民主法则和选民的1.多数票准则：得到第1名票数超过选民半数的候选人应当是获胜者.简单多数法（得到第1名票数最多的候选人为获胜者）满足多数票准则.证明：若某候选人得到第1名票数超过半数，那么他必定是第1名票数最多的候选人，按照简单多数法他是获胜者.单轮决胜法和系列决胜法满足多数票准则.证明类似.选举中的公平性准则说明一种选举方法满足某条准则,需要证明.1.多数票准则：得到第1名票数超过选民半数的候选人应当是获胜Borda计数法违反多数票准则.票数98541第1名CACAB第2名DDDBA第3名ABBDD第4名BCACC例.27位选民对4位候选人的投票结果：按照Borda计数法计算得分：D:22×3+5×2=76,C:69，B:51，A:74.获胜者是D.但是C的第1名票数(14)过半数！存在用Borda计数法决定获胜者违反多数票准则的选举.用Borda计数法每次选举都会违反这个准则？只需举出一个反例⨉Borda计数法违反多数票准则.票数98541第1名CACAD与B对决,票数比是19:112.获胜者准则：如果候选人X在与每位候选人的两两对决中都获胜，那么X应当是获胜者.D与C对决,票数比是20:10D与A对决,票数比是21:9D在两两对决中都获胜.单轮、系列决胜法获胜者是CCoombs法和Borda法获胜者是D若某种选举方法确定的获胜者不是D,那么它就违反获胜者准则!简单多数法、单轮和系列决胜法违反获胜者准则!票数11109第1名BCA第2名DDD第3名CAC第4名ABB选举喜爱球队简单多数法获胜者是BCoombs法和Borda法

呢？D与B对决,票数比是19:112.获胜者准则：如果候选人3.失败者准则：如果候选人Y在与每位候选人的两两对决中都未获胜,那么Y不应当是获胜者.若某种投票方法确定的获胜者是B,那么它就违反失败者准则!简单多数法违反失败者准则!票数11109第1名BCA第2名DDD第3名CAC第4名ABB选举喜爱球队简单多数法获胜者是BB与D对决,票数比是11:19B与C对决,票数比是11:19B与A对决,票数比是11:19D在两两对决中未获胜.3.失败者准则：如果候选人Y在与每位候选人的两两对决中都未4.无关候选人独立性准则：假定在最终排序中候选人X领先于候选人Y，如果其他一位候选人退出选举，或者一位新的候选人进入选举，那么在最终排序中候选人X仍领先于候选人Y.用系列决胜法最终排序是C,B,A,D.票数11109第1名DCA第2名CDD第3名AAC票数11109第1名DCD第2名CDCB退出,偏爱不变淘汰A,进入第2轮B退出,其余球队最终排序是D,C,A.系列决胜法违反独立性准则.

选举喜爱球队票数11109第1名BCA第2名DDD第3名CAC第4名ABB4.无关候选人独立性准则：假定在最终排序中候选人X领先于候5.单调性准则：

假定候选人X在一次选举的最终排序中居于某个位置，如果某些选民只将X的顺序提前而其他候选人的排序不变，那么对于新的选举X在最终排序中的位置不应在原来位置的后面.简单多数法和Borda计数法显然满足单调性准则.违反单调性准则看来似乎是荒谬的，而单轮决胜法和系列决胜法就违反单调性准则!若选民对X的排序没有后移，那么最终排序中X相对其他候选人的优先性不应改变.

5.单调性准则：假定候选人X在一次选举的最终排序中居于5种选举方法满足或者违反哪一条公平性准则简单多数法、单轮决胜法、系列决胜法满足多数票准则，Borda计数法违反多数票准则.简单多数法、单轮和系列决胜法违反获胜者准则.简单多数法违反失败者准则.系列决胜法违反独立性准则.简单多数法、Borda计数法满足单调性准则，单轮决胜法、系列决胜法违反单调性准则.满足全部公平性准则的选举方法是否存在?需要继续研究直到找出这样的一种方法吗？5种选举方法满足或者违反哪一条公平性准则简单多数法、单轮决胜Arrow不可能性定理Arrow：“我开始有种想法，也许不存在满足所有我认为是合理条件的选举方法，我着手去证明这点，实际上只用了不过几天时间”。1951年Arrow列出自己的公平性准则，并且为找不