,

Ll"paom8!d

oc:;09puelll~a

5o££S

"L

" rsssnn"

'~'0o£0

(/09o£G H99H0

"" .L(/(/

SLLVV t?o£ Mot?1M

AlddnSG

S3(fO.LS

lSO::l-mnmTUilllB'suOIlnloslIB13uoum'pug01s~[B013gll.L'g.101SlBlpJOpUBmgpglll

lBnbgg.lOlSq:mglB13U~Al.IJBSlUgmd~qslB10lgqlpUBAlddnss,gSnoqg.TBMgq1pgg::lXglOU

opgSIl01p.rBMq::lBg13U!ABgISlugwdlqslBWlgqllBqlOSU'1)g13pgq::lBgUOdlqs01(IX

1lI1l0WBgqlsgYI::lgdsmg[qo.ldUOI1B1.lOdSlIB.llB011I0~1010SV'Sg.101SgqlliBlBPliBLUgp

gqllggm01glBllbgpBg,m'sgSnoqg.lBMlIB.IgAOpgmwns'sgqddnslBlOlgqllBqlgUrnSSB

gM.fpgZISJOPUBWgpBSBq[gJ01SpUB"sgZIS.toAlddnsBSBq1gSlloqg.TBM

'lP.lBgS;USUOIlBlgdo1IlpglPl1lSsmg[qOJdUOI1BZrlllTldo

lS.lYgqlJOgUOSBMII'lU;}[qO.ldUOHl:l.lodSUl:.lJ.gqlpgnB::lAIglBl.IdO.lddBSImg[qOJd

UOllBZlLU~ldoslql'Ll'vg.ll113ldUlLUg(qOJdglellllBSglPggs'S150::lUOllBlTOdSUB.llgql

SgZillllUffillBqlSg.T01S01sgSnoqglBMmOJJSWgllgqlI1BJO13UllnO.lBpug01SI[B013

glllocr'1)g13pgUOWgjIUB13l1Telel~qs10Jpg13.TBlI::l(I;)IS0::lBSIg.Tgql1BqlSIMgllSI

lBL[M,ISg101SlI::lBg011MgSIlOlpmMlI::lBgWO.lJU'1)g13pgUB1I11M'glgldmo::lgq

01pgUIllSSBSI(3',{'X)=0qdBJ13;;llTl.mel~q;;ll[l'So,lOjSSBSg::lll.TgApUBm;;lpgl[lpUB

sosnOL/o.JVIHSBSg::lll.TgAAlddnsgq101J;;lp.l;;lM°1uBql.I;;l13.TB[S.r;;l13;;llUlMOU-SPUBW;;lP

pUBsgTlddnsgABqS;;l::ll].l;;lA;;lqlpUBA11::lBelB::lpglTlUl[Un;;lABq;;l.r;;lllS;;l13pgglll'SllIgIqOJel

13UTq::llBWgt.p01lB[TllHS°vovUOll::lgSlITS)[.TOMlgU13lHlI::llBmgllllITSB'gl!PBdlqglB

sqdB.11313UlApgpUn;;lSOqMS)j.lOM1;;lUl;;lPlSllO::lWMgM°g13pgUB13UOIBMOg01pg13,mq::l

lSO::lBSIg.1gqlL[::lll[MUISA'\Og)[.lOMlgUApnlS01SUOIpgSsnOlAg.ldgqlUlpgdOlgAgpS13U!

-l[::llBWpUB'SMOg)[.lOM1;;lU'Sgg.Tl13llTUUBds.t0g13pglMOU)[.lIlOAIcTcTBgMUOll::lgSSllllUI

Wa'1aOHdNOILVl,HOdSNVHl,aHl,sol'

'(B1BplndmSIl[elB.l13g1l1)lIelB.T13glll,mcTlqBlTT.IgAO::l

g13pgWl1LLlTUffilBpUB13Ull[::llBmLUlllUlXBlUBpug.01LlIB.l130.rcT.IglOdwO::lBgll.TM·SZ

°13Ulq::nBmmlllllTXBlLIBl;;l1301pOL[lgm

SILIIgsnpUB6'vg.lll13'dU~qcTB.l13gL[l.rOJ13Ull[JlRWIBT1,melB)[::llcTAIWOpUB(l(q)

4.5 The Transportation Problem 165

solution. A mathematical statement of the trallspoL1ation problem is

mll11mlZe L cijxij sllch thati,j

Lxij :::Si for each i, L xij = d) for each j, and Xi) :::: 0)

While spallllillg trees do Ilot appecu' anywhere in the statement of the problem, itturns out that they are celltral to sol villg this problem: The set of edges used forshipmellts in the opti mal solution form a spanning tree. Our strategy to find an optimalsolutioll will start with an initial (nonoptimal) solution that is a spanning tree. Wewill repeatedlyfilld a cheaper spanning tree solution by dropping one edge from thecurrent spanning tree and replacing it with another edge to form a cheaper spanningtree solution.

The data describing a Transportation Problem are Llsually presented in a tablecalled a transportation tableau. See the tableau and associated bipartite graph for asample transportatioll problem in Figure 4.17. (The graph representation is so clut-tered that it is only drawn for small problems.) Our analysis of how to solve thetransportation problem will be developed in terms of this example. The suppliesSi of the warehouses appear on the right side of the tableau, and the demands eLjof the stores appear at the bottom. The shipping cost C'j for edge (i, j) appearsin the upper right half of entry (i, j) in the tableau. The number X'j in the lowerleft half of entry (i, j) tells how much is shipped from warehouse i to store j.[Note: we refer interchangeably to (i, j) as an edge or an entry in the tableau.]The xi) 's in Figure 4.17 are a (nonoptimal) solution for this transportation prob-lem. In the graph ill Figure 4.17, we have thickened the edges used in the solution.The reader can check that the sum of the xij's in each row i is ::: Si and that thesum of the xij's in each column j exactly equals dj. The cost of the sample solu-tion ill Figure 4.17's tableau, which uses the four edges (1,1), (2,1), (2,2), (3,2) is30 x $4 + 30 x $6 + 30 x $6 + 20 x $6 = $600.

To simplify the problem, we will assume that the sum of the supplies exactlyequals the sum of the demands. If the supplies exceed the demands, we can create a"dummy" store that takes in all excess supply. In Figllre 4.17, the total of the sup-plies is 130 and the total of the demands is J 10. In this case, we would create adummy store with a demand of 130 - 110 = 20, as shown in the tableau and graphinFigure 4.18. The solution in Figure 4.17 has been appropriately modified in Figure4.18 so that the sum of the xi)'s in row i now exactly equals Si. The cost of ship-ping a unit along any eelge to this dummy store will be 0, since no real costs areinvolved in this gimmick to balance supply alld demand. With 0 costs for shipping tothe dummy store, the total transportation cost does not change from Figure 4.17 toFigure 4.18.

We will now show that it suffices to lirnit ourselves to solutions involving a setof edges that does not contain any circuits. Recall that a set of edges that contains nocircuit forms a tree or collection of trees.

01'SJSI.IB

)J[llqSJM

mlllSSBsn

8sqSJ.IO.1

Irn::>.rI~oU

1l0.ld

O.lqJ.l;)M

JrB.TJA;;JS

:0::>gums

;;;JS.lJA;l.l

~ppOUI

1QI1[08B

PJPIAlp

''<I4dBJa

';;JH

S;)41JO

Sll;).IJ;;Jp

IM'1S0;)

J;;JAJ1I0

rqrssod

07\\;)M

S;;J]lP;:J

11111l1ToS

[]lId111

11M;:JU

l;;Jsqns

;;Jr;;Jlll

]llllAUPAqlBql;:JloN's;:J13P;:JU;:JA;:J;:JqluoorAqm;:Jql;:J;)I1P;:J.1pUBS;:J13P;:Jppo;:JqlUO0[AqSPA;:JIjU;:JWdlqSgSBg.1;)UlUB;);:JMos'(['[);:J13pgUO01ST.1;:JqWI1UlS;:JlIBlIIS;:Jlfl·S1IlS;:J13P;:JU;:JA;:J;:Jl[1UlSr;:JA;:J[lU;:JmcT~qs;:Jql;:JlITWBX;:J;:JMos'0MOpq11l1;).Tl;);:JqlJO;:J13P;:J

U;:JA;:JAUB1IllU;:Jurd!L[S;:Jql;:JSB;:J.1JgplOUUBJ;:JMlBljlS!UOT1BJyrpolU.Tl10U!lUlBllSUO;)

IBJI1UJ;:Jql,'l~nJll;);:JL[1JOS;:J13P;:JU;:JA;:J;:JlPUOS;:JSB;;l.1J;:JP13u~puocTs;:JDO;)qllM';:JIqlssod

SBq;)l1WSB11l1;).IT;)s1qlJOs;:J13P;:Jppo;:JqlUlsjU;:JlIId~qs;:JqlgSB;:Jl;)UTsnl;:JI'UOllB;)Ylpom

STqlAq;:JlqlssocTISO;)Ul1I0lpnp;:J.llSg131BI;:Jql1;:J13ol,·ZAquOTll1rOS;:JlPJOlSO;)gql

s;:J;)np;:J.lUOT1BJYlpoLlrSTLII'snql,'Z-=Zl-01SI;:J13UBl[JI;:JU;:JL[l,'ZI=0+9+9Aq

lSO;);;lljls;:J;)np;:JJ(['[)pUB'(Z'[)'(tZ)13UO[B11L111SS;;l[;:JuO'01=(S;:J'1lP;:J;:J;:Jllll;:JSOlll10J

SlSO;);:Jq1)0+9+vAqlS0;);:JL[1S;;lSB;:JJJUl(['[)'(Z'Z)'(t[)13UOIB11un;:J.10m;:JuO'SJO

UOI1B;)YIPOWSlql1pTMS;:J13UBq;)uorll1los;:JqlJOlSO;)[BUl13l.TO;;lqlMOq)[;);:J1I;)sn1;:J'l

'UO!ll1[OSpnBABum13B;;l.TBslu;:Jwdll[S

p;:Jyrpow;:JqlospUB';:Jums;:JqlsJ1Xp;:JylpOW;:Jl[1JOsLImsUUIl1[O;)pUBMO.l;:Jqldg;:J)[

S;:J13UBL[;)13uquBIBq;:Js;:JL[l,·ll1l;).TTJSlljlJO(S;:J13P;:J.1;:JqlO;:JL[1)S;:J13pgLiotta;:JqluoTAq

slLI;:Jmdlqs;:JlIl13UT;)np;:J.1pUB'(f'[)lB13l1Tl.mlSl111;)Jl;)SIL[l.10S;:J13P;:Jppo;:JqlIlBJ;:JMlBqM

'lm;)JT;)SlqlJOS;:J13P;:JqlJYpUB'pnql'lS.lY;:Jl[luo1Aqslu;:JwcT!l[s;:Jql13UTsB;:J.1J

-1IlAqSAJ!POWLIB;);:JM'81'val1l13TdUlqdB.l13gqlUls;:J13pgp;:Ju;:J)[.TBp;:Jql;:J;:JS

:lTilJll;)BW.10J'(['[)'(['E)'(G'[)'(Z'G)'(['G)'en)'sUlSlU;:JmcTlqsJOJp;:Jsn

