更多专业的人工智能相关文章，微信搜索  : robot-learner ， 或扫码
 
 
 
 
最优化问题(Optimization)是人工智能和机器学习的最底层的基石和明珠。系统性的讲最优化问题在一篇文章中实在无法办到。
 
 
 
喜欢最优化问题的读者不妨先关注一下这个公众号，因为后面我们会用一个系列来讨论最优化问题。
 
 
 
 
 
今天我们简单的讨论一下，约束最优化问题中常常预见的几个名词关系，比如原问题（primal problem），对偶问题（dual problem）, KKT约束条件，和拉格朗日符号等。他们之间的关系是什么？
 
 
 
1.
 
 
 
什么是最优化问题？ 比如我们要找到最佳的变量值x0，从而使得下列的方程达到最小值：
 
 
 
 
             
 
上面式子表的的意思就是一个最小化问题，即寻找最佳的变量，从而使得f(x)方程的值最小。
 
如果f(x)满足凸函数特性(convex function)，上面问题是相对容易的。
 
 
 
2.
 
 
 
但是问题来了，有时候我们需要对变量x做一些约束，比如在一定的距离内找到短的路径等。最小化问题就成了约束最小化问题。用公式表达就是这个意思：
 
 
 
 
 
 
 
 
上式的意思是：我们仍然要找到x使得f(x)最小，但是x也必须满足条件 h(x)<=0。这个约束条件在实际情况中很普遍。但是却使得最优化问题不再具有凸函数特性，从而大大增加了寻找最值的难度。
 
 
 
3.
 
 
 
这个问题的救星就是原问题和对偶问题的关系。上面的式子称为原问题或者primal problem，我们可以把这个问题转化为一个标准的拉格朗日dual problem 或者对偶问题来解决：
 
 
 
 
 
 
 
 
 
 
上面式子中，g(λ)= L(x,λ) 以x作为变量的最小值  , 并且 L(λ) = f(x) + λh(x) 叫做拉格朗日式子。λ就是新引入的限制因子。这个形式的表达式在机器学习算法中很常见。如果要对算法中的参数做一些约束，很多时候就是加上这种形式的限制因子。
 
 
 
需要注意的是上面的对偶问题可以证明只是为原问题提供了一个下限：假设 f* 是f(x)的最小值，g*是g(λ)的最小值，那么存在这样的的关系 f* >= g*。 但在满足一定的条件下，如KKT条件，可以证明 原问题和对偶问题等价即 f* = g*。
 
 
 
为什么要解决对偶问题？因为有的时候对偶问题更好解决，并且在一定条件下，两者等价。即使条件不满足，我们仍然获得一个下限，在实际问题中通常可行。
 
 
 
我们可以注意到上面的对偶问题中，其实是先求拉格朗日式子最小值，再求最大值。如果我们把顺序颠倒一下，先求max 再求min, 则这个问题完全等价于原问题：
 
 
 
 
 
 
 
 
4.
 
 
 
我们注意最小化问题中的条件，一个是 h(x)<=0， 另一个是λ>=0，并且在拉格朗日式子中λ前面的符号是正的。如果你的限制条件 h(x)>=0, 那么λ前面的符号需要改为负的。
 
 
 
为什么一定要这样？因为对偶问题提供的是原问题的一个下限答案。 在最小化问题中，只有提供下限才有意义， 如果提供的是一个上限，那么直接用无穷大就好了。
 
 
 
 
 
为什么我们只讲最小化问题，而不是最大化问题？因为最大化问题只需前面添加一个负号，就可以转化为最小化问题了。
 
 
 
 
 
上面也说到了，对偶问题很多时候只是一个下限。但实际问题中没有多大关系。另外，在利用机器学习算法解决问题时候，我们只是需要利用约束条件来限制一下参数以求稀疏化的目的。所以λ都是我们事先给定的或者用validation的方法来挑选。所以上面的有约束的对偶问题就进一步简化为:
 
 
 
 
 
这个形式大家就更加熟悉了。

 
 
