Solution Manual for Optimization in Operations Research, 2nd Edition

Preview (16 of 186 Pages)

100%

Purchase to unlock

Loading page image...

1Chapter 1 Solutions121Supplement to the 2nd edition ofOptimization inOperations Research,by Ronald L. Rardin, PearsonHigher Education, Hoboken NJ,○c 2017.2As of June 4, 20151-1.(a)The only unsettled quantity isdecision variables.(b)Given quantities orparameters ared,pandb.(c)Minimize themaximum error, i.e. objective min(d/s)2(d)We must have an integer number of sensorsand not exceed the available budget, i.e.constraintsps≤b,snonnegative and integer.1-2.(a)Feasible because 3.5(4)14≤, andoptimal because any largerswould not befeasible.(b)Infeasible and thus not optimalbecause 3.5(6)/≤14.(c)Feasible because3.5(2)≤14, but not optimal because feasiblesolutions= 4 yields a better objective value.1-3.(a)The only quantities to bedetermined arex1andx2, the numbers of lotson the 2 lines.(b)Given quantities orparameters aret1,t2,c1,c2,bandT.(c)Minimize total production cost or objectiveminc1x1+c2x2.(d)t1x1+t2x2≤T(atmostThours of production),x1+x2=b(produceblots),x1, x2≥0and integer(numbers nonnegative integers).1-4.(a)Infeasible and thus not optimalbecause10(0) + 20(3)/≤40.(b)Feasiblebecause10(2) + 20(1)≤40 and 2 + 1 = 3.Also optimal because no more or lessexpensivex2can be used ifb= 3 lots are torun.(c)Feasible because10(3) + 20(0)≤40and 3 + 0 = 3, but not optimal becausex1= 2,x2= 1yields a lower cost.1-5.(a)Exact numerical optimizationbecause it is the maximum feasible choice forthe given set of parameter values.(b)Descriptive modeling because we have merelyevaluated the consequences of a given choiceof decision variables and parameters.(c)Closed-form optimization because an optimalsolution is specified for each choice of decisionvariables.(d)Heuristic optimization becausea good feasible solution is identified for thegiven choice of parameter values, but anon-usual layout might yield superior results.1-6.(a)Provides optimum for all choices ofinput parameters, not just one.(b)Providesa provably best solution, not just a goodfeasible one.(c)Systematically searches for agood feasible solution, rather than justevaluating the consequences of one.1-7.Higher tractability usually means loss ofvalidity, so results from the model might notbe useful in the application.1-8.(a)(3 for the first)·(3 for the second)·. . .·(3 for thenth) =3ncombinations.(b)One run per second is 3,600 per hour, 86,400per day, 31,536,000 per year. The310= 59,049requires 59,049/3,600 = 16.4hours;315= 14,348,907requires 166.1 days;320≈3.49×109requires 110.6 years; and330≈2.06×1014requires 6.5 million years.(c)Practical computation would be limited toa few days which could accommodate no morethan 10−11 decision variables.1-9.(a)Random variable because short termrainfall is unpredictable.(b)Deterministicquantity because annual rainfall averages arefairly stable.(c)Deterministic quantity be-cause history can be known with certainty.(d)Random variable because future stock marketbehavior is highly uncertain.(e)Deterministicquantity because the seating capacity is fairlyfixed.(f )Random variable because night tonight arrivals are usually variable.(g)Ran-dom variable because breakdowns make the ef-fective production rate uncertain.(h)Deter-ministic quantity because a reliable robot has apredictable rate of production.(i)Determin-istic quantity because short term demand forsuch an expensive product would be fairly wellknown for the next few days.(j)Random vari-able because long term demand for a productis usually uncertain.

Loading page image...

1Chapter 2 Solutions121Supplement to the 2nd edition ofOptimization inOperations Research,by Ronald L. Rardin, PearsonHigher Education, Hoboken NJ,○c 2017.2As of September 24, 20152-1.(a)max200x1+350x2(maxtotalprofit),s.t.5x1+ 5x2≤300(legs),0.6x1+ 1.5x2≤63(assemblyhours),x1≤50(woodtops),x2≤35(glasstops),x1≥0,x2≥0(b)x∗1=basic=30,x∗2=deluxe=30(c)x1x1≤50x2x2≤35≥0x2≥0x15+5x2x1≤300≤.6+1.5x2x1631020304010203040x2x1(*,*) = (30,30)5050max(d)x1x1≤50x2x2≤35≥0x2≥0x15+5x2x1≤300≤.6+1.5x2x16310203040102030405050maxalternative optimaAlloptimalfromx= (30,30)tox= (17.5,35).2-2.(a)max.11x1+.17x2(maxtotalreturn),s.t.x1+x2≤12($12millioninvestment),x1≤10(max$10milliondomestic),x2≤7(max$7millionforeign),x1≥.5x2(domesticatleasthalfforeign),x2≥.5x1(foreignatleasthalfdomestic),x1≥0,x2≥0(b)x∗1=domestic=$5million,x∗2=foreign=$7million(c)x1x248124812x≥01x≥021x≤102x≤712x+x≤1221x≥.5xx≥.5x21optimalsolution(x* ,x* )=(5,7)12max(d)x1248124812x≥01x≥021x≤102x≤712x+x≤1221x≥.5xx≥.5x21maxalternativeoptimaxAlloptimalfromx= (5,7)tox= (8,4).2-3.(a)min3x1+ 5x2(mintotalcost),s.t.x1+x2≥50(atleast50thousandacres),x1≤40(atmost40thousandfromSquawkingEagle),x2≤30(atmost30thousandfromCrookedCreek),x1≥0,x2≥0(b)x∗1=SquawkingEagle=40thousand,x∗2=CrookedCreek=10thousand

Loading page image...

