Linear Programming

Linear Programming

• The process of taking various linear inequalities relating to a given situation and then finding the
best obtainable value satisfying the required conditions is formally known as linear programming.

• The problem which seeks to maximize or minimize a linear function (e.g. profit or cost expressed in
some variables) subject to some certain constraints as determined by a set of linear inequalities is
called an optimization problem.

• Linear programming problems are a special case of optimization problems.

• A linear programming problem (LPP) is one that is concerned with finding the optimum value
(maximum or minimum value) of a linear function (called objective function) of several variables
(say x and y), subject to the conditions that the variables are non-negative and satisfy a set of linear
inequalities (called linear constraints).

• For example, consider the following problem.

Two tailors A and B are working in a tailoring shop. Tailor A and B earn Rs 150 and Rs 200
per day respectively. Tailor A can stitch 6 shirts and 4 pants per day while tailor B can stitch
10 shirts and 4 pants per day. It is desired to produce at least 60 shirts and 32 pants at a
minimum labour cost. Express the given situation in the form of a linear programming
problem to find the number of days for which A and B should work.

Solution:

Let the tailors A and B work for x days and y days respectively.

Then, our problem is to minimise C = 150x + 200y

Subject to the constraints,

6x + 10y ≥ 60

Or, 3x + 5y ≥ 30

and 4x + 4y ≥ 32

Or, x + y ≥ 8, where x ≥ 0, y ≥ 0

Thus, the linear programming problem is obtained as

Minimise C = 150x + 200y

 Subject to,

3x + 5y ≥ 30

x+y≥8

x, y ≥ 0

Term Definition Expression in

above problem

Objective Linear function Z = ax + by, which has to be C = 150x + 200y

function minimized or maximised

Decision Deciding variables in the LPP x and y

variables

Constraints Linear inequalities or equations or restrictions on the 3x + 5y ≥ 30

variables of a linear programming problem
x+y≥8

x, y ≥ 0

Optimisation Problem which seeks to minimise or maximise a Min C = 150x +

Problem linear function subject to certain constraints as 200y
determined by a set of linear inequalities
3x + 5y ≥ 30

x+y≥8

x, y ≥ 0

Solved Examples

Example 1:
Two positive numbers x and y are such that their sum is at least 15 and their difference is at most 7.
Express the given situation mathematically in the form of a linear programming problem, which
aims at maximising the product of the two numbers.

Solution:

Let the two numbers be x and y.

It is given that x ≥ 0, y ≥ 0

The sum of x and y should be at least 15.

⇒ x + y ≥ 15

The difference of x and y should be at most 7.

⇒x−y≤7

We have to maximise the product xy.

Thus, the linear programming problem can be formulated as:

Max P = xy

Subject to,

x + y ≥ 15

x−y≤7

x, y ≥ 0

Example 2:

A decorative item dealer deals in only two items − wall hangings and artificial plants. He has Rs
15000 to invest and a space to store at the most 80 pieces. A wall hanging costs him Rs 300 and an
artificial plant costs him Rs 150. He can sell a wall hanging at the profit of Rs 50 and an artificial
plant at the profit of Rs 18. Assume that he can sell all the items that he bought. Make a
mathematical model to maximise his profit with the given conditions.

Solution:

Let the person sell x wall hangings and y artificial plants.

 Wall-hangings Artificial Plants Available

No. of items he sells x y 80

Unit cost 300 150 15000

Unit profit 50 18

The objective is to maximise the profit.

∴ Z = 50x + 18y

It is given that,

x + y ≤ 80

300x + 150y ≤ 15000

⇒ 2x + y ≤ 100

Also, x, y ≥ 0

Thus, the required linear programming problem is

Max Z = 50x + 18y

Subject to,

x + y ≤ 80

2x + y ≤ 100

x, y ≥ 0

Graphical Solution to Linear Programming Problems

• Consider the following linear programming problem:

Maximise Z = x + y

Subject to 4x + 2y ≤ 12

−x + y ≤ 1

x + 2y ≤ 4

x, y ≥ 0

The above problem can be represented on a graph as:

• The graph of this system (shown by shaded region) constitutes all the common points to all the
inequalities.
Basic constituents of this graph:

• Each point in the shaded region represents a feasible choice.

• The shaded region is called the feasible solution to the given problem.

• The common region determined by all the constraints including non-negative constraints x, y ≥ 0 of
a linear programming problem is called the feasible region for the problem.
In the above example, OABCD is the feasible region.

• The region other than the feasible region is called infeasible region.
• Points within and on the boundary of the feasible region are called feasible solutions.

• Any point in the feasible region that gives an optical value of the objective function is called optical
solution.

• Let R be the feasible region for a linear programming problem and let Z = ax + by be the objective
function. If R is bounded, then the objective function Z has both a maximum and minimum value on
R and each of these occurs at corner (vertex) point of R.

• If R is unbounded, then maximum or minimum value of the objective function may or may not exist.
If it exists, then it occurs at a corner point of R.

• Corner point method for solving linear programming method consists of the following steps.

• Some important different types of linear programming problems:

• Manufacturing Problem

• Transportation Problem

• Diet Problem
Solved Examples

Example 1:

Solve the following linear programming problem graphically.

Minimise Z = x + y

Subject to x + 2y ≥ 3

2x + y ≥ 5

x, y ≥ 0

Solution:

First we draw the lines x + 2y = 3 and 2x + y = 5 on graph as

Minimum value of objective function Z = x + y is obtained at .

Thus, optimal solution is

Optimal value =

Example 2:

A pharmaceutical company manufactures two types of drugs A and B. The combined production of
the drugs should not exceed 900 units per week. The demand for drug B is at most half of drug A.
Also, the production level of drug A is less than the sum of 3 times the production level of drug B
and 500 units. If the company makes a profit of Rs 10 and Rs 15 respectively on selling of one unit
of drug A and B each, then how many of each drug should be produced in a week in order to
maximise profit?

[Assume that all drugs manufactured are able to sell]

Solution:

Let x units of drug A are produced and y units of drug B are produced in a week.

Objective function is

Maximise Z = 10x + 15y

Subject to constraints x + y ≤ 900

y≤

x ≤ 3y + 500

x, y ≥ 0

The inequalities can now be represented on graph as

It is observed that the corner points are (0, 0), (500, 0), (800, 100), and (600, 300).

The value of Z = 10x + 15y is maximum at the corner point (600, 300).

Therefore, feasible solution is x = 600, y = 300

Optimal value = 10x + 15y = 10 (600) + 15(300) = 6000 + 4500 = 10,500

Thus, in order to maximise the profit, 600 units of drug A and 300 units of drug B are to be
produced.