Decision Analysis and Operations Research in Management

This content delves into Management Decision Analysis and Operations Research techniques such as Linear Programming, Integer Linear Programming, Dynamic Programming, Nonlinear Programming, and Network Programming. It covers the phases of an Operations Research study, mathematical modeling for decision-making, and the application of Linear Programming in optimizing production processes. The content also discusses the properties and violations of Linear Programming, providing insights into optimizing business decisions under different scenarios.

• Decision Analysis
• Operations Research
• Linear Programming
• Mathematical Modeling
• Optimization

senara Follow

Uploaded on Jul 13, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. IME634: Management Decision Analysis Raghu Nandan SENGUPTA IME Department Indian Institute of Technology Kanpur, INDIA

2. Operations Research (OR) OR techniques Linear programming Integer linear programming Dynamic programming Nonlinear programming Network programming IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 2

3. Phases of an OR study Identifying the management problem Development of mathematical model Solving the model Validation of the model Implementation of the model IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 3

4. How much to produce? JOBCO produces two products on two machines. A unit of product 1 requires 2 hours on machine1 and 1 hour on machine 2. For product 2, a unit requires 1 hour on machine 1 and 3 hours on machine 2. The revenues per unit of products 1 and 2 are $3 and $2, respectively. The total daily processing time available for each machine is 8 hours. JOBCO wants the optimum mix of Products 1 and 2 that maximizes their profit IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 4

5. Mathematical Modeling Decision variables Quantity of product 1/day: x1 Quantity of product 2/day: x2 Objective Revenue/unit of product 1: $ 3 Revenue/unit of product 2: $ 2 Maximize the revenue: z = 3x1 + 2x2 Constraints Hours required per unit of Product 1 Product 2 Available hours of machine/day 2x1 + x2 8 x1 + 3x2 8 x1, x2 0 Machine 1 2 1 8 Machine 2 1 3 8 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 5

6. Linear Programming (LP) JOBCO problem in LP: maximize z = 3x1 + 2x2 Subject to 2x1 + x2 8 x1 + 3x2 8 x1, x2 0 Properties of LP 1. Proportionality 2. Additivity 3. Divisibility 4. Certainty IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 6

7. Violations of the Properties of LP Proportionality: Economies of scale Marketing effort Additivity Complementing products Certainty Stochastic business environment (price and cost may vary in future) Divisibility Integer decision variables (people to be employed) IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 7

8. Can You Help Asian Paints.? Asian paints produces both interior and exterior paints from two raw materials. The following table shows the basic data. A market survey indicates that, the daily demand for interior paint cannot exceed that of the exterior paint by more than 1 ton. Also, the maximum demand of interior paint is 2 tons. Asian paints want the optimal product mix. Tons of raw materials/ton of Maximum daily availability (tons) Exterior paint Interior paint Raw material 1 6 4 24 Raw material 2 1 2 6 Profit per ton (Rs. 10000) IME634 5 4 RNSengupta,IME Dept.,IIT Kapur,INDIA 8

9. LP Formulation: Asian Paints Decision variables: x1= tons of exterior paint produced daily x2 = tons of interior paint produced daily Objective: Maximize z = 5x1 + 4x2 (Rs. 10000) Constraints: 6x1 + 4x2 24 x1 + 2x2 6 -x1 + x2 1 x2 2 x1 , x2 0 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 9

10. Graphical Method for LP model Plot the constraints Identify the region satisfying the constraints (feasible solution) Plot the objective function Identify the direction of increase Identify the maximum value of objective function under the given constraints (optimal solution) IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 10

11. JOBCO Problem Maximize z = 3x1 +2x2 Subject to 2x1 + x2 8 x1 + 3x2 8 x1, x2 0 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 11

12. Optimal Solution to the JOBCO Problem (x1 = 3.2, x2 = 1.6), z= 12.8 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 12

13. JOBCO: An Increase in the Machine Available Hours Rate of revenue change due to increase in machine capacity by 1 hour = (14.2-12.8)/1=$1.4, is the shadow price or dual price Similar analysis will yield the shadow price of M2 = $0.2 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 13

14. Feasibility range of Machines Range of the limit of Machine 1 capacity for which the shadow (dual) price remains the same: Value of M1 corresponding to (0, 8) = 16 Value of M1 corresponding to (2.67, 0)= 2.67 Hence, range= 2.67 M 1Capacity 16 For M2, 4 M 2Capacity 24 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 14

15. Optimality Range: Revenue Component 1/3 c1/c2 2/1 (1) Range of c1: fix c2 and evaluate (1) 0.667 c1 4 Range of c2: fix c1 and evaluate (1) 1.5 c2 9 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 15

16. Some Insights If JOBCO can increase the capacity of both machines, which machine should be preferred first? Is it advised to increase the capacities of Machines 1 and 2 at the cost of $1/hr? If the capacity of the machine is increased from 8 hrs. to 13 hrs., how will it impact the revenue? Suppose that the unit revenues for product 1 and 2 are changed to $3.5 and $2.5, will the current optimum remain same? IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 16

