CHAPTER TWO

INTRODUCTION TO LINEAR
PRGRAMMING

Mulugeta K. (PhD)
Department of Management
2.1. Introduction to Linear Programming (LP)

• In 1947, George Danztig developed the use of algebra

for determining solutions to problems that involved
the optimal allocation of scarce resources.
• The term “linear” implies that all the mathematical
relations used in the problem are linear, while
 The word “programming” means “choosing a course
of action.”
• Linear programming involves choosing a course of
action when the mathematical model of the problem
contains only linear functions.
 Cont…

• LP is a family of mathematical techniques for

determining the optimum allocation of resources and
obtaining a particular objective when there are
alternative uses of the limited or constrained
resources.
• It involves the planning of activities to obtain an
optimal result,
– i.e., a result that reaches the specified goal best
(according to the mathematical model) among all
feasible alternatives.
Components of LP Models

• There are four major components of LP models:

1. Objective and Objective Function
– The objective is the criterion by which all decisions
are evaluated.
– A single, quantifiable objective must be specified by
the decision maker, as it gives focus for problem
solving.
– The mathematical statement of the objective is called
the objective function.
– The objective of an LP will be either maximization or
minimization.
 Cont…

2. Decision variables
– Are unknown quantities to be solved for.
– For example: how much of each product should be
produced in order to obtain the highest profit?
3. Constraints
– These are the restrictions on the values of the decision
variables.
– Restrictions can arise due to limited resources such as
space, money, manpower, material, etc.
– The constraints may be in the form of equations or
inequalities (≤, ≥ or ₌).
 Cont…

– Constraints can be arranged into three groups:

1. System constraints: involve more than one decision
variable,
2. Individual constraints: involve only one variable, and
3. Non-negativity constraints: specify that no variable is
allowed to take on a negative value.
4. Parameters
– These are constants in the functional relationships.
– They are fixed values that specify the impact that one unit
of each decision variable will have on the objective and on
any constraint it pertains to as well as the numerical value
of each constraint.
What Is a Linear Programming Problem?

• A linear programming problem (LP) is an optimization

problem for which we do the following:
1. Attempt to maximize (or minimize) a linear function of
the decision variables.
2. The values of the decision variables must satisfy a set
of constraints.
3. A sign restriction, for each variable xi, specifies either
that xi must be nonnegative (xi ≥ 0) or that xi may be
unrestricted in sign.
Mathematical structure of an LP Model

Let: X1, X2, X3, ………, Xn = decision variables

Z = Objective function or linear function
Objective: Maximization of the linear function Z.
Z = c1X1 + c2X2 + c3X3 + ………+ cnXn …..Eq (1)
Subject to: the following constraints:

…..Eq (2)

where aij, bi, and cj are given constants.

Mathematical structure: Illustration

Zion furniture uses wood and labour to produce

tables and chairs. Unit profit for tables is $6, and unit
profit for chairs is $8. There are 300 board feet (bf)
of wood available, and 110 hours of labour available.
It takes 30 bf of wood and 5 hours of labour to make
a table, and 20 bf of wood and 10 hours of labour to
make a chair. Formulate the LP model that can help
the company to maximize its profit.
 Cont…

Solution:
Let:
o x1 = number of chairs manufactured
o x2 = number of tables manufactured
• The problem can be summarized in the following table
 Cont…

• The complete LP model for the Zion’s example can be

expressed as follows.

• It adheres to the previous mathematical structure.

Question: Add the following mixture constraint to our example
and revise the model.
The number of chairs must be at least 4 times the number of
tables.
Guidelines for Model Formulation

1. Understand the problem thoroughly.

2. Describe the objective.
3. Describe each constraint.
4. Define the decision variables.
5. Write the objective in terms of the decision
variables (Objective function).
6. Write the constraints in terms of the decision
variables (Functional relationship on constraints).
Example 1: Giapetto’s Woodcarving