2(c)x1x2255075255075100x+x≤951212x+x≥50x≤302x≥01x≥02x≤401(x* ,x* ) = (40,10)12optimal solutionmin(d)x1x2255075255075100x+x≤951212x+x≥50x≤302minImprovesforeverindirectionΔx1= 1,Δx2=1−.(e)x1x2255075255075100x+x≤951212x+x≥50x≤302x≥01x≥02x≤02x≤401x2=0leavesnofeasible.2-4.(a)maxx1(maxbeefcontent),s.t.x1+x2≥125(weightatleast125),2.5x1+ 1.8x2≤350(caloriesatmost350),0.2x1+ 0.1x2≤15(fatatmost15),3.5x1+ 2.5x2≤360(sodiumatmost360),x1≥0,x2≥0(b)x∗1=beef=25g,x∗2=chicken=100g(c)x1x22550751001251501751020304050x+x≥125122.5x+1.8x≤35012x≥01x≥020.2x+ 0.1x≤15123.5x+ 2.5x≤36012maxoptimal solution(x* ,x* ) = (25,100)12(d)x1x225507510012515017510203040502.5x+1.8x≤35012x≥01x≥020.2x+ 0.1x≤15123.5x+ 2.5x≤3601212x+x≥200x1+x2≥200leavesnofeasible.

Loading page image...

3(e)x1x225507510012515017510203040502.5x+1.8x≤350120.2x+ 0.1x≤15123.5x+ 2.5x≤36012maxImproveforeverindirectionΔx1= 1,Δx2=−2.2-5.(a)max450v+200c(maxtotalprofit),s.t.10v+ 7c≤70000(wateratmost70000units),v+c≤10000(totalacreage10000),v≤7000(atmost70%vegetables),c≤7000(atmost70%cotton),v≥0,c≥0(b)v∗=7000,c∗= 0(c)vc200040006000800020004000600080001000010v+ 7c≤70000v+c≤10000v≥0c≥0v≤7000c≤7000optimal solution (v*,c*) = (7000,0)max(d)vc200040006000800020004000600080001000010v+ 7c≤70000v+c≤10000maxImprovesforeverindirectionΔv=10,Δc=−7.(e)c200040006000800020004000600080001000010v+ 7c≤70000v+c≤10000v≥0c≥0v≤7000c≤7000v+c≥10000Nosolutionwithv+c=10000.2-6.(a)minx1+x2(minusedstock),s.t.5x1+ 3x2≥15(cutatleast15longrolls),2x1+ 5x2≥10(cutatleast10shortrolls),x1≤4(atmost4timesonpattern1),x2≤4(atmost4timesonpattern2),x1, x2≥0andinteger.(b)Partialcutsmakenophysicalsensebecauseallunusedmaterialisscrap.(c)Eitherx∗1=x∗2= 2,orx∗1= 3,x∗2= 1

Loading page image...

4(d)x12x≤41x≥015x+ 3x≥15122x+ 5x≥1012x≤422x≥0alternativeoptimamin1234512345x(e)Both(2,2)and(3,1)arefeasibleandlieonthebestcontouroftheobjective.2-7.(a)min16x1+ 16x2(mintotalwallarea),s.t.x1x2=500(500sqftpool),x1≥2x2(lengthatleasttwicewidth),x2≤15(widthatmost15ft),x1≥0,x2≥0(b)x∗=length=331feet13,x∗=width2=15feet(c)x121020304010203040x≥01x≥2x21x x=500122x≥0x≤15250optimal solution(x* ,x* ) = (33.33,15)12minx(d)x1x21020304010203040x≥01x≥2x21x x=500122x≥0x≤15250x≤251x1≤25leavesnofeasible.2-8.(a)maxx2(maxnumberoffloors),s.t.π/4(x1)2x2=150000(150000sqftfloorspace),10x2≤4x1(height at most4timesdiameter),x10,x20≥≥(b)x∗1=diameter= 78.16feet,x∗2=floors=31.26(c)x12x≥012x≥0204060801002040608010x≤4x12π(x)x=1500001 2214_optimal solution(x* ,x* ) = (78.16,31.26)12maxx(d)x1x2x≥012x≥0204060801002040608010x≤4x12π(x)x=1500001 2214_x≤501x1≤50leavesnofeasible.2-9.(a)(b)minx2(c)minx1+x2(d)maxx2(e)x2≤1/22-10.

Loading page image...