17. Minimization : JOBCO Problem Hours required per unit of Product 1 Product 2 Minimum hours of machine/day Available hours of machine/day Machine 1 2 1 5 8 Machine 2 1 3 3 8 Objective Cost/unit of product 1: $ 2 Cost/unit of product 2: $ 1 Minimize w = 2x1 +x2 Subject to 2x1 + x2 8 x1 + 3x2 8 2x1 + x2 5 x1 + 3x2 3 x1, x2 0 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 17

18. Simplex Method: JOBCO Problem Maximize z = 3x1 + 2x2 Subject to 2x1 + x2 8 x1 + 3x2 8 x1, x2 0 Objective : Maximize z= 3x1 + 2x2 + 0s1+ 0s2 Constraint equations 2x1 + x2 + s1=8 x1 + 3x2 + s2=8 s1 and s2 are the slack variables 0 x1, x2, s1, s2 0 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 18

19. Simplex Table Objective function z row z-3x1-2x2-0s1-0s2=0 Basic z x1 -3 x2 -2 s1 0 s2 0 Solution Minimum ratio z 1 0 s1 s2 0 2 1 1 0 8 8/2 Leaving (feasibility condition) 0 1 3 0 1 8 8/1 Entering (optimality condition) 1. Maximization: entering variable = with most negative coefficient 2. Leaving: minimum non negative ratio 3. For pivot row (s1 row in this table) new pivot row= current pivot row/pivot element ( ) 4. For other rows new row= current row- (row s pivot column coefficient new pivot row) IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 19

20. Second iteration Basic z x1 x2 s1 s2 Solution Minimum ratio z 1 0 -1/2 3/2 0 12 x1 s2 0 1 1/2 1/2 0 4 8 0 0 5/2 -1/2 1 4 8/5 Third iteration Basic z x1 0 x2 0 s1 14/10 s2 1/5 Solution z 1 128/10 x1 x2 0 1 0 3/5 -1/5 16/5 0 0 1 -1/5 2/5 8/5 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 20

21. Special Cases 1. Alternate optima---Many solutions Maximize z = 4x1 + 2x2 2x1 + x2 8 x1 + 3x2 8 x1, x2 0 2. Unbounded solution---no bound on solution Subject to 2x1 + x2 8 x1 + 3x2 8 3. Infeasible solution---no solution Subject to 2x1 + x2 8 x1 + 3x2 8 x1 10 Plot and verify!!! IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 21

22. Minimization Problem: JOBCO Minimize w = 2x1 + x2 + 0s1 +0s2+0s3 +0s4 Subject to 2x1 + x2 + s1 = 8 x1 + 3x2 + s2 = 8 2x1 + x2 s3 = 5 x1 + 3x2 s4 = 3 x1, x2 , s1, s2, s3, s4 0 s3 and s4 are the surplus variables IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 22

23. Minimization Problem: JOBCO: Simplex Table---Big M Method Minimize w = 2x1 + x2 + 0s1 +0s2+0s3 +0s4+MA1+MA2 Subject to 2x1 + x2 + s1 = 8 x1 + 3x2 + s2 = 8 2x1 + x2 s3 +A1= 5 x1 + 3x2 s4 +A2 = 3 x1, x2 , s1, s2, s3, s4 , A1 , A2 0 s1, s2 = slack variables s3, s4 = surplus variables A1 , A2 =Artificial variables IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 23

24. Simplex Method A company which produces 2 different types of glass products has 3 factories, and the data for the same is as given Capacity per unit production rate Capacity available Product 1 2 Plant 1 1 0 2 0 2 3 3 2 Unit profit (USD) 3 5 4 12 18 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 24

25. Simplex Method The model formulation is as Max Z=3x1+5x2 s.t: x1 <= 4 2x2<=12 3x1+2x2<=18 x1, x2>=0 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 25

26. Simplex Method Introduce slack variables (red coloured) such that equality can be brought into the picture. Thus we have Max Z=3x1+5x2+0x3+0x4+0x5 s.t: x1+x3= 4 2x2+x4=12 3x1+2x2+x5=18 x1, x2, x3, x4, x5,>=0 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 26

27. Initial tableau Basic Variable Z x3 x4 x5 Eq # Z x1 x2 x3 x4 x5 RHS 0 1 2 3 1 0 0 0 -3 1 0 3 -5 0 2 2 0 1 0 0 0 0 1 0 0 0 0 1 0 4 12 18 You main task is to replace the basic variables with the actual real variables or decision variables which for your case is x1 and x2. As this is an maximization problem then make a decision which one will be the entering variables such that it has the largest non-negative coefficient Name the column corresponding to this entering variable as pivot variable, hence we will choose x2. WHY? IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 27

28. Changing tableau Basic Variable Z x3 x4 x5 Eq # Z x1 x2 x3 x4 x5 RHS 0 1 2 3 1 0 0 0 -3 1 0 3 -5 0 2 2 0 1 0 0 0 0 1 0 0 0 0 1 0 4 12 18 Now if a variable enters, one has to leave. We now have to decide which variable leaves. Calculate the ratios of 4/0 (non defined, hence left out), 12/2=6, 18/2=9. Choose the one for which the ratio is the smallest. WHY? The column marked is the pivot column corresponding to x2. IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 28

