This work addresses the problem of minimizing or maximizing a linear function in the presence of linear equality or inequality constraints. It provides methods for modeling complex problems via effective algorithms on modern computers. The general theory and characteristics of optimization problems are presented, along with effective solution algorithms. The text also explores linear programming and network flows, employing polynomial-time algorithms and various specializations of the simplex method. Includes many numerical examples to illustrate theory and techniques.

3, xx > -3}. Find all extreme points of X and represent x = (0, 1) as a convex combination of the extreme points. [2.49] Answer the following questions and provide a brief explanation or illustration: a. Is it possible for X in Equation (2.1) to be empty but D in Equation (2.2) to be nonempty? b. Is there a relationship between redundancy and degeneracy of a polyhedral set? c. Does degeneracy imply redundancy in two dimensions? d. If the intersection of a finite number of half-spaces is nonempty,

but zk - ck = 0 for at least one nonbasic variable xk. As xk is increased, we get (in the absence of degeneracy) points that are distinct from x* but have the same objective value (why?). If xk is increased until it is blocked by a basic variable (if it is blocked at all), we get an alternative optimal basic feasible solution. The process of increasing xk from level zero until it is blocked (if at all) generates an infinite number of alternative optimal solutions. Example 3.6 Minimize -3xj + x2

-3. Note that zx - q > 0 and yj = B aj = -1 -1 . Therefore, the optimal objec- tive value is unbounded. In this case, if xj is increased and x4 is kept zero, we get the following solution: x R =B"'b B 'aj xx 120 Chapter 3 i.e.. *3 = _ x 2. "10" "-Γ "10 + X!3 - -1 x,= 3 + x t with X] > 0, and x4 = 0. Note that this solution is feasible for all x^ > 0. In particular, X] - 2 x 2 + X3 =x\— 2(3 + X]) + (10 + Xj) = 4, and -χγ + x2 + X4 = -xi +(3 + xi) + 0 = 3. Furthermore, z = - 9 - 4x 1 ;

finite convergence. First, by examining row 0 before and after pivoting, note that ( C J B - V B B - 1 ) - ((-B-Vi-B-1) = Zk yrk Note that {br, yr\,—,yrm) z c k " k > ~Ck(br,yrUyr2,...,yrm). is the rth row of (b, B~ ) and is therefore >- 0. Since 0 and yrk > 0, it is therefore evident that (cgB-'b.CgB- 1 ) - ( c ^ b ^ B - 1 ) >- 0. We are now ready to show that the lexicographic rule of Section 4.6 will indeed prevent cycling. We do this by showing that the bases developed by the

may seek efficient or Pareto-optimal solutions, that is, solutions that are such that a further improvement in any objective function value is necessarily accompanied by a detriment in some other objective function value. The fourth stage is model testing, analysis, and (possibly) restructuring. One examines the model solution and its sensitivity to relevant system parameters, and studies its predictions to various what-if types of scenarios. This analysis provides insights into the system. One