5(a)(b)minx1+x2(c)minx1(d)maxx1(e)x1+x21≤2-11.(a)min4i=3i2j=1yi,j∑∑(b)max∑4i=1iyi,3(c)max∑pi=1αiyi,4(d)min∑ti=1δiyi(e)∑4j=1yi,j=si,i= 1, . . . ,3(f )∑4j=1aj,iyj=ci,i= 1, . . . ,32-12.(a)∑17i=1xi,j,t≤200, j= 1, . . . ,5;t=. . . ,7;35constraints(b)∑5j=1∑7t=1x5,j,t≤4000;1constraint(c)∑5j=1xi,j,t≥100, i= 1, . . . ,17;t= 1, . . . ,7;119constraints2-13.model; param m; param n; paramp; set products := 1 ..m; set lines:= 1 ..n; set weeks := 1 ..p; varx{i in products, j in lines, t inweeks}>= 0;subject to# part (a)linecap{j in lines, t in weeks}:sum{i in products}x[i,j,t]<=200;# part (b)prod5lim:sum{j in lines, t inweeks}x[5,j,t]<=4000;# part (c)minprodn{i in products, t in weeks}:sum{j in lines}x[i,j,t]>=100;#data; param m := 17; param n := 5;param p := 7;2-14.(a)∑9j=1xi,j,t≤pi, i= 1, . . . ,47;t= 1, . . . ,10;470constraints(b)0.25∑47i=1∑9j=1xi,j,t≤∑47i=1xi,4,t;t=1, . . . ,5;5constraints(c)xi,1,t≥xi,j,ti= 1,. . . ,47;j=1, . . . ,9;t= 1, . . . ,10;4230constraints2-15.model; param m; param n; paramq; set plots := 1 ..m; set crops :=1 ..n; set years := 1 ..q; param p{i in plots}; var x{i in plots, jcrops, t in years}>= 0; subject to# part (a)acrelims{i in plots, t in years}:sum{j in crops}x[i,j,t]<=p[i];# part (b)crop4min{t in years:t <= 5}:0.25* sum{i in plots, j in crops}x[i,j,t]<= sum{i in plots}x[i,4,t];# part (c)beam1st{i in plots, j in crops, t inyears}:x[i,1,t]>=x[i,j,t];#data; param m := 47; param n := 9;param q := 10;2-16.(a)f(y1, y2, y3)Δ=(y1)2y2/y3,g1(y1, y2, y3)Δ=y1+y2+y3,b1=13,g2(y1, y2, y3)Δ=2y1−y2+ 9y3,b2= 0,g3(y1, y2, y3)Δ=y1,b3= 0,g4(y1, y2, y3)Δ=y3,b4= 0(b)f(y1, y2, y3)Δ=13y1+ 22y2+ 10y2y3+ 100,g1(y1, yΔ2, y3)=y1−y2+ 9y3,b1=−5,g2(y1, y2, y3)Δ=8y2−4y3,b2= 0,g3(y1, y2, y3)Δ=y1,b3= 0,g4(yΔ1, y2, y3)=y2,b4= 0,g(yΔ51, y2, y3=y3,b5= 0,2-17.(a)LinearbecauseLHSisaweightedsumofthedecisionvariables.(b)LinearbecausebothLHSandRHSareweightedsumsofthedecisionvariables.(c)NonlinearbecauseLHShasreciprocal1/x9.(d)LinearbecauseLHSisaweightedsumofthedecisionvariables.(e)NonlinearbecauseLHShas(xj)2terms.(f )NonlinearbecauseLHShaslog(x1)term,andRHShasaproductof

Loading page image...

6variables.(g)NonlinearbecauseLHShasmaxoperator.(h)LinearbecauseLHSisaweightedsumofthedecisionvariables.2-18.(a)LPbecausetheobjectiveandallconstraintsarelinear.(b)NLPbecauseofthenonlinearobjectivefunctionwithreciprocalofw2.(c)NLPbecauseofthenonlinearfirstconstraint.(d)LPbecausetheobjectiveandallconstraintsarelinear.2-19.(a)Continuousbecausefractionsmakesense.(b)Discretebecausetheyeitherclosedornot.(c)Discretebecauseaspecificprocessmustbeused.(d)Continuousbecausefractionscanprobablybeignored.2-20.(a)8∑j=1xj= 3(b)x1+x2+x4+x5≥2(c)x3+x8≤1(d)x4x1≥2-21.(a)max85x1+ 70x2+ 62x3+ 93x4(maxtotalscore),s.t.700x1+400x2+300x3+600x4≤1000($1millionavailable),xj= 0or1, j= 1, . . . ,4(b)Fund2and4,i.e.x∗1=x∗3= 0,x∗2=x∗4= 12-22.(a)min43y1+175y2+ 60y3+ 35y4(mintotallandcost),s.t.y2+y4≥1(serviceNW),y1+y2+y4≥1(serviceSW),y2+y3≥1(servicecapital),y1+y4≥1(serviceNE),y1+y2+y3≥1(serviceSE),yj= 0or1, j= 1, . . . ,4(b)Build3and4,i.e.y1∗=y2∗= 0,y3∗=y4∗= 12-23.(a)ILPbecausetheobjectiveandallconstraintsarelinear,butvariablesarediscrete.(b)NLPbecausetheobjectiveisnonlinearandallvariablesarecontinuous.(c)INLPbecausetheobjectiveisnonlinearandvariablesarediscrete.(d)LPbecausetheobjectiveandallconstraintsarelinear,andallvariablesarecontinuous.(e)INLPbecausetheoneconstraintisnonlinear,andz3arediscrete.(f )ILPbecausetheobjectiveandallconstraintsarelinear,butvariablesz1andz3arediscrete.(g)LPbecausetheobjectiveandallconstraintsarelinear,andallvariablesarecontinuous.(h)INLPbecausetheobjectiveisnonlinearandz3isdiscrete.2-24.(a)Model(d)becauseLP’saregenerallymoretractablethanILP’s.(b)Model(d)becauseLP’saregenerallymoretractablethanNLP’s.(c)Model(d)becauseLP’saregenerallymoretractablethanINLP’s.(d)Model(f)becauseILP’saregenerallymoretractablethanINLP’s.(e)Model(g)becauseLP’saregeneratllymoretranctablethanILP’s.2-25.(a)x1x241216481216x≤81x≥02x≥01-x+x≤412maxalternativeoptimalsolutionsAlternativeoptimafromx∗1= 8,x∗2= 0tox∗1= 8,x∗2= 12(b)x1x241216481216x≤81x≥02x≥01-x+x≤412maxoptimal solution (x* ,x* ) = (0,4)12Uniqueoptimumx∗1= 0,x∗2= 4(c)Helpingonecanhurttheother.2-26.

Loading page image...

