Teacher wangshuyao's notes on operations research course 08 linear programming and simplex method (simplex method)

The first 8 speak Linear programming and simplex method （ Simplex method ）

Simplex method

give an example

See textbook P28 example 2-6.

How to find a base

Observation

Direct observation , And then verify . If the base is not found, replace the sub matrix and re verify .

Generally speaking, the number of possible bases is $C_n^m$, among $n$ Is the number of unknown variables ,$m$ It's a matrix $A$ The rank of .

Simplification first approach （ recommend ）

Because the principle of base selection is that the simpler the better , Preferably, the identity matrix $E$, Easy to calculate .

Therefore, the coefficient matrix and the free term can be transformed first , It is better to transform the diagonal elements into 1 The submatrix of , Or a submatrix with positive elements on the diagonal , Or at least 0 More submatrixes . One reason is that the simpler the submatrix is , The less computation after that , Second, if the elements on the diagonal of the submatrix are positive , Then the basic solution must be the basic feasible solution . And if the initial constraints are $\le$, And the free term is positive , Then a coefficient of 1 Of relaxation variables , It must be found in the coefficient matrix that the elements on the diagonal are 1 The submatrix of .

If there is no or it is not easy to find a base with positive elements on the diagonal , Then you can introduce artificial variables , namely “ Big M Law .

How to determine $X^{(i)}$ Is it the best solution

The basic idea ： By shifting the term of the equation , Use non base variables to represent base variables , Then substitute it into the objective function , Observe the value coefficient of the changed objective function , Analyze whether the current solution is optimal .

A more concise approach ： Inspection number $(\sigma )$ Discrimination .

summary

When solving the equation through the basis , Although the inverse matrix of the base can be used for solving operations , But this method of operation is not convenient for the subsequent discussion of the optimal solution , Therefore, it is still transformed into the form of original equations for analysis and solution . By simplifying and moving items , Let the non base variable be 0 To solve the . Use non base variables to represent base variables , Then substitute it into the objective function , Observe the value coefficient of the changed objective function , Analyze whether the current solution is optimal , And determine whether the base vector needs to be replaced . Then iterate the above process to find the optimal solution .

In the process , It is best to choose the identity matrix as the base , Because the basic solution thus solved must be the basic feasible solution. How to judge $X^{(i)}$ Whether it is the optimal solution has a more concise method , Inspection number $(\sigma )$ Discrimination .