单纯形方法求解课件

1.图解法的局限图解法只可解决两个变量的线性规划问题，而在实际应用中还有多个变量的线性规划问题无法解决。因此，

1947年G.B.Dantzig提出的单纯形法提供了方便、有效的通用算法求解线性规划。

1.图解法的局限图解法只可解决两个变量的线性规划问题，而在实2基：已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非奇异子矩阵（即可逆矩阵），则称B是线性规划问题中的一个基。基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。非基向量：在A中除了基B之外的一列则称之为基B的非基向量。基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n－m个。基本概念2基：已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中一、单纯形法的基本原理

顶点的逐步转移

即从可行域的一个顶点（基本可行解）开始，转移到另一个顶点（另一个基本可行解）的迭代过程，转移的条件是使目标函数值得到改善（逐步变优），当目标函数达到最优值时，问题也就得到了最优解。一、单纯形法的基本原理

顶点的逐步转移即从可基本思路：基本思路：

根据线性规划问题的可行域是凸多边形或凸多面体，一个线性规划问题有最优解，就一定可以在可行域的顶点上找到。

于是，若某线性规划只有唯一的一个最优解，这个最优解所对应的点一定是可行域的一个顶点；若该线性规划有多个最优解，那么肯定在可行域的顶点中可以找到至少一个最优解。顶点转移的依据根据线性规划问题的可行域是凸多边形或凸多面体表格单纯形法例题1：用单纯形法求解线性规划问题

maxf=3x1+4x2x1+2x2≤63x1+2x2≤12x2≤2x1≥0,x2≥0表格单纯形法例题1：用单纯形法求解线性规划问题首先将此现行规划问题化为标准形式得到：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常数dx1x2x3x4x50x31210060x432010120x5010012检验数b340000cjxjxBcB表格单纯形法：-3-4000常数x1x2x3x4x50x31单纯形表的列法：原方程中自带的变量称为非基变量，如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）确定换入基的变量。只要有检验数b﹥0，对应的变量xj就可作为换入基的变量，当有一个以上检验数大于零时，一般从最大的开始。因此在本题的检验数中找到最大的正检验数。-3-4000常数dx1x2x3x4x50x31210060x432010120x5010012检验数b340000cjxjxBcB解答：-3-4000常数x1x2x3x4x50x312100这说明我要调整非基变量x2，使其成为基变量，并相应调出一个基变量为非基变量。（2）确定换出基的变量。为确定哪个基变量调出首先计算:所以本题有：则此最小值对应x5,所以我们将x5行与x2列相交的数值“1”圈起来。即要将x2与x5进行调整。“1”被称为旋转元素。这说明我要调整非基变量x2，使其成为基变量，并相应调出一个（3）用换入变量xj替换换出变量xB，得到一个新的基。对应这个基找出新的基可行解并列出新的单纯性表。ⅰ）首先将旋转元变为“1”，即将所要转换的基变量行除以旋转元。因为本题中旋转元已经为“1”，所以x5行不用调整。ⅱ）将旋转元所在行转换后的整行数字乘以（-aij),加到表中的第i行数字上，即将要转化为基变量的列变为除转换元为“1”外，其他数字都为“0”的列。在本题中，即是将x5行中的各数乘以（-2），分别加到x3和x4行上。再将x5行乘以（-4）加到检验行上。使得x2列上除了旋转元变为“1”，其余数字都变为“0”。并将xB列中的x5调为x2,表示x2调入基变量，x5调入非基变量。因此得到下表。（3）用换入变量xj替换换出变量xB，得到一个新的基。对应这-3-4000常数dx1x2x3x4x50x31010-220x43001-28-4x2010012检验数b3000-4-8cjxjxBcB以上不过程称之为迭代。如果检验数中任然存在大于“0”的数字，则重复以上3个步骤。直至检验数中所有数字均小于等于0，此时所的的结果即为最优解。-3-4000常数x1x2x3x4x50x31010-220以上线性规划问题所得的最后检验数都小于或等于“0”的单纯形法表格如下：-3-4000常数dx1x2x3x4x5-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.以上线性规划问题所得的最后检验数都小于或等于“0”的单纯形法练习1：练习1：①将线性规划问题化成标准型②建立初始单纯形表③计算各非基变量xB的检验数

若所有b≤0，则问题已得到最优解，停止计算，否则转入下步。④在大于0的检验数中，若某个bj﹥0，而所对应的列中没有正数，则此问题是无界解，停止计算，否则转入下步。二、单纯形法的计算步骤

①将线性规划问题化成标准型二、单纯形法的计算步骤⑤根据max{dj｜dj＞0}=dk原则，确定xk为换入变量(进基变量)，再按

规则计算：

=min{bi′/aik′|aik′＞0}=bl′/aik′

确定出换出变量。建立新的单纯形表，此时换入非基变量取代了换出基变量的位置。以aik′为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik′变为1，同列中其它元素为0。后转第③步。

⑤根据max{dj｜dj＞0}=dk原则，确定xk为换入变量练习2：练习2：人工变量法

用单纯形法解题时，需要有一个单位阵作为初始基。当约束条件都是“≤”时，加入松弛变量就形成了初始基。但实际存在“≥”或“＝”型的约束，没有现成的单位矩阵。人工变量

采用人造基的办法：人工构造单位矩阵在没有单位列向量的等式约束中加入人工变量，构成原线性规划问题的伴随问题，从而得到一个初始基。人工变量是在等式中人为加进的，只有它等于0时，约束条件才是它本来的意义。处理方法有两种：大M法两阶段法人工变量法用单纯形法解题时，需要有一个单位阵作为初始基。人例题2：大M法例题2：大M法大M法：本题化为标准形式后，发现只有x4一个基变量，但题中需要三个基变量，于是，加入行x6,x7两个人工变量。其目标函数中的系数为M，M代表任意大的正值。大M法：本题化为标准形式后，发现只有x4一个基变量，但题中需练习3：练习3：两阶段法：第一阶段：先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中的其他变量系数取零，人工变量的系数取某个正的常数（一般取1），在保持原问题约束条件不变的情况下求这个目标函数极小化的解。显然在第一阶段中，当人工变量取值为零时，目标函数值为零。这个时候的最优解就是原线性规划问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为零，即最优解的非基变量中含有非零的人工变量，表明线性规划问题无可行解。第二阶段：当第一阶段求解结果表明问题有可行解，则此阶段在原问题中去除人工变量，并从此可行解出发继续寻找最优解。两阶段法：第一阶段：先求解一个目标函数中只包含人工变量的线性例3：两阶段法例3：两阶段法单纯形法一般还可证明：1.解的情况：(1)如果在单纯形表中所有检验数