0绪论1线性规划

李明超副教授

运筹学OperationsResearch课程说明1、教材与参考书教材钱颂迪主编，运筹学(第三/四版)，清华大学出版社，2005/2012参考书胡运权主编，运筹学教程(第三版)，清华大学出版社，2007Hillier,F.S.IntroductiontoOperationsResearch,8e.McGraw-Hill,20052、先修课程微积分、线性代数、概率论3、学习与考试方式学习课堂听课、课下习题、案例分析、程序编制课程资料→本科教学→课程信息→运筹学→课程资料考试闭卷考试+平时成绩课程说明运筹学讨论学习：QQ群：

305522490/运筹学2014需要验证：所在班级+姓名（例如：水电1班柴朝政、水港2班闫小龙）进群后要求将群名片修改为：班级+姓名。（例如：水1柴朝政、港2闫小龙）课程说明4、课程内容（32学时）课程说明绪论（1学时）第一章线性规划（6学时）第二章对偶理论与灵敏度分析（4学时）第三章整数规划（2学时）第四章动态规划（4学时）第五章图与网络分析（6学时）第六章排队论（4学时）第七章决策论（2学时）复习（1学时）考试（2学时）绪论

Introduction运筹学

OperationsResearch绪论一、运筹学的产生与发展运筹学的萌芽可以追朔到20世纪初期，但主要产生于20世纪40年代中期的二战期间。创建阶段（1945~1951）1947年美国Dantzig提出了单纯形法1948年英国运筹学会（ORClub）成立1950年英国伯明翰大学正式开设运筹学课程

《运筹学季刊》在英国创刊1951年美国Morse等著的《运筹学方法》一书出版绪论绪论成长阶段（1952~1959）计算机技术的发展促进了运筹学的推广应用美国已有约半数的大公司应用运筹学解决管理运营中的生产计划、资源分配等问题更多学会和刊物的出现：10个国家、6种刊物1957年英国牛津大学召开第一次国际运筹学会议1959年成立国际运筹学联合会（InternationalFederationofOperationalResearchSocieties，IFORS，http://）绪论普及发展阶段（1960~）进一步细分为各个分支：线性规划、动态规划……专业学术团体、期刊、书籍迅速增多运筹学课程更多地被纳入教学计划运筹学的广泛实际背景促使其不断发展并在经济管理、系统工程和工程建设等多领域中发挥着令人瞩目的重要作用。绪论我国运筹学的发展20世纪50年代中期由钱学森等引入，1957年正式定名为运筹学（“夫运筹帷幄之中，决胜千里之外”—《史记》）。1970年后，在华罗庚的直接指导下，全国范围内推广统筹法和优选法，并取得了卓著成效。1980年，中国运筹学会于成立，1982年作为正式成员加入了国际运筹学联合会（IFORS）。绪论二、运筹学的特性运筹学是一门以定量方法为管理决策提供科学依据的应用科学。基本特性以管理决策为基点以科学方法论为依据以系统观点为指导以数学模型为主要工具绪论三、运筹学的应用与软件运筹学在水利水电和港口工程中的应用土石方调配水文计算混凝土浇筑施工场地布置场内交通分析水库调度……绪论运筹学常用软件MSExcelSolverLINDO、LINGOCPLEX运筹学软件包Matlab……第一章线性规划

LinearProgramming运筹学

OperationsResearch1.1线性规划模型1.2图解法1.3单纯形法1.1线性规划模型一、线性规划问题第一章线性规划在生产和经营等管理工作中，需要经常进行计划或规划，共同需要解决的问题可归结为：

在现有各项资源条件的限制下，如何确定相应的方案，合理利用资源，使预期目标达到最优。第一章线性规划[例1]

某工厂要生产甲、乙两种产品，需消耗A、B、C三种资源。现将有关数据列表如下：试拟订使总利润最大的生产计划方案。第一章线性规划解：设安排甲、乙产量分别为x1、x2，总收入为z，则模型为：第一章线性规划[例2]某施工工地有3个不同土区，按工期要求和碾压条件所限，各土区所需土料和装运费情况如下表：求使装运费用最节省的土方调配方案。第一章线性规划解：设3个土区每天取土次数分别为x1、x2、x3，总费用为z，则模型为：第一章线性规划[例3]某工厂要为生产产品需购买材料来获取A、B、C、D四种物质，市场上可选择的材料有M、N两种。有关数据如下表：材料售价（元/kg）每kg含物质ABCDMN40每件产品需要量1.7试决定买M与N二种材料料各多少kg而使支出的总费用为最少？第一章线性规划解：设M、N材料分别购买x1、x2（kg）

，总费用为z，则模型为：第一章线性规划[练习1]A、B两水电站均属调节电站，同时从C水库引水发电，枯水期平均流量0.52m3/s，按规定A、B两站厂用电量不得超过0.9万kW·h，其它有关指标如下：项目单位A电站B电站装机kW4000400单位千瓦耗水m3/s0.000240.0004厂用电率%0.750.60可调小时h/月600600求枯水期上网电量最大的电站出力调度方案。第一章线性规划解：设A、B电站出力分别为x1、x2（kW）

