用LINGO解线性规划和整数规划.doc

用LINGO解线性规划和整数规划在工程技术、经济管理、科学研究和日常生活等许多领域中，人们经常遇到的一类决策问题是：在一系列客观或主观限制条件下，寻求使关注的某个或多个指标达到最大（或最小）的决策。例如： 结构设计要在满足强度要求条件下选择材料的尺寸，使其总重量最轻； 资源分配要在有限资源约束下制定各用户的分配数量，使资源产生的总效益最大； 运输方案要在满足物资需求和装载条件下安排从各供应点到各需求点的运量和路线，使运输总费用最低； 生产计划要按照产品工艺流程和顾客需求，制定原料、零件、部件等订购、投产的日程和数量，尽量降低成本使利润最高。上述这种决策问题通常称为优化问题。人们解决这些优化问题的手段大致有以下几种：1依赖过去的经验判断面临的问题。这似乎切实可行，并且没有太大的风险，但是其处理过程会融入决策者太多的主观因素，难以客观地加以描述，从而无法确认结果的最优性。2做大量的试验反复比较。这固然比较真实可靠，但是常要花费太多的资金和人力，而且得到的最优结果基本上离不开开始设计的试验范围。3用数学建模的方法建立数学规划模型求解最优决策。虽然由于建模时要作适当的简化，可能使得结果不一定完全可行或达到实际上的最优，但是它基于客观规律和数据，又不需要多大的费用，具有前两种手段无可比拟的优点。如果在此基础上再辅之以适当的经验和试验，就可以期望得到实际问题的一个比较圆满的回答，是解决这种问题最有效、最常用的方法之一。1. 1.1 数学规划模型数学规划模型一般有三个要素：一是决策变量，通常是该问题要求解的那些未知量，不妨用n维向量表示；二是目标函数，通常是该问题要优化（最小或最大）的那个目标的数学表达式，它是决策变量x的函数，这里抽象地记作 f(x)；三是约束条件，由该问题对决策变量的限制条件给出，即x允许取值的范围,称可行域，常用一组关于x的不等式（也可是等式）gi(x)0(I=1,2,m)来界定。一般地，这类模型可表示成如下形式： opt z=f(x) （1） s.t. gi(x)0 （2）这里opt(optimize)是最优化的意思，可以是求极小min(minimize)或求极大max(maximize)；s.t.(subject to)是“受约束于”的意思，满足（2）式的解x称为可行解，同时满足（1）式，（2）式的解x*称为最优解。模型（1），（2）中：若决策变量x的所有分量xi( i =1,n)均为实数，且f、gi( i =1,m)都是线性函数时，称为线性规划；若f、gi 至少有一个非线性函数，则称为非线性规划；若x至少有一个分量只取整数，则称为整数规划。线性规划和非线性规划是连续规划，而整数规划是离散优化（组合优化），它们统称为数学规划。我们简介用LINGO解线性规划和整数规划问题。LINGO(Linear Interactive and Generai Optimizer)是由美国芝加哥大学的Linus Schrage 于1986年开发的优化计算软件包，LINGO可以用来求解线性规划、线性整数规划、二次规划和整数二次规划、非线性规划等问题。LINDO公司的主页为：。1.2 用LINGO求解线性规划问题例1 加工奶制品的生产计划。（I） 问题及建模：一奶制品加工厂用牛奶生产A1、A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1、A2能全部售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。试为该厂制定一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题：1） 若用35元可以购买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？数学模型 设每天用x1桶牛奶生产A1 ，用x2桶牛奶生产A2 解： 目标函数：设每天获利为z元。 x1桶牛奶可生产3x1公斤A1，获利24*3x1，x2桶牛奶可生产4x2公斤A2，获利16*4x2，故z=72x1+64x2约束条件： 、原料供应 生产A1、A2的原料（牛奶）总量不超过每天的供应50桶，即： x1+x250、劳动时间 生产A1、A2的总加工时间不超过每天正式工人总的劳动时间480小时，即： 12x1+8x2480、设备能力 A1的产量不得超过设备甲每天的加工能力100小时，即 3x1100、非负约束 x1、x2均不能为负值，即：x10，x20综上所述可得：Max z=72x1+64x2s.t. x1+x25012x1+8x24803x1100x10，x20因为，目标函数和约束条件都是线性的，所以这是一个线性规划问题（linear programming，LP），求出的最优解将给出使净利润最大的生产计划，要讨论的问题需要考虑参数的变化对最优解和影响，一般称为敏感性（或灵敏度）分析。（II） 用LINGO求解在LINGO模型窗口输入：max =72*x1+64*x2; x1+x2=50;12*x1+8*x2=480;3*x1=100;注：由于LINGO中已假设所有的变量都是非负的，所以非负约束条件不必输入；LINGO也不区分变量中的大小写字符（实际上任何小写字符将被转换为大写字符）。 然后，用鼠标单击菜单中的“求解”命令（SOLVE）或点击工具栏上的“”就可以得到解答，结果窗口显示如下： Global optimal solution found. Objective value: 3360.000 Infeasibilities: 0.000000 Total solver iterations: 2 Variable Value Reduced Cost X1 20.00000 0.000000 X2 30.00000 0.000000 Row Slack or Surplus Dual Price 1 3360.000 1.000000 2 0.000000 48.00000 3 0.000000 2.000000 4 40.00000 0.000000其中：Value给出最优解中各变量（Variabl）的值：x1=20.000000，x2=30.000000。Reduced Cost（缩减成本系数）的含义是(max型问题)：基变量的REDUCED COST值为0，对于非基变量，相应的REDUCED COST值表示当非基变量增加一个单位时（其它非基变量保持不变）目标函数减少的量。本例中两个变量都是基变量。松弛变量：使添加变量，使约束条件变为等式.若松弛变量对应的是小于等于约束，说明这个约束还有余地，还有一定量的资源没有用Slack or Surplus给出松弛变量的值，表示约束是否取等式约束；第2、第3行松弛变量均为0，说明对于最优解而言，两个约束均取等式约束；第4行松弛变量为40.000000，说明对于最优解而言，这个约束取不等式约束。当求目标函数的最大值时，增加的数量就是改进的数量，所以影子价格就等于对偶价格；当求目标函数的最小值时，改进的数量应该是减少的数量，所以影子价格即为负的对偶价格Dual Price给出约束的影子价格（也称为对偶价格）的值：第2、第3、第4行（约束）对应的影子价格分别48.000000，2.000000，0.000000。具体地，计算结果说明：这个线性规划的最优解为x1=20，x2=30，最优值为z=3360，即用20桶牛奶生产A1, 30桶牛奶生产A2，可获最大利润3360元。输出中除了告诉我们问题的最优解和最优值以外，还有许多对分析结果有用的信息，下面结合题目中提出的3个附加问题给予说明。 3个约束条件的右端不妨看作3种“资源”：原料、劳动时间、车间甲的加工能力。Slack or Surplus给出这3种资源在最优解下是否有剩余：原料、劳动时间的剩余均为零，车间甲尚余40（公斤）加工能力。目标函数可以看作“效益”，成为紧约束的“资源”一旦增加，“效益”必然跟着增长。Dual Price给出这3种资源在最优解下“资源”增加1个单位时“效益”的增量：原料增加1个单位（1桶牛奶）时利润增长48（元），劳动时间增加1个单位（1小时）时利润增长2（元），而增加非紧约束车间甲的能力显然不会使利润增长。这里，“效益”的增量可以看作“资源”的潜在价值，经济学上称为影子价格，即1桶牛奶的影子价格为48元，1小时劳动的影子价格为2元，车间甲的影子价格为零。用影子价格的概念很容易回答附加问题1）：用35元可以买到1桶牛奶，低于1桶牛奶的影子价格48，当然应该作这项投资。回答附加问题2）：聘用临时工人以增加劳动时间，付给的工资低于劳动时间的影子价格才可以增加利润，所以工资最多是每小时2元。目标函数的系数发生变化时（假定约束条件不变），最优解和最优值会改变吗？上面输出给出了最优基不变条件下目标函数系数的允许变化范围x1的系数为（72-8，72+24）=（64，96）；x2的系数为（64-16，64+8）=（48，72）。注意：x1系数的允许范围需要x2系数64不变，反之亦然。由于目标函数的费用系数变化并不影响约束条件，因此此时最优基不变可以保证最优解也不变，但最优值变化。用这个结果很容易回答附加问题3）：若每公斤A1的获利增加到30元，则x1系数变为303=90，在允许范围内，所以不应改变生产计划，但最优值变为9020+6430=3720。 总之：用LINGO求解加工奶制品的生产计划，结果如下：20桶牛奶生产A1, 30桶生产A2，利润3360元。1）35元可买到1桶牛奶，要买吗？由于原料的影子价格为48，35 =50;x2+2*x4+x5+3*x6=20;x3+x5+2*x7=15;gin(x1);gin(x2);gin(x3);gin(x4);gin(x5);gin(x6);gin(x7); end可以得到最优解如下： Global optimal solution found. Objective value: 27.00000 Objective bound: 27.00000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost X1 0.000000 3.000000 X2 12.00000 1.000000 X3 0.000000 3.000000 X4 0.000000 3.000000 X5 15.00000 1.000000 X6 0.000000 1.000000 X7 0.000000 3.000000 Row Slack or Surplus Dual Price 1 27.00000 -1.000000 2 1.000000 0.000000 3 7.000000 0.000000 4 0.000000 0.000000即：按照模式2切割12根原料钢管，按照模式5切割15根原料钢管，共27根，总余料量27m。显然，在总余料量最小的目标下，最优解将是使用余料尽可能小的切割模式（模式2和模式5的余料为1m），这会导致切割原料钢管的总根数较多。问题（2）的求解非线性整数规划模型（7）（15）虽然用LINGO软件可以直接求解，但为了减少运行时间，可以增加一些显然的约束条件，从而缩小可行解的搜索范围。上取整函数：例：上取整函数：例：例如，由于3种切割模式的排列顺序是无关要紧的，所以不妨增加以下约束： x1x2x3 （16）又如，注意到所需原料钢管的总根数有明显的上界和下界。首先，原料钢管的根数不可能少于（根）。其次，考虑一种非常特殊的生产计划：第一种切割模式下只生产4m钢管，一根原料钢管切割成4根4m钢管，为满足50根4m钢管的需求，需要13根原料钢管；第二种切割模式下只生产5m，6m钢管，一根原料钢管切割成1根5m钢管和2根6m钢管，为满足10根5m和20根6m钢管的需求，需要10根原料钢管；第三种切割模式下只生产8m钢管，一根原料钢管切割成2根8m钢管，为满足15根8m钢管的需求，需要8根原料钢管。于是满足要求的这种生产计划共需要13+10+8=31根原料钢管，这就得到了最优解的一个上界，所以可增加以下约束： 26x1+x2+x331 (17)将式（7）（17）构成的模型输入LINGO如下：model:min=x1+x2+x3;r11*x1+r12*x2+r13*x3=50; r21*x1+r22*x2+r23*x3=10; r31*x1+r32*x2+r33*x3=20; r41*x1+r42*x2+r43*x3=15; 4*r11+5*r21+6*r31+8*r41=19; 4*r12+5*r22+6*r32+8*r42=19; 4*r13+5*r23+6*r33+8*r43=16; 4*r12+5*r22+6*r32+8*r42=16;4*r13+5*r23+6*r33+8*r43=16;x1+x2+x3=26;x1+x2+x3=x2;x2=x3;gin(x1) ; gin(x2) ; gin(x3) ;gin(r11) ; gin(r12) ; gin(r13) ;gin(r21) ; gin(r22) ; gin(r23) ;gin(r31) ; gin(r32) ; gin(r33) ;gin(r41) ; gin(r42) ; gin(r43) ;end得到结果如下： Global optimal solution found. Objective value: 28.00000 Objective bound: 28.00000 Infeasibilities: 0.000000 Extended solver steps: 1 Total solver iterations: 129601 Variable Value X1 10.00000 X2 10.00000 X3 8.000000 R11 2.000000 R12 3.000000 R13 0.000000 R21 1.000000 R22 0.000000 R23 0.000000 R31 1.000000 R32 1.000000 R33 0.000000 R41 0.000000 R42 0.000000 R43 2.000000 Row Slack or Surplus 1 28.00000 2 0.000000 3 0.000000 4 0.000000 5 1.000000 6 0.000000 7 1.000000 8 3.000000 9 3.000000 10 2.000000 11 0.000000 12 2.000000 13 3.000000 14 0.000000 15 2.000000即按照模式1，2，3分别切割10根，10根，8根原料钢管，使用原料钢管总根数为28根。第一种切割模式下一根原料钢管切割成3根4m钢管和1根6m钢管；第二种切割模式下一根原料钢管切割成2根4m钢管，1根5m钢管和1根6m钢管；第三种切割模式下一根原料钢管切割成2根8m钢管。2.3 练习实验目的:1练习建立实际问题的整数规划模型。2掌握用和LINGO软件求解整数规划问题。实验内容:1.（指派问题）考虑指派n个人完成n项任务（每人单独承担一项任务），使所需的总完成时间（成本）尽可能短已知某指派问题的有关数据（每人完成各任务所需的时间）如下表所示，试求解该指派问题。 任务工人12341151821242192322183261816194192123172工业区发展规划某小城市的政府当局拟将一块英亩的土地发展成工业区以增加税收，有家工厂与政府当局签定了初步协议，市府允诺对这些工厂所需的资金，施工力量及长期出租有关厂房及设备方面加以支持。 市府现有一切公用设施，且最近完成了一项为这些工厂所需的发展，以便需求能有节制地增长，可用资金最多六百万元。对该地劳动力情况的研究表明，可得到的本地临时工与外地工不超过表1所列数字: 劳动力 表 种类普通工半技工技工职员技术员管理员最大数40018012015012033平均年收入500070001200050001400030000 研究表明，在缴纳州与国家的税收后，净收在本地消费的情况（计算是以每种收水平的家庭的平均大小为基础进行的）列于表中。劳动力消费形式表 种类普通工半技工技工职员技术员管理员州,国税占总收入的百分比10% 12%16%10%18%24%年净收入450061601010045001150022800流入市区的现金4050524070703830740012520 还估算了城市从财产税与销售收入及公用设施、燃料、卫生设施及其它方面所得的税收，平均为每人在市内消费额的2.5%，市府从各种工人所得税收汇总于表1-3中: 城市得自每个劳动力的税收(表1-3) 单位：元 工人种类普通工半技工技工职员技术员管理员平均税收10113117796187313 城市拥有的公共设施可承担下列负荷:1. 电力；14.5百万度年 2. 水；75百万加仑年 3. .煤气：40百万立方英尺年4. 下水：40百万加仑年 5. .废品处理；2万吨年 城市的公共服务所得的单位利润；1.电力：0.0007元度 2.水：7元百万加仑 3.下水：1元百万加仑 4.煤气：0.004元立方英尺 5.废品；0.15元吨市政府与之签订初步协定的五家拟建工厂，将主要使用本地原材料，加上工厂引起的其它利润虽将提高社会的收入水平，但因不能确定的加以定量，故在最优化对策中未于考虑。然而，在决定实施此计划时，将这些看作为有利的因素。表4：各工厂所需的最大与最小厂房面积。工厂 主要产品电子器件压力罐铸件塑料薄膜再生轮胎最大面积(平方英尺)120,00080,00070,000100,000150,000最小面积(平方英尺