Goal Programming  CAS Goal Programming ¢â‚¬¢We have assumed so far that...
date post
10Feb2021Category
Documents
view
1download
0
Embed Size (px)
Transcript of Goal Programming  CAS Goal Programming ¢â‚¬¢We have assumed so far that...
Goal Programming An Analysis of MultipleObjective Optimization
Susana Barreiro
8 May 2020
Goal Programming
• We have assumed so far that linear programming encompasses a single overriding objective (e.g. maximizing total profit / minimizing total cost).
• Most times this is not realistic since we frequently focus on a variety of objectives, e.g. forest management:
• to maintain stable profit,
• increase wood production,
• diversify ecosystem services,
• restrain the impact of pests /diseases,
• minimize erosion,
• …
Goal programming provides a way of achieving
several objectives simultaneously.
• Linear programming Most LP problems have hard constraints that cannot be violated:
• Goal programming GP problems have soft constraints that represent goals or targets we want to achieve
Constraints are very important because they refer to the amount of resources / capacity limits we face
First, we look at our limitations;
Then, we think of an optimization model
Goal Programming
Max: Z = 90 x1 + 120 x2
Subject to:
x1 ≤ 40
x2 ≤ 50
2x1 + 3x2 ≤ 180
and x1 ≥ 0; x2 ≥ 0
(ha of pine)
(ha of eucalypt)
(days of work)
Capacity limits we cannot change (e.g. number of seats on a flight) or we do not want to change
• Linear programming Most LP problems have hard constraints that cannot be violated:
• Goal programming GP problems have soft constraints that represent goals or targets we want to achieve
Suppose we look back to the Poets problem again and he says that he reconsidered and would be:
“… willing to give an extra 250 days of work if needed… preferred having 40 and 50 ha of pine and eucalypt but he would be flexible ”
The “days of work” would no longer be a hard constraint
Goal Programming
Max: Z = 90 x1 + 120 x2
Subject to:
x1 ≤ 40
x2 ≤ 50
2x1 + 3x2 ≤ 180
and x1 ≥ 0; x2 ≥ 0
(ha of pine)
(ha of eucalypt)
(days of work)
• The basic approach of goal programming is to:
1) establish a specific numeric goal for each of the objectives
2) formulate an objective function for each objective
3) seek a solution that minimizes the (weighted) sum of deviations of these objective functions from their respective goals
Goal Programming
There are three possible types of goals:
• A lower, onesided goal sets a lower limit that we do not want to fall under (but exceeding the limit is fine).
• An upper, onesided goal sets an upper limit that we do not want to exceed (but falling under the limit is fine).
• A twosided goal sets a specific target that we do not want to miss on either side.
Goal Programming
• Goal programming problems can be categorized according to the type of mathematical programming model that it fits except for having multiple goals instead of a single objective:
• linear programming,
• integer programming,
• nonlinear programming,
• etc
In class, we ill only consider linear goal programming—those goal programming problems that fit linear programming, but I’ll refer to it just as goal programming
Goal Programming
• Goal programming problems can also be categorized according to how the goals compare in importance:
• nonpreemptive goal programming – if all the goals are of roughly comparable in importance
• preemptive goal programming – if there is a hierarchy of priority levels for the goals, so that the goals of primary importance receive first priority attention, those of secondary importance receive secondpriority attention, and so forth (if there are more than two priority levels).
Goal Programming
The OR department of the DEWRIGHT COMPANY has been assigned the task of determining which mix of products should be produced.
Management wants primary consideration given to the following three goals:
(1) achieving a longrun profit (NPV) of at least $125 million from these products
(2) maintaining the current employment level of 4,000 employees,
(3) holding the capital investment to less than $55 million.
Goal Programming  Nonpreemptive
However, it probably will not be possible to attain all these goals simultaneously, priorities have been discussed leading to setting a penalty weight:
1) 5 for missing the profit goal (per $1 million under),
2) 2 for going over the employment goal (per 100 employees) and 4 for going under this same goal
3) 3 for exceeding the capital investment goal (per $1 million over)
Each new product’s contribution to profit, employment level, and capital investment level is proportional to the rate of production.
Goal Programming  Nonpreemptive
These contributions per unit rate of production are shown in the table along with the goals and penalty weights.
Goal Programming  Nonpreemptive
Goal Programming  Nonpreemptive
Goal Programming Formulation: The Dewright Company problem includes all three possible types of goals:
• profit goal is a lower onesided goal: 12x1 + 9x2 + 15x3 ≥ 125
• employment goal is a twosided goal: 5x1 + 3x2 + 4x3 = 40
• investment goal is an upper onesided goal: 5x1 + 7x2 + 8x3 ≤ 55
Where x1, x2, x3 are the decision variables representing the production rates of products 1, 2, and 3, respectively and x1, x2, x3 ≥ 0
Goal Programming  Nonpreemptive
Linear Programming Formulation: Transform goals into constraints
• Subject to:
12x1 + 9x2 + 15x3 ≥ 125 5x1 + 3x2 + 4x3 = 40 5x1 + 7x2 + 8x3 ≤ 55
• Objective function:
The objective then is to choose the values of x1, x2, and x3 that minimize
Z = 5(amount under the longrun profit goal) + 2(amount over the employment level goal) + 4(amount under the employment level goal) + 3(amount over the capital investment goal)
Maybe we can’t satisfy all goals, but we want to
capture how much we can satisfy (find the deviations)
where no penalties are incurred for being over the longrun profit goal or for being
under the capital investment goal
Goal Programming  Nonpreemptive
Linear Programming Formulation:
To express this mathematically, we introduce some auxiliary variables y1, y2, and y3, to represent the deviations defined as follows:
y1 = 12x1 + 9x2 + 15x3  125 (longrun profit minus the target) y2 = 5x1 + 3x2 + 4x3  40 (employment level minus the target) y3 = 5x1 + 7x2 + 8x3  55 (capital investment minus the target)
Since each yi can be either positive or negative, and replace each one by the difference of two nonnegative variables:
y1 = y1 +  y1
, where y1 + ≥ 0, y1
 ≥ 0 y2 = y2
