Management Science

LINEAR
PROGRAMMING
www. https// By Group 4.com
 Linear Programming

OBJECTIVES:

Definition and Concepts

Characteristics and
Components
Situation, Problems, and
Methods
DEFINITION:
Linear programming is the technique used for
optimizing a particular scenario. Using linear
programming provides us with the best possible
outcome in a given situation. It uses all the
available resources in a manner such that they
produce the optimum result.
CONCEPTS/TERMINOLOGIES:
Decision Variables: Variables you want to
determine to achieve the optimal solution.
Objective Function: Mathematical equation that
represents the goal you want to achieve
Constraints: Limitations or restrictions that your
decision variables must follow.
Non-Negativity Restrictions: In some real-world
scenarios, decision variables cannot be negative
CHARACTERISTICS:
Constraints - limitations should be expressed in
mathematical form, regarding the source
Objective Function - In a problem, the objective function
should be specified in a quantitative way.
Linearity – The relationship between two or more
variables in the function must be linear. It means that the
degree of the variable is one.
CHARACTERISTICS:
Finiteness – There should be finite and infinite input and output
numbers. In case, if the function has infinite factors, the optimal
solution is not feasible.
Non-negativity – The variable value should be positive or zero. It
should not be a negative value.
Decision Variables – The decision variable will decide the output. It
gives the ultimate solution of the problem. For any problem, the
first step is to identify the decision variables.
COMPONENTS:
Decision Variables
- Variables used to determine optimal solution
Constraints
- Limitations or restrictions that the decision
variables must follow
Non-negativity restrictions
- In some cases, the decision variables cannot
be negative
Objective Functions
- The mathematical equation that represents
the goal to be achieved
EXAMPLE OF A LINEAR PROGRAMMING PROBLEM
FedEx delivery man has 6
packages to deliver in a
day. The warehouse is
located at point A. U, V, W,
X, Y, and Z represents the
6 delivery destinations.
The numbers on the lines
indicate the distance

6
between the cities. To
save on fuel and time the
delivery person wants to
take the shortest route.
EXAMPLE OF A LINEAR PROGRAMMING PROBLEM
Problem Statement: A FedEx delivery man has 6 packages to deliver
in a day. The warehouse is located at point A. Points U, V, W, X, Y, and
Z represent the 6 delivery destinations. The numbers on the lines
indicate the distance between the cities. To save on fuel and time,
the delivery person wants to take the shortest route.

Decision Variables: Let 𝖝𝖎 represent the distance from point A to

destination 𝖎
(where 𝖎 = U, V, W, X, Y, Z).

Objective Function: To save fuel, time and minimize the total

distance traveled,by the delivery person.
EXAMPLE OF A LINEAR PROGRAMMING PROBLEM
Constraints:
1. The delivery person must visit each destination
ASSUME:
exactly once.
2. The total distance traveled must be minimized. A TO U: 10M
A TO W: 18M
Route Calculation: A TO Y: 22M
The delivery person calculates different routes to A TO Z: 27M
all six destinations and then chooses the shortest
A TO X: 33M
one.
A TO V: 45M
LET'S ASSUME THE SHORTEST ROUTE IS : A TO U, W, Y,
Z, X, V.
EXAMPLE OF A LINEAR PROGRAMMING PROBLEM
Formulating a Problem:
Consider a chocolate manufacturing company that produces only two types
of chocolate – A and B. Both the chocolates require Milk and Choco only. To
manufacture each unit of A and B, the following quantities are required:

Each unit of A requires 1 unit of Milk and 3 units of Choco

Each unit of B requires 1 unit of Milk and 2 units of Choco
The company kitchen has a total of 5 units of Milk and 12 units of Choco. On
each sale, the company makes a profit of

Rs 6 per unit A sold

Rs 5 per unit B sold.
Now, the company wishes to maximize its profit. How many units of A and B
should it produce respectively?
EXAMPLE OF A LINEAR PROGRAMMING PROBLEM
SOLUTION:

To determine how many units of chocolate A and B the

company should produce to maximize its profit, we need to
set up a linear programming problem.
EXAMPLE OF A LINEAR PROGRAMMING PROBLEM
Let’s define the variables and constraints:

Variables:
Let be the number of units of chocolate A produced.
Let be the number of units of chocolate B produced.
Now, the total profit is represented by Z

Objective Function:
The profit from selling chocolates is given by:

Profit: Max Z = 6X+5Y

which means we have to maximize Z.

EXAMPLE OF A LINEAR PROGRAMMING PROBLEM
Constraints:
•Milk Constraint: Each unit of A requires 1 unit of Milk, and each
unit of B requires 1 unit of Milk. The total available Milk is 5
units.
X+Y ≤ 5
•Choco Constraint: Each unit of A requires 3 units of Choco,
and each unit of B requires 2 units of Choco. The total
available Choco is 12 units.
3X+2Y ≤ 12

Non-negativity Constraints:
X≥0 & Y≥0
 TYPES OF
LINEAR
PROGRAMMING
PROBLEMS
 Example
Manufacturing problems
aim to optimize production
decisions for maximum
MANUFACTURING profits or minimal costs,

PROBLEMS:
considering resource
availability (labor,
materials), production
rates, fees, and product
selling prices.
 Example

Diet problems seek the least

DIET
costly diet meeting nutritional
requirements, factoring in

PROBLEMS: nutritional content, food costs,

and dietary constraints (allergies,
preferences). A nutritionist may
minimize costs while meeting
nutritional needs.
 Transportation problems
minimize moving goods costs
type of Problems

from sources to destinations.

TRANSPORTATION Factors include supply at
PROBLEMS sources, demand at
destinations, and
transportation costs.
Companies optimize shipping
from factories to warehouses
under constraints.
 Optimal assignment
Types of Problems
problems efficiently allocate
tasks or resources. Factors
OPTIMAL ASSIGNMENT include individual or
PROBLEMS machine skills and costs or
time for different
assignments. Managers
may assign employees to
projects for time
optimization.
HOW TO SOLVE LINEAR PROGRAMMING PROBLEMS?
Step 1: Identify the decision variables in the problem.
Step 2: Construct the objective function and determine
whether it needs to be maximized or minimized.
Step 3: List all the constraints associated with the linear
problem.
Step 4: Ensure the decision variables meet non-negativity
restrictions.
Step 5: Solve the linear programming problem using a
suitable method, typically the simplex method or the
graphical method.
LINEAR 1. Graphical Method
PROGRAMMING 2. Simplex Method
METHODS
 The graphical method is used to
optimize the two-variable linear
Methods
programming. If the problem has two
decision variables, a graphical method

GRAPHICAL
is the best method to find the optimal
solution. In this method, the set of
inequalities are subjected to constraints.
Then the inequalities are plotted in the
XY plane. Once, all the inequalities are
plotted in the XY graph, the intersecting
region will help to decide the feasible
region. The feasible region will provide
the optimal solution as well as explains
what all values our model can take.
 Simplex Method is one of the
Methods
most powerful & popular
methods for linear

SIMPLEX
programming. The simplex
method is an iterative
procedure for getting the most
feasible solution. In this method,
we keep transforming the value
of basic variables to get
maximum value for the
objective function.
 Management science

THANK YOU!
+BSMA-1st year-section B

www.https//. By group 4.com

hello@group4 .com