Linear Programming

for Optimization
Ade Febransyah
[email protected]
Industry insight: Vaccine logistics
Supply chain decisions →
Who, what, where, how many, when, how?
Linear Programming
Characteristics

1. Problems seek to maximize or minimize

an objective: Objective Function
2. Constraints limit the degree to which
objective can be obtained
3. Mathematical relationships are linear
Example: Ebel Mining Company
It owns two different mines that produce a given kind of ore. The
mines are located in different parts of country and hence have
different production capacities and ore quality. After crushing, the
ore is graded into three classes: high, medium, and low.

Ebel has contracted to provide its parent company’s smelting plant

with 12 tons of high-grade, 8 tons of medium-grade, and 24 tons
of low-grade ore per week. It costs Ebel $20,000 per day to run
the first mine and $ 16,000 per day to run the second.

However, in a day’s operation the first mine produces 6 tons of

high-grade, 2 tons of medium-grade, and 4 tons of low-grade,
while the second mine produces daily 2 tons of high-grade, 2 tons
of medium-grade, and 12 tons of low-grade ore. How many days a
week should each mine operated in order to fulfill Ebel’s
commitment most economically?

6
Solution Ebel Mining Co.

⚫ Number of production days per week mine 1= M1

Number of production days per week mine 2= M2
⚫ Objective Function
Min 20,000 M1 + 16,000 M2
⚫ Constraint
6 M1 + 2 M2  12 (High-grade ore requirement)
2 M1 + 2 M2  8 (Med-grade ore requirement)
4 M1 + 12 M2  24 (Low-grade ore requirement )
M1, M2  7 (Days in a week)
M1 0, M2  0

7
Graphical Solution of Linear
Programming Models

⚫ Graphical solution is limited to linear

programming models containing only two
decision variables.
⚫ Graphical methods provide visualization of
how a solution for a linear programming
problem is obtained.
Solution: Ebel Mining

M2
8
: 0.0 M1 + 1.0 M2 = 7.0
7

6
: 1.0 M1 + 0.0 M2 = 7.0

5
Payoff: 20000.0 M1 + 16000.0 M2 = 68000.0
4

3
: 6.0 M1 + 2.0 M2 = 12.0
2
: 4.0 M1 + 12.0 M2 = 24.0

1
: 2.0 M1 + 2.0 M2 = 8.0
0
M1
0 1 2 3 4 5 6 7 8

Optimal Decisions(M1,M2): ( 1.0, 3.0)

: 6.0M1 + 2.0M2 >= 12.0
: 2.0M1 + 2.0M2 >= 8.0 Optimal solution : M1= 1, M2= 3
: 4.0M1 + 12.0M2 >= 24.0
: 1.0M1 + 0.0M2 <= 7.0 Optimal Value : 68,000
: 0.0M1 + 1.0M2 <= 7.0

9
NETWORK OPTIMIZATION
Distribution Unlimited Co. Problem
⚫ The Distribution Unlimited Co. has two factories producing a product
that needs to be shipped to two warehouses
⚫ Factory 1 produces 80 units.

⚫ Factory 2 produces 70 units.

⚫ Warehouse 1 needs 60 units.

⚫ Warehouse 2 needs 90 units.

⚫ There are rail links directly from Factory 1 to Warehouse 1 and

Factory 2 to Warehouse 2.
⚫ Independent truckers are available to ship up to 50 units from each
factory to the distribution center, and then 50 units from the
distribution center to each warehouse.
Question: How many units (truckloads) should be shipped
along each shipping lane?

6-11
The Distribution Network

80 units F1 W1 60 units
produced needed

DC

70 units W2 90 units
F2
produced needed

6-12
Data for Distribution Network

6-13
A Network Model

6-14
The Optimal Solution
[80] [- 60]
(30)
F1 W1
(50) (30)
[0]

DC
(30) (50)

(40)
F2 W2
[70] [- 90]

6-15
Spreadsheet Model
B C D E F G H I J K L
3 From To Ship Capacity Unit Cost Nodes Net Flow Supply/Demand
4 F1 W1 30 $700 F1 80 = 80
5 F1 DC 50 <= 50 $300 F2 70 = 70
6 DC W1 30 <= 50 $200 DC 0 = 0
7 DC W2 50 <= 50 $400 W1 -60 = -60
8 F2 DC 30 <= 50 $400 W2 -90 = -90
9 F2 W2 40 $900
10
11 Total Cost $110,000

6-16
Typical Applications of Minimum-Cost Flow Problems

Kind of Supply Transshipment Demand

Application Nodes Nodes Nodes

Operation of a Intermediate storage

Sources of goods Customers
distribution network facilities

Solid waste Sources of solid

