河南理工大学2010级《管理运筹学》讲义

运筹学讲义绪论〔2学时〕参考教材：运筹学根底教程〔魏权龄〕管理运筹学〔韩伯棠〕管理运筹学通论〔韩大卫〕运筹学〔胡运权〕先修课程：一元微积分、线性代数、概率统计学时：48+〔8〕主讲教师：狄军锋运筹学开展运筹学的产生最早与1938年出现于英国，简称OR(operationalResearch)夫运筹帷幄之中，决胜于千里之外，吾不如子房。---史记古代运筹学思想：田忌赛马+丁谓挖沟+沈括运军粮二战中的运筹学：反潜艇策略、深水炸弹的起爆深度、诺曼底登陆运筹学在我国的开展：50年代中期，钱学森、许国志等教授将运筹学由西方引入我国。管梅谷〔1962年，山东师范大学〕：“中国邮递员问题”华罗庚：优选法〔1970〕和统筹法〔1965〕2、运筹学的定义：管理运筹学是一门应用科学，它广泛应用现有的科学技术和数学方法，解决管理中提出的专门问题，为决策者选择最优或较优的决策提供定量依据。运筹学是一门新兴的交叉学科，来源于军事、管理和经济。本课程主要介绍用于解决管理领域问题的运筹学，因此称为管理运筹学，也有人称为管理科学。二、运筹学解决问题的思路提出问题→建模→求解→结果分析与调整→实施运筹学的学科内容：线性规划〔LP〕；*整数规划〔IP〕；*非线性规划(NP)；*多目标规划〔MP〕；动态规划〔DP〕；对策论〔GT〕；决策分析〔DA〕；存贮论〔IC〕；排队论〔QT〕；图论〔GraphTheory〕三、章节安排1、绪论〔2学时〕2、线性规划(14学时)3、动态规划〔6学时〕4、存储论〔6学时〕5、对策论〔10学时〕6、决策论〔6学时〕7、统筹方法〔2学时〕8、总复习〔2学时〕四、应用举例猴子运香蕉海盗分宝石猜生日第二章线性规划*主要内容1、线性规划的一般形式、压缩形式、矩阵形式、向量形式2、线性规划问题的图解法〔3〕3、线性规划问题的标准形式4、单纯形方法〔4〕5、线性规划问题应用举例〔3〕6、运输问题的解法〔4〕§1线性规划问题的根本模型引例【引例1】某工厂在方案期内要安排生产Ⅰ、Ⅱ两种产品，生产单位产品需的设备台时，A、B两种原材料的消耗以及每种产品可获利润如下表所示。问应如何安排生产进度使工厂的获利最多？ⅠⅡ资源限量设备128台时原材料A4016kg原材料B0412kg单位产品利润〔元〕23该问题可用一句话描述：即在有限资源的情况下，求使利润最大的生产方案方案。【引例2】营养配餐问题假定一个成年人每天需要从食物中获取300cal热量，55g蛋白质，88mg钙。如果一个市场上有四种食品可供选择，它们每kg所含热量和营养成分以及市场价格如下表所示。问如何选择才能满足营养的前提下使购置食物的费用最小？序号食品名称热量〔cal〕蛋白质〔g〕钙〔mg〕价格〔元〕1猪肉100050400202鸡蛋8006020073大米9002030054白菜200105002LP问题的模型＊线性规划：变量满足线性约束的条件下，求使线性目标函数值最优的问题。1、一般形式2、紧缩形式3、矩阵形式4、向量形式其中，，，。线性规划标准模型由线性规划模型的一般形式的讨论可知，线性规划模型有多种不同情况：目标函数可以是最大或最小，约束条件可以有大于等于、小于等于或等于三种情况。为便于线性规划模型的求解，可将线性规划模型的一般形式统一转化为标准形式，这里规定线性规划标准模型的条件：目标函数最小化、约束条件为等式、决策变量均非负、右端项非负。线性规划标准模型的一般表达式：化一般型为标准型：→≤→左边+松弛变量；≥→左边-剩余变量变量→；变量无限制→令→等式两边同乘以〔-1〕.§2图解法线性规划几何解的有关概念考虑线性规划模型一般形式：可行解：凡满足约束条件和非负条件的决策变量的取值称为线性规划可行解。可行域：所有可行解的集合称为线性规划的可行域。最优解：使目标函数到达最优值的可行解称为线性规划的最优解。图解法根本步骤在明确线性规划可行解、可行域和最优解的根底上，介绍线性规划的图解法。对于两个或三个变量的线性规划问题，可以通过平面图或立体图进行求解，是线性规划问题解的几何表示。图解法的优点简单、直观，有助于理解线性规划问题求解的根本原理。它的局限性在于只能对两个或三个变量的线性规划问题求解。图解法的根本步骤可以概括如下：〔1〕建立平面〔空间〕直角坐标系。取决策变量为坐标向量，标出坐标原点、坐标轴指向及单位长度。〔2〕确定线性规划解可行域。根据非负条件和约束条件画出解的可行域。只有在第一象限的点才满足线性规划非负条件，将以不等式表示的每个约束条件化为等式，在坐标系第一象限作出约束直线，每条约束直线将第一象限划分为两个半平面，通过判断确定不等式所决定的半平面。所有约束直线可能形成或不能形成相交区域，假设能形成相交区域，相交区域任意点所表示解称为此线性规划可行解，这些符合约束限制的点集合，称为可行集或可行域。转到第三步；否那么该线性规划问题无可行解。〔3〕绘制目标函数等值线〔面〕。目标函数等值线〔面〕就是目标函数取值相同点的集合，通常是一条直线〔二维平面〕或一个平面〔三维空间〕。〔4〕寻找线性规划最优解。对于目标函数的任意等值线〔面〕，确定该等值线〔面〕平移后值增加的方向，平移此目标函数的等值线〔面〕，使其到达既与可行域相交又不可能使目标函数值再增加的位置。相交位置存在三种情况：假设有唯一交点时，目标函数等值线〔面〕与可行域相切，切点坐标就是线性规划的最优解；假设相交于多个点，称线性规划有无穷多最优解；假设相交于无穷远处，此时无有限最优解。【例】运用图解法求解线性规划问题三、线性规划问题几何解的讨论利用图解法可以讨论线性规划解的四种情况。〔1〕唯一最优解。线性规划唯一最优解是指该规划问题有且仅有一个既在可行域内、又使目标值到达最优的解。〔2〕无穷多最优解。线性规划问题的无穷多解是指，该规划问题有无穷多个既在可行域内、又使目标值到达最优的解。如果例的目标函数变为，目标函数的等值线正好和约束条件相平行。在目标函数向右上方平移的过程中，与可行域相切于上的所有点，此时，该线性规划问题存在无穷多最优解。〔3〕无有限最优解〔无界解〕。线性规划问题的无有限最优解是指最大化问题中的目标函数值可以无限增大，或最小化问题中的目标函数值可以无限减少。考虑下述线性规划模型：利用图解法进行求解时，可行域是一个非封闭的无界区域，的取值可以无限增大，同时，目标函数值也可以增大到无穷，如以下图所示。在这种情况下，称线性规划无有限最优解或无界解。原因在于建立线性规划模型时，遗漏了某种必要资源的约束。454542x2x1+2x2=4x1-2x2=5x1ox2x1利用图解法进行求解时，在第一象限内，所有约束条件不能形成一个相交平面区域，如上图。线性规划问题不存在可行域，也就是说，问题没有可行解。其原因是线性规划模型自身的错误，约束条件之间自相矛盾，应根据实际情况进行调整。针对线性规划几何解还有一些重要的性质，这里不加证明表达如下：〔1〕线性规划几何解存在四种情况：唯一最优解、无穷多最优解、无有限最优解、无可行解。〔2〕假设线性规划可行域非空，那么可行域必定是一个凸集。〔3〕假设线性规划可行域非空，那么凸集至多有有限个极点。〔4〕假设线性规划优解存在，那么最优解或最优解之一肯定能够在可行域〔凸集〕的某个极点找到。通过上述的讨论，求线性规划问题最优解，可以转化为在其可行域有限个极点上进行搜索的方法。根本思路是，先找出凸集任意一个极点，计算极点的目标函数值。比拟与之相邻的目标函数值是否比该极点的目标函数值更优，如果为否，那么该极点就是最优解，如果为是，转到比该点目标函数值更优的另一极点。重复上述过程，直到找出使目标函数值到达最忧的极点为止。可行域可行域空集无界有界解无可行解唯一最优解多重最优解解无界解作业：1、讨论变化对最优解的影响。2、P51.3§3单纯形法〔SimplexMethod丹茨格1947丹麦〕一、预备知识1、基考虑线性规划标准模型其中：系数矩阵为阶矩阵。假设的秩为，为中的任意阶子矩阵，且行列式，那么称为线性规划模型式的一个基。为中其余阶子矩阵，称为线性规划模型式的一个非基矩阵。不失一般性，假设：，那么为基向量。与基向量相对应的变量称为基变量，与基的列向量相对应；其它个变量称为非基变量，与非基矩阵的列向量相对应。基于上述讨论，假设为线性规划的一个基，为线性规划的一个非基，那么可以表示为：，相应地、可以分为：。线性规划标准模型可以表示为：如非基变量取定值，由于，那么有唯一的值与之对应：。特别地，当时，。关于此类特别解，可以得到线性规划根本解、根本可行解、可行基的概念。？线性规划问题基的数量等于约束不等式的数量〔不含非负约束〕2、根本解、根本可行解、可行基。设为线性规划的一个基，令非基变量，可求得。此时，有，称是线性规划与基对应的一个根本解。如果，称是线性规划与基对应的一个根本可行解，相对应的基称为可行基。【例1】求引例1线性规划问题的所有根本解、根本可行解。〔0，0，8，4，3〕；〔4，0，4，0，3〕；〔4，2，0，0，1〕；〔2，3，0，2，0〕〔0，3，2，4，0〕；〔4，3，-2，0，0〕；〔8，0，0，-4，3〕；〔0，4，0，4，-1〕二单纯形法的根本思路及原理1、如何寻找初始根本可行解？2、最优性检验：判断初始根本可行解是否是最优解？检验数：目标函数中处理成只含有非基变量，那么目标函数中基变量的系数为0.记目标函数中变量的系数为。判定定理：所有检验数大于等于0，那么这个根本可行解是最优解。设令代入中的基变量，有3、基变化〔1〕入基变量确实定：选择检验数为负且绝对值较大的非基变量入基。〔2〕出基变量确实定：把已确定的入基变量在各约束方程中的正的系数除其所在约束方程常数项的值，把其中比值最小的约束方程中的原基变量确定为出基变量。迭代次数-2-3000比值001210088/2=40100104-00100133/1=3检验数〔〕-2-30000迭代次数-2-3000比值101010-222/1=201001044/1=4-3010013-检验数〔〕-20003-9迭代次数-2-3000比值2-21010-22-000-11222/2=1-30100133/1=3检验数〔〕0020-1-13迭代次数-2-3000比值3-2100104-000-0.50.511--3010.5-0.502-检验数〔〕001.50.51-14注：假设两个非基变量检验数均为最小的负值且相等，选择下标最小的非基变量入基注：假设两个出基变量对应的相同的最小比值，选择下标最小的基变量出基。出基变量确实定：令，，那么→，所以最大只能取3.三、人工变量的引入【例2】解：化为标准型显然不是典那么形式现引入辅助问题迭代次数0000011比值01121-101033/1=312-130-10144/3检验数-3-1-411007迭代次数0000011比值111/37/30-11/31-1/35/35/702/3-1/310-1/301/34/3-检验数-1/3-7/301-1/304/35/3迭代次数0000011比值201/710-3/71/73/7-1/75/7-05/701-1/7-2/71/72/711/7-检验数00000110迭代次数23400比值031/710-3/71/75/7545/701-1/7-2/711/711/5检验数-9/70013/73/759/7迭代次数23400比值1301-0.2-0.40.20.4-2101.4-0.2-0.42.2-检验数000.61.60.25.6四、几种特殊情况1、无可行解【例3】当引入人工变量时，如假设最优解中人工变量大于0，那么无可行解。2、无界解【例4】如假设存在一个大于0的检验数，并且该列的系数向量的每个元素都小于或者等于零，那么此线性规划问题是无界的。3、无穷多最优解【例5】〔8〕如假设求得的最优解中存在非基变量的检验数为零，那么多重解。作业：p51〔4〕§4运输问题〔TheTransportationProblem〕在经济建设中，经常会遇见大宗物资调拨中的运输问题。例如煤炭、钢材、木材、粮食等物资，在全国有假设干个生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运送至各消费点，而使总运费最小。根本模型数学描述：假设有m个产地，可以供给某种物资，用表示，有n个销地，用表示，产地的产量和销地的销售量分别为和，从至单位运价为。应用举例销地产地产量362470533480175250销量40307060200产销平衡的运输模型的线性规划模型产销不平衡的运输问题例：销地、、需求量依次为3000、1000、2000吨，产地、产量为4000、1500吨。由于需求大于供给，决定需求量可减少吨，区全部满足，需求量不少于1700吨，试求运费最小的分配方案。销地产地产量1.651.701.7540001.601.651.701500销量300010002000销地产地产量1.65M1.701.75M40001.60M1.651.70M1500M0MM0500销量2800200100017003006000表上作业法运输问题变量多，运算量大；必须化为产销平衡问题。表上作业法的步骤：①找出初始根本可行解；②求各非基变量的检验数；③确定入基和出基变量；④重复②、③直至得到最优解。确定初始根本可行解〔1〕西北角法销地产地产量40307007010805050销量40307060200〔2〕最小元素法销地产地产量70703005080401050销量40307060200最优解的判别〔1〕闭回路法在已经给出的调运方案的运输表上，从一个代表非基变量的空格出发，沿水平或垂直方向前进，只要碰到代表基变量的填入数字才能向左或向右转90度〔当然也可以不改变方向继续前进〕，这样继续下去，直到回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的毕回路。例如，增加1t，运输费用增加5元，就得减少1t，运输费用减少3元，为了产量平衡，就得增加1t，运输费用增加6元，为了销量平衡，就得减少1t，运输费用减小3元，所以检验数为5.非基变量闭回路检验数→→→→-4→→→→-3→→→→5→→→→→3→→→→6→→→→4我们把基数顶点运价之和减去偶数顶点运价之和即可得到非基变量的检验数。〔2〕位势法我们对运输表上的每一行赋予一个数值，对每一列赋予一个数值，它们的数值是由基变量的检验数所决定，那么非基变量的检验数为销地产地产量③⑥-4-305③③④-3364②-5销量36673.改良运输方案的方法：闭回路调整法首先选择负值最小的检验数，以它所对应的非基变量作为入基变量，并做一闭回路。销地产地产量4003070300704010805050销量40307060200求得调运方案，=30，即闭回路上偶数顶点的运量最小值，然后基数顶点加上这个值，偶数顶点减去这个值，即可得到调整后的运输方案。销地产地产量③4②101③③④1-164②-1销量3223存在负的检验数，仍需调整。销地产地产量403070304010805050销量40307060200=40，即闭回路上偶数顶点运量最小值，然后基数顶点加上这个值，偶数顶点减去这个值，即可得到调整后的运输方案。仍利用位势法求非基变量检验数。销地产地产量14②102③③④1①64②-1销量2223总运费为：2*70+3*30+3*0+4*50+2*10+1*40=490元，假设存在多个最优解即是存在非基变量的检验数为0.§4线性规划问题建模套材下料问题有10米长的钢管假设干，现在需要2、3、5长的钢管各100根，问如何建立模型？人力资源分配问题某医院昼夜24h各时段内需要的护士数量为：2：00~6：0010人；6：00~10：0015人；10：00~14：0025人；14：00~18：0020人；18：00~22：0018人；22：00~2：0012人。护士分别于2点、6点、10点、18点、22点分6批上班，并且连续工作8小时。试确定：该医院至少应设置多少名护士，才能满足值班需要?假设医院可以聘任合同工护士，上班时间同正式工时间，假设正式工报酬为10元/h，合同工为15元/h，问医院是否应聘用合同工护士及聘用多少？生产方案问题某机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，每种产品均需要A、B两道加工工序。设该厂有两种规格的设备能完成工序A，它们以A1和A2表示。有三种规格的设备能完成工序B，它们以B1、B2、B3表示。产品Ⅰ可在工序A和B的任何规格的设备上加工，产品Ⅱ可在工序A的任何一种规格的设备上加工，但完成工序B时，只能在设备B1上加工。产品Ⅲ只能在设备A2和B2上加工。在各种设备上加工的单位公示、各种设备的有效台时以及满负荷操作时设备的费用如下表。另外原材料的价格分别为0.25元件、0.35元/件，0.50元/件。销售价格分别为1.25、2.00、2.80元/件。要求制定最优的产品加工方案，使该厂利润最大？设备单位产品工时设备有效台时满负荷设备费用ⅠⅡⅢ2791210000321B1684000250B24117000783B374000200设产品表示产品i在工序j的设备k上加工的数量。；；；；；；；；4配料问题某工厂要用三种原料1，2，3混合调配出三种不同规格的甲乙丙三种产品，产品规格要求、产品单价、每天能供给的原材料的数量以及原材料价格如表所示。应如何安排生产？产品规格要求单价〔元/kg〕甲原材料1不少于50%，原材料2不超过25%50乙原材料1不少于25%，原材料2不超过50%35丙不限25原材料每天最多供给量/kg单价〔元/kg〕110065210025360355、投资问题某部门现有资金200万元，今后五年内考虑给以下工程投资：A:从第一年至第五年每年年初都投资，当年末收回本利110%；B:从第一年至第四年每年年初都可以投资，次年末收回本利125%，但规定每年最大投资额不能超过30万元；C:第三年年初需要投资，到第五年末能收回本利140%，但规定最大投资额不能超过80万元；D:到第二年初需要投资，到第五年末能收回本利155%，但规定最大投资额不能超过100万元。据测定每次投资1万元的风险指数如表4-10所示：工程风险指数〔每次投资1万元〕工程风险指数〔每次投资1万元〕A1C4B3D5.5(1)第5年末拥有资本最多？〔2〕使第5年末拥有资金本利在330万元的根底上总的风险系数最小？第三章动态规划〔DP〕1、教学目标：通过本章的学习，理解动态规划的根本概念，会用动态规划的方法建立多阶段决策问题的数学模型；了解动态规划方法的根本解法，会用动态规划的方法解决实际中的最短路问题、资源分配问题、生产方案等问题。2、教学要求：知识要点能力要求核心概念理解以下根本概念状态变量，决策变量，策略，状态转移方程，指标函数和最优值函数动态规划的根本方程动态规划的最优化原理数学模型(1)理解动态规划模型建立过程(2)了解动态规划的根本解法(3)会用动态规划的方法解决实际中的多阶段决策问题动态规划：在求解多阶段决策过程最优方案时，需要把多阶段决策问题转变为一系列相互联系的但阶段决策问题，然后逐个加以解决。在多阶段决策问题中，各个阶段所采取的决策，一般来说与时间或者空间是由关系的，决策依赖于当前状态，又引起状态的转移，一个决策序列就是在变化中的状态中产生的，故有动态的含义。动态规划可以解决哪些问题？最短路径问题装载问题：例如有一部货车沿着公路给四个零售店卸下一定数量货物，现有每个零售店出售货物的利润，问应如何分配，才能使总利润最大？生产与存贮问题：例如有每一期的需求量，现应如何安排生产和库存？资源分配问题§1动态规划的根本思想和最短路问题【引例】最短路线问题。某人要从城市A到城市E旅行，途中经过三个中间停留站，且每个中间停留站有几个不同的城市可供选择，选择不同的中间站旅行的距离是不同的，两点之间的连线上的数字表示两点间的距离，如下图。试求一条从A到E的旅行线路，使总距离最短。如下图的线路网络，求A到E的最短线路问题是动态规划中一个较为直观的典型例子。由图可知，从A点到E点可分为4个阶段：。在第一阶段，A为起点，终点有B1、B2两个，因而这时走的路线有两个选择：一是选择B1；一是选择B2。假设选择B1的决策，那么B1就是第一阶段决策之下的结果。它既是第一阶段路线的终点，又是第二阶段路线的起点。在第二个阶段，再从B1点出发，对应于B1点就有一个可供选择的终点集合{C1，C2，C3}；假设选择由B1走到C1为第二阶段的决策，那么C1就是第二阶段的终点，同时又是第三阶段的起点。同理递推下去，可看到：各个阶段决策不同，途径的城市路线就不同。很明显，当某阶段的起点给定时，它直接影响着后面各阶段的行进路线和整个路线的长度，而后面各阶段的路线的开展不受这点以前各阶段路线的影响。故此问题的要求是：在各个阶段选择一个恰当的决策，使由这些决策组成的一个决策序列所决定的一条路线，其总的路程最短。如何解决这个问题呢？最直接的方法就是穷举法，即把由A到E的所有可能路线的距离都算出来，然后比拟找出距离最短的路线。这样，从A到E的4个阶段中，一共有条不同的路线，比拟这12条不同路线的距离，最短距离的路线为：相应的最短值为13。显然，当路线数不多时这种方法是有效的，但当阶段数增加，且各阶段的不同选择数也很多时，这种解法的计算量将大大增加，甚至在计算机上也无法实现。那么对该问题是否存在更好的计算方法呢？答案是肯定的，这就是本章所讨论的动态规划法。最短路的最优化原理：从最短路上的每一点到终点的局部道路，也一定是从该点到终点的最短路。根本概念1．阶段把所给问题的过程，恰当地分为假设干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量，常用k表示。阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程转化为多阶段决策的过程，如引例中，可将问题分为4个阶段来求解，k=1、2、3、4。2．状态状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。在引例中，状态就是某阶段的出发位置。它既是该阶段某支路的起点，又是下一阶段某支路的终点。通常一个阶段有假设干个状态，第一阶段状态为，第二阶段状态为，一般第k阶段的状态就是第k阶段所有始点的集合。描述过程状态的变量称为状态变量。它可用一个数、一向量来表示，常用表示第k阶段的状态变量。如在引例中第三阶段有两个状态，我们记。动态规划的状态应具有下面的性质：如果某阶段状态给定后，那么在这阶段以后过程的开展不受这阶段以前各阶段状态的影响。换句话说，过程的过去历史只能通过当前的状态去影响它未来的开展，当前的状态是以往历史的一个总结，这个性质称为无后效性。3．决策当过程处于某一阶段的某个状态时，可以作出不同的选择，从而确定下一阶段的状态，这种选择称为决策。描述决策的变量，称为决策变量，它可用一个数或向量来描述。常用表示第k阶段当状态处于时的决策变量。它是状态变量的函数。如在引例第二阶段中，假设选择的点为D1，那么D1是状态C1在决策作用下的一个新状态，记。4．策略策略是一个按顺序排列的决策组成的集合，由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程〔或k子过程〕。由每段的决策按顺序排列组成的决策函数序列{}称为k子过程策略，简称子策略，记为，即当k=n时，此决策函数序列称为全过程的一个策略，简称策略，记为。即5．状态转移方程状态转移方程是确定过程由一个状态到另一个状态的演变过程。假设给定第k+1阶段状态变量的值，如果该段的决策变量确定后，第k阶段的状态变量的值就完全确定。这种确定的对应关系记为：上式描述了由k+1阶段到k阶段的状态转移规律，称为状态转移方程。称为状态转移函数。6．指标函数和最优值函数用来衡量所实现过程优劣的一种数量指标，称为指标函数。指标函数的最优值，称为最优值函数，记为，它表示从第k阶段的状态开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。在不同问题中，指标函数的含义是不同的，它可能是距离、利润、本钱等。动态规划的最优化原理下面结合解决最短路线问题来介绍动态规划方法的根本思想和最优化原理。最短路线有一个重要特性：如果由起点A经过点P和点H而到达终点E是一条最短路线，那么由点P出发经过点H到达终点E的这条子路线，对于从点P出发到达终点E的所有可能选择的不同路线来说，必定也是最短路线。例如，在最短路线问题中，假设找到了是由A到E的最短路线，那么应该是由C2出发到E的所有可能路线的最短路线，这点读者不难验证。根据最短路线这一特性，寻找最短路线的方法，就是从最后一段开始，用由后向前逐步递推的方法，求出各点到E的最短路线，最后求得由A到E的最短路线，所以动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。下面按照动态规划的方法，将引例从最后一段开始计算，然后逐步推移至A点。当k=1时，由D1到终点E只有一条路线，故，同理。当k=2时，出发点有C1、C2、C3和C4四个，假设从C1出发，有两个选择：eq\o\ac(○,1)至D1；eq\o\ac(○,2)至D2，那么

