OTHER ALGORITHMS FOR LINEAR PROGRAMMING:PARAMETRIC LINEAR PROGRAMMING

By -

PARAMETRIC LINEAR PROGRAMMING

At the end of Sec. 7.2 we mentioned that parametric linear programming provides an- other useful way for conducting sensitivity analysis systematically by gradually changing various model parameters simultaneously rather than changing them one at a time. We shall now present the algorithmic procedure, first for the case where the cj parameters are being changed and then where the bi parameters are varied.

Systematic Changes in the cj Parameters

For the case where the cj parameters are being changed, the objective function of the ordinary linear programming model

Introduction to Operations Research-0080where the aj are given input constants representing the relative rates at which the coefficients are to be changed. Therefore, gradually increasing 8 from zero changes the coefficients at these relative rates.

The values assigned to the aj may represent interesting simultaneous changes of the cj for systematic sensitivity analysis of the effect of increasing the magnitude of these changes. They may also be based on how the coefficients (e.g., unit profits) would change together with respect to some factor measured by 8. This factor might be uncontrollable, e.g., the state of the economy. However, it may also be under the control of the decision maker, e.g., the amount of personnel and equipment to shift from some of the activities to others.

For any given value of 8, the optimal solution of the corresponding linear program- ming problem can be obtained by the simplex method. This solution may have been ob- tained already for the original problem where 8 = 0. However, the objective is to find the optimal solution of the modified linear programming problem [maximize Z(8) subject to the original constraints] as a function of 8. Therefore, in the solution procedure you need to be able to determine when and how the optimal solution changes (if it does) as 8 in- creases from zero to any specified positive number.

Figure 8.1 illustrates how Z*(8), the objective function value for the optimal solution (given 8), changes as 8 increases. In fact, Z*(8) always has this piecewise linear and convex3 form (see Prob. 8.2-7). The corresponding optimal solution changes (as 8 increases) just at the

3See Appendix 2 for a definition and discussion of convex functions.

Introduction to Operations Research-0081

values of 8 where the slope of the Z*(8) function changes. Thus, Fig. 8.1 depicts a problem where three different solutions are optimal for different values of 8, the first for 0 ::: 8 ::: 81, the second for 81 ::: 8 ::: 82, and the third for 8 2: 82. Because the value of each xj remains the same within each of these intervals for 8, the value of Z*(8) varies with 8 only because the coefficients of the xj are changing as a linear function of 8. The solution procedure is based directly upon the sensitivity analysis procedure for investigating changes in the cj parameters (Cases 2a and 3, Sec. 7.2). The only basic difference with parametric linear programming is that the changes now are expressed in terms of 8 rather than as specific numbers.

Introduction to Operations Research-0082

Introduction to Operations Research-0083

Therefore, after 8 is increased past 8 = , x4 would need to be the entering basic variable for another iteration of the simplex method, which takes us from the first tableau in Table

8.2 to the second tableau. Then 8 would be increased further until another coefficient goes negative, which occurs for the coefficient of x5 in the second tableau when 8 is increased past 8 = 5. Another iteration of the simplex method then takes us to the final tableau of Table 8.2. Increasing 8 further past 5 never leads to a negative coefficient in Eq. (0), so the procedure is completed.

Summary of the Parametric Linear Programming Procedure for Systematic Changes in the cj Parameters

1. Solve the problem with 8 = 0 by the simplex method.

2. Use the sensitivity analysis procedure (Cases 2a and 3, Sec. 7.2) to introduce the

!Jcj = aj8 changes into Eq. (0).

3. Increase 8 until one of the nonbasic variables has its coefficient in Eq. (0) go negative

(or until 8 has been increased as far as desired).

4. Use this variable as the entering basic variable for an iteration of the simplex method to find the new optimal solution. Return to step 3.

Note in Table 8.2 how the first two steps of this procedure lead to the first tableau and then steps 3 and 4 lead to the second tableau. Repeating steps 3 and 4 next leads to the final tableau.

Systematic Changes in the bi Parameters

For the case where the bi parameters change systematically, the one modification made in the original linear programming model is that bi is replaced by bi + ai8, for i = 1, 2, . . . , m, where the ai are given input constants. Thus, the problem becomes

Introduction to Operations Research-0084

The goal is to identify the optimal solution as a function of 8.

