Title of the Project

To find the minimum

cost by applying the
concept of
transportation in
LPP (Linear
Programming
Problems)
 Aims and Observation

In Mathematics, linear programming is a method of optimising operations with some

constraints. The main objective of linear programming is to maximize or minimize the
numerical value. It consists of linear functions which are subjected to the constraints in the
form of linear equations or in the form of inequalities. Linear programming is considered an
important technique that is used to find the optimum resource utilisation. The term “linear
programming” consists of two words as linear and programming. The word “linear” defines
the relationship between multiple variables with degree one. The word “programming”
defines the process of selecting the best solution from various alternatives.

Linear Programming is widely used in Mathematics and some other fields such as economics,
business, telecommunication, and manufacturing fields. In this article, let us discuss the
definition of linear programming, its components, and different methods to solve linear
programming problems.
 Previous Knowledge
Linear Programming has many advantages
including problem solving, skills, practical
application, graphical approach, optimisation
technique. LPP is a mathematical techniques
for developing and solving decision making
problem. The problem is usually given as a
linear function that needs to be optimise while
meeting certain constraints.
 DATA COLLECTION

Linear programming is a versatile mathematical technique in operations research and a

plan of action to solve a given problem involving linearly related variables in order to
achieve the laid down objective in the form of minimizing or maximizing the objective
function under a given set of constraints

CHARACTERISTICS

 Objectives can be expressed in a standard form viz. maximize/minimize z = f(x)

where z is called the objective function.
 Constraints are capable of being expressed in the form of equality or inequality
viz. f(x) = or ≤ or ≥ k, where k = constant and x ≥ 0.
 Resources to be optimized are capable of being quantified in numerical terms.
 The variables are linearly related to each other.
 More than one solution exist, the objectives being to select the optimum solution.
 The linear programming technique is based on simultaneous solutions of linear
equations.

USES

There are many uses of L.P. It is not possible to list them all here. However L.P is very
useful to find out the following:

 Optimum product mix to maximize the profit.

 Optimum schedule of orders to minimize the total cost.
 Optimum media-mix to get maximum advertisement effect.
 Optimum schedule of supplies from warehouses to minimize transportation costs.
 Optimum line balancing to have minimum idling time.
 Optimum allocation of capital to obtain maximum R.O.I
 Optimum allocation of jobs between machines for maximum utilization of
machines.
 Optimum assignments of jobs between workers to have maximum labor
productivity.
 Optimum staffing in hotels, police stations and hospitals to maximize efficiency.
 Optimum number of crew in buses and trains to have minimum operating costs.
 Optimum facilities in telephone exchange to have minimum break downs.

The above list is not an exhaustive one; only an illustration.

ADVANTAGES

 Provide the best allocation of available resources.

 meet overall objectives of the management.
 Assist management to take proper decisions.
 Provide clarity of thought and better appreciation of problem.
 Improve objectivity of assessment of the situation.
 Put across our view points more successfully by logical argument supported by
scientific methods.

PRINCIPLES

Following principles are assumed in L.P.P

Proportionality: There exist proportional relationships between objectives and

constraints.

Additivity: Total resources are equal to the sum of the resources used in individual
activities.

Divisibility: Solution need not be a whole number viz decision variable can be in
fractional form.

Certainty: Coefficients of objective function and constraints are known constants and
do not change viz parameters remain unaltered.

Finiteness: Activities and constraints are finite in number.

Optimality: The ultimate objective is to obtain an optimum solution viz

'maximization' or 'minimization'.

DEFINITION OF TERMS

a) Basic solution: There are instances where number of unknowns (p) are more
than the number of linear equations (q) available. In such cases we assign zero
values to all surplus unknowns. There will be (p-q) such unknowns. With these
values we solve 'q' equations and get values of 'q' unknowns. Such solutions are
called Basic Solutions.
b) Basic variables: The variables whose value is obtained from the basic solution is
called basic variables
c) Non-basic variables: The variables whose value are assumed as zero in basic
solutions are called non-basic variables.
d) Solution: A solution to a L.P.P is the set of values of the variables which
satisfies the set of constraints for the problem.
e) Feasible solution: A feasible solution to a L.P.P the set of values of variables
which satisfies the set of constraints as well as the non-negative constraints of the
problem.
f) Basic feasible solution: A feasible solution to a L.P.P in which the vectors
associated with the non-zero variables are linearly independent is called basic
feasible solution
Note: Linearly independent: variables x 1, x2, x3......... are said to be linearly
independent if k1x1+k2x2+.........+knxn=0, implying k1=0, k2=0,........
g) Optimum (optimal) solution: A feasible solution of a L.P.P is said to be the
optimum solution if it also optimizes the objective function of the problem.
h) Slack variables: Linear equations are solved through equality form of equations.
Normally, constraints are given in the "less than or equal" (≤) form. In such
cases, we add appropriate variables to make it an "equality" (=) equation. These
variables added to the constraints to make it an equality equation in L.P.P is
called stack variables and is often denoted by the letter 'S'.
Eg: 2x1 + 3x2 ≤ 500
∴ 2x1 + 3x2 + S1 = 500, where S1 is the slack variable
i) Surplus variables: Sometime, constraints are given in the "more than or equal"
(≥) form. In such cases we subtract an approximate variable to make it into
"equality" (=) form. Hence variables subtracted from the constraints to make it
an equality equation in L.P.P is called surplus variables and often denoted by the
letter 's'.
Eg: 3x1 + 4x2 ≥ 100
3x1 + 4x2 - S2 = 0, where S2 is the surplus variable.
j) Artificial variable : Artificial variables are fictitious variables. These are
introduced to help computation and solution of equations in L.P.P. There are
used when constraints are given in (≥) "greater than equal" form. As discussed,
surplus variables are subtracted in such cases to convert inequality to equality
form . In certain cases, even after introducing surplus variables, the simplex
tableau may not contain an 'Identity matrix' or unit vector. Thus, in a L.P.P
artificial variables are introduced in order to get a unit vector in the simplex
tableau to get feasible solution. Normally, artificial variables are represented by
the letter 'A'.
k) Big-M-method: Problems where artificial variables are introduced can be solved
by two methods viz.
 Big-M-method and
 Two phase method.
Big-M-method is modified simplex method for solving L.P.P when high
penalty cost (or profit) has been assigned to the artificial variable in the
objective function. This method is applicable for minimizing and maximizing
problems.
APPLICATION OF LINEAR PROGRAMMING
The primary reason for using linear programming methodology is to ensure
that limited resources are utilized to the fullest extent without any waste and that
utilization is made in such a way that the outcomes are expected to be the best possible.

Some of the examples of linear programming are:

a) A production manager planning to produce various products with the given

resources of raw materials, man-hours, and machine-time for each product must
determine how many products and quantities of each product to produce so as to
maximize the total profit.
b) An investor has a limited capital to invest in a number of securities such as
stocks and bonds. He can use linear programming approach to establish a
portfolio of stocks and bonds so as to maximize return at a given level of risk.
c) A marketing manager has at his disposal a budget for advertisement in such
media as newspapers, magazines, radio and television. The manager would like
to determine the extent of media mix which would maximize the advertising
effectiveness.
d) A Farm has inventories of a number of items stored in warehouses located in
different parts of the country that are intended to serve various markets. Within
the constraints of the demand for the products and location of markets, the
company would like to determine which warehouse should ship which product
and how much of it to each market so that the total cost of shipment is
minimized.
e) Linear programming is also used in production smoothing. A manufacturer has
to determine the best production plan and inventory policy for future demands
which are subject to seasonal and cyclical fluctuations. The objective here is to
minimize the total production and inventory cost.
f) A marketing manager wants to assign territories to be covered by salespersons.
The objective is to determine the shortest route for each salesperson starting from
his base, visiting clients in various places and then returning to the original point
of departure. Linear programming can be used to determine the shortest route.
g) In the area of personnel management, similar to the travelling salesperson
problem, the problem of assigning a given number of personnel to different jobs
can be solved by this technique. The objective here is to minimize the total time
taken to complete all jobs.
h) Another problem in the area of personnel management is the problem of
determining the equitable salaries and sales-incentive compensation. Linear
programming has been used successfully in such problems.
 Types of Linear Programming Problems
