Unit 3 Lesson 1 - Linear Programming Lecture.pptx

Linear programming is a mathematical method used to find the best possible outcome in a scenario with a few requirements, which are represented by linear relationships. It involves maximizing or minimizing a linear function, known as the objective function, subject to a set of linear constraints or inequalities. This optimization technique is used across many industries to make decisions under limitations, such as limited resources, labor, or time.

1. Linear Programming

2. Lecture Outline Background and Definition of LP Linear Programming Model Graphical Solution Method Simplex Method

3. A model consisting of linear relationships representing a firm’s objective and resource constraints. A model, which is used for optimum allocation of scarce or limited resources to competing products or activities under such assumptions as certainty, linearity, fixed technology, and constant profit per unit. LP is a mathematical modeling technique used to determine a level of operational activity in order to achieve an objective, subject to restrictions called constraints Linear Programming (LP)

4. Any linear programming model (problem) must have the following properties: (a) The relationship between variables and constraints must be linear. (b) The model must have an objective function. (c) The model must have structural constraints. (d) The model must have non-negativity constraint. Properties of Linear Programming

5. Assumptions in LP Proportionality . With linear programs, we assume that the contribution of individual variables in the objective function and constraints is proportional to their value. Additivity . Additivity means that the total value of the objective function and each constraint function is obtained by adding up the individual contributions from each variable. Divisibility . The decision variables are allowed to take on any real numerical values within some range specified by the constraints. Certainty . We assume that the parameter values in the model are known with certainty or are at least treated that way.

6. Applications of LP

7. Applications of LP Aggregate Production Planning Determines the resource capacity needed to meet demand over immediate time horizon, including units produced, workers hired and fired and inventory

8. Applications of LP Product Mix Mix of different products to produce that will maximize profit or minimize cost given resource constraints such as material, labor, budget, etc

9. Applications of LP Transportation Logistical flow of items (goods or services) from sources to destinations, for example, truckloads of goods from plants to warehouses

10. Applications of LP Transshipment Flow of items from sources to destinations with intermediate points, for example shipping from plant to distribution center and then to stores.

11. Applications of LP (cont.)

12. LP Model Formulation

13. LP Model Formulation Decision variables mathematical symbols representing levels of activity of an operation Physical quantities controlled by the decision maker and represented by mathematical symbols. Objective function a linear relationship reflecting the objective of an operation Criterion for evaluating the solution. Function to be optimized (minimize or maximize) Constraints a linear relationship representing a restriction on decision making A set of functional equalities or inequalities that represent physical, economic, technological, legal, ethical, or other restrictions on what numerical values can be assigned to the decision variables.

14. LP Anatomy LP Model Max/min z = c 1 x 1 + c 2 x 2 + ... + c n x n subject to: a 11 x 1 + a 12 x 2 + ... + a 1n x n (≤, =, ≥) b 1 a 21 x 1 + a 22 x 2 + ... + a 2n x n (≤, =, ≥) b 2 : a m1 x1 + a m2 x 2 + ... + a mn x n (≤, =, ≥) b m Parameters or coefficients b i = constraint levels c j = objective function coefficients a ij = constraint coefficients Decision variables x i Objective function Constraints

15. LP Model Formulation Max/min z = c 1 x 1 + c 2 x 2 + ... + c n x n subject to: a 11 x 1 + a 12 x 2 + ... + a 1n x n (≤, =, ≥) b 1 a 21 x 1 + a 22 x 2 + ... + a 2n x n (≤, =, ≥) b 2 : a m1 x1 + a m2 x 2 + ... + a mn x n (≤, =, ≥) b m x j = decision variables b i = constraint levels c j = objective function coefficients a ij = constraint coefficients

16. Steps in LP Modelling

17. Steps in LP Modelling Identify and define the decision variables for the problem . Define the variables completely and precisely. All units of measure need to be stated explicitly, including time units if appropriate. Define the objective function . Determine the criterion for evaluating alternative solutions. The objective function will normally be the sum of terms made up of a variable multiplied by some appropriate coefficient (parameter). Identify and express mathematically all of the relevant constraints . It is often easier to express each constraint in words before putting it into mathematical form.