7(a)Uniqueoptimumx∗1= 4,x∗2= 0(b)Uniqueoptimumx∗1= 0,x∗2= 4(c)Helpingonecanhurttheother.2-27.(a)min.092x4+.112x5+.141x6+.420x9+.719x12(mintotalcost),s.t.x4+x5+x6+x9+x12=16000(16000mline),.279x4+.160x5+.120x6+.065x9+.039x12≤1600(atmost1600Ohmsresistance),.00175x4+.00130x5+.00161x6+.00095x9+.00048x12≤8.5(atmost8.5dBellattenuation),x4, x5, x6, x9, x12≥0(b)Nonzeros:x∗5=1000,x∗12=150002-28.(a)Pumpratesarethedecisionstobemade.(b)uΔj=thecapacityofpumpj,cΔj=thepumpingcostofpumpj(c)min∑10j=1cjxj(d)x1+x4+x7≤3000(well1),x2+x5+x8≤2500(well2),x3+x6+x9+x10≤7000(well3)(e)xj≤uj,j= 1, . . . ,10(f )∑10j=1xj≥10000(g)xj≥0,j= 1, . . . ,10(h)AsingleobjectiveLPbecausetheoneobjectiveandallconstraintsarelinear,andallvariablesarecontinuous.(i)x∗1=x∗2=x∗3=1100,x∗4=x∗6=1500,x∗5=1400,x∗7=400¡x∗8=x∗10= 0,x∗9=19002-29.(a)Thedecisionstobemadearewhichprojectstoundertake.(b)pΔj=theprofitforprojectj,mΔj=theman-daysrequiredonprojectj, andtΔj=theCPUtimerequiredonprojectj.(c)max∑8j=1pjxj(d)7≤(∑8j=1mjxj)/240≤10(e)∑8j=1tjxj≤1000(computertime),∑8j=1xj≥3(selectatleast3);x3+x4+x5+x8≥1(includeatleast1ofdirector’sfavorites)(f )xj= 0or1,j= 1, . . . ,8(g)AsingleobjectiveILPbecausetheoneobjectiveandallconstraintsarelinear,butvariablesarediscrete.(h)x∗1=x∗3=x∗6=x∗7= 1,others=02-30.(a)Wemustdecidewhatquantitiestomovefromsurplussitestofulfilleachneed.(b)sΔi=thesupplyavailableati,rΔj=thequantityneededatj,dΔi,j=thedistancefromitoj.(c)min∑4i=1∑7j=1di,jxi,j(d)7∑j=1xi,j=si,i= 1, . . . ,4(e)∑4i=1xi,j=rj,j= 1, . . . ,7(f )xi,j≥0,i= 1, . . . ,4,j= 1, . . . ,7(g)AsingleobjectiveLPbecausetheoneobjectiveandallconstraintsarelinear,andallvariablesarecontinuous.(h)Nonzeros:x∗1,1=81,x∗1,2=93,x∗1,3=166,x∗1,5=90,x∗1,6=85,x∗1,7=145,x∗2,2=301,x∗3,1=166,x∗3,4=105,x∗4,3= 992-31.(a)Thevaluestobechosenarethe

Loading page image...

8coefficientsintheestimatingrelationship.(b)minnj=1(cj−k/(1+ea+bfj))2∑(mintotalsquarederror)(c)SingleobjectiveNLPbecausetheobjectiveisquadratic,therearenoconstraints,andallvariablesarecontinuous.2-32.(a)The decisionstobe made arewheretoassigneachteacher.(b)min22∑i=1∑22j=1ci,jxi,j(mintotalcost),max∑2222i=1∑j=1ti,jxi,j(maxtotalteacherpreference),max∑22i=1∑22j=1si,jxi,j(maxtotalsupervisorpreference),max∑22i=1∑22j=1pi,jxi,j(maxtotalprincipalpreference)(c)∑22j=1xi,j= 1,i= 1, . . . ,22(eachteacheri)(d)∑22i=1xi,j= 1,j= 1, . . . ,22(eachschoolj)(e)xi,j= 0or1,i, j= 1, . . . ,22(f )AmultiobjectiveILPbecausethe4objectivesandallconstraintsarelinear,butvariablesarediscrete.2-33.(a)EachtaskmustgotoAssistant0orAssistant1.(b)max100(1−x1) +80x1+85(1−x2) +70x2+40(1−x3) + 90x3+45(1−x4) +85x4+70(1−x5) + 80x5+82(1−x6) + 65x66j=1xj= 3∑(c)(d)x5=x6(e)xj= 0or1,j= 1, . . . ,6(f )AsingleobjectiveILPbecausetheoneobjectiveandallconstraintsarelinear,butvariablesarediscrete.(g)x∗2=x∗3=x∗4= 1,others=02-34.(a)Batchsizesarethedecisionstobemade.(b)minxj/dj,j= 1, . . . ,4(eachburgerj)(c)∑4j=1tjdj/xj≤60(d)0≤xj≤uj,j= 1, . . . ,4(e)MultiobjectiveNLPbecausethefirstconstraintisnonlinearandallvariablesarecontinuous.2-35.(a)Theissueishowmanycarstomovefromwheretowhere.(b)Relativelylargevaluescanberoundediffractionalwithoutmuchloss,andcontinuousismoretractable.(c)cΔi,j=thecostofmovingacarfromitoj,pΔj=thenumberofcarspresentlyatj,nΔj=thenumberofcarsrequiredatj(d)min∑5i=1∑5j=1,j=ici,jxi,j(e)∑5i=1,i=kxi,k−5j=1,j=kxk,j=nk−pk∑,k= 1, . . . ,5(eachregionk)(f )xi,j≥0,i, j= 1, . . . ,5,i=j(g)AsingleobjectiveLPbecausetheoneobjectiveandallconstraintsarelinear,andallvariablesarecontinuous.(h)Nonzerovalues:x∗4,2=115,x∗4,3=165,x∗5,1=85,x∗5,3=225////2-36.(a)Wemustdecidehowmuchofwhatfueltoburnateachplant.(b)min∑4f=1∑23p=1cf,pxf,p(c)min∑4f=1sf∑23p=1xf,p(d)4∑f=1efxf,p≥rp,p= 1, . . . ,23(eachplantp);23constraints(e)xf,p≥0,f= 1, . . . ,4,p= 1, . . . ,23;92constraints(f )AmultiobjectiveLPbecausethe2objectivesandallconstraintsarelinear,andallvariablesarecontinuous.2-37.(a)Theavailableoptionsaretobuywholelogsorgreenlumber.(b)Relativelylargemagnitudescanberoundedwithoutmuchloss,andcontinuousismoretractable.(c)min70x10+200x15+620x20+ 1.55y1+ 1.30y2(d)100(.09)x10+240(.09)x15+400(.09)x20+.10y1+.08y2≥2350(e)x10+x15+x20≤1500(sawingcapacity),100x10+240x15+400x20+y1+y2≤26500(dryingcapacity)(f )x10≤50(size10logavailability),x15≤25(size15logavailability),x20≤10(size20logavailability),y1≤5000(grade1greenlumberavailability)(g)x10, x15, x20, y1, y2≥0(h)AsingleobjectiveLPbecausetheone

