Sem-1, BBA, B.COM, Business Maths, Unit VIII - Linear Programming, 21.06.2021-converted

IDOL Institute of Distance and Online Learning ENHANCE YOUR QUALIFICATION, ADVANCE YOUR CAREER.

2 Business Mathematics www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

What we are learning today 3 ✘ Linear Programming Problems www.cuidol.in 3 All right are reserved with CU-IDOL Unit-1(MAP-607)

4 FORMULATION OF LINEAR PROGRAMMING PROGRAM www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL

5 ✘ The XYZ Company wishes to schedule the production of two items namely chairs and tables. The management of the company has to decide as to how many chairs and tables to be produced per day to maximize the profit. The following information is available to the management. The profit per item is Rs.35 and Rs. 55 respectively. ✘ In order to produce the two items that requires resources wood, manpower and machine hour. The supply of wood is restricted to 1500 kg/day. The manpower available per day is 75 carpenters. Also the maximum of 120 machine hours available per day. The production formula is as given in the following table. www.cuidol.in 5 All right are reserved with CU-IDOL Unit-1(MAP-607)

6 www.cuidol.in 6 All right are reserved with CU-IDOL Unit-1(MAP-607)

Solution 7 ✘ Formulate an LP model to determine the daily production rate of various models in order to maximize the profit. ✘ Formulation ✘ Step 1: Identify the decision variables. Let the number of units of chairs and tables to be produced be x1 and x2, respectively. www.cuidol.in 7 All right are reserved with CU-IDOL Unit-1(MAP-607)

8 ✘ Step 2: Identify the constraints. In this problem, the constraints are the limited availability of the three resources wood, manpower and machine hour. In addition to that we restrict the variables x1, x2 to have only non-negative values. ✘ Step 3: Identify the objective. Here it is maximization of profit. ✘ Then tabulate the given items: www.cuidol.in 8 All right are reserved with CU-IDOL Unit-1(MAP-607)

9 www.cuidol.in 9 All right are reserved with CU-IDOL Unit-1(MAP-607)

10 ✘ Construction of the objective function: ✘ Profit from chairs: 35x1 ✘ Profit from tables: 55x2 ✘ ————— ✘ Total Profit: 35x1 + 55x2 ✘ ————— www.cuidol.in 10 All right are reserved with CU-IDOL Unit-1(MAP-607)

11 ✘ Max Z = 35x1 + 55x2 ✘ where Z is the name of the objective function. ✘ Construction of constraint for wood: ✘ Wood requirement for chairs: 6x1 www.cuidol.in 11 All right are reserved with CU-IDOL Unit-1(MAP-607)

✘ Wood requirement for tables: 12x2 12 ————— ✘ Total wood requirement: 6x1+12x2 ————— ✘ Given maximum availability is 1500 kg ✘ ⇒ 6x1 + 12x2 ≤ 1500 ✘ In order to achieve the maximization of the objective function, we can make use of all 1500 kg or less than 1500 kg. www.cuidol.in 12 All right are reserved with CU-IDOL Unit-1(MAP-607)

✘ Similarly, the other two constraints are 13 ✘ 2x1 + 3x2 ≤ 75 (Men) ✘ 4x1 + 6x2 ≤ 120 (Machine) ✘ In addition, we restrict the variables x1, x2, to have only non-negative values. ✘ Thus, the LPP for our product mix problem becomes: ✘ Max Z = 35x1 + 55x2 ✘ s.t. 6x1 + 12x2 ≤ 1500 2x1 + 3x2 ≤ 75 4x1 + 6x2 ≤ 120 x1, x2 ≥ 0 www.cuidol.in 13 All right are reserved with CU-IDOL Unit-1(MAP-607)

Fixed Charge Problem 14 1. The River Falls Textile Company can use any or all of three different processes for weaving its standard white polyester fabric. Each of these production processes has a weaving machine setup cost and per-square-meter processing cost. These costs and the capacities of each of the three production processes are as follows: www.cuidol.in 14 All right are reserved with CU-IDOL Unit-1(MAP-607)

15 www.cuidol.in 15 All right are reserved with CU-IDOL Unit-1(MAP-607)

16 ✘ The company forecasts daily demand for its white polyester fabric of 40,000 square meters. The company’s production manager wants to make a decision concerning which production processes to utilize to meet the daily demand forecast, and at what capacity, to minimize the total production costs. Formulate the suitable mathematical model for the above situation. www.cuidol.in 16 All right are reserved with CU-IDOL Unit-1(MAP-607)

✘ Let x1, x2 and x3 stand for the number of square meters of white polyester produced using process 1, process 2 and process 3, respectively. 17 www.cuidol.in 17 All right are reserved with CU-IDOL Unit-1(MAP-607)