18. Let’s Do the Modeling!!!

19. Example 1: Textile Industry A retail store stocks two types of shirts A and B . These are packed in attractive cardboard boxes. During a week the store can sell a maximum of 400 shirts of type A and a maximum of 300 shirts of type B . The storage capacity, however, is limited to a maximum of 600 of both types combined. Type A shirt fetches a profit of $2 per unit and type B a profit of $5 per unit. How many of each type the store should stock per week to maximize the total profit? Formulate a mathematical model of the problem.

20. Example 2: Manufacturing A company manufactures two products X and Y, which require, the following resources. The resources are the capacities machine M1, M2, and M3. The available capacities are 50,25,and 15 hours respectively in the planning period. Product X requires 1 hour of machine M2 and 1 hour of machine M3. Product Y requires 2 hours of machine M1, 2 hours of machine M2 and 1 hour of machine M3. The profit contribution of products X and Y are $5 and $4, respectively.

21. Example 3: Agriculture International Wool Company operates a large farm on which sheep are raised. The farm manager determined that for the sheep to grow in the desired fashion, they need at least minimum amounts of four nutrients (the nutrients are nontoxic so the sheep can consume more than the minimum without harm). The manager is considering three different grains to feed the sheep. Table B-2 lists the number of units of each nutrient in each pound of grain, the minimum daily requirements of each nutrient for each sheep, and the cost of each grain. The manager believes that as long as a sheep receives the minimum daily amount of each nutrient, it will be healthy and produce a standard amount of wool. The manager wants to raise the sheep at minimum cost.

22. International Wool Company operates a large farm on which sheep are raised. The farm manager determined that for the sheep to grow in the desired fashion, they need at least minimum amounts of four nutrients (the nutrients are nontoxic so the sheep can consume more than the minimum without harm). The manager is considering three different grains to feed the sheep. Table B-2 lists the number of units of each nutrient in each pound of grain, the minimum daily requirements of each nutrient for each sheep, and the cost of each grain. The manager believes that as long as a sheep receives the minimum daily amount of each nutrient, it will be healthy and produce a standard amount of wool. The manager wants to raise the sheep at minimum cost.

23. It’s Your Turn

24. Practice Problems A company manufactures two products X and Y . The profit contribution of X and Y are $3 and $ 4 respectively. The products X and Y require the services of four facilities. The capacities of the four facilities A , B , C , and D are limited and the available capacities in hours are 200 Hrs , 150 Hrs , and 100 Hrs. and 80 hours respectively. Product X requires 5, 3, 5 and 8 hours of facilities A , B , C and D respectively. Similarly, the requirement of product Y is 4, 5, 5, and 4 hours respectively on A , B , C and D . Find the optimal product mix to maximize the profit. The cost of materials A and B is $1 per unit respectively. We have to manufacture an alloy by mixing these to materials. The process of preparing the alloy is carried out on three facilities X , Y and Z . Facilities X and Z are machines, whose capacities are limited. Y is a furnace, where heat treatment takes place and the material must use a minimum given time (even if it uses more than the required, there is no harm). Material A requires 5 hours of machine X and it does not require processing on machine Z . Material B requires 10 hours of machine X and 1 hour of machine Z . Both A and B are to be heat treated at last one hour in furnace Y . The available capacities of X , Y and Z are 50 hours, 1 hour and 4 hours respectively. Find how much of A and B are mixed so as to minimize the cost

25. Solution to Linear Programming Problems Graphical Method

26. Graphical Solution Method Plot model constraint on a set of coordinates in a plane Identify the feasible solution space on the graph where all constraints are satisfied simultaneously Plot objective function to find the point on boundary of this space that maximizes (or minimizes) value of objective function

