(完整word版)单纯形法的解题步骤

单纯形法求解过程单纯形法是一种经典的线性规划求解方法，它是由乔治·达竞士等人在1947年提出的。

该方法的基本思想是，通过在单纯形空间内不断移动顶点的位置来寻找最优解。

单纯形法是目前广泛应用的线性规划求解方法之一，它求解线性规划问题可大大地简化计算过程。

单纯形法的求解过程包括以下几个步骤：1. 将线性规划问题转化为标准形式线性规划问题的标准形式为：$ \max_{x} \ \ c^T x $$s.t. \ Ax=b$$x\geq 0$其中，$x$是要求解的向量；$b$是一个常数向量；$A$是一个$m\times n$的矩阵；$c$是一个常数向量。

2. 初始化单纯形表因为单纯形法是通过移动顶点来寻找最优解的方法，因此需要初始化单纯形表。

单纯形表是将原始的约束条件表示为不等式形式时形成的。

例如，对于一个带有3个变量的线性规划问题，其单纯形表的形式如下：CB | X1 | X2 | X3 | X4 | RHS----|-----|-----|-----|-----|----0 | a11| a12| a13| 0 | b10 | a21| a22| a23| 0 | b20 | a31| a32| a33| 0 | b31 | z1 | z2 | z3 | 0 | 0其中，CB代表成本系数，X1、X2、X3、X4分别代表变量。

a11、a12、a13等代表矩阵A中的元素，b1、b2、b3代表矩阵b中的元素。

3. 选择进入变量和离开变量在单纯形表中，规定最后一列为等式右边的常数（RHS），即b。

在单纯形法的求解过程中，首先需要选择一个“进入变量”，即在单纯形表的第一行中，寻找一个系数为正的变量，使得将其加入目标函数后，目标函数值可以上升。

这里以X1为例，X1为进入变量。

接着，需要选择一个“离开变量”，即在单纯形表中，寻找一个使得添加X1变量后，约束条件不改变且取得约束条件中系数最小的一个变量离开。

线性规划问题解法：（1）图解法： 优点---只管易掌握，有助于理解结构。

缺点---只能解决低维的问题，对高维无能为力。

（2）单纯形法：单纯形法把寻优的目标集中在所有基本可行解（即可行域顶点）中。

单纯形法的一般步骤如下：1、寻找一个初始的基本可行解。

2、检查现行的基本可行解是否最优，如果为最优，则停止迭代，已找到最优解，否则转一步。

3、移至目标函数值有所改善的另一个基本可行解，然后转会到步骤（2）。

步骤1： 约束方程 表示为： 用可行基Ｂ的逆阵Ｂ-1左乘等式两端，再通过移项可推得： 若令所有非基变量 ，则基变量 由此可得初始的基本可行解：其过程为：存在问题：1、要判断m 个系数列向量是否恰好构成一个基并不是一件容易的事。

基由系数矩阵Ａ中m 个线性无关的系数列向量构成。

但是要判断m 个系数列向量是否线性无关并非易事。

2、即使系数矩阵Ａ中找到了一个基B ，也不能保证该基恰好是可行基。

因为不能保证基变量ＸB =Ｂ-1b ≥0。

3、为了求得基本可行解，必须求基Ｂ的逆阵Ｂ-1。

但是求逆阵Ｂ-1也是一件麻烦的事。

结论：在线性规划标准化过程中设法得到一个m 阶单位矩阵I 作为初始可行基Ｂ为了设法得到一个m 阶单位矩阵I 作为初始可行基Ｂ，可在规划标准化过程中作如下处理：1、若在化标准形式前，m 个约束方程都是“≤”的形式，那么在化标准形时只需在一个约束不等式左端都加上一个松弛变量x n+i (i=12…m)。

2、若在化标准形式前，约束方程中有“≥”不等式，那么在化标准形时除了在方程式左端减去剩余变量使不等式变成等式以外，还必须在左端再加上一个非负新变量，称为人工变量．3、若在化标准形式前，约束方程中有等式方程，那么可以直接在等式左端添加人工变量。

【步骤一完成：寻找一个初始的基本可行解】 AX=bB B N N X AX=(BN)=BX +NX =bX ⎛⎫ ⎪⎝⎭-1-1B N X =B b-B NX N X =0-1B X =B b1B b X=0-⎛⎫ ⎪⎝⎭-1-1-1B N B N N B AX=b BX +NX =b X =B b-B NX X =0,X =B b→→→步骤2： 假如已求得一个基本可行解将这一基本可行解代入目标函数，可求得相应的目标函数值其中 分别表示基变量和非基变量所对应的价值系数子向量。

