1、最小费用运输问题单位销地运价产地B1B2B3B4B5B6B7B8产量A16267425960A24953858255A35219743351A47673927143A52395726541A65522814352销量3537223241324338280/302i.e:model:!6发点8收点运输问题;sets:warehouses/wh1.wh6/:capacity;vendors/v1.v8/:demand;links(warehouses,vendors):cost,volume;endsets!目标函数;min=sum(links:cost*volume);!需求
2、约束;for(vendors(J):sum(warehouses(I):volume(I,J)=demand(J);!产量约束;for(warehouses(I):sum(vendors(J):volume(I,J)=0,FLOORreturnsthelargestinteger,I,suchthatI=X.LGM(X)Thisreturnsthenatural(basee)logarithmofthegammafunctionofX(i.e.,logof(X-1)!).Itisextendedtononinteg
3、ervaluesofXbylinearinterpolation.Note:伽玛方程表达式为：(x)=e(-t)*t(x-1)dt(积分的下限式0,上限式+)利用分部积分法(integrationbyparts)我们可以得到(x)=（x-1)*(x-1)LOG(X)ThisreturnsthenaturallogarithmofX.MOD(X,Y)ThisreturnsthevalueofXmoduloY,or,inotherwords,theremainderofanintegerdivideofXbyY.PO
4、W(X,Y)ThisreturnsthevalueofXrasiedtotheYpower.SIGN(X)Thisreturns-1ifX=Staffrequiredtoday,foreachdayoftheweekTheright-handsideofthisexpression,Staffrequiredtoday,iseasytocalculate.ItissimplythequantityREQUIRED(I).Theleft-handside,Staffondutytoday,i
5、sabittrickiertocompute.Giventhatallemployeesareonafivedayon,twodayoffschedule,thenumberofemployeesworkingtodayis:Numberworkingtoday=Numberstartingtoday+Numberstarting1dayago+Numberstarting2daysago+Numberstarting3daysago+Numberstarting4daysago.I
6、notherwords,tocomputethenumberofemployeesworkingtoday,wesumupthenumberofpeoplestartingtodayplusthosestartingoverthepreviousfourdays.Thenumberofemployeesstartingfiveandsixdaysbackdontcountbecausetheyareontheirdaysoff.So,usingmathematicalnotation,what
7、onemightconsiderdoingisaddingtheconstraint:=j-4,jSTARTiREQUIREDj,forjDAYSTranslatingintoLINGOnotation,wecanwritethisas:FOR(DAYS(J):SUM(DAYS(I)|I#LE#5:START(J-I+1)=REQUIRED(J);Inwords,theLINGOstatementsays,foreachdayoftheweek,thesumoftheemp
8、loyeesstartingoverthefivedayperiodbeginningfourdaysagoandendingtodaymustbegreater-than-or-equal-totherequirednumberofstafffortheday.Thissoundscorrect,butthereisaslightproblem.Ifwetrytosolveourmodelwiththisconstraintwegettheerrormessage:Toseewhywege
9、tthiserrormessage,considerwhathappensonThursday.Thursdayhasanindexof4inoursetDAYS.Aswritten,thestaffingconstraintforThursdaywillbe:START(4-1+1)+START(4-2+1)+START(4-3+1)+START(4-4+1)+START(4-5+1)=REQUIRED(4);Simplifying,weget:START(4)
10、+START(3)+START(2)+START(1)+START(0)=REQUIRED(4);TheSTART(0)termistherootofourproblem.STARTisdefinedfordays1through7.START(0)doesnotexist.Anindexof0onSTARTisconsideredoutofrange.Wewouldliketohaveanyindicesless-than-or-equal-to0wraparoundto
11、theendoftheweek.Specifically,0wouldcorrespondtoSunday(7),-1toSaturday(6),andsoon.LINGOhasafunctionthatdoesjustthiscalledWRAP.TheWRAPfunctiontakestwoargumentscallthemINDEXandLIMIT.Formallyspeaking,WRAPreturnsJsuchthatJ=INDEX-K*LIMIT,whereKisani
12、ntegersuchthatJisintheinterval1,LIMIT.Informallyspeaking,WRAPwillsubtractoraddLIMITtoINDEXuntilitfallsintherange1toLIMIT.Therefore,thisisjustwhatweneedtowraparoundanindexinmultiperiodplanningmodels.IncorporatingtheWRAPfunction,wegetthecorrected,fi
13、nalversionofourstaffingconstraint:FOR(DAYS(J):SUM(DAYS(I)|I#LE#5:START(WRAP(J-I+1,7)=REQUIRED(J);TheSolution：Belowisourstaffingmodelinitsentirety:SETS:DAYS/MONTUEWEDTHUFRISATSUN/:REQUIRED,START;ENDSETSDATA:REQUIRED=20161316191412;ENDDATAMIN=SUM(
14、DAYS(I):START(I);FOR(DAYS(J):SUM(DAYS(I)|I#LE#5:START(WRAP(J-I+1,7)=REQUIRED(J);Model:STAFFDEMSolvingthemodel,wegetthesolutionreport:Optimalsolutionfoundatstep:8Objectivevalue:22.00000VariableValueReducedCostSTART(MON)8.0000000.0000000START(TUE)2.00000
15、00.0000000START(WED)0.00000000.0000000START(THU)6.0000000.0000000START(FRI)3.0000000.0000000START(SAT)3.0000000.0000000START(SUN)0.00000000.0000000RowSlackorSurplusDualPrice122.000001.00000020.0000000-0.200000030.0000000-0.200000040.0000000-0.200000050.0000000-0.
16、200000060.0000000-0.200000070.0000000-0.200000080.0000000-0.2000000SolutiontoSTAFFDEMTheobjectivevalueof22meansweneedtohire22workers.Westartourworkersaccordingtotheschedule:MonTueWedThuFriSatSunStart8206330Ifwelookatthesurplusesonourstaffingrequirementrows(ro
17、ws2-7),weseethattheslackvaluesare0onallofthedays.Thismeanstherearenomoreworkersthanrequiredandwejustmeetstaffingrequirementsoneveryday.Eventhoughthisisasmallmodel,tryingtocomeupwithasolutionthisefficientbyhandwouldbeadifficulttask.职员时序安排模型一项工
18、作一周7天都需要有人（比如护士工作），每天（周一至周日）所需的最少职员数为20、16、13、16、19、14和12，并要求每个职员一周连续工作5天，试求每周所需最少职员数，并给出安排。注意这里我们考虑稳定后的情况。model:sets:days/mon.sun/:required,start;endsetsdata:!每天所需的最少职员数;required=20161316191412;enddata!最小化每周所需职员数;min=sum(days:start);for(days(J):sum(days(I)|I#le#5:start(wrap(J-I
19、+1,7)=required(J);end计算的部分结果为Globaloptimalsolutionfoundatiteration:0Objectivevalue:22.00000VariableValueReducedCostREQUIRED(MON)20.000000.000000REQUIRED(TUE)16.000000.000000REQUIRED(WED)13.000000.000000REQUIRED(THU)16.000000.000000REQUIRED(FRI)19.000000.000000REQU
20、IRED(SAT)14.000000.000000REQUIRED(SUN)12.000000.000000START(MON)8.0000000.000000START(TUE)2.0000000.000000START(WED)0.0000000.3333333START(THU)6.0000000.000000START(FRI)3.0000000.000000START(SAT)3.0000000.000000START(SUN)0.0000000.000000每周最少:22个职员，周一:8人，周二:2人，周三:0人
21、，周四:6人，周五和周六:3人，周日:0人。用Matlab编程为：先建立一个M文件：fssp.m然后再建立：%fssp.mf=1,1,1,1,1,1,1;%A=-1,0,0,-1,-1,-1,-1;-1,-1,0,0,-1,-1,-1;-1,-1,-1,0,0,-1,-1;-1,-1,-1,-1,0,0,-1;-1,-1,-1,-1,-1,0,0;0,-1,-1,-1,-1,-1,0;0,0,-1,-1,-1,-1,-1;b=-20,-16,-13,-16,-19,-14,-12;l=0,0,0,0,0,0,0;xo,fo,exitflag=linprog(f,A,b,l)结果为
22、：xo=8.00002.00000.00006.00003.00003.00000.0000fo=22.0000exitflag=13.7集循环函数（SetLoopingFunctions）Setloopingfunctionsoperateoveranentiresetand,withtheexceptionoftheFORfunction,produceasingleresult.Thesyntaxforasetloopingfunctionis:function(setname(set_index_l
23、ist)|conditional_qualifier:expression_list);functioncorrespondstooneofthesetloopingfunctionslistedbelow.setnameisthenameofthesetyouwanttoloopover.Theset_index_listisoptionalandisusedtocreatealistofindices,whichcorrespondtotheparentprimitivesetsthatform
24、thesetnameset.AsLINGOloopsthroughthemembersofthesetnameset,itwillsetthevaluesoftheindicesintheset_index_listtocorrespondtothecurrentmemberofthesetnameset.Theconditional_qualifierisoptionalandmaybeusedtolimitthescopeofthesetloopingfunction.WhenLING
25、Oisloopingovereachmemberofthesetnameset,itevaluatestheconditional_qualifier.Iftheconditional_qualifierevaluatestotrue,thenfunctionisperformedforthesetmember.Otherwise,itisskipped.Theexpression_listisalistofexpressionstobeappliedtoeachmemberofthesetname
26、set.WhenusingtheFORfunction,theexpression_listmaycontainmultipleexpressions,separatedbysemicolons.Theseexpressionswillbeaddedasconstraintstothemodel.Whenusingtheremainingthreesetloopingfunctions(SUM,MAX,andMIN),theexpression_listmustcontainoneexpressiononly
27、.Iftheset_index_listisomitted,allattributesreferencedintheexpression_listmustbedefinedonthesetnameset.Theavailablesetloopingfunctionsarelistedbelow:集循环函数遍历整个集进行操作。其语法为function(setname(set_index_list)|conditional_qualifier:expression_list);function相应于下面罗列的四个集循环函数之一；setname是要遍
28、历的集；set_index_list是集索引列表；conditional_qualifier是用来限制集循环函数的范围，当集循环函数遍历集的每个成员时，LINGO都要对conditional_qualifier进行评价，若结果为真，则对该成员执行function操作，否则跳过，继续执行下一次循环。expression_list是被应用到每个集成员的表达式列表，当用的是for函数时，expression_list可以包含多个表达式，其间用逗号隔开。这些表达式将被作为约束加到模型中。当使用其余的三个集循环函数时，expression_list只能有一个表达式。如果省略set_index_list
29、，那么在expression_list中引用的所有属性的类型都是setname集。FOR(setname(set_index_list)|cond_qualifier:exp_list)Thisgeneratestheexpressionscontainedinexp_listforallmembersofthesetnameset.FORisusedtogenerateconstraintsoverallthemembersofaset,andisoneofthemostpowerfulfeaturesofL
30、INGO.MAX(setname(set_index_list)|cond_qualifier:expression)Thisreturnsthemaximumvalueofexpressiontakenoverthesetnameset.MIN(setname(set_index_list)|cond_qualifier:expression)Thisreturnstheminimumvalueofexpressiontakenoverthesetnameset.PROD(setname(set_index_lis
31、t)|cond_qualifier:expression)Thisreturnstheproductofanexpressionoverthesetnameset.SUM(setname(set_index_list)|cond_qualifier:expression)Thisreturnsthesumofanexpressionoverthesetnameset.SetloopingfunctionsarediscussedinmoredetailinsectionSetLoopingFunctionsi
32、nChapter2.3.8辅助功能函数（MiscellaneousFunctions）IF(logical_condition,true_result,false_result)TheIFfunctionevaluateslogical_conditionand,iftrue,returnstrue_result,otherwiseitreturnsfalse_result.Forexample,considerthefollowingsimplemodelthatusesIFtocomputefixedproduction
33、costs:MIN=COST;COST=XCOST+YCOST;XCOST=IF(X#GT#0,100,0)+2*X;YCOST=IF(Y#GT#0,60,0)+3*Y;X+Y=30;Model:IFCOSTWeproducetwoproducts梄andY.Wewanttominimizetotalcost,subjecttoproducingatleast30totalunitsofXandY.IfweproduceX,thereisafixedchargeo
34、f100alongwithavariablecostof2.Similarly,forY,theserespectivevaluesare60and3.WeusetheIFfunctiontodetermineifeitheroftheproductsarebeingproducedinordertoapplytherelevantfixedcost.Thisisaccomplishedbytestingtoseeiftheirproductionlevelsaregreatertha
35、n0.Ifso,wereturnthefixedcostvalue,otherwise,wereturnzero.Experiencedmodelersknowthat,withoutthebenefitofanIFfunction,modelingfixedcostsrequiresinvokingsometricksusingbinaryintegervariables.TheresultingmodelsarenotasintuitiveasmodelsconstructedusingIF.Th
36、ecaveat,however,isthattheIFfunctionisnotalinearfunction.Atbest,thegraphofanIFfunctionwillbepiecewiselinear.Inourcurrentexample,theIFfunctionsarepiecewiselinearwithadiscontinuousbreakattheorigin.AswediscussinthechapterOnMathematicalModeling,itisalw
37、aysbesttotryandkeepamodellinear.Barringthis,itisbestforallfunctionsinanonlinearmodeltobecontinuous.Clearly,then,theIFfunctionisaprobleminthatitviolatesboththeseconditions.Thus,modelscontainingIFfunctionsmaybetoughtosolvetoglobaloptimality.Fortunate
38、ly,LINGOhastwooptionsthatcanhelpovercomethedifficultnatureofmodelscontainingIFfunctions條inearizationandglobaloptimization.ToillustratethedifficultyinsolvingmodelswithdiscontinuousfunctionssuchasIF,wewillsolveourexamplemodelwithbothlinearizationandglobalopti
39、mizationdisabled.Whenwedothis,wegetthefollowingsolution:Localoptimalsolutionfoundatiteration:42Objectivevalue:160.0000VariableValueCOST160.0000XCOST160.0000YCOST0.000000X30.00000Y0.000000ThissolutioninvolvesproducingonlyXatatotalcostof160.Clearly,thisisme
40、relyalocallyoptimalpoint,giventhatproducingonlyYandnotXwillresultinalowertotalcostof150.InordertofindthegloballyoptimalpointwemustresorttoeitherthelinearizationorglobaloptimizationfeaturesinLINGO.Briefly,linearizationseekstoreformulateanonlinearmodel
41、intoamathematicallyequivalentlinearmodel.Thisisdesirablefortworeasons.First,andmostimportant,linearmodelscanalwaysbesolvedtoglobaloptimality.Secondly,linearmodelswilltendtosolvemuchfasterthanequivalentnonlinearmodels.Unfortunately,linearizationcan抰alwaystra
42、nsformamodelintoanequivalentlinearstate,inwhichcase,itmaybeofnobenefit.Fortunately,oursamplemodelcanbeentirelylinearized.Toenablethelinearizationoption,runtheLINGO|OptionscommandandsettheLinearizationDegreetoHighontheGeneralSolvertab.Globaloptimization
43、breaksamodeldownintoaseriesofsmaller,localmodels.Oncethisseriesoflocalmodelshasbeensolved,agloballyoptimalsolutioncanbedetermined.Toenableglobaloptimization,runtheLINGO|Optionscommand,selecttheGlobalSolvertab,thenclickontheGlobalSolvercheckbox.Notethat
44、theglobalsolverisanadd-onoptiontoLINGO.Theglobalsolverfeaturewillnotbeenabledforsomeinstallations.RuntheHelp|AboutLINGOcommandtodetermineifyourinstallationhastheglobalsolvercapabilityenabled.Regardless,whetherusingthelinearizationoptionortheglobalsolver,
45、LINGOobtainsthetrue,globalsolution:Globaloptimalsolutionfoundatiteration:6Objectivevalue:150.0000VariableValueCOST150.0000XCOST0.000000YCOST150.0000X0.000000Y30.00000Note:Startingwithrelease9.0,thefalsebranchoftheIFfunctionmaycontainarithmeticerrorswithoutcau
46、singthesolvertotriggeranerror.ThismakestheIFfunctionusefulinavoidingproblemswhenthesolverstraysintoareaswherecertainfunctionsbecomeundefined.Forinstance,ifyourmodelinvolvesdivisionbyavariable,youmightuseIFasfollows:IF(X#GT#1.E-10,1/X,1.E10).WARN(text,
47、logical_condition)Thisfunctiondisplaysthemessage憈extifthelogical_conditionismet.Thisfeatureisusefulforverifyingthevalidityofamodelsdata.Inthefollowingexample,iftheuserhasenteredanegativeinterestrate,themessageINVALID營NTEREST燫ATEisdisplayed:!Amodelofahome
48、mortgage;DATA:!Prompttheuserfortheinterestrate,years,andvalueofmortgage.Wewillcomputethemonthlypayment;YRATE=;YEARS=;LUMP=;ENDDATA!Numberofmonthlypayment;MONTHS=YEARS*12;!Monthlyinterestrate;(1+MRATE)12=1+YRATE;!Solvenextlineformonthlypayment
49、;LUMP=PAYMENT*FPA(MRATE,MONTHS);!WarnthemifinterestrateisnegativeWARN(INVALIDINTERESTRATE,YRATE#LT#0);USER(user_determined_arguments)TheusercansupplythisinanexternalDLLorobjectcodefile.ForadetailedexampleontheuseofUSER,seeUserDefinedFunctions.4.灵敏度分析i.e
50、：某家具公司制造书桌、餐桌和椅子，所用的资源有三种：木料、木工和漆工。生产数据如下表所示：每个书桌每个餐桌每个椅子现有资源总数木料8单位6单位1单位48单位漆工4单位2单位1.5单位20单位木工2单位1.5单位0.5单位8单位成品单价60单位30单位20单位若要求桌子的生产量不超过5件，如何安排三种产品的生产可使利润最大？max=60*desks+30*tables+20*chairs;8*desks+6*tables+chairs=48;4*desks+2*tables+1.5*chairs=20;2*desks+1.5*tables+.5*chairs=8;tables=5;Global
51、optimalsolutionfound.Objectivevalue:280.0000Totalsolveriterations:3VariableValueReducedCostDESKS2.0000000.000000TABLES0.0000005.000000CHAIRS8.0000000.000000RowSlackorSurplusDualPrice1280.00001.000000224.000000.00000030.00000010.0000040.00000010.0000055.0000
52、000.000000“SlackorSurplus”给出松驰变量的值：第1行松驰变量=280（模型第一行表示目标函数，所以第二行对应第一个约束）第2行松驰变量=24第3行松驰变量=0第4行松驰变量=0第5行松驰变量=5“ReducedCost”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动时,目标函数的变化率。其中基变量的reducedcost值应为0，对于非基变量Xj,相应的reducedcost值表示当某个变量Xj增加一个单位时目标函数减少的量(max型问题)。本例中：变量tables对应的reducedcost值为5，表示当非基变量
53、tables的值从0变为1时（此时假定其他非基变量保持不变,但为了满足约束条件，基变量显然会发生变化），最优的目标函数值=280-5=275。“DUALPRICE”（对偶价格）表示当对应约束有微小变动时,目标函数的变化率。输出结果中对应于每一个约束有一个对偶价格。若其数值为p，表示对应约束中不等式右端项若增加1个单位，目标函数将增加p个单位（max型问题）。显然，如果在最优解处约束正好取等号（也就是“紧约束”，也称为有效约束或起作用约束），对偶价格值才可能不是0。本例中：第3、4行是紧约束，对应的对偶价格值为10，表示当紧约束3)4DESKS+2TABLES
54、+1.5CHAIRS=20变为3)4DESKS+2TABLES+1.5CHAIRS1的正整数）：N点求解Barrier:障碍法(即内点法)6.综合案例旅行售货员问题（TravelingSalesmanProblem）有一个推销员，从城市1出发，要遍访城市2，3，n各一次，最后返回城市1。已知从城市i到j的旅费为，问他应按怎样的次序访问这些城市，使得总旅费最少？可以用多种方法把TSP表示成整数规划模型。这里介绍的一种建立模型的方法，是把该问题的每个解（不一定是最优的）看作是一次“巡回”。在下述意义下，引入一些0-1整数变量：其目标只是使为最小。这里有两个
55、明显的必须满足的条件：访问城市i后必须要有一个即将访问的确切城市；访问城市j前必须要有一个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。123456到此我们得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP来说并不充分，仅仅是必要条件。例如：以上两个条件都满足，但它显然不是TSP的解，它存在两个子巡回。这里，我们将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。把额外变量附加到问题中。可把这些变量看作是连续的（最然这些变量在最优解中取普通的整数值）。现在附加下面形式的约束条件。为了证明该约束条件有预期的效果，必须证明：（1）任何含子巡回的路线
56、都不满足该约束条件；（2）全部巡回都满足该约束条件。首先证明（1），用反证法。假设还存在子巡回，也就是说至少有两个子巡回。那么至少存在一个子巡回中不含城市1。把该子巡回记为，则必有把这k个式子相加，有，矛盾！故假设不正确，结论（1）得证。下面证明（2），采用构造法。对于任意的总巡回，可取访问城市i的顺序数，取值范围为。因此，。下面来证明总巡回满足该约束条件。()总巡回上的边（）非总巡回上的边从而结论（2）得证。这样我们把TSP转化成了一个混合整数线性规划问题。显然，当城市个数较大（大于30）时，该混合整数线性规划问题的规模会很大，从而给求解带来很大问题。TSP已被证明是NP难问题，目前还没有发
58、:!进入城市K;sum(city(I)|I#ne#K:x(I,K)=1;!离开城市K;sum(city(J)|J#ne#K:x(K,J)=1;);!保证不出现子圈;for(city(I)|I#gt#1:for(city(J)|J#gt#1#and#I#ne#J:u(I)-u(J)+n*x(I,J)=n-1););!限制u的范围以加速模型的求解，保证所加限制并不排除掉TSP问题的最优解;for(city(I)|I#gt#1:u(I)=n-2);!定义X为01变量;for(link:bin(x)
59、;endGlobaloptimalsolutionfound.Objectivevalue:25.00000Extendedsolversteps:0Totalsolveriterations:19VariableValueReducedCostN5.0000000.000000U(1)0.0000000.000000U(2)0.0000000.000000U(3)2.0000000.000000U(4)1.0000000.000000U(5)3.0000000.000000DIST(1,1)0.0000000.000000DIST(1,2)2.0000000.000000DIST(1,3)6.0000000.000000DIST(1,4)7.0000000.000000DIST(1,5)4.0000000.0000