2.1 求解梯度的两种方法
 
 
以$f(x,y)={{x}^{2}}+{{y}^{3}}$为例，很容易得到：
 
 
$\nabla f=\left[ \begin{aligned}& \frac{\partial f}{\partial x} \\& \frac{\partial f}{\partial y} \\\end{aligned} \right]=\left[ \begin{aligned}& 2x \\& 3{{y}^{2}} \\\end{aligned} \right]$
 
 
这样就很容易求得某一点的梯度。
 
 
但是如果梯度的表达式很难写出来，或者根本就写不出来的时候，尤其定义去求梯度可是可以的：
 
 
$\nabla f=\left[ \begin{aligned}& \frac{\partial f}{\partial x} \\& \frac{\partial f}{\partial y} \\\end{aligned} \right]=\left[ \begin{aligned}& \frac{f(x+\Delta x,y)-f(x,y)}{\Delta x} \\& \frac{f(x,y+\Delta y)-f(x,y)}{\Delta y} \\\end{aligned} \right]$
 
 
在实际算的过程中这里的$\Delta x$，$\Delta y$也不用取太小一般$1\times {{10}^{-7}}$左右就可以了。
 
 
2.2 某些有约束优化问题可以转化为无约束优化问题：
 
 
\[\begin{aligned}& \operatorname{minimize}\text{  }f({{x}_{1}},{{x}_{2}})\text{         }\operatorname{minimize}\text{  }f({{x}_{1}},{{x}_{2}}) \\& \text{               }{{x}_{1}}>0\text{      }\Rightarrow \text{                   }{{x}_{1}}={{{\hat{x}}}^{2}}_{1} \\& \text{               }{{x}_{2}}\le -30\text{                         }-\text{30}-{{x}_{2}}\text{=}{{{\hat{x}}}^{2}}_{2}\text{ }\Rightarrow -\text{30}-{{{\hat{x}}}^{2}}_{2}\text{=}{{x}_{2}} \\\end{aligned}\]
 
 
把上式中左边的不等式优化，转化为右边的等式优化，再把等式代入目标函数中，形成了式(24)这样的无约束优化问题：
 
 
\[\operatorname{minimize}\text{  }f({{\hat{x}}_{1}},{{\hat{x}}_{2}})\]
 
 
通过优化求解得到满足上式的次优解$\left( {{{{\hat{x}}'}}_{1}},{{{{\hat{x}}'}}_{2}} \right)$，则原优化问题的解可以写为：
 
 
\[\begin{aligned}& \text{ }{{x}_{1}}={{\left( {{{{\hat{x}}'}}_{\text{1}}} \right)}^{\text{2}}} \\& {{x}_{2}}\text{=}-\text{30}-{{\left( {{{{\hat{x}}'}}_{2}} \right)}^{\text{2}}} \\\end{aligned}\]
 
 
这样的做法会增加目标函数的非线性度，但是很好的把有约束问题转变为无约束问题。下面这个带约束的优化问题同样可以用上述方式处理：
 
 
\[\begin{aligned}& \operatorname{minimize}\text{  }f({{x}_{1}},{{x}_{2}})\text{         }\operatorname{minimize}\text{  }f({{x}_{1}},{{x}_{2}}) \\ & \text{               3}\le {{x}_{1}}\le 12\text{      }\Rightarrow \text{                   } \\\end{aligned}\]             
 
 
这里的转化，我想着用Sigmoid函数(logistic函数)：
 
 
$f\left( x \right)=\frac{1}{1+{{e}^{-x}}}$                         
 
 
它的图像如下：
 
 
 
 
这样就可以用下面这个式子代替上述对${{x}_{1}}$的约束：
 
 
${{x}_{1}}=\frac{9}{1+{{e}^{-\hat{x}}}}+3$                    
 
 
它的图像如下
 
 
 
 
 
 
 
 
 
 
 
 
 
转载于:https://www.cnblogs.com/duyiExplorer/p/11177340.html

 
 
