数据、模型与决策运筹学课后习题和案例答案

PAGE

24

9-

PAGE

27

Chapter9

Integerprogramming

ReviewQuestions

9.1-1 Insomeapplications,suchasassigningpeople,machines,orvehicles,decisionvariableswillmakesenseonlyiftheyhaveintegervalues.

9.1-2 Integerprogramminghastheadditionalrestrictionthatsomeorallofthedecisionvariablesmusthaveintegervalues.

9.1-3 Thedivisibilityassumptionoflinearprogrammingisabasicassumptionthatallowsthedecisionvariablestohaveanyvalues,includingfractionalvalues,thatsatisfythefunctionalandnonnegativityconstraints.

9.1-4 TheLPrelaxationofanintegerprogrammingproblemisthelinearprogrammingproblemobtainedbydeletingfromthecurrentintegerprogrammingproblemtheconstraintsthatrequirethedecisionvariablestohaveintegervalues.

9.1-5 Ratherthanstoppingatthelastinstantthatthestraightedgestillpassesthroughthefeasibleregion,wenowstopatthelastinstantthatthestraightedgepassesthroughanintegerpointthatlieswithinthefeasibleregion.

9.1-6 No,roundingcannotbereliedontofindanoptimalsolution,orevenagoodfeasibleintegersolution.

9.1-7 Pureintegerprogrammingproblemsarethosewhereallthedecisionvariablesmustbeintegers.Mixedintegerprogrammingproblemsonlyrequiresomeofthevariablestohaveintegervalues.

9.1-8 Binaryintegerprogrammingproblemsarethosewhereallthedecisionvariablesrestrictedtointegervaluesarefurtherrestrictedtobebinaryvariables.

9.2-1 Thedecisionsare1)whethertobuildafactoryinLosAngeles,2)whethertobuildafactoryinSanFrancisco,3)whethertobuildawarehouseinLosAngeles,and4)whethertobuildawarehouseinSanFrancisco.

9.2-2 Binarydecisionvariablesareappropriatebecausethereareonlytwoalternatives,chooseyesorchooseno.

9.2-3 Theobjectiveistofindthefeasiblecombinationofinvestmentsthatmaximizesthetotalnetpresentvalue.

9.2-4 ThemutuallyexclusivealternativesaretobuildawarehouseinLosAngelesorbuildawarehouseinSanFrancisco.Theformoftheresultingconstraintisthatthesumofthesevariablesmustbelessthanorequalto1(x3+x4≤1).

9.2-5 Thecontingentdecisionsarethedecisionstobuildawarehouse.Theformsoftheseconstraintsarex3≤x1andx4≤

x2.

9.2-6 Theamountofcapitalbeingmadeavailabletotheseinvestments($10million)isamanagerialdecisiononwhichsensitivityanalysisneedstobeperformed.

9.3-1 Avalueof1isassignedforchoosingyesandavalueof0isassignedforchoosingno.

9.3-2 Yes-or-nodecisionsforcapitalbudgetingwithfixedinvestmentsarewhetherornottomakeacertainfixedinvestment.

9.3-3 Yes-or-nodecisionsforsiteselectionsarewhetherornotacertainsiteshouldbeselectedforthelocationofacertainnewfacility.

9.3-4 Whendesigningaproductionanddistributionnetwork,yes-or-nodecisionslikeshouldacertainplantremainopen,shouldacertainsitebeselectedforanewplant,shouldacertaindistributioncenterremainopen,shouldacertainsitebeselectedforanewdistributioncenter,andshouldacertaindistributioncenterbeassignedtoserveacertainmarketareamightarise.

9.3-5 Shouldacertainroutebeselectedforoneofthetrucks.

9.3-6 ItisestimatedthatChinaissavingabout$6.4billionoverthe15years.

9.3-7 Theformofeachyes-or-nodecisionisshouldacertainassetbesoldinacertaintimeperiod.