单纯形法表的解题步骤单纯形法表结构如下：j c →对应变量的价值系数i θB Cb Xb1x 2x 3x " j x基变量的价值系数基变量 资源列θ规则求的值j σ检验数①一般形式若线性规划问题标准形式如下：123451231425max 23000284164120,1,2,5j z x x x x x x x x x x x x x j =++++++=⎧⎪+=⎪⎨+=⎪⎪≥=⎩"取松弛变量345,,x x x 为基变量，它对应的单位矩阵为基。

这样就得到初始可行基解：()()00,0,8,16,12TX =。

将有关数字填入表中，得到初始单纯形表，如表1-1所示：表 1-1 ()()00,0,8,16,12TX =j c →2 3 0 0 0i θB C b X b1x 2x 3x 4x 5x0 3x 8 1 2 1 0 0 4 04x16 4 0 0 1 0 -5x12 0 [4] 0 0 1 3j σ2 3 0 0 0若检验数均未达到小于等于0，则对上表进行调整。

选择上表中检验数最大的列，该列对应的非变量为入基变量；再应用θ规则该列对应的各基变量对应的θ值，选出其中最小的一行，该行对应的基变量为出基变量。

修改单纯形表，对各行进行初等变换，确保基变量组成的矩阵为单为矩阵。

修改后的单纯形表如表1-2所示：表 1-2 ()()10,3,2,16,0TX =检验数12,0σσ>，则进行继续调整，调整后的单纯形法表如表1-3所示：表 1-3 ()()22,3,0,8,0TX =表1-3中， 50σ>，则继续进行调整，调整结果如表1-4所示：表 1-4 ()()34,2,0,0,4TX =检验数0j σ≤，这表示目标函数值已不可能再增大，于是得到最优解：()()3*4,2,0,0,4TX X ==*14z =②带人工变量现有线性规划问题：12312312313123min 321142321,,0z x x x x x x x x x x x x x x =−++−+≤⎧⎪−++≥⎪⎨−+=⎪⎪≥⎩ 将上述线性规划问题用大M 法求解，在约束条件中加入松弛变量4x ，剩余变量5x ，人工变量6x ，7x 得到：1234567123412356137min 300211423210,1,2,,7j z x x x x x Mx Mx x x x x x x x x x x x x x j =−++++++−++=⎧⎪−++−+=⎪⎨−++=⎪⎪≥=⎩"其中，M 是一个任意大的正数。

