Linear Programming

A problem solving approach for situation

involving maximizing or minimizing a linear
function subject to linear constraints that limit the
degree to which the objective can be persuaded

 Linear programming is a mathematical modeling technique

designed to optimize the usage of limited resources
Programming means planning of activities
Linear implies the activities are linearly related
Contribution of each decision variable in both objective
function and constraints to be directly proportional to the
value of the variable
Total contributions of all the variables in the objective
function and constraints be the direct sum of individual
contribution of each variable.

 In linear programming
Objective function and constraints are expressed as a linear
function of the variables (activities)
Linear programming uses a mathematical model in which
a linear objective function optimizes
maximizes)

(minimizes or

subject to certain specified linear constraints.

Output of the model provides the optimal activities level

Par, Inc.
Par, Inc., is a small manufacture of golf equipment and
supplies whose management has decided to move into the
market for medium and high priced golf bags. Pars distributor
is enthusiastic about the new product line and has agreed to
buy all the gulf bags Par produces over the next three months.
After a through investigation of the steps involved in
manufacturing a golf bag, management determined the each
golf bag produced will require the following operations:
1. Cutting and dying the material
2. Sewing
3. Finishing
4. Inspection and packaging

Par, Inc.
Director of manufacturing analyzed each of the operations and
concluded that if the company produces a medium priced
standard model, each bag will require 7/10 hour in the cutting
and dyeing department, 1/2 hour in the sewing department, 1
hour in the finishing department and 1/10 hour in the
inspection and packaging department. The more expensive
deluxe model will require 1 hour in the cutting and dyeing, 5/6
hour for sewing, 2/3 hour for finishing and hour for
inspection and packaging. Pars production is constrained by a
limited number of hours available in each department.

Par, Inc.
After studying departmental workload projections, the director
of manufacturing estimates that 630 hours of cutting and
dyeing, 600 hours for sewing, 708 hours for finishing and 135
hours for inspection and packaging will be available for the
production of golf bags during the next three months.
Accounting department analyzed the production data, assigned
all relevant variable costs and arrived at prices for both bags
that will result in a profit contribution of $10 for every
standard bag and $9 for every deluxe bag produced. Par, Inc.,
determines the number of standard and deluxe bags to produce
in order to maximize total profit contribution.

Par, Inc.

S = number of standard bags produce

D = number of deluxe bags produce
Max 10 S + 9 D
Subject to
7/10 S + 1 D 630 Cutting and dyeing
1/2 S + 5/6 D 600 Sewing
1 S + 2/3 D 708 Finishing
1/10 S + 1/4 D 135 Inspection and packaging
S, D 0

M&D Chemicals
M&D Chemicals produces two products that are sold as raw
materials to company manufacturing bath soap and laundry
detergents. Based on an analysis of current inventory levels and
potential demand for the coming month, M&Ds management
specified that the combined production for products A and B must
total at least 350 gallons. Separately, a major customers order for
125 gallons for product A must also be satisfied. Product A
requires 2 hours of processing time per gallons and product B
requires 1 hour of processing time per gallon. For the coming
month, 600 hours of processing time is available. M&Ds
objective is to satisfy these requirements at a minimum total
production cost. Production costs are $2 per gallon for product A
and $3 per gallon for product B.

M&D Chemicals

A = number of gallons of product A

B = number of gallons of product B
Min 2 A + 3 B
Subject to
1A
125 Demand for product A
1 A + 1 B 350 Total production
2 A + 1 B 600 Processing time
A, B 0

 Slack variable: A variable added to the left hand side of a less

than or equal to constraint to convert the constraint into an
equality. The value of this variable can usually be interpreted as
the amount of unused resource.
Surplus variable: A variable subtracted from the left hand side
of a greater than or equal to constraint to convert the constraint
into an equality. The value of this variable can usually be
interpreted as the amount over and above some required
minimum level.
Unrestricted Variable: Generally the nature of variables
requires them to assume non negative real values. There are
situation where a variable can assume and integer value.

Special cases of LP solution

Degeneracy: In the feasibility condition of simplex method a tie for

minimum ratios may be broken arbitrarily for the purpose of
determining the leaving variable. If this happens, then one or more of
the basic variables will be zero in the next iteration. In this case, the
new solution is degenerate.
Simplex procedure would repeat the same sequence of iterations, never
improving the objective value or never terminating the computations.
From practical standpoint, the condition reveals that the model has at
least one redundant constraint.
Example: Maximize z = 3x1 + 9x2
subject to x1+4x2 8
x1 + 2x2 4
x1, x2 0

Special cases of LP solution

Alternative Optima: When objective function is parallel to a
binding constraint (a constraint that is satisfied as an equation by
the optimal solution), the objective function will get the same
optimal value at more than one solution point, then the model has
alternative optima.
Alternative optima are useful as they allow us to choose from many
solutions without experiencing any deterioration of objective value.
Example: (infinity of solutions)
Maximize z = 2x1 + 4x2
subject to x1 + 2x2 5 x1 + x2 4
x 1, x2

Special cases of LP solution

Unbounded solutions: In LP models, the values of the variables may
be increased indefinitely without violating any of the constraints, means
the solution space is unbounded in at least one direction.
As a result, the objective value may increase (maximization case) or
decrease (minimization case) indefinitely.
It is due to poorly constructed model such as one or more non
redundant constraints are not accounted for and the parameters
(constants) of some constraints are not estimated correctly.
Example: Maximize z = 2x1 + x2
subject to x1 x2 10
2x1
40
x1 , x 2 0

Special cases of LP solution

4. Nonexisting (or infeasible) solutions: If the constraints are
not satisfied simultaneously, the model has no feasible
solution.
From the practical standpoint, an infeasible space points to
the possibility that the model is not formulated correctly.
Maximize z = 3x1 + 2x2
subject to 2x1 + x2 2
3xl + 4x2 12
x1, x2
0

Sensitivity Analysis
Changes in coefficients of the objective function within the specific limits
will not change the value of the decision variables but will affect the value
of the objective function.
Changes in right-hand side within the specified limits will alter the values
of both the variables and the objective function.
Dual price represents the unit worth of a resource, it gives the contribution
to the objective function resulting from a unit increase or decrease in the
availability of a resource.
LP variable is regarded as an economic activity that consumes resources
for the purpose of producing profit. Reduced cost per unit of activity =
(Cost of consumed resources per unit of activity j) - (Profit per unit of
activity j)

Sensitivity Analysis
If activitys reduced cost per unit is positive, implies value of
its associated variable in optimum solution should be zero, then
the cost of its consumed resources per unit is higher than its
profit per unit and the activity should not be undertaken.
Alternatively, an activity that is economically attractive will
have a zero reduced cost in the optimum solution, signifying an
equilibrium point has been reached at which the output (unit
profit) equals the input (unit cost of the resources).
Addition of new constraints lead to one of two cases such as
the new constraint is redundant i.e. it is satisfied by the current
optimum solution or the new constraint is violated, in which the
dual simplex method must be used to recover feasibility.

Sensitivity Analysis
Addition of a new activity in an LP model is equivalent to
adding a new variable. It is desirable only if it is profitable that
is, if it improves the optimal value of the objective function.
This condition can be checked by computing z j - cj = YPj cj
for the new activity, where Y are the current optimal dual
values and Pj and cj represent the resource usages and profit per
unit of the new activity.
If the computed zj cj satisfies the optimality condition, then
the new activity is not desirable. Otherwise, the new activity is
profitable and must be brought into the basic solution.

Par, Inc. Sensitivity Analysis

Optimal solution S = 540 standard bags and D = 252 deluxe
bags; the value of the optimal solution is $7668.
Reduced costs indicate how much objective function coefficient
of decision variable would have to improve before that variable
could assume positive values in optimal solution. Both decision
variables have positive value and corresponding reduced costs
are zero, so there is no chance of improvement in the objective
function coefficient of each decision variable.
Slack/Surplus column provides cutting and dyeing, and
finishing are binding constraints having zero slack. Sewing
department has 120 hours and inspection and packaging
department has 18 hours of slack or unused capacity.

Par, Inc. Sensitivity Analysis

Dual Prices column contains information about the marginal
value of each of the four resources at the optimal solution.
Dual price associated with a constraint is the improvement in
the value of the solution per unit increase in the right hand
side of the constraint.
Non zero dual prices of 4.37496 for constraint 1 (cutting and
dyeing constraint) and 6.93753 for constraint 3 (finishing
constraint) tell us that an additional hour of cutting and dyeing
time improves (increases) the value of the optimal solution by
$4.37 and an additional hour of finishing time improves
(increases) the value of the optimal solution by $6.94.

Par, Inc. Sensitivity Analysis

Thus if the cutting and dyeing time were increased from 630
to 631 hours with all other coefficients in the problem
remaining same, Pars profit would be increased by $4.37
from $7668 to $7668 + $4.37 = $7672.37.
A similar interpretation for the finishing time with all other
coefficients in the problem remaining the same, would
increase Pars profit to $7668 + $6.94 + $7674.94.
Sewing, and inspection and packaging constraints both have
slack or unused capacity available, but the dual prices is zero
show additional hours of these two resources will not improve
the value of the objective function.

Par, Inc. Sensitivity Analysis

Range of objective function coefficients provide as long as the
profit contribution associated with standard bags is between
$6.3 and $13.5, production of S = 540 standard bags and D =
252 deluxe bags will remain optimal.
Similarly, as long as profit contribution associated with deluxe
bags is between $6.76 and $14.29, production of S = 540
standard bags and D = 252 deluxe bags will remain optimal.
As long as the constraint right hand side is between lower and
upper limit values the associated duel price gives the
improvement in the value of optimal solution per unit increase
in the right hand side.

Par, Inc. Sensitivity Analysis

Cutting and dyeing constraint with a current right hand side
value is 630. An additional hour will increase the objective
function by $4.37 per hour. It is also true that a reduction in the
hour available will reduce the value of the objective function by
$4.37 per hour.
From the range information, it is given that the dual price of
$4.37 is valid for increases up to 682.36316 and decreases down
to 495.59998.
A similar interpretation for the finishing constraints right hand
side (constraint 3) shows dual price of $6.94 is applicable for
increases up to 900 hours and decreases down to 580.00146
hours. Changes outside the range, problem must be resolved to
find new optimal solution and the new dual price.

Par, Inc. Sensitivity Analysis

Sensitivity analysis information is based on the assumption
that only one coefficient changes; it is assumed that all other
coefficients will remain as stated in the original problem.
Analysis of simultaneous changes is possible with the help of
the 100 percent rule.
To observe the changes in the profit contributions of the
standard and deluxe bags to $11.5 and $8.25, we see that the
upper limit for the objective function coefficient of standard
bags is 13.49993; thus the allowable increase is 3.49993 =
13.49993-10.

Par, Inc. Sensitivity Analysis

In percentage changes the increase of $1.5 in the objective function
coefficient (from 10 to 11.5) for the standard bags is (1.5/3.49993)
(100) = 42.86% of the allowable increase.
Given the lower limit of 6.6667 for deluxe, the allowable decrease for
deluxe bags is 2.3330 = 9 - 6.6667.
In percentage change the decrease of $0.75 in the objective function
coefficient (from 9 to 8.25) for the deluxe bags is (0.75/2.3333) (100) =
32.14% of the allowable decrease.
Sum of percentage changes of the allowable increase (42.86%) and
percentage change of the allowable decrease (32.14%) is 75% which is
less than 100% implies no change in optimal solution, only change in
profit contribution.

Par, Inc. Sensitivity Analysis

To observe the changes by taking 20 additional hours of cutting
and dyeing time and 100 additional hours of finishing time, we
see the allowable increase for cutting and dyeing time is
682.36316 630 = 52.36316 and the allowable increase for
finishing time is 900 708 = 192. The 20 additional hours of
cutting and dyeing time are (20/52.36316) (100) = 38.19% of
the allowable increase in the constraints right hand side.
100 additional hours of finishing time are (100/192) (100) =
52.08% of the allowable increase in the finishing time
constraints right hand side. Sum of the percentage changes does
not exceed 100% therefore we can conclude that the dual prices
are applicable and that objective function will improve by (20)
(4.37) + (100) (6.94) = 781.4

Par, Inc. Sensitivity Analysis

In percentage changes the increase of $1.5 in the objective function
coefficient (from 10 to 11.5) for the standard bags is (1.5/3.49993)
(100) = 42.86% of the allowable increase.
Given the lower limit of 6.6667 for deluxe, the allowable decrease for
deluxe bags is 2.3330 = 9 - 6.6667.
In percentage change the decrease of $0.75 in the objective function
coefficient (from 9 to 8.25) for the deluxe bags is (0.75/2.3333) (100) =
32.14% of the allowable decrease.
Sum of percentage changes of the allowable increase (42.86%) and
percentage change of the allowable decrease (32.14%) is 75% which is
less than 100% implies no change in optimal solution, only change in
profit contribution.

M&D Chemicals Sensitivity Analysis

Minimum cost solution yields an objective function value of $800,
so the values of the decision variables show that 250 gallons of
product A and 100 gallons of product B provide the minimum cost
production schedule.
Slack/Surplus column shows the greater than equal to constraint
corresponding to the demand for product A (constraint 1) has a
surplus of 125 units implies production of product A in optimal
solution exceeds demand by 125 gallons.
Slack/Surplus variables are zero for the total production
requirement (constraint 2) and the processing time limitation
(constraint 3), which indicates that these constraints are binding at
the optimal solution.

M&D Chemicals Sensitivity Analysis

From the dual price column, it is observe that the processing
time constraint (constraint 3) has dual price $1 implies by
increase the processing time from 600 to 601 hours, the
objective function value will improve by $1 i.e. lowering the
cost of the objective function by $1 and it will be $800 - $1 =
$799.
On the other hand the dual price of $1 per unit would be
applicable for every additional hour of processing time up to
a total of 700 hours.

M&D Chemicals Sensitivity Analysis

Dual price for total production constraint (constraint 2) is 4
implies the value of optimal solution will not improve in the
value of the right hand side is increased by one unit.
If the right hand side of the total production constraint is
increased from 350 to 351 units, the value of optimal solution
will worsen by the amount of $4 that means the optimal
solution will become $800 + $4 = $804.
On the other hand if the right hand side of the total
production constraint were decrease from 350 to 349 units,
the dual price helps in lowering the optimal cost by $4 to
$800 - $4 = $796.

Modified Par, Inc., Problem

Suppose management is considering producing a lightweight
bags designed for golfers. Design department estimates that
each new lightweight bags will require 0.8 hours for cutting
and dyeing, 1 hour for sewing, 1 hour for finishing and 0.25
hours for inspection and packaging. Because of the unique
capabilities designed into the new model, Pars management
feels they the current production period.
Max 10S + 9D + 12.85L
0.7S + 1D + 0.8L 630 Cutting and dyeing
0.5S + 0.83D + 1L 600 Sewing
1S + 0.67D + 1L 708 Finishing
0.1S + 0.25D + 0.25L 135 Inspection and packaging
S, D, L 0