Or2a- Mr. Deepak

OR – 2 LINEAR PROGRAMMING

1

GENERAL: LPP 1. Mgt has to allocate Resources – Men, material, money, time, technology or space – so as to derive best possible output (or set of outputs) under given constraints. 2. The output may be profits, costs, social welfare, effectiveness etc. 3. In many situations, the outputs can be expressed as a linear relationship among number of variables. 4. The Available resources can also be expressed as a linear relationship among a number of variables. 2

5. Mgt problem may be to optimize (maximize or minimize) output subject to constraints. 6. An optimization problem, in which the objective function & the constraints are represented in linear forms, is a problem in linear programming.

3

LPP 1. LPP: Math Programming in which functions

of objectives and the constraints are linear. 2. Optimization means either to maximize or minimize the objective function. 3. General LPP model is defined as: Maximize or Minimize Z = c1x1 + c2x2 + …. + cnxn Subject to constraints A. a11 x1 + a12 x2 + ….. + a1n xn ~ b1 B. a21 x1 + a22 x2 + ….. + a2n xn ~ b2

C. ………… ... D. ………… .. E. am1 x1 + am2 x2 + ….. + amn xn ~ bm and x1 ≥ 0, x2 ≥ 0, …. , xn ≥ 0

4

4. Where c , bi & aij (i = 1,2,…, m; j = 1,2,…,n) are j

constants determined in formulating of problem. 5. And xj (j = 1,2,….,n) are the decision variables.

6. cj, bi & aij are interpreted as follows: A.bi is the available amount of resources. B.aij is the amount of resources i that be allocated to reach unit of activity j.

C. The worth per unit of activity is equal to cj .

5

LPP: Canonical Form 1. General LPP can be put into the following form known as canonical form. 2. Maximize Z = c1x1 + c2x2 + …. + cnxn Subject to :

A. a11 x1 + a12 x2 + ….. + a1n xn ≤ b1 B. a21 x1 + a22 x2 + ….. + a2n xn ≤ b2 C. ………… .. D. ………… .. E. am1 x1 + am2 x2 + ….. + amn xn ≤ bm and x1 ≥ 0, x2 ≥ 0, …. , xn ≥ 0

6

3. Characteristics of this form are: A. All decision variables are non – negative. B. All Constraints are ≤ type. C. The objective function is of maximization type.

7

How to Convert General LPP into Canonical Form? - 5 elements 1. The minimization function is mathematically equivalent to the max of the negative expression of this function. 2. i.e.Min Z = c1x1 + c2x2+ …. + cnxn is equivalent to Max Z = – c1x1 – c2x2 – …. – cnxn 3. Any inequality in one direction (≤ or ≥) may be changed to an inequality in the opposite direction (≥ or ≤) by multiplying both sides with –1. For example, 2x1 + 3x2 ≥ 5 is equivalent to 8 – 2x1 – 3x2 ≤ – 5.

4. An equation can be replaced by two

inequalities in opposite direction. For example, 2x1 + 3x2 = 5 can be written as A. 2x1 + 3x2 ≥ 5 and 2x1 + 3x2 ≤ 5 or B. – 2x1 – 3x2 ≤ – 5 and 2x1 + 3x2 ≤ 5 5. An inequality constraint with its LHS in the absolute form can be changed into two regular inequalities. For example: |2x1 + 3x2| ≤ 5 is equivalent to 2x1 + 3x2 ≤ 5 and 2x1 + 3x2 ≥ – 5 or – 2x1 – 3x2 ≤ 5

9

6. The variable which is unconstrained in sign (i.e. ≥ 0, ≤ 0 or zero) is equivalent to the difference between two non – negative variables. For example, if x is unconstrained in sign, then x = (x+ – x–) where x+ ≥ 0, x– ≤ 0.

10

EXAMPLES OF LPP 1. A firm engaged in producing two models, viz.,