三、单纯形法的解题步骤第一步：作单纯形表.）（1）把原线性规划问题化为标准形式；）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；）（3）目标函数非基化；）（4）作初始单纯形表.第二步：最优解的判定.(1) 若所有检验数都是非正数，即，则此时线性规划问题已取得最优解.(2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划问题无最优解.如果以上两条都不满足，则进行下一步.第三步：换基迭代.，并确定所在列的非基变量为进基变量.（1）找到最大正检验数，设为（2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号.主元是最大正检验数所在列，用常数项与进基变量所对应的列向量中正分量的比值最小者；替换出基变量，从而得到新的基变量.也就是主元所在（3）换基：用进基变量（4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表；（5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止.例3 求.解（1）化标准型：令，引进松弛变量，其标准型为求（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为标函数取得最优值.目性规划问题的最优解为：.原线目标函数的最优值为14，即.例4 用单纯形方法解线性规划问题.求.解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出，,代入目标函数, 经整理后，目标函数非基化了.作单纯形表，并进行换基迭代（见表6.9）.最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变换，基变量出基，非基变量进基.表 6.9目前最大检验数，其所在列没有正分量，所以该线性规划问题没有最优解.例5用单纯形方法解线性规划问题.求解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵，取为基变量，而目标函数没有非基化.从约束方程找出，,代入目标函数，经整理得,目标函数已非基化.作单纯形表，并进行换基迭代(见表6.10).最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变换，基变量出基，非基变量x2进基，先将主元化为1，然后再将主元所在列的其他元素化为零.表 6.10至此，检验数均为非正数，故得基础可行解.原问题的最优解为：.最优值为6，即.如果我们再迭代一次，将基变量出基，非基变量进基（见表6.11）.表 6.11可得到另一个基础可行解,原问题的最优解为：，最优值仍为6，说明该线性规划问题有无穷多最优解，其最优解均为6.如何知道线性规划问题有无穷多最优解呢？这主要反映在单纯形表中.如果非基变量所对应的检验数为0，我们可对此列继续进行换基迭代，就可以得到另一个基础可行解.以此作下去，可得到许多基础可行解，即相对应的最优解有无穷多个.（4） 011 0。

单纯形法的计算步骤1°把LP问题化为标准形。

2°在系数阵中找出或构造一个m阶排列阵作为初始可行基，建立初始单纯形表。

3°最优性检验: 若所有检验数σj=c j-z j<=0，就得到一个最优基本解，停止计算；否则转4°。

4°解无界判断: 在所有σj> 0中, 只要有一个σr> 0所对应的系数列向量ar≤ 0，即一切a ir≤ 0 ，i=1, 2, … , m则该LP问题解无界，停止计算；否则转5°。

预备步骤迭代步骤进基变量的相持•选择进基变量时，如果出现两个或更多个σj>0同时达到最大而相持时,则应：•任选一个最大的检验数所对应的变量作为进基变量。

离基变量的相持——退化与循环•如果在单纯形法的计算过程中，在确定离基变量时，存在两个及以上的相同的最小比值，必然导致一个退化的基本可行解，可能造成迭代过程循环。

•避免循环的方法：摄动法、辞典序法、布兰德法•如摄动法：从相持的离基变量中，选择下标最大者离基。

多重最优解•在最优单纯形表中：⑴若有一个或更多个非基变量x j 的检验数σj = 0，则该问题有无穷多个最优解；⑵若该x j 在该表中的系数列向量a j ≤0，则按单纯形法另作几次迭代，每次都选一个这样的x j 进基，就能得到其它最优基本解；⑶若问题有r个最优极点解X i *，则该LP问题有无穷多个最优解，且其中任一最优解X*都能表示成这r个最优极点解的凸组合：0≤ μi ≤1 ，i =1, 2, … , r,且∑u i =1X*=μ1X 1*+μ2X 2*+… +μr X r *其中：人工变量法•基于LP问题的标准型，可能找不到初始的基本可行解，可采用人工变量法。

如大M法和两阶段法。

•人造解X不是原LP问题的基本可行解。

•但若能通过单纯形法的迭代步骤，将虚拟的人工变量都替换出去，都变为非基变量（即人工变量xn+1=xn+2=… =x n+m =0），则X的前n个分量就构成原LP问题的一个基本可行解。

单纯形法求解原理过程第一篇：单纯形法求解原理过程单纯形法需要解决的问题：如何确定初始基本可行解；如何由一个基本可行解迭代出另一个基本可行解，同时使目标函数获得较大的下降；如何判断一个基本可行解是否为最优解。

min f(X)=-60x1-120x2 s.t.9x1+4x2+x3=360 3x1+10x2+x4=300 4x1+5x2+x5=200 xi≥0(i=1,2,3,4,5)(1)初始基本可行解的求法。

当用添加松弛变量的方法把不等式约束换成等式约束时，我们往往会发现这些松弛变量就可以作为初始基本可行解中的一部分基本变量。

例如：x1-x2+x3≤5 x1+2x2+x3≤10xi≥0 引入松弛变量x4，x5后，可将前两个不等式约束换成标准形式 x1-x2+x3+x4=5 x1+2x2+x3+x5=10xi≥0(i=1,2,3,4,5)令x1=x2=x3=0，则可立即得到一组基本可行解x1=x2=x3=0，x4=5，x5=10 同理在该实例中，从约束方程式的系数矩阵⎡94100⎤⎥A=[P1,P2,P3,P4,P5]=⎢310010⎢⎥⎢⎣45001⎥⎦中可以看出其中有个标准基，即⎡100⎤⎥B=⎢010⎢⎥⎢⎣001⎥⎦与B对应的变量x3，x4，x5为基本变量，所以可将约束方程写成X3=360-9x1-4x2 x4=300-3x1-10x2 x5=200-4x1-5x20 若令非基变量x1=x2=0，则可得到一个初始基本可行解X0 TX=[0,0,360,300,200]判别初始基本可行解是否是最优解。

此时可将上式代入到目标函数中，得： F(X)=-60x1-120x20对应的函数值为f(X)=0。

0由于上式中x1,x2系数为负，因而f(X)=0不是最小值。

因此所得的解不是最优解。

011(2)从初始基本可行解X迭代出另一个基本可行解X，并判断X 是否为最优解。

从一个基本可行解迭代出另一个基本可行解可分为两步进行：第一步，从原来的非基变量中选一个（称为进基变量）使其成为基本变量；第二步，从原来的基本变量中选一个（称为离基变量）使其成为新的非基变量。

§4.3 解目标规划的单纯形法目标规划的数学模型结构与线性规划的数学模型结构形式上没有本质的区别，所以也可用单纯形法求解目标规划模型。

但须注意：（1）因目标规划问题的目标函数都是最小化，所以要达到最优，应该所有检验数 0σ≥；（2）因非基变量的检验数中含有不同等级的优先因子， (1,2,,)i p i K =，故检验时须优先考察前一级的检验数，在迭代中，要保证不使得上一级的目标变差。

解目标规划的单纯形法的计算步骤：1.建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=1;2.检查该行中是否存在负数，且对应的前k-1行的检验数为零，若是，取其中最小者对应的变量为换入变量，转3，否则转5；3.按最小比值规则确定换出变量，当存在两个或两个以上相同的最小比值时，选取具有较高级别的变量为换出变量；4.按单纯形法进行基变换迭代运算，得新的单纯形表，返回2；5.当k=K 时，计算结束。

否则置k=k+1,返回2。

例 试用单纯形法求解目标规划11222331212111222123312min ()2 =110 .21081056,,,,0,1,2,3s s i i F p d p d d p d x x x x x d d s t x x d d x x d d x x x d d i +-+--+-+-+-+=+++++⎧⎪-+-=⎪⎪++-=⎨⎪++-=⎪≥=⎪⎩解 取123,,,sx dd d ---为初始基变量，可列出初始单纯形表（表1）：表1选定换入变量为2x,换出变量为2d-，从而主元素为[2]，进行基变换得（表2）：表2由于表2中12p p 与行检验数均非负，故对第一，第二级目标均优化完毕。

因3p 行检验数中有负数，故还需优化第三级目标。

注意：在3p 行检验数中2d +的检验数为5-最小，似应将2d +作为换入变量，但由于其上一行对应的检验数为1，非零，从而若将2d +引入基变量，必将使第二优先级目标变差，因此确定1x 为换入变量，再按最小比值原则定3d -为换出变量，于是[3]为主元素，进行基变换得（表3）表3 表3中所有检验数均非负，因此给出了问题的满意解，**122,4x x ==.检查表3的检验数行，发现非基变量3d +的检验数为0，这表示存在多重解。

,0121内年三、单纯形法的解题步骤第一步：作单纯形表.）（1）把原线性规划问题化为标准形式；）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；）（3）目标函数非基化；）（4）作初始单纯形表.第二步：最优解的判定.(1) 若所有检验数都是非正数，即，则此时线性规划问题已取得最优解.(2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划问题无最优解.如果以上两条都不满足，则进行下一步.第三步：换基迭代.，并确定所在列的非基变量为进基变量.（1）找到最大正检验数，设为（2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号.主元是最大正检验数所在列，用常数项与进基变量所对应的列向量中正分量的比值最小者；替换出基变量，从而得到新的基变量.也就是主元所在（3）换基：用进基变量（4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表；（5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止.例3 求.解（1）化标准型：令，引进松弛变量，其标准型为求（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表6.8）.表 6.8（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为目标函数取得最优值.原线性规划问题的最优解为：.目标函数的最优值为14，即.例4 用单纯形方法解线性规划问题.求.解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出，,代入目标函数,经整理后，目标函数非基化了.作单纯形表，并进行换基迭代（见表6.9）.最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变换，基变量出基，非基变量进基.表 6.9目前最大检验数，其所在列没有正分量，所以该线性规划问题没有最优解.例5用单纯形方法解线性规划问题. 求解 此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵，取为基变量，而目标函数没有非基化.从约束方程找出，,代入目标函数，经整理得,目标函数已非基化.作单纯形表，并进行换基迭代(见表 6.10). ，由最小比值最大检验数 法知：为主元，对主元所在列施量出基，非基变量以行初等变换，基变化为1，然后x 2进基，先将主元 再将主元所在列的其他元素化为零.表 6.10x 1 x 2 x 3 x 4常数x 3 x 41 -1 1 0 -3 (1) 0 12 4 S2 3 0 0 0 x 3 x 2-2 0 1 1 -3 1 0 1 6 4 S11 0 0 -312至此，检验数均为非正数，故得基础可行解.原问题的最优解为：.最优值为6，即.如果我们再迭代一次，将基变量出基，非基变量进基（见表6.11）.表 6.11（4）0 1 1 0可得到另一个基础可行解,原问题的最优解为：，最优值仍为6，说明该线性规划问题有无穷多最优解，其最优解均为6.如何知道线性规划问题有无穷多最优解呢？这主要反映在单纯形表中.如果非基变量所对应的检验数为0，我们可对此列继续进行换基迭代，就可以得到另一个基础可行解.以此作下去，可得到许多基础可行解，即相对应的最优解有无穷多个.。

单纯形法的解题步骤(总6页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--三、单纯形法的解题步骤第一步：作单纯形表.1）（1）把原线性规划问题化为标准形式；2）（2）找出初始可行基，通常取约束方程组系数矩阵中的单位矩阵；3）（3）目标函数非基化；4）（4）作初始单纯形表.第二步：最优解的判定.(1) 若所有检验数都是非正数，即，则此时线性规划问题已取得最优解.(2) 若存在某个检验数是正数，即，而所对应的列向量无正分量，则线性规划问题无最优解.如果以上两条都不满足，则进行下一步.第三步：换基迭代.（1）找到最大正检验数，设为，并确定所在列的非基变量为进基变量.（2）对最大正检验数所在列实施最小比值法，确定出主元，并把主元加上小括号.主元是最大正检验数所在列，用常数项与进基变量所对应的列向量中正分量的比值最小者；（3）换基：用进基变量替换出基变量，从而得到新的基变量.也就是主元所在列的非基变量进基，所在行的基变量出基；（4）利用矩阵的行初等变换，将主元变为1，其所在列其他元素都变为零，从此得到新的单纯形表；（5）回到第二步，继续判定最优解是否存在，然后进行新一轮换基迭代，直到问题得到解决为止.例3 求.解（1）化标准型：令，引进松弛变量，其标准型为求（2）作单纯形表：在约束方程组系数矩阵中的系数构成单位矩阵，故取为基变量，目标函数已非基化了，作初始单纯形表并“换基迭代”（见表）.表x1 x2x3x4x5常数x 3 x 4 x 5 1 0 1 0 01 2 0 1 00 （1） 0 0 15104S′ 1 3 0 0 0 0x 3 x 4 x2 1 0 1 0 0（1） 0 0 1 -20 1 0 0 1524S′ 1 0 0 0 -3 -12x 3 x 1 x 2 0 0 1 -1 21 0 0 1 -20 1 0 0 1324S′ 0 0 0 -1 -1 -14（3）最终结果：此时检验数均为非正数，线性规划问题取得最优解，最优解为目标函数取得最优值.原线性规划问题的最优解为：.目标函数的最优值为14，即.例4 用单纯形方法解线性规划问题.求.解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵（1、2行，3、4列构成），取为基变量，而目标函数没有非基化.从约束方程找出，,代入目标函数,经整理后，目标函数非基化了.作单纯形表，并进行换基迭代（见表）.最大检验数，由最小比值法知：为主元，对主元所在列施以行初等变换，基变量出基，非基变量进基.表目前最大检验数，其所在列没有正分量，所以该线性规划问题没有最优解.例5用单纯形方法解线性规划问题.求解此数学模型已是标准型了，其中约束方程含有一个二阶单位矩阵，取为基变量，而目标函数没有非基化.从约束方程找出，,x1x2 x3x4常数x3x41 -1 1 0-3 (1) 0 124S 2 3 0 0 0x3x2-2 0 1 1-3 1 0 164S 11 0 0 -3 12代入目标函数，经整理得,目标函数已非基化.作单纯形表，并进行换基迭代(见表.最大检验数 ，由最小比值法知： 为主元，对主元所在列施以行初等变换，基变量 出基，非基变量x 2进基，先将主元 化为1，然后再将主元所在列的其他元素化为零.表至此，检验数均为非正数，故得基础可行解.x 1 x 2 x 3 x 4 常数 x 3 x 4-2 （2） 1 0 3 1 0 14 6 S-2 2 0 010x 2x 4 -1 10 4 0 -12 4 S ’ 0 0 -1 06原问题的最优解为：.最优值为6，即.如果我们再迭代一次，将基变量出基，非基变量进基（见表）.表可得到另一个基础可行解,原问题的最优解为：，最优值仍为6，说明该线性规划问题有无穷多最优解，其最优解均为6.如何知道线性规划问题有无穷多最优解呢这主要反映在单纯形表中.如果非基变量所对应的检验数为0，我们可对此列继续进行换基迭代，就可以得到另一个基础可行解.以此作下去，可得到许多基础可行解，即相对应的最优解有无穷多个.x 1 x 2 x 3 x 4 常数 x 2x 4-1 1（4） 01 2 4 S ’ 0 0 -1 0 6x 2 x 1 0 11 0 3 1 S ’0 0 －1 06。