《定量分析方法（第三版）》第九讲：最优化与决策方法

定量分析方法

第9章最优化与决策方法公共管理中的很多复杂问题仅凭经验难以做出抉择，还需要借助科学方法。决策是为达到某种目标，从若干个求解方案中选择一个最优或合理方案的过程。最优化是指针对决策问题，按照决策目标，从多个可能方案中选择出最好方案的过程。第9章最优化与决策方法主要内容一、最优化与决策方法概述二、线性规划问题及其求解三、对策方法四、风险型决策方法五、多目标决策方法六、最优化与决策的工具软件简介第9章最优化与决策方法重点问题一、最优化问题的解决过程二、线性规划问题及求解三、有鞍点的矩阵对策问题及求解四、无鞍点的矩阵对策问题及图解法求解五、决策树方法解多阶段决策问题六、化多为少法和分层序列法求解多目标决策问题第9章最优化与决策方法决策包含从发现问题到解决问题的全过程，根据决策的广义定义，即：把决策看作一个过程，在这个过程中，决策者以特定目标为核心，利用自己所掌握的信息和具有的经验，考虑主客观条件，提出各种可行方案，然后采用一定的科学方法和手段，进行比较、分析和评价，按照决策准则，从众多不同方案中筛选出最满意的方案，并根据方案实施的反馈情况对方案进行修正控制，直至目标实现。从这里看出，在决策过程中包含有最优化的过程，最优方法起源于第二次世界大战期间。第二次世界大战之后，开始探讨最优化方法在工商企业和其他国民经济部门的应用；20世纪40年代后半期，致力于最优化方法理论基础的研究20世界50年代后期，最优化方法作为一门理论性和应用性很强的学科逐渐形成并发展；20世纪60年代，最优化发挥的作用越来越大，取得一系列成就，并在20世纪80年代，发展到兴旺时期。最优化与决策方法的产生与发展一、最优化与决策方法概述1、模型的基本要求能完整地描述所研究的系统，以便能代替现实系统供我们分析研究在适合所研究问题的前提下，模型应尽量简单决策问题的分析和求解步骤一、最优化与决策方法概述2、分析问题和求解模型的步骤提出并明确问题建立模型分析并求解模型检验并评价模型应用或实施模型的解决策问题的分析和求解步骤一、最优化与决策方法概述问题的提出二、线性规划问题及其求解在管理活动中，经常提出一类问题，即如何合理利用有限的人力、物力、财力等资源，以达到最好的经济效果。例9.1某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗（见表）。该工厂生产一件产品I可获利2元，每生产一件产品II可获利3元，问应如何安排计划可使该上产获利最多？产品投入ⅠⅡ≤限量设备128台时原材料A4016kg原材料B0412kg问题的提出二、线性规划问题及其求解解这类问题可以用以下的数学模型来描述。设分别表示在计划内产品I、II的产量。因为设备的有效台时是8，这是一个限制产量的条件，所以在确定产品I、II的产量时，要考虑不超过设备的有效台时数，即可用不等式表示为：同理，因原材料A、B的限量，可以得到以下不等式：设该工厂的目标是在不超过所有资源限量的条件下，如何确定产量以得到最大的利润。若用z来表示利润，这时。综上所述，该计划问题可用数学模型表示为：问题的提出二、线性规划问题及其求解目标函数：满足的约束条件：线性规划问题的数学模型二、线性规划问题及其求解从例9.1可以看出，实际中存在这样一类优化问题，它们具有以下共同特征：每一个问题都用一组决策变量表示某一方案，这组决策变量的值代表某一个具体方案。一般这些变量取值都是非负的。存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示都有一个要求达到的目标，它可用决策变量的线性函数（称为目标函数）来表示，按问题的不同，这些目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划数学模型。其一般形式为：目标函数：线性规划问题的数学模型二、线性规划问题及其求解满足的条件：线性规划问题的可行解集为凸集可行解集S中的点x是极点，并且仅当x是基可行解线性规划问题的最优解可以在极点上达到线性规划问题解的性质二、线性规划问题及其求解线性规划问题的单纯形法二、线性规划问题及其求解单纯形法是求解线性规划问题的基本方法之一，其基本思路是，首先从可行域中找一个基可行解，然后判别它是否为最优解，如果是，则停止计算；否则，就找一个更好的基可行解，再进行检验，如此反复迭代，直至找到最优解，或者判定它无解（即无有限最优解）为止。矩阵对策问题三、对策方法对策的三要素：局中人：有权决定自己行为方案的对局参加者称为局中人。策略：对局中一个实际可行的方案称为一个策略。赢得矩阵（支付）：当每个局中人在确定了所采取的策略后，其策略组合就形成一个局势，并产生确定的收益或损失称为赢得（支付）。赢得与局势之间的对应关系称为赢得（支付）函数。矩阵对策问题三、对策方法

