第二章线性规划基本内容总结

第二章线性规划与单纯形法2.1线性规划的基本概念2.2单纯形法2.3单纯形法的进一步探讨2.4使用计算机软件求解线性规划2.5应用举例2.6案例2.1线性规划的基本概念2.1.1线性规划的数学模型2.1.2线性规划的图解法2.1.3线性规划的标准型2.1.4基可行解2.1.1线性规划的数学模型例1（生产计划问题）某工厂在计划期内要安排生产A、B两种产品（假定产品畅销）。已知生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗，如表2-1所示。问应如何安排生产使该厂获利最大？产品A产品B资源限额劳动力94360工时设备45200台时原材料310300公斤单位产品利润（元）70120解：设21,xx分别表示在计划期内产品A、B的产量0,3001032005436049..12070max2121212121xxxxxxxxtsxxz例2（营养问题）某公司饲养实验用的动物以供出售。已经知道这些动物的生长对饲料中的三种营养元素特别敏感，我们分别称它们为营养元素A、B、C。已求出这些动物每天至少需要700克营养元素A，30克营养元素B，而营养元素C的每天需要量刚好是200毫克，不够和过量都是有害的。现有五种饲料可供选用，各种饲料每千克所含的营养元素及单价如表2-2所示。为了避免过多使用某种饲料，规定混合饲料中各种饲料的最高含量分别为50、60、50、70、40千克。要求确定满足动物需要而费用最低的饲料配方。饲料营养元素A（克）营养元素B（克）营养元素C（毫克）价格（元/千克）1310.52220.517310.20.24462295180.50.85解：设5,,1jxj为每天混合饲料内包含的第j种饲料的千克数，则营养问题的模型为：5,,1,040,70,50,60,502008.022.05.0305.022.05.070018623..59472min5432154321543215432154321jxxxxxxxxxxxxxxxxxxxxxtsxxxxxzj例3（人员安排问题）某医院根据日常工作统计，每昼夜24小时中至少需要下列数量的护士。序号时段护士的最少人数16:00-10:0060210:00-14:0070314:00-18:0060418:00-22:0050522:00-2:002062:00-6:0030护士们分别在各时段开始时上班，并连续工作8小时，问应如何安排各个时段开始上班工作的人数，才能使护士的总人数最少？解：设第j时段开始上班的人数为6,,1,jxj，则6,,10603020506070..min166554433221654321jxxxxxxxxxxxxxtsxxxxxxzj且为整数，线性规划模型的一般形式3.2,,1,0,2.2,,..2.1minmax221122222121112121112211njxbxaxaxabxaxaxabxaxaxatsxcxcxczjmnmnmmnnnnnn或其中，z称为目标函数，（2.2）、（2.3）称为约束条件，（2.3）也称为变量的非负约束条件，在线性规划软件一般是默认的。线性规划问题隐含的假设（1）比例性假设（2）可加性假设（3）可分性假设（4）确定性假设2.1.2线性规划的图解法线性规划问题解的情况（1）唯一最优解（2）无穷多最优解（3）无界解（4）无可行解（1）唯一最优解（例1）0,3001032005436049..12070max2121212121xxxxxxxxtsxxz30010321xx2005421xx3604921xx40(0,30)90100(40,0)(50,0)0B(20,24)C(1000/29,360/29)DAE1x2x在B点获得最大值，z=4280（2）无穷多最优解0,3001032005436049..5.8270max2121212121xxxxxxxxtsxxz30010321xx2005421xx3604921xx40(0,30)90100(40,0)(50,0)0B(20,24)C(1000/29,360/29)DAE1x2x在线段BC上任意一点都使z取得相同的最大值（3）无界解0,6232..max21212121xxxxxxtsxxz62321xx221xx1x2x02134-1-2123（4）无可行解0,603001032005436049..12070max212121212121xxxxxxxxxxtsxxz30010321xx2005421xx3604921xx40(0,30)90100(40,0)(50,0)0B(20,24)C(1000/29,360/29)DAE1x2x6021xx二维线性规划的两个几何特征（1）若可行域非空，它是一个凸集。（2）若线性规划存在最优解，它一定可在可行域的某个顶点（极点）得到。凸集定义2.2.1：设nRS是n维欧氏空间的点集，若对任意SySx,的和任意]1,0[都有就称S是一个凸集。定义2.2.2：设S为凸集Sx，如果对任意Szy,和10，都有zyx)1(,则称x为S的顶点。定理2.2.1线性规划的可行域}0,{xbAxxD是凸集定理2.2.2任意多个凸集的交还是凸集Syx)1(问题1.可行域顶点的个数是否有限？2.最优解是否一定在可行域顶点上达到？3.如何找到顶点？4.如何从一个顶点转移到另一个顶点?2.1.3线性规划的标准型（SLP）0,,,..max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz其中右端项0ib。SLP的简写2.6,,2,1,02.5,,2,1,..2.4max11njxmibxatsxczjinjjijnjjj引入TnxxxX,,,21，ncccC,,,21，Tnbbbb,,,21，nmijaA（m×n阶矩阵），TnjjjaaaP,,,21（矩阵A的第j列）则SLP的矩阵描述：0..maxXbAXtsCXzSLP的向量描述：njxbxPtsCXzjnjjj,,2,1,0..max1一般称C为价值向量，b为资源向量，A为技术系数矩阵。转化成标准型的方法1．最小化问题的转化（改变目标函数的符号）。2．不等式约束的处理（1）对小于等于约束加上松弛变量化为等式。（2）对大于等于约束减去剩余变量化为等式。3．非正变量与符号无限制变量的处理。（1）若0kx，令kkxx（2）若kx为符号无限制变量，则kkkxxx，其中0,kkxx。例10,3001032005436049..12070max2121212121xxxxxxxxtsxxz标准化后0,,3001032005436049..12070max5152142132121xxxxxxxxxxxtsxxz例2符号无限制321321321321321,0,0533229..32minxxxxxxxxxxxxtsxxxz解：令zz，11xx，543xxx，其中0,54xx，则标准化后有0,,,,,5333229..332max765421542175421654215421xxxxxxxxxxxxxxxxxxxxtsxxxxz补充练习1符号无限制423143132143214321,0,0,x12285327..32maxxxxxxx-xxxxxxxtsxxxxz补充练习1符号无限制423143132143214321,0,0,x12285327..32maxxxxxxx-xxxxxxxtsxxxxz解：令44422,xxxxx化为标准形式为：0,,,,,,122285327..0032max6544321644313215443216544321xxxxxxxxxxxxxxxxxxxxxtsxxxxxxxz补充练习2613032632s.t.2max21321321321xxxxxxxxxxxz解：令122xx，333xxx，则标准形式为0,,,,,,,6133126312s.t.21max76543321726153321433213321xxxxxxxxxxxxxxxxxxxxxxxxxxz化简后得0,,,,,,,73424332s.t.122max76543321726153321433213321xxxxxxxxxxxxxxxxxxxxxxxxxxz2.1.4基可行解基可行解令),(NBA，TNBNBxxxxx,bAx分块bNxBxNB左乘1BbBNxBxNB11即NBNxBbBx11Nx=001bBx定义设B是矩阵A中的一个m×m阶非奇异子矩阵（即B的行列式0B），则称B为一个基；B中m个线性无关的列向量称为基向量，变量x中与之对应的m个分量称为基变量，其余的变量为非基变量，令所有的非基变量取值为0，得到的解01bBx称为相应于B的基解。当01bB则称基本解为基可行解，这时对应的基阵B为可行基。如果01bB则称该基可行解为非退化的，如果一个线性规划的所有基可行解都是非退化的则称该规划为非退化的。例6求下列标准线性规划的两个基可行解（例1）0,,3001032005436049..12070max5152142132121xxxxxxxxxxxtsxxz解：这里m=3，n=5。约束方程组的系数矩阵为54321,,,,1001030105400149PPPPPA易见100010001,,543PPP为一个基。令非基变量0,21xx，由方程组可解出3603x，2004x，3005x，因此得到基解TX300,200,360,0,00，也是基可行解。另外，1010015004,,542PPP也是一个基。令非基变量0,31xx，由方程组可解出902x，2504x，6005x，可得到相应的基解TX600,250,0,90,01，但不是基可行解。又0010105014,,432PPP也是一个基，相应的基解TX0,50,240,30,02，也是基可行解。结论（1）SLP的基可行解对应于其可行域的顶点（极点）。（2）若SLP有最优解，则必有最优基可行解。练习：求下列标准线性规划的一个基可行解。5,4,3,2,1;052222..min52142132121jxxxxxxxxxxtsxxzj系数矩阵100110102100112A基阵为1000100011B