Motivation Standard form Applications References

Chapter 1: Modeling with linear programming

Manuel Navarro García

IE University

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 1 / 34
Motivation Standard form Applications References

1 Motivation

2 Standard form

3 Applications

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 2 / 34
Motivation Standard form Applications References

1 Motivation

2 Standard form

3 Applications

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 3 / 34
Motivation Standard form Applications References

Linear programming example

A company produces two products, P1 and P2 , using two raw materials, M1 and M2 .
The following table provides the basic data of the problem:
Tons of Mj per ton of Maximum daily
P1 P2 availability (tons)
M1 6 4 24
M2 1 2 6
Profit/ton (e) 5 4
Further demands:
• The daily production of P2 cannot exceed that for P1 by more than 1 ton.
• The maximum daily production for P2 is 2 tons.

What is the best product mix of P1 and P2 that maximizes the total daily profit?

Any Operations Research model has three basic components:

• Decision variables that we seek to determine.

• Objective (goal) that we need to optimize (maximize or minimize).
• Constraints that the solution must satisfy.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 4 / 34
Motivation Standard form Applications References

Linear programming example

We need to determine the daily amounts of P1 and P2 produced daily. Thus, the
decision variables of the problem are

x1 = Tons produced daily of P1 ,

x2 = Tons produced daily of P2 .

By definition, x1 ≥ 0, x2 ≥ 0.

Letting z represent the total daily profit (in e), the objective of the company is

maximize z = 5x1 + 4x2

x1 , x2 ≥ 0

This problem is unbounded, i.e. letting x1 , x2 → ∞, then z → +∞. We must

incorporate some constraints so that the solution space remains bounded, and the
objective function finite.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 5 / 34
Motivation Standard form Applications References

Linear programming example

The raw material restrictions are expressed verbally as

   
Usage of raw material Maximum raw material
≤
by both products availability

The daily usage of raw materials are

Usage of M1 by both products = 6x1 + 4x2 tons/day

Usage of M2 by both products = 1x1 + 2x2 tons/day

Because the daily availabilities of M1 and M2 are limited to 24 and 6 tons, respectively,
the associated constraints are given as

6x1 + 4x2 ≤ 24 (Raw material M1 )

x1 + 2x2 ≤ 6 (Raw material M2 )

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 6 / 34
Motivation Standard form Applications References

Linear programming example

Now, we address the further demands:

• The daily production of P2 cannot exceed that for P1 by more than 1 ton. The
excess of the daily production of P2 over P1 is expressed as x2 − x1 . Then,
x2 − x1 ≤ 1

• The maximum daily production for P2 is 2 tons. Algebraically,

x2 ≤ 2
Therefore, the complete linear programming (LP) model is

maximize z = 5x1 + 4x2

subject to 6x1 + 4x2 ≤ 24,

x1 + 2x2 ≤ 6,
x2 − x1 ≤ 1,
0 ≤ x2 ≤ 2,
x1 ≥ 0.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 7 / 34
Motivation Standard form Applications References

Linear programming example

x2

maximize z = 5x1 + 4x2

subject to 6x1 + 4x2 ≤ 24,

x1 + 2x2 ≤ 6,
x2 − x1 ≤ 1,
0 ≤ x2 ≤ 2,
x1 ≥ 0.

x1

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 8 / 34
Motivation Standard form Applications References

Linear programming example

x2

maximize z = 5x1 + 4x2

subject to 6x1 + 4x2 ≤ 24,

x1 + 2x2 ≤ 6,
x2 − x1 ≤ 1,
0 ≤ x2 ≤ 2,
x1 ≥ 0.

x1

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 9 / 34
Motivation Standard form Applications References

Linear programming example

x2

maximize z = 5x1 + 4x2

subject to 6x1 + 4x2 ≤ 24,

x1 + 2x2 ≤ 6,
x2 − x1 ≤ 1,
0 ≤ x2 ≤ 2,
x1 ≥ 0.

x1

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 10 / 34
Motivation Standard form Applications References

Linear programming example

x2

maximize z = 5x1 + 4x2

subject to 6x1 + 4x2 ≤ 24,

x1 + 2x2 ≤ 6,
x2 − x1 ≤ 1,
0 ≤ x2 ≤ 2,
x1 ≥ 0.
Solution
space
x1

The feasible solution space of the problem represents the area in which all the constraints
are satisfied simultaneously.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 11 / 34
Motivation Standard form Applications References

Linear programming example

The feasible space consists of an in- x2

