15 Goal Programming

After studying this chapter, the reader will be able to

• discuss the formulation of goal programming (GP)
• understand single-goal objective programming
• explain the multiple-goal model with equal or no priorities
• get acquainted with the GP algorithm or modified simplex method
• understand and explain the multiple-goal model with priorities and
weights
• provide a graphical solution for a GP problem

15.1 INTRODUCTION
Goal programming (GP) is an extension of linear programming (LP). It is a multi-
objective programming that intends to minimize the deviations between the actual
results and the desired goals and works according to the priorities assigned to
different goals. This model was first presented by Charnes and Copper as an
extension to the LP model without naming it as the GP model.

15.2 FORMULATION OF GOAL PROGRAMMING

If there are m goals and p resource constraints in a problem, then the most general
GP model can be written in the following form:
m
Min Z = ∑
Σ pi (wi+ di+ + w−i di− )
ii==11
nn

Subject to ∑
Σ aij xj + di− − d i+ = bi , i = 1, ..., m
j=1
j =1
n
∑
Σ aij xj ≤ = ≥ bi, i = m + 1, ..., m + p
j=1
j =1

where xj, j = 1, …, n are n decision variables, pi, i = 1, …, m are the priorities

associated with m goals, di− = deviational variable representing underachievement in
the ith goal, di+ = deviational variable representing overachievement in the ith
 GOAL PROGRAMMING 405

goal, wi+ is the relative weight of di+ in the ith priority level, and wi− is the relative
weight of di− in the ith priority level.
Here priorities pi’s are not assigned any values, but this is simply a convenient
way of providing more importance to one goal over another. Thus, if pi is given
more importance than pj, it means pi > npj however large n may be. We also indicate
this by writing pi >>> pj. At the same priority level pi, the deviational variables
di− and di+ may be provided different weights in the objective function. The
person formulating the GP model has to analyse each of the m goals carefully. If
overachievements are acceptable, di+ (called surplus variable in LP) is removed
from the objective function and if underachievement is acceptable, then di− (called
slack variable in LP formulation) is removed from the objective function. If the
exact achievement of the ith goal is desired, then both di− and di+ must be included
in the objective function and ranked according to their order of priority. In this
manner, the higher priority goals are considered before the lower priority goals.

15.3 BASIC TERMINOLOGIES

Before providing a detailed description of GP, we shall discuss certain necessary
preliminaries:
Goal equation A goal expressed in the form of an equation by using variables
di− (underachievement) and di+ (overachievement) is called the goal equation. The
variables di− and di+ are called the deviational variables.
Priorities in GP model The coefficients of deviational variables in the objective
function of the GP are called priorities. The magnitude of priorities reflects the
order of preference of a goal.
Multiple goals with priorities and weights A multiple-goal model in which
different weights are employed in one or more priority levels, to distinguish the
goal preference, are called multiple goals with priorities and weights.
GP simplex method The modified version of simplex method used in solving a
GP problem is called the GP simplex method.
Resource or structure constraints The constraints that are not directly related
to the goals of the problem are called structural or resource constraints. Deviational
variables are not incorporated into these constraints. These constraints have to be
satisfied by the solution.
Trade-off function The objective function of a GP is called the trade-off
function. This may be linear or non-linear.

