pdfbox c# port : Create bookmark pdf file SDK software service wpf winforms .net dnn AMP-Chapter-041-part512

140
DualityinLinearProgramming
4.4
subjectto:
n
j
=
1
a
ij
x
j
b
i
(
i
=
1
,
2
,...,
m
),
n
j
=
1
a
ij
x
j
b
i
(
i
=
m
+
1
,
m
+
2
,...,
m

),
(11)
n
j
=
1
a
ij
x
j
=
b
i
(
i
=
m

+
1
,
m

+
2
,...,
m
),
x
j
0
(
j
=
1
,
2
,...,
n
).
Sincethedualofthedualistheprimal,weknowthatthedualofaminimizationproblemwillbeamaximization
problem.Thedualof(11)canbefoundbyperformingtransformationssimilartothoseconductedpreviously.
Theresultingdualof(11)isthefollowingmaximizationproblem:
Maximize
v =
m
i
=
1
b
i
y
i
+
m

i
=
m
+
1
b
i
y
i
+
m
i
=
m
+
1
b
i
y

i
,
subjectto:
m
i
=
1
a
ij
y
i
+
m

i
=
m
+
1
a
ij
y
i
+
m
i
=
m

+
1
a
ij
y

i
c
j
(12)
y
i
0
(
i
=
1
,
2
,...,
m
),
y
i
0
(
i
=
m
+
1
,
m
+
2
,...,
m

).
Observethatnowthesignofthedualvariablesassociatedwiththeinequalityconstraintshaschanged,
asmightbeexpectedfromtheshadow-priceinterpretation. Inacost-minimizationproblem,increasingthe
availableresourceswilltendtodecreasethetotalcost,sincetheconstrainthasbeenrelaxed.Asaresult,the
dualvariableassociatedwithaless-than-or-equal-toconstraintinaminimizationproblemisnonpositive.On
theotherhand,increasingrequirementscouldonlygenerateacostincrease.Thus,agreater-than-or-equal-to
constraintinaminimizationproblemhasanassociatednonnegativedualvariable.
Theprimalanddualproblemsthatwehavejustdevelopedillustrateonefurtherdualitycorrespondence.
If(12)isconsideredastheprimalproblemand(11)asitsdual,thenunrestrictedvariablesintheprimalare
associatedwithequalityconstraintsinthedual.
Wenowcansummarizethegeneraldualityrelationships.Basicallywenotethatequalityconstraintsinthe
primalcorrespondtounrestrictedvariablesinthedual,whileinequalityconstraintsintheprimalcorrespond
torestrictedvariablesinthedual,wherethesignoftherestrictioninthedualdependsuponthecombinationof
objective-functiontypeandconstraintrelationintheprimal.Thesevariouscorrespondencesaresummarized
inTable4.1.Thetableisbasedontheassumptionthattheprimalisamaximizationproblem.Sincethedual
ofthedualistheprimal,wecaninterchangethewordsprimalanddualinTable4.1andthecorrespondences
willstillhold.
4.4 THEFUNDAMENTALDUALITYPROPERTIES
Intheprevioussectionsofthischapterwehaveillustratedmanydualitypropertiesforlinearprogramming.In
thissectionweformalizesomeoftheassertionswehavealreadymade.Thereadernotinterestedinthetheory
shouldskipoverthissectionentirely,ormerelyreadthestatementsofthepropertiesandignoretheproofs.
Weconsidertheprimalproblemininequalityformsothattheprimalanddualproblemsaresymmetric.Thus,
Create bookmark pdf file - add, remove, update PDF bookmarks in C#.net, ASP.NET, MVC, Ajax, WinForms, WPF
Empower Your C# Project with Rapid PDF Internal Navigation Via Bookmark and Outline
create bookmark pdf; adding bookmarks in pdf
Create bookmark pdf file - VB.NET PDF bookmark library: add, remove, update PDF bookmarks in vb.net, ASP.NET, MVC, Ajax, WinForms, WPF
Empower Your VB.NET Project with Rapid PDF Internal Navigation Via Bookmark and Outline
create bookmarks in pdf; add bookmarks pdf
4.4
TheFundamentalDualityProperties
141
Table4.1
Primal(Maximize)
Dual(Minimize)
ithconstraint
ithvariable
0
ithconstraint
ithvariable
0
ithconstraint
=
ithvariableunrestricted
jthvariable
0
jthconstraint
jthvariable
0
jthconstraint
jthvariableunrestricted
jthconstraint
=
anystatementthatismadeabouttheprimalproblemimmediatelyhasananalogforthedualproblem,and
conversely.Forconvenience,werestatetheprimalanddualproblems.
Primal
Maximizez
=
n
j
=
1
c
j
x
j
,
subjectto:
n
j
=
1
a
ij
x
j
b
i
(
i
=
1
,
2
,...,
m
),
(13)
x
j
0
(
j
=
1
,
2
,...,
n
).
Dual
Minimize
v=
m
i
=
1
b
i
y
i
,
subjectto:
m
i
=
1
a
ij
y
i
c
j
(
j
=
1
,
2
,...,
n
),
(14)
y
i
0
(
i
=
1
,
2
,...,
m
).
Thefirstpropertyisreferredtoas‘‘weakduality’’andprovidesaboundontheoptimalvalueofthe
objectivefunctionofeithertheprimalorthedual.Simplystated,thevalueoftheobjectivefunctionforany
feasiblesolutiontotheprimalmaximizationproblemisboundedfromabovebythevalueoftheobjective
functionforanyfeasiblesolutiontoitsdual. Similarly,thevalueoftheobjectivefunctionforitsdualis
boundedfrombelowbythevalueoftheobjectivefunctionoftheprimal.Pictorially,wemightrepresentthe
situationasfollows:
Dual
feasible
v
decreasing
Primal
feasible
zincreasing
Thesequenceofpropertiestobedevelopedwillleadustothe‘‘strongduality"property,whichstates
thattheoptimalvaluesoftheprimalanddualproblemsareinfactequal. Further,indevelopingthisresult,
weshowhowthesolutionofoneoftheseproblemsisreadilyavailablefromthesolutionoftheother.
VB.NET Create PDF from Excel Library to convert xlsx, xls to PDF
C#.NET Annotate PDF in WPF, C#.NET PDF Create, C#.NET NET convert PDF to images, C#.NET PDF file & pages search text in PDF, C#.NET edit PDF bookmark, C#.NET
convert word to pdf with bookmarks; acrobat split pdf bookmark
VB.NET PDF File Split Library: Split, seperate PDF into multiple
Split PDF document by PDF bookmark and outlines in VB.NET. 3, 5} ' Valid value for each index: 1 to (Page Count - 1). ' Create output PDF file path list
bookmarks pdf files; how to bookmark a pdf file in acrobat
142
DualityinLinearProgramming
4.4
WeakDualityProperty. If
x
j
,
j
=
1
,
2
,...,
n, is afeasiblesolutionto theprimalproblemand
y
i
,
i
=
1
,
2
,...,
m,isafeasiblesolutiontothedualproblem,then
n
j
=
1
c
j
x
j
m
i
=
1
b
i
y
i
.
Theweakdualitypropertyfollowsimmediatelyfromtherespectivefeasibilityofthetwosolutions.Primal
feasibilityimplies:
n
j
=
1
a
ij
x
j
b
i
(
i
=
1
,
2
,...,
m
)
and
x
j
0
(
j
=
1
,
2
,...,
n
),
whiledualfeasibilityimplies
m
i
=
1
a
ij
y
i
c
j
(
j
=
1
,
2
,...,
n
)
and
y
i
0
(
i
=
1
,
2
,...,
m
).
Hence,multiplyingtheithprimalconstraintby
y
i
andaddingyields:
m
i
=
1
n
j
=
1
a
ij
x
j
y
i
m
i
=
1
b
i
y
i
,
whilemultiplyingthe jthdualconstraintby
x
j
andaddingyields:
n
j
=
1
m
i
=
1
a
ij
y
i
x
j
n
j
=
1
c
j
x
j
.
Sincethelefthandsidesofthesetwoinequalitiesareequal,togethertheyimplythedesiredresultthat
n
j
=
1
c
j
x
j
m
i
=
1
b
i
y
i
.
Thereareanumberofdirectconsequencesoftheweakdualityproperty. Ifwehavefeasiblesolutions
totheprimalanddualproblemssuchthattheirrespectiveobjectivefunctionsareequal,thenthesesolutions
areoptimaltotheirrespectiveproblems. Thisresultfollowsimmediatelyfromtheweakdualityproperty,
sinceadualfeasiblesolutionisanupperboundontheoptimalprimalsolutionandthisboundisattained
bythegivenfeasibleprimalsolution. Theargumentforthedualproblemisanalogous. Hence,wehavean
optimalitypropertyofduallinearprograms.
OptimalityProperty. If
ˆ
x
j
,
j
=
1
,
2
,...,
n,isafeasiblesolutiontotheprimalproblemand
ˆ
y
i
,
i
=
1
,
2
,...,
m,isafeasiblesolutiontothedualproblem,and,further,
n
j
=
1
c
j
ˆ
x
j
=
m
i
=
1
b
i
ˆ
y
i
,
then
ˆ
x
j
,
j
=
1
,
2
,...,
n,isanoptimalsolutiontotheprimalproblemand
ˆ
y
i
,i
=
1
,
2
,...,
m,isan
optimalsolutiontothedualproblem.
Furthermore,ifoneproblemhasanunboundedsolution,thenthedualofthatproblemisinfeasible.This
mustbetruefortheprimalsinceanyfeasiblesolutiontothedualwouldprovideanupperboundontheprimal
objectivefunctionbytheweakdualitytheorem;thiscontradictsthefactthattheprimalproblemisunbounded.
Again,theargumentforthedualproblemisanalogous.Hence,wehaveanunboundednesspropertyofdual
linearprograms.
C# Create PDF from Word Library to convert docx, doc to PDF in C#.
Easy to create searchable and scanned PDF files from Word. Able to get word count in PDF pages. Change Word hyperlink to PDF hyperlink and bookmark.
how to add a bookmark in pdf; split pdf by bookmark
VB.NET PDF File Compress Library: Compress reduce PDF size in vb.
list below is mainly to optimize PDF file with multiple 3.pdf"; String outputFilePath = Program.RootPath + "\\" 3_optimized.pdf"; 'create optimizing options
create bookmarks pdf files; add bookmarks to pdf
4.4
TheFundamentalDualityProperties
143
UnboundednessProperty. Iftheprimal(dual)problemhasanunboundedsolution,thenthedual(pri-
mal)problemisinfeasible.
Wearenowinapositiontogivethemainresultofthissection,the‘‘strongduality’’property. The
importanceofthispropertyisthatitindicatesthatwemayinfactsolvethedualprobleminplaceofor
inconjunctionwiththeprimalproblem. Theproofofthisresultdepends s merelyonobservingthatthe
shadowpricesdeterminedbysolvingtheprimalproblembythesimplexmethodgiveadualfeasiblesolution,
satisfyingtheoptimalitypropertygivenabove.
StrongDualityProperty. Iftheprimal(dual)problemhasafiniteoptimalsolution,thensodoesthe
dual(primal)problem,andthesetwovaluesareequal.Thatis,
ˆ
z
=ˆv
where
ˆ
z
=
Max
n
j
=
1
c
j
x
j
,
ˆv=
Min
m
i
=
1
b
i
y
i
,
subjectto:
subjectto:
n
j
=
1
a
ij
x
j
b
i
,
m
i
=
1
a
ij
y
i
c
j
,
x
j
0
;
y
i
0
.
Letusseehowtoestablishthisproperty. Wecanconverttheprimalproblemtotheequivalentequality
formbyaddingslackvariablesasfollows:
Maximizez
=
n
j
=
1
c
j
x
j
,
subjectto:
n
j
=
1
a
ij
x
j
+
x
n
+
i
=
b
i
(
i
=
1
,
2
,...,
m
),
x
j
0
(
j
=
1
,
2
,...,
n
+
m
).
Supposethatwehaveappliedthesimplexmethodtothelinearprogramand
ˆ
x
j
,
j
=
1
,
2
,...,
n,istheresulting
optimalsolution.Let
ˆ
y
i
,
i
=
1
,
2
,...,
m,betheshadowpricesassociatedwiththeoptimalsolution.Recall
thattheshadowpricesassociatedwiththeoriginalconstraintsarethemultiplesofthoseconstraintswhich,
whensubtractedfromtheoriginalformoftheobjectivefunction,yieldtheformoftheobjectivefunctionin
thefinaltableau[Section3.2,expression(11)].Thusthefollowingconditionholds:
z
+
n
j
=
1
c
j
x
j
=−
m
i
=
1
b
i
ˆ
y
i
,
(15)
where,duetotheoptimalitycriterionofthesimplexmethod,thereducedcostssatisfy:
c
j
=
c
j
m
i
=
1
a
ij
ˆ
y
i
0
(
j
=
1
,
2
,...,
n
),
(16)
and
c
j
=
0
−ˆ
y
i
0
(
j
=
n
+
1
,
n
+
2
,...,
n
+
m
).
(17)
VB.NET PDF File Merge Library: Merge, append PDF files in vb.net
Professional VB.NET PDF file merging SDK support Visual Studio .NET. Merge PDF without size limitation. Append one PDF file to the end of another one in VB.NET.
how to bookmark a pdf in reader; create pdf bookmarks from word
C# PDF File Split Library: Split, seperate PDF into multiple files
defined pages. Divide PDF file into multiple files by outputting PDF file size. Split PDF document by PDF bookmark and outlines. Also
adding bookmarks to pdf; add bookmarks to pdf reader
144
DualityinLinearProgramming
4.5
Conditions(16)and(17)implythat
ˆ
y
i
,fori
=
1
,
2
,...,
m,constitutesafeasiblesolutiontothedualproblem.
Whenx
j
isreplacedbytheoptimalvalue
ˆ
x
j
inexpression(15),theterm
n
j
=
1
c
j
ˆ
x
j
isequaltozero,since
c
j
=
0when
ˆ
x
j
isbasic,and
ˆ
x
j
=
0when
ˆ
x
j
isnonbasic. Therefore,themaximum
valueofz,say
ˆ
z,isgivenby:
−ˆ
z
=−
m
i
=
1
b
i
ˆ
y
i
.
Moreover,since
ˆ
x
j
,forj
=
1
,
2
,...,
n,isanoptimalsolutiontotheprimalproblem,
n
j
=
1
c
j
ˆ
x
j
z
=
m
i
=
1
b
i
ˆ
y
i
.
Thisistheoptimalitypropertyfortheprimalfeasiblesolution
ˆ
x
j
,
j
=
1
,
2
,...,
n,andthedualfeasible
solution
ˆ
y
i
,
i
=
1
,
2
,...,
m,sotheyareoptimalfortheirrespectiveproblems. (Theargumentintermsof
thedualproblemisanalogous.)
Itshouldbepointedoutthatitisnottruethatiftheprimalproblemisinfeasible,thenthedualproblem
isunbounded. Inthiscasethedualproblemmaybeeitherunboundedorinfeasible. Allfourcombinations
offeasibilityandinfeasibilityforprimalanddualproblemsmaytakeplace.Anexampleofeachisindicated
inTable4.2.
Inexample(2)ofTable4.2itshouldbeclearthatx
2
maybeincreasedindefinitelywithoutviolating
feasibilitywhileatthesametimemakingtheobjectivefunctionarbitrarilylarge.Theconstraintsofthedual
problemforthisexampleareclearlyinfeasiblesincey
1
+
y
2
2andy
1
+
y
2
≤−
1cannotsimultaneously
hold.Asimilarobservationismadeforexample(3),exceptthattheprimalproblemisnowinfeasiblewhile
thedualvariabley
1
maybeincreasedindefinitely. Inexample(4),thefactthatneitherprimalnordual
problemisfeasiblecanbecheckedeasilybymultiplyingthefirstconstraintofeachbyminusone.
4.5 COMPLEMENTARYSLACKNESS
Wehaveremarkedthatthedualitytheorydevelopedintheprevioussectionisaunifyingtheoryrelatingthe
optimalsolutionofalinearprogramtotheoptimalsolutionoftheduallinearprogram,whichinvolvesthe
shadowpricesoftheprimalasdecisionvariables.Inthissectionwemakethisrelationshipmorepreciseby
definingtheconceptofcomplementaryslacknessrelatingthetwoproblems.
ComplementarySlacknessProperty. If,inanoptimalsolutionofalinearprogram,thevalueofthedual
variable(shadowprice)associatedwithaconstraintisnonzero,thenthatconstraintmustbesatisfiedwith
equality. Further,ifaconstraintissatisfiedwithstrictinequality,thenitscorrespondingdualvariable
mustbezero.
Fortheprimallinearprogramposedasamaximizationproblemwithless-than-or-equal-toconstraints,
thismeans:
i)
if
ˆ
y
i
>
0
,
then
n
j
=
1
a
ij
ˆ
x
j
=
b
i
;
ii)
if
n
j
=
1
a
ij
ˆ
x
j
<
b
i
, then
ˆ
y
i
=
0.
VB.NET Create PDF from Word Library to convert docx, doc to PDF in
Easy to create searchable and scanned PDF files from Word. Ability to get word count of PDF pages. Change Word hyperlink to PDF hyperlink and bookmark.
pdf create bookmarks; how to bookmark a pdf page
C# PDF File Compress Library: Compress reduce PDF size in C#.net
list below is mainly to optimize PDF file with multiple pdf"; String outputFilePath = Program.RootPath + "\\" 3_optimized.pdf"; // create optimizing options
create pdf bookmark; bookmarks pdf documents
4.5
ComplementarySlackness
145
Table4.2
1
Primalfeasible
Dualfeasible
Maximizez
=
2x
1
+
x
2
,
Minimize
v=
4y
1
+
2y
2
,
subjectto:
subjectto:
x
1
+
x
2
4
,
x
1
x
2
2
,
x
1
0
,
x
2
0
.
y
1
+
y
2
2
,
y
1
y
2
1
,
y
1
0
,
y
2
0
.
2
Primalfeasibleandunbounded
Dualinfeasible
Maximizez
=
2x
1
+
x
2
,
Minimize
v=
4y
1
+
2y
2
,
subjectto:
subjectto:
x
1
x
2
4
,
x
1
x
2
2
,
x
1
0
,
x
2
0
.
y
1
+
y
2
2
,
y
1
y
2
1
,
y
1
0
,
y
2
0
.
3
Primalinfeasible
Dualfeasibleandunbounded
Maximizez
=
2x
1
+
x
2
,
Minimize
v=−
4y
1
+
2y
2
,
subjectto:
subjectto:
x
1
x
2
≤−
4
,
x
1
+
x
2
2
,
x
1
0
,
x
2
0
.
y
1
+
y
2
2
,
y
1
+
y
2
1
,
y
1
0
,
y
2
0
.
4
Primalinfeasible
Dualinfeasible
Maximizez
=
2x
1
+
x
2
,
Minimize
v=−
4y
1
+
2y
2
,
subjectto:
subjectto:
x
1
+
x
2
≤−
4
,
x
1
x
2
2
,
x
1
0
,
x
2
0
.
y
1
+
y
2
2
,
y
1
y
2
1
,
y
1
0
,
y
2
0
.
Wecanshowthatthecomplementary-slacknessconditionsfollowdirectlyfromthestrongdualityproperty
justpresented.Recallthat,indemonstratingtheweakdualityproperty,weusedthefactthat:
n
j
=
1
c
j
ˆ
x
j
m
i
=
1
n
j
=
1
a
ij
ˆ
x
j
ˆ
y
i
m
i
=
1
b
i
ˆ
y
i
(18)
forany
ˆ
x
j
,
j
=
1
,
2
,...,
n,and
ˆ
y
i
,
i
=
1
,
2
,...,
m,feasibletotheprimalanddualproblems,respectively.
Now,sincethesesolutionsarenotonlyfeasiblebutoptimaltotheseproblems,equalitymustholdthroughout.
Hence,consideringtherighthandrelationshipin(18),wehave:
m
i
=
1
n
j
=
1
a
ij
ˆ
x
j
ˆ
y
i
=
m
i
=
1
b
i
ˆ
y
i
,
whichimplies:
m
i
=
1
n
j
=
1
a
ij
ˆ
x
j
b
i
ˆ
y
i
=
0
.
C# PDF File Merge Library: Merge, append PDF files in C#.net, ASP.
concatenating library SDK, C# developers can easily merge and append one PDF document to another PDF document file, and choose to create a new PDF file in .NET
create pdf bookmarks online; create bookmark pdf file
146
DualityinLinearProgramming
4.5
Sincethedualvariables
ˆ
y
i
arenonnegativeandtheircoefficients
n
j
=
1
a
ij
ˆ
x
j
b
i
arenonpositivebyprimalfeasibility,thisconditioncanholdonlyifeachofitstermsisequaltozero;thatis,
n
j
=
1
a
ij
ˆ
x
j
b
i
ˆ
y
i
=
0
(
i
=
1
,
2
,...,
m
).
Theselatterconditionsareclearlyequivalentto(i)and(ii)above.
Fortheduallinearprogramposedasaminimizationproblemwithgreater-than-or-equal-toconstraints,
thecomplementary-slacknessconditionsarethefollowing:
iii)
if
ˆ
x
j
>
0, then
m
i
=
1
a
ij
y
i
=
c
j
,
iv)
if
m
i
=
1
a
ij
ˆ
y
i
>
c
j
, then
ˆ
x
j
=
0.
Theseconditionsalsofollowdirectlyfromthestrongdualitypropertybyanargumentsimilartothatgiven
above.Byconsideringthelefthandrelationshipin(18),wecaneasilyshowthat
m
i
=
1
a
ij
y
i
c
j
x
j
=
0
(
j
=
1
,
2
,...,
n
),
whichisequivalentto(iii)and(iv).
Thecomplementary-slacknessconditionsoftheprimalproblemhaveafundamentaleconomicinterpre-
tation. Iftheshadowpriceoftheithresource(constraint)isstrictlypositiveintheoptimalsolution
ˆ
y
i
>
0,
thenweshouldrequirethatallofthisresourcebeconsumedbytheoptimalprogram;thatis,
n
j
=
1
a
ij
ˆ
x
j
=
b
i
.
If,ontheotherhand,theithresourceisnotfullyused;thatis,
n
j
=
1
a
ij
ˆ
x
j
<
b
i
,
thenitsshadowpriceshouldbezero,
ˆ
y
i
=
0.
Thecomplementary-slacknessconditionsofthedualproblemaremerelytheoptimalityconditionsfor
thesimplexmethod,wherethereducedcost
c
j
associatedwithanyvariablemustbenonpositiveandisgiven
by
c
j
=
c
j
m
i
=
1
a
ij
ˆ
y
i
0
(
j
=
1
,
2
,...,
n
).
If
ˆ
x
j
>
0,then
ˆ
x
j
mustbeabasicvariableanditsreducedcostisdefinedtobezero.Thus,
c
j
=
m
i
=
1
a
ij
ˆ
y
i
.
4.6
TheDualSimplexMethod
147
If,ontheotherhand,
c
j
m
i
=
1
a
ij
ˆ
y
i
<
0
,
then
ˆ
x
j
mustbenonbasicandsetequaltozerointheoptimalsolution;
ˆ
x
j
=
0.
Wehaveshownthatthestrongdualitypropertyimpliesthatthecomplementary-slacknessconditions
mustholdforboththeprimalanddualproblems. Theconverseofthisalsoistrue. Ifthecomplementary-
slacknessconditionsholdforbothproblems,thenthestrongdualitypropertyholds.Toseethis,let
ˆ
x
j
,
j
=
1
,
2
,...,
n,and
ˆ
y
i
,
i
=
1
,
2
,...,
m,befeasiblesolutionstotheprimalanddualproblems,respectively.The
complementary-slacknessconditions(i)and(ii)fortheprimalproblemimply:
m
i
=
1
n
j
=
1
a
ij
ˆ
x
j
b
i
ˆ
y
i
=
0
,
whilethecomplementary-slacknessconditions(iii)and(iv)forthedualproblemimply:
n
j
=
1
m
i
=
1
a
ij
ˆ
y
i
c
j
ˆ
x
j
=
0
.
Thesetwoequationstogetherimply:
n
j
=
1
c
j
ˆ
x
j
=
m
i
=
1
n
j
=
1
a
ij
ˆ
x
j
ˆ
y
i
=
m
i
=
1
b
i
ˆ
y
i
,
andhencethevaluesoftheprimalanddualobjectivefunctionsareequal. Sincethesesolutionsarefeasible
totheprimalanddualproblemsrespectively,theoptimalitypropertyimpliesthatthesesolutionsareoptimal
totheprimalanddualproblems. Wehave,inessence,shownthatthecomplementary-slacknessconditions
holdingforboththeprimalanddualproblemsisequivalenttothestrongdualityproperty. Forthisreason,
thecomplementary-slacknessconditionsareoftenreferredtoastheoptimalityconditions.
OptimalityConditions. If
ˆ
x
j
,
j
=
1
,
2
,...,
n,and
ˆ
y
i
,
i
=
1
,
2
,...,
m,arefeasiblesolutionstothe
primalanddualproblems,respectively,thentheyareoptimalsolutionstotheseproblemsif,andonlyif,
thecomplementary-slacknessconditionsholdforboththeprimalandthedualproblems.
4.6 THEDUALSIMPLEXMETHOD
Oneofthemostimportantimpactsofthegeneraldualitytheorypresentedintheprevioussectionhasbeen
oncomputationalproceduresforlinearprogramming.First,wehaveestablishedthatthedualcanbesolved
inplaceoftheprimalwheneverthereareadvantagestodoingso. Forexample,ifthenumberofconstraints
ofaproblemismuchgreaterthanthenumberofvariables,itisusuallywisetosolvethedualinsteadofthe
primalsincethesolutiontimeincreasesmuchmorerapidlywiththenumberofconstraintsintheproblem
thanwiththenumberofvariables. Second,newalgorithmshavebeendevelopedthattakeadvantageofthe
dualitytheoryinmoresubtleways. Inthissectionwepresentthedualsimplexmethod. . Wehavealready
seentheessenceofthedualsimplexmethodinSection3.5,onrighthand-sideranging,wherethevariable
transitionsattheboundariesofeachrangeareessentiallycomputedbythedualsimplexmethod.Further,in
Section3.8,onparametricprogrammingoftherighthandside,thedualsimplexmethodisthecornerstoneof
thecomputationalapproach.Inthissectionweformalizethegeneralalgorithm.
148
DualityinLinearProgramming
4.6
Recallthecanonicalformemployedinthesimplexmethod:
x
1
+
a
1
,
m
+
1
x
m
+
1
+···+
a
1
,
n
x
n
=
b
1
,
x
2
+
a
2
,
m
+
1
x
m
+
1
+···+
a
2
,
n
x
n
=
b
2
,
.
.
.
.
.
.
.
.
.
.
.
.
x
m
+
a
m
,
m
+
1
x
m
+
1
+···+
a
m
,
n
x
n
=
b
m
,
(−
z
)
+
c
m
+
1
x
m
+
1
+···+
c
n
x
n
=−
z
0
.
Theconditionsforx
1
,
x
2
,...,
x
m
toconstituteanoptimalbasisforamaximizationproblemare:
i
)
c
j
0
(
j
=
1
,
2
,...,
n
),
ii
)
b
i
0
(
i
=
1
,
2
,...,
m
).
Wecouldrefertocondition(i)asprimaloptimality(orequivalently,dualfeasibility)andcondition(ii)as
primalfeasibility. Intheprimalsimplexmethod,wemovefrombasicfeasiblesolutiontoadjacentbasic
feasiblesolution,increasing(notdecreasing)theobjectivefunctionateachiteration. Terminationoccurs
whentheprimaloptimalityconditionsaresatisfied.Alternatively,wecouldmaintainprimaloptimality(dual
feasibility)byimposing(i)andterminatingwhentheprimalfeasibilityconditions(ii)aresatisfied.Thislatter
procedureisreferredtoasthedualsimplexmethodandinfactresultsfromapplyingthesimplexmethod
tothedualproblem. InChapter3,onsensitivityanalysis,wegaveapreviewofthedualsimplexmethod
whenwedeterminedthevariabletoleavethebasisattheboundaryofarighthand-siderange. Infact,the
dualsimplexmethodismostusefulinapplicationswhenaproblemhasbeensolvedandasubsequentchange
ontherighthandsidemakestheoptimalsolutionnolongerprimalfeasible, asinthecaseofparametric
programmingoftherighthand-sidevalues.
Therulesofthedualsimplexmethodareidenticaltothoseoftheprimalsimplexalgorithm,exceptfor
theselectionofthevariabletoleaveandenterthebasis. Ateachiterationofthedualsimplexmethod,we
requirethat:
c
j
=
c
j
m
i
=
1
y
i
a
ij
0
;
andsincey
i
0fori
=
1
,
2
,...,
m,thesevariablesareadualfeasiblesolution. Further,ateachiteration
ofthedualsimplexmethod,themostnegative
b
i
ischosentodeterminethepivotrow,correspondingto
choosingthemostpositive
c
j
todeterminethepivotcolumnintheprimalsimplexmethod.
Priortogivingtheformalrulesofthedualsimplexmethod,wepresentasimpleexampletoillustratethe
essenceoftheprocedure. Considerthefollowingmaximizationproblemwithnonnegativevariablesgiven
inTableau3.Thisproblemisin‘‘dualcanonicalform"sincetheoptimalityconditionsaresatisfied,butthe
basicvariablesarenotyetnonnegative.
Table4.3
Basic
Current
variables
values
x
1
x
2
x
3
x
4
x
3
1
1
1
1
x
4
2
2
3
1
(−
z
)
0
3
1
Inthedualsimplexalgorithm,weareattemptingtomakeallvariablesnonnegative. Theprocedureis
theoppositeoftheprimalmethodinthatitfirstselectsthevariabletodropfromthebasisandthenthenew
variabletointroduceintothebasisinitsplace. Thevariabletodropisthebasicvariableassociatedwith
theconstraintwiththemostnegativerighthand-sidevalue;inthiscasex
4
. Nextwehavetodeterminethe
enteringvariable. Weselectfromonlythosenonbasicvariablesthathaveanegativecoefficientinthepivot
4.6
TheDualSimplexMethod
149
row,sincethen,afterpivoting,therighthandsidebecomespositive,thuseliminatingtheprimalinfeasibility
intheconstraint. Ifallcoefficientsarepositive,thentheprimalproblemisclearlyinfeasible,becausethe
sumofnonnegativetermscanneverequalthenegativerighthandside.
Inthisinstance,bothnonbasicvariablesx
1
andx
2
arecandidates.Pivotingwillsubtractsomemultiple,
sayt,ofthepivotrowcontainingx
4
fromtheobjectivefunction,togive:
(−
3
+
2t
)
x
1
+(−
1
+
3t
)
x
2
tx
4
z
=
2t
.
Sincewewishtomaintaintheoptimalityconditions, wewantthecoefficientofeachvariabletoremain
nonpositive,sothat:
3
+
2t
0
(
thatis
,
t
3
2
),
1
+
3t
0
(
thatis
,
t
1
3
),
t
0
(
thatis
,
t
0
).
Settingt
=
1
3
preservestheoptimalityconditionsandidentifiesthenewbasicvariablewithazerocoefficient
intheobjectivefunction,asrequiredtomaintainthedualcanonicalform.
Thesestepscanbesummarizedasfollows:thevariabletoleavethebasisischosenby:
b
r
=
Min
i
{
b
i
}=
Min
{−
1
,−
2
}=
b
2
.
Thevariabletoenterthebasisisdeterminedbythedualratiotest:
c
s
a
rs
=
Min
j
c
j
a
rj
a
rj
<
0
=
Min
3
2
,
1
3
=
c
2
a
22
.
Pivotinginx
2
inthesecondconstraintgivesthenewcanonicalforminTableau4.
Table4.4
Basic
Current
variables
values
x
1
x
2
x
3
x
4
x
3
1
3
1
3
1
1
3
x
2
2
3
2
3
1
1
3
(−
z
)
2
3
7
3
1
3
Clearly,x
3
istheleavingvariablesince
b
1
=−
1
3
istheonlynegativerighthand-sidecoefficient;and x
4
is
theenteringvariablesince
c
4
/
a
14
istheminimumdualratiointhefirstrow.Afterpivoting,thenewcanonical
formisgiveninTableau5
Table4.5
Basic
Current
variables
values
x
1
x
2
x
3
x
4
x
4
1
1
3
1
x
2
1
1
1
1
(−
z
)
1
2
1
Since
b
i
0fori
=
1
,
2,and
c
j
0forj
=
1
,
2
,...,
4,wehavetheoptimalsolution.
Followingisaformalstatementoftheprocedure. Theproofofitisanalogoustothatoftheprimal
simplexmethodandisomitted.
Documents you may be interested
Documents you may be interested