Linear
Programming
presentors
apacionado, Bolilan,
hannah meryl rose
Aguirre, Bajamundi,
Jennilyn princess
Topics
PART 1 PART 2
Introduction Introduction
Structure of a Linear Programming Logic of the Simplex Method
Advantages and Limitations of LP Maximization Model Using
Linear Programming Simplex Method
The Graphical Method for Solving LP Minimization Model Using
Linear Programming Problems Simplex Method
Learning Outcomes
Summarize the structure of a linear programming problem and the
concept of objective functions, constrains, and non-negativity.
Distinguish product-mix and blending problems.
Discuss the assumptions of linear programming model.
Identify the advantages and limitations of linear programming.
Apply the graphical method for solving linear programming
problems
Discuss the logic of the simplex method
Create a simplex table and describe its components
Solve Problems using the simplex method.
Introduction
Decision-makers often utilize linear programming, which is
a mathematical technique for determining the best
allocation of a company’s resources
Linear Programming identifies the linear relationships
among variables in a manufacturing or production process.
In the 1940’s, George Dantzig an American mathematical
scientist developed linear programming for an air force
project to manage an efficient way to assign soldiers,
weapons, and supplies during World War II. It was originally
called "programming in a linear structure" but later
shortened to "linear programming".
2 Common linear
programming problems
Product mix problem
-The decision maker has to solve for which
product to include and in what quantities
should be included in the production plan
that will help achieve profit maximization.
2 Common linear
programming problems
Blending Problem
-Deals with finding the best blend of
available raw materials or ingredients that
will contribute to cost efficiency.
Structure of a
linear
programming
problem
The standard structure of an linear
programming problem consist of the
following:
Solve for x1 and x2 that will maximize the value
Decision Variables
of the given linear objective function
Profit Coefficient
Max z= 32x 1 + 13x 2 Objective Function
Decision Variables
Subject to:
4x1 + 6x2 500
|V
Capacities Constraints
7x 1 + 1x2 200
|V
x1 0
|V
x2 0 Non-Negativity
Input-Output |V
Coefficients
Decision Variables
-Variables whose values are to be determined
-The main characteristics of a decision variable
are controllable, continuous and non-negative
Objective Function
-A mathematical expression of the relationship
between the decision variable and a single goals.
Goals are given as total profit, total cost, market
share etc.
Profit or Cost Coefficient
-Expressed as the rate at which the value of the
objective function is increased based on the
decision variables.
Constraints
-The use of resources has limitations or
production has certain requirements, and these
consider constraints.
Input-Output Coefficients
- Express the rate at which a resource is put to use
Capacities
-The capacities or availability of the varying
resources are indicated by their highest or lowest
limit
Optimization
-The goals of the objective can be either maximize
or minimize
Non-negativity
-Decision Variables are required to be non-
negative ( 0 or positive ) values.
advantages of linear
programing
1. Resources are deployed productively and efficiently with the
use of linear programming
2. The Approach to decision-making is geared toward objectively.
Decision makers improve the quality of decisions and enhance
their ability to come to more sensible conclusions.
3. The optimal use of resources is attained by taking into account
the constraints of a production problem or business scenario
4. Bottlenecks are vital considerations when making a decision
limitations of linear
programing
1. The decision variables, constrains and objective function are not always
linearly related in real life situations.
2. Decision variables do not always result to get an integer value. To round
off to the nearest integer might not give an optimal solution
3. The effects of time and uncertainty are ignored in the linear
programming solution
4. Parameters in linear programming are assumed to be constant, which
contradicts real business situations
5. An linear programming is focused on one main objective. On the other
hand decisions in real life are oftentimes characterized by multiple
incompatible objectives.
Guidelines on LP model formulation
the graphical method for solving
linear programming problems
-The graphical method is appropriate for small problems
dealing with two decision variables and with few
constraints.
phases in graphical method
1. Graphing the feasible area
- In order to establish the feasible area all inequalities
and constraints must be plotted in a graph. Let us graph
the first constraint ( machine time constraint )
2.5x₁ + 2x₂ ≤ 40
Lovely enterprise manufactures 2 types of slippers: Rubber
flip-flops and bedroom slippers. The profitability,
limitations on machine, labor, and sales are listed below:
Slipper
Machine
Labor
Profit
Rubber flip-flops
2.5 hours
2 hours
P150
Bedroom
slippers 2 hours
1 hour
P140
The store can only sell a maximum of 10 pairs per day of
bedroom slippers. Labor hours are limited to 30 hours of labor a
day, while the machine time has only 40 hours daily. The owner
of Lovely enterprise wants to decide on how many pairs of each
will be produced every day in order to achieve the highest level
of profit.
To summarize the problem:
Maximize P = 150x1 + 140x2
subject to:
2.5x1 + 2x2 40 (machine time constraint)
VI VI VI VI VI
2x1 + 1x2 30 (labor constraint)
1x2 10 (marketing constraint)
x1
}
0 (non-negativity constraint)
x2 0
Consider the equality part of the constraint only. So it will
expressed as: 2.5x₁ + 2x₂ ≤ 40. The equation will form a straight line by
finding the coordinates of two points. In order to find the
coordinates, set x₁ to 0, which means that rubber flip flops ( x₁ ) will
not be produced. The calculations are done as follows:
If we set x₁ = 0, then 2.5(0) + 2x₂=40 or x₂ = 20.
Next, we set x₂ = 0, then 2.5x₁ + 2(0) = 40 or x₁ = 16.
This means that 20 rubber flip flops (x₁) must be produced while
16 bedroom slippers must be produced for the machine constraint.
Repeat the same steps for the labor and marketing constraint.
Labor constraint:
If we set x₁ = 0, then 2.5(0) +1x₂= 30 or x₂ = 30.
Next, we set x₂ = 0, then 2.5x₁ + 2(0) = 30 or x₁ = 15.
Marketing constraint:
x₂ = 10
Points
x₁
x₂
Figure 5.1
A
0
0
B
0
10
C
8
10
E
15
The shaded area in Figure 5.1
represents the feasible area. It
means that the area fits all the
requirement of the constraints
The values at each corner
points in Figure 5.1 should be
compared to determine the
optimal solution. Coordinates
for points A,B,C and E can be
easily identified by looking at
the graph
However, for point D, the intersection of machine time and labor constraint
can be approximated or computed using the substitution method:
1. 2.5x₁ + 2x₂ = 40
2. 2x₁ + 1x₂ = 30
Step 1. 2.5x₁ + 2x₂ = 40
2.5x₁ + 2x₂ - 2x₂ = 40 - 2x₂
2.5x₁ = 40 - 2x₂
2.5 2.5 2.5
x₁ = 16 - 0.08x₂
Step 2. 2x₁ + 1x₂ = 30
2(16 - 0.08x₂) + 1x₂ = 30
32 - 1.6x₂ + 1x₂ = 30
0.6x₂= 2
0.6 0.6
x₂ = 3.33
Step 3. 2x₁ + 2x₂ = 40
2x₁ + 2(3.33)= 40
2x₁ + 6.66= 40
2x₁ = 40 - 6.66
2x₁ = 33.34
2.5x 2.5x
x₁ = 13.34
Table below now includes the coordinates of point D.
Points
x₁
x₂
A
0
0
0
10
B
C
8
10
D
13.34
3.33
E
15
0
phases in graphical method
2. Determine the Optical Solution
- The Optical Solution is at the point of the feasible area
where the profit function is as its maximum.
Points
x₁
x₂
Total Profit
A
0
0
150 (0) + 140(0)x₂=
0
B
0
10
150 (0) + 140(10)x₂=
1,400
C
8
10
150 (0) + 140(10)x₂=
2,600
D
13.34 3.33
150 (13.34) + 140(3.33)x₂=
2,467.2
E
15
0
150 (15) + 140(0)x₂=
2,250
Comparing the profits from the five points result in
the selection of Point C because it has the highest
profit. Thus, Lovely Enterprises should produce 8 units
of rubber flip flops and 10 units of bedroom slippers per
day to earn a profit of P2,600.
Conclusion
Linear programming ( LP ) is very useful in solving
allocation problems as it provides an efficient search
for the optimal solution. There are two ways of solving
the model: the graphical method and simplex method.
The graphical method is appropriate for LP with only
two decision variables
Linear
Programming
Part2
Introduction
In the graphical solution procedure, the search for the optimal
solution is confined to the corner points within the feasible
area. While for the simplex method, the search starts at the
corner where all the unknowns are in zeros and then goes
around the area from one corner to another.
Figure 6.1 presents the
Logic of flowchart for LP
maximization model only.
Simplex
The LP minimization
model's solution is
slightly different from
method the maximization model.
Figure 6.1 Simplex method Flowchart
Step 1. Set the Lp problem by
determining the unknown
variables, objetive function,
and constraints.
Step 2. Add the necessary
slack variables, slack variables
are variables added to
constraints in order to
translate them into a linear
form
Step 3. Prepare the initial
tableau
Figure 6.1 Simplex method Flowchart
Step 4. Assess the tableau
if the solution is already
maximal. Otherwise,
proceed to step 5
Step 5. Calculate another
simplex tableau: choose the
pivot columns and find the
pivot row and pivot entry.
Step 6. Proceed to step 4.
PIVOT COLUMN - in maximization problem
should have the lowest negative value in the
last row.
PIVOT ROW- is a row in the simplex tableau
that contains the basic variable that will go out
of the solution.
INTERSECTIONAL ELEMENTS- are the elements
in the pivot column.
6.2 Maximization model Using
simplex method
Lovely enterprise manufactures two types of slippers:
rubber flip-flops and bedroom slippers. The profitability,
limitations on machine, labor, and sales are listed below:
Machine
Labor
Profit
Rubber Flip-flops
2.5 hours
2 hours
₱ 150
Bedroom
slippers 2 hours
1 hours
₱ 150
Solution :
1. The objective function and the constraints
2. Convert the LP problem to linear equations:
Take note of the following :
R ⬆
n
m| ⬅
Replacing/Remaining Row
⬅
Tableau Number
Row Number
P ⬅
m Tableau Number
n ⬅ Row Number
⬆
Pivot
6:3 LP minimization model
using simplex
Sample Problem
Happy chicken Co. is trying to determine the correct mix of two types of chicken feeds,
Brand A and Brand B, which cost ₱45 and ₱12 per kilogram, respectively. Two essential
ingredients are contained in the feed. Below shows the minimum daily requirements of each
ingredient:
Percent Per Percent Per Minimum
Ingredient
kilogram
kilogram
daily
number Brand A Brand B requirement
(Kg)
1
1
1
300
2
3
0
250
The Requirements
Ingredient 1:
1×1 + 1× 2>_ 300
Ingredient 2:
3× 1 + 0×2 >_ 250
1. The objective function and the constraints .
Minimize C = 45× 1 + 12×2
Subject to:
1×1 + 1×2 >_ 300
_ 250
3× 1 + 0× >