9.3-8 TheairlineindustryusesBIPforfleetassignmentproblemsandcrewschedulingproblems.

9.4-1 Abinarydecisionvariableisabinaryvariablethatrepresentsayes-or-nodecision.Anauxiliarybinaryvariableisanadditionalbinaryvariablethatisintroducedintothemodel,nottorepresentayes-or-nodecision,butsimplytohelpformulatethemodelasaBIPproblem.

9.4-2 Thenetprofitisnolongerdirectlyproportionaltothenumberofunitsproducedsoalinearprogrammingformulationisnolongervalid.

9.4-3 Anauxiliarybinaryvariablecanbeintroducedforasetupcostandcanbedefinedas1ifthesetupisperformedtoinitiatetheproductionofacertainproductand0ifthesetupisnotperformed.

9.4-4 Mutuallyexclusiveproductsexistwhenatmostoneproductcanbechosenforproductionduetocompetitionforthesamecustomers.

9.4-5 Anauxiliarybinaryvariablecanbedefinedas1iftheproductcanbeproducedand0iftheproductcannotbeproduced.

9.4-6 Aneither-orconstraintarisesbecausetheproductsaretobeproducedateitherPlant3orPlant4,notboth.

9.4-7 Anauxiliarybinaryvariablecanbedefinedas1ifthefirstconstraintmustholdand0ifthesecondconstraintmusthold.

9.5-1 Restriction1issimilartotherestrictionimposedinVariation2exceptthatitinvolvesmoreproductsandchoices.

9.5-2 Theconstrainty1+y2+y3≤2forceschoosingatmosttwoofthepossiblenewproducts.

9.5-3 ItisnotpossibletowritealegitimateobjectivefunctionbecauseprofitisnotproportionaltothenumberofTVspotsallocatedtothatproduct.

9.5-4 ThegroupsofmutuallyexclusivealternativeinExample2arex1=0,1,2,or3,x2=0,1,2,or3,andx3=0,1,2,or3.

9.5-5 Themathematicalformoftheconstraintisx1+x4+x7+x10≥

1.Thisconstraintsaysthatsequence1,4,7,and10includeanecessaryflightandthatoneofthesequencesmustbechosentoensurethatacrewcoverstheflight.

Problems

9.1 a) Let T=thenumberoftowbarstoproduce

S=thenumberofstabilizerbarstoproduce

MaximizeProfit=$130T+$150S

subjectto 3.2T+2.4S≤16hours

2T+3S≤15hours

and T≥0,S≥0

T,Sareintegers.

b) Optimalsolution:(T,S)=(0,5).Profit=$750.

c)

9.2 a)

b) Let A=thenumberofModelA(high-speed)copierstobuy

B=thenumberofModelB(lower-speed)copierstobuy

MinimizeCost=$6,000A+$4,000B

subjectto A+B≥6copiers

A≥1copier

20,000A+10,000B≥75,000copies/day

and A≥0,B≥

0

A,Bareintegers.

c) Optimalsolution:(A,B)=(2,4).Cost=$28,000.

9.3 a) Optimalsolution:(x1,x2)=(2,3).Profit=13.

b) TheoptimalsolutiontotheLP-relaxationis(x1,x2)=(2.6,1.6).Profit=14.6.

Roundedtothenearestinteger,(x1,x2)=(3,2).Thisisnotfeasiblesinceitviolatesthethirdconstraint.

RoundedSolution

Feasible?

ConstraintViolated

P

(3,2)

No

3rd

-

(3,1)

No

2nd&3rd

-

(2,2)

Yes

-

12

(2,1)

Yes

-

11

Noneoftheseisoptimalfortheintegerprogrammingmodel.TwoarenotfeasibleandtheothertwohavelowervaluesofProfit.

9.4 a) Optimalsolution:(x1,x2)=(2,3).Profit=680.

b) TheoptimalsolutiontotheLP-relaxationis(x1,x2)=(2.67,1.33).Profit=693.33.

