## Page 1

1

Chapter 1 & 2

FORMULATION OF LINEAR PROGRAMMING PROBLEM

INTRODUCTION TO LINEAR PROGRAMMING

Linear Programming is a problem solving approach that has been developed to help managers

to make decisions.

Linear Programming is a mathematical technique for determining the optimum allocation of

resources and obtaining a particular objective when there are alternative uses of the resources,

money, manpower, material, machine and other facilities.

THE NATURE OF LINEAR PROGRAMMING PROBLEM

Two of the most common are:

1. The product -mix problem

2. The blending Problem

In the product - mix problem there are two or more product also called candidates or activities

competing for limited resources. The problem is to find out which products to include in

production plan and in what quantities these should be produced or sold in order to maximize

profit, market share or sales revenue.

The blending problem involves the determination of the best blend of available ingredients to

form a certain quantity of a product under st rict specifications. The best blend means the least

cost blend of the required inputs.

FORMULATION OF THE LINEAR PROGRAMMING MODEL

Three components are:

1. The decision variable

2. The environment (uncontrollable) parameters

3. The result (dependent) variable

Linear Programming Model is composed of the same components

TERMINOLOGY USED IN LINEAR PROGRAMMING PROBLEM

1. Components of LP Problem: Every LPP is composed of a. Decision Variable, b.

Objective Function, c. Constraints.

2. Optimization: Linear Programming attempts to either maximise or minimize the values of

the objective function.

3. Profit of Cost Coefficient: The coefficient of the v ariable in the objective function

express the rate at which the value of the objective function increases or decreases by

including in the solution one unit of each of the decision variable. The Decision Variable

Objective Function

The Constraints munotes.in

## Page 2

2

4. Constraints: The maximisation (or minimisation) is performed s ubject to a set of

constraints. Therefore LP can be defined as a constrained optimisation problem. They reflect

the limitations of the resources.

5. Input -Output coefficients: The coefficient of constraint variables are called the Input -

Output Coefficients . They indicate the rate at which a given resource is unitized or depleted.

They appear on the left side of the constraints.

6. Capacities: The capacities or availability of the various resources are given on the right

hand side of the constraints.

THE MA THEMATICAL EXPRESSION OF THE LP MODEL

The general LP Model can be expressed in mathematical terms as shown below:

Let

Oij = Input -Output Coefficient

Cj = Cost (Profit) Coefficient

bi = Capacities (Right Hand Side)

Xj = Decision Variables

Find a vector (x 1, x2, x3 ..........x n) that minimise or maximise a linear objective function F(x)

where F(x) = c 1x1 + c 2x2 + ................+ c nxn

subject to linear constraints

a1x1 + a 2x2 + ................+ a nxn = b 2

a1x1 + a 2x2 + ................+ a nxn ≤ b2

.......................................................

.......................................................

.......................................................

.......................................................

am1x1 + am 2x2 + ................ + am nxn ≤ b2

and non -negativity constraints

x1 ≥ 0, x2 ≥ 0, .................., xn ≥ 0

FORMULATION OF LPP

STEPS

1. Identify decision variables

2. Write objective function

3. Formulate constraints

EXAMPLE 1. (PRODUCTION ALLOCATION PROBLEM)

A firm produces three products. These products are processed on three different machines.

The time required to manufacture one unit of each of the three products and the daily capacity

of the three machines are given in the table below:

Machine Time per u nit (Minutes) Machine Capacity

(minutes/day) Product 1 Product 2 Product 3

M1 2 3 2 440

M2 4 - 3 470

M3 2 5 - 430 munotes.in

## Page 3

3

It is required to determine the daily number of units to be manufactured for each product. The

profit per unit for product 1, 2 and 3 is Rs. 4, Rs.3 and Rs.6 respectively. It is assumed that all

the amounts produced are consumed in the market. Formulate the mathematical (L.P.) model

that will maximise the daily profit.

Formulation of Linear Programming Model

Step 1

From the study of the situation find the key -decision to be made. In the given situation key

decision is to decide the extent of products 1, 2 and 3, as the extents are permitted to vary.

Step 2

Assume symbols for variable quantities noticed in step 1. Let the extents (amounts) of

products 1, 2 and 3 manufactured daily be x 1, x2 and x 3 units respectively.

Step 3

Express the feasible alternatives mathematically in terms of variable. Feasible alternatives are

those which are physically, economically and financial ly possible. In the given situation

feasible alternatives are sets of values of x 1, x2 and x 3 units respectively.

where x1, x2 and x 3 ≥ 0.

since negative production has no meaning and is not feasible.

Step 4

Mention the objective function quantitatively a nd express it as a linear function of variables.

In the present situation, objective is to maximize the profit.

i.e., Z = 4x 1+ 3x 2 + 6x 3

Step 5

Put into words the influencing factors or constraints. These occur generally because of

constraints on availability (resources) or requirements (demands). Express these constraints

also as linear equations/inequalities in terms of variables.

Here, constraints are on the machine capacities and can be mathematically expressed as

2x1+ 3x 2 + 2x 3 ≤ 440

4x1+ 0x 2 + 3x 3 ≤ 470

2x1+ 5x 2 + 0x 3 ≤ 430

EXAMPLE 2: PRODUCT MIX PROBLEM

A factory manufactures two products A and B. To manufacture one unit of A, 1.5 machine

hours and 2.5 labour hours are required. To manufacture product B, 2.5 machine hours and

1.5 labour hours are required. In a month, 300 machine hours and 240 labour hours are

available.

Profit per unit for A is Rs. 50 and for B is Rs. 40. Formulate as LPP.

Solution :

Products Resource/unit

Machine Labour

A 1.5 2.5

B 2.5 1.5

Availability 300 hrs 240 hrs

There will be two constraints. One for machine hours availability and for labour hours

availability.

Decision variables munotes.in

## Page 4

4

X1 = Number of units of A manufactured per month.

X2 = Number of units of B manufactured per month.

The objective function:

Max Z = 50x 1+ 40x 2

Subjective Constraints

For machine hours

1.5x 1+ 2.5x 2 ≤ 300

For labour hours

2.5x 1+ 1.5x 2 ≤ 240

Non negativity

x1, x2 ≥0

EXAMPLE: 3

A company produces three products A, B, C.

For manufacturing three raw materials P, Q and R are used.

Profit per unit

A - Rs. 5, B - Rs. 3, C - Rs. 4

Resource requirements/unit

Raw Material

Product P Q R

A - 20 50

B 20 30 -

C 30 20 40

Maximum raw material availability:

P - 80 units; Q - 100 units; R - 150 units. Formulate LPP.

Solution:

Decision variables:

x1 = Number of units of A

x2 = Number of units of B

x3 = Number of units of C

Objective Function

Since Profit per unit is given, objective function is maximisation

Max Z = 5x 1+ 3x 2 + 4x 3

Constraints :

For P:

0x1+ 20x 2 + 30x 3 ≤ 80

For Q:

20x 1+ 30x 2 + 20x 3 ≤ 100

For R:

50x 1+ 0x 2 + 40x 3 ≤ 150

(for B, R is not required)

X1, X 2, X3 ≥ 0

EXAMPLE 4: PORTFOLIO SELECTION (INVESTMENT DECISIONS)

An investor is considering investing in two securities 'A' and 'B'. The risk and return

associated with these securities is different. munotes.in

## Page 5

5

Security 'A' gives a return of 9% and has a risk factor of 5 on a scale of zero to 10. Security

'B' gives return of 15% but has risk factor of 8.

Total amount to be invested is Rs. 5, 00, 000/ - Total minimum returns on the investment

should be 12%. Maximum combined risk should not be more than 6. Formulate as LPP.

Solution:

Decision Variables:

X1 = Amount invested in Security A

X2 = Amount invested in Security B

Objective Function:

The objectiv e is to maximise the return on total investment.