S;:J13P;:J;:Jql1BL[1;:JA.l;:JSqO'81'v;:J.Tl1131dUIP;:JABldsrpSuOTlnIos;:Jql.1;:JPTSUOJ·sw;:JIqo.ld

lIOT1Bl-IOdSUB.11lIB.10JSlIOlll1IOSlIB01S;:JZqB.1;:JU;:J'1l;:Jldumx;:JSll[lMOqumldx;:JpUB;:J[el

-WBX;:JUBlj11M1r;:J1B1lsnnlJ;:Jl[lBJlnq'BWUI;:JiSTljlJOJOOJcTTBW10JB;:JAl13lOll[1lM;:JM

foo.IJ

i-

·SlTn;).l!;)Oll13U!UlBlllO;)(S)3JOl;:JsqnsBSICS)3;:JJ;:JljM'suBqlSS;:JI.TO;:JlIIBS;:JqlSlSO;)lBqlS1I0l1n[OS.l;:JqlOlIBS~;:J.T;:JqllIgl[l,'lll1;)llJBSUlBllIO;)

lBlp(S):3.S;:J13P;:JJO19SB13UTAIOALllw;:J[qOJdUOIlB1JocTSllBJlB01uOllnjOSB;:JqS1;:J'l

Ivwwa7

8["pa.m8?.1

02:0<;09PUEllIOO

0102:

S022Sa309L3

'(lUluna~I:SSS9n02DEn3a0090(fl9ll_10992:Ho933J2:a(f(fSI17I\f02\f

M0171Ma2:17

A[ddnsAlUluno2:

S3(fOJ.S

SToRES

my

1atIan

m-ion

ges!lit;in-uit,:ntsgesJed

ion)sts:ostIcesthish. asticalveniSm, byling

4.5 The Transportation Problem 167

STORES

2 Supply

40

2 60

3 30

Demand 60 50 20Figure 4.19

the level of shipments down to 0 on edge (1,3), we have dropped this edge from thesubset of edges used in the new solution. Thus, the new solution is circuit-free. Thenew tableau is given in Figure 4.19. The reader shollld check that the new sollltionin Figure 4.19 has a cost of $580, which, as expected, is $20 less than the cost of thesolution in Figure 4.18.

If it had turned out that our modification of increasing shipments by 1 on oddedges and decreasing shipments by 1 on even edges had increased the cost, thenwe would reverse the strategy and decrease shipments on odd edges as much aspossible-until one of the odd edges has a shipment of zero-and increase shipmentson even edges correspondingly. Also, if our modification reslllted in no change in thecost, we would still follow the original strategy of increasing odd-edge shipments anddecreasing even-edge shipments as mllch as possible in order to get a new solutionof the same cost that was circllit-free.

Because the graph for a transportation problem is bipartite, every circuit in thegraph will be even-length, by Theorem 2 in Section 1.3. So al1Ycircuit's edges can bedivided into odd and even edges, as done in the preceding example. Then, whenevera Sollltion contains a circuit, we can apply the modification of increasing shipmentsin odd edges al1d decreasing shipments in even edges as mllch as possible, or thereverse strategy. This will produce a new sollltion that is less costly, or possibly thesame cost, and which does not contain that circuit. If the original sollltion containedseveral circllits, the modification would have to be applied repeatedly llntil all circllitswere broken. •

From Lemma 1, it follows that we only need to consider sollltions which containnocircllits-that is, solutions which are spanning trees or spanning forests; a spanningforest is a disconnected collection of trees incident to all vertices. For the moment, letus aSSllmethat all circuit-free sollltions are spanning trees. In the following discllssion,we shall explain how to add one or more edges to a spanning forest solution, if onearises, to convert it into a spanning tree solution.

'Il'vg.lll131d;;lgS'01701lgSnoqg.1BM

1BAldelnsgqlg;)npg.lpliBnBg]qB1gL[lWO.lJgUOULUllIO;)gl;:l[gpgMOSpUB'1g.T01SW

PUBWgpgqlp;;lgSllBSgAEl[gMMON'Ol=(Ol'017)Ulill=IlxOS'glqlssodSBgKml

SBA,qUgslq}g)[BUIpliB'(['Z)A.1ll1g'SIlBL[1-0l'vg.rn13T::I.UllfMOL[SnBg[qB}13UIlITBWg.1

glPLIl]gll.10;)ISgMql.lOUglP01U.lIllgM'1g.101SWPUBWgpgqlJOlSg1glP1991llOJ,

