# Concept Of Goal Programming Accounting Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Decision-makers always want to develop a model that can consider real-life situations with multiple objectives such as profit maximization, cost minimization, maximization of production capacity etc. which are conflicting in nature. In present scenario there is no single objective or goal for any organization. Now a days higher priorities are given the achievement of the goals such as public relationship, labor relationship, etc. Goal programming is a one technique used to derive a best possible solution of a multi-objective optimization problem. It is considered as a further extension of linear programming. Goal programming is first emerged as an issue for unsolvable or infeasible linear programming problems.

## A POINT OF ORIGIN OF GOAL PROGRAMMING

A. Charnes, W.W.Cooper and Ferguson (1955) on executive compensation gave the basic idea of GP according to Romero (1992, p.2). While the term goal programming did not appear in this 1955 article, this paper did present a constrained regression idea that embodies the deviation minimizing approach inherent in GP. According to Romero (1992), it was not until Charnes and Cooper's 1961 linear programming textbook, Management Models and Industrial Applications of Linear Programming that the term goal programming appeared. It was presented as an extension of linear programming (LP).

In the Charnes and Cooper (1961, pp. 215-221) book, goal programming was suggested for use in solving unsolvable LP problems (e.g. infeasible LP problems).

## CONCEPT OF GOAL PROGRAMMING

As GP is derived from LP, the GP model can be found by restating the LP model, its assumptions and modeling notation. Consider the canonical form of LP :

subject to :

for i = 1, . . . , m

xj â‰¥ 0 for j = 1, . . . , n (1.1)

where

xj = nonnegative decision variables or unknowns for j = 1, . . . , n

cj = cost associated with each unit of their respective decision variable for contribution to the objective function, Z for j = 1, . . . , n

aij = coefficients that represent the per unit usage by xj of the right-hand-side coefficient of bi for i= 1, 2, . . . , m and j = 1, 2, . . . , n

This LP model consists of a single objective or goal of minimizing the objective function or Z function. Here,the objective function is subject to a set of m constraints with n decision variables required to be non negative.

The LP model in (1.1) allows the possibility of positive deviation (called surplus in Linear Programming terminology) from the right-hand-side coefficients in the model, since the sum of the products in the left-hand-side can be greater-than or equal to any bi. It is also true that LP model can permit negative deviation ( called slack in Linear Programming terminology) from bi. Any LP model can include greater-than or equal-to and less-than or equal-to types of constraints.

In an LP model, the mathematical requirements represented by the constraints must be satisfied in order to have a feasible solution. Thus,when one or more constraints of an LP model finds itself outside or in conflict with the area of feasible solutions, we have an infeasible solution. Such constraints are called as hard constraints.

Charnes and Cooper (1961) suggested in their textbook that each constraint in a LP model can be considered as a separate function, called a functional. These functional are considered as individual objectives or goals to be attained where bi are the set of objectives or goals that must be satisfied in order to have a feasible solution. Thus, goal means objective in conjunction with the aspiration level, where, bi also called as aspiration level. If we subtract bi from both sides of an equality constraint, we can express the functional as the absolute value of an LP constraint, or :

(1.2)

As it is not always possible to achieve every goal to the extent the decision maker desires, GP helps to reach a satisfactory level of multiple objectives. Thus, the modern manager tries to "satisfice" or "come as close as possible" to the set goals because of which GP is often cited as a satisficing based technique.

Charnes and Cooper (1961, p. 217) illustrated how that deviation from goals existing in infeasible LP problem could be minimized by placing the variables representing deviation directly in the objective function of the model. This allows multiple ( and sometimes conflicting) goals to be expressed in a model that will permit a solution to be found. Multiple and conflicting goals are considered as a distinguishing characteristic to describe how a GP model differs from an LP model.

Basic assumptions of goal programming are:

Non-negative variables

Conditions of certainty

Variables are independent

Limited resources

GP consists of System constraints and Goal constraints. System constraints are:

Concerned with resources

Cannot be violated

Physical

For example, number of labor hours available for manufacturing

Goal constraints are:

Concerned with the target values

Can be changed/modified

For example, desire to achieve a certain level of profit.

The general goal programming model can be expressed as follows:

Subject to the linear constraints:

Goal constraints:

System constraints:

With , , xj â‰¥ 0, for i = 1, ... , m; for j = 1, ... , n (1.3)

Where there are m goals, p system constraints and n decision variables

Z = objective function

aij = the coefficient associated with variable j in the ith goal

xj = the jth decision variable

bi = the associated right hand side value

= negative deviational variable from the ith goal (underachievement)

= positive deviational variable from the ith goal (overachievement).

Both overachievement and underachievement of a goal cannot occur simultaneously. Hence, either one or both of these variable must have a zero value; that is,

## .

Both variables apply for the non-negativity requirement as to all other linear programming variables; that is,

## .

The deviation variables are related to the functional algebraically where :

Table 1 shows three basic options to achieve various goals:

## Table 1: Procedure for achieving a goal

## Minimize

## Goal

## If goal is achieved

Minimize the underachievement

Minimize the overachievement

Minimize both under- and overachievement

EXAMPLE 1: Suppose a firm manufactures two products which yield profit of Rs. 50 and Rs. 70 per unit, respectively.Each type A product requires 2 hours to manufacture and each type B product requires 4 hours to manufacture. The weekly availability of labor hour is limited to 360 hours. The raw material required to manufacture type A product is 5 kg /unit and for type B is 6 kg/unit with the total availability of 2000 kg of raw material. Formulate it as a goal programming problem.

If profit maximization is the main objective i.e. only one objective function then linear programming can be used to find the optimal solution. Thus the LPP is formulated as

Maximize profit, Z = 50x1 + 70x2

Subject to