Example 15.1 A company manufactures two products A and B. These products are
manufactured in two different departments D1 and D2 of the company. While product
A requires 2h in department D1 and 3h in department D2, product B requires 2h
in department D1 and 5h in department D2. The production time is limited to 60h in
department D1 and 80h in department D2. The profit per unit of products A and B is `3
and `6 respectively. To maximize profit, the company has set a high profit goal of `1500.
The management of the company desires to produce at least 30 units of each product.
406 OPERATIONS RESEARCH

The management considers this second goal to be as equally important as the first goal of
maximizing the profit. Formulate the given problem as a GP problem.
Solution
Profit constraint: Let x1 be the units of product A to be produced and x2 be the units of
product B to be produced. Therefore, the profit goal is 3x1 + 6x2 ≈ 1500 and the profit goal
equation is 3x1 + 6x2 + d1− − d1+ = 1500, where d1− = amount of underachievement of profit
and d1+ = amount of overachievement of profit.
Resource or structure constraints:
2 x1 + 3x2 ≤ 60 or 2 x1 + 3x2 + x3 = 60
2 x1 + 5 x2 ≤ 80 or 2 x1 + 5 x2 + x4 = 80

Production constraint: Since at least 30 units of products A and B have to be produced, the
production constraints can be written as follows:
x1 + d 2− − d 2+ = 30 and x 2 + d 3− − d 3+ = 30
Here x1 ≥ 30 and x2 ≥ 30. Thus d 2− and d3− are the deviational variables and have to be
included in the objective function.
Objective function: With priority-ranked goals, one objective function has to be formulated
for each goal in the GP. The management has given equal priority to all the goals. Thus, the
complete GP model is formulated as follows:

Min Z = d 1− + d 2− + d −3 (Objective function)

Subject to 3x1 + 6 x2 + d 1− − d 1+ = 1500 (Goal 1)
x1 + d 2− − d +2 = 30 (Goal 2)
x2 + d3− − d3+ = 30 (Goal 3)
2x 1 + 3x 2 + x 3 = 60
Resource constraints
2x 1 + 5x 2 + x 4 = 80
x1, x2 , x3 , x4 , d1−, d1+, d 2−, d 2+, d3−, d3+ ≥ 0; x3 , x4 are slack variables and d1+, d 2+, and d3+ are
overachievements for goals 1, 2, and 3 respectively. Here overachievements d1+, d 2+, and d3+
in goals 1, 2, and 3 are desired and hence have not been included in the objective function.

15.4 SINGLE-GOAL MODELS

To solve single-goal programming problems, we use the standard simplex
method. To have a clear understanding of the GP–LP relationship, we consider the
following example.

Example 15.2 A manufacturer produces

Product→ Product
two models P1 and P2 which have to go Available
through two machines M1 and M2 before the Machine↓ P1 P2 time (h)
final output is obtained. The machine time M1 2 3 60
available, time required by each product on
M2 2 5 80
two machines, and the profit on each product
is given in the adjacent table: Profit 3 5 –
 GOAL PROGRAMMING 407

Determine how the manufacturer can earn maximum profit. Further, if the manufacturer sets
the target of achieving a maximum profit of `200, then formulate the problem in GP model.
Solution The LP formulation of the problem is as follows
Max Z = 3x1 + 5x 2
Subject to 2x 1 + 3x 2 ≤ 60
(15.1)
2x 1 + 5x 2 ≤ 80
x 1, x 2 ≥ 0
where x1 units of product P1 are produced and x2 units of product P2 are produced.
The manufacturer’s objective is to determine x1 and x2 so that the profit is maximum. If
we solve the problem using the simplex method, the maximum profit Z = 95, for x1 = 15
and x2 = 10.
Now in Eq. (15.1), if the manufacturer fixes a target of achieving a maximum profit of
`200, then the GP formulation of the problem can be given as follows:
Min Z = d1− or Max −Z = −d1−
Subject to 2x 1 + 3x 2 ≤ 60
2x 1 + 5x 2 ≤ 80 (15.2)
3x1 + 5 x2 + d 1− − d 1+ = 200
x 1, x 2 , d 1−, d 1+ ≥ 0.
Here xi’s are the decision variables and di− (underachievement) and di+ (overachievement)
are the deviational variables. Taking x3 and x4 as slack variables added to constraints of
Eq. (15.2), we solve the GP models as follows:

Costs → 0 0 0 0 0 −1
Table Basic
no. CB variables XB x1 x2 d1+ −
x3 x4 +
d1− Min ratio
1 0 x3 60 2 3 0 1 0 0 60/3 = 20
0 x4 80 2 5 0 0 1 0 80/5 = 16→
−1 d1− 200 3 5 −1 0 0 1 200/5 = 40
c j − Zj 3 5↑ −1 0 0 0 –
2 0 x3 12 4/5 0 0 1 −3/5 0 60/4 = 15→
0 x2 16 2/5 1 0 0 1/5 0 16/(2/5) = 40
−1 d1− 120 1 0 −1 0 −1 1 120
cj − Zj 1↑ 0 −1 0 −1 0 –
3 0 x1 15 1 0 0 5/4 −3/4 0
0 x2 10 0 1 0 −1/2 1/2 0 –
0 d1− 105 0 0 −1 −5/4 −1/4 0
c j − Zj 0 0 −1 −5/4 −1/4 0 –

Therefore, the optimum solution is x1 = 15, x2 = 10, d1−1 = 105. In this problem, 105 is the under-
achievement of the maximum profit goal of `200. Thus the actual profit is 200 − 105 = `95,
which is the same as the maximum profit obtained using the LP model. Therefore in a single-
goal programming problem, the solution derived is same as that obtained using the LP model
of the problem.
408 OPERATIONS RESEARCH

The main difference between the LP model shown in Eq. (15.1) and the GP model in
Eq. (15.2) is the objective function. In GP model, we include deviational variable d1− in the
objective function. Further, while the problem in the LP model may be either maximization
or minimization, it is always a minimization problem in GP model where we minimize the
sum (weighted) of deviations. In addition, the profit objective function in Eq. (15.1) has
been considered as the goal equation in Eq. (15.2).

15.5 GP ALGORITHM OR MODIFIED SIMPLEX METHOD

The standard simplex method can easily be used to solve GP problems. This is
accomplished by assigning values to the priority coefficients in the objective
function of GP formulation, so that the values reflect the same order of relationship
as the priorities.
In Chapter 4, we have already described in detail the steps and procedure of the
simplex method. Here we shall describe how the simplex method algorithm can be
modified to solve a GP problem. The following steps are used in a GP algorithm:
Step 1 Construct the initial modified simplex table similar to that of a simplex
table with the only difference in the (cj − Zj) row, where it is split into as many
different goal rows as the number of priorities assigned.
Step 2 Check for optimality. If there is no positive entry in the (cj − Zj) row for
the highest priority row, say pk, then the priority pk goal has been met; go to Step 6,
otherwise go to Step 3.
Step 3 Determine the new entering variable by identifying the largest positive
entry in the pk row. This fixes the column of the entering variable.
Step 4 Determine the departing variable by considering the minimum of the
ratios of the XB column entries with the corresponding non-negative entries of the
column fixed in Step 3, as is done in standard simplex method.
Step 5 Develop the new table to update the entries in the body of the table by
using elementary row operations. The new (cj − Zj) rows are computed in the same
manner as in the simplex method. The only difference is the tabular representation.
As an example, compute Zj by multiplying the values in the jth column with the
corresponding entries of the CB column. Then subtract it from cj to obtain (cj − Zj).
Break (cj − Zj) into parts, where the parts are associated with the priority levels.
To be specific, if there are three priorities p1, p2, and p3 arranged in the order of
their importance and if cj − Zj = 0 + 3p3 − 4p1 + 0, then in the jth column we split it as
(c j − Z j ) row : p1 − 4 ( p1 >> p2 >> p3 )
p2 0
p3 3
In this way continue Steps 3, 4, and 5 until optimality conditions are satisfied for
the highest priority pk row and then go to Step 6.
Step 6 Evaluate the next lower priority level row pk + 1 (pk + 1 << pk) by identifying
the largest positive coefficient for which there are no negative coefficients at a
 GOAL PROGRAMMING 409

higher priority in the same column. If a tie exists in the values of the coefficients
that determine the entering variable, break it arbitrarily.
Note The lower priority goals must not be satisfied at the expense of higher priority goals.

15.6 MULTIPLE-GOAL MODELS

In this section, we shall discuss the following three types of the multiple-goal
model:
1. Multiple-goal models with equal or no priority
2. Multiple-goal models with priority
3. Multiple-goal models with priority and weights
In general, multiple-goal models with priority and weights are considered
most useful in day-to-day life.

15.6.1 Multiple-goal Models with Equal or No Priorities

The multiple-goal with equal-priority model of GP is not of much practical value
when compared to GP models with different priorities attached to different goals.
Nevertheless, we have illustrated it in Example 15.3 to have a better understanding
of the concept of priorities and weights.

Example 15.3 A firm is manufacturing B1 and B2 types of bags; while B1 bags are
ordinary, B2 are luxury bags. These bags are processed through two machines M1 and M2 to
give them a final form. B1 requires 20 h of machine M1 and 10 h of machine M2. B2 requires
10 h each of machines M1 and M2. The time available on machines M1 and M2 is 60 h and
40 h respectively. The profit earned per bag is `40 and `80 on bags B1 and B2 respectively.
The firm wants to maximize profit to as much as `1000. In addition to the profit goal, the
firm wants to produce at least two bags of each type and considers this second goal as
equally important as the first profit goal. Formulate and solve the given problem as a GP
problem. Interpret the solution.
Solution
Formulation: Let x1 be the number of type B1 bags manufactured and x2 be the number of
type B2 bags manufactured.
Resource constraints: Time taken on machine M1 to produce x1 and x2 = 20x1 + 10x2. Thus
20x1 + 10x2 ≤ 60.
Similarly for machine M2, we have 10x1 + 10x2 ≤ 40.
Profit constraints: 40 x1 + 80 x2 + d1− − d1+ = 1000
Production constraints: As x1 ≥ 2, x2 ≥ 2, the production constraints can be written as
x1 + d 2− − d 2+ = 2, x2 + d3− − d3+ = 2.
As equal priority (no priority) has been given to all the goals, the objective function is
to minimize the sum of deviational: Min Z = d1− + d 2− + d3−.
Thus, the complete GP model can be described as follows:
Min Z = d1− + d 2− + d3−
Subject to 20x1 + 10x2 ≤ 60
10x1 + 10x2 ≤ 40
(Contd on page 411)
 410 OPERATIONS RESEARCH
