单纯形法求解步骤：一个简单例子

爱被打了一巴掌 2021-09-24 16:50 405阅读 0赞

### 文章目录 ###

*  1. 题目
 *  2. 求解过程
 *   *  2.1. 第一次迭代
     *  2.2. 第二次迭代
     *  2.3. 第三次迭代
 *  3. 算法
 *  4. 手稿
 *  5. 参考

# 1. 题目 #

使用单纯形法求解  
 max ⁡ z = 50 x 1 + 100 x 2 \\max z = 50x\_1 + 100x\_2 maxz=50x1\+100x2

s.t. \{ x 1 + x 2 ≤ 300 2 x 1 + x 2 ≤ 400 x 2 ≤ 250 x i ≥ 0 , i = 1 , 2 \\text\{s.t.\} \\begin\{cases\} x\_1 + x\_2 \\leq 300 \\\\ 2x\_1 + x\_2 \\leq 400 \\\\ x\_2 \\leq 250 \\\\ x\_i \\geq 0, i= 1, 2 \\end\{cases\} s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧x1\+x2≤3002x1\+x2≤400x2≤250xi≥0,i=1,2

# 2. 求解过程 #

*  首先引入松弛变量，将线性规划问题化成标准型。  
     max ⁡ z = 50 x 1 + 100 x 2 + 0 x 3 + 0 x 4 + 0 x 5 \\max z = 50x\_1 + 100x\_2 + 0x\_3 + 0x\_4 + 0x\_5 maxz=50x1\+100x2\+0x3\+0x4\+0x5

s.t. \{ x 1 + x 2 + x 3 = 300 2 x 1 + x 2 + x 4 = 400 x 2 + x 5 = 250 x i ≥ 0 , i = 1 , 2 , … , 5 \\text\{s.t.\} \\begin\{cases\} x\_1 + x\_2 + x\_3 = 300 \\\\ 2x\_1 + x\_2 + x\_4 = 400 \\\\ x\_2 + x\_5 = 250 \\\\ x\_i \\geq 0, i = 1, 2, \\dots, 5 \\end\{cases\} s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧x1\+x2\+x3=3002x1\+x2\+x4=400x2\+x5=250xi≥0,i=1,2,…,5

## 2.1. 第一次迭代 ##

1.  首先画出如下的表格；（PS：表格第一行有 3 个  C C C、 σ \\sigma σ，应该合并，但是我不知道如何在Markdown中合并表格）

1.  在第一行中， C j C\_j Cj 表示目标函数的系数矩阵（向量）， C j C\_j Cj 右侧是目标函数的系数矩阵（向量）具体值，在题目中目标函数为  max ⁡ z = 50 x 1 + 100 x 2 + 0 x 3 + 0 x 4 + 0 x 5 \\max z = 50x\_1 + 100x\_2 + 0x\_3 + 0x\_4 + 0x\_5 maxz=50x1\+100x2\+0x3\+0x4\+0x5，因此按照  x 1 , x 2 , … , x 5 x\_1, x\_2, \\dots, x\_5 x1,x2,…,x5 的顺序写出它们的系数，  
     C = \[ 50 100 0 0 0 \] C = \\begin\{bmatrix\} 50 &100 & 0 & 0 & 0 \\end\{bmatrix\} C=\[50100000\]

1.  在  x 1 , x 2 , x 3 , x 4 , x 5 x\_1, x\_2, x\_3, x\_4, x\_5 x1,x2,x3,x4,x5 下面写上约束方程组的系数矩阵  A A A；需要注意的是：在方程中没有出现的变量，其系数为 0，必须写上；  
     A = ( a i j ) = \[ 1 1 1 0 0 2 1 0 1 0 0 1 0 0 1 \] A = (a\_\{ij\}) = \\begin\{bmatrix\} 1 & 1 & 1 & 0 & 0 \\\\ 2 & 1 & 0 & 1 & 0 \\\\ 0 & 1 & 0 & 0 & 1 \\\\ \\end\{bmatrix\} A=(aij)=⎣⎡120111100010001⎦⎤

<table> 
 <thead> 
 <tr> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th>50</th> 
 <th>100</th> 
 <th>0</th> 
 <th>0</th> 
 <th>0</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> C B C_B CB</td> 
 <td>基</td> 
 <td> b b b</td> 
 <td> x 1 x_1 x1</td> 
 <td> x 2 x_2 x2</td> 
 <td> x 3 x_3 x3</td> 
 <td> x 4 x_4 x4</td> 
 <td> x 5 x_5 x5</td> 
 </tr> 
 <tr> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td> 1 \color{#FF0000}{1} 1</td> 
 <td> 1 \color{#FF0000}{1} 1</td> 
 <td> 1 \color{#FF0000}{1} 1</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 </tr> 
 <tr> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td> 2 \color{#FF0000}{2} 2</td> 
 <td> 1 \color{#FF0000}{1} 1</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 1 \color{#FF0000}{1} 1</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 </tr> 
 <tr> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 1 \color{#FF0000}{1} 1</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 1 \color{#FF0000}{1} 1</td> 
 </tr> 
 <tr> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

1.  在  b b b 列依次写上约束矩阵右侧的常数，分别是  
     b = \[ 300 400 250 \] b = \\begin\{bmatrix\} 300 \\\\ 400 \\\\ 250 \\\\ \\end\{bmatrix\} b=⎣⎡300400250⎦⎤

1.  在系数矩阵中找到一个单位矩阵，其对应的变量作为初始基变量，因此基变量为  
     基 = \[ x 3 x 4 x 5 \] \\text\{基\} = \\begin\{bmatrix\} x\_3 \\\\ x\_4 \\\\ x\_5 \\\\ \\end\{bmatrix\} 基=⎣⎡x3x4x5⎦⎤  
    将其填入基列；

<table> 
 <thead> 
 <tr> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th>50</th> 
 <th>100</th> 
 <th>0</th> 
 <th>0</th> 
 <th>0</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> C B C_B CB</td> 
 <td>基</td> 
 <td> b b b</td> 
 <td> x 1 x_1 x1</td> 
 <td> x 2 x_2 x2</td> 
 <td> x 3 x_3 x3</td> 
 <td> x 4 x_4 x4</td> 
 <td> x 5 x_5 x5</td> 
 </tr> 
 <tr> 
 <td></td> 
 <td> x 3 \color{#FF0000}{x_3} x3</td> 
 <td>300</td> 
 <td>1</td> 
 <td>1</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 </tr> 
 <tr> 
 <td></td> 
 <td> x 4 \color{#FF0000}{x_4} x4</td> 
 <td>400</td> 
 <td>2</td> 
 <td>1</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 </tr> 
 <tr> 
 <td></td> 
 <td> x 5 \color{#FF0000}{x_5} x5</td> 
 <td>250</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

1.  在  C B C\_B CB 列中填入基向量在目标函数的系数矩阵（向量）中值  
     C B = \[ 0 0 0 \] C\_B = \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 0 \\\\ \\end\{bmatrix\} CB=⎣⎡000⎦⎤

<table> 
 <thead> 
 <tr> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th>50</th> 
 <th>100</th> 
 <th>0</th> 
 <th>0</th> 
 <th>0</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> C B C_B CB</td> 
 <td>基</td> 
 <td> b b b</td> 
 <td> x 1 x_1 x1</td> 
 <td> x 2 x_2 x2</td> 
 <td> x 3 x_3 x3</td> 
 <td> x 4 x_4 x4</td> 
 <td> x 5 x_5 x5</td> 
 </tr> 
 <tr> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> x 3 x_3 x3</td> 
 <td>300</td> 
 <td>1</td> 
 <td>1</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 </tr> 
 <tr> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> x 4 x_4 x4</td> 
 <td>400</td> 
 <td>2</td> 
 <td>1</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 </tr> 
 <tr> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> x 5 x_5 x5</td> 
 <td>250</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

1.  至此，迭代1中的初始单纯形表填入完毕，接下来计算检验和

σ j = C j − ∑ i C B ∗ a i j \\sigma\_j = C\_j - \\sum\_\{i\} C\_B \* a\_\{ij\} σj=Cj−i∑CB∗aij

因此，

σ 1 = C 1 − ∑ i = 1 3 C B ∗ a i 1 = 50 − \[ 0 0 0 \] T ∗ \[ 1 2 0 \] = 50 \\sigma\_1 = C\_1 - \\sum\_\{i=1\}^\{3\} C\_B \* a\_\{i1\} = 50 - \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 0 \\\\ \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 1 \\\\ 2 \\\\ 0 \\end\{bmatrix\} = 50 σ1=C1−i=1∑3CB∗ai1=50−⎣⎡000⎦⎤T∗⎣⎡120⎦⎤=50

σ 2 = C 2 − ∑ i = 1 3 C B ∗ a i 2 = 100 − \[ 0 0 0 \] T ∗ \[ 1 1 1 \] = 100 \\sigma\_2 = C\_2 - \\sum\_\{i=1\}^\{3\} C\_B \* a\_\{i2\} = 100 - \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 0 \\\\ \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 1 \\\\ 1 \\\\ 1 \\end\{bmatrix\} = 100 σ2=C2−i=1∑3CB∗ai2=100−⎣⎡000⎦⎤T∗⎣⎡111⎦⎤=100

σ 3 = C 3 − ∑ i = 1 3 C B ∗ a i 3 = 0 − \[ 0 0 0 \] T ∗ \[ 1 0 0 \] = 0 \\sigma\_3 = C\_3 - \\sum\_\{i=1\}^\{3\} C\_B \* a\_\{i3\} = 0 - \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 0 \\\\ \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 1 \\\\ 0 \\\\ 0 \\end\{bmatrix\} = 0 σ3=C3−i=1∑3CB∗ai3=0−⎣⎡000⎦⎤T∗⎣⎡100⎦⎤=0

σ 4 = C 4 − ∑ i = 1 3 C B ∗ a i 4 = 0 − \[ 0 0 0 \] T ∗ \[ 0 1 0 \] = 0 \\sigma\_4 = C\_4 - \\sum\_\{i=1\}^\{3\} C\_B \* a\_\{i4\} = 0 - \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 0 \\\\ \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 0 \\\\ 1 \\\\ 0 \\end\{bmatrix\} = 0 σ4=C4−i=1∑3CB∗ai4=0−⎣⎡000⎦⎤T∗⎣⎡010⎦⎤=0

σ 5 = C 5 − ∑ i = 1 3 C B ∗ a i 5 = 0 − \[ 0 0 0 \] T ∗ \[ 0 0 1 \] = 0 \\sigma\_5 = C\_5 - \\sum\_\{i=1\}^\{3\} C\_B \* a\_\{i5\} = 0 - \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 0 \\\\ \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 1 \\end\{bmatrix\} = 0 σ5=C5−i=1∑3CB∗ai5=0−⎣⎡000⎦⎤T∗⎣⎡001⎦⎤=0

因此在 σ \\sigma σ 行填入  
 σ = \[ 50 100 0 0 0 \] \\sigma = \\begin\{bmatrix\} 50 & 100 & 0 & 0 & 0 \\end\{bmatrix\} σ=\[50100000\]

<table> 
 <thead> 
 <tr> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th>50</th> 
 <th>100</th> 
 <th>0</th> 
 <th>0</th> 
 <th>0</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> C B C_B CB</td> 
 <td>基</td> 
 <td> b b b</td> 
 <td> x 1 x_1 x1</td> 
 <td> x 2 x_2 x2</td> 
 <td> x 3 x_3 x3</td> 
 <td> x 4 x_4 x4</td> 
 <td> x 5 x_5 x5</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 3 x_3 x3</td> 
 <td>300</td> 
 <td>1</td> 
 <td>1</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 4 x_4 x4</td> 
 <td>400</td> 
 <td>2</td> 
 <td>1</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 5 x_5 x5</td> 
 <td>250</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> 50 \color{#FF0000}{50} 50</td> 
 <td> 100 \color{#FF0000}{100} 100</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 </tr> 
 </tbody> 
</table>

1.  因为  ∃ j \\exist j ∃j，使得  σ j > 0 \\sigma\_j > 0 σj>0 成立，所以还需要继续进行迭代；选择使得  σ j \\sigma\_j σj 取得最大值的变量，作为入基变量；

k = arg max ⁡ σ j , σ j > 0 k = \\argmax \\sigma\_j, \\sigma\_j > 0 k=argmaxσj,σj>0

σ = \[ 50 100 0 0 0 \] \\sigma = \\begin\{bmatrix\} 50 & 100 & 0 & 0 & 0 \\end\{bmatrix\} σ=\[50100000\]  
中最大值为100，其对应的变量为  x 2 x\_2 x2（位置），所以  x 2 x\_2 x2 作为入基变量， k = 2 k=2 k=2；

1.  计算  θ j \\theta\_j θj 确认出基变量，

θ j = b j / a j k \\theta\_j = b\_j / a\_\{jk\} θj=bj/ajk

求使得  θ j \\theta\_j θj 取得最小值的变量，作为出基变量；

θ 1 = b 1 / a 12 = 300 / 1 = 300 , ( x 3 ) \\theta\_1 = b\_1 / a\_\{12\} = 300 / 1 = 300, (x\_3) θ1=b1/a12=300/1=300,(x3)

θ 2 = b 2 / a 22 = 400 / 1 = 400 , ( x 4 ) \\theta\_2 = b\_2 / a\_\{22\} = 400 / 1 = 400, (x\_4) θ2=b2/a22=400/1=400,(x4)

θ 3 = b 3 / a 32 = 250 / 1 = 250 , ( x 5 ) \\theta\_3 = b\_3 / a\_\{32\} = 250 / 1 = 250, (x\_5) θ3=b3/a32=250/1=250,(x5)

所以， min ⁡ θ j = 250 \\min \\theta\_j = 250 minθj=250，对应的变量为  x 5 x\_5 x5 作为出基变量；

## 2.2. 第二次迭代 ##

1.  入基变量  x 2 x\_2 x2，出基变量  x 5 x\_5 x5；

<table> 
 <thead> 
 <tr> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th>50</th> 
 <th>100</th> 
 <th>0</th> 
 <th>0</th> 
 <th>0</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> C B C_B CB</td> 
 <td>基</td> 
 <td> b b b</td> 
 <td> x 1 x_1 x1</td> 
 <td> x 2 x_2 x2</td> 
 <td> x 3 x_3 x3</td> 
 <td> x 4 x_4 x4</td> 
 <td> x 5 x_5 x5</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 3 x_3 x3</td> 
 <td>300</td> 
 <td>1</td> 
 <td>1</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 4 x_4 x4</td> 
 <td>400</td> 
 <td>2</td> 
 <td>1</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 </tr> 
 <tr> 
 <td> 100 \color{#FF0000}{100} 100</td> 
 <td> x 2 \color{#FF0000}{x_2} x2</td> 
 <td>250</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

1.  进行初等行变换，将基变量  x 2 x\_2 x2 所在列中，除了基变量  x 2 x\_2 x2 所在的行为1，其余全部消去；

( − 1 ) ∗ \[ 250 0 1 0 0 1 \] + 1 ∗ \[ 300 1 1 1 0 0 \] = \[ 50 1 0 1 0 − 1 \] (-1) \* \\begin\{bmatrix\} 250 & 0 & 1 & 0 & 0 & 1 \\end\{bmatrix\} + 1 \* \\begin\{bmatrix\} 300 & 1 & 1 & 1 & 0 & 0 \\end\{bmatrix\} = \\begin\{bmatrix\} 50 & 1 & 0 & 1 & 0 & -1 \\end\{bmatrix\} (−1)∗\[25001001\]\+1∗\[30011100\]=\[501010−1\]

( − 1 ) ∗ \[ 250 0 1 0 0 1 \] + 1 ∗ \[ 400 2 1 0 1 0 \] = \[ 150 2 0 0 1 − 1 \] (-1) \* \\begin\{bmatrix\} 250 & 0 & 1 & 0 & 0 & 1 \\end\{bmatrix\} + 1 \* \\begin\{bmatrix\} 400 & 2 & 1 & 0 & 1 & 0 \\end\{bmatrix\} = \\begin\{bmatrix\} 150 & 2 & 0 & 0 & 1 & -1 \\end\{bmatrix\} (−1)∗\[25001001\]\+1∗\[40021010\]=\[1502001−1\]

<table> 
 <thead> 
 <tr> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th>50</th> 
 <th>100</th> 
 <th>0</th> 
 <th>0</th> 
 <th>0</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> C B C_B CB</td> 
 <td>基</td> 
 <td> b b b</td> 
 <td> x 1 x_1 x1</td> 
 <td> x 2 x_2 x2</td> 
 <td> x 3 x_3 x3</td> 
 <td> x 4 x_4 x4</td> 
 <td> x 5 x_5 x5</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 3 x_3 x3</td> 
 <td> 50 \color{#FF0000}{50} 50</td> 
 <td> 1 \color{#FF0000}{1} 1</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 1 \color{#FF0000}{1} 1</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> − 1 \color{#FF0000}{-1} −1</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 4 x_4 x4</td> 
 <td> 150 \color{#FF0000}{150} 150</td> 
 <td> 2 \color{#FF0000}{2} 2</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 1 \color{#FF0000}{1} 1</td> 
 <td> − 1 \color{#FF0000}{-1} −1</td> 
 </tr> 
 <tr> 
 <td>100</td> 
 <td> x 2 x_2 x2</td> 
 <td>250</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

1.  计算检验和

σ j = C j − ∑ i C B ∗ a i j \\sigma\_j = C\_j - \\sum\_\{i\} C\_B \* a\_\{ij\} σj=Cj−i∑CB∗aij

σ 1 = C 1 − C B ∗ a i 1 = 50 − \[ 0 0 100 \] T ∗ \[ 1 2 0 \] = 50 , \\sigma\_1 = C\_1 - C\_B \* a\_\{i1\} = 50 - \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 100 \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 1 \\\\ 2 \\\\ 0 \\end\{bmatrix\} = 50, σ1=C1−CB∗ai1=50−⎣⎡00100⎦⎤T∗⎣⎡120⎦⎤=50,

σ 2 = C 2 − C B ∗ a i 2 = 100 − \[ 0 0 100 \] T ∗ \[ 0 0 1 \] = 0 , \\sigma\_2 = C\_2 - C\_B \* a\_\{i2\} = 100 - \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 100 \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 1 \\end\{bmatrix\} = 0, σ2=C2−CB∗ai2=100−⎣⎡00100⎦⎤T∗⎣⎡001⎦⎤=0,

σ 3 = C 3 − C B ∗ a i 3 = 0 − \[ 0 0 100 \] T ∗ \[ 1 0 0 \] = 0 , \\sigma\_3 = C\_3 - C\_B \* a\_\{i3\} = 0 - \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 100 \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 1 \\\\ 0 \\\\ 0 \\end\{bmatrix\} = 0, σ3=C3−CB∗ai3=0−⎣⎡00100⎦⎤T∗⎣⎡100⎦⎤=0,

σ 4 = C 4 − C B ∗ a i 4 = 0 − \[ 0 0 100 \] T ∗ \[ 0 1 0 \] = 0 , \\sigma\_4 = C\_4 - C\_B \* a\_\{i4\} = 0 - \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 100 \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 0 \\\\ 1 \\\\ 0 \\end\{bmatrix\} = 0, σ4=C4−CB∗ai4=0−⎣⎡00100⎦⎤T∗⎣⎡010⎦⎤=0,

σ 5 = C 5 − C B ∗ a i 5 = 0 − \[ 0 0 100 \] T ∗ \[ − 1 − 1 1 \] = − 100 , \\sigma\_5 = C\_5 - C\_B \* a\_\{i5\} = 0 - \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 100 \\end\{bmatrix\}^T \* \\begin\{bmatrix\} -1 \\\\ -1 \\\\ 1 \\end\{bmatrix\} = -100, σ5=C5−CB∗ai5=0−⎣⎡00100⎦⎤T∗⎣⎡−1−11⎦⎤=−100,

<table> 
 <thead> 
 <tr> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th>50</th> 
 <th>100</th> 
 <th>0</th> 
 <th>0</th> 
 <th>0</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> C B C_B CB</td> 
 <td>基</td> 
 <td> b b b</td> 
 <td> x 1 x_1 x1</td> 
 <td> x 2 x_2 x2</td> 
 <td> x 3 x_3 x3</td> 
 <td> x 4 x_4 x4</td> 
 <td> x 5 x_5 x5</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 3 x_3 x3</td> 
 <td>50</td> 
 <td>1</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>-1</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 4 x_4 x4</td> 
 <td>150</td> 
 <td>2</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 <td>-1</td> 
 </tr> 
 <tr> 
 <td>100</td> 
 <td> x 2 x_2 x2</td> 
 <td>250</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> 50 \color{#FF0000}{50} 50</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> − 100 \color{#FF0000}{-100} −100</td> 
 </tr> 
 </tbody> 
</table>

1.  因为  ∃ j \\exist j ∃j，使得  σ j > 0 \\sigma\_j > 0 σj>0 成立，所以还需要继续进行迭代；选择使得  σ j \\sigma\_j σj 取得最大值的变量，作为入基变量，

k = arg max ⁡ σ j , σ j > 0 k = \\argmax \\sigma\_j, \\sigma\_j > 0 k=argmaxσj,σj>0

σ = \[ 50 0 0 0 − 100 \] \\sigma = \\begin\{bmatrix\} 50 & 0 & 0 & 0 & -100 \\end\{bmatrix\} σ=\[50000−100\]  
中最大值为50，其对应的变量为  x 1 x\_1 x1（位置），所以  x 1 x\_1 x1 作为入基变量， k = 1 k=1 k=1；

1.  计算  θ j \\theta\_j θj 确认出基变量，

θ j = b j / a j k \\theta\_j = b\_j / a\_\{jk\} θj=bj/ajk

求使得  θ j \\theta\_j θj 取得最小值的变量，作为出基变量；

θ 1 = b 1 / a 11 = 50 / 1 = 50 , ( x 3 ) \\theta\_1 = b\_1 / a\_\{11\} = 50 / 1 = 50, (x\_3) θ1=b1/a11=50/1=50,(x3)

θ 2 = b 2 / a 21 = 150 / 2 = 75 , ( x 4 ) \\theta\_2 = b\_2 / a\_\{21\} = 150 / 2 = 75, (x\_4) θ2=b2/a21=150/2=75,(x4)

θ 3 = b 3 / a 31 = 250 / 0 = ? , ( x 5 ) \\theta\_3 = b\_3 / a\_\{31\} = 250 / 0 = ? , (x\_5) θ3=b3/a31=250/0=?,(x5)

所以， min ⁡ θ j = 50 \\min \\theta\_j = 50 minθj=50，对应的变量为  x 3 x\_3 x3 作为出基变量；

## 2.3. 第三次迭代 ##

1.  入基变量  x 1 x\_1 x1，出基变量  x 3 x\_3 x3；

<table> 
 <thead> 
 <tr> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th>50</th> 
 <th>100</th> 
 <th>0</th> 
 <th>0</th> 
 <th>0</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> C B C_B CB</td> 
 <td>基</td> 
 <td> b b b</td> 
 <td> x 1 x_1 x1</td> 
 <td> x 2 x_2 x2</td> 
 <td> x 3 x_3 x3</td> 
 <td> x 4 x_4 x4</td> 
 <td> x 5 x_5 x5</td> 
 </tr> 
 <tr> 
 <td> 50 \color{#FF0000}{50} 50</td> 
 <td> x 1 \color{#FF0000}{x_1} x1</td> 
 <td>50</td> 
 <td>1</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>-1</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 4 x_4 x4</td> 
 <td>150</td> 
 <td>2</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 <td>-1</td> 
 </tr> 
 <tr> 
 <td> 100 100 100</td> 
 <td> x 2 x_2 x2</td> 
 <td>250</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

1.  进行初等行变换，将基变量  x 1 x\_1 x1 所在列中，除了基变量  x 1 x\_1 x1 所在的行为1，其余全部消去；

( − 2 ) ∗ \[ 50 1 0 1 0 − 1 \] + 1 ∗ \[ 150 2 0 0 1 − 1 \] = \[ 50 0 0 − 2 1 1 \] (-2) \* \\begin\{bmatrix\} 50 & 1 & 0 & 1 & 0 & -1 \\end\{bmatrix\} + 1 \* \\begin\{bmatrix\} 150 & 2 & 0 & 0 & 1 & -1 \\end\{bmatrix\} = \\begin\{bmatrix\} 50 & 0 & 0 & -2 & 1 & 1 \\end\{bmatrix\} (−2)∗\[501010−1\]\+1∗\[1502001−1\]=\[5000−211\]

<table> 
 <thead> 
 <tr> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th>50</th> 
 <th>100</th> 
 <th>0</th> 
 <th>0</th> 
 <th>0</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> C B C_B CB</td> 
 <td>基</td> 
 <td> b b b</td> 
 <td> x 1 x_1 x1</td> 
 <td> x 2 x_2 x2</td> 
 <td> x 3 x_3 x3</td> 
 <td> x 4 x_4 x4</td> 
 <td> x 5 x_5 x5</td> 
 </tr> 
 <tr> 
 <td>50</td> 
 <td> x 1 x_1 x1</td> 
 <td>50</td> 
 <td>1</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>-1</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 4 x_4 x4</td> 
 <td> 50 \color{#FF0000}{50} 50</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> − 2 \color{#FF0000}{-2} −2</td> 
 <td> 1 \color{#FF0000}{1} 1</td> 
 <td> 1 \color{#FF0000}{1} 1</td> 
 </tr> 
 <tr> 
 <td>100</td> 
 <td> x 2 x_2 x2</td> 
 <td>250</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 <td></td> 
 </tr> 
 </tbody> 
</table>

1.  计算检验和  
     σ j = C j − ∑ i C B ∗ a i j \\sigma\_j = C\_j - \\sum\_\{i\} C\_B \* a\_\{ij\} σj=Cj−i∑CB∗aij

σ 1 = C 1 − C B ∗ a i 1 = 50 − \[ 50 0 100 \] T ∗ \[ 1 0 0 \] = 0 , \\sigma\_1 = C\_1 - C\_B \* a\_\{i1\} = 50 - \\begin\{bmatrix\} 50 \\\\ 0 \\\\ 100 \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 1 \\\\ 0 \\\\ 0 \\end\{bmatrix\} = 0, σ1=C1−CB∗ai1=50−⎣⎡500100⎦⎤T∗⎣⎡100⎦⎤=0,

σ 2 = C 2 − C B ∗ a i 2 = 100 − \[ 50 0 100 \] T ∗ \[ 0 0 1 \] = 0 , \\sigma\_2 = C\_2 - C\_B \* a\_\{i2\} = 100 - \\begin\{bmatrix\} 50 \\\\ 0 \\\\ 100 \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 0 \\\\ 0 \\\\ 1 \\end\{bmatrix\} = 0, σ2=C2−CB∗ai2=100−⎣⎡500100⎦⎤T∗⎣⎡001⎦⎤=0,

σ 3 = C 3 − C B ∗ a i 3 = 0 − \[ 50 0 100 \] T ∗ \[ 1 − 2 0 \] = − 50 , \\sigma\_3 = C\_3 - C\_B \* a\_\{i3\} = 0 - \\begin\{bmatrix\} 50 \\\\ 0 \\\\ 100 \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 1 \\\\ -2 \\\\ 0 \\end\{bmatrix\} = -50, σ3=C3−CB∗ai3=0−⎣⎡500100⎦⎤T∗⎣⎡1−20⎦⎤=−50,

σ 4 = C 4 − C B ∗ a i 4 = 0 − \[ 50 0 100 \] T ∗ \[ 0 1 0 \] = 0 , \\sigma\_4 = C\_4 - C\_B \* a\_\{i4\} = 0 - \\begin\{bmatrix\} 50 \\\\ 0 \\\\ 100 \\end\{bmatrix\}^T \* \\begin\{bmatrix\} 0 \\\\ 1 \\\\ 0 \\end\{bmatrix\} = 0, σ4=C4−CB∗ai4=0−⎣⎡500100⎦⎤T∗⎣⎡010⎦⎤=0,

σ 5 = C 5 − C B ∗ a i 5 = 0 − \[ 50 0 100 \] T ∗ \[ − 1 1 1 \] = − 50 , \\sigma\_5 = C\_5 - C\_B \* a\_\{i5\} = 0 - \\begin\{bmatrix\} 50 \\\\ 0 \\\\ 100 \\end\{bmatrix\}^T \* \\begin\{bmatrix\} -1 \\\\ 1 \\\\ 1 \\end\{bmatrix\} = -50, σ5=C5−CB∗ai5=0−⎣⎡500100⎦⎤T∗⎣⎡−111⎦⎤=−50,

<table> 
 <thead> 
 <tr> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th>50</th> 
 <th>100</th> 
 <th>0</th> 
 <th>0</th> 
 <th>0</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> C B C_B CB</td> 
 <td>基</td> 
 <td> b b b</td> 
 <td> x 1 x_1 x1</td> 
 <td> x 2 x_2 x2</td> 
 <td> x 3 x_3 x3</td> 
 <td> x 4 x_4 x4</td> 
 <td> x 5 x_5 x5</td> 
 </tr> 
 <tr> 
 <td>50</td> 
 <td> x 1 x_1 x1</td> 
 <td>50</td> 
 <td>1</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>-1</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 4 x_4 x4</td> 
 <td>50</td> 
 <td>0</td> 
 <td>0</td> 
 <td>-2</td> 
 <td>1</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td>100</td> 
 <td> x 2 x_2 x2</td> 
 <td>250</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> − 50 \color{#FF0000}{-50} −50</td> 
 <td> 0 \color{#FF0000}{0} 0</td> 
 <td> − 50 \color{#FF0000}{-50} −50</td> 
 </tr> 
 </tbody> 
</table>

1.  因为  ∀ j \\forall j ∀j，使得  σ j ≤ 0 \\sigma\_j \\leq 0 σj≤0 成立，所以迭代终止，算法结束；
2.  最终解

<table> 
 <thead> 
 <tr> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th> C C C</th> 
 <th>50</th> 
 <th>100</th> 
 <th>0</th> 
 <th>0</th> 
 <th>0</th> 
 </tr> 
 </thead> 
 <tbody> 
 <tr> 
 <td> C B C_B CB</td> 
 <td>基</td> 
 <td> b b b</td> 
 <td> x 1 x_1 x1</td> 
 <td> x 2 x_2 x2</td> 
 <td> x 3 x_3 x3</td> 
 <td> x 4 x_4 x4</td> 
 <td> x 5 x_5 x5</td> 
 </tr> 
 <tr> 
 <td>50</td> 
 <td> x 1 \color{#FF0000}{x_1} x1</td> 
 <td> 50 \color{#FF0000}{50} 50</td> 
 <td>1</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>-1</td> 
 </tr> 
 <tr> 
 <td>0</td> 
 <td> x 4 \color{#FF0000}{x_4} x4</td> 
 <td> 50 \color{#FF0000}{50} 50</td> 
 <td>0</td> 
 <td>0</td> 
 <td>-2</td> 
 <td>1</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td>100</td> 
 <td> x 2 \color{#FF0000}{x_2} x2</td> 
 <td> 250 \color{#FF0000}{250} 250</td> 
 <td>0</td> 
 <td>1</td> 
 <td>0</td> 
 <td>0</td> 
 <td>1</td> 
 </tr> 
 <tr> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td> σ \sigma σ</td> 
 <td>0</td> 
 <td>0</td> 
 <td>-50</td> 
 <td>0</td> 
 <td>-50</td> 
 </tr> 
 </tbody> 
</table>

解为：  
 \{ x 1 = 50 ; x 2 = 250 ; x 3 = 0 ; x 4 = 50 ; x 5 = 0. \\begin\{cases\} x\_1 = 50; \\\\ x\_2 = 250; \\\\ x\_3 = 0; \\\\ x\_4 = 50; \\\\ x\_5 = 0. \\end\{cases\} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧x1=50;x2=250;x3=0;x4=50;x5=0.

max ⁡ z = 50 x 1 + 100 x 2 = 50 ∗ 50 + 100 ∗ 250 = 27500. \\max z = 50x\_1 + 100x\_2 = 50 \* 50 + 100 \* 250 = 27500. maxz=50x1\+100x2=50∗50\+100∗250=27500.

# 3. 算法 #

> 1、 标准化（引入松弛变量）；  
> 2、构造初始单纯形表；  
> 3、确定基变量和非基变量；  
> 4、计算检验和；  
> 5、确定入基变量和出基变量；  
> 6、初等行变换；  
> 7、重复4-6步，直到所有的检验和小于等于0；  
> 8、 b b b 值就是对应的基变量的解，非基变量的解为0。

# 4. 手稿 #

![20200919121330649.jpg_x-oss-][]

# 5. 参考 #

1.  [cruelty\_angel：单纯形法][cruelty_angel]
2.  [妙恋非恋：单纯形法的计算步骤][Link 1]
3.  [mohu：常用数学符号的 LaTeX 表示方法][mohu_ LaTeX]
4.  [CodeAllen的博客：Markdown文字添加颜色方法总结（珍藏）][CodeAllen_Markdown]

![图片来自网络][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center]

[20200919121330649.jpg_x-oss-]: /images/20210923/13d2ceeaaace4aa1bf123fd77927c389.png
[cruelty_angel]: https://www.cnblogs.com/cruelty_angel/p/10493527.html
[Link 1]: https://wenku.baidu.com/view/02407993dd88d0d233d46ab7.html
[mohu_ LaTeX]: http://www.mohu.org/info/symbols/symbols.htm
[CodeAllen_Markdown]: https://blog.csdn.net/super828/article/details/99055541
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70_pic_center]: /images/20210923/db8d50eb1be44bb99fffb91e999df074.png