+  y2 , where y2
+ ≥ 0, y2  ≥ 0
y3 = y3 +  y3
, where y3 + ≥ 0, y3
 ≥ 0
yi + represents the positive part of yi variable (positive deviation)
yi  represents the negative part of yi variable (negative deviation)
Goal Programming  Nonpreemptive
Linear Programming Formulation:
Subject to:
12x1 + 9x2 + 15x3 ≥ 125 5x1 + 3x2 + 4x3 = 40 5x1 + 7x2 + 8x3 ≤ 55
Now we have a legitimate objective function for a linear programming model:
Min Z = 5y1  + 2 y2
+ + 4 y2  + 3 y3
+
Because there is no penalty for exceeding the profit goal of 125 or being under the investment goal of 55, neither y1
+ nor y3  should appear in this objective function
representing the total penalty for deviations from the goals.
If we’re above 125, we have a positive deviation y1 +, but it’s
according to the goal, so there is no problem. However, we don’t want to have a negative deviation, so we penalize y1

125 y1 +
y1 
Goal Programming  Nonpreemptive
Linear Programming Formulation:
Subject to:
12x1 + 9x2 + 15x3 ≥ 125 5x1 + 3x2 + 4x3 = 40 5x1 + 7x2 + 8x3 ≤ 55
Now we have a legitimate objective function for a linear programming model:
Min Z = 5y1  + 2 y2
+ + 4 y2  + 3 y3
+
Because there is no penalty for exceeding the profit goal of 125 or being under the investment goal of 55, neither y1
+ nor y3  should appear in this objective function
representing the total penalty for deviations from the goals.
We don’t care if we meet exactly the goal of 40 (=40), but we don’t want to be above or below 40 (having positive or negative deviations, respectively), thus we penalize y2
+
both y2 
40 y2 +
y2 
Goal Programming  Nonpreemptive
Linear Programming Formulation:
Subject to:
12x1 + 9x2 + 15x3 ≥ 125 5x1 + 3x2 + 4x3 = 40 5x1 + 7x2 + 8x3 ≤ 55
Now we have a legitimate objective function for a linear programming model:
Min Z = 5y1  + 2 y2
+ + 4 y2  + 3 y3