Roundedtothenearestinteger,(x1,x2)=(3,1).Thisisnotfeasiblesinceitviolatesthesecondandthirdconstraint.

RoundedSolution

Feasible?

ConstraintViolated

P

(3,1)

No

2nd&3rd

-

(3,2)

No

2nd

-

(2,2)

Yes

-

600

(2,1)

Yes

-

520

Noneoftheseisoptimalfortheintegerprogrammingmodel.TwoarenotfeasibleandtheothertwohavelowervaluesofProfit.

9.5 a)

b) Let L=thenumberoflong-rangejetstopurchase

M=thenumberofmedium-rangejetstopurchase

S=thenumberofshort-rangejetstopurchase

MaximizeAnnualProfit($millions)=4.2L+3M+2.3S

subjectto 67L+50M+35S≤1,500($million)

(5/3)L+(4/3)M+S≤40(maintenancecapacity)

L+M+S≤30(pilotcrews)

and L≥0,M≥

0,S≥

0

L,M,Sareintegers.

9.6 a) Let xij=tonsofgravelhauledfrompititositej(fori=N,S;j=1,2,3)

yij=thenumberoftruckshaulingfrompititositej(fori=N,S;j=1,2,3)

MinimizeCost=$130xN1+$160xN2+$150xN3+$180xS1+$150xS2+$160xS3+

$50yN1+$50yN2+$50yN3+$50yS1+$50yS2+$50yS3

subjectto xN1+xN2+xN3≤18tons(supplyatNorthPit)

xS1+xS2+xS3≤14tons(supplyatSouthPit)

xN1+xS1=10tons(demandatSite1)

xN2+xS2=5tons(demandatSite2)

xN3+xS3=10tons(demandatSite3)

xij≤5yij(fori=N,S;j=1,2,3)(max5tonspertruck)

and xij≥0,yij≥

0,

yijareintegers(fori=N,S;j=1,2,3)

b)

9.7 a) Let FLA=1ifbuildafactoryinLosAngeles;0otherwise

FSF=1ifbuildafactoryinSanFrancisco;0otherwise

FSD=1ifbuildafactoryinSanDiego;0otherwise

WLA=1ifbuildawarehouseinLosAngeles;0otherwise

WSF=1ifbuildawarehouseinSanFrancisco;0otherwise

WSD=1ifbuildawarehouseinSanDiego;0otherwise

MaximizeNPV($million)=9FLA+5FSF+7FSD+6WLA+4WSF+5WSD

subjectto 6FLA+3FSF+4FSD+5WLA+2WSF+3WSD≤

$10million(Capital)

WLA+WSF+WSD≤1warehouse

WLA≤FLA(warehouseonlyiffactory)

WSF≤FSF

WSD≤FSD

and FLA,FSF,FSD,WLA,WSF,WSDarebinaryvariables.

b)

9.8 SeethearticlesinInterfaces.

9.9 a) Let EM=1ifEvedoesthemarketing;0otherwise

EC=1ifEvedoesthecooking;0otherwise

ED=1ifEvedoesthedishwashing;0otherwise

EL=1ifEvedoesthelaundry;0otherwise

SM=1ifStevendoesthemarketing;0otherwise

SC=1ifStevendoesthecooking;0otherwise

SD=1ifStevendoesthedishwashing;0otherwise

SL=1ifStevendoesthelaundry;0otherwise

MinimizeTime(hours)=4.5EM+7.8EC+3.6ED+2.9EL+

4.9SM+7.2SC+4.3SD+3.1SL

subjectto EM+EC+ED+EL=2(eachpersondoes2tasks)

SM+SC+SD+SL=2

EM+SM=1(eachtaskisdoneby1person)

EC+SC=1

ED+SD=1

EL+SL=1

and EM,EC,ED,EL,SM,SC,SD,SLarebinaryvariables.

b)

9.10 a) Let x1=1ifinvestinproject1;0otherwise

