1. Linear Programming Problem and its Mathematical Formulation

Chapter  12

Linear Programming Problems

Introduction, related terminology such as constraints, objective function, optimization, different types of linear programming (L.P.) problems, mathematical formulation of L.P. problems, graphical method of solution for problems in two variables, feasible and infeasible regions (bounded or unbounded), feasible and infeasible solutions, optimal feasible solutions (up to three non-trivial constraints), described by amar sir. Furthermore, it helps the student while facing other exams in the future.

Introduction

This section the discussion of linear equations, linear inequalities, applications of linear inequalities in previous grades. It introduces the concept of optimisation problems and a special case of optimisation problem called linear programming problem, using an example and described by amarsir. An ideal example of optimisation would be maximising the profit and minimising the cost of a production unit. 

Linear Programming Problem and its Mathematical Formulation

Formulation of an LPP refers to translating the real-world problem into the form of mathematical equations which could be solved. It usually requires a thorough understanding of the problem.

Mathematical formulation of the problem

In formulating a problem for linear Programming problem .study analysis must be made of the following major components: 

  1. The environment
  2. The objectives
  3. The decision maker
  4. The alternative courses of action and constraints.

It defines the non-negative constraints, objective function, decision variables.

A linear programming problem is finding the optimal value [maximum or minimum] of a linear function of variables, which are subjected to certain conditions and satisfying a set of linear constraints.

The variables involved in the objective function are called decision variables.

The constraints are the restrictions on the variables.

Important Definitions and Results:

Linear Programming

It is an important optimization (maximization or minimization) technique used in decision making is business and everyday life for obtaining the maximum or minimum values as required of a linear expression to satisfying certain number of given linear restrictions.

Linear Programming Problem (LPP)

The linear programming problem in general calls for optimizing a linear function of variables called the objective function subject to a set of linear equations and/or linear inequations called the constraints or restrictions.

2. Related terminology such as constraints, objective function, feasible and infeasible regions (bounded or unbounded) ,etc.

Related terminology

Objective Function

The function which is to be optimized (maximized/minimized) is called an objective function.

Constraints

The system of linear inequations (or equations) under which the objective function is to be optimized is called constraints.

Non-negative Restrictions / Decision variables

The variables involved in the objective function are called decision variables.

All the variables considered for making decisions assume non-negative values.

Mathematical Description of a General Linear Programming Problem

A general LPP can be stated as (Max/Min) z = clxl + c2x2 + … + cnxn (Objective function)

Subject to constraints

and the non-negative restrictions

xl, x2,….., xn ≥ 0 where all al1, al2,…., amn; bl, b2,…., bm; cl, c2,…., cn are constants and xl, x2,…., xn are variables.

  1. Solution of a LPP : A set of values of the variables xl, x2,…., xn satisfying the constraints of a LPP is called a solution of the LPP.
  2. Feasible Solution of a LPP: A set of values of the variables xl, x2,…., xn satisfying the constraints and non-negative restrictions of a LPP is called a feasible solution of the LPP.
  3. Optimal Solution of a LPP: A feasible solution of a LPP is said to, be optimal (or optimum), if it also optimizes the objective function of the problem.
  4. Graphical Solution of a LPP: The solution of a LPP obtained by graphical method i.e., by drawing the graphs corresponding to the constraints and the non-negative restrictions is called the graphical solution of a LPP.
  5. Unbounded Solution: If the value of the objective function can be increased or decreased indefinitely, such solutions are called unbounded solutions.
  6. Fundamental Extreme Point Theorem: An optimum solution of a LPP, if it exists, occurs at one of the extreme points (i.e., corner points) of the convex
    Polygon of the set of all feasible solutions

Solution of Simultaneous Linear Inequations:

The graph or the solution set of a system of simultaneous linear inequations is the region containing the points (x, y) which satisfy all the inequations of the given system simultaneously.

To draw the graph of the simultaneous linear inequations, we find the region of the xy-plane, common to all the portions comparing the solution sets of the given inequations. If there is no region common to all the solutions of the given inequations, we say that the solution set of the system of inequations is empty.

Note The solution set of simultaneous linear inequations may be an empty set or it may be the region bounded by the straight lines corresponding to given linear inequations or it may be an unbounded region with straight line boundaries.

3. Graphical method of solving linear programming problems

Graphical method of solving linear programming problems

This section comprises the definition of the feasible region, feasible solution and infeasible solution, optimal solution, bounded and unbounded region of feasible solution.