⸫ Max Z = 0.09 X 1 + 0.015 X2 ((% = 0.09, 15% = 0.15)

Constraints:

1. Related to Total Investment:

X1 + X 2 = 5, 00, 000

2. Related to Risk:

5X1 + 8X 2 = (6 X 5, 00, 000)

5X1 + 8X 2 = 30, 00, 000

3. Related to Returns:

0.09X 1 + 0.15X 2 = (0.12 X 5, 00, 000)

⸫0.09X 1 + 0.15X 2 = 60, 000

4. Non -negativity

X1, X2 ≥ 0

EXAMPLE 5: INSPECTION PROBLEM

A company has two grades of inspectors, I and II to undertake quality control inspection. At

least 1, 500 pieces must be inspected in an 8 -hour day. Grade I inspector can check 20 pieces

in an hour with an accuracy of 96%. Grade II inspector checks 14 piec es an hour with an

accuracy of 92%.

Wages of grade I inspector are Rs. 5 per hour while those of grade II inspector are Rs. 4 per

hour. Any error made by an inspector costs Rs. 3 to the company. If there are, in all, 10 grade

I inspectors and 15 grade II i nspectors in the company, find the optimal assignment of

inspectors that minimise the daily inspection cost.

Solution:

Let x 1 and x 2 denote the number of grade I and grade II inspectors that may be assigned the

job of quality control inspection.

The objective is to minimise the daily cost of inspection. Now the company has to incur two

types of costs; wages paid to the inspectors and the cost of their inspection errors. The cost of

grade I inspector/hour is

Rs. (5 + 3 X 0.04 X 20) = Rs. 7.40.

Simila rly, cost of grade II inspector/hour is

Rs. (4 + 3 X 0.08 X 14) = Rs. 7.36.

⸫ The objective function is

minimise Z = 8(7.40x 1 + 7.36x 2) = 59.20 x1 + 58.88x 2.

Constraints are

on the number of grade I inspectors: x 1 ≤ 10, munotes.in

## Page 6

6

on the number of grade II inspect ors: x 2 ≤ 15

on the number of pieces to be inspected daily: 20 x 8x 1 + 14 x 8x 2 ≥ 1500

or 160x 1 + 112x 2 ≥ 1500

where, x 1, x2 ≥ 0.

EXAMPLE 6: TRIM LOSS PROBLEM

A manufacturer of cylindrical containers receives tin sheets in widths of 30 cm and 60 cm

respectively . For these containers the sheets are to be cut to three different widths of 15 cm,

21 cm and 27 cm respectively. The number of containers to be manufactured from these three

widths are 400, 200 and 300 respectively. The bottom plates and top covers of the containers

are purchased directly from the market. There is no limit on the lengths of standard tin sheets.

Formulate the LPP for the production schedule that minimises the trim losses.

Solution:

Key decision is to determine how each of the two standard widths of tin sheets be cut to the

require widths so that trim losses are minimum.

From the available widths of 30 cm and 60 cm, several combinations of the three required

widths of 15 cm, 21 cm and 27 cm are possible.

Let x ij represent these combinations. Each combination results in certain trim loss.

Constraints can be formulated as follows:

The possible cutting combinations (plans) for both types of sheets are shown in the table

below:

Width

(cm) i = I (30 cm) i = II (60 cm)

X11 X12 X13 X21 X22 X23 X24 X25 X26

15 2 0 0 4 2 2 1 0 0

21 0 1 0 0 1 0 2 1 0

27 0 0 1 0 0 1 0 1 2

Trim Loss

(cm) 0 9 3 0 9 3 3 12 6

Thus, the constraints are

2x11 + 4x 21 + 2x 22 + 2x 23 + x 24 ≥ 400

x12 + x 22 + 2x 24 + x 25 ≥ 200

x13 +x23 + x25 + x 26 ≥ 300

Objective is to maximise the trim losses.

i.e., minimise Z = 9x 12 + 3x 13 + 9x 22 + 3x 23 + 3x 24 + 12x 25 + 6x 26

where x 11, x12, x13, x21, x22, x23, x24, x25, x26 ≥ 0.

EXAMPLE 7: MEDIA SELECTION

An advertising agency is planning to launch an ad campaign. Media under consideration are

T.V., Radio & Newspaper. Each medium has different reach potential and different cost.

Minimum 10, 000, 000 households are to be reached through T.V. Expenditure on

newspapers should not be more than Rs. 10, 00, 000. Total advertising budget is Rs. 20

million.

Following data is available:

Medium Cost per Unit

(Rs.) Reach per unit

(No. of households)

Television 2, 00, 000 20, 00, 000 munotes.in

## Page 7

7

Radio 80, 000 10, 00, 000

Newspaper 40, 000 2, 00, 000

Solution:

Decision Variables:

x1 = Number of units of T.V. ads,

x2 = Number of units of Radio ads,

x3 = Number of units of Newspaper ads.

Objective function: (Maximise reach)

Max. Z = 20, 00, 000 x 1 + 10, 00, 000 x 2 + 2, 00, 000x 3

Subject to constraints:

20, 00, 000 x 1 ≥ 10, 000, 000 ........ (for T.V.)

40, 000 x 3 ≤ 10, 00, 000 ........... (for Newspaper)

2, 00, 000x 1 + 80, 000x 2 + 40, 000x 3 ≤ 20, 000, 000 .......... (Ad. budget)

x1, x2, x3 ≥ 0

⸫ Simplifying constraints:

for T.V. 2 x1 ≥ 10 ⸫ x1 ≥ 5

for Newspaper 4 x3 ≤ 100 ⸫ x3 ≤ 25

Ad. Budget

20 x1 + 8 x2 + 4 x3 ≤ 2000

5 x1 + 2x 2 + x 3 ≤ 500

x1, x2, x3 ≥ 0

EXAMPLE 8: DIET PROBLEM

Vitamins B 1 and B 2 are found in two foods F 1 and F 2. 1 unit of F 1 contains 3 units of B 1 and 4

units of B 2. 1 unit of F 2 contains 5 units of B 1 and 3 units of B 2 respectively.

Minimum daily prescribed consumption of B 1 & B 2 is 50 and 60 units respectively. Cost per

unit of F 1 & F 2 is Rs. 6 & Rs. 3 respectively.

Formulate as LPP.

Solution:

Vitamins Foods Minimum

Consumption F1 F2

B1 3 5 30

B2 5 7 40

Decision Variables:

x1 = No. of units of P 1 per day.

x2 = No. of units of P 2 per day.

Objective function:

Min. Z = 100 x1 + 150 x2

Subject to constraints:

3x1+ 5x 2 ≥ 30 (for N 1)

5x1+ 7x 2 ≥ 40 (for N 2)

x1, x2 ≥ 0

EXAMPLE 9: BLENDING PROBLEM

A manager at an oil company wants to find optimal mix of two blending processes.

Formulate LPP. munotes.in

## Page 8

8

Data:

Process Input (Crude Oil) Output (Gasoline)

Grade A Grade B X Y

P1 6 4 6 9

P2 5 6 5 5

Profit per operation: Process 1 (P 1) = Rs. 4, 000

Process 2 (P 2) = Rs. 5, 000

Maximum availability of crude oil: Grade A = 500 units

Grade B = 400 units

Minimum Demand for Gasoline: X = 300 units

Y = 200 units

Solution:

Decision Va riables:

x1 = No. of operations of P 1

x2 = No. of operations of P 2

Objective Function:

Max. Z = 4000 x1 + 5000 x2

Subjective to constraints:

6x1+ 5x 2 ≤ 500

4x1+ 6x 2 ≤ 400

6x1+ 5x 2 ≥300

9x1+ 5x 2 ≥200

x1, x2 ≥ 0

EXAMPLE 10: FARM PLANNING

A farmer has 200 acres of land. He produces three products X, Y & Z. Average yield per acre

for X, Y & Z is 4000, 6000 and 2000 kg.

Selling price of X, Y & Z is Rs. 2, 1.5 & 4 per kg respectively. Each product needs fertilizers.

Cost of fertilizer is Rs. 1 p er kg. Per acre need for fertilizer for X, Y & Z is 200, 200 & 100

kg respectively. Labour requirements for X, Y & Z is 10, 12 & 10 man hours per acre. Cost

of labour is Rs. 40 per man hour. Maximum availability of labour is 20, 000 man hours.

Formulate as LPP to maximise profit.

Solution:

Decision variables:

The production/yield of three products X, Y & Z is given as per acre.

Hence,

x1 = No. of acres allocated to X

x2 = No. of acres allocated to Y

x3 = No. of acres allocated to Z

Objective Function:

Profit = Revenue - Cost

Profit = Revenue - (Fertiliser Cost + Labour Cost)

Product X Y Z

Revenue 2 (4000) x 1 1.5 (6000) x 2 4 (2000) x 3

(-) Less: munotes.in

## Page 9

9

Fertiliser Cost 1 (200) x 1 1 (200) x 2 1 (100) x 3

Labour Cost 40 (10) x 1 40 (12) x 2 40 (10) x 3

Profit 7400 x 1 8320 x 2 7500 x 3

⸫ Objective function

Max. = 7400 x 1 + 8320 x 2 + 7500 x 3

Subject to constraints:

x1 + x2 + x3 = 200 (Total Land)

10 x1 + 12 x2 + 10 x3 ≤ 20, 000 (Max Man hours)

x1, x2, x3 ≥ 0

MERITS OF LPP

1. Helps management to make efficient use of resources.

2. Provides quality in decision making.

3. Excellent tools for adjusting to meet changing demands.

4. Fast determination of the solution if a computer is used.

5. Provides a natural sensitivity analysis.

6. Finds solution to problems with a very large or infinite number of possible solution.

DEMERITS OF LPP

1. Existence of non -linear equation: The primary requirements of Linear Programming is

the objective function and constraint function should be linear . Practically linear relationship

do not exist in all cases.

2. Interaction between variables: LP fails in a situation where non -linearity in the equation

emerge due to joint interaction between some of the activities like total effectiveness.

3. Fractiona l Value: In LPP fractional values are permitted for the decision variable.

4. Knowledge of Coefficients of the equation: It may not be possible to state all coefficients

in the objective function and constraints with certainty.

munotes.in

## Page 10

10

EXERCISES

1. Explain what is meant by decision variables, objective function and constraints in Linear

Programming.

2. Give the mathematical formulation of the linear programming problems.

3. What are the components of LPP? What is the significance of non -negativity restriction?

4. State the limitations of LPP.

5. Give the assumptions and advantages of LPP.

6. An investor wants to identify how much to invest in two funds, one equity and one debt.

Total amount available is Rs. 5, 00, 000. Not more than Rs. 3 , 00, 000 should be invested in a

single fund. Returns expected are 30% in equity and 8% in debt. Minimum return on total

investment should be 15%. Formulate as LPP.

7. A company manufactures two products P 1 and P 2. Profit per unit for P 1 is Rs. 200 and fo r

P2 is Rs. 300. Three raw materials M 1, M2 and M 3 are required. One unit of P 1 needs 5 units of

M1 and 10 units of M 2. One unit of P 2 needs 18 units of M 2 and 10 units of M 3. Availability is

50 units of M 1, 90 units of M 2 and 50 units of M 3. Formulate as LPP.

8. A firm produces two products X and Y. Minimum 50 units of X should be produced. There

is no limit for producing Y. Profit per unit is Rs. 100 for X and Rs. 150 for Y.

Product Resource Requirement Resource Availability

X 20 Machine Hours Mach ine Hours = 2500

10 Labour Hours Labour Hours = 3000

Y 10 Machine Hours

15 Labour Hours

Formulate as LPP.

9. A patient has been recommended two nutrients N 1 and N 2 everyday. Minimum intake is

10g for N 1 and 15g for N 2 everyday.

These nutrients ar e available in two products P 1 and P 2. One unit of P 1 contains 2g of N 1 and

3g of N 2. One unit of P 2 contains 1g of N 1 and 2g of N 2. Cost per unit is Rs. 200 for P 1 and

Rs. 150 for P 2.

Formulate as LPP such that nutrient requirement can be fulfilled at the lowest cost.

10. Two vitamins A and B are to be given as health supplements on daily basis to students.

There are two products Alpha & Beta which contain vitamins A and B. One unit of Alpha

contains 2g of A and 1g of B. One unit of Beta contains 1g of A a nd 2g of B. Daily

requirements for A and B are atleast 10g each. Cost per unit of Alpha is Rs. 20 and of Beta is

Rs. 30. Formulate as LPP to satisfy the requirements at minimum cost.

------ xxx------ xxx----- munotes.in

## Page 11

1

UNIT 3

LINEAR PROGRAMMING SOLUTION - GRAPHICAL METHOD

INTRODUCTION

There are two methods available to find optimal solution to a Linear Programming Problem.

One is graphical method and the other is simplex method.

Graphical method can be used only for a two variables problem i.e. a problem which involves

two decision variables. The two axes of the graph (X & Y axis) represent the two decision

variables X 1 & X 2.

METHODOLOGY OF GRAPHICAL METHOD

Step 1: Formulation of LPP (Linear Programming Problem)

Use th e given data to formulate the LPP.

Maximisation

Example 1

A company manufactures two products A and B. Both products are processed on two

machines M 1 & M 2.

M1 M2

A

B 6 Hrs/Unit

4 Hrs/Unit 2 Hrs/Unit

4 Hrs/Unit

Availability 7200 Hrs/month 4000 Hrs/month

Profit per unit for A is Rs. 100 and for B is Rs. 80. Find out the monthly production of A and

B to maximise profit by graphical method.

Formulation of LPP

X1 = No. of units of A/Month

X2 = No. of units of B/Month

Max Z = 100 X1 + 80 X2

Subject to constraints:

6 X1 + 4 X2 ≤ 7200

2 X 1 + 4 X2 ≤ 4000

X1, X2 ≥ 0

Step 2: Determination of each axis

Horizontal (X) axis: Product A ( X1)

Vertical (Y) axis: Product B (X 2)

Step 3: Finding co -ordinates of constraint lines to represent constraint lines on the

graph.

The constraints are presently in the form of inequality ( ≤). We should convert them into

equality to obtain co -ordinates.

Constraint No. 1: 6 X 1 + 4 X 2 ≤ 7200

Converting into equality:

6 X1 + 4 X2 ≤ 7200

X1 is the intercept on X axis and X 2 is the intercept on Y axis.

To find X 1, let X 2 = 0

6 X1 = 7200 munotes.in

## Page 12

2

6 X1 = 7200 ⸫ X1 = 1200; X 2 = 0 (1200, 0)

To find X 2, let X 1 = 0

4 X2 = 7200 X2 = 1800; X 1 = 0 (0, 1800)

Hence the two points which make the constraint line are:

(1200, 0) and (0, 1800)

Note: When we write co -ordinates of any point, we always write (X 1, X2). The value of X 1 is

written first and then value of X 2. Hence, if for a point X 1 is 1200 and X 2 is zero, then its co -

ordinates will be (1200, 0).

Similarly, for second point, X 1 is 0 and X 2 is 1800. Hence, its co -ordinates are (0, 1800).

Constraint No. 2:

2 X 1 + 4 X2 ≤ 4000

To find X1, let X2 = 0

2 X 1 = 4000 ⸫ X1 = 2000; X 2 = 0 (2000, 0)

To find X2, let X1 = 0

4 X2 =4000 ⸫ X2 = 1000; X 1 = 0 (0, 1000)

Each constraint will be represented by a single straight line on the graph. There are two

constraints, hence there will be two straight lines.

The co -ordinates of points are:

1. Constraint No. 1: (1200, 0) and (0, 1800)

2. Constraint No. 2: (2000, 0) and (0, 1000)

Step 4: Representing constraint lines on graph

To mark the points on the graph, we need to select appropriate scale. Which scale to take will

depend on maximum value of X1 & X 2 from co -ordinates.

For X 1, we have 2 values 1200 and 2000

⸫Max. value for X 2 = 2000

For X 2, we have 2 values 1800 and 1000

⸫Max. value for X 2 = 1800

Assuming that we have a graph paper 20 X 30 cm. We need to accommodate our lines such

that for X -axis, maximum value of 2000 contains in 20 cm.

⸫ Scale 1 cm = 200 units

⸫ 2000 units = 10 cm (X-axis)

1800 units = 9 cm (Y-axis)

The scale should be such that the diagram should not be too small.

Constraint No. 1:

The line joining the two points (1200, 0) and (0, 1800) represents the constraint

6 X1 + 4 X2 ≤ 7200.

munotes.in

## Page 13

3

Fig 1.

(0, 1800) 6 X1 + 4 X2 ≤ 7200.

(1200, 0)

Every point on the line will satisfy the equation (equality) 6 X1 + 4 X2 ≤ 7200.

Every point below the line will satisfy the inequality (less than) 6 X1 + 4 X2 ≤ 7200.

Constraint No. 2:

The line joining the two points (2000, 0) and (0, 1000) represents the constraint

2 X 1 + 4 X2 ≤ 4000

Every point on the line will satisfy the equation (equality) 2 X 1 + 4 X2 ≤ 4000.

Every point below the line will satisfy the inequality (less than) 2 X 1 + 4 X2 ≤ 4000 .

Fig 2

(0, 1000)

2 X 1 + 4 X2 ≤ 4000.

(2000, 0)

Now the final graph will look like this:

munotes.in

## Page 14

4

(0, 1800) Fig. 3

(0, 1000) 6 X1 + 4 X2 ≤ 7200 Feasible region: OABC

2 X 1 + 4 X2 ≤ 4000.

(1200, 0) (2000, 0)

Step 5: Identification of Feasible Region

The feasible region is the region bounded by constraint lines. All points inside the feasible

region or on the boundary of the feasible region or at the corner of the feasible region satisfy

all constraints.

Both the constraints are 'less than or equal to' ( ≤) type. H ence, the feasible region should be

inside both constraint lines.

Hence, the feasible region is the polygon OABC. 'O' is the origin whose coordinates are (0,

0). O, A, B and C are called vertices of the feasible region.

Fig 3 Scale 1 cm = 200 units

(0, 1800)

(0, 1000) A 6 X1 + 4 X2 ≤ 7200

B

2 X 1 + 4 X2 ≤ 4000

O (1200, 0) C (2000, 0)

Step 6: Finding the optimal Solution

The optimal solution always lies at one of the vertices or corners of the feasible region.

To find optimal solution:

We use corner point method. We find coordinates (X1, X2 Values) for each vertex or corner

point. From this we fine 'Z' value for each corner point.

Vertex Co-ordinates Z = 100 X 1 + 80 X 2

O X1 = 0, X 2 = 0

From Graph Z = 0

A X1 = 0, X 2 = 1000

From Graph Z = Rs. 80, 000 munotes.in

## Page 15

5

B X1 = 800, X 2 = 600

From Simultaneous equations Z = Rs. 1, 28, 000

C X1 = 1200, X 2 = 0

From Graph Z = Rs. 1, 20, 000

Max. Z = Rs. 1, 28, 000 (At point B)

For B B is at the intersection of two constraint lines 6 X1 + 4 X2 ≤ 7200 and 2 X 1 + 4

X2 ≤ 4000. Hence, values of X1 and X 2 at B must satisfy both the equations.

We have two equations and two unknowns, X 1 and X 2. Solving simultaneously.

6 X1 + 4 X2 ≤ 7200 (1)

2 X 1 + 4 X2 ≤ 4000 (2)

4 X1 = 3200 Subtracting (2) from (1)

X1 = 800

Substituting value of X 1 in equation (1), we get

4 X2 = 2400 ⸫ X2 = 600

Solution

Optimal Profit = Max Z = Rs. 1, 28, 000

Product Mix:

X1 = No. of units of A / Month = 800

X2 = No. of units of A / Month = 600

ISO Profit line:

ISO profit line is the line which passes through the points of optimal solution (Maximum

Profit). The slope of the iso -profit line depends on the objective function.

In the above example, the objective function is:

Max. Z = 100 X 1 + 80 X2

How to find slop e of iso -profit line:

Equation of a straight line: y = mx + c

where, m = slope of the straight line

In our case, y means ' X2' and x means ' X1'.

c means 'Z' .

⸫ X2 = m . X 1 + Z

Converting original objective function in this format:

Max. Z = 100 X 1 + 80 X2

⸫ 80 X2 = Z - 100 X 1 = - 100 X 1 + Z

⸫ X2 = −100

80X1 + 𝑍

80

⸫ X2 = −5

4X1 + 𝑍

80

⸫ Slope of ISO profit line = −5

4

Negative sign indicates that the line will slope from left to right downwards. And slope will

be 5/4. Every 4 units on X -axis for 5 units on Y-axis.

munotes.in

## Page 16

6

Slope of ISO - profit line

S Direction away from Origin for Profit

Maximisation

4

As we start from the origin and go away from origin to maximise profit, 'B' is the last point

on the feasible region that is intersected by the iso -profit line. Hence, B is the optimal

solution.

MINIMISATION

Example 2

A firm is engaged in animal breeding. The animals are to be given nutrition supplements

everyday. There are two products A and B which contain the three required nutrients.

Nutrients Quantity/unit Minimum Requirement

A B

1

2

3 72

6

40 12

24

20 216

72

200

Product cost per unit are: A: rs. 40; B: Rs. 80. Find out quantity of product A & B to be given

to provide minimum nutritional requirement.

Step 1: Formulation as LPP

X1 - Number of units of A

X2 - Number of units of B

Z - Total Cost

Min. Z = 40 X1 + 80 X2

Subject to constraints:

72 X1 + 12 X2 ≥ 216

6 X1 + 24 X2 ≥ 72

40 X1 + 20 X2 ≥ 200

X1, X 2 ≥ 0.

Step 2: Determination of each axis

Horizontal (X) axis: Product A ( X1)

Vertical (Y) axis: Product B (X 2)

Step 3: Finding co -ordinates of constraint lines to represent the graph

All constraints are 'greater than or equal to' type. We should convert them into equality:

1. Constraint No. 1: 72 X1 + 12 X2 ≥ 216

Converting into equality munotes.in

## Page 17

7

72 X1 + 12 X2 = 216

To find X1, let X 2 = 0

72 X1 = 216 ⸫ X1 = 3, X 2 = 0 (3, 0)

To find X 2, let X 1 = 0

12 X2 = 216 ⸫ X1 = 0, X 2 = 18 (0, 18)

2. Constraint No. 2:

6 X1 + 24 X2 ≥ 72

To find X1, let X 2 = 0

6 X1 = 72 ⸫ X1 = 12, X 2 = 0 (12, 0)

To find X 2, let X 1 = 0

24 X2 = 72 ⸫ X1 = 0, X 2 = 3 (0, 3)

3. Constraint No. 3:

40 X1 + 20 X2 ≥ 200

To find X1, let X 2 = 0

40 X1 = 200 ⸫ X1 = 5, X2 = 0 (5, 0)

To find X 2, let X 1 = 0

20 X2 = 200 ⸫ X1 = 0, X 2 = 10 (0, 10)

The co -ordinates of points are:

1. Constraint No. 1: (3, 0) & (0, 18)

2. Constraint No. 2: (12, 0) & (0, 3)

3. Constraint No. 3: (5, 0) & (0, 5)

Every point on the line will satisfy the equation (equality) 72 X1 + 12 X2 = 216.

Every point above the line will satisfy the ineq uality (greater than) 72 X1 + 12 X2 = 216.

Similarly, we can draw lines for other two constraints.

Step 5: Feasible Region

(0, 18) A 72 X1 + 12 X2 = 216 Feasible Region

40 X1 + 20 X2 ≥ 200

(0, 10)

B

6 X1 + 24 X2 ≥ 72

(0, 3) C

D

(3, 0) (5, 0) (10, 0)

All constraints are greater than or equal to ( ≥) type. Hence, feasible region should be above

(to the right of) all constraints.

The vertices of the feasible region are A, B, C & D. munotes.in

## Page 18

8

Step 6: Finding the optimal solution

Corner Point Method

Vertex Co-ordinates Z = 40 X 1 + 80 X 2

A X1 = 0, X 2 = 18

From Graph ⸫ Z = 1, 440

B X1 = 2, X 2 = 6

From Simultaneous Equations ⸫ Z = 560

C X1 = 4, X 2 = 2

From Simultaneous Equations ⸫ Z = 320

D X1 = 12, X 2 = 0

From graph ⸫ Z = 480

⸫ Min. Z = Rs. 320 (At point 'C')

For B - Point B is at intersection of constraint lines ' 72 X1 + 12 X2 ≥ 216' and '40 X1 + 20 X2

≥ 200'. Hence, point B should satisfy both the equations.

72 X1 + 12 X2= 216 (1)

40 X1 + 20 X2 = 200 (2)

⸫360 X1 + 60 X2 = 1080 (1) x 5

120 X1 + 60 X2 = 600 (2) x 3

⸫ 240 X1 = 480

X1 = 2

Substituting value of X 1 in equation (1), we get:

12 X2= 216 - 144 = 72

X2= 6

For C - Point C is at intersection of constraint lines ' 6 X1 + 24 X2= 72' and '40 X1 + 20 X2 =

200'. Hence, point C should satisfy both the equations.

6 X1 + 24 X2= 72 (1)

40 X1 + 20 X2 = 200 (2)

30 X1 + 120 X2 = 360 (1) x 5

240 X1 + 120 X2 = 1200 (2) x 6

210 X1 = 840

X1 = 4

Substituting value of X 1 in equation (1), we get

24 X2= 72 - 24 = 48

X2= 2

Solution

Optimal Cost = Z min = Rs. 320

Optimal Product Mix:

X1 = No. of units of product A = 4

X2 = No. of units of product B = 2

ISO Cost Line

ISO Cost line passes through the point of optimal solution (Minimum cos t)

Objective function: Z = 40 X1 + 80 X2

Equation of straight line: y = mx + c

where m = slope munotes.in

## Page 19

9

In this case, y is X2 & x is X 1

Z = 40 X1 + 80 X2

⸫ 80 X2 = - 40 X1 + Z

⸫ X2 = -1/2x 1 + Z/80

⸫ Slope of ISO -cost line = -1/2

Sloping from left to right downwards

Slope of ISO -cost line

Direction for minimisation

⸫ Point C is the nearest to the origin.

MAXIMISATION -MIXED CONSTRAINTS

Example 1

A firm makes two products P 1 & P 2 and has production capacity of 18 tonnes per day. P 1 &

P2 require same production capacity. The firm must supply at least 4 t of P 1 & 6 t of P 2 per

day. Each tonne of P 1 & P 2 requires 60 hours of machine work each. Maximum machine

hours available are 720. Profit per tonne for P 1 is Rs. 160 & P 2 is Rs. 240. Find optimal

solution by graphical method.

LPP Formulation

X1 = Tonnes of P 1 / Day

X2 = Tonnes of P 2 / Day

Max. Z = 160 X 1 + 240 X 2

Subject to constraints

X1 ≥ 4

X2 ≥ 6

X1 + X 2 ≤ 18

60 X 1 + 60 X 2 ≤ 720

X1, X2 ≥ 0

Coordinates for constraint lines:

1. X 1 ≥ 4 (4, 0) .... No value for X 2, ⸫ X2 = 0

2. X 2 ≥ 6 (0, 6) .... No value for X 1, ⸫ X1 = 0

3. X 1 + X 2 ≤ 18 (18, 0) (0, 18)

4. 60 X 1 + 60 X 2 ≤ 720 (12, 0) (0, 12)

If X 1 = 0, 60 X 2 = 720 ⸫ X2 = 12 (0, 12) munotes.in

## Page 20

10

If X 2 = 0, 60 X 1 = 720 ⸫ X1 = 12 ( 12, 0)

Graph: X 1: X Axis

X2: Y Axis

Scale:

Maximum value for X 1 = 18; Maximum value for X 2 = 18; ⸫ Scale: 1 cm = 2 Tonnes.

(0, 18) X1 ≥ 4

X1 + X 2 ≤ 18

(0, 12)

60 X 1 + 60 X 2 ≤ 720

A

(0, 6) B C X2 ≥ 6

(0, 0) (4, 0) (12, 0) (18, 0)

Two constraints are 'greater than or equal to' type. Hence, feasible region will be above or to

the right of these constraint lines. Two constraints are 'less than or equal to' type. Hence,

feasible region will be below or to the left of these constraint lines. Hence, feasible region is

ABC.

Optimal Solution

Corner Point Method

Vertex Coordinates Z = 160 X 1 + 240 X 2

A X1 = 4, X 2 = 8

Simultaneous Equation ⸫ Z = Rs. 2, 560

B X1 = 4, X 2 = 6

From Graph ⸫ Z = Rs. 2, 080

C X1 = 6, X 2 = 6

Simultaneous Equations ⸫ Z = Rs. 2, 400

For A X1 = 4 from graph

A is on the line 60 X 1 + 60 X 2 = 720

60 X 2 = 720 - 60 (4) = 480 ⸫ X2 = 8

For C X2 = 6 from graph

A is on the line 60 X 1 + 60 X 2 = 720

60 X 1 = 720 - 60 (6) = 360 ⸫ X1 = 6

⸫ Z = Rs. 2, 560 (At point 'A')

Solution

Optimal Profit Z. Max = Rs. 2, 560

X1 = Tonnes of P 1 = 4 tonnes

X2 = Tonnes of P 2 = 8 tonnes.

munotes.in

## Page 21

11

MINIMISATION MIXED CONSTRAINTS

Example 1:

A firm produces two products P and Q. Daily production upper limit is 600 units for total

production. But at least 300 total units must be produced every day. Machine hours

consumption per unit is 6 for P and 2 for Q. At least 1200 machine hours must be used daily.

Manufacturing costs per unit are R s. 50 for P and Rs. 20 for Q. Find optimal solution for the

LPP graphically.

LPP formulation

X1 = No. of Units of P / Day

X2 = No. of Units of Q / Day

Min. Z = 50 X 1 + 20 X 2

Subject to constraints

X1 + X 2 ≤ 600

X1 + X 2 ≥ 300

6 X 1 + 2 X 2 ≥ 1200

X1, X2 ≥ 0

Coordinates for Constraint lines

1. X 1 + X 2 = 600

If X 1 = 0, X 2 = 600 ⸫ (0, 600 )

If X 2 = 0, 60 X 1 = 600 ⸫ (600, 0)

2. X 1 + X 2 = 300

If X 1 = 0, X 2 = 300 ⸫ (0, 300)

If X 2 = 0, 60 X 1 = 300 ⸫ (300, 0)

3. 6 X 1 + 2 X 2 ≥ 1200

If X 1 = 0, 2X 2 = 1200 ⸫ X2 = 600 (0, 600)

If X 2 = 0, 6 X 1 = 1200 ⸫ X1 = 200 (200, 0)

Graph: X 1: X Axis

X2: Y Axis

Scale:

Maximum value for X 1 = 600; Maximum value for X 2 = 600; ⸫ Scale: 1 cm = 50 units.

Feasible region is ABCD.

(0, 600) A

X1 + X 2 = 600

(0, 300) X1 + X 2 = 300

6 X 1 + 2 X 2 ≥ 1200 B

C D

(0, 0) (200, 0) (300, 0) (600, 0) munotes.in

## Page 22

12

Two constraints are 'greater than or equal to' type. Hence, feasible region will be above or to

the right of these constraint lines. Two constraints are 'less than or equal to' type. Hence,

feasible region will be below or to the left of these constraint lines. Hence, feasible region is

ABCD.

Optimal Solution

Corner Point Method

Vertex Coordinates Z = 160 X 1 + 240 X 2

A X1 = 0, X 2 = 600

From Graph ⸫ Z = Rs. 12, 000

B X1 = 150, X 2 = 150

Simultaneous Equations ⸫ Z = Rs. 10, 500

C X1 = 300, X 2 = 0

From Graph ⸫ Z = Rs. 15, 000

D X1 = 600, X 2 = 0

From Graph ⸫ Z = Rs. 30, 000

Min. Z = Rs. 10, 500

For B - B is at intersection of two constraint lines '6 X 1 + 2 X 2 ≥ 1200' and ' X1 + X 2 = 300'.

6 X 1 + 2 X 2 ≥ 1200 (1)

X1 + X 2 = 300 (2)

2X1 + 2X 2 = 600 (2) X 2

2X1 = 600

X1 = 150

Substituting value in Equation (2), X 2 = 150.

Solution

Optimal Cost = Rs. 10, 500/ -

X1 = No. of Units of P = 150

X2 = No. of Units of P = 150.

munotes.in

## Page 23

13

EXERCISES

1. What is meant by feasible region in graphical method.

2. What is meant by 'iso -profit' and 'iso -cost line' in graphical solution.

3. Mr. A. P. Ravi wants to invest Rs. 1, 00, 000 in two companies 'A' and 'B' so as not to

exceed Rs. 75, 000 in either of the company. The company 'A' assures average return of 10%

in whereas the average return for company 'B' is 20%. The risk factor rating of company 'A' is

4 on 0 to 10 scale whereas the risk factor rating for 'B' is 9 on similar scale. As Mr. Ravi

wants to maximise his returns, he will not accept an average rate of return below 12% risk or

a risk factor above 6.

Formulate this as LPP and solve it graphically.

4. Solve the following LPP graphically and interpret the result.

Max. Z = 8X 1 + 16 X 2

Subject to:

X1 + X 2 ≤ 200

X2 ≤ 125

3X1 + 6X2 ≤ 900

X1, X2 ≥ 0

5. A furniture manufacturer makes two products - tables and chairs.

Processing of these products is done on two types of machines A and B. A chair requires 2

hours on machine type A and 6 hours on machine type B. A table requires 5 hours on

machine type A and no time on Machine type B. There are 16 hours/day available on

machine type A and 30 hours/day on machin e type B. Profits gained by the manufacturer

from a chair and a table are Rs. 2 and Rs. 10 respectively. What should be the daily

production of each of the two products? Use graphical method of LPP to find the solution.

munotes.in

## Page 24

1

CHAPTER 5

LINEAR PROGRAMMING

SYLLABUS

Linear Programming - Special Properties, Interpretation Of Final Tableau, Concept Of

Shadow Price, Concept Of Primal Dual Analysis

munotes.in

## Page 25

2

Special Cases in Linear Programming

a. Infeasible Solution (Infeasibility)

Infeasible means not possible. Infeasible solution happens when the constraints have

contradictory nature. It is not possible to find a solution which can satisfy all constraints.

In graphical method, infeasibility happens when we cannot f ind Feasible region.

Example 1:

Max. Z = 5 X 1 + 8 X 2

Subject to constraints

4 X 1 + 6 X 2 ≤ 24

4 X 1 + 8 X 2 ≤ 40

X1, X2 ≥ 0

D

B

4 X 1 + 8 X 2 ≤ 40

A C

4 X 1 + 6 X 2 ≤ 24

There is no common feasible region for line AB and CD.

Hence, solution is infeasible.

b. Unbounded Solution (Unboundedness)

Unbounded mean infinite solution. A solution which has infinity answer is called unbounded

solution.

In graphical solution, the direction wit h respect to origin is as follows:

Max Z Min. Z

away from origin towards origin

Maximisation Minimisation

Now, in a maximisation problem, if we have following feasible region:

munotes.in

## Page 26

3

Max. Z

There is no upper limit (away from origin), hence the answer will be infinity. This is called

unbounded solution.

c. Redundant Constraint (Redundancy)

A constraint is called redundant when it does not affect the solution. The feasible region does

not depend on that constraint.

Even if we remove the constraint from the solution, the optimal answer is not affected.

Example

Max. Z = 5 X 1 + 8 X 2

Subject to Constraints

3 X 1 + 2 X 2 ≤ 24

X1 + 3 X2 ≤ 12

X1 ≤ 16

X1, X2 ≥ 0

(0, 12)

(0, 4)

(8, 0) (12, 0) (16, 0)

The feasible region for the above problem is OABC. The 3rd constraint does not affect the

feasible region.

Hence, the constraint X 1 ≤ 16 is redundant constraint.

d. Alternate Optimal Solution: (Multiple Optimal Solution)

Alternate or multiple optimal solution means a problem has more than one solution which

gives the optimal answer. munotes.in

## Page 27

4

There are two or more sets of solution values which give maximum profit or minimum cost.

In graphical method, we come to know that there is optimal solution which is alternative

when:

The iso -profit or iso -cost line is parallel to one of the boundaries of feasible region (they have

the same slope value).

SPECIAL CASES IN SIMPLEX

1. Unbounded Solution

Max Z = 60 X 1 + 20X 2∆

Subject to

2 X 1 + 4X 2 ≥ 120

8 X 1 + 6X 2 ≥ 240

X1, X2 ≥ 0

Solution

Max Z = 60 X 1 + 20X 2 + 0S 1 + 0S 2 - MA 1 - MA 2

Subject to

2 X 1 + 4X 2 - S1 + A 1 = 120

8 X 1 + 6X 2 - S2 + A 1 = 240

X1, X2, S1, S2, A1, A2, ≥ 0

When we solve this LPP by simplex method, we will get the following values in 4th Simplex

Table.

Cj 60 20 0 0 - M - M R.R

C X B X1 X2 S1 S2 A1 A2

0 S2 240 0 10 - 4 1 - 60

60 X1 60 1 2 -1/2 0 - 120

Zj 60 120 - 30 0

∆ = C j - Zj 0 - 100 30 0

Max Positive C j - Zj = 30

Key Column = S 1

But there is no positive Replacement Ration R means there is an Entering variable, but there

is no outgoing variable.

Hence, the solution is unbounded or infinity.

The value of Z (Profit) keeps on increasing infinitely.

2. Infeasible Region

Max Z = 3 X 1 + 2 X 2

Subject to:

X1 + X 2 ≤ 4

2 X 1 + X 2≥ 10

X1, X2 ≥ 0

Solution

Standard Form

Max Z = 3 X 1 + 2 X 2 + 0S 1 + 0S 2 - MA 1

Subject to

X1 + X 2 + S 1 = 4 munotes.in

## Page 28

5

2 X 1 + X 2 - S2 + A 1 = 10

X1, X2, S1, S2, A1 ≥ 0

When we solve this LPP by simplex method, we will get the following values in 2nd Simplex

Table.

Cj 60 20 0 0 - M R.R

C X B X1 X2 S1 S2 A1

3 X1 4 1 1 1 0 0

- M A1 2 - 2 - 1 -1/2 - 1 1

Zj 3 3 + M 3 + 2M M - M

∆ = C j - Zj 0 - 1 - M -3 -2M - M 0

No positive ∆ value.

All C j - Zj values are either zero or negative. Hence, test of optimality is satisfied. So, the

solution appears to be optimal. But an artificial variable (A 1) is present in the basis, which has

objective function coefficient of - M (infinity).

Hence, the solution is infeasible (Not feasible).

Infeasibility occurs when there is no solution which satisfies all the constraints of the LPP.

Concept of Shadow Price

Shadow price of resource means value of one extra unit of resource. It is the maximum price

the company should pay for procuring extra resources from market. It also indicates

profitability or profit contribution of each resource (per unit).

Shadow price = 'Zi' value of slack variables.

S1 - slack variable of resource 1 and S 2 - Slack Variable of resource 2. A slack variable

represents unutilised capacity of a resource. Slack Variable is represented by 'S'.

Concept of Duality

Every linear programming problem has a mirror image associated with it. If the original

problem is maximisation, the mirror image is minimisation and vice versa.

The original problem is called 'primal' and the mirror image is called 'dual'.

The format of simplex method is such t hat when we obtain optimal solution of any one out of

primal or dual, we automatically get optimal solution of the other.

For example, if we solve dual by simplex method, we also get optimal solution of primal.

Characteristics of Dual Problem

1. Dual of the dual is primal.

2. If either the primal or dual has a solution, then the other also has a solution. The optimal

value of both the solutions is equal.

3. If any of the primal or dual is infeasible then the other has an unbounded solution.

Advantages of Duality munotes.in

## Page 29

6

1. If primal problem contains a large number of rows and a smaller number of columns we

can reduce the computational procedure by converting into dual.

2. Solution of the dual helps in checking computational accuracy of the primal.

3. Economic int erpretation of the dual helps the management in decision making.

For example,

Minimisation LPP can be solved by two methods:

1. Simplex of Dual Method and

2. Artificial Variable Method

Method:1 Simplex of Dual Method

The original problem is called 'Primal'. We convert the problem in its 'Dual'.

Primal Dual

1. Minimisation Problem Min. Z Maximisation Problem Max. Z*

2. Constraints are of ' ≥′ type Constraints are of ' ≤' type.

3. Decision variables are X 1, X2 etc. Decision variables are Y 1, Y2 etc.

4. Objective function coefficients of primal (4, 3) become RHS of constraints in Dual.

5. RHS of Constraints of Primal (4000, 50, 1400) become objective function coefficients of

Dual.

6. In the LHS (left side) of constraints, all vertical values are writ ten horizontally in Dual.

7. No. of Decision Variables in Primal = No. of constraints in Dual

8. No. of Constraints in Primal = No. of Decision Variables in Dual

For example,

Primal Dual

Min Z = 4 X 1 + 3 X 2

Subject to:

200 X 1 + 100 X 2 ≥ 4000

1 X1 + 2 X 2 ≥ 50

40 X 1 + 40 X 2 ≥1400 Max Z = 4000 Y 1 + 50 Y 2 + 1400 Y 3

Subject to:

200 y 1 + 1y 2 + 40y 3 ≤ 4

100 y 1 + 2y 2 + 40y 3 ≤ 3

The numerical is calculated as shown in Simplex Method.

EXERCISES

1. Why an optimal solution to an unbounded maximisation LPP cannot be found in Simplex

Method?

2. What is meant by shadow price of a resource?

munotes.in

## Page 31

1

UNIT 6

SENSITIVITY ANALYSIS

The solution to a LPP is determined by simplex method is a static solution, It means that

solution corresponds to:

1. Value of profit coefficients in the objective function, and

2. Availability of resources (i.e R.H.S of constraints)

But in reality, profit coefficients of variables may increase or decrease. Similarly, availability

of resources may also increase or decrease. In that case, the optimal profit and optimal

quantity (b values) of variables calculated as per Simplex solution will change.

The objective of sensitivity analysis is to determine the new values of solution. If possible,

from the given simplex solution. This will be possible only if the changes (increase/decrease)

in the objective function or constraint capacities is in certain limits. These will be two limits,

lower limit (max. possible decrease) and upper limit (max. possible increase). These two

limits provide the range within which the present simplex table remains optimal.

Hence, if the change in profit or change in capacity constraints is in the range, we can find

new values of the solution. If it is not in the range, we cannot find the new values of the

solution. Because the present simplex table will not remain optimal any more.

EXAMP LE 1: An electronics firm manufactures three products - transistors, resistors and

capacitors which give profit of Rs. 100, 60 and 40 per unit respectively.

The firm uses three resources - Engineering, Direct Labour and Admin. capacities are 100,

600 and 3 00 hrs. respectively.

Following simplex solution is obtained.

Cj 100 60 40 0 0 0

C X B X1 X2 X3 S1 S2 S3

60 X2 200/3 0 1 5/6 1 - 1/6 0

100 X1 100/3 1 0 1/6 0 1/6 0

0 S3 100 0 0 4 0 1

Zj 100 60 200/3 0 20/3 0

∆ = C j - Zj 0 0 -80/3 0 - 20/3 0

Note: The solution is optimal as there is no positive Cj - Zj.

Optimal Product Mix is:

X1 = 100/3 = No. of units of transistors.

X2 = 200/3 = No. of units of resistors

X3 (capacitors) is not produced.

Optimal Profit is:

Max. Z = [60 X 200/3] + [100 X 100/3] = [4000 + 10, 000/3]

Max. Z = Rs. 22, 000/3 munotes.in

## Page 32

2

A. Range for profit coefficients of products:

Formula = ∆𝑗

𝑋𝑛

B. Range for profit coefficients of X 1:

Formula = ∆𝑗

𝑋𝑖

We take ration of ' ∆′ (Cj - Zj) row and ' X1' row:

The ratios will be:

−80/3

1/6 = − 80

3 x 6

1 = - 160

−100

3

−2/3 = − 100

3 x −3

2 = 50

−20/3

1/6 = − 20

3 x 6

1 = - 40

'-' sign indicates decrease in profit & '+' sign indicates increase in profit. It means possible

decrease is 160 or 40. Hence, we can decrease profit by only 40. Possi ble increase is 50.

⸫ Range for profit coefficient of X 1 is:

Original Profit ± (increase or decrease)

100 + 50 = 150

100 - 40 = 60

⸫ Rs. 60 to Rs. 150

It means profit of X 1 (transistors) can fluctuate within the range of Rs. 60 to Rs. 150. The

simplex solution will remain optimal in this range.

2. Range for profit coefficient of X 2

Formula = ∆1

𝑋2

We take ration of ' ∆′ (Cj - Zj) row and 'X 2' row:

−80/3

5/6 = − 80

3 x 6

5 = - 32

−100

3

5/3 = − 100

3 x −3

5 = - 20

−20/3

1/6 = − 20

3 x 6

1 = 40

Hence, possible decrease is Rs. 20 and possible increase is Rs. 40. Range for profit

coefficient of X 2 is

60 - 20 = 40

60 + 40 = 100

Rs. 40 to Rs. 100.

It means the present simplex solution will remain optimal even if profit of X 2

(resistors)fluctuates in the range of Rs. 40 to Rs. 100.

3. Range for profit coefficient of X 3

X3 capacitors is not produced.

∆ of X 3 = -80/3

It means if we produce X 3, we will incur a loss of Rs. 80/3 per unit of X 3.So, X 3 will be

produced only if present profit of X 3 is increased by Rs. 80/3.

⸫ X3 will be produced if its profit becomes [40 + 80/3] = Rs. 200/3 or more than that.

Hence, the present simplex solution remains optimal till the profit value of 200/3 for X 3. munotes.in

## Page 33

3

⸫ Range for profit coefficient of X 3 is

Rs. zero to 200/3.

B. Range for capacity of resources

OR Range for validity of shadow prices of Resources

Formula = - [𝑏

𝑆𝑛]

1. Range for capacity or availability of Engineering hours

Engineering hours is represented in simplex table by slack variable s 1:

Formula = - [𝑏

𝑆1]

We will take ratio of 'b' column and 'S 1' column.

The ratios will be

- [200 /3

5/6] = - [ 200

3 x 3

5 ] = - 40

- [100 /3

− 2/3] = - [ 100

3 x −3

2 ]= 50

- [100 /3

− 2/3] = - [- 50] = 50

Hence, possible decrease in capacity is 40 hrs and possible increase in capacity is 50 hrs.

Range for resource capacity of Engineering is:

Original Capacity ± (increase or decrease)

100 + 950) = 150

