最优化理论与方法课件.ppt

《最优化理论与方法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划求解单纯形法针对的问题（LP标准型）基本概念:凸集：给定集合，若对任意均有，即连接两点的线段仍在集合内，则称集合为凸集。如：矩形，圆，四面体等均为凸集，圆环，空心球等不是凸集。基本概念：极点：若凸集中的点不能成为中的任何线段的内点，则称为的极点，即对任意不存在，使，则称为的极点。如三角形的顶点为极点；圆的圆周也为极点。线性规划问题的可行域若不是空集，则极点个数一定是有限个。基本概念基本解：在个变量，个方程的方程组中，若为的任意一个秩为的非奇异子方阵，且将不与的列对应的个变量置0，则求得的解就称为的一个基本

2、解。称为线性规划问题的一个基。记为其中称为基向量，对应的变量称为基变量，置0的变量称为非基变量，对应的向量也称为非基向量。例：求约束方程的基本解x1x2x3x4是否可行解006016是01006是016-360否2000-24否80360是4800是基本概念：基本可行解：满足非负条件的基本解叫基本可行解。基本最优解：使目标函数值最大的基本可行解称为基本最优解。定理1：线性规划问题的可行域D是凸集。定理2：设D是可行域，则是基本可行解的充要条件是为D的极点。定理3：若LP问题有最优解，则目标函数的最大值一定可在某个

3、极点上找到。小结：LP问题的可行域是个凸集；最优解在极点。为什么要介绍单纯形法？求解线性规划问题如何求第一个基本可行解？即令为非基变量，若令非基变量为0，则求出的一组解为基本可行解这个基本可行解是最优解吗？（将目标函数用非基变量表示，判断是否最优）的系数为正，当增大时，将增大，不是最优解怎么办？寻找下一个基本可行解显然，要成为基变量，称为“进基变量”，基变量总数为2，进一个必定要出一个，那么如何决定出基变量？出基变量的判定：希望越大越好，能不能无穷大？还是非基变量，仍然设定为0，有谁先被挤出去？新的基本可行解：基

4、变量：非基变量：基本可行解为是最优解吗？有是最优解，最优值单纯形法步骤总结求基本可行解判定是否最优结束寻找新的基变量和非基变量是否单纯形表第一个极点处基变量bix1x2x3x4比值检验x1610-336/3=2x2401-844/4=1f20003-1第二个极点处基变量bix1x2x3x4x131-3/430x4101/4-21f2101/410考虑一般情况线性规划标准型目标函数表示为非基变量初始单纯形表？（讨论）用单纯形表求解LP问题举例。使用ExcelSolver求解LP问题。