Table 15.1 Solution to problem in Example 15.3
cj → 0 0 −1 0 −1 0 −1 0 0 0
Table Basic
−−
no. CB variable XB x1 x2 d1− + −
d1+ −− ++
d 2−− ++
d 2++ −−− +++
d−3− ++ −
d 3+ x3 x4 Min ratio
1 0 x3 60 20 10 0 0 0 0 0 0 1 0 60/10 = 6
0 x4 40 10 10 0 0 0 0 0 0 0 1 40/10 = 4
−1 d1− 1000 40 80 1 −1 0 0 0 0 0 0 1000/80
−1 d 2− 2 1 0 0 0 1 −1 0 0 0 0 …
−1 d 3− 2 0 1 0 0 0 0 1 −1 0 0 2/1 = 2 min
cj − Zj 41 81↑ 0 −1 0 −1 0 −1 0 0 –
2 0 x3 40 20 0 0 0 0 0 −10 10 1 0 40/10 = 4
0 x4 20 10 0 0 0 0 0 −10 10 0 1 20/10 = 2 min
−1 d1− 840 40 0 1 −1 0 0 −80 80 0 0 840/80
−1 d 2− 2 1 0 0 0 1 −1 0 0 0 0 …
0 x2 2 0 1 0 0 0 0 1 −1 0 0 …
cj − Zj 41 0 0 −1 0 −1 −81 80↑ 0 0 –
3 0 x3 20 10 0 0 0 0 0 0 0 1 −1
0 d 3+ 2 1 0 0 0 0 0 −1 1 0 1/10
−1 d1− 680 −40 0 1 1 0 0 0 0 0 −8 –
−1 d 2− 2 1 0 0 0 1 −1 0 0 0 0
0 x2 4 1 1 0 0 0 0 0 0 0 1/10
cj − Zj −39 0 0 −1 0 −1 −1 0 0 −8 –
 GOAL PROGRAMMING 411

40 x1 + 80 x2 + d1− − d 1+ = 1000 (Goal 1)

x1 + d 2− − d 2+ = 2 (Goal 2)
x 2 + d 3− − d 3+ = 2 (Goal 3)
x1, x2 , d1−, d1+ , d −2 , d +2 , d −3 , d +3 ≥ 0. d1−, d 2−, d3− are the underachievements d1+, d 2+, d3+ are the
overachievements of goals 1, 2, and 3 respectively. The canonical form is as follows:

Min Z = d 1− + d 2− + d 3− or Max − Z = − d 1− − d 2− − d −3
Subject to 20 x1 + 10 x 2 + x 3 = 60
10 x1 + 10 x2 + x4 = 40
40 x1 + 80 x2 + d 1− − d 1+ = 1000 (Goal 1)
− +
x1 + 0 x2 + d 2 − d 2 = 2
. (Goal 2)
0.x1 + x2 + d −3 − d +3 = 2 (Goal 3)
x1, x2, x3, d1−, d1+ , d −2 , d +2 , d −3 , d +3 ≥ 0. x3, x4 are the slack variables, d1−, d 2−, d3− are the
underachievements, d1+, d 2+, d3+ are the overachievements of goals 1, 2, and 3 respectively.
To solve the problem we use the modified simplex method (Table 15.1). The solution is
x1 = 0, x2 = 4, x3 = 20, x4 = 0, d1− = 680, d1+ = 0, d 2− = 2, d 2+ = 0, d3− = 0, d3+ = 2 and Z = 682.

Interpretation of solution obtained Here d1− = 680 implies that the profit goal of `1000
is underachieved by `680. Thus the actual profit is `1000 − `680 = `320. Further d 2− = 2
indicates that the production goal of type B1 bags was missed by 2. Further d3+ = 2 indicates
that the production goal of type B2 bags was overachieved by 2.

15.6.2 Multiple-goal Models with Priorities

In Section 15.6.1, we have considered a GP problem with no priorities (having
equal priorities). To solve those problems, we used the standard simplex
method. In this section, we shall consider multiple-goal programming problems
with priorities. To solve these problems, we shall use the modified simplex
method.

Example 15.4 A manufacturer produces

Available
two models 1 and 2 of a product that first Activity Model 1 Model 2 time (h)
requires machining and then assembling.
The time available for machining and Machining 2 3 60
assembling is respectively 60 h and 80 h. Assembling 2 5 80
The time required (h) and profit per piece
Profit 3 6 –
of a model are given as per the adjacent
table:
Now, the manufacturer, who is planning to increase the manufacturer production to earn
more profit, decides to use overtime to maximize profit. Assume that he sets the following
priorities for the attainment of the goal: (a) first priority p1 is to limit the total overtime in
assembly to 30 h and (b) second priority p2 is set to earn maximum profit with an arbitrary
high goal of `200. Formulate and solve the problem using GP.
 412 OPERATIONS RESEARCH
Table 15.2 Solution to problem in Example 15.4
cj → 0 0 0 0 0 −p2 0 0 −p1
− + − + −− ++ − −− + ++−− − ++ + −− ++ −− ++ −
Table no. CB Basic variable XB x1 x2 x3 d 1 d 1 d 2 d 2 d 3 d 2+ − +
Min ratio
1 0 x3 60 2 3 1 0 0 0 0 0 0 60/3 = 20
0 d1− 80 2 5 0 1 −1 0 0 0 0 80/5 = 16 min
−P2 d 2− 200 3 6 0 0 0 1 −1 0 0 200/6 = 33.3
0 d 3− 30 0 0 0 0 1 0 0 1 −1 …
p1 0 0 0 0 0 0 0 0 −1
c j − Zj –
p2 3 6↑ 0 0 0 0 −1 0 0
2 0 x3 12 4/5 0 1 −3/5 3/5 0 0 0 0 20 min
0 x2 16 2/5 1 0 1/5 −1/5 0 0 0 0 …
−P2 d 2− 104 3/5 0 0 −6/5 6/5 1 −1 −6 6 520/6
0 d 3− 30 0 0 0 0 1 0 0 1 −1 30
p1 0 0 0 0 0 0 0 0 −1
cj − Zj –
p2 3/5 0 0 −6/5 6/5↑ 0 −1 0 0
3 0 d1+ 20 4/3 0 1 −1 1 0 0 0 0
0 x2 20 2/3 1 1/5 0 0 0 0 0 0
–
−P2 d 2− 80 −1 0 −6/5 0 0 1 −1 −6 6
0 d 3− 10 −4/3 0 −1 1 0 0 0 1 −1
p1 0 0 0 0 0 0 0 0 −1
c j − Zj –
p2 −1 0 −6/5 0 0 0 −1 0 0
 GOAL PROGRAMMING 413

Solution The GP model of the problem is formulated as follows:

