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.