最优化-lec2-lp.pptVIP

* Revised Tableau(修表) The revised form of the simplex method generates at each iteration only the information that is specifically required for that iteration. In the full-tableau form of the simplex method, many of the computations performed in a given iteration are not used in that iteration. require less storage and less computation possible to utilize the sparsity of the matrix A to reduce the number of computations * Revised Tableau Procedure of the revised tableau * Revised Tableau * Special Situations No feasible solution x2 x1 0 What happens when we apply the simplex method to the problem? * Special Situations Multiple optimal solutions x1 x2 0 What happens when we apply the simplex method to the problem? * Special Situations No finite optimal solution x1 x2 0 What happens when we apply the simplex method to the problem? Chapter 2 Linear Programming * Geometry of Linear Programming Linear programming can be studied both algebraically and geometrically(代数与几何) The algebraic point of view is based on writing the linear program in a particular way, called “standard form” The geometric point of view is based on the geometry of the feasible region, and uses ideas such as convexity to analyze There is a direct correspondence between these two points of view First, we review how a two-dimensional linear programming can be solved graphically. * Geometry of Linear Programming The feasible region is graphed as below. It is no coincidence that the solution occurred at a corner or extreme point. * Standard Form(标准形式) In matrix-vector(矩阵向量) notation, a linear program in standard form will be written as The important things to notice are:- it is a minimization problem all the variables are constrained to be nonnegative all the other constraints are represented as equations the components of the right-hand side vector b are all nonnegative ☆ All linear programs can be converted to standard form. The rules for doing this are simple and can be perform