文档库 最新最全的文档下载
当前位置:文档库 › Introduction to Management Science 5th Edition, 课后习题答案 Chapter 6

Introduction to Management Science 5th Edition, 课后习题答案 Chapter 6

Introduction to Management Science 5th Edition, 课后习题答案 Chapter 6
Introduction to Management Science 5th Edition, 课后习题答案 Chapter 6

CHAPTER 6

NETWORK OPTIMIZATION PROBLEMS

SOLUTION TO SOLVED PROBLEMS

6.S1Distribution at Heart Beats

Heart B eats i s a m anufacturer o f m edical e quipment. T he c ompany’s p rimary p roduct i s a device u sed t o m onitor t he h eart d uring m edical p rocedures. T his d evice i s p roduced i n t wo factories a nd s hipped t o t wo w arehouses. T he p roduct i s t hen s hipped o n d emand t o f our

third--‐party w holesalers. A ll s hipping i s d one b y t ruck. T he p roduct d istribution n etwork i s shown b elow. T he a nnual p roduction c apacity a t F actories 1 a nd 2 i s 400 a nd 250, respectively. T he a nnual d emand a t W holesalers 1, 2, 3, a nd 4 i s 200, 100, 150, a nd 200, respectively. T he c ost o f s hipping o ne u nit i n e ach s hipping l ane i s s hown o n t he a rcs. D ue t o limited t ruck c apacity, a t m ost 250 u nits c an b e s hipped f rom F actory 1 t o W arehouse 1 e ach year. F ormulate a nd s olve a n etwork o ptimization m odel i n a s preadsheet t o d etermine h ow to d istribute t he p roduct a t t he l owest p ossible a nnual c ost.

This i s a m inimum--‐cost f low p roblem. T o s et u p a s preadsheet m odel, f irst l ist a ll o f t he a rcs as s hown i n B4:C11, a long w ith t heir c apacity (F4) a nd u nit c ost (G4:G11). O nly t he a rc from F1 t o W H1 i s c apacitated. T hen l ist a ll o f t he n odes a s s hown i n I4:I11 a long w ith e ach node’s s upply o r d emand (L4:L11).

The c hanging c ells a re t he a mount o f f low t o s end t hrough e ach a rc. T hese a re s hown i n

Flow (D4:D11) b elow, w ith a n a rbitrary v alue o f 10 e ntered f or e ach. T he f low t hrough t he arc f rom F1 t o W H1 m ust b e l ess t han t he c apacity o f 250, a s i ndicated b y t he c onstraint D4

<= F4.

For e ach n ode, c alculate t he n et f low a s a f unction o f t he c hanging c ells. T his c an b e d one using t he S UMIF f unction. I n e ach c ase, t he f irst S UMIF f unction c alculates t he f low l eaving the n ode a nd t he s econd o ne c alculates t he f low e ntering t he n ode. F or e xample, c onsider the F 1 n ode (I4). S UMIF(From, N odes, F low) s ums e ach i ndividual e ntry i n F low (the

changing c ells i n D 4:D11) i f t hat e ntry i s i n a r ow w here t he e ntry i n F rom (B4:B11) i s t he same a s i n t hat r ow o f N odes (i.e., F 1). S ince I 4 = F 1 a nd t he o nly r ows t hat h ave F 1 i n F rom (B4:B11) a re r ows 4 a nd 5, t he s um i n t he s hip c olumn i s o nly o ver t hese s ame r ows, s o t his sum i s D 4+D5.

The g oal i s t o m inimize t he t otal c ost o f s hipping t he p roduct f rom t he f actories t o t he wholesalers. T he c ost i s t he S UMPRODUCT o f t he U nit C osts w ith t he F low, o r T otal C ost = SUMPRODUCT(UnitCost, F low). T his f ormula i s e ntered i nto T otalCost (D13).

34567891011

J

Net Flow

=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)

The S olver i nformation a nd s olved s preadsheet a re s hown b elow.

Thus, F low (D4:D11) i ndicates h ow t o d istribute t he p roduct s o a s t o a chieve t he m inimum Total C ost (D13) o f $58,500.

Solver Parameters

Set Objective Cell: TotalCost To: Min

By Changing Variable Cells: Flow

Subject to the Constraints: D4 <= Capacity

NetFlow = SupplyDemand Solver Options:

Make Variables Nonnegative Solving Method: Simplex LP

34567891011

J

Net Flow

=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)

6.S 2 Assessing the Capacity of a Pipeline Network

Exxo 76 i s a n o il c ompany t hat o perates t he p ipeline n etwork s hown b elow, w here e ach

pipeline i s l abeled w ith i ts m aximum f low r ate i n m illion c ubic f eet (MMcf) p er d ay. A n ew o il well h as b een c onstructed n ear A . T hey w ould l ike t o t ransport o il f rom t he w ell n ear A t o their r efinery a t G . F ormulate a nd s olve a n etwork o ptimization m odel t o d etermine t he maximum f low r ate f rom A t o G .

This i s a m inimum--‐cost f low p roblem. A ssociated w ith e ach p ipe i n t he n etwork w ill b e a n arc (or, f or p ipes w hich m ight f low i n e ither d irection, t wo a rcs, o ne i n e ach d irection). T o set u p a s preadsheet m odel, f irst l ist a ll o f t he a rcs a s s hown i n B 5:C19, a long w ith t heir capacity (F5:F19). T hen l ist a ll o f t he n odes a s s hown i n H 5:H11. A ll t he t ransshipment nodes (every n ode e xcept t he s tart n ode A a nd t he e nd n ode G ) w ill b e c onstrained t o h ave net f low = 0 (Supply/Demand = 0). T he s

