Linear Programming
Linear programming (LP) is a mathematical optimization technique. The method applies to many situations when one needs to maximize or minimize an objective while faced with constraints. An example is introduced to demonstrate the versatility of this method. It assume that a production process where one is interested in maximizing profits using the available quantity of inputs. This is an optimization function for which this mathematical technique provides the optimum or best solution possible given the constraints.
Definition: LP is a mathematical technique to help decision makers in resource allocation. The process provides a plan that efficiently applies available resources to achieve a desired objective.
LP Graphic Solution
One way to solve the problems is using graphs. The problem with graphs is that the solution is not easy to determine unless one uses special graph paper.
The first step in a graphical solution is to plot each constraint. After plotting the constraints, the corner solutions are identified. Numerical outcomes are then calculated at each corner solution to identify the one that satisfies the objective. Calculations are made using the substitution method.
Example:
Linear programming problem in a specific firm; the manufacturer of two types of furniture
1. tables
2. chairs
There are four characteristics that linear programming problems must have:
1.) There must have an objective in achieve the major objective here is to
maximize dollar profits. Profits are NOT linearly related to sale but
concept of Total Contribution is :
Total = (Selling price - variable cast ) x ( sale volume )
Contribution ( per unit per unit ) ( in units )
Where: profit is refer to contribution
2.) There must be alternative course of action. One of that alternative will achieve the objective.
3.) Resources must be in limited supply
4.) Must be able to expressed the firm’s objective and its limitation as mathematical equations or inequalities; and there must be linear equation or inequalities ; so furniture objective = Dollar profits as P1 can be expressed this equation.
P = $ 8 ( number of tables ) + $ 6 ( number of chair )
GRAPHIC SOLUTION TO A MAXIMIZATION PROBLEM :
Ø Manufacturing of one table requires:
4 Hours in Assembly
2 hours in Finishing
Ø Manufacturing of Eacher chair requires
2 hours in Assembly
4 hours in Finishing
Ø Assembly has 60 hours available
Ø Finishing handle up to 48 hours of work
Ø If Profit is per table and per chair
Ø The problem is to determine the best possible combination of TABLES and CHAIRS to produce and sell in order to realize the maximum profit.
Ø There are two limitations here which is also called the constraints in the problem:
1.) The time available in Assembly (60 hrs)
2.) The time available in Finishing (48 hrs)
> We use T to represent the number of tables and C to represent the number of Chairs
FIRST STEP
a.) Let us restate the information in mathematical form by using a new term called OBJECTIVE FUNCTION, which refers to the expression which shows the relationship of output to profit as:
T = total profit from sale of Tables
C = total profit from sale of chairs
= $ 8 T + $ 6 C = as objective function
HOURS REQUIRED FOR
1 UNIT OF PRODUCT
Assembly (A) 4 hours / table 2 hours / chair 60 hrs. avail
Finishing (F) 2 hours / table 4 hours / chair 48 hrs. avail
Profit for Unit per table per chair
How to Solve :
A = 60 hours available = 15 tables
4 hrs per table
A = 60 hrs. available = 30 chair
2 hrs. per chair
F = 48 hrs. available = 24 tables
4 per chair
b.) Department time constraints
= Time used in making the two products must NOT exceed the total time available in the two department:
FORMULA:
Assembly: 4T + 2 C Í 60
Finishing: 2T + 4C Í 48
T Ê 0 A = 0 x 4 + 0 x 2 = 0
C Ê 0 F = 0 x 2 + 0 x 4 = 0
SECOND STEP :
GRAPHING THE CONSTRAINTS
Chair Axis
Table Axis
= the inequality of 4T + 2C Í 60 can be found in : ( ASSEMBLY
Example :
a.) If we assume that all time available in assembly is used in making chair (then the production of table is O ), then 30 chairs could be made.
Formula:
T = O, then C Í 30 chairs
Solution :
4 T + 2 C Í 60
4 (o) + 2 C Í 60
C Í 30 chairs-- If we make the maximum number of chair, then C = 30
= the first print here in ( 0, 30 )
= this point denotes the production of 0 tables and 30 hairs.
(b.) The SECOND POINT :
= Lets assume that all the time available in Assembly is used in making table (then production of CHAIR is 0), and we produce 15 tables
Formula :
Solution :
4 T + 2 C Í 60 hrs.
4 T + 2 (0) Í 60
T = 15 tables
= Second point is ( 15, 0 )
= this denotes the production of table of 15 and O chairs
= locating these two points ( 0, 30 ) chair and ( 15, 0 ) tables joining the result in the graph as : (Figure ______ )
= Any combination of tables and chairs on line BC will use up to 60 hours available (ex. 10 chairs and 10 tables)
GRAPH
C
Number of Tables
Graph of capacity constraints in the Assembly Department
C
Number of Tables
= 5 tables and 15 chair = this point is not on line BC but the combination can be produced without exceeding the 60 hours
= available same with 10 tables and 10 chairs
= the shade area ABC is the graphic Representation of the inequality of 4T + 2 C Í 60
As long as T and C are both greater than or equal to O, or any point at any combination of tables and chairs falling within the shaded are ABC, will satisfy the time Restriction in the Assembly Department.
Graph for Constraints in Finishing Department
= same explanation applies for finishing that :
FINISHING2 T + 4 C Í 48 hours available
= line EF represents all combination of tables and chairs which exactly use for 48 hours as ( 2 T + 4 C Í 48 )
= The shaded area AEF contains all possible combination which do NOT exceed 48 hours ( 2 T + 4 C Í 48 )
= As long as T and C are both greater them or equal to O; any point that any
combination of table and chairs falling within the shaded AEF will satisfy the
restriction in the finishing department
= The shaded AEF is the graphic representation of the inequality 2 T + 4 C Í 48
= Best combination of tables and chairs must fall within the schedule area of both Assembly and Finishing.
Formula:
A = 4 T + 2 C Í 60 hrs.
F = 2 T + 4 C Í 48 hrs.
T Ê O
C Ê O
Graph in capacity constraints in Finishing Department
C
Number of Tables
Graphic Representation of Problem Constraints
C
Number of Tables
= Combination of Tables and chairs that fall within AEDC are called Feasible Solution and AEDC is the Feasible Region
= outside AEDC are called infeasible
THIRD STEP : Locate Point D
a.) to solve the equation of the two line which intersect to form D ( the point to both equation )
Formula:
A = 2 ( 4T + 2 C = 60 )
F = 2 2T + 4C = 48
b.) multiply the first equation by - 2
c.) add the second equation
d.) substitute 12 for T in the second equation
F 2T + 4C = 48
2 (12) + 4C = 48
24 + 4C = 48
4C = 28
C = 6
e.) point D is ( 12, 6 )
FOURTH STEP :
= test the four corners of the shaded area to see which yield the greatest dollar
Profit Profit $ 8 + $ 6
Point A ( 0,0 ) _____________________ $ 8 (0) + $ 6 (0) = $ 0
Point E ( 0,12) ______________________ $ 8 (0) + $ 6 (0) = $ 72
Point C (15,0) ______________________ $ 8 (15) + $ 6 (0) = $ 120
Point D (12,6) ______________________ $ 8 (12) + $ 6 (6) = $ 132
= Point D yield the greatest profit point $ 132 points table and chairs ( 12,6 )
GRAPHIC SOLUTION TO A MINIMIZATION :
Many problem of interest to managers involve minimizing some objective function instead of maximizing one; in these situations we can fine an optimal solution by graphic methods.
Example :
Hanks Kennel wants to mix up 500 pounds of a special hotdog food supplement Hank retails. There are two principal ingredients in the mixture, both sources of protein
a.) ingredient P1
b.) ingredient P2
The first source of ingredients protein, cost $ 5 pounds
The second ingredient cost $ 8 pounds
Chemical constraints dictate that the mixture contain not more than 400 pounds of P1, and at least 200 pounds of P2
STEP ONE: Problem information .
Minimize total cost = $ 5 P1 + $ 8 P2
Subject to the Constraints
P1 Í 400 pounds
P2 Ê 200 pounds
P1 + P2 = 500 pounds
P1 Ê 0
P2 Ê 0
STEP 2 :
We plot the problem constraints, looking first at the constraint P1 Í 400 pounds, we can see that vertical line erected from the 400 pound point on the horizontal axis will denote the maximum value P1 can table. P1 can take on any value up to an including 400 pounds; thus constraints P1 Í 400 pounds is properly represented by the darker area to the left of the vertical line AB or in the darker area to the left of the vertical line will satisfy the constraints P1 Í 400
P2
Pounds P1
Second constraints P2 Ê 200 pounds. If we were to constraints a horizontal line CD at the 200 pounds point on the P2 axis, we could say that any value of P2 lying on that line or in the space colored it would satisfy the constraint P2 Ê 200. There will be a line and the darker space above it. The darker area is a constraints only at bottom ( at the 200 pounds minimum level ), not at the top.
P2
Pounds
> third constraints P1 + P2 = 500 ? this ensure that Hank get the quantity of the
mixture that he requires; no more no less the equation P1 + P2 = 500 has been
plotted on graph as line EF, Any combination of P1 and P2 falls on this line will
represent exactly 500 pounds of the supplemental foods satisfy Hanks third
constraints.
Pounds
STEP 5
As many mixture that Hanks produce must satisfy all three constraints this shows that any combination of the two ingredients P1 and P2 which is on the line segments EG will satisfy all the three constraints.
Such combination will exactly 500 pounds the amount of P1 in such a combination will be less then 400 pounds the amount of P2 such as a combination will be more than 200 pounds.
P
Pounds
But there are many combinations of P1 and P2 lying on the line segment EG. Which one of these will generate the minimum cost of producing 500 pounds of the required mixture? One way for Hank to answer this question is to observe that P2 is the more expensive of the two ingredients ( per pound) and that it would be best to use the smallest possible amount of this ingredient. The constraint P2 Ê 200 pounds sets the minimum amount of P2 which must appear in Hank’s mixture, 200 pounds; with P2 being more expensive than P1, it does not behoove us to include more than the minimum amount of P2 in the final mixture. Thus a bit of simple logic would indicate that the final mixture should consist of 200 pounds of P2 and 300 pounds of P1, represented by point G.
Another method of determining the particular combination of P1 and P2 on line segment EG which minimize the total cost of the mixture is to use a variant of the isoprofit lines we employed in the maximization example discussed earlier. Let us call these lines isocost lines. You will remember that we begin by plotting one such line representing a total cost we know we could achieve; with only 500 pounds of the mixture to be produced, it would be possible to mix it entirely of P2 at per pound; if Hank did this, the total cost would be represented by this equation:
The line segment EG on which any acceptable mixture must lie; in addition, we have plotted three isocost lines, beginning with a total cost of ,000, then decreasing to a total cost of ,000, and finally plotting the lowest isocost line, which has at least one point (G) on the line segment EG. The total cost of this third isocost line, which passes through point G, is found by solving simultaneously the equations of the two lines which pass through point G. A simpler method would be to read the coordinates of point G regardless of the method chosen, the final solution to Hank’s minimizing problem is
P1 = 300 pounds
P2 = 200 pounds
As P1 is less than or equal to 400 pounds, it satisfies the original constraint; and because P2 in the final solution is greater than or equal to 200 pounds, it too satisfies Hank’s constraints.
Of course, this is a trivial problem, one that is easily solved in a moment simply by inspecting the ingredient costs and the constraints; however in almost all operational applications of linear programming, the complexities of the mixture constraints are such as to make solution by inspection impossible; in this sense, our simple mixture problem serves us as an introduction to the methodology of the more complex solution methods to follow and not as the quickest method to solve the simple problem we have used as an example.
Summary of graphic minimization procedure
1. Restate the problem information (objective function and constraints) in mathematical form.
2. Plot the problem constraints on the graph.
3. Determine the feasible region.
4. Plot an isocost line and move it parallel to itself so that total cost decreases until further shifting would move it out of the feasible region.
Important Terms
Constrained resources. Organizational resources which are limited in quantity.
Constraint. A limit on the availability of resources
Extreme point. A corner of the feasible region
Feasible region. That area containing all the possible solutions to the problem which are feasible, that is, those solutions which satisfy all the constraints in the problem.
Inequality. A mathematical expression indicating that minimum or maximum requirements must be met.
Infeasibility. The condition when there is no solution which satisfies all the constraints in a problem.
Isocost line. A line representing all possible combinations of products variables which produce a given profit.
Isoprofit line. A line representing all possible combinations of products which will produce a given profit.
Linear - used to describe a relationship between two or more variables, a relationship which is directly and precisely proportional
Linear programming. A mathematical technique for finding the best uses of an organization’s resources.
Linear relationship. A directly proportional relationship between variables.
Nonnegativity constraints. Constraints that restrict all the variables to be zero or positive.
Objective. A goal of the organization.
Objective function. An expression which shows the relationship between the variables in the problem and the firm’s goal.
Programming - refers to the use of certain mathematical technique to get the best possible solution to get the best possible solution to a problem involving limited resources.
Redundancy. A constraint which does not affect the feasible region.
Structural constraints. All constraints in a linear program besides the nonnegativity constraints.
Total contribution. (Selling price per unit – variable cost per unit) x sales volume.
Unboundedness. The condition when the objective of a linear programming problem can be made infinitely large without violating any of the constraints.
Credit:ivythesis.typepad.com
0 comments:
Post a Comment