CHAPTER 3: LINEAR PROGRAMMING
Introduction
Many management decisions involve trying to make the
most effective use of an organizations resources.
Resources typically include machinery, labor, money, time,
warehouse space, or raw materials.
Linear programming (LP) is a widely used mathematical
technique designed to help managers in planning and
decision making relative to resource allocation.
Despite the name, linear programming, and the more
general category of techniques called mathematical
programming, have very little to do with computer
programming.
Programming refers to modeling and solving a problem
2
mathematically.
Linear Programming Model
General form of Linear programming model:
Maximize / Minimize z = f(x1, x2 ,, xn)
Subject to
gi(x1, x2 , , xn)
{}
bi
i =1,,m
xj 0, j = 1,,n
3
Model Components
xj are called decision variables, things that you
control and you want to determine their values.
gi(x1, x2 ,, xn)
{}
bi are called structural
( functional or technological) constraints
xj 0 are nonnegativity constraints
f(x1, x2 ,, xn) is the objective function
Example: YB woodcarving PLC,
YB Woodcarving PLC manufactures two types of
wooden toys: soldiers and trains. A soldier sells for
$27 and uses $10 worth of raw materials. Each
soldier manufactured increases YBs variable labor
and overhead cost by $14. A train sells for $21 and
uses $9 worth of raw materials. Each train built
increases YBs variable labor and overhead cost by
$10. The manufacture of wooden soldiers and trains
requires two types of skilled labor: carpentry and
finishing. A soldier requires 2 hours of finishing labor
and 1 hour of carpentry labor. A train requires 1 hour
of finishing and 1 hour of carpentry labor. Each week,
YB 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. Formulate a linear programming
model for YB that can be used to maximize its weekly
profit?
5
Solution: YB woodcarving PLC
Step 1: Model formulation
[Link] variables: The decision variables should
completely describe the decisions to be made. Clearly,
YB must decide how many soldiers and trains should be
manufactured each week.
With this in mind, we define:
X1 = number of soldiers produced per week
X2 = number of trains produced per week
2. Objective function: The decision maker wants to
maximize (revenue or profit) or minimize (costs).
The function to be maximized/minimized is called the
objective function.
For the YB problem, we will maximize the net profit
(weekly revenues raw materials cost labor and
overhead costs).
Weekly revenues and costs can be expressed in terms
of the decision variables, X1 and X2, as following:
Weekly revenues = weekly revenues from soldiers +
weekly revenues from trains
= 27 X1 + 21 X2
Weekly raw materials costs = 10 X1 + 9 X2
Other weekly variable costs = 14 X1 + 10 X2
YB wants to maximize:
(27 X1 + 21 X2) (10 X1 + 9 X2) (14 X1 + 10 X2) = 3 X1 +
2 X2
Objective function is maximize Z = 3 X1 + 2 X2
8
3. Constraints: as X1 and X2 increase, YBs objective
function grows larger.
This means that if YB were free to choose any values
of X1 and X2, the company could make an arbitrarily
large profit by choosing X1 and X2 to be very large.
Unfortunately, the values of X1 and X2 are limited by
the following three restrictions (called constraints):
Cons-1: No more than 100 hours of finishing time may be
used/week.
Cons-2: No more than 80 hours of carpentry time may be
used/week.
Cons-3: At most 40 soldiers should be produced
9
due to limited demand.
The three constraints can be expressed in
terms of the decision variables X1 and X2 as
follows:
Constraint 1: 2 X1 + X2 100
Constraint 2: X1 + X2 80
Constraint 3: X1 40
The coefficients of the decision variables in the
constraints
are
called
technological
coefficients.
This is because it often reflects the technology
used to produce different products.
The number on the right-hand side of each
constraint is called Right-Hand Side (RHS).
It often represents the quantity of a resource
10
Sign restrictions: Answer this question: can
the decision variable only assume nonnegative
values or it is allowed to assume both negative
and positive values?
If a decision variable Xi can only assume a
nonnegative values, we add the sign
restriction, called non-negativity constraints,
Xi 0.
If a variable Xi can assume both positive and
negative values (or zero), we say that Xi is
unrestricted in sign
In our example, the two variables are
restricted in sign (X1 0 and X2 0)
11
Combining the non-negativity constraints
with the objective function and the
structural constraints yield the following
optimization model, usually called LP model:
Max Z = 3 X1 + 2 X2
subject to
2 X1 + X2 100
(finishing constraint)
X1 + X2 80
(carpentry constraint)
X1 40
(soldier demand constraint)
X1 0 and X2 0 (non-negativity constraint)
Optimal solution: X1 = 20, X2 = 60, Z = 180
12
What is Linear programming problem (LP)?
LP is an optimization problem for which we do the
following:
1. We attempt to maximize/minimize a linear function of
the decision variables.
The function to be maximized/minimized is called
objective function.
2. The values of decision variables must satisfy a set of
constraints.
Each constraint must be a linear equation or linear
inequality.
3. A sign restriction is associated with each variable.
For any Xi, the sign restriction specifies either that Xi >
13
0 or that Xi may be unrestricted in sign.
Applications of LP
Product mix problem
Diet problem
Transportation problem
Portfolio selection problem
Work-scheduling problem
Production scheduling problem
Inventory Problem
Multi period financial problem
Capital budgeting problem
14
1. Product Mix Problem: example
Formulate a linear programming model for this problem
to determine how many containers of each product to
produce tomorrow in order to maximize the profits.
The company makes four types of juice using orange,
grapefruit, and pineapple.
The following table shows the price and cost per quart
of juice (one container of juice) as well as the number of
kilograms of fruits required to produce one quart of
juice.
Product
Price/quart
Cost/quart
Fruit needed
Orange juice
1 Kg.
Grapefruit juice
0.5
2 Kg.
Pineapple juice
2.5
1.5
1.25 Kg.
15
0.25 Kg each
All in - one
Example: On hand there are 400 Kg of orange, 300 Kg.
of grapefruit, and 200 Kg. of pineapples. The manager
wants grapefruit juice to be used for no more than 30
percent of the number of containers produced. He
wants the ratio of the number of containers of orange
juice to the number of containers of pineapples juice
to be at least 7 to 5. pineapples juice should not
exceed one-third of the total product.
16
Solution
Decision variables
X1 = # of containers of orange juice
X2 = # of containers of grapefruit juice
X3 = # of containers of pineapple juice
X4 = # of containers of All-in-one juice
Objective function
Max Z = 2 X1 + 1.5 X2 + 1 X3 + 2 X3
Constraints
Orange constraints
X 1 0.25 X 4 400
Grapefruit constraint
2 X 2 0.25 X 4 300
Pineapple constraints
1.25 X 3 0.25 X 4 200
X 2 0.3( X 1 X 2 X 3 X 4) Max. of grapefruit
X1 7
X3 5
Ratio of orange to pineapple
1
Max. of pineapple
X 2 ( X 1 X 2 X 3 X 4)
3
X 1, X 2, X 3, X 4 0
Non-negativity constraints
17
[Link] selection: Example
The International City Trust invests in short-term
trade credits, corporate bonds, gold stocks, and
construction loans. To encourage a diversified
portfolio, the board of directors has placed limits on
the amount that can be committed to any one type of
investment. The ICT has $5 million available for
immediate investment and wishes to do two things: (1)
maximize the interest earned on the investments made
over the next six months, and (2) satisfy the
diversification requirements as set by the board of
directors. The specifics of the investment possibilities
are:
18
Investment
Interest
earned %
Maximum
investment
($ Million)
Trade credit
Corporate bonds
11
2.5
Gold stocks
19
1.5
Construction
15
1.8
loans
In addition, the board specifies that at least 55% of the
funds invested must be in gold stocks and construction
loans, and that no less than 15% be invested in trade
credit.
19
Solution
To formulate ICTs investment problem as a linear
programming model, we assume the following
decision variables:
X1 = dollars invested in trade credit
X2 = dollars invested in corporate bonds
X3 = dollars invested in gold stocks
X4 = dollars invested in construction loans
20
Max Z = 0.07 X1 + 0.11 X2 + 0.19 X3 + 0.15 X4
St.
X1
X2
1
2.5
X3 1.5
X4 1.8
X3 + X4 0.55(X1 + X2 + X3 + X4)
X1
0.15(X1 + X2 + X3 + X4)
X1 + X2 + X3 + X4 5
Xi 0 , i = 1, 2, 3, 4
Optimal values: X1 = 75,000, X2 = 950,000, X3 =
1,500,000, and X4 = 1,800,000, and total interest
Z = 712,000
21
Terminology for solution of LP
A feasible solution is a solution for which all the
constraints are satisfied.
A corner point feasible solution (CPF) is a feasible
solution that lies at a corner point.
An infeasible solution is a solution for which at least one
constraint is violated.
The feasible region is the collection of all feasible solution.
An Optimal solution is a feasible solution that has the
most favorable value of the objective function. (it is always
one of the CPF solution
22
Graphical solution
A Graphical Solution Procedure (for LPs with 2 decision variables)
1. Plot each constraint as an equation and then decide which
side of the line is feasible (if its an inequality).
2. Find the feasible region.
3. find the coordinates of the corner (extreme) points of the feasible
region.
4. Substitute the corner point coordinates in the objective function
5. Choose the optimal solution
23
Example 1: A Minimization Problem
LP Formulation
Min z = 5x1 + 2x2
s.t.
2x1 + 5x2 > 1
4x1 - x2 > 12
x1 + x2 > 4
x1, x2 > 0
24
Graphical Solution
Graph the Constraints
Constraint 1:When x1 = 0, x2 = 2; when x2 = 0, x1 = 5.
Connect (5,0) and (0,2). The ">" side is above this
line.
Constraint 2: When x2 = 0, x1 = 3. But setting x1 to 0
will yield x2 = -12, which is not on the graph. Thus, to
get a second point on this line, set x1 to any number
larger than 3 and solve for x2: when x1 = 5, then x2 =
8. Connect (3,0) and (5,8). The ">" side is to the
right.
Constraint 3: When x1 = 0, then x2 = 4; when x2 = 0,
then x1 = 4. Connect (4,0) and (0,4). The ">" side is
above this line.
25
Constraints Graphed
x2
Feasible Region
4x1 - x2 > 12
x1 + x2 > 4
2x1 + 5x2 > 10
(16/5,4/5)
(10/3, 2/3)
1
1
(5,0)
x1
26
Solve for the Extreme Point at the Intersection of the second and third
Constraints
4x1 - x2 = 12
x1 + x2 = 4
Adding these two equations gives:
5x1 = 16 or x1 = 16/5.
Substituting this into x1 + x2 = 4 gives: x2 = 4/5
Solve for the extreme point at the intersection of the first and third constraints
2x1 + 5x2 =10
x1 + x 2 = 4
Multiply the second equation by -2 and add to the first equation, gives
3x2 = 2 or x2 = 2/3
Substituting this in the second equation gives x1 = 10/3
Point
(16/5, 4/5)
88/5
(10/3, 2/3)
18
(5, 0)
25
27
