Description
Please find attached Operation Research Presentation FYI.
The origin of Operations Research was during the Second World-War. ? The military management in England called upon a team of scientists to study the strategic problems related to air force and Defence of the country. Their aim was effective utilization of limited resources to have higher impact. ? e.g. the efficient ocean transport ,effective bombing etc.
?
?
‘Operations Research ‘ was apparently invented because the team was dealing with research on (military) operations.
The impact of O.R. can be felt in many areas such as(to name a few)
? ? ? ? Transportation system Hospitals Libraries Financial institutions
?
OR is the application of scientific methods, techniques and tools to problems involving the operations of systems so as to provide these in control of the operations with optimum solutions to the problem. Hence OR is inherently inter-disciplinary in nature with applications not only in military and business but also in medicine, engineering,physics etc.,
?
? ?
?
?
? ?
Phase I: Formulating the problem Phase II: Constructing a Mathematical Model Phase III : Deriving the solutions from the model Phase IV : Testing the Model and its Updation Phase V : Controlling the solution Phase VI : Implementing the solution
Finance-Budgeting and Investments ? Purchasing, Procurement and Exploration ? Production Management ? Marketing ? Personnel Management ? Research and Development
?
?
Imagine that you have a 5- week business commitment between Colorado(COL) and Denver(DEN).You fly out of Colorado on Monday and return on Wednesday. A regular round –trip ticket costs $400, but a 20% discount is granted if the dates of the ticket span a weekend. A one-way ticket in either direction costs 75% of the regular price. How should you buy the tickets for the five week period?
?
This situation is a decision making problem whose solution requires identifying three main components.
? What are the decision alternatives? ? Under what restrictions is the decision made? ? What is an appropriate Objective criterion for evaluating the alternatives?
?
Buy five regular COL-DEN-COL. Buy one COL-DEN, four DEN-COL-DEN that span weekends, and one DEN-COL. Buy one COL-DEN-COL to cover Monday of the first week and Wednesday of the last week and four DEN-COL-DEN that span weekends to cover the remaining legs
?
?
?
Restriction: You have to leave from Colorado on Monday and return on Wednesday of the same week.
?
Objective: Minimize the total amount spent on ticket.
?
Solution:
Alternative 1 cost = 5 × 400 = $2000 Alternative 2 cost = .75 × 400 + 4 × 400 + .75 × 400 = $2200 Alternative 3 cost = 5 × (.8 × 400) = $1600 Conclusion : Choose alternative 3.
?
?
?
?
Alternatives ? Restrictions ? Objective criterion.
?
Note:Alternatives of the decision problem may take the form of a unknown variables.Which are used to form the restrictions and objective.
?
What is a Mathematical Model?
? Model which relates all the three principle components of a OR model mathematically is a Mathematical Model.
?
What is an Optimum Feasible Solution?
? The values of the decision variables that optimizes the objective function and also satisfies all the constraints is an optimum feasible solution.
?
Mathematical Model vs Human element:
?
Situation : Elevator problem.
?
?
?
Many management decisions involve trying to make the most effective use of limited resources ? Machinery, labor, money, time, warehouse space, raw materials Linear programming (LP) is a widely used mathematical LP modeling technique designed to help managers in planning and decision making relative to resource allocation Belongs to the broader field of mathematical programming
? ?
LP has been applied in many areas over the past 50 years All LP problems have 4 properties in common 1. All problems seek to maximize or minimize some quantity (the objective function) function 2. The presence of restrictions or constraints that limit the degree to which we can pursue our objective 3. There must be alternative courses of action to choose from 4. The objective and constraints in problems must be expressed in terms of linear equations or inequalities
PROPERTIES 1. One objective function 2. One or more constraints 3. Alternative courses of action 4. Objective function and constraints are linear ASSUMPTION 1. Certainty 2. 3. 4. 5. Proportionality Additivity Divisibility Nonnegative variables
?
?
?
?
?
We assume conditions of certainty exist and numbers in the objective and constraints are known with certainty and do not change during the period being studied We assume proportionality exists in the objective and constraints We assume additivity in that the total of all activities equals the sum of the individual activities We assume divisibility in that solutions need not be whole numbers All answers or variables are nonnegative
?
?
Formulating a linear program involves developing a mathematical model to represent the managerial problem The steps in formulating a linear program are 1. Understand the managerial problem being faced 2. Identify the objective Function and constraints 3. Define the decision variables. 4. Use the decision variables to write mathematical expressions for the objective function and the constraints
?
?
?
?
One of the most common LP applications is the product mix problem Two or more products are produced using limited resources such as personnel, machines, and raw materials The profit that the firm seeks to maximize is based on the profit contribution per unit of each product The company would like to determine how many units of each product it should produce so as to maximize overall profit given its limited resources
? The X Furniture Company produces inexpensive tables and ?
? ? ? ?
chairs Processes are similar in that both require a certain amount of hours of carpentry work and in the painting and varnishing department Each table takes 4 hours of carpentry and 2 hours of painting and varnishing Each chair requires 3 of carpentry and 1 hour of painting and varnishing There are 240 hours of carpentry time available and 100 hours of painting and varnishing Each table yields a profit of Rs. 70 and each chair a profit of Rs.50
?
The company wants to determine the best combination of tables and chairs to produce to reach the maximum profit
HOURS REQUIRED TO PRODUCE 1 UNIT DEPARTMENT Carpentry Painting and varnishing Profit per unit (T) TABLES (C) CHAIRS AVAILABLE HOURS THIS WEEK 4 2 Rs 70 3 1 Rs 50 240 100
? The objective is to
Maximize profit
? The constraints are
1. The hours of carpentry time used cannot exceed 240 hours per week 2. The hours of painting and varnishing time used cannot exceed 100 hours per week ? The decision variables representing the actual decisions we will make are T = number of tables to be produced per week C = number of chairs to be produced per week
? We create the LP objective function in terms of T and C
Maximize profit = $70T + $50C ? Develop mathematical relationships for the two constraints ? For carpentry, total time used is (4 hours per table)(Number of tables produced) + (3 hours per chair)(Number of chairs produced) ? We know that Carpentry time used ? Carpentry time available 4T + 3C ? 240 (hours of carpentry time)
? Similarly
Painting and varnishing time used ? Painting and varnishing time available 2 T + 1C ? 100 (hours of painting and varnishing time) This means that each table produced requires two hours of painting and varnishing time
? Both of these constraints restrict production capacity and
affect total profit
? The values for T and C must be nonnegative
T ? 0 (number of tables produced is greater than or equal to 0) C ? 0 (number of chairs produced is greater than or equal to 0) ? The complete problem stated mathematically
subject to
Maximize profit = 70T + 50C
3C ? 1C ? ? 0
240 (carpentry constraint) 100 (painting and varnishing constraint) (nonnegativity constraint)
? The easiest way to solve a small LP problems is
with the graphical solution approach ? The graphical method only works when there are just two decision variables ? When there are more than two variables, a more complex approach is needed as it is not possible to plot the solution on a two-dimensional graph ? The graphical method provides valuable insight into how other approaches work
C 100 – – Number of Chairs 80 – – 60 – – 40 – – 20 – – 0 Figure 7.1
|– | | | | | | | | | | |
This Axis Represents the Constraint T ? 0
This Axis Represents the Constraint C ? 0
20
40
60
80
100
T
Number of Tables
The first step in solving the problem is to identify a set or region of feasible solutions ? To do this we plot each constraint equation on a graph ? We start by graphing the equality portion of the constraint equations 4T + 3C = 240 ? We solve for the axis intercepts and draw the line
?
When X produces no tables, the carpentry constraint is 4(0) + 3C = 240 3C = 240 C = 80 ? Similarly for no chairs 4T + 3(0) = 240 4T = 240 T = 60 ? This line is shown on the following graph
?
C 100 – – Number of Chairs 80 – – 60 – – 40 – – 20 – – 0 Figure 7.2
|– | | | |
Graph of carpentry constraint equation (T = 0, C = 80)
(T = 60, C = 0)
| | | | | | |
20
40
60
80
100
T
Number of Tables
C 100 – – Number of Chairs 80 – – 60 – – 40 – – 20 – – 0 Figure 7.3
|– |
? Any point on or below the
constraint plot will not violate the restriction ? Any point above the plot will violate the restriction
(30, 40)
(70, 40)
(30, 20)
| | | | | | | | | |
20
40
60
80
100
T
Number of Tables
?
The point (30, 40) lies on the plot and exactly satisfies the constraint 4(30) + 3(40) = 240 The point (30, 20) lies below the plot and satisfies the constraint 4(30) + 3(20) = 180 The point (30, 40) lies above the plot and does not satisfy the constraint 4(70) + 3(40) = 400
?
?
C 100 – – Number of Chairs 80 – – 60 – – 40 – – 20 – – 0 Figure 7.4
|– | | | | | | | | | | |
(T = 0, C = 100) Graph of painting and varnishing constraint equation
(T = 50, C = 0)
20
40
60
80
100
T
Number of Tables
?
?
? ?
? ?
To produce tables and chairs, both departments must be used We need to find a solution that satisfies both constraints simultaneously A new graph shows both constraint plots The feasible region (or area of feasible solutions) is solutions where all constraints are satisfied Any point inside this region is a feasible solution Any point outside the region is an infeasible solution
C 100 – – Number of Chairs 80 – – 60 – – 40 – –
? Feasible solution region for X Furniture
Painting/Varnishing Constraint
20 – Feasible – 0 Figure 7.5
|–
Carpentry Constraint
| | | | | | | |
Region
| |
|
20
40
60
80
100
T
Number of Tables
?
For the point (30, 20)
4T + 3C ? 240 hours available (4)(30) + (3)(20) = 180 hours used 2T + 1C ? 100 hours available (2)(30) + (1)(20) = 80 hours used
? ?
Carpentry constraint Painting constraint
?
For the point (70, 40)
Carpentry constraint Painting constraint
4T + 3C ? 240 hours available (4)(70) + (3)(40) = 400 hours used 2T + 1C ? 100 hours available (2)(70) + (1)(40) = 180 hours used
? ?
?
For the point (50, 5)
4T + 3C ? 240 hours available (4)(50) + (3)(5) = 215 hours used 2T + 1C ? 100 hours available (2)(50) + (1)(5) = 105 hours used
?
Carpentry constraint Painting constraint
?
?
? ? ?
?
Once the feasible region has been graphed, we need to find the optimal solution from the many possible solutions The speediest way to do this is to use the isoprofit line method Starting with a small but possible profit value, we graph the objective function We move the objective function line in the direction of increasing profit while maintaining the slope The last point it touches in the feasible region is the optimal solution
? ?
?
? ? ?
?
For X Furniture, choose a profit of $2,100 The objective function is then $2,100 = 70T + 50C Solving for the axis intercepts, we can draw the graph This is obviously not the best possible solution Further graphs can be created using larger profits The further we move from the origin, the larger the profit will be The highest profit ($4,100) will be generated when the isoprofit line passes through the point (30, 40)
C 100 – – Number of Chairs 80 – – 60 – – – 20 – – 0 Figure 7.6
|– | | | |
? Isoprofit line at $2,100
40 –
(0, 42)
$2,100 = $70T + $50C (30, 0)
| | | | | | |
20
40
60
80
100
T
Number of Tables
C 100 – – Number of Chairs 80 – – 60 – – 40 – – 20 – – 0 Figure 7.7
|– | | | |
? Four isoprofit lines
$3,500 = $70T + $50C $2,800 = $70T + $50C $2,100 = $70T + $50C $4,200 = $70T + $50C
|
|
|
|
|
|
|
20
40
60
80
100
T
Number of Tables
C 100 – – Number of Chairs 80 – – 60 – – 40 – – 20 – – 0 Figure 7.8
|– | | | |
? Optimal solution to the X
Furniture problem
Maximum Profit Line Optimal Solution Point (T = 30, C = 40) $4,100 = $70T + $50C
|
|
|
|
|
|
|
20
40
60
80
100
T
Number of Tables
A second approach to solving LP problems employs the corner point method ? It involves looking at the profit at every corner point of the feasible region ? The mathematical theory behind LP is that the optimal solution must lie at one of the corner points, or extreme point, in the feasible region points point ? For X Furniture, the feasible region is a four-sided polygon with four corner points labeled 1, 2, 3, and 4 on the graph
?
C 100 – Number of Chairs
? Four corner points of the
feasible region
2 –
80 – – 60 – – 40 – – 20 – –
| | | | | | | | | | |
3
1 |–
0 Figure 7.9
20
40
Number of Tables
4 60
80
100
T
Point 1 Point 2 $4,000 4 Point 3 $3,500
: (T = 0, C = 0) Profit = $70(0) + $50(0) = $0 : (T = 0, C = 80) Profit = $70(0) + $50(80) = : (T = 50, C = 0) Profit = $70(50) + $50(0) =
Point : (T = 30, C = 40) Profit = $70(30) + ? Because Point 3 returns the highest profit, this is the optimal $50(40) = $4,100 solution
To find the coordinates for Point accurately we have to solve for the intersection of the two constraint lines ? The details of this are on the following slide
?
?
Using the simultaneous equations method, we multiply the method painting equation by –2 and add it to the carpentry equation
4T + 3C = 240 – 4T – 2C = –200 C= 40
?
(carpentry line) (painting line)
Substituting 40 for C in either of the original equations allows us to determine the value of T 4T + (3)(40) = 4T + 120 = T= 240 240 30 (carpentry line)
ISOPROFIT METHOD 1. Graph all constraints and find the feasible region. 2. Select a specific profit (or cost) line and graph it to find the slope. 3. Move the objective function line in the direction of increasing profit (or decreasing cost) while maintaining the slope. The last point it touches in the feasible region is the optimal solution. 4. Find the values of the decision variables at this last point and compute the profit (or cost). CORNER POINT METHOD 1. Graph all constraints and find the feasible region. 2. Find the corner points of the feasible reason. 3. Compute the profit (or cost) at each of the feasible corner points. 4. select the corner point with the best value of the objective function found in Step 3. This is the optimal solution. Table 7.3
?
Reddy Mikks produces both interior and exterior paints from two raw materials.M1 and M2.The following table provides the basic data of the problem:
Exterior paint Raw material M1 Raw Material M2 Profit per ton($1000) 6 1 5
Interior paint 4 2 4
Maximum daily availability(tons) 24 6
?
A market survey restricts the maximum daily demand of interior paint to 2 tons.Additionally , the demand for the interior paint cannot exceed that of exterior paint by more than 1 ton. Reddy Mikks wants to determine the optimum product mix of interior and exterior paints that maximizes the daily profit.
Let Xi be the decision variables,(for eg.,Number of units of product A to produce)
Ci be one unit effect of each Xi on the objective.
Then the objective function is Maximize or Minimize Z = C1X1 + C2X2 + …+ CnXn
?
There are three general forms of constraints: Less-than-or-equal-to variety(limited resources) Greater -than-or-equal-to variety(requirements that must be met) Equal-to variety Let aij be the per unit consumption(in case of <= variety) or per unit contribution(in case of >= variety) and bi is the upper limit which cannot be exceeded in case of <= variety or it is the lower limit (>=)
•
•
•
?
Therefore the constraints are: a11X1 +a12X2 + ………….+a1nXn ?=? b1 a21x1 +a22X2 +………….+a2nXn
.
?=? b2
.
.
an1X1 +…………………..+anmXn ?=?bm
Non- negative restrictons are: Xi ? 0 for all values of i
The Illini Metal company produces a certain casting which must contain minimum amounts of various metals. They have four types of ore to choose from, and they want to select from these ores in such a way as to minimize the cost of producing the product. Once the ores are selected,the metal must be refined. The cost of refining a pound of ore is the same regardless of the type. The casting requires a minimum of 20 ounces of lead , 24 ounces of copper, and 30 ounces of cast iron.Type 1 ore has been analyzed and found to contain 2 ounces of lead, 1 ounce of copper, and 1 ounce of cast iron per pound. One pound of type 2 ore contains 1,3,3 ounces respectively .A pound of type 3 contains ½ ,2,2 ounces resply and type 4 ore contains 1/4,1/2, and 4 ounces respectively.
Type 1 ore costs $10 pounds,Type2 ore costs $15perpound,Type3 ore costs$30 per pound and
? ?
Type 4 ore costs$25 per pound. Define the decision variables. Set up the linear programming model.
doc_634028720.ppt
Please find attached Operation Research Presentation FYI.
The origin of Operations Research was during the Second World-War. ? The military management in England called upon a team of scientists to study the strategic problems related to air force and Defence of the country. Their aim was effective utilization of limited resources to have higher impact. ? e.g. the efficient ocean transport ,effective bombing etc.
?
?
‘Operations Research ‘ was apparently invented because the team was dealing with research on (military) operations.
The impact of O.R. can be felt in many areas such as(to name a few)
? ? ? ? Transportation system Hospitals Libraries Financial institutions
?
OR is the application of scientific methods, techniques and tools to problems involving the operations of systems so as to provide these in control of the operations with optimum solutions to the problem. Hence OR is inherently inter-disciplinary in nature with applications not only in military and business but also in medicine, engineering,physics etc.,
?
? ?
?
?
? ?
Phase I: Formulating the problem Phase II: Constructing a Mathematical Model Phase III : Deriving the solutions from the model Phase IV : Testing the Model and its Updation Phase V : Controlling the solution Phase VI : Implementing the solution
Finance-Budgeting and Investments ? Purchasing, Procurement and Exploration ? Production Management ? Marketing ? Personnel Management ? Research and Development
?
?
Imagine that you have a 5- week business commitment between Colorado(COL) and Denver(DEN).You fly out of Colorado on Monday and return on Wednesday. A regular round –trip ticket costs $400, but a 20% discount is granted if the dates of the ticket span a weekend. A one-way ticket in either direction costs 75% of the regular price. How should you buy the tickets for the five week period?
?
This situation is a decision making problem whose solution requires identifying three main components.
? What are the decision alternatives? ? Under what restrictions is the decision made? ? What is an appropriate Objective criterion for evaluating the alternatives?
?
Buy five regular COL-DEN-COL. Buy one COL-DEN, four DEN-COL-DEN that span weekends, and one DEN-COL. Buy one COL-DEN-COL to cover Monday of the first week and Wednesday of the last week and four DEN-COL-DEN that span weekends to cover the remaining legs
?
?
?
Restriction: You have to leave from Colorado on Monday and return on Wednesday of the same week.
?
Objective: Minimize the total amount spent on ticket.
?
Solution:
Alternative 1 cost = 5 × 400 = $2000 Alternative 2 cost = .75 × 400 + 4 × 400 + .75 × 400 = $2200 Alternative 3 cost = 5 × (.8 × 400) = $1600 Conclusion : Choose alternative 3.
?
?
?
?
Alternatives ? Restrictions ? Objective criterion.
?
Note:Alternatives of the decision problem may take the form of a unknown variables.Which are used to form the restrictions and objective.
?
What is a Mathematical Model?
? Model which relates all the three principle components of a OR model mathematically is a Mathematical Model.
?
What is an Optimum Feasible Solution?
? The values of the decision variables that optimizes the objective function and also satisfies all the constraints is an optimum feasible solution.
?
Mathematical Model vs Human element:
?
Situation : Elevator problem.
?
?
?
Many management decisions involve trying to make the most effective use of limited resources ? Machinery, labor, money, time, warehouse space, raw materials Linear programming (LP) is a widely used mathematical LP modeling technique designed to help managers in planning and decision making relative to resource allocation Belongs to the broader field of mathematical programming
? ?
LP has been applied in many areas over the past 50 years All LP problems have 4 properties in common 1. All problems seek to maximize or minimize some quantity (the objective function) function 2. The presence of restrictions or constraints that limit the degree to which we can pursue our objective 3. There must be alternative courses of action to choose from 4. The objective and constraints in problems must be expressed in terms of linear equations or inequalities
PROPERTIES 1. One objective function 2. One or more constraints 3. Alternative courses of action 4. Objective function and constraints are linear ASSUMPTION 1. Certainty 2. 3. 4. 5. Proportionality Additivity Divisibility Nonnegative variables
?
?
?
?
?
We assume conditions of certainty exist and numbers in the objective and constraints are known with certainty and do not change during the period being studied We assume proportionality exists in the objective and constraints We assume additivity in that the total of all activities equals the sum of the individual activities We assume divisibility in that solutions need not be whole numbers All answers or variables are nonnegative
?
?
Formulating a linear program involves developing a mathematical model to represent the managerial problem The steps in formulating a linear program are 1. Understand the managerial problem being faced 2. Identify the objective Function and constraints 3. Define the decision variables. 4. Use the decision variables to write mathematical expressions for the objective function and the constraints
?
?
?
?
One of the most common LP applications is the product mix problem Two or more products are produced using limited resources such as personnel, machines, and raw materials The profit that the firm seeks to maximize is based on the profit contribution per unit of each product The company would like to determine how many units of each product it should produce so as to maximize overall profit given its limited resources
? The X Furniture Company produces inexpensive tables and ?
? ? ? ?
chairs Processes are similar in that both require a certain amount of hours of carpentry work and in the painting and varnishing department Each table takes 4 hours of carpentry and 2 hours of painting and varnishing Each chair requires 3 of carpentry and 1 hour of painting and varnishing There are 240 hours of carpentry time available and 100 hours of painting and varnishing Each table yields a profit of Rs. 70 and each chair a profit of Rs.50
?
The company wants to determine the best combination of tables and chairs to produce to reach the maximum profit
HOURS REQUIRED TO PRODUCE 1 UNIT DEPARTMENT Carpentry Painting and varnishing Profit per unit (T) TABLES (C) CHAIRS AVAILABLE HOURS THIS WEEK 4 2 Rs 70 3 1 Rs 50 240 100
? The objective is to
Maximize profit
? The constraints are
1. The hours of carpentry time used cannot exceed 240 hours per week 2. The hours of painting and varnishing time used cannot exceed 100 hours per week ? The decision variables representing the actual decisions we will make are T = number of tables to be produced per week C = number of chairs to be produced per week
? We create the LP objective function in terms of T and C
Maximize profit = $70T + $50C ? Develop mathematical relationships for the two constraints ? For carpentry, total time used is (4 hours per table)(Number of tables produced) + (3 hours per chair)(Number of chairs produced) ? We know that Carpentry time used ? Carpentry time available 4T + 3C ? 240 (hours of carpentry time)
? Similarly
Painting and varnishing time used ? Painting and varnishing time available 2 T + 1C ? 100 (hours of painting and varnishing time) This means that each table produced requires two hours of painting and varnishing time
? Both of these constraints restrict production capacity and
affect total profit
? The values for T and C must be nonnegative
T ? 0 (number of tables produced is greater than or equal to 0) C ? 0 (number of chairs produced is greater than or equal to 0) ? The complete problem stated mathematically
subject to
Maximize profit = 70T + 50C
3C ? 1C ? ? 0
240 (carpentry constraint) 100 (painting and varnishing constraint) (nonnegativity constraint)
? The easiest way to solve a small LP problems is
with the graphical solution approach ? The graphical method only works when there are just two decision variables ? When there are more than two variables, a more complex approach is needed as it is not possible to plot the solution on a two-dimensional graph ? The graphical method provides valuable insight into how other approaches work
C 100 – – Number of Chairs 80 – – 60 – – 40 – – 20 – – 0 Figure 7.1
|– | | | | | | | | | | |
This Axis Represents the Constraint T ? 0
This Axis Represents the Constraint C ? 0
20
40
60
80
100
T
Number of Tables
The first step in solving the problem is to identify a set or region of feasible solutions ? To do this we plot each constraint equation on a graph ? We start by graphing the equality portion of the constraint equations 4T + 3C = 240 ? We solve for the axis intercepts and draw the line
?
When X produces no tables, the carpentry constraint is 4(0) + 3C = 240 3C = 240 C = 80 ? Similarly for no chairs 4T + 3(0) = 240 4T = 240 T = 60 ? This line is shown on the following graph
?
C 100 – – Number of Chairs 80 – – 60 – – 40 – – 20 – – 0 Figure 7.2
|– | | | |
Graph of carpentry constraint equation (T = 0, C = 80)
(T = 60, C = 0)
| | | | | | |
20
40
60
80
100
T
Number of Tables
C 100 – – Number of Chairs 80 – – 60 – – 40 – – 20 – – 0 Figure 7.3
|– |
? Any point on or below the
constraint plot will not violate the restriction ? Any point above the plot will violate the restriction
(30, 40)
(70, 40)
(30, 20)
| | | | | | | | | |
20
40
60
80
100
T
Number of Tables
?
The point (30, 40) lies on the plot and exactly satisfies the constraint 4(30) + 3(40) = 240 The point (30, 20) lies below the plot and satisfies the constraint 4(30) + 3(20) = 180 The point (30, 40) lies above the plot and does not satisfy the constraint 4(70) + 3(40) = 400
?
?
C 100 – – Number of Chairs 80 – – 60 – – 40 – – 20 – – 0 Figure 7.4
|– | | | | | | | | | | |
(T = 0, C = 100) Graph of painting and varnishing constraint equation
(T = 50, C = 0)
20
40
60
80
100
T
Number of Tables
?
?
? ?
? ?
To produce tables and chairs, both departments must be used We need to find a solution that satisfies both constraints simultaneously A new graph shows both constraint plots The feasible region (or area of feasible solutions) is solutions where all constraints are satisfied Any point inside this region is a feasible solution Any point outside the region is an infeasible solution
C 100 – – Number of Chairs 80 – – 60 – – 40 – –
? Feasible solution region for X Furniture
Painting/Varnishing Constraint
20 – Feasible – 0 Figure 7.5
|–
Carpentry Constraint
| | | | | | | |
Region
| |
|
20
40
60
80
100
T
Number of Tables
?
For the point (30, 20)
4T + 3C ? 240 hours available (4)(30) + (3)(20) = 180 hours used 2T + 1C ? 100 hours available (2)(30) + (1)(20) = 80 hours used
? ?
Carpentry constraint Painting constraint
?
For the point (70, 40)
Carpentry constraint Painting constraint
4T + 3C ? 240 hours available (4)(70) + (3)(40) = 400 hours used 2T + 1C ? 100 hours available (2)(70) + (1)(40) = 180 hours used
? ?
?
For the point (50, 5)
4T + 3C ? 240 hours available (4)(50) + (3)(5) = 215 hours used 2T + 1C ? 100 hours available (2)(50) + (1)(5) = 105 hours used
?
Carpentry constraint Painting constraint
?
?
? ? ?
?
Once the feasible region has been graphed, we need to find the optimal solution from the many possible solutions The speediest way to do this is to use the isoprofit line method Starting with a small but possible profit value, we graph the objective function We move the objective function line in the direction of increasing profit while maintaining the slope The last point it touches in the feasible region is the optimal solution
? ?
?
? ? ?
?
For X Furniture, choose a profit of $2,100 The objective function is then $2,100 = 70T + 50C Solving for the axis intercepts, we can draw the graph This is obviously not the best possible solution Further graphs can be created using larger profits The further we move from the origin, the larger the profit will be The highest profit ($4,100) will be generated when the isoprofit line passes through the point (30, 40)
C 100 – – Number of Chairs 80 – – 60 – – – 20 – – 0 Figure 7.6
|– | | | |
? Isoprofit line at $2,100
40 –
(0, 42)
$2,100 = $70T + $50C (30, 0)
| | | | | | |
20
40
60
80
100
T
Number of Tables
C 100 – – Number of Chairs 80 – – 60 – – 40 – – 20 – – 0 Figure 7.7
|– | | | |
? Four isoprofit lines
$3,500 = $70T + $50C $2,800 = $70T + $50C $2,100 = $70T + $50C $4,200 = $70T + $50C
|
|
|
|
|
|
|
20
40
60
80
100
T
Number of Tables
C 100 – – Number of Chairs 80 – – 60 – – 40 – – 20 – – 0 Figure 7.8
|– | | | |
? Optimal solution to the X
Furniture problem
Maximum Profit Line Optimal Solution Point (T = 30, C = 40) $4,100 = $70T + $50C
|
|
|
|
|
|
|
20
40
60
80
100
T
Number of Tables
A second approach to solving LP problems employs the corner point method ? It involves looking at the profit at every corner point of the feasible region ? The mathematical theory behind LP is that the optimal solution must lie at one of the corner points, or extreme point, in the feasible region points point ? For X Furniture, the feasible region is a four-sided polygon with four corner points labeled 1, 2, 3, and 4 on the graph
?
C 100 – Number of Chairs
? Four corner points of the
feasible region
2 –
80 – – 60 – – 40 – – 20 – –
| | | | | | | | | | |
3
1 |–
0 Figure 7.9
20
40
Number of Tables
4 60
80
100
T
Point 1 Point 2 $4,000 4 Point 3 $3,500
: (T = 0, C = 0) Profit = $70(0) + $50(0) = $0 : (T = 0, C = 80) Profit = $70(0) + $50(80) = : (T = 50, C = 0) Profit = $70(50) + $50(0) =
Point : (T = 30, C = 40) Profit = $70(30) + ? Because Point 3 returns the highest profit, this is the optimal $50(40) = $4,100 solution
To find the coordinates for Point accurately we have to solve for the intersection of the two constraint lines ? The details of this are on the following slide
?
?
Using the simultaneous equations method, we multiply the method painting equation by –2 and add it to the carpentry equation
4T + 3C = 240 – 4T – 2C = –200 C= 40
?
(carpentry line) (painting line)
Substituting 40 for C in either of the original equations allows us to determine the value of T 4T + (3)(40) = 4T + 120 = T= 240 240 30 (carpentry line)
ISOPROFIT METHOD 1. Graph all constraints and find the feasible region. 2. Select a specific profit (or cost) line and graph it to find the slope. 3. Move the objective function line in the direction of increasing profit (or decreasing cost) while maintaining the slope. The last point it touches in the feasible region is the optimal solution. 4. Find the values of the decision variables at this last point and compute the profit (or cost). CORNER POINT METHOD 1. Graph all constraints and find the feasible region. 2. Find the corner points of the feasible reason. 3. Compute the profit (or cost) at each of the feasible corner points. 4. select the corner point with the best value of the objective function found in Step 3. This is the optimal solution. Table 7.3
?
Reddy Mikks produces both interior and exterior paints from two raw materials.M1 and M2.The following table provides the basic data of the problem:
Exterior paint Raw material M1 Raw Material M2 Profit per ton($1000) 6 1 5
Interior paint 4 2 4
Maximum daily availability(tons) 24 6
?
A market survey restricts the maximum daily demand of interior paint to 2 tons.Additionally , the demand for the interior paint cannot exceed that of exterior paint by more than 1 ton. Reddy Mikks wants to determine the optimum product mix of interior and exterior paints that maximizes the daily profit.
Let Xi be the decision variables,(for eg.,Number of units of product A to produce)
Ci be one unit effect of each Xi on the objective.
Then the objective function is Maximize or Minimize Z = C1X1 + C2X2 + …+ CnXn
?
There are three general forms of constraints: Less-than-or-equal-to variety(limited resources) Greater -than-or-equal-to variety(requirements that must be met) Equal-to variety Let aij be the per unit consumption(in case of <= variety) or per unit contribution(in case of >= variety) and bi is the upper limit which cannot be exceeded in case of <= variety or it is the lower limit (>=)
•
•
•
?
Therefore the constraints are: a11X1 +a12X2 + ………….+a1nXn ?=? b1 a21x1 +a22X2 +………….+a2nXn
.
?=? b2
.
.
an1X1 +…………………..+anmXn ?=?bm
Non- negative restrictons are: Xi ? 0 for all values of i
The Illini Metal company produces a certain casting which must contain minimum amounts of various metals. They have four types of ore to choose from, and they want to select from these ores in such a way as to minimize the cost of producing the product. Once the ores are selected,the metal must be refined. The cost of refining a pound of ore is the same regardless of the type. The casting requires a minimum of 20 ounces of lead , 24 ounces of copper, and 30 ounces of cast iron.Type 1 ore has been analyzed and found to contain 2 ounces of lead, 1 ounce of copper, and 1 ounce of cast iron per pound. One pound of type 2 ore contains 1,3,3 ounces respectively .A pound of type 3 contains ½ ,2,2 ounces resply and type 4 ore contains 1/4,1/2, and 4 ounces respectively.
Type 1 ore costs $10 pounds,Type2 ore costs $15perpound,Type3 ore costs$30 per pound and
? ?
Type 4 ore costs$25 per pound. Define the decision variables. Set up the linear programming model.
doc_634028720.ppt