其相应的决策为，这说明由C1至终点E的最短距离为8，最短路线为

同理，从C2、C3和C4出发，有其相应的决策为其相应的决策为其相应的决策为类似地，可算得当k=3时，有：当k=4时，出发点只有一个A点，那么且。于是得到从起点A到终点E的最短距离为13。因而最短路线为从上面的计算过程中可以看出，在求解的各个阶段，我们利用了k阶段与k+1阶段之间的递推关系：一般情况，k阶段与k+1阶段的递推关系式可写为式5-SEQ式5-\*ARABIC1这种递推关系称为动态规划的根本方程，后一个等式称为边界条件。现在把动态规划的根本思想总结如下：1〕动态规划方法的关键在于正确写出根本的递推关系式和恰当的边界条件。2〕在多阶段决策过程中，动态规划方法是既把当前一个阶段和未来各阶段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。3〕在求整个问题的最优策略时，由于初始状态是的，而每个阶段的决策都是该阶段状态的函数。故最优策略所经过的各阶段状态便可逐次变换得到，从而确定了最优路线。动态规划方法是基于贝尔曼等人提出的最优化原理，这个最优化原理指出：“作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简而言之，一个最优策略的子策略总是最优的。引例正是根据这一原理求解的。利用这一原理，可以把多阶段决策问题的求解过程表示成一个连续的递推过程，由后向前逐步计算。在求解时，前面的各状态与决策，对后面的子过程来说，只相当于初始条件，并不影响后面子过程的最优决策。§2动态规划的应用一资源分配问题例1：某公司拟将某种高效率的5台设备，分配给所属的甲、乙、丙三个工厂，各工厂假设获得这种设备后，可以为公司提供的盈利如表5-1所示。表5-SEQ表5-\*ARABIC1设备分配赢利表设备台数工厂012345甲乙丙00035479891111111211121211问，这5台设备如何分配给各工厂，才能使公司得到最大的赢利。解：将问题按工厂分为三个阶段，甲、乙、丙三个工厂分别编号为1，2，3。设阶段变量；状态变量表示为分配给第1个工厂至第k个工厂的设备台数；决策变量表示分配给第k个工厂的设备台数；那么状态转移方程为表示为台设备分配到第k个工厂所得赢利值；表示为台设备分配给第1个工厂至第k个工厂所得到的最大赢利值。因而可写出递推关系式为下面从第一个阶段开始向前计算有：第一阶段〔k=1〕：设将台设备〔〕全局部配给工厂甲时，那么最大赢利值为因为这时只有一个工厂，有多少台设备就全局部配给工厂甲，故它的赢利值就是该段的最大赢利值，其数值计算结果如表所示：k=1时的计算结果x1s10123450123450379111203791112012345表中表示使为最大值时的最优决策。第二阶段〔k=2〕：设把台设备〔〕分配给工厂甲和工厂乙时，那么对每个值，有一种最优分配方案，使最大赢利值为因为给乙工厂台，其赢利为，余下的台给甲工厂，那么它的赢利最大值为，现要选择的值，使取最大值，其数值计算结果如表所示。第三阶段〔k=3〕：设把台设备〔〕分配给甲、乙、丙三个工厂时，那么最大赢利值为其中因为给丙工厂台，其赢利为，余下的台分给乙和甲工厂，那么它的赢利最大值为，现要选择的值，使取最大值，它就是所求的赢利最大值，其数值计算结果如表所示。k=2时的计算结果x3s301234501234500+30+70+90+110+125+05+35+75+95+119+09+39+79+911+011+311+712+012+312+00591216180121，222，3k=3时的计算结果x3s301234550+184+168+1211+911+511+0201，2，3然后按计算表格的顺序反推算，可知最优分配方案有四个。二背包问题背包问题的一般提法是：一位旅行者携带背包去登山，他所能承受的背包重量最多为kg，现有n中物品可供选择装入背包，第i种物品的单位重量为kg，其价值为携带量。问旅行者应如何选择携带各种物品的件数，使得总价值最大？背包问题等同于车、船、飞机等工具的最优装载问题。设为i种物品装入的件数，那么背包问题可归结为如下的整数规划模型：下面用动态规划建模求解：阶段k表示将可装入物品按排序，每段装一种物品，共划分为n阶段，即；状态变量表示在第k阶段，背包中允许装入的从第1种物品到第k种物品的总重量；决策变量表示装入第k种物品的件数；状态转移方程为：允许决策集合为：其中。最优指标函数表示在背包中允许装入的第1种到第k种物品总重量不超过kg所获得的最大价值。那么可得到动态规划的递推公式为利用上面这个递推关系式求解出即为所求最大价值。当的取值仅为0或1时，那么模型为0-1背包问题。【例】有一辆最大运货量为10t的货车，用以装载3种货物，每种货物的单位重量和相应单位价值如表所示。问如何装载才使总价值最大？表货物重量价值表货物编号123单位重量/t543单位价值654解设表示第i种货物装载的件数，根据前面的线性规划知识，该问题可表示为如下线性规划模型：我们采用上述的方法建立动态规划模型求解有：当k=1时；其中。如表所示。k=1时计算结果01234567891000000666661200000111112当k=2时其中，计算结果如表所示。k=2时计算结果当k=3时，其中，计算结果如下表所示。k=3时计算结果01231210131213此时，，顺推可得全部策略.三多阶段生产安排问题有某种原材料，可用于两种方式的生产，原料用于生产后，除了产生一定数量外，还可以回收一局部，生产信息为：原材料投入量为x，与分别为第Ⅰ种和第Ⅱ种生产方式的收益函数，为按Ⅰ种生产方式生产时的原料回收率，为按第Ⅱ种方式生产的原料回收率。今有原料吨，方案进行n个阶段的生产，问每个阶段如何分别确定两种生产方式原料的投入量，使得总收益最大？令为资源数量为x，进行k个阶段生产采取最优决策安排时，所得的最大收益。第一阶段将数量原料用于Ⅰ方式，数量用于Ⅱ方式，那么该阶段产生的收益为，回收的原料数量为，如果在以后的k-1个阶段采取最优决策安排生产，最大收益为那么，k=2，3，…,n例：在多阶段生产安排中，设收益函数为。回收率。生产阶段数为初始原料数量为。第一阶段：全部原料投入方式Ⅱ；第二阶段：全部原料投入方式Ⅱ；第三阶段：全部原料投入方式Ⅰ。四、特殊问题仍然将此问题化为三阶段的动态规划问题第一阶段：；第二阶段：；第三阶段：；五、随机采购问题某公司打算在5周内采购一批原料，未来五周的原料价格有三种，如表所示。该部门由于生产需要，必须在五周内采购这批原料，假设第一周价格很高，可以等到第二周；同样的第二周如果对价格不满意，可以等到第三周。类似的未来几周可能选择等待或者购置，但必须保证第五周时采购了该原料。问该采取哪种采购方案，才能使得采购费用最小？价格概率5000.36000.37000.4n为阶段数，为第n周价格，--当第n周价格为时，按最优策略进行采购时所花费的最低费用。〔这里假设前n-1周都没有进行采购〕。假设前四周没有采购，那么第五周必须采购，即下面考虑第四周：用表示第k周等待以后采购的期望值，即在第四周的价格如果为500或600时选择采购，700时选择等待。第三周：即在第三周的价格如果为500时选择采购，否那么选择等待。第二周：第一周：最优的采购策略为：第1，2，3周的市场价格为500时选择采购，否那么等待；第四周时，假设市场价格为500或600时选择采购，否那么等待；假设等到第五周，只能采购。第四章存贮论§1概论一、存贮的定义1、什么东西需要存贮？①原材料、半成品、外购件：保证生产的均衡性和连续行②商品：以便及时销售，满足顾客需要③军备、人才、信息2、存贮：把一些物资储存起来以备将来使用和消费3、库存：直接影响到生产和流动资金的周转。①库存量过少，可能导致供需发生脱节，破坏生产的连续性或因发生缺货，失去销售时机而减少利润。②库存量过多，那么会造成积压，影响流动资金的周转，给国家、集体造成损失。4、存贮论：就是专门研究存贮问题有关理论和方法的一门学科，是运筹学的一个重要分支。他们用定量的方法描述存贮物品供需关系的动态过程和存贮状态，描述存贮状态和费用之间的关系。并确定经济合理的供给策略。从而为人们提供定量的决策和有价值的定性指导。二、存贮系统考虑最广泛的存贮系统，如下图补充补充需求存贮存贮状态：是指某货物随时间推移而发生的盘点数量上的变化。其数量随需求过程而减少，又随补充过程而增加。需求：是系统的输出，他可以表示成多种不同形式。间断式或连续式：顾客对时令商品的需求是间断性的，对日用品的需求是连续的均匀的或不均匀的：如工厂自动生产的流水线对原材料的需求是均匀的，而一个城市对电力的需求是不均匀的；确定的或随机的：如生产活动中对原材料的需求一般是确定的，而销售活动中对商品的需求那么往往是随机的。补充的方式：内部生产和外部订购两种方式。从订货到交货之间有一段滞后时间，简称时滞。多少时间补充一次？每次补充的数量为多少？三、存贮模型的建立存贮模型的建立需抓住三个环节：存贮状态图、费用函数和经济批量公式。存贮状态图：描述存贮状态。它表示某物品随时间推移而发生的盘点数量上的变化。；；：t时刻的存贮量；：0时刻的存贮量；：0~t时刻的累计补充量；：i时刻补充量；：0~t时刻的累计需求量；：t时刻需求速度〔单位时间的需求量〕。在各种具体情况下，由于需求和补充的形式不同，存贮状态图也是各种各样，只有分清补充过程和需求过程两个关键因素，就容易得到符合实际的存贮状态图。2．费用函数研究存贮模型的目的是为了选用最优的存贮策略，使得存贮的总费用最小。费用函数便是将存贮状态图各个参数与费用的关系定量的表示出来。在存贮分析中一般需要考虑以下几种费用。存贮费：指货物被出售或被使用之前与存贮有关的费用。其中包括仓库管理费、存贮设备的保养与维修费用、保险费用等。订货费。包括两项费用。一项为哪一项订购费，如手续费、电信往来、派人员外出采购的差旅费等。一般给出的是每次平均订货费用。另一项为哪一项订货本身的本钱，它与订货数量有关〔可变费用〕。如货物的单价、运输费用等。假设货物的单位本钱为K，订购数量为Q，那么总本钱为：KQ。生产费用：假设货物不是订购而是自行生产，那么自行生产所需的总费用包括：一是生产准备费用〔对应于订购费〕，另一项为哪一项生产本钱〔对应于订货本钱〕，它与产品数量有关。缺货费用：是指存贮不能满足需求而引起的失去销售时机的损失或停工待料的损失，以及不能履行合同而缴纳的罚款等。上述费用是费用函数的主要工程，在制定短期存贮方针时，只考虑这四项费用就足够了。但是在制定长期存贮方针时，还需要考虑折旧费和贴现率等。一旦费用工程确定，就可以根据存贮状态图及有关的统计资料建立相应的费用函数。3.经济批量公式存贮状态图与费用函数确定之后，下一步就是求出使费用最小的订货批量Q和订货点。四、根本符号R—年需求率；n—进货次数；每次进货量Q；I—单位货物年保管费；S—订购费；A—单位货物的年短缺费；C—一年的总存贮费。§2第一类存贮模型模型Ⅰ：不允许缺货，进货能力无限1、根本假设〔1〕缺货费用无穷大；〔2〕当存贮降为0时，可以立即得到补充〔即生产时间或拖后时间很短，可以近似的看成为0〕；〔3〕需求是连续的均匀的，设需求速度R〔单位时间的需求量〕为常数，那么t时间的需求量为Rt；〔4〕每次的订货量不变，订购费不变〔每次生产量不变，装配费用不变〕2、存贮状态图假设在1年内，每隔时间进一次货，每次订货量为Q，共进n次，那么有n=R/Q；=Q/R。t时刻存贮量为I(t)=Q-tR,这样整个周期的存贮量为：，所以一个周期内的平均存贮量为：Q/2。总的订购费用为：一年的总存贮费用为，，，.3灵敏度分析假设某部门为了少占用流动资金，希望存贮量比偏低；或者资金方面不存在问题，主要由于担忧缺货而造成的损失宁愿选择较高的订货量。在这种情况下，所需支付的总费用比最正确订购批量时所需支付的总费用C会增加多少？假设存贮量比多即,那么-0.5-0.2-0.10.10.20.30.5125%2.5%0.6%0.45%1.7%3.5%8.3%25%由于偏离最正确批量所引起的费用增加是相当小的，故最正确批量公式不灵敏。一般的订货量与最正确订购批量略有增减而引起的费用增加不多，因此，可根据具体情况给出比拟符合实际的订购批量。例1：某轧钢厂每月按照方案需角钢3000吨，每吨每月需存贮费5.3元，每次生产所需调整机器设备等供需装配费2500元，该厂每年的生产量是多少？全年应分几批生产？假设该厂每月生产角钢一次，生产批量为3000吨。那么每月的总费用为5.3*3000/2+2500=10450(元/月)全年总费用为：10450*12=125400元/年按照公式计算吨全年生产次数次；两次生产的时间间隔为天；17天的单位存贮费为：5.3*17/30=3(元/吨)；共需费用3*1682/2+2500≈5023元；按照全年生产21.5次计算，全年共需的总费用为5023*21.5=107995元/年例2：假设某工厂需要外购某部件，年需求率为4800件，单价为40元，每次的订购费用为350元，每个部件存贮一年的费用为其价格的25%，又假设每年有250个工作日。该部件需要提前五天订货。不允许缺货，请求出：最优的订购量；再订货点；两次订货的时间间隔；每次订货与存贮的总费用。模型Ⅱ：允许缺货进货能力无限1、根本假设〔1〕允许缺货，缺货后补；〔2〕需求是连续的均匀的，设需求速度R〔单位时间的需求量〕为常数，那么t时间的需求量为Rt；〔3〕每次的订货量不变，订购费不变〔每次生产量不变，装配费用不变〕2.存贮状态图每次进货量为Q，每隔时间进一次货，共进n次货，那么有n=R/Q；=Q/R。仍考虑第一周期：t时刻的存贮量为t时刻的缺货量为所以第一周期内的平均存贮量为：平均缺货量为又=Q/R，，那么年总存贮费用为上式分别对Q和G求偏导可得：,,，，当，与模型Ⅰ一致。例：假设允许缺货，单位缺货费用为16元，其他类似于例1.问：允许缺货和不允许缺货哪个好？§3第二类存贮模型模型Ⅲ：不允许缺货，进货能力有限1、根本假设〔1〕缺货费用无穷大；〔2〕假设进货能力是有限的，即每期的订货量分假设干次进入存贮，直到到达订货量为止，生产速度为P；〔3〕需求是连续的均匀的，设需求速度R〔单位时间的需求量〕为常数，那么t时间的需求量为Rt；〔4〕每次的订货量不变，订购费不变〔每次生产量不变，装配费用不变〕2、存贮状态图每次进货量为Q，每隔时间进一次货，共进n次货，那么有n=R/Q；=Q/R。t时刻的库存量为所以第一周期内的平均存贮量为：从而总存储费为;，，.例。有一个生产和销售图书馆设备的公司，存贮一个书架一年需要花费1000元。年需求量为4900件年生产能力为9800件，每次生产的单位准备费为500元。年工作日250天。；=50；=5,.自行生产与外购哪个好？模型Ⅳ：允许缺货，进货能力有限〔1〕允许缺货，缺货后补；〔2〕需求是连续的均匀的，设需求速度R〔单位时间的需求量〕为常数，那么t时间的需求量为Rt，生产速度为P；〔3〕每次的订货量不变，订购费不变〔每次生产量不变，装配费用不变〕2.存贮状态图，最大存贮量为G，最大缺货量为V，那么；；；；，那么可知在和内的平均存贮量为：每个周期的平均存贮量为每个周期的平均缺货量为一年的总费用可以求得：；,§3报童模型报童每天售出报纸数量是一个随机变量，每天售出d份报纸的概率为q〔d〕，根据以往经验是可知的。报童每售出一份报纸赚k元，如假设报纸未能售出，每份赔h元，问报童每日最好准备多少张报纸。〔1〕供大于求〔Q≥d〕这时因不能售出报纸而承当损失，每份损失为h元。其数学期望值为〔2〕供不应求时〔Q<d〕这时因缺货而造成赚钱时机的损失，每份损失为k元。期望值为.欲使期望损失值最小，需满足：①②从①式推导从②式推导经化简得例1：某商店准备在新年前订购一批挂历销售。每售出一批〔100元〕可获利70元，如假设挂历售不出去，那么每批损失40元。根据以往销售经验，该商店售出挂历的数量如下表所示。销售量012345概率0.050.10.250.350.150.10例2：售出1本可盈利20元，售不出去亏损16元，市场需求近似服从均匀分布，最低需求为550本，最高需求为1100本，问该书店应订购多少？证明：市场价格为p，单位本钱为c，市场需求概率密度函数为f，累计分布函数为F，F(0)=0。商品残值为v〔v<c〕，缺货损失为s。试求最正确订购量。Cha5决策论§1绪论从清晨醒来导夜晚再进入梦乡，没完没了的各种决策充满着我们的大脑。这些决策范围很广，既有日常琐碎的事情，如打什么领带、穿哪件衬衫上班，自己开车还是坐公车；也包括需要认真考虑的中大问题，如是否进行学习深造，接受新工作还是继续现在的职业等等。可以说，决策贯穿于我们日常的生活、学习和工作。美国著名的管理学家西蒙〔1978年诺贝尔经济学奖获得者〕曾经说过这样的一句名言：管理就是决策。号称现代企业管理之父的杜拉克也说：不管管理者做什么，他都是通过决策进行的。杜拉克甚至断言：管理始终是一个决策的过程。决策的含义决策的怪现象决策之前“拍脑门”；决策之中“拍胸脯”，决策之后“拍巴掌”；决策成功“拍大腿”；决策失败“拍屁股”。什么是决策决策是人们生活中最常见的一种综合活动，是为了到达特定的目标，运用科学的理论和方法，分析主客观条件，提出各种不同的备选方案，并从中选取最优方案的过程。决策的步骤：Step1：确定决策目标没有目标的决策是盲目的，是不可能成功的。制定准确的决策过程，是成功决策的第一步。例：有一天Alice来到一条岔道口，看到一只猫趴在树上。“我应该走哪条路？”她问道。它以一个问题作答：“你想到哪里去？”“我不知道，”Alice答复。“那么，”那只猫说，“哪条路都无关紧要。”Step2：拟定各种备选方案Step3：选取最优方案假定你是个女性，决定要结婚，你身边社交圈里有100个适宜的单身男子都有意追求你，你的任务就是，从他们当中挑选一个最好的作为结婚对象，但要从这100个里面选出最好的并非易事，你该怎么做才能争取到这个结果？条件如下：每个人只能约会一次，而且只能当场决定选择还是放弃，不能把他们冷冻起来作为后备，一旦你选择了其中一个，你就没有时机再约会别人了。决策的根本概念例：〔萨维奇〕如果方案用六个鸡蛋做鸡蛋煎饼，已向碗里打了五个好鸡蛋，准备打第六个鸡蛋时，有三种方案可供选择：即方案A1：将第六个鸡蛋打入成有五个好蛋的碗里，简称“打入”；方案A2：丢弃第六个鸡蛋，简称“丢弃”；方案A3：将第六个鸡蛋单独打入另一个碗里以检查好坏，简称“单打”；由于第六个鸡蛋不知是好是坏，每种方案均面临者两个自然状态，即：S1：第六个鸡蛋是好鸡蛋；S2：第六个鸡蛋是坏鸡蛋。把各种方案在不同自然状态下所产生的效果称为损益值，用aij表示。pj表示第j个自然状态出现的概率。那么可得下面的决策矩阵。状态方案S1S2p1p2A1六个鸡蛋煎饼〔a11〕无鸡蛋煎饼〔a12〕A2五个鸡蛋煎饼，浪费一个鸡蛋〔a21〕五个鸡蛋煎饼〔a22〕A3六个鸡蛋煎饼，多洗一个碗〔a31〕五个鸡蛋煎饼〔a32〕决策的要素:明确的决策目标；至少存在一个自然状态；至少存在两个或两个以上的备选方案；不同方案在各自然条件下的损益值可以计算出来。§2确定型决策1、根本概念：决策的未来状态是一个完全确定的情况，即提供给决策者的每一个方案都有一个确定的结果。Case1：买复印机，多个厂家和品牌的机器进行比拟，功能、品质、效劳、价格等因素均满足要求，选择最低价的厂商。Case2：田忌赛马：固定齐威王的策略，田忌的选择。例题：A公司与B公司的待遇，除了以下两项略有不同外，其余方面是完全相同的。A：1〕半年工资50万元；2〕工资每半年增加5万元；B：1〕年工资100万元，2〕工资每年增加20万元。现在你想去待遇比拟邮购的公司就知，你会选择哪个公司？例题：在一个企业中，生产某种产品的固定本钱是86000元，售价为65元/台。每台的材料费为20元，工资为7元，其他变动本钱为4元。请根据以上材料答复下面问题。该企业不亏本的数量应是多少？假设企业决定今年必须盈利25000元，那么企业今年至少需要生产多少台？如企业的生产能力为6500台，试问：产销平衡时，企业生产这一产品的最大利润是多少？§3不确定型决策不确定型决策的根本概念〔1〕不确定型决策：自然状态不止一个，自然状态发生的概率可以无法估计出来。〔2〕不确定型决策与风险型决策的区别：①前者自然状态发生的无法估计，后者可以估计出来。②前者人为制定原那么，带有某种程度的主观随意性，后者从合理的假设出发，有严格的推理和论证。〔3〕不确定型决策者的四种态度：乐观、悲观、折衷、尽可能防止懊悔〔4〕不确定决策的方法例题：某地方书店希望订购最新出版的某种图书。根据以往经验，销售量可能是50、100、150或200本。假定每本书的订购价为4元，销售价为6元，剩书的处理价为每本2元。首先建立收益矩阵。方案状态S1S2S3S4A1100100100100A20200200200A3-100100300300A4-2000200400乐观法：收益大中取大，损失小中取小。〔对有利的情况估计比拟有信息的决策者〕悲观法：收益小中取大，损失大中取小。〔比拟保守稳妥，并害怕承当较大风险〕折中法：对形势判断位于乐观和悲观之间。乐观系数：。最小遗憾法：懊悔值〔遗憾值〕大中取小。平均法：假设各自然状态发生的概率相等。§4风险型决策看下面几句话：▽常言道：商场如战场。▽克劳塞维茨〔1780~1830〕：普鲁士军事理论家，西方近代军事理论奠基者，参加过欧洲反法联盟对拿破仑的战争。“战争是一种概念性和偶然性的活动，…，在战中中不冒险将一事无成，在某些场合，最大的冒险，倒表现了最大的智慧。”▽日本经营学者大桥墩武夫曾告诫人们：“千万不要全部条件不齐备就不做决策，通常，在条件不明确的情况下，事态依然每时每刻的开展，这就是现实。倘假设等到全部的条件都明确就丧失良机了。如果给出了全部的条件，那么计算机就能为我们找到答案了。”▽日本经济学家池本正纯说：“所谓大胆的冒险并不是盲目蛮干，而是以谨慎周密的判断为根底，比别人抢得获得利益的时机。”答复以下问题：A、何谓风险？风险是指在某一特定环境下，在某一特定时间段内，某种损失发生的可能性。风险是由风险因素、风险事故和风险损失组成。换句话来说，是指在一个特定时间段内，人们所期望到达的目标与实际出现的结果之间的距离称之为风险。Case：比方某人在一个大雪天，在下班的顶峰期，骑着他的没闸没铃的自行车从家里出发，准备去超市买皮鞋。不幸在半道出现了交通事故。这里让我们分析一下：大雪天、车流顶峰期、没闸没铃的自行车属于风险因素；交通事故属于风险事故；当事人的死亡或残疾是本次风险事故所导致的风险损失。B、决策者对待风险的态度有哪些？a、厌恶风险：对于损失的反响比拟敏感而对收益的反响比拟缓慢，不求利大，逃避风险，谨小慎微，厌恶风险的保守主义者。b、追求风险：对于利益的反响较为敏感而对损失的反响比拟缓慢，追求利大，敢冒风险，泼辣大胆，追求风险的进攻式决策者。c、中立稳健：循规蹈矩、中立稳妥的决策者。课堂讨论：如果我有500万，我会干什么？1、风险型决策：决策者根据不同自然状态下，事态发生的概率进行决策。2、风险型决策的五个必备条件：①明确的目标；②两个或两个以上的备选方案；③不以决策者的主观意志为转移的两种或两种以上的自然状态；④存在着决策者可以主观确定或者根据有关资料计算出来的各种自然状态出现的主观概率。⑤存在着可根据决策方案在不同自然状态下计算出来的损益值。3、决策方法〔1〕期望值法例题：某商店销售某种食品，根据市场预测，该食品需求量的概率分布为：需求量100150200250300概率0.20.250.30.150.1设该产品每包本钱为25元，售价为49元，如果当天销售不出去，只能以处理价每包15元销售。商店可采取的进货量与需求状态相同。试用期望值法确定每天的最优订货量。〔2〕最大可能法使用情况：各种自然状态中其中某一状态的概率明显高于其他状态所出现的概率，而期望值又相差不大的情况。例：某一生产跑步机的企业看到市场上流行运动减肥，很多女士喜欢呆在家中在跑步机上运动减肥，拟在原有根底上增加跑步机的生产。现有两种方案：一是增加一套设备大规模生产，二是在原有根底上小批量试产。自然状态大概有两种：一种是销路好，二是销路差，概率分别为0.3、0、7.决策矩阵如下：概率方案0.30.7期望值)一200-5025二501022案例讨论：有一风险投资时机，成功和失败的概率分别为0.5，你每投1元，假设成功可以得到1.6元的利润。假设失败，失去本金。投资次数和投资额不限，你为了不把钱输光，采取了如下策略：总是拿你所持有钱的一半去投资〔假设钱是无限可分的，你不会破产〕，你开始的资金是100万元。①在如此吸引人的投资环境中运用此资本保护策略的结果如何？②具体来说，平均说来你是赢还是输？如果你投资了10000次，平均来说，你最后有多少钱？③你有多大的可能性在最后拥有的钱不少于开始的100万元？观点一：设投资者初始资金为a元，经依次投资后的资本有两种可能：P1：假设成功，资金为a1=a+1.6〔0.5a〕=1.8aP2：假设失败，资金为a1=0.5a一期投资后的期望值为E1=0.5(1.8a+0.5a)=1.15a可以证明第二次投资后的期望值为，依次类推，投资10000次的资本期望值为。观点二：由于投资的胜率为0.5，在10000次投资中赢和输的概率都很可能接近5000.由于在赢时，资本值由a变为1.8a，在输时资本值由a变为0.5a。假设总投资次数为N，胜负次数各半，投资N次后的资本额变为假设N=360，那么。只剩下不到1分。设N次投资中有n次赢，最后有我们首先考虑要使投资者不输，需要赢的次数。为了理解此概率有多小，我们可以假设全世界100亿人，每人10万根头发，合计。如果在每个人的头上选一根头发，刻上记号，然后把所有人的头发剔下来，放在太平洋里均匀搅拌，然后让一个人随便抓一根，抓到的头发正常时预先做好记号的那根的概率就是投资能保本或者盈利的概率。〔3〕决策树法有些决策问题，决策后有新情况出现，并需要进行新的决策，当进行决策后又产生新情况，接着又需要进行新的决策。这样决策、情况、决策、…一个序列，这就是序列决策。描述序列决策的有力工具是决策树。决策树是按一定的决策顺序画出的树状图帮助决策者进行序列决策。它由决策节点、方案枝、事件节点、概率枝和结果节点按一定关系联结而构成的树形图。〔l〕决策点，一般用方形节点□表示。从这类节点引出的弧表示不同决策方案；〔2〕状态点，一般用圆形节点○表示，从这类节点引出的弧表示不同的状态。在弧旁写上的数字表示对应状态出现的概率；〔3〕结果点，一般用三角形节点△表示，位于树的末梢处，并在这类节点旁注明各种结果的损益值。〔4〕∥表示修剪，比拟各行动方案的收益期望值的大小，确定最优方案分支，其他分支删掉。其体做法是：首先，从左向右绘制决策树；其次，从树的末梢开始，计算每个状态点的期望值，然后将其中最大值标在相应决策点旁；最后，决策时，根据期望收益最大原那么从后向前进行“剪技”，直到最开始的决策点，从而得到一个多阶段决策构成完整的决策方案。下面通过例子说明决策树的应用。【例】某销售公司拟代理一企业新产品销售，但为了得到代理合同必须参加投标，投标的准备费用为4万元，中标的可能性是60%。假设中标有两种销售方案，第一种方案成功的概率80%，费用30万元；方案成功的概率60%，费用为15万元。如果中标，销售达不到业绩标准即失败那么需要赔偿10万元，成功可得到50万元报酬。问题是要决策：是否参加投标，假设中标采用哪种方案。解：画决策树，如图9-4所示。计算各点期望值。比拟大小选择，删减分支。状态点4值：500000×0.8＋〔-100000〕×0.2=380000元状态点5值：500000×0.6＋〔-100000〕×0.4=260000元决策点3值：比拟所有分支取最大值max｛38000-300000，260000-150000｝=110000元，应选择方案2，删去方案1分支。状态点2值：110000×0.6＋0×0.4=66000决策点1值：比拟所有分支取最大值max｛66000-40000，0｝=26000元，应选择投标，删去不投标分支。本问题的最优决策方案：参加投标，假设中标选择方案2。风险型决策的灵敏度分析1、灵敏度分析的意义：研究概率值的变化对最优方案的选择究竟存在多大影响的分析。2、转折概率：概率变化引起方案变化的临界点的概率。3、两状态两方案的灵敏度分析例：某工程队签署一项开赴远地施工的合同，由于出发之前有一段必要的准备时间，故眼下就要面临着决定是否下月开工的问题，如果开工后天气好，那么当月可顺利完工，获利润12.5万元；如果开工后天气坏，那么将造成各种损失计4.8万元。假设下月不开工，那么就地待命，那么天气好可以承包一些零星工程，利润值估计可达6.5万元；天气坏那么付出损失费1.2万元。根据气象预测，下月天气好的概率为0.65，天气坏的概率为0.35.试做敏感性分析。4、三状态三方案的敏感性分析例题：某过滤设备由上中下三层组成：每层有一个过滤筛，是易损件。在修理时测不出是哪层坏了，只有换上后才恩那个试出是不是这层坏了，各层的修理费用不同。过滤筛本身不贵，主要是费工。换上层筛需要20元，换中层筛需要拆开上中两层，共费35元；换下层筛需要大拆大卸，需要65元。现有三种方案：一拆到底，直至下层，全部换新筛；先换上中两层，假设不行再换下层；一层一层换下去。根据大量统计资料，这种设备上中下三层出现故障的概率为0.35、0、30、0、35.Cha6对策论在日常生活中，我们经常可以看到一些具有相互之间竞争性质的行为，如下棋、打牌、游戏、体育比赛等。还比方战争中的双方，都力争选择对自己最有利的策略，千方百计取得胜利。政治方面，国际间的谈判，各种政治团体之间的斗争，等无一不具有竞争的性质。在经济活动中，各企业之间的经济谈判，产量、价格的竞争，等等。因此，我们可以这么定义对策论，是研究在多人决策时，策略之间存在相互依存关系的一门学科。为了到达各自的目标和利益，各方必须考虑竞争对手的各种方案，从理性出发，力图选择对自己最为有利的方案。【引例】故事发生在一个遥远的神秘世界。在那里，人们可以制造出不同等级的毒药。这种毒药是致命的，唯一的解药那么是更强的毒药。假设不幸中毒后，只要及时喝下更强的毒药就没事了，否那么不管是谁都会在10分钟之内死亡。一天，恶魔向国王发起挑战，看谁拥有最毒的毒药。这是一场死亡竞赛，比赛规那么很简单：双方各带一瓶毒药，先把对方瓶中的毒药喝掉一半，然后再把毒药换回来，把自己的毒药喝完。10分钟后，活下来的人便赢得这次比赛。恶魔藏有世上的最毒的毒药。国王知道，他无论如何也造不出比那更强的毒药来，并且也知道比赛时恶魔用的就是他那瓶绝无仅有的毒药。国王有方法赢得比赛吗？

