simplex method for operation research .pdf

simplex method for operation research academic

1. The Simplex Method
Thegraphicalmethodofsolvinglinearprogrammingproblemsis
usefulonlyforproblemsinvolvingtwodecisionvariablesand
relativelyfewproblemconstraints.
Whathappenswhenweneedmoredecisionvariablesandmoreproblemconstraints?
Weuseanalgebraicmethodcalledthesimplexmethod,which
wasdevelopedbyGeorgeB.DANTZIG(1914-2005)in1947while
onassignmentwiththeU.S.Departmentoftheairforce.

2. Standard Maximization Problems in
Standard Form
Alinearprogrammingproblemissaidtobeastandardmaximizationproblemin
standardformifitsmathematicalmodelisofthefollowingform:
Maximize the objective function
Subject to problem constraints of the form
With non-negative constraintsmax 1 1 2 2 ...
nnZ P cx cx c x     1 1 2 2... , 0
nnax ax ax b b     12, ,..., 0
nx x x

3. Slack Variables
“A mathematical representation of surplus
resources.” In real life problems, it’s unlikely
that all resources will be used completely, so
there usually are unused resources.
Slack variables represent the unused resources
between the left-hand side and right-hand
side of each inequality.

4. Basic and Nonbasic Variables
Basicvariablesareselectedarbitrarilywiththerestrictionthat
therebeasmanybasicvariablesasthereareequations.The
remainingvariablesarenon-basicvariables.
Thissystemhastwoequations,wecanselectanytwoofthefour
variablesasbasicvariables.Theremainingtwovariablesare
thennon-basicvariables.Asolutionfoundbysettingthetwo
non-basicvariablesequalto0andsolvingforthetwobasic
variablesisabasicsolution.Ifabasicsolutionhasnonegative
values,itisabasicfeasiblesolution.1 2 1
1 2 2
2 32
3 4 84
x x s
x x s
  
  

5. SIMPLEX METHOD
Step-1
Writethe
standard
maximization
problem in
standardform,
introduceslack
variablestoform
theinitialsystem,
andwritethe
initialtableau.
Step-3
Select
the
pivot
column
Step-5
Selectthe
pivot
element
and
perform
thepivot
operation
STOP
Theoptimal solutionhas been
found.
STOP
Thelinearprogramming
problem has no optimal
solution
Step 2
Arethere
any
negative
indicators
in the
bottom
row?
Step 4
Arethere
anypositive
elementsin
thepivot
column
abovethe
dashed
line?
Simplex algorithm for standard maximization problems
NO
Y
Y
NO

6. To solve a linear programming problem in standard form, use the following steps.
1-Converteachinequalityinthesetofconstraintstoanequationbyaddingslack
variables.
2-Createtheinitialsimplextableau.
3-Selectthepivotcolumn.(Thecolumnwiththe“mostnegativevalue”element
inthelastrow.)
4-Selectthepivotrow.(Therowwiththesmallestnon-negativeresultwhenthe
lastelementintherowisdividedbythecorrespondinginthepivotcolumn.)
5-Useelementaryrowoperationscalculatenewvaluesforthepivotrowsothat
thepivotis1(Divideeverynumberintherowbythepivotnumber.)
6-Useelementaryrowoperationstomakeallnumbersinthepivotcolumnequal
to0exceptforthepivotnumber.Ifallentriesinthebottomrowarezeroor
positive,thisthefinaltableau.Ifnot,gobacktostep3.
7-Ifyouobtainafinaltableau,thenthelinearprogrammingproblemhasa
maximumsolution,whichisgivenbytheentryinthelower-rightcornerof
thetableau.

7. Pivot
Pivot Column: The column of the tableau
representing the variable to be entered into
the solution mix.
Pivot Row:The row of the tableau representing
the variable to be replaced in the solution mix.
Pivot Number:The element in both the pivot
column and the pivot row.