根据参加对策的局中人的数目，可以将对策分为二人对策和多人对策，局中人为二人的称为二人对策。根据局中人可供选择的策略的有限或无限，可将对策分为有限对策和无限对策。根据各局中人赢得值的代数和（赢者为正，输者为负）是否为零，将对策分为零和对策与非零和对策。矩阵对策的数学模型三、对策方法

设两个局中人为I、II，局中人I有m个策略：；用S1表示这些策略的集合：

同样，局中人II有n个策略：,用S2表示这些策略的集合：

矩阵对策的数学模型三、对策方法局中人I的赢得矩阵是：局中人II的赢得矩阵是。把一个对策记为。矩阵对策的数学模型三、对策方法在局中人I设法使自己的赢得尽可能大的同时，局中人II也设法使局中人I的赢得尽可能小。

所以局中人I应首先考虑用

策略所能赢得的最小，然后在这些最小赢得中选择最大。局中人I可以保证赢得同样，局中人II可以保证局中人I的赢得不超过

矩阵对策的最优纯策略三、对策方法1、混合策略定义定义7-1：对给定的矩阵对策若等式成立，则称这个公共值为对策G的值，记为VG，而达到的局势称为对策G在纯策略意义下的解，记为而

和

分别称为局中人I和局中人II的最优纯策略。矩阵对策的最优纯策略三、对策方法定理7-1：矩阵对策在纯策略意义下有解的充分必要条件是：存在一个局势，使得对一切均有

矩阵对策的最优纯策略三、对策方法定理7-1表明矩阵对策有解的充分必要条件是在A中存在元素是其所在行中最小的同时又是其所在列中最大的。这时即是对策值，因此也称为“鞍点”，而为对策的解。矩阵对策的混合策略三、对策方法

对矩阵对策

而言，局中人I有把握的至少赢得是，局中人II有把握的至多损失是。局中人I的赢得不会超过局中人II的损失，即总有。仅当时，矩阵对策G存在纯策略意义下的解，且。但实际更多的情况是，此时不存在纯策略意义下的解。矩阵对策的混合策略三、对策方法例如，假设赢得矩阵为：

对两个局中人来说，不存在一个双方均可接受的平衡局势，对策没有纯策略意义下的解。一种较合乎实际的想法是给出一个选取不同策略的概率分布。矩阵对策的混合策略三、对策方法定义7-2:对给定的矩阵对策其中把纯策略集合对应的概率向量其中和其中分别称为局中人I和局中人II的混合策略。矩阵对策的混合策略三、对策方法如果局中人I选取的策略为局中人II选取的策略为，则期望值称为局中人I的期望赢得，而局势（X，Y）称为“混合局势”，局中人I，II的混合策略集合记为

。矩阵对策的混合策略三、对策方法定义7-3:设是对策G的混合扩充，如果有则称这个公共值为对策G在混合意义下的值，记为

，而达到

的混合局势称为对策G在混合策略意义下的解，而和

分别称为局中人I，II的最优混合策略。矩阵对策的混合策略三、对策方法定理7-2：任意一个给定的矩阵对策在混合策略意义下一定有解。

矩阵对策的解可能不只一个，但对策值是唯一的。矩阵对策的混合策略三、对策方法2、优超原则

在局中人I的纯策略中，假设存在和，如果对局中人II的一切纯策略，都有，即局中人I的赢得矩阵的第l行元素不小于第k行对应的元素，则局中人I的纯策略优于，局中人I选择的概率为零，可以去掉赢得矩阵的第k行。同理，在局中人II的纯策略中，假设存在和，如果对局中人I的一切纯策略，都有，则局中人II的纯策略

优于，局中人II选择的概率为零，可以去掉赢得矩阵的第k列。三、对策方法矩阵对策的混合策略例7.4.3：设某矩阵对策的赢得矩阵为试利用优超原则简化该矩阵。解：经4步后最终可化为二阶矩阵矩阵对策的混合策略三、对策方法3、没有鞍点的矩阵对策的解法

2*2矩阵对策的公式解法定理7-3：对给定的矩阵对策如果A无鞍点，则局中人I的最优混合策略

，局中人II的最优混合策略和对策值由下列公式给出：令矩阵对策的混合策略三、对策方法上述公式来源于以下两个方程组：决策风险四、风险性决策方法在人们的日常生活或企业组织的经营管理中，经常会遇到一些决策问题，它包括下列要素：1、自然状态，描述了决策问题所处的各种状态；2、行动方案，解决决策问题，决策者可采取的行动；3、后果，是决策者采取了某一行动方案后可能获得的结果；4、效能，是客观结构在决策者心中的价值。决策问题通常有两种描述和解决方法，一种是决策矩阵法，一种是决策树方法。决策矩阵法四、风险性决策方法状态概率状态方案决策益损期望值E(A)E(A)决策矩阵的一般形式决策矩阵法四、风险性决策方法叫做决策空间；叫做状态向量；同样设有m个行动方案A1,A2,…,Am，写成集合为对风险型决策问题，假定它们是随机变量，其发生的概率分别用表示，由于发生这类事件的可能性是相互排斥的，又是相互独立的事件，故有表中主要部分是在各自然状态下决策者采取行动方案的后果。决策树方法四、风险性决策方法