The graphical method is used to optimize the two-variable linear programming. If the problem has two decision variables, a graphical method 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.

 It briefs about the Corner Point Method, which is used to solve linear programming problems with solved examples.

The region obtained by the constraints [including non-negative constraints] can be termed as the feasible region.

The points within the feasible region are called feasible solutions.

The points outside the feasible region are called infeasible solutions.

The point in the feasible region which gives the optimal value of the objective function is called an optimal solution.

There are two Techniques / Methods of solving a LPP by graphical method :

1. Corner point method and

2. Iso-profit or Iso-cost method( outside syllabus )

1. Corner Point Method

This method of solving a LPP graphically is based on the principle of extreme point theorem.

Procedure to Solve a LPP Graphically by Corner Point Method

(i) Consider each constraint as an equation.

(ii) Plot each equation on graph, as each one will geometrically represent a straight line.

(iii) The common region, thus obtained satisfying all the constraints and the non-negative restrictions is called the feasible region. It is a convex polygon.

(iv) Determine the vertices (corner points) of the convex polygon. These vertices are known as the extreme points of corners of the feasible region.

  1. Find the values of the objective function at each of the extreme points. The point at which the value of the objective function is optimum (maximum or minimum) is the optimal solution of the given LPP.

Theorem 1 Let R be the feasible region (convex polygon) for a linear programming problem and let  be the objective function. When Z has an optimal value (maximum or minimum), where the variables x and y are subject to constraints described by linear inequalities, this optimal value must occur at a corner point (vertex) of the feasible region.

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

  • If the feasible region is unbounded, then a maximum or a minimum may not exist. However, if it exists, it must occur at a corner point of R.
  • Corner point method : For solving a linear programming problem. The method comprises of the following steps:

(i)     Find the feasible region of the linear programming problem and determine its corner points (vertices).

(ii)   Evaluate the objective function  , at each corner point. Let M and m respectively be the largest and smallest values at these points.

(iii)     If the feasible region is bounded, M and m respectively are the maximum and minimum values of the objective function.

  • If the feasible region is unbounded, then,

(i)   M is the maximum value of the objective function, if the open half plane determined by  has no point in common with the feasible region. Otherwise, the objective function has no maximum value.

(ii)   m is the minimum value of the objective function, if the open half plane determined by  has no point in common with the feasible region. Otherwise, the objective function has no minimum value.

  • If two corner points of the feasible region are both optimal solutions of the same type, i.e., both produce the same maximum or minimum, then any point on the line segment joining these two points is also an optimal solution of the same type.

1. Determine the maximum value of Z = 11+ 7subject to the constraints: 2 6,  2, ≥ 0, ≥ 0.

Solution:

Given: Z = 11+ 7and the constraints 2 6,  2, ≥ 0, ≥ 0

Let 2x + y = 6

Now, plotting all the constrain equations we see that the shaded area OABC is the feasible region determined by the constraints.

The feasible region is bounded. So, the maximum value will occur at a corner point of the feasible region.

Corner points are (0, 0), (2, 0), (2, 2) and (0, 6).

On evaluating the value of Z, we get

From the above table it’s seen that the maximum value of Z is 42.

Therefore, the maximum value of Z is 42 at (0, 6).

2. Maximize Z = 3+ 4y, subject to the constraints: ≤ 1, ≥ 0, ≥ 0.

Solution:

Given: Z = 3+ 4y and the constraints  1, ≥ 0,

≥ 0

Taking x + y = 1, we have

Now, plotting all the constrain equations we see that the shaded area OAB is the feasible region determined by the constraints.

The area is feasible. So, maximum value will occur at the corner points O(0, 0), A(1, 0), B(0, 1).

On evaluating the value of Z, we get

From the above table it’s seen that the maximum value of Z is 4.

Therefore, the maximum value of Z is 4 at (0, 1).

3. Maximize the function Z = 11+ 7y, subject to the constraints: ≤ 3, ≤ 2, ≥ 0, ≥ 0.

Solution:

Given: Z = Z = 11+ 7y and the constraints ≤ 3, ≤ 2, ≥ 0, ≥ 0.

Plotting all the constrain equations we see that the shaded area OABC is the feasible region determined by the constraints.

The feasible region is bounded with four corner points O(0, 0), A(3, 0), B(3, 2) and C(0, 2).

So, the maximum value can occur at any corner.

On evaluating the value of Z, we get

From the above table it’s seen that the maximum value of Z is 47.

Therefore, the maximum value of the function Z is 47 at (3, 2).

4. Minimize Z = 13– 15subject to the constraints: ≤ 7, 2– 3+ 6 ≥ 0, ≥ 0, ≥ 0.

