Linear Programming Problem

Dr. Chanchala Jain

Asst. Prof.
PIMR, Indore
 What is Linear Programming?
Linear programming (LP) or Linear
Optimization may be defined as the problem of
maximizing or minimizing a linear function that is
subjected to linear constraints. The constraints
may be equalities or inequalities. The
optimization problems involve the calculation of
profit and loss. Linear programming
problems are an important class of optimization
problems, that helps to find the feasible region
and optimize the solution in order to have the
highest or lowest value of the function.
 What is Linear Programming?
Linear programming is the method of considering
different inequalities relevant to a situation and
calculating the best value that is required to be
obtained in those conditions.
Some of the assumption taken while working
with linear programming are:
• The number of constraints should be expressed
in the quantitative terms
• The relationship between the constraints and
the objective function should be linear
• The linear function (i.e., objective function) is
to be optimized
 Example of Linear Programming
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.
Components of Linear Programming

The basic components of the LP are as follows:

• Decision Variables
• Constraints & Necessary constraints
• Data
• Objective Functions
Characteristics of Linear Programming
Constraints – The limitations should be expressed
in the mathematical form, regarding the resource.
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.
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.
Characteristics of Linear Programming

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.
 Process to formulate a LPP

• Identify the decision variables

• Write the objective function
• Mention the constraints
• Explicitly state the non-negativity restriction

For a problem to be a linear programming problem,

the decision variables, objective function and
constraints all have to be linear functions.
If all the three conditions are satisfied, it is called
a Linear Programming Problem.
Stages of a Linear Programming Model
• Stage I: In every LPP certain decisions are to
be made to resolve the problem. So first of all
we have to specified the quantities whose
values are to be determined. Establishing the
relationship between them and their impact
on the desired goal. Determined the
availability of resources.
• Stage II: Now form a mathematical model
from the given data. Identified the quantities
for which decisions to be taken and denote
them by variables setting up linear equation
for objective that to be achieved. Ascertain
Stages of a Linear Programming Model
the availability of resources and represent them
by inequalities (contains ‘≥’ or ‘≤’ sign) or
equations (contain ‘= ‘sign).
• Stage III: Apply appropriate method to obtain
the solution of the given problem and test the
solution for optimality. In general, we use
 Graphical Method (When no. of decision
variables involved in problem are two)
 Simplex Method (When no. of decision
variables involved in problem are more
than two)
Steps for Formulating Linear Programming
Although there is no standard set of rules to
formulate linear programming model of all the
problems. However in general following steps
are used to formulate mathematical model of
given problem:
• Step I: Denote the quantities by variables x1,
x2, x3.... Xn for which we want to determine
how much quantities are required to
optimised the objective.
• Step II: Setting up a objective function. It is a
linear equation for optimization
(Maximization and Minimization) with the
Steps for Formulating Linear Programming

help of variables introduced in step (I).

• Step III: Identify the set of constraints in terms
of Inequalities of equations which arises due
to limitation, restriction or unavailability of
resources.
 Mathematical Programming
A mathematical model consists of:
• Decision Variables, Constraints, Objective
Function, Parameters and Data
The general form of a math programming model is:

Linear program (LP): all functions f and gi are linear

and X is continuous.
Integer program (IP): X is discrete.
 Mathematical Programming
Objective Function n
Minimize Z = c1x1 + c2x2 + ....... + cnxn or Z = ∑cjxj
j=1

Constraints
a11x1 + a12x2 + ....... + a1nxn ≤ b1
a21x1 + a22x2 + ....... + a2nxn ≤ b2 n
∑aijxj ≤ bi
. or j=1

. for j = 1,2. ..., m

am1x1 + am2x2 + ....... + amnxn ≤ bm

Non-negative restrictions
or xj ≥ 0
x1, x2, ....... xn ≥ 0
for i = 1,2. ..., n
 Formulate a LPP