8. Simplex Tableau
Mostreal-worldproblemsaretoocomplexto
solvegraphically.Theyhavetoomanycorners
toevaluate,andthealgebraicsolutionsare
lengthy.Asimplextableauisawayto
systematicallyevaluatevariablemixesinorder
tofindthebestone.

9. All variables Solution
Basic variables coefficients
0
Initial Simplex Tableau

10. EXAMPLE
TheCannonHillfurnitureCompanyproducestables
andchairs.Eachtabletakesfourhoursoflabor
fromthecarpentrydepartmentandtwohoursof
laborfromthefinishingdepartment.Eachchair
requiresthreehoursofcarpentryandonehour
offinishing.Duringthecurrentweek,240hours
ofcarpentrytimeareavailableand100hoursof
finishingtime.Eachtableproducedgivesaprofit
of$70andeachchairaprofitof$50.Howmany
chairsandtablesshouldbemade?

11. All information about example
Resource Table s ( )Chairs ( )Constraints
Carpentry (hr) 4 3 240
Finishing (hr) 2 1 100
Unit Profit $70 $501x 2x
Objective Function
Carpentry Constraint
Finishing Constraint
Non-negativity conditions1270 50P x x 124 3 240xx 122 1 100xx 12,0xx
STEP 1

12. Thefirststepofthesimplexmethodrequiresthateachinequality
beconvertedintoanequation.”lessthanorequalto”
inequalitiesareconvertedtoequationsbyincludingslack
variables.
Supposecarpentryhoursand finishinghoursremainunused
inaweek.Theconstraintsbecome;
or
Asunusedhoursresultinnoprofit,theslackvariablescanbe
includedintheobjectivefunctionwithzerocoefficients:1 2 1
1 2 2
4 3 240
2 100
x x s
x x s
  
   1s 2s 1 2 1 2
1 2 1 2
4 3 0 240
2 0 100
x x s s
x x s s
   
    1 2 1 2
1 2 1 2
70 50 0 0
70 50 0 0 0
P x x s s
P x x s s
   
    

13. Theproblemcannowbeconsideredassolvingasystemof3linear
equationsinvolvingthe5variables insuchaway
thatPhasthemaximumvalue;
Now,thesystemoflinearequationscanbewritteninmatrixform
orasa3x6augmentedmatrix.Theinitialtableauis;1 2 1 2, , , ,x x s s P 1 2 1 2
1 2 1 2
1 2 1 2
4 3 0 240
2 0 100
70 50 0 0 0
x x s s
x x s s
P x x s s
   
   
    

14. Basic
Variables
x
1 x
2 S
1 S
2 P
Right
Hand
Side
S
1 4 3 1 0 0 240
S
2 2 1 0 1 0 100
P -70-500 0 1 0
The tableau represents the initial solution;
The slack variables S
1and S
2form the initial solution mix. The initial
solution assumes that all avaliable hours are unused. i.e. The slack variables
take the largest possible values.1 2 1 20, 0, 240, 100, 0x x s s P    
STEP 2

15. Variablesinthesolutionmixarecalledbasicvariables.Eachbasic
variableshasacolumnconsistingofall0’sexceptforasingle1.
allvariablesnotinthesolutionmixtakethevalue0.
Thesimplexprocess,abasicvariableinthesolutionmixis
replacedbyanothervariablepreviouslynotinthesolution
mix.Thevalueofthereplacedvariableissetto0.

16. Selectthepivotcolumn(determinewhichvariabletoenterintothe
solutionmix).Choosethecolumnwiththe“mostnegative”
elementintheobjectivefunctionrow.
STEP 3
Basic
Variables
x
1 x
2 S
1 S
2 P
Right
hand
side
S
1 4 3 1 0 0 240
S
2 2 1 0 1 0 100
P -70-500 0 1 0
Pivot column
x
1shouldenterintothesolutionmixbecauseeachunitofx
1(atable)
contributesaprofitof$70comparedwithonly$50foreachunitofx
1(a
chair)