100 - 40 = 60

⸫ Range is 60 hrs to 150 hrs.

It means the present simplex solution will remain optimal even if availability of Engineering

resource fluctuates between 60 hrs to 150 hrs.

Note: In other words the shadow price of Engineering resource [which is Rs. 100/3] will

remain valid even if the resource availability fluctuate s between 60 hrs. to 150 hrs.

2. Range for availability of Direct Labour

Formula = - [𝑏

𝑆2]

The ratios will be

- [200 /3

− 1/6] = - [ 200

3 x− 6

1] = 400

- [100 /3

−1/6] = - [ 100

3 x 6

1 ]= - 200

- [100

0] = Infinity.

⸫ Range for resource capacity of Direct Labour is:

600 + 400 = 1000

600 - 200 = 400

⸫ Range is 400 hrs to 1000 hrs.

It means the present simplex solution will remain optimal even if availability of Direct

Labour resource fluctuates between 400 hrs to 1000 hrs.

Note: In other words, the shadow pr ice of Direct Labour resource (which is Rs. 20/3) will

remain valid even if the resource availability fluctuates between 400 hrs to 1000 hrs.

3. Range for availability of Admin:

Formula = - [𝑏

𝑆3] munotes.in

## Page 34

4

The ratios will be

- [200 /3

0] = - [Infinity] = Infinity