finite number of points, so we need (maximize z = 5x1 + 4x2 )
a systematic procedure to identify
the optimum solution.

The determination of the optimum

solution requires identifying the di-
rection in which the profit function

z = 5x1 + 4x2

z
increases (recall that we are maxi-

=
mizing z).

10

15

20
x1

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 12 / 34
Motivation Standard form Applications References

Linear programming example

x2

The optimum LP solution is always

associated with a corner point of
the solution space.

(x1 , x2 ) z
(0, 0) 0
(4, 0) 20 x1
(3, 3/2) 21
This is true even if the objective function happens to
(2, 2) 18
be parallel to a constraint:
(1, 2) 13
(0, 1) 4 • If z = 6x1 + 4x2 (parallel to one of the con-
straints), the optimum occurs at the two cor-
ners (any point in this line is an alternative op-
timum).

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 13 / 34
Motivation Standard form Applications References

1 Motivation

2 Standard form

3 Applications

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 14 / 34
Motivation Standard form Applications References

Definition of linear programming

A linear programming problem (LP) is an optimization problem so that

1 We attempt to maximize/minimize a linear function of the decision variables,
which we call objective function.
2 The values of the decision variables must satisfy a set of constraints. Each
constraint must be a linear (in)equality.
3 A sign restriction is associated with each decision variable. It specifies that xj
must be either non-negative (xj ≥ 0) or unrestricted in sign.

For example:

maximize z = 5x1 + 4x2

subject to 6x1 + 4x2 ≤ 24,

x1 + 2x2 ≤ 6,
x2 − x1 ≤ 1,
0 ≤ x2 ≤ 2,
x1 ≥ 0.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 15 / 34
Motivation Standard form Applications References

Standard form problems

A linear programming problem of the form

minimize z = c1 x1 + c2 x2 + · · · + cn xn

subject to a11 x1 + a12 x2 + · · · + a1n xn = b1 ,

..
. ,
am1 x1 + am2 x2 + · · · + amn xn = bm ,
x1 , x2 , . . . , xn ≥ 0.

is said to be in standard form.

In matrix form, we can rewrite it as follows:

minimize z = c⊤ x
x
subject to Ax = b,
x ≥ 0n ,

where A = (aij ) ∈ Rm×n , b = (b1 , . . . , bm )⊤ ∈ Rm , c = (c1 , . . . , cn )⊤ ∈ Rn are data

vectors/matrices, and x = (x1 , . . . , xn )⊤ ∈ Rn are continuous decision variables.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 16 / 34
Motivation Standard form Applications References

Interpretation: The diet problem

Suppose that there are n different foods and m different nutrients

Food 1 ··· Food n
Nutrient 1 a11 ··· a1n
.. .. ..
. . .
Nutrient m am1 ··· amn
Let
• A be the m × n matrix with entries aij , with columns Aj , j = 1, . . . , n.
• b be a vector with the requirements of an ideal diet (i.e. a specification of the
nutritional contents of an “ideal food”.)
• c be a vector with the unit cost of each food.

Intuitively, we wish to “synthesize” b by using a non-negative amount xj of each food

(resource), while minimizing the cost

X
n
cj xj .
j=1

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 17 / 34
Motivation Standard form Applications References

Expressing a LP in standard form

To express a linear programming model in standard form, we proceed as follows:

1 Remove any constant term k from the objective function by replacing

z ′ = c⊤ x + k → z = c⊤ x

2 If the problem is posed as a maximization, modeled as

maximize z ′ = c′⊤ x
x ∈ Rn
rewrite it as

minimize z = c⊤ x
x ∈ Rn

where z = z ′ and c = −c′ .

3 Remove any unconstrained variables xj by setting

xj = xj+ − xj−

where xj+ , xj− ≥ 0, and replacing xj by xj+ − xj− whenever it occurs in the
objective function and the constraints.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 18 / 34
Motivation Standard form Applications References

Expressing a LP in standard form

4 Remove any non-positive variable xj ≤ 0 by setting xj′ = −xj and replacing xj by

−xj′ wherever it occurs in the objective function and the constraints.
5 Convert any constraint of the form

ai1 x1 + ai2 x2 + · · · + ain xn ≤ bi

to an equality by adding a slack variable, xn+i , to give

ai1 x1 + ai2 x2 + · · · + ain xn + xn+i = bi , xn+i ≥ 0.

6 Convert any constraint of the form

ai1 x1 + ai2 x2 + · · · + ain xn ≥ bi

