Published On:Sunday 27 November 2011
Posted by Muhammad Atif Saeed
Linear Programming (LP)
Linear Programming (LP):- LP is an operations research technique that can be used to decide on the optimum use of scarce resources. Use of LP
• Budgeting
• Calculation of relevant cost
• Selling different products
• Maximum payment for scare resources
Problems with LP
1. It may be difficult to identify scare resources 3. Assumption of linearity
2. Static model 4. Shadow price of scare resource
STEPS IN LP
- Determine the variable
• Let Z= total contribution
• X1 = No of units to be produced
- Constructing the objective function
- Specifying the constrains
- Writing the non-negative condition
ASSUMPTIONS IN LINEAR PROGRAMMING
When we use LP as an approximate representation of a real-life situation, the following assumptions are inherent:
– Proportionality. - The contribution of each decision variable to the objective or constraint is directly proportional to the value of the decision variable.
– Additivity. - The contribution to the objective function or constraint for any variable is independent of the values of the other decision variables, and the terms can be added together sensibly.
– Divisibility. - The decision variables are continuous and thus can take on fractional values.
– Deterministic. - All the parameters (objective function coefficients, right-hand side coefficients, left-hand side, or technology, coefficients) are known with certainty.
Methods of LP
Graphical method
• Draw a graph two axes to represent the decision variables.
• Plot all the constrains of the model as straight lines by evaluating where the limiting equations intersect the axes.
• Identify the area on the graph that satisfies all the constrains. If such area doesn’t exist then model has no solution
• If the problem is maximization then the values of decision variables that yield highest figure is result.
Slack
Slack is the amount by which resource is under utilized. It will occur when the optimum point fall inside the given resource line rather then exactly on it.
Shadow Price/Dual
Shadow price of a resource is the increase in contribution obtained when one extra unit of the constrain is made available.
Example: Olympic Bike Co.
Olympic Bike is introducing two new lightweight bicycle frames, the Deluxe and the Professional, to be made from special aluminum and steel alloys. The anticipated unit profits are $10 for the Deluxe and $15 for the Professional.
The number of pounds of each alloy needed per frame is summarized below. A supplier delivers 100 pounds of the aluminum alloy and 80 pounds of the steel alloy weekly. How many Deluxe and Professional frames should Olympic produce each week?
Aluminum Alloy Steel Alloy
Deluxe 2 3
Professional 4 2
Model Formulation
• Verbal Statement of the Objective Function
– Maximize total weekly profit.
• Verbal Statement of the Constraints
– Total weekly usage of aluminum alloy < 100 pounds.
– Total weekly usage of steel alloy < 80 pounds.
• Definition of the Decision Variables
x1 = number of Deluxe frames produced weekly.
x2 = number of Professional frames produced weekly.
Max 10x1 + 15x2 (Total Weekly Profit)
s.t. 2x1 + 4x2 < 100 (Aluminum Available)
3x1 + 2x2 < 80 (Steel Available)
x1, x2 > 0
