A PROJECT REPORT ON LINEAR PROGRAMMING

Submitted by

SOVAN DAS (REGD: 190402120003)

SATYAJIT SETHI (REGD: 190402120010)

AMAR KUMAR CHOUDHARY (REGD: 190402120013)

In partial fulfillment for the award of the degree

Of

MASTER IN BUSINESS ADMINISTRATION

of

Data Analytics

SCHOOL of MANAGEMENT

CENTURION UNIVERSITY OF TECHNOLOGY&MANAGEMENT,

BHUBANESWAR, ODISHA
Abstract
We identify a novel class of distributed
optimization problems, namely a networked
version of abstract linear programming. For such
problems we propose distributed algorithms for
networks with various connectivity and/or memory
constraints. Finally, we show how a suitable target
localization problem can be tackled through
appropriate linear programs.
Content
1>Introduction
2>Essential of linear programming model
3>Properties of linear programming model
4>Formulation of linear programming
5>Example
6> Graphical method
7>Simplex Method
8>Application
9>Conclusion
Introduction
Linear programming is a widely used mathematical modelling
technique to determine the optimum allocation of scarce resources
among competing demands. Resources typically include raw
materials, manpower, machinery, time, money and space.
The technique is very powerful and found especially useful because
of its application to many different types of real business problems in
areas like finance, production, sales and distribution, personnel,
marketing and many more areas of management.
As its name implies, the linear programming model consists of linear
objectives and linear constraints, which means that the variables in a
model have a proportionate relationship. For example, an increase in
manpower resource will result in an increase in work output.

ESSENTIALS OF LINEAR PROGRAMMING

MODEL
1. Limited resources: limited number of labour, material equipment
and finance
2. Objective: refers to the aim to optimize (maximize the profits or
minimize the costs).
3. Linearity: increase in labour input will have a proportionate
increase in output.
4. Homogeneity: the products, workers' efficiency, and machines are
assumed to be identical.
5. Divisibility: it is assumed that resources and products can be
divided into fractions. (In case the fractions are not possible, like
production of one-third of a computer, a modification of linear
programming called integer programming can be used).

PROPERTIES OF LINEAR PROGRAMMING

MODEL
The following properties form the linear programming model:
1. Relationship among decision variables must be linear in nature.
2. A model must have an objective function.
3. Resource constraints are essential.
4. A model must have a non-negativity constraint.

FORMULATION OF LINEAR PROGRAMMING

Formulation of linear programming is the representation of problem
situation in a mathematical form. It involves well defined decision
variables, with an objective function and set of constraints.

Objective function:
The objective of the problem is identified and converted into a
suitable objective function. The objective function represents the aim
or goal of the system (i.e., decision variables) which has to be
determined from the problem. Generally, the objective in most cases
will be either to maximize resources or profits or, to minimize the cost
or time.
 Constraints:
When the availability of resources is in surplus, there will be no
problem in making Decisions. But in real life, organizations normally
have scarce resources within which the job has to be performed in the
most effective way. Therefore, problem situations are Within
confined limits in which the optimal solution to the problem must be
found.
 Non-negativity constraint
Negative values of physical quantities are impossible, like producing
negative number of chairs, tables, etc., so it is necessary to include the
element of non-negativity as a constraint.

When to use Linear Programming

Linear programming can be used to solve a problem when the goal of
the problem is to maximize some value and there is a linear system of
inequalities that defines the constraints on the problem.

A constraint is an inequality that defines how the values of the

variables in a problem are limited. In order for linear programming
techniques to work, all constraints should be linear inequalities.
Example of a linear programming problem
Let’s say a FedEx delivery man has 6 packages to deliver in a
day. The warehouse is located at point A. The 6 delivery
destinations are given by U, V, W, X, Y, and Z. 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.

So, the delivery person will calculate different routes for

going to all the 6 destinations and then come up with the
shortest route. This technique of choosing the shortest route is
called linear programming.

In this case, the objective of the delivery person is to deliver

the parcel on time at all 6 destinations. The process of
choosing the best route is called Operation Research.
Operation research is an approach to decision-making, which
involves a set of methods to operate a system. In the above
example, my system was the Delivery model.

Linear programming is used for obtaining the most optimal

solution for a problem with given constraints. In linear
programming, we formulate our real-life problem into a
mathematical model. It involves an objective function, linear
inequalities with subject to constraints.

Is the linear representation of the 6 points above

representative of the real-world? Yes and No. It is an
oversimplification as the real route would not be a straight
line. It would likely have multiple turns, U-turns, signals and
traffic jams. But with a simple assumption, we have reduced
the complexity of the problem drastically and are creating a
solution that should work in most scenarios.