2x1 + 4x2 <= 360 (Labor hours)

5x1 + 6x2 <= 2000 (Raw material)

x1 , x2 >= 0

where

x1 = Number of units of type A product manufactured

x2 = Number of units of type B product manufactured

Now, suppose the management is not interested in maximizing profit but rather desire a certain profit level of say 10,000 as desirable to achieve under the given constraints. Then, for this it is required to formulate a goal programming problem in which we want to find the product mix that achieves this goal as close as possible under the given constraints.

Let

d1- = underachievement of the profit goal of Rs. 10,000

d1+ = overachievement of the profit goal of Rs. 10,000

Now we state the goal programming model as:

Minimize Z = d1- + d1+

Subject to

50x1 + 70x2 +d1- - d1+ = 10,000 (Profit goal)

2x1 + 4x2 <= 360 (Labor hours)

5x1 + 6x2 <= 2000 (Raw material)

x1 , x2, d1-, d1+ >= 0

## Extension to equally important goals

In the above example, consider the following goals each having equal importance i.e. equal priority.

## Goal 1 : To avoid underachievement of the profit goal

## Goal 2 : To minimize overtime of the labor hours available

## Goal 3 : To fully utilize the raw material available

To define the goal programming problem for the above condition, consider the following deviational variables:

d1- = underachievement of the profit goal of Rs. 10,000

d1+ = overachievement of the profit goal of Rs. 10,000

d2- = underachievement of available labor hours

d2+ = overachievement of available labor hours

d3- = underachievement of available raw material

d3+ = overachievement of available raw material

The new objective function and constraints for the goal programming problem are:

Minimize Z = d1- + d2+ + d3-

Subject to

50x1 + 70x2 +d1- - d1+ = 10,000 (Profit goal)

2x1 + 4x2 +d2- - d2+ = 360 (Labor hours)

5x1 + 6x2 +d3- - d3+ = 2000 (Raw material)

x1 , x2, d1-, d1+, d2-, d2+ , d3-, d3+ >= 0

## COMPARISON OF LINEAR PROGRAMMING AND GOAL PROGRAMMING

Linear programming tries to maximize or minimize the objective function say profit maximization or cost minimization whereas in goal programming deviations between goals and what can be achieved within the given set of constraints are to be minimized.

Linear programming involves cardinal values or numbers which are the basis of calculations expressed in exact amount i.e. profit or loss. Goal programming allows for an ordinal solution as practically speaking management is unable to specify the cost or utility of a goal or a subgoal but upper or lower limits may be stated for each goal or a subgoal. Here, manager is required to set priority of attainment of each goal or subgoal and rank them in ordinal sequence for decision analysis.

## LEXICOGRAPHIC GOAL PROGRAMMING MODEL

In a decision making situation, the goals set by management can be achieved only at the expense of other goals. For this to accomplish it is necessary to establish a hierarchy of importance among the stated goals so that higher priority goals are considered first and are satisfied followed by lower-priority goals. Thus before solving a goal programming problem, the goals need to be ranked. Lexicographic goal programming is also called the preemptive or non-Archimedean goal programming model (Ignizio, 1985). In priority goal programming, the objectives can be divided into different priority classes or k ranks (P1, P2â€¦). Here it is assumed that no two goals have equal priority. Here, P's are not given actual values, but this is a method to indicate that one goal is more important than the other. These priority factors have the relationship Pj >>> nPj+1 (j=1,2,â€¦k) where >>> means is "very much greater than" and n is very large. This indicates however large n may be, multiplication of priority with n cannot make nPj+1 greater than Pj. This means that priority ranking is absolute i.e. the P1 goal is so much more important than the P2 goal and P2 goal will never be attempted until the P1 goal is achieved to the greatest extent possible.

The above model can be restated as:

Subject to the linear constraints:

Goal constraints:

System constraints:

With di+, di-, xj â‰¥ 0, for i = 1,..., m; for j = 1,..., n (1.4)

Where there are m goals, p system constaints, k priority levels and n decision variables

Z = objective function

aij = the coefficient associated with variable j in the ith goal

xj = the jth decision variable

bi = the associated right hand side value

= negative deviational variable from the ith goal (underachievement)

= positive deviational variable from the ith goal (overachievement).

Pk = the priority factor of the kth goal.

Here, the difference between equations (1.3) and (1.4) is the priority factor in the objective function.

The objective function of a goal programming model may consist of nonhomogeneous units of measure, such as Rs., Kg, pounds, dollar, rather than one type of unit. To overcome this, if the unwanted deviation variables are assumed to be linear and separable then it will assume the form

where uk is the preferential weight associated with the minimization of unwanted deviational variable, at kth priority level. vk is the preferential weight associated with the minimization of unwanted deviational variable, at kth priority level. Division by bi is a percentage normalization constant associated with ith goal which in turn is necessary to scale all the goals onto the same units of measurement.

In the above example let the following priorities are assigned:

Priority 1 is attached to the achievement of goal 1, priority 2 to achievement of goal 3 and priority 3 to achievement of goal 2.

Then, the preemptive goal programming problem is formulated as:

Minimize Z =P1 d1- + P2 d3- + P3 d2+

Subject to

50x1 + 70x2 +d1- - d1+ = 10,000 (Profit goal)

2x1 + 4x2 +d2- - d2+ = 360 (Labor hours)

5x1 + 6x2 +d3- - d3+ = 2000 (Raw material)

x1 , x2, d1-, d1+, d2-, d2+ , d3-, d3+ >= 0

## WEIGHTED GOAL PROGRAMMING MODEL

Weighted goal programming is used for direct comparison of objectives. The weighting of deviational variables at the same priority level shows the relative importance of each deviation. Charnes and Cooper (1977) stated the weighted goal programming model as:

