Simplex method (1)

Simplex method

Ideas ： From a basic feasible solution （ The initial basic feasible solution ） set out , Each search is more than the previous one “ good ” The basic feasible solution of , Instead of the previous one “ good ” The basic feasible solution of is not calculated

To solve the following problems ：

1. How to get an initial basic feasible solution
2. How to judge whether the current basic feasible solution has reached the optimal solution
3. If the current solution is not the optimal solution , How to find a better basic feasible solution

example
$$maxz=5x_1+2x_2$$
$$s.t.30x_1+20x_2\le 160$$
$$5x_1+x_2\le 15$$
$$x_1\le 4$$
$$x_1,x_2\ge 0$$

Standard form ：（ Join in 3 Relaxation variables ）
$$maxz=5x_1+2x_2+0x_3+0x_4+x_5$$
$$s.t.30x_1+20x_2+x_3=160$$
$$5x_1+x_2+x_4=15$$
$$x_1+x_5=4$$
$$x_1,x_2,x_3,x_4,x_5\ge 0$$
Get the corresponding coefficient matrix A
$$B=\left[\begin{array}{ccccc}30& 20& 1& 0& 0\\ 5& 1& 0& 1& 0\\ 1& 0& 0& 0& 1\end{array}\right]$$

step

① Select the initial base matrix B⁽⁰⁾ And base variables x_B( In the constraint matrix A_m×n Middle structure m Order unit matrix )

$$B^{(0)}=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]$$
$$x_B=\left[\begin{array}{c}{x}_3\\ x_4\\ x_5\end{array}\right]$$
So the initial basic feasible solution is
$$\left[\begin{array}{c}{x}_B\\ x_N\end{array}\right]=\left[\begin{array}{c}{B}^{-1}b\\ 0\end{array}\right]$$
After calculation, the initial basic feasible solution is （0,0,160,15,4）^T, The corresponding objective function value is max z=0

② Determine whether the current solution is the optimal solution

1. Express the base variable as a non base variable - Canonical form
   $$x_3=160-30x_1-20x_2$$
   $$x_4=15-5x_1-x_2$$
   $$x_4=4-x_1$$
2. Express the objective function with non base variables - Canonical form
   $$z=0+5x_1+2x_2$$

because x1 and x2 The coefficient of is positive , and x1 and x2 The value of is zero , So we can see that the current solution is not the optimal solution
In the classical expression of the objective function, all the coefficients before the non base variable are called Inspection number
For the maximization problem , When all the inspection numbers ≤0 when , The current solution is the optimal solution
For minimization problem , When all the inspection numbers ≥0 when , The current solution is the optimal solution

③ Improvement of solution
because x₁ The coefficient of 5 Than x₂ Big , seek max Each additional unit contributes more , So let x₁ The value of is changed from zero to positive （ From non base variables Select one of them to become a non base variable - Base variable ）
Select one of the original base variables to become the base variable - Off base variable

---

Select base variable
According to the objective function, it can make the result better （max) The greater the contribution of variables

---

Select the off base variable
In the expression of base variable with non base variable , When x₁ Increase from zero until x₃,x₄,x₅ Stop when the value of decreases to zero , At this point, the first base variable that becomes zero is the off base variable

---

So we exchange x₄ Its value becomes 0 A new basic feasible solution is obtained
$$x^{(1)}=(3,0,70,0,1{)}^T$$
The corresponding base matrix is $B^{(1)}=(p_3,p_1,p_5)$, The base variable is x₃,x₁,x₅ The non base variable is x₂,x₄, The corresponding objective function value is $z(x^{(1)})=15>z(x^{(0)})=0$
Return to the second step again to determine whether the current solution is the optimal solution , Repeat the process

Get in $z(x^{(2)})=20$ The objective function is found
$z=20-\frac{1}{14}{x}_3-\frac{4}{7}{x}_4$ The Central African base variable consists of 0 increase , Can only make z Value decline

Thus, it is judged that the current solution is the optimal solution
$$x^{(2)}=(2,5,0,0,2{)}^T$$
The corresponding value is
$$z^{\ast }=z(x^{(2)})=20$$

The above is a detailed explanation of the actual operation process of the simplex method