29. Changing tableau Basic Variable Z x3 x4 x5 Eq # Z x1 x2 x3 x4 x5 RHS 0 1 2 3 1 0 0 0 -3 1 0 3 -5 0 2 2 0 1 0 0 0 0 1 0 0 0 0 1 0 4 12 18 Choose the row corresponding to this as the pivot row and the element common to pivot column and pivot row is the pivot number. Hence x4 leaves and x2 enters and 2 is the pivot number. IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 29

30. Changing tableau Basic Variable Z x3 x2 x5 Eq # Z x1 x2 x3 x4 x5 RHS How are the new rows formed: (New row) = (old row) (pivot column coefficient) X (new pivot row) Eq # 0 has changed as per the following calculation to (-3 -5 0 0 0 0)-(-5)X(0 1 0 0 6)=(- 3 0 0 5/2 0 30) Eq # 1 has changed as per the following calculation to (1 0 1 0 0 4)-(0)X(0 1 0 0 6)=(1 0 1 0 0 4), i.e., it does not change as we have 0 Eq # 2 has changed as per the following calculation to (0 2 0 1 0 12)=(0 1 0 0 6) Eq # 3 has changed as per the following calculation to (3 2 0 0 1 18)-(2)X(0 1 0 0 6)=(3 0 0 -1 1 6) 0 1 2 3 1 0 0 0 -3 1 0 3 0 0 1 0 0 1 0 0 5/2 0 1/2 -1 0 0 0 1 30 4 6 6 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 30

31. Changing tableau Basic Variable Z x3 x2 x5 Eq # Z x1 x2 x3 x4 x5 RHS 0 1 2 3 1 0 0 0 -3 1 0 3 0 0 1 0 0 1 0 0 5/2 0 1/2 -1 0 0 0 1 30 4 6 6 IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 31

32. Changing tableau Basic Variable Z x3 x2 x1 Eq # Z x1 x2 x3 x4 x5 RHS 0 1 2 3 1 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 3/2 1/3 1/2 -1/3 1 -1/3 0 1/3 36 2 6 2 How are the new rows formed: (New row) = (old row) (pivot column coefficient) X (new pivot row) Eq # 0 has changed as per the following calculation to (-3 0 0 5/2 0 30)-(-3)X(1 0 0 -1/3 1/3 2)=(0 0 0 3/2 1 36) Eq # 1 has changed as per the following calculation to (1 0 1 0 0 4)-(1)X(1 0 0 -1/3 1/3 2)=(0 0 1 1/3 -1/3 2) Eq # 2 has changed as per the following calculation to (0 1 0 0 6)-(0)X(1 0 0 -1/3 1/3 2)=(0 1 0 0 6) Eq # 3 has changed as per the following calculation to 1/3(3 0 0 -1 1 6)=(1 0 0 -1/3 1/3 2) IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 32

33. Final solution x=(x1, x2, x3, x4, x5)=(2,6,2,0,0) and maximum Z is 36 What are the constraints now X1+x3=4, hence slack is x2=2 2x2+x4=12, hence slack is x3=0 3x1+2x2+x5=18, hence slack is x5=0 Which would be better? To have all slacks as zeros or optimize IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 33

34. Primal and Dual Problems Primal problem: JOBCO Maximize z = 3x1 + 2x2 Subject to 2x1 + x2 8 x1 + 3x2 8 x1, x2 0 Basic rules for constructing the dual problem Dual problem Objective Constraint Variable sign Primal : Maximization Minimization unrestricted Primal: Minimization IME634 Maximization unrestricted RNSengupta,IME Dept.,IIT Kapur,INDIA 34

35. Primal and Dual Problems Primal problem Maximize z = 3x1 + 2x2 + 0s1+ 0s2 2x1 + x2 + s1+ 0s2 = 8 y1 x1 + 3x2 + 0s1+ s2 = 8 y2 s1 and s2 are the slack variables 0 x1, x2, s1, s2 0 Dual Problem Minimize w = 8y1+8y2 2y1 + y2 3 y1 + 3y2 2 y1 + 0y2 0 and y1 unrestricted y1 0 0y1 + y2 0 and y2 unrestricted y2 0 Dual variables Solving the dual problem will give y1 = 14/10, and y2 = 1/5, which are the dual price or the worth of the resources and objective w = 128/10. Hence, at optimality, z = w. IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 35

36. Rules for Constructing the Dual Problem Primal: Maximization Dual: Minimization Constraints Variables 0 0 = unrestricted Variables Constraints 0 0 unrestricted = = + increase , decrease or + + i y in w.r.t unrestrict is 1 + ed or x x y x x y positive negative + + y + 1 1 1 i i i i i i + i + + i i + = ; . 0 y y y + 1 1 1 1 1 i IME634 RNSengupta,IME Dept.,IIT Kapur,INDIA 36