Loading page image...

9objectiveandallconstraintsarelinear,andallvariablesarecontinuous.(i)x∗10=50,x∗15=25,x∗20= 5,y1∗=5000,y2∗=85002-38.(a)Decisionstobemadearewhentoscheduleeachfilm.(b)m−1mnminj=1j′=j+1aj,j′t=1xj,txj′,t∑∑∑(c)∑nt=1xj,t= 1,j= 1, . . . , m(eachfilmj)(d)mj=1xj,t≤4∑,t= 1, . . . , n(eachtimet)(e)xj,t= 0or1,j= 1, . . . , m;t= 1, . . . , n(f )AsingleobjectiveINLPbecausetheoneobjectiveisnonlinear,andvariablesarediscrete.(g)model; param m; param n;set films := 1 ..m; set slots := 1..n; var x{j in films, t in slots}binary; param a{j in films, jp infilms}; minimize totconflict:sum{jin films, jp in films:j < m and jp >j}a[j,jp]*sum{t in slots}x[j,t]*x[jp,t]; subject to allin{j infilms}:sum{t in slots}x[j,t] = 1;max4{t in slots}:sum{j in films}x[j,t]<=4;2-39.(a)Weneedtodecidebothwhichofficestoopenandhowtoservicecustomersfromthem.(b)Officesmusteitherbeopenedornot.(c)fΔi=fixedcostofsitei,cΔi,j=unitcostofauditsatjfromi,rΔj=requirednumberofauditsinstatej(d)555mini=1j=1ci,jrjxi,j+i=1fiyi∑∑∑(e)∑5i=1xi,j= 1,j= 1, . . . ,5(eachlocationj)(f )xi,j≤yi,i, j= 1, . . . ,5 (eachsitei,locationjcombination)(g)xi,j≥0,i, j= 1, . . . ,5,yi= 0or1,i= 1, . . . ,5(h)AsingleobjectiveILPbecausetheoneobjectiveandallconstraintsarelinear,buttheyivariablesarediscrete.(i)Nonzeros:x∗2,2=x∗2,4=x∗3,1=x∗3,3=x∗5,5= 1,y2∗=y3∗=y5∗= 1(j)model; param m;param n; set sites := 1 ..m; setstates := 1 ..n; var x{i in sites, jin states}>= 0; var y{i in sites}binary; param c{i in sites, j instates}; param f{i in sites}binary; param r{j in states};minimize totcost:sum{i in sites, jin states}c[i,j]*r[j]*x[i,j] + sum{iin sites}f[i]*y[i]; x[j,t]*x[jp,t];subject to doeach{j in states}:sum{iin sites}x[i,j] = 1; switch{i insites, j in states}:x[i,j] <= y[i];data; param m := 5; param n := 5;param f := 1 160 2 49 3 246 4 86 4100; param r := 1 200 2 100 3 300 4100 5 200; param c:1 2 3 4 5 := 10.0 0.4 0.8 0.4 0.8 2 0.7 0.0 0.8 0.40.4 3 0.6 0.4 0.0 0.5 0.4 4 0.6 0.40.9 0.0 0.4 5 0.9 0.4 0.7 0.4 0.0 ;2-40.(a)8max∑j=1rjxj,subjectto,∑8j=1xj≤4,x1+x2+x3≥2,x4+x5+x6+x7+x8≥1,x2+x3+x4+x8≥2,x1. . . x8= 0or1(b)model; param n ;set games := 1 ..n;#ratings param r{j in games}; #home?param h{j in games}; #state?params{j in games}; #cover?var x{j ingames}binary; maximize totrat:sum{jin games}r[j]*x[j]; subject tocapacity:sum{j in games}x[j] <= 4;home:sum{j in games}h[j]*x[j] >= 2;away:sum{j in games}(1-h[j])* x[j]>= 1; state:sum{j in games}s[j]*x[j]>= 2; data; param n := 8; param r :=13.0 2 3.7 3 2.6 4 1.8 5 1.5 6 1.3 71.6 8 2.0; param h:=1 12 1 3 1 4 0 50 6 0 7 0 8 0; param s:=10 2 1 3 1 41 5 0 6 0 7 0 8 1;(c)ThemodelisanILPbecauseallconstraintsandtheobjectivearelinear,butdecisionvariablesarebinary.2-41.(a)Howtodividefundsistheissue.(b)max∑nj=1vjxj(c)min∑nj=1rjxj(d)∑nj=1xj= 1(e)xj≥ℓj,j= 1, . . . , n(eachcategoryj)

Loading page image...

