Linear
Programming
2
Introduction to Linear Programming (LP)
Definition: Linear Programming (LP) is a technique
used to achieve the best outcome (such as maximum
profit or lowest cost) in a mathematical model.
The model's requirements are expressed as linear
equations or inequalities.
Why Use LP?
• To maximize an objective (like profit, output) or
minimize an objective (like cost, time) given
certain limitations (resources, time, etc.).
3
Example Scenarios
•A company wants to maximize profit by producing two
products but is limited by available labor and raw
materials.
•A logistics company wants to minimize
transportation costs while satisfying customer
demands.
Real-World Applications:
•Manufacturing (optimizing production)
•Agriculture (crop planning)
•Finance (investment portfolios)
•Transportation (route optimization)
4
Properties of Linear Programming
1. Objective Function: This is the formula
representing what you are trying to optimize
(maximize or minimize). It is a linear equation.
Example: A company wants to maximize profit. The
objective function could be:
Maximize 𝑃 = 50 + 30, where:
• P is the total profit,
• is the number of units of Product A,
• is the number of units of Product B.
5
Properties……
2. Constraints: These are the limits or restrictions
on the decision variables. They are usually
inequalities.
•Example: A company has a maximum of 100 hours
of labor. This can be written as:
+ ≤ 100, meaning 2 hours of labor for Product A
and 3 hours for Product B, with a total labor limit of
100 hours.
3. Non-Negativity: Decision variables cannot be
negative. You cannot produce a negative number of
products, so:
6
Additional Properties of LP
4. Feasibility: A solution is feasible if it satisfies all
constraints. The collection of all feasible solutions is called the
feasible region.
Example: The feasible region on a graph is where all the
constraints overlap. Solutions that fall within this region are
valid.
5. Linearity: The relationships in LP (objective function and
constraints) are linear, meaning they can be represented as
straight lines when plotted on a graph.
6. Boundedness: If the feasible region is enclosed (bounded),
there will be an optimal solution. If the region is unbounded,
the solution might be infinite or not exist.
7
Formulating LP Models
Step 1: Define Decision Variables
Identify what you're solving for.
Example: Let = the number of units of Product A,
and the number of units of Product B.
Step 2: Write the Objective Function
This is what you want to optimize (maximize or
minimize).
Example: Maximize profit:
𝑃=50 +30 , where 50 and 30 are the profits per unit
of Products A and B.
8
Continuation….
Step 3: Write the Constraints
Constraints represent the limitations or resources.
Example: If the company has only 100 hours of labor available,
and Product A takes 2 hours to make and Product B takes 3 hours,
the constraint is:
2+3 ≤ 100.
Step 4: Non-Negativity Restrictions
•Your decision variables should be non-negative because negative
production quantities are impossible.
•Example: ≥ 0, ≥ 0
9
Example of LP Model Formulation
Problem: A company produces two products, A and B. Each
unit of A provides a profit of $50, and each unit of B provides
a profit of $30. The company has a total of 100 hours of labor
available. Each unit of A requires 2 hours of labor, and each
unit of B requires 3 hours.
Formulation:
Objective: Maximize profit:
Maximize 𝑃=50 +30
Constraints: Labor availability: 2 + 3 ≤ 100 (total available
labor is 100 hours).
Non-Negativity: ≥ 0 , ≥ 0.
10
Graphical Solution of LP (Step 1: Plotting
Constraints)
Graphing the Constraints:
Convert each constraint into an equation by replacing the inequality sign
with an equal sign.
For the constraint 2+3≤ 100, plot the line 2+ 3= 100.
Plot the line by finding intercepts:
When = 0,= 0, = = 33.33,
When = 0,= 0, = =50.
Plot these points on a graph and draw the line.
Feasible Region:
The feasible region is the area where all constraints overlap. This represents
all valid solutions.
11
Graphical Solution of LP (Step 2: Optimizing the Objective
Function)
Plot the Objective Function:
The objective function is 𝑃=50 + 30 .Plot this line by choosing a
value of 𝑃 (e.g., P=1500) and finding the intercepts:
When = 0, =0, = =50,
When = 0, =0, = =30.
Draw the line and move it parallel towards the feasible region
until it touches the boundary.
Optimal Solution:
The point where the objective line touches the boundary of the
feasible region is the optimal solution.
12
Example of Graphical Solution
Example Problem:
Objective: Maximize 𝑃=50+30
Constraints: 2+3≤ 100
Graph: Show a graph with the constraints and the
feasible region.
Solution: The optimal point could be, for example, =
20, = 10. At this point,
profit 𝑃=50(20)+30(10)=$1300.
13
Interpreting the Results
Optimal Solution:
From the graph, determine the values of and that maximize
the objective function.
𝑃=50(20)+30(10)=$1,300.
Example: = 20, = 10, resulting in a maximum profit of
Conclusion:
The company should produce 20 units of A and 10 units of B
to achieve the maximum profit of $1,300.
14
Applications of Linear
Programming
Product Mix Optimization: Deciding how many units
of each product to produce to maximize profit.
Resource Allocation: Allocating limited resources like
labor and materials efficiently.
Supply Chain Optimization: Minimizing costs in
transporting goods from suppliers to customers.
Workforce Scheduling: Optimizing employee
schedules to meet demand while minimizing costs.
15
Conclusion
Key Takeaways:
Linear programming helps in making the best possible
decision when faced with limited resources.
Proper formulation of the LP model is crucial to solving real-
world business problems.
Graphical solutions provide a clear and intuitive method for
solving LP problems with two variables.
16
Practice Exercises