16
Aug

Operations Research 04G: Goal Programming


In this video, I’ll talk about how to formulate
goal programming problems. All the LP problems we have introduced so
far have only a single objective function. In real-world applications, we may face multiple
conflicting goals, and we may not be able to meet all the goals simultaneously. Goal programming provides a way for dealing
with such situations. It seeks a solution that minimizes the weighted
sum of deviations of these objective functions from their respective goals. In general, there are three types of goals. A lower, one-sided goal sets a lower limit
that we do not want to fall under, but exceeding the limit is fine. This corresponds to a ≥ constraint. An upper, one-sided goal sets an upper limit
that we do not want to exceed, but falling under the limit is fine. This corresponds to a ≤ constraint. A two-sided goal sets a specific target that
we do not want to miss on either side. This corresponds to an equality constraint. Let’s see an example. A project manager is trying to determine the
quantities of three types of products to produce. Producing one unit of product 1 will need
40 employees and 2 tons of raw material, and it will bring the company $5 million of profit. For product 2, these values are 30, 4, and
8. For product 3, these values are 20, 3, and
4. The manager wants to meet these three goals. First, the maximum number of employees that
can be allocated to producing these products is 100. Second, there are 10 tons of raw material
in the warehouse. The manager wants to consume them all, no
more and no less. Third, the total profit is expected to be
at least $30 million. The manager realizes that it probably will
not be possible to attain all these goals simultaneously. Therefore, he sets some penalty weights for
the unmet goals. If the project needs more than 100 employees,
each extra employee is associated with a penalty of 5. This penalty weight is unitless. If the total raw material needed is different
from 10 tons, each ton that is below this goal is associated with a penalty of 8, and
each ton that is above this goal is associated with a penalty of 12. If the profit is less than $30 million, each
million dollars under the goal is associated with a penalty of 15. So, the manager wants to minimize the total
penalty. Let’s define the decision variables. xi is the amount of product i to be produced. i=1,2,3. This is the first goal: the total number of
employees needed should not exceed 100. This is the second goal: the total amount
of raw material should be exactly 10, no more and no less. This is the third goal: the total profit should
be at least $30 million. Now, let’s introduce three variables, y1,
y2, and y3. They represents the deviations from the goals. For example, y1 is equal to the number of
employees needed in the project minus the goal, which is the 100 employees. If the needed number of employees is less
than 100, then y1 is a negative number. It the needed number of employees is equal
to 100, y1 is 0. If the needed number of employees is greater
than 100, y1 is a positive number. Therefore, y1 is an urs variable. So are y2 and y3. Now, let me re-write these three equations
by moving some items to the LHS and others to the RHS. This is the new form. We introduced in a previous video that, if
we have an urs variable, we need to define two new variables to represents the positive
deviation and the negative deviation from the goal, and replace the urs variable with
the positive deviation minus the negative deviation. Let’s do that for these three equations. The manager wants to minimize the total penalty. For the labor, there will be a penalty only
if the number of needed employees is over 100. So the penalty is 5 times y1+. For the raw material, there will be a penalty
if it is less than 10 tons, there will also be a penalty if it is greater than 10 tons. So, the penalty is 8 times y2- plus 12 times
y2+. For the profit, there will be a penalty if
it is less than $30 million. So, the penalty is 15 times y3-. The total penalty is their sum. This is the complete problem formulation. Even though it is unrealistic, we assume the
variables can take fraction numbers. So it is a LP problem. Otherwise, if some variables must take integers,
then this problem is a mixed integer programming problem. For this LP problem, we can solve it using
the simple method. This is the optimal solution. It means the manager should decide to only
produce 3.33 product 2. The first goal is achieved. He will not need more than 100 employees
The second goal is not achieved. He will need 3.33 tons of more raw material. The third goal is not achieved. The total profit is $3.33 million under the
goal. The minimum total penalty for deviating from
all three goals is z*=90. Okay, this is how to formulate goal programming
problems. Thanks for watching.

Tags: , , , , , , , , , , , , , , , , , , , , , ,

12 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *