CONCEPT OF GOAL PROGRAMMING

CIT907 ADVANCED OPERATION RESEARCH

95 7.0 REFERENCES/FURTHER READING

Asoke Kumar Bhunia, Laxminarayan Sahoo, Ali Akbar Shaikh (2019), Advanced Optimization and Operations Research, Springer Optimization and Its Applications, 153 https://doi.org/10.1007/978-32-9967-2_1

Merigó, José M; Yang, Jian-Bo (2017). "A bibliometric analysis of operations research and management science". Omega - International Journal of Management Science. 73: 37–48.

doi:10.1016/j.omega.2016.12.004. ISSN 0305-0483

Frederick S. Hillier & Gerald J. Lieberman (2014), Introduction to Operations Research, McGraw-Hill: Boston MA; 10th Edition

The Institute for Operations Research and the Management Sciences (INFORMS), https://www.informs.org/

Taha, Hamdy A. (2016), "Operations Research: An Introduction", Pearson, 10th Edition Saul I. Gass, Arjang A. Assad, An Annotated Timeline of Operations Research: An Informal History. New York, Kluwer Academic Publishers, 2005.

International Federation of Operational Research Societies https://www.ifors.org/

Saul I. Gass (Editor), Arjang A. Assad (2011), Profiles in Operations Research: Pioneers and Innovators. Springer

.

CIT907 ADVANCED OPERATION RESEARCH

96

Since the LPP can measure the objective function in one dimension only (i.e. it can either maximise profit or minimise costs) a new mathematical techniques has been developed to find solution to problems with multiple, often conflicting objectives. In this technique, all goals of the management are considered in the objective function and only business environment constraints are treated as constraints. Also, goals are set to

be satisfied to the best fit solution „as close as possible‟ level and not for optimal or best found solutions. A set of solutions satisfying the business environment conditions/constraints are provided in order of priority and effort is made to minimise the deviation from the set goals.

There have been very few applications for goal programming techniques in business and industry. The first effort to use this technique was made by Charnes Cooper who used it for advertisement and manpower planning problems.

Though goal programming has flexibility and can have applications as wide-ranging as that of linear programming, yet its potential has not been realised and not much work done in this field. It is useful in the practical problems and it is more realistic in its approach. Some of the areas where goal programming may be used are:

Marketing Management- marketing management is a very vast discipline in which the organisation could have many objectives that are conflicting (i.e. it is possible to achieve one at the cost of the other). Goals could be:

i. maximising market share

ii. maximising profit margin/item sold iii. minimise advertising costs

iv. optimise brand image.

Production Planning and Control (PPC). There are lots of contradicting requirements in production like:

i. minimise operation time

ii. minimise cost

iii. maximise quality of the product iv. optimise resource utilization.

Inventory Management- conflicting goals could be : i. minimise stock outs

ii. minimise storage cost

iii. minimise lead time (Just-in-Time).

It must be noted that goal programming aims at satisfaction of the goals set by the management or decision-makers. Exact achievement of the objectives is not aimed. The technique attempts to do so in order of priority of the objectives as decided by the management. Often, it is a complex task for decision-makers to decide the priority and accept the solution as satisfactory.

2.0 INTENDED LEARNING OUTCOMES

At the end of this unit, you should be able to:

explain the concept of goal programming

use multiple goals as goal programming problems

CIT907 ADVANCED OPERATION RESEARCH

97 formulate goal programming model

state how to solve goal programming problems graphically.

3.0 MAIN CONTENT

3.1 Formulation of Goal Programming Mathematical Model

As seen earlier, the first and the most important step in the solution of a problem is the ability of the management to convert the problem into a mathematical model which represents the problem. Here a number of assumptions has to be made first, while trying to convert the real life situation into a scientific model written on a piece of paper. Except the problem is very clearly conceptualised by the experts it will not represent the real world problems and any solution will give misleading results. It is a complex process finding the solution, using the model is again a very time-consuming, complicated and cumbersome process. However, the computers and their software can help decision-makers a great deal in this.

Steps involved in formulation of the goal programming model are as follows.

Step 1 Identification of decision-variable and constraints. This is the vital step in finding a solution to the problem. Clear identification of all the decision variables and environment conditions which are the constraints in the equations on the RHS have to be determined. RHS constraints are:

(i) Available resources as specified in the problem Goals specified by the decision-maker

Step 2 Formulation of objectives or goals of the problem. As discussed earlier, an organisation could have more than one objective.

Some of these could be:

Maximise profits.

Maximise gain of share-holders.

Maximise machine utilisation Maximise manpower utilisation

Maximise mean time between failures (MTBF) of machines

Minimise operation costs

Minimise operational time of the machine

Minimise overall time of production of the production Optimise use of raw material

Satisfy social responsibilities Maximise quality of the product

Satisfy many government rules and other legal requirements.

Step 3 Formulation of the constraints. The constraints of the problem must be formulated. A constraint represents relationship between different variables in a problem. It could be the relationship between the decision-variables and the goals or objectives selected to be satisfied in order of priority.

Step 4 Identify least important and redundant goals. This is done to remove them from the problem which helps in simplifying the

CIT907 ADVANCED OPERATION RESEARCH

98

problem to some extent. This is again based on the judgment of the management.

Step 5 Establishing the objective function. Objective function has to be established based on the goals selected by the decision makers.

Priority weight factors have to be allotted to deviational variables. The goal process models can be mathematically represented as

Minimise Objective function Z = ^mWi di d1 i 1

Subject to the constraints n

aij X j di di bi where i 1, 2, 3, ...n and x j , di , di , i, j 0

1

where j is the decision variable.

W_i = is the weight of goal i

di = degree of underachievement of goal i d_i = degree of overachievement of goal i

As seen earlier, goal programming attempts at full or partial achievement of goals in order of priority. Low priority goals are considered only after the high priority goals have been considered. This is very difficult to decide as contribution of a particular goal to the overall well-being of an organisation is very difficult to determine. The concept of underachievement of goals or overachievement of goals may

be understood as the most important. Selected goal continues to remain in the problem unless and until the achievement of a lower priority goal would cause the management to fail to achieve a higher priority goal.

Example 1

ABC Ltd produces two types of product P-1 and P–2 using common production facilities which are considered scare resources by the company. The scarce production facilities are in the two departments of Machining and Assembling. The company is in a position to sell whatever number it produces as their brand enjoys the market confidence. However, the production capacity is limited because of the availability of the scarce resources.

The company wants to set a goal maximum daily profit, because of its other problems and constraints and would be satisfied with #2000 daily profit. The details of processing time, capacities of each of the departments and unit profit combinations of products P₁ and P₂ are given in the table below:

Type of Time to process each product Profit

product (Hours) contribution per

unit

P1 3 1 200

P₂ 2 1 300

Time available 100 50

(hours) per day

CIT907 ADVANCED OPERATION RESEARCH

99

The company wishes to know the product mix that would get them the desired profit of #2000 per day. Formulate the problem as goal programming model.

Solution

Let X₁ be the number of units of P₁ to be produced Let X₂ be the number of units of P₂ to be produced

di = the amount by which actual profit will fall short of #2000/day di+

= the amount by which actual profit will exceed the desired profit of

# 2000/day

Minimise Z = di di

Subject to 3 X₁ + 2 X₂ < 100 (Machine hours constraint) X1 + X2 < 50 (Assembly hours constraint)

and 200 X₁ + 300 X₂ + d_i d_i = 2000. (Desired profit goal constraint)

where X1, X2, di di > 0

Example 2

The manufacturing plant of an electronic firm produces two types of television sets, both colour and black and white. According to the past experience, production of either a colour or a black and white set 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, because of the limited sales opportunity, the maximum number of colour and black-and-white sets that can be sold are 24 and 30 respectively for the week. The gross margin from the sale of a colour set is # 80, whereas it is #40 from the black-and-white set.

The chairman of the company has set the following goals arranged in the order of their importance to the organisation.

First, he wants to avoid an under-utilisation of normal production capacity (on lay offs of production workers).

Second, he wants to sell as many television sets as possible. Since the gross margin from the sale of colour television set is twice the amount from a black-and –white, he has twice as much desire to achieve sale for colour sets as for black-and-white sets.

Third, the chairman wants to minimise the overtime operation of the plant as much as possible. Formulate this as a goal programming problem and solve it.

Solution

Let X1 and X2 denote the number of colour TV sets and number of black-and-white TV sets for production respectively.

The production capacity of both types of TV sets is given by

X₁ + X₂ + d_i d_i = 40 d_i and d_i are deviational variables.

The sale capacity of two types of TV sets is given by X1

+ d 2 d 2 = 24

X2 + d3 d3 = 30

CIT907 ADVANCED OPERATION RESEARCH

100

where d 2 d 2 are the deviational variables representing under-achievements of sales towards goals and d₃ d₃ represent

deviational variables of over-achievement of sales goals.

(iii) Let P₁ and P₂ be the priority of the goals, complete mathematical formulation of goal programming is

Minimise Z = p1d1 + 2 p1 d2

+ p2d3

+ p2d1+

Subject to the constraints

X₁ + X₂ + d_i d_i = 40, X₁ + d ₂ d ₂ = 24

X₃ + d₃ d₃ = 30 and X₁ , X₂, d₁ , d₂ , d₃ d₁ , d₂ , d₃ 0 3.2 Graphical Method of Solving Goal Programming Problems

The graphical method used in goal programming is quite similar to the one used in linear programming problems. The only difference is that in LPP only one objective function is achieved either maximisation or minimisation with only one goal. In goal programming, there are a number of goals and total deviation from these goals is required to be minimised.

The minimisation of deviations is done in order of priority.

The following procedure is followed:

Step 1 Formulation of linear goal programming mathematical model Step 2 Construction of graph of all goals in relation with the decision

variables. For each goal write an equation with positive and negative deviation variables and set the equation to zero. For the entire goal equation, two points are selected arbitrarily and joined with straight lines. Positive deviations are indicated with

→ arrow and negative deviation by ← arrow for each goal.

Step 3 Determine the goal line of that goal which has the highest priority. Identify the feasible region (area) with respect to the goal with highest priority.

Step 4 Proceed to the next highest priority and determine the best solutions space with respect to these goals corresponding to this priority.

Step 5 Determine the optimal solution Example 3

A manufacturer produces two types of products A and B. The plant has production capacity of 500 hours a month. The production of product A or B on an average requires one hour in the plant. The number of products A and B sold every month and the net profit from the sales of these products is given in the following table.

Type of product Number sold in a Net Profit month

A 250

B 300

The MD of the company has set the following goals which are arranged in order of priority:

P1 No under-utilisation of plant production capacity

CIT907 ADVANCED OPERATION RESEARCH

101

P₂ Sell maximum possible numbers of products A and B. The MD has twice as much desire to sell product A as for product B, because the net profit from the sale of product A is twice the amount from that of product B.

P3 Minimise overtime operation of the plant

Formulate the above as a goal programming problem and solve it

Solution

Let X1 and X2 be the number of products of A and B. Since overtime operations are not allowed.

where d₁^- = under-utilisation of production capacity constraint d₁

= overtime production operation capacity variable

Since goal is the maximisation of sales, hence positive deviation will not appear in constraints related with sales.

Then X + d ^- = 250

1 2

where d 2

= under achievement of sales goal for product A d3

= under achievement of sales goal for product B

Now, the goal programming mathematical model can be written as Minimise Z = p1 d1 +2p2 d 2 + p2 d3 + p3 d1

Subject o he constraints

X₁ + X₂ + d₁ - d ₂ = 500 X₁ + d ₂ = 250

X₂ + d3 = 300

and X1 , X2 , d1 , d3 , d1 > 0

All the goal constraints can be plotted on the graph as shown below:

_ _ _

300 ^_ E B

200 ^_ 100 ^_d3 F

0 _

I I I I I I I I

0 100

d 250

400 500 600 200 300

CIT907 ADVANCED OPERATION RESEARCH

102 Example 4

Use dynamic programming to show that

Z = p1 log p1 + p2 log p2 + ….. + pn log pn

subject to the constraints

p₁ + p₂ + ………+ p_n = 1 and p₁ > 0 (j = 1, 2, …..n) is minimum when p1 = p2 = ….. = pn = ¹n

Solution

The constraints p1 + p2 ……..+ pn = 1 indicates that the problem is to divide unity into n parts (p_1, p₂ ….. pn) so that



^pi log p_i (i = 1, 2,….

i n) minimum

Let the minimum sum of pi log pi = fn (1) Stage 1 For n = 1, we have

f₁ (1) = min (p₁ log p₁) = 1 log 1 0 < x < 1 as at this sage 1 is divided only into p1 = 1 part

Stage 2 For n =2. 1 is divided into tow part p1 and p2 in such a manner that p₁ + p₂ = 1

If p1 = x then p2 = 1 – x, Hence f2 (1) = min {p1 log p1 + p2 log p2)

0 < x ≤1

= min {x log x +(1 – x) log (1 – x)}

0 <x ≤1

= min {x log x +f₁ (1 – x )}

0  x 1

In general

f_n (1) = min [p₁ log p₁ + p₂ log p₂ + ….. + p_n log p_n]

0  x 1



log x  f n1



1 x



= min

0  x 1

For n = 2 (stage 2)

The function x log x + (1 – x) log (1 – x) is minimum at x =

1

2

^{so as to}

satisfy 0 < x < 1



1



1 1  1   1  1 1 

f ₂ log 1   log1   2  log 

2 2 2

 2   2   2 

For n = 3 (stage 3)

f₃ (1) = min [x log x + f₂ (1 – x)]

0  x 1

 1  x  1  x

= min x log x  2   log 

0  x 1   2   2

Minimum value of this function is attainable at x < 1



_



x =

1

3

so as to satisfy 0 <

f



1



1 log 1  2 1 log 1 3 1 log 1

3  

3 3 ^{ }

3 3 3 3

CIT907 ADVANCED OPERATION RESEARCH

103

In general, for n stages problems f



1



 n



1 log 1 

n  

n n 

Optimal policy p₁ = p₂ = ….. = p_n = ¹ for n = m + 1, the recursive

n

equation is f_m-1 (1) = min [x log x + f_m (1 – x)]

0  x 1



1  x





 1  x

= min x log x  m  log 

m

0  x 1 

 m ^

 

1 1  1 1 

 log  m log 

m 

1 m  1 m  1 m  1

 1 1 

m  1 log 

m  1 m  1

Minimum of the function is attainable at x = 1

m 1 The required optimal policy is

1 1 1  0



1



1 1 

 , ,...  with f n  n  log 

n n

n

 n   n 

CIT907 ADVANCED OPERATION RESEARCH

104 Example 5

Use dynamic programming to solve the problem Minimise Z = y12

y22

y32

subject to the constraints y1 + y2 + y3 > 15 and y1 , y2 , y3 > 0

Solution. It is a three stage problem with decision variables being y₁, y₂ and y₃ S3 = y1 + y2 + y3 > 15

S₂ = y₁ + y₂ = S₃ – y S = y₁ = S₂ y₂

This can be put in the following functional relationship

f₁



S₁



min y₁² 



S₂  y₂



²

0  y1  S1



^y1

2  y₂²



^



^y2

2  f₁



S₁

 

f₁



S₁



min min

0  y₂  S ₂



^y1

2  y₂²



^{0 y2  S 2}

f

2



S₂



 min

0  y2  S 2



^y12  y₂² 



^y32



y32  f₂



S₂

 

