运筹学课件1-3单纯形法原理

《运筹学课件1-3单纯形法原理》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、§1.3单纯形法原理理论方法算法步骤单纯形表算例一、基本概念可行解：满足AX=b,且X≥0的解称为可行解。最优解：使目标函数达到最大值的可行解称为最优解。其中A为m×n阶矩阵基：设B是系数矩阵A的一个m×n阶的满秩子矩阵，称B是(LP)的一个基。可行域：全部可行解的集合称为可行域。基本概念不失一般性，设B中每一个向量称为基向量，与基向量对应的变量称为基变量,其余的变量称为非基变量.基解：令所有的非基变量为零所得到的唯一的解基可行解：满足非负约束条件X≥0的基解可行基：对应与基可行解的基求解m×m的线性方程组，令非基变量等于0，得到基变量的一组解，连同等于0的非基变量这n个变量

2、的值称为线性规划的一个基解如果一个基解中的所有变量都是非负的这个基解称为基可行解。例1考虑问题系数矩阵基maxZ=2x1+3x2+x3s.t.x1+x3＝5x1+2x2+x4＝10x2+x5＝4xi≥0(i=1,…5)例2x1x2x3x4x5Z是否为基可行解？10051045204520173500541040550－120√√√×maxZ=2x1+3x2+x3s.t.x1+x3＝5x1+2x2+x4＝10x2+x5＝4xi≥0(i=1,…5)x1x2x3x4x5Z是否为基可行解？5100－50415652.5001.517.57540－302282430019例2×√×√至

3、少n-m个问：基解中零的个数至少有多少个？maxz=x1+2x2s.t.x1+x23x21x1,x20maxz=x1+2x2s.t.x1+x2+x3=3x2+x4=1x1,x2,x3,x40x1=0,x2=0x3=3,x4=1基可行解x1=0,x4=0x2=1,x3=2基可行解x2=0,x3=0x1=3,x4=1基可行解x3=0,x4=0x1=2,x2=1基可行解x1=0,x3=0x2=3,x4=-2是基解，但不是可行解OABx3=0x4=0x2=0x1=0CD可行域例3二、凸集和顶点1.凸集：如果集合C中任意两点x1，x2，其连线上的所有点也都是集合C中的点，则称C

4、为凸集，其中x1，x2的连线可以表示为：αx1＋（1－α）x2(0＜α＜1)数学解析式为：任意x1∈C，x2∈C，有αx1＋（1－α）x2∈C(0＜α＜1)，则C为凸集。2.顶点如果集合C中不存在任何两个不同的点x1，x2，使x为这两点连线上的一个点，即对任何不同的x1∈C，x2∈C，不存在x=αx1＋（1－α）x2(0＜α＜1)，则称x为凸集的顶点。凸集和顶点三、几个基本定理定理1线性规划问题的可行域是凸集证：设X1、X2为可行域C内的任意两点,则有故C为凸集对于三、几个基本定理引理线性规划问题的可行解为基可行解的充要条件是它的正分量所对应的系数列向量线性无关。证：(1)必

5、要性设可行解若X为基本可行解，则取正值的变量必是基变量，它们所对应的约束矩阵A中的列向量A1,…,Ak是基向量，故必线性无关。三、几个基本定理引理线性规划问题的可行解为基可行解的充要条件是它的正分量所对应的系数列向量线性无关。证：（2）充分性因为A的秩为m,则可以从其余向量中找构成一个基，其对应的解为X,故X为基可行解.出m-k个与定理2LP的基可行解对应可行域的顶点证(1)充分性：由引理知线性相关,即存在一组不全为零的数,使得假设顶点X不是基可行解,不妨设它的前k个分量为正,则有用反证法2021/10/1615(2)必要性仍用反证法因此X不是基可行解。2021/10/161

6、6定理3若线性规划问题有最优解,一定存在一个基可行解是最优解2021/10/1617总结几个基本定理定理1若线性规划问题存在可行解，则问题的可行域是凸集。引理线性规划问题的可行解X＝(x1,x2,……xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。定理2线性规划问题的基可行解X对应线性规划问题可行域的顶点。定理3若线性规划问题有最优解，一定存在一个基可行解是最优解。问题：1.可行域顶点的个数是否有限？2.最优解是否一定在可行域顶点上达到？3.如何找到顶点？4.如何从一个顶点转移到另一个顶点?maxZ=6x1+5x2x1+3x2≤902x1+x2≤752

7、x1+2x2≤80x1,x2≥0maxZ=6x1+5x2x1+3x2+x3＝902x1+x2+x4＝752x1+2x2+x5＝80xi≥0，i=1,…,5找一个基可行解，X(0)＝（0，0，90，75，80），Z=0(1)Z＝6x1+5x2，x1的系数C1＝6大于C2=5；选择x1为新的基变量。X3=90-(x1+3x2)当x3=0，X2=0时，x1=90X4=75-(2x1+x2)当x4=0，X2=0时，x1=37.5X5=80-(2x1+2x2)当x5=0，X2=0时，x1=40最小选择x4为换出变