Teacher wangshuyao's notes on operations research 06 linear programming and simplex method (geometric significance)

The first 6 speak Linear programming and simplex method （ Geometric meaning ）

The geometric meaning of linear programming

Graphic method

Dimension of linear programming	Variable	Feasible domain dimension	Image dimension
1	$x_1$	1（ Line segment ）	1
2	$x_1、x_2$	2（ Plane ）	2
3	$x_1、x_2、x_3$	3（ Three-dimensional ）	3
n	$x_1、x_2、\dots 、x_n$	n（n Dimensional hypercube ）	n

Graphic method has great limitations , It is best to use , Three dimensional theory can , But it is difficult to operate , Basically not used . therefore , When the dimension is high, you need to use the simplex method .

Simplex method

The core idea of simplex method

1. Solve the intersection of all constraint equations , Including vertices of feasible region and vertices of infeasible region .（ As long as the constraints are limited , The number of intersections must be limited .）
2. Bring the coordinates of all intersections into the objective function , The largest of the corresponding function values is the maximum value , The smallest is the smallest .

limitations ： When there are too many intersections , Too much calculation .

Pilot method

Due to the heavy workload of enumeration , Therefore, the pilot method is adopted , That is, select a point first , Then study the surrounding points , If the function value corresponding to the starting point is maximum or minimum , Then it is the optimal solution .

Simplex

Linear geometry with the least number or sides below a certain dimension .

dimension	Simplex
0	spot
1	Line segment
2	triangle
3	tetrahedron

Solution situation

The results of solving linear programming problems are 3 Kind of ： Alternative optimal solution （ Multiple optimal solution ）、 Unbounded solution and no solution .

If the feasible region is closed, there must be an optimal solution , There may be a unique optimal solution or an infinite number of optimal solutions . If the feasible region is unbounded , You may get an unbounded solution at the unbounded place , There may also be a unique optimal solution or an infinite number of optimal solutions . If you can't draw a feasible region , There is no solution. .

Several theorems

Theorem 1（ The teaching material P24）： If the linear programming problem has a feasible region , Then its feasible region is a convex set .

Theorem 2（ The teaching material P25）： Basic feasible solution of linear programming problem $X$ Corresponding to feasible region $D$ The summit of .

Theorem 3（ The teaching material P26）： If the feasible region is bounded , The objective function of a linear programming problem must be optimal at the vertex of its feasible region .

summary

For linear programming problems , Because the graphic method will fail when dealing with three-dimensional and above situations , Therefore, we need to use the simplex method . At the same time, the workload of enumeration method is large , Therefore, the pilot method is adopted , That is, select a point first , Then study the surrounding points , If the function value corresponding to the starting point is maximum or minimum , Then it is the optimal solution .

If the feasible region is closed, there must be an optimal solution , There may be a unique optimal solution or an infinite number of optimal solutions . If the feasible region is unbounded , You may get an unbounded solution at the unbounded place , There may also be a unique optimal solution or an infinite number of optimal solutions . If you can't draw a feasible region , There is no solution. .

The feasible region is a convex set .