Linear Programs with Multiple Objectives - PDF

Please download to get full document.

View again

of 20
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report

How To, Education & Training


Views: 45 | Pages: 20

Extension: PDF | Download: 0

Related documents
p. 4 NJ: and ont, Linear Programs with Multiple Objectives 5.A A RATIONALE FOR MULTIOBJECTIVE DECISION MODELS For many engineering management problems, particularly those in the public sector, more than
p. 4 NJ: and ont, Linear Programs with Multiple Objectives 5.A A RATIONALE FOR MULTIOBJECTIVE DECISION MODELS For many engineering management problems, particularly those in the public sector, more than one objective is generally important. Consider the problem of developing an operating strategy for a large, multipurpose water reservoir. It is not uncommon for such a facility to be used to meet a variety of societal needs including municipal water supply, agricultural water supply, flood control and streamfiow management, hydroelectric power production, outdoor recreation, and protection of fragile envi ronmental habitat. From a management perspective, these uses of such a facility conflict with one another. For example, an optimal management strategy with re spect to ensuring a reliable supply of water from a reservoir for municipal use might have as its objective function: maximize storage in the reservoir at all times. Yet for purposes of containing an extreme flood event, the objective function could be just the opposite: minimize storage in the reservoir at all times. Several optimization tech niques have been developed to capture explicitly the tradeoffs that may exist be tween conflicting, and possibly noncommensurate, objectives. In this chapter we lay the foundation for multiobjective analysis that can be applied across the spectrum of public sector engineering management problems and demonstrate the applica tion of two of the most useful multiobjective optimization methodologies. Multiobjective programming deals with optimization problems with two or more objective functions. The multiobjective programming formulation differs from the classical (single-objective) optimization problem only in the expression of their Linear Programs with Multiple Objectives Chap. respective objective functions; the multiobjective formulation accommodates explicit ly more than one. Yet the evaluation of management solutions is significantly differ ent: instead of seeking an optimal or best overall solution, the goal of multiobjectiv analysis is to quantify the degree of conflict, or tradeoff among objectives. From an other perspective, we seek to find the set of solutions for which we can demonstrat that no better solutions exist. This best available set of solutions is referred to as th set of noninferior solutions. It is from this set that the person or persons responsibl for decision making should choose; the role of the systems analyst is to describe as ac curately and completely as possible the range for that choice and the tradeoffs amon objectives between members of that set of management solutions. Noninferiority i the metric by which we include or exclude solutions in this set. 5.A. A Definition of Noninferiority In single-objective problems our goal is to find the single feasible solution that pro vides the optimal value of the objective function. Even in cases where alternate op tima exist, the optimal value of the objective function is the same for each alternat optima (extreme point), as can be seen in Figure 3.3b. For problems (models) havin multiple objectives, the solution that optimizes any one objective will not, in gener-, al, optimize any other. In fact, for decision-making problems that are most challeng ing from an engineering management perspective, there is usually a very larg degree of conflict between objectives such as in the example of reservoir manage ment. Another example might be in the area of structural design, where objectives might include the maximization of strength concurrent with the desire to minimize weight or cost. In managing environmental resources, we might seek to trade off en vironmental quality and economic efficiency concerns, or even conflicting environ mental quality goals; minimizing the volume of landfill disposal against discharges to the atmosphere by incineration of municipal refuse. Note that in these latter ex amples, the units of measure for different objective functions may be quite different as well. We call such objective functions noncommensurate. When dealing with objectives that are in conflict, the concept of optimality may be inappropriate; a strategy that is optimal with respect to one objective may likely be clearly inferior for another. Consequently, a new concept is introduced by which we can measure solutions against multiple, conflicting, and even noncommen surate objectives the concept of noninferiority: A solution to a problem having multiple and conflicting objectives is noninferior if there exists no other feasible solution with better performance with respect to any one objective, without having worse performance in at least one other objective. Noninferiority is similar to the economic concept of dominance and is even called nondominance by some mathematical programmers, efficiency by statisti cians and economists, and Pareto optimality by welfare economists. A simple exten sion to the Homewood Masonry problem presented as Example 3- will help the reader understand this often nebulous concept. Sec. 5.A A Rationale for Multiobjective Decision Models 3 5.A. Example 5-: Environmental Concerns for Homewood Masonry Problem Statement. The management of Homewood Masonry has long been concerned about the local environmental impacts of their production operation. both as a responsible member of the community within which their plant resides, and in anticipation of increasingly tighter standards and governmental controls. You have been asked to study the operation of the plant and to identify from a technical per spective the level of conflict that exists between these two management obiectives. After analyzing the results of a comprehensive air-monitoring program, you discover that the major environmental impact of the operation results from a re lease of contaminated dust during the blending process; the binder used in manu facturing both HYDIT and FILIT attaches to these dust particles, and is thereby released to the environment during production. Laboratory tests suggest the release of this pollutant from the plant amounts to 500 milligrams for each ton of HYDT produced and 00 milligrams for each ton of FILIT produced. A second objective function, one that seeks to minimize total plant emissions, can now be specified as Minimize Z = 500x. + 00x The feasibility of solutions (the feasible region in decision space) is not affected by the consideration of this objective function. Note that the sense of this objective function is opposite that of our original production objective function (maximize to tal weekly revenue), and the units (milligrams discharged) are different as well (dollars). Yet both objective functions are related through the same set of decision variables. By the same argument presented in the previous chapter, the solution that op timizes this second objective function must be a basic feasible (extreme point) solu tion in the original problem. The values for the decision variables at each of these solutions are repeated in Table 5., and the values of both objective functions at each of those solutions are included. Not surprisingly, the solution that optimizes the environmental objective is the do nothing solution: x = 0. x = 0. TABLE 5. DECISION VARIABLES AND THEIR VALUES FOR ALL FEASIBLE EXTREME POINT SOLUTIONS FOR THE TWO-OBJECTIVE HOMEWOOD MASONRY PROBLEM: EXAMPLE 5- Alternative r Max Z A Mm B C D E F Z Noninferiority Noninferior 4000 Dominated by D. 400 Dominated by D Noninferior Noninferior 00 Noninferior E 4 Linear Programs with Multiple Objectives Chap. 5 Because both objective functions have been previously specified, and are thus assumed to reflect the overall goals of production and environmental concern (im plicitly, we assume that there are no other management objectives), we can apply the concept of noninferiority as defined above to each of these solutions (produc tion alternatives). Notice that the solutions that optimize the individual objective functions Z and Z alternative A and alternative D, respectively are indicated as being noninferior. In fact, for any multiobjective optimization model, the solution that optimizes any single objective function is always noninferior, unless there are alternate optima at that solution with respect to that objective function (this qualifi cation will be clarified later). By the definition of noninferiority, if a solution is opti mal for a given objective function, it is not possible to find a clearly better feasible solution regardless of how that solution might perform with respect to any (or all) other objective functions. Consider alternative B. It is not the worst solution with respect to profit; it is clearly better than alternative F by this measure. Nor is it the worst solution envi ronmentally; it is better than alternative C. But given the stated objective functions and awareness of this set of alternatives, would you ever select alternative B? Would anybody ever select alternative B? Stated another way, is there any alternative that would always be preferred to alternative B by anybody having preferences repre sented by this specific set of objective functions? The answer, of course, is that both alternatives D and E perform better with respect to both objectives than does alter native B, so that no decision maker would ever implement alternative B if he or she were aware of the availability of alternatives D or E. Similarly, alternative C is clearly dominated by alternative D. Now let s compare alternative D an alternative that has already been shown to be noninferior with alternative E. While alternative D represents a production strategy that maximizes profit for Homewood Masonry, it would also have a more adverse impact on the local environment than would E. Therefore, the choice be tween these alternatives is not obvious, and probably depends on the specific pref erences of the decision maker. It is easy to envision a scenario in which the board of directors of Homewood Masonry might themselves be divided over which strategy to implement, particularly if they reside in the vicinity of the plant, for instance. Can you see that the same logic applies to the determination that alternative F is also noninferior? The goal of such an analysis is thus to identiy all solutiqg that are ioninfrri or: the set of solutions for which there does not exist añothcr soluti9ri thalwould al ways be preferable to any of those solutions. This set of alternatives is referred to as the noninferior set, or sometimes the Pareto frontier. It is then the responsibility of the decision maker to select from among these solutions that which represents their best compromise solution among the stated objectives. The definition of noninferiority seems more difficult to state than to compre hend. Make sure you understand the logic used to determine dominance and non dominance with respect to the solutions presented in Table 5., then review carefully the definition of noninferiority given above. When you feel that you ve mastered the x Sec. 5.A A Rationale for Multiobjective Decision Models 5 TABLE 5. DECISION VARIABLES AND THEIR VALUES FOR ALL FEASIBLE EXTREME POINT SOLUTIONS FOR A MORE COMPLICATED THREE-OBJECTIVE PROBLEM: EXAMPLE 5- Alternative x Max Z Max Z Mm Z3 Noninferiority A 0 6 Noninferior B Noninferior C Noninferior D Noninferior E Noninferior F Dominated by E G Dominated by E H 0 Noninferior concept, examine the data for a three-objective, eight-solution multiobjective pro gram presented in Table 5. and try to verify that the noninferior set for this prob lem consists of points A, B, C, D, E, H. Note that objective Z has alternate optima both solution E and solution F provide an objective function value of 9 but for the three-objective problem, solution E dominates solution F You might also try writing your own objective function that depends on those values of the decision variables x and x, and see how the inclusion of this fourth objective function changes the noninferior set. You should start to realize that the determination of noninferiority gets increasingly complicated as the problem grows inslin both number of basic feasible extreme point solutions and number of ob jective functions. Most real engineering problems in the public sector have hundreds of thousands of feasible extreme points, and may have tens of objective functions. Before we discuss a general-purpose algorithm for identifying the noninferior set, it is useful to develop a graphical framework within which to study further the concept of noninferiority. 5.A.3 A Graphical Interpretation of Noninferiority Consider the two-objective mathematical program presented below: Maximize [Zi(xi, x7), Z(xi, 7)] where: Z = 3x Z = x Subject to: 4x + x x 6 6 4x S 4 6 Linear Programs with Multiple Objectives Chap x 5 x + 4x x 6x 8 + 3x 9 x, x 0. The feasible region in decision space and the objective functions are plotted in Figure 5., with each basic feasible solution labeled A H. The most astute of readers will have noticed that this two-objective problem us es the same feasible region specified in Table 5. as well as the first two objective func tions listed in that table (we will ignore the third minimization objective for the time being). The shaded cells in that table indicate the optimal solutions. The presence of alternate optima for Z is not surprising if we note that the coefficients that multiply the decision variables in that objective ( xi + x) result in an objective function having a slope that is identical to one of the binding constraints ( x + 4x 8). Because we have limited our example problem to not more than three objec tives, we can map the feasible region in decision space to a corresponding feasible region in objective space; we simply plot the ordered (Z, Z) pairs as presented in Figure 5.. Using the common reference provided by Table 5., each basic feasible solution labeled in Figure 5. has a corresponding solution in objective space using the same letter designator. For example, point B in Figure 5. corresponds to Point B in Figure 5., with the corresponding coordinates taken from Table 5.. Signifi cantly, adjacent feasible extreme points in decision space map to adjacent solutions in objective space. Whereas the shape of the feasible region in decision space de pends on the constraint set for a particular problem, the shape of the feasible region zi Figure 5. The feasible region in decision I space for the problem presented in Table 5. with solutions that optimize Z and Z shown passing through their respective optima points B and F, respectively. Xj Sec. 5.A A Ralionale for Multiobjective Decision Models 7 Northeast corner Noninferior set in objective space f y El e n e g I [5 n A No B Figure 5. The feasible region in objective space is defined by plotting all basic feasible solutions from decision space mapped through the objective functions Z and Z. Noninferiority is then easily determined using the northeast corner rule. in objective space depends on the objective functions, which serve as mapping functions for a particular set of objectives. This graphical representation provides a much easier means for identifying noninferior solutions. First, it should be obvious that all interior points must be infe rior, because given any such point, one would always be able to find another feasible solution that would improve both objectives simultaneously. For example, consider interior point P in Figure 5., which is inferior. Alternative D gives more Z than does P without decreasing the amount of 4. Similarly, D gives more Z without de creasing Z. In fact, any alternative in the shaded wedge shape to the northeast of point P dominates alternative P. We can generalize this notion in the form of a rule having this directional analog: A feasible solution to a two-objective optimization problem in which both jective functions are to be maximized is noninferior if there does not exist a feasible solution in the northeast corner of a quadrant centered at that point. Applying this northeast corner rule to the rest of the entire feasible region in Figure 5. leads to the conclusion that any point that is not on the northeastern bound ary of the feasible region is inferior. The noninferior solutions for the feasible region in Figure 5. are found in the thickened portion of the boundary between points B and E. Use the northeast corner rule to convince yourself that solution F is indeed dominated (by solution E) and is thus not a member of the noninferior set even though it was shown to be an alternate optimum when we solved Z as a single-objective optimization. We can, of course, generalize this result to evaluating solutions for problems with any combination of objective function sense. For example, in the current prob lem if, instead of both objectives being maximized, they were minimized. Can you see that the noninferior set would then consist of those solutions on the southwest border of the feasible region in objective space between points A and F? What if one objective is a maximization and one a minimization? What should you con clude if the tradeoff surface (noninferior set in objective space) reduces to a single point? ob 8 Linear Programs with Multiple Objectives Chap. 5 The noninferior set for the two-objective problem that we just solved consisted of the points labeled B, C, D, and E. Yet when considering a third objective Z3 in Table 5., points A and H are also included in the noninferior set. An important as sumption underlying multiobjective analyses is that the decision maker(s) must be able to articulate all relevant objectives for a particular problem. Otherwise, solu tions that are noninferior may be excluded from consideration in the same way that for our hypothetical example, we would not consider alternative H for implementa tion without a consideration of objective Z3. Now that we are comfortable with the concept of noninferiority, let s examine two methodologies that will allow us to identify efficient solutions when it is not possible to graph our solution space. We will demonstrate these techniques with the sample problem we just studied, but the reader should appreciate that the method ologies are applicable to any multiobjective model. 5.B METHODS FOR GENERATING THE NONINFERIOR SET A number of methodologies have been devised to portray the noninferior set among conflicting objectives. We will confine our treatment of this topic to a class of techniques that enjoys widespread use among engineers. Generating techniques, as they are commonly called, do not require (or allow) decision makers preferences to be incorporated into the solution process. The relative importance of one objective in comparison to another is not considered when identifying the noninferior set, but used later on to compare noninferior solutions and to quantify the tradeoffs be tween them. Typically, analyst(s) will work iteratively with the decision maker(s) to identify a complete set of objective functions for a particular problem domain and to specify the appropriate set of decision variables to relate these objectives to one another and to problem constraint conditions. The noninferior set is then generated by the appropriate technique, such as those presented below, and presented to the decision maker for further consideration. The selection of a solution to be implemented from among those solutions in the noninferior set is the responsibility of the decision maker(s). The strength of the use of generating methods for multiobjective optimization is that the roles of the an alyst(s) versus the decision maker(s) are as they should be: the analyst provides comprehensive information about the best available choices in a given problem do main, and the decision maker assumes the responsibility for selecting among those choices. The analyst is not involved with making value judgments about the relative importance of one objective
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks