Lindo使用教程.pdf

1 第六讲、第六讲、lindo 软件简介软件简介 一、lindo 软件简介 运筹学要用到的工具就是 lindo，它的作用就是负责把问题的最优决策求出来，省去大 量难以想象的人工计算。lindo 软件是一种专门用于求解数学规划问题的软件包。由于 lindo 执行速度很快、易于方便输入、求解和分析数学规划问题。因此在数学、科研和工 业界得到广泛应用。lindo 主要用于解线性规划、非线性规划、二次规划和整数规划等问 题。也可以用于一些非线性和线性方程组的求解以及代数方程求根等。lindo 中包含了一 种建模语言和许多常用的数学函数（包括大量概论函数） ，可供使用者建立规划问题时调用。 一般用 lindo(linear, interactive, and discrete optimizer)是一个解决二次线性整数规 划问题的方便而强大的工具。这些问题主要出现在商业、工业、研究和政府等领域。已被证 实 lindo 能在其中发挥巨大作用的具体事务包括：产品分销、成分混合、生产与个人事务 安排、存货管理lindo 可以大展拳脚的领域是多不胜数的。其中 lindo 6 .1 学生版至 多可求解多达 300 个变量和 150 个约束的规划问题。在大型的机器上，lindo 被用来解决 一些拥有超过 50,000 个约束条件和 200,000 万个变量的大规模复杂问题。 lindo 的主要设 计原则是，如果一个用户只是想解决一个简单的问题，就不应该在学习 lindo 的基本特性 2 上花费太多的准备成本。例如，解决以下这样一个问题： maxmize 2x + 3y subject to 4x + 3y y 是错的，应写成 x-y0； 12） 、式子的左端只能是变量及其系数，如：10x+y-10=0 是错的； 应写成 10x+y=10 13） 、一般 lindo 中不能接受括号“ （） “和逗号“， “，例：400(x1+x2) 需写成 400x1+400x2； 10,000 需写成 10000； 14） 、表达式应当已经过简化。不能出现 2 x1+3 x2-4 x1，而应写成-2x1+3 x2。 第一节 案例 下面就先举一个例说明 lindo 软件的最基本的用法。 输入一个模型输入一个模型 现在让我们用例子来说明怎样输入和求解一个模型。当我们打开 lindo 后，屏幕将出现 以下窗口： 在前面，我们假设的目标函数是：max 10x 15y，同时，我们已经对 x 和 y 加以限制 了，即：x = = = 建模过程在这里就省略了，直接得到如下的线性规划方程： 目标函数：max z=x1+x2+x3+x4 约束条件：x5+x6+x7+x8=250000 x1+x5=0 16.5x1+2.0x2-4.0x3+17x4=0 7.5x5-7.0x6-13.0x7+8.0x8=0 xj=0(j=1,2.,8) 下面我们就用 lindo 来解这一优化问题。 输入语句： max(不区分大小写) x1+x2+x3+x4 st(大写或写 subject to) x5+x6+x7+x8=250000 x1+x5=0 16.5x1+2.0x2-4.0x3+17x4=0 7.5x5-7.0x6-13.0x7+8.0x8=0 15 end 然后再按运算符键即可得结果。 lindo 是规定 xj非负的，我们可发现输入方式与我们的数学书写的形式基本一致，运算 后，计算机会问您是否需要灵敏度分析，在这里，我们选择“是”，结果如下： 16 17 下面给出其结果的一般解释： “lp optimum found at step 6”表示 lindo 在（用单纯形法）次迭代或旋转后得到最优 解。 “objective function value 1)933400.0”表示最优目标值为 933400。 “value”给出最优解中各变量的值。 “slack or surplus”给出松弛变量的值。上例中 slk 2= 第二行松弛变量（模型第一 行表示目标函数，所以第二行对应第一个约束） “reduce cost”列出最优单纯形表中判别数所在行的变量的系数，表示当变量有微小变动 时， 目标函数的变化率， 其中基变量的reduce cost 值应为， 对于非基变量xj相应的reduce cost 值表示 xj增加一个单位（此时假定其他非基变量保持不变）时目标函数减小的量（max 型问题）。上例中：x1 对应的 reduce cost 值为，表示当 x1=1 时，目标函数值不变。 “dual price”（对偶价格）列出最优单纯形表中判别数所在行的松弛变量的系数，表示当 对应约束有微小变动时，目标函数的变化率，输出结果中对应每一个约束有一个对偶价格。 若其数值为 x， 表示对应约束中不等式右端项若增加一个单位， 目标函数将增加 x 个单位 （max 型问题）。上例中：第二行对应的对偶价格值应为-，表示当约束 ）x5 + x6 + x7 + x8250000 变为 ）x5 + x6 + x7 + x8250001 时，目标函数值933400-1933399 当 reduce cost 或 dual price 的值为。表示当微小扰动不影响目标函数。有时，通过 分析 dual price，也可对产生不可行问题的原因有所了解。 灵敏度分析：如果做敏感性分析，则系统报告当目标函数的费用系数和约束右端项在什么范 围变化（此时假定其他系数保持不变）时，最优基保持不变。报告中 infinity 表示正无穷， 如上例：目标函数中 x的变量系数为，当它在1-1.154137,1-0-0.154137,1 变 化时，最优基保持不变 。 18 第一个约束右端项为 250000，当它在250000-234752.984375,250000+186222.0625 15247.015625,436222.0625 范围变化时，最优基保持不变 。 当我们要判断表达式输入是否有错误时，也可以使用菜单“reports“的”picture“选项。 若想获得灵敏度分析，可用“reports“的”rang“选项。 若需显示单纯形表，可执行“reports“的”tab lean“选项。 例 2有四个工人，要分别指派他们完成四项不同的工作，每个人做各项工作所消耗的时间 如表。问应该如何指派，才能使总的消耗时间为最小？ 工作 工作 所耗时间所耗时间 工人工人 a a b b c c d d 甲 甲 15 18 21 24 乙 乙 19 23 22 18 丙 丙 26 17 16 19 丁 丁 19 21 23 17 这是一道典型的整数规则问题。 我们记派第 i 去做工作记为 xij 注意到每人只能做一项工作。每项工作一人做。我们得到目标函数为约束条件： min 15x11+19x21+26x31+19x41+18x12+23x22+17x32+21x42+24x13+22x23+16x33+23x43+24x14+1 8x24+19x34+17x44 s.t. 19 x11+x12+x13+x14=1 x21+x22+x23+x24=1 x31+x32+x33+x34=1 x41+x42+x43+x44=1 x11+x21+x31+x41=1 x12+x22+x32+x42=1 x13+x23+x33+x43=1 x14+x24+x34+x44=1 end int 16 20 21 运行后我们可得到最优目标值为 71。 在用 lindo 解整数规划（ip）问题时，只要在 end 后加上标识即可，其中解 0/1 规划的 用命令：int name 或 int n (n 指前 n 个变量标识为 0/1 型)。解混合型整数规划则用 gin 来标识。 例 3某学校举办暑期辅导班，欲打广告以扩大影响面，已知户外广告的影响面 是 192次，电视的影响面为 36次，其它为 12次，已知户外广告的费用 是 15000 元次，电视为 2400 元次，其它为 12000 元次，总费用不得超 过 100000 元，而户外广告投入不得低于 65000 元，次数不能少于 2 次，电视 不能少于 3 次，其它不能多于 2 次。请确定使影响面最大的符合条件的方案。 由题意，我们可以建立起线性规划模型，即： max e（x）192x1+36x2+12x3 满足 15000x1+2400x2+12000x3=65000 x1=2 x2=3 x3=0 且为整数 如果想要解这样的模型，我们可以看到，它存在着几个问题： ? 变量有三个； 22 ? 约束条件有大于和小于； ? 还有整数约束。 一般的方法： ? 用单纯型法 ? 加剩余变量或人工变量成为等式，不断涌线性变换，直到最优解出现或无解。 这样方法都太麻烦了，下面，我们就借助于 lindo 软件来解这样的模型。 还是按照前面的步骤来做。 键入： 然后再按运算符键即可得结果。 23 这样，我们就很方便的得到了所需要的答案。 例 4广告媒体选择 娱悦湖滨开发公司（relax-and-enjoy lake development corporation）在一处私人湖 泊的附近开发度假别墅，打算向方圆 100 英里之内的中上等收入家庭出售。娱悦已请包括布 恩（boone）在内的几家广告公司设计推广计划。布恩对若干广告媒体和拟覆盖的市场作考 24 察之后，提出一个初步计划，在头一个月拟将广告局限在 5 家媒体上，到月末再根据实绩对 计划进行评价。布恩收集了有关潜在置产家庭的数量、广告成本、各媒体可提供的最大时间 量和期望曝露量。曝露以管理层判断的每家媒体上一则广告的相对价值为计量单位，在考虑 诸如受众背景（年龄、收入、受教育程度等） 、展现的形象和广告质量等因素的基础上，布 恩结合自己的业务经验作出判断计量。所获信息见下表： 广告媒体 被调查的 潜在置产 家庭数目 广告 成本 每月可提 供的最大 时间量 期望曝 露单位 wkla 电视台 日间（每分钟） 1000 $150015 65 wkla 电视台 晚间（每 30 秒） 2000 $300010 90 日报(整版) 晨报 1500 $400 25 40 周日新闻杂志（半版彩色） 星期天新闻 2500 $10004 60 knop 广播电台 上午 8:00 或 下午 5:00 pm（每 30 秒） 300 $100 30 20 娱悦给布恩$30000 作为头一个月的预算，以期望曝露单位最大化为目标，同时提出以下 配置原则：至少打出 10 则电视广告，至少要达中 50000 名潜在置产者，而花在电视广告上 的钱不能超过$18000。 根据要求，我们可以建立如下的线性规划模型： max p = 65x1 + 90x2 + 40x3 + 60x4 + 20x5 s.t. x1 15 x2 10 x3 25 25 x4 4 x5 30 1500x1 + 3000x2 + 400x3 + 1000x4 + 100x5 30000 x1 + x2 10 1500x1 + 3000x2 18000 1000x1 + 2000x2 + 1500x3 + 2500x4 + 300x5 50000 x1 , x2 , x3 , x4 , x5 0 借助 lindo 软件，我们可以很快地解出这个模型，从而得到我们所需要的方案： 26 计算结果： 广 告 媒 体 月 频 度 广告成本 wkla 电视台 日间（每分钟） 10 $15000 27 日报(整版) 晨报 25 10000 周日新闻杂志（半版彩色） 星期天新闻 2 2000 knop 广播电台 上午 8:00 或下午 5:00 pm（每 30 秒） 30 3000 布恩可得到这样一个答案：可达中受众总数 61500 人；期望曝露单位总量 2370；总成本为 $30000。 例 5投资组合 惠尔托互助基金（welte mutual funds, inc.）刚刚将$1000000 企业债券转换成现金， 欲寻求新的投资机会。高级财务分析师推荐了 5 家投资对象： 对 象 预期回报率（%） 大西洋石油 7.3 太平洋石油 10.3 美国在线-时代华纳 6.4 戴尔计算机 7.5 政府债券 4.5 基金管理层对投资组合有如下指导意见： 1石油和信息两类企业都不得占投资额的 50%以上。 2政府证券投资至少相当于信息企业的 25%。 3对太平洋石油的投资不得超过对两石油企业投资合计的 60%。 同样，根据要求，我们建立如下的线性规划模型： max p = 0.073x1 + 0.103x2 + 0.064x3 + 0.075x4 + 0.045x5 s.t. x1 + x2 + x3 + x4 + x5 = 1000000 x1 + x2 500000 x1 + x2 0.5(1000000) x3 + x4 500000 x3 + x4 0.5(1000000) -0