IIM Mumbai

Business Intelligence
Decision Modelling
1

Goal Programming

1
 Goal Programming: Example
A client has $80,000 to invest and, as an initial strategy, would like the investment
portfolio restricted to two stocks with the details as mentioned below.
Stock Price/Share Estimated Annual Risk Index/Share
Return/Share
U.S. Oil $25 $3 0.50
Hub Properties $50 $5 0.25

Find the optimal portfolio allocation so that the portfolios satisfy the maximum total
risk index of 700 and ensure an annual return of at least $9000. Assume, the client’s
top‐priority goal is to restrict the risk.

Dr. M S Mahapatra

Goal Programming: Example

Primary Goal (Priority Level 1)
Goal 1: Find a portfolio that has a risk index of 700 or less.

Secondary Goal (Priority Level 2)

Goal 2: Find a portfolio that will provide an annual return of at least $9000.

Dr. M S Mahapatra

2
 Goal Programming: Example
Decision variables:
U = number of shares of U.S. Oil purchased
H = number of shares of Hub Properties purchased

Constraints
25U + 50H ≤ 80,000 (Fund Available)

Dr. M S Mahapatra

Goal Programming: Example

Constraints (Goal 1)
The portfolio risk index is 0.50U + 0.25H, which can be more or less than 700. So,
it can be written as
0.50U + 0.25H = 700 + 𝒅𝟏 ‐ 𝒅𝟏
where
𝒅𝟏 = the amount by which the portfolio risk index exceeds the target value of 700
𝒅𝟏 = the amount by which the portfolio risk index is less than the target value of 700

In goal programming, 𝒅𝟏 and 𝒅𝟏 are called deviation variables.

Dr. M S Mahapatra

3
 Goal Programming: Example
Constraints (Goal 2)
The annual return for the investment: 3U + 5H, which can again be more or less than
$9000. So, it can be written as
3U + 5H = 9000 + 𝒅𝟐 ‐ 𝒅𝟐
where
𝒅𝟐 = the amount by which the annual return for the portfolio is greater than the
target value of $9000
𝒅𝟐 = the amount by which the annual return for the portfolio is less than the target
value of $9000

Dr. M S Mahapatra

Goal Programming: Example

Based on the preemptive priorities as mentioned in the problem

P1 Problem
Min 𝒅𝟏
s.t.
25U + 50H ≤ 80,000 (Fund Available)
0.50U + 0.25H = 700 + 𝒅𝟏 ‐ 𝒅𝟏 Goal 1
3U + 5H = 9000 + 𝒅𝟐 ‐ 𝒅𝟐 Goal 2
U, H, 𝒅𝟏 , 𝒅𝟏 , 𝒅𝟐 , 𝒅𝟐 0

Dr. M S Mahapatra

4
 Goal Programming: Example

Dr. M S Mahapatra

Goal Programming: Example

Based on the preemptive priorities as mentioned in the problem

P2 Problem
Min 𝒅𝟐
s.t.
25U + 50H ≤ 80,000 (Fund Available)
0.50U + 0.25H = 700 + 𝒅𝟏 ‐ 𝒅𝟏 Goal 1
3U + 5H = 9000 + 𝒅𝟐 ‐ 𝒅𝟐 Goal 2
𝒅𝟏 0 Maintain achievement
U, H, 𝒅𝟏 , 𝒅𝟏 , 𝒅𝟐 , 𝒅𝟐 0

Dr. M S Mahapatra

10

5
 Goal Programming: Example

Dr. M S Mahapatra

11

Goal Programming: Example

• Thus, the goal programming solution for the Nicolo Investment problem
Recommends that the $80,000 available for investment be used to purchase
800 shares of U.S. Oil and 1200 shares of Hub Properties.

• Note that the priority level 1 goal of a portfolio risk index of 700 or less has
been achieved.

• However, the priority level 2 goal of at least a $9000 annual return is not
achievable. The annual return for the recommended portfolio is $8400.

Dr. M S Mahapatra

12

6
 Goal Programming: Example
Fairville is a small city with a population of about 20,000 residents. The annual taxation
base for real estate property is $550 million. The annual taxation bases for food and
drugs and for general sales are $35 million and $55 million, respectively. Annual local
gasoline consumption is estimated at 7.5 million gallons. The city council wants to
develop the tax rates based on four main goals:

1. Tax revenues must be at least $16 million to meet the city’s financial commitments.
2. Food and drug taxes cannot exceed 10% of all taxes collected.
3. General sales taxes cannot exceed 20% of all taxes collected.
4. Gasoline tax cannot exceed 2 cents per gallon.

Dr. M S Mahapatra

13

Goal Programming: Example

Decision Variables

𝒙𝒑 : tax rates (expressed as proportions of taxation base) for property

𝒙𝒇 : tax rates (expressed as proportions of taxation base) for food & drugs

𝒙𝒔 : tax rates (expressed as proportions of taxation base) for general sales

𝒙𝒈 : gasoline tax in cents per gallon