答案：国王有方法赢得比赛。在比赛开始前，国王先制造一个药性很弱的毒药，把它喝掉，然后拿着一瓶白开水去比赛。比赛时，国王喝掉恶魔手中的牛B毒药，反而没事了；恶魔喝的那么是白开水。然后，国王喝掉自己的白开水，恶魔喝掉自己的牛B毒药；结果呢，即使他还想找解药都找不着了……因为他那瓶毒药已经是世上最牛的了。

故事并没有结束。如果恶魔在国王身边安插了间谍，知道了国王的手段，事情就又开始变得有意思起来了。恶魔是可以破解这个手段的。一个简单的方法是，在上战场前他也喝点弱毒药。这样下来，两个人最终都能活下来，谁也弄不死谁。恶魔还有一个更绝的方法：赛前什么都不喝，比赛时也带着一瓶白开水上去，于是双方在比赛过程中都喝不到半点毒药，国王将被他比赛前喝掉的那点毒药害死。如果恶魔的“反欺诈”方案又被国王知道了呢？国王有没有一种“反反欺诈”呢？在这种局势下，我们不妨认为，这一折腾下来国王成功地骗恶魔两手空空上战场，于是他赛前喝点弱毒药，再带个稍微强点的去就能击垮恶魔了，成功地实现三重圈套。当然，当恶魔意识到这一点后，他又会重新带着无敌毒药上战场，整个局势转了一个大圈又回来了。