to an equality by subtracting a surplus variable, xn+i , to give

ai1 x1 + ai2 x2 + · · · + ain xn − xn+i = bi , xn+i ≥ 0.

7 Extend c to include zero elements cn+i for the slack and surplus variables xn+i . If
necessary and if desired, renumber the variables.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 19 / 34
Motivation Standard form Applications References

Exercise

Write the following problem in standard form

maximize z = 3x1 − 2x2 + 4x3

subject to 2x1 + 3x2 − 4x3 ≥ 2,

x1 + 5x2 + 3x3 ≤ −3,
x1 + 2x2 + 4x3 = 4,
x1 ≥ 0, x2 ≤ 0, x3 unrestricted.

minimize z = −3x1 − 2x2′ − 4x3+ + 4x3−

subject to 2x1 − 3x2′ − 4x3+ + 4x3− − x1s = 2,

− x1 + 5x2′ − 3x3+ + 3x3− − x2s = 3,
x1 − 2x2′ + 4x3+ − 4x3− = 4,
x1 , x2 , x3+ , x3− , x1s , x2s ≥ 0.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 20 / 34
Motivation Standard form Applications References

Canonical form problems

The canonical form provides a general method for solving linear programming models.
However, in some cases, it is useful to relax this equality to an inequality.

A minimization LP problem is in canonical form if it is written as

minimize z = c⊤ x

subject to Ax ≥ b,
x ≥ 0n .

Similarly, a maximization LP problem is in canonical form if it is written as

maximize z = c⊤ x

subject to Ax ≤ b,
x ≥ 0n .

Thanks to the previous procedure, we can transform any LP problem into another
equivalent problem in canonical or standard form.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 21 / 34
Motivation Standard form Applications References

Some basic definitions

• c is called the cost vector .

• b is called the resource vector .
• A is called the coefficient matrix .
• The set of points which satisfy the constraints,

S = {x ∈ Rn : Ax = b, x ≥ 0n }
minimize z = c⊤ x
is called feasible solution space.
subject to Ax = b, • The points from the feasible solution space S are called
x ≥ 0n . feasible solutions.
• The value of c⊤ x, where x ∈ S, is called objective func-
tion value.
• A solution x∗ is optimal if it is feasible and c⊤ x∗ ≤ c⊤ x
for every x ∈ S.
• Two LP problems P1 and P2 are said to be equivalent if
they have the same feasible solution space.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 22 / 34
Motivation Standard form Applications References

Solution types

A linear programming problem P can have the following so-

lution types:
• Optimal solution: If a feasible solution exists that min-
minimize z = c⊤ x imizes the objective function. P may have unique or
subject to Ax = b, multiple optimal solutions.
• Unbounded solution: If the objective function can be
x ≥ 0n ,
made arbitrarily small.
• No feasible solution: If there is no point that satisfies
Ax = b and x ≥ 0n . It is also said that P is infeasible.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 23 / 34
Motivation Standard form Applications References

Example: optimal solution

x2

2x1 + x2 = 6

minimize z = x1 + x2
7
x1 + x2 = 2
subject to 2x1 + x2 ≥ 6,
2x1 + 5x2 ≥ 10,
x1 , x2 ≥ 0.

2x1 + 5x2 = 10
x1

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 24 / 34
Motivation Standard form Applications References

Example: multiple optimal solutions

x2
−x1 + 2x2 = 6

2x1 + 3x2 = 18

maximize z = 2x1 + x2

subject to − x1 + 2x2 ≤ 6,
2x1 + x2 = 14
2x1 + 3x2 ≤ 18,
2x1 + x2 ≤ 14,
x1 , x2 ≥ 0.

x1

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 25 / 34
Motivation Standard form Applications References

Example: unbounded solution

x2

2x1 + x2 = 6

maximize z = x1 + x2

subject to 2x1 + x2 ≥ 6,
2x1 + 5x2 ≥ 10, x1 + x2 = 12
x1 , x2 ≥ 0.

2x1 + 5x2 = 10
x1

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 26 / 34
Motivation Standard form Applications References

Example: no feasible solutions

x2

minimize z = 3x1 + 2x2

subject to 2x1 − x2 ≤ 3, 2x1 − x2 = 3 −2x1 + x2 = −4

− 2x1 + x2 ≤ −4,
x1 , x2 ≥ 0.

x1

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 27 / 34
Motivation Standard form Applications References

1 Motivation

2 Standard form

3 Applications

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 28 / 34
Motivation Standard form Applications References

The transportation problem

