数学模型第07章第五版ppt课件.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 dij Ai对Xj的取值 原始权重 3种汽车价格 万元 25 18 12 3种汽车性能 打分 10分满分 9 7 5 3种汽车款式 7 7 5 以汽车选购为例说明如何确定决策矩阵 属性权重以及利用综合方法得到决策结果 1 决策矩阵及其标准化 m个备选方案A1 A2 Am 决策矩阵 dij Ai对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个准则两两对比 aij Xi和Xj对Y的重要性之比 对比采用相对尺度 2 成对比较矩阵和特征向量 A 112131221121321221121 2 成对比较矩阵和特征向量 成对比较的一致性 n个元素需做n n 1 2次成对比较 要求全部一致是不现实 也不必要的 AHP容许成对比较存在不一致 并确定了这种不一致的容许范围 a12 1 2 X1与X2重要性之比是1 2 X1与X3重要性之比应是1 4 a23 1 2 X2与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 当CR 0 1时通过一致性检验 Saaty引入随机一致性指标RI 从1 2 9及1 1 2 1 9随机取值构成A 计算CI的平均值作为RI 3 一致性指标和一致性检验 制定衡量CI数值的标准 界定A不一致的范围 Saaty给出 应用时将n阶成对比较阵A的CI与同阶的RI比较 准则对目标的成对比较阵 计算最大特征根 特征向量w及一致性指标CI RI 0 90 归一化的w 0 1223 0 2270 0 4236 0 2270 T为权向量 A 112131221121321221121 职员晋升 4 综合权重 3位职员对4个准则的成对比较阵 0 4505 0 3202 0 2292 T 3位职员对晋升的综合权重 4 1341 2121 41 21 Bj归一化得到wj 3 W 3 w1 3 w4 3 CRj CIj RI 0 1 Bj通过一致性检验 A归一化得到w 2 3位职员的优劣顺序为A1 A2 A3 4 综合权重 与多属性决策的简单加权和法比较 W 3 第3层 方案 对第2层 准则 的权向量构成的矩阵 w 2 第2层 准则 对第1层 目标 的权向量 w 3 第3层 方案 对第1层 目标 的权向量 二者综合方法相同 矩阵W 3 和R的来源不同 AHP推广到s层 W k 第k层对第k 1层的权向量构成的矩阵 w s 最下层对第1层的权向量 分层加权和法 5 1 9比较尺度 Saaty提出1 9尺度 aij 1 2 9及1 1 2 1 9 心理学家认为成对比较的因素不宜超过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重要性 aij 每一准则分若干等级 工作年限 教育程度用入职时间和学历分级 工作能力 道德品质按照优 良 中划分 职员晋升问题的再讨论 工作4年 能力优秀 品质良好的本科毕业生Ak总分 60 0 1223 90 0 2270 100 0 4236 80 0 2270 88 29 每个申报者根据在准则中所处等级的位置对号入座 评定前确定标准分 如80 标准分以上才可以晋升 88 29 4个准则的权重仍为成对比较得到的w1 w2 w3 w4 每一准则中最高等级为100分 决定其他分数wij 建立由目标层 准则层 方案层等构成的层次结构 计算各个成对比较阵的特征根和特征向量 作一致性检验 通过后将特征向量取作权向量 构造下层各元素对上层每一元素的成对比较阵 对各层权向量进行综合 用分层加权和法计算最下层各元素对最上层元素的权重 层次分析法应用的步骤 评注 层次分析法与多属性决策的比较 两种方法的重点都是确定准则对目标 方案对准则的权重 方法可分为相对量测和绝对量测 成对比较属于前者 用定量尺度来描述方案或准则的特征属于后者 两种方法都用于解决决策问题 二者在步骤 方法上有很多相同之处 也有一些差别 对于尚无太多知识的新问题和模糊 抽象的准则 主要依赖相对量测 对已有充分了解的老问题和明确 具体的准则 应尽可能采用绝对量测 绝对量测的另一优点 新方案加入或老方案退出时原有方案的结果不会改变 用相对量测要重新做比较 原有方案的结果可能改变 一般来说 相对量测偏于主观 定性 绝对量测偏于客观 定量 应尽量采用绝对量测 应用中可将多属性决策和层次分析中的方法结合起来 如用成对比较阵来确定属性权重 用绝对量测确定决策矩阵 评注 层次分析法与多属性决策的比较 某公司为增加产量 拓展市场拟制定10年规划 现有两种备选方案 新建厂房或改建厂房 问题 据估计未来市场销路好与销路差的可能性之比是7 3 若投资400万元新建厂房 销路好时年收益100万元 销路差时年亏损20万元 若投资100万元改建厂房 销路好时年收益40万元 销路差时年收益10万元 从净利润最大化角度为公司确定决策 7 3厂房新建还是改建 分析与求解 未来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年总利润期望值240万元改建厂房10年总利润期望值210万元 对概率p的估计有多大变化就会导致决策的改变 结果分析 新建厂房10年总利润的期望值E 1 240改建厂房10年总利润的期望值E 2 210 p 未来10年销路好的概率 1 p 销路差的概率 E 1 100 10 p 20 10 1 p 400 1200p 600 E 2 40 10 p 10 10 1 p 100 300p 令E 1 E 2 若目前估计的概率p从0 7降到0 66 只下降约5 按期望值准则决策将由新建厂房变为改建厂房 决策对概率的变化相当敏感 提出新方案 降低风险的折中方案 如果3年销路好 未来7年销路仍好的概率将提高至0 9 若再投资200万元扩建 销路好时年收益为90万元 销路差时不盈不亏 若不扩建 年收益不变 如果3年销路差 未来7年预计销路一定也差 则不扩建 年收益也不变 先改建厂房经营3年 3年后视市场情况再定 第1次决策 新建厂房还是改建厂房经营3年 第2次决策 3年后扩建还是不扩建 第1次决策时为计算10年总利润期望值须对第2次决策的后果做出估计 即从全过程的终点向前推进 2次决策 决策树模型 原问题决策树的构造 原问题决策树的求解 取最大值的方案为决策 砍掉其余分枝 加入新方案后决策树的构造 决策树模型 求解由结果节点开始 反向进行 决策树模型 E 3 1 E 3 2 决策2选择扩建 E E 3 1 367 砍掉不扩建分支 E 3 270 9 E 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满足Ar 0 A称素阵 双向连通竞赛图的排名 排名次序为 1 3 2 5 4 6 3 2 4 5 排名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 n1 p2 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 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 定义 1 若p1 n1 1 p2 n2 则这席应给A 2 若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 则这席应给B 当rB n1 1 n2 rA n1 n2 1 该席给A 该席给A 否则 该席给B 推广到m方分配席位 该席给Q值最大的一方 相等比例法 即EP法 Huntington 1921 三系用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席给甲系 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 种除数法 EP 几何平均 MF 算术平均 HM 调和平均 5种除数法 一个数值例子 一般情况下 偏向程度也按照表中的顺序 GD偏向人数pi较大的一方SD偏向人数pi较小的一方 公平的席位分配 优化模型 MF法 最大剩余法 GR 实际上解决了以下优化问题 你能证明这些结论吗 任意lt范数 t 1 如 1 2 范数 EP法 模型的公理化研究 关键性质 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 P ni fi p s 表示人数为p 总席位为s时分配给第i方席位 参见教材注释 1 份额性 GR方法满足性质1 但不满足性质2 3 除数方法满足性质2 3 但不满足性质1 模型的公理化研究 模型的公理化研究 可以找到同时满足份额性和席位单调性的方法 已经证明 对于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 相关问题 得到席位 就意味着有权力吗 投票规则 权力指标 计量政治学 7 6存在公平的选举吗 在公众生活和政治活动中 靠投票选举决定的事情众多 人们都希望公平 公正的选举 国际奥委会一轮又一轮投票选出奥运会举办城市 推选班长 队长 竞选市长 总统 评选最佳影片 优秀运动员 推举旅游胜地 宜居城市 什么是真正的公平 世界上存在公平的选举吗 对投票选举的表述和约定 每位选民对所有候选人按照偏爱程度所作的排序称为一次投票 根据全体选民的投票确定哪位候选人是获胜者的规则称为选举方法 按照公认的民主法则和选民的理性行为对选举的公平 公正做出的一些规定 称为公平性准则 介绍几种选举方法和几条公平性准则 讨论是否存在满足全部公平性准则的选举方法 不可能性定理 应用实例 例 一个班30名学生从A B C D共4支球队中投票选举喜爱的球队 每个学生将球队从第1名排到第4名 B是获胜者吗 但是近2 3投票人将B排到最后一名 C是获胜者 因为不仅没有人将C排到最后 而且把C排在第1名的只比把B排在第1名的少1人 D是获胜者 因为没有人把D排到第2名以后 怎么确定获胜者呢 5种选举方法 1 简单多数法 得到第1名票数最多的候选人为获胜者 优点 易于实施 按照简单多数法获胜者是B 缺点 没有考虑除投票人把哪位候选人排在第1名以外的全部排序信息 好的投票方法应该考虑更多的排序信息 选举喜爱球队 2 单轮决胜法 得到第1名票数最多和次多的两位候选人进入决胜投票 由简单多数法确定决胜投票的获胜者 并定为整个选举的获胜者 假设所有投票人对B C的偏爱不改变 按照单轮决胜法获胜者是C 得到第1名票数最多和次多的B C进入决胜投票 3 系列决胜法 进行多轮决胜投票 每轮只淘汰得第1名票数最少的候选人 当剩下两位候选人时 由简单多数法决定获胜者 并定为整个选举的获胜者 淘汰D 进入第2轮投票 淘汰A 进入第3轮投票 按照系列决胜法获胜者是C 4 Coombs法 与系列决胜法的多轮投票类似 但每轮只淘汰倒数第1名票数最多的候选人 按照Coombs法获胜者是D 淘汰B 进入第2轮投票 淘汰A 进入第3轮投票 5 Borda计数法 对每一张选票 排倒数第1名的候选人得1分 排倒数第2名的得2分 依此下去 排第1名的得分是候选人的总数 将全部选票中各位候选人的得分求和 总分最高的为获胜者 按照Borda计数法获胜者是D A 第1名9票 第3名10票 第4名11票 A总分 9 4 10 2 11 1 67 C总分 10 4 20 2 80 B总分 11 4 19 1 63 D总分 30 3 90 在投票者对候选人同样的偏爱下 不同的选举方法会导致不同的结果 5种选举方法的结果 选举喜爱球队 一个既有趣又令人不安的现象 选举中的公平性准则 换一个角度思考 在公认的民主法则和选民的理性行为下 选举方法应该满足哪些公平性准则 5种选举方法满足或者违反了其中哪些准则 自然提出的问题 哪一种选举办法才是公平的 哪位候选人是获胜者不仅取决于选民的偏爱 而且与采用的选举方法有关 1 多数票准则 得到第1名票数超过选民半数的候选人应当是获胜者 简单多数法 得到第1名票数最多的候选人为获胜者 满足多数票准则 证明 若某候选人得到第1名票数超过半数 那么他必定是第1名票数最多的候选人 按照简单多数法他是获胜者 单轮决胜法和系列决胜法满足多数票准则 证明类似 选举中的公平性准则 说明一种选举方法满足某条准则 需要证明 Borda计数法违反多数票准则 例 27位选民对4位候选人的投票结果 按照Borda计数法计算得分 D 22 3 5 2 76 C 69 B 51 A 74 获胜者是D 但是C的第1名票数 14 过半数 存在用Borda计数法决定获胜者违反多数票准则的选举 用Borda计数法每次选举都会违反这个准则 只需举出一个反例 D与B对决 票数比是19 11 2 获胜者准则 如果候选人X在与每位候选人的两两对决中都获胜 那么X应当是获胜者 D与C对决 票数比是20 10 D与A对决 票数比是21 9 D在两两对决中都获胜 单轮 系列决胜法获胜者是C Coombs法和Borda法获胜者是D 若某种选举方法确定的获胜者不是D 那么它就违反获胜者准则 简单多数法 单轮和系列决胜法违反获胜者准则 选举喜爱球队 简单多数法获胜者是B Coombs法和Borda法呢 3 失败者准则 如果候选人Y在与每位候选人的两两对决中都未获胜 那么Y不应当是获胜者 若某种投票方法确定的获胜者是B 那么它就违反失败者准则 简单多数法违反失败者准则 选举喜爱球队 简单多数法获胜者是B B与D对决 票数比是11 19 B与C对决 票数比是11 19 B与A对决 票数比是11 19 D在两两对决中未获胜 4 无关候选人独立性准则 假定在最终排序中候选人X领先于候选人Y 如果其他一位候选人退出选举 或者一位新的候选人进入选举 那么在最终排序中候选人X仍领先于候选人Y 用系列决胜法最终排序是C B A D B退出 偏爱不变 淘汰A 进入第2轮 B退出 其余球队最终排序是D C A 系列决胜法违反独立性准则 选举喜爱球队 5 单调性准则 假定候选人X在一次选举的最终排序中居于某个位置 如果某些选民只将X的顺序提前而其他候选人的排序不变 那么对于新的选举X在最终排序中的位置不应在原来位置的后面 简单多数法和Borda计数法显然满足单调性准则 违反单调性准则看来似乎是荒谬的 而单轮决胜法和系列决胜法就违反单调性准则 若选民对X的排序没有后移 那么最终排序中X相对其他候选人的优先性不应改变 5种选举方法满足或者违反哪一条公平性准则 简单多数法 单轮决胜法 系列决胜法满足多数票准则 Borda计数法违反多数票准则 简单多数法 单轮和系列决胜法违反获胜者准则 简单多数法违反失败者准则 系列决胜法违反独立性准则 简单多数法 Borda计数法满足单调性准则 单轮决胜法 系列决胜法违反单调性准则 满足全部公平性准则的选举方法是否存在 需要继续研究直到找出这样的一种方法吗 Arrow不可能性定理 Arrow 我开始有种想法 也许不存在满足所有我认为是合理条件的选举方法 我着手去证明这点 实际上只用了不过几天时间 1951年Arrow列出自己的公平性准则 并且为找不到满足所有准则的选举方法而困扰 他不断修正提出的准则 一再尝试 但是没有结果 Arrow不可能性定理 修正版本 任何选举方法都至少违反下列4条准则之一 多数票准则 获胜者准则 独立性准则 单调性准则 按照任何选举方法进行的每一次投票都至少违反4条准则之一 对于任意给出的选举方法 总可以发现选民对候选人的一次投票 使得在这种选举方法下投票结果至少违反4条准则之一 Arrow不可能性定理 重新审查所谓公平性准则 其中最受人质疑的是独立性准则 认为这条准则的要求太高 Saari提出考虑到选民对候选人偏爱强度的二元强度独立性准则 代替原来的独立性准则 得到Saari可能性定理 存在满足所有准则的选举方法 Saari可能性定理 Borda计数法就是满足可能性定理中全部准则的一种选举方法 Arrow不可能性定理的原始版本 Saari可能性定理的内容 以及其他一些选举方法 可参看拓展知识7 3 选举方法和公平性准则的应用实例 例1 用系列决胜法推选2004年奥运会举办城市 国际奥委会采用系列决胜法选择奥运会举办城市 先从申办城市中挑出几座候选城市 奥委会成员进行几轮投票 不要求对候选城市排序 只要求投给最偏爱的一座城市 每轮将得票最少的城市淘汰 直至选出获胜城市 2004年奥运会举办城市的推选过程 第1轮投票对5座候选城市得票最少且相同的布宜诺斯艾利斯和开普敦进行附加投票 结果布宜诺斯艾利斯被淘汰 第2轮投票结果斯德哥尔摩被淘汰 第3轮投票结果开普敦被淘汰 第4轮投票最终获胜者是雅典 采用系列决胜法在推选过程中可能出现的情况 如果第2轮投票中斯德哥尔摩的19票在第3轮投票中都投给开普敦 开普敦将得到22 19 41票 第3轮淘汰的将是罗马 如果第3轮投票中罗马的35票在第4轮投票中都投给开普敦 那么开普敦将是最终的获胜者 尽管开普敦在第1轮投票中是得票最少的城市之一 但是直到第3轮才被淘汰 如果下面的情况发生呢 第1轮投票中差点被淘汰的城市可能最终获胜 采用系列决胜法可能违反单调性准则 假定第1轮投票原来投给开普敦的有一票转投给雅典 有利于雅典的一点改变 会导致什么结果 第1轮开普敦被淘汰 第2轮可能出现的结果 第2轮斯德哥尔摩被淘汰 第3轮可能出现的结果 第3轮罗马被淘汰 雅典和布宜诺斯艾利斯进入最后一轮竞争 而布宜诺斯艾利斯有可能获胜 第1轮投票有利于雅典的一点改变 可使雅典在最终排序中落到第2位 违反单调性准则 例2 用单轮决胜法进行的2002年法国总统选举 在初次投票中不要求选民对候选人排序 只投票给最偏爱的一位候选人 法国总统选举采用单轮决胜法 获得票数最多和次多的两位候选人进入决胜投票 决胜投票由简单多数法决定获胜者 2002年法国总统的选举过程 在2002年法国总统选举中进入初次投票的有16位候选人 得票最多和次多的希拉克 Chirac 和勒庞 LePen 进入决胜投票 结果希拉克以82 的绝对优势获胜 采用单轮决胜法在选举过程中可能出现的情况 希拉克 著名右翼政治家 勒庞 极右翼政治家 有60 以上选民反对他 若斯潘 左翼政治家 在初次投票中希拉克 勒庞和若斯潘 Jospin 3位候选人得票都超过15 且相差不大 希拉克和若斯潘本是被看好能够进入决胜投票的势均力敌的两位候选人 但勒庞以稍多一点的票数挤掉了若斯潘 如果不用单轮决胜法而采用系列决胜法 希拉克和若斯潘最终将有一场决战 结果难料 采用单轮决胜法可能违反单调性准则 假定在初次投票中有1 的选民将原来投给勒庞的票转投希拉克 使勒庞的得票低于若斯潘 决胜投票将是希拉克和若斯潘竞选 而一旦若斯潘获胜 这是可能的 就违反了单调性准则 按照选民最初的真实意愿是希拉克位居第1 而有利于希拉克的1 选民的转投这一点点改变 却可能使希拉克在最终排序中落到第2位 后记15年之后的2017年法国总统选举 得票最多和次多的马克龙 Macron 和勒庞 2002年法国总统选举中LePen的女儿 进入决胜投票 决胜投票结果马克龙以66 的优势获胜 与2002年的选举对比发现 旧的一幕几乎重演 采用单轮决胜法同样可能出现违反单调性准则的情况 单调性准则与虚假投票 法国总统选举的实例清楚地说明单调性准则的重要性 那些最偏爱希拉克将他排到第1位的选民 可能会伤害希拉克在最终排序中的位置 偏爱希拉克的选民的最佳策略是把一部分票投给勒庞 增加勒庞领先若斯潘进入决胜投票的机会 以避免让若斯潘进入有可能胜过希拉克的决胜投票 单轮决胜法对于虚假投票非常敏感 虚假投票 投票不反映选民的真实意愿 而是帮助所喜爱的候选人最终得到某个位置 小结与评注 5种选举方法中简单多数法 单轮决胜法和系列决胜法都只考虑第1名的票数 这3种方法适用于只要求选民给最喜爱的一位候选人投票的情况 5种选举方法中只有Borda计数法利用了选民对候选人的全部排序信息 本节讨论的选举过程可以看作一种群体决策 即根据若干人对某些对象的个体决策结果 如每位选民的投票 综合得到这个群体的决策 社会上有许多专门机构通过民意调查了解部分群众对社会福利 内外政策及领导人的态度 然后用群体决策方法归纳出国民的整体倾向 本节讨论的选举问题可以看作公理化建模过程 提出的公平性准则认为是无需证明的公理 从公理出发进行逻辑推理 公理不合适 过严 过多甚至相互矛盾 会导致得不到满足公理的结论