There are many different linear programming problems(LPP) but we will deal with three
major linear programming problems in this article.
Manufacturing Problems
Manufacturing problems are a problem that deals with the number of units that should be
produced or sold to maximize profits when each product requires fixed manpower, machine
hours, and raw materials.
Diet Problems
It is used to calculate the number of different kinds of constituents to be included in the diet
to get the minimum cost, subject to the availability of food and their prices.
Transportation Problems
It is used to determine the transportation schedule to find the cheapest way of transporting a
product from plants /factories situated at different locations to different markets.
Linear Programming Formula
A linear programming problem consists of,
 Decision variables
 Objective function
 Constraints
 Non-Negative restrictions
Decision variables are the variables x, and y, which decide the output of the linear
programming problem and represent the final solution.
The objective function, generally represented by Z, is the linear function that needs to be
optimized according to the given condition to get the final solution.
The restrictions imposed on decision variables that limit their values are called constraints.
Now, the general formula of a linear programming problem is,
Objective Function: Z = ax + by
Constraints: cx + dy ≥ e, px + qy ≤ r
Non-Negative restrictions: x ≥ 0, y ≥ 0
In the above condition x, and y are the decision variables.
How to Solve Linear Programming Problems?
Before solving the linear programming problems first we have to formulate the problems
according to the standard parameters. The steps for solving linear programming problems
are,
Step 1: Mark the decision variables in the problem.
Step 2: Build the objective function of the problem and check if the function needs to be
minimized or maximized.
Step 3: Write down all the constraints of the linear problems.
Step 4: Ensure non-negative restrictions of the decision variables.
Step 5: Now solve the linear programming problem using any method generally we use
either the simplex or graphical method.

Linear Programming Methods

We use various methods for solving linear programming problems. The two most common
methods used are,
 Simplex Method
 Graphical Method
Let’s learn about these two methods in detail in this article,

Linear Programming Simplex Method

One of the most common methods to solve the linear programming problem is the simplex
method. In this method, we repeat a specific condition ‘n’ a number of times until an
optimum solution is achieved.
The steps required to solve linear programming problems using the simplex method are,
Step 1: Formulate the linear programming problems based on the given constraints.
Step 2: Convert all the given inequalities to equations or equalities of the linear
programming problems by adding the slack variable to each inequality where ever
required.
Step 3: Construct the initial simplex table. By representing each constraint equation in a
row and writing the objective function at the bottom row. The table so obtained is called
the Simplex table.
Step 4: Identify the greatest negative entry in the bottom row the column of the element
with the highest negative entry is called the pivot column
Step 5: Divide the entries of the right-most column with the entries of the respective pivot
column, excluding the entries of the bottommost row. Now the row containing the least
entry is called the pivot row. The pivot element is obtained by the intersection of the pivot
row and the pivot column.
Step 6: Using matrix operation and with the help of the pivot element make all the entries
in the pivot column to be zero.
Step 7: Check for the non-negative entries in the bottommost row if there are no negative
entries in the bottom row, end the process else start the process again from step 4.
Step 8: The final simplex table so obtained gives the solution to our problem.

Linear Programming Graphical Method

Graphical Method is another method than the Simplex method which is used to solve linear
programming problems. As the name suggests this method uses graphs to solve the given
linear programming problems. This is the best method to solve linear programming
problems and requires less effort than the simplex method.
While using this method we plot all the inequalities that are subjected to constraints in the
given linear programming problems. As soon as all the inequalities of the given LPP are
plotted in the XY graph the common region of all the inequalities gives the optimum
solution. All the corner points of the feasible region are calculated and the value of the
objective function at all those points is calculated then comparing these values we get the
optimum solution of the LPP.
Example: Find the maximal and minimal value of z = 6x + 9y when the constraint
conditions are,
 2x + 3y ≤ 12
 x and y ≥ 0
 x+y≤5