27. Graphical Solution: Example 4 x 1 + 3 x 2  120 lb x 1 + 2 x 2  40 hr Area common to both constraints 50 – 40 – 30 – 20 – 10 – – | 10 | 60 | 50 | 20 | 30 | 40 x 1 x 2

28. Computing Optimal Values x 1 + 2 x 2 = 40 4 x 1 + 3 x 2 = 120 4 x 1 + 8 x 2 = 160 -4 x 1 - 3 x 2 = -120 5 x 2 = 40 x 2 = 8 x 1 + 2(8) = 40 x 1 = 24 4 x 1 + 3 x 2  120 lb x 1 + 2 x 2  40 hr 40 – 30 – 20 – 10 – – | 10 | 20 | 30 | 40 x 1 x 2 Z = $50(24) + $50(8) = $1,360 24 8

29. Extreme Corner Points x 1 = 224 bowls x 2 =  8 mugs Z = $1,360 x 1 = 30 bowls x 2 =  0 mugs Z = $1,200 x 1 = 0 bowls x 2 =  20 mugs Z = $1,000 A B C | 20 | 30 | 40 | 10 x 1 x 2 40 – 30 – 20 – 10 – –

30. 4 x 1 + 3 x 2  120 lb x 1 + 2 x 2  40 hr 40 – 30 – 20 – 10 – – B | 10 | 20 | 30 | 40 x 1 x 2 C A Z = 70 x 1 + 20 x 2 Optimal point: x 1 = 30 bowls x 2 =  0 mugs Z = $2,100 Objective Function

31. Minimization Problem CHEMICAL CONTRIBUTION Brand Nitrogen (lb/bag) Phosphate (lb/bag) Gro-plus 2 4 Crop-fast 4 3 Minimize Z = $6x 1 + $3x 2 subject to 2 x 1 + 4 x 2  16 lb of nitrogen 4 x 1 + 3 x 2  24 lb of phosphate x 1 , x 2  0

32. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- 32 14 – 12 – 10 – 8 – 6 – 4 – 2 – – | 2 | 4 | 6 | 8 | 10 | 12 | 14 x 1 x 2 A B C Graphical Solution x 1 = 0 bags of Gro-plus x 2 = 8 bags of Crop-fast Z = $24 Z = 6 x 1 + 3 x 2

33. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- 33 Simplex Method A mathematical procedure for solving linear programming problems according to a set of steps Slack variables added to ≤ constraints to represent unused resources x 1 + 2x 2 + s 1 =40 hours of labor 4x 1 + 3x 2 + s 2 =120 lb of clay Surplus variables subtracted from ≥ constraints to represent excess above resource requirement. For example 2 x 1 + 4 x 2 ≥ 16 is transformed into 2 x 1 + 4 x 2 - s 1 = 16 Slack/surplus variables have a 0 coefficient in the objective function Z = $40x 1 + $50x 2 + 0s 1 + 0s 2

34. Copyright 2006 John Wiley & Sons, Inc. Supplement 13- 34 Solution Points with Slack Variables

35. Solution Points with Surplus Variables

36. Problem 2.5. A machine tool company conducts a job-training programme at a ratio of one for every ten trainees. The training programme lasts for one month. From past experience it has been found that out of 10 trainees hired, only seven complete the programme successfully. (The unsuccessful trainees are released). Trained machinists are also needed for machining. The company's requirement for the next three months is as follows: January: 100 machinists, February: 150 machinists and March: 200 machinists. In addition, the company requires 250 trained machinists by April. There are 130 trained machinists available at the beginning of the year. Pay roll cost per month is: Each trainee Rs. 400/- per month. Each trained machinist (machining or teaching): Rs. 700/- p.m. Each trained machinist who is idle: Rs.500/- p.m. ( Labour union forbids ousting trained machinists). Build a l.p.p. for produce the minimum cost hiring and training schedule and meet the company’s requirement.