Solution:

 

Given: Z = 13– 15y and the constraints ≤ 7, 2– 3+ 6 ≥ 0, ≥ 0, ≥ 0.

Taking x + y = 7, we have


The feasible region is bounded with four corners O(0, 0), A(7, 0), B(3, 4) and C(0, 2).Now, plotting all the constrain equations we see that the shaded area OABC is the feasible region determined by the constraints.

So, the maximum value can occur at any corner.

On evaluating the value of Z, we get

From the above table it’s seen that the minimum value of Z is -30.

Therefore, the minimum value of the function Z is -30 at (0, 2).

5. Determine the maximum value of Z = 3+ 4if the feasible region (shaded) for a LPP is shown in Fig. 12.7.

Solution:

As shown in the figure, OAED is the feasible region.

At A, y = 0 in equation 2x + y = 104 we get,

x = 52

This is a corner point A = (52, 0)

At D, x = 0 in equation x + 2y = 76 we get,

y = 38

This is another corner point D = (0, 38)

Now, solving the given equations x + 2y = 76 and 2x + y = 104 we have

2x + 4y = 152

2x + y = 104

(-)___(-)____(-)____

3y = 48 y = 16

Using the value of y in the equation, we get

x + 2(16) = 76 x = 76 – 32 = 44

So, the corner point E = (44, 16)

On evaluating the maximum value of Z, we get

From the above table it’s seen that the maximum value of Z is 196.

Therefore, the maximum value of the function Z is 196 at (44, 16).

6. Feasible region (shaded) for a LPP is shown in Fig. 12.8. Maximize Z = 5+ 7y.

Solution:

Given: Z = 5x + 7y and feasible region OABC.

The corner points of the feasible region are O(0, 0), A(7, 0), B(3, 4) and C(0, 2).

On evaluating the value of Z, we get

From the above table it’s seen that the maximum value of Z is 43.

Therefore, the maximum value of the function Z is 43 at (3, 4).

7. The feasible region for a LPP is shown in Fig. 12.9. Find the minimum value of Z = 11+ 7y.

Solution:

In the given figure, it’s seen that the feasible region is ABCA. The corner points are C(0, 3), B(0, 5) and for A, we have to solve equations

x + 3y = 9 and

x + y = 5

(-)_(-)_(-)

2y = 4 y = 2

And, putting value of y in the equation we get x = 3

So, the corner point is A(3, 2).

Now, evaluating the value of Z we get

From the above table it’s seen that the minimum value of Z is 21.

Therefore, the minimum value of the function Z is 21 at (0, 3).
Q8. Find solution using graphical method

max z = 5x1 + 4x2

subject to

x1 - 2 x2 <= 1

x1 + 2 x2 >= 3

and x1, x2 >= 0

To draw constraint    x1 - 2 x2 ≤1    →  (1)

Let x1 - 2 x2 =1
 

To draw constraint  x1 + 2 x2 ≥ 3     →(2)
Let   x1 + 2 x= 3
 

 

4. Different Types of Linear Programming Problems

Different Types of Linear Programming Problems:

A few important types of  linear programming problems are:

 (i) Manufacturing problems

 (ii) Diet problems

 (iii) Transportation problems

(iv) Allocation Problems

The different types of linear programming problems are discussed below.

Manufacturing problems

These problems can be seen in the manufacturing sector in order to optimize production by maximising profits. The profits can be a function of the number of workers, working hours, materials required, the value of the product in the market, the demand for the product, the supply of the product etc.

Constraints – Factors such as labour hours, the cost of packing materials, and so on.

The production rate is the objective function.

Example:

A manufacturer produces nuts and bolts. It takes 1 hour of work on machine A and 3 hours on machine B to produce a package of nuts. It takes 3 hours on machine A and 1 hour on machine B to produce a package of bolts. He earns a profit of Rs 17.50 per package on nuts and Rs 7.00 per package on bolts. How many packages of each should be produced each day so as to maximize his profit, if he operates his machines for at the most 12 hours a day?

Solution:

Let the manufacturer produce x package of nuts and y package of bolts. Hence,

x ≥ 0 and y ≥ 0

The given information can be compiled in a table as given below

The profit on a package of nuts is Rs 17.50 and on a package of bolts is Rs 7

Hence, the constraints are

x + 3y ≤ 12

3x + y ≤ 12

Then, total profit, Z = 17.5x + 7y

The mathematical formulation of the given problem can be written as follows

Maximize Z = 17.5x + 7y …………. (1)

