信息系统项目管理师基础知识之运筹学1

2007-6-28第一章线性规划（LinearProgramming）第一章线性规划（LinearProgramming）1.1线性规划的模型与图解法1.2单纯形法1.3对偶问题与灵敏度分析1.4运输问题1.5线性整数规划线性规划的模型与图解法一、线性规划问题及其数学模型1.线性规划问题在生产管理和经营活动中经常需要解决：如何合理地利用有限的资源，以得到最大的效益。某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下：试拟订使总收入最大的生产计划方案。资源单耗产品资源甲乙资源限量煤电油9445310360200300单位产品价格712决策变量：需决策的量，即待求的未知数；2.目标函数：需优化的量，即欲达的目标，用决策变量的表达式表示；3.约束条件：为实现优化目标需受到的限制，用决策变量的等式或不等式表示。线性规划模型的三要素第一章线性规划目标函数：总收入，记为,则，为体现对其追求极大化，在的前面冠以极大号Max；决策变量：甲、乙产品的计划产量，记为；在本例中约束条件：分别来自资源煤、电、油限量的约束，和产量非负的约束，表示为⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+0,3001032005436049..21212121xxxxxxxxts21,xxz12712zxx=+z第一章线性规划解：设安排甲、乙产量分别为,总收入为，则模型为：21,xxz21127xxMaxz+=⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+0,3001032005436049..21212121xxxxxxxxts第一章线性规划线性规划模型的一个基本特点：目标和约束均为变量的线性表达式如果模型中出现如的非线性表达式，则不属于线性规划。32211ln2xxx−+某市今年要兴建大量住宅,已知有三种住宅体系可以大量兴建，各体系资源用量及今年供应量见下表：要求在充分利用各种资源条件下使建造住宅的总面积为最大，求建造方案。水泥(公斤/m2)4000(千工日)147000(千块)150000(吨)20000(吨)110000(千元)资源限量3.5——18025120大模住宅3.0——19030135壁板住宅4.521011012105砖混住宅人工(工日/m2)砖(块/m2)钢材(公斤/m2)造价(元/m2)资源住宅体系第一章线性规划解:设今年计划修建砖混、壁板、大模住宅各为,为总面积,则本问题的数学模型为:⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤++≤≤++≤++≤++0,,40000035.0003.00045.0147000210.0150000180.0190.0110.020000025.0030.0012.0110000120.0135.0105.0.3213211321321321xxxxxxxxxxxxxxxxts321xxxMaxz++=前苏联的尼古拉也夫斯克城住宅兴建计划采用了上述模型，共用了12个变量，10个约束条件。123,,xxxz第一章线性规划练习：某畜牧厂每日要为牲畜购买饲料以使其获取A、B、C、D四种养分。市场上可选择的饲料有M、N两种。有关数据如下：试决定买M与N二种饲料各多少公斤而使支出的总费用为最少？410售价（元/公斤）0.40.62.01.7牲畜每日每头需要量00.10.20.1N0.100.10.2M每公斤含营养成分ABCD第一章线性规划解：设购买M、N饲料各为，则21410xxMinz+=⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥+≥+≥+≥+0,7.11.02.00.22.01.06.01.004.001.0..2121212121xxxxxxxxxxts21,xx第一章线性规划线性规划模型的一般形式：以MAX型、约束为例2.线性规划的数学模型决策变量：目标函数：约束条件：nxx,,1nnxcxcMaxz++=11⎪⎪⎩⎪⎪⎨⎧≥≤++≤++0,,..11111111nmnmnmnnxxbxaxabxaxats≤),,(,)(),,,(,),,(111====×⎩⎨⎧≥≤=0..XbAXtsCXMaxz第一章线性规划一般地中称为决策变量向量，称为价格系数向量,称为技术系数矩阵,称为资源限制向量。⎩⎨⎧≥≤=0..XbAXtsCXMaxzXCAb第一章线性规划图解法是用画图的方式求解线性规划的一种方法。它虽然只能用于解二维（两个变量）的问题，但其主要作用并不在于求解，而是在于能够直观地说明线性规划解的一些重要性质。二、线性规划问题的图解法先做约束的图形先做非负约束的图形；再做资源约束的图形。以例1为例，其约束为⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+0,3001032005436049.21212121xxxxxxxxts01x2x9040501004030对于目标函数任给二不同的值，便可做出相应的二直线，用虚线表示。以例1为例，其目标为，分别令，做出相应的二直线，便可看出增大的方向。nnxcxcz++=11z21127xxz+=16884==zz和z71214242.再做目标图形求出昀优解将目标直线向使目标优化的方向移，直至可行域的边界为止，这时其与可行域的“切”点即昀优解。如在例1中，是可行域的一个角点，经求解交出的二约束直线联立的方程可解得z*X*X*XTX)24,20(*=01x2x9040501003040*X的最优解，还可将其代入目标函数求得相应的最优目标值。说明当甲产量安排20个单位，乙产量安排24个单位时，可获得最大的收入428元。TX)24,20(*=428*=z第一章线性规划⎪⎩⎪⎨⎧≥≥+≥++=0,5.14312..4621212121xxxxxxtsxxMinz01x2x15.0375.05.11*X3,)0,5.0(**==zXT练习：用图解法求解下面的线性规划。第一章线性规划昀优解在什么位置获得？线性规划的可行域是一个什么形状？思考——多边形，而且是“凸”形的多边形。——在边界，而且是在某个顶点获得。第一章线性规划（1）线性规划的约束集（即可行域）是一个凸多面体。凸多面体是凸集的一种。所谓凸集是指：集中任两点的连线仍属此集。试判断下面的图形是否凸集：凸集中的“极点”，又称顶点或角点，是指它属于凸集，但不能表示成集中某二点连线的内点。如多边形的顶点。由图解法得到线性规划解的一些特性第一章线性规划因为，由图解法可知，只有当目标直线平移到边界时，才能使目标z达到昀大限度的优化。问题：本性质有何重要意义？（2）线性规划的最优解（若存在的话）必能在可行域的顶点获得第一章线性规划（3）线性规划解的几种情形1）唯一解2）多重昀优解3）无可行解注：出现3）、4）情况时，建模有问题4）无有限昀优解第一章线性规划单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出。尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。1.2单纯形法第一章线性规划一、单纯形法的预备知识1.线性规划问题的标准型⎩⎨⎧≥==0..XbAXtsCXMaxz标准型的特征：Max型、等式约束、非负约束。）（的秩为其中，0,≥≤×bnmmAnm第一章线性规划线性规划问题的一般型如何化为标准型？（1）如果目标函数求极小，则（2）如果约束条件为不等式，则引入松弛或剩余变量CXMinz=CXMaxz−=/加负号3604921≤+xx36049321=++xxx)(xf)(xf−*xx3称为松弛变量。问题：它的实际意义是什么？——煤资源的“剩余”。第一章线性规划（3）如果存在自由变量，则：（4）右端项仅需将等式或不等式两端同乘（-1）（5）对即可xxx−=≤'0令0ib0,,//////≥−=kkkkkxxxxx第一章线性规划练习：请将例1的约束化为标准型⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+0,3001032005436049..21212121xxxxxxxxts,,,543xxx⎪⎪⎩⎪⎪⎨⎧≥=++=++=++0,,,,3001032005436049..54321521421321xxxxxxxxxxxxxxts解：增加松弛变量则约束化为易见，增加的松弛变量的系数恰构成一个单位阵I。第一章线性规划一般地，记松弛变量的向量为Xs，则⎩⎨⎧≥≤0..XbAXts⎩⎨⎧≥=+0,..ssXXbIXAXts⎩⎨⎧≥≥0..XbAXts⎩⎨⎧≥=−0,..ssXXbIXAXts基本概念（1）可行解与昀优解；的解，记为可行解：满足全体约束X*,XXCXCX∗≤昀优解：可行解中昀优的，记为则对任可行解，有。直观上，可行解是可行域中的点，是一个可行的方案；昀优解是可行域的顶点，是一个昀优的方案。第一章线性规划（2）基矩阵与基变量基矩阵(简称基)：系数阵A中的m阶可逆子阵，记为B；其余部分称为非基矩阵，记为N。基向量：基B中的列；其余称非基向量。基变量：与基向量Pj对应的决策变量xj，记其组成的向量为XB；与非基向量对应的变量称非基变量，记其组成的向量为XN。=⎧⎪−+=⎨⎪≥⎩例：下面为某线性规划的约束请例举出其基矩阵和相应的基向量、基变量。3第一章线性规划阶可逆子阵有中的，解：本例中，210011221AA⎥⎦⎤⎢⎣⎡−=——6个。一般地，m×n阶矩阵A中基的个数昀多有多少个？个。——mnC;,,,100143434311⎟⎟⎠⎞⎜⎜⎝⎛=⎥⎦⎤⎢⎣⎡=xxXxxPPBB，基变量为，其相应的基向量为。基变量为其相应的基向量为⎟⎟⎠⎞⎜⎜⎝⎛=⎥⎦⎤⎢⎣⎡−=21212122,,,,,1221xxXxxPPBB问题：本例的A中一共有几个基？第一章线性规划（3）基本解与基本可行解()().0,0,,,,1111⎟⎠⎞⎜⎝⎛===−==⎟⎠⎞⎜⎝⎛===−−−−bBXbBXXNXBbBXbXXNBbAXXXXNBAmABBABNNBNBTNB时，有当取即可表示为约束中的相应地）（列，则可记中的前表示取定后，不妨设中的基当解；为线性规划的一个基本的解称⎟⎠⎞⎜⎝⎛==−01bBXb