MGMT90141 Business Analysis and Decision

Making
Week 4 – Linear Programming Applications
and Extensions

Dr. William Ho

Professor of Operations Management

Department of Management and Marketing
Faculty of Business and Economics
The Spot 10.036
william.ho@unimelb.edu.au
 Objectives of Lecture

• To differentiate between linear and integer

programming

• To formulate the pure integer and binary integer

programming

• To apply Lindo/Excel to solve the pure integer

and binary integer programming
 Integer Programming – 1

Elizabeth Bailey is the owner and general manager of Princess Brides,

which provides a wedding planning service. She uses radio advertising to
market her business. Two types of ads are available – those during prime
time hours and those at other times. Each prime time ad costs $390 and
reaches 8,200 people, while the off-peak ads each cost $240 and reach
5,100 people. Bailey has budgeted $1,800 per week for advertising. Based
on comments from her customers, Bailey wants to have at least 2 prime
time ads and no more than 6 off-peak ads. Elizabeth’s goal is to reach the
maximum number of audience.

(a) Formulate this as a LP.

(b) Find a good or optimal integer solution by rounding off or making an
educated guess at the answer in part (a).
(c) Solve this as an IP.
 Integer Programming – 1(a)

Step 1: Fully understand the managerial or optimization problem

being faced

Prime Off-peak Budget

Audience reached 8,200 5,100
Cost $390 $240 $1,800
Min. ads 2 -
Max. ads - 6

How many prime time and off-peak radio advertisements

should Elizabeth Bailey take to reach the maximum
number of audience, while not exceeding the budget and
following the customer comments?
 Integer Programming – 1(a)

Step 2: Define the decision variables

x1 = number of prime time radio ads to be taken per week

x2 = number of off-peak radio ads to be taken per week

Step 3: Identify the objective function

Maximize audience coverage or z = 8200x1 + 5100x2

Step 4: Identify the constraints

390x1 + 240x2 ≤ 1800 (Weekly advertising budget)

x1 ≥ 2 (Min. prime time ads/week)
x2 ≤ 6 (Max. off-peak ads/week)
x1 and x2 ≥ 0 (Non-negativity)
 Integer Programming – 1(a) and 1(b)

1(b) solutions:
x1 = 2
x2 = 4
Audience = 36,800
 Integer Programming – 1(c)

Maximize audience coverage or z = 8200x1 + 5100x2

Subject to

390x1 + 240x2 ≤ 1800 (Weekly advertising budget)

x1 ≥ 2 (Min. prime time ads/week)
x2 ≤ 6 (Max. off-peak ads/week)
x1 and x2 ≥ 0 and integer (Non-negativity and integral)
 Integer Programming – 1(c)

“GIN” defines
decision variables
as general integer.
Integer Programming – 1(c)

=SUMPRODUCT(B4:C4,B12:C12)

=SUMPRODUCT(B5:C5,B12:C12)
=B12
=C12
 Integer Programming – 1(c)

Maximize the
number of audience

Integer constraints
Min ads constraint
Budget constraint
Max ads constraints
Integer Programming – 1(c)
 Integer Programming – 1

(a) Formulate this as a LP.

(b) Find a good or optimal integer solution by rounding off or making an
educated guess at the answer in part (a).
(c) Solve this as an IP.

1(a) 1(b) 1(c)

Prime ads (x1) 2 2 4
Off-peak ads (x1) 4.25 4 1
Number of audience 38075 36800 37900
 Integer Programming – 2

To enhance its competitiveness in terms of teaching, research, and consultancy,

the decision makers of a university running the market-oriented system have
proposed 8 projects, which can be classified as 2 groups: “hardware” and
“software”. The decision makers wishes to determine which projects to be
implemented in order to maximize the total importance ratings.

“Hardware” refers to the university’s infrastructures, including

1. establishing an industrial centre;
2. establishing a self-learning centre;
3. establishing a management development centre;
4. establishing a conference theatre.

“Software” refers to the intangible effects that can be beneficial to the university,
its members, and its students. It consists of
5. establishing E-learning systems
6. establishing library information systems
7. establishing an Intranet portal
8. establishing incentive scheme
 Integer Programming – 2

University requirements:
• At least 4 projects must be established;
• At least 1 “hardware” project must be established;
• At least 1 “software” project must be established.
Remark:
• “Hardware” projects must be carried out sequentially. Similarly, “software”
projects cannot be carried out simultaneously.