x2=1ifinvestinproject2;0otherwise

x3=1ifinvestinproject3;0otherwise

x4=1ifinvestinproject4;0otherwise

x5=1ifinvestinproject5;0otherwise

MaximizeNPV($million)=1x1+1.8x2+1.6x3+0.8x4+1.4x5

subjectto 6x1+12x2+10x3+4x4+8x5≤20($millioncapitalavailable)

and x1,x2,x3,x4,x5arebinaryvariables.

b)

c)

9.11 a)

b)

9.12

Mutuallyexclusivealternatives:

Eachswimmercanonlyswimonestroke.

Eachstrokecanonlybeswumbyoneswimmer.

9.13

9.14

9.15

9.16

Analternativeoptimalsolutionistoproduce3planesforcustomer1and2planesforcustomer2.

9.17

9.18 a) Let yij=1ifxi=j;0otherwise(fori=1,2;andj=1,2,3)

MaximizeProfit=3y11+8y12+9y13+9y21+24y22+9y23

subjectto y11+y12+y13≤1(xicanonlytakeononevalue)

y21+y22+y13≤1

(y11+2y12+3y13)+(y21+2y22+3y23)≤3

and yijarebinaryvariables(fori=1,2;andj=1,2,3)

b)

c) OptimalSolution(x1,x2)=(1,2).Profit=27.

9.19

TheconstraintsinC11:E13aremutuallyexclusivealternative(ateachstage,exactlyonearcisused).TheconstraintsinD6:I8arecontingentdecisions(aroutecanleaveanodeonlyifarouteentersthenode).

9.20

9.21

Thesixequalityconstraints(totalstations=2;onestationassignedtoeachtract)correspondtomutuallyexclusivealternatives.Inaddition,therearethefollowingcontingentdecisionconstraints:eachtractcanonlybeassignedtoastationlocationifthereisastationatthatlocation(D21:D25≤B21:B25;E21:E25≤B21:B25;F21:F25≤B21:B25;G21:G25≤B21:B25;H21:H25≤B21:B25).

9.22 a) Letxi=1ifastationislocatedintracti;0otherwise(fori=1,2,3,4,5)

MinimizeCost($thousand)=200x1+250x2+400x3+300x4+500x5

subjectto x1+x3+x5≥1(stationswithin15minutesoftract1)

x1+x2+x4≥1(stationswithin15minutesoftract2)

x2+x3+x5≥1(stationswithin15minutesoftract3)

x2+x3+x4+x5≥1(stationswithin15minutesoftract4)

x1+x3+x4+x5≥1(stationswithin15minutesoftract5)

and xiarebinaryvariables(fori=1,2,3,4,5).

b)

Cases

9.1 a) Withthisapproach,weneedtoformulateanintegerprogramforeachmonthandoptimizeeachmonthindividually.

Inthefirstmonth,Emilydoesnotbuyanyserverssincenoneofthedepartmentsimplementtheintranetinthefirstmonth.

