Module 6 Linear Programming
Table of contents
1. Objectives
2. Types of Linear Programming Models and Applications
3. Linear Programming
4. Model Formulation
4.1. Linear Programming Model Formulation
4.2. Illustrative Problem for Linear Programming
4.3. Graphical Solution Method
4.4. A Minimization Linear Programming Model
5. The Simplex Method
5.1. Slack and Surplus Variables
5.2. Illustrative Problem for Simplex Method
6. Sensitivity Ranges
7. References
1. Objectives
The Learners are expected to:
1. Understand what is Linear Programming.
2. Understand the objective function.
3. Understand the simplex method.
4. Understand the formulation of a linear program.
2. Types of Linear Programming Models and Applications
Linear Programming
Model Type OM Application
Aggregate Production Determines the resource capacity needed to meet
Planning demand over an immediate time horizon, including
units produced, workers hired and fired, and inventory.
Product Mix Mix of different products to produce that will
maximize profit or minimize cost given resource
constraints such as material, labor, budget, and so
forth.
Transportation Logistical flow of items (goods or services) from
sources to destinations, for example, truckloads of
goods from plants to warehouses.
Transshipment Flow of items from sources to destinations with
intermediate points, for example, shipping from plant
to distribution center and then to stores.
Assignment Assigns work to limited resources, called “Loading,”
for example, assigning jobs or workers to different
machines.
Multiperiod Schedules regular and overtime production, plus
Scheduling inventory to carry over, to meet demand in future
periods.
Blend Determines “recipe” requirements, for example, how
to blend different petroleum components to produce
different grades of gasoline and other petroleum
products.
Diet Menu of food items that meets nutritional or other
requirements, for example, hospital or school
cafeteria menus.
Investment/Capital Financial model that determines amount to invest in
Budgeting different alternatives given return objectives and
constraints for risk, diversity, and so forth, for
example, how much to invest in a new plant, facilities,
or equipment.
Data Envelopment Compares service units of the same type—banks,
Analysis (DEA) hospitals, schools—based on their resources and
outputs to see which units are less productive or
inefficient.
Shortest Route Shortest routes from sources to destinations, for
example, the shortest highway truck route from coast
to coast.
Maximal Flow Maximizes the amount of flow from sources to
destinations, for example, the flow of work in process
through an assembly operation.
Trim-Loss Determines patterns to cut sheet items to minimize
waste, for example, cutting lumber, film, cloth, glass,
and so forth.
Facility Location Selects facility locations based on constraints such as
fixed, operating, and shipping costs, production
capacity, and so forth.
Set Covering Selection of facilities that can service a set of other
facilities, for example, the selection of distribution
hubs that will be able to deliver packages to a set of
cities.
3. Linear Programming
Linear programming is a mathematical modeling technique used to determine a level of
operational activity in order to achieve an objective, subject to restrictions called constraints.
Many decisions faced by an operations manager are centered around the best way to achieve
the objectives of the firm subject to the constraints of the operating environment. These
constraints can be limited resources, such as time, labor, energy, materials, or money, or they
can be restrictive guidelines, such as a recipe for making cereal, engineering specifications, or a
blend for gasoline. The most frequent objective of business firms is to maximize profit—whereas
the objective of individual operational units within a firm (such as a production or packaging
department) is often to minimize cost.
Linear programming A model consisting of linear relationships representing a firm’s objective
and resource constraints.
● The constraints define the limit or decision environment of the problem. The term
optimal may mean maximizing profit or minimizing cost in the specific context. Linear
programming models are used to assist people and organizations in making decisions.
● Linear Programming (LP) is a widely used problem-solving method. The LP problem is to
determine the optimal value of a linear function which defines the objectives of the
problem subject to a set linear constraint
4. Model Formulation
A common linear programming problem is to determine the number of units to produce to
maximize profit subject to resource constraints such as labor and materials. All these
components of the decision situation—the decisions, objectives, and constraints—are expressed
as mathematically linear relationships that together form a model.
A linear programming model consists of decision variables, an objective function, and model
constraints. Decision variables are mathematical symbols that represent levels of activity of an
operation. For example, an electrical manufacturing firm wants to produce radios, toasters, and
clocks. The number of each item to produce is represented by symbols, x1, x2, and x3. Thus,
x1=the number of radios, x2=the number of toasters, and x3=the number of clocks. The final
values of x1, x2, and x3, as determined by the firm, constitute a decision (e.g., x1=10x1=10 radios
is a decision by the firm to produce 10 radios).
Decision variables Mathematical symbols representing levels of activity of an operation.
The objective function is a linear mathematical relationship that describes the objective of an
operation in terms of the decision variables. The objective function always either maximizes or
minimizes some value (e.g., maximizing the profit or minimizing the cost of producing radios).
For example, if the profit from a radio is $6, the profit from a toaster is $4, and the profit from a
clock is $2, then the total profit, Z, is Z=$6x1+4x2+2x3.
Objective function A linear relationship reflecting the objective of an operation.
The model constraints are also linear relationships of the decision variables; they represent the
restrictions placed on the decision situation by the operating environment. The restrictions can
be in the form of limited resources or restrictive guidelines. For example, if it requires 2 hours of
labor to produce a radio, 1 hour to produce a toaster, and 1.5 hours to produce a clock, and only
40 hours of labor are available, the constraint reflecting this is 2x1+1x2+1.5x3≤40 .
Constraint A linear relationship representing a restriction on decision making.
The general structure of a linear programming model is as follows:
Maximize (or minimize) Z=c1x1+c2x2+...+cnxnZ=c1x1+c2x2+...+cnxn
subject to
a11x1+a12x2+⋯+a1nxn(≤,=,≥)b1
a21x1+a22x2+⋯+a2nxn(≤,=,≥)b2
an1x1+an2x2+⋯+annxn(≤,=,≥)bn
xi≥0
where
xi=decision variables
bi=constraint levels
cj=objective function coefficients
aij=constraint coefficients
4.1. Linear Programming Model Formulation
The Highlands Craft Store is a small craft operation that employs local artisans to produce clay
bowls and mugs based on designs and colors from the 1700s and 1800s. The two primary
resources used by the company are special pottery clay and skilled labor. Given these limited
resources, the company wants to know how many bowls and mugs to produce each day to
maximize profit.
The two products have the following resource requirements for production and selling price per
item produced (i.e., the model parameters):
Resource Requirements
Produc Labor (hr/unit) Clay (lb/unit) Revenue ($/unit)
t
Bowl 1 4 40
Mug 2 3 50
There are 40 hours of labor and 120 pounds of clay available each day. Formulate this problem
as a linear programming model.
Solution:
Management’s decision is how many bowls and mugs to produce represented by the following
decision variables:
x1=number of bowls to produce
x2=number of mugs to produce
The objective of the company is to maximize total revenue computed as the sum of the
individual profits gained from each bowl and mug:
Maximize Z=$40x1+50x2
The model contains the constraints for labor and clay, which are
x1+2x2 ≤ 40hr
4x1+3x2 ≤ 120lb
The less than or equal to inequality(≤) is used instead of an equality (=) because 40 hours of
labor is a maximum that can be used, not an amount that must be used. However, constraints
can be equalities,(=), greater than or equal to inequalities (≥), or less than or equal to inequalities
(≤) .
The complete linear programming model for this problem can now be summarized as follows:
Maximize Z=$40x1+$50x2
subject to
1x1+2x2≤40
4x1+3x2≤120
x1,x2≥0
The solution of this model will result in numerical values for x1 and x2 that maximize total profit,
Z, without violating the constraints. The solution that achieves this objective is x1=24 bowls and
x2=8 mugs, with a corresponding revenue of $1360.
4.2. Illustrative Problem for Linear Programming
4.3. Graphical Solution Method
The basic steps in the graphical solution method are to plot the model constraints on a set of
coordinates in a plane and identify the area on the graph that satisfies all the constraints
simultaneously. The point on the boundary of this space that maximizes (or minimizes) the
objective function is the solution.
Graphical Solution
Determine the solution for Highlands Craft Store :
Maximize Z= $40x1 + $50x2
subject to
x1+2x2 ≤ 40
4x1+3x2 ≤ 120
x1,x2$0
Solution:
The graph of the model constraints is shown in the following figure of the feasible solution
space. The graph is produced in the positive quadrant since both decision variables must be
positive or zero; that is, x1,x2≥0 :
STEP 1 is to plot the constraints on the graph. This is done by treating both constraints as
equations (or straight lines) and plotting each line on the graph. A simple way to plot a line is to
determine where it intersects the horizontal and vertical axes and draw a straight line
connecting the points. The shaded area in the preceding figure is the area that is common to
both model constraints. Therefore, this is the only area on the graph that contains points (i.e.,
values for x1 and x2) that will satisfy both constraints simultaneously. This area is the feasible
solution space, because it is the only area that contains values for the variables that are
feasible, or do not violate the constraints.
Feasible solution space An area that satisfies all constraints in a linear programming model
simultaneously.
STEP 2 is to locate the point in the feasible solution area that represents the greatest total
revenue. We will plot the objective function line for an arbitrarily selected level of revenue. For
example, if revenue, Z, is $800, the objective function is
$800=40x1+50x2
Plotting this line just as we plotted the constraint lines results in the graph showing the
determination of the optimal point in the following figure. Every point on this line is in the
feasible solution area and will result in a revenue of $800 (i.e., every combination of x1 and x2 on
this line will give a Z value of $800). As the value of Z increases, the objective function line
moves out through the feasible solution space away from the origin until it reaches the last
feasible point on the boundary of the solution space and then leaves the solution space.
The solution point is always on this boundary, because the boundary contains the points
farthest from the origin (i.e., the points corresponding to the greatest profit). Moreover, the
solution point will not only be on the boundary of the feasible solution area, but it also will be at
one of the corners of the boundary where two constraint lines intersect. These corners (labeled
A, B, and C in the following figure) are protrusions called extreme points. It has been proven
mathematically that the optimal solution in a linear programming model will always occur at an
extreme point. Therefore, in our example problem, the possible solution points are limited to the
three extreme points A, B, and C. The optimal, or “one best,” solution point is B, since the
objective function touches it last before it leaves the feasible solution area.
Extreme points Corner points on the boundary of the feasible solution space.
Optimal solution The single best solution to a problem.
Because point B is formed by the intersection of two constraint lines, these two lines are equal
at point B. Thus, the values of x1 and x2 at that intersection can be found by solving the two
equations simultaneously:
x1+2x2= 40
4x1+3x2= 120
−−−−−−−−−−−−−−−−−−−
4x1+8x2= 160
−4x1−3x2=−120
−−−−−−−−−−−−−−−−−−−
5x2=40
x2=8
Thus,
x1+2(8)=40
x1=24
The optimal solution at point B in the preceding figure is x1=24x1=24 bowls and x2=8x2=8
mugs. Substituting these values into the objective function gives the maximum revenue,
Z=$40(24)+$50(8)=$1360
Given that the optimal solution will be at one of the extreme corner points A, B, or C, you can find
the solution by testing each of the three points to see which results in the greatest revenue
rather than by graphing the objective function and seeing which point it last touches as it moves
out of the feasible solution area. The following figure shows the solution values for all three
points A, B, and C and the amount of revenue, Z, at each point:
The objective function determines which extreme point is optimal, because the objective
function designates the revenue that will accrue from each combination of x1 and x2 values at
the extreme points. If the objective function had had different coefficients (i.e., different x1 and
x2 profit values), one of the extreme points other than B might have been optimal.
Assume for a moment that the revenue for a bowl is $70 instead of $40 and the revenue for a
mug is $20 instead of $50. These values result in a new objective function, Z=$70x1+20x2. If
the model constraints for labor or clay are not changed, the feasible solution area remains the
same, as shown in the following figure. However, the location of the objective function in this
figure is different from that of the original objective function in the previous figure because the
new profit coefficients give the linear objective function a new slope. Point C becomes optimal,
with Z=$2100 . This demonstrates one of the useful functions of linear programming—and
model analysis in general—called sensitivity analysis: the ability to test changes in the model
parameters reflecting different operating environments to analyze the impact on the solution.
4.4. A Minimization Linear Programming Model
The Farmer’s Hardware and Feed Store is putting together a fertilizer mix for a farmer who is
preparing a field to plant a crop. The store will use two brands of fertilizer, Gro-Plus and
Crop-Fast, to make the proper mix for the farmer. Each brand yields a specific amount of
nitrogen and phosphate, as follows:
Chemical Contribution
Brand Nitrogen (lb/bag) Phosphate
(lb/bag)
Gro-Plus 2 4
Crop-Fast 4 3
The farmer’s field requires at least 16 pounds of nitrogen and 24 pounds of phosphate. Gro-Plus
costs $6 per bag, and Crop-Fast costs $3. The store wants to know how many bags of each
brand to purchase to minimize the total cost of fertilizing. Formulate a linear programming
model for this problem, and solve it using the graphical method.
Solution:
This problem is formulated as follows:
Minimize Z=$6x1+3x2
subject to
2x1+4x2≥16lb of nitrogen
4x1+3x2≥24lb of phosphate
x1, x2≥0
The graphical solution of the problem is shown in the following figure. Notice that the optimal
solution, point A, occurs at the last extreme point the objective function touches as it moves
toward the origin (point 0,0).
5. The Simplex Method
● The simplex method presents an organized strategy for evaluating a feasible region's
vertices. This helps to figure out the optimal value of the objective function.
● Objectives of a simplex method
○ The simplex method is used to eradicate the issues in linear programming.
○ It examines the feasible set's adjacent vertices in sequence to ensure that, at
every new vertex, the objective function increases or is unaffected.
○ The simplex method uses a systematic strategy to generate and test candidate
vertex solutions to a linear program.
●
Graphically determining the solution to a linear programming model can provide insight into how
a solution is derived, but it is not generally effective or efficient. The traditional mathematical
approach for solving a linear programming problem is a mathematical procedure called the
simplex method. In the simplex method, the model is put into the form of a table, and then a
number of mathematical steps are performed on the table. These mathematical steps are the
same as moving from one extreme point on the solution boundary to another. However, unlike
the graphical method, in which we simply searched through all the solution points to find the
best one, the simplex method moves from one better solution to another until the best one is
found.
5.1. Slack and Surplus Variables
Recall that the solution to a linear programming problem occurs at an extreme point where
constraint equation lines intersect with each other or with the axis. Thus, the model constraints
must all be in the form of equations (=) rather than inequalities (≥ or ≤) .
The procedure for transforming inequality constraints into equations is by adding a new
variable, called a slack variable, to each constraint. For the Beaver Creek Pottery Company, the
addition of a unique slack variable (si) to each of the constraint inequalities results in the
following equations:
Slack variable A variable added to a linear programming constraint to make it an equality.
x1+2x2+s1=40 hours of labor
4x1+3x2+s2=120 lb of clay
The slack variables, s1 and s2, will take on any value necessary to make the left side of the
equation equal to the right side. If slack variables have a value in the solution, they generally
represent unused resources. Since unused resources would contribute nothing to total revenue,
they have a coefficient of zero in the objective function:
MaximizeZ=$40x1+50x2+0s1+0s2
The graph shows all the solution points in our Beaver Creek Pottery Company example with the
values for decision and slack variables.
This example is a maximization problem with all ≤ constraints. A minimization problem with ≥
constraints requires a different adjustment. With a ≥ constraint, instead of adding a slack
variable, we subtract a surplus variable. Whereas a slack variable is added and reflects unused
resources, a surplus variable is subtracted and reflects the excess above a minimum
resource-requirement level. Like the slack variable, a surplus variable is represented
symbolically by si and must be nonnegative.
For example, consider the following constraint from our fertilizer mix problem, presented in the
Minimization Linear Programming model in a previous lesson:
2x1+4x2≥16
Surplus variable A variable subtracted from a linear programming constraint to make it an
equality.
Subtracting a surplus variable results in
2x1+4x2−s1=16
The graph shows all the solution points with the values for decision and surplus variables for
the minimization problem.
5.2. Illustrative Problem for Simplex Method
6. Sensitivity Ranges
The marginal, or dual values do not hold for an unlimited supply of labor and clay. As the store
increases (or reduces) the amount of labor or clay it has, the constraints change, which will
eventually change the solution to a new point. Thus, the dual values are only good within a range
of consistent values. These ranges are given under the column labeled “Allowable Increase” and
“Allowable Decrease” in Exhibit S14.4. For example, the original amount of labor available is 40
hours. The dual value of $16 for one hour of labor holds if the available labor is between 30 and
80 hours. If there are more than 80 hours of labor, then a new solution point occurs and the dual
value of $16 is no longer valid. The problem would have to be solved again to see what the new
solution is and the new dual value.
This can be observed graphically. If the labor hours are increased from 40 to 80 hours, the
constraint line moves out and up. The new solution space is OA'C, and a new solution variable
mix occurs at A', as shown in Figure S14.3a. At the original optimal point, B, both x1 and x2 are in
the solution; however, at the new optimal point, A', only x2 is produced (i.e., x1=0, x2=40, s1=0,
s2=0 ).
Thus, the upper limit of the sensitivity range for the labor constraint is 80 hours. At this value the
solution mix changes such that bowls are no longer produced. Furthermore, as labor increases
past 80 hours, s1 increases (i.e., slack hours are created). Similarly, if labor hours are decreased
to 30 hours, the constraint line moves down and in. The new feasible solution space is OA'C,as
shown in Figure S14.3b. The new optimal point is at C, where no mugs (x2) are produced. The
new solution is x1=30, x2=0, s1=0, s2=0,and Z=$1200 . Again, the variable mix is changed.
Summarizing, the sensitivity range for the constraint quantity value for labor hours, is between
30 and 80 hours.
A similar range of values exist for the clay constraint. The solution values are good for down to
60 lbs and up to 160 lbs.
There are also sensitivity ranges for the objective function coefficients: “$40” for bowls and
“$50” for mugs. The optimal solution point will remain the same if the profit for a bowl remains
within $25 and $66.67, or if the profit for mugs remains between $30 and $80.
If the profit for a bowl increases from $40 to $66.67, the objective function line rotates to a new
location where it is parallel with the constraint line for clay, as shown in Figure S14.4a. (At this
new location, the objective function line and the constraint line for clay have the same slope.)
Both points B and C are now optimal. If the profit for bowls is increased greater than $66.67,
then only point C will be optimal and we will have a new solution mix. Similarly, if the profit for a
bowl is decreased to $25, as shown in Figure S14.4b, points A and B are both optimal. If the
profit for a bowl is decreased to less than $25, only point A will be optimal and a new solution
exists. Thus, the range for the profit for a bowl is between $25 and $66.67. Over this range the
current solution mix will remain optimal, and the marginal values are valid.
These sensitivity ranges for constraint values and objective function values provide managers
with a convenient means for analyzing resource usage. The marginal value of resources lets
managers know what their resources are worth as they make decisions, and the sensitivity
ranges indicate the ranges over which the marginal values are valid. When using software like
Excel, it is often just as easy to change different values in the linear programming model and
see what happens. In either case, this points out a very useful feature of linear programming: It
not only provides you with a possible solution or decision, but it also enables you to
“experiment” with the model to test different operational scenarios.
7. References
1. Powell,S., & Baker,K. (2013). Management Science: The Art of Modeling with
Spreadsheets. [Link]. ISBN: 9781118786840
2. William, T.(2008). Management Science in Practice. [Link].
ISBN: 978EUDTE00317
3. Puschmann, T., & Alt, R. (2005). Supply Chain Management: An International
Journal. Successful use of e-procurement in supply chains, 10 (2), 122
-[Link], S., Müll
4. Chen, F., Drezner, Z., Ryan, J. K., & Simchi-Levi, D. (2000). Quantifying the Bullwhip
Effect in a Simple Supply Chain: The Impact of Forecasting, Lead Times, and
Information. Management Science, 436- 443.
5. [Link]
6. Russell, Roberta S., Bernard Taylor. Operations and Supply Chain Management, 10th
Edition. Wiley, 10/2019. VitalBook file