1.线性规划与单纯形方法.ppt

第一章 线性规划与单纯形法 本章框架 第一节 线性规划问题及数学模型 一、实例 二、线性规划问题（Linear Programming）的共同特征 线性规划模型的紧缩形式 练习题：是否线性规划模型？ 三、两变量线性规划问题的图解法 例4 例5 用图解法求解线性规划问题 例6 用图解法求解线性规划问题 例7 用图解法求解线性规划问题 例8 用图解法求解线性规划问题 3.图解法的作用 图解法的基本步骤： 1．在直角坐标系作出可行域S的区域（一般是一个凸多边形）； 2．作目标函数等值线：c1x1+c2x2=z 3．对于max问题，让目标函数值z由小变大，即让等值线进行平移，若它与可行域S最后交于一个点（一般是S的一个顶点），则该点就是所求的最优点，若与S的一条边界重合，此时边界线上的点均是最优点 4．将最优点所在的两条边界线所代表的方程联立求解，即得最优解X*，把最优解X*带入目标函数，得最优值Z*=CX* 注意：若是求目标函数最小值，等值线向反方向移动 关于线性规划问题的结论 若LP问题有可行解，则可行域是一个凸多边形（或凸多面体）。它可能是有界的，也可能是无界的； 若LP问题有最优解，则最优解可能是唯一的，也可能是无穷多个。如果是唯一的，这个解一定在该凸多边形的某个顶点上，如果是无穷多个，则这些最优解一定是多边形的一条边界线（包括此边界的两个顶点）； 若LP问题有可行解，但没有有限最优解，此时凸多边形是无界的； 若LP问题没有可行解，则该问题没有最优解。 四、线性规划问题的标准型 2.线性规划标准型的紧缩形式 4.所有LP问题均可化为标准型 4.所有LP问题均可化为标准型 例10 化标准型 例11 化标准型 课堂练习 五、标准型LP问题解的概念 B1=(P1,P2)：基 线性规划标准型问题解的关系 六、可行解、基解和基可行解举例 例13 第二节 线性规划的基本理论 判断以下图形哪些是凸集，哪些不是凸集？ 二、基本定理 定理3 若可行域有界，则LP问题的目标函数一定可以在其可行域的顶点上达到最优。 线性规划问题的可行域是凸集(定理1)；凸集的顶点对应于基可行解(定理2)，基可行解(顶点)的个数是有限的；若线性规划有最优解，必在可行域某顶点上达到(定理3)。因此,我们可以在有限个基可行解中寻找最优解。 第三节 单纯形法 二、枢轴运算 单纯形法举例（P20） 用非基变量表示基变量： 三、检验数的意义 对于线性规划问题：Max Z=CTX AX=b，X≥0，可用如下三个判别定理来判别线性规划问题是否已经获得最优解或为无界解。 判别定理1 设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≤0，则X为线性规划的最优解。 判别定理2 设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj ≤0，同时有某个非基变量的检验数σk=0( k∈J)，则该线性规划有无穷多最优解。 判别定理3 设X为线性规划的一个基可行解，若有σk0 ( k∈J) ，且pk≤0，即aik ≤0（i=1,…,m），则该线性规划问题具有无界解（无最优解）。 第四节 单纯形法的步骤 1.初始单纯形表 x1 +a1, m+1 x m+1 + … +a1n x n= b1 x2 +a2, m+1 x m+1 + … +a2n x n= b2 … … xm +am, m+1 x m+1 + … +amn x n= bm 对于上述单纯形表： （1）一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。 （2）从初始单纯形表中，可立即得到一个基可行解： x1=b1, x2=b2, …, xm=bm , xm+1=xm+2= … =xn= 0 （3）用检验数的计算公式很容易计算检验数，并可根据三个判别定理判别上述基可行解是否为最优解或线性规划问题无最优解。 2.进基变量的选择 3.出基变量的选择 4.旋转运算 二、实例 单纯形表算法 对于极小化问题，其最优解的判定定理和进基变量的选取和极大化问题刚好相反，如下所示： 判别定理1 设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≥0，则X为线性规划的最优解。 判别定理2 设X为线性规划的一个基可行解，且对于一切j∈J（J为非基变量的下标集）有σj≥0，同时有某个非基变量的检验数σk=0( k∈J)，则该线性规划有无穷多最优解。 判别定理3 设X为线性规划的一个基可行解，若有σk0 ( k∈J) ，且pk≤0，即aik ≤0（i=