Scribd
Upload
145 views

The Steps of The Simplex Algorithm

This document describes the steps of the simplex algorithm for solving linear programs. It begins by introducing standard form and how to write constraints with slack and surplus variables. It then discusses basic and non-basic variables. The main steps of the simplex algorithm are to choose an entering variable, choose a leaving variable, perform a pivot on the constraint matrix, and update the table until an optimal solution is found where the objective function is maximized or minimized.

Uploaded by

tbmari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
145 views

The Steps of The Simplex Algorithm

This document describes the steps of the simplex algorithm for solving linear programs. It begins by introducing standard form and how to write constraints with slack and surplus variables. It then discusses basic and non-basic variables. The main steps of the simplex algorithm are to choose an entering variable, choose a leaving variable, perform a pivot on the constraint matrix, and update the table until an optimal solution is found where the objective function is maximized or minimized.

Uploaded by

tbmari
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

THESTEPSOFTHESIMPLEXALGORITHM

Contents
1.

Introduction.............................................................................................................................2

2.

Slackandsurplusvariables......................................................................................................2

3.

Basicandnonbasicvariables...................................................................................................2

4.

Admissiblesolutions................................................................................................................3

5.

Solutionofalinearprogram(LP)............................................................................................3

6.

Lecritredarrt..............................................................................Erreur!Signetnondfini.

1. Introduction
A linear program (LP) that appears in a particular form where all constraints are
equationsandallvariablesarenonnegativeissaidtobeinstandardform.

2. Slack and surplus variables


Before the simplex algorithm can be used to solve a linear program, the problem
mustbewritteninstandardform.
a. Constraints of type ( ): for each constraint of this type, we add a slack
variable ,suchthat isnonnegative.
Example:3

2translatesinto3

2,

b. Constraintsoftype( ):foreachconstraint ofthistype,weaddasurplus


variable ,suchthat isnonnegative.
Example:3

2translatesinto3

2,

Alinearprogramthatcontains(technological)constraintsofthetype isabbreviated
as (LP). A linear program that contains mixed (technological) constraints , , ) is
abbreviated as (GP). A linear program (LP) resp. (GP)converted into standard form is
abbreviatedas(PL=)resp.(PG=).

3. Basic and nonbasic variables


Considerasystemofequationswith variablesand equationswhere
solutionforthissystemisobtainedinthefollowingway:

.Abasic

a) Set
variablesequaltozero.Thesevariablesarecallednonbasicvariables
(N.B.V).
b) Solvethesystemforthe remainingvariables.Thesevariablesarecalledbasic
variables(B.V.)
c) The vector of variables obtained is called the basic solution (it contains both
basicandnonbasicvariables).
Abasicsolutionisadmissibleifallvariablesofthebasicsolutionarenonnegative.
Itiscrucialtohavethesamenumberofvariablesasequations.

Page2of8

4. Admissible solutions
Each basic solution of (LP=) for which all variables are nonnegative, is called an
admissible basic solution. This admissible basic solution corresponds to an extreme
point(cornersolution).

5. Solution of a linear program (LP)

(LP)

(LP)

Ex:

. . 10
2

1000
1200
5
200
3
60
34
14
,
0

Ex:

. . 10
2
,

1000
5
3


,

1200
200
60
34
14
0

6and

2variables

Nonbasicvariables
x1 x2

Basicvariables:
200
60
34
14

then

Page3of8


StepA:initialtable
Coef.inZ
1000
Base

X1
Coef.Z BasicVar.
0
E1
10
0
E2
2
0
E3
1
0
E4
0
zj
0
Cjzj
1000

1200
X2

0
E1

0
E2

0
E3

0
E4

0
1
0
0
0
0

0
0
1
0
0
0

0
0
0
1
0
0

bi

200
60
34
14
0

5
3
0
1
0
1200

1
0
0
0
0
0

Theinitialtableiswritteninthefollowingway:
Thebleuframecorrespondstotheconstraintsof(LP=).
Thegreenframecorrespondsto :thecoefficientsin

Exampleforthecolumnof

called( ):
0

10

The pink frames correspond to the coefficients ( ) of the variables in the


objectivefunction( ).
Thegreyframecorrespondstothevalueofthebasicvariables.
Theorangeframecorrespondstothevalueof ,i.e.thevalueoftheobjective
function,calculatedasfollows:
0

200

60

34

14

StepB:selectionoftheenteringvariable(tothesetofbasicvariables)
Maximumofthe formaximumproblems.
Minimumofthe
In our example:
variables.

