pdfbox c# port : Bookmarks pdf Library software component asp.net winforms html mvc AMP-Chapter-040-part511

DualityinLinearProgramming
4
Intheprecedingchapteronsensitivityanalysis,wesawthattheshadow-priceinterpretationoftheoptimal
simplexmultipliersisaveryusefulconcept. First,theseshadowpricesgiveusdirectlythemarginalworth
ofanadditionalunitofanyoftheresources. Second,whenanactivityis‘‘pricedout’’usingtheseshadow
prices,theopportunitycostofallocatingresourcestothatactivityrelativetootheractivitiesisdetermined.
Dualityinlinearprogrammingisessentiallyaunifyingtheorythatdevelopstherelationshipsbetweena
givenlinearprogramandanotherrelatedlinearprogramstatedintermsofvariableswiththisshadow-price
interpretation.Theimportanceofdualityistwofold.First,fullyunderstandingtheshadow-priceinterpretation
oftheoptimalsimplexmultiplierscanproveveryusefulinunderstandingtheimplicationsofaparticular
linear-programmingmodel.Second,itisoftenpossibletosolvetherelatedlinearprogramwiththeshadow
pricesasthevariablesinplaceof,orinconjunctionwith,theoriginallinearprogram,therebytakingadvantage
ofsomecomputationalefficiencies. Theimportanceofdualityforcomputationalprocedureswillbecome
moreapparentinlaterchaptersonnetwork-flowproblemsandlarge-scalesystems.
4.1 APREVIEWOFDUALITY
Wecanmotivateourdiscussionofdualityinlinearprogrammingbyconsideringagainthesimpleexample
giveninChapter2involvingthefirmproducingthreetypesofautomobiletrailers. Recallthatthedecision
variablesare:
x
1
=numberofflat-bedtrailersproducedpermonth,
x
2
=numberofeconomytrailersproducedpermonth,
x
3
=numberofluxurytrailersproducedpermonth.
Theconstrainingresourcesoftheproductionoperationarethemetalworkingandwoodworkingcapacities
measuredindayspermonth.Thelinearprogramtomaximizecontributiontothefirm’soverhead(inhundreds
ofdollars)is:
Maximizez
=
6x
1
+
14x
2
+
13x
3
,
subjectto:
1
2
x
1
+
2x
2
+
x
3
24
,
x
1
+
2x
2
+
4x
3
60
,
(1)
x
1
0
,
x
2
0
,
x
3
0
.
Afteraddingslackvariables,theinitialtableauisstatedincanonicalforminTableau1.
InChapter2,theexamplewassolvedindetailbythesimplexmethod,resultinginthefinaltableau,
repeatedhereasTableau2.
130
Bookmarks pdf - 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
auto bookmark pdf; pdf bookmarks
Bookmarks pdf - 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
bookmark pdf acrobat; how to bookmark a pdf page
4.1
APreviewofDuality
131
Tableau1
Basic
Current
variables
values
x
1
x
2
x
3
x
4
x
5
x
4
24
1
2
2
1
1
x
5
60
1
2
4
1
(−
z
)
0
6
14
13
Tableau2
Basic
Current
variables
values
x
1
x
2
x
3
x
4
x
5
x
1
36
1
6
4
1
x
3
6
1
1
1
1
2
(−
z
)
294
9
11
1
2
AswesawinChapter3,theshadowprices, y
1
formetalworkingcapacityand y
2
forwoodworking
capacity,canbedeterminedfromthefinaltableauasthenegativeofthereducedcostsassociatedwiththe
slackvariablesx
4
andx
5
.Thustheseshadowpricesarey
1
=
11andy
2
=
1
2
,respectively.
Wecaninterprettheshadowpricesintheusualway.Oneadditionaldayofmetalworkingcapacityisworth
$1100,whileoneadditionaldayofwoodworkingcapacityisworthonly$50.Thesevaluescanbeviewedas
thebreakevenrentsthatthefirmcouldpayperdayforadditionalcapacityofeachtype.Ifadditionalcapacity
couldberentedforlessthanitscorrespondingshadowprice,itwouldbeprofitabletoexpandcapacityin
thisway.Hence,inallocatingthescarceresourcestotheproductionactivities,wehavedeterminedshadow
pricesfortheresources,whicharethevaluesimputedtotheseresourcesatthemargin.
Letusexaminesomeoftheeconomicpropertiesoftheshadowpricesassociatedwiththeresources.
Recall,fromChapter3,Eq.(11),thatthereducedcostsaregivenintermsoftheshadowpricesasfollows:
c
j
=
c
j
m
i
=
1
a
ij
y
i
(
j
=
1
,
2
,...,
n
).
Sincea
ij
istheamountofresourceiusedperunitofactivity j,andy
i
istheimputedvalueofthatresource,
theterm
m
i
=
1
a
ij
y
i
isthetotalvalueoftheresourcesusedperunitofactivity j. Itisthusthemarginalresourcecostforusing
thatactivity.Ifwethinkoftheobjectivecoefficients c
j
asbeingmarginalrevenues,thereducedcosts
c
j
are
simplynetmarginalrevenues(i.e.,marginalrevenueminusmarginalcost).
Forthebasicvariablesx
1
andx
3
,thereducedcostsarezero,
c
1
=
6
11
(
1
2
)−
1
2
(
1
)=
0
,
c
3
=
13
11
(
1
)−
1
2
(
4
)=
0
.
Thevaluesimputedtotheresourcesaresuchthatthenetmarginalrevenueiszeroonthoseactivitiesoperated
atapositivelevel.Thatis,foranyproductionactivityatpositivelevel,marginalrevenuemustequalmarginal
cost.
VB.NET PDF File Compress Library: Compress reduce PDF size in vb.
document file. Remove bookmarks, annotations, watermark, page labels and article threads from PDF while compressing. Also a preview
add bookmarks to pdf file; creating bookmarks in pdf from word
C# PDF File Split Library: Split, seperate PDF into multiple files
Split PDF file by top level bookmarks. The following C# codes explain how to split a PDF file into multiple ones by PDF bookmarks or outlines.
add bookmarks to pdf online; create bookmarks pdf file
132
DualityinLinearProgramming
4.1
Thesituationismuchthesameforthenonbasicvariablesx
2
,
x
4
,andx
5
,withcorrespondingreduced
costs:
c
2
=
14
11
(
2
)−
1
2
(
2
)=−
9
,
c
4
=
0
11
(
1
)−
1
2
(
0
)=−
11
,
c
5
=
0
11
(
0
)−
1
2
(
1
)=−
1
2
.
Thereducedcostsforallnonbasicvariablesarenegative. Theinterpretationisthat,forthevaluesimputed
tothescarceresources,marginalrevenueislessthanmarginalcostfortheseactivities,sotheyshouldnotbe
pursued.Inthecaseofx
2
,thissimplymeansthatweshouldnotproduceanyeconomytrailers.Thecasesof
x
4
andx
5
aresomewhatdifferent,sinceslackvariablesrepresentunusedcapacity.Sincethemarginalrevenue
ofaslackactivityiszero,itsreducedcostequalsminusitsmarginalcost,whichisjusttheshadowpriceof
thecorrespondingcapacityconstraint,aswehaveseenbefore.
Theaboveconditionsinterpretedforthereducedcostsofthedecisionvariablesarethefamiliaroptimality
conditionsofthesimplexmethod.Economicallywecanseewhytheymusthold.Ifmarginalrevenueexceeds
marginalcostforanyactivity,thenthefirmwouldimproveitscontributiontooverheadby increasingthat
activity.If,however,marginalcostexceedsmarginalrevenueforanactivityoperatedatapositivelevel,then
thefirmwouldincreaseitscontributionby decreasingthatactivity. . Ineithercase,anewsolutioncouldbe
foundthatisanimprovementonthecurrentsolution.Finally,aswehaveseeninChapter3,thosenonbasic
variableswithzeroreducedcostsrepresentpossiblealternativeoptimalsolutions.
Untilnowwehaveusedtheshadowpricesmainlytoimputethemarginalresourcecostassociatedwith
eachactivity.Wethenselectedthebestactivitiesforthefirmtopursuebycomparingthemarginalrevenueof
anactivitywithitsmarginalresourcecost.Inthiscase,theshadowpricesareinterpretedastheopportunity
costsassociatedwithconsumingthefirm’sresources. Ifwenowvaluethefirm’stotalresourcesatthese
prices,wefindtheirvalue,
v=
11
(
24
)+
1
2
(
60
)=
294
,
isexactlyequaltotheoptimalvalueoftheobjectivefunctionofthefirm’sdecisionproblem.Theimplication
ofthisvaluationschemeisthatthefirm’smetalworkingandwoodworkingcapacitieshaveanimputedworth
of$264and$30,respectively. Essentiallythen,theshadowpricesconstituteaninternalpricingsystemfor
thefirm’sresourcesthat:
1. permitsthefirmtoselectwhichactivitytopursuebyconsideringonlythemarginalprofitabilityofits
activities;and
2. allocatesthecontributionofthefirmtoitsresourcesatthemargin.
Supposethatweconsidertryingtodeterminedirectlytheshadowpricesthatsatisfytheseconditions,
withoutsolvingthefirm’sproduction-decisionproblem. Theshadowpricesmustsatisfytherequirement
thatmarginalrevenuebelessthanorequaltomarginalcostforallactivities. Further,theymustbenon-
negativesincetheyareassociatedwithless-than-or-equal-toconstraintsinamaximizationdecisionproblem.
Therefore,theunknownshadowpricesy
1
onmetalworkingcapacityandy
2
onwoodworkingcapacitymust
satisfy:
1
2
y
1
+
y
2
6
,
2y
1
+
2y
2
14
,
y
1
+
4y
2
13
,
y
1
0
,
y
2
0
.
Theseconstraintsrequirethattheshadowpricesbechosensothatthenetmarginalrevenueforeachactivity
isnonpositive. Ifthiswerenotthecase,animprovementinthefirm’stotalcontributioncouldbemadeby
changingthechoiceofproductionactivities.
VB.NET PDF File Split Library: Split, seperate PDF into multiple
Demo Code in VB.NET. The following VB.NET codes explain how to split a PDF file into multiple ones by PDF bookmarks or outlines.
adding bookmarks to pdf document; creating bookmarks in pdf documents
C# PDF File Compress Library: Compress reduce PDF size in C#.net
NET framework. Remove bookmarks, annotations, watermark, page labels and article threads from PDF while compressing. C# class demo
adding bookmarks to pdf reader; excel print to pdf with bookmarks
4.1
APreviewofDuality
133
Recallthattheshadowpriceswereinterpretedasbreakevenrentsforcapacityatthemargin.Imaginefor
themomentthatthefirmdoesnotownitsproductivecapacitybuthastorentit.Nowconsideranyvaluesfor
theshadowprices,orrentalrates,thatsatisfytheaboveconstraints,sayy
1
=
4andy
2
=
4.Thetotalworth
oftherentedcapacitiesevaluatedattheseshadowpricesis
v=
24
(
4
)+
60
(
4
)=
336,whichisgreaterthan
themaximumcontributionofthefirm.Sincetheimputedvalueofthefirm’sresourcesisderivedsolelyfrom
allocatingthefirm’scontributiontoitsresources,
v=
336istoohighatotalworthtoimputetothefirm’s
resources.Thefirmclearlycouldnotbreakevenifithadtorentitsproductioncapacityatsuchrates.
Ifwethinkofthefirmasrentingallofitsresources,thensurelyitshouldtrytorentthematleastcost.
Thissuggeststhatwemightdeterminetheappropriatevaluesoftheshadowpricesbyminimizingthetotal
rentalcostoftheresources,subjecttotheaboveconstraints.Thatis,solvethefollowinglinearprogram:
Minimize
v=
24y
1
+
60y
2
,
subjectto:
1
2
y
1
+
y
2
6
,
2y
1
+
2y
2
14
,
y
1
+
4y
2
13
,
(2)
y
1
0
,
y
2
0
.
Ifwesolvethislinearprogrambythesimplexmethod,theresultingoptimalsolutionisy
1
=
11,y
2
=
1
2
,
and
v =
294. Theseareexactlythedesiredvaluesoftheshadowprices,andthevalueof
v
reflectsthat
thefirm’scontributionisfullyallocatedtoitsresources. Essentially,thelinearprogram(2),intermsofthe
shadowprices,determinesrentsfortheresourcesthatwouldallowthefirmtobreakeven,inthesensethatits
totalcontributionwouldexactlyequalthetotalrentalvalueofitsresources.However,thefirminfactowns
itsresources,andsotheshadowpricesareinterpretedasthebreakevenratesforrentingadditionalcapacity.
Thus,wehaveobservedthat,bysolving(2),wecandeterminetheshadowpricesof(1)directly.Problem
(2)iscalledthedualofProblem(1).SinceProblem(2)hasaname,itishelpfultohaveagenericnamefor
theoriginallinearprogram.Problem(1)hascometobecalledtheprimal.
Insolvinganylinearprogrambythesimplexmethod,wealsodeterminetheshadowpricesassociated
withtheconstraints. Insolving(2),theshadowpricesassociatedwithitsconstraintsareu
1
=
36
,
u
2
=
0,
andu
3
=
6. However,theseshadowpricesfortheconstraintsof(2)areexactlytheoptimalvaluesofthe
decisionvariablesofthefirm’sallocationproblem. Hence,insolvingthedual(2)bythesimplexmethod,
weapparentlyhavesolvedtheprimal(1)aswell.Aswewillseelater,thiswillalwaysbethecasesince‘‘the
dualofthedualistheprimal.’’Thisisanimportantresultsinceitimpliesthatthedualmaybesolvedinstead
oftheprimalwhenevertherearecomputationaladvantages.
Letusfurtheremphasizetheimplicationsofsolvingtheseproblemsbythesimplexmethod. Theopti-
malityconditionsofthesimplexmethodrequirethatthereducedcostsofbasicvariablesbezero.Hence,
if
ˆ
x
1
>
0
,
then
c
1
=
6
1
2
ˆ
y
1
− ˆ
y
2
=
0
;
if
ˆ
x
3
>
0
,
then
c
3
=
13
− ˆ
y
1
4
ˆ
y
2
=
0
.
Theseequationsstatethat,ifadecisionvariableoftheprimalispositive,thenthecorrespondingconstraint
inthedualmustholdwithequality.Further,theoptimalityconditionsrequirethatthenonbasicvariablesbe
zero(atleastforthosevariableswithnegativereducedcosts);thatis,
if
c
2
=
14
2
ˆ
y
1
2
ˆ
y
2
<
0
,
then
ˆ
x
2
=
0
.
Theseobservationsareoftenreferredtoascomplementaryslacknessconditionssince,ifavariableispositive,
itscorresponding(complementary)dualconstraintholdswithequalitywhile,ifadualconstraintholdswith
strictinequality,thenthecorresponding(complementary)primalvariablemustbezero.
.NET PDF SDK - Description of All PDF Processing Control Feastures
Fully featured PDF Viewer in HTML5; Outstanding rendering of PDF documents; Full page navigation, zooming & rotation; Outlines, bookmarks, & thumbnail display;
how to bookmark a pdf file; export excel to pdf with bookmarks
XDoc.Word for .NET, Advanced .NET Word Processing Features
& rotation; Outlines, bookmarks, & thumbnail display; Integrated annotation; More about Web Viewer ▶. Conversion. Word Create. Create Word from PDF; Create Word
bookmark pdf in preview; bookmarks in pdf files
134
DualityinLinearProgramming
4.2
TheseresultsareanalogoustowhatwehaveseeninChapter3. Ifsomeshadowpriceispositive,then
thecorrespondingconstraintmustholdwithequality;thatis,
if
ˆ
y
1
>
0
,
then
1
2
ˆ
x
1
+
2
ˆ
x
2
+ ˆ
x
3
=
24
;
if
ˆ
y
2
>
0
,
then
ˆ
x
1
+
2
ˆ
x
2
+
4
ˆ
x
3
=
60
.
Further,ifaconstraintoftheprimalisnotbinding,thenitscorrespondingshadowpricemustbezero. In
oursimpleexampletheredonothappentobeanynonbindingconstraints,otherthantheimplicitnonnega-
tivityconstraints.However,thereducedcostshavetheinterpretationofshadowpricesonthenonnegativity
constraints,andweseethatthereducedcostsofx
1
andx
3
areappropriatelyzero.
Inthis chapterwedevelop these ideas furtherbypresentingthe generaltheoryofduality inlinear
programming.
4.2 DEFINITIONOFTHEDUALPROBLEM
Thedualityprincipleswehaveillustratedintheprevioussectionscanbestatedformallyingeneralterms.
Lettheprimalproblembe:
Primal
Maximizez
=
n
j
=
1
c
j
x
j
,
subjectto:
n
j
=
1
a
ij
x
j
b
i
(
i
=
1
,
2
,...,
m
),
(3)
x
j
0
(
j
=
1
,
2
,...,
n
).
Associatedwiththisprimalproblemthereisacorrespondingdualproblemgivenby:
Dual
Minimize
v=
m
i
=
1
b
i
y
i
,
subjectto:
m
i
=
1
a
ij
y
i
c
j
(
j
=
1
,
2
,...,
n
),
(4)
y
i
0
(
i
=
1
,
2
,...,
m
).
TheseprimalanddualrelationshipscanbeconvenientlysummarizedasinFig.4.1.
Withoutthevariablesy
1
,
y
2
,...,
y
m
,
thistableauisessentiallythetableauformutilizedinChapters2
and3foralinearprogram.Thefirst mrowsofthetableaucorrespondtotheconstraintsoftheprimalproblem,
whilethelastrowcorrespondstotheobjectivefunctionoftheprimalproblem.Ifthevariablesx
1
,
x
2
,...
x
n
,
areignored,thecolumnsofthetableauhaveasimilarinterpretationforthedualproblem.Thefirst ncolumns
ofthetableaucorrespondtotheconstraintsofthedualproblem,whilethelastcolumncorrespondstothe
objectivefunctionofthedualproblem.Notethatthereisonedualvariableforeachexplicitconstraintinthe
primal,andoneprimalvariableforeachexplicitconstraintinthedual.Moreover,thedualconstraintsarethe
familiaroptimalityconditionof‘‘pricingout’’acolumn. Theystatethat,atoptimality,noactivityshould
appeartobeprofitablefromthestandpointofitsreducedcost;thatis,
c
j
=
c
j
m
i
=
1
a
ij
y
i
0
.
XDoc.Excel for .NET, Comprehensive .NET Excel Imaging Features
zooming & rotation; Outlines, bookmarks, & thumbnail display; Integrated annotation; More about Web Viewer ▶. Excel Convert. Convert Excel to PDF; Convert Excel
acrobat split pdf bookmark; excel pdf bookmarks
XDoc.PowerPoint for .NET, All Mature Features Introductions
& rotation; Outlines, bookmarks, & thumbnail display; Integrated annotation; More about Web Viewer ▶. PowerPoint Convert. Convert PowerPoint to PDF; Convert
how to create bookmark in pdf automatically; adding bookmarks in pdf
4.2
DefinitionoftheDualProblem
135
Figure4.1 Primalanddualrelationships.
Toillustratesomeoftheserelationships,letusconsideranexampleformulatedinChapter1.Recallthe
portfolio-selectionproblem,wherethedecisionvariablesaretheamountstoinvestineachsecuritytype:
Maximizez
=
0
.
043x
A
+
0
.
027x
B
+
0
.
025x
C
+
0
.
022x
D
+
0
.
045x
E
,
subjectto:
Cash
x
A
+
x
B
+
x
C
+
x
D
+
x
E
10,
Governments
x
B
+
x
C
+
x
D
4
,
Quality
0
.
6x
A
+
0
.
6x
B
0
.
4x
C
0
.
4x
D
+
3
.
6x
E
0,
Maturity
4x
A
+
10x
B
x
C
2x
D
3x
E
0,
x
A
0
,
x
B
0
,
x
C
0
,
x
D
0
,
x
E
0
.
Thedualofthisproblemcanbefoundeasilybyconvertingittothestandardprimalformulationgivenin(3).
Thisisaccomplishedbymultiplyingthesecondconstraintby
1,thuschangingthe‘‘greaterthanorequal
to’’constrainttoa‘‘lessthanorequalto’’constraint.Theresultingprimalproblembecomes:
Maximizez
=
0
.
043x
A
+
0
.
027x
B
+
0
.
025x
C
+
0
.
022x
D
+
0
.
045x
E
,
subjectto:
x
A
+
x
B
+
x
C
+
x
D
+
x
E
10
,
x
B
x
C
x
D
≤ −
4
,
0
.
6x
A
+
0
.
6x
B
0
.
4x
C
0
.
4x
D
+
3
.
6x
E
0
,
4x
A
+
10x
B
x
C
2x
D
3x
E
0
,
x
A
0
,
x
B
0
,
x
C
0
,
x
D
0
,
x
E
0
.
Accordingtoexpression(4),thecorrespondingdualproblemis:
Minimize
v=
10y
1
4y
2
,
subjectto:
y
1
+
0
.
6y
3
+
4y
4
0
.
043
,
y
1
y
2
+
0
.
6y
3
+
10y
4
0
.
027
,
y
1
y
2
0
.
4y
3
y
4
0
.
025
,
y
1
y
2
0
.
4y
3
2y
4
0
.
022
,
y
1
+
3
.
6y
3
3y
4
0
.
045
,
136
DualityinLinearProgramming
4.2
y
1
0
,
y
2
0
,
y
3
0
,
y
4
0
.
Byapplyingthesimplexmethod,theoptimalsolutiontobothprimalanddualproblemscanbefoundtobe:
Primal:x
A
=
3
.
36
,
x
B
=
0
,
x
C
=
0
,
x
D
=
6
.
48,
x
E
=
0
.
16
,
andz
=
0
.
294;
Dual: y
1
=
0
.
0294
,
y
2
=
0
,
y
3
=
0
.
00636,
y
4
=
0
.
00244
,
and
v=
0
.
294
.
Aswehaveseenbefore,theoptimalvaluesoftheobjectivefunctionsoftheprimalanddualsolutions
areequal. Furthermore,anoptimaldualvariableisnonzeroonlyifitsassociatedconstraintintheprimalis
binding.Thisshouldbeintuitivelyclear,sincetheoptimaldualvariablesaretheshadowpricesassociatedwith
theconstraints. Theseshadowpricescanbeinterpretedasvaluesimputedtothescarceresources(binding
constraints),sothatthevalueoftheseresourcesequalsthevalueoftheprimalobjectivefunction.
TofurtherdevelopthattheoptimaldualvariablesaretheshadowpricesdiscussedinChapter3,wenote
thattheysatisfytheoptimalityconditionsofthesimplexmethod.Inthefinaltableauofthesimplexmethod,
thereducedcostsofthebasicvariablesmustbezero.Asanexample,considerbasicvariablex
A
.Thereduced
costofx
A
inthefinaltableaucanbedeterminedasfollows:
c
A
=
c
A
5
i
=
1
a
iA
y
i
=
0
.
043
1
(
0
.
0294
)−
0
(
0
)−
0
.
6
(
0
.
00636
)−
4
(
0
.
00244
)=
0
.
Fornonbasicvariables,thereducedcostinthefinaltableaumustbenonpositiveinordertoensurethatno
improvementscanbemade.Considernonbasicvariablex
B
,whosereducedcostisdeterminedasfollows:
c
B
=
c
B
5
i
=
1
a
iB
y
i
=
0
.
027
1
(
0
.
0294
)−
1
(
0
)−
0
.
6
(
0
.
00636
)−
10
(
0
.
00244
)=−
0
.
0306
.
Theremainingbasicandnonbasicvariablesalsosatisfytheseoptimalityconditionsforthesimplexmethod.
Therefore,theoptimaldualvariablesmustbetheshadowpricesassociatedwithanoptimalsolution.
Sinceanylinearprogramcanbeputintheformof(3)bymakingsimpletransformationssimilartothose
usedinthisexample,thenanylinearprogrammusthaveaduallinearprogram.Infact,sincethedualproblem
(4)isalinearprogram,itmustalsohaveadual.Forcompleteness,onewouldhopethatthedualofthedual
istheprimal(3),whichisindeedthecase. Toshowthisweneedonlychangethedual(4)intotheformof
(3)andapplythedefinitionofthedualproblem.Thedualmaybereformulatedasamaximizationproblem
withless-than-or-equal-toconstraints,asfollows:
Maximize
v
=
m
i
=
1
b
i
y
i
,
subjectto:
m
i
=
1
a
ij
y
i
≤−
c
j
(
j
=
1
,
2
,...,
n
),
(5)
y
i
0
(
i
=
1
,
2
,...,
m
).
Excelspreadsheetavailableathttp://web.mit.edu/15.053/www/Sect4.2_Primal_Dual.xls
4.3
FindingtheDualinGeneral
137
Applyingthedefinitionofthedualproblemandlettingthedualvariablesbe x
j
,
j
=
1
,
2
,...,
n,wehave
Minimizez
=
n
j
=
1
c
j
x
j
,
subjectto:
n
j
=
1
a
ij
x
j
≥−
b
i
(
i
=
1
,
2
,...,
m
),
(6)
x
j
0
(
j
=
1
,
2
,...,
n
),
which,bymultiplyingtheconstraintsbyminusoneandconvertingtheobjectivefunctiontomaximization,
isclearlyequivalenttotheprimalproblem.Thus,thedualofthedualistheprimal.
4.3 FINDINGTHEDUALINGENERAL
Veryoftenlinearprogramsareencounteredinequalityformwithnonnegativevariables. Forexample,the
canonicalform,whichisusedforcomputingasolutionbythesimplexmethod,isinequalityform. Itisof
interest,then,tofindthedualoftheequalityform:
Maximizez
=
n
j
=
1
c
j
x
j
,
subjectto:
n
j
=
1
a
ij
x
j
=
b
i
(
i
=
1
,
2
,...,
m
),
(7)
x
j
0
(
j
=
1
,
2
,...,
n
).
Aprobleminequalityformcanbetransformedintoinequalityformbyreplacingeachequationbytwo
inequalities.Formulation(7)canberewrittenas
Maximizez
=
n
j
=
1
c
j
x
j
,
subjectto:
n
j
=
1
a
ij
x
j
b
i
n
j
=
1
a
ij
x
j
≤−
b
i
(
i
=
1
,
2
,...,
m
),
x
j
0
(
j
=
1
,
2
,...,
n
).
Thedualoftheequalityformcanthenbefoundbyapplyingthedefinitionofthedualtothisproblem.Letting
y
+i
andy
i
(
i
=
1
,
2
,...,
m
)
bethedualvariablesassociatedwiththefirst mandsecondmconstraints,
respectively,fromexpression(4),wefindthedualtobe:
Minimize
v=
m
i
=
1
b
i
y
+i
+
m
i
=
1
b
i
y
i
,
subjectto:
m
i
=
1
a
ij
y
+i
+
m
i
=
1
a
ij
y
i
c
j
(
j
=
1
,
2
,...,
n
),
138
DualityinLinearProgramming
4.3
y
+i
0
,
y
i
0
(
i
=
1
,
2
,...,
m
).
Collectingterms,wehave:
Minimize
v=
m
i
=
1
b
i
(
y
+i
y
i
),
subjectto:
m
i
=
1
a
ij
(
y
+i
y
i
)≥
c
j
(
j
=
1
,
2
,...,
n
),
y
+i
0
,
y
i
0
(
i
=
1
,
2
,...,
m
).
Lettingy
i
=
y
+i
y
i
,andnotingthaty
i
isunrestrictedinsign,givesusthedualoftheequalityform(7):
Minimize
v=
m
i
=
1
b
i
y
i
,
subjectto:
m
i
=
1
a
ij
y
i
c
j
(
j
=
1
,
2
,...,
n
),
(8)
y
i
unrestricted
(
i
=
1
,
2
,...,
m
).
Notethatthedualvariablesassociatedwithequalityconstraintsareunrestricted.
Thereareanumberofrelationshipsbetweenprimalanddual,dependinguponwhethertheprimalproblem
isamaximizationoraminimizationproblemanduponthetypesofconstraintsandrestrictionsonthevariables.
Toillustratesomeoftheserelationships,letusconsiderageneralmaximizationproblemasfollows:
Maximizez
=
n
j
=
1
c
j
x
j
,
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

),
(9)
n
j
=
1
a
ij
x
j
=
b
i
(
i
=
m

+
1
,
m

+
2
,...,
m
),
x
j
0
(
j
=
1
,
2
,...,
n
).
Wecanchangethegeneralprimalproblemtoequalityformbyaddingtheappropriateslackandsurplus
variables,asfollows:
Maximizez
=
n
j
=
1
c
j
x
j
,
4.3
FindingtheDualinGeneral
139
subjectto:
n
j
=
1
a
ij
x
j
+
x
n
+
i
=
b
i
(
i
=
1
,
2
,...,
m
),
n
j
=
1
a
ij
x
j
x
n
+
i
=
b
i
(
i
=
m
+
1
,
m
+
2
,...,
m

),
n
j
=
1
a
ij
x
j
=
b
i
(
i
=
m

+
1
,
m

+
2
,...,
m
),
x
j
0
(
j
=
1
,
2
,...,
n
+
m

).
Lettingy
i
,
y
i
,andy