Solution:
Step 1: First convert the inequations into normal equations. Hence the equations will be
2x+3y = 0, x = 0, y = 0 and x + y = 5.
Step 2: Find the points at which 2x + 3y and x + y = 5 cut the x-axis and y-axis. To find the
point of intersection of the x-axis put y = 0 in the respective equation and find the point.
Similarly for y-axis intersection points put x = 0 in the respective equation.
Step 3: Draw the two lines cutting the x-axis and y-axis. We find that the two axes cut each
other at (3,2).
Step 4: For x ≥ 0 and y ≥ 0, we find that both inequations are followed. Hence the region
will include an area region enclosed by two axes and both lines including the origin. The
plotted region is shown below in the figure.
Step 5: Find Z for each point and maxima and minima.
Coordinates Z = 6x + 9y

(0,5) Z = 45

(0,4) Z = 36

(5,0) Z = 30

(6,0) Z = 36

(3,2) Z = 36

Hence, we find that Z = 6x + 9y is maximum at (0,5) and minimum at (5,0).

Linear Programming
Applications
Linear Programming has applications in various fields. It is used to find the minimum cost
of a process when all the constraints of the problems are given. It is used to optimize the
transportation cost of the vehicle, etc. Various applications of Linear Programming are
Engineering Industries
Engineering Industries use linear programming to solve design and manufacturing problems
and to get the maximum output from a given condition.
Manufacturing Industries
Manufacturing Industries use linear programming to maximize the profit of the companies
and to reduce the manufacturing cost.
Energy Industries
Energy companies use linear programming to optimize their production output.
Transportation Industries
Linear programming is also used in transportation industries to find the path to minimize
the cost of transportation.
Importance of Linear Programming
Linear Programming has huge importance in various industries it maximizes the output
value while minimizing the input values according to various constraints.
LP is highly applicable when we have multiple conditions while solving a problem and we
have to optimize the output of the problem i.e. either we have to find the minimum or the
maximum value according to a given condition.
 NUMERICALS

Since number of units transported to each depot must be greater than or equal to
zero :-
∴ x ≥ 0 , y ≥0
Minimum cost = Rs 1550

From P : 0,5,3 units to depots A,B,C respectively

From Q : 5,0,1 units to depots A,B,C respectively

Corner Points Value of objective function

 1
Z= 10 (3x+y+39500)

A (3000,0) z = 4850

B (4500,0) z = 5300

C (4500,2500) 1
Z= 10 (13500+2500+39500)
= 5550
D (4000,3000) 1
Z= 10 (12000+3000+39500)
= 5450
E (500,3000) 1
Z= 10 (1500+3000+39500)
= 4400

z is Minimum at x=500 & y= 3000

∴From A: 500 liters, 3000 liters & 3500 liters to D, E, F Respectively

∴From B: 4000 liters, 0 liter and 0 liter to D, E, F Respectively

and Min transportation cost is Rs. 4400 ans.

Q.6) If a young man drives his vehicle at, he has to spend Rs. 2 per km on
petrol. If he drives it at a faster speed of, the petrol cost increases to. He has Rs.
100 to spend on petrol and travel with one hour. Express this on LPP and solve
the same.

Sol.6) Let x km distance traveled with speed and y km distance traveled with
speed. Let z total distance traveled.

LPP:

Maximize. (Distance)

Z=x+y

subject to constraints

2x + 5y ≤ 100 .....(Investment on petrol constraint)

 Conclusion
Linear programming is a systematic and structured approach to solving optimization
problems. It can be used to maximize or minimize a desired outcome while considering
constraints. Here are some conclusions about linear programming:

A powerful tool

Linear programming is a valuable tool for decision-making that can help organizations save
time and money. It can be used in a wide range of industries, including agriculture,
engineering, supply chain management, healthcare, and transportation.

Provides clear results

Linear programming can provide clear, actionable results that help organizations make data-
driven decisions.

Can solve complex problems

Linear programming can be used to solve complex problems by representing them

mathematically and then finding the optimal solution.

Can be solved graphically

Linear programming problems with two variables can be solved using the graphical method,
which is visual and provides a clear picture.

Has multiple categories

Linear programming can be divided into three categories: integer programming, nonlinear
programming, and mixed-integer programming.

Has assumptions and limitations

Linear programming has certain assumptions and limitations, but it can still provide practical
solutions to complex problems.