线 性 规 划

第1页运筹帷幄之中决胜千里之外线性规划LinearProgramming运筹学课件第2页线性规划线性规划问题可行区域与基本可行解单纯形算法初始可行解对偶理论灵敏度分析计算软件案例分析第3页线性规划问题线性规划实例生产计划问题运输问题线性规划模型一般形式规范形式标准形式形式转换概念第4页某工厂用三种原料生产三种产品，已知的条件如表2.1.1所示，试制订总利润最大的生产计划单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品的利润（千元）354生产计划问题第5页问题分析可控因素：每天生产三种产品的数量，分别设为321,,xxx目标：每天的生产利润最大利润函数321453xxx受制条件：每天原料的需求量不超过可用量：原料1P：15003221xx原料2P：8004232xx原料3P：2000523321xxx蕴含约束：产量为非负数0,,321xxx第6页模型321453maxxxx15003221xxs.t.8004232xx2000523321xxx0,,321xxx第7页计算结果OBJECTIVEFUNCTIONVALUE2675.000VARIABLEVALUEREDUCEDCOSTX1375.0000000.000000X2250.0000000.000000X375.0000000.000000ROWSLACKORSURPLUSDUALPRICES1)0.0000001.0500002)0.0000000.6250003)0.0000000.300000第8页运输问题一个制造厂要把若干单位的产品从两个仓库2,1;iAi发送到零售点4,3,2,1;jBj，仓库iA能供应的产品数量为2,1;iai，零售点jB所需的产品的数量为4,3,2,1;jbj。假设供给总量和需求总量相等，且已知从仓库iA运一个单位产品往jB的运价为ijc。问应如何组织运输才能使总运费最iA小？第9页问题分析可控因素：从仓库iA运往jB的产品数量设为4,3,2,1,2,1;jixij目标：总运费最小费用函数2141ijijijxc受控条件：从仓库运出总量不超过可用总量，运入零售点的数量不低于需求量。由于总供给量等于总需求量，所以都是等号。即2,1;4321iaxxxxiiiii4,3,2,1;21jbxxjjj蕴含约束：数量非负4,3,2,1,2,1;0jixij第10页模型min2141ijijijxc2,1;4321iaxxxxiiiiis.t.4,3,2,1;21jbxxjjj4,3,2,1,2,1;0jixij第11页一般形式qjxqjxmpibxaxaxapibxaxaxatsxcxcxczjjininiiininiinn,...,2,1;,...,2,1;0,...,1;,...,2,1;..min221122112211无限制目标函数约束条件第12页注释njxj,...,2,1;为待定的决策变量，),,,(21ncccc为价值向量，njcj,...,2,1;为价值系数，),...,,(21mbbbb为右端向量，矩阵为系数矩阵。mnmmnnaaaaaaaaaA212222111211第13页规范形式0..minxbAxtsxc第14页标准形式0..minxbAxtsxc第15页概念可行解（或可行点）：满足所有约束条件的向量),,(21nxxxx可行集（或可行域）：所有的可行解的全体}0,{xbAxxD最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体称为最优解集合DyycxcDxO,{}最优值：最优解的目标函数值Oxxcv,第16页模型转换约束转换实例令自由变量jjjxxx，其中jjxx,为非负变量求最大可以等价成求负的最小xcxcminmax目标转换变量转换第17页约束转换不等式变等式不等式变不等式ininiibxaxaxa2211ininiibxaxaxa2211ininiibxaxaxa2211等式变不等式第18页不等式变等式ininiibxaxaxa22110,2211iiininiisbsxaxaxa或ininiibxaxaxa22110,2211iiininiisbsxaxaxa松弛变量剩余变量第19页不等式变不等式ininiibxaxaxa2211ininiibxaxaxa2211或ininiibxaxaxa2211ininiibxaxaxa2211第20页例2.1.3把问题转化为标准形式052222..21max1212121xxxxxxxtsxxz7,6,5,4,3,1;05)(2)(22)(2..)(min743164315431431ixxxxxxxxxxxxxtsxxxzi第21页可行区域与基本可行解图解法可行域的几何结构基本可行解与基本定理第22页图解法对于只有两个变量的线性规划问题可以用图解法求解：变量用直角坐标系中的点表示约束条件用坐标系中的半空间或直线的交表示可行区域是一个凸多面体目标函数用一组等值线表示，沿着增加或减少的方向移动，与可行域最后的交点就是最优解。第23页例2.2.1解线性规划2221xx2221xx521xx最优解（1，4）052222..max121212121xxxxxxxtsxxz第24页当目标函数该边后，等值线的方向会发生改变，如果等值线与某个约束对应的函数直线平行，则该函数值线上的所有可行解都是最优解2221xx2221xx最优解（1，4）521xx第25页注释可能出现的情况：可行域是空集可行域无界无最优解最优解存在且唯一，则一定在顶点上达到最优解存在且不唯一，一定存在顶点是最优解第26页可行域的几何结构基本假设凸集可行域的凸性第27页基本假设考虑线性规划的标准形式其中nmmnRARbRcx,,,，并且假定可行域}0,{xbAxRxDn不空，系数矩阵A是行满秩的，mAr)(，否则的话可以去掉多余约束。0..minxbAxtsxc第28页凸集定义2.2.1：设nRS是n维欧氏空间的点集，若对任意SySx,的和任意]1,0[都有就称S是一个凸集。定理2.2.1线性规划的可行域}0,{xbAxxD是凸集定理2.2.2任意多个凸集的交还是凸集Syx)1(第29页可行域的凸性超平面}{bxaRxHn半空间}{bxaRxHn；}{bxaRxHn多面凸集},...,2,1;;,...,2,1;{qpppibxapibxaRxSiiiin定义2.2.2：设S为凸集Sx，如果对任意Szy,和10，都有zyx)1(,则称x为S的顶点。第30页问题1.可行域顶点的个数是否有限？2.最优解是否一定在可行域顶点上达到？3.如何找到顶点？4.如何从一个顶点转移到另一个顶点?第31页基本可行解与基本定理定义基本定理问题第32页基本可行解定义令),(NBA，x=(Bx,Nx)。bAx分块bNxBxNB左乘1BbBNxBxNB11即NBNxBbBx11Nx=001bBx第33页定义2.2.2：设B是秩为m的约束矩阵A的一个m阶满秩子方阵，则称B为一个基；B中m个线性无关的列向量称为基向量，变量x中与之对应的m个分量称为基变量，其余的变量为非基变量，令所有的非基变量取值为0，得到的解01bBx称为相应于B的基本解。当01bB则称基本解为基本可行解，这时对应的基阵B为可行基。如果01bB则称该基可行解为非退化的，如果一个线性规划的所有基可行解都是非退化的则称该规划为非退化的。第34页例考虑问题：5,4,3,2,1;052222..min52142132121jxxxxxxxxxxtsxxzj系数矩阵100110102100112A基阵为1000100011B1010110022B对应的基解分别为)5,2,2,0,0(1x和)6,3,0,0,1(2x，其中x1为基本可行解，x2不是基本可行解。第35页基本定理定理2.2.3可行解x是基本可行解的充要条件是它的正分量所对应的矩阵A中列向量线性无关。定理2.2.4x是基本可行解的充要条件是x是可行域D的顶点。定理2.2.5一个标准的LP问题如果有可行解，则至少有一个基本可行解定理2.2.6一个标准的LP问题如果有有限的最优值，则一定存在一个基本可行解是最优解。第36页问题1．基本可行解不一定都是最优解，最优解也不一定都是基本解2．如果有两个基本可行解是最优解，则两解的凸组合也都是最优解。3．如果最优解不唯一，则会有多个基本可行解是最优解，它们必然在同一个面上。4．行解个数有限，可以在基可行解中寻找最优解。剩余的问题是如何判断一个基可行解是最优解，如果不是则如何从一个基可行解转到另一个基可行解。第37页单纯形算法理论方法算法步骤单纯形表算例第38页理论方法定理2.3.1（最优性准则）如果0，则基可行解x为原问题的最优解。定理2.3.2如果向量的第k个分量0k，而向量01kAB，则原问题无界。定理2.3.3对于非退化的基本可行解x，若向量的第k个分量0k，而向量.1kAB至少有一个正分量，则可以找到一个新的基本可行解xˆ使得xcxcˆ。★★★第39页定理2.3.1给定一个非退化的基可行解x，对应的可行基为B，则等式约束变为：bBNxBxNB11典式NBNxBbBx11目标函数NNBBxcxcxcNNNBxcNxBbBc)(11NNBBxcNBcbBc)(11令NBNcNBc1，0B，则xbBcxcB1规划等价于0..min111xbBNxBxtsxbBcNBB第40页定理2.3.2令)0,,0,1,0,,0,(ˆ1kkABb其基变量取值为。非基变量中第k个非基变量取值为1，其它为0。令kkbxxxˆˆ，其中0kx。由于0x，可知对任意0kx，0ˆx，且满足bBNxBxNB11和xcxcˆ。当x时，kkxxcxcˆ。第41页定理2.3.3令)0,,0,1,0,,0,(ˆ1kkABb其基变量取值为。非基变量中第k个非基变量取值为1，其它为0。令kkbxxxˆ，其中0kx。为了保证0ˆkkbxxx，即要求对于.1kAB的正分量0)(ˆ1ikikABa，满足0ˆkikixab，其中iibBb)(1。因而kikixabˆ/，令},...,2,1,0ˆˆ/min{miaabikiki，令kbxxˆˆ则显然x是个可行解。在原基阵中以第k列替代第i列，则显然所得子阵可逆，所以x是个基可行解。其对应的目标函数值xcxcxckˆ。第42页算法步骤step1找一个初始可行基step2求出典式和检验数step3求},...,2,1max{njjkstep4如果0k则该基可行解就是最