Dr. M S Mahapatra

14

7
 Goal Programming: Example
Constraints
550 𝒙𝒑 + 35 𝒙𝒇 + 55 𝒙𝒔 + .075 𝒙𝒈 ≥ 16 (Tax revenue)
35 𝒙𝒇 ≤ 0.1(550 𝒙𝒑 + 35 𝒙𝒇 + 55 𝒙𝒔 + .075 𝒙𝒈 ) (Food/drug tax)
55 𝒙𝒔 ≤ 0.2 (550 𝒙𝒑 + 35 𝒙𝒇 + 55 𝒙𝒔 + .075 𝒙𝒈 (General tax)
𝒙𝒈 ≤ 2 (Gasoline tax)
𝑥 ,𝑥 ,𝑥 ,𝑥 ≥0

Dr. M S Mahapatra

15

Goal Programming: Example

After simplification
550 𝒙𝒑 + 35 𝒙𝒇 + 55 𝒙𝒔 + .075 𝒙𝒈 ≥ 16
55 𝒙𝒑 ‐ 31.5 𝒙𝒇 + 5.5 𝒙𝒔 + .0075 𝒙𝒈 ≥ 0
110 𝒙𝒑 + 7 𝒙𝒇 ‐ 44 𝒙𝒔 + 0.015 𝒙𝒈 ≥ 0
𝒙𝒈 ≤ 2
𝑥 ,𝑥 ,𝑥 ,𝑥 ≥0

• Each of the inequalities of the model represents a goal that the city council
aspires to satisfy.
• A compromise solution involving these conflicting goals is derived as the best
solution.

Dr. M S Mahapatra

16

8
 Goal Programming: Example
Each inequality constraint is allowed to be violated, if necessary
550 𝒙𝒑 + 35 𝒙𝒇 + 55 𝒙𝒔 + .075 𝒙𝒈 + 𝑠 ‐ 𝑠 = 16
55 𝒙𝒑 ‐ 31.5 𝒙𝒇 + 5.5 𝒙𝒔 + .0075 𝒙𝒈 + 𝑠 ‐ 𝑠 = 0
110 𝒙𝒑 + 7 𝒙𝒇 ‐ 44 𝒙𝒔 + 0.015 𝒙𝒈 + 𝑠 − 𝑠 = 0
𝒙𝒈 + 𝑠 ‐ 𝑠 = 2
𝑥 ,𝑥 ,𝑥 ,𝑥 ≥0
𝑠 , 𝑠 ≥ 0, i=1,2,3,4

The nonnegative variables 𝑠 and 𝑠 , i = 1, 2, 3, 4, are deviational variables

representing the deviations below and above the right‐hand side of constraint i.

Dr. M S Mahapatra

17

Goal Programming: Example

The first three constraints are of the type ≥ and the fourth constraint is of the type
≤, the deviational variables 𝒔𝟏 , 𝒔𝟐 , 𝒔𝟑 and 𝒔𝟒 represent the amounts by which the
respective goals are violated.

The compromise solution seeks to satisfy the following four objectives as much as
possible
Minimize 𝐺 =𝑠
Minimize 𝐺 =𝑠
Minimize 𝐺 =𝑠
Minimize 𝐺 =𝑠

Dr. M S Mahapatra

18

9
 Goal Programming: Example
Two algorithms for solving Goal Programming
1. weights method
2. preemptive method

• In the weights method, the single objective function is the weighted sum of the
functions representing the goals of the problem.

• The preemptive method starts by prioritizing the goals in order of importance.

The model then optimizes the goals one at a time in order of priority and in a
manner that does not degrade a higher‐priority solution.

Dr. M S Mahapatra

19

The Weights Method

In a GP, n goals are combined into a single objective as follows:

Minimize z =𝑤 𝐺 + 𝑤 𝐺 + … 𝑤 𝐺

where parameters 𝒘𝒊 , i=1,2,…,n are positive weights that reflect the decision
maker’s preferences regarding the relative importance of each goal.

Dr. M S Mahapatra

20

10
 The Weights Method: Example
TopAd, a new advertising agency with 10 employees, has received a contract to
promote a new product. The agency can advertise by radio and television. The
following table gives the number of people reached daily by each type of
advertisement and the cost and labor requirements.
The contract prohibits TopAd from using more than 6 minutes of radio
advertisement. Additionally, radio and television advertisements need to reach at
least 45 million people. TopAd has a budget goal of $100,000 for the project. How
many minutes of radio and television advertisement should TopAd use?

Dr. M S Mahapatra

21

The Weights Method

𝑥 : minutes allocated to radio advertisements
𝑥 : minutes allocated to television advertisements

Minimize 𝐺 = 𝑠 (Satisfy exposure goal)

Minimize 𝐺 = 𝑠 (Satisfy budget goal)
subject to
4𝑥 +8𝑥 +𝑠 ‐𝑠 = 45 (Exposure goal)
8 𝑥 + 24𝑥 +𝑠 ‐𝑠 = 100 (Budget goal)
𝑥 +2𝑥 ≤ 10 (Personnel limit)
𝑥 ≤6 (Radio limit)
𝑥 ,𝑥 ,𝑠 ,𝑠 ,𝑠 ,𝑠 ≥0
Dr. M S Mahapatra

22

11
 The Weights Method
TopAd’s management estimates that the exposure goal is twice as important as
the budget goal. The combined objective function thus becomes

Minimize 𝑧 2𝐺 + 𝐺 = 2𝑠 + 𝑠
subject to
4𝑥 +8𝑥 +𝑠 ‐𝑠 = 45 (Exposure goal)
8 𝑥 + 24𝑥 +𝑠 ‐𝑠 = 100 (Budget goal)
𝑥 +2𝑥 ≤ 10 (Personnel limit)
𝑥 ≤6 (Radio limit)
𝑥 ,𝑥 ,𝑠 ,𝑠 ,𝑠 ,𝑠 ≥0

Dr. M S Mahapatra

23

The Weights Method

The optimum solution is z = 10, 𝒙𝟏 = 5 min, 𝒙𝟐 = 2.5 min, 𝒔𝟏 = 5 million persons,
𝒔𝟏 = 0, 𝒔𝟐 = 0 and 𝒔𝟐 = 0.

The fact that the optimum value of z is not zero indicates that at least one of the
goals is not met. Specifically, 𝒔𝟏 = 5 means that the exposure goal (of at least 45
million persons) is missed by 5 million individuals. Conversely, the budget goal (of
not exceeding $100,000) is not violated, because 𝒔𝟐 = 0.

Dr. M S Mahapatra

24

12
 The Preemptive Method
In the preemptive method, the decision maker ranks the goals of the problem in
order of importance. Given an n‐goal situation, the objectives of the problem are
written as
Minimize 𝐺 = 𝜌 (Highest priority)
.
.
Minimize 𝐺 =𝜌 (Lowest priority)

The variable 𝜌 is the component of the deviational variables, 𝑠 or ‐ 𝑠 ,

representing goal i. For example, in the TopAd model, 𝜌 = 𝑠 and 𝜌 = 𝑠

Dr. M S Mahapatra

25

The Preemptive Method: Example

Step 0: Identify the goals of the model and rank them in order of priority:
𝐺 =𝜌 >𝐺 =𝜌 >…>𝐺 =𝜌

Based on Example: 𝐺 > 𝐺

Minimize 𝐺 = 𝑠 (Satisfy exposure goal)
Minimize 𝐺 = 𝑠 (Satisfy budget goal)

Step 1: Solve LP that minimizes 𝐺 , and let 𝜌 =𝜌∗ define the corresponding
optimum value of the deviational variable ri. If i = n, stop; LPn solves

Dr. M S Mahapatra

26

13
 The Preemptive Method: Example
Step 1: Solve LP
Minimize 𝐺 = 𝑠
subject to
4𝑥 +8𝑥 +𝑠 ‐𝑠 = 45 (Exposure goal)
8 𝑥 + 24𝑥 +𝑠 ‐𝑠 = 100 (Budget goal)
𝑥 +2𝑥 ≤ 10 (Personnel limit)
𝑥 ≤6 (Radio limit)
𝑥 ,𝑥 ,𝑠 ,𝑠 ,𝑠 ,𝑠 ≥0

Dr. M S Mahapatra

27

The Preemptive Method: Example

The optimum solution is 𝑥 = 5 min, 𝑥 = 2.5 min, 𝑠 = 5 million persons, 𝑠 =0,
𝑠 =0 and 𝑠 =0.

The solution shows that the exposure goal, 𝐺 , is violated by 5 million persons.
The additional constraint to be added to the 𝐺 ‐problem is 𝑠 = 5 (or,
equivalently, 𝑠 ≤ 5)

Dr. M S Mahapatra

28

14
 The Preemptive Method: Example
Step 2: Solve LP
Minimize 𝐺 = 𝑠
subject to
4𝑥 +8𝑥 ‐𝑠 = 40 (Exposure goal)
8 𝑥 + 24𝑥 +𝑠 ‐𝑠 = 100 (Budget goal)
𝑥 +2𝑥 ≤ 10 (Personnel limit)
𝑥 ≤6 (Radio limit)
𝑥 ,𝑥 ,𝑠 ,𝑠 ,𝑠 ,𝑠 ≥0

Dr. M S Mahapatra

29

The Preemptive Method: Example

The optimum solution is 𝑥 = 5 min, 𝑥 = 2.5 min, 𝑠 = 5 million persons, 𝑠 = 0,
𝑠 = 0 and 𝑠 = 0.

Actually, the optimization of LP is not necessary for this problem, because the
optimum solution to problem G1 already yields 𝑠 = 0; that is, it is already
optimum for LP . Such computational‐saving opportunities should be exploited
during the course of implementing the preemptive method.

Dr. M S Mahapatra

30

15