《运筹学汇总》由会员分享，可在线阅读，更多相关《运筹学汇总（17页珍藏版）》请在金锄头文库上搜索。
1、前言：投票博弈（一）投票博弈知识点：【定义 1】：设投票博弈中，参加投票人的集合为 N=1,2,n 。N 的一个子集 S 称为一个联盟。【定义 2】：设投票博弈中, 若对某一个联盟 S 满足：（ 1）投票人 i 在 S 中；（2）S中的投票人一致同意，则提出的议案通过；且 S i中的投票人一致同意，则提出的议案不能通过。则该联盟 S 称为投票人 i 的一个摆盟。【定义 3】：用 i 表示第 i 个投票人的摆盟数，则记 i= i /（1+ 2+n） i=1，2,n=( 1 , 2 , , n) 称为 Banzhaf 势指标。一般情况下，可用 Banzhaf 势指标 来表示投票人的权力大小。-例
2、1：一个董事会有 4 位董事，其中董事长有 3 票，副董事长有 2 票，剩余 2 名董事各有1 票，进行投票表决。表决的规则是：超过半数票，讨论的提案通过。问：1）副董事长的权力和 1 个董事的权力有多大的差异？2）若表决的规则是：超过 2/3 票，讨论的提案通过。副董事长的权力和 1 个董事的权力有多大的差异？1）解：投票人集合：N=1，2，3，4 。设 Si 为投票人 i 的摆盟，i =1,2,3,4。S 1：1,2 、 1,3 、 1,4 、 1,2,3 、 1,2,4 、 1,3,4S 2 ：2,1 、 2,3,4S 3 ：3,1 、 3,2,4S 4 ：4,1 、 4,2,3摆盟数为
3、：1 = 6, 2 = 2, 3 = 2, 4 = 2.势指标为：1 = 1/2, 2 = 3 = 4 = 1/6（即副董事长与董事权力无差异） 。2）解：若表决的规则改为：达到或超过 2/3 时，提出的议案通过。解：投票人集合：N=1,2,3,4 。设 Si 为投票人 i 的摆盟，i=1,2,3,4。S1：1,2,1,2,3,1,2,4,1,3,4,1,2,3,4S2：2,1 、 2,1,3 、 2,1,4S3：3,1,4S4：4,1,3摆盟数为：1 = 5, 2 = 3, 3 = 1, 4 = 1.势指标为：1 = 5/10，2 = 3/10, 3= 4 = 1/10例 2：一个董事会由
4、4 位股东组成，每位股东依次拥有股份为：40%，30% ，20%，10%。在董事会投票时，每位股东的票数与他所拥有的股份成正比。当投票规则为：（1）严格超过一半，提出的议案通过；（2）只要达到一半，提出的议案通过；（3）达到或超过 2/3，提出的议案通过。试进行三种投票规则下，每位股东的权力比较分析。解：设投票人集合为：N=1,2,3,4 ，每人依次拥有股份为：40%,30%,20%,10%.（1）每个投票人的摆盟分别为：S1: 1,2, 1,3,1,2,3,1,2,4,1,3,4;S2: 2,1,2,3,4,2,1,4;S3:3,1,3,1,4,3,2,4;S4:4,2,3.摆盟数分别为：1
5、=5, 2=3, 3=3, 4=1;势指标分别为：1=5/12, 2=3/12, 3=3/12, 4=1/122） (此时只需要 50%就可以通过）每个投票人的摆盟分别为：S1:1,2 、 1,3 、 1,4 、 1,2,4 、 1,3,4S2:2,1 、 2,3 、 2,3,4S3:3,1 、 3,2 、 3,2,4S4:4,1每个投票人的摆盟数分别为：1=5, 2=3, 3=3, 4=1势指标分别为： 1=5/12, 2=3/12, 3=3/12, 4=1/12.（3） （此时需 66.67%就可以通过）每个投票人的摆盟分别为：S:1,2,1,2,3, 1,2,4,1,3,4, 1,2,3
6、,4S:2,1,2,1,3, 2,1,4S:3,1,4S:4,1,3每个投票人的摆盟数分别为：=5, =3, =1, =1势指标分别为：=5/10, =3/10, =1/10, =1/10-第一章 线性规划与单纯形法（一）线性规划与单纯形法知识点：1、线性规划在应用中用得最成功的是解决稀缺资源的最优分配问题。线性规划最常用于讨论利益（利润）的最大（max）和成本（支出）的最小（min）.2、数学规划问题有三个组成部分：1）决策变量（一般是多个决策变量） ；2）含决策变量的目标函数；3）对决策变量的约束条件。-例 1：设有一根长为 L 果的铁丝，要围成一个矩形。问矩形的长和宽各为多少，使所围成的
7、矩形面积最大？解：设围成矩形的长为 x 米，宽为 y 米。线性规划模型为：Max s = x ys.t. xy=L/2 （约束条件）0”125 （百万元）12x19x 2+15x3+ d1 d 1 = 125 雇佣水平，希望“=”40 （百人）5x1+3x2+4x3+ d2 d 2 = 40资本投入，希望“” ，目标为： min d1 希望“=” ，目标为： min（d 2 d 2 ）希望“ P2 P n 对目标规划可用 WinQSB 软件中的 GPIGP 程序求解。-例 1： 某企业生产 I、II 两种产品，两种产品都需在 A、B、C 、D 四种设备上加工。单位产品加工生产所需时间（h） 、
8、利润、设备可用加工时间（h）都见下表：企业在生产计划中，C 和 D 为贵重设备，严禁超时使用；其余各层次目标依次为：第一目标：利润不低于 12 元；第二目标：考虑到市场需求，I、II 两种产品的比例保持在 1 : 1；第三目标：设备 B 必要时可以加班，加班要控制；设备 A 一旦工作，将连续进行，希望A 的工时充分利用。这两者的重要比为 1: 3。企业生产 I、II 两种产品分别为 x 1, x 2 。一般利润最大化线性规划： 12123.840,Maxzxstx线性目标规划：第四章 决策分析基本（一）不确定型决策方法知识点例 4.1 某决策问题的方案和状态的收益表如下：一、悲观准则（ max
9、min 准则）从每个方案中最差结果出发，从中选择最有利的方案u（Ai）=min a i,j i =1,2,m j最优方案是：u（A i）=max u（A i ）本例中是最优方案是 A1二、乐观准则（ maxmax 准则）从每个方案中最好的结果出发，从中选择最有利的结果u (Ai) = max ai,j最优方案是 Ai* ，u (Ai*) = max u(A i) i本例中最优方案是 A 2 三、折衷准则悲观准则和乐观准则的折衷.乐观系数为 ，悲观系数为 1 . （0 1）j j i本例中：； = 0.8，最优方案 A2 （二）期望效用值决策例 1：有一风险决策问题的收益表如下：12341213
10、124()().408,.,.1,234.iiMinzPdPdstxdxjiji aau,i mn)1(x)(*iiA（1）用货币期望值法时行决策。（2）若 ：U( 200) = 0, U(150) = 0.05,U( 500) =0.3, U (1000) = 1 用期望效用值方法进行决策。解：（1） E（A）=0.75000.3(200)=290E（B）=0.7(-500)0.31000=195则选择方案 A（2）E（U A）=0.7U（500）0.3U(200)=0.70.30.30=0.21E（U B）=0.7U(-500)0.3U(1000)=0.70.050.31=0.335则选择
11、方案 B第五章 确定性网络图（一）网络图的绘制（1）单代号网络图（本书介绍）（2）双代号网络图（其它多数书介绍）下面只介绍单代号网络图的绘制：（1）用一个园圈表示一个工序；用边表示工序间的逻辑关系。（2）不允许有循环圈出现。（3）加一个虚拟的结束工序。（4）按逻辑关系给出每一个工序的编号，虚拟的结束工序的编号为最后一个编号。（二）各工序时间参数知识：（1）工序的最早开工时间ES i ，工序的最早完工时间EF i 按工序给定的编号顺序进行计算： ES1=0 ； EF 1=t1 ESi=max EF h ,(工序 h 是工序 i 的紧前工序)EFi= ESi+ti 按自然序从小到大计标(顺向)，直
12、到结束工序。（2）工序的最迟开工时间LS i ，工序的最迟完工时间LF i 按工序给定的编号顺序逆向进行计算： LFn= EFn ； LS n = LF n t n LFi= mi n LS j , (工序 j 是工序 i 的紧后工序)LSi= LFi t i按自然序从大到小计标（逆向） ，直到第 1 号工序。（3）工序总时差 R i 在不影响任务总工期的条件下，某工序 i 可以延迟其开工时间的最大幅度.Ri=LFiEF i=LSiES i （三）关键路线知识点：关键路线从开工到结束工序，时差为零的工序串。关键路线上的工序称为关键工序。总工期完成所有工序所需最少时间 。总工期 = LF n =
13、 EF n = LS n = ES n注：（1）可由 ES n =的求得路径进行倒推；（2）一个网络图，关键路线至少有一条。网络图中工序的表示法例 1：现有一项目，其工序分解、工序间的逻辑关系和工序完成时间如下表。求各工序的时间参数、关键路线、总工期。第六章 网络优化（一）最小树问题一、树及其性质。1.定义：连通且不含圈的无向图称为树。一个无圈的图称为森林。森林的每一个分图是树。2.定理 6.3：图 则下列命题等价。（1）T 是一个树。（2）T 无圈，且 m=n-1.（3）T 连通，且 m=n-1.（4）T 无圈，但每加一新边，即得唯一圈。（5）T 连通，但每舍去一边就不连通。（6）T 中任意
14、两点有唯一初等链相连。二、图的生成树1、定义：若图 G 的生成子图是一棵树，则该树称为 G 的生成树。图的生成树是不唯一的。2、定理 6.4：图 G 有生成树的充分必要件为 G 是连通图。3、寻找生成树方法：（1）生成法（避圈法） 。 （2）破圈法。（二）Dijkstra 算法， （双标号法）前提：是连通图，且每一条边上的权为正数。作用：可求中对给定一点给到任意其它点的最短路。双标号意义：P(v)永久标号。T(v) 临时标号。算法中 vi 到 v j 的路长记为 l i,j ，即前述的边的权重 w i,j 。若 vi 到 vi 无边，则记 l i,j 为无穷大。第七章 （一）双矩阵博弈的定义知识点在博弈中，若三要素的前两个
