Archimedean Goal Programming Using Constraints
We must now minimize a weighted sum of violations of the constraints. Suppose that we have the following problem, this time with penalties attached:
| Penalties | ||||
|---|---|---|---|---|
| goal 1 (G1): | 7x + 3y | ≥ | 40 | 8 |
| goal 2 (G2): | 10x + 5y | = | 60 | 3 |
| goal 3 (G3): | 5x + 4y | ≤ | 35 | 1 |
| LIMIT: | 100x + 60y | ≤ | 600 |
Then the solution will be the solution of the following problem:
| minimize: | 8d1 + 3d2 + 3d3 + 1d4 | ||
| subject to: | 7x + 3y + d1 | ≥ | 40 |
| 10x + 5y + d2 – d3 | = | 60 | |
| 5x + 4y + d4 | ≥ | 35 | |
| 100x + 60y | ≤ | 600 | |
| d1≥ 0, d2≥ 0, d3≥ 0, d4≥ 0 |
In this case a penalty of 8 units is incurred for each unit that 7x + 3y is less than 40 and so on. the final solution will minimize the weighted sum of the penalties. Penalties are also referred to as weights. This solution will be x=6, y=0, d1=d2=d3=0 and d4=5, which means that the first and second most important constraints can be met, while for the third constraint the right hand side must be reduced by 5 units in order to be met.
Note that if the problem is infeasible after all the goal constraints have been relaxed, then no solution will be found.