运筹学讲义.doc

运筹学讲义 绪论（2学时）参考教材：（1） 运筹学基础教程（魏权龄）（2） 管理运筹学（韩伯棠）（3） 管理运筹学通论（韩大卫）（4） 运筹学（胡运权）先修课程：一元微积分、线性代数、概率统计学时：48+（8）主讲教师：狄军锋一、 运筹学发展1、 运筹学的产生 最早与1938年出现于英国，简称OR(operational Research) 夫运筹帷幄之中，决胜于千里之外，吾不如子房。-史记 古代运筹学思想：田忌赛马+丁谓挖沟+沈括运军粮 二战中的运筹学：反潜艇策略、深水炸弹的起爆深度、诺曼底登陆 运筹学在我国的发展： 50年代中期，钱学森、许国志等教授将运筹学由西方引入我国。 管梅谷（1962年，山东师范大学）：“中国邮递员问题” 华罗庚：优选法（1970）和统筹法（1965）2、运筹学的定义：管理运筹学是一门应用科学，它广泛应用现有的科学技术和数学方法，解决管理中提出的专门问题，为决策者选择最优或较优的决策提供定量依据。运筹学是一门新兴的交叉学科，来源于军事、管理和经济。本课程主要介绍用于解决管理领域问题的运筹学，因此称为管理运筹学，也有人称为管理科学。二、运筹学解决问题的思路提出问题建模求解结果分析与调整实施二、 运筹学的学科内容：线性规划（LP）；*整数规划（IP）；*非线性规划(NP)；*多目标规划（MP）；动态规划（DP）；对策论（GT）；决策分析（DA）；存贮论（IC）；排队论（QT）；图论（Graph Theory）三、章节安排1、绪论（2学时）2、线性规划(14学时)3、动态规划（6学时）4、存储论（6学时）5、对策论（10学时）6、决策论（6学时）7、统筹方法（2学时）8、总复习（2学时）四、应用举例1、 猴子运香蕉2、 海盗分宝石3、 猜生日第二章线性规划*主要内容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白菜200105002二、 LP问题的模型线性规划：变量满足线性约束的条件下，求使线性目标函数值最优的问题。1、一般形式 2、紧缩形式3、矩阵形式 4、向量形式 其中， 。三、 线性规划标准模型由线性规划模型的一般形式的讨论可知，线性规划模型有多种不同情况：目标函数可以是最大或最小，约束条件可以有大于等于、小于等于或等于三种情况。为便于线性规划模型的求解，可将线性规划模型的一般形式统一转化为标准形式，这里规定线性规划标准模型的条件：目标函数最小化、约束条件为等式、决策变量均非负、右端项非负。线性规划标准模型的一般表达式： 化一般型为标准型： 左边+松弛变量；左边-剩余变量 变量；变量无限制令 等式两边同乘以（-1）.2图解法一、 线性规划几何解的有关概念考虑线性规划模型一般形式： 可行解：凡满足约束条件和非负条件的决策变量的取值称为线性规划可行解。可行域：所有可行解的集合称为线性规划的可行域。最优解：使目标函数达到最优值的可行解称为线性规划的最优解。二、 图解法基本步骤在明确线性规划可行解、可行域和最优解的基础上，介绍线性规划的图解法。对于两个或三个变量的线性规划问题，可以通过平面图或立体图进行求解，是线性规划问题解的几何表示。图解法的优点简单、直观，有助于理解线性规划问题求解的基本原理。它的局限性在于只能对两个或三个变量的线性规划问题求解。图解法的基本步骤可以概括如下：（1）建立平面（空间）直角坐标系。取决策变量为坐标向量，标出坐标原点、坐标轴指向及单位长度。 （2）确定线性规划解可行域。根据非负条件和约束条件画出解的可行域。只有在第一象限的点才满足线性规划非负条件，将以不等式表示的每个约束条件化为等式，在坐标系第一象限作出约束直线，每条约束直线将第一象限划分为两个半平面，通过判断确定不等式所决定的半平面。所有约束直线可能形成或不能形成相交区域，若能形成相交区域，相交区域任意点所表示解称为此线性规划可行解，这些符合约束限制的点集合，称为可行集或可行域。转到第三步；否则该线性规划问题无可行解。（3）绘制目标函数等值线（面）。目标函数等值线（面）就是目标函数取值相同点的集合，通常是一条直线（二维平面）或一个平面（三维空间）。（4）寻找线性规划最优解。对于目标函数的任意等值线（面），确定该等值线（面）平移后值增加的方向，平移此目标函数的等值线（面），使其达到既与可行域相交又不可能使目标函数值再增加的位置。相交位置存在三种情况：若有唯一交点时，目标函数等值线（面）与可行域相切，切点坐标就是线性规划的最优解；若相交于多个点，称线性规划有无穷多最优解；若相交于无穷远处，此时无有限最优解。【例】 运用图解法求解线性规划问题 三、线性规划问题几何解的讨论利用图解法可以讨论线性规划解的四种情况。（1）唯一最优解。线性规划唯一最优解是指该规划问题有且仅有一个既在可行域内、又使目标值达到最优的解。（2）无穷多最优解。线性规划问题的无穷多解是指，该规划问题有无穷多个既在可行域内、又使目标值达到最优的解。如果例的目标函数变为，目标函数的等值线正好和约束条件相平行。在目标函数向右上方平移的过程中，与可行域相切于上的所有点，此时，该线性规划问题存在无穷多最优解。（3）无有限最优解（无界解）。线性规划问题的无有限最优解是指最大化问题中的目标函数值可以无限增大，或最小化问题中的目标函数值可以无限减少。考虑下述线性规划模型：利用图解法进行求解时，可行域是一个非封闭的无界区域，的取值可以无限增大，同时，目标函数值也可以增大到无穷，如下图所示。在这种情况下，称线性规划无有限最优解或无界解。原因在于建立线性规划模型时，遗漏了某种必要资源的约束。4542x2x1+2x2=4x1-2x2=5x1ox2x1（4）无可行解。当线性规划问题中的约束条件不能同时满足时，将出现无可行域的情况，这时不存在可行解，即该线性规划问题无解。考虑下述线性规划模型 利用图解法进行求解时，在第一象限内，所有约束条件不能形成一个相交平面区域，如上图。线性规划问题不存在可行域，也就是说，问题没有可行解。其原因是线性规划模型自身的错误，约束条件之间自相矛盾，应根据实际情况进行调整。针对线性规划几何解还有一些重要的性质，这里不加证明叙述如下：（1）线性规划几何解存在四种情况：唯一最优解、无穷多最优解、无有限最优解、无可行解。（2）若线性规划可行域非空，则可行域必定是一个凸集。（3）若线性规划可行域非空，则凸集至多有有限个极点。（4）若线性规划优解存在，则最优解或最优解之一肯定能够在可行域（凸集）的某个极点找到。通过上述的讨论，求线性规划问题最优解，可以转化为在其可行域有限个极点上进行搜索的方法。基本思路是，先找出凸集任意一个极点，计算极点的目标函数值。比较与之相邻的目标函数值是否比该极点的目标函数值更优，如果为否，则该极点就是最优解，如果为是，转到比该点目标函数值更优的另一极点。重复上述过程，直到找出使目标函数值达到最忧的极点为止。可行域空集无界有界解无可行解唯一最优解多重最优解解无界解作业：1、 讨论变化对最优解的影响。2、P51.33 单纯形法（Simplex Method丹茨格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 运输问题（The Transportation Problem）在经济建设中，经常会遇见大宗物资调拨中的运输问题。例如煤炭、钢材、木材、粮食等物资，在全国有若干个生产基地，根据已有的交通网，应如何制定调运方案，将这些物资运送至各消费点，而使总运费最小。一、 基本模型1、 数学描述：假设有m个产地，可以供应某种物资，用表示，有n个销地，用表示，产地的产量和销地的销售量分别为和，从至单位运价为。2、 应用举例 销地产地产量362470533480175250销量403070602003、 产销平衡的运输模型的线性规划模型4、 产销不平衡的运输问题例：销地、需求量依次为3000、1000、2000吨，产地、产量为4000、1500吨。由于需求大于供给，决定需求量可减少吨，区全部满足，需求量不少于1700吨，试求运费最小的分配方案。销地产地产量1.651.701.7540001.601.651.701500销量300010002000 销地产地产量1.65M1.701.75M40001.60M1.651.70M1500M0MM0500销量2800200100017003006000二、 表上作业法运输问题变量多，运算量大；必须化为产销平衡问题。表上作业法的步骤：找出初始基本可行解；求各非基变量的检验数；确定入基和出基变量；重复、直至得到最优解。1、 确定初始基本可行解（1）西北角法 销地产地产量40307007010805050销量40307060200（2）最小元素法 销地产地产量70703005080401050销量403070602002、 最优解的判别（1）闭回路法在已经给出的调运方案的运输表上，从一个代表非基变量的空格出发，沿水平或垂直方向前进，只要碰到代表基变量的填入数字才能向左或向右转90度（当然也可以不改变方向继续前进），这样继续下去，直到回到出发的那个空格，由此形成的封闭折线叫做闭回路。一个空格存在唯一的毕回路。例如，增加1t，运输费用增加5元，就得减少1t，运输费用减少3元，为了产量平衡，就得增加1t，运输费用增加6元，为了销量平衡，就得减少1t，运输费用减小3元，所以检验数为5.非基变量闭回路检验数-4-35364我们把基数顶点运价之和减去偶数顶点运价之和即可得到非基变量的检验数。（2）位势法我们对运输表上的每一行赋予一个数值，对每一列赋予一个数值，它们的数值是由基变量的检验数所决定，则非基变量的检验数为 销地产地产量-4-305-3364-5销量36673.改进运输方案的方法：闭回路调整法首先选择负值最小的检验数，以它所对应的非基变量作为入基变量，并做一闭回路。 销地产地产量4003070300704010805050销量40307060200求得调运方案，=30，即闭回路上偶数顶点的运量最小值，然后基数顶点加上这个值，偶数顶点减去这个值，即可得到调整后的运输方案。 销地产地产量41011-164-1销量3223存在负的检验数，仍需调整。 销地产地产量403070304010805050销量40307060200=40，即闭回路上偶数顶点运量最小值，然后基数顶点加上这个值，偶数顶点减去这个值，即可得到调整后的运输方案。仍利用位势法求非基变量检验数。 销地产地产量14102164-1销量2223总运费为：2*70+3*30+3*0+4*50+2*10+1*40=490元，若存在多个最优解即是存在非基变量的检验数为0.4 线性规划问题建模1、 套材下料问题有10米长的钢管若干，现在需要2、3、5长的钢管各100根，问如何建立模型？2、 人力资源分配问题某医院昼夜24h各时段内需要的护士数量为：2：006：00 10人；6：0010：00 15人；10：0014：00 25人；14：0018：00 20人；18：0022：00 18人；22：002：00 12人。护士分别于2点、6点、10点、18点、22点分6批上班，并且连续工作8小时。试确定：（1） 该医院至少应设置多少名护士，才能满足值班需要?（2） 若医院可以聘任合同工护士，上班时间同正式工时间，若正式工报酬为10元/h，合同工为15元/h，问医院是否应聘用合同工护士及聘用多少？3、 生产计划问题某机械厂生产、三种产品，每种产品均需要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出发，有两个选择：至D1；至D2，则 其相应的决策为，这说明由C1至终点E的最短距离为8，最短路线为同理，从C2、C3和C4出发，有其相应的决策为其相应的决策为其相应的决策为类似地，可算得当k=3时，有：当k=4时， 出发点只有一个A点，则且。于是得到从起点A到终点E的最短距离为13。因而最短路线为从上面的计算过程中可以看出，在求解的各个阶段，我们利用了k阶段与k+1阶段之间的递推关系： 一般情况，k阶段与k+1阶段的递推关系式可写为 式5- 1这种递推关系称为动态规划的基本方程，后一个等式称为边界条件。现在把动态规划的基本思想总结如下： 1）动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件。2）在多阶段决策过程中，动态规划方法是既把当前一个阶段和未来各阶段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。3）在求整个问题的最优策略时，由于初始状态是已知的，而每个阶段的决策都是该阶段状态的函数。故最优策略所经过的各阶段状态便可逐次变换得到，从而确定了最优路线。动态规划方法是基于贝尔曼等人提出的最优化原理，这个最优化原理指出：“作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简而言之，一个最优策略的子策略总是最优的。引例正是根据这一原理求解的。利用这一原理，可以把多阶段决策问题的求解过程表示成一个连续的递推过程，由后向前逐步计算。在求解时，前面的各状态与决策，对后面的子过程来说，只相当于初始条件，并不影响后面子过程的最优决策。2 动态规划的应用一 资源分配问题例1：某公司拟将某种高效率的5台设备，分配给所属的甲、乙、丙三个工厂，各工厂若获得这种设备后，可以为公司提供的盈利如表5-1所示。 表5- 1设备分配赢利表 设备台数工厂012345甲乙丙00035479891111111211121211问，这5台设备如何分配给各工厂，才能使公司得到最大的赢利。解：将问题按工厂分为三个阶段，甲、乙、丙三个工厂分别编号为1，2，3。设阶段变量；状态变量表示为分配给第1个工厂至第k个工厂的设备台数；决策变量表示分配给第k个工厂的设备台数；则状态转移方程为 表示为台设备分配到第k个工厂所得赢利值；表示为台设备分配给第1个工厂至第k个工厂所得到的最大赢利值。因而可写出递推关系式为下面从第一个阶段开始向前计算有：第一阶段（k=1）：设将台设备（）全部分配给工厂甲时，则最大赢利值为因为这时只有一个工厂，有多少台设备就全部分配给工厂甲，故它的赢利值就是该段的最大赢利值，其数值计算结果如表所示： k=1时的计算结果 x1s10123450123450379111203791112012345表中表示使为最大值时的最优决策。第二阶段（k=2）：设把台设备（）分配给工厂甲和工厂乙时，则对每个值，有一种最优分配方案，使最大赢利值为因为给乙工厂台，其赢利为，余下的台给甲工厂，则它的赢利最大值为，现要选择的值，使取最大值，其数值计算结果如表所示。第三阶段（k=3）：设把台设备（）分配给甲、乙、丙三个工厂时，则最大赢利值为其中因为给丙工厂台，其赢利为，余下的台分给乙和甲工厂，则它的赢利最大值为，现要选择的值，使取最大值，它就是所求的赢利最大值，其数值计算结果如表所示。k=2时的计算结果 x 3 s301234501234500+30+70+90+110+125+05+35+75+95+119+09+39+79+911+011+311+712+012+312+00591216180121，222，3k=3时的计算结果 x3 s301234550+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时计算结果0123 1210131213此时，顺推可得全部策略.三 多阶段生产安排问题有某种原材料，可用于两种方式的生产，原料用于生产后，除了产生一定数量外，还可以回收一部分，生产信息为：原材料投入量为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、存贮论：就是专门研究存贮问题有关理论和方法的一门学科，是运筹学的一个重要分支。他们用定量的方法描述存贮物品供需关系的动态过程和存贮状态，描述存贮状态和费用之间的关系。并确定经济合理的供应策略。从而为人们提供定量的决策和有价值的定性指导。二、存贮系统考虑最广泛的存贮系统，如图所示补充需求存贮1、 存贮状态：是指某货物随时间推移而发生的盘点数量上的变化。其数量随需求过程而减少，又随补充过程而增加。2、 需求：是系统的输出，他可以表示成多种不同形式。 间断式或连续式：顾客对时令商品的需求是间断性的，对日用品的需求是连续的 均匀的或不均匀的：如工厂自动生产的流水线对原材料的需求是均匀的，而一个城市对电力的需求是不均匀的； 确定的或随机的：如生产活动中对原材料的需求一般是确定的，而销售活动中对商品的需求则往往是随机的。3、 补充的方式：内部生产和外部订购两种方式。从订货到交货之间有一段滞后时间，简称时滞。多少时间补充一次？每次补充的数量为多少？三、存贮模型的建立存贮模型的建立需抓住三个环节：存贮状态图、费用函数和经济批量公式。1、 存贮状态图：描述存贮状态。它表示某物品随时间推移而发生的盘点数量上的变化。；：t时刻的存贮量；：0时刻的存贮量；：0t时刻的累计补充量；：i时刻补充量；：0t时刻的累计需求量；： t时刻需求速度（单位时间的需求量）。在各种具体情况下，由于需求和补充的形式不同，存贮状态图也是各种各样，只有分清补充过程和需求过程两个关键因素，就容易得到符合实际的存贮状态图。2费用函数研究存贮模型的目的是为了选用最优的存贮策略，使得存贮的总费用最小。费用函数便是将存贮状态图各个参数与费用的关系定量的表示出来。在存贮分析中一般需要考虑以下几种费用。（1） 存贮费：指货物被