Min Z = p1 d +3 + p2 d 2− or Max (− Z ) = − p1 d +3 − p2 d −2
Subject to 2x 1 + 3x 2 + x 3 = 60
2x 1 + 5x 2 + d 1− − d 1+ = 80
3x1 + 6x 2 + d 2− − d +2 = 200 (Goal 2)
d1+ + d 3− − d +3 = 30 (Goal 1)
x1, x2, x3, d1+, d1−, d 2+, d 2−, d 3+, d 3− ≥ 0.

The procedure for constructing the initial table is identical to that of the simplex table.
The only difference between the initial table for GP and that of the LP is the (cj − Zj) row.
For example, in Table 15.2 for x1 column,
Z 1 = (0)(2) + (0)(2) + ( − p 2 )(3) + (0)(0)
and c1 − z 1 = 0 − (0 + 0 − 3 p 2 + 0) = 3 p 2 = 0 p1 + 3p 2
Therefore in (cj − Zj) row under the x1 column, we write 0 in front of p1 and 3 in front of
p2, instead of writing a single entry 3p2.
Thus, the solution is x1 = 0, x2 = 20, x3 = 0, d1− = 0, d1+ = 20, d 2− = 80, d 2+ = 0, d 3− = 10,
+
d 3 = 0.
Here goal 1, with priority p1, is fully achieved as the overtime in assembly is exactly
30 h. Goal 2, with priority p2, is also completely achieved. The profit is exactly `200. The
results indicate that the profit goal is achieved by extending 20 h overtime in assembly.

15.6.3 Multiple-goal Models with Priorities and Weights

This is the GP model where a differential weight is used to reflect the difference in
importance within the same priority level. To illustrate let us consider Example 15.5.

Example 15.5 A company produces two types of products—A (ordinary) and B (fancy).
These products are processed through two machines M1 and M2 to get them in their final
forms. Type A requires 20 h of machine M1 and 10 h of machine M2. Type B requires 10 h
each of machine M1 and M2. The time available on machine M1 and M2 is 60 h and 40 h
respectively. The profit earned per product is `40 and `80 on bags B1 and B2 respectively.
The firm wants to maximize profit to as much as `800. The management of the company
has set the following priorities as goals to achieve.

p1 (Priority 1): Maintain the minimum production goals of 4 units of product A and
6 units of product B. Use the differential weights of 1 and 2 respectively,
since these weights reflect the ‘weighted contribution to profit’ of `40
and `80.
p2 (Priority 2): Limit the total overtime on two machines to 50 h.
p3 (Priority 3): Maximize the profit.
Formulate and solve the given problem as a GP problem.
Solution The GP model of the problem is formulated as follows:
Min Z = 1p1d 2− + 2 p1d 3− + p 2d 6+ + p3d 1−
or Max (− Z ) = −1 p1d 2− − 2 p1d −3 − p2 d 6+ − p3d 1−
(Contd on page 417)
 414 OPERATIONS RESEARCH
Table 15.3 Solution to problem in Example 15.5
cj → 0 1 −p3 0 −p1 0 −2p1 0 0 0 0 0 0 −p2
Basic Min
CB variables XB x1 x2 d1− + − − + −+ − +− −+ −+ +− −+ −+ +− −+ −+ +− + −+ − + + −
d1 d2 d 2
d 3 d 3+ d 4− d 4+ d 5− d 5+ d 6− d 6+ ratio
0 d4− 60 20 10 0 0 0 0 0 0 1 −1 0 0 0 0 6
−
0 d 5 40 10 10 0 0 0 0 0 0 0 0 1 −1 0 0 4 min →
−
−p3 d1 800 40 80 1 −1 0 0 0 0 0 0 0 0 0 0 10
−
−p1 d 2 4 1 0 0 0 1 −1 0 0 0 0 0 0 0 0 …
−
−2p1 d 3 6 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 6
−
0 d 6 50 0 0 0 0 0 0 0 0 0 1 0 1 1 −1 …
p1 1 2↑ 0 0 0 −1 0 −2 0 0 0 0 0 0
cj − Zj p2 0 0 0 0 0 0 0 0 0 0 0 0 0 −1 –
p3 40 80 0 −1 0 0 0 0 0 0 0 0 0 0
0 d4− 20 10 0 0 0 0 0 0 0 1 −1 −1 1 0 0 20
0 x2 4 1 1 0 0 0 0 0 0 0 0 1/10 −1/10 0 0 …
−
−p3 d1 480 −40 0 1 −1 0 0 0 0 0 0 −8 8 0 0 60
−
−p1 d 2 4 1 0 0 0 1 −1 0 0 0 0 0 0 0 0 …
−
−2p1 d 3 2 −1 0 0 0 0 0 1 −1 0 0 −1/10 1/10 0 0 20 →
0 d6− 50 0 0 0 0 0 0 0 0 0 1 0 1 1 −1 50
p1 −1 0 0 0 0 −1 0 −2 0 0 −1/5 1/5↑ 0 0
cj − Zj p2 0 0 0 0 0 0 0 0 0 0 0 0 0 −1 –
p3 −40 0 0 −1 0 0 0 0 0 0 −8 8 0 0

(Contd)
(Contd )

cj → 0 1 −p3 0 −p1 0 −2p1 0 0 0 0 0 0 −p2

Basic Min
CB variables XB x1 x2 d1− + − − + −+ − +− −+ −+ +− −+ −+ +− −+ −+ +− + −+ − + + −
d1 d2 d 2
d 3 d 3+ d 4− d 4+ d 5− d 5+ d 6− d 6+ ratio
0 d4− 0 20 0 0 0 0 0 −10 10 1 −1 0 0 0 0 0 (min) →
0 x2 6 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 …
−
−p3 d1 320 40 0 1 −1 0 0 −80 80 0 0 0 0 0 0 8
−
−p1 d 2 4 1 0 0 0 1 −1 0 0 0 0 0 0 0 0 4
+
0 d 5 20 −10 0 0 0 0 0 10 −10 0 0 −1 1 0 0 …
−
0 d 6 30 10 0 0 0 0 0 −10 10 0 1 1 0 1 −1 3
p1 1↑ 0 0 0 0 −1 −2 0 0 0 0 0 0 0
cj − Zj p2 0 0 0 0 0 0 0 0 0 0 0 0 0 −1 –
p3 40 0 0 −1 0 0 −80 80 0 0 0 0 0 0
0 x1 0 1 0 0 0 0 0 −1/2 1/2 1/20 −1/20 0 0 0 0 –
0 x2 6 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 –
−
−p3 d1 320 0 0 1 −1 0 0 −120 120 0 0 0 0 0 0 –
−
−p1 d 2 4 0 0 0 0 1 −1 1/2 −1/2 −1/20 1/20 0 0 0 0 80
0 d5+ 20 0 0 0 0 0 0 5 −5 1/2 −1/2 −1 1 0 0 –

