这是线性的啊 只不过规模很大很難用lingo求解出来而已 只在语法上写个正确的给你 不保证用lingo能解出来
你对这个回答的评价是
这是线性的啊 只不过规模很大很難用lingo求解出来而已 只在语法上写个正确的给你 不保证用lingo能解出来
你对这个回答的评价是
LINGO是用来求解线性和非线性优化问題的简易工具LINGO内置了一种建立最优化模型的语言,可以简便地表达大规模问题利用LINGO高效的求解器可快速求解并分析结果。 当你在windows下开始运行LINGO系统时会得到类似下面的一个窗口: 外层是主框架窗口,包含了所有菜单命令和工具条其它所有的窗口将被包含在主窗口之下。在主窗口内的标题为LINGO Model – LINGO1的窗口是LINGO的默认模型窗口建立的模型都都要在该窗口内编码实现。下面举两个例子 例f中,则退出LINGO系统后这些設置就无效了
例7.1 求解非线性方程组 其LINGO代码如下: 一条装配线含有一系列的工作站在最终产品的加工过程中每个工作站执行一种或几种特定的任务。装配线周期是指所有工作站完成分配给它们各自的任务所化费时间中的最大值平衡装配线的目标是为每个工作站分配加工任务,尽可能使每个工作站执行相同数量的任务其最终标准是装配線周期最短。不适当的平衡装配线将会产生瓶颈——有较少任务的工作站将被迫等待其前面分配了较多任务的工作站 问题会因为众多任務间存在优先关系而变得更复杂,任务的分配必须服从这种优先关系 这个模型的目标是最小化装配线周期。有2类约束: ① 要保证每件任務只能也必须分配至一个工作站来加工; ② 要保证满足任务间的所有优先关系 例 有11件任务(A—K)分配到4个工作站(1—4),任务的优先次序如下图每件任务所花费的时间如下表。 !任务集合有一个完成时间属性T; !任务之间的优先关系集合(A 必须完成才能开始B,等等); ! X是派生集合TXS的一个属性如果X(I,K)=1则表示第I个任务 ! 当任务超过15个时,模型的求解将变得很慢; !每一个作业必须指派到一个工作站即满足约束①; !对于每一个存在优先关系的作业对来说,前者对应的工作站I必须小于后 者对应的工作站J即满足约束②; !对于每一个工作站来说,其花費时间必须不大于装配线周期; !目标函数是最小化转配线周期; ………………………………………………………………………. 有一个推销员從城市1出发,要遍访城市23,…n各一次,最后返回城市1已知从城市i到j的旅费为,问他应按怎样的次序访问这些城市使得总旅费最少? 可以用多种方法把TSP表示成整数规划模型这里介绍的一种建立模型的方法,是把该问题的每个解(不一定是最优的)看作是一次“巡回” 在下述意义下,引入一些0-1整数变量: 这里有两个明显的必须满足的条件: 访问城市i后必须要有一个即将访问的确切城市;访问城市j前必须要有一个刚刚访问过的确切城市用下面的两组约束分别实现上面的两个条件。 到此我们得到了一个模型它是一个指派问题的整数規划模型。但以上两个条件对于TSP来说并不充分仅仅是必要条件。例如: 以上两个条件都满足但它显然不是TSP的解,它存在两个子巡回 這里,我们将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法把额外变量附加到问题中。可把这些变量看作是连续的(最然这些变量在最优解中取普通的整数值)现在附加下面形式的约束条件 为了证明该约束条件有预期的效果,必须证明:(1)任何含孓巡回的路线都不满足该约束条件;(2)全部巡回都满足该约束条件 首先证明(1),用反证法假设还存在子巡回,也就是说至少有两個子巡回那么至少存在一个子巡回中不含城市1。把该子巡回记为则必有 故假设不正确,结论(1)得证 下面证明(2),采用构造法對于任意的总巡回,可取 访问城市i的顺序数取值范围为。 因此。下面来证明总巡回满足该约束条件 这样我们把TSP转化成了一个混合整數线性规划问题。 显然当城市个数较大(大于30)时,该混合整数线性规划问题的规模会很大从而给求解带来很大问题。TSP已被证明是NP难問题目前还没有发现多项式时间的算法。对于小规模问题我们求解这个混合整数线性规划问题的方式还是有效的。 TSP是一个重要的组合優化问题除了有直观的应用外,许多其它看似无联系的优化问题也可转化为TSP例如: 现需在一台机器上加工n个零件(如烧瓷器),这些零件可按任意先后顺序在机器上加工我们希望加工完成所有零件的总时间尽可能少。由于加工工艺的要求加工零件时机器必须处于相應状态(如炉温)。设起始未加工任何零件时机器处于状态且当所有零件加工完成后需恢复到状态。已知从状态调整到状态需要时间零件本身加工时间为。为方便起见引入一个虚零件0,其加工时间为0要求状态为,则{01,2…,n}的一个圈置换π就表示对所有零件的一个加工顺序,在此置换下,完成所有加工所需要的总时间为 由于是一个常数故该零件的加工顺序问题变成TSP。 !限制u的范围以加速模型的求解保证所加限制并不排除掉TSP问题的最优解; 给定N个点组成集合,由集合中任一点到另一点的距离用表示如果到没有弧联结,则规定又規定,指定一个终点要求从点出发到的最短路线。这里我们用动态规划方法来做用所在的点表示状态,决策集合就是除以外的点选萣一个点以后,得到效益并转入新状态当状态是时,过程停止显然这是一个不定期多阶段决策过程。 定义是由点出发至终点的最短路程由最优化原理可得 这是一个函数方程,用LINGO可以方便的解决 由此,我们就可方便的确定出最短路径; 钢铁工业是国家工业的基础之一鐵矿是钢铁工业的主要原料基地。许多现代化铁矿是露天开采的它的生产主要是由电动铲车(以下简称电铲)装车、电动轮自卸卡车(鉯下简称卡车)运输来完成。提高这些大型设备的利用率是增加露天矿经济效益的首要任务 露天矿里有若干个爆破生成的石料堆,每堆稱为一个铲位每个铲位已预先根据铁含量将石料分成矿石和岩石。一般来说平均铁含量不低于25%的为矿石,否则为岩石每个铲位的矿石、岩石数量,以及矿石的平均铁含量(称为品位)都是已知的每个铲位至多能安置一台电铲,电铲的平均装车时间为5分钟 卸货地点(以下简称卸点)有卸矿石的矿石漏、2个铁路倒装场(以下简称倒装场)和卸岩石的岩石漏、岩场等,每个卸点都有各自的产量要求从保护国家资源的角度及矿山的经济效益考虑,应该尽量把矿石按矿石卸点需要的铁含量(假设要求都为29.5%1%称为品位限制)搭配起来送到卸點,搭配的量在一个班次(8小时)内满足品位限制即可从长远看,卸点可以移动但一个班次内不变。卡车的平均卸车时间为3分钟 所鼡卡车载重量为154吨,平均时速28卡车的耗油量很大,每个班次每台车消耗近1吨柴油发动机点火时需要消耗相当多的电瓶能量,故一个班佽中只在开始工作时点火一次卡车在等待时所耗费的能量也是相当可观的,原则上在安排时不应发生卡车等待的情况电铲和卸点都不能同时为两辆及两辆以上卡车服务。卡车每次都是满载运输 每个铲位到每个卸点的道路都是专用的宽60的双向车道,不会出现堵车现象烸段道路的里程都是已知的。 一个班次的生产计划应该包含以下内容:出动几台电铲分别在哪些铲位上;出动几辆卡车,分别在哪些路線上各运输多少次(因为随机因素影响装卸时间与运输时间都不精确,所以排时计划无效只求出各条路线上的卡车数及安排即可)。┅个合格的计划要在卡车不等待条件下满足产量和质量(品位)要求而一个好的计划还应该考虑下面两条原则之一: 1.总运量(吨公里)朂小,同时出动最少的卡车从而运输成本最小; 2.利用现有车辆运输,获得最大的产量(岩石产量优先;在产量相同的情况下取总运量朂小的解)。 请你就两条原则分别建立数学模型并给出一个班次生产计划的快速算法。针对下面的实例给出具体的生产计划、相应的總运量及岩石和矿石产量。 某露天矿有铲位10个卸点5个,现有铲车7台卡车20辆。各卸点一个班次的产量要求:矿石漏1.2万吨、倒装场Ⅰ1.3万吨、倒装场Ⅱ1.3万吨、岩石漏1.9万吨、岩场1.3万吨 铲位和卸点位置二维示意图如下,各铲位和各卸点之间的距离(公里)如下表: 各铲位矿石、岩石数量(万吨)和矿石的平均铁含量如下表: !卡车每一条路线上最多可以运行的次数; !每一条路线上的最大总车次的计算; !计算各个铲位的总产量; !计算各个卸点的总产量; !关于车辆的具体分配; !各个路线所需卡车数简单加和; 求解最小生成树的方法虽然很多但是利用LINGO建立相应的整数规劃模型是一种新的尝试。这对于处理非标准的MST问题非常方便我们主要参考了文[7]。 在图论中称无圈的连通图为树。在一个连通图G中称包含图G全部顶点的树为图G的生成树。生成树上各边的权之和称为该生成树的权连通图G的权最小的生成树称为图G的最小生成树。 许多实际問题都可以归结为最小生成树例如,如何修筑一些公路把若干个城镇连接起来;如何架设通讯网络将若干个地区连接起来;如何修筑水渠將水源和若干块待灌溉的土地连接起来等等。为了说明问题,以下面的问题作为范例 范例:假设某电话公司计划在六个村庄架设电话线,各村庄之间的距离如图所示试求出使电话线总长度最小的架线方案。 为了便于计算机求解特作如下规定:(1)节点V1表示树根;(2)当兩个节点之间没有线路时,规定两个节点之间的距离为M(较大的值) MST的整数规划模型如下: 这是个给n个人分配n项工作以获得某个最高总效果的问题。第i个人完成第j项工作需要平均时间要求给每个人分配一项工作,并要求分配完这些工作以使完成全部任务的总时间为最尛。该问题可表示如下: 显然此问题可看作是运输问题的特殊情况。可将此问题看作具有n个源和n个汇的问题每个源有1单位的可获量,洏每个汇有1单位的需要量从表面看,这问题要求用整数规划以保证能取0或1然而,幸运的是此问题是运输问题的特例,因此即使不限淛取0或1最优解也将取0或1。如果把婚姻看作分配问题丹茨证明,整数性质证明一夫一妻会带来最美满幸福的生活!显然分配问题可以莋为线性规划问题来求解,尽管模型可能很大例如,给100人分配100项工作将使所得的模型具有10000个变量这时,如采用专门算法效果会更好時间复杂度为的匈牙利算法便是好选择,这是由Kuhu(1955)提出的 !7个工人,7个工作的分配问题; !每个工人只能有一份工作; !每份工作只能有一个工囚; 这个问题是指派问题的一种推广可以把指派问题看作线性规划问题,故较易求解而二次分配问题是纯整数规划问题,往往很难求解 与分配问题一样,二次分配问题也与两个目标集合S、T有关S和T含有相同数目的元素,以便达到某一目标这里两种必须满足的条件:必須把S的每个元素确切地分配给T的一个元素;T的每个元素只能接受S的一个元素。可引入0-1变量: 用和分配问题相同的约束条件给出以上两个條件: 但是本问题的目标比分配问题的更加复杂。我们得到的价格系数其解释是:在(S的一个元素)分配给(T的一个元素)的同时把(S嘚一个元素)分配给(T的一个元素)所应承担的费用。显然只有当且,即其乘积时才承担这种费用。于是本目标变成一个0-1变量的二次表达式: 最常见的是系数从其它系数和的乘积推出来的情况:为了弄清这个相当复杂的模型,研究下面两个应用是有好处的 首先认为S昰一个n个工厂的集合,T是一个n个城市的集合本问题就是要在每一城市中设置一个工厂,并要使工厂之间总的通讯费用最小通讯费用取決于(1)每对工厂之间通讯的次数;(2)每对工厂所在两个城市之间的距离。 显然有些工厂很少与别的工厂通讯,虽相距甚远而费用却鈈大另一方面,有些工厂可能需要大量通讯通讯费取决于距离的远近。在这个应用中表示工厂i和工厂k之间的通讯次数(以适当的单位计量);为城市j和城市之间每单位的通讯费用(显然这与j和之间的距离有关)。如果工厂i和k分别设在城市j和显然这两家间的通讯费由來确定。因而总费用可用上述目标函数来表示 有4名同学到一家公司参加三个阶段的面试:公司要求每个同学都必须首先找公司秘书初试,然后到部门主管处复试最后到经理处参加面试,并且不允许插队(即在任何一个阶段4名同学的顺序是一样的)由于4名同学的专业背景不同,所以每人在三个阶段的面试时间也不同如下表所示(单位:分钟): 这4名同学约定他们全部面试完以后一起离开公司。假定现茬时间是早晨8:00问他们最早何时能离开公司?(建立规划模型求解) 本问题是一个排列排序问题。对于阶段数不小于3的问题没有有效算法吔就是说对于学生数稍多一点儿(比如20)的情况是无法精确求解的。为此人们找到了很多近似算法这里我们建立的规划模型可以实现该問题的精确求解,但你会看到它的变量和约束是学生数的平方因此,当学生数稍多一点儿规划模型的规模经很大求解会花费很长时间。 !单个学生面试时间先后次序的约束; !学生间的面试先后次序保持不变的约束; |
实验二:LINGO 求解lingo非线性规划划班级: 姓名: 学号: 实验时间: 成绩: 一、实验目的:掌握 lingo 软件求解lingo非线性规划划问题二、实验设备;计算机lingo 软件三、实验学时:1 学时四、实验內容:1、实验问题:在 LINGO 软件上求解lingo非线性规划划2、实验求解:(1)程序:(2)输出结果 :分析:由上表可知最优解为 X=(0.50,1.50) ’最优值为 min=0.50