Subject to the constraints,

x + 3y ≤ 12 …………. (2)

3x + y ≤ 12 ………… (3)

x, y ≥ 0 …………….. (4)

The feasible region determined by the system of constraints is given below

A (4, 0), B (3, 3) and C (0, 4) are the corner points

The values of Z at these corner points are given below

Therefore, Rs 73.50 at (3, 3) is the maximum value of Z

Hence, 3 packages of nuts and 3 packages of bolts should be produced each day to get the maximum profit of Rs 73.50

Diet problems

Such problems involve the optimisation of the amount of intake of different types of foods, which are required by the body to obtain necessary nutrients. The agenda of a diet problem will be selecting those foods with the required nutrient at a lesser cost.

Example:

.Reshma wishes to mix two types of food P and Q in such a way that the vitamin contents of the mixture contain at least 8 units of vitamin A and 11 units of vitamin B. Food P costs Rs 60/kg and Food Q costs Rs 80/kg. Food P contains 3 units /kg of vitamin A and 5 units /kg of vitamin B while food Q contains 4 units /kg of vitamin A and 2 units /kg of vitamin B. Determine the minimum cost of the mixture?

Solution:

Let the mixture contain x kg of food P and y kg of food Q.

Hence, x ≥ 0 and y ≥ 0

The given information can be compiled in a table as given

The mixture must contain at least 8 units of vitamin A and 11 units of vitamin B. Hence, the constraints are

3x + 4y ≥ 8

5x + 2y ≥ 11

Total cost of purchasing food is, Z = 60x + 80y

So, the mathematical formulation of the given problem can be written as

Minimise Z = 60x + 80y (i)

Now, subject to the constraints,

3x + 4y ≥ 8 … (2)

5+ 2y ≥ 11 … (3)

xy ≥ 0 … (4)

The feasible region determined by the system of constraints is given below

Clearly, we can see that the feasible region is unbounded

A (8 / 3, 0), B (2, 1 / 2) and C (0, 11 / 2)

The values of Z at these corner points are given below

Here the feasible region is unbounded, therefore, 160 may or may not be the minimum value of Z.

For this purpose, we graph the inequality, 60x + 80y < 160 or 3x + 4y < 8, and check whether the resulting half plane has points in common with the feasible region or not

Here, it can be seen that the feasible region has no common point with 3x + 4y < 8

Hence, at the line segment joining the points (8 / 3, 0) and (2, 1 / 2), the minimum cost of the mixture will be Rs 160

 

Transportation problems

These problems involve the transportation of manufactured goods efficiently to different places such that the transportation cost is minimum. For big companies, the analysis of transportation cost is very much important as it caters to a widespread area.

Example: Two godowns A and B have grain capacity of 100 quintals and 50 quintals respectively. They supply to 3 ration shops, D, E and F whose requirements are 60, 50 and 40 quintals respectively. The cost of transportation per quintal from the godowns to the shops are given in the following table:

How should the supplies be transported in order that the transportation cost is minimum? What is the minimum cost?

Solution:

Let godown A supply x and y quintals of grain to the shops D and E

So, (100 – x – y) will be supplied to shop F.

Since, x quintals are transported from godown A, so the requirement at shop D is 60 quintals. Hence, the remaining (60 – x) quintals will be transported from godown B.

Similarly, (50 – y) quintals and 40 – (100 – x – y) = (x + y – 60) quintals will be transported from godown B to shop E and F

The given problem can be represented diagrammatically as given below

x ≥ 0, y ≥ 0, and 100 – x – y ≥ 0

Then, x ≥ 0, y ≥ 0, and x + y ≤ 100

60 – x ≥ 0, 50 – y ≥ 0, and x + y – 60 ≥ 0

Then, x ≤ 60, y ≤ 50, and x + y ≥ 60

Total transportation cost z is given by,

z = 6x + 3y + 2.5 (100 – x – y) + 4 (60 – x) + 2 (50 – y) + 3 (x + y – 60)

= 6x + 3y + 250 – 2.5x – 2.5y + 240 – 4x + 100 – 2y + 3x + 3y – 180

= 2.5x + 1.5y + 410

The given problem can be formulated as given below

Minimize z = 2.5x + 1.5y + 410 …………. (i)

Subject to the constraints,

x + y ≤ 100 ……….. (ii)

x ≤ 60 ……….. (iii)

y ≤ 50 ………. (iv)

x + y ≥ 60 ……… (v)

x, y ≥ 0 …………..(vi)

The feasible region determined by the system of constraints is given below