f

3



S₃



 min  min

0  y3  S3 0  y3  S3

f₂



S₂



 min y1 ² 



S₂  y₂ ²



^as y1 ^{2 }



S₂  y ² ²

0  y₂  S ₂

Since the function [ y₂² +



S₂y₂



² ] can attain its minimum value at y = ¹ S so that to satisfy.

2 2 ²

0  y₂  S₂ f₂



S₂



  1



^{2  1}



^{2 1 2}

min   S₂    S₂  S₂   S₂

2 2

0  y S

2

 2   

2 2 2 

f₃



S₃



 min 



^y3  f₂



S₂

 

^ min 

y

1

3 



S₃

 y

3





S

3 2

0  y₃   ^{0 y3  S3}  

2

1 ^{2 }

or f₃



15



 min  ^y

3





15  y₃



_

2

0 y₃  S₃ ^{ }

Since S₃ (y₁ + y₂ + y₃) > 15

The minimum value of function

 

y₃² 1



15  y₃



²

 

occurs at y₃ = 5 2

 

f₃(15) = 

5

^{2  1}



15  5



^{2 } = 75

2

 

S₃ = 5 S₂ = S₃ - y₃ = 15 - 5 = 10 S₁ = S₂ - y₂ = 10 – 5 = 5

CIT907 ADVANCED OPERATION RESEARCH

105 Hence the optimal policy is (5, 10, 5) with f3(15) = 75

4.0 CONCLUSION

In this unit, we discussed dynamic programming and graphical methods of solving goal programming problem. Also, some mathematical model were formulated and solved.

5.0 SUMMARY

In this unit, we discussed dynamic programming and graphical methods of solving goal programming problem. Also, some mathematical model were formulated and solved.

6.0 SELF-ASSESSMENT EXERCISES

A manufacturer produces two types of products A and B. The plant has production capacity of 500 hours a month. Production of product A or B on average requires one hour in the plant. The number of products A and B sold every month and the net profit from the sales of these products is given in the following table.

Type of Number sold in a Net Profit product month

A 150

B 200

The MD of the company has set the following goals which are arranged in order of priority P1 No under-utilisation of plant production capacity

P2 Sell maximum possible numbers of products A and B. The MD has twice as much desire to sell product A as for product B, because the net profit from the sale of product A is twice the amount from that of product B.

P3 Minimise overtime operation of the plant

Formulate the above as a goal programming problem and solve it

Use dynamic programming to solve the problem

Minimise Z = y₁² y₂² y₃² subject to the constraints y₁ + y₂ + y₃ >

10 and y1, y2 , y3 > 0 7.0 REFERENCES/FURTHER READING

Asoke Kumar Bhunia, Laxminarayan Sahoo, Ali Akbar Shaikh (2019), Advanced Optimization and Operations Research, Springer Optimization and Its Applications, 153 https://doi.org/10.1007/978-32-9967-2_1

Merigó, José M; Yang, Jian-Bo (2017). "A bibliometric analysis of operations research and management science". Omega - International Journal of Management Science. 73: 37–48.

doi:10.1016/j.omega.2016.12.004. ISSN 0305-0483

Frederick S. Hillier & Gerald J. Lieberman (2014), Introduction to Operations Research, McGraw-Hill: Boston MA; 10th Edition

The Institute for Operations Research and the Management Sciences (INFORMS), https://www.informs.org/

Taha, Hamdy A. (2016), "Operations Research: An Introduction", Pearson, 10th Edition

CIT907 ADVANCED OPERATION RESEARCH

106

Saul I. Gass, Arjang A. Assad, An Annotated Timeline of Operations Research: An Informal History. New York, Kluwer Academic Publishers, 2005.

International Federation of Operational Research Societies https://www.ifors.org/

Saul I. Gass (Editor), Arjang A. Assad (2011), Profiles in Operations Research: Pioneers and Innovators. Springer

In document ADVANCED OPERATIONS RESEARCH (Page 95-106)