Model A & Model B, performs only 3 operations – manufacture, assembly and `quality control. Relevant Data is: Unit Sale Price

Hours Required for Each Unit manufact assembly ure

Quality control

Model A Rs 50/

1.0

0.2

0.0

Model B Rs 80/

1.5

0.2

0.1

2. Total Number of hours available each week are as under: manufacture 600, assembly 100, QC 30.

11

3. Firm want to determine weekly produced –

mix to maximize revenue. Solution: 4. Notations: A. Z = Total Revenues B. x1 = No. of units of Model A x2 = No. of units of Model B C. b1= Weekly hours available for manufacture b2= Weekly hours available for assembly b3 = Weekly hours available for QC

12

5. Therefore, objective function is: Max Z = 50x1 + 80x2 Subject to: 1.0x1 + 1.5x2 ≤ 600 0.2x1 + 0.2x2 ≤ 100 0.0x1 + 0.1x2 ≤ 30 and x1 ≥ 0, x2 ≥ 0 (non – negative conditions) Hence, x1 and x2 are decisions variables. 13

Example 2: 1. A milk distributor supplies milk in bottles to

houses in three areas A, B, C in a city. His delivery charges per bottle is 20paise in Area A, 30paise in Area B, 50paise in Area C. He has to spend on an average 1 minute to supply one bottle in Area A, 2 minutes per bottle in Area B and 3 minutes per bottle in Area C. He can spend only 2 hours & 30 minutes for this milk distribution but not more than one hour 20 minutes for Area A & B together. Max number of bottles he can deliver is 100. Find the number of bottles that he has to supply in each area so as to earn the max. Construct a math model. 14

Solution The decision variables of the model can be defined as follows: A.No. of bottles to which the supplier distribute milk in area A – x1 B.No. of bottles to which the supplier distribute milk in area B – x2 C.No. of bottles to which the supplier distribute milk in area C – x3 The objective of the Distributor is to maximize income. Maximize Z =

15

There are four constraints: A.Max No. of milk bottles is 100, i.e., x1 + x2 + x3 ≤ 100

B.Time spent in Area A per bottle 1 minute, 2 minutes in Area B, 3 minutes in Area C & max time is 150 minutes, x1 + 2x2 + 3x3 ≤ 150

C.He cannot spend more than 80 minutes in Area A & B, x1 + 2x2 ≤ 80

D.& non–negativity conditions:x1 ≥ 0, x2 ≥ 0, x3 ≥ 0.

16

Problem in Standard LPP form: Maximize Z = 0.2x1 + 0.3x2 + 0.5x3 Subject to: x1 + x2 + x3 ≤ 100 x1 + 2x2 + 3x3 ≤ 150 x1 + 2x2 ≤ 80 and x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 17

GRAPHICAL ANALYSIS 1. An LPP with two decision variables can be solved graphically. Example: Maximize Z = 700x1 + 500x2 Subject to: 4x1 + 3x2 ≤ 210 2x1 + x2 ≤ 90 and x1 ≥ 0, x2 ≥ 0 18

Let the Horizontal Axis represents x1 & Vertical Axis represents x2. Put the line 4x1 + 3x2 = 210 by replacing the inequality symbol which meets x1 axis at the point A(52.5, 0) & B(0,70) by putting x2= 0 & x1 = 0 respectively.

19

Any point on line AB or within the shaded portion will satisfy the constraint: 4x1 + 3x2 ≤ 210

20

Similarly, plot for 2x1 + x2 ≤ 90 C(45, 0) & D(0, 90)

21

Combining the Constraints, we can sketch as follows: 1. Take only positive values. 2. Shaded Area is the feasible region. 22

Basic Definition: Graphical Analysis

1. Any non – negative value of x1 & x2 (i.e., x1 ≥ 0 & x2 ≥ 0) is a feasible solution of the LPP if it satisfies all constraints. 2. A set X is convex if for any points x1, x2 in X, the line segment joining these points is also in X. 3. A linear inequality in two variables is known as a half plane. The corresponding equality or the two is known as the boundary of the half – plane. 4. A convex polygon is a convex set formed by the inter – section of finite number of closed half – planes. 23

24

Note: the objective function is maximized or minimized at one of the extreme points which is the Optimum Solution. Extreme points are referred to as vertices or corner points of the convex regions. 5.A redundant constraint is one which does not affect the feasible region. 6.A basic solution of a system of m equations & n variables (m
25

7. A basic feasible solution of m equations & n variables (m
26

Example Find all basic solutions for the system x1 + 2x2 + x3 = 4, 2x1 + x2 + 5x3 = 5 Solution: Here A =

,X=

&B=

If x1 = 0, then the basic matrix is B= . . In this case 2x2 + x3 = 4, x2 + 5x3 = 5. By solving this, x2 = 5/3, x3 = 2/3 (a basic feasible solution). 11

If x2 = 0, then the basic matrix is B case x1 + x3 = 4, 2x1 + 5x3 = 5.

=2 5.

In this

By solving this, x1 = 5, x3 = -1. Therefore, x1 = 5, x3=-1 is a basic solution,(not feasible since 27 x3 =-1 <0)

3. If x3 = 0, then the basic matrix is B = 1 2 21

In this case x1 + 2x2= 4, 2x1 + x2 = 5. By solving this, x1 = 2, x2 = 1 (a basic feasible solution). Therefore, i. (x2, x3) = (5/3, 2/3)

ii. (x1, x3) = (5, -1) iii.(x1, x2) = (2, 1) are only the collection of all Basic Solutions.

28

Graphical Methods to Solve the LPP

1. LPP with 2 decision variables x1&x2 can be solved

easily by graphical method. We consider the x1, x2 plane where we plot the solution space – which is a space enclosed by the constraints. 2. Usually the solution space is a Convex Set bounded by Polygon. Since a linear Function attains extreme (max, min) values only on the boundaries of the region, it is sufficient to consider the vertices of the polygon and find the value of the objective function of the problem. This method of solving a LPP on the basis of the alone analysis is known as the Graphical Method.

29

Working Rules

Step 1: Write down the equation by replacing inequality symbols by the equality symbols in the given constraints. Step 2: Plot the straight lines represented by the equations obtained. Step 3: Identify the convex polygon region relevant to the problem we must decide on sides of the line the half – plane is located. Step 4: Determine the vertices of the polygon and find the values of the given objective function Z at each of these vertices. Step 5: Identify the values of (x1,x2) which corresponds to the desired extreme value of Z. This is two optimal solution of the problem.

30

Solution of the Example 1(Models A & B) Max Z = 50x1 + 80x2 Constraints: 1.0x1 + 1.5x2 ≤ 600 0.2x1 + 0.2x2 ≤ 100 0.0x1 + 0.1x2 ≤ 30 and x1 ≥ 0, x2 ≥ 0 Put the constraints 31

Any point on the line or in the shaded portion will Satisfy all the constraints. ABCDE is the feasible Region of the objective function with the Constraints & where decision variables are Permissible. The intersection points C and D can be solved by The linear equations: C(150, 300), D(300, 200). Now maximize revenues subject to the alone Shaded area. We work out the revenue at different corner points. 32

Point

Feasible Solution of Product Mix

Corresponding Revenue

Total Revenue

x1

x2

From x1

From x2

A

0

0

0

0

0

B

0

300

0

24000

24000

C

150

300

7500

24000

31500

D

300

200

15000

16000

31000

E

500

0

25000

0

25000

We find that, Revenue is Maximum at Rs 31,500 where 150 units of x1 and 300 units of x2 are produced.

33

Example 2(Mixed Constraints LP Problem) 1. By using Graphical Method 2. Find Max & Min value of the function Z = x – 3y where x & y are non –negative & are subject to following constraints: 3x + 4y ≥ 19 2x – y ≤ 9 2x + y ≤ 15 x – y ≥ –3 3. Solution: First we write constraints to be satisfied by x, y in standard (less than or equal) form –3x – 4y ≤ –19 2x – y ≤ 9 2x + y ≤ 15 –x + y ≤ 3

34

4. Now consider these equations which represents straight lines in the xy plane. Let them by L1, L2, L3 & L4 as shown in the figure.

35

5. ABCD is a quadrilateral in xy plane & region bounded by it is convex. 6. All points (x, y) within or on the boundary lines of the quadrant will satisfy the inequalities x ≥ 0, y ≥ 0, and the constraints. 7. Coordinates of A, B, C, D are also obtained by solving equations taking two of them at a time, we find that A(1, 4), B(5, 1), C(6, 3), D(4, 7). 36

Solution: Z at A(1.4)= 1-3x4 = -11 Z at B(5,1) = 5 -3x1 = 2 Z at C(6,3) = 6 - 3x3 =-3 Z at D(4,7) = 4 - 3x7 =-17 Evidently Z is max at B and min at vertex D for which values are x=5, y=1 and x=4. Y=7 respectively.

Conclusion

1. In LPP, we first identify the Decision

Variables – Economic or Physical Quantities – whose values are of interest to the Management. 2. Should be well – defined Objective Function expressed in terms of decision variables (maximize or minimize). 3. Decision Variables Interact with each other through some constraints – due to limited resources, technical, legal, time or stipulation on quality. 4. These are linear functions. 38

5. LPP with 2 decision variables can be solved graphically. 6. Any non –negative solution which satisfies all constraints is feasible solution of the problem – collection is feasible region – it is a convex set. 7. Value of Decision Variable which max or min the objective function is located on the extreme points of the convex set. 8. Sometimes problems are infeasible. 39