《运筹学》第二章，对偶问题。本篇文章的目标是，找到原问题与对偶问题的规律，给定原问题，快速写出其对偶问题（在考试中可以节省时间）。
 
 
该方法是同学给我讲的，在此感谢。
 以《运筹学基础及其应用(胡运权)》第二章例2为例：
 $$\begin{gathered} \min z=7x_1+4x_2-3x_3 \\ s.t.\{\begin{array}{l}-4x_1+2x_2-6x_3\le 24\\ -3x_1-6x_2-4x_3\ge 15\\ 5x_2+3x_3=30\\ x_1\le 0,x_2无约束,x_3\ge 0\end{array} \end{gathered}$$
 
要求写出它的对偶问题。当然可以用书上的方法，不再赘述。这里我们掌握一个规律，叫做“大同小异”，有了这个规律可以直接写出它的对偶问题。
 “小”，即原问题是求最小值，“异”，即变化。具体要变化什么，且看下文。
 
首先，写出系数矩阵$A$，向量$B$和$C$：
 $$A=\left[\begin{array}{ccc}-4& 2& -6\\ -3& -6& -4\\ 0& 5& 3\end{array}\right],B=\left[\begin{array}{c}24\\ 15\\ 30\end{array}\right],C=\left[\begin{array}{ccc}7& 4& -3\end{array}\right]$$
 
对偶问题的矩阵
 $$A^T=\left[\begin{array}{ccc}-4& -3& 0\\ 2& -6& 5\\ -6& -4& 3\end{array}\right],C^T=\left[\begin{array}{c}7\\ 4\\ -3\end{array}\right],B^T=\left[\begin{array}{ccc}24& 15& 30\end{array}\right]$$
 
先把对偶问题的大概框架写好：
 $$\begin{gathered} \max w=24y_1+15y_2+30y_3 \\ s.t.\{\begin{array}{l}-4y_1-3y_2+0y_{3}7\\ 2y_1-6y_2+5y_{3}4\\ -6y_1-4y_2+3y_3-3\\ y_1{y}_2{y}_3\end{array} \end{gathered}$$
 
也就是不知道约束条件和变量的符号。
 
记住以下几点：
 
 
原问题第$i$个变量符号对应对偶问题第$i$个约束，同样，
 原问题第$i$个约束对应对偶问题第$i$个变量符号。
 二者的大于或小于符号方向有关联。
 $$\begin{gathered} x_1⟷-4y_1-3y_2+0y_3 \\ {x}_2⟷2y_1-6y_2+5y_3 \\ {x}_3⟷-6y_1-4y_2+3y_3 \\ {y}_1⟷-4x_1+2x_2-6x_3 \\ {y}_2⟷-3x_1-6x_2-4x_3 \\ {y}_3⟷5x_2+3x_3 \end{gathered}$$
 
 
“小异”，原问题求最小值。那么
 原问题第$i$个变量符号与对偶问题第$i$个约束符号相反；
 $$\begin{gathered} \because x_1\le 0,\therefore -4y_1-3y_2+0y_3\ge 7; \\ \because x_2无约束,\therefore 2y_1-6y_2+5y_3=4; \\ \because x_3\ge 0,\therefore -6y_1-4y_2+3y_3\le -3; \end{gathered}$$
 
因为已经变过一次了，所以原问题第$i$个约束与对偶问题第$i$个变量符号相同。只记前面一条即可。
 $$\begin{gathered} \because -4x_1+2x_2-6x_3\le 24,\therefore y_1\le 0; \\ \because -3x_1-6x_2-4x_3\ge 15,\therefore y_2\ge 15; \\ \because 5x_2+3x_3=30,\therefore y_3无约束; \end{gathered}$$
 
 
“大同”，原问题求最大值。那么
 原问题第$i$个变量符号与对偶问题第$i$个约束符号相同；
 所以原问题第$i$个约束与对偶问题第$i$个变量符号相反，
 因为必须变化一次。
 我们首先都讨论约束条件的符号方向，再考虑变量的符号方向，这样不容易乱。
 
 
这样对偶问题也就写出来了
 $$\begin{gathered} \max w=24y_1+15y_2+30y_3 \\ s.t.\{\begin{array}{l}-4y_1-3y_2+0y_3\ge 7\\ 2y_1-6y_2+5y_3=4\\ -6y_1-4y_2+3y_3\le -3\\ y_1\le 0,y_2\ge 0,y_3无约束\end{array} \end{gathered}$$
 
 
可以再看一道题，选自《运筹学习题集(胡运权主编)》2.6(a)，也是一道“小异”：
 
$$\begin{gathered} \min z=3x_1+2x_2-3x_3+4x_4 \\ s.t.\{\begin{array}{l}{x}_1-2x_2+3x_3+4x_4\le 3\\ x_2+3x_3+4x_4\ge -5\\ 2x_1-3x_2-7x_3-4x_4=2\\ x_1\ge 0,x_2,x_3无约束,x_4\le 0\end{array} \end{gathered}$$
 
首先，写出系数矩阵$A$，向量$B$和$C$：
 $$A=\left[\begin{array}{cccc}1& -2& 3& 4\\ 0& 1& 3& 4\\ 2& -3& -7& -4\end{array}\right],B=\left[\begin{array}{c}3\\ -5\\ 2\end{array}\right],C=\left[\begin{array}{cccc}3& 2& -3& 4\end{array}\right]$$
 
对偶问题的矩阵
 $$A^T=\left[\begin{array}{ccc}1& 0& 2\\ 2& 1& -3\\ 3& 3& -7\\ 4& 4& 4\end{array}\right],C^T=\left[\begin{array}{c}3\\ 2\\ -3\\ 4\end{array}\right],B^T=\left[\begin{array}{ccc}3& -5& 2\end{array}\right]$$
 
答案是
 $$\begin{gathered} \max w=3y_1-5y_2+2y_3 \\ s.t.\{\begin{array}{l}{y}_1+0y_2+2y_3\le 3\\ -2y_1+y_2-3y_3=2\\ 3y_1+3y_2-7y_3=-3\\ 4y_1+4y_2+4y_3\ge 4\\ y_1\le 0,y_2\ge 0,y_3无约束\end{array} \end{gathered}$$
 
over!
 
个人作业，转载需注明网址。谢谢。
 https://blog.csdn.net/Wolf_AgOH/article/details/121185244

 
文章目录
 
人工变量法
1. 大Ｍ法
1.1. 题目
1.2. 转化为标准型
1.3. 添加人工变量
  
2. 两阶段法
2.1. 步骤
2.2. 题目
2.2.1. 转化为标准型
2.2.2. 添加人工变量
2.2.3. 两阶段
  
  
3. 参考

 
人工变量法
 
在一些模型中并不包含单位矩阵，为了得到一组基向量和初始可行解，在约束条件的等式左端添加一组虚拟变量，得到一组基向量。这种人为添加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解。
 
1. 大Ｍ法
 
大M法，通过引进人工变量，构造一个辅助的线性规划问题， 然后由辅助的线性规划问题找出原问题的第一个初始可行基，在此基础上，利用单纯形法求出原问题的最优解。
 
1.1. 题目
 
用大 M 法解下列线性规划
 
$$\max Z=3x_1+2x_2-x_3$$
 
$$\text{s.t.}\{\begin{array}{l}-4x_1+3x_2+x_3\ge 4\\ x_1-x_2+2x_3\le 10\\ -2x_1+2x_2-x_3=-1\\ x_i\ge 0,i=1,2,3\end{array}$$
 
1.2. 转化为标准型
 
首先将线性规划转换成标准型
 
$$\max Z=3x_1+2x_2-x_3+0x_4+0x_5$$
 
$$\text{s.t.}\{\begin{array}{l}-4x_1+3x_2+x_3-x_4=4\\ x_1-x_2+2x_3+x_5=10\\ 2x_1-2x_2+x_3=1\\ x_i\ge 0,i=1,2,\dots ,5\end{array}$$
 
画出其对应的单纯形表（如果这一步，还不会的话，可以参考单纯形法求解步骤：一个简单例子）
 
$C$
$C$
$C$
3
2
-1
0
0
$C_B$
基
$b$
$x_1$
$x_2$
$x_3$
$x_4$
$x_5$
4
-4
3
1
-1
0
10
1
-1
2
0
1
1
2
-2
1
0
0
$\sigma$
$\sigma$
$\sigma$

在这个表的系数矩阵中，没有单位矩阵存在，所以无法直接进行求解，需要使用一些辅助手段–人工变量法。
 
1.3. 添加人工变量
 
$$\max Z=3x_1+2x_2-x_3+0x_4+0x_5-M{x}_6-M{x}_7$$
 
$$\text{s.t.}\{\begin{array}{l}-4x_1+3x_2+x_3-x_4+x_6=4\\ x_1-x_2+2x_3+x_5=10\\ 2x_1-2x_2+x_3+x_7=1\\ x_i\ge 0,i=1,2,\dots ,7\end{array}$$
 
$C$
$C$
$C$
3
2
-1
0
0
-M
-M
$C_B$
基
$b$
$x_1$
$x_2$
$x_3\downarrow$
$x_4$
$x_5$
$x_6$
$x_7$
-M
$x_6$
4
-4
3
1
-1
0
1
0
0
$x_5$
10
1
-1
2
0
1
0
0
-M
$\leftarrow x_7$
1
2
-2
[1]
0
0
0
1
$\sigma$
$\sigma$
$\sigma$
3-2M
2+M
-1+2M
-M
0
0
0
入基变量 $x_3$，出基变量 $x_7$；
 
$C$
$C$
$C$
3
2
-1
0
0
-M
-M
$C_B$
基
$b$
$x_1$
$x_2\downarrow$
$x_3$
$x_4$
$x_5$
$x_6$
$x_7$
-M
$\leftarrow x_6$
3
-6
[5]
0
-1
0
1
-1
0
$x_5$
8
-3
3
0
0
1
0
-2
-1
$x_3$
1
2
-2
1
0
0
0
1
$\sigma$
$\sigma$
$\sigma$
5-6M
5M
0
-M
0
0
1-M
入基变量 $x_2$，出基变量 $x_6$；
 
$C$
$C$
$C$
3
2
-1
0
0
-M
-M
$C_B$
基
$b$
$x_1\downarrow$
$x_2$
$x_3$
$x_4$
$x_5$
$x_6$
$x_7$
2
$x_2$
$\frac{3}{5}$
$-\frac{6}{5}$
1
0
$-\frac{1}{5}$
0
$\frac{1}{5}$
$-\frac{1}{5}$
0
$\leftarrow x_5$
$\frac{31}{5}$
[$\frac{3}{5}$]
0
0
$\frac{3}{5}$
1
$-\frac{3}{5}$
$-\frac{7}{5}$
-1
$x_3$
$\frac{11}{5}$
$-\frac{2}{5}$
0
1
$-\frac{2}{5}$
0
$\frac{2}{5}$
$\frac{3}{5}$
$\sigma$
$\sigma$
$\sigma$
5
0
0
0
0
-M
1-M
入基变量 $x_1$，出基变量 $x_5$；
 
$C$
$C$
$C$
3
2
-1
0
0
-M
-M
$C_B$
基
$b$
$x_1$
$x_2$
$x_3$
$x_4$
$x_5$
$x_6$
$x_7$
2
$x_2$
13
0
1
0
1
2
1
-3
3
$x_1$
$\frac{31}{3}$
1
0
0
1
$\frac{5}{3}$
-1
$-\frac{7}{3}$
-1
$x_3$
$\frac{19}{3}$
0
0
1
0
$\frac{2}{3}$
0
$-\frac{1}{3}$
$\sigma$
$\sigma$
$\sigma$
0
0
0
-5
$-\frac{25}{3}$
1-M
$\frac{38}{3}$-M
因为 ${\sigma }_j\le 0$，对所有的 $j$ 成立，所以迭代结束。
 最优解为
 
$$x^{\ast }=(\frac{31}{3},13,\frac{19}{3},0,0{)}^T,$$
 
$$Z^{\ast }=3x_1+2x_2-x_3=3\ast \frac{31}{3}+2\ast 13-\frac{19}{3}=\frac{152}{3}.$$
 
2. 两阶段法
 
在原来问题引入人工变量后分两个阶段求解线性规划问题的方法。其中，第一阶段在原来问题中引入人工变量，设法构造一个单位矩阵的初始可行基。在此基础上，建立辅助线性规划问题。然后运用单纯形法求解，直到辅助目标函数为0为止。第二阶段重新回到原来的问题，以第一阶段得到的可行基为初始可行基，运用单纯形法求出原来问题的解。
 
2.1. 步骤
 
不考虑原问题是否存在基可行解，引进人工变量，构造辅助线性规划问题；
用单纯形法求解辅助问题，若辅助问题的目标函数值 $Z\ne 0$，则原问题无可行解，停止计算；
若辅助问题的目标函数值 $Z=0$，则将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换为原问题的目标函数系数，作为第二阶段的初始表；
使用单纯形法求解。
 
2.2. 题目
 
用两阶段法求解线性规划问题
 
$$\max Z=3x_1+2x_2-x_3$$
 
$$\text{s.t.}\{\begin{array}{l}-4x_1+3x_2+x_3\ge 4\\ x_1-x_2+2x_3\le 10\\ -2x_1+2x_2-x_3=-1\\ x_i\ge 0,i=1,2,3\end{array}$$
 
2.2.1. 转化为标准型
 
$$\max Z=3x_1+2x_2-x_3$$
 
$$\text{s.t.}\{\begin{array}{l}-4x_1+3x_2+x_3-x_4=4\\ x_1-x_2+2x_3+x_5=10\\ 2x_1-2x_2+x_3=1\\ x_i\ge 0,i=1,2,\dots ,5\end{array}$$
 
2.2.2. 添加人工变量
 
$$\max Z=3x_1+2x_2-x_3$$
 
$$\text{s.t.}\{\begin{array}{l}-4x_1+3x_2+x_3-x_4+x_6=4\\ x_1-x_2+2x_3+x_5=10\\ 2x_1-2x_2+x_3+x_7=1\\ x_i\ge 0,i=1,2,\dots ,7\end{array}$$
 
2.2.3. 两阶段
 
第一阶段
 
$$\min W=0x_1+0x_2+0x_3+0x_4+0x_5+x_6+x_7$$
 
$$⟺$$
 
$$\max -W=0x_1+0x_2+0x_3+0x_4+0x_5-x_6-x_7$$
 
$C$
$C$
$C$
0
0
0
0
0
-1
-1
$C_B$
基
$b$
$x_1$
$x_2$
$x_3\downarrow$
$x_4$
$x_5$
$x_6$
$x_7$
-1
$x_6$
4
-4
3
1
-1
0
1
0
0
$x_5$
10
1
-1
2
0
1
0
0
-1
$\leftarrow x_7$
1
2
-2
[1]
0
0
0
1
$\sigma$
$\sigma$
$\sigma$
-2
1
2
-1
0
0
0
入基变量 $x_3$，出基变量 $x_7$；
 
$C$
$C$
$C$
0
0
0
0
0
-1
-1
$C_B$
基
$b$
$x_1$
$x_2\downarrow$
$x_3$
$x_4$
$x_5$
$x_6$
$x_7$
-1
$\leftarrow x_6$
3
-6
[5]
0
-1
0
1
-1
0
$x_5$
8
-3
3
0
0
1
0
-2
0
$x_3$
1
2
-2
1
0
0
0
1
$\sigma$
$\sigma$
$\sigma$
-6
5
0
-1
0
0
-2
入基变量 $x_2$，出基变量 $x_6$；
 
$C$
$C$
$C$
0
0
0
0
0
-1
-1
$C_B$
基
$b$
$x_1$
$x_2$
$x_3$
$x_4$
$x_5$
$x_6$
$x_7$
0
$x_2$
$\frac{3}{5}$
$-\frac{6}{5}$
1
0
$-\frac{1}{5}$
0
$\frac{1}{5}$
$-\frac{1}{5}$
0
$x_5$
$\frac{31}{5}$
$\frac{3}{5}$
0
0
$\frac{3}{5}$
1
$-\frac{3}{5}$
$-\frac{7}{5}$
0
$x_3$
$\frac{11}{5}$
$-\frac{2}{5}$
0
1
$-\frac{2}{5}$
0
$\frac{2}{5}$
$\frac{3}{5}$
$\sigma$
$\sigma$
$\sigma$
0
0
0
0
0
-1
-1
所有的人工变量都是非基变量，第一阶段结束。
 
第二阶段
 
$C$
$C$
$C$
3
2
-1
0
0
$C_B$
基
$b$
$x_1\downarrow$
$x_2$
$x_3$
$x_4$
$x_5$
2
$x_2$
$\frac{3}{5}$
$-\frac{6}{5}$
1
0
$-\frac{1}{5}$
0
0
$\leftarrow x_5$
$\frac{31}{5}$
[$\frac{3}{5}$]
0
0
$\frac{3}{5}$
1
-1
$x_3$
$\frac{11}{5}$
$-\frac{2}{5}$
0
1
$-\frac{2}{5}$
0
$\sigma$
$\sigma$
$\sigma$
5
0
0
0
0
入基变量 $x_1$，出基变量 $x_5$；
 
$C$
$C$
$C$
3
2
-1
0
0
$C_B$
基
$b$
$x_1$
$x_2$
$x_3$
$x_4$
$x_5$
2
$x_2$
13
0
1
0
1
2
3
$x_1$
$\frac{31}{3}$
1
0
0
1
$\frac{5}{3}$
-1
$x_3$
$\frac{19}{3}$
0
0
1
0
$\frac{2}{3}$
$\sigma$
$\sigma$
$\sigma$
0
0
0
-5
$-\frac{25}{3}$
${\sigma }_j\le 0$， 对所有的 $j$ 都成立，因此求解结束。
 
最优解
 
$$x^{\ast }=(\frac{31}{3},13,\frac{19}{3},0,0{)}^T,$$
 
$$Z^{\ast }=3x_1+2x_2-x_3=3\ast \frac{31}{3}+2\ast 13-\frac{19}{3}=\frac{152}{3}.$$
 
3. 参考
 
正气清风：(完整版)单纯形法、大M法
Homyee King：初始解----两阶段的单纯形法