运筹学 Operational Research运筹帷幄，决胜千里史记张良传1绪 论一、运筹学发展简介 二、运筹学的特点及研究对象 三、运筹学的工作步骤 四、运筹学内容介绍2一、运筹学（OR）发展简介 运筹学在国外 英国称为 Operational Research 美国称为 Operations Research 起源于二战期间的军事问题，如雷达的设置、运输船 队的护航舰队的规模、反潜作战中深水炸弹的深度、 飞机出击队型、军事物资的存储等。 二战以后运筹学应用于经济管理领域（LP、计算机） 1948年英国首先成立运筹学会；1952年美国成立运筹 学会。 1952年，Morse 和 Kimball出版运筹学方法 1959年成立国际运筹学联合会3 运筹学在国内 中国古代朴素的运筹学思想（田忌与齐 王对马、都江堰工程、丁渭修复皇宫） 1956年成立运筹学小组 1958年提出运输问题的图上作业法 1962年提出中国邮路问题 1964年华罗庚推广统筹方法 我国于1982年加入国际运筹学联合会， 并于1999年8月组织了第15届大会4二、运筹学的特点及研究对象运筹学的定义 运筹学为决策机构对所控制的业务活动作决策时，提供以 数量为基础的科学方法Morse 和 Kimball 运筹学是把科学方法应用在指导人员、工商企业、政府和 国防等方面解决发生的各种问题，其方法是发展一个科学的 系统模式，并运用这种模式预测、比较各种决策及其产生的 后果，以帮助主管人员科学地决定工作方针和政策英国 运筹学会 运筹学是应用分析、试验、量化的方法对经济管理系统中 人力、物力、财力等资源进行统筹安排，为决策者提供有根 据的最优方案，以实现最有效的管理中国百科全书 现代运筹学涵盖了一切领域的管理与优化问题，称为 Management Science5三、运筹学的工作步骤明确问题建立模型设计算法整理数据求解模型评价结果简化？满意 ？YesNoNo 明确问题 建立模型 设计算法 整理数据 求解模型 评价结果6四、运筹学内容介绍 排队论 线性规划及单纯形 法 对偶理论及灵敏度分析 运输问题 整数规划 动态规划 图与网络分析7第一章 线性规划及单纯形法第一节 线性规划问题及数学模型1939年 苏 康托洛维奇 1941年 美 Hichook 1947年 G.B.Dantzig 单纯形法 1979年 苏 哈奇安算法 1984年 Karmarkar算法8一、实例例1 (书P8)I II设 备 1 2 8台时 原材料A 4 0 16公斤原材料B 0 4 12公斤设I、II两种产品的产量分别为x1, x2 。建立该问题的数学模型为：例2 现要做100套钢架，每套需2.9米、2.1米和1.5米的圆钢各 一根。已知原料长7.4米，问如何下料，使用的原料最少（余料 最少或根数最少）？9解：设 x1, x2 , x3, x4 , x5分别代表五种 不同的原料用量方案（余料最少）方案2.9米2.1米1.5米合计余料 x11037.40 x22017.30.1 x30227.20.2 x41207.10.3x50136.60.81011二、总结 目标函数用决策变量的线性函数来表示。按问题 的不同，要求目标函数实现最大化和最小化。线性规划问题（LP问题）的共同特征： 每一个问题变量都用一组决策变量（x1, x2, , xn） 表示某一方案，这组决策变量的值代表一个具体方 案，这些变量是非负的。 存在一定的约束条件，这些约束条件可以用一组 线性等式或线性不等式来表示。12三、两变量线性规划问题的图解法1.线性不等式的几何意义 半平面1) 作出LP问题的可行域2) 作出目标函数的等值线3) 移动等值线到可行域边界得到最优点2.图解法步骤134x1=164x2=12x1+2x2=8x1x248430例1 （书P8）：Q(4,2)Z=2x1+3x2做目标函数2x1+3x2的等值线，与 阴影部分的边界相交于Q(4,2)点， 表明最优生产计划为：生产I产品4 件，生产II产品2件。14例2Z=36153. 图解法的作用 能解决少量问题LP问题有可行解有最优解唯一解无穷多解无最优解（可行域为无界）无可行解（无解）规律1： 揭示了线性规划问题的若干规律16结论2：若LP问题有最优解 ，则要么最优解唯一，要么 有无穷多最优解。17规律2： 线性规划问题的可行域为一凸集 线性规划问题凸集的顶点个数是有限的 最优解肯定可在凸集的某顶点处达到 18四、 线性规划问题的标准型1. 标准型192. 所有LP问题均可化为标准型20例1可化为21例2 化标准型22课堂作业23五、标准型LP问题的解2425令B = =( P1 , P2 , , Pm )且| B | 0 ，则称Pj (j=1,2,m) 为基向量。与基向量Pj对应的变量xj称为基变量，记为XB = ( x1 , x2 , , xm )T，其余的变量称为非基变量，记为 XN = ( xm+1 , xm+2 , , xm+n ) T 。基变量：26基本解令非基变量 XN = 0，求得的一组基变量 XB的值称为基础解 。 基可行解（顶点）既是基本解，又是可行解。基最优点既是基本解，又是使目标函数值达到最优的解27线性规划标准型问题解的关系约束方程的 解空间基解可行解非可行解基可 行解2810/3244x1x2x1+x2=43x1 +5x2=1029可行解、基础解和 基础可行解举例30第二节 单纯型法一、基本思想化LP问题为标准型， 确定一个初始基本可行解检验解的 最优性结束Y枢轴运算（旋转运算） 确定另一个基本可行解N31二、枢轴运算32三、检验数的意义33第三节 单纯型法的步 骤一、步骤1. 化LP问题为标准型,建立初始单纯型表;34二、实例化为标准型35单纯型表算法Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 0 X5816 121 2 1 0 0 44 0 0 1 0 -0 4 0 0 1 30 2 3 0 0 0以4为枢轴元素进行旋转运 算，x2为换入变量，x5为换出 变量Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 0 X3 0 X4 3 X221631 0 1 0 -1/2 24 0 0 1 0 40 1 0 0 1/4 -9 2 0 0 0 -3/4以1为枢轴元素进行运算 ，x1为换入变量， x3为换 出变量36Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X4 3 X22831 0 1 0 -1/2 -0 0 -4 1 2 40 1 0 0 1/4 12-13 0 0 -2 0 1/4以2为枢轴元素进行运 算，x5为换入变量， x4 为换出变量Cj 2 3 0 0 0 CB XB b X1 X2 X3 X4 X5 2 X1 0 X5 3 X24421 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 -14 0 0 -3/2 -1/8 0此时达到最优解。X*=(4,2), MaxZ=14。37第四节 LP问题的进一步讨论一、人工变量法381. 大M法(M为任意大的正数 )加入松弛变量x4; 剩余变量x5;人工 变量x6,x7391) 人工变量的识别2) 目标函数的处理3) 计算(单纯型法)40Cj-31100MMCBXBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011-3+6M1-M1-3M0M000x4103-20100-1-Mx610100-11-211x31-2010001-11-M00M03M-1注意：本例是求最小值，所以用所有 来判别目标函数是否实现了最小化。因而换 入变量xk的选取标准为41结果得: X*=(4,1,9,0,0,0,0) Z*=2Cj-31100MMCBXBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2-1x31-2010001-10001M-1M+1-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/30001/31/3M-1/3M-2/3（接上表）422. 两阶段法(将LP问题分成两个阶段来考虑)第I 阶段: 不考虑原问题是否存在可行解，给原LP问题 加入人工变量，并构造仅含人工变量的目标函数和要求最 小化；然后用单纯型法求解，若得w=0，则进行第二阶段计 算，否则无可行解。第II 阶段：将第一阶段得到的最终表除去人工变量，将 目标函数行的系数换为原问题的系数，作为第二阶段的初 始表。43加入松弛变量x4; 剩余变量x5;人工 变量x6,x7用单纯形法求解第一阶段的结果得： 44Cj0000011CBXBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-201000116-1-301000x4103-20100-1-1x610100-11-210x31-2010001-0-1001030x4123001-22-540x210100-11-2-0x31-2010000-0000011此时，达到第一阶段的最优解，W=045Cj-31100CBXBbx1x2x3x4x50