pdfbox c# port : Add bookmark pdf file application Library tool html asp.net winforms online AMP-Chapter-042-part513

150
DualityinLinearProgramming
4.7
DualSimplexAlgorithm
STEP(0)Theproblemisinitiallyincanonicalformandall
c
j
0.
STEP(1)If
b
i
0
,
i
=
1
,
2
,...,
m,thenstop,weareoptimal.Ifwecontinue,then
thereexistssome
b
i
<
0.
STEP(2)Choosetherowtopivotin(i.e.,variabletodropfromthebasis)by:
b
r
=
Min
i
b
i
|
b
i
<
0
.
If
a
rj
0
,
j
=
1
,
2
,...,
n,thenstop;theprimalproblemisinfeasible(dual
unbounded).Ifwecontinue,thenthereexists
a
rj
<
0forsomej
=
1
,
2
,...,
n.
STEP(3)Choosecolumnstoenterthebasisby:
c
s
a
rs
=
Min
j
c
j
a
rj
a
rj
<
0
.
STEP(4)Replacethebasicvariableinrowrwithvariablesandreestablishthecanonical
form(i.e.,pivotonthecoefficient
a
rs
).
STEP(5)GotoStep(1).
Step(3)isdesignedtomaintain
c
j
0ateachiteration,andStep(2)findsthemostpromisingcandidatefor
animprovementinfeasibility.
4.7 PRIMAL-DUALALGORITHMS
Therearemanyothervariantsofthesimplexmethod. Thusfarwehavediscussedonlytheprimalanddual
methods.Thereareobviousgeneralizationsthatcombinethesetwomethods.Algorithmsthatperformboth
primalanddualstepsarereferredtoasprimal-dualalgorithmsandthereareanumberofsuchalgorithms.We
presenthereonesimplealgorithmofthisformcalledtheparametricprimal-dual.Itismosteasilydiscussed
inanexample.
x
1
0
,
x
2
0
,
x
1
+
x
2
6
,
x
1
+
2x
2
≤−
1
2
,
x
1
3x
2
≤−
1
,
2x
1
+
3x
2
=
z
(
max
).
Theaboveexamplecaneasilybeputincanonicalformbyadditionofslackvariables. However,neither
primalfeasibilitynorprimaloptimalityconditionswillbesatisfied. Wewillarbitrarilyconsidertheabove
exampleasafunctionoftheparameter
θ
inTableau6.
Clearly,ifwechoose
θ
largeenough,thissystemofequationssatisfiestheprimalfeasibilityandprimal
optimalityconditions. Theideaoftheparametricprimal-dualalgorithmistochoose
θ
largeinitiallyso
thattheseconditionsaresatisfied,andattempttoreduce
θ
tozerothroughasequenceofpivotoperations.
Ifwestartwith
θ =
4andlet
θ
approachzero,primaloptimalityisviolatedwhen
θ <
3. Ifwewereto
reduce
θ
below3,theobjective-functioncoefficientof x
2
wouldbecomepositive. Thereforeweperforma
primalsimplexpivotbyintroducingx
2
intothebasis. Wedeterminethevariabletoleavethebasisbythe
minimum-ratioruleoftheprimalsimplexmethod:
b
r
a
rs
=
Min
i
b
i
a
is
a
is
>
0
=
6
1
,
2
1
2
2
=
b
2
a
22
.
x
4
leavesthebasisandthenewcanonicalformisthenshowninTableau7.
Add 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
bookmark pdf reader; how to bookmark a pdf file
Add 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
creating bookmarks in a pdf document; convert word pdf bookmarks
4.8
MathematicalEconomics
151
Tableau6
Basic
Current
variables
values
x
1
x
2
x
3
x
4
x
5
x
3
6
1
1
1
x
4
1
2
1
2
1
x
5
1
1
3
1
(−
z
)
0
2
(
3
−θ)
Tableau7
Basic
Current
variables
values
x
1
x
2
x
3
x
4
x
5
x
3
6
1
4
1
2
θ
3
2
1
1
2
x
2
1
4
+
1
2
θ
1
2
1
1
2
x
5
7
4
+
5
2
θ
1
2
3
2
1
(−
z
)
−(
3
−θ)(−
1
4
+
1
2
θ)
(−
1
2
1
2
θ)
(−
3
2
+
1
2
θ)
Theoptimalityconditionsaresatisfiedfor
7
10
≤θ ≤
3.Ifweweretoreduce
θ
below
7
10
,therighthand-
sidevalueofthethirdconstraintwouldbecomenegative. Therefore,weperformadualsimplexpivotby
droppingx
5
fromthebasis. Wedeterminethevariabletoenterthebasisbytherulesofthedualsimplex
method:
Min
j
c
j
a
3j
a
3j
<
0
=
1
2
+−
1
2
θ
1
2
=
c
1
a
31
.
AfterthepivotisperformedthenewcanonicalformisgiveninTableau8.
Tableau8
Basic
Current
variables
values
x
1
x
2
x
3
x
4
x
5
x
3
1
+
7
θ
1
4
3
x
2
3
2
2
θ
1
1
1
x
1
7
2
5
θ
1
3
2
(−
z
)
−(
3
−θ)
1
4
+
1
2
θ
(−
3
−θ)
(−
1
−θ)
+(
1
2
+
1
2
θ)(
7
2
5
θ)
Aswecontinuetodecrease
θ
tozero,theoptimalityconditionsremainsatisfied. Thustheoptimalfinal
tableauforthisexampleisgivenbysetting
θ
equaltozero.
Primal-dualalgorithmsareusefulwhensimultaneouschangesofbothrighthand-sideandcostcoefficients
areimposedonapreviousoptimalsolution,andanewoptimalsolutionistoberecovered.Whenparametric
programmingofboththeobjective-functioncoefficientsandtherighthand-sidevaluesisperformedsimulta-
neously,avariationofthisalgorithmisused.Thistypeofparametricprogrammingisusuallyreferredtoas
therimproblem.(SeeAppendixBforfurtherdetails.)
4.8 MATHEMATICALECONOMICS
As wehaveseeninthetwoprevious sections,dualitytheoryisimportantfordevelopingcomputational
proceduresthattakeadvantageoftherelationshipsbetweentheprimalanddualproblems.However,thereis
anotherlessobviousareathatalsohasbeenheavilyinfluencedbyduality,andthatismathematicaleconomics.
C# PDF Password Library: add, remove, edit PDF file password in C#
This example shows how to add PDF file password with access permission setting. passwordSetting.IsAssemble = true; // Add password to PDF file.
bookmark template pdf; create bookmarks in pdf from excel
VB.NET PDF File Split Library: Split, seperate PDF into multiple
Split PDF document by PDF bookmark and outlines in VB.NET. VB.NET PDF Splitting & Disassembling DLLs. Add necessary references: RasterEdge.Imaging.Basic.dll.
pdf bookmark; export pdf bookmarks to text
152
DualityinLinearProgramming
4.8
Inthebeginningofthischapter,wegaveapreviewofdualitythatinterpretedthedualvariablesasshadow
pricesimputedtothefirm’sresourcesbyallocatingtheprofit(contribution)ofthefirmtoitsresourcesat
themargin. Inaperfectlycompetitiveeconomy,itisassumedthat,ifafirmcouldmakeprofitsinexcess
ofthevalueofitsresources,thensomeotherfirmwouldenterthemarketwithalowerprice,thustending
toeliminatetheseexcessprofits. Thedualitytheoryoflinearprogramminghashadasignificantimpacton
mathematicaleconomicsthroughtheinterpretationofthedualastheprice-settingmechanisminaperfectly
competitiveeconomy.Inthissectionwewillbrieflysketchthisidea.
Supposethatafirmmayengageinany nproductionactivitiesthatconsumeand/orproducemresources
intheprocess. Letx
j
0bethelevelatwhichthe jthactivityisoperated,andletc
j
betherevenueper
unit(minusmeanscost)generatedfromengaginginthe jthactivity. . Further,leta
ij
betheamountofthe
ithresourceconsumed(minusmeansproduced)perunitlevelofoperationofthe jthactivity. Assumethat
thefirmstartswithapositionof b
i
unitsoftheithresourceandmaybuyorsellthisresourceataprice
y
i
0determinedbyanexternalmarket.Sincethefirmgeneratesrevenuesandincurscostsbyengagingin
productionactivitiesandbybuyingandsellingresources,itsprofitisgivenby:
n
j
=
1
c
j
x
j
+
m
i
=
1
y
i
b
i
n
j
=
1
a
ij
x
j
,
(19)
wherethesecondtermincludesrevenuesfromsellingexcessresourcesandcostsofbuyingadditionalre-
sources.
Notethatifb
i
>
n
j
=
1
a
ij
x
j
,thefirmsells b
i
n
j
=
1
a
ij
x
j
unitsofresourcesitothemarketplaceat
apricey
i
. If,however,b
i
<
n
j
=
1
a
ij
x
j
,thenthefirmbuys
n
j
=
1
a
ij
x
j
b
i
unitsofresourceifromthe
marketplaceatapricey
i
.
Nowassumethatthemarketmechanismforsettingpricesissuchthatittendstominimizetheprofitsof
thefirm,sincetheseprofitsareconstruedtobeattheexpenseofsomeoneelseinthemarket.Thatis,given
x
j
for j
=
1
,
2
,...,
n,themarketreactstominimize(19). Twoconsequencesimmediatelyfollow. . First,
consuminganyresourcethatneedstobepurchasedfromthemarketplace,thatis,
b
i
n
j
=
1
a
ij
x
j
<
0
,
isclearlyuneconomicalforthefirm,sincethemarketwilltendtosetthepriceoftheresourcearbitrarilyhigh
soastomakethefirm’sprofitsarbitrarilysmall(i.e.,thefirm’slossesarbitrarilylarge). Consequently,our
imaginaryfirmwillalwayschooseitsproductionactivitiessuchthat:
n
j
=
1
a
ij
x
j
b
i
(
i
=
1
,
2
,...,
m
).
Second,ifanyresourcewerenotcompletelyconsumedbythefirminitsownproductionandthereforebecame
availableforsaletothemarket,thatis,
b
i
n
j
=
1
a
ij
x
j
>
0
,
this‘‘malevolentmarket"wouldsetapriceofzeroforthatresourceinordertominimizethefirm’sprofit.
Therefore, thesecondtermof(19)willbezeroandthefirm’sdecisionproblemofchoosingproduction
activitiessoastomaximizeprofitssimplyreducesto:
Maximize
n
j
=
1
c
j
x
j
,
VB.NET PDF insert image library: insert images into PDF in vb.net
using RasterEdge.XDoc.PDF; Have a try with this sample VB.NET code to add an image to the first page of PDF file. ' Open a document.
bookmarks in pdf from word; add bookmark pdf
VB.NET PDF File Compress Library: Compress reduce PDF size in vb.
Also able to uncompress PDF file in VB.NET programs. Offer flexible and royalty-free developing library license for VB.NET programmers to compress PDF file.
adding bookmarks to a pdf; copy pdf bookmarks to another pdf
4.8
MathematicalEconomics
153
subjectto:
n
j
=
1
a
ij
x
j
b
i
(
i
=
1
,
2
,...,
m
),
(20)
x
j
0
(
j
=
1
,
2
,...,
n
),
theusualprimallinearprogram.
Nowletuslookattheproblemfromthestandpointofthemarket.Rearranging(19)asfollows:
n
j
=
1
c
j
m
i
=
1
a
ij
y
i
x
j
+
m
i
=
1
b
i
y
i
,
(21)
wecanmorereadilyseetheimpactofthefirm’sdecisiononthemarket. Notethattheterm
m
i
=
1
a
ij
y
i
is
themarketopportunitycostforthefirmusingtheresources a
1j
,
a
2j
,...,
a
mj
,inordertoengageinthejth
activityatunitlevel.Again,twoconsequencesimmediatelyfollow.First,ifthemarketsetsthepricessothat
therevenuefromengaginginanactivityexceedsthemarketcost,thatis,
c
j
m
i
=
1
a
ij
y
i
>
0
,
thenthefirmwouldbeabletomakearbitrarilylargeprofitsbyengagingintheactivityatanarbitrarilyhigh
level,aclearlyunacceptablesituationfromthestandpointofthemarket. Themarketinsteadwillalways
choosetosetitspricessuchthat:
m
i
=
1
a
ij
y
i
c
j
(
j
=
1
,
2
,...,
n
).
Second,ifthemarketsetsthepriceofaresourcesothattherevenuefromengaginginthatactivitydoesnot
exceedthepotentialrevenuefromthesaleoftheresourcesdirectlytothemarket,thatis,
c
j
m
i
=
1
a
ij
y
i
<
0
,
thenthefirmwillnotengageinthatactivityatall. Inthislattercase,theopportunitycostassociatedwith
engagingintheactivityisinexcessoftherevenueproducedbyengagingintheactivity.Hence,thefirstterm
of(21)willalwaysbezero,andthemarket’s‘‘decision"problemofchoosingthepricesfortheresourcesso
astominimizethefirm’sprofitreducesto:
Minimize
m
i
=
1
b
i
y
i
,
subjectto:
m
i
=
1
a
ij
y
i
c
j
(
j
=
1
,
2
,...,
n
),
(22)
y
i
0
(
i
=
1
,
2
,...,
m
).
Thelinearprogram(22)isthedualof(20).
Thequestionsthatthennaturallyariseare‘‘Whendotheseproblemshavesolutions?"and‘‘Whatisthe
relationshipbetweenthesesolutions?"Inarrivingatthefirm’sdecisionproblemandthemarket’s‘‘decision"
C# PDF File Compress Library: Compress reduce PDF size in C#.net
All object data. File attachment. Flatten visible layers. C#.NET DLLs: Compress PDF Document. Add necessary references: RasterEdge.Imaging.Basic.dll.
bookmarks pdf file; copy bookmarks from one pdf to another
C# PDF File Merge Library: Merge, append PDF files in C#.net, ASP.
Add necessary references: using RasterEdge.XDoc.PDF; Note: When you get the error "Could not load file or assembly 'RasterEdge.Imaging.Basic' or any other
convert excel to pdf with bookmarks; bookmarks pdf
154
DualityinLinearProgramming
4.9
problem,weassumedthatthefirmandthemarketwouldinteractinsuchamannerthatanequilibriumwould
bearrivedat,satisfying:
b
i
n
j
=
1
a
ij
ˆ
x
j
ˆ
y
i
=
0
(
i
=
1
,
2
,...,
m
),
(23)
c
j
m
i
=
1
a
ij
ˆ
y
i
ˆ
x
j
=
0
(
j
=
1
,
2
,...,
n
).
Theseequationsarejustthecomplementary-slacknessconditionsoflinearprogramming.Thefirstcondition
impliesthateithertheamountofresourceithatisunused(slackintheithconstraintoftheprimal)iszero,or
thepriceofresourceiiszero.Thisisintuitivelyappealingsince,ifafirmhasexcessofaparticularresource,
thenthemarketshouldnotbewillingtopayanythingforthesurplusofthatresourcesincethemaketwishes
tominimizethefirm’sprofit.Theremaybeanonzeromarketpriceonaresourceonlyifthefirmisconsuming
allofthatresourcethatisavailable.Thesecondconditionimpliesthateithertheamountofexcessprofiton
the jthactivity(slackinthe jthconstraintofthedual)iszeroorthelevelofactivity jiszero. Thisisalso
appealingfromthestandpointoftheperfectlycompetitivemarket,whichactstoeliminateanyexcessprofits.
Ifwehadanequilibriumsatisfying(23),then,byequating(19)and(21)forthisequilibrium,wecan
quicklyconcludethattheextremevaluesoftheprimalanddualproblemsareequal;thatis,
n
j
=
1
c
j
ˆ
x
j
=
m
i
=
1
b
i
ˆ
y
i
.
Observethatthisconditionhastheusualinterpretationforafirmoperatinginaperfectlycompetitivemarket.
Itstatesthatthemaximumprofitthatthefirmcanmakeequalsthemarketevaluationofitsinitialendowment
ofresources.Thatis,thefirmmakesnoexcessprofits.Theimportantstepistoanswerthequestionofwhen
suchequilibriumsolutionsexist.Aswehaveseen,iftheprimal(dual)hasafiniteoptimalsolution,thenso
doesthedual(primal),andtheoptimalvaluesoftheseobjectivefunctionsareequal. Thisresultisjustthe
strongdualitypropertyoflinearprogramming.
4.9 GAMETHEORY
Theexampleoftheperfectlycompetitiveeconomygivenintheprevioussectionappearstobeagameof
somesortbetweenthefirmandthemalevolentmarket.Thefirmchoosesitsstrategytomaximizeitsprofits
whilethemarketbehaves(‘‘chooses"itsstrategy)insuchawayastominimizethefirm’sprofits. Duality
theoryis,infact,closelyrelatedtogametheory,andinthissectionweindicatethebasicrelationships.
Inmanycontexts,adecision-makerdoesnotoperateinisolation,butrathermustcontendwithother
decision-makerswithconflictingobjectives. Consider,forexample,advertisinginacompetitivemarket,
portfolioselectioninthepresenceofotherinvestors,oralmostanypublic-sectorproblemwithitsmultifaceted
implications.Eachinstancecontrastssharplywiththeoptimizationmodelspreviouslydiscussed,sincethey
concernasingledecision-maker,beitanindividual,acompany,agovernment,or,ingeneral,anygroup
actingwithacommonobjectiveandcommonconstraints.
Gametheoryisoneapproachfordealingwiththese‘‘multiperson"decisionproblems. Itviewsthe
decision-makingproblemasagameinwhicheachdecision-maker,orplayer,choosesastrategyoranaction
tobetaken. Whenallplayershaveselectedastrategy, , eachindividualplayerreceivesapayoff. Asan
example,considertheadvertisingstrategiesofatwo-firmmarket.TherearetwoplayersfirmR(rowplayer)
andfirmC(columnplayer). Thealternativesopentoeachfirmareitsadvertisingpossibilities;payoffsare
marketsharesresultingfromthecombinedadvertisingselectionsofbothfirms.ThepayofftableinTableau
9summarizesthesituation.
C# PDF File Split Library: Split, seperate PDF into multiple files
Split PDF document by PDF bookmark and outlines. Add necessary references: RasterEdge.Imaging.Basic.dll. Split PDF file by number of pages.
create bookmarks pdf file; export pdf bookmarks to excel
VB.NET PDF File Merge Library: Merge, append PDF files in vb.net
by directly tagging the second PDF file to the target one, this PDF file merge function VB.NET Project: DLLs for Merging PDF Documents. Add necessary references
how to bookmark a pdf document; copy pdf bookmarks
4.9
GameTheory
155
Sincewehaveassumedatwo-firmmarket,firmRandfirmCsharethemarket,andfirmCreceives
whatevershareofthemarketRdoesnot.Consequently,firmRwouldliketomaximizethepayoffentryfrom
thetableandfirmBwouldliketominimizethispayoff. Gameswiththisstructurearecalled two-person,
zero-sumgames.Theyarezero-sum,sincethegainofoneplayeristhelossoftheotherplayer.
Toanalyzethegamewemustmakesomebehavioralassumptionsastohowtheplayerswillact.Letus
suppose,inthisexample,thatbothplayersareconservative,inthesensethattheywishtoassurethemselves
oftheirpossiblepayofflevelregardlessofthestrategyadoptedbytheiropponent.Itselectingitsalternative,
firmRchoosesarowinthepayofftable.TheworstthatcanhappenfromitsviewpointisforfirmCtoselect
theminimumcolumnentryinthatrow.IffirmRselectsitsfirstalternative,thenitcanbeassuredofsecuring
30%ofthemarket,butnomore,whereasifitselectsitssecondalternativeitisassuredofsecuring10%,but
nomore. Ofcourse,firmR,wishingtosecureasmuchmarketshareaspossible,willselectalternative1,
toobtainthemaximumofthesesecuritylevels.Consequently,itselectsthealternativegivingthemaximum
ofthecolumnminimum,knownasamaximinstrategy. Similarly,firmC’ssecuritylevelsaregivenbythe
maximumrowentries;ifitselectsalternative1,itcanbeassuredoflosingonly30%ofthemarket,andno
more,andsoforth.Inthisway,firmCisledtoa minimaxstrategyofselectingthealternativethatminimizes
itssecuritylevelsofmaximumrowentries(seeTableau10).
Fortheproblemathand,themaximinandminimaxareboth30andwesaythattheproblemhasa
saddlepoint. Wemightverywellexpectbothplayerstoselectthealternativesthatleadtothiscommon
value—bothselectingalternative1. Observethat,bythewaywearrivedatthisvalue,thesaddlepointisan
equilibriumsolutioninthesensethatneitherplayerwillmoveunilaterallyfromthispoint. Forinstance,if
firmRadherestoalternative1,thenfirmCcannotimproveitspositionbymovingtoeitheralternative2or3
sincethenfirmR’smarketshareincreasestoeither40%or60%.Similarly,iffirmCadherestoalternative1,
thenfirmRaswellwillnotbeinducedtomovefromitssaddlepointalternative,sinceitsmarketsharedrops
to20%ifitselectsalternative2.
Thesituationchangesdramaticallyifwealterasingleentryinthepayofftable(seeTableau11).
Nowthesecuritylevelsforthetwoplayersdonotagree,andmoreover,givenanychoiceofdecisions
bythetwofirms,oneofthemcanalwaysimproveitspositionbychangingitsstrategy.If,forinstance,both
firmschoosealternative1,thenfirmRincreasesitsmarketsharefrom30%to60%byswitchingtoalternative
2.Afterthisswitchthough,itisattractiveforfirmCthentoswitchtoitssecondalternative,sothatfirmR’s
marketsharedecreasesto10%.Similarmovementswillcontinuetotakeplaceasindicatedbythearrowsin
thetable,andnosinglechoiceofalternativesbytheplayerswillbe‘‘stable".
Isthereanywayforthefirmstodobetterinusing randomizedstrategies? Thatis,insteadofchoosing
astrategyoutright,aplayerselectsoneaccordingtosomepreassignedprobabilities. Forexample,suppose
156
DualityinLinearProgramming
4.9
thatfirmCselectsamongitsalternativeswithprobabilities x
1
,x
2
,andx
3
,respectively. Thentheexpected
marketshareoffirmRis
30x
1
+
40x
2
+
60x
3
iffirmRselectsalternative1
,
or
60x
1
+
10x
2
+
30x
3
iffirmRselectsalternative2
.
SinceanygaininmarketsharebyfirmRisalosstofirmC,firmCwantstomaketheexpectedmarket
shareoffirmRassmallaspossible,i.e.,maximizeitsownexpectedmarketshare.FirmCcanminimizethe
maximumexpectedmarketshareoffirmRbysolvingthefollowinglinearprogram.
Minimize
v,
subjectto:
30x
1
+
40x
2
+
60x
3
−v≤
0
,
60x
1
+
10x
2
+
30x
3
−v≤
0
,
(24)
x
1
+
x
2
+
x
3
=
1
,
x
1
0
,
x
2
0
,
x
3
0
.
ThefirsttwoconstraintslimitfirmR’sexpectedmarketsharetobelessthanorequalto
v
foreachoffirm
R’spurestrategies.Byminimizing
v
,fromClimitstheexpectedmarketshareoffirmRasmuchaspossible.
Thethirdconstraintsimplystatesthatthechosenprobabilitiesmustsumtoone. Thesolutiontothislinear
programisx
1
=
1
2
,x
2
=
1
2
,x
3
=
0,and
v =
35. Byusingarandomizedstrategy(i.e.,selectingamong
thefirsttwoalternativeswithequalprobability),firmChasimproveditssecuritylevel. Itsexpectedmarket
sharehasincreased,sincetheexpectedmarketshareoffirmRhasdecreasedfrom40percentto35percent.
LetusnowseehowfirmRmightsetprobabilities y
1
andy
2
onitsalternativeselectionstoachieveits
bestsecuritylevel.WhenfirmRweightsitsalternativesby y
1
andy
2
,ithasanexpectedmarketshareof:
30y
1
+
60y
2
iffirmCselectsalternative1
,
40y
1
+
10y
2
iffirmCselectsalternative2
,
60y
1
+
30y
2
iffirmCselectsalternative3
.
FirmRwantsitsmarketshareaslargeaspossible, buttakesaconservativeapproachinmaximizingits
minimumexpectedmarketsharefromthesethreeexpressions.Inthiscase,firmRsolvesthefollowinglinear
program:
Maximize
w,
subjectto:
30y
1
+
60y
2
−w≥
0
,
40y
1
+
10y
2
−w≥
0
,
60y
1
+
30y
2
−w≥
0
,
(25)
y
1
+
y
2
=
1
,
4.9
GameTheory
157
y
1
0
,
y
2
0
.
Thefirstthreeconstraintsrequirethat,regardlessofthealternativeselectedbyfirmC,firmR’smarketshare
willbeatleast
w
,whichisthenmaximized. Thefourthconstraintagainstatesthattheprobabilitiesmust
sumtoone. Inthiscase,firmRactsoptimallybyselectingitsfirstalternativewithprobability
y
1
=
5
6
and
itssecondalternativewithprobabilityy
2
=
1
6
,givinganexpectedmarketshareof35percent.
Notethatthesecuritylevelsresultingfromeachlinearprogramareidentical. Oncloserexamination
weseethat(25)isinfactthedualof(24)! Toseethedualitycorrespondence,firstconverttheinequality
constraintsin(24)tothestandard
(≥)
foraminimizationproblembymultiplyingby
1. Thenthedual
constraintderivedfrom‘‘pricing-out" x
1
,forexample,willread
30y
1
60y
2
+w≤
0,whichisthefirst
constraintin(25).Inthissimpleexample,wehaveshownthattwo-person,zero-sumgamesreducetoprimal
andduallinearprograms. Thisistrueingeneral,sothattheresultspresentedfordualitytheoryinlinear
programmingmaybeusedtodrawconclusionsabouttwo-person,zero-sumgames. Historically,thistook
placeinthereverse,sincegametheorywasfirstdevelopedbyJohnvonNeumannin1928andthenhelped
motivatedualitytheoryinlinearprogrammingsometwentyyearslater.
GeneralDiscussion
Thegeneralsituationforatwo-person,zero-sumgamehasthesamecharacteristicsasoursimpleexample.
ThepayofftableinTableau12andtheconservativeassumptionontheplayer’sbehaviorleadtotheprimal
andduallinearprogramsdiscussedbelow.
Thecolumnplayermustsolvethelinearprogram:
Minimize
v,
subjectto:
a
i1
x
1
+
a
i2
x
2
+···+
a
in
x
n
−v≤
0
(
i
=
1
,
2
,...,
m
),
x
1
+
x
2
+···+
x
n
=
1
,
x
j
0
(
j
=
1
,
2
,...,
n
);
andtherowplayertheduallinearprogram:
Maximize
w,
subjectto:
a
1j
y
1
+
a
2j
y
2
+···+
a
mn
y
m
−w ≥
0
(
j
=
1
,
2
,...,
n
),
y
1
+
y
2
+···+
y
m
=
1
,
y
i
0
(
i
=
1
,
2
,...,
m
).
Theoptimalvaluesforx
1
,
x
2
,...,
x
n
,andy
1
,
y
2
,...,
y
m
,fromtheseproblemsaretheprobabilitiesthat
theplayersusetoselecttheiralternatives. Theoptimalsolutionsgive
(
min
v)=(
max
w)
and,asbefore,
158
DualityinLinearProgramming
thesesolutionsprovideastableequilibrium,sinceneitherplayerhasanyincentiveforimprovedvalueby
unilaterallyalteringitsoptimalprobabilities.
Moreformally,iftherowplayerusesprobabilitiesy
i
andthecolumnplayerusesprobabilitiesx
j
,then
theexpectedpayoffofthegameisgivenby:
m
i
=
1
n
j
=
1
y
i
a
ij
x
j
.
Bycomplementaryslackness,theoptimalprobabilities
ˆ
y
i
and
ˆ
x
j
oftheduallinearprogramssatisfy:
ˆ
y
i
=
0
if
n
j
=
1
a
ij
ˆ
x
j
<ˆv
and
ˆ
y
i
=
0
onlyif
n
j
=
1
a
ij
ˆ
x
j
= ˆv.
Consequently,multiplyingtheithinequalityintheprimalby
ˆ
y
i
,andaddinggives
m
i
=
1
n
j
=
1
ˆ
y
i
a
ij
ˆ
x
j
=
m
i
=
1
ˆ
y
i
ˆv= ˆv,
(26)
showingthattheprimalanddualsolutions
ˆ
x
j
and
ˆ
y
i
leadtothepayoff
ˆv
.Thelastequalityusesthefactthat
theprobabilities
ˆ
y
i
sumto1.
Next,consideranyotherprobabilitiesy
i
fortherowplayer.Multiplyingtheithprimalequation
n
j
=
1
a
ij
ˆ
x
j
≤ˆv
byy
i
andadding,wefindthat:
m
i
=
1
n
j
=
1
y
i
a
ij
ˆ
x
j
m
i
=
1
y
i
ˆv=ˆv.
(27)
Similarly,multiplyingthejthdualconstraint
m
i
=
1
ˆ
y
i
a
ij
≥wˆ
byanyprobabilitiesx
j
andaddinggives:
m
i
=
1
n
j
=
1
ˆ
y
i
a
ij
x
j
n
j
=
1
x
j
=wˆ.
(28)
Since
ˆv=wˆ
bylinearprogrammingdualitytheory,Eqs.(26),(27),and(28)implythat:
m
i
=
1
n
j
=
1
y
i
a
ij
ˆ
x
j
m
i
=
1
n
j
=
1
ˆ
y
i
a
ij
ˆ
x
j
m
i
=
1
n
j
=
1
ˆ
y
i
a
ij
x
j
.
Thisexpressionsummarizestheequilibriumcondition.Byunilaterallyalteringitsselectionofprobabilities
ˆ
y
i
toy
i
,therowplayercannotincreaseitspayoffbeyond
ˆv
.
Similarly, thecolumnplayercannotreducetherowplayer’spayoff below
ˆv
byunilaterallychangingits
selectionofprobabilities
ˆ
x
j
tox
j
.Therefore,theprobabilities
ˆ
y
i
and
ˆ
x
j
actsasanequilibrium,sinceneither
playerhasanincentivetomovefromthesesolutions.
GameTheory
159
EXERCISES
1. Findthedualassociatedwitheachofthefollowingproblems:
a)
Minimizez
=
3x
1
+
2x
2
3x
3
+
4x
4
,
subjectto:
x
1
2x
2
+
3x
3
+
4x
4
3
,
x
2
+
3x
3
+
4x
4
≥−
5
,
2x
1
3x
2
7x
3
4x
4
=
2
,
x
1
0
,
x
4
0
.
b)
Maximizez
=
3x
1
+
2x
2
,
subjectto:
x
1
+
3x
2
3
,
6x
1
x
2
=
4
,
x
1
+
2x
2
2
,
x
1
0
,
x
2
0
.
2. Considerthelinear-programmingproblem:
Maximizez
=
2x
1
+
x
2
+
3x
3
+
x
4
,
subjectto:
x
1
+
x
2
+
x
3
+
x
4
5
,
2x
1
x
2
+
3x
3
=−
4
,
x
1
x
3
+
x
4
1
,
x
1
0
,
x
3
0
,
x
2
andx
4
unrestricted
.
a) Statethisproblemwithequalityconstraintsandnonnegativevariables.
b) Writethedualtothegivenproblemandthedualtothetransformedproblemfoundinpart(a).Showthatthese
twodualproblemsareequivalent.
3. Theinitialandfinaltableausofalinear-programmingproblemsareasfollows:
InitialTableau
Basic
Current
variables
values
x
1
x
2
x
3
x
4
x
5
x
6
x
5
6
4
9
7
10
1
x
6
4
1
1
3
40
1
(−
z
)
0
12
20
18
40
a) Findtheoptimalsolutionforthedualproblem.
b) Verifythatthevaluesoftheshadowpricesarethedualfeasible,i.e.,thattheysatisfythefollowingrelationship:
c
j
=
c
j
m
i
=
1
a
ij
y
i
0
,
wherethetermswithbarsrefertodatainthefinaltableauandthetermswithoutbarsrefertodataintheinitial
tableau.
Documents you may be interested
Documents you may be interested