- [100 /3

0] = - [Infinity]= Infinity

- [100

1] = - 100.

It means the capacity can increase upto infinity.

Possible decrease = 100 hrs.

Range for resource capacity of Admin is

300 + Infinity = Infinity

300 - 100 = 200

⸫ Range is 200 hrs to Infinity.

It means the present simplex solution will remain optimal even if availability of Admin

resource fluctuates between 200 hrs to Infinity.

Note: In other words, the shadow price of Admin resource (which is Rs. zero) will remain

valid even if the resource availabilit y fluctuates between 200 hrs to infinity.

c. Effect on the solution due to increase or decrease in the availability of resources

1. What will be the effect on solution if capacity of Engineering is increased by 30%?

Answer:

Original capacity = 100 hrs.

Increase = 30%

New capacity = 130 hrs.

Note:

To find the effect on solution we need to find the range of resource capacity. We can find the

effect on solution only if the new capacity is in the range.

If the new capacity goes out of the range, then we cannot find effect on solution.

Because in that case, the present simplex solution does not remain optimal any more.

From earlier calculation, we know that, Range for resource capacity of Engineering is 60 hrs

to 150 hrs.

⸫ New capacity is in the range.

Change in capacity = 130 - 100 = + 30 hrs.

Hence, we multiply column S 1 by + 30.

