第二章 运筹学各分支简介
运筹学作为一门学科，在理论和方法上取得了巨大的进展，现在我们就来介绍一下各分支研究问题的对象和基本的分析方法，使读者对它们有一个概貌的了解。
作为一门学科来说，运筹学的内容可以大致表示如下：
以下对其中的主要分支，分别介绍如下。
§1 数学规划
数学规划所要解决的问题就是要在某种约束条件之下，决定某些可控制的因素应该取什么样的值，使得所选定的目标达到最小（或最大），用数学的语言来表示，就是要解决下述极值问题：
，其中S表示满足约束条件的可行解的集合。
极值问题虽然早已存在，但现在考虑的数学规划问题与古典的极值问题却有很大的差别：（i）古典方法只能处理当f（x）和可行域S很简单的情况，而现在实际中所出现的问题，f（x）和S一般都很复杂；（ii）古典方法只能处理n比较小的情形，例如n＝3，4，而现在n一般都相当大，个别问题的n甚至上百万；（iii）古典方法往往满足于一个表达式，而现在则需要把所需数值具体求出。基于上述原因，要想解决数学规划问题，必须另辟新路，，实际上，自从Dantzig在1947年发表关于解线性规划（即f（x）为x1，···，xn的一次式，S由x1，···，xn的一些线性不等式组成）的单纯形法以来，数学规划已得到非常迅速的发展，形成许多分支，成为近代应用数学的一个重要组成部分，由于它的发展，使得有关学科，如凸分析、数理经济学、应用泛函等也得到相应的发展，国际数学规划讨论会于1970年成立，有关杂志不下10种，国际数学规划讨论会至今已召开12届，我国第十一、十二届均有人参加，会议设立了Fulkerson奖（1979年始）和Dantzig奖（1982年始），授予那些在数学规划方面具有开创性成绩的工作者。
本书将详细介绍数学规划的若干分支，故这里不多叙述，有关参考书较多，如：
管梅谷，郑汉鼎，线性规划，1983
俞玉森主编，数学规划的原理和方法，1985
唐焕文，实用数学规划导论，1986
魏权龄等，数学规划与优化设计，1984
§2 图与网络方法
所谓图乃是指由一组给定的点（称为顶点）及一组连接这些点的线（称为边或弧）所组成的总体（如交通图），而图论则是研究图的理论。图论的产生可以上溯到十八世纪，但它得到重视而且逐渐成为一门学科，则是本世纪三十年代之后的事。特别是五十年代以来，由于许多具有离散性的问题皆可以通过图来表示，使得图论的研究越来越为人们所重视，如
兰姆赛问题（Ramsey）：任意六个人在一起，若不是有三个人彼此相互认识，必然有三个人互不认识。
将此问题化为图来分析：视6个人为6个顶点，认识，用实线相连接；不认识，用虚线连接。往证至少存在一个实三角形或虚三角形。任取一点V1，它与其他五点的连线中至少有三条同为实线或同为虚线，不妨假设为实线，而另一端点分别为V2,V3,V4
，这后三个顶点形成的三角形若是虚线的则问题已经解决，不然则至少有一条边为实线，从而又与已知实线构成一实三角形，故问题得证。
图1
可见用图来处理问题有时很有效，并且形象直观（如哥尼斯堡七桥问题）。许多有经济意义的问题都归结为图与网络（边上有各种数据的连通图叫做网络，数据又叫权），如
（I）、最短路问题。
在给定网络中求指定两点的最短路是图论中的一个基本问题，此问题已有有效算法。
用表示连接顶点i和j的线段长（若无则视＝＋∞），现在要从点1出发，走到n，问怎样走路程最短？
图2
考虑从点1到点j的路，按中途所经过的线段数目分类，用表示从点1到点j的且限制中途经过的线段数目不超过m的这类路中的一条最短路之长，研究，即所经线段数目为（m＋1）时的最短路长，易见它或者等于，或者等于，于是有
（1）
而1到n的最短路即为。
分析计算量：关系式（1）中，m取1，2，···，（n－2），对每一个固定的m，j取2，3，···，n，对于固定的m和j，一般说来，要经过（n－1）次加法运算和比较运算才能得到，因此计算量是。这实际上就是动态规划的顺推算法，按照动态规划的最优化原理：“作为整个过程的最优策略，具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。而对于无向图说来，起点到终点的最短路自然也是终点到起点的最短路”。
当所有线段的长度都是正数，还有更好的算法：Dijkstra算法（标号算法）。它的计算量为。具体做法是：先对起点标号，每步考察已标号顶点的相邻顶点，把距起点最近的顶点标号，直到终点被标号，按标号反向追踪即得到最短路。
例：求下图中A到B的最短路。
标号过程如下：
故最短路为，最短路长为6。
最短路问题可以直接应用于解决生产实际的许多问题，诸如各种管道铺设、线路安排、厂区布局、设备更新、选址等。
（II）、最短网络。
亦称最小树。一个实际背景是：在若干城市间架设电话线，如何架设使总长最短？
先讲讲什么是树？对于图中的任二顶点Vi 和Vj，如果从一个顶点出发沿着若干边或弧（有方向的边叫做弧），可以达到另一顶点，则称所顺次经过的边和顶点为连接Vi 和Vj的链。如果所连接的顶点重合，即Vi ＝Vj，则称这样的闭链为圈。一个圈中如果任意两顶点之间至少有一条链，则称为连通图，而连通且无圈的图叫做树。
对于含圈的连通圈，去掉每个圈的一条边，便可生成一个树，去掉的边不同生成的树也不一样，其中边权和最小的，叫做最小生成树。
求最短网络，首先容易想到的是求最小生成树，目前的方法有所谓破圈法（即任取一个圈，每次去掉其中最长的一条边，直到无圈为止），顶点扩充法（即任取一顶点，考察以此顶点为一端点的所有的边，取其中最短边的另一顶点为扩充顶点，依次类推，但要注意新扩充的边与已选好的边不能构成圈，直到所有顶点均被扩充为止）等，计算量是。
继之想到在原基础上增加一些新点和连线，扩大成一个新的网络，要求在此新网络上找出一个子网络，它是连通的，包含原图中的点，并且边权和最小，这种网络称为斯坦纳最小树（树中新增加的点叫斯坦纳点，简称斯点），它的边权和显然小于最小树的，现已证明：
任一斯点均为夹角为120o的三线段交点。
n顶点的图形最多含（n－2）个斯点。
三个顶点的斯坦纳最小树很容易找出：
以AC为边作正△ACD，连BD交△ACD的外接圆于S，则S即为斯点（见图3）
图3
易证，SA＋SB＋SC<AC+BC（注意SA＋SC＝SD）。
当n＝4时，方法仍是用一新点E代替两原顶点C，D（△ECD成一正三角形），先求△ABE的斯点S1，连S1E交外接圆于S2，则S1和S2即为所求（图4）。同样若以新点代替A，C，则可另得二个斯点，如此递归进行，可以求出任意个顶点的所有斯点。
图4
问题是图形数目太多（当，共有62370个图形），有人（Garey等）已证明最短网络是NP-complete问题，因此n略大时，譬如，计算机就不能胜任，目前可做10个顶点的问题。
现在研究方向有二，其一是对具有特殊性质的点集构造斯坦纳树，如对正n边形顶点集合，当n>5时，斯坦纳最小树即是最小生成树（详见，翁家丰，应用数学学报，2（1985）），其二是对一般的集合构造次优树，即不一定最短但接近最短，通常以最小生成树为次优树，人们对点集A，定义
称为最小斯坦纳比例，猜测，由正三角形的例子知，曾证得3<n<5时，，黄光明[3]证明了（1983年），钟金芳蓉和Graham又宣布了（计算机结果），已经很接近了。最近（2000年）我国运筹学家越民义[4]证明了猜测为真。替代结果，最坏情形增加13.4%的网络长，对随机情形只增加3%。
（III）作业时间的优化
作业时间的优化问题，象大规模工程、房屋建筑、产品开发设计、维修以及工厂的开工投产活动等一次完成的规划项目，如果对完工时间要求很严（如附有罚款条件），那么采用网络分析，以缩短工时，则具有特别重要的意义。
运用网络来描述规划，制作进度表，可以有以下几方面的好处。
有助于管理者系统的、全面的考虑规划，弄清程序，便于估计完成时间和找出可能的改进方案，从而加快规划的实现。
能提供工程计划的简明概况，其形式便于有关部门进行评论和参考，从而便于汇集各方面的意见，找出存在的问题和延误工程的原因。
对网络进行分析可找出关键路线，这就是网络中所需时间最长的一组活动。网络的解可以揭示缩短哪些活动的时间，有助于缩短整个完工时间，它还可揭示在哪些活动中加班是无益的。某些活动可延长时间而并不会延长总的完工时间，这就明确了各个工序或过程在网络中的地位。
有助于识别有关任务及其时间顺序关系，从而可更好的分派职责，更有效地运用资源，当出现问题时，网络可用来确定各种可能的其它解决方法。
网络分析可以说明各项活动的最早可能开始时间及最迟允许完工时间。
进度表法或称网络计划技术最早是在1957年，由美国杜邦公司研究出来的，最初用于计划和管理化学工厂的筹建，其结果使该项工程比原计划缩短了两个月时间，随后又将此方法用于维修，使原来需停工125小时的工程缩短为78小时，取得显著效果。
还有其它一些典型问题，都可以用图论方法来处理，如最大流问题，最小费用流问题，以及匹配（无公共顶点的边所成集合）问题，哈密顿回路和旅行商问题等等。
总之，图论所研究的问题主要分两类，一是给定的图中具有某种性质的点是否存在？若存在有多少？或至多（少）有多少？二是如何构造一个具有某些性质的图或子图？
有关参考书：
李修睦著，图论导引，1982
卢开澄著，图论及其应用，1981
§3 组合最优化
在运筹学的最优化问题中有一部分问题所涉及的因素的取值范围是离散的，而且在许多情况下是有限的（例如只取0和1）。这类问题中有些不能用传统的数学式子描述，有一些可描述，但极为复杂，以致变得不能驾驭。这类问题往往需要用某些特殊方法来处理，这样就产生了一门新兴学科－－组合最优化。它包含了许多常用的但一般很难于处理的著名问题，象在图与网络一节中提到的最短路问题，最小树问题，匹配问题，旅行售货员问题，也都属于组合最优化问题。下边我们针对一些典型问题介绍几种基本方法。
（Ⅰ）背包问题和Greedy算法（贪婪算法）。
有n件东西重量为,i=1,……，n，价格为，i=1,……，n，要求从中选出若干件装入背包，既使总重量不超过M，又使总价值最大。
Greedy算法：将比值由小到大排好队逐件考虑，不超重就装入，否则放弃之，考虑下一件。
算法的实质就是“挑好的装，装进后就不再换出”，不过一般地讲这种方法不一定能求得最优解。其实背包问题是NP-Complete问题至今没有有效解法。
（Ⅱ）匹配问题和交错链方法
Greedy算法对背包问题不能保证求得最优解，但是能求得一个比较好的初始解，人们通常以它为基础再作一些调整，如尝试用两件东西去换一件，或三件去换二件等办法来改进所求的解。交错链方法就是这种朴素思想的发展，它是组合最优化方法的核心，让我们通过匹配问题来说明交错链方法。
有n个工人和n项工作，每个人只能适应其中某几项工作。要求寻找一种分配方式，使得尽可能多的人分配到适应的工作岗位上。
例如有5个工人：A、B、C、D、E；5项工作1，2，3，4，5，各工人与各工作之间的适应关系如图5所示。图中有线段相连表示适应。例如A适应于1和2，问最多能同时安排几个人的工作？
图5 图6 图7
从图上看，是要求利用线段来将图中的端点一一配对，且希望配得对数越多越好。这就是图论中最大匹配问题。可见，所谓匹配就是无公共顶点的边所成集合。
首先，通过直觉观察，求出一个较好的初始匹配方案。在图中我们用粗线段表出，如图6所示。这时已连上粗线段的点称为已盖点，尚未连粗线的点称为未盖点，图上的一条路，若路上的线段粗细交错，则称其为交错链，如图7所示。称连接两个未盖点的交错链为增广链。对于增广链，细线段比粗线段多一条。对给定的匹配方案I，假若存在一增广链S，那么只要把路S上的细线和粗线交换一下，便可得到多安排一个人的新匹配方案。通常用下述符号表示上述调整运算：
图论中有下列基本事实：
定理1，一个匹配为最大匹配的充要条件是不存在关于它的增广链。
如何寻找增广链？采用“树生长法”（或称标号法），以图6为例，开始任取一未盖点为树根，如D，从树根沿着细线生长，接着从树梢出发沿着粗线往外生长，这样交错的沿着细线粗线继续从树梢往外延伸，直到不能再生长（如图8）
图8
我们称图（8）是以D为根的交错树，在树的生长过程中，一旦发现除树根外，另一未盖点被长到树上，过程就可中止。这时树上连结两个未盖点的那条路，便是一条增广链。图8中D与⑤之间就是一条增广链，沿着它们调整后，可得匹配如图9
图9
总结交错链方法的计算步骤如下：
1、任选初始的匹配图。
2、利用树生长法寻找增广链。如找到一条增广链则转步骤3，如所有交错树上都无增广链，则步骤终止，已找到最大匹配。
3、（调整）替换增广链上的粗线和细线，得到一个新的匹配图，然后转步骤1。
交错链方法的计算量是O(n2)。
最优匹配问题（亦称分配（派）问题）
假如我们进一步还知道了每个工人干各项工作的效率或产值，而要求找出使总的产值最大的匹配方式，这在图论中称为最优问题，即图中每条线都有权与其相对应，要求找出使权和最大（或最小）的匹配。
对交错链S，我们定义
e为S上的粗线 为S上的细线其中（e）表示线段e的权，称（S）为S的长度，让表示在所有含K条线段的匹配中，使权的和达到最大的匹配，进一步假如存在关于的增广链，则用SK表示最短增广链，即
下面的定理是组合最优化中最基本的性质。
定理2，对，若存在SK，则有如下递推关系：
，
据此定理，可知求解最优匹配的关键是寻求最短增广链，然而求又可化为在一个定向图中，求两点的最短定向路问题，如求图10。
图10 图11
由图10的最短增广链，可对应地作出定向图11，容易求出图11S到t的最短定向路为：
相应地，图10中的最短增广链为：
假如求上述最短定向路的计算量为,则求出最优匹配的计算量为。
解分配问题亦可在表上进行，采用标号法求增广链和最大匹配，然后通过简单的矩阵变换，逐步找出最优分配，这种形式的解法叫作匈牙利方法（详见管梅谷等[13]，线性规划）
还可以用下面将介绍的分枝定界法、最小调整法求最优匹配。
还有二次分配问题。例如，对厂址和厂房要求一个总的分配（一对一），使得厂址之间的距离各乘以相应工厂的运输量所得的和最小。
此问题很难解决，无有效算法，也几乎无有效的启发式算法可以利用。
（Ⅲ）排序问题和分枝定界法在许多可能的顺序中找一个最优顺序，分配加上加工顺序的限制，就成排序问题，如A与B两车床加工n件产品，加工时间分别为ti(A)和ti(B)，i＝1,2,…,n。A先加工，然后B再加工，问如何安排所用时间最少？
由于加工顺序是A先B后，故应尽量减少B的等待时间，因此不难理解其最优方案应是每次从｛ti(A)，ti(B)｝中取出一个最小值，若它属于｛ti(A)｝，则应排在最先加工，若属于｛ti(B)｝，则应排在最后加工，然后对已确定加工顺序的数据从｛ti(A)，ti(B)｝中去掉，在余集上重复上述过程，依次排列，便得最优排序，此问题亦可用动态规划的方法求解。
上述是2×n的同顺序排序问题，对于一般的m×n(m>3)的同顺序排序问题以及不同顺序的排序问题，要用“分枝定界法”求解，现将该方法简介如下：
分枝定界法欲求
（2）
考虑求
（3）
其中要求AB，称（3）为（2）的松弛问题，它要好解些。若（3）的最优解，则；否则分A为两个（或多个）子集：，解相应的松弛问题：；若，则A1问题已解决（否则，对A1重复A的过程）。同样若，则A2问题已解决，从而即为所求最小值。若而（但），则A2亦不必考虑了；否则，对A2继续实行如同A的步骤，如此进行，直到求得最优值为止（取最小的子集先考虑）。
（IV）旅行商问题和最小调整法
设有n个城市，C1，···，Cn，由Ci到Cj的路程为已知，一旅行商为了推销货物，从一城市（如C1）出发，要经过所有城市，且每个城市正好经过一次，然后回到出发点。问题是如何选择一条最优路线。容易看出，旅行商有（n－1）！种方案可供选择，对于n＝21这个不大的数目，就有20！种方案，20！是个天文数字，即使用高速计算机也无法处理这一问题。这类问题至今没有有效算法，甚至连有效的近似算法（与集合I无关）亦没有，被称为NP-困难（完全）问题。
但是上述问题有着广泛的实际背景和深刻的经济含义，例如，在计算机的集成电路的设计中就出现这一问题，还包括派车，排序，底板布线，考古学中的排号，自动钻井，工件加工顺序，邮局到各个邮箱开箱收信，以及去各分局送邮件等其它许多方面。所有这些需要又促使我们不得不研究它的解法。下面考虑用最小调整法来求解。
最小调整法的思想和步骤如下：
设旅行商问题的关系矩阵为A
其中元素表示由第i个城市到第j个城市的路程。
（1o）取每列的一个最小值，画圈，得一最小方案。若这些画圈元素又分属于不同行，则得到相应分派问题的最优解，转（3o）；否则转（2o）。
（2o）应把有二个以上画圈元素的行中的一个改画到同列的别处，待到某一无圈行中有一元素画上圈，则算一次调整。如此进行，直到每行均有一个画圈元素时为止，然后转入
（3o）即可。而每次调整均以目标函数（其值为各画圈元素之和）增值最小为原则。
（3o）如果从1o或2o得到的分派问题最优解元素的任一行指标i出发，先到其列指标j，接着从以j为行指标的元素出发，再到其列指标，如此进行下去，最后回到以i为列指标的元素止，便形成一个圈，若圈中的元素恰为n个，则所得方案即为最优方案；否则，便会形成两个以上的子圈，它不是最优解，需进行再调整，转（4o）。
（4o）以增值最小的原则实行对调调整，所谓对调调整，就是于任二子圈中各取一个元素，如与，交换它们的列指标，变成与，其结果该二子圈便合成一个圈，该变化用图简示，则为
由图可知，此四元素形成一矩形，调整是把该矩形原先对角线上的二画圈元素与的圈转给了另一对角线上的二画圈元素与。显然，调整结果，目标函数将增加：
考虑所有可能的对调调整，取其中增值最小的，加以调整，便破掉一圈。如此进行，直到无子圈为止。
对于大规模问题，求最短调整路线可用标号算法，详见文献[7]。
例1．已知五个城市间的距离如下表所示，求旅行商的最短路线。
（4）
（1o）先求出相应分配问题的最优解：（用最小调整法）
（5）
故此例的分配问题最优解为，转（3o）。
检验结果，此方案形成两个子圈：
容易看出，在两个圈中任意各取一个元素，交换它们的列下标，则这两个圈便合成一个圈。
例如，将第一个圈中的与第二个圈中的的列下标对调（或交换），便成为：
此即：
于是便破掉一个圈，此例经此处理便得到一个可行方案。在（5）中上述处理相当于：若把分属于不同圈中的两元素看成为矩形一对角线的二顶点，则其圈调换给了该矩形另外两个对角顶点对应的元素，即：
（6）
调整的结果将导致目标函数（总路程）的增加。若每次对调都选择增值最小的进行，当所有的子圈全被破掉后，即得原问题的一个更好的解。
此例中的最优解为：（对调增值为0）
（7）
由此最短路线即为：，此问题的解不唯一，另一条是：，它不能通过一步对调调整得到。
例2，设旅行商的关系矩阵为（8），求最优解。
（8）
求解过程图示如下：
得到相应分派问题最优解：，但其中有二个子循环，实行最小对调调整。
检验（3o）成立，故得较好的可行解：，它实际上是最优解，可通过对相应分派问题最优解按增值最小的原则继续调整得到并加以验证。当问题规模较大时，寻找最短调整路线可像最短路那样实行标号算法[7]。
当松弛问题的最优解有较多的圈时，破圈需涉及较多的矩形，可以证明，当问题的规模为时，所涉及的总的矩形数不超过，总的计算量不超过3，可见此算法相当有效。
对调调整对于破圈来说简单而有效，但其增值最小却又仅限于所有对调调整所破的圈，并不包括其他非对调调整所破的圈，换句话说，既能破圈而又增值最小的路线未必一定是对调调整路线。因此，我们得到的解只是近似解。
由最小对调调整得到的可行解虽然未必是最优的，但也是较好的可行解。设为最优解，是相应松弛问题——分派问题的最优解，是对调最优解，则有，若不是很大，或可以接受，则便可以作为可接受的近似解使用。
若不然，可以对继续使用最小调整法，以便求得最优解，其最小调整路线的求法仍可归结为求最短路，但考虑到最短路线可能不减少（有时甚至增加）圈，故要做些限制，即在调整后圈必须减少的限制条件下求最短路，为此需要给出某一调整是否减圈的判别方法，此问题正在研究中。
§4 投入产出方法投入产出方法是考察各种经济活动的投入与产出之间的数量关系的一种方法，于本世纪三十年代产生于美国，创始人列昂节夫因之获得73年诺贝尔经济科学奖，近年来有很大发展，目前已普遍地用来研究和分析国民经济各部门之间的数量依存关系、计划和安排未来的经济活动、预测和分析采取一项重要经济政策的经济后果研究和计算产品的价格形成等，在实践中取得一定效果，我国曾编制了1973年国民经济投入产出表。
投入：指从事一项经济活动的消耗，如原材料、能源、机器设备和人的劳动等。
产出：指经济活动的结果，如产品等。
模型分静态和动态二种类型，下表是静态价值型投入产出表。
中间产品
最终产品
总产品
合计
消费
新固定资产
库存及进出口
合计
生产资料转移价值
小计
（）
固定资产折旧合计
新创造价值
劳动报酬
社会纯收入
合计
总产品
表中Xij表示第i个部门的产品用作第j的部门生产消耗的数量。
（Ⅰ）反映各部门之间的生产技术联系，相互提供劳动对象（如原材料、辅助材料、燃料、动力等）的情况，是编表和计算的基础（如计算直接消耗系数等）
（Ⅱ）反映最终产品的构成及使用（分配），其中?即为社会最终产值或国民生产总值，从数量上它等于国民收入加上本年度的固定资产折旧额之和：?
（Ⅲ）反映社会最终产值即国民生产总值的价值形成过程，它包含二个内容，一是固定资产折旧，二是新创造价值（其中社会纯收入由利润税金等组成）。
（Ⅳ）反映国民收入的再分配从水平看有关系式：
?
将代入，并写成矩阵形式，可得：
其中A是直接消耗系数矩阵：，上式表明根据最终产品的需要量Y即可算出总产品产量X应是多少（以销定产）
从垂直方向看有如下关系式：
这个式子的经济意义为各部门的产值等于中间产品转移价值、固定资产折旧、劳动报酬和社会存收入之和，引入直接消耗系数写成矩阵形式，可得：
其中C是对角阵，其对角线上第i 个元素为。当已知C及各部门D、V、M的数值后，即可算出各部门总产量X的数值来。
投入产出方法的发展趋势，一是与数学规划结合，编制最优表（把上述方程组看作基本约束，再补充一些其它约束，求一个目标函数的最大值）二是进一步与经济计量学结合。
§5 决策论决策是人们工作和生活中普遍存在的一种活动，是为解决问题选择最佳方案的一种过程。决策效果的好坏，关系重大。它是管理过程的核心，因此决策者必须掌握科学的决策原理和方法。
一般说来，每一实际问题经常可能面临几种不同的客观环境，它不以人的意志而改变，称为自然状态（全体自然状态的集合记为I，简称状态集）；又有几种不同的行动方案（所有可供选择的行动方案之集合记为D，简称行动集）；人们希望通过对各个方案在每一状态下可能产生的效果（称为后果，用C表示）进行综合分析、比较，进而选定一个最优方案加以实施。这就提出了决策问题。
某农场考虑是否提早种植某种农作物的决策问题，详情见下表。
状态后果行动方案
不遇霜冻
遇霜冻
提早种不提早种
45
30
10
20
其中提早种遇霜冻的概率为0.4，不提早种遇霜冻的概率为0.2。
表1中的后果构成一矩阵，称为后果矩阵或益损矩阵，一般地，后果阵可表示为。
决策类型主要分以下三种：
（i）确定型。只有一种自然状态，这种决策看起来似乎很简单，但若可供选择的方案很多，例如有n个产地，m个销地的运输问题，当m和n较大时，要决定出一个运费最小的方案也并非易事。
（ii）风险型（统计型）有两种以上自然状态，并知该状态出现的概率。
（iii）不确定型，自然状态发生的概率未知。
我们下边主要介绍风险型决策方法，即当自然状态出现的概率已知时的决策问题。
首先须对“概率”进一步加以认识。以往，我们认为随机事件的概率是事件的客观属性，它具有频率解释：在相同条件下大量重复的独立试验中事件发生的次数与总试验次数之比，称之为客观概率，但对许多不确定事件，大量重复试验是不可行的。比如关于花费上亿元经费发射一枚导弹的某项决策问题，就不能依赖反复试验来取得必要的数据。对于这种一次性的、不确定事件也应根据所掌握的资料，对它们出现的可能性给出定量描述。这就产生了所谓主观概率。一个事件的主观概率是人关于该事件出现的可能性在现有认识水平上给予的主观信任程度的一种度量，它不是以重复试验为基础来作出判断，而是根据一种可以接受的数据（包括没有数据）和逻辑分析来作判断的，而且一个事件的主观概率随着事件信息增加而改变，因为信息增加将会减少不确定性，如在例1中，若有中、长天气预报，则当年霜冻的可能性就会有较好的估计。
主观概率除了获得的方法不同外，其余与客观概率无异。下面介绍一种评定主观概率的方法：讯问法。
把事件E和它的补事件E－1（即EE－1＝I，EE－1＝）进行比较。问决策者E与E－1哪个更可能发生？若回答是E，即 ，则把等分成两段，分点为，再问决策者，与，宁可接受哪个？若回答是后者，即P。照此下去，直到决策者对与不加区别为止，就取P为E的主观概率。
一、最大可能法。在风险型决策问题中选择一个概率最大的自然状态进行决策，其它自然状态可以不管，这就变成了确定型决策问题，称之为最大可能法。按此法分析例1，应选不提早种。
上述决策方法应用很广，但要注意，在一组状态中其中某一个状态出现的概率比其它的特别大，而它们相应的益损值差别不很大，这种方法的效果是较好的。如果在一组状态中，它们发生的概率都很小，且互相很接近，再要采用这种决策方法，效果是不好的，有时会引起严重错误。
二、期望值法。这里所说的期望值即概率论中的数学期望（），若，则
即等于该行动对应的益损值与取此益损值（即相应自然状态出现的）概率乘积之和。对例1有：
E（d1）=45×0.6＋10×0.4＝31
E（d2）=30×0.8＋20×0.2＝28
期望值法就是采取期望值最大（或最小）的行动方案，据此，例1应选早种。
上述分析过程可用图表示如下：
这样构造的树状图称为决策树。它直观方便，特别适用于多级决策（包含若干个决策点）比如发展某项新产品的决策过程如下图所示：
第一个决策点（方框表示决策点）为是否发展该项产品，若决定发展，则其开发（包括研究等）费是不确定的（如研究费不能确切预知），必须对各种可能的开发费及出现的概率作出评定。第二个决策点是对各开发费决定投入生产的规模（规模为0表示不投入生产），其生产费，由于原料的价格等因素，又是不确定的。对各种生产费及出现的概率又要作出评定，最后面临的决策是决定产品的售价。无论哪种售价，其销售量又是不确定的，对各种销量及可能出现的概率应作出评定。不同的可能售量决定该项产品的盈利值和亏损值。分析的步骤本质上与例1类似，应对每个决策点及其各个可能结果作通盘考虑，从决策树最右端开始逐步往左，反向进行分析。首先对任一固定的售价，评定各最终后果的期望值，比较各售价的期望值，选取最高者，作为该决策点的益损值，相应的行动就是该决策点的最优决策。对每种生产费都这样进行，然后依此往左推，直到决策树的开始决策点为止。
三、效用理论。我们已看到，对例1，按期望值最大的原则应选提早种的方案，但应当指出：对同一期望值，不同决策人会有不同的反映，就是同一决策者，在不同情况下也会有不同的反映。好比一杯水，在泰山顶上与泰山脚下，对一个人的效用是不一样的。在例1中设成本为15万，若提早种又遇霜冻，则要亏本5万，即提早种要冒亏本的风险。不同的决策者对待风险的态度会有差别，有的人回避，有的人无所谓，还有人敢冒风险，解释这种现象的理论是效用理论。
用表示提早种这一方案，虽说它的期望值是31，但风险较大，决策者甲可能认为它只能与收入25（万元）等效用，可记为25～（0.6,45;0.4,10），同理可有28～(0.8,30;0.2,20)，这样甲在决策中必然选择方案：不提早。一般地，若C～(P,a;1-P,b)（称C为的确定性当量），则可用一个所谓效用函数u(*)来反映上述事实，效用函数的构造方法如下：
先找出最好与最差的后果（如45）和（如10），令，，而定义效用值为
(10)
据此效用值（10）可作出效用曲线.具体作法是，先把 ，代入（10）并取P＝，从而算出，再用逐次讯向法寻找确定性当量C1～(P,C*;1-P,C0)，这样曲线上便有了三个点，，，分别代入（10）（仍取P＝），又可算出二个点，依此类推，即可得到所需的效用曲线，有了效用曲线后，就可从上查得任何后果的效用值，于是对每一方案均可通过效用曲线计算期望效用值（即用（10）式计算），其中期望效用值最大的方案，便是最优决策。
如对例1，已知u(45)=1,u(10)=0,这样曲线已有二个端点（10,0）和（45,1），取P＝，，，代入（10），算得效用值
然后用逐步讯问法求出确定性当量
C1=22.5～(0.5,45;0.5,10)
从而得到一点A＝（22.5，），照此下去又可算得
=0.75
讯问法C2～(0.5,45;0.5,22.5)，得C2＝30，从而得点B＝（30，0.75），同样，点C＝（16，0.25）等等，用平滑曲线把这些点连起来，即得该问题的效用曲线：
据之可查得后果为30、20的效用值分别为0.75、0.4，从而点②点③的期望效用值为：
点②：0.6×1+0.4×0=0.6
点③：0.8×0.75+0.2×0.4=0.68
故按期望效用最大恒量应选方案：不提早.把以上结果添到决策树上（括号内的数字即期望效用值）.对于多级决策，只须用效用值替代后果，用期望效用值代替期望值，其余分析都是一样的。
效用曲线可分为上凸（避险型）、直线（无关型）和下凸（冒险型）三种，与例1对应的效用曲线是上凸，即避险型的。
基于主观概率与效用理论两者之上的决策分析是更为广泛的决策理论的一部分，是近代决策理论的标志。
决策分析首先用于石油和燃气工业的一些重大决策问题，现在它已广泛地应用于医学、心理学、经济学、商业及管理甚至政府方面的决策，它已发展成为运筹学、系统科学以及管理科学工作者的重要工具。
§6 对策论
对策论（Game Theory）亦称博弈论。它是研究具有竞争、冲突等性质问题的理论，原是运筹学的一个分支。然而对策论的研究和应用始终与经济学紧密地联系在一起，带根本性的原因是经济学和对策论的研究模式是一样的，这就是强调个人理性，也就是在给定的约束条件下，追求效用最大化。在这点上，两者是完全一致的。1944年Von Newmann和Morgenstern发表了《对策论与经济行为》一书，从此开始了对策论系统化，公理化的研究。从二十世纪50年代到70年代，对策论的研究取得了丰硕的成果，并成功地应用于经济学、管理科学，军事、政治等诸多领域，特别是70年代后，对策论逐渐成为经济学研究的重要理论工具，并被当成经济学的一部分。1994年，在对策论研究中做出突出贡献的三位学者Nash（纳什）、Selten(泽尔腾)和Harsanyi(海萨尼)获得了诺贝尔经济学奖，更加显示了对策论在经济学当中的重要地位。
(一) 基本概念
对策是决策者在某种竞争场合下作出的决策。带有竞争性质的现象，如下棋、打桥牌、外交谈判、订货谈判等，称为对策现象，古代的齐王赛马就是一个非常典型的对策现象。
对策现象含有三个基本要素：局中人、策略和支付函数。
①局中人（或参与人）：有决策权的参加者。可理解为集体，如桥牌只能算两个局中人（称为二人对策），多于两个局中人的对策称为多人对策。
②策略：整个行动方案，它告诉局中人在什么时候选择什么行动。其全体称为策略集合。注意策略是指局中人在一局对策中对付对手的一个完整方案。例如，在象棋比赛中，"当头炮"不是一个策略，而只是策略的一部分。按策略多少，对策分为有限对策和无限对策（如对攻的坦克）
③支付函数。在一局对策中，若每一局中人都选定了自己的策略，把这些策略合在一起，就构成一个局势。当局势确定后，对策的结果也就确定了，这时每个局中人都有得失。因此“得失”是局势的函数，称之为支付函数（payoff function）或收益函数。
如果在一局势下，全体局中人得失的代数和总为0，则称之为零和对策，否则称为非零和对策。
对策的类型很多，例如，各局中人之间均不能协商或订立有约束的协议，一般称为非合作对策，否则称为合作对策。从局中人行动的先后顺序上考虑，又分为静态对策和动态对策。静态对策是指对策中，局中人同时选择行动或虽非同时但后行动者并不知道前者采取了什么行动。动态对策是指局中人的行动有先后顺序，且后行动者能观察到前者所选择的行动，此外，从信息角度看，又分为完全信息对策和非完全信息对策。完全信息是指每一个局中人对所有其它参与人的特征、策略集合及支付函数有准确的了解或掌握。否则就是不完全信息。
对于动态对策，用对策树来表示是非常方便的，它一目了然地显示出局中人行动的先后次序，每位局中人可选择的行动，及不同行动组合下的支付水平。请看下例。
例1 某地区的两个厂商生产同类产品，为了占领市场，各自制定了自己的产销计划。把两个厂商当作局中人I、II。为了简便，两个局中人各有两种产出水平（A1,A2）和（B1,B2）。
这一市场竞争过程可用“对策树”描述如下：
I先作出选择。从起点画出的两条线表示I可选择两种不同的产出水平。标有II的顶点表示II在知道I的选择后，再作出自己的选择，由这两个顶点分别引出的两条线表示厂商II在不同情况下可作出的不同选择。图中最上面的顶点称为对策树的终点，每个终点上的向量表示对策结束时，两个厂商分别取得的纯利润（见图（a））
（a） （b）
如果厂商Ⅰ、Ⅱ同时作出选择，则厂商Ⅱ不能确定I的选择，我们将Ⅱ对应的两个顶点用虚线框起来见图（b）,表示Ⅱ不能确定自己到底在哪一点。
虚线框起的顶点的集合，或单个顶点等都称为局中人的信息集。
在这一例子中，对策用对策树表示，一般称为扩展型对策（Extensive form），以区别通常的策略型对策（如矩阵对策）。
(二) 矩阵对策
下边介绍一下有限二人零和对策，亦称矩阵对策，因为这时支付函数可用一个矩阵表示（叫支付矩阵或赢得矩阵）。
设局中人Ⅰ的纯策略集，局中人Ⅱ的纯策略集，则Ⅰ的赢得矩阵中，元素表示在局势之下I的赢得，当然也表示Ⅱ的支付，而整个对策可简记为 为了寻求各自的最优策略，考虑下面的例子。
例2 设有一矩阵对策
求双方的最优策略。
分析：为了不冒风险，双方都应当从最坏处着想，尽量争取最好的结果，对局中人Ⅰ所有最坏结果，即A中每行的最小值：
-8,2,-1,-3
这些最坏情形中最好的结果是，因此无论局中人Ⅱ选什么策略，Ⅰ只要选参加对策，就能保证收入不会小于2，同理对局中人Ⅱ说来，应从各列的最大(表示损失最大)数中取最小值（输的最少），即
亦即选参加对策，这时两人的最坏情况下的最好结果之绝对值相等，所选策略称为最优纯策略，相应局势，称为对策的最优局势（或鞍点）由于双方对此局势都感到满意，无意再打破它，故亦称均衡解。一般地，若等式
（1）
成立，则称G有最优纯策略，这样的对策也称为有鞍点的对策，若（1）不成立，则说G在纯策略中没有解。例如对于赢得矩阵为
由于
，不满足（1），故问题在纯策略中无解。事实上，当双方各根据从最不利情形中选取最有利的结果的原则选择纯策略时，应分别选取，此时局中人Ⅰ将赢得3，比其预期赢得还多，原因就在于局中人Ⅱ选择了，使他的对手多得了不该得的赢得，故对局中人Ⅱ来说并不是最优的，因而它会考虑出，局中人Ⅰ亦会估计到这种情形而采取相应的办法，改出以使赢得为5，而局中人Ⅱ又可能仍取策略来对付局中人Ⅰ的策略。这样，局中人Ⅰ出或的可能性以及局中人Ⅱ出或的可能性都不能排除。在这种情况下，一个自然的想法是判断不同策略的概率分布。设局中人Ⅰ以概率x选取，以概率1-x选取，局中人Ⅱ以概率y选取，以概率（1-y）选取，于是对Ⅰ来说他的期望赢得应当是
由上式可见，当时，。就是说当局中人Ⅰ以概率选策略，他的赢得期望值是，他并不能保证自己的期望值超过,因为当Ⅰ企图以的概率选以提高的值，Ⅱ可通过取使反而少于。同样局中人Ⅱ只有取时，才能保证它的付出不会多于。这样，对于此例来说，局中人Ⅰ分别以概率和选取，局中人Ⅱ分别以概率选取，对策的双方都会得到满意的结果，故以这样一种方式选取策略参加对策是双方的最优策略。
一般地，设局中人Ⅰ以概率选取策略，局中人Ⅱ以概率选取策略，则向量与向量分别称为局中人Ⅰ和Ⅱ的混合策略。称数学期望
为Ⅰ的赢得（Ⅱ的支付），而（x,y）称为混合局势。局中人Ⅰ的所有混合策略集记为，Ⅱ的记为，叫做G的混合扩充。
局中人Ⅰ在选择最优策略时只能以
为出发点，而后争取最好的结果，即取
（2）
同样局中人Ⅱ的支付至多是
（3）
当时，称这个公共值为对策G的值，相应策略分别称为Ⅰ与Ⅱ的最优策略，混合局势（）称为G在混合策略下的解。
定理1（对策基本定理） 在混合扩充意义下，任何矩阵对策G一定有解。（证明暂略）
定理2 矩阵对策在混合扩充意义下有解的充分必要条件是：存在，使（）为函数的一个鞍点，即对一切 ，有
（4）
证：充分性。
由于对一切，（4）均成立，故
从而
（5）
另方面，对，有
从而
（6）
由（5）和（6）有
故对策G有解。
必要性。 若G有解，则因
设
则应有
于是便有
从而（4）式成立。 证毕。
当局中人Ⅰ取纯策略时，记其相应的赢得函数为，于是
（7）
同样，当局中人Ⅱ取纯策略时，记其相应赢得函数为，于是
（8）
由（7）和（8）式，有
根据上面的记号，可给出定理2的另一等价形式：
定理3 设，则是G的解的充要条件是：对任意 有
（9）
证,设是G的解，则由定理2，（4）成立，由于纯策略是混合策略的特例，故（9）式成立，反之，由（9）成立，则有
即得（4）式。 证毕。
容易看出验证（9）式成立要比（4）式容易。
定理4 设，则为G的解充要条件是：存在，使得分别是不等式组
（10）
和不等式组
（11）
的解，且。
证,若对，存在使（10）与（11）均成立，则必有
从而
于是
（12）
将（12）中的换成，不等式仍然不变，即有
从而有
由定理2或3，是G的解。
至于必要性，只需令，即知（10）、（11）成立。 证毕。
定理4提供了求解对策问题混合扩充解的方法。由于未知，直接求解（10）、(11)似有困难，但若作变换（这里不妨设）
则（10）、（11）变成
对于Ⅰ来说越大越好，对Ⅱ来说越小越好，故问题归结为求解如下的线性规划问题：
（13）
以及
（14）
容易验证，（13）与（14）恰好互为对偶规划，因此求解其中之一即可。
如果不作变换，可据的含义直接求解如下的两个线性规划问题：
（15）
及
（16）
前述变换（13）`（14）表明，（15）及（16）互为对偶规划，取，则易见此为（15）的一个可行解。取，则易见此是（16）的可行解，现在（15）及（16）都有可行解，根据对偶理论，它们都有最优解，且最优值相同，即。据定理4，由于满足（15）、（16）的和必满足（12）进而满足（4）。这就证明了定理1的结论成立。
由于（14）中有一个自然可行解，故实际多以求解它为宜。
(三) 双矩阵对策及多人对策一、（双矩阵对策的）定义和例子
如果局中人Ⅰ的支付为，局中人Ⅱ的支付为，且不全为0，则称此对策为二人有限非零和对策。这时局中人Ⅰ、Ⅱ分别有支付矩阵，因此这一矩阵模型也称为双矩阵对策，两个局中人的支付矩阵常常合写在一起，记为，其中第一个数字是Ⅰ的支付，第二个数字是Ⅱ的支付。
例1 囚徒困境（prisoners’dilemma）
警方拘捕了两个犯罪嫌疑人（记为局中人Ⅰ和Ⅱ），分别关押、审讯。告之；若都坦白，各判刑8年；若都抵赖，各判刑一年（或因证据不足）；如一人坦白，另一人抵赖，坦白者放出，不坦白者判刑10年。下表给出囚徒困境的策略表述。
在这一对策模型中，同一局势下两个局中人所得之代数和不等于0，故为二人非零和对策，其形态为双矩阵，故而得名。
在这个对策中，每个囚徒都有两种可选择的策略：坦白或抵赖。显然不论同伙选择什么策略，每个人的最优策略是“坦白”。比如说，如果Ⅱ选择坦白，Ⅰ选择坦白时支付为-8，选择抵赖支付为-10，因而坦白比抵赖好；如果Ⅱ选择抵赖，Ⅰ坦白时支付为0，抵赖时支付为-1，因而坦白还是比抵赖好。就是说“坦白”是Ⅰ的最优选择。类似地，“坦白”也是Ⅱ的最优选择。
囚徒困境反映了一个很深刻的问题，这就是个人理性与集体理性的矛盾。如果两个人都抵赖各判刑1年，显然比都坦白判刑8年好，但这个帕雷托（Pareto）改进办不到，因为它不满足个人理性要求，不是均衡，换个角度即使两人订立攻守同盟（死不坦白）也没有用，因为它不构成均衡，没有人有积极性遵守协议。
囚徒困境在经济中有广泛的应用。一是两个寡头企业选择产量的博弈。如果两个企业联合起来形成垄断（卡特尔），选择垄断利润最大化的产量，每个企业都可得到更多的利润，但这个协议不是一个均衡，因为给定对方遵守协议的情况下，每个企业都想增加生产，结果每个企业都得到均衡产量的利润，它严格小于垄断下产量的利润。
公共产品的供给也是一个囚徒困境问题。如果大家都出钱兴办公用事业，所有人的福利都会增加。问题是，若我出钱，你不出，我得不偿失，而你出我不出，我就可以占便宜。所以每个人的最优选择都是“不出钱”，这种均衡使得所有的人的福利都得不到提高。
还有军备竞赛。如果都不搞，各把资源用之于民，不是很好吗？问题是，你搞我不搞，我就要受到威胁，对我不利。均衡结果各国都大量增加军费，福利都变得更糟糕。
经济改革本身也是这样，改革者要付出成本，而改革成果大家共享，结果是，尽管人人都认为改革好，却没有人真正去改，大家只好在都不满意的体制下，继续生活下去。
还有“一龙涝，多龙靠”；一个和尚挑水，二个和尚抬水，三个和尚没水吃了等都属于同类性质的问题。
从囚徒困境中，我们可以引出一个很重要的结论：一种制度（体制）安排，要发生效力，必须是一种（纳什）均衡。否则这种制度安排便不能成立。
二、最优策略均衡定义1 一般地，策略称为局中人i的（严格）最优策略，如果对应所有的是i的的严格最优选择，即对支付函数有
（17）
对应地，所有的被称为“劣策略”（dominated strategies）。这里表i之外所有局中人的策略组合。
显然最优策略不依赖于其他局中人的策略选择。如果对于所有的i，是i的最优策略，那么策略组合称为最优策略均衡（dominant-strategy equilibrium）。
例2 房地产开发博弈：
（a）高需求情况
（b）低需求情况
（a）的最优策略均衡是（开发，开发）（b）没有。
三、重复剔除的占优均衡
最优策略均衡若存在，则必唯一。但在绝大多数对策中，最优策略均衡是不存在的，如例2的（b）。尽管如此，在有些对策中，我们仍可用最优的逻辑找出均衡。请看下例例3 智猪博弈（boxed pigs）
猪圈里圈着两头猪，一大一小，圈里一头有个食槽，另一头装着一个按钮，控制着猪食的供应。按一下按钮，8个单位的猪食进槽，但需要支付2个单位的成本。若大猪先到，它能吃到7个单位，小猪只能吃到1个单位；若小猪先到，两者各吃到4个单位，若同时到，大猪吃到5个单位，小猪吃到3个单位。这里每头猪都有两种策略：按或等待。下表列出对应不同策略组合下的支付矩阵，如左上格表示两头猪同时按按钮，因而同时走到食槽，大猪吃到5个单位，小猪吃到3个单位，扣除2个单位的成本，支付水平分别是3和1。
显然，这个博弈没有最优策略均衡，因为尽管“等待”是小猪的最优策略，大猪却没有最优策略。大猪的最优策略依赖于小猪的策略：如果小猪选择“等待”，大猪的最优策略是“按”；反之如果小猪选择“按”，大猪的最优策略是“等待”。因此我们不能应用最优策略找出均衡。
那么什么是这个博弈的可能均衡解呢？假定小猪是理性的，小猪肯定不会选择“按”的策略，因为不论大猪选择什么策略，对小猪来说“等待”严格优于“按”，因而理性的小猪会选择“等待”。再假定大猪知道小猪是理性的，那么它会正确地预测到小猪会选择“等待”；给定这个预测，大猪的最优选择只能是“按”。这样，（按，等待）是这个博弈的唯一均衡，支付水平分别是2和4。这是一个“多劳不多得，少劳不少得”的均衡。
智猪博弈有许多应用的例子。比如说股份公司里有大股东和小股东之分。在监督成本相同的情况下，大股东得到的好处显然多于小股东，这里大股东类似大猪，小股东类似小猪。均衡的结果是，大股东担当起收集信息、监督经理的作用，小股东则搭大股东的便车。
股票市场上炒股也是如此。那里有大户，也有小户，类似“大猪、小猪”。这时对小户而言跟大户是最优选择，而大户则必须自己收集信息进行分析。
还有市场上大小企业之间的关系。进行研究开发，为新产品作广告，对大企业是值得的，对小企业则得不偿失。一种可能的情况是，小企业把精力化在模仿上，或等待大企业用广告打开市场后出售廉价产品。
类似的情况在公共产品提供上也可能出现。如富户修路，穷户坐享其成。“吃大户”等等。
在找出上述问题的均衡解时，我们实际上是应用了“重复剔除严格劣策略” （iterated elimination of strictly dominated strategies）。这个策略的思路是这样的：首先找出某局中人的劣策略（假定存在），将其剔除掉，得一新的博弈，然后再剔除这个新博弈的某个劣策略，继续剔除过程，直到只剩下一个唯一的策略组合为止，这个剩下的唯一策略组合就是问题的均衡解，称为“重复剔除的占优均衡”（iterated dominance equilibrium）。
定义2 一般地，弱劣于策略（ is weakly dominated by ），如果对于所有的
（18）
且对于某些，严格不等式成立。称相对于弱占优策略。若，上面不等式严格成立，则说（严格）劣于。
例4
(U，M)是经剔除劣策略剩下的唯一均衡结果。
均衡结果是否与劣策略的剔除顺序有关？答案是，如果每次剔除的是严格劣策略，均衡结果与剔除顺序无关；如果剔除的是弱劣策略，均衡结果可能于剔除顺序有关。这可通过下例说明。
例5
在这个博弈里，如果剔除按进行，是剩下的策略组合；另方面，如果剔除按的顺序进行，是剩下的策略组合。由于这个原因，我们一般使用严格劣策略剔除。但对此例用之，则是不可解的（读者将会看到和都是纳什均衡）。
下面的两个例子反映出博弈中的奇怪因而复杂的情形：
例6
这个博弈中（U,L）是重复剔除的占优均衡，但A中相当一部分人可能会选择D而不是U，这是因为万一B选择R所引起的后果损失太大，因而风险太大的缘故。如果损失不是-1000，而是-1，则情形就会不同。这个例子说明，有些博弈的结果对行为的不确定性是很敏感的。
例7
此例中U是局中人A的占优策略，重复剔除严格劣策略得出的均衡是（U,L）。现在假定当A选择U时（不论B选择L还是R），A的支付同时减少2，从而得到新的博弈：
决策论告诉我们，这样的改变不会使A受益，但在博弈论里则不然。因为此时B知道D是A的占优策略，故B将选择R而不是L，A将得到3个单位的效益而不是1。
四 纳什均衡
对于相当多的博弈，我们无法使用重复剔除劣策略的办法找出均衡解。如例2房地产开发博弈中的低需求的情况(b)，无论对于A还是B，没有任何一种策略优于另一种，每一个局中人的最优策略都依赖于另一个局中人的策略：如果B选择开发，A的最优策略是不开发，如果B选择不开发，A的最优策略是开发；类似地，如果A选择开发，B的最优策略是不开发，如果A选不开发，B应选开发。为了找出这个博弈的均衡解，需要引入纳什均衡（Nash equilibrium）的概念。
定义3 有n个局中人的策略表述博弈，，策略组合是一个纳什均衡，如果对于每一个i，是给定其他局中人选择的情况下，第i个局中人的最优策略。即对支付函数有
（19）
考虑策略组合，说不是G的一个纳什均衡，等价说至少对某些i而言，不是i的最优策略（给定），换言之，至少存在一个，使得
就是说如果预测不是一个纳什均衡，那么至少存在某些局中人有积极性偏离这个结果。而对于纳什均衡，则没有任何一个局中人有积极性偏离这个均衡，此时协议将自动遵守并实施。
在囚徒困境里，（坦白，坦白）是一个纳什均衡，在房地产开发博弈中，如果是低需求（开发，不开发）以及（不开发，开发）是纳什均衡等等。
当局中人的策略空间很大时，在两个有限策略博弈中，求解纳什均衡的一个简单方法如下：首先考虑A的策略，对于每一个B的给定策略，找出A的最优策略，在其对应支付下划一横杠，然后再用类似方法找出B的最优策略。在完成这一过程后，如果某一支付对两个数下都有杠，这对数字对应的策略组合就是一个纳什均衡。
例8
按上法实施，则知（D,R）是一个纳什均衡。
纳什均衡有强弱之分，定义3给出的是弱纳什均衡的概念。如果（3）式中严格不等式总成立，则称之为强纳什均衡，它似乎更可取，且对支付矩阵的微小变化不敏感。
例9 市场进入博弈
这个博弈有两个纳什均衡：（进入，默许）和（不进入，斗争），其中（进入，默许）是强纳什均衡，（不进入，斗争）是弱纳什均衡，尽管在进入者不进入时，默许和斗争对在位者是无差异的。但只有当在位者斗争时，不进入才是进入者的最优策略。所以（不进入，斗争）是纳什均衡而（不进入，默许）不是，虽然它们的支付无差异。此外，如果想用重复剔除弱劣策略的方法找到博弈的解,“斗争”是在位者的弱劣策略，因而被剔除，（进入，默许）是唯一剩下的策略组合，因而是重复剔除占优均衡，纳什均衡（不进入，斗争）将被剔除掉。这个例子也说明，（弱）纳什均衡允许弱劣策略的存在。
由定义3给出的纳什解有时不存在，请看下例。
例10 社会福利博弈
这个博弈不存在纳什均衡，类似于矩阵对策，可以定义混合纳什均衡如下：
定义4 在n个局中人对策的策略式表述中，假定局中人i有个纯策略：，那么概率分布称为i的一个混合策略，这里是i选择的概率，。
局中人i的全部混合策略的集合记为，当每一局中人都选定自己的策略时，就形成混合局势，在局势下，每一局中人的期望支付就应为
其中表示纯局势发生的概率，支付是纯局势的函数，表示对所有可能出现的纯局势求和。这样就得到n人非合作对策混合扩充
定义5 设是G的一个混合局势，如果对任意有
其中，则称是G的一个混合策略纳什均衡局势或均衡点。
让我们以福利博弈为例（例10）求解混合策略纳什均衡。假定政府的混合策略为，流浪汉的混合策略为。那么政府的期望效用函数为
对上述效用函数求微分，得到政府最优化一阶条件为：
就是说在混合战略均衡，流浪汉以0.2的概率选择找工作，0.8的概率选择游荡。同理，令 ，可求得。
纳什证明了，若为有界闭凸集，连续有界，对任意局势x，是关于的拟凹函数，则G至少有一均衡点。
五 纳什均衡应用举例
1° 库诺特（cournot）寡头竞争模型
在此模型里局中人是企业1和企业2，企业策略是选择产量；支付是利润，它是产量的函数。
用代表第i个企业的产量，代表成本函数，代表逆需求函数（P是价格，q(P)是原需求函数），第i个企业的利润函数
是纳什均衡产量意味着：
找出Nash均衡的一个办法是对利润函数求一阶导数并令其为0：
（20）
上述两个一阶条件分别定义了两个反应函数（reaction function）：
（21）
反映函数意味着每个企业的最优策略（产量）是另一个企业产量的函数。两个反映函数的交叉点就是纳什均衡，如图所示：
为了得到更具体的结果，让我们考虑上述模型的简单情况。假定企业具有相同的不变成本，即，需求函数取如下线性形式
那么最优化的一阶条件分别为：
反映函数为
就是说，j每增加1个单位的产量，i将减少单位的产量。解两个反映函数，得到纳什均衡：
此时利润分别为
为了与垄断情况作比较，让我们计算一下垄断企业的最优产量和均衡利润。垄断企业的问题是：
容易算出，垄断企业的最优产量为；垄断利润为
寡头竞争的总产量大于垄断产量的原因在于每个企业在选择自己的最优产量时，只考虑对本企业利润的影响，而忽视对另一个企业的外部负效应，这是典型的囚徒困境问题。
2° 公共地的悲剧
考虑一个有n个农民的村庄共同拥有一片草地，每个农民都有在这片草地上放牧的自由。每年春天，每个农民要决定自己养多少只羊。这里用代表第个农民饲养的数量，；，代表个农民饲养的总数量；代表每只羊的平均价值。一个重要的假设是是的函数，。假设。且存在最大存活量：当时，；当时，。
在这个博弈中，每个农民的问题是选择以最大化自己的利润。假定购买一只羊羔的价格是，则利润函数为：
最优化的一阶条件为：
这个一阶条件定义了个反应函数：
这个反应函数的交叉点就是纳什均衡，纳什均衡的总饲养量为。
将个一阶条件相加，我们得到：
如果考虑这个农民组成的群体，为了使得集体的利益最大化应求解
最优化的一阶条件为：
这里，是使集体利益最大的最优饲养量。通过比较两个最优的一阶条件可以看出，。也就是说，个人理性驱动下的纳什均衡总饲养量超过了使集体利益达到最优的饲养量。公共草地被过度使用了，集体未能实现最优，从而也没实现真正意义上的个人最优。这就是公共地的悲剧！生动地体现了个人理性和集体理性的矛盾——从个体利益出发的行为往往不能实现集体的最大利益，同时也不一定能真正实现个体的最大利益。
实际上，作为有着完全理性的每一个局中人都知道以下事实：如果他们进行合作,在集体利益达到最优的情况下，他们的利益都将增加从而达到帕累托最优的均衡结果。但也就因为他们都是完全理性的，只考虑自己利益最大化的本性内在地决定了合作是不会产生的。我们认为，这个矛盾产生的根本原因是代表集体理性的主体的缺位。下面我们引入“政府”的概念，以“政府”的理性代表集体的理性，给集体以明确的主体地位。“政府”作为局中人参与博弈，通过设立控制变量对参与人施加影响，使得博弈达到集体目标函数最优的纳什均衡结果。为此，我们建立一个有“政府”参与的控制博弈模型（参见文献[12]）。
需要说明的是，这里的“政府”可以是现实中的各级政府组织，也可以是具有一定的权力，能够对博弈中的各个参与人施加影响和控制的任何个人或组织。“政府”的控制变量对各个参与人具有强制性和约束力。下面我们以完全信息静态博弈为例加以讨论。
（Ⅰ）控制博弈模型
考虑一个完全信息静态博弈。为分析的方便起见，我们考虑局中人的战略为连续的情况，并假设目标函数可微。在此，设博弈中有个局中人，第个局中人的战略为，支付目标函数为。第个局中人的目标是使支付目标函数最大化，即，一阶条件为。若记=，则此博弈的纳什均衡即为：
方程组 的解，记为。
在引入“政府”之后，设“政府”对博弈各方设立的控制变量为，“政府”的目标函数为。这时，由于“政府”作为局中人参与博弈，改变了博弈的性质和类型，由原来的完全信息静态博弈变成了完全信息动态博弈。在这个博弈模型中，“政府”先行动决定控制变量，其他原局中人后行动，决定在控制变量约束下的最优反应。由于原来的博弈变成了这个控制博弈模型的子博弈，每个局中人的最优决策不仅依赖于其他局中人的策略，还要受到控制变量的约束，因而，第个局中人的支付目标函数变为。根据纳什均衡的存在性定理，至少存在一个相应的子博弈的纳什均衡，可能是纯策略或混合策略。即为：
方程组 的解，记为。
注意到这里是控制变量的函数，记作。代入“政府”的最优解，即得到这个控制博弈模型的子博弈精炼纳什均衡解。也就是说，“政府”的最优控制变量为，原局中人的均衡策略组合为。这就是控制博弈模型的基本思路。
上面的分析中有三个问题值得注意：1、子博弈可能存在多重均衡，从而面临选择的问题。由于理性的局中人知道“政府”的目标函数，根据聚点均衡的理论，他们会一致选择最优控制变量所对应的纳什均衡。2、子博弈中可能会存在混合策略的纳什均衡，这时“政府”的目标函数将变成期望目标函数，不影响问题的讨论； 3、在第二阶段求“政府”单人博弈最优解时，最优控制变量可能不唯一，需要在具体的问题中具体分析。
（Ⅱ）公共地悲剧博弈的最优控制
让我们回到“公共地悲剧”博弈模型中。假设这块公共地所有权属于村集体，并且在完全理性的假设下大家都知道“过度利用”这个事实。现在，村委会以“政府”的身份出现，通过对养羊收费这个控制变量对此博弈进行控制。
假设“政府”的目标是使均衡养殖总量为，控制变量变为：
当时，不收费；当时，收费。那么最优费率该是多少呢？也就是说，当每多养一只羊收费至少为多少时，才能使均衡养殖总量为呢？
由于农民的目标函数变成了分段函数：
。
对上面第二式求偏导数（对gi），然后代入的值，并令其等于零即可求得最优控制t。下面针对具体的数据进行分析。设。容易解得自由博弈下的纳什均衡为：每个农民养24只羊，各人收益都是576。而在集体利益达到最优的情况下的养羊数量为每人养16只羊，各人收益都是768。
在控制博弈模型中，第个农民的收益函数为
容易计算，当时每个农民的最优选择也是养16只羊。因此，“政府”的最优费率是。此时，每个农民都养16只羊，公共草地得到了最优利用，同时，农民的收益也达到了最大化，每人收入768。控制成功。
（Ⅲ）总结
上面控制模型的实质是将公共地养羊的最优量等额分配给各博弈方，并对超限额的博弈方实施惩罚性的收费威胁。使各个博弈方均不能从违背限额中获得好处，从而实现帕累托最优的纳什均衡结果。
实际上，对公共地悲剧问题的解决还有其他的方法。比如：1、明晰产权——公共地私有化；或者2、成立一个股份制的企业——企业合并——以消除外部性。但上面的两个思路在实际的应用中会出现可操作性差或成本过高的问题。通过政府的介入实现对博弈的控制往往能取得更好的结果，比如在应对反倾销时，可以对出口企业实行出口配额。
在现实经济生活中有许多类似于公共地悲剧的博弈，如多寡头瓜分市场、价格竞争等。由于往往更加复杂，存在博弈各方地位不对称的情况，比如规模不同、技术水平差异等。不能简单地等额分配，这时如何实现最优控制呢？
对公共地悲剧博弈的最优控制模型稍作变化，思路如下：
第一步，求出自由博弈的均衡结果，计算各个局中人所占的比例
。
第二步，求出在集体利益最大情况下的总量，按原来博弈中各局中人所占均衡总产量的比例分配给局中人，得出最优控制下的均衡结果。
第三步，建立最优控制模型
第四步，求出相应的最优费率。
按照这一思路，我们可以得到另一种形式的最优控制博弈模型。在这个博弈模型中，先求出最优均衡。控制变量可以简单的设定为区别收费，使第个博弈方的收益函数变成如下的分段函数：
其中 ＜0，
应满足：
而最优费率。显然对于每一个博弈方，在最优费率的约束下的最优选择都是。从而在最优费率的约束下存在唯一的最优均衡。
还有动态博弈和不完全信息下的博弈，这里就不介绍了，感兴趣的人可参看张维迎著《博弈论与信息经济学》一书[11]。
§7 排队论排队论也称随机服务系统理论。
排队问题在国民经济生活中和生产实际中是大量存在的。
一个排队系统主要由两个因素构成：一是服务机构（称为服务台），一是被服务的对象（称为顾客），服务机构设置得当，效率高，就会减少甚至避免排队现象，同时又可作到机构精简，节省费用，不使服务能力超过实际需要。这就需要探讨排队的规律，预测服务机构改变之后，将发生的变化，进行理论方面的研究，如排队等待维修工具和考虑增加修理设施是否合理的问题。
随机服务理论早在上世纪初就已开始，1909年瑞典工程师Erlang在研究电话网络的壅塞问题时，就曾对电话呼叫的到来所形成的“流”作了系统的研究，二次大战后受到广泛注意，近年来排队论的研究逐步走向实际应用方面。
排队问题中首要的是应研究
1、相继顾客到达时间间隔的规律。
2、服务时间的规律。
这些显然都是随机的。
设N（t）为在时间区间［0，t］内到达的顾客数（t>0）令Pn(t1，t2)表示在时间区间［t1，t2］（t2＞t1）内有n(>0)个顾客到达的概率，即
如果合于下列三个条件：
①在不重迭的时间区间内，顾客到达数是相互独立的，称这种性质为无后效性。
②对充分小的，在内有1个顾客到达的概率与t无关，而约与区间长成正比，即
③，即有两个以上到达的概率几乎是0。
则在内到达n个客户的概率满足
（1）
式中右端第一项是在内到n个而在内到0个的概率（注意），第二项表示在内到（n－1）个而在内到1个的概率，从而有
令，可得
（2）
当n=0时，（1）式中右端的第二项不存在，故有
（3）
解之得：
代入（2），可求得，从而可推得
（4）
这是周知的Poisson分布，它表示长为t的时间区间内到达n个顾客的概率，象在概率论中所学过的，我们说随机变量服从Poisson分布，它的数学期望和方差分别是
其中表示单位时间内平均到达的顾客数。
称满足①－③的顾客流为Poisson流。
当输入过程（即顾客到达排队系统）是Poisson流，两顾客相继到达的间隔时间T的概率分布就容易确定了，设T的分布函数为，则这个概率等于在时间内至少有一个顾客到达的概率（有顾客到达，事件就发生了，t越大事件发生的可能性越大），即
（5）
而概率密度
（6）
此分布称为负指数分布，其数学期望和方差是
因表示单位时间平均到达的顾客数，所以表示相继顾客到达的平均间隔时间，这正和的意义相吻合。
服务时间V的分布
对一顾客的服务时间V也就是在忙期（两空闲间连续繁忙的时间长度）相继离开系统的两顾客的间隔时间，一般的，也服从负指数分布，设它的分布函数和概率密度分别是
其中u表示单位时间能被服务完的顾客数（期望值），称为平均服务率，而，就表示一个顾客的平均服务时间，这样就表示相同时间区间内顾客到达的平均数与能被服务的平均数之比，这个比是刻画服务效率和服务机构利用程度的重要指标，我们称为服务强度。
Erlang分布
设是k个相互独立的随机变量，服从相同参数的负指数分布，那么
的概率密度是
（7）
我们说T服从K阶Erlang分布
（8）
串列的K个服务台，每台服务时间相互独立，服从相同的负指数分布（参数），那么一顾客走完这K个服务台总共所需要服务时间就服从上述的k阶Erlang分布。
注意Erlang分布族提供更为广泛的模型类，比指数分布具有更大的适应性，事实上，当K＝1时，Erlang分布化为负指数分布，这可看成是完全随机的；当K增大时，Erlang分布的图形逐渐变成对称的；当时Erlang分布近似于正态分布；时，由（8）看出，因此这是Erlang分布化为确定型分布，所以一般K阶Erlang分布可以看成完全随机与完全确定的中间型，故能现实世界提供更为广泛的适应性。
排队论中除了以上提到的一些重要指标外，还有队长（指在系统中的顾客数，它等于排队等待的顾客数（队列长）与正被服务的顾客数之和），逗留时间（指在系统中停留时间，它等于等待时间和服务时间之和），忙期等。
由于各随机变量的分布不同，排队模型亦有分类，目前普遍采用记号。
X/Y/Z （9）
其中X处填写相继到达间隔时间的分布，Y处填写服务时间的分布，Z处填写并列服务台的个数，各种分布符号是：
M——负指数分布
D——确定型
Ek——K阶Erlang分布
GI——一般相互独立的随机分布
G——一般随机分布
例如，M/M/1表示相继到达间隔时间为负指数分布，服务时间为负指数分布，单服务台的模型；等等。
下边对标准的M/M/1模型做简单分析以便获得最优服务率。所谓标准是指顾客源是无限的，单个到来，到达过程亦是平稳的；单队，且对队长无限制，先到先服务，此外还假定到达时间间隔和服务时间是相互独立的。
在分析标准的M/M/1模型时，首先要求出系统在任意时刻t的状态为n（即系统中的顾客数为n）的概率，它决定了系统运行的特征。
在时刻，系统中有n个顾客，不外下列四种情况（到达或离去2个以上的（因概率是）未列入）：
情况
在时刻t客户数
在区间
在时刻顾客数
到达
离去
（A）
n
×
×
n
(B)
n+1
×
n
(C)
n-1
×
n
(D)
n
n
其中表示发生（1个），×表示没有发生，它们的概率分别是（略去）：
情况（A）
（B）
（C）
（D）
由于这四种情况是互不相容的，所以应是这四项之和，令可得
（10）
当n＝0时，表中只有两种情况（A）和（B），从而
（11）
在稳态情形与t无关，它的导数为0，从而由（11）得，代入（10）可推得，今设（否则队列将排至无限远），又由概率性质可知，，于是有
故有
（12）
这是系统状态为n的概率，以它为基础可算出系统的运行指标和最优服务率。
（i）在系统中的平均顾客数（队长期望值）：
（13）
或
（ii）在队列中等待的平均顾客数（队列长期望值）：
（14）
关于顾客在系统中逗留的时间W（随机变量），在M/M/1情形下它服从参数为的负指数分布，即
分布函数
概率密度
于是得
（iii）在系统中顾客逗留的时间的期望值
（15）
（iv）在队列中顾客等待时间的期望值
（16）
（v）最优服务率
取目标函数Z为单位时间的服务成本与顾客在系统逗留费用之和的期望值
（17）
其中为服务机构单位时间内对一个顾客的服务费用，为每个顾客在系统停留单位时间的费用。
将（17）中的用（13）之值代入，求，并令它为0，得
由之，最优服务率为
（18）
§8 存贮论在运筹学出现之前，存贮问题就为人们所注意。比如一个大型的工厂或公司要进行正常业务活动，就必须贮备大量的备件，每种备件存贮多少才能收到最好的经济效益，这自然是人们所关心的问题，具体象水库蓄水，商店存货，甚至储蓄都是周知的存贮问题。
当然我们所关心的主要是寻求某些存贮策略，即根据需求等情况，决定多少时间补充一次，以及每次补充的数量。而存贮策略的优劣，最直接的衡量标准是该策略所耗用平均费用的多少，关于费用，大体有以下几项。
存贮费，用C1表示单位存贮费。
订货费（开工费），如手续费等（开工准备、结束费用等），用C2表示。
缺货损失费，当存贮供不应求时所引起的损失，用C3表示单位缺货费，在不允许缺货的情况下，缺货费为。
成本费，它与订货数量有关（可变费用）如货物本身的价格、运费等，在研究最优存贮策略时，此项费用一般可略去不计。
从存贮模型上看大体可分为两类：一类叫作确定性模型，即模型中的数据皆为确定的数值；另一类叫作随机性模型，即模型中含有随机变量，象需求和拖后时间（从订货到进入存贮往往需一定时间，称这段时间为拖后时间）是随机的，按概率给出。
存贮策略（即决定何时补充，补充多少数量的办法）：
t0---循环策略：每隔t0时间补充存贮量Q。
策略：当存贮量时，不补充。当时，补充存贮量。
混合策略：每经过t时间检查存贮量X，当时，不补充。当时，补充存贮量。
一个好的存贮策略，即可以使总费用小，又可以避免因缺货影响生产或使顾客失去信心，下面具体地研究一个确定性的模型，以便得到较好的存贮策略。
假设单位时间需求量为R。
生产（订货）需要时间，单位时间产量为P（P＞R）。
允许缺货则一周期时间t的总费用（略去成本费）为
总费用＝存贮费＋订货费＋缺货费其中存贮费＝×平均存贮量×存贮时间。设生产时间为T，则平均存贮量为
订货费＝
缺货费＝×平均缺货量×缺货时间
＝
＝
注意到以速度P生产T时间得产品等于时间的需求，故有，从而，于是单位时间的平均总费用是周期t和生产时间T的二元函数：
那么t与T取何值时，最小？为此令
解之得最佳周期和生产时间为
当，则得不容许缺货模型得最佳周期和生产计算时间公式：
当时，意味着生产时间很短，这样在存贮降为0时，可立得补充，这时，而生产时间很短得最佳周期为
当同时时，，则得最简单的生产时间很短且不允许缺货模型之最佳周期为
这时生产（订购）数量
便是著名的订货批量公式。
若问题的需求是随机的，导至存贮、缺货随机，这时则须计算各种费用的期望值，然后求得期望值最小的策略，这里就不多述了。
运筹学作为一门学科，在理论和方法上取得了巨大的进展，现在我们就来介绍一下各分支研究问题的对象和基本的分析方法，使读者对它们有一个概貌的了解。
作为一门学科来说，运筹学的内容可以大致表示如下：
以下对其中的主要分支，分别介绍如下。
§1 数学规划
数学规划所要解决的问题就是要在某种约束条件之下，决定某些可控制的因素应该取什么样的值，使得所选定的目标达到最小（或最大），用数学的语言来表示，就是要解决下述极值问题：
，其中S表示满足约束条件的可行解的集合。
极值问题虽然早已存在，但现在考虑的数学规划问题与古典的极值问题却有很大的差别：（i）古典方法只能处理当f（x）和可行域S很简单的情况，而现在实际中所出现的问题，f（x）和S一般都很复杂；（ii）古典方法只能处理n比较小的情形，例如n＝3，4，而现在n一般都相当大，个别问题的n甚至上百万；（iii）古典方法往往满足于一个表达式，而现在则需要把所需数值具体求出。基于上述原因，要想解决数学规划问题，必须另辟新路，，实际上，自从Dantzig在1947年发表关于解线性规划（即f（x）为x1，···，xn的一次式，S由x1，···，xn的一些线性不等式组成）的单纯形法以来，数学规划已得到非常迅速的发展，形成许多分支，成为近代应用数学的一个重要组成部分，由于它的发展，使得有关学科，如凸分析、数理经济学、应用泛函等也得到相应的发展，国际数学规划讨论会于1970年成立，有关杂志不下10种，国际数学规划讨论会至今已召开12届，我国第十一、十二届均有人参加，会议设立了Fulkerson奖（1979年始）和Dantzig奖（1982年始），授予那些在数学规划方面具有开创性成绩的工作者。
本书将详细介绍数学规划的若干分支，故这里不多叙述，有关参考书较多，如：
管梅谷，郑汉鼎，线性规划，1983
俞玉森主编，数学规划的原理和方法，1985
唐焕文，实用数学规划导论，1986
魏权龄等，数学规划与优化设计，1984
§2 图与网络方法
所谓图乃是指由一组给定的点（称为顶点）及一组连接这些点的线（称为边或弧）所组成的总体（如交通图），而图论则是研究图的理论。图论的产生可以上溯到十八世纪，但它得到重视而且逐渐成为一门学科，则是本世纪三十年代之后的事。特别是五十年代以来，由于许多具有离散性的问题皆可以通过图来表示，使得图论的研究越来越为人们所重视，如
兰姆赛问题（Ramsey）：任意六个人在一起，若不是有三个人彼此相互认识，必然有三个人互不认识。
将此问题化为图来分析：视6个人为6个顶点，认识，用实线相连接；不认识，用虚线连接。往证至少存在一个实三角形或虚三角形。任取一点V1，它与其他五点的连线中至少有三条同为实线或同为虚线，不妨假设为实线，而另一端点分别为V2,V3,V4
，这后三个顶点形成的三角形若是虚线的则问题已经解决，不然则至少有一条边为实线，从而又与已知实线构成一实三角形，故问题得证。
图1
可见用图来处理问题有时很有效，并且形象直观（如哥尼斯堡七桥问题）。许多有经济意义的问题都归结为图与网络（边上有各种数据的连通图叫做网络，数据又叫权），如
（I）、最短路问题。
在给定网络中求指定两点的最短路是图论中的一个基本问题，此问题已有有效算法。
用表示连接顶点i和j的线段长（若无则视＝＋∞），现在要从点1出发，走到n，问怎样走路程最短？
图2
考虑从点1到点j的路，按中途所经过的线段数目分类，用表示从点1到点j的且限制中途经过的线段数目不超过m的这类路中的一条最短路之长，研究，即所经线段数目为（m＋1）时的最短路长，易见它或者等于，或者等于，于是有
（1）
而1到n的最短路即为。
分析计算量：关系式（1）中，m取1，2，···，（n－2），对每一个固定的m，j取2，3，···，n，对于固定的m和j，一般说来，要经过（n－1）次加法运算和比较运算才能得到，因此计算量是。这实际上就是动态规划的顺推算法，按照动态规划的最优化原理：“作为整个过程的最优策略，具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。而对于无向图说来，起点到终点的最短路自然也是终点到起点的最短路”。
当所有线段的长度都是正数，还有更好的算法：Dijkstra算法（标号算法）。它的计算量为。具体做法是：先对起点标号，每步考察已标号顶点的相邻顶点，把距起点最近的顶点标号，直到终点被标号，按标号反向追踪即得到最短路。
例：求下图中A到B的最短路。
标号过程如下：
故最短路为，最短路长为6。
最短路问题可以直接应用于解决生产实际的许多问题，诸如各种管道铺设、线路安排、厂区布局、设备更新、选址等。
（II）、最短网络。
亦称最小树。一个实际背景是：在若干城市间架设电话线，如何架设使总长最短？
先讲讲什么是树？对于图中的任二顶点Vi 和Vj，如果从一个顶点出发沿着若干边或弧（有方向的边叫做弧），可以达到另一顶点，则称所顺次经过的边和顶点为连接Vi 和Vj的链。如果所连接的顶点重合，即Vi ＝Vj，则称这样的闭链为圈。一个圈中如果任意两顶点之间至少有一条链，则称为连通图，而连通且无圈的图叫做树。
对于含圈的连通圈，去掉每个圈的一条边，便可生成一个树，去掉的边不同生成的树也不一样，其中边权和最小的，叫做最小生成树。
求最短网络，首先容易想到的是求最小生成树，目前的方法有所谓破圈法（即任取一个圈，每次去掉其中最长的一条边，直到无圈为止），顶点扩充法（即任取一顶点，考察以此顶点为一端点的所有的边，取其中最短边的另一顶点为扩充顶点，依次类推，但要注意新扩充的边与已选好的边不能构成圈，直到所有顶点均被扩充为止）等，计算量是。
继之想到在原基础上增加一些新点和连线，扩大成一个新的网络，要求在此新网络上找出一个子网络，它是连通的，包含原图中的点，并且边权和最小，这种网络称为斯坦纳最小树（树中新增加的点叫斯坦纳点，简称斯点），它的边权和显然小于最小树的，现已证明：
任一斯点均为夹角为120o的三线段交点。
n顶点的图形最多含（n－2）个斯点。
三个顶点的斯坦纳最小树很容易找出：
以AC为边作正△ACD，连BD交△ACD的外接圆于S，则S即为斯点（见图3）
图3
易证，SA＋SB＋SC<AC+BC（注意SA＋SC＝SD）。
当n＝4时，方法仍是用一新点E代替两原顶点C，D（△ECD成一正三角形），先求△ABE的斯点S1，连S1E交外接圆于S2，则S1和S2即为所求（图4）。同样若以新点代替A，C，则可另得二个斯点，如此递归进行，可以求出任意个顶点的所有斯点。
图4
问题是图形数目太多（当，共有62370个图形），有人（Garey等）已证明最短网络是NP-complete问题，因此n略大时，譬如，计算机就不能胜任，目前可做10个顶点的问题。
现在研究方向有二，其一是对具有特殊性质的点集构造斯坦纳树，如对正n边形顶点集合，当n>5时，斯坦纳最小树即是最小生成树（详见，翁家丰，应用数学学报，2（1985）），其二是对一般的集合构造次优树，即不一定最短但接近最短，通常以最小生成树为次优树，人们对点集A，定义
称为最小斯坦纳比例，猜测，由正三角形的例子知，曾证得3<n<5时，，黄光明[3]证明了（1983年），钟金芳蓉和Graham又宣布了（计算机结果），已经很接近了。最近（2000年）我国运筹学家越民义[4]证明了猜测为真。替代结果，最坏情形增加13.4%的网络长，对随机情形只增加3%。
（III）作业时间的优化
作业时间的优化问题，象大规模工程、房屋建筑、产品开发设计、维修以及工厂的开工投产活动等一次完成的规划项目，如果对完工时间要求很严（如附有罚款条件），那么采用网络分析，以缩短工时，则具有特别重要的意义。
运用网络来描述规划，制作进度表，可以有以下几方面的好处。
有助于管理者系统的、全面的考虑规划，弄清程序，便于估计完成时间和找出可能的改进方案，从而加快规划的实现。
能提供工程计划的简明概况，其形式便于有关部门进行评论和参考，从而便于汇集各方面的意见，找出存在的问题和延误工程的原因。
对网络进行分析可找出关键路线，这就是网络中所需时间最长的一组活动。网络的解可以揭示缩短哪些活动的时间，有助于缩短整个完工时间，它还可揭示在哪些活动中加班是无益的。某些活动可延长时间而并不会延长总的完工时间，这就明确了各个工序或过程在网络中的地位。
有助于识别有关任务及其时间顺序关系，从而可更好的分派职责，更有效地运用资源，当出现问题时，网络可用来确定各种可能的其它解决方法。
网络分析可以说明各项活动的最早可能开始时间及最迟允许完工时间。
进度表法或称网络计划技术最早是在1957年，由美国杜邦公司研究出来的，最初用于计划和管理化学工厂的筹建，其结果使该项工程比原计划缩短了两个月时间，随后又将此方法用于维修，使原来需停工125小时的工程缩短为78小时，取得显著效果。
还有其它一些典型问题，都可以用图论方法来处理，如最大流问题，最小费用流问题，以及匹配（无公共顶点的边所成集合）问题，哈密顿回路和旅行商问题等等。
总之，图论所研究的问题主要分两类，一是给定的图中具有某种性质的点是否存在？若存在有多少？或至多（少）有多少？二是如何构造一个具有某些性质的图或子图？
有关参考书：
李修睦著，图论导引，1982
卢开澄著，图论及其应用，1981
§3 组合最优化
在运筹学的最优化问题中有一部分问题所涉及的因素的取值范围是离散的，而且在许多情况下是有限的（例如只取0和1）。这类问题中有些不能用传统的数学式子描述，有一些可描述，但极为复杂，以致变得不能驾驭。这类问题往往需要用某些特殊方法来处理，这样就产生了一门新兴学科－－组合最优化。它包含了许多常用的但一般很难于处理的著名问题，象在图与网络一节中提到的最短路问题，最小树问题，匹配问题，旅行售货员问题，也都属于组合最优化问题。下边我们针对一些典型问题介绍几种基本方法。
（Ⅰ）背包问题和Greedy算法（贪婪算法）。
有n件东西重量为,i=1,……，n，价格为，i=1,……，n，要求从中选出若干件装入背包，既使总重量不超过M，又使总价值最大。
Greedy算法：将比值由小到大排好队逐件考虑，不超重就装入，否则放弃之，考虑下一件。
算法的实质就是“挑好的装，装进后就不再换出”，不过一般地讲这种方法不一定能求得最优解。其实背包问题是NP-Complete问题至今没有有效解法。
（Ⅱ）匹配问题和交错链方法
Greedy算法对背包问题不能保证求得最优解，但是能求得一个比较好的初始解，人们通常以它为基础再作一些调整，如尝试用两件东西去换一件，或三件去换二件等办法来改进所求的解。交错链方法就是这种朴素思想的发展，它是组合最优化方法的核心，让我们通过匹配问题来说明交错链方法。
有n个工人和n项工作，每个人只能适应其中某几项工作。要求寻找一种分配方式，使得尽可能多的人分配到适应的工作岗位上。
例如有5个工人：A、B、C、D、E；5项工作1，2，3，4，5，各工人与各工作之间的适应关系如图5所示。图中有线段相连表示适应。例如A适应于1和2，问最多能同时安排几个人的工作？
图5 图6 图7
从图上看，是要求利用线段来将图中的端点一一配对，且希望配得对数越多越好。这就是图论中最大匹配问题。可见，所谓匹配就是无公共顶点的边所成集合。
首先，通过直觉观察，求出一个较好的初始匹配方案。在图中我们用粗线段表出，如图6所示。这时已连上粗线段的点称为已盖点，尚未连粗线的点称为未盖点，图上的一条路，若路上的线段粗细交错，则称其为交错链，如图7所示。称连接两个未盖点的交错链为增广链。对于增广链，细线段比粗线段多一条。对给定的匹配方案I，假若存在一增广链S，那么只要把路S上的细线和粗线交换一下，便可得到多安排一个人的新匹配方案。通常用下述符号表示上述调整运算：
图论中有下列基本事实：
定理1，一个匹配为最大匹配的充要条件是不存在关于它的增广链。
如何寻找增广链？采用“树生长法”（或称标号法），以图6为例，开始任取一未盖点为树根，如D，从树根沿着细线生长，接着从树梢出发沿着粗线往外生长，这样交错的沿着细线粗线继续从树梢往外延伸，直到不能再生长（如图8）
图8
我们称图（8）是以D为根的交错树，在树的生长过程中，一旦发现除树根外，另一未盖点被长到树上，过程就可中止。这时树上连结两个未盖点的那条路，便是一条增广链。图8中D与⑤之间就是一条增广链，沿着它们调整后，可得匹配如图9
图9
总结交错链方法的计算步骤如下：
1、任选初始的匹配图。
2、利用树生长法寻找增广链。如找到一条增广链则转步骤3，如所有交错树上都无增广链，则步骤终止，已找到最大匹配。
3、（调整）替换增广链上的粗线和细线，得到一个新的匹配图，然后转步骤1。
交错链方法的计算量是O(n2)。
最优匹配问题（亦称分配（派）问题）
假如我们进一步还知道了每个工人干各项工作的效率或产值，而要求找出使总的产值最大的匹配方式，这在图论中称为最优问题，即图中每条线都有权与其相对应，要求找出使权和最大（或最小）的匹配。
对交错链S，我们定义
e为S上的粗线 为S上的细线其中（e）表示线段e的权，称（S）为S的长度，让表示在所有含K条线段的匹配中，使权的和达到最大的匹配，进一步假如存在关于的增广链，则用SK表示最短增广链，即
下面的定理是组合最优化中最基本的性质。
定理2，对，若存在SK，则有如下递推关系：
，
据此定理，可知求解最优匹配的关键是寻求最短增广链，然而求又可化为在一个定向图中，求两点的最短定向路问题，如求图10。
图10 图11
由图10的最短增广链，可对应地作出定向图11，容易求出图11S到t的最短定向路为：
相应地，图10中的最短增广链为：
假如求上述最短定向路的计算量为,则求出最优匹配的计算量为。
解分配问题亦可在表上进行，采用标号法求增广链和最大匹配，然后通过简单的矩阵变换，逐步找出最优分配，这种形式的解法叫作匈牙利方法（详见管梅谷等[13]，线性规划）
还可以用下面将介绍的分枝定界法、最小调整法求最优匹配。
还有二次分配问题。例如，对厂址和厂房要求一个总的分配（一对一），使得厂址之间的距离各乘以相应工厂的运输量所得的和最小。
此问题很难解决，无有效算法，也几乎无有效的启发式算法可以利用。
（Ⅲ）排序问题和分枝定界法在许多可能的顺序中找一个最优顺序，分配加上加工顺序的限制，就成排序问题，如A与B两车床加工n件产品，加工时间分别为ti(A)和ti(B)，i＝1,2,…,n。A先加工，然后B再加工，问如何安排所用时间最少？
由于加工顺序是A先B后，故应尽量减少B的等待时间，因此不难理解其最优方案应是每次从｛ti(A)，ti(B)｝中取出一个最小值，若它属于｛ti(A)｝，则应排在最先加工，若属于｛ti(B)｝，则应排在最后加工，然后对已确定加工顺序的数据从｛ti(A)，ti(B)｝中去掉，在余集上重复上述过程，依次排列，便得最优排序，此问题亦可用动态规划的方法求解。
上述是2×n的同顺序排序问题，对于一般的m×n(m>3)的同顺序排序问题以及不同顺序的排序问题，要用“分枝定界法”求解，现将该方法简介如下：
分枝定界法欲求
（2）
考虑求
（3）
其中要求AB，称（3）为（2）的松弛问题，它要好解些。若（3）的最优解，则；否则分A为两个（或多个）子集：，解相应的松弛问题：；若，则A1问题已解决（否则，对A1重复A的过程）。同样若，则A2问题已解决，从而即为所求最小值。若而（但），则A2亦不必考虑了；否则，对A2继续实行如同A的步骤，如此进行，直到求得最优值为止（取最小的子集先考虑）。
（IV）旅行商问题和最小调整法
设有n个城市，C1，···，Cn，由Ci到Cj的路程为已知，一旅行商为了推销货物，从一城市（如C1）出发，要经过所有城市，且每个城市正好经过一次，然后回到出发点。问题是如何选择一条最优路线。容易看出，旅行商有（n－1）！种方案可供选择，对于n＝21这个不大的数目，就有20！种方案，20！是个天文数字，即使用高速计算机也无法处理这一问题。这类问题至今没有有效算法，甚至连有效的近似算法（与集合I无关）亦没有，被称为NP-困难（完全）问题。
但是上述问题有着广泛的实际背景和深刻的经济含义，例如，在计算机的集成电路的设计中就出现这一问题，还包括派车，排序，底板布线，考古学中的排号，自动钻井，工件加工顺序，邮局到各个邮箱开箱收信，以及去各分局送邮件等其它许多方面。所有这些需要又促使我们不得不研究它的解法。下面考虑用最小调整法来求解。
最小调整法的思想和步骤如下：
设旅行商问题的关系矩阵为A
其中元素表示由第i个城市到第j个城市的路程。
（1o）取每列的一个最小值，画圈，得一最小方案。若这些画圈元素又分属于不同行，则得到相应分派问题的最优解，转（3o）；否则转（2o）。
（2o）应把有二个以上画圈元素的行中的一个改画到同列的别处，待到某一无圈行中有一元素画上圈，则算一次调整。如此进行，直到每行均有一个画圈元素时为止，然后转入
（3o）即可。而每次调整均以目标函数（其值为各画圈元素之和）增值最小为原则。
（3o）如果从1o或2o得到的分派问题最优解元素的任一行指标i出发，先到其列指标j，接着从以j为行指标的元素出发，再到其列指标，如此进行下去，最后回到以i为列指标的元素止，便形成一个圈，若圈中的元素恰为n个，则所得方案即为最优方案；否则，便会形成两个以上的子圈，它不是最优解，需进行再调整，转（4o）。
（4o）以增值最小的原则实行对调调整，所谓对调调整，就是于任二子圈中各取一个元素，如与，交换它们的列指标，变成与，其结果该二子圈便合成一个圈，该变化用图简示，则为
由图可知，此四元素形成一矩形，调整是把该矩形原先对角线上的二画圈元素与的圈转给了另一对角线上的二画圈元素与。显然，调整结果，目标函数将增加：
考虑所有可能的对调调整，取其中增值最小的，加以调整，便破掉一圈。如此进行，直到无子圈为止。
对于大规模问题，求最短调整路线可用标号算法，详见文献[7]。
例1．已知五个城市间的距离如下表所示，求旅行商的最短路线。
（4）
（1o）先求出相应分配问题的最优解：（用最小调整法）
（5）
故此例的分配问题最优解为，转（3o）。
检验结果，此方案形成两个子圈：
容易看出，在两个圈中任意各取一个元素，交换它们的列下标，则这两个圈便合成一个圈。
例如，将第一个圈中的与第二个圈中的的列下标对调（或交换），便成为：
此即：
于是便破掉一个圈，此例经此处理便得到一个可行方案。在（5）中上述处理相当于：若把分属于不同圈中的两元素看成为矩形一对角线的二顶点，则其圈调换给了该矩形另外两个对角顶点对应的元素，即：
（6）
调整的结果将导致目标函数（总路程）的增加。若每次对调都选择增值最小的进行，当所有的子圈全被破掉后，即得原问题的一个更好的解。
此例中的最优解为：（对调增值为0）
（7）
由此最短路线即为：，此问题的解不唯一，另一条是：，它不能通过一步对调调整得到。
例2，设旅行商的关系矩阵为（8），求最优解。
（8）
求解过程图示如下：
得到相应分派问题最优解：，但其中有二个子循环，实行最小对调调整。
检验（3o）成立，故得较好的可行解：，它实际上是最优解，可通过对相应分派问题最优解按增值最小的原则继续调整得到并加以验证。当问题规模较大时，寻找最短调整路线可像最短路那样实行标号算法[7]。
当松弛问题的最优解有较多的圈时，破圈需涉及较多的矩形，可以证明，当问题的规模为时，所涉及的总的矩形数不超过，总的计算量不超过3，可见此算法相当有效。
对调调整对于破圈来说简单而有效，但其增值最小却又仅限于所有对调调整所破的圈，并不包括其他非对调调整所破的圈，换句话说，既能破圈而又增值最小的路线未必一定是对调调整路线。因此，我们得到的解只是近似解。
由最小对调调整得到的可行解虽然未必是最优的，但也是较好的可行解。设为最优解，是相应松弛问题——分派问题的最优解，是对调最优解，则有，若不是很大，或可以接受，则便可以作为可接受的近似解使用。
若不然，可以对继续使用最小调整法，以便求得最优解，其最小调整路线的求法仍可归结为求最短路，但考虑到最短路线可能不减少（有时甚至增加）圈，故要做些限制，即在调整后圈必须减少的限制条件下求最短路，为此需要给出某一调整是否减圈的判别方法，此问题正在研究中。
§4 投入产出方法投入产出方法是考察各种经济活动的投入与产出之间的数量关系的一种方法，于本世纪三十年代产生于美国，创始人列昂节夫因之获得73年诺贝尔经济科学奖，近年来有很大发展，目前已普遍地用来研究和分析国民经济各部门之间的数量依存关系、计划和安排未来的经济活动、预测和分析采取一项重要经济政策的经济后果研究和计算产品的价格形成等，在实践中取得一定效果，我国曾编制了1973年国民经济投入产出表。
投入：指从事一项经济活动的消耗，如原材料、能源、机器设备和人的劳动等。
产出：指经济活动的结果，如产品等。
模型分静态和动态二种类型，下表是静态价值型投入产出表。
中间产品
最终产品
总产品
合计
消费
新固定资产
库存及进出口
合计
生产资料转移价值
小计
（）
固定资产折旧合计
新创造价值
劳动报酬
社会纯收入
合计
总产品
表中Xij表示第i个部门的产品用作第j的部门生产消耗的数量。
（Ⅰ）反映各部门之间的生产技术联系，相互提供劳动对象（如原材料、辅助材料、燃料、动力等）的情况，是编表和计算的基础（如计算直接消耗系数等）
（Ⅱ）反映最终产品的构成及使用（分配），其中?即为社会最终产值或国民生产总值，从数量上它等于国民收入加上本年度的固定资产折旧额之和：?
（Ⅲ）反映社会最终产值即国民生产总值的价值形成过程，它包含二个内容，一是固定资产折旧，二是新创造价值（其中社会纯收入由利润税金等组成）。
（Ⅳ）反映国民收入的再分配从水平看有关系式：
?
将代入，并写成矩阵形式，可得：
其中A是直接消耗系数矩阵：，上式表明根据最终产品的需要量Y即可算出总产品产量X应是多少（以销定产）
从垂直方向看有如下关系式：
这个式子的经济意义为各部门的产值等于中间产品转移价值、固定资产折旧、劳动报酬和社会存收入之和，引入直接消耗系数写成矩阵形式，可得：
其中C是对角阵，其对角线上第i 个元素为。当已知C及各部门D、V、M的数值后，即可算出各部门总产量X的数值来。
投入产出方法的发展趋势，一是与数学规划结合，编制最优表（把上述方程组看作基本约束，再补充一些其它约束，求一个目标函数的最大值）二是进一步与经济计量学结合。
§5 决策论决策是人们工作和生活中普遍存在的一种活动，是为解决问题选择最佳方案的一种过程。决策效果的好坏，关系重大。它是管理过程的核心，因此决策者必须掌握科学的决策原理和方法。
一般说来，每一实际问题经常可能面临几种不同的客观环境，它不以人的意志而改变，称为自然状态（全体自然状态的集合记为I，简称状态集）；又有几种不同的行动方案（所有可供选择的行动方案之集合记为D，简称行动集）；人们希望通过对各个方案在每一状态下可能产生的效果（称为后果，用C表示）进行综合分析、比较，进而选定一个最优方案加以实施。这就提出了决策问题。
某农场考虑是否提早种植某种农作物的决策问题，详情见下表。
状态后果行动方案
不遇霜冻
遇霜冻
提早种不提早种
45
30
10
20
其中提早种遇霜冻的概率为0.4，不提早种遇霜冻的概率为0.2。
表1中的后果构成一矩阵，称为后果矩阵或益损矩阵，一般地，后果阵可表示为。
决策类型主要分以下三种：
（i）确定型。只有一种自然状态，这种决策看起来似乎很简单，但若可供选择的方案很多，例如有n个产地，m个销地的运输问题，当m和n较大时，要决定出一个运费最小的方案也并非易事。
（ii）风险型（统计型）有两种以上自然状态，并知该状态出现的概率。
（iii）不确定型，自然状态发生的概率未知。
我们下边主要介绍风险型决策方法，即当自然状态出现的概率已知时的决策问题。
首先须对“概率”进一步加以认识。以往，我们认为随机事件的概率是事件的客观属性，它具有频率解释：在相同条件下大量重复的独立试验中事件发生的次数与总试验次数之比，称之为客观概率，但对许多不确定事件，大量重复试验是不可行的。比如关于花费上亿元经费发射一枚导弹的某项决策问题，就不能依赖反复试验来取得必要的数据。对于这种一次性的、不确定事件也应根据所掌握的资料，对它们出现的可能性给出定量描述。这就产生了所谓主观概率。一个事件的主观概率是人关于该事件出现的可能性在现有认识水平上给予的主观信任程度的一种度量，它不是以重复试验为基础来作出判断，而是根据一种可以接受的数据（包括没有数据）和逻辑分析来作判断的，而且一个事件的主观概率随着事件信息增加而改变，因为信息增加将会减少不确定性，如在例1中，若有中、长天气预报，则当年霜冻的可能性就会有较好的估计。
主观概率除了获得的方法不同外，其余与客观概率无异。下面介绍一种评定主观概率的方法：讯问法。
把事件E和它的补事件E－1（即EE－1＝I，EE－1＝）进行比较。问决策者E与E－1哪个更可能发生？若回答是E，即 ，则把等分成两段，分点为，再问决策者，与，宁可接受哪个？若回答是后者，即P。照此下去，直到决策者对与不加区别为止，就取P为E的主观概率。
一、最大可能法。在风险型决策问题中选择一个概率最大的自然状态进行决策，其它自然状态可以不管，这就变成了确定型决策问题，称之为最大可能法。按此法分析例1，应选不提早种。
上述决策方法应用很广，但要注意，在一组状态中其中某一个状态出现的概率比其它的特别大，而它们相应的益损值差别不很大，这种方法的效果是较好的。如果在一组状态中，它们发生的概率都很小，且互相很接近，再要采用这种决策方法，效果是不好的，有时会引起严重错误。
二、期望值法。这里所说的期望值即概率论中的数学期望（），若，则
即等于该行动对应的益损值与取此益损值（即相应自然状态出现的）概率乘积之和。对例1有：
E（d1）=45×0.6＋10×0.4＝31
E（d2）=30×0.8＋20×0.2＝28
期望值法就是采取期望值最大（或最小）的行动方案，据此，例1应选早种。
上述分析过程可用图表示如下：
这样构造的树状图称为决策树。它直观方便，特别适用于多级决策（包含若干个决策点）比如发展某项新产品的决策过程如下图所示：
第一个决策点（方框表示决策点）为是否发展该项产品，若决定发展，则其开发（包括研究等）费是不确定的（如研究费不能确切预知），必须对各种可能的开发费及出现的概率作出评定。第二个决策点是对各开发费决定投入生产的规模（规模为0表示不投入生产），其生产费，由于原料的价格等因素，又是不确定的。对各种生产费及出现的概率又要作出评定，最后面临的决策是决定产品的售价。无论哪种售价，其销售量又是不确定的，对各种销量及可能出现的概率应作出评定。不同的可能售量决定该项产品的盈利值和亏损值。分析的步骤本质上与例1类似，应对每个决策点及其各个可能结果作通盘考虑，从决策树最右端开始逐步往左，反向进行分析。首先对任一固定的售价，评定各最终后果的期望值，比较各售价的期望值，选取最高者，作为该决策点的益损值，相应的行动就是该决策点的最优决策。对每种生产费都这样进行，然后依此往左推，直到决策树的开始决策点为止。
三、效用理论。我们已看到，对例1，按期望值最大的原则应选提早种的方案，但应当指出：对同一期望值，不同决策人会有不同的反映，就是同一决策者，在不同情况下也会有不同的反映。好比一杯水，在泰山顶上与泰山脚下，对一个人的效用是不一样的。在例1中设成本为15万，若提早种又遇霜冻，则要亏本5万，即提早种要冒亏本的风险。不同的决策者对待风险的态度会有差别，有的人回避，有的人无所谓，还有人敢冒风险，解释这种现象的理论是效用理论。
用表示提早种这一方案，虽说它的期望值是31，但风险较大，决策者甲可能认为它只能与收入25（万元）等效用，可记为25～（0.6,45;0.4,10），同理可有28～(0.8,30;0.2,20)，这样甲在决策中必然选择方案：不提早。一般地，若C～(P,a;1-P,b)（称C为的确定性当量），则可用一个所谓效用函数u(*)来反映上述事实，效用函数的构造方法如下：
先找出最好与最差的后果（如45）和（如10），令，，而定义效用值为
(10)
据此效用值（10）可作出效用曲线.具体作法是，先把 ，代入（10）并取P＝，从而算出，再用逐次讯向法寻找确定性当量C1～(P,C*;1-P,C0)，这样曲线上便有了三个点，，，分别代入（10）（仍取P＝），又可算出二个点，依此类推，即可得到所需的效用曲线，有了效用曲线后，就可从上查得任何后果的效用值，于是对每一方案均可通过效用曲线计算期望效用值（即用（10）式计算），其中期望效用值最大的方案，便是最优决策。
如对例1，已知u(45)=1,u(10)=0,这样曲线已有二个端点（10,0）和（45,1），取P＝，，，代入（10），算得效用值
然后用逐步讯问法求出确定性当量
C1=22.5～(0.5,45;0.5,10)
从而得到一点A＝（22.5，），照此下去又可算得
=0.75
讯问法C2～(0.5,45;0.5,22.5)，得C2＝30，从而得点B＝（30，0.75），同样，点C＝（16，0.25）等等，用平滑曲线把这些点连起来，即得该问题的效用曲线：
据之可查得后果为30、20的效用值分别为0.75、0.4，从而点②点③的期望效用值为：
点②：0.6×1+0.4×0=0.6
点③：0.8×0.75+0.2×0.4=0.68
故按期望效用最大恒量应选方案：不提早.把以上结果添到决策树上（括号内的数字即期望效用值）.对于多级决策，只须用效用值替代后果，用期望效用值代替期望值，其余分析都是一样的。
效用曲线可分为上凸（避险型）、直线（无关型）和下凸（冒险型）三种，与例1对应的效用曲线是上凸，即避险型的。
基于主观概率与效用理论两者之上的决策分析是更为广泛的决策理论的一部分，是近代决策理论的标志。
决策分析首先用于石油和燃气工业的一些重大决策问题，现在它已广泛地应用于医学、心理学、经济学、商业及管理甚至政府方面的决策，它已发展成为运筹学、系统科学以及管理科学工作者的重要工具。
§6 对策论
对策论（Game Theory）亦称博弈论。它是研究具有竞争、冲突等性质问题的理论，原是运筹学的一个分支。然而对策论的研究和应用始终与经济学紧密地联系在一起，带根本性的原因是经济学和对策论的研究模式是一样的，这就是强调个人理性，也就是在给定的约束条件下，追求效用最大化。在这点上，两者是完全一致的。1944年Von Newmann和Morgenstern发表了《对策论与经济行为》一书，从此开始了对策论系统化，公理化的研究。从二十世纪50年代到70年代，对策论的研究取得了丰硕的成果，并成功地应用于经济学、管理科学，军事、政治等诸多领域，特别是70年代后，对策论逐渐成为经济学研究的重要理论工具，并被当成经济学的一部分。1994年，在对策论研究中做出突出贡献的三位学者Nash（纳什）、Selten(泽尔腾)和Harsanyi(海萨尼)获得了诺贝尔经济学奖，更加显示了对策论在经济学当中的重要地位。
(一) 基本概念
对策是决策者在某种竞争场合下作出的决策。带有竞争性质的现象，如下棋、打桥牌、外交谈判、订货谈判等，称为对策现象，古代的齐王赛马就是一个非常典型的对策现象。
对策现象含有三个基本要素：局中人、策略和支付函数。
①局中人（或参与人）：有决策权的参加者。可理解为集体，如桥牌只能算两个局中人（称为二人对策），多于两个局中人的对策称为多人对策。
②策略：整个行动方案，它告诉局中人在什么时候选择什么行动。其全体称为策略集合。注意策略是指局中人在一局对策中对付对手的一个完整方案。例如，在象棋比赛中，"当头炮"不是一个策略，而只是策略的一部分。按策略多少，对策分为有限对策和无限对策（如对攻的坦克）
③支付函数。在一局对策中，若每一局中人都选定了自己的策略，把这些策略合在一起，就构成一个局势。当局势确定后，对策的结果也就确定了，这时每个局中人都有得失。因此“得失”是局势的函数，称之为支付函数（payoff function）或收益函数。
如果在一局势下，全体局中人得失的代数和总为0，则称之为零和对策，否则称为非零和对策。
对策的类型很多，例如，各局中人之间均不能协商或订立有约束的协议，一般称为非合作对策，否则称为合作对策。从局中人行动的先后顺序上考虑，又分为静态对策和动态对策。静态对策是指对策中，局中人同时选择行动或虽非同时但后行动者并不知道前者采取了什么行动。动态对策是指局中人的行动有先后顺序，且后行动者能观察到前者所选择的行动，此外，从信息角度看，又分为完全信息对策和非完全信息对策。完全信息是指每一个局中人对所有其它参与人的特征、策略集合及支付函数有准确的了解或掌握。否则就是不完全信息。
对于动态对策，用对策树来表示是非常方便的，它一目了然地显示出局中人行动的先后次序，每位局中人可选择的行动，及不同行动组合下的支付水平。请看下例。
例1 某地区的两个厂商生产同类产品，为了占领市场，各自制定了自己的产销计划。把两个厂商当作局中人I、II。为了简便，两个局中人各有两种产出水平（A1,A2）和（B1,B2）。
这一市场竞争过程可用“对策树”描述如下：
I先作出选择。从起点画出的两条线表示I可选择两种不同的产出水平。标有II的顶点表示II在知道I的选择后，再作出自己的选择，由这两个顶点分别引出的两条线表示厂商II在不同情况下可作出的不同选择。图中最上面的顶点称为对策树的终点，每个终点上的向量表示对策结束时，两个厂商分别取得的纯利润（见图（a））
（a） （b）
如果厂商Ⅰ、Ⅱ同时作出选择，则厂商Ⅱ不能确定I的选择，我们将Ⅱ对应的两个顶点用虚线框起来见图（b）,表示Ⅱ不能确定自己到底在哪一点。
虚线框起的顶点的集合，或单个顶点等都称为局中人的信息集。
在这一例子中，对策用对策树表示，一般称为扩展型对策（Extensive form），以区别通常的策略型对策（如矩阵对策）。
(二) 矩阵对策
下边介绍一下有限二人零和对策，亦称矩阵对策，因为这时支付函数可用一个矩阵表示（叫支付矩阵或赢得矩阵）。
设局中人Ⅰ的纯策略集，局中人Ⅱ的纯策略集，则Ⅰ的赢得矩阵中，元素表示在局势之下I的赢得，当然也表示Ⅱ的支付，而整个对策可简记为 为了寻求各自的最优策略，考虑下面的例子。
例2 设有一矩阵对策
求双方的最优策略。
分析：为了不冒风险，双方都应当从最坏处着想，尽量争取最好的结果，对局中人Ⅰ所有最坏结果，即A中每行的最小值：
-8,2,-1,-3
这些最坏情形中最好的结果是，因此无论局中人Ⅱ选什么策略，Ⅰ只要选参加对策，就能保证收入不会小于2，同理对局中人Ⅱ说来，应从各列的最大(表示损失最大)数中取最小值（输的最少），即
亦即选参加对策，这时两人的最坏情况下的最好结果之绝对值相等，所选策略称为最优纯策略，相应局势，称为对策的最优局势（或鞍点）由于双方对此局势都感到满意，无意再打破它，故亦称均衡解。一般地，若等式
（1）
成立，则称G有最优纯策略，这样的对策也称为有鞍点的对策，若（1）不成立，则说G在纯策略中没有解。例如对于赢得矩阵为
由于
，不满足（1），故问题在纯策略中无解。事实上，当双方各根据从最不利情形中选取最有利的结果的原则选择纯策略时，应分别选取，此时局中人Ⅰ将赢得3，比其预期赢得还多，原因就在于局中人Ⅱ选择了，使他的对手多得了不该得的赢得，故对局中人Ⅱ来说并不是最优的，因而它会考虑出，局中人Ⅰ亦会估计到这种情形而采取相应的办法，改出以使赢得为5，而局中人Ⅱ又可能仍取策略来对付局中人Ⅰ的策略。这样，局中人Ⅰ出或的可能性以及局中人Ⅱ出或的可能性都不能排除。在这种情况下，一个自然的想法是判断不同策略的概率分布。设局中人Ⅰ以概率x选取，以概率1-x选取，局中人Ⅱ以概率y选取，以概率（1-y）选取，于是对Ⅰ来说他的期望赢得应当是
由上式可见，当时，。就是说当局中人Ⅰ以概率选策略，他的赢得期望值是，他并不能保证自己的期望值超过,因为当Ⅰ企图以的概率选以提高的值，Ⅱ可通过取使反而少于。同样局中人Ⅱ只有取时，才能保证它的付出不会多于。这样，对于此例来说，局中人Ⅰ分别以概率和选取，局中人Ⅱ分别以概率选取，对策的双方都会得到满意的结果，故以这样一种方式选取策略参加对策是双方的最优策略。
一般地，设局中人Ⅰ以概率选取策略，局中人Ⅱ以概率选取策略，则向量与向量分别称为局中人Ⅰ和Ⅱ的混合策略。称数学期望
为Ⅰ的赢得（Ⅱ的支付），而（x,y）称为混合局势。局中人Ⅰ的所有混合策略集记为，Ⅱ的记为，叫做G的混合扩充。
局中人Ⅰ在选择最优策略时只能以
为出发点，而后争取最好的结果，即取
（2）
同样局中人Ⅱ的支付至多是
（3）
当时，称这个公共值为对策G的值，相应策略分别称为Ⅰ与Ⅱ的最优策略，混合局势（）称为G在混合策略下的解。
定理1（对策基本定理） 在混合扩充意义下，任何矩阵对策G一定有解。（证明暂略）
定理2 矩阵对策在混合扩充意义下有解的充分必要条件是：存在，使（）为函数的一个鞍点，即对一切 ，有
（4）
证：充分性。
由于对一切，（4）均成立，故
从而
（5）
另方面，对，有
从而
（6）
由（5）和（6）有
故对策G有解。
必要性。 若G有解，则因
设
则应有
于是便有
从而（4）式成立。 证毕。
当局中人Ⅰ取纯策略时，记其相应的赢得函数为，于是
（7）
同样，当局中人Ⅱ取纯策略时，记其相应赢得函数为，于是
（8）
由（7）和（8）式，有
根据上面的记号，可给出定理2的另一等价形式：
定理3 设，则是G的解的充要条件是：对任意 有
（9）
证,设是G的解，则由定理2，（4）成立，由于纯策略是混合策略的特例，故（9）式成立，反之，由（9）成立，则有
即得（4）式。 证毕。
容易看出验证（9）式成立要比（4）式容易。
定理4 设，则为G的解充要条件是：存在，使得分别是不等式组
（10）
和不等式组
（11）
的解，且。
证,若对，存在使（10）与（11）均成立，则必有
从而
于是
（12）
将（12）中的换成，不等式仍然不变，即有
从而有
由定理2或3，是G的解。
至于必要性，只需令，即知（10）、（11）成立。 证毕。
定理4提供了求解对策问题混合扩充解的方法。由于未知，直接求解（10）、(11)似有困难，但若作变换（这里不妨设）
则（10）、（11）变成
对于Ⅰ来说越大越好，对Ⅱ来说越小越好，故问题归结为求解如下的线性规划问题：
（13）
以及
（14）
容易验证，（13）与（14）恰好互为对偶规划，因此求解其中之一即可。
如果不作变换，可据的含义直接求解如下的两个线性规划问题：
（15）
及
（16）
前述变换（13）`（14）表明，（15）及（16）互为对偶规划，取，则易见此为（15）的一个可行解。取，则易见此是（16）的可行解，现在（15）及（16）都有可行解，根据对偶理论，它们都有最优解，且最优值相同，即。据定理4，由于满足（15）、（16）的和必满足（12）进而满足（4）。这就证明了定理1的结论成立。
由于（14）中有一个自然可行解，故实际多以求解它为宜。
(三) 双矩阵对策及多人对策一、（双矩阵对策的）定义和例子
如果局中人Ⅰ的支付为，局中人Ⅱ的支付为，且不全为0，则称此对策为二人有限非零和对策。这时局中人Ⅰ、Ⅱ分别有支付矩阵，因此这一矩阵模型也称为双矩阵对策，两个局中人的支付矩阵常常合写在一起，记为，其中第一个数字是Ⅰ的支付，第二个数字是Ⅱ的支付。
例1 囚徒困境（prisoners’dilemma）
警方拘捕了两个犯罪嫌疑人（记为局中人Ⅰ和Ⅱ），分别关押、审讯。告之；若都坦白，各判刑8年；若都抵赖，各判刑一年（或因证据不足）；如一人坦白，另一人抵赖，坦白者放出，不坦白者判刑10年。下表给出囚徒困境的策略表述。
在这一对策模型中，同一局势下两个局中人所得之代数和不等于0，故为二人非零和对策，其形态为双矩阵，故而得名。
在这个对策中，每个囚徒都有两种可选择的策略：坦白或抵赖。显然不论同伙选择什么策略，每个人的最优策略是“坦白”。比如说，如果Ⅱ选择坦白，Ⅰ选择坦白时支付为-8，选择抵赖支付为-10，因而坦白比抵赖好；如果Ⅱ选择抵赖，Ⅰ坦白时支付为0，抵赖时支付为-1，因而坦白还是比抵赖好。就是说“坦白”是Ⅰ的最优选择。类似地，“坦白”也是Ⅱ的最优选择。
囚徒困境反映了一个很深刻的问题，这就是个人理性与集体理性的矛盾。如果两个人都抵赖各判刑1年，显然比都坦白判刑8年好，但这个帕雷托（Pareto）改进办不到，因为它不满足个人理性要求，不是均衡，换个角度即使两人订立攻守同盟（死不坦白）也没有用，因为它不构成均衡，没有人有积极性遵守协议。
囚徒困境在经济中有广泛的应用。一是两个寡头企业选择产量的博弈。如果两个企业联合起来形成垄断（卡特尔），选择垄断利润最大化的产量，每个企业都可得到更多的利润，但这个协议不是一个均衡，因为给定对方遵守协议的情况下，每个企业都想增加生产，结果每个企业都得到均衡产量的利润，它严格小于垄断下产量的利润。
公共产品的供给也是一个囚徒困境问题。如果大家都出钱兴办公用事业，所有人的福利都会增加。问题是，若我出钱，你不出，我得不偿失，而你出我不出，我就可以占便宜。所以每个人的最优选择都是“不出钱”，这种均衡使得所有的人的福利都得不到提高。
还有军备竞赛。如果都不搞，各把资源用之于民，不是很好吗？问题是，你搞我不搞，我就要受到威胁，对我不利。均衡结果各国都大量增加军费，福利都变得更糟糕。
经济改革本身也是这样，改革者要付出成本，而改革成果大家共享，结果是，尽管人人都认为改革好，却没有人真正去改，大家只好在都不满意的体制下，继续生活下去。
还有“一龙涝，多龙靠”；一个和尚挑水，二个和尚抬水，三个和尚没水吃了等都属于同类性质的问题。
从囚徒困境中，我们可以引出一个很重要的结论：一种制度（体制）安排，要发生效力，必须是一种（纳什）均衡。否则这种制度安排便不能成立。
二、最优策略均衡定义1 一般地，策略称为局中人i的（严格）最优策略，如果对应所有的是i的的严格最优选择，即对支付函数有
（17）
对应地，所有的被称为“劣策略”（dominated strategies）。这里表i之外所有局中人的策略组合。
显然最优策略不依赖于其他局中人的策略选择。如果对于所有的i，是i的最优策略，那么策略组合称为最优策略均衡（dominant-strategy equilibrium）。
例2 房地产开发博弈：
（a）高需求情况
（b）低需求情况
（a）的最优策略均衡是（开发，开发）（b）没有。
三、重复剔除的占优均衡
最优策略均衡若存在，则必唯一。但在绝大多数对策中，最优策略均衡是不存在的，如例2的（b）。尽管如此，在有些对策中，我们仍可用最优的逻辑找出均衡。请看下例例3 智猪博弈（boxed pigs）
猪圈里圈着两头猪，一大一小，圈里一头有个食槽，另一头装着一个按钮，控制着猪食的供应。按一下按钮，8个单位的猪食进槽，但需要支付2个单位的成本。若大猪先到，它能吃到7个单位，小猪只能吃到1个单位；若小猪先到，两者各吃到4个单位，若同时到，大猪吃到5个单位，小猪吃到3个单位。这里每头猪都有两种策略：按或等待。下表列出对应不同策略组合下的支付矩阵，如左上格表示两头猪同时按按钮，因而同时走到食槽，大猪吃到5个单位，小猪吃到3个单位，扣除2个单位的成本，支付水平分别是3和1。
显然，这个博弈没有最优策略均衡，因为尽管“等待”是小猪的最优策略，大猪却没有最优策略。大猪的最优策略依赖于小猪的策略：如果小猪选择“等待”，大猪的最优策略是“按”；反之如果小猪选择“按”，大猪的最优策略是“等待”。因此我们不能应用最优策略找出均衡。
那么什么是这个博弈的可能均衡解呢？假定小猪是理性的，小猪肯定不会选择“按”的策略，因为不论大猪选择什么策略，对小猪来说“等待”严格优于“按”，因而理性的小猪会选择“等待”。再假定大猪知道小猪是理性的，那么它会正确地预测到小猪会选择“等待”；给定这个预测，大猪的最优选择只能是“按”。这样，（按，等待）是这个博弈的唯一均衡，支付水平分别是2和4。这是一个“多劳不多得，少劳不少得”的均衡。
智猪博弈有许多应用的例子。比如说股份公司里有大股东和小股东之分。在监督成本相同的情况下，大股东得到的好处显然多于小股东，这里大股东类似大猪，小股东类似小猪。均衡的结果是，大股东担当起收集信息、监督经理的作用，小股东则搭大股东的便车。
股票市场上炒股也是如此。那里有大户，也有小户，类似“大猪、小猪”。这时对小户而言跟大户是最优选择，而大户则必须自己收集信息进行分析。
还有市场上大小企业之间的关系。进行研究开发，为新产品作广告，对大企业是值得的，对小企业则得不偿失。一种可能的情况是，小企业把精力化在模仿上，或等待大企业用广告打开市场后出售廉价产品。
类似的情况在公共产品提供上也可能出现。如富户修路，穷户坐享其成。“吃大户”等等。
在找出上述问题的均衡解时，我们实际上是应用了“重复剔除严格劣策略” （iterated elimination of strictly dominated strategies）。这个策略的思路是这样的：首先找出某局中人的劣策略（假定存在），将其剔除掉，得一新的博弈，然后再剔除这个新博弈的某个劣策略，继续剔除过程，直到只剩下一个唯一的策略组合为止，这个剩下的唯一策略组合就是问题的均衡解，称为“重复剔除的占优均衡”（iterated dominance equilibrium）。
定义2 一般地，弱劣于策略（ is weakly dominated by ），如果对于所有的
（18）
且对于某些，严格不等式成立。称相对于弱占优策略。若，上面不等式严格成立，则说（严格）劣于。
例4
(U，M)是经剔除劣策略剩下的唯一均衡结果。
均衡结果是否与劣策略的剔除顺序有关？答案是，如果每次剔除的是严格劣策略，均衡结果与剔除顺序无关；如果剔除的是弱劣策略，均衡结果可能于剔除顺序有关。这可通过下例说明。
例5
在这个博弈里，如果剔除按进行，是剩下的策略组合；另方面，如果剔除按的顺序进行，是剩下的策略组合。由于这个原因，我们一般使用严格劣策略剔除。但对此例用之，则是不可解的（读者将会看到和都是纳什均衡）。
下面的两个例子反映出博弈中的奇怪因而复杂的情形：
例6
这个博弈中（U,L）是重复剔除的占优均衡，但A中相当一部分人可能会选择D而不是U，这是因为万一B选择R所引起的后果损失太大，因而风险太大的缘故。如果损失不是-1000，而是-1，则情形就会不同。这个例子说明，有些博弈的结果对行为的不确定性是很敏感的。
例7
此例中U是局中人A的占优策略，重复剔除严格劣策略得出的均衡是（U,L）。现在假定当A选择U时（不论B选择L还是R），A的支付同时减少2，从而得到新的博弈：
决策论告诉我们，这样的改变不会使A受益，但在博弈论里则不然。因为此时B知道D是A的占优策略，故B将选择R而不是L，A将得到3个单位的效益而不是1。
四 纳什均衡
对于相当多的博弈，我们无法使用重复剔除劣策略的办法找出均衡解。如例2房地产开发博弈中的低需求的情况(b)，无论对于A还是B，没有任何一种策略优于另一种，每一个局中人的最优策略都依赖于另一个局中人的策略：如果B选择开发，A的最优策略是不开发，如果B选择不开发，A的最优策略是开发；类似地，如果A选择开发，B的最优策略是不开发，如果A选不开发，B应选开发。为了找出这个博弈的均衡解，需要引入纳什均衡（Nash equilibrium）的概念。
定义3 有n个局中人的策略表述博弈，，策略组合是一个纳什均衡，如果对于每一个i，是给定其他局中人选择的情况下，第i个局中人的最优策略。即对支付函数有
（19）
考虑策略组合，说不是G的一个纳什均衡，等价说至少对某些i而言，不是i的最优策略（给定），换言之，至少存在一个，使得
就是说如果预测不是一个纳什均衡，那么至少存在某些局中人有积极性偏离这个结果。而对于纳什均衡，则没有任何一个局中人有积极性偏离这个均衡，此时协议将自动遵守并实施。
在囚徒困境里，（坦白，坦白）是一个纳什均衡，在房地产开发博弈中，如果是低需求（开发，不开发）以及（不开发，开发）是纳什均衡等等。
当局中人的策略空间很大时，在两个有限策略博弈中，求解纳什均衡的一个简单方法如下：首先考虑A的策略，对于每一个B的给定策略，找出A的最优策略，在其对应支付下划一横杠，然后再用类似方法找出B的最优策略。在完成这一过程后，如果某一支付对两个数下都有杠，这对数字对应的策略组合就是一个纳什均衡。
例8
按上法实施，则知（D,R）是一个纳什均衡。
纳什均衡有强弱之分，定义3给出的是弱纳什均衡的概念。如果（3）式中严格不等式总成立，则称之为强纳什均衡，它似乎更可取，且对支付矩阵的微小变化不敏感。
例9 市场进入博弈
这个博弈有两个纳什均衡：（进入，默许）和（不进入，斗争），其中（进入，默许）是强纳什均衡，（不进入，斗争）是弱纳什均衡，尽管在进入者不进入时，默许和斗争对在位者是无差异的。但只有当在位者斗争时，不进入才是进入者的最优策略。所以（不进入，斗争）是纳什均衡而（不进入，默许）不是，虽然它们的支付无差异。此外，如果想用重复剔除弱劣策略的方法找到博弈的解,“斗争”是在位者的弱劣策略，因而被剔除，（进入，默许）是唯一剩下的策略组合，因而是重复剔除占优均衡，纳什均衡（不进入，斗争）将被剔除掉。这个例子也说明，（弱）纳什均衡允许弱劣策略的存在。
由定义3给出的纳什解有时不存在，请看下例。
例10 社会福利博弈
这个博弈不存在纳什均衡，类似于矩阵对策，可以定义混合纳什均衡如下：
定义4 在n个局中人对策的策略式表述中，假定局中人i有个纯策略：，那么概率分布称为i的一个混合策略，这里是i选择的概率，。
局中人i的全部混合策略的集合记为，当每一局中人都选定自己的策略时，就形成混合局势，在局势下，每一局中人的期望支付就应为
其中表示纯局势发生的概率，支付是纯局势的函数，表示对所有可能出现的纯局势求和。这样就得到n人非合作对策混合扩充
定义5 设是G的一个混合局势，如果对任意有
其中，则称是G的一个混合策略纳什均衡局势或均衡点。
让我们以福利博弈为例（例10）求解混合策略纳什均衡。假定政府的混合策略为，流浪汉的混合策略为。那么政府的期望效用函数为
对上述效用函数求微分，得到政府最优化一阶条件为：
就是说在混合战略均衡，流浪汉以0.2的概率选择找工作，0.8的概率选择游荡。同理，令 ，可求得。
纳什证明了，若为有界闭凸集，连续有界，对任意局势x，是关于的拟凹函数，则G至少有一均衡点。
五 纳什均衡应用举例
1° 库诺特（cournot）寡头竞争模型
在此模型里局中人是企业1和企业2，企业策略是选择产量；支付是利润，它是产量的函数。
用代表第i个企业的产量，代表成本函数，代表逆需求函数（P是价格，q(P)是原需求函数），第i个企业的利润函数
是纳什均衡产量意味着：
找出Nash均衡的一个办法是对利润函数求一阶导数并令其为0：
（20）
上述两个一阶条件分别定义了两个反应函数（reaction function）：
（21）
反映函数意味着每个企业的最优策略（产量）是另一个企业产量的函数。两个反映函数的交叉点就是纳什均衡，如图所示：
为了得到更具体的结果，让我们考虑上述模型的简单情况。假定企业具有相同的不变成本，即，需求函数取如下线性形式
那么最优化的一阶条件分别为：
反映函数为
就是说，j每增加1个单位的产量，i将减少单位的产量。解两个反映函数，得到纳什均衡：
此时利润分别为
为了与垄断情况作比较，让我们计算一下垄断企业的最优产量和均衡利润。垄断企业的问题是：
容易算出，垄断企业的最优产量为；垄断利润为
寡头竞争的总产量大于垄断产量的原因在于每个企业在选择自己的最优产量时，只考虑对本企业利润的影响，而忽视对另一个企业的外部负效应，这是典型的囚徒困境问题。
2° 公共地的悲剧
考虑一个有n个农民的村庄共同拥有一片草地，每个农民都有在这片草地上放牧的自由。每年春天，每个农民要决定自己养多少只羊。这里用代表第个农民饲养的数量，；，代表个农民饲养的总数量；代表每只羊的平均价值。一个重要的假设是是的函数，。假设。且存在最大存活量：当时，；当时，。
在这个博弈中，每个农民的问题是选择以最大化自己的利润。假定购买一只羊羔的价格是，则利润函数为：
最优化的一阶条件为：
这个一阶条件定义了个反应函数：
这个反应函数的交叉点就是纳什均衡，纳什均衡的总饲养量为。
将个一阶条件相加，我们得到：
如果考虑这个农民组成的群体，为了使得集体的利益最大化应求解
最优化的一阶条件为：
这里，是使集体利益最大的最优饲养量。通过比较两个最优的一阶条件可以看出，。也就是说，个人理性驱动下的纳什均衡总饲养量超过了使集体利益达到最优的饲养量。公共草地被过度使用了，集体未能实现最优，从而也没实现真正意义上的个人最优。这就是公共地的悲剧！生动地体现了个人理性和集体理性的矛盾——从个体利益出发的行为往往不能实现集体的最大利益，同时也不一定能真正实现个体的最大利益。
实际上，作为有着完全理性的每一个局中人都知道以下事实：如果他们进行合作,在集体利益达到最优的情况下，他们的利益都将增加从而达到帕累托最优的均衡结果。但也就因为他们都是完全理性的，只考虑自己利益最大化的本性内在地决定了合作是不会产生的。我们认为，这个矛盾产生的根本原因是代表集体理性的主体的缺位。下面我们引入“政府”的概念，以“政府”的理性代表集体的理性，给集体以明确的主体地位。“政府”作为局中人参与博弈，通过设立控制变量对参与人施加影响，使得博弈达到集体目标函数最优的纳什均衡结果。为此，我们建立一个有“政府”参与的控制博弈模型（参见文献[12]）。
需要说明的是，这里的“政府”可以是现实中的各级政府组织，也可以是具有一定的权力，能够对博弈中的各个参与人施加影响和控制的任何个人或组织。“政府”的控制变量对各个参与人具有强制性和约束力。下面我们以完全信息静态博弈为例加以讨论。
（Ⅰ）控制博弈模型
考虑一个完全信息静态博弈。为分析的方便起见，我们考虑局中人的战略为连续的情况，并假设目标函数可微。在此，设博弈中有个局中人，第个局中人的战略为，支付目标函数为。第个局中人的目标是使支付目标函数最大化，即，一阶条件为。若记=，则此博弈的纳什均衡即为：
方程组 的解，记为。
在引入“政府”之后，设“政府”对博弈各方设立的控制变量为，“政府”的目标函数为。这时，由于“政府”作为局中人参与博弈，改变了博弈的性质和类型，由原来的完全信息静态博弈变成了完全信息动态博弈。在这个博弈模型中，“政府”先行动决定控制变量，其他原局中人后行动，决定在控制变量约束下的最优反应。由于原来的博弈变成了这个控制博弈模型的子博弈，每个局中人的最优决策不仅依赖于其他局中人的策略，还要受到控制变量的约束，因而，第个局中人的支付目标函数变为。根据纳什均衡的存在性定理，至少存在一个相应的子博弈的纳什均衡，可能是纯策略或混合策略。即为：
方程组 的解，记为。
注意到这里是控制变量的函数，记作。代入“政府”的最优解，即得到这个控制博弈模型的子博弈精炼纳什均衡解。也就是说，“政府”的最优控制变量为，原局中人的均衡策略组合为。这就是控制博弈模型的基本思路。
上面的分析中有三个问题值得注意：1、子博弈可能存在多重均衡，从而面临选择的问题。由于理性的局中人知道“政府”的目标函数，根据聚点均衡的理论，他们会一致选择最优控制变量所对应的纳什均衡。2、子博弈中可能会存在混合策略的纳什均衡，这时“政府”的目标函数将变成期望目标函数，不影响问题的讨论； 3、在第二阶段求“政府”单人博弈最优解时，最优控制变量可能不唯一，需要在具体的问题中具体分析。
（Ⅱ）公共地悲剧博弈的最优控制
让我们回到“公共地悲剧”博弈模型中。假设这块公共地所有权属于村集体，并且在完全理性的假设下大家都知道“过度利用”这个事实。现在，村委会以“政府”的身份出现，通过对养羊收费这个控制变量对此博弈进行控制。
假设“政府”的目标是使均衡养殖总量为，控制变量变为：
当时，不收费；当时，收费。那么最优费率该是多少呢？也就是说，当每多养一只羊收费至少为多少时，才能使均衡养殖总量为呢？
由于农民的目标函数变成了分段函数：
。
对上面第二式求偏导数（对gi），然后代入的值，并令其等于零即可求得最优控制t。下面针对具体的数据进行分析。设。容易解得自由博弈下的纳什均衡为：每个农民养24只羊，各人收益都是576。而在集体利益达到最优的情况下的养羊数量为每人养16只羊，各人收益都是768。
在控制博弈模型中，第个农民的收益函数为
容易计算，当时每个农民的最优选择也是养16只羊。因此，“政府”的最优费率是。此时，每个农民都养16只羊，公共草地得到了最优利用，同时，农民的收益也达到了最大化，每人收入768。控制成功。
（Ⅲ）总结
上面控制模型的实质是将公共地养羊的最优量等额分配给各博弈方，并对超限额的博弈方实施惩罚性的收费威胁。使各个博弈方均不能从违背限额中获得好处，从而实现帕累托最优的纳什均衡结果。
实际上，对公共地悲剧问题的解决还有其他的方法。比如：1、明晰产权——公共地私有化；或者2、成立一个股份制的企业——企业合并——以消除外部性。但上面的两个思路在实际的应用中会出现可操作性差或成本过高的问题。通过政府的介入实现对博弈的控制往往能取得更好的结果，比如在应对反倾销时，可以对出口企业实行出口配额。
在现实经济生活中有许多类似于公共地悲剧的博弈，如多寡头瓜分市场、价格竞争等。由于往往更加复杂，存在博弈各方地位不对称的情况，比如规模不同、技术水平差异等。不能简单地等额分配，这时如何实现最优控制呢？
对公共地悲剧博弈的最优控制模型稍作变化，思路如下：
第一步，求出自由博弈的均衡结果，计算各个局中人所占的比例
。
第二步，求出在集体利益最大情况下的总量，按原来博弈中各局中人所占均衡总产量的比例分配给局中人，得出最优控制下的均衡结果。
第三步，建立最优控制模型
第四步，求出相应的最优费率。
按照这一思路，我们可以得到另一种形式的最优控制博弈模型。在这个博弈模型中，先求出最优均衡。控制变量可以简单的设定为区别收费，使第个博弈方的收益函数变成如下的分段函数：
其中 ＜0，
应满足：
而最优费率。显然对于每一个博弈方，在最优费率的约束下的最优选择都是。从而在最优费率的约束下存在唯一的最优均衡。
还有动态博弈和不完全信息下的博弈，这里就不介绍了，感兴趣的人可参看张维迎著《博弈论与信息经济学》一书[11]。
§7 排队论排队论也称随机服务系统理论。
排队问题在国民经济生活中和生产实际中是大量存在的。
一个排队系统主要由两个因素构成：一是服务机构（称为服务台），一是被服务的对象（称为顾客），服务机构设置得当，效率高，就会减少甚至避免排队现象，同时又可作到机构精简，节省费用，不使服务能力超过实际需要。这就需要探讨排队的规律，预测服务机构改变之后，将发生的变化，进行理论方面的研究，如排队等待维修工具和考虑增加修理设施是否合理的问题。
随机服务理论早在上世纪初就已开始，1909年瑞典工程师Erlang在研究电话网络的壅塞问题时，就曾对电话呼叫的到来所形成的“流”作了系统的研究，二次大战后受到广泛注意，近年来排队论的研究逐步走向实际应用方面。
排队问题中首要的是应研究
1、相继顾客到达时间间隔的规律。
2、服务时间的规律。
这些显然都是随机的。
设N（t）为在时间区间［0，t］内到达的顾客数（t>0）令Pn(t1，t2)表示在时间区间［t1，t2］（t2＞t1）内有n(>0)个顾客到达的概率，即
如果合于下列三个条件：
①在不重迭的时间区间内，顾客到达数是相互独立的，称这种性质为无后效性。
②对充分小的，在内有1个顾客到达的概率与t无关，而约与区间长成正比，即
③，即有两个以上到达的概率几乎是0。
则在内到达n个客户的概率满足
（1）
式中右端第一项是在内到n个而在内到0个的概率（注意），第二项表示在内到（n－1）个而在内到1个的概率，从而有
令，可得
（2）
当n=0时，（1）式中右端的第二项不存在，故有
（3）
解之得：
代入（2），可求得，从而可推得
（4）
这是周知的Poisson分布，它表示长为t的时间区间内到达n个顾客的概率，象在概率论中所学过的，我们说随机变量服从Poisson分布，它的数学期望和方差分别是
其中表示单位时间内平均到达的顾客数。
称满足①－③的顾客流为Poisson流。
当输入过程（即顾客到达排队系统）是Poisson流，两顾客相继到达的间隔时间T的概率分布就容易确定了，设T的分布函数为，则这个概率等于在时间内至少有一个顾客到达的概率（有顾客到达，事件就发生了，t越大事件发生的可能性越大），即
（5）
而概率密度
（6）
此分布称为负指数分布，其数学期望和方差是
因表示单位时间平均到达的顾客数，所以表示相继顾客到达的平均间隔时间，这正和的意义相吻合。
服务时间V的分布
对一顾客的服务时间V也就是在忙期（两空闲间连续繁忙的时间长度）相继离开系统的两顾客的间隔时间，一般的，也服从负指数分布，设它的分布函数和概率密度分别是
其中u表示单位时间能被服务完的顾客数（期望值），称为平均服务率，而，就表示一个顾客的平均服务时间，这样就表示相同时间区间内顾客到达的平均数与能被服务的平均数之比，这个比是刻画服务效率和服务机构利用程度的重要指标，我们称为服务强度。
Erlang分布
设是k个相互独立的随机变量，服从相同参数的负指数分布，那么
的概率密度是
（7）
我们说T服从K阶Erlang分布
（8）
串列的K个服务台，每台服务时间相互独立，服从相同的负指数分布（参数），那么一顾客走完这K个服务台总共所需要服务时间就服从上述的k阶Erlang分布。
注意Erlang分布族提供更为广泛的模型类，比指数分布具有更大的适应性，事实上，当K＝1时，Erlang分布化为负指数分布，这可看成是完全随机的；当K增大时，Erlang分布的图形逐渐变成对称的；当时Erlang分布近似于正态分布；时，由（8）看出，因此这是Erlang分布化为确定型分布，所以一般K阶Erlang分布可以看成完全随机与完全确定的中间型，故能现实世界提供更为广泛的适应性。
排队论中除了以上提到的一些重要指标外，还有队长（指在系统中的顾客数，它等于排队等待的顾客数（队列长）与正被服务的顾客数之和），逗留时间（指在系统中停留时间，它等于等待时间和服务时间之和），忙期等。
由于各随机变量的分布不同，排队模型亦有分类，目前普遍采用记号。
X/Y/Z （9）
其中X处填写相继到达间隔时间的分布，Y处填写服务时间的分布，Z处填写并列服务台的个数，各种分布符号是：
M——负指数分布
D——确定型
Ek——K阶Erlang分布
GI——一般相互独立的随机分布
G——一般随机分布
例如，M/M/1表示相继到达间隔时间为负指数分布，服务时间为负指数分布，单服务台的模型；等等。
下边对标准的M/M/1模型做简单分析以便获得最优服务率。所谓标准是指顾客源是无限的，单个到来，到达过程亦是平稳的；单队，且对队长无限制，先到先服务，此外还假定到达时间间隔和服务时间是相互独立的。
在分析标准的M/M/1模型时，首先要求出系统在任意时刻t的状态为n（即系统中的顾客数为n）的概率，它决定了系统运行的特征。
在时刻，系统中有n个顾客，不外下列四种情况（到达或离去2个以上的（因概率是）未列入）：
情况
在时刻t客户数
在区间
在时刻顾客数
到达
离去
（A）
n
×
×
n
(B)
n+1
×
n
(C)
n-1
×
n
(D)
n
n
其中表示发生（1个），×表示没有发生，它们的概率分别是（略去）：
情况（A）
（B）
（C）
（D）
由于这四种情况是互不相容的，所以应是这四项之和，令可得
（10）
当n＝0时，表中只有两种情况（A）和（B），从而
（11）
在稳态情形与t无关，它的导数为0，从而由（11）得，代入（10）可推得，今设（否则队列将排至无限远），又由概率性质可知，，于是有
故有
（12）
这是系统状态为n的概率，以它为基础可算出系统的运行指标和最优服务率。
（i）在系统中的平均顾客数（队长期望值）：
（13）
或
（ii）在队列中等待的平均顾客数（队列长期望值）：
（14）
关于顾客在系统中逗留的时间W（随机变量），在M/M/1情形下它服从参数为的负指数分布，即
分布函数
概率密度
于是得
（iii）在系统中顾客逗留的时间的期望值
（15）
（iv）在队列中顾客等待时间的期望值
（16）
（v）最优服务率
取目标函数Z为单位时间的服务成本与顾客在系统逗留费用之和的期望值
（17）
其中为服务机构单位时间内对一个顾客的服务费用，为每个顾客在系统停留单位时间的费用。
将（17）中的用（13）之值代入，求，并令它为0，得
由之，最优服务率为
（18）
§8 存贮论在运筹学出现之前，存贮问题就为人们所注意。比如一个大型的工厂或公司要进行正常业务活动，就必须贮备大量的备件，每种备件存贮多少才能收到最好的经济效益，这自然是人们所关心的问题，具体象水库蓄水，商店存货，甚至储蓄都是周知的存贮问题。
当然我们所关心的主要是寻求某些存贮策略，即根据需求等情况，决定多少时间补充一次，以及每次补充的数量。而存贮策略的优劣，最直接的衡量标准是该策略所耗用平均费用的多少，关于费用，大体有以下几项。
存贮费，用C1表示单位存贮费。
订货费（开工费），如手续费等（开工准备、结束费用等），用C2表示。
缺货损失费，当存贮供不应求时所引起的损失，用C3表示单位缺货费，在不允许缺货的情况下，缺货费为。
成本费，它与订货数量有关（可变费用）如货物本身的价格、运费等，在研究最优存贮策略时，此项费用一般可略去不计。
从存贮模型上看大体可分为两类：一类叫作确定性模型，即模型中的数据皆为确定的数值；另一类叫作随机性模型，即模型中含有随机变量，象需求和拖后时间（从订货到进入存贮往往需一定时间，称这段时间为拖后时间）是随机的，按概率给出。
存贮策略（即决定何时补充，补充多少数量的办法）：
t0---循环策略：每隔t0时间补充存贮量Q。
策略：当存贮量时，不补充。当时，补充存贮量。
混合策略：每经过t时间检查存贮量X，当时，不补充。当时，补充存贮量。
一个好的存贮策略，即可以使总费用小，又可以避免因缺货影响生产或使顾客失去信心，下面具体地研究一个确定性的模型，以便得到较好的存贮策略。
假设单位时间需求量为R。
生产（订货）需要时间，单位时间产量为P（P＞R）。
允许缺货则一周期时间t的总费用（略去成本费）为
总费用＝存贮费＋订货费＋缺货费其中存贮费＝×平均存贮量×存贮时间。设生产时间为T，则平均存贮量为
订货费＝
缺货费＝×平均缺货量×缺货时间
＝
＝
注意到以速度P生产T时间得产品等于时间的需求，故有，从而，于是单位时间的平均总费用是周期t和生产时间T的二元函数：
那么t与T取何值时，最小？为此令
解之得最佳周期和生产时间为
当，则得不容许缺货模型得最佳周期和生产计算时间公式：
当时，意味着生产时间很短，这样在存贮降为0时，可立得补充，这时，而生产时间很短得最佳周期为
当同时时，，则得最简单的生产时间很短且不允许缺货模型之最佳周期为
这时生产（订购）数量
便是著名的订货批量公式。
若问题的需求是随机的，导至存贮、缺货随机，这时则须计算各种费用的期望值，然后求得期望值最小的策略，这里就不多述了。