Giapetto’s Woodcarving, Inc., manufactures two types of wooden toys:

soldiers and trains. A soldier sells for $27 and uses $10 worth of raw
materials. Each soldier that is manufactured increases Giapetto’s variable
labour and overhead costs by $14. A train sells for $21 and uses $9 worth of
raw materials. Each train built increases Giapetto’s variable labour and
overhead costs by $10. The manufacture of wooden soldiers and trains
requires two types of skilled labour: finishing and carpentry. A soldier
requires 2 hours of finishing labour and 1 hour of carpentry labour. A train
requires 1 hour of finishing and 1 hour of carpentry labour. Each week,
Giapetto can obtain all the needed raw material but only 100 finishing hours
and 80 carpentry hours. Demand for trains is unlimited, but at most 40
soldiers are bought each week. Giapetto wants to maximize weekly profit.
Formulate a mathematical model of Giapetto’s situation that can be used
to maximize Giapetto’s weekly profit.
Solution

• In developing the Giapetto model, we explore

characteristics shared by all linear programming
problems.
 Decision Variables:
o x1 = number of soldiers produced each week
o x2 = number of trains produced each week
 Objective Function
o We note that, for the Giapetto problem, fixed costs
do not depend upon the values of x1 or x2.
 Cont…

• So, Giapetto can concentrate on maximizing its weekly profit.

Weekly Profit = (weekly revenues) - (raw material
purchase costs) - (other variable costs)
• Giapetto’s weekly profit can be expressed in terms of the
decision variables x1 and x2:
Weekly revenue = 27x1 + 21x2
Weekly raw material costs = 10x1 + 9x2
Weekly labor costs = 14x1 + 10x2

• Weekly profit = (27x1 + 21x2) – (10x1 + 9x2) – (14x1 + 10x2 )

= 3x1 + 2x2
 Cont…

• Therefore, Giapetto’s objective function is expressed

as:
Maximize z = 3x1 + 2x2
• The coefficient of an objective function variable is
called an objective function coefficient.
 Constraints
• The values of x1 and x2, for Giapetto, are limited by the
following three restrictions /constraints:
 Cont…

Constraint 1: Each week, no more than 100 hours of

finishing time may be used.
Constraint 2: Each week, no more than 80 hours of
carpentry time may be used.
Constraint 3: Because of limited demand, at most 40
soldiers should be produced.

These three constraints can be expressed mathematically by

the following equations:
Constraint 1: 2 x1 + x2 ≤ 100
Constraint 2: x1 + x2 ≤ 80

Constraint 3: x1 ≤ 40
 Cont…

• To complete the formulation of a linear programming

problem we need to decide whether NNC (sign
restriction) has to be assumed or not.
– If the decision variable can assume only
nonnegative values, the sign restriction xi ≥ 0 is
added.
– If the variable can assume both positive and
negative values, the decision variable xi is
unrestricted in sign (often abbreviated urs).
 Cont…

• The optimization model For the Giapetto problem is

summarized and stated as follows.

Max z = 3x1 + 2x2 (objective function)

Subject to (s.t.):

2 x1 + x2 ≤ 100 (finishing constraint)

x1 + x2 ≤ 80 (carpentry constraint)

x1 ≤ 40 (constraint on dd for soldiers)

x1 ≥0 (sign restriction)

x2 ≥ 0 (sign restriction)
Assumptions Of LP Models

1. Linearity (proportionality)
– The linearity requirement is that each variable has a
linear impact on the objective function and in each
constraint in which it appears.
– On the other hand, the amount of each resource
used (supplied) and its contribution to the profit (or
cost) must be proportional to the value of each
decision variable.
– For example, the contribution to the objective
function for 4 soldiers is exactly fours times the
contribution of 1 soldier.
 Cont…