fortheminimumproblems.

has the greatest

; hence it enters in the set of basic

Page4of8


StepC:selectionoftheleavingvariable
InaproblemofeitherminORmax,theleavingvariableistheminimumof
0
Inourexample,weneedtoevaluate:
Enteringvariable
Coef.inZ
Base

Coef.Z Basic
Var.
0
E1
0
E2
0
E3
0
E4
zj
Cjzj

1000
X1

1200
X2

0
E1

0
E2

0
E3

0
E4

bi

0
1
0
0
0
0

0
0
1
0
0
0

0
0
0
1
0
0

200
60
34
14
0

10
2
1
0
0
1000

5
3
0
1
0
1200

1
0
0
0
0
0

200/5=40
60/3=20
14/1=14istheminimum,hence
variables.

isthevariablethatleavesthesetofbasic

StepD:pivot
Coef.inZ
Base

Coef.Z Basic
var.
0
E1
0
E2
0
E3
0
E4
zj
Cjzj

1000
X1

1200
X2

0
E1

0
E2

0
E3

0
E4

bi

0
1
0
0
0
0

0
0
1
0
0
0

0
0
0
1
0
0

200
60
34
14
0

10
2
1
0
0
1000

5
3
0
1
0
1200

1
0
0
0
0
0

Page5of8

Thebluecelliscalledthepivot.Togotothenexttable(andhencetocarryoutthe
firstiteration),itisessentialtousethepivot.
Pivotinggoeslikethis:
Onestartsbydividingthelineofthepivotbythepivot.
Inourexample,wedivideby1.
Coef.inZ
Base

Coef.Z Basic
var.
0
E1
0
E2
0
E3
1200
X2
zj
Cjzj

1000
X1

1200
X2

0
E1

0
E2

0
E3

0
E4

bi

0
0
0

0
0
0

1
0
0

14
0

0
0
1000

1
0
1200

0
0
0

Wecontinuetoconstructtheidentitymatrixforthebasicvariables.Wewriteonethe
intersectionofthesevariablesandzeroelsewhere.
Coef.inZ
Base

Coef.Z Basic
var.
0
E1
0
E2
0
E3
1200
X2
zj
Cjzj

1000
X1

1200
X2

0
E1

0
E2

0
E3

0
E4

bi

0
1
0
0
0
0

0
0
1
0
0
0

1
0
0

14
0

0
0
1000

0
0
0
1
0
1200

1
0
0
0
0
0

Weneedtocalculatethevaluesfortheremainingcellsfromtheprevioustable(orthe
initialtableforthefirstiteration).

Page6of8

Coef.inZ
Base

Coef.Z Basic
var.
0
E1
0
E2
0
E3
1200
X2
zj
Cjzj

1000
X1

1200
X2

0
E1

0
E2

0
E3

0
E4

bi

0
0
1000

0
0
0
1
0
1200

1
0
0
0
0
0

0
1
0
0
0
0

0
0
1
0
0
0

1
0
0

14
0

1000
X1

1200
X2

0
E1

0
E2

0
E3

0
E4

bi

0
1
0
0
0
0

0
0
1
0
0
0

0
0
0
1
0
0

200
60
34
14
0

Initialtable:
Coef.inZ
Base

Coef.Z Basic
var.
0
E1
0
E2
0
E3
0
E4
zj
Cjzj

10
2
1
0
0
1000

5
3
0
1
0
1200

1
0
0
0
0
0

Inourexample,the10intheredframedcelliscalculatedwiththefollowingformula

10
Hence, 10

05
1

10.

Letuscalculatethegreenframedcell.Weobtain3inthefollowingway:
0

31

1

Page7of8

Coef.inZ
Base

Coef.Z Basic
var.
0
E1
0
E2
0
E3
1200
X2
zj
Cjzj

1000
X1

1200
X2

0
E1

0
E2

0
E3

0
E4

bi

0
1
0
0
0
0

0
0
1
0
0
0

5
3
0
1
0
0

14
0

10
2
1
0
0
1000

0
0
0
1
0
1200

1
0
0
0
0
0

Theremainingcellsarecalculatedinthesameway.Whenthetableisfull(suchasthe
one below), one can continue to the second iteration, that will be carried out in the
sameway.

6. Stopping criterion
Westopwhenwereachtheoptimalitycriterion.Thesimplexalgorithmstopswhen:

0foramaximumproblem
0foraminimumproblem

Page8of8

You might also like