17. STEP 5
Selectthepivotrow(determinewhichvariabletoreplaceinthesolutionmix).
Dividethelastelementineachrowbythecorrespondingelementinthe
pivotcolumn.Thepivotrowistherowwiththesmallestnon-negative
result.
Basic
Variables
x
1 x
2 S
1 S
2 P
Right
hand
side
S
1 4 3 1 0 0 240
S
2 2 1 0 1 0 100
P -70-500 0 1 0240/4 60 100/2 50
Pivot column
Pivot row
Enter
Exit
Pivot number

18. Shouldbereplacedbyx
1inthesolutionmix.60tablescanbemadewith240
unusedcarpentryhoursbutonly50tablescanbemadewith100finishing
hours.Thereforewedecidetomake50tables.
Nowcalculatenewvaluesforthepivotrow.Divideeverynumberintherow
bythepivotnumber.
Basic
Variables
x
1 x
2 S
1 S
2 P
Right
hand
side
S
1 4 3 1 0 0 240
x
1 11/201/20 50
P -70-500 0 1 02
2
R

19. Basic
Variables
x
1 x
2 S
1 S
2 P
Right
hand
side
S
1 0 1 1 -2 0 40
x
1 11/201/20 50
P 0-150 35 13500214.RR 2370.RR
Use row operations to make all numbers in the pivot column equal to 0 except
for the pivot number which remains as 1.
If50tablesaremade,thentheunusedcarpentryhoursarereducedby200
hours(4h/tablemultipliedby50tables);thevaluechangesfrom240hoursto40
hours.Making50tablesresultsintheprofitbeingincreasedby$3500;thevalue
changesfrom$0to$3500.

20. In this case,
Now repeat the steps until there are no negative numbers in the last row.
Select the new pivot column. x
2should enter into the solution mix.
Select the new pivot row. S
1should be replaced by x
2in the solution mix.1 2 1 250, 0, 40, 0, 3500x x s s P    
Basic
Variables
x
1 x
2 S
1 S
2 P
Right
hand
side
S
1 0 1 1 -2 0 40
x
1 11/201/20 50
P 0-150 35 1350040/1 40 50/0,5 100
New pivot
column
New pivot row
Enter
Exit

21. Basic
Variables
x
1 x
2 S
1 S
2 P
Right
hand
side
x
2 0 1 1 -2 0 40
x
1 1 0-1/23/20 30
P 0 0 15 5 14100
Calculatenewvaluesforthepivotrow.Asthepivotnumberisalready1,
thereisnoneedtocalculatenewvaluesforthepivotrow.
Userowoperationstomakeallnumbersinthepivotcolumnequalto
exceptforthepivotnumber.12
1
.
2
RR 1315.RR

22. If40chairsaremade,thenthenumberoftablesarereducedby
20tables(1/2table/chairmultipliedby40chairs);thevalue
changesfrom50tablesto30tables.Thereplacementof20
tablesby40chairsresultsintheprofitbeingincreasedby
$600;thevaluechangesfrom$3500to$4100.
As the last row contains no negative numbers, this solution gives
the maximum value of P.

23. Result
Thissimplextableaurepresentstheoptimal
solutiontotheLPproblemandisinterpreted
as:
and profit or P=$4100
The optimal solution (maximum profit to be
made) is to company 30 tables and 40 chairs
for a profit of $4100.1 2 1 230, 40, 0, 0x x s s   

24. Example-2
Afarmerownsa100acrefarmandplanstoplantat
mostthreecrops.TheseedforcropsA,B,andCcosts
$40,$20,and$30peracre,respectively.Amaximum
of$3200canbespentonseed.CropsA,B,andC
require1,2,and1workdaysperacre,respectively,
andtherearemaximumof160workdaysavailable.If
thefarmercanmakeaprofitof$100peracreon
cropA,$300peracreoncropB,and$200peracre
oncropC,howmanyacresofeachcropshouldbe
plantedtomaximizeprofit?