Example 1: 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?
 Formulate a LPP
Solution:

Profit per
Milk Choco
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.
 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.
 Formulate a LPP
Example 2: Food X contains 6 units of vitamin A per
gram and 7 units of vitamin B per gram and cost 12
paise per gram. Food Y contains 8 units of vitamin A
per gram and 12 units of vitamin B per gram and
costs 20 paise per gram. The daily minimum
requirement of vitamin A and vitamin B is 100 units
and 120 units respectively. Formulate the LPP for
minimum cost.
 Formulate a LPP
Solution:
Step I: The data of the problem can be represented
in tabular form as:

Food X Food Y Requirement

Vitamin A 6 8 100 units

Vitamin B 7 12 120 units

Cost 12 20
 Formulate a LPP
Step II: Decision Variables: Let assume mix x1 gram
of food X and x2 gram of food Y for getting
minimum requirements of vitamin A and B in
minimum cost.
Step III: Objective Function: Food X costs 12 paise
per gram so cost of x1 gram is 12x1 and food Y costs
20 paise per gram so cost of x2 gram is 20x2. thus
total cost of food X and Y is (12x1 + 20x2) paise
which we wan to minimize. Therefore,
Minimize Z = (12x1 + 20x2) paise or
Minimize Z = 0.12x1 + 0.20x2 (in rupees)
 Formulate a LPP
Step IV: Constraints: Food X contains 6 units of
vitamin A and food Y contains 8 units of vitamin A.
Thus, total vitamin A available by x1 units of food X
and x2 units of food Y is (6x1 + 8x2) which should not
be less than 100 gram daily. Therefore, it can be
expressed as
6x1 + 8x2 ≥ 100 (more than or equals to 100 units)
Similarly, the inequality for vitamin B
7x1 + 12x2 ≥ 120 (more than or equals to 120 units)
 Formulate a LPP

Step V: Non-negative Constraints: Negative

purchasing of food X and Y is meaningless,
therefore x1 ≥ 0 and x2 ≥ 0
Step VI: Linear Programming Model
Minimize = 0.12x1 + 0.20x2
Subject to constraints
6x1 + 8x2 ≥ 100
7x1 + 12x2 ≥ 120
x1 ≥ 0 and x2 ≥ 0
 Formulate a LPP
Example 3: The Agro Promotion Bank is trying to select
investment portfolio for a cotton farmer. The bank has
chosen a set of five investment alternatives, with subjective
estimates of rates of return and risk, as follows:
Investment Annual rate of return (%) Risk
Tax-free municipal bonds 6.0 1.3
Corporate bonds 8.0 1.5
High grade common stock 5.0 1.9
Mutual fund 7.0 1.7
Real estate 15.0 2.7

The bank officer in charge of the portfolio would like to

maximize the annual rate of return on the portfolio.
However, the wealthy investor has specified that the average
risk of the portfolio should not exceed 2.0; and does not
want more than 20% of the investment to be put into real
estate. Formulate an LP Model for the problem.
Let u, v, w, x and y be the proportion of portfolio
allocated to investment of type 1, 2, 3, 4 and 5
respectively.
Objective is to maximize the annual rate of return on
the portfolio.
i.e., Maximize Z = 0.06u + 0.08v + 0.05w + 0.07x + 0.15Y
Constraints are
On the average risk:
(1.3u + 1.5v + 1.9w + 1.7x + 2.7y)/1 ≤ 2.0
On investment in real estate:
y ≤ 0.2
On the total amount of investment:
u+v+w+x+y=1
where u, v, w, x, y ≥ 0
 Formulate a LPP
Example 4: Mr. Krishnamurty, a retired Govt. officer, has
recently received his retirement benefits, viz. provident fund,
gratuity, etc. He is contemplating as to how much funds he
should invest in various alternatives open to him so as to
maximize return on investment. The investment alternatives
are: government securities, fixed deposits of a public limited
company, equity share, time deposits in banks, national
saving certificates and real estate. He has made a subjective
estimate of the risk involved. The data on the return on
investment, the number of years for which the funds will be
blocked to earn this return on investment and the subjective
risk involved are as follows:
 Formulate a LPP
