运筹学-第一章-单纯形法基本原理

1、单纯形法基本原理,窦志武,云南财经大学 物流学院,连接几何形体中任意两点的线段仍完全在该几何形体之中。 有限个凸集的交集仍然是凸集。,单纯形法基本原理,单纯形法基本原理,凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。,顶点：如果凸集C中不存在任何两个不同的点X1，X2，使X成为这两个点连线上的一个点,单纯形法基本原理,定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。 定理2：线性规划问题的基可行解X对应可行域(凸集)的顶点。 定理3：若问题存在最优解，一定存在一个基可行解是最优解。（或在某个顶点取得）,单纯形法的计算步骤,单纯形法的思路,找出

2、一个初始可行解,是否最优,转移到另一个基本可行解 （找出更大的目标函数值）,最优解,是,否,循 环,核心是：变量迭代,结束,四、单纯形法的迭代原理 1、确定初始基可行解 (1)初始可行基的确定 观察法观察系数矩阵中是否含有现成的单位阵？ LP限制条件中全部是“”类型的约束 将新增的松弛变量作为初始基变量，对应的系数列向量构成单位阵；,单纯形法基本原理,先将约束条件标准化，再引入非负的人工变量， 以人工变量作为初始基变量，其对应的系数列向量构成单位阵，称为“人造基”； 然后用大M法或两阶段法求解；,线性规划限制条件都是“”或“=”类型的约束,单纯形法基本原理,使约束方程的系数矩阵中出现一个单位阵

3、，用单位阵的每一个列向量对应的决策变量作为“基变量”，这样，出现在单纯形表格中的B(i)列（即约束方程的右边常数）值正好就是基变量的取值。,单纯形法基本原理,如果限制条件中既有“”类型的约束，又有“”或“=”类型的约束，怎么办？ 构造单位阵,问题,初始可行基一定要选单位阵？ b列正好就是基变量的取值，因此称b列为解答列,单纯形法基本原理,（2）写出初始基可行解 令非基变量取0，基变量对应b(i)，一起构成初始基可行解,单纯形法基本原理,此时LP的标准型为,单纯形法基本原理,在约束条件中的变量系数矩阵中总会有一个单位矩阵 初始可行基 ：,当线性规划的约束条件均为，其松弛变量的系数矩阵为单位矩阵；

4、当线性规划的约束条件均为或=，为便于找到初始基可行解，构造人工变量，人为产生一个单位矩阵。,单纯形法基本原理,初始基本可行解：,式中p1,pm 为基变量,同其所对应的x1,x2,.,xm为基变量；其它变量xm+1,xm+2，,xn为非基变量。令所有的非基变量等于零。,单纯形法基本原理,定义：两个基可行解称为相邻的，如果它们之间变换 且仅变换一个基变量。 初始基可行解的前m个为基变量，,2、基变换,代入约束条件有,单纯形法基本原理,系数矩阵的增广矩阵,因为p1,pm,是一个基，其他向量pj可以这个基的线性组合表示：,单纯形法基本原理,相减，然后乘上一个正数,加上,经过整理得到：,找到满足约束方程

5、组,的另一点：,第j个大于0 只变换1个变量； 前m个变量必须换出1个,单纯形法基本原理,其中是X（1）的第j个坐标的值，要使X（1）是一个基可行解，对所有的i=1,m,存在,令这m个不等式至少有一个等号成立，当,单纯形法基本原理,是一个可行解。因为变量 x11, x21, xl-11, xl+11,xm1, xj1所对应的向量， 经过重新排列后加行b列形成的增广矩阵为：,L,alj(1/alj)=1,rL(-al-1j) +rL-1,0,-(bL/aLj)+bL-1,单纯形法基本原理,所以，P1,P2,Pl-1,Pj,Pl+1,Pm,是一个基。 进行初等行变换，将第L行乘上1/alj,再分别

6、乘以 -aij,(i=1,l-1,l+1,m)加到各行，增广矩阵 的左边变成一个单位矩阵，,单纯形法基本原理,将 代入目标函数计算：,单纯形法基本原理,最优性判别,、如果所有的检验数，表明现有的顶点对应的基可行解为最优解。 、当所有的检验数，又对某个非基变量xj的检验数等于 0，并且可以找到0,这表明可以找到一个顶点目标函数达到最大，说明LP有无穷多个最优解。 、如果存在某个检验数0,又0, 表明目标函数达到无限，说明LP有无界解。,单纯形法基本原理,单纯形法的计算步骤,单纯形表,单纯形法的计算步骤,例1.12 用单纯形法求下列线性规划的最优解,解：1）将问题化为标准型，加入松驰变量x3、x4

7、则标准型为:,单纯形法的计算步骤,2）求出线性规划的初始基可行解，列出初始单纯形表。,检验数,单纯形法的计算步骤,3）进行最优性检验,如果表中所有检验数 ，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。,4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表,确定换入基的变量。选择 ，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即： ，其对应的xk作为换入变量。 确定换出变量。根据下式计算并选择 ，选最小的对应基变量作为换出变量。,单纯形法的计算步骤,用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新

8、的基可行解，并相应地可以画出一个新的单纯形表。 5）重复3）、4）步直到计算结束为止。,单纯形法的计算步骤,换入列,bi /ai2，ai20,40,10,换出行,将3化为1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,乘以3/5后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,单纯形法的计算步骤,例1.13 用单纯形法求解,解：将数学模型化为标准形式：,不难看出x4、x5可作为初始基变量，列单纯形表计算。,单纯形法的计算步骤,20,x2,2,1/3,1,5,0,1,20,75,3,0,17,1,3,1/3,0,9,0,2,25,60,x1,1,1,0,17/3,1/3,1,25,0,1,28/9,-1/9,2/3,35/3,0,0,-98/9,-1/9,-7/3,变成标准型,单纯形法的计算步骤,例1.14 用单纯形法求解,约束方程的系数矩阵,为基变量,为非基变量