Simplex Algorithm(linear programming)

研究一组线性不等式或等式约束下使得某一线性目标函数取最大值（或最小值）的极值问题

Standard Form

    \(b\geq0\), \(m\leq n\), \(rank(A)=m\), but Why \(rank(A)=m\)?

    If not, the constraint \(AX=b\) would have only one solution.

Transform a general form into standard form

• Maxmium the objective function. \(min(z)=CX\rightarrow max(w)=-CX(w=-z)\)
• Transform inequality into equality(Same thing for greater inequality)

• Change unconstrait variable into two constraint variable.

• When \(b_j<0\) multiply (-1) in both side.

Now we have the standard form. How to solve for the optimal solution?

    Remember the \(y\) variables we added for constriant?

    These variables all have the same coefficient \(1\), so these coefficient form a identity matrix \(I\).

    So we can write something like this \([A\space I]\begin{bmatrix}X\\Y\end{bmatrix}=b\) We use what is called Simplex Tableau

Example

  \(x_3,x_4\)是基变量（basic variable也就是上面的y，辅助变量），\(x_1,x_2\)是非基变量，也就是要求的值。

Simple Tableau

    We introduce a operation called povit(d,e).

    We choose a non-basic variable \(x_e\) \(s.t.\space c_e>0(Max\space c_e)\)

    Then choose a basic variable \(x_d\) \(s.t.\space A_{(d,e)}>0\space and \space min(\frac{b_d}{A_{(d,e)}})\)

    Here we have the same \(c_e\)for both \(x_1\) and \(x_2\), we just go with \(x_1\)

    So here we see that for \(x_3\), \(b_3=12\), \(A_{(3,1)}=2\), for \(x_4\), \(b_4=9\), \(A_{(4,1)}=1\)

    Because, \(\frac{12}{2}<\frac{9}{1}\) we choose \(x_3\)

After Row Exchange

Repeat until we have all \(c\) variable into non-positive ones

Now \(x_3=5,x_4=2\) is the optimal solution.

作者：卢弘毅