线性规划问题的lingo求解

第五章线性规划问题的 Lingo求解5.1 一般线性规划模型的建立与求解5.1.1 基本理论线性规划问题的标准形式是等约束的，用矩阵表示如下：一般线性规划问题都可以通过引入 松弛变量 与 剩余变量 的方法化成标准形式。线性规划模型的一般性质：(1)比例性 ，每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比。(2)可加性 ，每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关。(3)连续性 ，每个决策变量的取值都是连续的。比例性和可加性保证了目标函数和约束条件对于决策变量的线性性质，连续性则允许得到决策变量的实数最优解。单纯形算法的实质 ：在保证可行 (最小比值法则 )的前提下，先在可行解上取一个顶点，判断是否达到最优解，如果没有，则通过一定的规则 (入基，旋转等 )到另一个更优的顶点，如此迭代下去直到最优，或者判断不可行或者判断无界为止。5.1.2 应用举例例 5-1(运输问题 ) 两个粮库 A1,A2,向三个粮站 B1,B2,B3调运大米，两个粮库现存大米分别为 4t， 8t，三个两站至少需要大米分别为 2t,4t,5t，两个粮库到三个粮站的距离 (km)如下表，求使运费最低。B1 B2 B3 库存A1 12 24 8 4A2 30 12 24 8需求 2 4 5解： (1)问题分析：总需求量为 11t，小于总库存量 12t，所以问题可行。(2)从线性规划的三个要素出发， 决策变量 ：问题是各个粮仓向粮站调运了多少大米，此调运量就是决策变量。目标函数 ：运费和运量和距离有关系，即 t*km最小，所以要将运量与相应的距离相乘然后使总和最小。约束条件 ：两个粮库的库存量限制和三个粮站需求量的限制。(3)建立模型，设 A1,A2分别向 B1,B2,B3运送大米 x11,x12,x13,x21,x22,x23，则有：min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23s.t. x11+x12+x13=2x12+x22=4x13+x23=5x11,x12,x13,x21,x22,x23=0(4)转化成对应的 Lingo建模语言程序 1，求解模型，结果如下页图示：通过选择 Lingo|Generate|Display model将模型展开，方便查看求解报告的第三部分。相应的添加的剩余变量或者松弛变量。程序改进一、上面解法是一种傻瓜式的直接输入法，适用于程序规模不大的问题，如果问题规模很大的话用这种方式很费力，可以使用矩阵生成器来编写程序 2min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23s.t. x11+x12+x13+y1=4x21+x22+x23+y2=8x11+x21-y3=2x12+x22-y4=4x13+x23-y5=5x11,x12,x13,x21,x22,x23,y1,y2,y3,y4,y5=0转换成 Lingo语言如下所示：注： 1、写程序要习惯给程序用 title命名2、为了方便查看报告，用行号区分约束3、此程序的格式可以固定为标准形式的求解模式。程序改进三：可以减少引入的变量个数，将模型修改为下面的形式min f=12*x11+24*x12+8*x13+30*x21+12*x22+24*x23s.t. x11+x12+x13=0写成 lingo语言如下所示：注： 1、改程序把不等式约束全部转化为小于等于约束， 是为了将约束可以写到一个循环语句中实现 ，如果还有等是约束的话，则要在写一个循环语句来控制约束。2、当程序比较大的时候，一般将 约束按性质 进行分类程序改进四：将约束进行分类，代码如下：注： 1、在进行调试程序时，可以用 !号某些语句屏蔽，缩小寻找出错的范围。2、可以编写程序边运行，保证每行书写都是正确的3、常见的出错情况有：(1)定义了多个长度一样的集合，而在使用中区分不明确；(2)定义了同名的属性；(3)漏掉了括号；(4)分号不是英文半角；(5)使用的字母没有定义；(6)循环语句中元素下标颠倒或者不明；(7)约束错误变成不可行或者无界；(8)关系运算符误用成逻辑运算符；(9)函数调用错误等等 例 5-2 （ 阶段生产问题 ）某公司产品最大生产能力为 10000单位，每单位存储费 2元，预定的销售量与单位成本如下表所示：月份 单位成本 销售量1 70 60002 71 70003 80 120004 76 6000求一生产计划，使 (1)满足需求； (2)不超过生产能力； (3)成本 (生产成本与存储费之和最低 )问题分析：这是一个多阶段生产计划问题，设计多阶段存储，只需要制定 14月份的生产计划，不妨假定 1月初无库存， 4月底卖完，当月生产的不作为当月的库存，库存量无限制。模型建立（ 1）： 设 xi为第 i月产量， di为销售量， ei为存储费， ci为单位成本，则目标生产成本为 :第 j月到 j+1月的库存量 (记作第 j+1月的库存量 )应该是 1月到 j月的总产量减去 1月到 j月的总销售量，即：总的库存费用为：总成本为：即求总成本的最小值。约束条件 1：如果每个月都有非负的存储量，显然满足要求，可用约束：约束条件 3：产量限制， 0=xi=10000。综上，建立如下数学模型：约束条件 2： 4个月的总产量等于总需求量即：转成相应的 Lingo语言如下：模型改进 (2)：引入 库存变量 ，再利用库存平衡方程使模型更加流畅简洁。设 xi为第 i个月的产量， di为销售量， ei为存储费， ci为单位成本，设第 i个月的库存为 si,则：程序编写如下：模型改进 (3)：将该模型转化成 运输问题 。设 xij表示第 i个月生产的产品在第 j个月卖出去的数量， cij表示第 i个月生产的产品在第 j月卖出去时的生产成本与存储成本之和，dj表示第 j月的销售量，则生产月生产的产品在需求月卖出时单位总成本如下表所示： 需求月 1 需求月 2 需求月 3 需求月 4 产量生产月 1 70 72 74 76 10000生产月 2 71 73 75 10000生产月 3 80 82 10000生产月 4 76 10000销量 6000 7000 12000 6000建立模型如下：相应的 Lingo程序如下：例 5-3 （ 连续投资问题 ）某部门在今后 5年内考虑给下列项目投资，已知：(1)项目 A，从第 1年到第 4年每年初要投资，次年末回收本利 1.15；(2)项目 B，第 3年初投资，到第 5年末回收本利 1.25，最大投资 4万元 ;(3)项目 C，第 2年初投资，到第 5年末回收本利 1.40，最大投资 3万元；(4)项目 D，每年初购买国债，当年末回收本利 1.06;该部门现有资金 10万元，问应如何投资到第 5年末总资本最大。问题分析：将可能的投资情况设为变量，如下表所示第 1年 第 2年 第 3年 第 4年 第 5年A x1A x2A x3A x4AB x3BC x3CD x1D x2D x3D x4D x5D因为具有项目 D，所以可以认为该部门每年都把自己全部投出去，而且年末的总资本等于第二年初的总投资额。由此可建立模型如下：转换成 Lingo程序如下所示：5.2 灵敏性分析与影子价格5.2.1 灵敏性分析例 5-4(生产计划问题 )某工厂计划安排生产 I II两种产品，已知每种单位产品的利润，生产单位产品所需设备台时及 A,B两种原材料的消耗，现有原材料和设备台时的定额见下表所示：产品 I 产品 II 最大资源量设备 1 2 8台原材料 A 4 0 16kg原材料 B 0 4 12kg单位产品利润 2 3求 ： (1)怎么样安排生产使得工厂利润最大？ (2)产品 I的单位利润降低到 1.8万元，要不要改变生产计划，如果降低到 1万元呢？ (3)产品 II的单位利润增大到 5万元，要不要改变生产计划？ (4)如果产品 I,II的单位利润同时降低了 1万元，要不要改变生产计划？建立模型：用 x1,x2分别表示计划生产产品 I II的数量，可建立如下模型编写 lingo程序如下：程序执行结果：通过执行结果对问题进行分析：问题 1：安排生产产品 I为 4个单位， II为 2个单位，最大利润为 14万元。灵敏性分析：打开 LINGO中的灵敏性分析开关， LINGO|Options | General Solver | Dual Computations | Prices and Ranges 分析结果通过点击 Lingo | Range命令获得说明 1、 (1)红框内的部分是对目标函数进行的灵敏性分析，第一列是 变量 ，第二列是 对应的系数 ，第三列是 允许增加量 ，第四列是 允许减少量 ，允许增加和允许减少都是在 当前系数基础 上改变的。在其他变量系数都不变的情况下有：当 x1在 (2-0.5,2+)=(1.5, )之间变化时 ,最优解不变；当 x2在 (3-3,3+1)=(0,4)之间变化时，最优解不变。问题 2： 产品 I的单位利润降低到 1.8万元，在 (1.5, )之间，所以不改变生产计划；而降低到 1万元，则需要重新制定生产计划；问题 3： 5万不在 (0,4)范