Subject to the linear constraints:

Goal constraints:

System constraints:

With di+, di-, xj â‰¥ 0, for i = 1,..., m; for j = 1,..., n (1.5)

Where wi+ and wi- are non-negative constants representing the relative weight to be assigned to the respective positive and negative deviation variables. The greater the weight the greater the assigned importance to minimize the respective deviation variable to which the relative weight is attached. This model is a non-preemptive model that seeks to minimize the total weighted deviation from all goals stated in the model.

While Ijiri (1965) had introduced the idea of combining preemptive priorities and weighting, Charnes and Cooper (1977) suggested the goal programming model as:

Subject to the linear constraints:

Goal constraints:

System constraints:

With di+, di-, xj â‰¥ 0, for i = 1,..., m; for j = 1,..., n (1.6)

Consider the following preferential weights attached to the previous problem and then represent this situation as a weighted goal program with the preferential weights and priorities given:

## Goal

## Goal description

## Preference weight

## 1

To avoid underachievement of the profit goal

5.0

## 2

To minimize overtime of the labor hours available

3.0

## 3

To fully utilize the raw material available

2.0

The weighted goal programming problem is defined as:

Minimize Z =P1(5.0 d1- )+ P2 (3.0d3- )+ P3 (2.0d2+ )

Subject to

50x1 + 70x2 +d1- - d1+ = 10,000 (Profit goal)

2x1 + 4x2 +d2- - d2+ = 360 (Labor hours)

5x1 + 6x2 +d3- - d3+ = 2000 (Raw material)

x1 , x2, d1-, d1+, d2-, d2+ , d3-, d3+ >= 0

## GRAPHICAL SOLUTION OF GOAL PROGRAMMING PROBLEMS:

Graphical method is used for solving a two decision variables problem. Following procedural steps are employed after the problem has been formulated for solving the goal programming problem.

Step 1: Plot all the structural or system or hard constraints and identify the feasible region. In case no such constraint exists, the feasible region is where x1 and x2 are both non-negative.

Step 2: Plot the straight lines corresponding to the goal constraints. For this, set the deviational variables in the goal constraints equal to zero and plot the resulting equation labeling the deviational variables.

Step 3: Select the point or points which best satisfy the highest priority goal for identifying the top-priority solution.

Step 4: Move to the next highest priority goal and determine the best solution(s) in such a manner that this "best" solution does not degrade the solution(s) already achieved for higher priority goals.

Step 5: Repeat step 4 until all the priority levels are investigated.

Step 6: Identify the optimum point and analyze it in terms of degrees of goal attainment.

The purpose of graphical method is to illustrate the concept of goal programming solutions rather than a general technique for solving goal programming problems. Thus, graphical method is recommended for problems involving two structural variables.

EXAMPLE 2: A company manufactures two products radios and transistors. According to past experience, production of either a radio or a transistor requires an average of one hour in the plant. The plant has a normal production capacity of 40 hours a week. The marketing department reports that the maximum number of radios and transistors that can be sold are 24 and 30 respectively for a week because of limited sales opportunity. The gross margin from the sale of a radio is Rs. 80 and that from transistor is Rs. 40. The company has established the following goals and has assigned them priorities arranged in order of their importance as follows:

First, company wants to avoid any underutilization of normal production capacity.

Second, company wants to sell as many radios as possible. Since the gross margin from the sale of radio is twice the amount from transistor, company has twice as much desire to achieve sales for radio as for transistor.

Third, company wants to minimize the overtime operation for the plant as much as possible.

Formulate the problem as a goal programming problem and find the optimum solution using graphical method.

SOLUTION: Formulation of goal programming problem:

Let

x1, x2 = Number of radios and transistors manufactured, respectively.

d1- = Underachievement of normal operation hours

d1+ = Overachievement of normal operation hours

d2- = Underachievement of sales goal for radio

d2+ = Overachievement of sales goal for radio

d3- = Underachievement of sales goal for transistor

d3+ = Overachievement of sales goal for transistor

Then the given problem is formulated as a goal programming problem defined as follows:

Minimize Z = P1 d1- + 2 P2 d2- + P2 d3- + P3 d1+

Subject to

x1 + x2 + d1- - d1+ = 40

x1 + d2- - d2+ = 24

x2 + d3- - d3+ = 30

x1, x2, d1- , d1+, d2-, d2+, d3-, d3+ â‰¥ 0

## SOLUTION USING GRAPHICAL METHOD

Step 1: Taking the deviational variables equal to zero in each constraint, plot all the goal equations, as shown in the figure. Then associate arrows with each line to represent underachievement or overachievement of the goal.

Step 2: Identify top priority goal: Unwanted deviational variable in priority 1 is d1-. Setting d1- = 0 (minimum value), the feasible region is the shaded region as shown in the graph representing d1+. Any point in this shaded region satisfies the first goal to be achieved.

Step 3: Identify second priority goal: In the second priority goal, underachievement of the number of units sold of each radio and transistor is to be minimized with higher importance given to selling of radio as compared to transistor. For this set, d2- = 0. Similarly, the target of sales goal of transistors to 30 is attained by setting d3- = 0. Thus, the second priority goals are attained or satisfied at the point P with x1= 24, x2 =30 in the feasible region of the top priority.

Step 4: Identify third priority goal: In the third priority goal, overachievement of the normal operation hours, d1+ is to be minimized. Obviously, d1+ = 0 at all points on the line segment AB, at which top priority goal is satisfied. But second priority goal is not achieved at any point on the line segment AB. We cannot achieve the third goal without sacrificing the second goal. Thus, first two goal are satisfied and third goal is not satisfied. Putting d2- = 0, d3- = 0, x1= 24, x2 =30, we get, d2+ = 0, d3+ = 0.

Substituting the value of x1 and x2 in first goal constraint with d1- = 0, we get,

d1+ = 14.

Hence, the company should produce 24 radios and 30 transistors per week, so that the first two goals are fully achieved and in the third goal the overtime operation of the plant is minimized to 14 hours per week.

EXAMPLE 3: Solve the following goal programming problem using graphical method.

Minimize Z = 2P1 d1+ + 3 P1 d2+ + P2 d3- + P3 d4+

Subject to

x1 + x2 + d1- - d1+ = 10

x1 + d2- - d2+ = 4

5x1 + 3x2+ d3- - d3+ = 56

x1 + x2 + d4- - d4+ = 12

x1, x2, d1- , d1+, d2-, d2+, d3-, d3+, d4-, d4+ â‰¥ 0

The graphical solution to the above problem is given below.

We first begin with first priority level. The solution space satisfying the set of priority one is indicated in the graph with both d1+ and d2+ set to zero with achievement of second goal considered first having higher weight followed with achievement of first goal.

Next we attempt to satisfy priority two without degrading the solution to level 1. However, d3- cannot be set to zero as this would degrade the solution at priority level 1.

Further, we attempt to achieve priority level 3 which try to minimize d4- by setting d4- = 0. Consequently the final solution is given by:

x1= 4, x2 =6, d1- = 0 , d1+ =0, d2- = 0, d2+ = 0, d3- = 18, d3+ = 0, d4- = 2, d4+ = 0

## MODIFIED SIMPLEX METHOD APPLIED TO GOAL PROGRAMMING PROBLEMS

In this section we present an algorithm to solve a linear goal programming model, based on the well known simplex method used to solve linear programming problem. Thus, simplex method used to solve goal programming problem is similar to that for a linear programming problem in the modified form. Following steps are involved for solving a goal programming problem by modified simplex method:

Step 1: Establishing the Initial table : Construct the initial simplex table in the same manner as for linear programming problem with the coefficients of the decision variables and the deviational variables placed in the appropriate columns. Also, write the pre-emptive priority goals P1, P2,. . .,in xB column, starting from bottom to the top with the first priority, P1 placed at the bottom and the least priority placed at the top.

Step 2: The pre-emptive priority factors with weights attached with the deviational variables in the objective function Z will represent cj values as there is no profit maximization or cost minimization in the objective function in goal programming problems. Here we try to minimize the deviations from the goal as much as possible, by minimizing the deviational variables through the use of pre-emptive priority factors and different weights attached with the deviational variables in the objective function.

Step 3: Test of optimality : As different goals are measured in different units, compute the values of Zj and cj - Zj separately for each of the priority goals P1, P2,. . .,. Zj and cj - Zj are computed in the same manner as in the usual simplex method of linear programming problem. Thus,

cj - Zj = (cj - cB column)T. (jth column)

and Zj = (cB column)T . (xB column)

The optimality criterion Zj or cj - Zj is a matrix of size k x n, where k represents the number of pre-emptive priority levels and n is the number of variables including both decision and deviational variables.

For optimality test, check the c1 - Z1 row for the top priority P1; j =1. If all cj - Zjâ‰¥ 0 in the P1 row or there is zero in P1 row in xB column, then top priority goal P1 is said to be achieved.

In case at least one of these entries is negative in P1 row and there is no zero in P1 row in xB column, then the goal P1 is not achieved and can be improved further. For this proceed to the next step.

Step 4: To determine the entering variable : The variable in the column corresponding to the largest or most negative c1 - Z1 value in the P1 row is considered as the entering variable. In case of a tie, consider the next lower priority level. The column corresponding to the largest negative value in the lower priority row, out of the columns in which there is a tie in c1 - Z1 row, is selected as the incoming variable.

Step 5: To determine the outgoing variable : The process is the same as we do in simplex method in linear programming problem. The variable corresponding to the minimum non-negative value in the row known as key row, obtained by dividing the values in the xB column by the corresponding positive values in the column called as key column is selected as the outgoing variable.

The intersection element of the key row and key column is called as the key element.

Step 6 : Follow the same steps further as in simplex method in linear programming problem where we reduce the key element to 1 and with its help all other elements in the key column are reduced to 0 giving us new reduced matrix.

For this matrix, again determine Zj or cj - Zj for each of the priority goals P1, P2,. . .,. Again do the optimality test. If all the entries in P1 row are positive then first goal is achieved. Also, here values in xB column in P1 row will be zero to show that first goal is fully achieved.

If at least one of these entries is negative in P1 row and there is no zero in P1 row in xB column, then the goal P1 is not achieved. In this case again repeat step 4, 5 and 6.

Step 7: After achieving goal placed at P1 priority, proceed to achieve the next priority goal P2 in the same manner discussed above. The goal P2 cannot be improved or achieved further if there is positive entry in row P1 below the most negative entry in row P2.

Continue this process until the lowest priority goal is fully achieved or achieved to the nearest satisfaction.

For clear understanding of the above discussed method see the illustration of example 2 discussed above.

Minimize Z = P1 d1- + 2 P2 d2- + P2 d3- + P3 d1+

Subject to

x1 + x2 + d1- - d1+ = 40

x1 + d2- - d2+ = 24

x2 + d3- - d3+ = 30

x1, x2, d1- , d1+, d2-, d2+, d3-, d3+ â‰¥ 0

Taking x1 = x2 = d1+ = d2+ = d3+ = 0, we get d1- =40, d2- = 24, d3- = 30 which is the starting basic feasible solution. Computing modified simplex method, we get,

Step 1 : Formulation of initial table :

## B

## cB

## cj

## 0

## 0

## P1

## P3

## 2P2

## 0

## P2

## 0

## Minimum ratio (xB/xi)

## xB

## x1

## x2

## d1-

## d1+

## d2-

## d2+

## d3-

## d3+

## d1-

## P1

40

1

1

1

-1

0

0

0

0

40

## d2-

## 2P2

24

1

0

0

0

1

-1

0

0

24â†’

## d3-

## P2

30

0

1

0

0

0

0

1

-1

## -

## cj-Zj

## P3

0

0

-1

0

1

0

0

0

0

## P2

78

-2

-1

0

0

0

2

0

1

## P1

40

-1

0

0

1

0

0

0

0

## â†‘

Step 2 : cj row is written at he top of the table.

Step 3: Test of optimality : Here compute cj-Zj ; âˆ€ j = 1, 2, . . ., 8

C1-Z1 = 0 - (P1, 2P2, P2). (1, 1, 0)T = -P1-2P2

C2-Z2 = 0 - (P1, 2P2, P2). (1, 0, 1)T = -P1-P2

C3-Z3 = 0 - (P1, 2P2, P2). (1, 0, 0)T = 0

C4-Z4 = 0 - (P1, 2P2, P2). (-1, 0, 0)T = P3 + P1

C5-Z5 = 0 - (P1, 2P2, P2). (0, 1, 0)T = 0

C6-Z6 = 0 - (P1, 2P2, P2). (0, -1, 0)T = 2P2

C7-Z7 = 0 - (P1, 2P2, P2). (0, 0,1)T = 0

C8-Z8 = 0 - (P1, 2P2, P2). (0, 0, -1)T = P2

NOTE:- All the entries in the columns corresponding to vectors in the basis are zero. So, we compute cj-Zj for columns corresponding to non-basic variables only.

## Z = cBxB = (P1, 2P2, P2). (40, 24, 30)T = 40P1 + 78P2

Step 4: The most negative entry in top priority P1 is -1 in the first column. Therefore, x1 is the incoming variable and computing the minimum ratio, xB/xi, d2-

Is the outgoing variable. Thus the key element is a21.

Step 5: Here reducing all the elements in key column equal to zero with the help of key element, we obtain the next reduced table as :

## B

## cB

## cj

## 0

## 0

## P1

## P3

## 2P2

## 0

## P2

## 0

## Minimum ratio (xB/xi)

## xB

## x1

## x2

## d1-

## d1+

## d2-

## d2+

## d3-

## d3+

## d1-

## P1

16

0

1

1

-1

-1

1

0

0

16â†’

## x1

## 0

24

1

0

0

0

1

-1

0

0

## -

## d3-

## P2

30

0

1

0

0

0

0

1

-1

30

## cj-Zj

## P3

0

0

0

0

1

0

0

0

0

## P2

30

0

-1

0

0

2

0

0

1

## P1

16

0

-1

0

1

0

-1

0

0

## â†‘

Here again computing cj-Zj for columns corresponding to non-basic variables only as all entries in the columns corresponding to basic variables will be zero, we get,

C2-Z2 = 0 - (P1, 0, P2). (1, 0, 1)T = -P1-P2

C4-Z4 = P3 - (P1, 0, P2). (-1, 0, 0)T = P3 + P1

C5-Z5 = 2P2 - (P1, 0, P2). (-1, 1, 0)T = 2P2 + P1

C6-Z6 = 0 - (P1, 0, P2). (1, -1, 0)T = -P1

C8-Z8 = 0 - (P1, 0, P2). (0, 0, -1)T = P2

The most negative entry in top priority P1 is -1 in the second column. Therefore, x2 is the incoming variable and computing the minimum ratio, xB/xi, d1- is the outgoing variable. Thus the key element is a12.

## Z = cBxB = (P1, 0, P2). (16, 24, 30)T = 16P1 + 30P2

Step 6 : Repeating the above steps of reducing all the elements in key column equal to zero with the help of key element, we obtain the next reduced table as:

## B

## cB

## cj

## 0

## 0

## P1

## P3

## 2P2

## 0

## P2

## 0

## Minimum ratio (xB/xi)

## xB

## x1

## x2

## d1-

## d1+

## d2-

## d2+

## d3-

## d3+

## x2

## 0

16

0

1

1

-1

-1

1

0

0

## -

## x1

## 0

24

1

0

0

0

1

-1

0

0

## -

## d3-

## P2

14

0

0

-1

1

1

-1

1

-1

14â†’

## cj-Zj

## P3

0

0

0

0

1

0

0

0

0

## P2

14

0

0

1

-1

1

1

0

1

## P1

0

0

0

1

0

0

0

0

0

## â†‘

Here again computing cj-Zj for columns corresponding to non-basic variables only as all entries in the columns corresponding to basic variables will be zero, we get,

C3-Z3 = P1 - (0,0, P2). (1, 0, -1)T = P1 + P2

C4-Z4 = P3 - (0,0, P2). (-1, 0, 1)T = P3 - P1

C5-Z5 = 2P2 - (0,0, P2). (-1, 1, 1)T = P2

C6-Z6 = 0 - (0,0, P2). (1, -1, -1)T = P2

C8-Z8 = 0 - (0,0, P2). (0, 0, -1)T = P2

Since all the entries in P1 row are â‰¥ 0, so goal at priority first is achieved fully. Now we proceed to achieve goal P2 without affecting the achievement of goal P1.

## Z = cBxB = (0, 0, P2). (16, 24, 14)T = 14P2

Step 7: In P2 row, most negative value is -1 in column corresponding to variable d1+ in the above table. Therefore, d1+ is the incoming variable and computing the minimum ratio, xB/xi, d3- is the outgoing variable. Thus the key element is a34.

Reducing the above table as done in simplex method, we get,

## B

## cB

## cj