Project

x1 x2 x3 x4 x5 x6 x7 x8 Limitation
Importance 0.191 0.107 0.091 0.094 0.126 0.132 0.116 0.144
Cost 71,400 57,000 50,000 35,700 4,300 2,100 6,400 28,600 150,000
Space 12,500 2,500 10,800 625 - - - - 25,000
Time – H 24 6 15 12 - - - - 36
Time – S - - - - 6 12 9 - 24
 Integer Programming – 2

Ho W, Higson HE, Dey PK (2007) An integrated multiple criteria decision

making approach for resource allocation in higher education. International
Journal of Innovation and Learning, Vol. 4(5), pp. 471–486.
 Integer Programming – 2

Step 1: Fully understand the managerial or optimization problem

being faced

Which “hardware” and “software” projects should the

university invest to reach the maximum importance
rating, while not exceeding the resource limitations and
meeting the university requirements?

Step 2: Define the decision variables

1 if project i is selected,
xi = 
0 otherwise.
 Integer Programming – 2

Step 3: Identify the objective function

Maximize importance or z = 0.191x1 + 0.107x2 + 0.091x3 + 0.094x4

+ 0.126x5 + 0.132x6 + 0.116x7 + 0.144x8

Step 4: Identify the constraints

71400x1 + 57000x2 + 50000x3 + 35700x4

+ 4300x5 + 2100x6 + 6400x7 + 28600x8 ≤ 150000 (Budget)
12500x1 + 2500x2 + 10800x3 + 625x4 ≤ 25000 (Space)
24x1 + 6x2 + 15x3 + 12x4 ≤ 36 (Time – H)
6x5 + 12x6 + 9x7 ≤ 24 (Time – S)
x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 ≥ 4 (Requirement 1)
x1 + x2 + x3 + x4 ≥ 1 (Requirement 2)
x5 + x6 + x7 + x8 ≥ 1 (Requirement 3)
xi = 0 or 1 for all i (Integral)
 Integer Programming – 2

“INT” defines
decision variables
as binary integer.
Integer Programming – 2

=SUMPRODUCT(B4:I4,B13:I13)

B19 =SUMPRODUCT(B5:I5,B13:I13)
B20 =SUMPRODUCT(B6:E6,B13:E13)
B21 =SUMPRODUCT(B7:E7,B13:E13)
B22 =SUMPRODUCT(F8:H8,F13:H13)
B23 =SUM(B13:I13)
B24 =SUM(B13:E13)
B25 =SUM(F13:I13)
 Integer Programming – 2

Maximize the
importance ratings

Binary integer constraints

Space constraint
Budget constraint Time – S constraint
Time – H constraint
Requirement 2
Requirement 1
Requirement 3
Integer Programming – 2
 Workshop 1

Quemo Chemical Company is considering three possible improvement projects

for its plant: a new catalytic converter, a new software program for controlling
operations, and expanding the warehouse used for storage. The company is
required to select no more than two of three projects regardless of the funds
available. Besides, the new catalytic converter could be purchased only if the
software was purchased also. The company aims to maximize the net present
value of the project investment. The net present value (the future value of the
project discounted back to the present time) of each of the projects, the capital
requirements, and the available funds for the next two years are:
Project Net Present Value Year 1 Year 2
Catalytic converter $25,000 $8,000 $7,000
Software $18,000 $6,000 $4,000
Warehouse expansion $32,000 $12,000 $8,000
Available funds $20,000 $16,000

Define the decision variables, formulate the integer programming model, and
apply Excel Solver to solve the problem faced by the Company.
 Workshop 1

Define the decision variables

1 if project i is funded,
xi = 
0 otherwise.

i.e., x1 = 1 if catalytic converter project is funded, 0 otherwise

x2 = 1 if software project is funded, 0 otherwise
x3 = 1 if warehouse expansion project is funded, 0 otherwise
 Workshop 1

Integer programming formulation

Maximize NPV or z = 25000x1 + 18000x2 + 32000x3

Subject to

8000x1 + 6000x2 + 12000x3 ≤ 20000 (Year 1 budget)

