|
|
|
运筹学是处于数学、管理科学和计算机科学等的交叉领域。它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。运筹学可以根据问题的要求，通过数学上的分析、运算，得出各种各样的结果，最后提出综合性的合理安排，以达到最好的效果。
|
|
|
|
|
|
线性规划是研究在有限的资源条件下，如何有效地使用这些资源达到预定目标的数学方法。用数学的语言来说，也就是在一组约束条件下寻找目标函数的极值问题。
|
|
|
|
|
|
|
|
|
|
在上述条件下，求解x1，x2，…，xn，使满足下列表达式的Z取极大值（或极小值）：
|
|
|
|
|
|
解线性规划问题的方法有很多，最常用的有图解法和单纯形法。图解法简单直观，有助于了解线性规划问题求解的基本原理，下面，通过一个例子来说明图解法的应用。
|
|
|
|
例题1某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原料的消耗，如下表所示。
|
|
|
|
|
|
|
|
该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应该如何安排计划使该工厂获利最多？
|
|
|
|
该问题可用以下数学模型来描述，设x1，x2分别表示在计划期内产品I、II的产量，因为设备的有效台时是8，这是一个限制产量的条件，所以在确定产品I、II的产量时，要考虑不超过设备的有效台时数，即可用不等式表示为x1+2x2≤8
|
|
|
|
|
|
|
|
该工厂的目标是在不超过所有资源限制的条件下，如何确定产量x1，x2以得到最大的利润。若用z表示利润，这时z=2x1+3x2。综上所述，该计划问题可用数学模型表示为：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
在以x1，x2为坐标轴的直角坐标系中，非负条件x1，x2≥0是指第一象限。上述每个约束条件都代表一个半平面。如约束条件x1+2x2≤8是代表以直线x1+2x2=8为边界的左下方的半平面，若同时满足x1，x2≥0，x1+2x2≤8，4x1≤16和4x2≤12的约束条件的点，必然落在由这3个半平面交成的区域内。由例题1的所有约束条件为半平面交成的区域如下图中的影部分所示。影区域中的每一个点（包括边界点）都是这个线性规划问题的解（称可行解），因而此区域是例1的线性规划问题的解的集合，称它为可行域。
|
|
|
|
再分析目标函数z=x21+3x2，在坐标平面上，它可表示以z为参数，-2/3为斜率的一簇平行线：
|
|
|
|
|
|
位于同一直线上的点，具有相同的目标函数值，因此称它为等值线。当z值由小变大时，直线沿其法线方向向右上方移动。当移动到Q2点时，使z值在可行域边界上实现最大化（如下图所示），这就得到了例1的最优解Q2，Q2点的坐标为（4，2）。于是可计算出z=14。
|
|
|
|
|
|
|
|
这说明该厂的最优生产计划方案是：生产4件产品I，2件产品II，可得最大利润为14元。
|
|
|
|
例题1中求解得到的最优解是唯一的，但对一般线性规划问题，求解结果还可能出现以下几种情况：无穷多最优解（多重解），无界解（无最优解），无可行解。当求解结果出现后两种情况时，一般说明线性规划问题的数学模型有错误。无界解源于缺乏必要的约束条件，无可行解源于矛盾的约束条件。
|
|
|
|
从图解法中直观地看到，当线性规划问题的可行域非空时，它是有界或无界多边形。若线性规划问题存在最优解，它一定能在可行域的某个顶点得到；若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。
|
|
|
|
图解法虽然直观，但当变量数多于3个以上时，它就无能为力了，这时需要使用单纯形法。
|
|
|
|
单纯形法的基本思路是：根据问题的标准，从可行域中某个可行解（一个顶点）开始，转换到另一个可行解（顶点），并且使目标函数达到最大值时，问题就得到了最优解。限于篇幅，不再介绍单纯形法的详细求解过程。
|
|
|
|
|
|
对策论也称为竞赛论或博弈论，是研究具有斗争或竞争性质现象的数学理论和方法。具有竞争或对抗性质的行为为对策行为，对策行为的种类可以有很多，但本质上都必须包括如下的3个基本要素：
|
|
|
|
（1）局中人。指在一个对策行为中，有权决定自己行动方案的对策参加者。显然，一个对策中至少有2个局中人。通常用I表示局中人的集合。
|
|
|
|
（2）策略集。指可供局中人选择的一个实际可行的完整的行动方案的集合。每一个局中人的策略集中至少应包括2个策略。
|
|
|
|
（3）赢得函数（支付函数）。在一局对策中，各局中人所选定的策略形成的策略组称为一个局势，即若si是第i个局中人的一个策略，则n个局中人的策略组s=（s1，s2，…，sn）就是一个局势。全体局势的集合S可用各局中人策略集的笛卡儿积表示，即
|
|
|
|
|
|
对任一局势s∈S，局中人i可以得到一个赢得Hi（s）。显然，Hi（s）是局势s的函数，称为第i个局中人的赢得函数。
|
|
|
|
可以根据不同的原则对对策进行分类，其中主要的有零和对策（对抗对策）和非零和对策。零和对策是指一方的所得值为他方的所失值。在所有对策中，占有重要地位的是二人有限零和对策（矩阵对策）。
|
|
|
|
用I和II分别表示两个局中人，设局中人I有m个策略α1，α2，…，αm可供选择，局中人II有n个策略β1，β2，…，βn可供选择，则局中人I和II的策略集分别为：
|
|
|
|
S1={α1，α2，…，αm}，S2={β1，β2，…，βn}
|
|
|
|
当局中人I选定策略αi和局中人II选定策略βj后，就形成了一个局势（αi，βj）。这样的局势共有m×n个，对任一局势（αi，βj），记局中人I的赢得值为αij并称
|
|
|
|
|
|
为局中人I的赢得矩阵（或为局中人II的支付矩阵）。由于假定对策为零和的，所以局中人II的赢得矩阵就是-A。
|
|
|
|
当局中人I、II和策略集S1、S2及局中人I的赢得矩阵A确定后，一个矩阵对策就给定了，通常记成G={I，II，S1，S2；A}或G={S1，S2；A}。
|
|
|
|
在对策论方面，有一个经典的例子。战国时期，齐王有一天提出要与忌进行赛马。双方约定：从各自的上、中、下三个等级中各选一匹参赛，每匹马只能参赛一次，每一次比赛双方各出一匹马，负者要付给胜者千金。已经知道，在同等级的马中，忌的马不如齐王的马，而如果忌的马比齐王的马高一等级，则忌的马可能取胜。当时，忌手下的一个谋士给忌出了个主意：每次比赛时先让齐王牵出他要参赛的马，然后用下马对齐王的上马，用中马对齐王的下马，用上马对齐王的中马。比赛结果，忌二胜一负，可得千金。
|
|
|
|
在这个例子中，局中人是齐王和忌，局中人集合为I={1，2}。各自都有6个策略，分别为（上，中，下）、（上，下，中）、（中，上，下）、（中，下，上）、（下，中，上）、（下，上，中）。可分别表示为S1={α1，α2，α3，α4，α5，α6}和S2={β1，β2，β3，β4，β5，β6}，这样齐王的任一策略αi和忌的任一策略βj就决定了一个局势sij。如果α1=（上，中，下），β1=（上，中，下），则在局势s11下齐王的赢得值为H1（s11）=3，齐王的赢得值为H2（s11）=-3。其他局势的结果可类似得出，因此，齐王的赢得矩阵为
|
|
|
|
|
|
|
|
|
|
按性质的重要性分类，可将决策分为战略决策（涉及某组织发展和生存有关的全局性、长远问题的决策）、策略决策（为完成战略决策所规定的目的而进行的决策）和执行决策（根据策略决策的要求对执行方案的选择）。
|
|
|
|
按决策的结果分类，可分为程序决策（有章可循的决策，可重复的）和非程序决策（无章可循的决策，一次性的）。
|
|
|
|
|
|
按决策环境分类，可分为确定型决策（决策环境是完全确定的，做出的选择的结果也是确定的），风险决策（决策的环境不是完全确定的，其发生的概率是已知的）和不确定型决策（将来发生结果的概率不确定，凭主观倾向进行决策）。
|
|
|
|
按决策过程的连续性分类，可分为单项决策（整个决策过程只作一次决策就得到结果）和序列决策（整个决策过程由一系列决策组成）。
|
|
|
|
构造决策行为的模型主要有2种，分别为面向结果的方法和面向过程的方法。面向决策结果的方法程序比较简单，其过程为“确定目标→收集信息→提出方案→方案选择→决策”。面向决策过程的方法一般包括“预决策→决策→决策后”3个阶段。
|
|
|
|
|
|
|
|
|
|
|
|
（4）事件，即不为决策者所控制的客观存在的将发生的状态。
|
|
|
|
|
|
|
|
|
|
随机型决策问题是指决策者所面临的各种自然状态是随机出现的一类决策问题。一个随机型决策问题，必须具备以下几个条件：
|
|
|
|
|
|
（2）存在着不以决策者的主观意志为转移的两个以上的自然状态；
|
|
|
|
|
|
（4）不同行动方案在不同自然状态下的益损值可以计算出来。
|
|
|
|
随机型决策问题，又可以进一步分为风险型决策问题和不确定型决策问题。在风险型决策问题中，虽然未来自然状态的发生是随机的，但是每一种自然状态发生的概率是已知的或者可以预先估计的。在非确定型决策问题中，不仅未来自然状态的发生是随机的，而且各种自然状态发生的概率也是未知的或无法预先估计的。
|
|
|
|
例如，假设软考在线公司需要根据下一年度宏观经济的增长趋势预测决定投资策略。宏观经济增长趋势有不景气、不变和景气3种，投资策略有积极、稳健和保守3种，各种状态的收益如下表所示。
|
|
|
|
|
|
|
|
由于下一年度宏观经济的各种增长趋势的概率是未知的，所以是一个不确定型决策问题。常用的不确定型决策的准则主要有以下几个：
|
|
|
|
（1）乐观主义准则。乐观主义准则也叫最大最大准则（maxmax准则），其决策的原则是“大中取大”。持这种准则思想的决策者对事物总抱有乐观和冒险的态度，他决不放弃任何获得最好结果的机会，争取以好中之好的态度来选择决策方案。决策者在决策表中各个方案对各个状态的结果中选出最大者，记在表的最右列，再从该列中选出最大者。在上例中，如果使用乐观主义准则，在3种投资方案下，积极方案的最大结果为500，稳健方案的最大结果为300，保守方案的最大结果为400。其最大值为500，因此选择积极投资方案。
|
|
|
|
（2）悲观主义准则。悲观主义准则也叫做最大最小准则（maxmin）准则，其决策的原则是“小中取大”。这种决策方法的思想是对事物抱有悲观和保守的态度，在各种最坏的可能结果中选择最好的。决策时从决策表中各方案对各个状态的结果选出最小者，记在表的最右列，再从该列中选出最大者。在上例中，如果使用maxmin准则，在3种投资方案下，积极方案的最小结果为50，稳健方案的最小结果为150，保守方案的最小结果为200。其最大值为200，因此选择保守投资方案。
|
|
|
|
（3）折中主义准则。折中主义准则也叫做赫尔威斯准则（Harwicz Decision Criterion），这种决策方法的特点是对事物既不乐观冒险，也不悲观保守，而是从中折中平衡一下，用一个系数α（称为折中系数）来表示，并规定0≤α≤1，用以下算式计算结果
|
|
|
|
cvi=α×max{aij}+（1-α）×min{aij}
|
|
|
|
即用每个决策方案在各个自然状态下的最大效益值乘以α，再加上最小效益值乘以1-α，然后比较cvi，从中选择最大者。
|
|
|
|
（4）等可能准则。等可能准则也叫做Laplace准则，它是19世纪数学家Laplace提出来的。他认为，当决策者无法事先确定每个自然状态出现的概率时，就可以把每个状态出现的概率定为1/n（n是自然状态数），然后按照最大期望值准则决策。事实上，这就转变为一个风险决策问题了。
|
|
|
|
（5）后值准则。后值准则也叫做Savage准则，决策者在制定决策之后，如果不能符合理想情况，必然有后的感觉。这种方法的特点是每个自然状态的最大收益值（损失矩阵取为最小值），作为该自然状态的理想目标，并将该状态的其他值与最大值相减所得的差作为未达到理想目标的后值。这样，从收益矩阵就可以计算出后值矩阵。决策的原则是最大后值达到最小（minmax），也叫最大最小后值。例如，上表的后值矩阵如下表所示。
|
|
|
|
|
|
|
|
根据上表，在3种投资方案下，积极方案的最大后值为350，稳健方案的最大后值为300，保守方案的最大后值为300。其最小值为300。按照后值准则，既可以选择保守投资方案，也可以选择稳健投资方案。
|
|
|
|
|
|
风险决策是指决策者对客观情况不甚了解，但对将发生各事件的概率是已知的。在风险决策中，一般采用期望值作为决策准则，常用的有最大期望收益决策准则（Expected Monetary Value, EMV）和最小机会损失决策准则（Expected Opportunity Loss, EOL）。
|
|
|
（1）最大期望收益决策准则。决策矩阵的各元素代表“策略——事件”对的收益值，各事件发生的概率为pj，先计算各策略的期望收益值 ，i=1，2，…，n，然后从这些期望收益值中选取最大者，以它对应的策略为决策者应选择的决策策略。
|
|
|
（2）最小机会损失决策准则。决策矩阵的各元素代表“策略——事件”对的损失值，各事件发生的概率为pj，先计算各策略的期望损失值 ，i=1，2，…，n，然后从这些期望收益值中选取最小者，以它对应的策略为决策者应选择的决策策略。当EMV为最大时，EOL便为最小。所以在决策时用这2个决策准则所得结果是相同的。
|
|
|
|
例如，软考在线公司要从A地向B地的用户发送一批价值90 000元的货物。从A地到B地有水、两条路线。走路时比较安全，其运输成本为10 000元；而走水路时一般情况下的运输成本只要7000元，不过一旦遇到暴风雨天气，则会造成相当于这批货物总价值的10%的损失。根据历年情况，这期间出现暴风雨天气的概率为1/4，那么软考在线公司应该选择走哪条路呢？这就是一个风险型决策问题，其决策树如下图所示。
|
|
|
|
|
|
|
|
由于该问题本身带有外生的不确定因素，因此最终的结果不一定能预先确定。不过，软考在线公司应该根据一般解决带概率分布、具有不确定性的问题时常用的数学期望值进行决策，而不是盲目碰运气或一味害怕、避风险。
|
|
|
|
根据本问题的决策树，走水路时，成本为7000元的概率为75%，成本为16 000元的概率为25%，因此走水路的期望成本为（7 000×75%）+（16 000×25%）=9250元。走路时，其成本确定为10 000元。因此，走水路的期望成本小于走路的成本，所以应该选择走水路。
|
|
|
