Solving Linear Programming Problems with
Simplex Method
Suppose you are a wholesale fruit buyer for a grocery store. You have been given the assignment to
purchase five varieties of apples, two varieties of peaches, and three varieties of pears. The grocery
store has known budget and space constraints. You are asked to maximize the number of pieces of
fruit purchased. This linear programming problem has 10 decision variables and cannot be solved
graphically. Although the graphical method works well for linear programming problems with two
decision variables, it does not work for problems containing more than two decision variables.
We will introduce an alternative method that may be used to solve linear programming problems with
any number of decision variables.
In 1947, George B. Dantzig developed the simplex method to solve linear programming problems.
His method has been used to solve linear programming problems with hundreds of decision variables
and hundreds of constraints.
First we will use the method to solve standard maximization problems.
Solving Standard Maximization Problems
Graphically speaking, the simplex method starts at the origin and moves from corner point to corner point
of the feasible region, each time increasing the value of the objective function until it attains its maximum
value. Remarkably, the method doesn’t require that all corner points be tested, a fact that is appreciated
by those solving linear programming problems with hundreds of corner points.
Although the simplex method may be used for linear programming problems with any number of decision
variables, we will restrict our use to problems with four variables or less. Larger problems are typically
solved using computers.
We will introduce the simplex method with a two-variable example before formally listing the steps of the
method.
Definitions
In the Simplex method the nonnegative variables which we add to the inequality ≤ to make it an equality = are
called slack variables.
After we change the system of constrained inequalities to the system of equalities after adding slack variables,
we can represent the system of equations using matrix notation. The augmented matrix is called the initial
simplex tableau.
The variables of the columns of the simplex tableau that contain exactly one nonzero entry are called active
(basic) variables. The variables of the columns that contain more than one nonzero entry are called inactive
(nonbasic) variables. Inactive variables we set = 0.
For the initial tableau, the slack s, t, etc. and the objective function are the active variables, since their
corresponding columns in the tableau contain exactly one nonzero value.
Exercises
1. 1-10 Exercises from the page 60.
2. Solve the standard maximization problems by using the simplex method. Check your answer by graphing the feasible
region and calculating the value of the objective function at each of the corner points:
a)
b)
3. Solve the standard maximization problems by using the simplex method:
a)
b)
4. A plain hamburger requires one ground beef patty and a bun. A cheeseburger requires one ground beef patty, one
slice of cheese, and a bun. A double cheeseburger requires two ground beef patties, two slices of cheese, and a bun.
Frozen hamburger patties are typically sold in packs of 12; hamburger buns, in packs of 8; and cheese slices, in
packs of 24. A family is in charge of providing burgers for a neighborhood block party. The family members have
purchased 13 packs of buns, 11 packs of hamburger patties, and 3 packs of cheese slices. How many of each type of
sandwich should the family prepare if its members want to maximize the number of burgers with cheese?
Solving Standard Minimization Problems
with the Dual
The Dual
For a standard minimization problem whose objective function has nonnegative coefficients, we may
construct a standard maximization problem called the dual problem. By solving the dual problem, we
can find the solution to the standard minimization problem.
Consider the standard minimization problem,
Exercises
1. In Exercises 1–10, from page 79, determine if the problem is a standard minimization problem. If it isn’t,
explain why.
2. In Exercises 11–20 , from page 79, find the transpose of the given matrix.
3.
4.
5. Wal-Mart Stores, Inc., has food distribution centers in Monroe, Georgia, and Shelbyville, Tennessee, and Wal-
Mart Supercenters in Birmingham, Alabama, and Scottsboro, Alabama. (Source: [Link].) Suppose
that the Monroe distribution center must ship at least 600 cases of peanut butter weekly and the Shelbyville
distribution center must ship at least 400 cases of peanut butter weekly.* If the Birmingham store requires at least
700 cases of peanut butter weekly and the Scottsboro store requires at least 300 cases of peanut butter weekly,
what shipment plan will minimize the distribution cost?
Solving General Linear Programming Problems
with the Simplex Method
A general linear programming problem is a linear programming problem with mixed constraints.
First we will see how to solve a maximization general linear programming problem.
To transfer inequalities ≥ to the equalities = we subtract some nonnegative value u called a surplus
variable from the left-hand side of the inequality.
Minimization Problems
What if we want to minimize the objective function? Fortunately, with one minor modification to the
objective function, the same procedure works. We begin by observing the relationship between a function f
and the function - f = -1 · f shown in the Figure
Exercises
1. Solve the general linear programming problem. If there is no solution, so state.
a)
b)
c)
d)
[Link]’s Market Prices ([Link]) is a daily fruit and vegetable wholesale market price service.
Produce retailers who subscribe to the service can use wholesale prices to aid them in setting retail prices for the
fruits and vegetables they sell. A 25-pound carton of peaches holds 60 medium peaches or 70 small peaches. In
August 2002, the wholesale price for local peaches in Los Angeles was $9.00 per carton for medium peaches and
$10.00 per carton for small peaches. (Source: Today’s Market Prices.) A fruit vendor has budgeted up to $100 to
spend on peaches. He estimates that weekly demand for peaches is no more than 660 peaches. He wants to buy
at least four boxes of each size of peach. Subject to these constraints, how many boxes of each size of peach
should he buy in order to maximize the number of peaches available for sale?