Formulating a problem – Let’s manufacture some

chocolates
Example: 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?

Solution: The first thing I’m gonna do is represent the

problem in a tabular form for better understanding.

Milk Choco Profit per unit

A 1 3 Rs 6

B 1 2 Rs 5

Total 5 12

Let the total number of units produced by A be = X

Let the total number of units produced by B be = Y

Now, the total profit is represented by Z

The total profit the company makes is given by the total number of
units of A and B produced multiplied by its per-unit profit of Rs 6 and
Rs 5 respectively.

Profit: Max Z = 6X+5Y

which means we have to maximize Z.

The company will try to produce as many units of A and B to

maximize the profit. But the resources Milk and Choco are available
in a limited amount.

As per the above table, each unit of A and B requires 1 unit of Milk.
The total amount of Milk available is 5 units. To represent this
mathematically,

X+Y ≤ 5

Also, each unit of A and B requires 3 units & 2 units of Choco

respectively. The total amount of Choco available is 12 units. To
represent this mathematically,

3X+2Y ≤ 12

Also, the values for units of A can only be integers.

So we have two more constraints, X ≥ 0 & Y ≥ 0

For the company to make maximum profit, the above inequalities

have to be satisfied.

This is called formulating a real-world problem into a

mathematical model.
Solve Linear Programs by Graphical Method

A linear program can be solved by multiple methods. In this section,

we are going to look at the Graphical method for solving a linear
program. This method is used to solve a two-variable linear program.
If you have only two decision variables, you should use the graphical
method to find the optimal solution.

A graphical method involves formulating a set of linear inequalities

subject to the constraints. Then the inequalities are plotted on an X-Y
plane. Once we have plotted all the inequalities on a graph the
intersecting region gives us a feasible region. The feasible region
explains what all values our model can take. And it also gives us the
optimal solution.

Let’s understand this with the help of an example.

Example: A farmer has recently acquired a 110 hectares piece of

land. He has decided to grow Wheat and barley on that land. Due to
the quality of the sun and the region’s excellent climate, the entire
production of Wheat and Barley can be sold. He wants to know how
to plant each variety in the 110 hectares, given the costs, net profits
and labor requirements according to the data shown below:

Cost Net Profit Man-

Variety
(Price/Hec) (Price/Hec) days/Hec

Wheat 100 50 10

Barley 200 120 30

The farmer has a budget of US$10,000 and availability of 1,200 man-

days during the planning horizon. Find the optimal solution and the
optimal value.
Solution: To solve this problem, first we gonna formulate our linear
program.

Formulation of Linear Problem

Step 1: Identify the decision variables

The total area for growing Wheat = X (in hectares)

The total area for growing Barley = Y (in hectares)

X and Y are my decision variables.

Step 2: Write the objective function

Since the production from the entire land can be sold in the market.
The farmer would want to maximize the profit for his total produce.
We are given net profit for both Wheat and Barley. The farmer earns
a net profit of US$50 for each hectare of Wheat and US$120 for
each Barley.

Our objective function (given by Z) is, Max Z = 50X + 120Y

Step 3: Writing the constraints

1. It is given that the farmer has a total budget of US$10,000. The cost
of producing Wheat and Barley per hectare is also given to us. We
have an upper cap on the total cost spent by the farmer. So our
equation becomes:

100X + 200Y ≤ 10,000

2. The next constraint is the upper cap on the availability of the total
number of man-days for the planning horizon. The total number of
man-days available is 1200. As per the table, we are given the man-
days per hectare for Wheat and Barley.

10X + 30Y ≤ 1200

3. The third constraint is the total area present for plantation. The total
available area is 110 hectares. So the equation becomes,

X + Y ≤ 110

Step 4: The non-negativity restriction

The values of X and Y will be greater than or equal to 0. This goes

without saying.

X ≥ 0, Y ≥ 0

We have formulated our linear program. It’s time to solve it.

Solving an LP through Graphical method

Since we know that X, Y ≥ 0. We will consider only the first

quadrant.

To plot for the graph for the above equations, first I will simplify all
the equations.

100X + 200Y ≤ 10,000 can be simplified to X + 2Y ≤ 100 by dividing

by 100.

10X + 30Y ≤ 1200 can be simplified to X + 3Y ≤ 120 by dividing by

10.

The third equation is in its simplified form, X + Y ≤ 110.

Plot the first 2 lines on a graph in the first quadrant (like shown
below)

The optimal feasible solution is achieved at the point of intersection

where the budget & man-days constraints are active. This means the
point at which the equations X + 2Y ≤ 100 and X + 3Y ≤ 120
intersect gives us the optimal solution.
The values for X and Y which gives the optimal solution is at (60,20).