tart n ode (A) a nd e nd n ode (G) a re l eft unconstrained. W e w ant t o m aximize t he n et f low o ut o f n ode A .

The c hanging c ells a re t he a mount o f f low t o s end t hrough e ach p ipe (arc). T hese a re s hown in F low (D5:D19) b elow, w ith a n a rbitrary v alue o f 0 e ntered f or e ach. T he f low t hrough each a rc i s c apacitated a s i ndicated b y t he <= i n E5:E19.

For e ach n ode, c alculate t he n et f low a s a f unction o f t he c hanging c ells. T his c an b e d one using t he S UMIF f unction. I n e ach c ase, t he f irst S UMIF f unction c alculates t he f low l eaving the n ode a nd t he s econd o ne c alculates t he f low e ntering t he n ode. F or e xample, c onsider the A n ode (H5). S UMIF(From, N odes, F low) i n I 5 s ums e ach i ndividual e ntry i n F low (the changing c ells i n D 5:D19) i f t hat e ntry i s i n a r ow w here t he e ntry i n F rom (B5:B19) i s t he same a s i n t he e ntry i n t hat r ow o f N odes (i.e., A ). S ince t he o nly r ows t hat h ave A i n F rom (B5:B19) a re r ows 5 a nd 6, t he s um i n t he s hip c olumn i s o nly o ver t hese s ame r ows, s o t his sum i s D 5+D6.

4567891011

I

Net Flow

=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)

The g oal i s t o m aximize t he a mount s hipped f rom A t o G. S ince n odes B t hrough F a re

transshipment n odes (net f low = 0), a ny a mount t hat l eaves A m ust e nter G. T hus, maximizing t he f low o ut o f A w ill a chieve o ur g oal. T hus, t he f ormula e ntered i nto t he

objective c ell M aximumFlow (D21) i s =I5.

The S olver i nformation a nd s olved s preadsheet a re s hown b elow.

Thus, F low (D5:D19) i ndicates h ow t o s end o il t hrough t he n etwork s o a s t o a chieve t he Maximum F low (D21) o f 34 t housand g allons/hour.

Solver Parameters

Set Objective Cell: MaximumFlow To: Max

By Changing Variable Cells: Flow

Subject to the Constraints: Flow <= Capacity

NetFlow = SupplyDemand Solver Options:

Make Variables Nonnegative Solving Method: Simplex LP

4567891011

I

Net Flow

=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)

=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)

6.S 3 Driving to the Mile -High City

Sarah a nd J ennifer h ave j ust g raduated f rom c ollege a t t he U niversity o f W ashington i n Seattle a nd w ant t o g o o n a r oad t rip. T hey h ave a lways w anted t o s ee t he m ile--‐high c ity o f Denver. T heir r oad a tlas s hows t he d riving t ime (in h ours) b etween v arious c ity p airs, a s shown b elow. F ormulate a nd s olve a n etwork o ptimization m odel t o f ind t he q uickest r oute from S eattle t o D enver?

This i s a s hortest p ath p roblem. T o s et u p a s preadsheet m odel, f irst l ist a ll o f t he a rcs a s shown i n B 4:C11, a long w ith t heir c apacity (F4). O nly t he a rc f rom F 1 t o W H1 i s

capacitated. T hen l ist a ll o f t he n odes a s s hown i n I 4:I11 a long w ith e ach n ode’s s upply o r demand (L4:L11).

The c hanging c ells a re t he a mount o f f low t o s end t hrough e ach a rc. T hese a re s hown i n

Flow (D4:D11) b elow, w ith a n a rbitrary v alue o f 10 e ntered f or e ach. T he f low t hrough t he arc f rom F 1 t o W H1 m ust b e l ess t han t he c apacity o f 250, a s i ndicated b y t he c onstraint D 4 <= F 4.

Seattle

Grand Junction

Denver

For e ach n ode, c alculate t he n et f low a s a f unction o f t he c hanging c ells. T his c an b e d one using t he S UMIF f unction. I n e ach c ase, t he f irst S UMIF f unction c alculates t he f low l eaving the n ode a nd t he s econd o ne c alculates t he f low e ntering t he n ode. F or e xample, c onsider the F 1 n ode (I4). S UMIF(From, I 4, F low) s ums e ach i ndividual e ntry i n F low (the c hanging cells i n D 4:D11) i f t hat e ntry i s i n a r ow w here t he e ntry i n F rom (B4:B11) i s t he s ame a s i n I4 (i.e., F

1). S ince I 4 = F 1 a nd t he o nly r ows t hat h ave F 1 i n F rom (B4:B11) a re r ows 4 a nd 5, t he s um i n t he s hip c olumn i s o nly o ver t hese s ame r ows, s o t his s um i s D 4+D5.

34567891011

J

Net Flow

=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)

The g oal i s t o m inimize t he t otal c ost o f s hipping t he p roduct f rom t he f actories t o t he wholesalers. T he c ost i s t he S UMPRODUCT o f t he U nit C osts w ith t he F low, o r T otal C ost = SUMPRODUCT(UnitCost, F low). T his f ormula i s e ntered i nto T otalCost (D13).

The S olver i nformation a nd s olved s preadsheet a re s hown b elow.

Thus, F low (D4:D11) i ndicates h ow t o d istribute t he p roduct s o a s t o a chieve t he m inimum Total C ost (D13) o f $58,500.

Solver Parameters

Set Objective Cell: Total Cost To: Min

By Changing Variable Cells: Flow

Subject to the Constraints: D4 <= Capacity

NetFlow = SupplyDemand Solver Options:

Make Variables Nonnegative Solving Method: Simplex LP

34567891011

J

Net Flow

=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)=SUMIF(From,Nodes,Flow)-SUMIF(To,Nodes,Flow)

相关文档