2. Divisibility (Continuity)
• It is assumed that non-integer values are acceptable.
• However, if the problem requires strictly integer
solutions, integer-programming methods should be
used.
• For example, this assumption implies it is acceptable
to produce a fractional number of trains.
• The Giapetto LP does not satisfy the divisibility
assumption since a fractional soldier or train cannot
be produced.
 Cont…

3. Certainty
• Its holds that each parameter (objective function
coefficients, RHS, and technological coefficients)
are known with certainty.
4. Additivity
• The value of the objective function and the total
amount of each resource used (or supplied), must
be equal to the sum of the respective individual
contributions (profit or cost) by decision variables.
 Cont…

5. Non-negativity
• It assumes that negative values of variables are
unrealistic and, therefore, will not be considered in
any potential solutions.
• Only positive values and zero will be allowed and
the non-negativity assumption is inherent in LP
models.
• It is always expressed as xj≥0.
• The constraint used is called sign restriction /NNC.
Additional Example on LP Model Formulation

Example 2: Investment Application

An individual investor has Birr 70,000 to divide among several
investments. The alternative investments are municipal bonds
with an 8.5% return, certificates of deposits with a 10% return,
Treasury bill with a 6.5% return, and income bonds with a 13%
return. The amount of time until maturity is the same for each
alternative. However, each investment alternative has a
different perceived risk to the investor; thus it is advisable to
diversify. The investor wants to know how much to invest in
each alternative in order to maximize the return. The following
guidelines have been established for diversifying the
investment and lessening the risk perceived by the investor.
 Cont…

1. No more than 20% of the total investment should be in an

income bonds.
2. The amount invested in certificates of deposit should not
exceed the amount invested in other three alternatives.
3. At least 30% of the investment should be in treasury bills
and certificates of deposits.
4. The ratio of the amount invested in municipal bonds to
the amount invested in treasury bills should not exceed
one to three.
5. The investor wants to invest the entire Birr 70,000

Required: Formulate a LP model for the problem.


0
Cont…

Solution
• The complete LPM for this problem can be summarized
as:
Solving LP Model

• The most common approaches to solve are to solve

Linear Programming Models are:
1. The Graphic Approach: a relatively straightforward
approach for determining the optimal solution to
LPPs involving only two decision variables.
2. The Algebraic Approach: The simplex method, or
iterative or step by step method, which is an
efficient method for solving LPPs involving two or
more decision variables.
Feasible Region and Optimal Solution

• The feasible region of an LP is the set of all points

satisfying all the LP’s constraints and sign restrictions.
• A feasible solution satisfies all the problem's
constraints and sign restrictions.
• An optimal solution is a feasible solution that results in
the largest possible objective function value when
maximizing (or smallest when minimizing).
• Most LPs have only one optimal solution.
• However, some LPs have no optimal solution, and
some LPs have an infinite number of solutions.
I. Graphical Solution to LP Problems

• Any LP with only two variables can be solved

graphically.
• We always label the variables x1 and x2 and the
coordinate axes the x1 and x2 axes.
• Since the Giapetto LP has two variables, it may be
solved graphically.
• The feasible region is the set of all points satisfying
the constraints:
Example [Maximization]: Giapetto

• Giapetto’s Problem Constraints

2 x 1 + x2 ≤ 100 (finishing constraint)

x1 + x 2 ≤ 80 (carpentry constraint)
x1 ≤ 40 (demand constraint)
x1, x2 ≥ 0 (non-negativity constraint)

A graph of the constraints and feasible region is shown on

the next slide.
 Cont…

• Feasible Solution for Giapetto’s Problem

 Cont…

• From figure, we see that the set of points satisfying

the Giapetto LP is bounded by the five sided polygon
IBCEF.
• Any point on or in the interior of this polygon (the
shade area) is in the feasible region.
• Set of Points which make up the feasible solution
are: I (0,0), B (0, 80), C (20, 60), E (40, 20), F (40, 0).
Finding the Optimal Solution

• We use an Extreme Point Approach to find the optimal