A (60, 0), B (60, 40), C (50, 50) and D (10, 50) are the corner points

The values of z at these corner points are given below

The minimum value of z is 510 at (10, 50)

Hence, the amount of grain transported from A to D, E and F is 10 quintals, 50 quintals and 40 quintals respectively and from B to D, E and F is 50 quintals, 0 quintals, 0 quintals respectively

Thus, the minimum cost is Rs 510

 

Example: A farmer mixes two brands P and Q of cattle feed. Brand P, costing Rs 250 per bag, contains 3 units of nutritional element A, 2.5 units of element B and 2 units of element C. Brand Q costing Rs 200 per bag contains 1.5 units of nutritional element A, 11.25 units of element B, and 3 units of element C. The minimum requirements of nutrients A, B and C are 18 units, 45 units and 24 units respectively. Determine the number of bags of each brand which should be mixed in order to produce a mixture having a minimum cost per bag? What is the minimum cost of the mixture per bag?

Solution:

Let the farmer mix x bags of brand P and y bags of brand Q respectively

The given information can be compiled in a table is given below

 

The given problem can be formulated as given below

Minimize z = 250x + 200y ………… (i)

3x + 1.5y ≥ 18 ………….. (ii)

2.5x + 11.25y ≥ 45 ……….. (iii)

2x + 3y ≥ 24 ………….. (iv)

x, y ≥ 0 ………. (v)

The feasible region determined by the system of constraints is given below

A (18, 0), B (9, 2), C (3, 6) and D (0, 12) are the corner points of the feasible region

The values of z at these corner points is given below

Here, the feasible region is unbounded, hence, 1950 may or may not be the minimum value of z

For this purpose, we draw a graph of the inequality, 250x + 200y < 1950 or 5x + 4y < 39, and check whether the resulting half plane has points in common with the feasible region or not

Here, it can be seen that the feasible region has no common point with 5x + 4y < 39

Hence, at point (3, 6) the minimum value of z is 1950

Therefore, 3 bags of brand P and 6 bags of brand Q should be used in the mixture to minimize the cost to Rs 1950

 

Allocation problems

The problem is to determine the optimum weekly production quantities for the products. The goal is to maximize total profit. In constructing a model, the first step is to define the decision variables; the next step is to write the constraints and objective function in terms of these variables and the problem data.

Example:

There are two types of fertilizers F1 and F2. F1 consists of 10% nitrogen and 6% phosphoric acid and F2 consists of 5% nitrogen and 10% phosphoric acid. After testing the soil conditions, a farmer finds that she needs atleast 14 kg of nitrogen and 14 kg of phosphoric acid for her crop. If F1 costs Rs 6 / kg and F2 costs Rs 5 / kg, determine how much of each type of fertilizer should be used so that nutrient requirements are met at a minimum cost. What is the minimum cost?

Solution:

Let the farmer buy x kg of fertilizer F1 and y kg of fertilizer F2. Hence,

x ≥ 0 and y ≥ 0

The given information can be compiled in a table is given below

F1 consists of 10% nitrogen and F2 consists of 5% nitrogen.

However, the farmer requires at least 14 kg of nitrogen

So, 10% of x + 5% of y ≥ 14

x / 10 + y / 20 ≥ 14

By L.C.M we get

2x + y ≥ 280

F1 consists of 6% phosphoric acid and F2 consists of 10% phosphoric acid.

However, the farmer requires at least 14 kg of phosphoric acid

So, 6% of x + 10 % of y ≥ 14

6x / 100 + 10y / 100 ≥ 14

3x + 5y ≥ 700

Total cost of fertilizers, Z = 6x + 5y

The mathematical formulation of the given problem can be written as

Minimize Z = 6x + 5y ………….. (i)

Subject to the constraints,

2x + y ≥ 280 ……… (ii)

3x + 5y ≥ 700 ………. (iii)

x, y ≥ 0 …………. (iv)

The feasible region determined by the system of constraints is given below

Here, we can see that the feasible region is unbounded.

A (700 / 3, 0), B (100, 80) and C (0, 280) are the corner points

The values of Z at these points are given below

Here, the feasible region is unbounded, hence, 1000 may or may not be the minimum value of Z.

For this purpose, we draw a graph of the inequality, 6x + 5y < 1000, and check whether the resulting half plane has points in common with the feasible region or not.

Here, it can be seen that the feasible region has no common point with 6x + 5y < 1000

Hence, 100 kg of fertilizer F1 and 80 kg of fertilizer F2 should be used to minimize the cost. The minimum cost is Rs 1000

Related Unit Name