实验2Lingo求解运输问题和整数规划.

数学规划实验2Lingo求解运输问题和整数规划LINGO软件简介•目标与约束段•集合段（SETSENDSETS）•数据段（DATAENDDATA）•初始段（INITENDINIT）LINGO模型的构成：4个段LINGO模型的优点•包含了LINDO的全部功能•提供了灵活的编程语言（矩阵生成器）简单Lingo程序Model:min=7*x1+3*x2;x1+x2=345.5;x1=98;2*x1+x2=600;end•lingo程序:优化模型实际问题中的优化模型mixgtsxxxxfzMaxMiniTn,2,1,0)(..),(),()(1或x~决策变量f(x)~目标函数gi(x)0~约束条件数学规划线性规划(LP)二次规划(QP)非线性规划(NLP)纯整数规划(PIP)混合整数规划(MIP)整数规划(IP)0-1整数规划一般整数规划连续规划LINDO公司软件产品简要介绍美国芝加哥(Chicago)大学的LinusSchrage教授于1980年前后开发,后来成立LINDO系统公司（LINDOSystemsInc.），网址：(V6.1)LINGO:LinearINteractiveGeneralOptimizer(V8.0)LINDOAPI:LINDOApplicationProgrammingInterface(V2.0)What’sBest!:(SpreadSheete.g.EXCEL)(V7.0)演示(试用)版、学生版、高级版、超级版、工业版、扩展版…（求解问题规模和选件不同）LINDO和LINGO软件能求解的优化模型LINGOLINDO优化模型线性规划(LP)非线性规划(NLP)二次规划(QP)连续优化整数规划(IP)LingoLPQPNLPIP全局优化(选)ILPIQPINLPLINDO/LINGO软件的求解过程LINDO/LINGO预处理程序线性优化求解程序非线性优化求解程序分枝定界管理程序1.确定常数2.识别类型1.单纯形算法2.内点算法(选)1、顺序线性规划法(SLP)2、广义既约梯度法(GRG)(选)3、多点搜索(Multistart)(选)单位销地运价产地B1B2B3B4B5B6B7B8产量A16267425960A24953858255A35219743351A47673927143A52395726541A65522814352销量3537223241324338二、实验例题例2.1使用LINGO软件计算6个发点8个收点的最小费用运输问题。产销单位运价如下表。302524143515560iia2803843324132223735iib•解:设第I个产地运到第j个销地的单位运价为cij,第I个产地运到第j个销地的运量为xij,第I个产地的产量为ai(I=1,2,…,6),第j个销地的销量为bj(j=1,2,…,8),运费为z,则此问题的数学模型为如下的数学规划问题:8....,1,6,...,2,1,0)8,...,2,1()6,...,2,1(..min61816181jixjdxiaxtsxcijiiijijijijijij302524143515560iia2803843324132223735iib使用LINGO软件，编制程序如下：使用LINGO软件，编制程序如下：model:!6发点8收点运输问题;sets:warehouses/wh1..wh6/:capacity;vendors/v1..v8/:demand;links(warehouses,vendors):cost,volume;endsets!目标函数;min=@sum(links:cost*volume);!需求约束;@for(vendors(J):@sum(warehouses(I):volume(I,J))=demand(J));!产量约束;@for(warehouses(I):@sum(vendors(J):volume(I,J))=capacity(I));data:capacity=605551434152;demand=3537223241324338;cost=626742954953858252197433767392712395726555228143;enddataend8....,1,6,...,2,1,0)8,...,2,1()6,...,2,1(..min61816181jixjdxicxtsxcijiiijijijijijij产销不平衡问题model:!6发点8收点运输问题;sets:chandi/A1..A6/:a;xiaodi/B1..B8/:d;links(chandi,xiaodi):c,x;endsets!目标函数;min=@sum(links(i,j):c(i,j)*x(i,j));!需求约束;@for(xiaodi(J):@sum(chandi(I):x(I,J))=d(J));!产量约束;@for(chandi(I):@sum(xiaodi(J):x(I,J))=a(I));!这里是数据;data:a=605551434152;d=3537223241324338;c=626742954953858252197433767392712395726555228143;enddataendLINGO模型的构成：4个段集合段（SETSENDSETS）数据段（DATAENDDATA）目标与约束段初始段（INITENDINIT）(此题无初始数据)例2.2选址问题某公司有6个建筑工地，位置坐标为(ai,bi)(单位：公里),水泥日用量di(单位：吨）i１２３４５６a1.258.750.55.7537.25b1.250.754.7556.57.75d35476111)现有2料场，位于A(5,1),B(2,7),记(xj,yj),j=1,2,日储量ej各有20吨。假设：料场和工地之间有直线道路目标：制定每天的供应计划，即从A,B两料场分别向各工地运送多少吨水泥，使总的吨公里数最小。用例中数据计算，最优解为i1234561ic（料场A）3507012ic（料场B）0040610总吨公里数为136.22,1,6,...,1,..])()[(min612121612/122jecidctsbyaxcjijiiijjjiijijij线性规划模型决策变量：cij(料场j到工地i的运量）~12维Location(Linear)MODEL:TitleLocationProblem;sets:demand/1..6/:a,b,d;supply/1..2/:x,y,e;link(demand,supply):c;endsetsdata:!locationsforthedemand(需求点的位置);a=1.25,8.75,0.5,5.75,3,7.25;b=1.25,0.75,4.75,5,6.5,7.75;!quantitiesofthedemandandsupply（供需量）;d=3,5,4,7,6,11;e=20,20;x,y=5,1,2,7;enddatainit:!initiallocationsforthesupply（初始点）;!x,y=5,1,2,7;endinit!Objectivefunction（目标）;[OBJ]min=@sum(link(i,j):c(i,j)*((x(j)-a(i))^2+(y(j)-b(i))^2)^(1/2));!demandconstraints（需求约束）;@for(demand(i):[DEMAND_CON]@sum(supply(j):c(i,j))=d(i););!supplyconstraints（供应约束）;@for(supply(i):[SUPPLY_CON]@sum(demand(j):c(j,i))=e(i););@for(supply:@free(X);@free(Y););!@for(supply:@bnd(0.5,X,8.75);@bnd(0.75,Y,7.75););ENDLocation(Linear)选址问题：NLP2）改建两个新料场，需要确定新料场位置(xj,yj)和运量cij，在其它条件不变下使总吨公里数最小。2,1,6,...,1,..])()[(min612121612/122jecidctsbyaxcjijiiijjjiijijij决策变量：cij，(xj,yj)~16维非线性规划模型Location(NonLinear)LINGO模型的构成：4个段集合段（SETSENDSETS）数据段（DATAENDDATA）初始段（INITENDINIT）目标与约束段局部最优：89.8835(吨公里)LP：移到数据段边界集合的类型集合派生集合基本集合稀疏集合稠密集合元素列表法元素过滤法直接列举法隐式列举法setname[/member_list/][:attribute_list];setname(parent_set_list)[/member_list/][:attribute_list];SETS:CITIES/A1,A2,A3,B1,B2/;ROADS(CITIES,CITIES)/A1,B1A1,B2A2,B1A3,B2/:D;ENDSETSSETS:STUDENTS/S1..S8/;PAIRS(STUDENTS,STUDENTS)|&2#GT#&1:BENEFIT,MATCH;ENDSETS集合元素的隐式列举类型隐式列举格式示例示例集合的元素数字型1..n1..51,2,3,4,5字符-数字型stringM..stringNCar101..car208Car101,car102,…,car208星期型dayM..dayNMON..FRIMON,TUE,WED,THU,FRI月份型monthM..monthNOCT..JANOCT,NOV,DEC,JAN年份-月份型monthYearM..monthYearNOCT2001..JAN2002OCT2001,NOV2001,DEC2001,JAN2002运算符的优先级优先级运算符最高#NOT#—（负号）^*/+—（减法）#EQ##NE##GT##GE##LT##LE##AND##OR#最低(=)=(=)三类运算符：算术运算符逻辑运算符关系运算符集合循环函数四个集合循环函数：FOR、SUM、MAX、MIN@function(setname[(set_index_list)[|condition]]:expression_list);[objective]MAX=@SUM(PAIRS(I,J):BENEFIT(I,J)*MATCH(I,J));@FOR(STUDENTS(I):[constraints]@SUM(PAIRS(J,K)|J#EQ#I#OR#K#EQ#I:MATCH(J,K))=1);@FOR(PAIRS(I,J):@BIN(MATCH(I,J)));MAXB=@MAX(PAIRS(I,J):BENEFIT(I,J));MINB=@MIN(PAIRS(I,J):BENEFIT(I,J));Example:PAIRSJIJIMATCHJIBENEFIT),(),(*),(1),(),(IKorIJPAIRSKJKJMATCH状态窗口SolverType:•B-and-B•Global•MultistartModelClass:LP，QP，ILP，IQP，PILP,PIQP，NLP，INLP，PINLPState:•GlobalOptimum•LocalOptimum•Feasi