## 0

## 0

## P1

## P3

## 2P2

## 0

## P2

## 0

## Minimum ratio (xB/xi)

## xB

## x1

## x2

## d1-

## d1+

## d2-

## d2+

## d3-

## d3+

## x2

## 0

30

0

1

0

0

0

0

1

-1

## x1

## 0

24

1

0

0

0

1

-1

0

0

## d1+

## P3

14

0

0

-1

1

1

-1

1

-1

## cj-Zj

## P3

14

0

0

1

0

-1

1

-1

1

## P2

0

0

0

0

0

2

0

1

0

## P1

0

0

0

1

0

0

0

0

0

Here again computing cj-Zj for columns corresponding to non-basic variables only as all entries in the columns corresponding to basic variables will be zero, we get,

C3-Z3 = P1 - (0,0, P3). (0, 0, -1)T = P1 + P3

C5-Z5 = 2P2 - (0,0, P3). (0, 1, 1)T = 2P2- P3

C6-Z6 = 0 - (0,0, P3). (0, -1, -1)T = P3

C7-Z7 = P2 - (0,0, P3). (1, 0, 1)T = P2 - P3

C8-Z8 = 0 - (0,0, P3). (-1, 0, -1)T = P3

## Z = cBxB = (0, 0, P3). (30, 24, 14)T = 14P3

Here all cj-Zj â‰¥ 0 in P1 and P2 rows and 0, 0 in xB column. Therefore, the priority goals P1 and P2 are fully achieved. Now consider P3 row. Here all cj-Zj are not non-negative, and most negative entries are -1 and -1 in this row. But no further improvement is possible as below -1 and -1, there are positive entries in the higher priority order. Therefore, the optimal solution of the goal programming problem is

x1 = 24, x2 = 30, d1+ = 14, d1- =0, d2+ = 0, d2- = 0, d3+ = 0, d3- = 0

Here, first two priorities P1 and P2 are achieved fully while priority goal P3 is not achieved fully.

EXAMPLE 4: A manufacturer produces two products A and B. Each product requires time in two production departments. Product A requires 20 hours in department 1 and 10 hours in department 2. Product B requires 10 hours in department 1 and 10 hours in department 2. Production time is limited to 60 hours in department 1 and 40 hours in department 2. Contribution to profits for the two products in Rs. 40 and Rs. 60, respectively. Minimum profit level to be achieved is Rs. 1000. Management goals are to maximize profit and to manufacture 2 units of each product. Management considers the deviation of Re. 1 from the profit goal equal to one unit deviation from the product goal. Formulate the above problem as goal programming problem and solve it using modified simplex method.

SOLUTION : The goal programming problem is formulated as:

Minimize Z = d1- + d2- + d3-

Subject to

20x1 + 10x2 â‰¤ 60

10x1 + 10x2 â‰¤ 40

40x1 + 80x2 + d1- - d1+ = 1000

x1 + d2- - d2+ = 2

x2 + d3- - d3+ = 2

x1, x2, d1- , d1+, d2-, d2+, d3-, d3+ â‰¥ 0

where,

x1, x2 = Number of units of product A and B manufactured, respectively.

d1- = Underachievement of profit goal

d1+ = Overachievement of profit goal

d2- = Underachievement of units manufactured of product A

d2+ = Overachievement of units manufactured of product A

d3- = Underachievement of units manufactured of product B

d3+ = Overachievement of units manufactured of product B

Introducing slack variables S1 and S2, we get,

Minimize Z = d1- + d2- + d3-

Subject to

20x1 + 10x2 + S1 â‰¤ 60

10x1 + 10x2 + S2 â‰¤ 40

40x1 + 80x2 + d1- - d1+ = 1000

x1 + d2- - d2+ = 2

x2 + d3- - d3+ = 2

x1, x2, d1- , d1+, d2-, d2+, d3-, d3+, S1,S2â‰¥ 0

Initial basic feasible solution is given by

x1 = x2 = d1+ = d2+ = d3+ = 0, d1- =1000, d2- = 2, d3- = 2, S1 = 60,S2 = 40

Following the same steps as in the above example, modified simplex method is shown in the following table:

## B

## cB

## cj

## 0

## 0

## P1

## P3

## 2P2

## 0

## P2

## 0

## 0

## 0

## Minimum ratio (xB/xi)

## xB

## x1

## x2

## d1-

## d1+

## d2-

## d2+

## d3-

## d3+

## S1

## S2

## S1

## 0

60

20

10

0

0

0

0

0

0

1

0

6

## S2

## 0

40

10

10

0

0

0

0

0

0

0

1

4

## d1-

## 1

1000

40

80

1

-1

0

0

0

0

0

0

1000/80

## d2-

## 1

2

1

0

0

0

1

-1

0

0

0

0

## -

## d3-

## 1

2

0

1

0

0

0

0

1

-1

0

0

2â†’

## cj-Zj

## 5000

## -41

## -81

## â†‘

## 0

## 1

## 0

## 1

## 0

## 1

## 0

## 0

## S1

## 0

60

20

0

0

0

0

0

-10

10

1

0

4

## S2

## 0

40

10

0

0

0

0

0

-10

10

0

1

2â†’

## d1-

## 1

840

40

0

1

-1

0

0

-80

80

0

0

10.5

## d2-

## 1

2

1

0

0

0

1

-1

0

0

0

0

## -

## x2

## 0

2

0

1

0

0

0

0

1

-1

0

0

## -

## cj-Zj

## 842

## -41

## 0

## 0

## 1

## 0

## 1

## 81

## -81

## â†‘

## 0

## 0

## S1

## 0

20

10

0

0

0

0

0

0

0

1

-1

## d3+

## 0

2

1

0

0

0

0

0

-1

