1. Understand the problem.
The goal of linear programming problems is to find a way to get the most, or least, of
some quantity -- often profit or expenses. This quantity is called your objective.
The answer should depend on how much of some decision variables you choose. Your options
for how much will be limited by constraints stated in the problem.
2. Describe the objective.
What are you trying to optimize? Are you trying to minimize costs? Maximize
production quantities?
You may have constraints like "you can't spend more than $1000" or "you mus't ship at least 50
tons of product C". These are limits but don't necessarily reflect your employer's top priorities;
don't mistake these for suggestions that you minimize costs or maximize production.
3. Define the decision variables.
The answer to a linear programming problem is always "how much" of some things.
What are those things? Choose variables to represent how much of each of those things.
For example:
L = number of leadership training programs offered
P = number of problem solving programs offered.
4. Write the objective function.
Use the variables you just chose to write down an algebraic expression that describes the
amount you're trying to minimize. Do not use an = sign. Do not use < or > signs.
5. Describe the constraints.
What are the limits on "how much" your decision variables can be? Look for words like
"at least", "no more than", "two thirds of of", "we must fill orders for", etc.
6. Write the constraints in terms of the decision variables.
For each constraint such as "at least $500" or "no more than 29" write an inequality using
the decision variables. For example: 2.5 L > 500
P + L < 29
7. Add the nonnegativity constraints.
Don't forget to include non-negativity constraints like P >= 0. These are worth a quick
two points on the quiz.
8. Write it up pretty.
Your formulation should look something like:
Maximize 4U + 3H
Subject to: U < 70
H < 60
2U - H < 100
U > 0
H > 0
Steps to Solve a Linear Programming Problem
We should follow the following steps while solving a linear programming problem graphically.
Step 1 - Identify the decision variables
The first 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:
Simple 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 specifically discuss how to solve linear 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 satisfies 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 and 140
chocolate chip cookies daily. To be profitable the bakery must sell at least 240 cookies daily.
Each chocolate chip cookie sold results in a profit of $0.75 and each caramel cookie produces
$0.88 profit.
a) How many chocolate chip and caramel cookies should be made daily to maximize the profit?
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 profit of $0.75 and each caramel cookie produces a
profit 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 profitable the company must sell at least 240 cookies daily. Therefore, the third constraint
is: Step 4 - Choose the
method for solving the linear programming problemWe will find 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 profit.
Now, we will proceed to solve the part b of the problem.
