Unit4
Simplex Method
Simplex Method
• It is the classic algorithm for linear
programming.
• Many important practical problems can be
modeled as instances of linear programming.
Example
• Optimizing a linear function of several
variables subject to a set of linear constraints.
• Maximize (or) Minimize
c1x1 + … + cnxn
Subject to
ai1x1 + …. + ainxn ≤ (or ≥ or =) bi
For i=1,…m
x1 ≥0,… xn ≥0
Simplex Method
• A feasible solution to this problem is any point
(x,y) that satisfies all the constraints of the
problem.
• The problem’s feasible region is the set of all its
feasible points.
• Linear programming problem with the empty
feasible region are called infeasible.
• Infeasible problems do not have optimal
solutions.
An outline of the simplex method
Geometric description
Translate
algebra
Standard form
• Has the following requirements
1. It must be a maximization problem.
2. All the constraints (except the non negativity
constraints) must be in the form of linear
equations.
3. All the variables must be required to be non
negative.
Standard form
• Thus, the general linear programming problem in
standard form with m constraints and n unknowns
(n≥m) is,
• maximize or minimize
c1x1 + … + cnxn
Subject to
ai1x1 + …. + ainxn ≤ (or ≥ or =) bi
For i=1,…m
x1 ≥0,… xn ≥0
Standard form
• It can also be written in compact matrix
notation.
• Maximize cx
subject to
Ax = b
x ≥0
Standard form
• Any linear programming problem can be
transformed in to an equivalent problem in
standard form.
• If a constraint is given as an inequality
• It can be replaced by an equivalent equation
by adding slack variables.
Summary of the simplex method
Step1 (initialization)
• Present a given linear programming problem
- in standard form
- set up an initial table
- with non negative entries
in the rightmost column.
- m other columns
composing the m by m identity matrix
Step1 (initialization)
These m columns define the basic variables
Of the initial basic feasible solution
Used as the labels of the table’s rows
Step2 (optimality test)
• If all the entries in the objective row are non
negative
• Stop: the table represents an optimal solution
• Whose basic variables are in the right most
column
• And the remaining non basic variables are zero
Step3 (finding the entering variable)
Select a –ve entry, among the first n elements
of the objective row
Make its column to indicate the entering
variable and the pivot column
Step4 (finding the departing/leaving variable)
For each –ve entry in the pivot column
Calculate the ratio, by dividing that row’s entry in
the rightmost column , by its entry in the pivot
column
Find the row with the smallest ratio
Mark this row, to indicate the departing variable
and the pivot row
Step5 (forming the next table)
Divide all the entries in the pivot row, by its
entry in the pivot column
Subtract from each of the above rows, including
the objective row
The new pivot row, multiplied by the entry in the
pivot column of the row in question
Step5 (forming the next table)
• Replace the label of the pivot row , by the
variable’s name of the pivot column and go
back to step1