Resources Academic Maths Linear Algebra Linear Programming
Steps to Solve a Linear Programming Problem
Learn Maths from the best
First Lesson Free!
Emma
June 26, 2019
Chapters
Introduction to Linear Programming
Features of Linear Programming
Parts of Linear Programming
Why we Need Linear Programming?
Steps to Solve a Linear Programming Problem
Example
Solution
Introduction to Linear Programming
t is an optimization method for a linear objective function and a
I system of linear inequalities or equations. The linear inequalities
or equations are known as constraints. The quantity which needs to
be maximized or minimized (optimized) is re ected by the objective
function. The fundamental objective of the linear programming model
is to look for the values of the variables that optimize (maximize or
minimize) the objective function.
We know that in linear programming, we subject linear functions to
multiple constraints. These constraints can be written in the form of
linear inequality or linear equations. This method plays a fundamental
role in nding optimal resource utilization. The word "linear" in linear
programming depicts the relationship between di erent variables. It
means that the variables have a linear relationship between them.
The word "programming" in linear programming shows that the
optimal solution is selected from di erent alternatives.
We assume the following things while solving the linear programming
problems:
The constraints are expressed in the quantitative values
There is a linear relationship between the objective function and the
constraints
The objective function which is also a linear function needs
optimization
The best Maths tutors available
The best Maths tutors available
1st lesson free! 1st lesson free! 1st lesson free! 1st less
4.9 (14 reviews) 4.9 (7 reviews) 5 (34 reviews) 4.9
Paolo Dr. Kritaphat Ayush Petar
£25/h £49/h £60/h £27/h
First Lesson Free
Features of Linear Programming
The linear programming problem has the following ve features:
Constraints
These are the limitations set on the main objective function. These
limitations must be represented in the mathematical form.
Objective function
This function is expressed as a linear function and it describes the
quantity that needs optimization.
Linearity
There is a linear relationship between the variables of the function.
Non-negativity
The value of the variable should be zero or non-negative.
Parts of Linear Programming
The primary parts of a linear programming problem are given below:
Objective function
Decision variables
Data
Constraints
Why we Need Linear Programming?
The applications of linear programming are widespread in many
areas. It is especially used in mathematics, telecommunication,
logistics, economics, business, and manufacturing elds. The main
bene ts of using linear programming are given below:
It provides valuable insights to the business problems as it helps in
nding the optimal solution for any situation.
In engineering, it resolves design and manufacturing issues and
facilitates in achieving optimization of shapes.
In manufacturing, it helps to maximize pro ts.
In the energy sector, it facilitates optimizing the electrical power
system
In the transportation and logistics industries, it helps in achieving time
and cost e ciency.
In the next section, we will discuss the steps involved in solving linear
programming problems.
Steps to Solve a Linear Programming Problem
We should follow the following steps while solving a linear
programming problem graphically
programming problem graphically.
Step 1 - Identify the decision variables
The rst step is to discern the decision variables which control the
behavior of the objective function. Objective function is a function that
requires optimization.
Step 2 - Write the objective function
The decision variables that you have just selected should be employed
to jot down an algebraic expression that shows the quantity we are
trying to optimize. In other words, we can say that the objective
function is a linear equation that is comprised of decision variables.
Step 3 - Identify Set of Constraints
Constraints are the limitations in the form of equations or inequalities
on the decision variables. Remember that all the decision variables are
non-negative; i.e. they are either positive or zero.
Step 4 - Choose the method for solving the linear
programming problem
Multiple techniques can be used to solve a linear programming
problem. These techniques include:
Simplex method
Solving the problem using R
Solving the problem by employing the graphical method
Solving the problem using an open solver
In this article, we will speci cally discuss how to solve linear
i bl i hi l th d
programming problems using a graphical method.
Step 5 - Construct the graph
After you have selected the graphical method for solving the linear
programming problem, you should construct the graph and plot the
constraints lines.
Step 6 - Identify the feasible region
This region of the graph satis es all the constraints in the problem.
Selecting any point in the feasible region yields a valid solution for the
objective function.
Step 7 - Find the optimum point
Any point in the feasible region that gives the maximum or minimum
value of the objective function represents the optimal solution.
Now, that you know what are the steps involved in solving a linear
programming problem, we will proceed to solve an example using the
steps above.
Example
A bakery manufacturers two kinds of cookies, chocolate chip, and
caramel. The bakery forecasts the demand for at least 80 caramel and
120 chocolate chip cookies daily. Due to the limited ingredients and
employees, the bakery can manufacture at most 120 caramel cookies
p y , y
and 140 chocolate chip cookies daily. To be pro table the bakery must
sell at least 240 cookies daily.
Each chocolate chip cookie sold results in a pro t of $0.75 and each
caramel cookie produces $0.88 pro t.
a) How many chocolate chip and caramel cookies should be made
daily to maximize the pro t?
b) Compute the maximum revenue that can be generated in a day?
Solution
Part a
Follow the following steps to solve the above problem.
Step 1 - Identify the decision variables
Suppose:
Number of caramel cookies sold daily = x
Number of chocolate chip cookies sold daily = y
Step 2 - Write the Objective Function
Since each chocolate chip cookie yields the pro t of $0.75 and each
caramel cookie produces a pro t of $0.88, therefore we will write the
objective function as:
, where x and y are non
negative
Step 3 - Identify Set of Constraints
It is mentioned in the problem that the demand forecast of caramel
cookies is at least 80 and the bakery cannot produce more than 120
caramel cookies. Therefore, we will write this constraint as:
It is also mentioned that the expected demand for the chocolate chip
cookies is at least 120 and the bakery can produce no more than 140
cookies. Therefore, the second constraint is:
To be pro table the company must sell at least 240 cookies
daily. Therefore, the third constraint is:
Step 4 - Choose the method for solving the linear
programming problem
W ill d h l i f h b bl hi ll
We will nd the solution of the above problem graphically.
Step 5 - Construct the graph
is subjected to the following constraints:
Step 6 - Identify the feasible region
Example graph
The green area of the graph is the feasibility region.
Step 7 - Find the Optimum point
Now, we will test the vertices of the feasibility region to determine the
optimal solution. The vertices are:
(120, 120) , (100, 140), (120, 140)
(120, 120) P = 0.88 (120) + 0.75 (120) = $ 195.6
(100, 140) P = 0.88 (100) + 0.75 (140) = $ 193
(120, 140) P = 0.88 (120) + 0.75 (140) = $ 210.6
Hence, the bakery should manufacture 120 caramel cookies and 140
chocolate cookies daily to maximize the pro t.
Now, we will proceed to solve the part b of the problem.
Part b
The answer to the part b is given in the previous section. The
maximum pro t that can be generated in a day is $210.6.
Need a Maths teacher?
Maths
Where (Address, city…)
Search
Did you like the article?
Emma
I am passionate about travelling and currently live and work in Paris. I
like to spend my time reading, gardening, running, learning languages
and exploring new places.
Theory
Linear Programming Examples
Linear Programming
Exercises
Linear Programming Problems and Solutions