With this formulation, the corresponding objective function value Z*(8) always has the piecewise linear and concave4 form shown in Fig. 8.2. (See Prob. 8.2-8.) The set of basic variables in the optimal solution still changes (as 8 increases) only where the slope of Z*(8) changes. However, in contrast to the preceding case, the values of these variables now change as a (linear) function of 8 between the slope changes. The reason is that increasing 8 changes the right-hand sides in the initial set of equations, which then causes changes in the right-hand sides in the final set of equations, i.e., in the values of the final set of basic variables. Figure 8.2 depicts a problem with three sets of basic variables that are optimal for different values of 8, the first for 0 ::: 8 ::: 81, the second for 81 ::: 8 ::: 82, and the third for 8 2: 82. Within each of these intervals of 8, the value of Z*(8) varies with 8 despite the fixed coefficients cj because the xj values are changing.

The following solution procedure summary is very similar to that just presented for systematic changes in the cj parameters. The reason is that changing the bi values is equiv- alent to changing the coefficients in the objective function of the dual model. Therefore, the procedure for the primal problem is exactly complementary to applying simultane- ously the procedure for systematic changes in the cj parameters to the dual problem. Consequently, the dual simplex method (see Sec. 8.1) now would be used to obtain each new optimal solution, and the applicable sensitivity analysis case (see Sec. 7.2) now is Case 1, but these differences are the only major differences.

Summary of the Parametric Linear Programming Procedure for Systematic Changes in the bi Parameters

1. Solve the problem with 8 = 0 by the simplex method.

2. Use the sensitivity analysis procedure (Case 1, Sec. 7.2) to introduce the £1bi = ai8 changes to the right side column.

Introduction to Operations Research-0085

3. Increase 8 until one of the basic variables has its value in the right side column go negative (or until 8 has been increased as far as desired).

4. Use this variable as the leaving basic variable for an iteration of the dual simplex method to find the new optimal solution. Return to step 3.

Introduction to Operations Research-0086

The Solved Examples section of the book’s website includes another example of the procedure for systematic changes in the bi parameters.

Comments

Post a Comment

Popular posts from this blog

DUALITY THEORY:THE ESSENCE OF DUALITY THEORY

By -
Image
THE ESSENCE OF DUALITY THEORY Given our standard form for the primal problem at the left (perhaps after conversion from another form), its dual problem has the form shown to the right. Thus, with the primal problem in maximizatio n form, the dual problem is in minimization form instead. Furthermore, the dual problem uses exactly the same pa r amete r s as the primal problem, but in different locations, as summarized below. 1. The coefficients in the objective function of the primal problem are the right-hand sides of the functional constraints in the dual problem. 2. The right-hand sides of the functional constraints in the primal problem are the coef- ficients in the objective function of the dual problem. 3. The coefficients of a variable in the functional constraints of the primal problem are the coefficients in a functional constraint of the dual problem. To highlight the comparison, now look at these same two problems in matrix notation (as introduced at the beginn...
Read more

NETWORK OPTIMIZATION MODELS:THE MINIMUM SPANNING TREE PROBLEM

By -
Image
THE MINIMUM SPANNING TREE PROBLEM The minimum spanning tree problem bears some similarities to the main version of the shortest-path problem presented in the preceding section. In both cases, an undi r ecte d and connected network is being considered, where the given information includes some mea- sure of the positive length (distance, cost, time, etc.) associated with each link. Both problems also involve choosing a set of links that have the shortest total length among all sets of links that satisfy a certain property. For the shortest-path problem, this property is that the chosen links must provide a path between the origin and the destination. For the minimum spanning tree problem, the required property is that the chosen links must provide a path between ea c h pair of nodes. The minimum spanning tree problem can be summarized as follows: 1. You are given the nodes of a network but not the links. Instead, you are given the po- tential links and the positive length for each ...
Read more

INTEGER PROGRAMMING:THE BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS

By -
TH E BRANCH-AND-CUT APPROACH TO SOLVING BIP PROBLEMS Integer programming has been an especially exciting area of OR since the mid-1980s be- cause of the dramatic progress being made in its solution methodology. Background To place this progress into perspective, consider the historical background. One big break- through had come in the 1960s and early 1970s with the development and refinement of the branch-and-bound approach. But then the state of the art seemed to hit a plateau. Rel- atively small problems (well under 100 variables) could be solved very efficiently, but even a modest increase in problem size might cause an explosion in computation time be- yond feasible limits. Little progress was being made in overcoming this exponential growth in computation time as the problem size was increased. Many important problems arising in practice could not be solved. Then came the next breakthrough in the mid-1980s, with the introduction of the b r an c h- and-cu t approach to sol...
Read more