，总上网电量为z，则模型为：第一章线性规划[练习2]某港口某年生产经营指标如下表。该年吞吐量不超过880万吨，其中：煤炭吞吐量至少630万吨；木材需求在10万吨以上，二码头通过能力难以突破32万吨；矿石吞吐量至少130万吨，化肥货源预计在45万吨以下，三码头实际通过能力难以突破300万吨。以码头通过能力和货源预测为约束条件求得最佳货种搭配，以取得最大营业收入。码头一码头二码头三码头货物煤炭木材石油矿石化肥其他单位收入(万元/万吨)1.857.3220.318.5第一章线性规划第一章线性规划二、线性规划数学模型一般形式如下（以max型、约束为例）：第一章线性规划矩阵形式：X——决策变量向量C——价格系数向量A——技术系数矩阵b——资源限制向量？为什么将A称为技术系数矩阵？技术系数：生产一定量某种产品所需要的各种生产要素的配合比例。第一章线性规划第一章线性规划线性规划模型的一个基本特点：目标和约束均为变量的线性表达式若模型中出现非线性表达式，如：则不属于线性规划，而是非线性规划。1.2图解法第一章线性规划

图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。分三步进行：第一章线性规划1、作约束的图形先做非负约束的图形；再做资源约束的图形。以例1为例，其约束为：x1x203448可行域第一章线性规划2、作目标的图形对于目标函数：x2x103448任给两个不同的z值，可作相应的两条直线，用虚线表示。z

＝6z

＝12可以看出z增大的方向。第一章线性规划3、求最优解将目标直线向使目标优化的方向移，直至可行域的边界为止，这时其与可行域的“切”点X*

即最优解。例1中的最优解：X*＝（4，2）Tx1x203448X*第一章线性规划由图解法的结果得到例1的最优解，即：x1＝4，x2＝2。将其代入目标函数求得相应的最优目标值：z

＝14。说明该厂最优生产计划方案为：当生产甲产品4件，乙产品2件时，可获得最大的利润14元。第一章线性规划[练习]用图解法求解下列线性规划问题：x100.51x211.50.375X*＝（0.5，0）T，z*=3X*第一章线性规划[思考]线性规划的可行域是什么形状？——多边形，而且是“凸”形的多边形。最优解在什么位置获得？——在边界，而且是在某个顶点获得。第一章线性规划由图解法得到线性规划解的一些特性：（1）线性规划的约束集（即可行域）是一个凸多面体。凸多面体是凸集的一种，所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：凸集中的“极点”，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点，如多边形顶点。第一章线性规划（2）线性规划的最优解（若存在的话）必能在可行域的顶点获得。由图解法可知，只有当目标直线平移到边界时，才能使目标z达到最大限度的优化。问题：本性质有何重要意义？第一章线性规划（3）线性规划解的几种情形a）唯一解c）无可行解注：出现c）、d）情况时，建模有问题。b）无穷多最优解（多重最优解）d）无界解（无有限最优解）矛盾的约束条件缺乏必要的约束条件1.3单纯形法第一章线性规划单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Dantzig）提出。尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。第一章线性规划一、预备知识1、线性规划问题的标准型式标准型式特点：max型、等式约束、非负约束Am×n的秩为m(mn)，b0第一章线性规划标准模型是基于理性决策的假设前提得到的。什么是理性决策（MakingRationalDecisions）？人是目标最大化的经济动物，即决策者是理性的（好事越多越好，坏事越少越好）；每个可行决策方案可能产生的结果，或者至少是结果的概率和收益都已知；决策者有着明确的偏好顺序，能够对结果进行排序（从最好到最坏）。第一章线性规划线性规划问题的一般型式如何转化为标准型式？——引入符号和变量（1）目标函数：min型max型，引入负号（2）约束条件：不等式，引入松弛变量或剩余变量x3称为松弛变量。问：其实际意义是什么？第一章线性规划（3）对于取值无约束的变量xk：（4）对于右端项bi<0的情况：等式两端同时乘以－1即可。（5）对于xi<0的情况：令x'=－x即可。由此，任何形式的线性规划模型均可化为标准型式。第一章线性规划[例4]

将例1的数学模型化为标准型式。解：增加松弛变量x3、x4、x5，可得到标准型式为：易见，增加的松弛变量的系数恰构成一个单位矩阵I。第一章线性规划若用向量和矩阵符号来表述，记松弛变量的向量为Xs，则有：第一章线性规划[练习3]

将下列线性规划问题化为标准型式。第一章线性规划[作业]（第四版）

1、P55，习题2.1。2、P55，习题2.2：

只需写出标准型，不用列初始单纯形表。3、P56，习题2.5。第一章线性规划2、基本概念（对于标准型）（1）可行解与最优解可行解：满足全部约束条件的解，记为X；最优解：可行解中最优的，记为X*。对于任一可行解X，有CX