决策树是一种形象的说法，如下图所示。它所伸出的线条像大树的树干和树枝，整个图形就像一棵大树。自然状态点自然状态点123决策点概率枝概率枝概率枝结果点结果点结果点结果点方案分枝方案分枝修枝概率枝

图中左边的方块叫决策点，由它画出若干线条，每条线代表一个方案，叫方案分枝。方案分枝的末端画个圆圈，叫做自然状态点。从它引出的线条代表不同的自然状态，叫概率枝。在概率枝的末端画个三角，叫做结果点，在结果点决策树方法四、风险性决策方法旁，一般列出不同自然状态下的收益或损失值。决策树的画图是从左至右逐步完成的。

应用决策树来作决策的过程，是从右至左逐步后退进行分析的。根据右端结果点旁的益损值和概率枝上的概率，计算出每个自然状态点上的益损期望值，然后根据不同方案分枝末端的益损期望值结果作出选择。方案的舍弃叫做修枝，被舍弃的方案用在方案分枝上做“”的记号来表示（即修剪的意思）。最后在决策点留下一条方案分枝，即为最优方案。决策树方法四、风险性决策方法决策树法的优点

（1）可以构成简单、明了、清晰的决策过程，使决策者有步骤、有顺序地进行决策；

（2）直观、形象，可使决策者以科学的逻辑推理去周密地思考各种有关因素；

（3）便于集体决策，集思广益，集中群众智慧和统一不同意见，同时也很适合于向上级领导机关汇报决策过程和结果。贝叶斯决策方法四、风险性决策方法在风险决策问题中，自然状态的发生概率一般是根据过去的资料和经验估计的，其估计结果是否准确直接影响着决策效果。概率估计的准确程度取决于所掌握情报资料的多少和详细程度，但是为了获取情报，需要进行调查研究等活动，要消耗人财物力。因此需要权衡是否需要再作调查或试验，以及需要投入多少人力和财力去获取新的情报。这是一类复杂的决策问题，涉及统计决策中的先验概率和后验概率。贝叶斯决策法就是运用概率论中的贝叶斯定理解决这类问题的方法。贝叶斯决策是在已知自然状态先验概率的情况下，通过抽样调查，利用贝叶斯公式修正先验概率，进而取得后验概率，并据此进行决策的。贝叶斯决策方法四、风险性决策方法

设A、B为两个随机事件，它们发生的概率分别为P(A)、P(B)，P(AB)表示A、B同时发生的概率。所谓条件概率是指在事件B发生的前提（条件）下，A发生的概率，记为P(A|B)。或而根据全概率公式贝叶斯决策方法四、风险性决策方法可以得到贝叶斯定理表达式：

上式说明，已知事件发生的概率和发生条件下发生的概率，就可以求得在事件发生的前提下，发生的概率。完全情报的价值四、风险性决策方法对完全不确定型决策问题，获得了有关情报资料后就易于把问题转化为风险型决策问题。而对于风险型决策问题，获得的情报（信息）越多，对自然状态发生概率的估计就越准确，作出的决策就越合理。但为了获得情报，就要进行调查、试验等工作，这需要支付一定费用。因此，为了权衡得失，有必要估算情报本身的价值。多目标决策问题的基本概念五、多目标决策方法在多目标决策问题中，由于不能简单比较两个解的优和劣，所以就有劣解和非劣解两个重要概念。现用一直线坐标描述和两个目标（极大化）的大小，得到5个点（见9-1图），显然点③④⑤都比①②点为优，故①②为劣解，在多目标决策中应舍去。而③④⑤三点各有一个指标优越，故不能舍去，称之为非劣解，也叫有效解。处理多目标决策问题，要先找出非劣解，然后再按一定规则从中选取满足要求的，作出最后决策。多目标决策问题的基本概念五、多目标决策方法图9-1多目标决策多目标决策问题的解法五、多目标决策方法1、以少胜多的方法“以少胜多”的主要目的是将多目标化成单目标问题处理，目前主要有以下几种方法：（1）主要目标法。通过对实际问题的分析，抓住其中一两个主要目标，让它们尽可能优化，而其他指标只要满足一定要求即可。这种方法比较有效。（2）线性加权法。若有m个目标，分别给以权系数，然后作新的目标函数（也称有效函数）。这种方法的难点是如何找到合理的权系数，使多个目标用同一尺度统一起来，同时所找到的最优解又是向量极值的好的非劣解。多目标决策问题的解法五、多目标决策方法2、层次序列法由于同时处理m个目标比较麻烦，故可采用层次序列法。层次序列法的思想是把目标按其重要性给出一个序列，分别为最重要目标、次要目标等。设给出的重要性序列为，下面介绍逐个求最优化地序列最优化。首先对第一个目标求最优，并找出所有最优解的集合记为,然后在求第二个目标的最优解，记这时的最优解集合为，如此等等，一直到求出第个目标的最优解，其模型如下：该方法有解的前提是