第7讲线性规划与单纯形法.pptVIP

前面利用单纯形法的基本原理求解线性规划问题，其计算过程显得比较繁琐，现在我们介绍一种单纯形的列表算法，这一方法可以直观而清楚地表明计算过程．对标准形的线性规划问题不妨设m×m阶的非奇异方阵B是(LP)问题的一个基，为讨论方便，不妨假设A=(B，N)，则方程组（2.51）可等价地变换为第94页，共157页，星期日，2025年，2月5日由于B是非奇异方阵，故B-1存在，有XB+B-1NXN=B-1b，移项得(2.53)再将目标函数（2.50）作相应的变换，将它用非基变量来表示第95页，共157页，星期日，2025年，2月5日则(LP)问题又可等价地写成：我们称式（2.54）~（2.56）为问题(LP)对应于基B的典式．第96页，共157页，星期日，2025年，2月5日在式（2.53）中令XN=0（即全部非基变量取值为零），则得XB=B-1b，当XB=B-1b≥0时，就是初始基B对应的初始基可行解．令σN=CN-CBB-1N,显然，σN就是非基变量XN的检验数．这样，我们可以根据(LP)问题的典式列出一张初始表，称为初始单纯形表．见表2.5.第97页，共157页，星期日，2025年，2月5日表2.5C→CBCNCBXBbXBXNCBXBB-1bIB-1NZ-CBB0CN-CBB-1N第98页，共157页，星期日，2025年，2月5日又因为并记其中，于是，表2.5还可简化为表2.6.第99页，共157页，星期日，2025年，2月5日表2.6C→CCBXBbXCBXBB-1bB-1AZ-CBBC-CBB-1A表2.5的具体表示形式为表2.7.第100页，共157页，星期日，2025年，2月5日Cj→C1…CmCm+1…CnθiCBXBbx1…xmxm+1…xnc1x1b11…0a1,m+1…a1nθ1c2x2b20…0a2,m+1…a2nθ2…………cmxmbm0…1am,m+1…amnθmCj–Zj0…0…表2.7第101页，共157页，星期日，2025年，2月5日其中：XB列为基变量，这里是x1,x2,…,xm；CB 列中为基变量的价值系数，这里是c1,c2,…,cm；它们随基变量改变而改变，并与基变量相对应；b列中为约束方程组右端的常数；cj行中为所有变量的价值系数c1,c2,…,cn；θi列的数字是在确定换入变量后，按θ规则计算的相应的θ值；最后一行称为检验数行，对应各非基变量xj的检验数是，即cj-zj=σj(j=m+1,…,n)表2.7称为初始单纯形表，每迭代一次构造一个新单纯形表．第102页，共157页，星期日，2025年，2月5日现在我们结合例题来说明如何利用单纯形列表算法求解线性规划问题．解：（1）根据例2.1的标准形，取松弛变量x3,x4,x5为基变量，它对应的单位矩阵为初始基．这时可以得到一个初始基可行解X(0)=(0,0,4,8,6)T，将相关数字填入表中，得到初始单纯形表，见表2.8．第103页，共157页，星期日，2025年，2月5日表2.8中的左上角的Cj是表示目标函数中各变量的价值系数，在表的CB列中，填入初始基变量的价值系数，它们都是0，检验数行各非基变量的检验数为第104页，共157页，星期日，2025年，2月5日（2）因σ1=2,σ2=3,都大于零，且P1、P2、的坐标有正分量存在，转入下一步．（3）因为max(σ1,σ2)=max(2,3)=3，所以x2为换入变量．因为3/2对应x5这一行，所以x5为换出变量.第105页，共157页，星期日，2025年，2月5日（4）以x5所在行与x2所在列的交叉元素[4]为主元素，进行旋转运算，即将P2变换为(0,0,1)T，在XB列中将x5替换为x2，得到新表2.9．第106页，共157页，星期日，2025年，2月5日b列的数字是x3=1,x4=8,x2=3/2.于是得到新的基可行解x(1)=