Goal Programming

The Goal Programming approach is the most popular for handling multiple objective problems in Linear Programming.

The basic idea is to convert multiple objectives into a single objective. The resulting model yields what is usually referred to as an efficient solution because it may not be optimum, with respect to all the conflicting objectives of the problem.

There are two cases to be considered :

Non-Preemptive Goal Programming : where all the goals are roughly comparable importance.

Preemptive Goal Programming : where there is a hierarchy of priority levels for the goals, so the goal of primary importance   receive first-priority attention, those of secondary importance receive second-priority attention, and so forth ( if there are more than two priority levels ).

Let  c₁(x),. . . .,c_k(x)  be the various objective functions to be optimized over the set of feasible solutions X.

In this approach, instead of trying to optimize each objective function, the decision maker is asked to specify a goal or target value that realistically is the most desirable value for that function.

For r = 1 to k, let g_r be the specified goal for c_r(x).

At any feasible solution  x є X,  for r = 1 to k, we express the deviation in the rth objective function from its goal, c_r(x) - g_r , as a difference of two nonnegative variables

                                                          c_r(x) - g_r = u_r⁺ - u_r^-                          //   Multiple objectives                                       ( 1 )

Where u_r⁺ , u_r^-  are the positive and negative parts of the deviation c_r(x) - g_r. Such that

                                                           u_r⁺      =    0                     if   c_r(x) - g_r  ≤  0

                                                           u_r⁺      =    c_r(x) - g_r         if   c_r(x) - g_r  >  0 

                                                           u_r^-       =   0                      if   c_r(x) - g_r   ≥  0

                                                           u_r^-       =   -(c_r(x) - g_r)      if   c_r(x) - g_r   <  0                                                               ( 2 )

The goal programming model for the original multiobjective problem will be a single objective problem in which we try to minimize a linear function of these deviation variables of the form  ∑₁^k ( α_ru_r⁺ + β_ru_r^- )     , where α_r , β_r ≥ 0 for all r , called a penalty function.  

If  objective function c_r(x)   is to be maximized then, then feasible solution x which make  u_r^- = 0 and  u_r⁺ ≥ 0 are desirable, and  u_r⁺ = 0 and       u_r^- > 0 become more and more undesirable. To guarantee that algorithm seeks solutions in which  u_r^- is as small as possible, we associate a positive penalty coefficient β_r with u_r^- , and include a term of the form α_ru_r⁺ + β_ru_r^- ( where α_r = 0 , β_r > 0 ) in the penalty function that the goal programming tries to minimize.

β_r > 0 measures the loss or penalty per unit shortfall in the value of  c_r(x) from its specified goal of g_r. Higher values of β_r represent greater importance.                       

If  objective function c_r(x)   is to be minimized then, then feasible solution x which make  u_r⁺ = 0 and  u_r^- ≥ 0 are desirable, and  u_r^- = 0 and u_r⁺ > 0 become more and more undesirable. So, for these we associate a positive penalty coefficient α_r with u_r⁺ , and include a term of the form         α_ru_r⁺ + β_ru_r^- ( where α_r > 0, β_r = 0 ) in the penalty function that the goal programming tries to minimize. Higher values of α_r represent greater importance attached by the decision maker to the objective functions in this class.

So, the goal programming model is the following single objective problem.

                                                  Minimize       ∑₁^k ( α_ru_r⁺ + β_ru_r^- )

                                                  subject to      c_r(x) - g_r = u_r⁺ - u_r^-    , r = 1 to k                                                                     ( 3 )

                                                                       u_r⁺ , u_r^-   ≥  0,  r = 1 to k

                                                                        x є X

The optimum solution of ( 3 ) depends critically on the goals selected, and on the choice of the penalty coefficients α = (α₁,...,α_k),  β = (β₁,...,β_k). With loss of generality we can assume that the vectors α_r, β_r are scaled so that ∑₁^k ( α_r + β_r ) = 1. Once  α_r, β_r are determined, an optimum solution of (3) is the solution to implement. One can solve (3) with different set of goal vectors for the various objective functions. This process can be repeated until at some stage, an optimum solution obtained for (3) seems to be a reasonable one for the original multiobjective problem. Exploring with the optimum solutions of (3) for different goal and penalty coefficient vectors in this manner, one can expect a practically satisfactory solution for the multiobjective problem.

Example on Goal Programming.