结论呢就是，这个博弈问题没有Nash均衡点。即使游戏双方都聪明绝顶也无用，递归思维深入到的层数唯一地决定了最终决策，整个游戏就像石头剪子布一样无限循环下去，最后倒还不如随机选择一种决策了事。举例：1、囚徒困境：警察抓住了两个罪犯，但是警察局却缺乏足够的证据指证他们所犯下的罪行，如果罪犯中至少有一人供认犯罪就能确定罪名成立。为了得到所需的口供，警察将这两名罪犯分别关押以防止他们串通或者结成攻守联盟，并分别跟他们将清楚了他们的处境和面对的选择：如果他们两人中有一人坦白认罪那么坦白者立即得到释放而另一人将重判8年徒刑。如果两人都坦白认罪，那么他们将各判五年徒刑。当然两人都拒不认罪，那么警察手上缺乏证据，那么他们会以较轻的阻碍公事各判一年徒刑。2、智猪博弈：猪圈里有两头猪，一只大猪，一只小猪。猪圈里的一头有一个猪食槽，另一头安装一个按钮，控制猪食的供给。按一下按钮就会有十个单位的猪食进槽，但是谁按按钮就需要付出两个单位的本钱。假设大猪先到，大猪吃到9个单位的猪食，小猪只能吃到一个单位的猪食，小猪只能吃到1个单位。假设同时到，大猪吃到7个单位，小猪吃三个单位；假设小猪先到，大猪吃6个单位，小猪吃4个单位。3、顶牛博弈：设想在一条笔直的道路两端各有一个司机驾驶者自己的汽车开足马力向对方冲去。在这个过程中，谁害怕躲避退让就被冠以胆小鬼的美名；谁毫不退让最终停在道路中间就被称为英雄。显然，双方如果都停在道路中央，结果将是灾难性的，但是如果双方都躲避退让，他们显然都是胆小鬼。如果一个勇往直前另一个退避让路，那么前者就会非常荣耀并享有较高的满足感。对策论的根本概念1、对策模型的根本要素从“田忌赛马”例子中，我们可以得出对策模型必须具备以下三个根本要素：〔1〕局中人局中人〔players〕是指参与竞争的各方，每方必须有独立的决策能力和承当风险的能力。而那些在竞争中，既不作决策，结局又和他的得失无关的人，就不能称为局中人。例如，“田忌赛马”中，参与人共有三个：田忌、孙膑和齐王。但是孙膑是田忌的谋事，没有独立承当风险的能力，就不能称为局中人，局中人为田忌和齐王。有些对策问题局中人不一定是两个，也可以是多个，后面我们将提到人对策。这里的“局中人”的概念，不一定是单个的人，可以是一个集体，如两个球队之间的比赛，两个企业之间的竞争等，有时我们也可以把“大自然”作为局中人。〔2〕策略集在对策问题中，局中人为了应对其他局中人的行动而采取的方案和手段称为该局中人的一个策略〔strategy〕。这里所说的策略必须是局中人选择的实际可行的通盘筹划的完整的行动方案，并非指竞争过程中某一步所采取的局部方案。例如在齐王赛马的例子中，“先出上马”只是作为一个策略的一个组成局部，并非一个完整的策略，而完整的策略是一开始就要把各人的三匹马排好次序，然后依次出赛。那么三匹马排列的一个次序就是一个完整的行动方案，称为一个策略。如田忌先出下马，然后出中马，最后出上马〔简记为〔下、中、上〕〕就是田忌的一个策略。每个局中人拥有的策略的个数可以相同，也可不相同，可以是有限个，也可以是无限个。我们把一个局中人拥有的策略的全体称为该局中人的策略集。例如，在“田忌赛马”中，田忌的策略集里有六个策略：〔上，中，下〕，〔上，下，中〕，〔中，上，下〕，〔中，下，上〕，〔下，上，中〕，〔下，中，上〕。这六个策略的集合就是田忌的策略集，而齐王的策略集与田忌的一样。如果在一局对策中，各个局中人都有有限个策略，我们称为有限对策〔finitegame〕，否那么称为无限对策〔infinitegame〕。例如，田忌赛马就是一个有限对策，而市场竞争中，因价格变动可能有无限个值，故可认为是无限对策。〔3〕赢得及赢得函数局中人采用不同策略对策时，各方总是有得或有失，统称赢得〔payoff〕或得失。在齐王赛马的例子中，最后田忌得1千金，而齐王损失1千金，即为这局对策〔结局时〕双方的赢得。可以用1和-1来表示。实际上，每个局中人在一局对策结束时的赢得，是与局中人所选定的策略有关，例如在齐王赛马的例子中，当齐王出策略〔上、中、下〕，田忌出策略〔下、上、中〕时，田忌得千金；而如果齐王与田忌都出策略〔上、中、下〕时，田忌就得付出三千金了。所以用数学语言来说，一局对策结束时，每个局中人的赢得是全体局中人所取定的一组策略的函数，通常称为赢得函数(payofffunction)。我们用符号表示局中人的赢得函数。在对策论中，从每个局中人的策略集中各取一个策略，组成的策略组，称为一个局势〔situation〕。于是赢得是局势的函数.如果在任一局势中，全体局中人的赢得相加总和等于零时，这个对策就称为零和对策〔zero-sumgame〕，否那么就称为非零和对策。例如，“田忌”赛马中，假设齐王采取〔上，中，下〕策略，田忌也采取〔上，中，下〕策略，就构成了一个局势，此时，齐王的得益为3千金，田忌为-3千金。我们可以知道，本对策问题中，共存在个策略组合，各策略组合下局中人的得益值都可以计算出来，如表所示。“田忌赛马”损益矩阵