37. A ship has three cargo holds, forward, aft and center. The capacity limits are: Forward 2000 tons, 100,000 cubic meters Center 3000 tons, 135,000 cubic meters Aft 1500 tons, 30,000 cubic meters. The following cargoes are offered, the ship owners may accept all or any part of each commodity: Commodity Amount in tons. Volume/ton in cubic meters Profit per ton in Rs. A 6000 60 60 B 4000 50 80 C 2000 25 50 26 Operations Research In order to preserve the trim of the ship the weight in each hold must be proportional to the capacity in tons. How should the cargo be distributed so as to maximize profit? Formulate this as linear programming problem.

38. Simplex Method - exercises 1) A company produces 3 different products : A, B and C. Each product has to go under 3 processes consuming different amounts of time along the way . The time available for each process is described in the table below . Assuming the selling profits for products A, B and C are 2, 3 and 4€ per unit . Determine how many units of each product should be produced to maximize the profit . Was there any time left ? Process Total number of hours available Number of hours needed to produce each product A B C I 12000 5 2 4 II 24000 4 5 6 III 18000 3 5 4

39. Simplex Method - exercises 2) A company produces 3 diferente bookshelves : a luxury , a regular and na exportation model . Consider the maximum demand for each model to be 500, 750 and 400 respectively . The working hours at the carpentry and finishing sections have the working time limitations below : Assuming the selling profit for the luxury , regular and exportation models is 1500, 1300 2500 respectively , formulate the LP problema in order to maximize the profit . Interpret the results detailling the optimal number of bookshelves of each type produced discussing the total amount of hours used in each section . How far from meeting the maximum demands were we ? Section Total number of hours (thousands) Number of hours needed to produce each model luxury regular exportation carpentry 1.4 0.5 0.5 1.0 finishing 1.2 0.5 0.5 2.0

40. Simplex Method - exercises 3) Max: Z = x 1 + 2 x 2 Subject to: 2x 1 + 4x 2 ≤ 20 x 1 + x 2 ≤ 8 and x 1 x 2 ≥ 0 4) Max: Z = x 1 + x 2 Subject to: x 1 + x 2 ≤ 4 2 x 1 + x 2 ≤ 6 x 1 + 2 x 2 ≤ 6 and x 1 x 2 ≥ 0 5) Max: Z = x 1 + x 2 Subject to: x 1 + x 2 ≤ 10 2 x 1 - 3 x 2 ≤ 15 x 1 - 2 x 2 ≤ 20 and x 1 x 2 ≥ 0 Apply the Simplex to find the optimal solution Multiple , unbound and degenerate solutions

41. Simplex Method - exercises Max: Z = 10 x 1 + 30 x 2 Subject to: x 1 ≤ 15 x 1 - x 2 ≤ 20 -3 x 1 + x 2 ≤ -30 and x 1 ≥ 0 x 2 ≤ 0 7) 8) Bring the following PL problems to standard form and apply the Simplex to find the optimal solution Minimization , negative RHS, negative and unbounded variables 6) Min: Z = 2 x 1 - 3 x 2 – 4 x 3 Subject to: x 1 + 5 x 2 - 3 x 3 ≤ 15 x 1 + x 2 + x 3 ≤ 11 5 x 1 – 6 x 2 + x 3 ≤ 4 and x 1 x 2 x 3 ≥ 0 Max: Z = - x 2 Subject to: x 1 + x 2 + x 3 ≤ 100 x 1 - 5 x 2 ≤ 40 x 3 ≥ -10 and x 1 ≥ 0 x 2 ≤ 0 x 3 unbounded

42. Simplex Method - exercises 10) Bring the following PL problems to standard form introducing artificial variables apply the big M method using Simplex to find the optimal solutions 9) Max: Z = x 1 + 2 x 2 Subject to: x 1 + x 2 ≤ 10 x 1 - 2 x 2 ≥ 6 x 1 , x 2 ≥ 0 Min: Z = 4 x 1 + 2 x 2 Subject to: 2 x 1 - x 2 ≥ 4 x 1 + x 2 ≥ 5 x 1 , x 2 ≥ 0