From that we will get change in 'b' column.

S1 X (+30) = Change in 'b' column

X2 5/3 X + 30 = + 50

X1 -2/3 X + 30 = - 20

Now we can find new basis values.

New Basis:

c X New b

60 X2 200/3 + 50 = 350/3

100 X1 100/3 - 20 = 40/3

New Z = (60 x 350/3) + (100 X 40/3)

New Z = 25, 000/3 Rs.

Increase in optimal profit = 25, 000 - 22, 000/3

= Rs. 1, 000 munotes.in

## Page 35

5

New Optimal Product Mix:

X1 = 40/3 units

X2 = 350/3 units.

2. Can you find out effect on optimal solution if excess capacity of abundant resource is

transferred to Direct Labour?

Answer:

In the optional solution, S 3 is present in the basis.

S3 = 100

S3 represents slack value of Admin.

Hence, Admin is abundant resource and its exc ess (unused) capacity is 100 hrs.

Capacity of Direct Labour = 600 hrs.

If 100 hrs are transferred,

New capacity of Direct labour = 700 hrs.

We, know that range of Direct Labour capacity is 400 hrs to 1000 hrs.

New capacity is in the range.

S1 X (+30) = Change in 'b' column

X2 -1/6 X + 100 = - 100/6 - -50/3