10(f )xj≤uj,j= 1, . . . , n(eachcategoryj)(g)AmultiobjectiveLPbecausethe2objectivesandallconstraintsarelinear,andallvariablesarecontinuous.2-42.(a)Theissueiswhichmodulegoestowhichsite.(b)Ifxi,jxi′,j′= 1theiisatjandi′isatj′,sowiredj,j′willberequired.Summingoverallpossiblelocationpairscapturesthewirerequirementsforiandi′.(c)min∑m−1i=1∑mnni=i+1ad′i,i′∑j=1∑j′=1j,j′xi,jxi′,j′(d)n∑j=1xi,j= 1,i= 1, . . . , m(eachmodulei)(e)∑mi=1xi,j≤1,j= 1, . . . , n(eachsitej)(f )xi,j=0or1,i= 1, . . . , m,j= 1, . . . , n(g)SingleobjectiveINLPbecausetheoneobjectiveisnonlinearandvariablesarediscrete.(h)model; param m; param n;set modules := 1 ..m; set sites := 1..n; var x{i in modules, j in sites}binary; param a{i in modules, ip inmodules}; param d{j in sites, jp insites}; minimize totdist:sum{i inmodules, ip in modules:i < m and ip> i}a[i,ip] sum{j in sites, jp insites :j < n and jp > j}d[j,jp]*x[i,j]*x[ip,jp]; subject toalli{i in modules}:sum{j in sites}x[i,j] = 1; allj{j in sites}:sum{i in modules}x[i,j] <= 1;2-43.max 199x1+229x2+188x3+205x4−180y1−224y2−497y3,subjectto,23x3+ 41x4≤2877y1, 14x1+ 29x2≤2333y2,11x3+ 27x4≤3011y3,x1+x2+x3+x4≥205,y1+y2+y3≤2,x1, . . . , x4≥0,y1, . . . , y3= 0or12-44.max 11x1,1+ 15x1,2+ 19x1,3+ 10x1,4+19x2,1+ 23x2,2+ 44x2,3+ 67x2,4+ 17x3,1+18x3,2+ 24x3,3+ 55x3,4, subjectto, 15x1,1+24x2,1+ 17x3,1≤7600,19x1,2+ 26x2,2+13x3,2≤8200,23x1,3+ 18x2,3+ 16x3,3≤6015,14x1,4+33x2,4+14x3,4≤5000,31x1,1+26x2,1+21x3,1≤6600,25x1,2+ 28x2,2+ 17x3,2≤7900,39x1,3+ 22x2,3+ 20x3,2≤5055,29x1,4+31x2,4+ 18x3,4≤7777,x1,1+x2,1+x3,1≥200,x1,2+x2,2+x3,2≥300,x1,3+x2,3+x3,3≥250,x1,4+x2,4+x3,4≥500,xj,t≥0,j=1, . . .3, t= 1, . . .4.

Loading page image...

1Chapter 3 Solutions121Supplement to the 2nd edition ofOptimization inOperations Research,by Ronald L. Rardin, PearsonHigher Education, Hoboken NJ,c 2017.○2As of October 1, 20153-1.(a)x(1)isfeasibleandonlyalocalmaxbecauseallconstraintsaresatisfiedandnonearbypointhasbetterobjectivevalue,buttherearebettersuchas(1,3).x(2)isinfeasibleandthusnosortofoptimumbecauseitviolatesconstraintx2≥0.x(3)isfeasiblebecauseitsatisfiesallconstraints,butnosortofoptimumbecauseitcanbeimprovedintheneighborhood.x(4)isfeasibleandbothalocalandaglobalmaxbecauseitsatisfiesallconstraintsandhasbetterobjectivevaluethananyotherpointinthefeasibleregion.(b)x(1)isinfeasibleandthusnosortofoptimumbecauseitviolatesconstraintx1+x2≤4.x(2)isfeasiblebecauseitsatisfiesallconstraints,butnokindofoptimumbecauseitcanbeimprovedinavarietyofdirections.x(3)isfeasibleandalocalminimumbecauseitcannotbeimprovedintheneighborhood,butnotglobalbecauseotherfeasiblepointssuchasx(4)havebetterobjectivevalues.x(4)isfeasibleandbothalocalandaglobalminimumbecauseitsatisfiesallconstraintsandhasbetterobjectivevaluethananyotherpointinthefeasibleregion.3-2.(a)y(1)= (2,0,5)+2(3,1,0)=(8,2,5),−−y(2)= (8,−2,5)+5(−1,2,1)=(3,8,10),(3)y= (3,8,10)+1/2(0,6,0)=(3,11,10)(b)y(1)= (2,0,5)+2(1,3,−2)=(4,6,1),y(2)= (4,6,1)+1/2(1,0,2)=(41/2,6,2),y(3)= (41/2,6,2)+12(4,3,2)=(521/2,42,26)3-3.(a)Δw(1)= (4,−1,7)−(0,1,1)=(4,−2,6),Δw(2)= (4,−3,19)−(4,−1,7)=(0,−2,8),(3)Δw= (3,−3,22)−(4,−3,19)=(−1,0,3)(b)Δw(1)= (4,2,10)−(4,0,7)=(0,2,3),Δw(2)= (2,4,5)(4,2,10)=(6,2,5),−−−Δw(3)= (5,5,5)(2,4,5)=(7,1,0)−−3-4.(a)Nonimprovingbecausetheobjectivevalueworsensintheneighborhoodalongthisdirection.(b)Nonimprovingbecausetheobjectivedecreasesintheneighborhoodalongthisdirection.(c)Improvingbecausetheobjectiveimprovesintheneighborhoodalongthisdirection.(d)Improvingbecausetheobjectiveimprovesintheneighborhoodalongthisdirection.(e)Nonimprovingbecausex(3)isalocalminimum.(f )Improvingbecausetheobjectivevalueimprovesintheneighborhoodalongthisdirection.3-5.(a)Feasiblebecausemovementalongthisdirectionretainsfeasibilityintheneighborhood.(b)Infeasiblebecauseanymovementalongthisdirectionproducesinfeasibility.(c)Feasiblebecausemovementalongthisdirectionretainsfeasibilityintheneighborhood.(d)Feasiblebecausemovementalongthisdirectionretainsequalityoftheonlyactiveconstraint.(e)Feasiblebecauseanymovementalongthisdirectionviolatesnoconstraintsimmediately.(f )Infeasiblebecausemovementalongthisdirectionimmediatelyviolatesx2≥0.3-6.(a)(4−1λ)−2(0 + 3λ) + 3(6−2λ)≤25issatisfiedforallpositiveλ;(4−1λ)≥0issatisfiedforλ≤4;(0 + 3λ)≥0issatisfiedforallpositiveλ;(6−3λ)≥0issatisfiedforλ≤3.Thustheproperstepisλ= min4,3=3{}.Themodelisnotunboundedbecausethisλisfinite.(b)(8−2λ)−2(5 + 1λ) + 3(3−1λ)≤25issatisfiedforallpositiveλ;(8−2λ)≥0issatisfiedforλ≤4;(5 + 1λ)≥0issatisfiedforallpositiveλ;(3−1λ)≥0issatisfiedforλ≤3.Thustheproperstepisλ= min{4,3}=3.Themodelisnotunboundedbecausethisλisfinite.(c)(0 + 1λ)−2(0 + 3λ)+ 3(4 + 1λ)≤25issatisfiedforallpositiveλ;(0+1λ)≥0issatisfiedforallpositiveλ;(0+3λ)≥0is

