Practical Goal Programming is intended to allow academics and practitioners to be Included format: EPUB, PDF; ebooks can be used on all reading devices. Goal programming is an excellent tool that can provide solutions to Practical Goal Programming is intended to allow academics and practitioners to be able. Ordering or Ranking. 7. Balancing. 8. 2 Goal Programming Variants. Generic Goal Programme. Distance Metric Based Variants.
|Language:||English, Spanish, Japanese|
|PDF File Size:||10.20 MB|
|Distribution:||Free* [*Regsitration Required]|
DOWNLOAD PDF .. D. Jones, M. Tamiz, Practical Goal Programming, International Series in Operations Research & Management Science , DOI. View Practical Goal meteolille.info from MECHANIC E at Vietnam National University, Ho Chi Minh City. 1 INTERNATIONAL SERIES IN. To illustrate goal programming (GP) we consider the Two Mines problem. . it is standard notational practice in GP to use a plus superscript to indicate upward.
Chapter 7 details the current state of the art in terms of the integration of goal programming with other techniques, and the text concludes with two case studies which were chosen to demonstrate the application of goal programming in practice and to illustrate the principles developed in Chapters 1 to 7. Chapter 8 details an application in healthcare, and Chapter 9 describes applications in portfolio selection.
The decision maker s sets a numeric target level for each goal which is denoted bq. This then leads to the basic formulation of the qth goal: It represents the level by which the target level is under-achieved. It represents the level by which the target level is over-achieved. The two deviational variables are constrained to take non-negative values and both cannot take a non-zero value simultaneously.
These are penalised in an achievement function. There are three basic types of penalisation, as discussed in Section 1. The relation to the deviational variables is given in Table 2.
Table 2. A typical type 2 goal would involve profit, where any negative deviation below the goal level would be penalised. A typical type 3 goal would involve a workforce-level target, where any negative or positive deviation from the target level would be penalised. We note that the set of goals are sometimes termed soft constraints. That is, the decision maker desires to meet each goal but if the goal is not achieved then this does not imply that the solution is infeasible.
Goal programming also allows for an addition of a set of linear programming style hard constraints whose violation will make the solution infeasible. The exact nature of the achievement is dependent on the goal programming variant used, so in our generic form it is simply represented by a generic function of the deviational variables: That is the distance from the target to the achieved level of the goals.
The above considerations lead to the generic algebraic form of the goal programme: Lee, used the lexicographic goal programming variant. The distinguishing feature of lexicographic goal programming is the existence of a number of priority levels.
Each priority level contains a number of unwanted deviations to be minimised. A practical example of how to formulate a lexicographic goal programme is given in Sections 3.
Each priority level is now a function of a subset of unwanted deviational variables which we define as hl n p. This leads to the following formulation: The preferential weights are used to model the relative importance of the minimisation of the associated deviational variable to the decision maker. The setting and control of the preferential weights is discussed in Section 3. Note that if a deviational variable is not included in a particular priority level then its preferential weight for that priority level is set equal to zero.
Deviational variables whose minimisation is considered unimportant to the decision maker s e. These constants are necessary in order to scale all the goals onto the same units of measurement. A discussion of types of normalisation used in goal programming is given in Section 3.
The meaning of the lexicographic minimisation of the achievement function is that the minimisation of deviational variables placed in a higher priority level is regarded as infinitely more important than that of deviational variables placed in a lower priority level.
This has the effect of producing a series of sequential optimisations, each of which has a reduced feasible region as the minimal values of the higher priority level optimisations must be maintained. A practical numerical example of this process is given in Section 3. This also has the effect of combining the ordering philosophy discussed in Section 1. The lexicographic structure has been criticised by some authors on the grounds of its incompatibility with utility function theory Min and Storbeck, This could be due to political sensitivities or ethical considerations, such as tradeoffs between safety goals measured in lives lost and monetary goals such as cost or profit.
Furthermore, Tamiz et al. Therefore, whilst it is true that lexicographic goal programming will not be appropriate for every multi-objective situation, it can be seen that there is a class of situations in which it proves to be an effective and appropriate decision aiding tool.
This is because each hard constraint can be converted into a goal and the first priority level can be reserved for the minimisation of the deviational variables from the hard constraints. This is a mathematically correct transformation; however, it is not the convention adopted in this book as we wish to emphasise and maintain the difference between hard constraints whose non-satisfaction will render the solution infeasible and goals whose non-satisfaction is undesirable but will not render the solution infeasible.
Weighted goal programming is sometimes termed nonpre-emptive goal programming in the literature. If we assume linearity of the achievement function then we can represent the linear weighted goal programme by the following formulation: As reported in Tamiz et al. A similar survey for the period — is not yet available but a clear trend from using lexicographic towards using weighted goal programming can be seen.
Increases in computing power and hence decreased solution times may have contributed to this effect as multiple weighting schemes and trade-offs can now be more easily compared even for larger scale goal programmes. That is, the maximal deviation from any goal, as opposed to the sum of all deviations, is minimised. For this reason Chebyshev goal programming is sometimes termed Minmax goal programming. As discussed in Section 1. That is, the decision maker is trying to achieve a good balance between the achievement of the set of goals as opposed to the lexicographic approach which deliberately prioritises some goals over others or the weighted approach which chooses the set of decision variable values which together make the achievement function lowest, sometimes at the expense of a very poor value in one or two of the goals.
Chebyshev goal programming is also the only major variant that can find optimal solutions for linear models that are not located at extreme points in decision space such as point D in Fig. All of the above points lead to the conclusion that Chebyshev goal programming has the potential to give the most appropriate solution where a balance between the levels of satisfaction of the goals is needed.
This should include a large number of application areas, especially those with multiple decision makers each of whom has a preference to their own subset of goals that they regard as most important. However, surveys of the literature e. Jones and Tamiz, find little practical use of the Chebyshev goal programming variant.
It is hoped that greater awareness and the development of methodologies such as extended goal programming outlined in Section 4. In the previous section the factor that varied was the underlying distance metric. Therefore, it is possible to formulate a goal programme that has a variant from both Sections 2.
For example, 2. This imprecision normally relates to the goal target values bq but could also relate to other aspects of the goal programme such as the priority structure. The early fuzzy goal programming models used both Chebyshev Narasimhan, ; Hannan, and weighted Hannan, ; Tiwari et al. There are various possibilities for measuring the fuzziness around the target goals, each of which leads to a different fuzzy membership function.
These functions model the drop in dissatisfaction from a state of total satisfaction where the membership function takes the value 1 to a state of total dissatisfaction where the membership function takes the value 0.
There are many possible fuzzy membership functions, the algebraic structure of four of the most common linear fuzzy membership functions are outlined below: Right-sided positive deviations penalised linear function — shown graphically by Fig. Left-sided negative deviations penalised linear function — shown graphically by Fig.
Triangular both deviations penalised linear function — shown graphically by Fig. Trapezoidal both deviations penalised with an interval of complete satisfaction linear function — shown graphically by Fig. If we assume a weighted goal programme variant then the most recent and comprehensive modelling framework is given by Yaghoobi et al.
Assuming that the Q goals are divided into q1 right-sided membership functions, q2 leftsided membership functions, q3 triangular membership functions, and q4 trapezoidal membership functions gives the following algebraic formulation: This formulation allows the solution of a weighted fuzzy goal programme via a single, linear model that can be solved via any standard linear programming software.
This means that techniques from the field of integer programming rather than linear programming must be adapted when designing solution and Pareto efficiency detection and restoration tools detailed in Chapter 6.
As integer programmes are a lot harder to solve than similarly sized linear programmes, this will result in longer solution times and more restrictions on the number of decision variables and constraints in the goal programme.
A practical example of the issues raised in solving large-scale integer goal programmes is given in Chapter 8 in the context of a healthcare planning model. A discussion of the technical aspects of modelling and solving integer programmes is beyond the scope of this book but the reader is referred to the following seminal books on the topic: Williams ; Wolsey As previously noted, an integer goal programming can be of either the lexicographic, weighted, or Chebyshev distance metric variants.
If we assume the weighted variant and restrict all decision variables to take only positive integer variables then we have the following algebraic structure: This subset of integer goal programmes has special characteristics that may aid the solution process. Typical application areas include multi-objective shortest path, assignment, 22 2 Goal Programming Variants logistics, network flow, spanning tree, travelling salesperson, knapsack, scheduling, location, and set covering problems Ehrgott and Gandibleux, This type of goal programme is mentioned by Romero as arising in the fields of financial planning, production planning, and engineering.
This variant also occurs in some goal programming based methods for deriving weighting vectors from pairwise comparison matrices Despotis, Romero also warns on the perils of simple linearisation to the following form: The advent of more powerful non-linear programming technology and computing power; heuristics such as multi-objective evolutionary methods Deb, ; and advances in exact methods for solving fractional goal programmes Audet et al.
In many cases the model can now be solved without linearisation. Fractional goal programmes also require their own adapted form of Pareto efficiency detection and restoration procedure Caballero and Hernandez, , as will be discussed in Chapter 6. Chapter 3 Formulating Goal Programmes This chapter concerns methods and concepts that need to be considered in order to formulate effective goal programming models.
This chapter will address the modelling issues sequentially and show how to employ good goal programming practice and avoid common pitfalls. For a good description of the holistic process of operational research modelling the reader is referred to the first chapter of the Winston textbook.
Advice on liaising with decision maker s in order to extract criteria of relevance is given in Belton and Stewart For the remainder of this chapter, it is assumed for the purposes of explanation that all technical coefficient data is deterministic and known with certainty. When a set of criteria has been determined it is necessary to distinguish between goals and hard constraints. Hard constraints are in variable space and, as described in Chapter 2, are conditions that must be satisfied in order for the solution to be implementable.
Any condition that does not fulfil this requirement should be included as a goal and not a hard constraint. The modeller is cautioned against using more hard constraints than is necessary as this could cause infeasibility and also exclude solutions that may be of practical interest to the decision maker.
Once the set of goals has been determined then it is necessary to both form the algebraic structure of the goal and set its target level. Suppose our first criterion relates to the amount of hours labour per week used to manufacture the two products A and B. Assume our decision variables are x1: The number of products of type A manufactured per week x1: The number of products of type B manufactured per week and each type A product takes 4 h to manufacture and each type B product takes 3 h to manufacture.
Suppose that the desired level is to use no more than h labour. This is an example of a type 1 goal. It can be seen that at most one deviational variable should take a positive value if this solution is to make sense, with both deviational variables taking the value zero if the goal target value of h is achieved exactly. Fortunately, this non-linear condition need not be modelled explicitly in the standard goal programming model due to the nature of the achievement function not making it profitable to allow both deviational variables to take positive values.
Also, both deviational variables are constrained to take non-negative values: This is good practice, even if it is suspected that solutions below the h limit will never occur, as if these are by chance possible and the variable n1 has been omitted, then this will act as a hard constraint, forcing the solution to remain above h and hence excluding some potentially good solutions, and even in some cases the true optimal solution.
Therefore, deviational variables should not be omitted from the formulation. The one exception to this rule is where the ideal best value of the objective has been used as a target level, as detailed in the discussion in the following paragraph.
The first is that: At one extreme, the target level will be determined beforehand with certainty due to some technical requirement, natural occurrence, or policy of the problem-owning organisation.
A goal for the level of financial surplus desired at the same university could be a lot more difficult to set. It is important to note that the initial target level chosen in such a case should be regarded as an initial estimate and not a definitive set-in-stone value. Sensitivity analysis techniques, an interactive methodology, or a preference structure should be employed in order to explore the effects of different levels of the target level.
These techniques will be outlined in Chapter 4. There are also modelling and solution reasons why the target levels have to be set at appropriate levels, especially for type 1 or type 2 goals. If they are set too pessimistically then the resulting solution may be Pareto inefficient Romero, , and a Pareto efficiency restoration technique Tamiz and Jones, will need to be employed in order to restore Pareto efficiency to the solution.
Such techniques are detailed in Chapter 6. If on the other hand they are set too optimistically, especially when using the lexicographic variant, then the problem of lexicographic redundancy will occur Romero, , meaning that only a few and in many cases in the literature, only one of the goals will be taken into consideration.
This will not give a true multi-objective analysis of the situation. Lexicographic redundancy is dealt with in Section 3. One means of avoiding decision maker setting target levels as seen in the literature is to set the target level at its maximum possible value within the feasible set, known as the ideal value. This value can be relatively easily found by the following single-objective optimisation assuming without loss of generality a first goal of type 2: This is the ultimate in optimistic target-level setting and for reasons outlined above therefore should not be used with the lexicographic variant.
With the Chebyshev variant ideal values could also cause scaling problems as this variant is very sensitive to the distance from target to ideals for certain goals and therefore stretching that distance by setting the target level to the ideal value could lead to an unintended bias.
Ideal target levels have the potential to work for the weighted variant but it has been noted Romero et al. In this case it has been shown Romero et al. If this is the desired philosophy, it is suggested that the modeller move from using goal programming to a full use of compromise programming which allows for a complete analysis of such models.
In short, setting target levels to the ideal is neither in accordance with the philosophy of goal programming nor a panacea for the problem of setting target levels. It can also cause real problems for some variants. In our opinion, a better solution would be increased interaction with the decision maker, sensitivity analysis, interactive methods, or preference modelling inclusion in order to set realistic target levels.
These relate to the levels of desired profit and strategic production plans. This leads to the following algebraic formulation of the second goal: Additionally, the company has some strategic aims for their weekly production. They wish to maintain production of at least 40 units of each of the products. This leads to the following two type 2 goals: The first relates to a minimum agreement for a type of material used in the manufacture of the products.
The company has to purchase a minimum of 50 l of this product weekly. Each item of type A uses 2 l of the product and each item of type B uses 1 l of the product. Disposing of unused product is prohibitively expensive.
The second constraint relates to machine time, which caps the maximum combined production of both products to 75 per week. These considerations lead to the following two constraints: There is no feasible solution that simultaneously satisfies all the goals at their target values. Some of the conflicts can be seen immediately. For example if the company has a strategic aim to produce 40 of each of the two products but only machine time for 75 products then the strategic aim will never be met.
Other conflicts are less obvious. For example Fig. A level of conflict between goals is to be expected in any modern organisation due to the laudable aim to achieve good levels on all criteria. As detailed in Chapter 2, the nature of the achievement function will be dependent on the variant or variants chosen. The following section will demonstrate how the above example can be formulated as a lexicographic, weighted, and Chebyshev goal programme and discuss good modelling practice within these variants.
An example of such an order could be Priority 1: Achieve the profit goal. Priority 2: Achieve the strategic production goals.
Priority 3: Achieve the labour goal. The algebraic formulation is given as a vector to be lexicographically minimised: The significance of this vector is that the satisfaction of goals placed in a higher priority level is strictly preferred to that of goals placed in lower priority levels. Thus the first step is to minimise the first priority level: This set will form the feasible region for the optimisation of the second priority level.
The second priority level is now optimised. The minimisation is that of the second priority level: The feasible alternative optimal solutions to this optimisation are shown by Fig. These form the feasible region for the minimisation of the third priority level. This is the optimal solution to the lexicographic solution. In terms of satisfaction of the target levels, the data given in Table 3. The effects of using the priority structure together with the L1 distance metric which is not concerned with balance between goals can be observed.
The goals placed in the top two priority levels have done relatively well but the labour goal, placed in the third priority level, is a long way from being achieved. If these indeed reflect the priorities of the company then this solution is appropriate and they will employ extra labour to make up for the shortfall. If they are not satisfied with this solution then it will probably be due to the labour goal and either a different variant or sensitivity analysis with the priority structure and goal target values should be employed to investigate other solutions.
Also, recall that the company was uncertain about the level of the profit goal. In fact the optimal solution for this variant turns out not to be sensitive to this target level. If the priority structure is altered then a completely different solution will probably be obtained. The goal satisfaction levels are as in Table 3. This is, however, at the expense of considerable non-achievement of the profit and strategic production goals.
One reason for this decline could be the perceived lack of flexibility and suggested incompatibility with utility functions Min and Storbeck, This section gives some advice on the topic. One major issue in lexicographic goal programming is that of priority level redundancy. Therefore there is now no point in continuing with the 3.
The only goal to be considered is the one in the first priority level.
One may as well have conducted a single-objective optimisation of that goal. There has therefore been no true consideration of the multi-objective nature of the problem. This is an extreme case of the problem of lexicographic redundancy Romero, In reality it does not have to involve all but one of the priority levels and does not only occur when goals are set to their ideal values.
There is some discussion on the gravity of this problem, with Schniederjans arguing that some redundancy is not necessarily a problem as goals are placed in lower priority levels by the decision maker for a reason, but nevertheless the consensus seems to be that redundancy is in general undesirable as it limits the number of goals considered. The following causal effects of redundancy are therefore identified: As one of the advantages of using the lexicographic variant is the avoidance of direct comparison of incommensurate goals, one would be wary of including goals in the same priority level that one did not wish to compare.
However, in many cases there are goals which are in the same units or which can be compared if normalised e. These should be placed in the same priority level rather than creating separate priority level if they have similar levels of decision maker priority.
Intra-priority weights can be used to allow for decision maker preference between them. The opposite approach would be to use one priority level for each goal. It can be appropriate for cases with few goals but great care should be taken over setting target levels if this approach is used. The consensus in the goal programming literature is that no more than five priority levels should be used in the lexicographic variant.
It would be unusual to find a practical situation with more than five mutually non-comparable priorities. This uses Pi to represent the ith priority level. This notation is not preferred in this book as it expresses the lexicographic minimisation as a summation when in fact it is not, neither from a theoretical nor a practical viewpoint.
It can be the ideal choice when such a priority scheme exists in the mind of the decision maker. It can also be used to avoid unwanted direct comparisons between sensitive criteria. The example will now be formulated as a weighted goal programme. Critical to this process are the weights associated with the penalisation of the deviational variables.
The weight technically contains two parts. The first is a preferential weight in the numerator that represents the relative importance of the penalisation to the decision maker. Additionally, a normalisation factor in the denominator is needed that scales the deviations so they can be compared in the same units. It is vital that this second part is not omitted if the goals are not measured in compatible units.
Otherwise, the summation will be meaningless due to the problem of incommensurability. As a demonstration of this consider that the following two goals express the same concept: Therefore, some scaling is needed. The following section examines commonly used scaling, or normalisation, constants.
Here each deviation is turned into a percentage value away from its target level. Thus all deviations are measured in the same units. In our example, consider that the decision maker regards the penalisation of all unwanted deviations as equally important.
The weighted goal programme with percentage normalisation is given as 3. The former gives the same effect as the latter but with less effort in reformulation. Also, the objective function contributions are actually proportions rather than percentages.
That is they are one hundredth of the percentage value. The entire achievement function could be multiplied by to give percentages, but this does not affect the optimal solution found.
The achievement function value a now has meaning, the total sum of proportional deviations away from the goals. It can, however, cause some distortion when a subset of the goals is measured in the same units. For instance consider the following two goals, both expressed in dollars that form part of a goal programme: This is correct if the concern is about percentage shortfall of budgets but not correct if wishing to compare the shortfalls directly in dollars.
Thus care should be taken as the correct choice is problem dependent. The other situation which will cause problems for percentage normalisation are goals with zero target values or target values that are not representative of the range of possible values for the criterion.
In this case, a realistic value for the normalisation constant based on investigations of the range of possible values should be derived. In any case, whichever normalisation scheme is used, for every goal a verification of the normalisation constant should take place in the context of the decision situation to ensure that it is having the desired effect.
The value zero will represent a deviation of zero and the value one will represent the worst highest possible value of the deviation within the feasible set, which gives the anti-ideal value of the underlying objective. This latter value can be found by a single-objective maximisation, except in some cases where this optimisation is unbounded in which case a realistic worst practical value will have to be estimated.
In our example problem the worst possible values of our unwanted deviational variables are given in Table 3. Table 3. This shows that the choice of normalisation method can indeed affect the optimal solution found and hence care should be taken to choose a method that reflects the preferences and interests of the decision maker.
The zero—one method is good in cases such as the example presented when each objective has clearly defined ranges and all portions of the feasible set are of potential interest to the decision maker. However, for examples with unbounded goals i. That is, the worst value, and hence the normalisation constant, corresponds to an arbitrarily chosen or irrelevant solution. A theoretical alternative is to use the worst value from amongst the set of Pareto-efficient solutions nadir value , but this value is computationally difficult to determine Ehrgott, , p.
The other point to note about zero—one normalisation is that it requires Q single-objective optimisations in order to determine the worst values for the objectives.
This could be impractical for complex or large problems where the solution time for the problem is large. Here the normalisation constant is the Euclidean mean of the technical coefficients of the goal. However, the two problems outlined by Romero with respect to Euclidean optimisation are evident from the example. The first is that a lack of consideration of the target value has led to relatively low values of the normalisation constants of goals 3 and 4.
The second is that, unlike the other two normalisation methods, the optimal value of the achievement function does not have any obvious meaning. Hence, in our opinion, this normalisation scheme should be reserved for cases in which it is impractical to apply either percentage or zero—one normalisation.
A further normalisation scheme based on the summation of the absolute values of the technical coefficients of the goals is proposed by Jones , as an automated means of measuring the level of incommensurability in a goal programme. It should be noted, however, that the ultimate choice of the normalisation scheme is dependent on the individual problem situation and preferences of the decision maker.
As detailed in Chapter 2, these weights should be non-negative for the basic WGP model and the following notation will be used: Other deviations, for example excess profit in the example, p2 , should be given a zero weight.
Giving deviations such as p2 a positive weight will unnecessarily penalise good solutions and hence may lead to erroneous conclusions. The derivation of a weight set that will accurately represent the preferences of the decision maker is an issue of key importance when using weighted goal programming.
Many decision makers will not instantly be able to know or express weights with confidence, especially when implications of their weight choice are as yet unknown. Decision maker s naturally relate more to the implications of weighting strategies in terms of the levels of achievement of the goals or the actual decisions made.
Therefore, just as for the target values, it is important to regard weight determination as a process of interaction with the decision maker s rather than a single a priori declaration of a weighting scheme. This interaction can take many forms. Formal interactive methods exist for goal programming and for the wider field of multiple objective programming e. Gardiner and Steuer, ; Caballero et al. Otherwise, a good sensitivity analysis should be conducted, with the effects on goal satisfaction of changing individual weights or subsets of weights described and reported to the decision maker s.
This could result in the decision maker s moving to a different solution once this information is known. This process needs to start from an initial solution and there are several options seen in the literature for choosing an initial point: This is a good option if the decision maker s is confident enough to produce one.
This is a valid starting point if no other information is available, but tragically it can be seen in the literature as the only point investigated in some cases. This can supply a starting point, but again does not circumvent the need for good sensitivity analysis with respect to the set of weights. They do not always have the time or inclination to engage in a complex or iterative weight elicitation process.
In this case, the weighting space should be explored by the modeller and an appropriate set of solutions prepared for the decision maker s. The weight space exploration heuristic used to produce Table 3. The three axes give the value of the first three weights and the value of the fourth weight can be ascertained by the fact that the Fig.
See Section 4. This leads to a certain imbalance, with some goals doing very well but other goals being a long way from being achieved. If a balance between the objectives is the dominant need, then the Chebyshev goal programming CGP variant Flavell, should be applied. This is represented by point D in Fig. The levels of the goals are given in Table 3. Always include both deviational variables in the goal formulation except where the target level has been set to the ideal value.
Regard the weights, priority schemes, and target levels as initial estimates and not set in stone values. Always use an appropriate normalisation scheme with the weighted variant. Remember that the Chebyshev variant and priority levels within the lexicographic variant need normalising too if they are not commensurable.
Always perform a validation of each normalisation constant in the context of the decision situation. Always check the solution for Pareto efficiency and use a restoration scheme if required.
Only penalise unwanted deviations. Always make an informed choice of variant based on the nature of the problem. Neither constraint should be violated. The objective function should achieve a level of at least Compare this formulation to that of the original linear programme. What does this lead you to conclude about the relationship between linear programming and lexicographic goal programming?
The retailer has the following goals: Goal 1: The retailer wishes to employ exactly 15 pickers. Goal 2: The retailer wishes to process at least orders per hour. Goal 3: In addition, there are hard constraints that at least three experienced pickers must be employed and no more than 20 pickers can be employed in total.
Priority Level 1: Achieve goal 3. Priority Level 2: Achieve goals 1 and 2 equally weighted. Each grade A cup requires 2 h of furnace time and 3 h of finishing labour. Each grade B cup requires three hours of furnace time and 5 h of finishing labour.
Each grade C cup requires 4 h of furnace time and 10 h of finishing labour. The company currently has h of furnace time and h of finishing labour per day.
They have a high level of demand and therefore they have a strategic aim of increasing production to cups per day by increasing the level of furnace and finishing hours available. Priority 1: Achieve the strategic aim of cups per day.
Minimise the extra finishing and furnace hours needed.
Priority 4: Ensure that at least of each type of cup is manufactured. The estimated demand by 3-hourly intervals is given in Table 3. Workers working at night between Ensure that each interval has at least the estimated number of workers.
Minimise the number of workers employed above the estimate for each interval. Minimise the number of workers starting their shift at The values of protein, carbohydrate, saturated fat, vitamin B6, vitamin C, and calcium should ideally fall between the bounds given in Table 3. The diet can be composed of an integer number of units of ten basic foodstuffs, termed FOOD1,. The amount of nutrients in one unit of foodstuff and its cost is given in Table 3.
Formulate 1. A normalised weighted goal programme that places ten times as much importance on medical needs as cost considerations or patient preferences 2. A lexicographic goal programme that considers medical needs, cost considerations, and patient preferences in that order 3. The distance in kilometres , time in hours , and cost in C of travelling between cities are given in Table 3.
The salesperson wishes to achieve goals of no more than km, 10 h, and C for the trip. Refer to Applegate et al. The supply and demand levels in l per day are given in Table 3.
Given that all customer demands must be fulfilled, formulate a normalised weighted goal programme with the following goals: Goal 4: Assign any unused capacity to site three. How would you go about determining weights for this goal programme and checking their validity? Reformulate as a lexicographic goal programme with the following priority order: Does this solve the issue of commensurability or is normalisation required?
Reformulate as a normalised Chebyshev goal programme. These actions affect the low-income, mid-income, and high-income members of the populace in different ways. Assuming the three groups are of equal importance, formulate a weighted goal programme to represent this situation.
Does this model require normalisation? Why or why not? Again, assuming the three groups are of equal importance, formulate a Chebyshev goal programme of this situation.
Assuming the priority order: Example 9 — Budget Planning A new budget has to be allocated to ten facilities based on their values in five key performance measures F1—F5 , given in Table 3. Formulate a goal programme whose solution will give the correct mix of the five measures so as to minimise the total change in budget positive or negative for the ten facilities in transitioning from the current to the new budget.
Formulate a goal programme whose solution will give the correct mix of the five measures so as to minimise the maximum change in budget positive or negative for any facility in transitioning from the current to the new budget. Example 10 — Healthcare Planning A hospital consists of six departments. The hospital manager wishes to achieve goals relating to the time of service and cost of service, for both individual departments and the hospital as a whole.
A total of beds must be divided amongst the six departments by the hospital manager. Each department has a minimum and maximum bound on the number of beds, as shown in Table 3. Each department is given the opportunity to place its own relative preference weights on time and cost and these are given in Table 3. The target cost and time levels for the departments are also given in Table 3.
The hospital manager also has an overall time target of and cost target of She weights these two goals equally at a hospital level. Achieve the hospital-level goal with respect to time of service. Achieve the hospital-level goal with respect to cost of service. Chapter 4 Advanced Topics in Goal Programming Formulation The topic of how to formulate effective goal programmes using the major variants is covered in Chapter 3.
This chapter expands on those concepts by introducing techniques developed to expand the flexibility of goal programming and enhance its use. These axioms Winston, are as follows: In the goal programming paradigm this axiom requires that the penalisation for an unwanted deviation from a target level is directly proportional to the distance away from the target level.
This axiom requires that the level of penalisation for an unwanted deviation from a target level is independent of the levels of unwanted deviations from the other goals. This axiom requires that all the decision variables should be free to take any value within their prescribed range greater or equal to zero by default.
Thus a decision variable cannot be forced to take an integer or a discrete value.
This axiom requires all the data coefficients to be known with certainty. However, if one of the above axioms does not hold, the use of goal programming is not necessarily precluded. In the case of the additivity axiom not holding, a nonlinear goal programme could be formulated or a meta-heuristic method described in Chapter 7 could be used.
In the event of the divisibility axiom not holding, an integer or binary goal programming described in Section 2. When the certainty axiom does not hold then the method used will depend on the type of coefficients over which there exists uncertainty. As described in Chapter 3, a certain amount of uncertainty over weights and target values often exists and this can frequently be handled by good sensitivity or weight analysis techniques or D. An alternative is to use the fuzzy goal programming variant described in Section 2.
If there is uncertainty over the technological coefficients then either the fuzzy goal programming variant could be utilised or a combination with a technique such as simulation could be attempted.
The choice of method in this case is highly problem dependent. A range of real-life situations in which the proportionality axiom does not hold was identified in the s and a technology known as penalty functions was developed to allow more accurate modelling in such cases. This has been expanded into the general case of non-standard preference function modelling in the s. Section 4.
These lead to a linear relationship between the magnitude of the unwanted deviation and the penalty imposed. This type of relationship will be termed a preference structure in this book.
The basic linear preference structure is graphically demonstrated by Fig. The gradient of the line shown is ui or vi. However, in many fields of application the penalties for exceeding a certain level of unwanted deviation could become more or even less severe.
This change could for example take the form of a sudden increase in penalty to represent the cost of an event. An example of this would be if an extra vehicle or warehouse is required in a logistics model. Alternatively, there could be an increase in per unit penalty at Fig. The opposite could also be true, as is the case if a bulk discount is offered. These considerations lead to the proposition of modelling any combination of the above circumstances as a series of four types of preference changes.
These are proposed by Jones and Tamiz and are capable of modelling any type of monotonically increasing penalty structure. Type 1: Increase in Per Unit Penalty Penalty Function This type of preference change is used when the per unit penalty to be applied is increased beyond a certain level of deviation. For example, consider the second objective in the manufacturing example given in Chapter 3. This leads to with the penalisation of the term the relationship between profit made and penalty applied to the achievement function shown graphically by Fig.
This leads to the new preference structure given by Fig. The first is introduced by Can and Houck in the context of water resources planning. It is also used by Romero , Martel and Aouni , and Chang This method involves the introduction of bounded deviational variables to represent the different linear segments of the preference structure.
The above example requires 2 3 two extra deviation variables, which shall be termed n2 and n2. The original devi 1 ation variable n2 will be re-termed n2. The relevance of these deviational variables is shown in the preference structure given by Fig. It should also be noted that the same normalisation constant, based on the original goal, is used to normalise all the deviational variables. This is the case because they are all measured in the same unit.
The advantage of this type of formulation is that it is able to represent the new preference structure without adding any extra constraints to the model. The disadvantage is the lack of transparency in reading the results.
This can be overcome by a simple piece of computer code to add the deviations together or by using a graphical representation of the achievement level of the preference function such as Fig. Another point to consider when using this type of formulation is that it could interfere with some of the goal programming speed-up and analysis techniques Jones, The second method, introduced by Jones and Tamiz , is to define a secondary objective at each of the points where the preference increases, and a hard constraint, known as an objective bound at the point beyond which the objective becomes so badly achieved as to make the resulting solution unimplementable.
Again considering the second objective of the manufacturing examples, the original 1 1 deviational variables n2 and p2 are re-termed n2 and p2. The significance of the new deviational variables is shown graphically by Fig. The corresponding algebraic formulation for the second objective is given as Fig.
This formulation has added more objectives and deviational variables but is more transparent and also has the advantage of being more easily extendable to the other types of preference structure change discussed in this section.
Type 2: Decrease in Per Unit Penalty Reverse Penalty Function A less common but still realistic situation is to see a decrease in per unit penalty beyond a certain level of achievement. For instance, consider the first objective in the manufacturing example given in Chapter 3.
Now suppose that any labour with an achievement function contribution of between and h should be made up by overtime at a high cost but over h would result in the hiring of permanent labour at a lower cost and greater strategic benefit for the company.
Therefore labour beyond h, whilst still being undesirable, has a lower per unit cost than for between and h. Using the second Jones and Tamiz, system as for an increase in penalty, only subtracting the change term in the achievement function leads to the following algebraic representation of the preference structure: The original goal programming models were designed to have deviational variables with only positive or zero coefficients in the achievement function.
This implicitly ensured that both deviational variables of an objective would never take non-zero values simultaneously. This is an implicit modelling of the non-linear condition: Thus one of two ways to explicitly take this condition into account must be utilised.
If access to the solver code is available, a basis restriction routine Jones can be implemented to ensure that these two variables are not allowed to take non-zero values simultaneously. These two constraints will together enforce the required condition. A graphical example of a type 2 preference change is given by Fig.
Type 3: Single Increase in Penalty Discontinuity in Preference There may exist situations where sudden consequences occur at a certain level of deviation from the target. Examples of this are in logistics where items have to be sent in lorries and to exceed the target beyond a certain point would require an extra lorry. Figure 4. This discontinuous increase occurs with every new lorry that is required.
Consider the third and fourth strategic production objectives in the manufacturing example given in Chapter 3. Suppose the company now wishes to refine their strategic aims to give the preference structure of the type shown graphically by Fig. This requires the use of binary variables and will result in a binary goal programme.
This allows for the scaling of the dissatisfaction of a range between 0 1 1 and 1 unit with 0. Type 4: The objective function fi x is non-linear over this range and therefore linear programming based techniques cannot be immediately applied. Jones and Tamiz recommend that this situation is handled by applying a piecewise linear approximation Williams, and then applying a series of preference changes of types 1—3 to convert the problem into an integer goal programme.
The greater the level of accuracy required in the approximation, the more preference changes are required and hence the larger the size of the resulting goal programme. Model Growth Adding non-standard preferences causes the size of the goal programme to grow as they require additional constraints, variables, and integer variables.
This can result in longer computational solution times, particularly if large numbers of preference types 2, 3, and 4 are added because they require binary variables. Table 4. This case is termed an objective bound.
An appropriate upper bound is then added to the relevant deviational variable. In the case where no deviational variables exist for the criterion 4. For discontinuous criteria, these bounds can often be implicitly specified in the choice of value M. Charnes and Collomb proposed to relax the condition that a single goal target value should be specified. Instead they allow the decision maker to choose an interval which is satisfactory and penalise deviations from either end of this interval.
This approach is termed goal interval programming. In algebraic terms it involves converting the single target point bi. Most of the frameworks prior to the Jones—Tamiz framework described above concentrated on the type 1 penalty function preference change, the earliest example of which is formulated by Charnes et al. Martel and Aouni provide the first global preference change framework in with their adaptation of the Promethee discrete multi-criteria method Brans et al.