To maximize profit the farmer should produce Wheat and Barley in

60 hectares and 20 hectares of land respectively.

The maximum profit the company will gain is,

Max Z = 50 * (60) + 120 * (20)

= US$5400
Simplex Method
Simplex Method is one of the most powerful & popular methods for
linear 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.

A linear programming function is in its standard form if it seeks to

maximize the objective function.

subject to constraints,

. . .
. . .

where, and . After adding slack variables, the

corresponding system of constraint equation is,

.
. .

where,
 The variables, ………………. are called slack variables.
They are non-negative numbers that are added to remove the
inequalities from an equation.

The above explanation gives the theoretical explanation of the

simplex method. Now, I am gonna explain how to use the simplex
method in real life using Excel.

Example: The advertising alternatives for a company include

television, newspaper and radio advertisements. The cost for each
medium with its audience coverage is given below.

Television Newspaper Radio

Cost per advertisement ($) 2000 600 300
Audience per advertisement 100,000 40,000 18,000
The local newspaper limits the number of advertisements from a
single company to ten. Moreover, in order to balance the advertising
among the three types of media, no more than half of the total number
of advertisements should occur on the radio. And at least 10% should
occur on television. The weekly advertising budget is $18,200. How
many advertisements should be run in each of the three types of
media to maximize the total audience?

Solution: First I am going to formulate my problem for a clear

understanding.

Step 1: Identify Decision Variables

Let , , represent the total number of ads for television,

newspaper, and radio respectively.

Step 2: Objective Function

The objective of the company is to maximize the audience. The

objective function is given by:
Step 3: Write down the constraints

Now, I will mention each constraint one by one.

It is clearly given that we have a budget constraint. The total budget

which can be allocated is $18,200. And the individual costs per
television, newspaper and radio advertisement is $2000, $600 and
$300 respectively. This can be represented by the equation,

For a newspaper advertisement, there is an upper cap on the number

of advertisements to 10. My first constraints are,

The next constraint is the number of advertisements on television. The

company wants at least 10% of the total advertisements to be on
television. So, it can be represented as:

The last constraint is the number of advertisements on the radio

cannot be more than half of the total number of advertisements. It can
be represented as

Now, I have formulated my linear programming problem. We are

using the simplex method to solve this. I will take you through the
simplex method one by one.

To reiterate all the constraints are as follows. I have simplified the last
two equations to bring them in standard form.
We have a total of 4 equations. To balance out each equation, I am

introducing 4 slack variables, , and .

So our equations are as follows:

I hope now you are available to make sense of the entire advertising
problem. All the above equations are only for your better
understanding. Now if you solve these equations, you will get the
values for X1= 4, X2= 10 and X3= 14.

Applications of Linear Programming

Linear programming and Optimization are used in various
industries. The manufacturing and service industry uses linear
programming on a regular basis. In this section, we are going
to look at the various applications of Linear programming.

1. Manufacturing industries use linear programming

for analyzing their supply chain operations. Their
motive is to maximize efficiency with minimum
operation cost. As per the recommendations from the
linear programming model, the manufacturer can
 reconfigure their storage layout, adjust their workforce
and reduce the bottlenecks. Here is a small Warehouse
case study of Cequent a US-based company, watch
this video for a more clear understanding.
2. Linear programming is also used in organized retail
for shelf space optimization. Since the number of
products in the market has increased in leaps and bounds,
it is important to understand what does the customer
want. Optimization is aggressively used in stores like
Wal-Mart, Hypercity, Reliance, Big Bazaar, etc. The
products in the store are placed strategically keeping in
mind the customer shopping pattern. The objective is to
make it easy for a customer to locate & select the right
products. This is subject to constraints like limited shelf
space, a variety of products, etc.
3. Optimization is also used for optimizing Delivery
Routes. This is an extension of the popular traveling
salesman problem. The service industry uses
optimization for finding the best route for multiple
salesmen traveling to multiple cities. With the help of
clustering and greedy algorithm, the delivery routes are
decided by companies like FedEx, Amazon, etc. The
objective is to minimize the operation cost and time.
4. Optimizations are also used in Machine Learning.
Supervised Learning works on the fundamental of linear
programming. A system is trained to fit on a
mathematical model of a function from the labeled input
data that can predict values from an unknown test data.
Conclusion
You should now be able to:
 formulate a given simplified description of a suitable

real-world problem as a linear programming model

in general, standard and canonical forms
 sketch a graphical representation of a two-

dimensional linear programming model given in

general, standard or canonical form
 classify a two-dimensional linear programming

model by the type of its solution

 solve a two-dimensional linear programming

problem graphically
 use the simplex method to solve small linear

programming models by hand, given a basic feasible

point.