Teacher Wang Shuyao's notes on operations research 09 linear programming and simplex method (Application of simplex table)

The first 9 speak Linear programming and simplex method （ Application of simplex table ）

Simplex table

give an example

See textbook P37 2.4

According to the inspection number ${\sigma }_i$ Select the variable of the base

about $>0$ Of ${\sigma }_i$, Compare their sizes , maximal ${\sigma }_i$ The corresponding variable is the variable to be entered into the base . Until after several rounds of iteration, all ${\sigma }_i$ all $\le 0$.（ This approach is also based on the standard requirements of the objective function $max$.）

Additional explanation

Inspection number ${\sigma }_i$ The meaning of is when introducing a unit variable $x_i$ when , How much can the objective function be changed . If it doesn't exist ${\sigma }_i>0$, It shows that the optimal solution has been obtained .

Can prove that , The test number of the base variable must be 0, Therefore, there is no need to calculate .

According to the comparison coefficient $\theta$ Select the base variable

according to $\theta =\frac{B^{-1}b}{B^{-1}a}$ Calculate the... Of each row that will be entered into the base $\theta$, And find the minimum , According to the position of the minimum value , Determine the vector to base .

Additional explanation

In the first iteration , The inspection number and value coefficient are exactly the same .（ Because the initial feasible basis is the identity matrix , And the identity matrix corresponds to $c_B$ yes 0.）

Some values don't need to be calculated completely , That is, the simplex table does not need to be completely filled , For example, because you only need to find ${\sigma }_i$ The maximum of , Therefore, it can be calculated to judge the size relationship . Therefore, a modified simplex method is proposed , It can reduce the computational load of the computer .

The optimal solution and the optimal objective function value can be seen in the final table .

summary

Simplex is a method to solve linear programming problems , Simplex table is a tool for simplex method , The steps of solving the equation of simplex can be more systematic , And you can see a lot of information from the table . You need to master how to count according to the inspection number ${\sigma }_i$ Select the variables of the basis and according to the comparison coefficient $\theta$ Select the base variable . Special attention should be paid to correct each step .