MS 6230
5 LECTURE
TH
LINEAR PROGRAMMING
Definition of Terms
Linear programming (LP) is a
method used to find the optimal
solution (maximum or minimum
value) of a linear objective function,
given a set of linear constraints.
Or
It's a mathematical technique that
helps in resource allocation and
decision-making by finding the
best possible outcome under
certain limitations.
Definition of terms
Decision Variables:
These are the unknown quantities
that the linear programming model
seeks to determine. They represent
the actions or decisions that can be
adjusted to achieve the best outcome.
Examples
For example, in a production
planning problem, decision
variables might be the number
of units of each product to
produce.
Definition of Terms
Objective Function:
This is a mathematical expression
that defines the quantity that the
linear programming model aims to
optimize (maximize or minimize).
Objective function
It represents the goal, such as
maximizing profit or
minimizing cost.
Examples
Maximize or min imize
z c1 x1 c2 x2 c3 x3 .....cn xn
Constraints:
These are linear inequalities or
equations that define the limitations
or restrictions on the decision
variables. They represent the
resources, capacity, or other
limitations that must be considered.
Example of a linear constraint
a1 x1 a2 x2 ......... an xn b
Note
The inequalities often used
or
Optimal Solution:
This is the best possible
solution among all the feasible
solutions that satisfy the
constraints.
Optimal solution
It represents the values of the
decision variables that result in
the optimal (maximum or
minimum) value of the
objective function
Feasible Region:
The feasible region is the set of all
points (combinations of decision
variables) that satisfy all the
constraints of the linear
programming problem. It represents
the area of possible solutions.
Parameters:
These are known quantities or
data that are used in the linear
programming model, such as
prices, resource capacities, and
technology coefficients.
QUESTION
What is “Linearity” in
linear Programming?
Linearity
In linear programming, all
relationships (the objective
function, the constraints, and the
parameters) must be linear,
meaning they can be represented
by straight lines.
OR
In Linear Programming, "linearity"
means that all functions involved
(objective and constraints) are first-
degree polynomials—no curves, no
powers, just straight-line
relationships.
Steps to follow in Solving an LP Problem
1.Identify the Decision Variables
Define the variables that represent
choices you can control.
Example: Let x = number of units of
product A, y = number of units of
product B.
2. Formulate the Objective
Function
State what you want to maximize
or minimize (e.g., profit, cost).
Must be a linear function of
the decision variables.
Example: Maximize Z=5x+3y
3. Write the Constraints
Express the limitations or
restrictions in the form of linear
inequalities.
These include limits on
resources like time, material,
labor, etc.
Example
2x+y≤100
(resource limit)
x+3y≤90
(another constraint)
4. Add Non-Negativity
Constraints
Most real-world problems
require variables to be
non-negative.
Examples
x≥0, y≥0
5. Graph the Constraints (for 2-variable
problems)
Plot the inequalities on a graph.
Identify the feasible region
(area where all constraints overlap).
This step is mainly useful
for problems with 2 variables.
6. Identify the Feasible Region
Shade the region where all
constraints
(including non-negativity)
are satisfied.
This region contains all
possible solutions.
7. Find the Corner Points
(Vertices)
These are the points where constraint
lines intersect.
The optimal solution is the maximum
or minimum value of the objective
function.
It lies at one of these points.
8. Evaluate the Objective
Function at Each Corner Point
Plug each vertex into the objective
function.
Choose the point that gives the
highest (or lowest) value based on
whether you're maximizing or
minimizing.
9. Interpret the Solution
State the values of decision
variables and the optimal value of
the objective function.
Make sure the solution makes
sense in the real-world context.
10. Use the Simplex
Method (for ≥ 3 variables)
If the problem has three or
more variables, graphical methods
aren't practical.
Use Simplex Algorithm or
software tools like: excel solver etc
Examples
1. A small firm builds two types of garden shed.
Type A requires 2 hours of machine time and 5
hours of craftsman time.Type B requires 3 hours
of machine time and 5 hours of craftsman
time.Each day there are 30 hours machine time
available and 60 hours of craftsman time
available.The profit on each type A shed is
sh.60 and on each type B shed is sh.84.
How many types of each should be
produced in order to maximize the profit?
Solution
Let x be no.of type A sheds
produced each day.
Y be no.of type B sheds
produced each day
Solution
A 2 5
B 3 5
Available 30 60
Solution
Objective function f 60 x 84 y
Subject to constra int s
2 x 3 y 30
5 x 5 y 60
x 0
y 0
Graphing the points
i) 2 x 3 y 30
when x 0, y 10
when y 0, x 15
ii ) 5 x 5 y 60
when x 0, y 12
when y 0, x 12
SOLUTION
FINISH THIS
PROBLEM