≤CX*。可行解是可行域中的点，是一个可行的方案；最优解是可行域的顶点，是一个最优的方案。第一章线性规划（2）基矩阵与基变量基矩阵(简称基)：系数阵A中的m阶可逆子阵，记为B；其余部分称为非基矩阵，记为N。第一章线性规划（2）基矩阵与基变量基向量：基B中的列；其余称非基向量。基变量：与基向量Pj对应的决策变量xj，记其组成的向量为XB；与非基向量对应的变量称非基变量，记其组成的向量为XN。第一章线性规划[例5]下面为例1线性规划模型的标准型式，列出其基矩阵和相应的基向量、基变量。？例5中模型一共有几个基？？一般地，m×n阶矩阵A中基的个数最多有多少个？第一章线性规划（3）基本解与基本可行解基本解(基解)：一个基本解第一章线性规划可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。基本可行解(基可行解)：非负的基本解。求例5中相应于基B1和B2的基本解，并判断它们是否基本可行解？第一章线性规划基本概念之间的联系：系数阵A中可找出若干个基B几种解之间的关系：基本可行解每个基B都对应于一个基本解非负的基本解就是基本可行解第一章线性规划问题：基本可行解、基本解是可行域中的哪些点？x1x203448第一章线性规划3、基本定理（1）线性规划的可行域是一个凸多面体。（2）线性规划可行域的顶点与基本可行解一一对应。（3）线性规划的最优解（若存在的话）必能在可行域的顶点获得。第一章线性规划二、单纯形法的计算步骤单纯形法是一种迭代算法，它的思想是在可行域的顶点——基本可行解中寻优。由于顶点个数有限，因此，算法经有限步可结束。数学模型标准化初始基本可行解是否最优？寻找更优的基本可行解结束YN第一章线性规划何为单纯形？单纯形是代数拓扑中最基本的概念，单纯剖分是研究代数拓扑的基本手段。

0维单纯形就是点；1维单纯形就是线段；2维单纯形就是三角形；3维单纯形就是立体三角形（四面体）……人们希望能够把一个拓扑对象剖分成许多个小的单纯形，要求任何两个相邻的单纯形相交的公共部分仍是一个单纯形——这种剖分称为单纯剖分。第一章线性规划【引例】第一章线性规划1、确定初始基本可行解确定方法：若A中含I，则B0=I；若A中不含I，则可用人工变量法构造一个I.由于基可行解是由一个可行基决定的，因此，确定初始基可行解X0相当于确定一个初始可行基B0

。回顾：若B0=I，则X0=？例5中X0=？第一章线性规划2、最优性检验检验数向量，记为。当≤0时，当前解为最优解。第一章线性规划检验方法：（1）计算每个xj的检验数（2）若所有

j≤0，则当前解为最优否则，若至少有

j>0，则转入下一步。问题：计算上一步所求得X0的每个xj的检验数，并判断X0是否为最优解？第一章线性规划3、寻找更优的基本可行解由于基本可行解与基对应，即寻找一个新的基可行解，相当于从上一个基B0变换为下一个新的基B1，因此，本步骤也称为基变换。第一章线性规划寻找方法：i

称为检验比。问题：接上一步，确定进基、出基，换基计算下一个基本可行解、再检验，直至最优。当模型规模较大时，计算量很大。事实上，单纯形法的实现是在单纯形表上完成的。第一章线性规划线性规划解的相关概念可行域、可行解、最优解、最优值基、可行基基向量、基变量、非基变量基解、基可行解第一章线性规划【例6】令P=(P3,P4,P5)=P3,P4,P5是三个基向量与P3,P4,P5相对应的三个变量x3,x4,x5是基变量XB=[x3,x4,x5]TXN=[x1,x2]T得到XB=[x3,x4,x5]T=[8,16,12]T其也是基可行解此时，z=0P是一个基,(1)令XN=[x1,x2]T=[0,0]T,x1,x2是非基变量,对应的可行基为P=(P3,P4,P5),则为基解,第一章线性规划P’=(P3,P4,P2)=XB’=[x3,x4,x2]TXN’=[x1,x5]T得到XB’=[x3,x4,x2]T=[8,10,3]T其也是基可行解此时，z=15x2进基，x5出基(2)令XN’=[x1,x5]T=[0,0]T,x1,x5是非基变量,对应的可行基为P’=(P3,P4,P2),则为基解,第一章线性规划用P2替换P5，则P3,P4,P2是三个基向量P’是一个基,则为最优解，z=15为最优值第一章线性规划三、单纯形表单纯形表是基于单纯形法的计算步骤设计的计算格式，是单纯形法的具体实现。过程：单纯形表的主体内容是：B-1(bA)，即第一章线性规划问题：（1）第一张表的B-1=？（2）检验数的公式是什么？（3）B-1Pj在表格哪里？单纯形表的结构形式：第一章线性规划[例7]采用单纯形表求解例1的线性规划问题。初始单纯形表：初始基本可行解X0=？z0=？230004—3[4]第一章线性规划以[4]为主元素进行初等行变换：新的基本可行解X1=？z1=？[1]2000–3/424—3x2–1/