第二章 线性规划 山大刁在筠 运筹学讲义

第二章线性规划教学重点：线性规划可行区域的几何结构，基本可行解及可行区域的基本定理，单纯形方法，两阶段法，对偶和对偶理论，灵敏度分析。教学难点：线性规划可行区域的几何结构，基本可行解及可行区域的基本定理，单纯形方法，两阶段法，对偶性，灵敏度分析。教学课时：24学时主要教学环节的组织：首先通过各种形式的例子归纳出线性数学规划的一般形式，然后在详细讲解主要内容的基础上，尽可能以图形和例题的形式给以形象的说明，使学生对知识点有更直观、具体的认识。再通过大量习题巩固知识，也可以应用软件包解决一些实际问题。第一节线性规划问题教学重点：线性规划问题的实例，线性规划的一般形式、规范形式和标准形式教学难点：线性规划一般形式转换成标准形式。教学课时：2学时主要教学环节的组织：首先通过几个实例总结出线性规划问题的一般形式，再介绍如何将一般形式转换成标准形式。1、线性规划问题举例生产计划问题某工厂用三种原料生产三种产品，已知的条件如下表所示，试制订总利润最大的生产计划单位产品所需原料数量（公斤）产品Q1产品Q2产品Q3原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000单位产品的利润（千元）354可控因素(所求变量)：设每天生产3种产品的数量分别为321,,xxx.目标：使得每天的生产利润最大，就是使得利润函数：321453xxx达到最大.受制条件：每天原料的需求量不超过可用量：原料1P：15003221xx原料2P：8004232xx原料3P：2000523321xxx蕴含约束：产量为非负数0,,321xxx模型321453maxxxx15003221xxs.t.8004232xx2000523321xxx0,,321xxx运输问题一个制造厂要把若干单位的产品从两个仓库2,1;iAi发送到零售点4,3,2,1;jBj，仓库iA能供应的产品数量为2,1;iai，零售点jB所需的产品的数量为4,3,2,1;jbj。假设供给总量和需求总量相等，且已知从仓库iA运一个单位产品往jB的运价为ijc。问应如何组织运输才能使总运费最小？求解设(1,2,1,2,3,4)ijxij表示从仓库iA运往零售点jB的产品数量。模型：min2141ijijijxc2,1;4321iaxxxxiiiiis.t.4,3,2,1;21jbxxjjj4,3,2,1,2,1;0jixij2、线性规划模型112211221122min;1,2,...,;1,...,..0;1,2,...,;1,,nniiinniiiinnijjzcxcxcxaxaxaxbipaxaxaxbipmstxjqxjqn无限制njxj,...,2,1;为待定的决策变量，),,,(21ncccc为价值向量，njcj,...,2,1;为价值系数，),...,,(21mbbbb为右端向量，矩阵1111nmmnaaAaa为系数矩阵线性规划模型的概念可行解（或可行点）：满足所有约束条件的向量),,(21nxxxx可行集（或可行域）：所有的可行解的全体}0,{xbAxxD最优解：在可行域中目标函数值最大（或最小）的可行解，最优解的全体称为最优解集合DyycxcDxO,{}最优值：最优解的目标函数值Oxxcv,线性规划解的情况：无解或不可行}0,{xbAxxD无界D但目标函数在可行域上无界有最优解D且目标函数在D上有有限的现象规划模型的规范形式和标准形式：规范形式：min..0cxAxbstx标准形式：min..0cxAxbstx形式转换一般形式转换成规范式：等式化成不等式：ininiibxaxaxa2211ininiibxaxaxa2211ininiibxaxaxa2211自由变量化成非负变量：令自由变量jjjxxx，其中jjxx,为非负变量ininiibxaxaxa22110,2211iiininiisbsxaxaxa或ininiibxaxaxa22110,2211iiininiisbsxaxaxa目标函数的最大问题向最小问题的转换xcxcminmax例：将下述问题转换成标准形式：052222..21max1212121xxxxxxxtsxxz解：7,6,5,4,3,1;05)(2)(22)(2..)(min743164315431431ixxxxxxxxxxxxxtsxxxzi第二节可行域与基本可行解教学重点：线性规划问题的图解法，可行区域的几何结构和线性规划基本定理。教学难点：线性规划的基本定理。教学课时：4学时主要教学环节的组织：首先通过图解法求出两个变量时可行区域的结构和最有点的位置，再进行一般情况下可行区域的结构进行讨论，得到线性规划的基本定理。1、图解法对于只有两个变量的线性规划问题可以用图解法求解：变量用直角坐标系中的点表示，约束条件用坐标系中的半空间或直线的交表示，可行区域是一个凸多面体，目标函数用一组等值线表示，沿着增加或减少的方向移动，与可行域最后的交点就是最优解。例1、052222..max121212121xxxxxxxtsxxz2221xx2221xx521xx例2、若将例2.2.1中的目标函数改为求1242zxx的最小值当目标函数改变后，等值线的方向会发生改变，如果等值线与某个约束对应的函数直线平行，则该函数值线上的所有可行解都是最优解最优解（1，4）2221xx2221xx目标函数值可能出现的情况：1、可行域是空集；2、可行域无界无最优解；3、最优解存在且唯一，则一定在顶点上达到；4、最优解存在且不唯一，一定存在顶点是最优解。从图解法的几何直观易得：线性规划的可行域是若干个半平面的交集，它形成了一个有界或无界的凸多边形。对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。2、可行区域的结构定义2.2.1：设nRS是n维欧氏空间的点集，若对任意,xSyS的和任意[0,1]都有(1)xyS就称S是一个凸集。定理2.2.1：线性规划的可行域}0,{xbAxxD是凸集证明：略。定理2.2.2：任意多个凸集的交还是凸集定义2.2.2：超平面}{bxaRxHn半空间}{bxaRxHn；}{bxaRxHn定义2.2.3：多面凸集},...,2,1;;,...,2,1;{qpppibxapibxaRxSiiiin定义2.2.4：设S为凸集Sx，如果对任意Szy,和10，都有zyx)1(,则称x为S的顶点。基本可行解令),(NBA，其中B为A的一个满秩子方阵，x=(Bx,Nx)。最优解（1，4）521xxbAx分块bNxBxNB左乘1BbBNxBxNB11即NBNxBbBx11Nx=001bBx定义2.2.5：设B是秩为m的约束矩阵A的一个m阶满秩子方阵，则称B为一个基（或基阵）；B中m个线性无关的列向量称为基向量，变量x中与之对应的m个分量称为基变量，其余的变量为非基变量，令所有的非基变量取值为0，得到的解01bBx称为相应于B的基本解。当01bB则称基本解为基本可行解，这时对应的基阵B为可行基。如果01bB则称该基可行解为非退化的，如果一个线性规划的所有基可行解都是非退化的则称该规划为非退化的。定理2.2.3可行解x是基本可行解的充要条件是它的正分量所对应的矩阵A中列向量线性无关。证明：不妨设1(,,,,0,0),0,1,,Tkjxxxxjk.若x是基本可行解，则取正值的变量对应的列向量1,,KAA，为基向量，故线性无关.反之，若1,,KAA线性无关，则有1,kjjjxAbkm.若km，则有1(,,)KBAA为基.x为基可行解；若km，则可从其余nk个列向量中再挑选mk列向量与1,,KAA组成基，易知，x为基可行解.定理2.2.4x是基本可行解的充要条件是x是可行域D的顶点。定理2.2.5一个标准的LP问题如果有可行解，则至少有一个基本可行解证明：设.0x是任意一个可行解，则有00,0Axbx.不妨设00,1,,jxjk；后nk个向量为0.若1,,kAA线性无关，则由定理2.2.3知0x是基本可行解；否则存在不全为零的j，使得10kiijA，补充0,1,,llkn得，满足0A.定理2.2.6一个标准的LP问题如果有有限的最优值，则一定存在一个基本可行解是最优解。证明：设0x是一个最优解，如果0x是基本可行解，则问题得证；否则按定理2.2.5的证明可得到0x和0x，由00TTTcxccx和00TTTcxccx知0Tc，故有00()TTcxcx.按照定理2.2.5的证明方法迭代，最终可得到基本可行解x，满足0TTcxcx.第三节单纯型方法教学重点：单纯形算法和单纯形表。教学难点：单纯形算法，单纯形表。教学课时：4学时主要教学环节的组织：首先给出单纯形算法，然后给出单纯形算法的一种实现手段，单纯形表。1、单纯型方法考虑标准形式的线性规划问题min..0cxAxbstx其中nmmnRARbRcx,,,，并且假定nm且可行域}0,{xbAxRxDn，系数矩阵A是行满秩的，即mAr)(。给定一个非退化的基本可行解x，对应的可行基为B，则等式约束AX=b可以变为：011bBNxBxNB--------典式或NBNxBbBx11此时令0Nx，则1BxBb.所以100BNxBbxx.目标函数NNBBxcxcxcNNNBxcNxBbBc)(11NNBBxcNBcbBc)(11令NBNcNBc1，0B，则xbBcxcB1规划等价于0..min111xbBNxBxtsxbBcNBB定理2.3.1（最优性准则）如果0，则基可行解x为原问题的最优解。证：设x为原问题的任一可行解。由于0x，而0，所以0Tx.从而00TTTcxzxzcx.定理2.3.2如果向量的第k个分量0k，而向量01kAB，则原问题无界。证明：令0kkAde，其中ke是第k个分量为1，其余分量为0的n维向量.因为0kA，所以有0d，而(,)00kkAAdBNAe对于充分大的正数，观察向量xd，此时有()0Axdbxd它所对应的目标函数值为()()TTTTTTBkkkcxdcxcdcxcAccx由于0k，而0可任意的大，故原问题目标函数无下定理2.3.3对于非退化的基本可行解x，若向量的第k个分量0k，而向量.1kAB至少有一个正分量，则可以找到一个新的基本可行解xˆ使得xcxcˆ。证明：只需将ˆx具体的找出来.令0kkAde满足0Ad令ˆ0kkbAxxde下面证明，当适当选取0后，ˆx即为所求.显然，ˆAxAxAdb，为使ˆ0x，则要求0kbA，所以令min0,1,,irikikrkbbaimaa定定理理22..33..33的的一一些些说说明明::11、、检检验验数数向向量量：：T1TTBcBAc