7000x1 + 4000x2 + 8000x3 ≤ 16000 (Year 2 budget)
x1 + x2 + x3 ≤ 2 (Max. 2 projects funded)
x2 ≥ x1 (Dependent selection)
i.e., x2 - x1 ≥ 0
xi = 0 or 1 for all i (Integral)
Workshop 1

=SUMPRODUCT(B4:B6,B12:B14)

B20 =SUMPRODUCT(C4:C6,B12:B14)
B21 =SUMPRODUCT(D4:D6,B12:B14)
B22 =SUM(B12:B14)
B23 =B13-B12
Workshop 1
Workshop 1
 Integer Programming – 3

The Martin-Beck company operates a plant in St. Louis with an annual capacity
of 30,000 units. Product is shipped to regional distribution centers located in
Boston, Atlanta, and Houston. Because of an anticipated increase in demand,
Martin-Beck plans to increase capacity by constructing a new plant in one or
more of the following cities: Detroit, Toledo, Denver, or Kansas City. The
estimated annual fixed cost and the annual capacity for the 4 proposed plants
are as follows:

Proposed Plant Annual Fixed Cost Annual Capacity

Detroit $175,000 10,000
Toledo $300,000 20,000
Denver $375,000 30,000
Kansas City $500,000 40,000
 Integer Programming – 3

The company’s long-range planning group developed forecasts of the

anticipated annual demand at the distribution centers as follows:
Distribution Center Annual Demand
Boston 30,000
Atlanta 20,000
Houston 20,000

The shipping cost per unit from each plant to each distribution center:
Distribution Center
Plant Site Boston Atlanta Houston
Detroit 5 2 3
Toledo 4 3 4
Denver 9 7 5
Kansas City 10 4 2
St. Louis 8 4 3
 Integer Programming – 3

Step 1: Fully understand the managerial or optimization problem

being faced
Which plant should the company operate AND how many products
should be shipped from plant i to distribution center j to reach the
minimum total costs, while not exceeding the plant capacity and meeting
the distribution center demand?
Distribution center j
Plant i 1 2 3 si Annual fixed cost

1 5 2 3
x11 x12 x13 10000 175000
2 4 3 4
x21 x22 x23 20000 300000
3 9 7 5
x31 x32 x33 30000 375000
4 10 4 2
x41 x42 x43 40000 500000
5 8 4 3
x51 x52 x53 30000
dj 30000 20000 20000
 Integer Programming – 3

Step 2: Define the decision variables

1 if a plant is constructed in city i,

yi = 
0 otherwise.

i.e., y1 = 1 if a plant is constructed in Detroit;

…
y4 = 1 if a plant is constructed in Kansas City.

xij = units of products to be shipped from plant i to center j

i.e., x11 = units of products to be shipped from Detroit to Boston;

…
x53 = units of products to be shipped from St. Louis to Houston.
 Integer Programming – 3

Step 3: Identify the objective function

Minimize total annual costs or z

= annual transportation costs + annual fixed cost of operating the new plant(s)

= (5x11 + 2x12 + 3x13 + 4x21 + 3x22 + 4x23 + 9x31 + 7x32 + 5x33 + 10x41 + 4x42 +
2x43 + 8x51 + 4x52 + 3x53) + (175000y1 + 300000y2 + 375000y3 + 500000y4)
 Integer Programming – 3

Step 4: Identify the constraints

x11 + x12 + x13 ≤ 10000y1 (Detroit capacity)

i.e., x11 + x12 + x13 - 10000y1 ≤ 0
x21 + x22 + x23 - 20000y2 ≤ 0 (Toledo capacity)
x31 + x32 + x33 - 30000y3 ≤ 0 (Denver capacity)
x41 + x42 + x43 - 40000y4 ≤ 0 (Kansas City capacity)
x51 + x52 + x53 ≤ 30000 (St. Louis capacity)
x11 + x21 + x31 + x41 + x51 = 30000 (Boston Demand)
x12 + x22 + x32 + x42 + x52 = 20000 (Atlanta Demand)
x13 + x23 + x33 + x43 + x53 = 20000 (Houston Demand)
xij ≥ 0 and integer; yi = 0 or 1 for all i and j (Integral)
Integer Programming – 3
Integer Programming – 3

=SUMPRODUCT(B4:D8,B18:D22)+SUMPRODUCT(F4:F7,F18:F21)

=SUM(B18:D18)

=E18-E4*F18

