最优化-lec2 Linear Programming 最优化理论与方法课件（英文版－南京大学）.pptVIP

Chapter 2 Linear Programming 2 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. 3 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. 4 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 performed automatically by a computer program. 5 Standard Form (1) If the original problem is a maximization problem (2) If any of the components of b are negative, then those constraints should be multiplied by -1. An upper bound on a variable can be treated as a general constraint, that is, as one of the constraints included in the coefficient matrix A. (4) A variable without specified lower or upper bounds, called a “free” or “unrestricted” variable, can be replaced by a pair of nonnegative variables. 6 Standard Form The remaining two transformations are used to convert general constraints into equations. 7 Standard Form One of the reasons that the general constraints in the problem are converted to equalities is that it allows us to use the techniques of elimination to manipulate and simplify the constraints. For example, the syste