(完整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 是一个任意大的正数。