✘ Here the objective is to minimize the overall production cost. 18 ✘ ✘ Min Z = 50d1 + 80d2 + 100d3 + 0.06x1 + 0.04x2 + 0.03x3 ✘ st. ✘ x1 + x2 + x3 ≤ 40,000 ✘ x1 ≤ 20,000 d1 ✘ x2 ≤ 30,000 d2 ✘ x3 ≤ 35,000 d3 ✘ x1, x2, x3 ≥ 0 and integers d1, d2, d3 are either 0 or 1 www.cuidol.in 18 All right are reserved with CU-IDOL Unit-1(MAP-607)

Graphical Method 19 ✘ Max Z = 3x1 + 9x2; st. x1 + x2 ≤ 8; x1 + 2x2 ≤ 4, x1, x2 ≥ 0 ✘ Here the given problem consists of exactly two variables and both the variables are positive. ✘ So, we can apply the graphical method to get the optimum solution. ✘ Step 1: Consider the constraints with equality symbol ✘ i.e., ✘ x1 + x2 = 8 (1) ✘ x1 + 2x2 = 4 (2) www.cuidol.in 19 All right are reserved with CU-IDOL Unit-1(MAP-607)

20 ✘ Step 2: Get the two co-ordinate points for each equation. ✘ Consider Eq. (1) x1 + x2=8 (0,8) ✘ Put x1 = 0 in equ(1) ✘ 0+ x2 =8 ; x2 = 8 => (0,8) ✘ Similarly, x2 = 0 in equ (1) ✘ x1+0 = 8 = > x1 = 8 => (8,0) ✘ ✘ x2 = 0 ⇒ x1 = 8; put x1 = 0 ⇒ x2 = 8 (8,0) ✘ i.e., (8,0) ✘ ✘Uniti-.1e(2M0.A,P-(6007,) 8) All right are reserved with CU-IDOL www.cuidol.in

21 ✘ x1 + 2x2 = 4 ✘ Put x1 = 0 ✘ 0 + 2x2 = 4 => 2 x2 = 4 x✘ 2 = 4/ 2 = 2 => (0,2) (0,2) ✘ Put x2 = 0 ✘ x1 + 2(0) = 4 = > x1 + 0 = 4 => x1 = 4 = > (4,0) (4,0) www.cuidol.in 21 All right are reserved with CU-IDOL Unit-1(MAP-607)

✘ Similarly proceeding for Eq. (2), we have (4,0) and (0,2). 22 www.cuidol.in 22 All right are reserved with CU-IDOL Unit-1(MAP-607)

23 ✘ Step 3: Using the co-ordinate points, draw the lines in a two- dimensional graph, and shade the regions. ✘ Step 4: Put x1 = 0 and x2 = 0 in constraint (1) ✘ i.e., ✘ ✘ x1 + x2 ≤ 8 ⇒ 0 ≤ 8; www.cuidol.in 23 All right are reserved with CU-IDOL Unit-1(MAP-607)

24 ✘ The constraint is satisfied, shade towards the origin. Also, the 2nd constraint is satisfied when x1 = 0 and x2 = 0 then shade towards the origin. ✘ Step 5: We have a closed intersection area common to both the lines, call it OAB, ✘ i.e., area OAB is the required feasible region. ✘ Step 6: Consider the extreme points of the feasible region. Get the co-ordinates of the extreme points in the feasible region, O(0,0); A(4,0) and B(0,2). www.cuidol.in 24 All right are reserved with CU-IDOL Unit-1(MAP-607)

25 www.cuidol.in 25 All right are reserved with CU-IDOL Unit-1(MAP-607)

26 THANKS www.cuidol.in 26 All right are reserved with CU-IDOL Unit-1(MAP-607)

Extra Problems 27 Min Z = 2x1 + 3x2; s.t. x1 + x2 ≤ 4; 6x1 + 2x2 ≥ 8; x1 + 5x2 ≥ 4; x1 ≤ 3; x2 ≤ 3; x1, x2 ≥ 0 ✘ Here, the given problem consists of exactly two variables and both the variables are positive. ✘ So, we can apply graphical method to get the optimum solution. www.cuidol.in 27 All right are reserved with CU-IDOL Unit-1(MAP-607)

28 ✘ Step 1: Consider the constraints with equality symbol. ✘ x1 + x2 = 4; … (1) ✘ 6x1 + 2x2 = 8; … (2) ✘ x1 + 5x2 = 4; … (3) ✘ x1 = 3; … (4) ✘ x2 = 3 … (5) www.cuidol.in 28 All right are reserved with CU-IDOL Unit-1(MAP-607)

29 www.cuidol.in 29 All right are reserved with CU-IDOL Unit-1(MAP-607)

✘ Step 3: Using the co-ordinate points, draw the lines in a two- 30 dimensional graph and shade the regions. www.cuidol.in 30 All right are reserved with CU-IDOL Unit-1(MAP-607)