43. Given the following linear programming model: Min Z=4x1+x2 s.t. 3x1+6x2>=15 8x1+2x2>=12 x1, x2>=0 Solve graphically and using the simplex method. What type of special case is this problem? Explain? 3. Transform the following linear programming model into proper form and setup the initial tableau. Do not solve it. Min Z=40x1+55x2+30x3 s.t. x1+2x2+3x3 <=60 2x1+x2+x3 = 40 x1+3x2+x3>=50 5x2+x3>=100 x1, x2, x3>=0 4. Given the following linear programming model: Max Z=x1+2x2-x3 s.t. 4x2+x3<=40 x1-x2<=20 2x1+4x2+3x3<=60 x1, x2, x3>=0 Solve this problem using the simplex method. What type of special case is this problem? Explain?

44. Worked Out Problems

45. 47 Example Problem Maximize Z = 5x 1 + 2x 2 + x 3 subject to x 1 + 3x 2 - x 3 ≤ 6, x 2 + x 3 ≤ 4, 3x 1 + x 2 ≤ 7, x 1 , x 2 , x 3 ≥ 0.

46. 48 Simplex and Example Problem Step 1. Convert to Standard Form a 11 x 1 + a 12 x 2 + ••• + a 1n x n ≤ b 1 , a 21 x 1 + a 22 x 2 + ••• + a 2n x n ≥ b 2 , a m1 x 1 + a m2 x 2 + ••• + a mn x n ≤ b m , a 11 x 1 + a 12 x 2 + ••• + a 1n x n + x n+1 = b 1 , a 21 x 1 + a 22 x 2 + ••• + a 2n x n - x n+2 = b 2 , a m1 x 1 + a m2 x 2 + ••• + a mn x n + x n+k = b m , In our example problem: x 1 + 3x 2 - x 3 ≤ 6, x 2 + x 3 ≤ 4, 3x 1 + x 2 ≤ 7, x 1 , x 2 , x 3 ≥ 0. x 1 + 3x 2 - x 3 + x 4 = 6, x 2 + x 3 + x 5 = 4, 3x 1 + x 2 + x 6 = 7, x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ≥ 0.

47. 49 Simplex: Step 2 Step 2. Start with an initial basic feasible solution (b.f.s.) and set up the initial tableau. In our example Maximize Z = 5x 1 + 2x 2 + x 3 x 1 + 3x 2 - x 3 + x 4 = 6, x 2 + x 3 + x 5 = 4, 3x 1 + x 2 + x 6 = 7, x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ≥ 0.

48. 50 Step 2: Explanation Adjacent Basic Feasible Solution If we bring a nonbasic variable x s into the basis, our system changes from the basis, x b , to the following (same notation as the book): x 1 + ā 1s x s = x r + ā rs x r = x m + ā ms x s = x i = for i =1, …, m x s = 1 x j = 0 for j=m+1, ..., n and j s The new value of the objective function becomes: Thus the change in the value of Z per unit increase in x s is = new value of Z - old value of Z = = This is the Inner Product rule

49. 51 Simplex: Step 3 Use the inner product rule to find the relative profit coefficients c 1 = 5 - 0(1) - 0(0) - 0(3) = 5 -> largest positive c 2 = …. c 3 = …. Step 4: Is this an optimal basic feasible solution?

50. 52 Simplex: Step 5 Apply the minimum ratio rule to determine the basic variable to leave the basis. The new values of the basis variables: x i = for i = 1, ..., m In our example: Row Basic Variable Ratio 1 x 4 6 2 x 5 - 3 x 6 7/3

51. 53 Simplex: Step 6 Perform the pivot operation to get the new tableau and the b.f.s. c 2 = 2 - (0) 8/3 - (0) 1 - (5) 1/3 = 1/3 c 3 = 1 - (0) (-1) - (0) 1 - (5) 0 = 1 c 6 = 0 - (0) 0 - (0) 0 - (5) 1/3 = -5/3 c B = (0 0 5) New iteration: find entering variable:

52. 54 Final Tableau x 3 enters basis, x 5 leaves basis Wrong value! 4 should be 11/3