Investment Return No. of years Risk
Govt. securities 6% 15 1
Company deposits 15% 3 3
Equity shares 20% 6 7
Time deposits 10% 3 1
N. S. C. 12% 6 1
Real estate 25% 10 2

He was wondering what percentage of funds he should

invest in each alternative so as to maximize the return on
investment. He decided that average risk should not be more
than 4 and funds should not be locked up for more than 15
years. Formulate an L.P. model for the problem if he does not
want more than 30% of the investment to be put in the real
estate.
 Formulate a LPP
Example 5: A leading Charted Accountant is
attempting to determine the ‘best’ investment
portfolio and is considering six alternative
investment proposals. The following table indicates
point estimates for the price per share, the growth
rate in the price per share, the annual dividend per
share and a measure of the risk associated with
each investment.
 Formulate a LPP
A B C D E F
Current price/share 80 100 160 120 150 200
(Rs.)
Projected annual 0.08 0.07 0.10 0.12 0.09 0.15
growth rate
Projected annual 4.00 4.50 7.50 5.50 5.75 0.00
dividend per share
(Rs.)
Projected risk in 0.05 0.03 0.10 0.20 0.06 0.08
return

The total amount available for investment is Rs. 25

lakhs and the following conditions are required to
be satisfied:
 Formulate a LPP
1. The maximum rupee amount to be invested in
alternative F is Rs. 2,50,000
2. No more than Rs. 5,00,000 should be invested in
alternatives A and B combined.
3. Total weighted risk should not be greater than 0.10,
where
Total weighted risk = (Amount invested in alternative i)
(risk of alternative i)/ Total amount invested in all
alternatives
4. For the sake of diversity, at least 100 shares of each stock
should be purchased.
5. At least 10% of the total investment should be in
alternatives A and B combined.
6. Dividends for the year should be at least Rs. 10,000
 Formulate a LPP
Rupees return per share of stock is defined as price
per share one year hence less current price per
share plus dividend per share. If the objective is to
maximize total rupee return, formulate the linear
programming model for determining the optimal
number of shares to be purchased in each of the
shares under consideration. You may assume that
the time horizon for the investment is one year.
The formulated L.P. problem is not required to be
solved.
 Formulate a LPP
Example 6: A truck company has Rs. 50 lakh to
invest and is to choose among three types of trucks
A, B and C. Truck A has 12 tonne payload and is
expected to average 50 km per hour. It costs Rs.
80,000. Truck B has a 20 tonne payload, is expected
to average 45 km per hour and costs Rs. 1,00,000.
Truck C has a modified form of B. It has sleeping
space for the driver, which reduces its payload
capacity to 17 tonne, while raising the cost to Rs.
1,20,000.
Truck A requires a crew of one man, and if driven on
three shifts per day, could run for an average of 20
 Formulate a LPP
hours a day. Trucks B and C require a crew of two
men each and if driven on three shifts per day, could
be run for an average of 19 hours and 22 hours
respectively. The company has a fleet of 120
crewmen available to it. If the company wants to
maximize its capacity in tonne km per day?
Formulate the problem as LP problem.
 Formulate a LPP
Example 7: Consider a company that must products
over a production period of three months of
duration. The company can pay for materials and
labour from two sources: company funds and
borrowed funds. The firm faces three decisions:
1. How many units should it produce of product 1?
2. How many units should it produce of product 2?
3. How much money should it borrow to support
the production of the two products?
In making these decisions the firm wishes to
maximize the profit contribution subject to the
conditions stated below:
 Formulate a LPP
(i) Since the company’s products are enjoying a
seller’s market, it can sell as many as units as it can
produce.