《讲义：用lingo解线性规划和整数规划》由会员分享，可在线阅读，更多相关《讲义：用lingo解线性规划和整数规划（19页珍藏版）》请在金锄头文库上搜索。
1、用LINGO解线性规划和整数规划在工程技术、经济管理、科学研究和日常生活等许多领域中，人们经常遇到的一类决策问题是：在一系列客观或主观限制条件下，寻求使关注的某个或多个指标达到最大（或最小）的决策。例如： 结构设计要在满足强度要求条件下选择材料的尺寸，使其总重量最轻； 资源分配要在有限资源约束下制定各用户的分配数量，使资源产生的总效益最大； 运输方案要在满足物资需求和装载条件下安排从各供应点到各需求点的运量和路线，使运输总费用最低； 生产计划要按照产品工艺流程和顾客需求，制定原料、零件、部件等订购、投产的日程和数量，尽量降低成本使利润最高。上述这种决策问题通常称为优化问题。人们解决这些优化问题
2、的手段大致有以下几种：1依赖过去的经验判断面临的问题。这似乎切实可行，并且没有太大的风险，但是其处理过程会融入决策者太多的主观因素，难以客观地加以描述，从而无法确认结果的最优性。2做大量的试验反复比较。这固然比较真实可靠，但是常要花费太多的资金和人力，而且得到的最优结果基本上离不开开始设计的试验范围。3用数学建模的方法建立数学规划模型求解最优决策。虽然由于建模时要作适当的简化，可能使得结果不一定完全可行或达到实际上的最优，但是它基于客观规律和数据，又不需要多大的费用，具有前两种手段无可比拟的优点。如果在此基础上再辅之以适当的经验和试验，就可以期望得到实际问题的一个比较圆满的回答，是解决这种问题
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)或求
4、极大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 O
5、ptimizer)是由美国芝加哥大学的Linus Schrage 于1986年开发的优化计算软件包，LINGO可以用来求解线性规划、线性整数规划、二次规划和整数二次规划、非线性规划等问题。LINDO公司的主页为：http:/。1.2 用LINGO求解线性规划问题例1 加工奶制品的生产计划。（I） 问题及建模：一奶制品加工厂用牛奶生产A1、A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1、A2能全部售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为4
6、80小时，并且设备甲每天至多能加工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约
7、束条件： 、原料供应 生产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），求出的最优解将给出使净利润最大的生产计
8、划，要讨论的问题需要考虑参数的变化对最优解和影响，一般称为敏感性（或灵敏度）分析。（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
9、.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。Reduce
10、d Cost（缩减成本系数）的含义是(max型问题)：基变量的REDUCED COST值为0，对于非基变量，相应的REDUCED COST值表示当非基变量增加一个单位时（其它非基变量保持不变）目标函数减少的量。本例中两个变量都是基变量。松弛变量：使添加变量，使约束条件变为等式.若松弛变量对应的是小于等于约束，说明这个约束还有余地，还有一定量的资源没有用。Slack or Surplus给出松弛变量的值，表示约束是否取等式约束；第2、第3行松弛变量均为0，说明对于最优解而言，两个约束均取等式约束；第4行松弛变量为40.000000，说明对于最优解而言，这个约束取不等式约束。当求目标函数的最大值时
11、，增加的数量就是改进的数量，所以影子价格就等于对偶价格；当求目标函数的最小值时，改进的数量应该是减少的数量，所以影子价格即为负的对偶价格Dual Price给出约束的影子价格（也称为对偶价格）的值：第2、第3、第4行（约束）对应的影子价格分别48.000000，2.000000，0.000000。具体地，计算结果说明：这个线性规划的最优解为x1=20，x2=30，最优值为z=3360，即用20桶牛奶生产A1, 30桶牛奶生产A2，可获最大利润3360元。输出中除了告诉我们问题的最优解和最优值以外，还有许多对分析结果有用的信息，下面结合题目中提出的3个附加问题给予说明。 3个约束条件的右端不妨看
12、作3种“资源”：原料、劳动时间、车间甲的加工能力。Slack or Surplus给出这3种资源在最优解下是否有剩余：原料、劳动时间的剩余均为零，车间甲尚余40（公斤）加工能力。目标函数可以看作“效益”，成为紧约束的“资源”一旦增加，“效益”必然跟着增长。Dual Price给出这3种资源在最优解下“资源”增加1个单位时“效益”的增量：原料增加1个单位（1桶牛奶）时利润增长48（元），劳动时间增加1个单位（1小时）时利润增长2（元），而增加非紧约束车间甲的能力显然不会使利润增长。这里，“效益”的增量可以看作“资源”的潜在价值，经济学上称为影子价格，即1桶牛奶的影子价格为48元，1小时劳动的影子
13、价格为2元，车间甲的影子价格为零。用影子价格的概念很容易回答：附加问题1）的第1问：用35元可以买到1桶牛奶，低于1桶牛奶的影子价格48，当然应该作这项投资。附加问题2）：聘用临时工人以增加劳动时间，付给的工资低于劳动时间的影子价格才可以增加利润，所以工资最多是每小时2元。要回答附加问题3）及1）的第2问，需要做灵敏度分析。在Lingo中，欲做灵敏度分析，需要在求解前先作设置，方法如下：方法一：先设置启动灵敏度分析功能，方法是“LINGO（或程序） Options（选项，或设置） General Solver Tab（通用求解程序，或一般求解器） 在Dual Computations（对偶价格
14、和灵感性分析）列表框中，选择Prices & Ranges（对偶价格和灵感性分析）”，设置好后，先“求解”得到基本结果，再则通过菜单操作“Lingo Range（或“程序变程，或Lingo灵敏性分析”）即可求得灵敏度分析结果。方法二：直接用命令计算，方法是当某一规划模型求解后，打开“command window（命令窗口）”，操作方法是：“窗口command - window”），然后在命令窗口中输入“Range 回车”即可得分析结果。注意：、lingo不能做整数规划的灵敏度分析。、当不需要灵敏度分析是不要启动该功能，因为该功能需要较大的系统开支。允许增长值目标系数范围本例的灵敏度分析结果如下：Ranges in which the basis is unchanged:允许减少值当前系数
