Filetype PDF | Posted on 28 Jan 2023 | 2 years ago
Authentication
digital resources
174x Filetype PDF File size 0.34 MB Source: crab.rutgers.edu
99790_17_ch17_p001-047.qxd 03/08/2007 04:27 PM Page 17-1
CHAPTER 17
Linear Programming:
Simplex Method
CONTENTS
17.1 AN ALGEBRAIC OVERVIEW 17.6 TABLEAU FORM:
OF THE SIMPLEX METHOD THE GENERALCASE
Algebraic Properties of the Greater-Than-or-Equal-to
Simplex Method Constraints
Determining a Basic Solution Equality Constraints
Basic Feasible Solution Eliminating Negative Right-Hand-
17.2 TABLEAU FORM Side Values
Summary of the Steps to Create
17.3 SETTING UPTHE INITIAL Tableau Form
SIMPLEX TABLEAU 17.7 SOLVING AMINIMIZATION
17.4 IMPROVING THE SOLUTION PROBLEM
17.5 CALCULATING THE NEXT 17.8 SPECIALCASES
TABLEAU Infeasibility
Interpreting the Results of an Unboundedness
Iteration Alternative Optimal Solutions
Moving Toward a Better Solution Degeneracy
Interpreting the Optimal Solution
Summary of the Simplex Method
99790_17_ch17_p001-047.qxd 03/08/2007 04:27 PM Page 17-2
17-2 Chapter 17 Linear Programming: Simplex Method
InChapter2weshowedhowthegraphicalsolutionprocedurecanbeusedtosolvelinearpro-
gramming problems involving two decision variables. However, most linear programming
problemsaretoolargetobesolvedgraphically,andanalgebraicsolutionproceduremustbe
employed.Themostwidelyusedalgebraicprocedureforsolvinglinearprogrammingprob-
1
lemsiscalledthesimplexmethod. Computerprogramsbasedonthismethodcanroutinely
solve linear programming problems with thousands of variables and constraints. The Man-
agement Science inAction, FleetAssignment at DeltaAir Lines, describes solving a linear
programinvolving60,000variablesand40,000constraintsonadailybasis.
MANAGEMENT SCIENCE IN ACTION
FLEETASSIGNMENTATDELTAAIR LINES*
Delta Air Lines uses linear and integer programming shows the size of linear programs that can be solved
in its Coldstart project to solve its fleet assignment today. The typical size of the daily Coldstart model
problem. The problem is to match aircraft to flight is about 60,000 variables and 40,000 constraints.
legs and fill seats with paying passengers. Airline The first step in solving the fleet assignment prob-
profitability depends on being able to assign the right lem is to solve the model as a linear program.
size of aircraft to the right leg at the right time of day. The model developers report successfully solving
An airline seat is a perishable commodity; once a these problems on a daily basis and contend that
flight takes off with an empty seat the profit poten- use of the Coldstart model will save Delta Air Lines
tial of that seat is gone forever. Primary objectives of $300 million over the next three years.
the fleet assignment model are to minimize operat-
ing costs and lost passenger revenue. Constraints are *Based on R. Subramanian, R. P. Scheff, Jr., J. D.
aircraft availability, balancing arrivals and depar- Quillinan, D. S. Wiper, and R. E. Marsten, “Coldstart:
tures at airports, and maintenance requirements. Fleet Assignment at Delta Air Lines,” Interfaces
The successful implementation of the Cold- (January/February 1994): 104–120.
start model for assigning fleet types to flight legs
17.1 AN ALGEBRAIC OVERVIEWOFTHE SIMPLEX METHOD
Let us introduce the problem we will use to demonstrate the simplex method. HighTech In-
dustries imports electronic components that are used to assemble two different models of
personal computers. One model is called the Deskpro, and the other model is called the
Portable. HighTech’s management is currently interested in developing a weekly produc-
tion schedule for both products.
The Deskpro generates a profit contribution of $50 per unit, and the Portable generates
a profit contribution of $40 per unit. For next week’s production, a maximum of 150 hours
of assembly time can be made available. Each unit of the Deskpro requires 3 hours of
assembly time, and each unit of the Portable requires 5 hours of assembly time. In addi-
tion, HighTech currently has only 20 Portable display components in inventory; thus, no
more than 20 units of the Portable may be assembled. Finally, only 300 square feet of ware-
house space can be made available for new production. Assembly of each Deskpro requires
8 square feet of warehouse space; similarly, each Portable requires 5 square feet.
1
Several computer codes also employ what are called interior point solution procedures. They work well on many large prob-
lems, but the simplex method is still the most widely used solution procedure.
99790_17_ch17_p001-047.qxd 03/08/2007 04:27 PM Page 17-3
17.1 An Algebraic Overview of the Simplex Method 17-3
To develop a linear programming model for the HighTech problem, we will use the fol-
lowing decision variables:
x number of units of the Deskpro
1
x2 number of units of the Portable
The complete mathematical model for this problem is presented here.
Max 50x 40x
1 2
s.t.
3x 5x 150 Assembly time
1 2
1x2 20 Portable display
8x 5x 300 Warehouse capacity
1 2
x , x 0
1 2
Adding a slack variable to each of the constraints permits us to write the problem in
standard form.
Max 50x 40x 0s 0s 0s (17.1)
1 2 1 2 3
s.t.
3x 5x 1s 150 (17.2)
1 2 1
1x2 1s2 20 (17.3)
8x 5x 1s 300 (17.4)
1 2 3
x , x , s , s , s 0 (17.5)
1 2 1 2 3
The simplex method was Algebraic Properties of the Simplex Method
developed by George Constraintequations(17.2)to(17.4)formasystemofthreesimultaneouslinearequationswith
Dantzig while working for
the U.S. Air Force. It was five variables.Wheneverasystemofsimultaneouslinearequationshasmorevariablesthan
first published in 1949. equations,wecanexpectaninfinitenumberofsolutions.Thesimplexmethodcanbeviewed
as an algebraic procedure for finding the best solution to such a system of equations. In the
preceding example, the best solution is the solution to equations (17.2) to (17.4) that maxi-
mizestheobjectivefunction(17.1)andsatisfiesthenonnegativityconditionsgivenby(17.5).
Determining a Basic Solution
For the HighTech Industries constraint equations, which have more variables (five) than
equations (three), the simplex method finds solutions for these equations by assigning zero
values to two of the variables and then solving for the values of the remaining three vari-
ables. For example, if we set x2 0 and s1 0, the system of constraint equations becomes
3x1 150 (17.6)
1s 20 (17.7)
2
8x1 1s3 300 (17.8)
99790_17_ch17_p001-047.qxd 03/08/2007 04:27 PM Page 17-4
17-4 Chapter 17 Linear Programming: Simplex Method
Using equation (17.6) to solve for x , we have
1
3x 150
1
and hence x 150/3 50. Equation (17.7) provides s 20. Finally, substituting x 50
1 2 1
into equation (17.8) results in
8(50) 1s3 300
Solving for s , we obtain s 100.
3 3
Abasic solution is obtained Thus, we obtain the following solution to the three-equation, five-variable set of linear
by setting two of the five equations:
variables equal to zero and
solving the three equations x 50
simultaneously for the 1
values of the other three x2 0
variables. Mathematically, s1 0
we are guaranteed a s 20
solution only if the resulting 2
three equations are linearly s3 100
independent. Fortunately,
the simplex method is This solution is referred to as a basic solution for the HighTech linear programming prob-
designed to guarantee that lem. To state a general procedure for determining a basic solution, we must consider a
a solution exists for the standard-form linear programming problem consisting of n variables and m linear equa-
basic variables at each tions, where n is greater than m.
iteration.
Basic Solution
To determine a basic solution, set n m of the variables equal to zero, and solve the
mlinear constraint equations for the remaining m variables.2
In terms of the HighTech problem, a basic solution can be obtained by setting any two
variables equal to zero and then solving the system of three linear equations for the re-
maining three variables. We shall refer to the n m variables set equal to zero as the non-
basicvariablesandtheremainingmvariablesasthebasicvariables.Thus,inthepreceding
example, x and s are the nonbasic variables, and x , s , and s are the basic variables.
2 1 1 2 3
Basic Feasible Solution
Abasic solution can be either feasible or infeasible. Abasic feasible solution is a basic so-
lution that also satisfies the nonnegativity conditions. The basic solution found by setting
x and s equal to zero and then solving for x , s , and s is not a basic feasible solution be-
2 1 1 2 3
cause s 100. However, suppose that we had chosen to make x and x nonbasic vari-
3 1 2
ables by setting x1 0 and x2 0. Solving for the corresponding basic solution is easy
because with x x 0, the three constraint equations reduce to
1 2
1s 150
1
1s 20
2
1s3 300
2
In some cases, a unique solution cannot be found for a system of m equations and n variables. However, these cases will
never be encountered when using the simplex method.
no reviews yet
Please Login to review.
