单纯形法的计算步骤及应用.ppt

单纯形法的计算步骤及应用 单纯形法的计算步骤及应用 单纯形法介绍及相关问题 单纯形法的策略是从一个已知的初始基本可行解x0（或者说从可行域的某一个顶点）出发，转换到另一个基本可行解（或者另一个顶点）x1，使s(x0)s(x1),再从x1转到x2,依次类推使得s(x0)s(x1)s(x2s(x3)… 直到目标函数达到最大值时就得到最优解。每一次转换称之为一次迭代。由于基本可行解的个数是有限的，所以经过有限次迭代，一定可以达到最优解。 （1）初始基本可行解的确定； （2）怎样由一个基本可行解迭代出另一个基本可行解； （3）怎样确定可以使目标函数有较大上升的基本可行解。 单纯形法介绍及相关问题 1、初始基本可行解的确定 为了确定初始基本可行解，要首先找出初始可行基。一个实际的线性规划问题，经过化成标准型之后，若约束方程的系数矩阵中出现了m个线性独立的单位向量，那么这m个单位向量就可以作为一个初始可行基。比如一个小于等于约束在化为标准型时，每增加一个非负的松弛变量，就会产生一个单位向量，如果所有的约束都是小于等于型，那么产生的单位向量正好为m个。 单纯形法介绍及相关问题 标准型线性规划问题 max s=c1x1+c2x2+…+cnxn s.t. a11x1+a12x2+…+a1nxn=b1 a21x1+a22x2+…+a2nxn=b2 an1x1+an2x2+…+annxn=bn xj≥0(j=1,2,…,n) 单纯形法介绍及相关问题 例1 已知约束如下 3x1-x2≤2 2x1-2x2≤1 -2x1-x2≤3 x1,x2≥0 求基本可行解。 解：化为标准型 3x1-x2+x3=2 2x1-2x2+x4=1 -2x1-x2+x5=3 xj≥0(j=1,2,…,5) 其中 即为一个可行基。 单纯形法介绍及相关问题 如果除了小于等于形式的约束之外还有等于或者大于等于形式的约束，那么，小于等于约束加松弛变量所产生的单位向量就不足m个；对于等式形式的约束，可以采用一个非负的人工变量，也即人为的制造一个单位向量的办法；对于大于等于的约束，在化标准型时减去非负的剩余变量，由于剩余变量所对应的向量不是单位向量，因此，再采用等于约束的处理办法，加上一个人工变量。 单纯形法介绍及相关问题 例2：已知约束如下 x1+x2+x3=5 -6x1+10x2+5x3≤20 5x1-3x2+x3≥15 xj≥0(j=1,2,3) 求一初始可行基。 解：先化为标准型 x1+x2+x3=5 -6x1+10x2+5x3+x4=20 5x1-3x2+x3-x5=15 xj≥0(j=1,2,…,5) 引入人工变量 x1+x2+x3+x6=5 -6x1+10x2+5x3+x4=20 5x1-3x2+x3-x5+x7=15 xj≥0(j=1,2,…,7) 其中x6与x7为两个人工变量， 则下面两向量即为一个初始可行基。 单纯形法介绍及相关问题 根据上述办法，我们总有可以找到m个线性无关的单位向量。构成初始可行基。假如对约束方程经过整理，重新对xj及aij(i=1,2,…,m；j=1,2,…,n)进行编号，总可以得到以下方程组： x1+a1,m+1xm+1+…+a1nxn=b1