solution of the problem.
• Corner points which make up the feasible region will be
taken in to consideration, and the one that can maximize
the Z-value will be the optimal Solution.
Corner Points Coordinates O.F (Zmax=3x1+2x2)
I (0,0) 0
B (0,80) 160
C (20,60) 180
E (40,20) 160
F (40,0) 120
 Cont…

• We can see in the previous table that the combination of

values for each variable which yield the maximum profit
is the one indicated by point C.
• Therefore, the optimal solution to the Giapetto problem
is:
X1=20
X2=60, and
Maximum profit= $180
 Interpretation
• For Giapetto to maximize its weekly profit ($180), it
should produce 20 soldiers and 60 trains.
Binding and Nonbinding constraints

• A constraint is binding if the left-hand and right-hand side

of the constraint are equal when the optimal values of the
decision variables are substituted into the constraint.
– In the Giapetto LP, the finishing and carpentry
constraints are binding.
• A constraint is nonbinding if the left-hand side and the
right-hand side of the constraint are unequal when the
optimal values of the decision variables are substituted
into the constraint.
– In the Giapetto LP, the demand constraint for wooden
soldiers is nonbinding since x1 = 20, x1 < 40.
Example [Minimization]: Dorian Auto

Dorian Auto manufactures luxury cars and trucks. The company

believes that its most likely customers are high-income women and
men. To reach these groups, Dorian Auto has embarked on an
ambitious TV advertising campaign and has decided to purchase 1-
minute commercial spots on two types of programs: comedy shows
and football games. Each comedy commercial is seen by 7 million
high-income women and 2 million high-income men. Each football
commercial is seen by 2 million high-income women and 12 million
high-income men. A 1-minute comedy ad costs $50,000, and a 1-
minute football ad costs $100,000. Dorian would like the
commercials to be seen by at least 28 million high-income women
and 24 million high-income men. Use linear programming to
determine how Dorian Auto can meet its advertising requirements
at minimum cost.
 Cont…

• Model Formulation:
Let: x1 = number of 1-minute comedy ads
x2 = number of 1-minute football ads
• Complete LP Model for Dorian’s Problem

