第5章 单纯形法

管理运筹学1第五章单纯形法•§1单纯形法的基本思路和原理•§2单纯形法的表格形式•§3求目标函数值最小的线性规划的问题的单纯形表解法•§4几种特殊情况管理运筹学2单纯形法单纯形法不是最好的算法，但是一种非常适用的算法基本思路：从可行域某个顶点开始，判断是否为最优解，若不是则再找另一个使目标函数更优的顶点（称之为迭代），再判断是否为最优解，直到找到一个顶点为其最优解（或者判断无最优解）为止。单纯形法中可行域的顶点叫基本可行解找到的第一个可行域的顶点叫初始基本可行解管理运筹学3§1单纯形法的基本思路和原理引例（第二章例１）目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0标准形式为：目标函数：Maxz=50x1+100x2+0s1+0s2+0s3约束条件：s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s3≥0管理运筹学4§1单纯形法的基本思路和原理三个约束方程的系数矩阵为：100100101200111),,,,(54321pppppA其中pj为系数矩阵A中第ｊ列的列向量A的秩m（＝3）小于此方程组的变量的个数n（＝5），即有无数多解。为了找到一个初始基本可行解，先介绍以下几个线性规划的基本概念。管理运筹学5§1单纯形法的基本思路和原理基：已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非奇异子矩阵（即可逆矩阵，），则称B是线性规划问题中的一个基。（注：B是A中ｍ个线性无关的系数列向量组成的。）基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。非基向量：在A中除了基B之外的一列则称之为基B的非基向量。基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n－m个。0B管理运筹学6§1单纯形法的基本思路和原理123111100110210010100010001101BBB120111基基向量和非基向量向量是基的基向量，也是基和基的非基向量1B2B3B向量是基和基的基向量，也是基的非基向量1B3B2B121,,xxs基变量和非基变量都是的基变量，是的非基变量1B23,ss1B管理运筹学7§1单纯形法的基本思路和原理基本解：如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。管理运筹学8§1单纯形法的基本思路和原理基本解在此例中我们不妨找到了为A的一个基，令这个基的非基变量x１，s2为零。这时约束方程就变为基变量的约束方程：x2+s1＝300x2=400，x2+s3=250.x1=0，x2=400，s1=－100，s2=0，s3=－1503110100101B管理运筹学9§1单纯形法的基本思路和原理基本可行解：所有变量的解基本可行解足非负的条件的一个基本解叫做基本可行解。（一个基本解可以是可行解，也可以是非可行解，它们之间的主要区别在于其所有变量的解是否满足非负的条件。）可行基：能够得到基本可行解的基叫做可行基。管理运筹学10§1单纯形法的基本思路和原理由于在这个基本解中s1=－100，s3=－150，不满足该线性规划s1≥0，s3≥0的约束条件，显然不是此线性规划的可行解。因此不是可行基。因此我们选基为，令这个基的非基变量为零。这时约束方程就变为基变量的约束方程：3B1111210010B22,xs11133002400250xsxs求解得到此线性规划的一个基本解：12123200,0,100,0,250.xxsss管理运筹学11§1单纯形法的基本思路和原理由于所有变量的解都大于等于零，可知此基本解为基本可行解。因此，基是可行基。1B==目标函数约束条件行列式≠0基矩阵右边常数基变量非基变量管理运筹学12§1单纯形法的基本思路和原理初始可行基：在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基。初始基本可行解：初始可行基相应的基本可行解叫初始基本可行解。管理运筹学13一般来说判断一个基是否是可行基，只有在求出其基本解以后，当其基本解所有变量的解都是大于等于零，才能断定这个解是基本可行解，这个基是可行基。我们能否在求解之前，就找到一个可行基呢？也就是说我们找到的一个基能保证在求解之后得到的解一定是基本可行解呢？由于在线性规划的标准型中要求bj都大于等于零，如果我们能找到一个基是单位矩阵，或者说一个基是由单位矩阵的各列向量所组成（至于各列向量的前后顺序是无关紧要的事）例如，那么显然所求得的基本解一定是基本可行解，这个单位矩阵或由单位矩阵各列向量组成的基一定是可行基。实际上这个基本可行解中的各个变量或等于某个bj或零。010001100§1单纯形法的基本思路和原理管理运筹学14在本例题中我们就找到了一个基是单位矩阵。在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基，其相应的基本可行解叫初始基本可行解。如果找不到单位矩阵或由单位矩阵的各列向量组成的基作为初始可行基，我们将构造初始可行基，具体做法在以后详细讲述。1000100012B§1单纯形法的基本思路和原理管理运筹学15§1单纯形法的基本思路和原理基：已知A是约束条件的m×n系数矩阵，其秩为m。若B是A中m×m阶非奇异子矩阵（即可逆矩阵，），则称B是线性规划问题中的一个基。（注：B是A中ｍ个线性无关的系数列向量组成的。）基向量：基B中的一列即称为一个基向量。基B中共有m个基向量。非基向量：在A中除了基B之外的一列则称之为基B的非基向量。基变量：与基向量pi相应的变量xi叫基变量，基变量有m个。非基变量：与非基向量pj相应的变量xj叫非基变量，非基变量有n－m个。基本解：如果我们在约束方程组系数矩阵中找到一个基，令这个基的非基变量为零，再求解这个m元线性方程组就可得到唯一的解了，这个解我们称之为线性规划的基本解。基本可行解：所有变量的解基本可行解足非负的条件的一个基本解叫做基本可行解。可行基：能够得到基本可行解的基叫做可行基。初始可行基：在第一次找可行基时，所找到的基或为单位矩阵或为由单位矩阵的各列向量所组成，称之为初始可行基。初始基本可行解：初始可行基相应的基本可行解叫初始基本可行解。0B管理运筹学16二、最优性检验所谓最优性检验就是判断已求得的基本可行解是否是最优解。1.最优性检验的依据——检验数σj一般来说目标函数中既包括基变量，又包括非基变量。现在我们要求只用非基变量来表示目标函数，这只要在约束等式中通过移项等处理就可以用非基变量来表示基变量，然后用非基变量的表示式代替目标函数中基变量，这样目标函数中只含有非基变量了，或者说目标函数中基变量的系数都为零了。此时目标函数中所有变量的系数即为各变量的检验数，把变量xi的检验数记为σi。显然所有基变量的检验数必为零。在本例题中目标函数为50x1+100x2。由于初始可行解中x1，x2为非基变量，所以此目标函数已经用非基变量表示了，不需要再代换出基变量了。这样我们可知σ1=50，σ2=100，σ3=0，σ4=0，σ5=0。§1单纯形法的基本思路和原理管理运筹学17§1单纯形法的基本思路和原理•2.最优解判别定理对于求最大目标函数的问题中，对于某个基本可行解，如果所有检验数≤0，则这个基本可行解是最优解。下面我们用通俗的说法来解释最优解判别定理。设用非基变量表示的目标函数为如下形式由于所有的xj的取值范围为大于等于零，当所有的都小于等于零时，可知是一个小于等于零的数，要使z的值最大，显然只有为零。我们把这些xj取为非基变量(即令这些xj的值为零)，所求得的基本可行解就使目标函数值最大为z0。**对于求目标函数最小值的情况，只需把≤0改为≥0j0jjjJzzxjjjjJxjjjJxjj管理运筹学18§1单纯形法的基本思路和原理三、基变换通过检验，我们知道这个初始基本可行解不是最优解。下面介绍如何进行基变换找到一个新的可行基。具体的做法：从可行基中换一个列向量，得到一个新的可行基，使得求解得到的新的基本可行解，其目标函数值更优。1.入基变量的确定把基检验数大于0的非基变量定为入基变量。若有两个以上的σj＞0，则选其中的σj最大者的非基变量为入基变量。从最优解判别定理知道，当某个σj＞0时，非基变量xj变为基变量不取零值可以使目标函数值增大，故我们要选基检验数大于0的非基变量换到基变量中去（称之为入基变量）。若有两个以上的σj＞0，则为了使目标函数增加得更大些，一般选其中的σj最大者的非基变量为入基变量，在本例题中σ2=100是检验数中最大的正数，故选x2为入基变量。管理运筹学19§1单纯形法的基本思路和原理2.出基变量把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。(1)若确定s1为出基变量，则新的基变量为x2，s2，s3。可求出基本解ｘ1＝0，x2=300，s1=0，s2=100，s3=-50，不是基本可行解，所以s1不能作为出基变量。(2)如果把s3作为出基变量，则新的基变量为x2，s1，s2，因为非基变量x1=s3=0，x2+s1=300，x2+s2=400，x2=250，求出基本解：x1=0，x2=250，s1=50，s2=150，s3=0。条件，是基本可行解，故s3可以确定为出基变量。管理运筹学20§1单纯形法的基本思路和原理我们把确定出基变量的方法概括如下：把已确定的入基变量在各约束方程中的正的系数除以其所在约束方程中的常数项的值，把其中最小比值所在的约束方程中的原基变量确定为出基变量。这样在下一步迭代的矩阵变换中可以确保新得到的bj值都大于等于零。在本例题中约束方程为在第二步中已经知道x2为入基变量，我们把各约束方程中x2的为正的系数除对应的常量，得12112223300,2400,250.xxsxxsxs312122232300400250300,400,250.111bbbaaa管理运筹学21§1单纯形法的基本思路和原理其中的值最小，所以可以知道在原基变量中系数向量为的基变量s3为出基变量，这样可知x2，s1，s2为基变量，x1，s3为非基变量。令非基变量为零，得x2+s1=300,x2+s2=400,x2=250.求解得到新的基本可行解x1=0,x2=250,s1=50,s2=150.这时目标函数值为50x1+100x2=50×0+100×250=25000。显然比初始基本可行解x1=0,x2=0,s1=300,s3=250时的目标函数值为0要好得多。下面我们再进行检验其最优性，如果不是最优解还要继续进行基变换，直至找到最优解，或者能够判断出线性规划无最优解为止。332ba30,0,1Te管理运筹学22基变换步骤=目标函数约束条件基矩阵=基变量右边常数管理运筹学23=入基变量出基变量目标函数约束条件右边常数=管理运筹学24=目标函数约束条件新的基矩阵右边常数=管理运筹学25§2单纯形法的表格形式在讲解单纯形法的表格形式之前，先从一般数学模型里推导出检验数的表达式。可行基为m阶单位矩阵的线性规划模型如下（假设其系数矩阵的前m列是单位矩阵）：以下用表示基变量，用表示非基变量。j112211,111,122,112,2,11,max.,,,0.1,2,,nnmmnnmmnnmmmmmnnmjzcxcxcxxaxaxbxaxaxbxaxaxbxjn1,2,,ixim1,2,,jxjmmn管