i
bedualvariablesassociatedrespectivelywiththethreesetsofequations,thedualof
(9)isthen
Minimize
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
(10)
y
i
0
,
y
i
0
,
wherey

i
isunrestrictedinsignandthelastinequalitycouldbewritteny
i
0. Thus,iftheprimalproblem
isamaximizationproblem,thedualvariablesassociatedwiththeless-than-or-equal-toconstraintsarenon-
negative,thedualvariablesassociatedwiththegreater-than-or-equal-toconstraintsarenonpositive,andthe
dualvariablesassociatedwiththeequalityconstraintsareunrestrictedinsign.
Theseconventionsreflecttheinterpretationofthedualvariablesasshadowpricesoftheprimalproblem.
Aless-than-or-equal-toconstraint, normallyrepresentingascarceresource, hasapositiveshadowprice,
since theexpansionofthatresourcegeneratesadditionalprofits. . Onthe e otherhand, agreater-than-or-
equal-toconstraintusuallyrepresentsanexternalrequirement(e.g.,demandforagivencommodity).Ifthat
requirementincreases, theproblembecomesmoreconstrained;thisproducesadecreaseintheobjective
functionandthusthecorrespondingconstrainthasanegativeshadowprice.Finally,changesintherighthand
sideofanequalityconstraintmightproduceeithernegativeorpositivechangesinthevalueoftheobjective
function.Thisexplainstheunrestrictednatureofthecorrespondingdualvariable.
Letusnowinvestigatethedualityrelationshipswhentheprimalproblemiscastinminimization,rather
thanmaximizationform:
Minimizez
=
n
j
=
1
c
j
x
j
,
Documents you may be interested
Documents you may be interested