《线性规划求解》PPT课件.ppt

《《线性规划求解》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、线性规划的求解LinearProgramming二维线性规划的图解法2.线性规划的单纯形法2006/081---第1章线性规划---1.1.4线性规划问题解的有关概念设模型nmaxz=cjxjj=1ns.t.aijxj=bi（i=1,2,……,m)j=1xj≥0（j=1,2,……,n)（1）可行解：满足所有约束方程和变量符号限制条件的一组变量的取值。（2）可行域：全部可行解的集合称为可行域。（3）最优解：使目标函数达到最优值的可行解。2006/082---第1章线性规划---（4）基：设A为线性规划模型约束条件系数矩阵（mn，m

2、

3、B

4、≠0，则称B为该线性规划模型的一个基。（5）基变量：基中每个向量所对应的变量称为基变量。（6）非基变量：模型中基变量之外的变量称为非基变量。（7）基解（基解）：令模型中所有非基变量X非基=0后，由模型约束方程组naijxj=bi(i=1,2,……,m)得到的一组解。j=1（8）基本可行解（基可行解）：在基解中，同时又是可行解的解称为基可行解。（9）可行基：对应于基可行解的基称为可行基。2006/083---第1章线性规划---Maxz=2x1+3x2st.x1+x2≤3x1+2x2≤4x1,x2

5、≥0Maxz=2x1+3x2+0x3+0x4st.x1+x2+x3=3x1+2x2+x4=4x1,x2,x3,x4≥0A=x1x2x3x411101201可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T等。设B=1001，令，则

6、B

7、=1≠0,令x1=x2=0，则x3=3,x4=4，X=(0,0,3,4)T例：x3x4——基变量令B=1110x1x3，则令x2=x4=0，则x3=-1,x1=4，X=(4,0,-1,0)T

8、B

9、=-1≠0,——非基本可行解——基本可行解标准化2006/084---第1章线性规划---

10、复习思考题：1.可行解和可行域有怎样的关系？2.一个标准化LP模型，最多可有多少个基？3.基解是如何定义的？怎样才能得到基解？4.可行解、基解、基可行解三者之间有什么关系？在LP模型中是否一定存在？5.什么是可行基？2006/085---第1章线性规划---1.2线性规划问题的图解方法*利用作图方法求解。例：maxz=2x1+3x2s.t2x1+2x212----------①x1+2x28----------②4x116----------③4x212----------④x10,x202006/086---第1章线性规

11、划---x1x222468460①②④③Z=6Z=0(4,2)Zmax2006/087---第1章线性规划---AAB唯一解无穷多解无界解无可行解2006/088---第1章线性规划---步骤：（1）作平面直角坐标系，标上刻度；（2）做出约束方程所在直线，确定可行域；（3）做出一条目标函数等值线，判定优化方向；（4）沿优化方向移动，确定与可行域相切的点，确定最优解，并计算最优值。讨论一：模型求解时，可得到如下几种解的状况：（1）唯一最优解：只有一点为最优解点，简称唯一解；（2）无穷多最优解：有许多点为最优解点，简称无穷多解；（3

12、）无界最优解：最优解取值无界，简称无界解；（4）无可行解：无可行域，模型约束条件矛盾。讨论二：LP模型求解思路：（1）若LP模型可行域存在，则为一凸形集合；（2）若LP模型最优解存在，则其应在其可行域顶点上找到；（3）顶点与基本解、基本可行解的关系：2006/089---第1章线性规划---复习思考题：1.LP模型的可行域是否一定存在?2.图解中如何去判断模型有唯一解、无穷多解、无界解和无可行解？3.LP模型的可行域的顶点与什么解具有对应关系？4.你认为把所有的顶点都找出来，再通过比较目标函数值大小的方式找出最优解，是否是最好的算法？

13、为什么？2006/0810---第1章线性规划---1.3单纯形法的基本原理（SimplexMethod）1.3.1两个概念：（1）凸集：对于集合C中任意两点连线上的点，若也在C内，则称C为凸集。或者，任给X1C，X2C，X=X1+(1-)X2C(0<<1)，则C为凸集。凸集非凸集2006/0811---第1章线性规划---（2）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。或者，设C为凸集，对于XC，不存在任何X1C，X2C，且X1≠X2，使得X=X1+(1-)X2C，(0<<1)，则X为凸集顶点。X

14、XXXX2006/0812---第1章线性规划---定理1：若线性LP模型存在可行解，则可行域为凸集。证明：设maxz=CXst.AX=bX0并设其可行域为C，若X1、X2为其可行解，且X1≠X2，则X1C，X2C