Assignment:
Read handout titled "Linear Programming."
Find a journal article in which linear programming was used
to solve a problem. Read the article and prepare a brief (several paragraph)
review. Email the review to the course instructor (engelb) by class time
on Friday of week 4.
Problems - Due End of Week 3
Problems are due Monday of week 4 at class time.
-
A rock quarry has two pits from which it obtains rock.
The rock is run through a crusher to produce 2 products: concrete grade stone
and road surface chat. Each ton of rock from the south pit
converts to 0.75 tons of stone and 0.25 tons of chat when crushed.
Rock from the north pit is of different quality and produces
50% of each type when crushed.
The quarry has contracts for 60 tons of stone
and 40 tons of chat this planning period (note this is the minimum amount
that must be produced).
The cost per ton of extracting and crushing the rock from
the south pit is 1.6 times as costly as from the north pit.
- What are the decision variables for the problem?
- State the 2 constraints.
- Graph the feasible region.
- Draw an appropriate iso-cost (line of equal cost)
on the graph and indicate graphically and numerically the optimal
solution.
- Suppose all the information given in the problem description
is accurate. What additional information might you nevertheless
wish to know before having confidence in this model?
-
An equipment manufacturer produces two products,
a field cultivator and a chisel plow,
which share production facilities.
Raw materials cost $600 per field cultivator and $750 per chisel plow.
The field cultivator requires 4 hours in the foundry/forge area per unit
and the chisel plow requires 2 hours per unit in the foundry/forge area.
The field cultivator requires 2 hours in the assembly portion of
the production facility and the chisel plow requires 3 hours in the
assembly portion of the plant.
The available daily capacities are 160 hours in the foundry/forge
area and 180 hours in the assembly portion of the facility.
The selling price of each field cultivator at the factory door
is $4800 and that of the chisel plow is $5250.
Whatever number of each type of equipment that can be produced
at this factory can be sold.
- Write the objective function.
- Write the constraints.
- The above description assumes that the capacities of the forge/foundry
and assembly line are sunk costs. Reformulate the LP
under the conditions that each hour of foundry/forge time costs $95
while each hour of assembly line time costs $65.
The capacities remain as before.
Unused capacity has no charge.
-
A town is considering operating a materials recovery
center (MRC)
where paper can be separated and sold from municipal solid waste (MSW)
for $25 per ton.
The town generates 10,000 tons of MSW per year.
Fifty percent of the solid waste is recyclable paper.
The tipping fees are $10 per ton at the MRC and $50 per ton
at the landfill.
Note that materials not recycled at the MRC must be sent to
the landfill.
Assume all shipping fees are equal to zero.
Given the above information, would you
recommend operating the MRC?
Show your work including a simple network diagram.
Important Terms and Concepts:
Linear Programming (LP) - mathematical procedure for
determining optimal allocation of scarce resources.
Objective function - function defined within an LP
problem that is to be maximized or minimized;
often called the profit function.
constraints - limitations placed on the decision variables
in an LP problem
decision variables - variables that comprise the objective
function of a LP
slack variable - used to convert LP constraint equality
of type 1 (<=) to an equation;
a non-negative variable (slack variable) is added
to such an inequality to produce an equation;
For example, 3X1 + X2 - 2X3 <= 10 becomes
3X1 + X2 - 2X3 + X4 = 10 when X4 is added as a slack variable.
surplus variable - used to convert LP constraint
inequality of type 2 (>=) to an equation;
For example 4X1 + 2X2 >= 10 becomes 4X1 + 2X2 - X3 = 10
when a non-negative surplus variable is subtracted from
the left hand side.
Note that most LP solvers convert inequalities to equations
using slack and surplus variables prior to solving the objective function.
Simplex Method - the most widely used procedure for solving LP problems;
commonly used within computer-based LP solvers
Linear Programming (LP) is a mathematical procedure for
determining optimal
allocation of scarce resources.
LP has found practical application in nearly
all facets of business.
Transportation, distribution, and aggregate production planning
problems are the most typical objects of LP analysis.
Within agriculture, LP has been widely used
for allocation of limited resources (selection of crop land mix),
allocation of limited resources with time (irrigation),
formulation of least cost rations (animal feed),
and transportation.
It is important to note that "programming" in LP is quite
different than programming in a computer language such
as C or FORTRAN. With LP, the bulk of the effort is in
formulating the problem.
In LP problems, there are two types of objects: "limited
resources" such as land, labor, capital, or plant capacity;
and "activities" such as "produce corn flakes" or "produce widgets".
Each activity consumes or possibly contributes additional
amounts of the resources.
The problem is to determine the best combination of activity
levels which does not use more resources than are actually
available.
The following approach is normally followed in formulating
a model to be solved with linear programming:
- Define the control or decision variables
- Establish the objective function
- Establish constraints placed on the system
The constraint set of an optimization model model serve two major purposes:
- It simulates the system or process under investigation.
- It is a statement of restrictions reflecting policy, resources,
budgetary, and other limiting factors.
The region specified by the constraint set is called a feasible region.
The optimum solution will lie within or on the boundary
of the feasible region.
For linear models (as in the case of LP), the optimum solution
must occur at an extreme point, a point formed by the intersection
of boundary lines.
The following example will demonstrate a simple LP example
to provide a better understanding of how such problems
might be formulated and solved.
A Simple Product Mix LP Example
The XYZ Sensor Production company makes two types of sensors -
(1) wind speed and (2) rainfall.
There are two production lines, one for each type of sensor.
The capacity of the wind speed sensor line is 60 per day and the
capacity of the rainfall sensor line is 50 per day.
The wind speed sensor requires one manhour of labor
and the rainfall sensor requires 2 manhours of labor.
At the present time, there are 120 hours of labor per
day that can be used to produce these two types of sensors.
If the profits are $20 and $30 respectively
for each wind speed and rainfall sensor, what should
be the daily production?
First, let W represent the number of wind speed sensors
and R represent the number of rainfall sensors.
The second step is to define and write the objective function.
The objective function is:
Maximize 20W + 30R
Next the resource constraints are defined.
In this case, there are two types of constraints:
on labor and on the production capacity of the production lines.
W < = 60 (wind speed sensor line capacity)
R < = 50 (rainfall sensor line capacity)
W + 2R < = 120 (labor)
In addition to the above constraints, most LP solver computer
programs assume the constraint variables are nonnegative
(i.e., W >= 0 and R >= 0).
The constraints for the above problem are plotted in the
diagram below.
For the problem above, the objective function is maximized when 60
wind speed sensors and 30 rainfall sensors are produced.
Linearity
Linear programming applies directly only to situations in which the
effects of the different activities being examined are linear.
For practical purposes, the following requirements define the linearity
requirements:
- The effects of a single variable or activity by itself
are proportional; e.g., doubling the amount of steel produced
will double the dollar amount of steel sold, the amount of
electricity to produce the steel, etc., regardless of the
current level of steel produced
-
The interactions among variables must be additive; e.g., the dollar
amount of sales is the sum of the steel dollar sales, the aluminum
dollar sales, etc., while the amount of electricity used is
the sum of that used to produce steel, aluminum, etc.
-
The variables must be continuous; i.e., fractional values
for the decision variables, such as 3.46, must be allowed.
Outcomes (Solutions) to LP Problems
There are 4 possible outcomes when solving a LP:
-
Single unique optimum solution
-
Multiple optimum solutions
-
No feasible solution
-
Unbounded solution
Sensitivity Analysis
Once the LP model has been formulated,
a sensitivity analysis should be conducted to determine
how the system behaves under different conditions.
In many instances, there may also be some uncertainty about the
coefficients (unit costs) of the control variables.
Many LP solvers provide information concerning the sensitivity
of the solution if requested.
The figure below shows the solution for our example
problem above.
The figure that follows provides information
concerning the sensitivity of the solution.
For this particular example, the coefficient to the number
of wind speed gages produced (the profit per wind speed gage)
could decrease by 5 or increase to infinity without the solution changing
while the coefficient (profit) for the rain gages could increase
by 10 or decrease by 30 without the solution changing.
The information for rows 2, 3, and 4 represent the constraints:
W < = 60 (wind speed sensor line capacity)
R < = 50 (rainfall sensor line capacity)
W + 2R < = 120 (labor)
In this instance, changes in the righthand side values of the
constraints are given that would not change the solution.
Using this information, one can determine how sensitive the solution
obtained is - very often there are additional factors that can
not easily be put in mathematical form that may influence
a decision and thus the sensitivity analysis can be extremely valuable.
The sensitivity analysis also provides information that is useful
in understanding how well coefficients and constraints
must be defined.