'0(','17g.lll131d1I1UMOL[SSInBg]qBlpgylpOlli13L111lnSgJ;;lllJ,

'Ol=017-09011g.10}S}BPUBllIgpgl[lg;)llpg.1pUBIlBg[qBlgqlLUO.1JgUOMO.lglg[gpgi\",

OSpUB'1gsnoqg.mMlBAIddllSgL[ldllpgSllA:WlOlgABl[gM'017=(09'OV)UTlU=IIX

'mgIqoJd.ll10JOtI'1PpUBISJOllI11WTUITllgqlgq11'Mgn[BAgllJ,·gjqlssodSBg13.1BISB

Ilxg)[BV\I'(['r)A:JllIg}B'S1lBql-I1BgIqB1glllJO.IgU.lO;)ISgMljllOUgqllBl.lB1S

'SMOnOJSBpgqcTcTBSlg[lUSlljJ,·gjllCI.1gUJOJlSgMlIl.10NglllAqpglllBlqogUOglPSl61'17

g.ll113!tILIllfOTllllOSgqllBq1lnoS11.ll111l·lI.IglqOJcTuOllBl.locTsUB.11g[dWBS.mOgSIl[11MgM

all1(f.'/iJU.IO:)JSiJM1p.IONdLfJlqU01J111oSlU1JIUJUI)PU1d.']iJsmld

:gl[l

JJO

lOLlS

$S~.TBM

OE

0(:Oc:;

)JOOt?

S"~O.lS

glfllIOS

S.1g

IJOgsn

PliCUlQOS

"SnoH

"1I

VM

--

'UOTll1[OSlBW1lcTogqlOllgSOPS1AlIB:)ldAllBl[1

1l01l11lOSIBll1U1LIB13lfTU!BlqoJOA:BM.IgqlOlIBllIgsgJdgM'8gSlJ.1gX3UI·glll(l.1gllJOJ

lSgM1llJONgqlpgnB;)poqlgW;)oqpBUBAqS!lIOTll1lOS[BllIU~LIB1pnspug01ABM

lSgrdlLl1SgqJ,'pUllOJSIUOlln]OSlsgcTBgq;)Bjlllln'lIOT111IOS.1gcTBgl[JBpug01uOllnIos

;;lg.1113UlUUBcTs1lI;;U.ll1;)gqlAJTpOUlAIPglBgdg.T'PUQ;)gs'POLjlgLU;)OllpBUBAq1I011nlos

gg.q13ll!UUBdsIBlllLlTgWOSpuy'IS.lTd'sgSBL[cTOM}gAl'lL[lllMA13g1B.llS1I0!11l10S.lila

0(:OC:;0(:PUUUl30S

OZ'Pa.m8?d

" I~"'-..S

O£I~"'-..I."'-..IEn0H

" 09"'-..I"'-..I"'-..I(:1I

V

">,M .....'

'(IddnsAlUllina(:

S"(fO.LS

sultfluo2l'tf,>/-JO,HPNfr../oldmO891

'lOS

IJO

4.5 The Transportation Problem 169

STORES

2 Dummy Supply

2 040

6 060

7 I "'-.. 6 030

~10 ""J 20

60 50 20

2

3

Figure 4.22 Demand

We continue the procedure of repeatedly making the entry in the northwest cornerof the remaining tableau as large as possible. The complete Northwest Corner Rulesolution is shown in Figure 4.19, which for convenience is displayed in Figure 4.22.

Note that if the value we assign the current northwest entry in the current tableauuses up the supplies at the first (remaining) warehouse and also satisfies the demandof the first remaining store, then we would have to delete both the first row and thefirst columll of the current tableau. This will lead to a disconnected set of edges in thesolutioll-that is, a spanning forest. To avoid this outcome, we arbitrarily keep eitherthe first row or first column, although its supplies or demand is O.

Next we explain the second phase of how to improve the currellt solution. Thereare three steps to determining the improvement.

Phase II: Finding a Better SolutionStep ll.A. Determining Selling Prices at Warehouses and Stores

At this point, the initial solution is the Northwest Corner Rule solution in Figure4.22. We now introduce "selling prices" for the commodity at the warehouses andstores, based on the transportation costs in the initial solution. To start the pricingprocess, we need to pick an arbitrary price u I for the COI1Ullodityat warehouse 1, sayU.I = $10. We use edge (1,1) in our initial Sollltion to transport the commodity fromwarehouse 1 to store 1 at a cost of CII = $4 per unit. Thus, if we buy the commodityat warehouse I for $10 and ship it for $4 to store 1, the commodity should sell forVI = U I + CII = $10 + $4 = $14 at store 1.

Store 1 also receives shipments from warehouse 2 with a transportatioll costof e21 = $6 per unit. Now we reverse the reasolling used to determine the price atwarehouse I from the price at store 1. Given that the commodity's price at store]is $14 and it costs $6 to ship from warehouse 2 to store 1, the price at warehouse 2should be U2 = VI - C21 = $14 - $6 = $8. Warehouse 2 also ships to store 2 at a costof C22 = $6 so the price at store 2 should be V2 = U2 + C22 = $8 + $6 = $14. Usingthe shipping costs on the edges in our current spannillg tree solution, we can continue

;:J.l01S-l!,JO.ldp;:J;)np;;)JB;:JsnB:)[[1MZ;:J.l01S1B;:J;)UcTpg;)np;:JJV'W;:J1IJ;:JcTZ$AqZ;:).lOIS