GOAL PROGRAMMING
−
0 d 6 30 0 0 0 0 0 0 −5 5 −1/2 3/2 1 0 1 −1 20 min →
p1 0 0 0 0 0 −1 −3/2 −1/2 −1/20 1/20↑ 0 0 0 0
cj − Zj p2 0 0 0 0 0 0 0 0 0 0 0 0 0 −1 –
p3 0 0 0 −1 0 0 −60 60 −2 2 0 0 0 0
(Contd)

415
 416 OPERATIONS RESEARCH
(Contd )

cj → 0 1 −p3 0 −p1 0 −2p1 0 0 0 0 0 0 −p2

Basic Min
CB variables XB x1 x2 d1− + − − + −+ − +− −+ −+ +− −+ −+ +− −+ −+ +− + −+ − + + −
d1 d2 d 2
d 3 d 3+ d 4− d 4+ d 5− d 5+ d 6− d 6+ ratio
0 x1 10 1 0 0 0 0 0 −2/3 2/3 1/30 0 1/30 0 1/30 −1/30 –
0 x2 6 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 –
−
−p3 d1 320 0 0 1 −1 0 0 −120 120 0 0 0 0 0 0 –
−
−p1 d 2 3 0 0 0 0 1 −1 2/3 −2/3 −1/30 0 −1/30 0 −1/30 1/30 →
+
0 d 5 30 0 0 0 0 0 0 10/3 −10/3 1/3 0 −2/3 0 1/3 −1/3 –
−
0 d 4 20 0 0 0 0 0 0 −10/3 10/3 −1/3 1 2/3 0 2/3 −2/3 –
p1 0 0 0 0 0 −1 −11/4 −3/4 −2/30 0 −1/30 0 −1/30 1/30↑
cj − Zj p2 0 0 0 0 0 0 0 0 0 0 0 0 0 −1 –
p3 0 0 0 −1 0 0 −160/3 160/3 −11/60 – −4/3 0 −4/3 4/3
0 x1 4 1 0 0 0 1 −1 0 0 0 0 0 0 0 0 –
0 x2 6 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 –
−p3 d1− 320 0 0 1 −1 0 0 −120 120 0 0 0 0 0 0 –
−
0 d 6 90 0 0 0 0 30 −30 20 −20 −1 0 −1 0 −1 1 –
+
0 d 5 60 0 0 0 0 10 −10 10 −10 0 0 −1 0 0 0 –
−
0 d 4 80 0 0 0 0 20 −20 10 −10 −1 1 0 0 0 0 –
p1 0 0 0 0 −1 0 −41/12 −1/12 −1/30 0 0 0 0 0
cj − Zj p2 0 0 0 0 30 −30 20 −20 −1 0 −1 0 −1 0 –
p3 0 0 0 −1 −10 10 −60 60 −3/2 0 −1 0 −1 0
 GOAL PROGRAMMING 417

Subject to 20 x1 + 10 x2 + d 4− − d 4+ = 60
10 x1 + 10 x 2 + d 5− − d 5+ = 40
40 x1 + 80 x 2 + d 1− − d 1+ = 800
x 1 + d −2 − d +2 = 4
x 2 + d 3− − d +3 = 6
d 4+ + d 5+ + d 6− − d 6+ = 50
and x1, x2 , d1+, d1−, d 2+, d 2−, d3+, d3−, d 4−, d 4+, d5−, d5+, d 6−, d 6+ ≥ 0.

In Table 15.3 priority p1 is satisfied. In priority p2 row, 30 is the most positive entry in
column d 2−. However, it cannot be entered because of the negative entry above it in the
higher priority row (p1 row). The next most positive entry is 20 and is in column d 3−.
However, d 3− cannot be entered as well because of a negative entry above it in the p1
row. In the next lower priority row p3, the most positive entry, 60, is in d 3+ and 10 is in
the d 2+ column. However, these deviational variables as well cannot enter because of the
same reasons as stated for the entries in the p2 row. Thus, the optimal solution is x1 = 3,
x2 = 6, d1− = 320, d 6− = 90, d 5+ = 60, d 4+ = 80, and the remaining variables are zero, being
non-basic.

Example 15.6 A manufacturer produces