1

0

1/10

## d1-

## 1

680

-40

0

1

-1

0

0

0

0

0

-8

## d2-

## 1

2

1

0

0

0

1

-1

0

0

0

0

## x2

## 0

4

1

1

0

0

0

0

0

0

0

1/10

## cj-Zj

## 682

## 39

## 0

## 0

## 1

## 0

## 1

## 0

## 0

## 0

## 8

Since all cj-Zj â‰¥ 0, therefore, this is an optimal solution with

x1 = 0, x2 = 4, d1+ = 0, d1- =680, d2+ = 0, d2- = 2, d3+ = 2, d3- = 0, S1 = 20, S2 = 0

Therefore, production goal of product A is missed by 2 and profit goal is missed by Rs. 680.

EXAMPLE 5 : A firm produces two products P and Q, which yield a contribution margin of Rs. 120 and Rs. 90 per unit, respectively. The firm has a limited capacity in the two departments where these products need processing. The availability and requirements are given below:

## Department

## Processing time (hours)

## Daily Availability(hours)

## Product P

## Product Q

## I

6

3

90

## II

3

6

72

The management of the firm has specified the following goals:

## Goal

## Priority

Achieve a daily sales of at least 13 units of product P

P1

Produce a product-mix to make a daily profit of at least Rs. 1950

P2

Achieve a daily sales of at least 5 units of product Q

P3

Formulate the problem as a goal programming problem and find the optimum solution.

SOLUTION : The goal programming problem is formulated as:

Minimize Z = P1 d2- + P2d1- + P3d3-

Subject to

6x1 + 3x2 â‰¤ 90

3x1 + 6x2 â‰¤ 72

120x1 + 90x2 + d1- - d1+ = 1950

x1 + d2- - d2+ = 13

x2 + d3- - d3+ = 5

x1, x2, d1- , d1+, d2-, d2+, d3-, d3+ â‰¥ 0

where,

x1, x2 = Number of units of product P and Q manufactured, respectively.

d1- = Underachievement of profit goal

d1+ = Overachievement of profit goal

d2- = Underachievement of units manufactured of product P

d2+ = Overachievement of units manufactured of product P

d3- = Underachievement of units manufactured of product Q

d3+ = Overachievement of units manufactured of product Q

Introducing slack variables S1 and S2, we get,

Minimize Z = P1 d2- + P2d1- + P3d3-

Subject to

6x1 + 3x2 + S1â‰¤ 90

3x1 + 6x2 +S2â‰¤ 72

120x1 + 90x2 + d1- - d1+ = 1950

x1 + d2- - d2+ = 13

x2 + d3- - d3+ = 5

x1, x2, d1- , d1+, d2-, d2+, d3-, d3+, S1,S2â‰¥ 0

Initial basic feasible solution is given by

x1 = x2 = d1+ = d2+ = d3+ = 0, d1- =1950, d2- = 13, d3- = 5, S1 = 90,S2 = 72

Following the same steps as in the above example, modified simplex method is shown in the following table:

## B

## cB

## cj

## 0

## 0

## P2

## 0

## P1

## 0

## P3

## 0

## 0

## 0

## Minimum ratio (xB/xi)

## xB

## x1

## x2

## d1-

## d1+

## d2-

## d2+

## d3-

## d3+

## S1

## S2

## S1

## 0

90

6

3

0

0

0

0

0

0

1

0

90/6

## S2

## 0

72

3

6

0

0

0

0

0

0

0

1

72/3

## d1-

## P2

1950

120

90

1

-1

0

0

0

0

0

0

1950/120

## d2-

## P1

13

1

0

0

0

1

-1

0

0

0

0

13â†’

## d3-

## P3

5

0

1

0

0

0

0

1

-1

0

0

## -

## cj-Zj

## P3

5

0

1

0

0

0

0

0

1

0

0

## P2

1950

-120

-90

0

-1

0

0

0

0

0

0

## P1

13

-1

## â†‘

0

0

0

0

1

0

0

0

0

## S1

## 0

12

0

3

0

0

-6

6

0

0

1

0

2â†’

## S2

## 0

33

0

6

0

0

-3

3

0

0

0

1

11

## d1-

## P2

390

0

90

1

-1

-120

120

0

0

0

0

390/120

## x1

## 0

13

1

0

0

0

1

-1

0

0

0

0

## -

## d3-

## P3

5

0

1

0

0

0

0

1

-1

0

0

## -

## cj-Zj

## P3

5

0

-1

0

0

0

0

0

1

0

0

## P2

390

0

-90

0

1

120

-120

0

0

0

0

## P1

0

0

0

0

0

1

0

## â†‘

0

0

0

0

## d2+

## 0

2

0

## Â½

0

0

-1

1

0

0

1/6

0

4â†’

## S2

## 0

27

0

9/2

0

0

0

0

0

0

-1/2

1

6

## d1-

## P2

150

0

30

1

-1

0

0

0

0

-20

0

5

## x1

## 0

15

1

## Â½

0

0

0

0

0

0

1/6

0

30

## d3-

## P3

5

0

1

0

0

0

0

1

-1

0

0

5

## cj-Zj

## P3

5

0

-1

0

0

0

0

0

1

0

0

## P2

150

0

-30

0

1

0

0

0

0

20

0

## P1

0

0

0

## â†‘

0

0

1

0

0

0

0

0

## x2

## 0

4

0

1

0

0

-2

2

0

0

1/3

0

## S2

## 0

9

0

0

0

0

9

-9

0

0

-2

1

## d1-

## P2

30

0

0

1

-1

60

-60

0

0

-30

0

## x1

## 0

13

1

0

0

0

1

-1

0

0

0

0

## d3-

## P3

1

0

0

0

0

2

-2

