Another example of Linear Programming:
Problem:
The Balelo Company manufactures vases and candle holders using only two materials: labor and
resin. Given these two finite resources, the corporation want to determine the optimal daily
production of vases and candle holders. This is referred regarded as a product mix problem in
general. There are 40 hours of labor and 120 grams of resins available each day for production.
The two items use the following resources for manufacturing and generate the following profit
per item produced.
Labor Resin Profit
Product (hr/unit) (gm/unit) (Php / unit)
Vase 1 4 40
Candle holder 2 3 50
Step 1: Define the decision variable
How many vases and candle holder to produce?
Decision variable:
x1 = number of vases produced
x2 = number of candle holder produced
Step 2: Objective Function:
Maximize Z = Php 40x1 + 50x2
Php 40x1 = profit form vase
Php 50x2 = profit form candle holder
Step 3: Model Constraints
x1 + 2x2 ≤ 40 hr. of labor
4x1 + 3x2 ≤ 120grms of resins
x1, x2 ≥ 0
Complete linear Programming model:
Maximize Z = Php 40x1 + 50x2
Subject to:
x1 + 2x2 ≤ 40 hr. of labor
4x1 + 3x2 ≤ 120grms of resins
x1, x2 ≥ 0
Where:
x1 = number of vases produced
x2 = number of candle holder produced
x1 + 2x2 ≤ 40 hr. of labor
(Assumption: x1 = 5 vases; and x2 = 10 candle holders – for us to get possible solution, since it
is not given to the problem)
(5) + 2(10) ≤ 40 hr. of labor
5 + 20 ≤ 40
25 ≤ 40
4x1 + 3x2 ≤ 120grms of resins
4(5) + 3(10) ≤ 120
20+ 30 ≤ 120
50 ≤ 120
Note: Because neither the constraint is violated by this hypothetical solution, we can say the
solution is feasible or possible
Step 4: Solution:
Feasible Solution: (trial and error)
Maximize Z = Php 40x1 + 50x2
Z = 40x1 + 50x2
Z= 40(5) + 50(10)
Z = 200 + 500
Z = Php 700
Let’s compute for an infeasible solution:
(Assumption: x1 = 10 vases; and x2 = 20 candle holders – for us to get possible solution, since it
is not given to the problem)
Z = 40x1 + 50x2
Z = 40(10) + 50 (20)
Z = 400 + 1000
Z = Php 1,400.00
For checking if feasible:
x1 + 2x2 ≤ 40 hr. of labor
10 + 2(20) ≤40
50 ≤ 40 - It is infeasible since it violates the resource constraints for labor
Optimal Solution:
The solution to this problem must maximize the profit without violating the constraints.
x1 = 24, x2 = 8
Z = 40x1 + 50x2
Z = 40 (24) + 50 (8)
Z = 960 + 400
Z = Php 1,360
For checking if feasible:
x1 + 2x2 ≤ 40 hr. of labor
24 + 2(8) ≤40
24 + 16 ≤40
40 = 40
GRAPHING SOLUTION:
1. Constraints line plotted as equation X2
Consider the line 1 (labor constraint)
50
x1 + 2x2 ≤ 40 hrs of labor
40
x1 + 2x2 = 40 x1 + 2x2 = 40
30
(0) + 2x2 = 40 x1 +2(0) = 40
20
x2 = 40/2 x1 = 40
x2 = 20 10
X1
0 10 20 30 40 50
Consider the line 2 (resin constraint) X2
4x1 + 3x2 ≤ 120grms of resins
4x1 + 3x2 = 120 4x1 +3x2 = 120 50
4 (0) + 3x2 = 120 4x1 + 3(0) =120 40
x2 = 120 / 3 x1 = 120 / 4 30
x2 = 40 x1 = 30 20
10
X1
0 10 20 30 40 50
2. Optimal Solution
X2
50
40
Point A: x1=0 ; x2= 20
30
A
20
10
B
Point C: x1=30 ; x2= 0
C X1
0 10 20 30 40 50
Point B = ? (Determine the solution values mathematically once the optimal solution points on
the graph have been determined)
a. Convert the both equations to function of x1
x1 + 2x2 = 40 4x1 + 3x2 = 120
x1= 40- 2x2 4x1 = 120-3x2
x1 = 30 – (3x2/4)
b. Let x2 in the first equation equal x
40-2x2 = 30-(3x2/4)
[40-2x2 = 30-(3x2/4)]4
160-8x2 = 120-3x2
8x2-3x2 -= 160-120
5x2 = 40
x2 = 40/5
x2= 8
Substituting the value of x2 = 8 into either one of the original equations to give value
to x1
x1 + 2x2 = 40
x1 = 40-2x2
x1 = 40 – 2(8)
x1 = 40 – 16
x1 = 24
To compute the profit (Point B)
Z = 40x1 + 50x2
Z = 40 (24) + 50 (8)
Z = 960 + 400
Z = Php 1,360.00
To compute the profit (Point A) To compute the profit (Point C)
Z = 40x1 + 50x2 Z = 40x1 + 50x2
Z = 40(0) + 50(20) Z = 40(30) + 50(0)
Z =0+ 1000 Z = 1200 + 0
Z = Php 1,000.00 Z = Php 1,200.00
Point A profit: Php 1,000.00
Point B profit: Php 1,360.00
Point C profit: Php 1,200.00
The optimum solution is point B which will give a maximum profit of Php 1,360.00
SPECIAL CASES OF LINEAR PROGRAMMING MODELS
Only one optimal solution has been attained in the production problem of ABC, Inc. It is a distinctive in
most cases linear programming problems. Figure 2.12 express the feasible area together with the objective
function z (the arrow specifies the improvement directions of the objective value). Unique optimal solution
is the corner point A.
In the previous discussion, let’s assume that the price
of the car is 650 (instead of 550), the management of
ABC, Inc. has two basic possibilities how to optimize
the profit. Producing 1000 cars (and 2000 boats) or
2000 cars (and 1000 boats) would bring the identical
optimal profit 1,650,000.
A linear programming problem with two or more
optimal solutions is said to have alternative (or
multiple) optimal solutions.
This condition occurs in graphical depiction of the
model when the objective function line is parallel to the
borderline of one constraint, as can be shown in Figure
2.13. Because the objective function reflects the
isoprofit line (in case of maximization) or the isocost
line (in case of minimization), all the solutions at the
edge of the feasible area have the same objective value
(optimal). There are two optimal corner points (B and
C) and the infinite number of optimal points on line
segment BC.
Figure 2.14 shows an interesting alternative of just
described case. The difference is evident – the feasible
area is unbounded and there is only one optimal corner
point D; the other optimal points lie on the borderline
running to infinity.
There is no optimal solution if the feasible solution area
is unbounded and the objective value is being enhanced
in the direction of unboundedness, therefore, the optimal
solution is endless (see Figure 2.15). Since these
instances are uncommon in reality, this finding typically
indicates mistake in formulation.
Infeasibility exists when no solution meets any of the
constraints. There is no common feasible area (no
feasible solution) in case of two constraints graphed in
Figure 2.16. In reality this scenario sometimes occurs,
particularly if the manager wants to be too accurate in
model formulation. In order to remove the infeasibility,
the model must be simplifying by for example
eliminating any vain restrictions.
While the two-variable model is not popular in practice
and is used more for analytical purposes, for
multidimensional problems both theories may be
simplified and transformed.
CHAPTER 2
LINEAR PROGRAMMING
Learning Objectives
1. Understand and define linear programming.
2. Identify all necessary items that must be included in a model
3. Write a verbal statement of the objective function and each
constraint.
4. Define the decision variables.
5. Write the objective function in terms of the decision variables.
6. Write the constraints in terms of the decision variables
7. Make a decision about the solution of the problem.
LINEAR PROGRAMMING
A comput er science t echnique t o
address issues of opt imizat ion
process.
The word “Linear”
Implies the linearity of all mathematical relationship
within a model.
Constraints
A standard model is the set of linear equations and / or
inequalities
Example:
ABC, Inc. creates 2 types of toys: car and boat. The car is priced
at P550, and the boat at P700. The cost of the car is P50, while
P70 for the boat. The car needs 1 hour of woodwork labor and 1
hour of painting and assembling labor. The boat requires 2 hours
of woodwork labor and1 hour of painting and assembling labor.
Cost of woodwork labor is P30 per hour, worth of painting and
assembling labor is P20 per hour. Monthly, ABC has 5000 existing
hours of woodwork labor and 3000 hours of painting and
assembling labor. There is an unlimited demand for boat, while an
average demand for car is at most 2000. ABC wants to get the
best out of monthly profit (total revenue - total cost).
Observe:
What is the situation all about?
Observe:
What is the situation all about?
Define t he problem:
What is the problem?
What do we need to achieve?
Formulat ion:
1. Decision Variables:
Formulat ion:
1. Decision Variables:
x1 = number of cars produce each month
Formulat ion:
1. Decision Variables:
x1 = number of cars produce each month
x2 = number of boats produce each month
Formulat ion:
2. Objective Function
Formulat ion:
2. Objective Function
2.1 TOTAL REVENUE (TR)
Price of one car = P 550.00x1
Price of one boat = P 700.00x2
Formulat ion:
2. Objective Function
2.1 TOTAL REVENUE (TR)
Revenues from sold car + revenues from sold boat
Formulat ion:
2. Objective Function
2.1 TOTAL REVENUE (TR)
Revenues from sold car + revenues from sold boat
TR = 500x1 + 700x2
Formulat ion:
2. Objective Function
2.1 MONTHLY WOOD COST (WC)
Formulat ion:
2. Objective Function
2.2 MONTHLY WOOD COST (WC)
Wood cost of production of one car = 50
50x1
Wood cast of production of one boat = 70
70x2
Formulat ion:
2. Objective Function
2.2 MONTHLY WOOD COST (WC)
WC = 50x1 + 70x2
Formulat ion:
2. Objective Function
2.3 WOOD WORK LABOR COST (WLC)
Formulat ion:
2. Objective Function
2.3 WOOD WORK LABOR COST (WLC)
1 car needs = 1 hr of woodwork
Cost of labor = Php 30.00
30x1
1 boat need = 2 hrs of woodwork
Cost of labor = Php 60.00
60x2
Formulat ion:
2. Objective Function
2.3 WOOD WORK LABOR COST (WLC)
WLC = 30x1 + 60x2
Formulat ion:
2. Objective Function
2.4 PAINTING AND ASSEMBLING LABOR COST (PALC)
1 hr of painting and assembling labor = Php 20.00
Formulat ion:
2. Objective Function
2.4 PAINTING AND ASSEMBLING LABOR COST (PALC)
PALC = 20x1 + 20x2
Formulat ion:
2. Objective Function
2.5 TOTAL MONTHLY COST
TC = WC + WLC + PALC
Formulat ion:
2. Objective Function
2.5 TOTAL MONTHLY COST
TC = WC + WLC + PALC
TC = (50x1 + 70x2) + (30x1 + 60x2) + ( 20x1+ 20x2)
Formulat ion:
2. Objective Function
2.5 TOTAL MONTHLY COST
TC = WC + WLC + PALC
TC = (50x1 + 70x2) + (30x1 + 60x2) + ( 20x1+ 20x2)
TC = 100x1 + 150x2
Formulat ion:
2. Objective Function
2.6 TOTAL PROFIT
TP = TR-TC
Formulat ion:
2. Objective Function
2.6 TOTAL PROFIT
TP = TR-TC
TP = (550x1 + 700x2) – (100x1+150x2)
Formulat ion:
2. Objective Function
2.6 TOTAL PROFIT
TP = TR-TC
TP = (550x1 + 700x2) – (100x1+150x2)
TP = 450x1 + 550x2
Formulat ion:
2. Objective Function
Objective function in the linear programming model is:
Maximize z = 450x1 + 550x2
Formulat ion:
450 and 550 in the function are termed
objective function coefficients
Formulat ion:
3. Constraints
Formulat ion:
3. Constraints
a. ABC, Inc. has just 5000 hours of woodwork labor accessible
per month
Formulat ion:
3. Constraints
a. ABC, Inc. has just 5000 hours of woodwork labor accessible
per month
b. No more than 3000 hours of finished labor can be used each
month
Formulat ion:
3. Constraints
a. ABC, Inc. has just 5000 hours of woodwork labor accessible
per month
b. No more than 3000 hours of finished labor can be used each
month
c. Because of minimal demand, there will be a maximum of 2000
cars delivered each month
Formulat ion:
3. Constraints
Formulat ion:
3. Constraints
a. One car needs 1 hour of woodwork labor. If ABC
manufactures monthly x1 of cars, x1 hour of labor are
consumed. Since one boat requires 2 hours and the
manufacturing quantity equals x2, the monthly
consumption of woodwork labor is 2x2 hours.
Formulat ion:
3. Constraints
a. One car needs 1 hour of woodwork labor. If ABC manufactures monthly x1 of
cars, x1 hour of labor are consumed. Since one boat requires 2 hours and the
manufacturing quantity equals x2, the monthly consumption of woodwork labor
is 2x2 hours.
Total consumption of woodwork labor for both products can be expressed as
x1 + 2x2. This is actual use of labor (in hours) that cannot be greater than
available number of hours (5000).
Formulat ion:
3. Constraints
With this, the constraint can be:
x1 + 2x2 5000
Formulat ion:
3. Constraints
b. The creation of the second constraint regarding painting and
assembling labor is like to the foregoing:
x1 + x2 3000
Formulat ion:
3. Constraints
c. The last constraint is easy to be construct. The number of produced
cars x1 must be less than or equal to 2000:
x1 2000
Formulat ion:
3. Constraints
Technological coefficients are coefficients of the decision
variables in the constraints while numbers 5000, 3000 and
2000 are termed right-hand side values.
Formulat ion:
4. Non- negativity Constraints
Formulat ion:
4. Non- negativity Constraints
Both decision variables have rational sign
restrictions:
because the values of variables reflect numbers of
toys made, we would expect them not to be
negative:
Formulat ion:
4. Non- negativity Constraints
Both decision variables have rational sign
restrictions:
because the values of variables reflect numbers of
toys made, we would expect them not to be
negative:
x1, x2 0
Formulat ion:
Summary of mathematical model in standard form:
Maximize z = 450x1 + 550x2
subject to:
x1 + 2x2 ≤ 5000,
x1 + x2 ≤ 3000 ,
x1 ≤ 2000 ,
x1, x2 ≥ 0 .
Thank you!
47
CHAPTER 2
LINEAR PROGRAMMING
2.2 GRAPHICAL
SOLUTION OF LINEAR
PROGRAMMING
PROBLEMS
Graphical Solut ions of Linear Programming
Models:
• Following the formulation of mathematical model, the next step in the
application of linear programming to a decision-making problem is to find
the solution of the model
• A common solution is to solve algebraically the set of mathematical
relationships that form the model either manually or using a computer
program, thus determining the values of the decision variables.
Graphical Solut ions of Linear Programming
Models:
• The graphical method is realistically limited to models with only two
decision variables, which can be represented on a graph of two
dimensions. Models with three dimensions, but the process is quite
cumbersome, and models of four or more decision variables cannot be
graphed at all
• Although the graphical method is limited as a solution approach, it is very
useful at this point in our presentation of linear programming in that it
gives a picture of how a solution is derived.
• Graphs can provide a cleared understanding of how the mathematical
solution approaches presented in subsequent chapters work, and thus, a
better understanding of the solution.
Graphical Solut ions of a Maximizat ion Model
• The product mix model will be used to demonstrate the graphical interpretation of
a linear programming problems. Recall that the problem describes ABC Inc.,
attempts to decide how many car and boats to produce monthly, given limited
amount of woodwork labor and painting and assembling labor. The complete
linear programming model was formulated as:
Maximize z = 450x1 + 550x2
subject to:
x1 + 2x2 ≤ 5000 hrs of woodwork labor
x1 + x2 ≤ 3000 hrs of painting and assembling labor
x1 ≤ 2000 cars produce ,
x1, x2 ≥ 0 .
X1 = number of cars produce each month
X2= number of boats produce each month
STEP 1: Graphing a feasible area
x2
6000
Figure 2.0 is a set of coordinates for the
5000
decision variables x1 and x2 on which
4000
the graph of our model will be drawn.
Note that only positive quadrant is 3000
drawn because of the nonnegativity 2000
constraint , x1 and x2 greater than or 1000
equal to 0.
0
1000 2000 3000 4000 5000 x1
Figure 2.0
• The first step in drawing the graph of the model is to plot the constraints on the
graph, this is done by treating both constraints as equation and plotting each line
on the graph.
(Line 1) x1 + 2x2 ≤ 5000
(Line 2) x1 + x2 ≤ 3000
Let ’s consider t he labor const raint line f irst :
x1 + 2x2 = 5000
• The first step in drawing the graph of the model is to plot the constraints on the
graph, this is done by treating both constraints as equation and plotting each line
on the graph.
(Line 1) x1 + 2x2 ≤ 5000
(Line 2) x1 + x2 ≤ 3000
Let ’s consider t he labor const raint line f irst :
x1 + 2x2 ≤ 5000
(0) + 2x2 = 5000
X2 = 2500
Thus, one point is at t he coordinat es x1 = 0 and x2 = 2500
• A second point can be found by letting x2 = 0 and solving for x1
x1 + 2x2 ≤ 5000
X1+ 2(0) = 5000
X1= 5000
Now we have t he second point , x1=5000, x2 = 0
• Thus, for the labor constraint, the first point is x1=0 and X2 = 2,500, and second
point x1=5000, x2=0. This is Line 1 (Woodwork labor)
• We draw a line for the painting and assembling labor (Line 2) the same way as
the one for the woodwork labor constraint – by finding the two points on the
constraints line and connecting them with a straight line. First let x1= 0 and solve
for x2
x1 + x2 ≤ 3000
(0) + x2 = 3000
x2 = 3000
Performing this operation results in a point x1=0, x2= 3000
Next, let x2=0 and then solve for x1
x1 + x2 = 3000
x1 + (0) = 3000
x1 = 3000
Thus, for the painting and assembling labor constraint, the first point is x1=0 and x2
=3000 and second point, x1=3000, x2=0.
• We draw a line for the number of cars produce (Line 3) the same way as the one
for the two constraints
x1 ≤ 2000
x1 = 2000
STEP 2: COMBINING CONSTRAINTS
Infeasible
Solution
Feasible
Solution
STEP 3: FINDING THE OPTIMAL SOLUTION
A
B
D
STEP 3: FINDING THE OPTIMAL SOLUTION
A
B
D
STEP 4: The Solut ion Value
• The 4th step in the graphical solution approach is to solve for the values of x1
and x2 once the possible optimal solution points have been found.
• Point A is x1 = 0 and x2 = 2500
• Point C is x1 = 2000 and x2 = 1000
• Point D is x1 = 2000 and x2 = 0
• But what are the coordinates of point B?
• The more exact approach is to determine the solution values mathematically
once the possible optimal solution points on the graph has been determined.
• The value of x1 and x2 coordinates of point B can be found by solving the two
equations simultaneously.
• First, we convert both equations to x1:
x1 + 2x2 = 5000
x1= 5000-2x2
and
x1 + x2 = 3000
x1 =3000-x2
• Now, we let x1 in the first equation equal x2 in the second equation:
5000 - 2x2 = 3000 - x2
• And solve for x2:
5000-2x2 = 3000 – x2
2x2 –x2 = 5000-3000
x2 = 2000
• Substituting x2 = 2000 into either one of the original equations gives a value for
x1:
x1 = 5000 - 2x2
x1 = 5000 – 2(2000)
x1 = 5000 – 4000
x1 = 1000
• Thus the coordinates for B are x1 = 1000 and x2 = 2000. Substituting these
values into the objective functions gives us the following profit for point B:
z = 450x1 + 550x2
z = 450 (1000) + 550 (2000)
z = 450,000 + 1,100,000
z = 1,550,000.00
Point A ( x1= 0, x2= 2500) will give us a profit of :
z = 450x1 + 550x2
z = 450 (0) + 550 (2500)
z = 0 + 1,375,000
z = Php 1,375,000
Point C (x1 = 2000, x2=1000) will give us a profit of:
z = 450x1 + 550x2
z = 450 (2000) + 550 (1000)
z = 9000 + 550,000
z = Php 1,450,000
Point D ( x1= 2000, x2= 0) will give us a profit of :
z = 450x1 + 550x2
z = 450 (2000) + 550 (0)
z = 900,000 + 0
z =Php 900,000
Thus the optimal solution is Point B (x1 = 1000, x2= 2000)
Which will give us a maximum profit z of Php 1,550.00
x1 = 0
X2 = 2500
A Z= Php 1,375,000
x1 = 1000
B X2 = 2000
Z= Php 1,550,000
x1 = 2000
X2 = 1000
C Z= Php 1,450,000
x1 = 2000
X2 = 0
D Z= Php 900,000
Summary of t he graphical solut ion st eps:
The steps for solving a graphical linear programming models are
summarized here:
1. Plot the model constraint as equations on the graph; then,
considering the inequalities of the constraints, indicate the feasible
solution area
2. Solve simultaneous equations at each corner point to find the
solution values at each point.
3. Substitute these values into the objective functions to find the set of
values that results in the maximum Z value
Thank you!
29