X1 1/6 X + 100 = 100/6 = 50/3

New Basis:

c X New b

60 X2 200/3 - 50/3 = 150/3 = 50

100 X1 100/3 + 50/3 = 150/3 = 50

New Z = (60 x 50) + (100 + 50) = Rs. 8, 000

Increase in optimal profit = 8, 000 - 22, 000/3

= Rs. 2, 000/3

New Optimal Product Mix:

X1 = 50 units

X2 = 50 units.

3. What will be the effect on optimal solution if capacity of Admin is reduced to 175 hrs?

Answer: Range for capacity of Admin = 200 hrs to Infinit y.

Since, 175 hrs is out of the range, if Admin capacity is reduced to 175 hr. solution will not

remain optimal.

munotes.in

## Page 36

6

EXERCISES

1. An engineering company BMS Ltd. produces three products A, B and C using three

machines M 1, M 2 and M 3. The resource constraints on M 1, M 2 and M 3 are 96, 40 and 60 hours

respectively. The profits earned by the products A, B and C are Rs. 2, Rs.5 and Rs. 8 per unit

respectively. A simplex optimal solution to maximize the profit is given below where X 1, X2

and X 3 are quantities of products A, B and C produced by the company s 1, s2 and s 3 represent

the slack in the resources M 1, M 2 and M 3. Study the solution given below and answer the