InthesecondmonthshemustbuycomputerstoensurethattheSalesDepartmentcanstarttheintranet.Emilycanformulateherdecisionproblemasanintegerproblem(theserverspurchasedmustbeinteger.Herobjectiveistominimizethepurchasecost.Shehastosatisfytoconstraints.Shecannotspendmorethan$9500(shestillhasherentirebudgetforthefirsttwomonthssinceshedidn'tbuyanycomputersinthefirstmonth)andthecomputer(s)mustsupportatleast60employees.ShesolvesherintegerprogrammingproblemusingtheExcelsolver.

Note,thatthereisasecondoptimalsolutiontothisintegerprogrammingproblem.ForthesameamountofmoneyEmilycouldbuytwostandardPC'sthatwouldalsosupport60employees.However,sinceEmilyknowsthatsheneedstosupportmoreemployeesinthenearfuture,shedecidestobuytheenhancedPCsinceitsupportsmoreusers.

ForthethirdmonthEmilyneedstosupport260users.Sinceshehasalreadycomputingpowertosupport80users,shenowneedstofigureouthowtosupportadditional180usersatminimumcost.ShecandisregardtheconstraintthattheManufacturingDepartmentneedsoneofthethreelargerservers,sinceshealreadyboughtsuchaserverinthepreviousmonth.Hertaskleadshertothefollowingintegerprogrammingproblemandsolution.

EmilydecidestobuyoneSGIWorkstationinmonth3.Thenetworkisnowabletosupport280users.

InthefourthmonthEmilyneedstosupportatotalof290users.Sinceshehasalreadycomputingpowertosupport280users,shenowneedstofigureouthowtosupportadditional10usersatminimumcost.Thistaskleadshertothefollowingintegerprogrammingproblem:

EmilydecidestobuyastandardPCinthefourthmonth.Thenetworkisnowabletosupport310users.

Finally,inthefifthandlastmonthEmilyneedstosupporttheentirecompanywithatotalof365users.Sinceshehasalreadycomputingpowertosupport310users,shenowneedstofigureouthowtosupportadditional55usersatminimumcost.Thistaskleadshertothefollowingintegerprogrammingproblemandsolution.

EmilydecidestobuyanotherenhancedPCinthefifthmonth.(NotethatagainshecouldhavealsoboughttwostandardPC's,butclearlytheenhancedPCprovidesmoreroomfortheworkloadofthesystemtogrow.)TheentirenetworkofCommuniCorpconsistsnowof1standardPC,2enhancedPC'sand1SGIworkstationanditisabletosupport390users.Thetotalpurchasecostforthisnetworkis$22,500.

b) DuetothebudgetrestrictionanddiscountinthefirsttwomonthsEmilyneedstodistinguishbetweenthecomputersshebuysinthoseearlymonthsandinthelatermonths.Therefore,Emilyusestwovariablesforeachservertype.

Emilyessentiallyfacesfourconstraints.First,shemustsupportthe60usersinthesalesdepartmentinthesecondmonth.Sherealizesthat,sinceshenolongerbuysthecomputerssequentiallyafterthesecondmonth,thatitsufficestoincludeonlytheconstraintonthenetworktosupporttheallusersintheentirecompany.Thissecondconstraintrequireshertosupportatotalof365users.Thethirdconstraintrequireshertobuyatleastoneofthethreelargeservers.Finally,Emilyhastomakesurethatshestayswithinherbudgetduringthesecondmonth.

EmilyshouldpurchaseadiscountedSGIworkstationinthesecondmonth,andanotherregularpricedoneinthethirdmonth.Thetotalpurchasecostis$19,000.

c) Emily'ssecondmethodinpart(b)findsthecostforthebestoverallpurchasepolicy.Themethodinpart(a)onlyfindsthebestpurchasepolicyforthegivenmonth,ignoringthefactthatthedecisioninaparticularmonthhasanimpactonlaterdecisions.Themethodin(a)isveryshort-sightedandthusyieldsaworseresultthatthemethodinpart(b).

d) Installingtheintranetwillincuranumberofothercosts.Thesecostsinclude:

Trainingcost,

Laborcostfornetworkinstallation,

Additionalhardwarecostforcabling,networkinterfacecards,necessaryhubs,etc.,

Salaryandbenefitsforanetworkadministratorandwebmaster,

Costforestablishingoroutsourcinghelpdesksupport.

e) Theintranetandthelocalareanetworkarecompletedeparturesfromthewaybusinesshasbeendoneinthepast.Thedepartmentsmaythereforebeconcernedthatthenewtechnologywilleliminatejobs.Forexample,inthepastthemanufacturingdepartmenthasproducedagreaternumberofpagersthancustomershaveordered.Feweremployeesmaybeneededwhenthemanufacturingdepartmentbeginsproducingonlyenoughpagerstomeetorders.Thedepartmentsmayalsobecometerritorialaboutdataandprocedures,fearingthatanotherdepartmentwillencroachontheirbusiness.Finally,thedepartmentsmaybeconcernedaboutthesecurityoftheirdatawhensendingitoverthenetwork.