1

-1

-1/3

0

## cj-Zj

## P3

5

0

0

0

0

-2

2

0

1

1/3

0

## P2

150

0

0

0

1

-60

60

0

0

30

0

## P1

0

0

0

0

0

1

0

0

0

0

0

Note that in the above table, there is negative entry -60 in P2 row. But it cannot be further improved as there is positive entry below this element in P1 row. Similarly, no further improvement of P3 is possible because of positive entry in P1 row. Thus, P2 and P3 cannot be improved further. Hence the optimal solution of the above goal programming problem is

x1 = 13, x2 = 4, d1+ = 0, d1- =30, d2+ = 0, d2- = 0, d3+ = 0, d3- = 1, S1 = 0, S2 = 9

Therefore, production goal of product P is achieved fully placed at priority P1. The second priority goal P2 is missed by Rs. 30 and the last priority goal P3 is missed by 1 unit of product Q.

## TEST YOUR UNDERSTANDING

## MULTIPLE COICE QUESTIONS

For applying a GP approach, decision-maker must

Set targets for each of the goals

Assign pre-emptive priority to each goal

Assume that linearity exists in the use of resources to achieve goals

All of these

In GP problem, goals are assigned priorities such that

Goals may not have equal priority

Higher priority goals must be achieved before lower priority goals

Goals of greatest importance are given lowest priority

None of these.

In a GP problem, deviational variables must satisfy the following characteristics:

di+ - di- = 0

di+ + di- = 0

di- * di+ =0

none of these

## State whether the following statements are T (True) or F (False)

Goal programming begins with the most important goal and continues until the achievement of less important goal.

Both the deviational variables related to a goal - one of underachievement and the other of overachievement - can together assume positive values.

In the simplex method of goal programming the variable to enter the solution-mix is selected with highest priority row and most positive cj - zj value in it.

The multiple goals specified in a goal programming problem are usually conflicting and incommensurate.

One of the deviational variables in a goal programming problem for a goal constraint must be equal to zero.

Penalty weights may be assigned to deviational variables related to different goals, in accordance with the relative importance to the decision-maker.

The inequalities related to system constraints are rigid and those with goal constraints are flexible.

## EXERCISE

What is goal programming? State the difference between linear programming and goal programming?

Why goal programming is cited as a satisficing based technique?

What are deviational variables? How do they differ from decision variables in traditional LP problems?

Differentiate between weighted and preemptive goal programming problems.

A company manufactures two types of products, A and B. The products are produced in three distinct steps: milling, grinding and fuming. The schedule for machine hours and availability of each type are as follows:

A (hour) B (hour) Availability (hour/month)

Milling 3 2 1700

Grinding 2 1 1400

Fuming 1 3 1600

Profit contribution of each type of product A and B is Rs. 600 and Rs. 800, respectively. The company has three desirable goals of equal importance:

To minimize the idle time in grinding

To minimize the idle time in fuming

Making a monthly profit of Rs. 1,00,000.

Set up the problem as a goal programming model and find the optimal solution.

A manufacturing firm produces two types of products A and B. According to past experience, production of either A or B requires an average of 1 hour in the plant. Because of limited market, it is reported that maximum number of products that can be sold of type A and B are 240 and 300 respectively in a month. The plant has a normal production capacity of 400 hours in a month. The net profit from the sale of product A is Rs. 800 and from B is Rs. 400. The manager of the firm set the following goals arranged in the order of importance:

P1: Avoid underutilization of normal production capacity

P2: Sell maximum possible units of products A and B. The manager has twice as much desire to achieve sales for product A as for product B

P3: Minimize the overtime operation of the plant as much as possible.

Formulate the problem as the preemptive goal programming problem and solve it by graphical method.

A carpenter produces two products, table and chairs. Each product must process through two departments, A and B. Department A consists of 30 hours of production capacity per day, and department B consists of 60 hours of production capacity per day. Each unit of a table requires 2 hours in department A and 6 hours in department B. Each unit of chair requires 3 hours in department A and 4 hours in department B. Management wants to determine the daily product mix considering the following priority levels:

P1: Avoid underachievement of total production of table and chairs for 10 units.

P2: Avoid underachievement of production for 7 units of chairs.

P3: Avoid underachievement of production for 8 units of tables.

Formulate the above problem as a goal programming model and solve it using graphical method.

A small paint company manufactures two types of paint, latex and enamel. In production, the company uses 10 hours of labor to produce 100 gallons of latex and 15 hours of labor to produce 100 gallons of enamel. The company has 40 hours of labor available each week, without hiring outside help or requiring overtime. Furthermore, each paint generates a profit at the rate of $1.00 per gallon. The company has the following objectives listed in decreasing priority:

avoid the use of overtime

achieve a weekly profit of $1000

produce at least 700 gallons of enamel paint each week

Formulate the above problem as a preemptive goal programming problem and solve it using modified simplex method.

10. An electronics company produces two types of television sets, color and black-and-white.Â The production of a color set requires 10 hours of skilled and 100 hours of unskilled labor.Â The production of a black-and-white set requires 5 hours of skilled and 150 hours of unskilled labor.Â The company has 100 hours of skilled labor and 1,500 hours of unskilled labor normally available per month for the production of television sets.Â The maximum number black-and-white and color sets that can be sold each month are 45 and 70, respectively.Â The profit margin from the sale of a color set is $20, whereas it is $15 from a black-and-white set.Â The company has set the following goals:

1. Avoid the over utilization of skilled labor since it is hard to obtain in the labor market.

2. Minimize the under utilization of unskilled labor.

3. Meet the demand as much as possible.

4. Limit over utilization of unskilled labor to 100 hours.

Formulate the above as a weighted goal programming problem and solve using modified simplex method.