Processing facilities Landfill locations
management waste

Operation of a Intermediate
Vendors Processing facilities
supply network warehouses

Coordinating product Production of a Market for a specific

Plants
mixes at plants specific product product

Cash flow Sources of cash at a Short-term Needs for cash at a

management specific time investment options specific time

6-17
BINARY INTEGER
PROGRAMMING
Applications of Binary Variables
⚫ Since binary variables only provide two
choices, they are ideally suited to be the
decision variables when dealing with yes-
or-no decisions.
⚫ Examples:
⚫ Should we undertake a particular fixed
project?
⚫ Should we make a particular fixed investment?
⚫ Should we locate a facility in a particular site?

7-19
California Manufacturing Company
⚫ The California Manufacturing Company is a diversified company with
several factories and warehouses throughout California, but none
yet in Los Angeles or San Francisco.
⚫ A basic issue is whether to build a new factory in Los Angeles or San
Francisco, or perhaps even both.
⚫ Management is also considering building at most one new
warehouse, but will restrict the choice to a city where a new factory
is being built.

Question: Should the California Manufacturing Company

expand with factories and/or warehouses in Los Angeles
and/or San Francisco?

7-20
Data for California Manufacturing

Net Present Capital

Decision Yes-or-No Decision Value Required
Number Question Variable (Millions) (Millions)
1 Build a factory in Los Angeles? x1 $8 $6
2 Build a factory in San Francisco? x2 5 3
3 Build a warehouse in Los Angeles? x3 6 5
4 Build a warehouse in San Francisco? x4 4 2
Capital Available: $10 million

7-21
Binary Decision Variables

Decision Decision Possible Interpretation Interpretation

Number Variable Value of a Value of 1 of a Value of 0

Build a factory in Do not build

1 x1 0 or 1
Los Angeles this factory

Build a factory in Do not build

2 x2 0 or 1
San Francisco this factory

Build a warehouse in Do not build

3 x3 0 or 1
Los Angeles this warehouse

Build a warehouse in Do not build

4 x4 0 or 1
San Francisco this warehouse

7-22
Algebraic Formulation
Let x1 = 1 if build a factory in L.A.; 0 otherwise
x2 = 1 if build a factory in S.F.; 0 otherwise
x3 = 1 if build a warehouse in Los Angeles; 0 otherwise
x4 = 1 if build a warehouse in San Francisco; 0 otherwise

Maximize NPV = 8x1 + 5x2 + 6x3 + 4x4 ($millions)

subject to
Capital Spent: 6x1 + 3x2 + 5x3 + 2x4 ≤ 10 ($millions)
Max 1 Warehouse: x3 + x4 ≤ 1
Warehouse only if Factory: x3 ≤ x1
x4 ≤ x2
and
x1, x2, x3, x4 are binary variables.

7-23
Spreadsheet Model
B C D E F G
3 NPV ($millions) LA SF
4 Warehouse 6 4
5
6 Factory 8 5
7
8 Capital Required
9 ($millions) LA SF
10 Warehouse 5 2 Capital Capital
11 Spent Available
12 Factory 6 3 9 <= 10
13
14 Total Maximum
15 Build? LA SF Warehouses Warehouses
16 Warehouse 0 0 0 <= 1
17 <= <=
18 Factory 1 1
19
20 Total NPV ($millions) 13

7-24
Sensitivity Analysis with Solver
Table
B C D E F G
23 Capital Available Warehouse Warehouse Factory Factory Total NPV
24 ($millions) in LA? in SF? in LA? in SF? ($millions)
25 0 0 1 1 13
26 5 0 1 0 1 9
27 6 0 1 0 1 9
28 7 0 1 0 1 9
29 8 0 1 0 1 9
30 9 0 0 1 1 13
31 10 0 0 1 1 13
32 11 0 1 1 1 17
33 12 0 1 1 1 17
34 13 0 1 1 1 17
35 14 1 0 1 1 19
36 15 1 0 1 1 19

7-25
Management’s Conclusion
⚫ Management’s initial tentative decision had been to make $10
million of capital available.
⚫ With this much capital, the best plan would be to build a factory
in both Los Angeles and San Francisco, but no warehouses.
⚫ An advantage of this plan is that it only uses $9 million of this
capital, which frees up $1 million for other projects.
⚫ A heavy penalty (a reduction of $4 million in total net present
value) would be paid if the capital made available were to be
reduced below $9 million.
⚫ Increasing the capital made available by $1 million (to $11
million) would enable a substantial ($4 million) increase in the
total net present value. Management decides to do this.
⚫ With this much capital available, the best plan is to build a
factory in both cities and a warehouse in San Francisco.
7-26