lB;:J;)ucl13uq[;:JS;:JL[l1311lJnp;:JJ''Gl$=Z$+01$.ToJZ;:JJ01SlB11H;:JSUB;);:JM'Z$.IOJ(Z'r);:J13P;:JUO11cTTqspUB01$.IoJ[;:Jsnoll;:J.TBMlBA1IPOUffilO;);:JqlAnq;:JMJI'J;:JA;:JMOH'vl$SI

;:J;)!.lcT13U'lPSs,Z;:J.l01SpUB01$SI;:J:)ud1311l1Pss,1;:Jsnoq;:J.lBM'l$=el;)lSO;)qllM(z'r);:J13P;:Jl;:Jp~SUOJ'uoqnIos11l;:J.T.lll;);:Jql1Ilp;:JsnJOU;:J.lBlBl[ls;:J13P;:J;:JqllB)[001MOll;:JM

U01J1170SlUo.W1:Jaw01PPV0)aSp'3LpnlMSunmu.laPGHIldaJS

'UOlll1[OSsn.p.rajSlSO;)UOllBlJodsllBJl;:JqlJOWllS;:JqlSI08~$':r;:JlPB;:JP;:J10UsV

08~$=on[$-OOLr$=(O£:x8$+09x8$+OVx01$)-(Olx8$+O~xvl$+09xv[$)

51(Z)].O;:Jprslq131.1;:JlIl'(nUI

s;:J;)ucTP;:J1Bl;)OSSB;:JlPqllMZZ'v;:J.Il1lll,:{Ulu011nlos;:JlP.loJ'lllWW;:J1:;:J1B.IlSnTlIOJ,