(上中下)(上下中)(中上下)(中下上)(下上中)(下中上)(上中下)3，-31，-11，-11，-1-1，11，-1(上下中)1，-13，-31，-11，-11，-1-1，1(中上下)1，-1-1，13，-31，-11，-11，-1(中下上)-1，11，-11，-13，-31，-11，-1(下上中)1，-11，-11，-1-1，13，-31，-1(下中上)1，-11，-1-1，11，-11，-13，-3上表，局中人甲方齐王的策略集为：局中人乙方田忌的策略集为：表中的元素前面数字表示局中人甲的得益值，后面元素表示局中人乙的得益值，我们把甲方齐王的得益值用下面的矩阵表示。称为局中人甲方的赢得矩阵。2、二人零和对策的条件对策模型的形式很多，我们可以按照以下图将对策问题进行分类：合作对策合作对策非合作对策静态对策动态对策多人对策二人对策零和对策常和对策变和对策对策论上图对策分类中，研究最早、占有重要地位的是二人有限零和对策。二人有限零和对策需具备以下三个条件：a、有两个局中人；b、每个局中人的策略都是有限的；c、每一策略组合下，各局中人得益之和始终为零。一个对策问题只要具备以上三个条件就称为二人有限零和对策，又叫做矩阵对策。显然，田忌赛马就是一个典型的二人有限零和对策的例子。局中人为田忌和齐王；每个局中人都有六个策略；在任何一对策略组合下，双方的得益之和始终为零。例如当齐王赢得1千金时，田忌就输掉1千金，有。本章所研究的对策问题主要是矩阵对策，通常矩阵对策表示为，表示局中人为甲、乙两个人，各自的策略分别为、，以及局中人甲的赢得矩阵为A。【例】甲、乙二人之间玩剪刀·石头·布游戏，输方付给赢方1元人民币，如假设双方所出策略相同，例如都出剪刀，那么得益均为零。试写出双方进行一次游戏时各局中人的策略集和局中人甲的赢得矩阵。解：显然，局中人甲和乙可出的策略有剪刀、石头和布，此对策问题为二人有限零和对策，=｛剪刀，石头，布｝，局中人甲的赢得矩阵为：矩阵对策的