Loading page image...

2satisfiedforallpositiveλ;(4 + 1λ)≥0issatisfiedforallpositiveλ. Thusλ= +∞, andthemodelisunbounded.(d)(20 + 2λ)−2(4 + 7λ) + 3(3 + 4λ)≤25issatisfiedforallpositiveλ;(20 + 2λ)≥0issatisfiedforallpositiveλ;(4 + 7λ)≥0issatisfiedforallpositiveλ;(3 + 4λ)≥0issatisfiedforallpositiveλ.Thusthemodelisunboundedbecausestepsinthisdirectioncanbearbitrarilylargewithoutlosingfeasibility.3-7.(a)∇f(2,−3,4,0,6)=(4,0,−2,0,1)and∇f·Δy=(4,0,−2,0,1)·(2,−3,4,0,6)=6,soimprovingforamaximize.(b)∇f(1,0,9,0,0)=(1,0,7,0,2)and∇f·Δy= (1,0,7,0,2)·(−1−,−20,2,0,4)=7>0,soimprovingforamaximize.(c)∇f(3,−1)=(−1 + 2(3),3 + 4)and∇f·Δy= (5,7)·(−7,5)=0,somoreinformationisneeded.(d)∇f(2,1)=(2(2)+1,2+4)and∇f·Δy= (5,6)·(−1,3)=13<0,sononimprovingforaminimize.(e)∇f(4,1)=(2(4−5),2(1+1))and∇f·Δy= (−2,4)·(−1,2)=12>0,soimprovingforamaximize.(f )∇f(1,1)=(2(1−2)+1,1 +2(1−3))and∇f·Δy= (−1,−3)·(3,−1)=0,somoreinformationisneeded.3-8.(a)Δw=∇f(2,0,5,1)=(3,−2,0,1)(b)Δw=−∇f(2,2,1,0)=(0,4,−5,1)(c)Δw=−∇f(3,2)=−(2(3+2)−2,−3)=(−8,3)(d)Δw=∇f(11,2)=(−4,9+4(2))=(−4,17)3-9.(a)2(4−2)+ (0−1)2= 5<10so[i]isinactive;2(4)−(0)=8so[ii]isactive;(4)>0so[iii]isinactive;(0)=0so[iv]isactive.(b)(6−2)2+ (4−1)2=25so[i]isactive;2(6)−(4)=8so[ii]isactive;(6)>0so[iii]inactive;(4)>0so[iv]inactive.3-10.(a)Activeconstraintsare3y12y2+ 8y3= 14andy20.−≥Forthesea(1)·Δy= 3,−2,8)·(0,4,1)=0anda(4)·Δy= 0,1,0)·(0,4,1)=4≥0as/requiredforfeasibility.(b)Activeconstraintsare3y1−2y2+ 8y3= 14andy2≥0.Forthese)a(1·Δy= (3,−2,8)·(0,−4,1)=16,infeasibleforan=constraint.a(4)·Δy=(0,1,0)·(0,−4,1)=−4≥0infeasiblefora≥constraint.(c)Activeconstraintsare3y1−2y2+ 8y3=,14andy1≥0.Inthefirsta(1)·Δy= (3,−2,8)·(2,0,1)=14= 0asrequiredsoinfeasible.(d)Activeconstraintsare3y1−2y2+ 8y3=14andy1≥0.Forthesea(1)·Δy= (3,−2,8)·(−2,1,1)=0asrequiredforfeasibilityofan=constraint.a(3)·Δy= (1,0,0)·(−2,1,1)=−2infeasibleforea≥0constraint./3-11.(a)Activeconstraintsare2w1+ 3w3=18,1w1+ 1w2+ 2w3=14,andw1≥0.Thusconditionsare2 Δw1+ 3 Δw3= 0,1 Δw1+ 1 Δw2+ 2 Δw3= 0,Δw1≥0(b)Activeconstraintsare2w1+ 3w3=18,and1w1+ 1w2+ 2w3=14.Thusconditionsare2 Δw1+ 3 Δw3= 0,1 Δw1+ 1 Δw2+ 2 Δw3= 0,(c)Activeconstraintsare1w1+ 1w2= 10and2w1−1w2≥8.Thusconditionsare1 Δw1+ 1 Δw2= 0,2 Δw1−1 Δw2≥0(d)Onlyactiveconstraintis1w1+ 1w2=10.Thusconditionsare1 Δw1+ 1 Δw2= 0,3-12.(a)−1 Δy1+ 5 Δy2<0(b)Directsubstitution(c)Activeconstraintsarey1≥0and−y1+y2≤3.(d)Activeconstraintsyieldconditions1 Δy1+ 0 Δy2≥0,−1 Δy1+ 1 Δy2≤0.(e)Directsupstitutionshowsdirectionisfeasible.Maximumstepisλ=1whereconstrainty2≥0isencountered.

Loading page image...

3(f )3-13.(a)3 Δx1−13 Δx3<0(b)3(−1)−13(2)=−16<0asrequired.(c)Onlyfirstconstraintwith11(3)+4(9)=69,andfourthconstraintx2=0areactiveat(3,0,9).(d)11 Δx1+ 3 Δx2+ 4 Δx3= 0andΔx2≥0.(e)Directsubstitution;Checkinglimitsonλ,(3−1λ) + (0 + 1λ) + (9 + 2λ)≤16givesλ≤2,3−1λ≥0givesλ≤3.Combiningλ←min{2,3}= 2.Thenx(2)←(3−2,0 +2,9 + 4)=(1,2,13)3-14.(a)∇f·Δz(1)= (4,7)·(2,0)=8>0and∇f·Δz(2)= (4,7)·(−2,4)=20>0asrequiredforimprovingdirectionsinamaximize.(b)Withbothdirectionsimprovingatallz,theonlyconsiderationsarewhendirectionsarefeasible.Atz(0)= (0,0),onlyΔz(1)isfeasiblebecauseΔz(2)hasa·Δz(2)= (1,0)·(−2,4)=−2/≥0foractivez1≥0.Amaximumfeasiblestepfollows(Δz1)forλ= 2toz(1)= (4,0).Atz(1)= (4,0),furtherpursuitofΔz(1)isinfeasible,butΔz(2)= (−2,4)isfeasible.AmaximumfeasiblestepfollowsΔz(2)forλ= 3/4 toz(2)= (5/2,3).Atz(2)= (5/2,3),furtherpursuitofΔz(2)isinfeasible,butΔz(1)= (2,0)isagainfeasible.AmaximumfeasiblestepfollowsΔz(1)forλ= 1/4toz(3)= (3,3).Atz(3),bothdirectionsareinfeasible,andthesearchterminates.(c)z1z21231232z≥01z≥02z≤4122z+z≤9z= (0,0)(0)z= (4,0)(1)z= (5/2,3)(2)z= (3,3)(3)1z≤4max3-15.(a)∇f·Δz(1)= (1,1)(0,−5)=−5<0·and(∇f·Δz2)= (1,1)·(2,1)=−2<−0asrequiredforaminimize.(b)Withbothdirectionsimprovingatallz, theonlyconsiderationsarewhendirectionsarefeasible.Atz(0)= (5,3),onlyΔz(1)isfeasiblebecauseΔz(2)hasa·Δz(2)= (0,1)·(−2,1)=1/≤0foractivez2≤3.AmaximumfeasiblestepfollowsΔz(1)forλ= 3/5toz(1)= (5,0).Atz(1)= (5,0),furtherpursuitofΔz(1)isinfeasible,butΔz(2)= (−2,1)isnowfeasible.AmaximumfeasiblestepfollowsΔz(2)forλ= 5/2toz(2)= (0,5/2).Atz(2)= (0,5/2),furtherpursuitofΔz(2)isinfeasible,butΔz(1)= (0,−5isagainfeasible.AmaximumfeasiblestepfollowsΔz(1)forλ= 1/10toz(3)= (0,2).Atz(3),bothdirectionsareinfeasible,andthesearchterminates.(c)12312345z21z12z+z≥42z≥01z≥01z≤52z≤3z= (5,0)(1)z= (0,5/2)(2)z= (0,2)(3)z= (5,3)(0)min3-16.(a)(3,1,0)+λ(−3,3,9),λ∈[0,1].Settingλ= 1/3inthisexpressionyieldsz(3);noλgivesz(4).(b)(6,4,4)+λ(4,−4,3),λ∈[0,1].Settingλ= 3/4inthisexpressionyieldsz(3); noλgivesz(4).3-17.

Loading page image...

4(a)x1x224241x≥02x≥0681068violationx+x≤101212(x) + (x)≥922Fromthegraph,thesetisnotconvexbecausepartofthelinesegmentfromx(1)= (0,3)tox(2)= (3,0)liesoutsidethefeasibleregion.(b)Fromthegraph,thesetisconvexbecausethelinesegmentbetweeneverypairoffeasiblesolutionsliesentirelywithinthefeasibleregion.(c)Convexbecauseallconstraintsarelinear.(d)Convexbecauseallconstraintsarelinear.(e)Notconvexbecausefractionalsolutionsbetweensayx(1)= (0,0,0,4)andx(2)= (0,0,0,5)areinfeasible.(f )Notconvexbecausefractionalsolutionsbetweentheallxj= 1andallxj= 0solutionsareinfeasible.3-18.(a)Onlythefirstandthirdconstraintsareviolatedatw=0.Addingnonnegativeartificialvariablesw4inthefirstandw5inthethird,andminimizingtheirsum,producesPhaseImodel:minw4+w5,s.t.40w1+ 30w2+ 10w3+w4=150,w1−w2≤0,4w2+w3+w5≥10,w1, w2, w3, w4, w5≥0.Settingw4=150−40(0)−30(0)−10(0)=150andw5= 10−4(0)−(0)=10(oranyhighervalue)completesastarting(artificially)feasiblesolution.(b)Onlythesecondandthirdconstraintsareviolatedatw=0.Addingnonnegativeartificialvariablew3inthesecond,andw4inthethird,thenminimizingtheirsum,producesPhaseImodel:minw3+w4,s.t.−w1+w2≤3,w2+w3≥2,w2+w4≥w1+ 1,w1, w2, w3, w4≥0.Settingw3= 2andw4= 1(oranyhighervalues),completesastarting(artificially)feasiblesolution.

Preview Mode

This document has 186 pages. Sign in to access the full document!

Report

Study Now!

Document Details

Related Documents

AP Calculus AB Scoring Guide Unit 6 Progress Check

Clinical Psychologist

Module 4 Matrices

MATH 1324 Homework 5 Answers

Ap progress 1 5 all 5

The Fundamental Theorem of Calculus and Definite I

AP Calculus AB Scoring Guide

Investigating the Rising Cost of MTA Transit Fare

Module 11 Geometry

AP Calculus AB Unit 5 Progress Check Scoring Guide

Company

Explore

Study Tools