d1[S

o

•,(Z)JOgpISpUBq-1PI;:JL[1AI·m;:JpSIs(£:)JOUlIlSS!L[lJO;:JP!SpllBq-1P[;:JL[,l,(Z)JO;:JP1SPUBlI-ll.{131.1;:JL[101IBl1b;:JS1(S):11IlS;:J13P;:JlIB.l;:JAOs(t:);:JqlJOLL1115;:Jq1JO;:JP!S

pUBlI-lq131.T;:Jql'SllqJ,.IpSI{;:J.l01SOWls1llaLlldrLjs;:JqlJOIBlO1;:JL[1pUB!sSI1;:Jsnoll;:J.lBM

JOlno('xSlll;:JwcTILj5;:JlPJOjBl01;:Jl[l'(S):;]UIS;:JllP;:JliBl;:JAO(£:)SWIlS;:JUOU;:JlIM

(t:)('xCn-(n)=I1X(I;)

U;:JLIJ,.'11-In=(1.)lBLjlUOI1IPUO;);;lqlAqP;:JUTlU.I;:Jl;:JP;:J.Tlls;:J;)ud;:Jql'(S):;]UlU'1);:J13P;:JL[;)B;:J.I0,:{

Ioo.lcl

(Z)((.,

'S'I1=:i-(p(n=:i=('x(1;)=:iII

'SIIBqJ,·sg;)l.ld

,S;:JSllOl[;:J.lBM;:JqllBs;:Jqc!clns,s;:JsnOL[;:J1BM;:JL[1JO1SO;);:J11lsnUrLLls;:J;)!.lcT,S;:J.l01SgqlW

SPUBW;:JP,S;:JJOIS;:JqlJO;:J[BS;:JL[1WO.TJglLlO;)Ul;:JqlSIBllb;:J'(S):;]1II(f',I)S;:J13P;:J.I;:JAO

P;:JUILllIlS'(1X(1.)I"'J,'uolllllossiquolSO;)UOIlBliOcTsUB.q;:JL[J,'V'lld;:J1SO113UlpJO;);)B

SuoqnIosuoP;:JSBq'A[dAlP;:Jds;:J.l,[;:J.l01SpUB1;:JsnOL[d.lBMlBS;:J;)!.Id;:JqInpliB'nPI

pUB'(s):;]l;:JS;:J13P;:J13UlsnLL1;:J]qO.1dU011B1JodSlIB.llBJOUOllll[OS;:J;:Jll13UILIllBclsB;:JqS1;:J1

Z1Jwwa7

.6;:JSlJ.I;:Jxg;:J;:JS

'llIIB[JSIL[lJOSlml;:Jp.I0J~lrn;).II:)BLlI.lOJlOllopUOlllllOS;:Jl.{llilp;:Jsns;:J13P;:J;:JL[1JI;:JlqISsac!

AjUOSIL1011lSBJSIL[lLITs;:J;)udJOuOqB[ll;)jll;)dlillBlIl;:JlON'UOllll[OSlU;:J.lJI1:);:JljlUIU'1)d13p;;lL[;)B;:J.TO]'11;)='n-In1BL[1SUOI1IPUO;);:Jlll13UISIl';:JlcTwBX;;l;;lL[1UlSB's,(npUBS,'11

;:JA1SS;:J;);)ns;;lUILLU;:Jl;:JP;:JMu;;lqJ,'gniBAklBJllq.lBAUB01[Bnb;;l111I;:JS;:JM'13U1Zl.mLLlWns

8$=En:AWWIlP8$=En:£:gSnoll;:J.lBM

(r)vi$=en:Z;:J.l01S8$=el1:Z;:Jsnoqg.lBM

vI$=In:I;:JJOIS01$=111:I.;:Jsnoq;:J.lBM

SIsg;)ud13Ull[;:JSJOIgS;:Jlgldmo;);:J1IJ,

·APAIP;:Jds;:J.I'£:;:J.l01SlB

pUB£:;:JsnOll;;l.lBMlBAllpommO:J;:JlllJOJEn'EI1s;:J;)l.lcT13U111;:JS;:JlBlmIB;)01SSd;)O.ldSIL[l

4.5 The Transportation Problem 171

sales minlls warehouse purchases-which by Lemma 2 equals a reduced transporta-tion cost. This means that a cheaper solution can be obtained by incorporating edge(1,2) illto the solution. [To maintain a spanning tree solution when edge (1,2) isadded, some edge in the CUlTelltsolution would have to be dropped-a choice made inStep II.C.] Before using edge (1,2), we check the other edges not in the CUlTentsolution to see how much each of them could reduce the profit. The results aresummarized below.

edge (1,2):edge (1,3):edge (2, 3):edge (3, 1):

Cl2 = $2 < V2 - UI = $14 - $10 = $4 decrease of $2Cl3 = $0> V3 - UI = $8 - $10 = -$2 increase of $2C23 = $0 = V3 - U2 = $8 - $8 = $0 no changeC31 = $7> VI - U3 = $14 - $8 = $6 increase of $1

(4)

We see that only edge (1,2) yields a reduction. So we add edge (1,2) to the currentsolution. If there were no edge that reduces the cost of the solution, then the currentsolution is optimal and we are finished.

Step n.c. Determining a Cheaper Spanning Tree Solution

In Step ILB, an edge is chosen to be added to the current solution. For the example inFigure 4.22, the choice is ecTge(1,2). When this edge is added to the set of edges inthe current solution, we have a unique circuit, by Exercise 28 in Section 3.2. Forthe solution in Figure 4.22, the circuit is (1,2), (2,2), (2,1), (1,1). As noted in theproof of Lemma 1 above, we get a cheaper solution by increasing the flow in theodd edges, (1,2) and (2,1), as much as possible while decreasing the flow in the evenedges, (2,2) and (1,1), correspondingl y. The net reduction is c 12 + C21 - C II - C22 =2+ 6 - 4 - 6 = -2. Note that this calculation cOllfirms our previous analysis that wewiIl save $2 for each unit shipped on edge (1,2).

The limiting constraint is when the shipment in an even edge decreases to O. Inour example, since the current shipment in both x II and X22 is 40, we can illcrease theshipmellts in (2,1) and (1,2) by 40 and reduce the shipments in (l,l) and (2,2) by 40.The new solution, cheaper by 40 x $2 = $80 than the previous solution, is shown illFigure 4.23.

STORES

2 Supply

40

2 60

3 30

DemandFigure 4.23 60 50 20

L$~$17$17$

Z[

9$17$

Z

£$Z8$T~snolp.llli\:\

1aToiS(u)

ZT~snoq~.IBi\:\

~.lOlS(q)

'S;;lqelelnsSS<l::lX;:J;:Jql.loJP;:JP;:J;:Ju;:Jq{EM;:J.l01S

AUIllHlPBlBlfl;:JlON'SlSO::lL10IlBlJOcTSLTBJlgL[l;:JAI13MO[;:JqS;:JlqBl;:Jq..L.Sllll11OSSP<l;;lU

Z;:J.l01SpLiBSlTlln0<=SP;:J;:JlI1;:Jj01SlI::lIL[MUIpUBSllllllOZSBqZ;;lsnOl[;:J.lBMpUB

SllLlIlO~SBq1;;lSllOll;:J.lBMq::lIL]MUIsW;:JlqO.ldLIOT1BlJodsURll13U1MOnOJ;:Jql;:JAToS·Z

17$9$[$17$ZT

[$17$Z$9$Z1

Zr~snoq~.IBi\:\

~J01S(u)

ZI;:Jsnoq~.IBi\:\

~lOlS(q)

'SlSO::lUO!lBl.loelSLTB.ll;:JlP;:JAI13MOpqSglqBl;;lqJ,'SllllnOvsP;:J;:Ju

Z;:J101SpliBSllUl1OZSP;:J;:JlIT;:J.I01Sll::lllj/\\1IlplWSllUl1asSBL[Z;:JsnOll<l.lBMpUB

S11unosSBqTgSIlOl[;:JJBMq::lIL[MUlsur;:JIqO.ldlIOT1Bl.IOcTSUBJl13l11MOnOJglll;:JA[OS·1

·1lll::l.lTJBSUTB1UO::luOllnlos;:JlIlJIP;:JUTUU;:Jl;:JP

AI;:Jllbmll;:JqlOULlB::ls;:J::luelAL[MS;;lUTllIBXg6;:JS1::J,T;:JXg';:JllU13111j.TB1S.1;:Jll;:JqBslll;:Js;:J.1c1

8;:JSI::lJ;:Jxg'sw;:JIqOJcTUOilBlIOcTsUBJlJOuOlll1loS;:Jlll.10J)[SBL-lS;:JSI::l.l;:JX3

S3:SIJ~mxa

'p;:JL[SlLIg;:JJB;:JMpUB'IBUIIldoSIUOllll[OS

11l;:J.1.m::l;:JL[1'LIOTllllOSlU;:JUI1::l;:JqlJOlSO::l;:J1PS;;l::JllP;:J.lS;:J13P;:J<lS;;lL[1JO;:JLTOU;:J::JU!S

1$JO;:JSB;:J,T::lUI9$=9$-Z[$=£11-[n<L$=IS;):(r'£);:J13P;:J

;:J13l1BlPou0$=9$-9$=(,11-En=0$=S1:;):(['z);:J13P;:J

17$JO<lSB;:J.lJUIv$-=01$-9$=111-En<0$=S[.):(£'[);;l13P;:J

Z$JO;:JSB;:J.1::JllIZ$=0[$-ZI$=[11-[n<17$=[I;):(['[);:J13P;:J

PI;:JIASliOilBIll::l[B::l<lql'SlSO::lLlOllBl.lodsLlB.ll;:JlP

U1UOll::lnp;:J.lB;:J::lnpcucTUOTllllOSjU;:J.l.m::l;:JqlU!lOUS;:J13P;;lAUBJI;:J;:JS;:JM'~rlld;:J1SLTT

9$=En

ZI$=1:nZI$=[n

:AWUIllP

:Z;;l.lOlS

:1;:J,T01S

:s;:JSllOlj;:JJBM

:Z;:JSllOl[;:J,TBM

:1;:JSIlOlI;:J,TBM

9$=En

9$=ll1

01$=111

:s;:J::ludJOps13l11MO][oJ;:JqluLBlqo;:JM';;l.IOpqSB131I1nlllllloJ'n$=Z$+01$=ZI;)+[n=ZnpuggM'(Z'[);:J13P;:J13l1ISIlpUBOT$=InL[llM13UllJB1S·S;:J.lOlSplW

S;:JSIlOL[;:J.lBMlBs;:J::l!.IdM;:JU;:Jll1dWO::l;:JM'SZ'v;:J.m131duruOllnlos;:Jql13L1Tsn'V'IId;:J1SUI

'UOIlllIOS,T;:Jll;;lqlITlSBPlIl]01II;;lsBlIdJOslmd;:J;:J.Tljl;:JL[lIB;:Jdg.l;:JMMON

,(Z'Z)p;:J)[::lId;:JM'SZ'17;:J.rn13ldLIT

'0JOI;:JA811U;:JwcTlqsBqllMll1qUOllDloSM;:JU;:JljlU1ABIS01(etZ)pUB(['r)JO;:J1I0)[::lrd

AI1.IB.lJlq.lB;:JN,.';:J;:J1l13l1lllLmelsB;;lqlOUPlllOMuOllnlosM;:JU;:JL[1'pIp;:JMJ1'S;:J13P;:JqlOq

cTOJpJOUUB::l;:JM'001P;:JSB;:J.1::J;:JPlfloq(Z'Z)pUB(['r)S;:J13P;:JUlMOll';;lL[1L[131101I1IBlBlll;:JloN