• A firm produces goods at supply centers, named D1 d1

{S1 , . . . , Sm }. c11
• The supply produced at Si is si , i = 1, . . . , n.
s1 S1
• The demand is spread out at demand centers, c12 c21
named {D1 , . . . , Dm }.
• The demand at Dj is dj , j = 1, . . . , m. D2 d2
• The shipping cost per unit from Si to Dj is cij .
• The shipping cost is linear. c22 c13
s2 S2
c23
The firm’s problem is getting goods from supply cen-
ters to demand centers at minimum cost. D3 d3

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 29 / 34
Motivation Standard form Applications References

The transportation problem

• xij ≡ number of units from Si to Dj .

• We aim to minimize the total cost of the firm:

X
n X
m
minimize cij xij D1 d1
i=1 j=1 c11

• The total shipment from Si cannot exceed the s1 S1

c12 c21
supply available si :

X
m
xij ≤ si , i = 1, . . . , n. D2 d2
j=1
c22 c13
• The demand is met at each Dj : s2 S2
c23
X
n
xij ≥ dj , j = 1, . . . , m. D3 d3
i=1

• The decision variables are non-negative:

xij ≥ 0, i = 1, . . . , n, j = 1, . . . , m.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 30 / 34
Motivation Standard form Applications References

Best fitting line

Let (x1 , y1 ), . . . , (xn , yn ) a set of observations, which

is the straight line y

yb = β0 + β1 x ,

that best fit the given data? yi − ybi

We aim to minimize the sum of the absolute devia-

tions:
X
n
x
minimize |β0 + β1 xi − yi |
β0 , β 1 ∈ R i=1

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 31 / 34
Motivation Standard form Applications References

Best fitting line

The problem

X
n
minimize |β0 + β1 xi − yi |
β0 , β 1 ∈ R i=1

is equivalent to y
X
n
minimize zi
i=1
yi − ybi
subject to |β0 + β1 xi − yi | ≤ zi , i = 1, . . . , n,
zi ≥ 0, i = 1, . . . , n,
β0 , β1 ∈ R.

Finally, we can replace the inequality constraints by x

these two families of constraints:

β0 + β1 xi − yi ≤ zi
yi − β0 − β1 xi − ≤ zi

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 32 / 34
Motivation Standard form Applications References

Production planning and inventory control

• A company must deliver di units of its product at the end of each month.
• Material produced during a month can be
1 delivered either at the end of the same month,
2 stored as inventory and delivered at the end of a subsequent month.
• There is a storage cost of c1 (in e) for each unit of product held in inventory.
• The year begins with zero inventory.
• If the company produces xi units in month i and xi+1 in month i + 1, it incurs a
cost of c2 |xi+1 − xi | (in e).

We aim to minimize the production and inventory schedule costs over 12 months.

x1 x2 xi xi+1 x12

y1 y2 y3 yi yi+1 yi+2 y12 y13

1 2 i i +1 12

d1 d2 di di+1 d12

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 33 / 34
Motivation Standard form Applications References

Production planning and inventory control

• The delivered units di are constituted

by the units yi on stock plus the units
xi produced minus the units yi+1 held
• xi ≡ number of units produced in
back for deliver next month:
month i.
• yi ≡ number of units produced in yi + xi − yi+1 = di , i = 1, . . . , 12
month i − 1 and delivered at the end
of month i. • No units are stored for more than one
• y1 = 0 as the year begins with zero month:
inventory. yi ≤ di , i = 1, . . . , 12
• y13 are the product units left over after
the end of the year The optimization problem is therefore
• We aim to minimize the total cost X
12 X
12
minimize c1 yi + c2 |xi − xi−1 |
X
12 X
12 i=2 i=1

minimize c1 yi + c2 |xi − xi−1 | subject to yi + xi − yi+1 = di , i = 1, . . . , 12,

i=2 i=1 y i ≤ di , i = 1, . . . , 12,
xi ≥ 0, i = 1, . . . , 12,
yi ≥ 0, i = 2, . . . , 12.

Manuel Navarro García IE University

Chapter 1: Modeling with linear programming 34 / 34
References I

Taha, H. A. (2007). Operations research: An introduction (8th ed.). Upper Saddle River,
New Jersey: Prentice Hall.
Winston, W. L. (2004). Operations research: Applications and algorithms (4th ed.).
Thomson Learning, Inc.
Bertsimas, D., & Tsitsiklis, J. (1997). Introduction to linear optimization (1st ed.).
Athena Scientific.