Lingo求解运输问题

（LinearInteractiveGeneralOptimizer）,LINGO简介,LINGO（LinearInteractiveGeneralOptimizer）是用来求解线性和非线性优化问题的简易工具。,LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果。,例1如何在LINGO中求解如下的LP问题：,min=2*x1+3*x2;x1+x2=350;x1=100;2*x1+x2=，大于等于)(在优化模型中约束一般没有严格小于、严格大于关系),运算符的优先级,例4使用LINGO软件计算6个发点8个收点的最小费用运输问题。产销单位运价如下表。,单位销地,68minz=cijxiji=1j=18s.t.xijai（i=1,2,6)j=16xij=bj（j=1,2,8)i=1xij0（i=1,2,6；j=1,2,8),建立模型：（产大于销）设xij为从第i个产地调运给第j个销地的物资数量,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);!这里是数据;,然后点击工具条上的按钮即可。,使用LINGO软件，编制程序如下：,data:capacity=605551434152;demand=3537223241324338;cost=626742954953858252197433767392712395726555228143;enddataend,集合的属性相当于以集合的元素为下标的数组。这里的相当于二维数组。它的两个下标分别来自集合warehouses和vendors，因此可以定义一个由二元对组成的新的集合，然后将定义成这个新集合的属性。,本例中集合的概念,利用集合的概念，可以定义产地warehouses和销地vendors两个集合，分别有6个和8个元素(下标)，其属性分别为产量capacity和销量demand。但从各个产地到销地的单位运价和决策变量(运送量)与集合warehouses和集合vendors都有关系的。该如何定义这样的属性？,输入程序,定义了三个集合，其中links在前两个集合warehouses和vendors的基础上定义,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);!这里是数据;,LINGO建模语言也称为矩阵生成器（MATRIXGENERATOR）。类似warehouses和vendors直接把元素列举出来的集合，称为基本集合(primaryset),而把links这种基于其它集合而派生出来的二维或多维集合称为派生集合(derivedset)。由于是warehouses和vendors生成了派生集合links，所以warehouses和vendors称为links的父集合。,data:capacity=605551434152;demand=3537223241324338;cost=626742954953858252197433767392712395726555228143;enddataend,表示集合links中的元素就是集合warehouses和vendors的元素组合成的有序二元组，从数学上看link是warehouses和vendors的笛卡儿积，也就是说links=（S，T）|Swarehouses，Tvendors因此，其属性cost和volume也就是一个6*8的矩阵（或者说是含有48个元素的二维数组）。,2020/5/13,18,目标函数的定义方式,SUM(集合（下标）：关于集合的属性的表达式),对语句中冒号“：”后面的表达式，按照“：”前面的集合指定的下标（元素）进行求和。,约束的定义方式,循环函数FOR(集合(下标)：关于集合的属性的约束关系式),对冒号“：”前面的集合的每个元素（下标），冒号“：”后面的约束关系式都要成立。,例5分配问题（指派问题，AssignmentProblem）,要求给每个人分配一项工作，并要求分配完这些工作，以使完成全部任务的总时间为最小。该问题可表示如下：,这是个给n个人分配n项工作以获得某个最高总效果的问题。第i个人完成第j项工作需要平均时间。,显然，分配问题可以作为线性规划问题来求解，尽管模型可能很大。例如，给100人分配100项工作将使所得的模型具有10000个变量。这时，如采用专门算法效果会更好。时间复杂度为的匈牙利算法便是好选择。,model:!7个工人，7个工作的分配问题;sets:workers/w1.w7/;jobs/j1.j7/;links(workers,jobs):cost,volume;endsets!目标函数;min=sum(links:cost*volume);!每个工人只能有一份工作;for(workers(I):sum(jobs(J):volume(I,J)=1;);!每份工