✘ Step 4: Put x1 = 0 and x2 = 0 in all the constraints, constraints (2), (4) and 31 (5) are satisfied then shade the corresponding lines towards origin. Also eqs (2) and (3) are not satisfied, then shade the corresponding lines away from the origin. ✘ The common intersection area of all the five lines is ABCDE (a closed feasible region). www.cuidol.in 31 All right are reserved with CU-IDOL Unit-1(MAP-607)

32 ✘ Step 5: Consider the extreme points of the feasible region. Get the co-ordinate of the extreme points in the feasible region. ✘ A: Intersection point of the lines, eqs (2) and (3), ✘ Solving eqs (2) and (3), ✘ ✘ 6x1 + 2x2 = 8 (2) ✘ x1 + 5x2 = 4 (3) www.cuidol.in 32 All right are reserved with CU-IDOL Unit-1(MAP-607)

33 www.cuidol.in 33 All right are reserved with CU-IDOL Unit-1(MAP-607)

34 www.cuidol.in 34 All right are reserved with CU-IDOL Unit-1(MAP-607)

35 www.cuidol.in 35 All right are reserved with CU-IDOL Unit-1(MAP-607)

36 www.cuidol.in 36 All right are reserved with CU-IDOL Unit-1(MAP-607)

37 www.cuidol.in 37 All right are reserved with CU-IDOL Unit-1(MAP-607)

38 www.cuidol.in 38 All right are reserved with CU-IDOL Unit-1(MAP-607)

39 www.cuidol.in 39 All right are reserved with CU-IDOL Unit-1(MAP-607)

40 www.cuidol.in 40 All right are reserved with CU-IDOL Unit-1(MAP-607)

✘ Solve: Max Z = 4x1 + 5x2 s.t. x1 + x2 ≥1; − 2x1 + x2 ≤ 1; 4x1 − 2x2 ≤ 1; x1, x2 ≥ 0For the 41 given problem, graphical method can be applied. ✘ Step 1: Consider the constraints with equality symbol. ✘ ✘ x1 + x2 = 1 (1) ✘ − 2x1 + x2 = 1 (2) ✘ 4x1 − 2x2 =1 (3) www.cuidol.in 41 All right are reserved with CU-IDOL Unit-1(MAP-607)

✘ Step 2: Get the two co-ordinate points for each equation. 42 ✘ For eq. (1), (0,1) and (1, 0) ✘ For eq. (2), (0,1) and (−1/2, 0) ✘ For eq. (3), (0, −1/2) and (1/4, 0) ✘ Step 3: Using the co-ordinate points, draw the lines in a two- dimensional graph and shade the regions. ✘ Step 4: When x1 = 0 and x2 = 0; constraints (2) and (3) are satisfied then shade towards origin and constraint (1) is not satisfied then shade away from the origin. www.cuidol.in 42 All right are reserved with CU-IDOL Unit-1(MAP-607)

43 www.cuidol.in 43 All right are reserved with CU-IDOL Unit-1(MAP-607)

44 Remarks: (1) If the line lies in quadrants (2), (3) and (4), then it must be extended into quadrant (1) (dotted line). (S2te) pSh5a:dTehoenfelyaisnibqlieu.eare.d,graio4nntx1(is1+)n.5otx2cl=os8ed. i.e., The feais.eib.l,e4rxe1g+ion5xis2 =4 unbounded. Select any two arbpituratryx1va=lu0e;sxf2o=r Z1a.6s Z = 8 and Z =p4ut x1 = 0; x2 = 0.8 SRteeppre6s:eCnlteathrley,ZthlinepeZuwitnhxce2ren=aZs0i=n; g8x1dai=nred2cZtio=n4ainlwtahyesginratepprhsueutcsxtins2gt=hte0hi;fcexka1lsi=inbe1le. region. ⇒ The solution to (th0e,1g.6iv)e;n(2p,r0o)blem is unbounded. (0, 0.8); (1, 0) i.e., The given LPP is having an unbounded solution. www.cuidol.in 44 All right are reserved with CU-IDOL Unit-1(MAP-607)

45 www.cuidol.in 45 All right are reserved with CU-IDOL Unit-1(MAP-607)

46 www.cuidol.in 46 All right are reserved with CU-IDOL Unit-1(MAP-607)

✘ Step 6: Clearly, the Z increasing direction does not intersect the feasible 47 region, the solution to the LPP is bounded. ✘ Step 7: Consider the lower bounds of the unbounded feasible region O and A. ✘ A lies at the intersection point of eqs (1) and (2) ✘ ✘ 2x1 − x2 = 0 ✘ x1 = 4 ✘ ⇒ x2= 8 ✘ (4, 8) www.cuidol.in 47 All right are reserved with CU-IDOL Unit-1(MAP-607)

48 www.cuidol.in 48 All right are reserved with CU-IDOL Unit-1(MAP-607)

49 END www.cuidol.in Unit-1(MAP-607) All right are reserved with CU-IDOL