two types of products A and B. The time Product
Available
required (in h) per unit of these products Department A B time
along with profit (in `) is given in the adjacent
table. Time (in h) available in departments D1 2 3 60
D1 and D2 is respectively 60 h and 80 h. The D2 2 5 80
manufacturer wants to earn profit as much Profit 3 6 –
as `600 and sets the following priorities, in
order to achieve this.
P1 (Priority 1): Meet the total over time limit of two departments to 44 h.
P2 (Priority 2): Meet the production goals of 5 and 8 units of type A and B products
respectively. On the basis of profit from these products, attach weights 1 and 2 with the
priority P2.
P3 (Priority 3): Meet the profit goal.
Formulate and solve the given problem as a GP problem.
Solution The GP model of the problem is formulated as follows:
Min Z = p1d 6+ + 1 p2 d 2− + 2 p2 d3− + p3d1−
or Max ( − Z ) = − p1d 6+ − 1p 2d 2− − 2 p 2d 3− − p3d1−
Subject to 2x 1 + 3x 2 + d 4− − d 4+ = 60
2x 1 + 5x 2 + d 5− − d 5+ = 80
3x1 + 6x 2 + d 1− − d 1+ = 600
x1 + d 2− − d 2+ = 5
x 2 + d −3 − d +3 = 8
d 4+ + d 5+ + d 6− − d 6+ = 44
and x1, x2, d1+, d1−, d 2+, d 2−, d 3+, d 3−, d 4−, d 4+, d 5−, d 5+, d 6−, d 6+ ≥ 0.

Thus, the optimal solution is x1 = 20, x2 = 8, d 1− = 492, d 6− = 40, d 2+ = 15, d 4+ = 4, and the
remaining variables are zero, being non-basic (Table 15.4).
 418 OPERATIONS RESEARCH
Table 15.4 Solution to problem in Example 15.6
cj 0 1 −p3 0 −p2 0 −2p1 0 0 0 0 0 0 −p1
Basic
CB variables XB x1 x2 d1− d1+ d 2− d 2+ d 3− d 3+ d 4− d 4+ d 5− d 5+ d 6− d 6+ Min ratio
−
0 d 4 60 2 3 0 0 0 0 0 0 1 −1 0 0 0 0 20
−
0 d 5 80 2 5 0 0 0 0 0 0 0 0 1 −1 0 0 16
−
−p3 d 1 600 3 6 1 −1 0 0 0 0 0 0 0 0 0 0 100
−
−p2 d 2 5 1 0 0 0 1 −1 0 0 0 0 0 0 0 0 …
−
−2p2 d 3 8 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 8→
0 d6− 44 0 0 0 0 0 0 0 0 0 1 0 1 1 −1 …
p1 0 0 0 0 0 0 0 0 0 0 0 0 0 −1
cj − Zj p2 1 2↑ 0 0 0 −1 0 −2 0 0 0 0 0 0 –
p3 3 6 0 −1 0 0 0 0 0 0 0 0 0 0
0 d4− 36 2 0 0 0 0 0 −3 3 1 −1 0 0 0 0 18
−
0 d 5 40 2 0 0 0 0 0 −5 5 0 0 0 0 0 0 20
−
−p3 d 1 552 3 0 1 −1 0 0 −6 6 0 0 0 0 0 0 552/3
−p2 d 2− 5 1 0 0 0 1 −1 0 0 0 0 0 0 0 0 5 min →
0 x2 8 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 …
−
0 d 6 44 0 0 0 0 0 0 0 0 0 1 0 1 1 −1 …
p1 0 0 0 0 0 0 0 0 0 0 0 0 0 −1
cj − Zj p2 1↑ 0 0 0 0 −1 −2 0 0 0 0 0 0 0 –
p3 3 0 0 −1 0 0 −6 6 0 0 0 0 0 0
(Contd )
(Contd )

cj 0 1 −p3 0 −p2 0 −2p1 0 0 0 0 0 0 −p1

Basic
CB variables XB x1 x2 d1− d1+ d 2− d 2+ d 3− d 3+ d 4− d 4+ d 5− d 5+ d 6− d 6+ Min ratio
−
0 d 4 26 0 0 0 0 −2 2 −3 3 1 −1 0 0 0 0 26/3
−
0 d 5 30 0 0 0 0 −2 2 −5 5 0 0 0 0 0 0 6 min →
−
−p3 d1 537 0 0 1 −1 −3 3 −6 6 0 0 0 0 0 0 537/6
0 x1 5 1 0 0 0 1 −1 0 0 0 0 0 0 0 0 …
0 x2 8 0 1 0 0 0 0 1 −1 0 0 0 0 0 0 …
0 d6− 44 0 0 0 0 0 0 0 0 0 1 0 1 1 −1 …
p1 0 0 0 0 0 0 0 0 0 0 0 0 0 −1
cj − Zj p2 0 0 0 0 −1 0 −2 0 0 0 0 0 0 0 –
p3 0 0 0 −1 −3 3 −6 6↑ 0 0 0 0 0 0
0 d4− 8 0 0 0 0 −4/5 4/5 0 0 1 −1 0 0 0 0 10 →
+
0 d 3 6 0 0 0 0 −2/5 2/5 −1 1 0 0 0 0 0 0 15
−p3 d1− 501 0 0 1 −1 −3/5 3/5 0 0 0 0 0 0 0 0 …
0 x1 5 1 0 0 0 1 −1 0 0 0 0 0 0 0 0 35
0 x2 14 0 1 0 0 −2/5 2/5 0 0 0 0 0 0 0 0 …

GOAL PROGRAMMING
−
0 d 6 44 0 0 0 0 0 0 0 0 0 1 0 1 1 −1 …
p1 0 0 0 0 0 0 0 0 0 0 0 0 0 −1
cj − Zj p2 0 0 0 0 −1 0 −2 0 0 0 0 0 0 0 –
p3 0 0 0 −1 −3/5 3/5↑ 0 0 0 0 0 0 0 0

419
(Contd)
 420 OPERATIONS RESEARCH
(Contd)

cj 0 1 −p3 0 −p2 0 −2p1 0 0 0 0 0 0 −p1

Basic
CB variables XB x1 x2 d1− d1+ d 2− d 2+ d 3− d 3+ d 4− d 4+ d 5− d 5+ d 6− d 6+ Min ratio
+
0 d 2 10 0 0 0 0 −1 1 0 0 5/4 −5/4 0 0 0 0 …
0 d 3+ 2 0 0 0 0 0 0 −1 1 −1/2 1/2 0 0 0 0 4 min →
−p3 d1− 495 0 0 1 −1 0 0 0 0 −3/4 3/4 0 0 0 0 large
0 x1 15 1 0 0 0 0 0 0 0 5/4 −5/4 0 0 0 0 …
0 x2 10 0 0 0 0 0 0 0 0 −1/2 1/2 0 0 0 0 20
−
0 d 6 44 0 1 0 0 0 0 0 0 0 1 0 1 1 −1 44
p1 0 0 0 0 0 0 0 0 0 0 0 0 0 −1
cj − Zj p2 0 0 0 0 −1 0 −2 0 0 0 0 0 0 0 –
p3 0 0 0 −1 0 0 0 0 −3/4 3/4↑ 0 0 0 0
0 d 2+ 15 0 0 0 0 −1 1 −5/2 5/2 0 0 0 0 0 0 –
+
0 d 4 4 0 0 0 0 0 0 −2 2 −1 1 0 0 0 0 –
−
−p3 d 1 492 0 0 1 −1 0 0 −3/2 3/2 0 0 0 0 0 0 –
0 x1 20 1 0 0 0 0 0 −5/2 5/2 0 0 0 0 0 0 –
0 x2 8 1 0 0 0 0 0 1 −1 0 0 0 0 0 0 –
−
0 d 6 40 0 0 0 0 0 0 2 −2 1 0 0 1 1 −1 –
p1 0 0 0 0 0 0 0 0 0 0 0 0 0 −1
cj − Zj p2 0 0 0 0 −1 0 −2 0 0 0 0 0 0 0 –
p3 0 0 0 −1 0 0 3/2 −3/2 0 0 0 0 0 0
 GOAL PROGRAMMING 421

15.7 GRAPHICAL SOLUTION OF GOAL PROGRAMMING PROBLEMS

We can use the graphical approach to solve GP problems with two variables as
used for LP problems. After formulating the problem, the following procedural
steps are used for obtaining the solution:

1. Plot all resource constraints and identify the feasible region. If no resource
constraints are present in the problem, the feasible region is the area where
both x1 and x2 are ≥ 0 (the non-negative quadrants).
2. Graph the lines corresponding to the goal constraints. This can be done
by equating the deviational variables to zero in the goal constraints and
plotting the resulting equation.
3. Determine the points within the feasible region that satisfy the highest
priority goal.
4. Move to the next priority goal and determine the best solution which does
not degrade the solutions already achieved for higher priority goals.
5. Repeat step 4 until all priority levels have been investigated.

Example 15.7 A company is producing two types of items—I1 and I2. As per past
experience, the production of either item requires an average of 1h in the plant. The plant has a
normal production capacity of 300h fortnightly. The company’s marketing department reports
that the maximum number of items I1 and I2 that can be sold fortnightly are 200 and 250
respectively. The net profit from the sales of items I1 and I2 are respectively `300 and `600.
The management of the company has set the following goals arranged in the order of their
importance. Priority p1 is to avoid any underutilization of idle time of the production capacity,
priority p2 is to minimize the overtime operation of the plant as much as possible, and priority
p3 is to sell the maximum possible units of items I1 and I2. The management has twice as much
desire to achieve the same sales as I1 for I2 since the profit from the sales of item I2 is the double
of item I1 (p1 >>p2 >>p3). Formulate and solve the problem using the graphical method of GP.
Solution Let x1 and x2 be the number of units of items I1 and I2 respectively to be produced.
Plant capacity constraint equation can be written as x1 + x2 + d1− − d1+ = 300 where d1− =
underutilization of the production capacity and d1+ = overutilization of the production
capacity.
Production goal constraint equation can be written as x1 + d 2− = 200 and x2 + d 3− = 250
where d 2− = underachievement of the sales goal for item I1 and d 3− = underachievement
of the sales goal for item I2.
Here we have not considered d 2+ and d 3+ in goal constraints as the maximum units that can
be sold are 200 and 250 units for items I1 and I2 respectively.
Combining the aforementioned constraints, the GP model of the problem is formulated
as follows:
Min Z = p1d −1 + p2 d +1 + p3 (2d −3 + d 2− ) (15.3)
− +
Subject to x 1 + x 2 + d 1 − d 1 = 300 (15.4)
x1 + d −2 = 200 (15.5)
−
and x 2 + d 3 = 250 (15.6)
x1, x2, d1−, d 2−, d 3−, d1+ ≥ 0.
The first step to solve a GP problem by graphical method is to plot all the resource
(structured) constraints. Since there are no resource constraints in this problem, the feasible
422 OPERATIONS RESEARCH

region is the area where x2

x1 ≥ 0 and x2 ≥ 0, that is, –
x2 + d3 = 250
the entire first quadrant. 300
Next, sketching the goal M A N
constraints (15.4), (15.5), 250
d1+
and (15.6) by setting the d3–
deviational variables to –
200 d1 x1 + d2– = 200
zero in each constraint, the
feasible region is repre- B – +
100 x1 + x2 + d1 – d1 = 300
sented by the shaded d2–

region OCNM (Fig. 15.1). C x1

Since the underutilization O 100 200 300
and overtime operations of
production capacity are
Figure 15.1 Graphical solution
permissible, both the
− +
deviational variables d1 and d1 are indicated by arrows and are shown in Fig. 15.1. Similarly,
d 2− and d3− indicated by arrows are also shown in Fig. 15.1.
For achivement of priority p1 goal, set d1− = 0 in Eq. (15.4) to get x1 + x2 − d1+ = 300, reducing
the shaded feasible region OCNM to region ABN. For achieving the next priority p2 goal set
d1+ = 0 to get x1 + x2 = 300. The feasible region ABN is further reduced to the points on line
segment AB where the underutilization of idle time and overtime operations of production
capacity are fully achieved. In the next lower priority p3 goal, the sale constraint of item I2
is given more weightage. Therefore to demonstrate the importance of item I2 over item I1,
set d3− = 0 in Eq. (15.6) to get x2 = 250, further reducing the feasible region of points on line
segment AB to a single point A on AB. At point A, x2 = 250 along with x1 + x2 = 300 gives
x1 = 50, which when put in constraint Eq. (15.5) gives d2− = 150. Thus the solution to the GP
problem is x1 = 50, x2 = 250, d2− = 150, and d1− = d1+ = d3− = 0.

RECAPITULATION
1. Goal programming model is an extension of the LP model. A single objective GP
solution is similar to the solution obtained by the LP method.
2. In GP, assigning priorities to different goals helps achieve the most important goal
first. In other words, important or higher priority goals can be achieved at the cost of
lower priority goals.
3. Goal programming is always a minimization problem where deviations from the
established goals within the given set of constraints are minimized.
4. Deviational variables in GP are the overachievement or the underachievement of the
goals.

EXERCISES

p
Multiple-choice Q
Questions
15.1 In GP model, deviational variables added to the ith constraints must satisfy the
following conditions:
(a) di+ × d +i = 0 (c) di− × d +i = 0
− −
(b) di × d i = 0 (d) None of these
 GOAL PROGRAMMING 423

15.2 In the optimal simplex table of GP model, two or more cj − zj rows indicate
(a) unequal priority goals (c) both (a) and (b)
(b) equal priority goals (d) none of these
15.3 Goal programming model is preferred when
(a) more than one objective is set to be achieved
(b) goals are multiple and incommensurable
(c) goals are satisfied in an ordinal sequence
(d) all of these
15.4 In GP model, goals are assigned priorities such that
(a) goals of greatest importance are given less priority
(b) goals may not have equal priority
(c) higher priority goals must be achieved before lower priority goals
(d) none of these

State
State True or False
15.1 In GP, if there are two or more zj or cj − zj rows, then the problem has prioritized goals.
15.2 Goal programming is used for solving a multi-objective optimization problem that
trade-offs conflicting objectives.
15.3 A single-objective GP problem ignores the concept of a goal.
15.4 The deviational variable in the basis of the initial simplex table of a GP problem is a
negative deviational variable.

FFill
ill in the Blanks
15.1 In a GP problem, a goal constraint having and overachievement
variables is expressed as equality constraints.
15.2 In a GP formulation, each goal generates new and adds at least one new
variable to the objective function.
15.3 Goal programming is an extension of the .
15.4 In simplex method of GP, the variable to enter the solution mix is selected from the
highest priority row and cj − Zj value in it.

Review Q
Questions
15.1 What is goal programming?
15.2 Write a short note on single-goal programming.
15.3 What do you mean by multiple-goal programming with priority?
15.4 Write the procedure of modified simplex method for a GP problem.
15.5 Explain the graphical solution to a GP problem.

Numerical
Numerical Problems
15.1 A manufacturer produces two types of products A and B. The production of each A and
B requires 1h of production capacity in the workshop. The workshop of the company
has a maximum production capacity of 80h per week. On account of restriction on the
sales capacity of these products, the maximum number of A and B that can be sold is 8
and 10 per week respectively. The profit on the sale of A is `100, whereas that on B is
`60. The manager wants to determine the number of units of each product that should
be produced per week and sets the following goals to achieve with equal priority:
Goal 1: The production capacity should not exceed 80 h per week.
Goal 2: The sales of the two products A and B must be as much as possible.
Formulate the problem as a GP problem.
424 OPERATIONS RESEARCH

15.2 A company produces two products A1 and A2 which yield a per unit profit of `400 and
`300 respectively. These products require a certain raw material whose supply is limited
to 300kg per month. The raw material requirement is 1 kg per unit of each product.
Further while one unit of A1 requires 2h of processing, each unit of A2 requires 1h of
processing. The company has a normal processing capacity of 400h per month. The
marketing department has stated that under the prevailing conditions, which are likely to
continue in the foreseeable future, the maximum number of units of A1 and A2 that can
be sold each month are 100 and 250 respectively. The manager of the company has set
the following goals in the order of their importance, the priorities being pre-emptive.
Goal 1: Avoid the underutilization of normal processing.
Goal 2: Sell the maximum number of units of products A1 and A2. Since the two
products yield profit in the ratio 400:300, the company manager would
give the weightage to the sale of the products in the same ratio.
Goal 3: Minimize overtime of processing capacity.
Formulate this problem as a GP problem.
15.3 A company produces two different types of products E and F. A product mix is to be
obtained by utilizing two limited resources—labour and raw material. Each unit of E
required 2h of labour and 3 units of raw material, whereas the respective figures for F
are 4h of labour and 4 units of raw material. Every day 20 h of labour and 24 units of
raw material are available. The goals before the management according to priorities
are as follows:
(a) The profit per day should be at least `36 assuming that the profit per unit of the
products E and F is `8 and `6 respectively.
(b) Due to market conditions as well as product substitutability, the number of units
of E should be twice the number of units of F.
(c) The labour should be fully utilized.
Formulate this problem as a GP problem.
15.4 Solve the following GP problems:
(a) Min Z = p1d 1− + p 2d −2 + p3d 3−
Subject to 200 x1 + 300 x 2 + d 1− − d +1 = 4800
x 2 + d −2 − d +2 = 15
x1 + d −3 − d 3+ = 5
4 x1 + 2x 2 + x 3 = 60
4 x1 + 4 x 2 + x 4 = 70
and x1, x2, x3, x4 , d1−, d1+, d 2−, d 2+, d 3−, d 3+ ≥ 0.
(b) Min Z = p1d 1+ + p 2d −2 + p3d 3−
Subject to 4 x1 + 5x 2 + d 1− − d 1+ = 80
100 x1 + 100 x 2 + d −2 − d +2 = 2000
x 2 + d 3− − d +3 = 10
and x1, x2, d1−, d1+, d 2−, d 2+, d 3−, d 3+ ≥ 0.
15.5 Solve the following GP problems using graphical method:
(a) Min Z = p1d 1− + p2 (4d −2 + 3d −3 ) + p3d 1+
Subject to x1 + x 2 ≤ 300
2 x1 + x2 + d −1 − d 1+ = 400
x1 + d −2 = 150
 GOAL PROGRAMMING 425

x 2 + d −3 = 350
x1, x2, d1−, d1 , d 2−, d 3− ≥ 0.
+

(b) Min Z = p1d −1 + p2 d −3 + p3d −2

Subject to 2x 1 + 3x 2 ≤ 30
6x 1 + 4 x 2 ≤ 60
x 1 + x 2 + d 1− − d 1+ = 10
x1 + d −2 − d +2 = 8
x2 + d −3 − d +3 = 7
x1, x2, d1−, d1+, d 2−, d 2+, d 3−, d 3+ ≥ 0.

CONCEPTUAL PROBLEM
A manufacturing company produces two types of products A and B. The production
of A and B requires an average of 1 h in the plant. The plant has a normal production
capacity of 400 h per week. A survey revealed that the maximum number of products
A and B that can be sold in a week are 240 and 300 respectively. The net profit from
the sales of A and B are `800 and `400 respectively. The manager of the company has
set the following goals in the order of importance (p1 >> p2 >> p3), that is, pi > npi + 1,
however large n may be. Priority p1 is the avoidance of any underutilization of the
normal production capacity. Priority p2 is the sale of maximum possible units of A
and B. As the net profit from the sale of product A is double than that of product B, the
manager has twice as much desire to achieve the same sales as product B for Product A.
Priority p3 is the manager’s aim to minimize the overtime operation of the plant as much
as possible. Formulate as a GP problem and solve using the modified simplex method.
Solution The formulation of the GP problem is as follows:
Let x1 and x2 be the number of units to be produced of products A and B respectively.
The plant capacity constraint equation is x1 + x2 + d1− − d1+ = 400 where d1− =
underutilization or idle time of the normal production capacity and d1+ = overutilization
of the normal production capacity of the plant.
The production goal or sales goal constraint equations are x1 + d 2− = 240 and x2 +
d 3 = 300 where d 2− and d 3− are the underachievement of sales goals for products A and B
−

respectively. Here d 2+ and d 3+ have not been incorporated because the given sales goals
are the maximum possible volumes (sales not to exceed 240 and 300 units for products
A and B respectively).
Since profit is to be maximized, the objective as per the order of priorities given to
different goals is as follows:
Min Z = p1d 1− + p2 (2d −2 + d 3− ) + p3d1+
where in sales priority p2, double weightage has been given to the sale of product A over
the sale of product B because of double profit obtained in the sales of A.
Combining all the aforementioned goals, the GP model of the problem becomes
Min Z = p1d 1− + p2 (2d −2 + d3− ) + p3d 1+
Subject to x1 + x2 + d −1 − d 1+ = 400
x1 + d −2 = 240
x 2 + d 3− = 300
x1, x2, d1−, d 2−, d 3−, d1+ ≥ 0

(Contd)
426 OPERATIONS RESEARCH

(Contd )

cj 0 0 −p3 −p1 −2p2 −p2

Table Basic
no. CB variables XB x1 x2 d1+ d1− d 2− d 3− Min ratio
−
1 −p1 d 1 400 1 1 −1 1 0 0 400
−
−2p2 d 2
240 1 0 0 0 1 0 …
−p2 d 3
−
300 0 1 0 0 0 1 300 min →
p1 1 1↑ −1 1 0 0
cj − Zj p2 2 1 0 0 0 0
p3 0 0 −1 0 0 0
2 −p1 d1− 100 1 0 −1 1 0 −1 100 min →
−2p2 d 2− 240 1 0 0 0 1 0 240
0 x2 300 0 1 0 0 0 1 …
p1 1↑ 0 −1 0 0 −1
cj − Zj p2 2 0 0 0 0 −1
p3 0 0 −1 0 0 0
3 0 x1 100 1 0 −1 1 0 −1 …
−2p2 d 2− 140 0 0 1 −1 1 1 140 min →
0 x2 300 0 1 0 0 0 1 …
p1 0 0 0 −1 0 0
cj − Zj p2 0 0 2↑ −2 0 1
p3 0 0 −1 0 0 1
4 0 x1 240 1 0 0 0 1 0
−p3 d 2+ 140 0 0 1 −1 1 1
0 x2 300 0 1 0 0 0 1
p1 0 0 0 −1 0 0
cj − Zj p2 0 0 0 0 −2 −1
p3 0 0 0 −1 1 2

The optimal solution is x1 = 240, x2 = 300, d1+ = 140 and all the remaining variables
are zero, being non-basic. In the final (modified) simplex table, the third goal is not
completely attained as there are positive values 1 and 2 in (cj − Zj) row at p3 level in
d 2− and d 3− columns respectively. As evident, we can attain the third goal to a greater
extent if we introduce d 3− in the solution. However, there is a negative value (−1) at the
higher priority level p2 in the same column (this implies that if we introduce d 3− in the
solution, we can improve the achievement of the third goal at the expense of achieving
the second goal which is not desirable). Similarly, we cannot enter d 2− as there is a
negative value (−2) at the higher priority level p2 in the same column.