Min z = 50 x1 + 100x2 (objective function (in 000’s)

s.t. 7x1 + 2x2 ≥ 28 (high-income women in millions)
2x1 + 12x2 ≥ 24 (high-income men in millions)
x1, x2 ≥ 0 (non-negativity constraints)
 Cont…

• Since Dorian wants to

X2
minimize total
14 B
advertising costs, the
optimal solution to the 12
High-income women constraint

problem is the point in

10
the feasible region with Feasible
Region
8
the smallest z value. (unbounded)

• The corner point E 6

z = 600
indicates the minimum 4 z = 320

cost, and the optimal High-income men constraint

2 E
solution is found at x1 = D
A C
3.6 and x2 = 1.4. 2 4 6 8 10 12 14 X1

• Min Cost= 310 (in 000’s)

 Cont…

• Because at point E, both the high-income women

and high-income men constraints are satisfied, both
constraints are binding.
• The Additivity Assumption was used in writing:
 total viewers = comedy ad viewers + football ad
viewers.
• Since many of the same people might view both ads,
double-counting of such people would occur
thereby violating the Additivity Assumption.
 Cont…

• If only 1-minute commercials are available, it is

unreasonable to say 3.6 comedy and 1.4 football
commercials should be purchased.
• So, the Divisibility Assumption has been violated, and
the Dorian LP should, in reality, be considered as an
integer programming problem.
• Since there is no may of knowing with certainty of
knowing how many viewers are added with each type
of commercial, the Certainty Assumption is also
violated.
• Despite these violations, analysts have used similar
models to help companies determine their optimal
media mix.
Graphical Solutions for the Special Cases of LP

1. Unboundedness: occurs when the decision variable

increases indefinitely without violating any of the
constraints.
– Reason: wrong formulation of the problem such as
incorrectly maximizing instead of minimizing and/or
errors in the given problem.
• Example:
 Cont…

2. Redundant Constraints: A constraint is redundant if

its removal would not alter the feasible solution
space.
– Constraints appear redundant when others are
more binding (restrictive) than them.
• Example:
 Cont…

3. Alternative or multiple optimal solutions

Example:
An auto company manufactures cars and trucks. Each vehicle
must be processed in the paint shop and body assembly shop.
If the paint shop were only painting trucks, then 40 per day
could be painted. If the paint shop were only painting cars,
then 60 per day could be painted. If the body shop were only
producing cars, then it could process 50 per day. If the body
shop were only producing trucks, then it could process 50 per
day. Each truck contributes $300 to profit, and each car
contributes $200 to profit. Use linear programming to
determine a daily production schedule that will maximize the
company’s profits.
 Cont…

 Let:
o x1 = number of trucks produced daily
o x2 = number of cars produced daily
• Objective Function: (in 00’s of $)
Max z = 3x1 + 2x2
• Constraints
– Constraint 1: The fraction of the day during which the
paint shop is busy is less than or equal to 1.
– Constraint 2: The fraction of the day during which the body
shop is busy is less than or equal to 1.
Cont…
 Cont…

• The complete LP model for the problem is:

• Solution: The feasible region for this LP is the shaded

region in the graph presented in the next slide bounded
by AEDF.
 Cont…

X2

60
B

• Any point (solution)

D
falling on line

50
Feasible Region

segment AE will yield

40
an optimal solution
E
of:
30
z = 100
z = 120

z =120. 20

z = 60
10

F
A C
10 20 30 40 50 X1
 Cont…

• Or, Using the Extreme-point approach:

Corner Points Coordinates O.F (Zmax=3x1+2x2)

A (40,0) 120
E (20,30) 120
D (0,50) 100
F (0,0) 0

• Points A through E along with point A and E can be

alternate optimal solutions.
 Cont…

4. Infeasibility: a condition that arises when no value of

the variables satisfy all the constraints simultaneously.
– Reason: wrong model formulation with conflicting
constraints.
• Example:
 Suppose that auto dealers require that the auto
company in the previous example produce at least 30
trucks and 20 cars. Find the optimal solution to the
new LP.
 Cont…

• The complete LP model will be:

X2

60
No Feasible Region

50
x1 >= 0

40
x2 >=0

30
20
10

10 20 30 40 50 X1

• Solution: No feasible region exists

Mix of constraints

• It is a situation where both maximization and minimization

problems may consist of constraints connected to RHS with a
mix of algebraic signs ( <, >, =).
• Example:
ABC Gasoline company operates on two resources with
different production capacity. Refinery A can produce 4000
gallon/ day of super unleaded gasoline, 2000 gallons/day of
regular unleaded gasoline and 1000 gallons/day of leaded
gasoline. On the other hand refinery B can produce 1000
gallons/day of super unleaded gasoline, 3000 gasoline/day of
regular unleaded gasoline and 4000 gallons/day of leaded
gasoline.
 Cont…

The company has made a contract with an automobile

manufacturer to provide 24,000 gallon of super unleaded,
42,000 gallons of regular unleaded and 36,000 gallon of
leaded gasoline. The automobile manufacturer wants the
delivery not more than 14 days. The cost of running refinery A
is $1500 and B is 24,000 per day.
• Required?
How many days should each refinery operate for the gasoline
company to meet its contractual agreement with the
minimum cost.
 Cont…

• LP Model for ABC Gasoline Company is:

Z Min =1500X1+2400X2
S.t:
4X1+X2 ≥ 24
2X1+3X2 ≥ 42
X1+4X2 ≥ 36
X1≤14
X2 ≤ 14
X1, X2 ≥ 0

• Solve the Model Graphically, and interpret the result.

54