=SUM(D18:D22)
 Integer Programming – 3

Integer constraints

Demand constraints
Capacity constraint
of St. Louis

Binary integer Capacity constraints

constraints of new plants
Integer Programming – 3
 Workshop 2

The Company wishes to determine which warehouse to operate and how many
products should be shipped from warehouse i to customer j to reach the
minimum total costs (including transportation costs cij, and fixed costs fci), while
not exceeding the warehouse capacity si and meeting the customer demand dj.

cij
Customer, j
Warehouse, i 1 2 3 4 5 6 7 si fci
1 1 1 2 4 4 3 6 30000 30000
2 2 6 9 3 7 8 4 26000 25000
3 8 4 3 6 3 2 4 22000 20000
4 8 8 9 3 5 7 2 18000 15000
dj 12000 9000 10000 8000 6000 11000 7000

Define the decision variables, formulate the integer programming model, and
apply Excel Solver to solve the problem faced by the Company.
 Workshop 2

Define the decision variables

1 if warehouse i is selected,
yi = 
0 otherwise.

xij = units of products to be shipped from warehouse i to customer j

 Workshop 2

Integer programming formulation

Minimize total costs or z

= total transportation costs + total fixed costs of operating the warehouse(s)

= (x11 + x12 + 2x13 + 4x14 + 4x15 + 3x16 + 6x17

+ 2x21 + 6x22 + 9x23 + 3x24 + 7x25 + 8x26 + 4x27
+ 8x31 + 4x32 + 3x33 + 6x34 + 3x35 + 2x36 + 4x37
+ 8x41 + 8x42 + 9x43 + 3x44 + 5x45 + 7x46 + 2x47)
+ (30000y1 + 25000y2 + 20000y3 + 15000y4)
 Workshop 2

Integer programming formulation (continue)

Subject to

x11 + x12 + x13 + x14 + x15 + x16 + x17 - 30000y1 ≤ 0 (Warehouse 1 capacity)
x21 + x22 + x23 + x24 + x25 + x26 + x27 - 26000y2 ≤ 0 (Warehouse 2 capacity)
x31 + x32 + x33 + x34 + x35 + x36 + x37 - 22000y3 ≤ 0 (Warehouse 3 capacity)
x41 + x42 + x43 + x44 + x45 + x46 + x47 - 18000y4 ≤ 0 (Warehouse 4 capacity)
x11 + x21 + x31 + x41 = 12000 (Customer 1 demand)
x12 + x22 + x32 + x42 = 9000 (Customer 2 demand)
x13 + x23 + x33 + x43 = 10000 (Customer 3 demand)
x14 + x24 + x34 + x44 = 8000 (Customer 4 demand)
x15 + x25 + x35 + x45 = 6000 (Customer 5 demand)
x16 + x26 + x36 + x46 = 11000 (Customer 6 demand)
x17 + x27 + x37 + x47 = 7000 (Customer 7 demand)
xij ≥ 0 and integer; yi = 0 or 1 for all i and j (Integral)
 Workshop 2

C12 =SUMPRODUCT(B4:H7,B17:H20)+SUMPRODUCT(J4:J7,J17:J20)

L17 =I17-I4*J17
L18 =I18-I5*J18
L19 =I19-I6*J19
L20 =I20-I7*J20
 Workshop 2

Integer constraints
Binary integer
constraints
Demand constraints
Capacity constraints
Workshop 2
 Workshop 2

Ho W, Lee CKM, Ho GTS (2008) Optimization of facility location-allocation

problem in customer-driven supply chain. Operations Management
Research, Vol. 1(1), pp. 69–79.

Ho W, Emrouznejad A (2009) Multi-criteria logistics distribution network

design using SAS/OR. Expert Systems with Applications, Vol. 36(3), pp.
7288–7298.
 Summary of Lecture

• Differentiated between linear and integer

programming

• Formulated the pure integer and binary integer

programming

• Applied Lindo/Excel to solve the pure integer and

binary integer programming
 Announcements

1) Readings
– Chapter 7 (An Introduction to Management Science:
Quantitative Approaches to Decision Making)

2) Useful websites
– http://www.lindo.com/
– http://office.microsoft.com/en-au/excel-help/load-the-
solver-add-in-HP010342660.aspx (Office 2010)
© Copyright The University of Melbourne 2013