following questions:

C X

Variables

in the

basis X1 X2 X3 S1 S2 S3 B

Solution

Values

5

8

0 X2

X3

S3 1/3

5/6

7/3 1

0

0 0

1

0 1/6

- 1/12

- 1/13 - 1/3

2/3

- 1/3 0

0

1 8/3

56/3

44/3

∆ = C - Z - 19/3 0 0 - 1/6 - 11/3 0

1. Indicate the shadow price of each resource. Which of the resources are abundant and which

are scarce?

2. What profit margin for product A do you expect the marketing department to secure if it is

to be produced, and justify your advice?

3. Within what range, the profit of product B can change for the above solution to remain

optimal?

4. How would an increase of 10 hours in the resource M 2 affect the optimality?

5. If the company BMS Ltd. wishes to raise production which of the three resources should

be given priority for enhancement?

2. A business problem is formulated and expressed below as an LPP. (Profit is in Rs. and

Resources are in units).

Objective function

Maximise Z = 80 X1 + 100 X 2

Subject to resource constraints,

X1 + 2X 2 ≤ 720 (Resource 1)

5X1 + 4X 2 ≤ 1800 (Resource 2)

3X1 + X 2 ≤ 900 (Resource 3)

X1, X2 ≥ 0

Simplex algorithm of LPP, applied to the above problem yielded following solution:

Basis B1

Cb Xb X1 X2 S1 S2 S3

100 X2 0 1 5/6 - 1/6 0 300

80 X2 1 0 - 2/3 1/3 0 120

0 S3 0 0 7/6 - 5/6 1 240

Cj 80 100 0 0 0

∆ = C j - Zj 0 0 - 30 - 10 0

1. Answer the following questions with justification:

a. Is the solution optimal and unique? munotes.in

## Page 37

7

b. Is the above solution infeasible?

c. What is the maximum profit as per optimal solution?

d. Which resources are abundant and which are scarce as per optimal solution?

2. Find out the r ange of coefficient of X 1 in the objective function for which the above

solution remains optimal.

3. Can you obtain the solution values of basic variables form the optimal solution when

resource constraint (a) Changes to 750 units? If yes, find the new val ues of the basic

variables.

.

munotes.in