单纯形方法求解课件.ppt

《单纯形方法求解课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.4单纯形方法1.图解法的局限图解法只可解决两个变量的线性规划问题，而在实际应用中还有多个变量的线性规划问题无法解决。因此，1947年G.B.Dantzig提出的单纯形法提供了方便、有效的通用算法求解线性规划。基：已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。非基向量：在A中除了基B之外的一列则称之为基B的非基向量。基变量：与基向量pi相应的变量xi叫基变量，

2、基变量有m个。非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n－m个。基本概念3一、单纯形法的基本原理顶点的逐步转移即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。基本思路：根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一

3、个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据表格单纯形法例题1：用单纯形法求解线性规划问题maxf=3x1+4x2x1+2x2≤63x1+2x2≤12x2≤2x1≥0,x2≥0首先将此现行规划问题化为标准形式得到：minf’=-f=-3x1-4x2x1+2x2+x3=63x1+2x2+x4=12x2+x5=2x1≥0,x2≥0,x3≥0,x4≥0,x5≥0表格单纯形法：1、初始单纯形表的建立(1)表格结构：-3-4000常数dx1x2x3x4x

4、50x31210060x432010120x5010012检验数b340000cjxjxBcB单纯形表的列法：原方程中自带的变量称为非基变量，如x1,x2;为解题而设出的变量称为基变量，如x3,x4,x5。cj：目标函数中变量的系数;xj:变量；xB：基变量；cB:基变量在目标函数中对应的系数；d:各约束条件的常数项；检验数：求例题的检验数：b01=0*1+0*3+0*0-(-3)同理求得b02,b03,b04,b05则最右下角的我们称之为b0，所以b0=0解答：（1）确定换入基的变量。只要有检

5、验数b﹥0，对应的变量xj就可作为换入基的变量，当有一个以上检验数大于零时，一般从最大的开始。因此在本题的检验数中找到最大的正检验数。-3-4000常数dx1x2x3x4x50x31210060x432010120x5010012检验数b340000cjxjxBcB这说明我要调整非基变量x2，使其成为基变量，并相应调出一个基变量为非基变量。（2）确定换出基的变量。为确定哪个基变量调出首先计算:所以本题有：则此最小值对应x5,所以我们将x5行与x2列相交的数值“1”圈起来。即要将x2与x5进行调整

6、。“1”被称为旋转元素。（3）用换入变量xj替换换出变量xB，得到一个新的基。对应这个基找出新的基可行解并列出新的单纯性表。ⅰ）首先将旋转元变为“1”，即将所要转换的基变量行除以旋转元。因为本题中旋转元已经为“1”，所以x5行不用调整。ⅱ）将旋转元所在行转换后的整行数字乘以（-aij),加到表中的第i行数字上，即将要转化为基变量的列变为除转换元为“1”外，其他数字都为“0”的列。在本题中，即是将x5行中的各数乘以（-2），分别加到x3和x4行上。再将x5行乘以（-4）加到检验行上。使得x2列上除

7、了旋转元变为“1”，其余数字都变为“0”。并将xB列中的x5调为x2,表示x2调入基变量，x5调入非基变量。因此得到下表。-3-4000常数dx1x2x3x4x50x31010-220x43001-28-4x2010012检验数b3000-4-8cjxjxBcB以上不过程称之为迭代。如果检验数中任然存在大于“0”的数字，则重复以上3个步骤。直至检验数中所有数字均小于等于0，此时所的的结果即为最优解。以上线性规划问题所得的最后检验数都小于或等于“0”的单纯形法表格如下：-3-4000常数dx1x2

8、x3x4x5-3x110-1/21/2030x500-3/41/411/2-4x2013/4-1/403/2检验数b00-3/2-1/20-15cjxjxBcB因此得到当x1=3，x2=3/2,x3=x4=0,x5=1/2时，目标函数最大值f=15.练习1：①将线性规划问题化成标准型②建立初始单纯形表③计算各非基变量xB的检验数若所有b≤0，则问题已得到最优解，停止计算，否则转入下步。④在大于0的检验数中，若某个bj﹥0，而所对应的列中没有正数，则此问题是无界解，停止计算，否则转入下步。二、