9.2 a) Wewanttomaximizethenumberofpiecesdisplayedintheexhibit.Foreachpiece,wethereforeneedtodecidewhetherornotweshoulddisplaythepiece.Eachpiecebecomesabinarydecisionvariable.Thedecisionvariableisassigned1ifwewanttodisplaythepieceandassigned0ifwedonotwanttodisplaythepiece.

Wegroupourconstraintsintofourcategories–theartisticconstraintsimposedbyAsh,thepersonalconstraintsimposedbyAsh,theconstraintsimposedbyCeleste,andthecostconstraint.Wenowstepthrougheachoftheseconstraintcategories.

ArtisticConstraintsImposedbyAsh

Ashimposesthefollowingconstraintsthatdependuponthetypeofartthatisdisplayed.Theconstraintsareasfollows:

1.Ashwantstoincludeonlyonecollage.Wehavefourcollagesavailable:“WastedResources”byNormMarson,“Consumerism”byAngieOldman,“MyNamesake”byZiggyLite,and“Narcissism”byZiggyLite.Aconstraintforcesustoincludeexactlyoneofthesefourpieces(D36=D38inthespreadsheetmodelthatfollows).

2.Ashwantsatleastonewire-meshsculpturedisplayedifacomputer-generateddrawingisdisplayed.Wehavethreewire-meshsculpturesavailableandtwocomputer-generateddrawingsavailable.Thus,ifweincludeeitheroneortwocomputer-generateddrawings,wehavetoincludeatleastonewire-meshsculpture.Therefore,weconstrainthetotalnumberofwire-meshsculptures(total)tobeatleast(1/2)timethetotalnumberofcomputer-generateddrawings(L40≥N40).

3.Ashwantsatleastonecomputer-generateddrawingdisplayedifawire-meshsculptureisdisplayed.Wehavetwocomputer-generateddrawingsavailableandthreewire-meshsculpturesavailable.Thus,ifweincludeone,two,orthreewire-meshsculptures,wehavetoincludeeitheroneortwocomputer-generateddrawings.Therefore,weconstraintthetotalnumberofwire-meshsculptures(total)tobeatleast(1/3)timesthetotalnumberofcomputer-generateddrawings(L41≥N41).

4.Ashwantsatleastonephoto-realisticpaintingdisplayed.Wehavethreephoto-realisticpaintingsavailable:“StorefrontWindow”byDavidLyman,“Harley”byDavidLyman,and“Rick”byRickRawls.Atleastoneofthesethreepaintingshastobedisplayed(G36≥

G38).

5.Ashwantsatleastonecubistpaintingdisplayed.Wehavethreecubistpaintingsavailable:“RickII”byRickRawls,“StudyofaViolin”byHelenRow,and“StudyofaFruitBowl”byHelenRow.Atleastoneofthesethreepaintingshastobedisplayed(H36≥H38).

6.Ashwantsatleastoneexpressionistpaintingdisplayed.Wehaveonlyoneexpressionistpaintingavailable:“RickIII”byRickRawls.Thispaintinghastobedisplayed(I36≥I38).

7.Ashwantsatleastonewatercolorpaintingdisplayed.Wehavesixwatercolorpaintingsavailable:“Serenity”byCandyTate,“CalmBeforetheStorm”byCandyTate,“AllThatGlitters”byAshBriggs,“TheRock”byAshBriggs,“WindingRoad”byAshBriggs,and“DreamsComeTrue”byAshBriggs.Atleastoneofthesesixpaintingshastobedisplayed(J36≥J38).

8.Ashwantsatleastoneoilpaintingdisplayed.Wehavefiveoilpaintingsavailable:“Void”byRobertBayer,“Sun”byRobertBayer,“Beyond”byBillReynolds,“Pioneers”byBillReynolds,and“LivingLand”byBearCanton.Atleastoneofthesefivepaintingshastobedisplayed(K36≥K38).

