*林齐宁北京邮电大学经济管理学院010-62282467(家）010-62282039（办）13621281705lqining@public3.bta.net.cn*运筹学OperationalResearch运筹帷幄，决胜千里?史记《张良传》*目录第一章线性规划问题及单纯型解法第二章线性规划的对偶理论及其应用第三章运输问题数学模型及其解法第四章整数规划第五章动态规划第六章图与网路分析第七章随机服务理论概论第八章生灭服务系统第九章特殊随机服务系统第十章存储理论*绪论一、运筹学的起源与发展二、运筹学的特点及研究对象三、运筹学解决问题的方法步骤四、运筹学与其它学科之间的关系*一、运筹学的起源与发展起源于二次大战的一门新兴交叉学科与作战问题相关如雷达的设置、运输船队的护航、反潜作战中深水炸弹的深度、飞行员的编组、军事物资的存储等英国称为OperationalResearch美国称为OperationsResearch战后在经济、管理和机关学校及科研单位继续研究1952年，Morse和Kimball出版《运筹学方法》1948年英国首先成立运筹学会1952年美国成立运筹学会1959年成立国际运筹学联合会(IFORS)我国于1982年加入IFORS，并于1999年8月组织了第15届大会*二、运筹学的特点及研究对象三、运筹学解决问题的方法步骤四、运筹学与其它学科之间的关系*第一章线性规划问题及单纯型解法1.1线性规划问题及其一般数学模型1.1.1线性规划问题举例例1、多产品生产问题（Max,?）设x1,x2分别代表甲、乙两种电缆的生产量，*例2、配料问题（min,?)设x1,x2分别代表每粒胶丸中甲、乙两种原料的用量*例3、合理下料问题设xj分别代表采用切割方案1~8的套数，*1.1.2线性规划数学模型的一般表示方式*1、和式*2、向量式*3、矩阵式*1.1.3线性规划的图解法f(x)=36*线性规划问题的几个特点：线性规划问题的可性解的集合是凸集线性规划问题的基础可行解一般都对应于凸集的极点凸集的极点的个数是有限的最优解只可能在凸集的极点上，而不可能发生在凸集的内部*1.2线性规划问题的单纯型解法1.2.1线性规划问题的标准形式为了使线性规划问题的解法标准，就要把一般形式化为标准形式*变换的方法：目标函数为min型，价值系数一律反号。令f?(x)=-f(x)=-CX,有minf(x)=-max[-f(x)]=-maxf?(x)第i个约束的bi为负值，则该行左右两端系数同时反号，同时不等号也要反向第i个约束为?型，在不等式左边增加一个非负的变量xn+i，称为松弛变量；同时令cn+i=0第i个约束为?型，在不等式左边减去一个非负的变量xn+i，称为剩余变量；同时令cn+i=0若xj?0，令xj=-xj?，代入非标准型，则有xj??0若xj?不限，令xj=xj?-xj?，xj??0，xj??0，代入非标准型*变换举例：*关于标准型解的若干基本概念：标准型有n+m个变量，m个约束行“基”的概念在标准型中，技术系数矩阵有n+m列，即A=(P1,P2,…,Pn+m)A中线性独立的m列，构成该标准型的一个基，即B=(P1?,P2?,…,Pm?)，|B|?0P1?,P2?,…,Pm?称为基向量与基向量对应的变量称为基变量，记为XB=(x1?,x2?,…,xm?)T，其余的变量称为非基变量，记为XN=(xm+1?,xm+2?,…,xm+n?)T，故有X=XB+XN最多有个基*关于标准型解的若干基本概念：可行解与非可行解满足约束条件和非负条件的解X称为可行解，满足约束条件但不满足非负条件的解X称为非可行解基础解令非基变量XN=0，求得基变量XB的值称为基础解即XB=B?1bXB是基础解的必要条件为XB的非零分量个数?m基础可行解基础解XB的非零分量都?0时，称为基础可行解，否则为基础非可行解基础可行解的非零分量个数<m时，称为退化解*线性规划标准型问题解的关系约束方程的解空间基础解可行解非可行解基础可行解退化解*可行解、基础解和基础可行解举例*1.2.2单纯型法的基本思路*1.2.3单纯型表及其格式*例1.2.2试列出下面线性规划问题的初始单纯型表*关于检验数的数学解释设B是初始可行基，则目标函数可写为两部分(1)约束条件也写为两部分，经整理得XB的表达式(2)，注意XB中含有非基变量作参数把XB代入目标函数，整理得到(3)式第j个非基变量的机会成本如(4)式若有cj?zj>