9.Finally,Ashwantsthenumberofpaintingstobenogreaterthantwicethenumberofotherartforms.Wehave18paintingsavailableand16otherartformsavailable.Weclassifythefollowingpiecesaspaintings:“Serenity,”“CalmBeforetheStorm,”“Void,”“Sun,”“StorefrontWindow,”“Harley,”“Rick,”“RickII,”“RickIII,”“Beyond,”“Pioneers,”“LivingLand,”“StudyofaViolin,”“StudyofaFruitBowl,”“AllThatGlitters,”“TheRock,”“WindingRoad,”and“DreamsComeTrue.”Thetotalnumberofthesepaintingsthatwedisplayhastobelessthanorequaltotwicethetotalnumberofotherartformswedisplay(L42≤N42).

PersonalConstraintsImposedbyAsh

1.Ashwantsallofhisownpaintingsincludedintheexhibit,sowemustinclude“AllThatGlitters,”“TheRock,”“WindingRoad,”and“DreamsComeTrue.”(Inthespreadsheetmodel,weconstraintthetotalnumberofAshpaintingstoequal4:N36=N38.)

2.AshwantsallofCandyTate’sworkincludedintheexhibit,sowemustinclude“Serenity”and“CalmBeforetheStorm.”(Inthespreadsheetmodel,weconstrainthetotalnumberofCandyTateworkstoequal2:O36=O38.)

3.AshwantstoincludeatleastonepiecefromDavidLyman,sowehavetoincludeoneormoreofthepieces“StorefrontWindow”and“Harley”(P36≥P38).

4.AshwantstoincludeatleastonepiecefromRickRawls,sowehavetoincludeoneormoreofthepieces“Rick,”“RickII,”and“RickIII”(Q36≥Q38)

5.AshwantstodisplayasmanypiecesfromDavidLymanasfromRickRawls.ThereforeweconstrainthetotalnumberofDavidLymanworkstoequalthetotalnumberofRickRawlsworks(L43=N43).

6.Finally,AshwantsatmostonepiecefromZiggyLitedisplayed.Wecanthereforeincludenomorethanoneof“MyNamesake”and“Narcissism”(R36≤

R38).

ConstraintsImposedbyCeleste

1.Celestewantstoincludeatleastonepiecefromafemaleartistforeverytwopiecesincludedfromamaleartist.Wehave11piecesbyfemaleartistsavailable:“ChaosReigns”byRitaLosky,“WhoHasControl?”byRitaLosky,“Domestication”byRitaLosky,“Innocence”byRitaLosky,“Serenity”byCandyTate,“CalmBeforetheStorm”byCandyTate,“Consumerism”byAngieOldman,“Reflection”byAngieOldman,“TrojanVictory”byAngieOldman,“StudyofaViolin”byHelenRow,and“StudyofaFruitBowl”byHelenRow.Thetotalnumberofthesepieceshastobegreater-than-or-equal-to(1/2)timesthetotalnumberofpiecesbymaleartists(L44≥N44).

2.Celestewantsatleastoneofthepieces“AgingEarth”and“WastedResources”displayedinordertoadvanceenvironmentalism(V36≥V38).

3.CelestewantstoincludeatleastonepiecebyBearCanton,sowemustincludeoneormoreofthepieces“Wisdom,”“SuperiorPowers,”and“LivingLand”toadvanceNativeAmericanrights(W36≥

W38).

4.Celestewantstoincludeoneormoreofthepieces“ChaosReigns,”“WhoHasControl,”“Beyond,”and“Pioneers”toadvancescience(X36≥X38).

5.Celesteknowsthatthemuseumonlyhasenoughfloorspaceforfoursculptures.Wehavesixsculpturesavailable:“Perfection”byColinZweibell,“Burden”byColinZweibell,“TheGreatEqualizer”byColinZweibell,“AgingEarth”byNormMarson,“Reflection”byAngieOldman,and“TrojanVictory”byAngieOldman.Wecanonlyincludeamaximumoffourofthesesixsculptures(Y36≤Y38).

6.Celestealsoknowsthatthemuseumonlyhasenoughwallspacefor20paintings,collages,anddrawings.Wehave28paintings,collages,anddrawingsavailable:“ChaosReigns,”“WhoHasControl,”“Domestication,”“Innocence,”“WastedResources,”“Serenity,”“CalmBeforetheStorm,”“Void,”“Sun,”“StorefrontWindow,”“Harley,”“Consumerism,”“Rick,”“RickII,”“RickIII,”“Beyond,”“Pioneers,”“Wisdom,”“SuperiorPowers,”“LivingLand,”“StudyofaViolin,”“StudyofaFruitBowl,”“MyNamesake,”“Narcissism,”“AllThatGlitters,”“TheRock,”“WindingRoad,”and“DreamsComeTrue.”Wecanonlyincludeamaximumof20ofthese28wallpieces(Z36≤Z38).

7.Finally,Celestewants“Narcissism”displayedif“Reflection”isdisplayed.Soifthedecisionvariablefor“Reflection”is1,thedecisionvariablefor“Narcissism”mustalsobe1.However,thedecisionvariablefor“Narcissism”canstillbe1evenifthedecisionvariablefor“Reflection”is0(L45≥N45).

CostConstraint

Thecostofallofthepiecesdisplayedhastobelessthanorequalto$4million(C36≤C38).

TheproblemformulationinanExcelspreadsheetfollows.

Intheoptimalsolution,15piecesaredisplayedatacostof$3.95million.Thefollowingpiecesaredisplayed:

1.“TheGreatEqualizer”byColinZweibell

2.“ChaosReigns”byRitaLosky

3.“WastedResources”byNormMarson

4.“Serenity”byCandyTate

5.“CalmBeforetheStorm”byCandyTate

6.“Void”byRobertBayer(or“Sun”byRobertBayer)

7.“Harley”byDavidLyman

8.“Reflection”byAngieOldman

9.“RickIII”byRickRawls

10.“Wisdom”byBearCanton

11.“StudyofaFruitBowl”byHelenRow(or“StudyofaViolin”)

12.“AllThatGlitters”byAshBriggs

13.“TheRock”byAshBriggs

14.“WindingRoad”byAshBriggs

15.“DreamsComeTrue”byAshBriggs

b) Theformulationofthisproblemisthesameastheformulationinpart(a)exceptthattheobjectivefunctionfrompart(a)nowbecomesaconstraintandthecostconstraintfrompart(a)nowbecomestheobjectivefunction.Thus,wehavethenewconstraintthatweneedtoselect20ormorepiecestodisplayintheexhibit.Wealsohavethenewobjectivetominimizethecostoftheexhibit.

ThenewformulationoftheprobleminanExcelfollows.

Intheoptimalsolution,exactly20piecesaredisplayedatacostof$5.45million–$1.45millionmorethanAshdecidedtoallocateinpart(a).Allpiecesfrompart(a)aredisplayedinadditiontothefollowingfivenewpieces:

1.“Perfection”byColinZweibell

2.“Burden”byColinZweibell

3.“Domestication”byRitaLosky

4.“Sun”(or“Void”)byRobertBayer

5.“StudyofaViolin”(or“StudyofaFruitBowl”)byHelenRow

c) Thisproblemisalsoacostminimizationproblem.Theproblemformulationisthesameasthatusedinpart(b).Anewconstraintisadded,however.ThepatronwantsallofRita’spiecesdisplayed.Ritahasfourpieces:“ChaosReigns,”“WhoHasControl?,”“Domestication,”and“Innocence.”Allofthesefourpiecesmustbedisplayed.

TheproblemformulationinEx