线性规划与LINGO编程.ppt

内容说明 以下内容在 数学建模与数学实验 第二版 汪晓银 周保平主编 第3章 2 1什么是数学规划2 2连续性线性规划2 3敏感性分析2 4整数线性规划2 50 1规划 内容说明 数学规划俗称最优化 首先是一种理念 其次才是一种方法 它所追求的是一种 至善 之道 一种追求卓越的精神 2 1什么是数学规划 小明同学 烧一壶水要8分钟 灌开水要1分钟 取牛奶和报纸要5分钟 整理书包要6分钟 为了尽快做完这些事 怎样安排才能使时间最少 最少需要几分钟 十个人各提一只水桶 同时到水龙头前打水 设水龙头注满第一个人的桶需要1分钟 注满第二个人的桶需要2分钟 依此类推 注满第几个人的桶就需要几分钟 如果只有一只水龙头 适当安排这10个人的顺序 就可以使每个人所费的时间总和尽可能小 问这个总费时至少是几分钟 2 1什么是数学规划 数学规划 最优化 作为一门学科孕育于20世纪的30年代 诞生于第二次世界大战弥漫的硝烟中 数学规划指在一系列客观或主观限制条件下 寻求合理分配有限资源使所关注的某个或多个指标达到最大 或最小 的数学理论和方法 是运筹学里一个十分重要的分支 2 1什么是数学规划 最优化问题的数学模型的一般形式为 1 2 三个要素 决策变量decisionbariable 目标函数objectivefunction 约束条件constraints 2 1什么是数学规划 约束条件 2 所确定的x的范围称为可行域feasibleregion 满足 2 的解x称为可行解feasiblesolution 同时满足 1 2 的解x称为最优解Optimalsolution 整个可行域上的最优解称为全局最优解globaloptimalsolution 可行域中某个领域上的最优解称为局部最优解localoptimalsolution 最优解所对应的目标函数值称为最优值optimum 2 1什么是数学规划 一 按有无约束条件 2 可分为 1 无约束优化unconstrainedoptimization 2 约束优化constrainedoptimization 大部分实际问题都是约束优化问题 优化模型的分类 2 1什么是数学规划 二 按决策变量取值是否连续可分为 1 数学规划或连续优化 可继续划分为线性规划 LP Linearprogramming和非线性规划 NLP Nonlinearprogramming 在非线性规划中有一种规划叫做二次规划 QP Quadraticprogramming 目标为二次函数 约束为线性函数 2 离散优化或组合优化 包含 整数规划 IP Integerprogramming 整数规划中又包含很重要的一类规划 0 1 整数 规划Zero oneprogramming 这类规划问题的决策变量只取0或者1 2 1什么是数学规划 三 按目标的多少可分为 1 单目标规划 2 多目标规划 四 按模型中参数和变量是否具有不确定性可分为 1 确定性规划 2 不确定性规划 五 按问题求解的特性可分为 1 目标规划 2 动态规划 3 多层规划 4 网络优化 5 等等 2 1什么是数学规划 LINGO软件和MATLAB软件 对于LINGO软件 线性优化求解程序通常使用单纯形法simplexmethod 单纯形法虽然在实际应用中是最好最有效的方法 但对某些问题具有指数阶的复杂性 为了能解大规模问题 也提供了内点算法interiorpointmethod备选 LINGO中一般称为障碍法 即barrier 非线性优化求解程序采用的是顺序线性规划法 也可用顺序二次规划法 广义既约梯度法 另外可以使用多初始点 LINGO中称multistart 找多个局部最优解增加找全局最优解的可能 还具有全局求解程序 分解原问题成一系列的凸规划 求解优化问题常用的软件 2 1什么是数学规划 线性规划的一般形式 2 2连续性线性规划 一般线性规划问题都可以通过引入非负的松弛变量slackvariable与非负的剩余变量surplusv ariable的方法化为标准形式 约束全是等约束 线性规划问题的可行域feasibleregion是一个凸集convexset 任意两点的连线上的点都在区域内部 可以看作是没有凹坑的凸多面体 所以最优解Optimalsolution point在凸多面体的某个顶点上达到 求解方法 单纯形算法simplexmethod 2 2连续性线性规划 1 比例性 每个决策变量对目标函数以及右端项的贡献与该决策变量的取值成正比 2 可加性 每个决策变量对目标函数以及右端项的贡献与其他决策变量的取值无关 3 连续性 每个决策变量的取值都是连续的 连续线性规划问题的性质 要解决的问题的目标可以用数值指标反映对于要实现的目标有多种方案可选择有影响决策的若干约束条件 2 2连续性线性规划 例1运输问题 2 2连续性线性规划 解设A1 A2调运到三个粮站的大米分别为x1 x2 x3 x4 x5 x6吨 题设量可总到下表 2 2连续性线性规划 结合存量限制和需量限制得数学模型 2 2连续性线性规划 程序编写1model min 12 x1 24 x2 8 x3 30 x4 12 x5 24 x6 x1 x2 x32 x2 x5 4 x3 x6 5 end 提示 课件中的程序请先粘贴在记事本中再转帖于lingo软件中 2 2连续性线性规划 运行结果Globaloptimalsolutionfound Objectivevalue 160 0000Totalsolveriterations 0VariableValueReducedCostX12 0000000 000000X20 00000028 00000X32 0000000 000000X40 0000002 000000X54 0000000 000000X63 0000000 000000RowSlackorSurplusDualPrice1160 0000 1 00000020 00000016 0000031 0000000 00000040 000000 28 0000050 000000 12 0000060 000000 24 00000 2 2连续性线性规划 变量更换为 2 2连续性线性规划 模型 2 2连续性线性规划 程序编写MODEL TITLE调运大米的运输问题程序3 定义集合段 SETS LIANGKU 1 2 A 定义粮库的集合 LIANGZHAN 1 3 B 定义粮站的集合 YULIANG LIANGKU LIANGZHAN X C 定义运量和距离 ENDSETSDATA 粮库到粮站的距离 C 12248301224 2 2连续性线性规划 粮库的限量 A 48 粮站的限量 B 245 ENDDATA OBJ MIN SUM YULIANG C X 粮库上限的约束 FOR LIANGKU I LK SUM LIANGZHAN J X I J B J END 2 2连续性线性规划 程序的调试1 直接点击运行 如果出错会弹出错误提示 根据提示做相应的修改 2 可以用 把约束变成说明语句 而把这条语句屏蔽掉 缩小寻找出错的范围 3 可以边写程序边运行 保证每行书写都是正确的程序 2 2连续性线性规划 例2阶段生产问题 某公司生产某产品 最大生产能力为10000单位 每单位存储费2元 预定的销售量与单位成本如下 求一生产计划 使1 满足需求 2 不超过生产能力 3 成本 生产成本与存储费之和 最低 2 2连续性线性规划 解假定1月初无库存 4月底买完 当月生产的不库存 库存量无限制 2 2连续性线性规划 model title生产计划程序1 Sets yuefen 1 4 c x e d endsetsdata c 70718076 d 60007000120006000 e 2222 a 10000 enddatamin sum yuefen c x sum yuefen j j lt 4 sum yuefen i i le j x d e j 1 for yuefen j j lt 4 sum yuefen i i le j x sum yuefen i i le j d sum yuefen x sum yuefen d for yuefen x a end 2 2连续性线性规划 2 2连续性线性规划 Model Title生产计划程序2 Sets yuefen 1 4 c x e d s endsetsdata c 70718076 d 60007000120006000 e 2222 a 10000 enddatamin sum yuefen c x e s for yuefen i i lt 4 s i 1 s i x i d i s 4 x 4 d 4 0 s 1 0 for yuefen x a End 2 2连续性线性规划 2 2连续性线性规划 2 2连续性线性规划 建立模型如下 2 2连续性线性规划 model title生产计划程序3 sets yuefen 1 4 a d xx 定义上三角矩阵 link yuefen yuefen End 2 2连续性线性规划 ModelTitle 生产计划程序1VariableValueReducedCostA10000 000 000000C 1 70 000000 000000C 2 71 000000 000000C 3 80 000000 000000C 4 76 000000 000000X 1 10000 000 000000X 2 10000 000 000000X 3 5000 0000 000000X 4 6000 0000 000000E 1 2 0000000 000000E 2 2 0000000 000000E 3 2 0000000 000000E 4 2 0000000 000000D 1 6000 0000 000000D 2 7000 0000 000000D 3 12000 000 000000D 4 6000 0000 000000 2 2连续性线性规划 设有两个工厂A B 产量都是10万个 工厂有三个仓库x y z 产品都先送到仓库 现有四个顾客分别为甲 乙 丙 丁 需求量分别为3 5 4 5万个 工厂到仓库 仓库到顾客的运费单价 元 个 见下表所示 试求总运费最少的运输方案以及总运费 课后训练 model title转运问题 sets Plant A B produce Warhouse x y z Customer 1 4 require LinkI Plant Warhouse cI xI LinkII Warhouse Customer cII xII endsetsdata produce 10 10 require 3 5 4 5 cI 4 2 5 3 1 2 cII 5 7 10 20 9 6 7 15 20 6 7 4 enddata 课后练习 OBJ min sum LinkI cI xI sum LinkII cII xII Thesupplyconstraints for Plant i SUP sum Warhouse j xI i j produce i 运进仓库的量等于运出的量 for Warhouse j MID sum Plant i xI i j sum Customer k xII j k Thedemandconstraints for Customer k DEM sum Warhouse j xII j k require k 课后练习 连续投资10万元 A 从第1年到第4年每年初要投资 次年末回收本利1 15 B 第3年初投资 到第5年末回收1 25 最大投资4万元 C 第2年初投资 到第5年末回收1 40 最大投资3万元 D 每年初投资 每年末回收1 11 求 5年末总资本最大 练习2连续投资 课后练习 练习2解答 变量设置 课后练习 模型建立 课后练习 程序编写model title投资问题 max 1 15 x4a 1 40 x2c 1 25 x3b 1 06 x5d x1a x1d 100000 x2a x2c x2d 1 06 x1d x3a x3b x3d 1 15 x1a 1 06 x2d x4a x4d 1 15 x2a 1 06 x3d x5d 1 15 x3a 1 06 x4d x3b 40000 x2c 30000 课后练习 运行结果Globaloptimalsolutionfound Objectivevalue 143750 0Totalsolveriterations 2ModelTitle 投资问题VariableValueReducedCostX4A45000 000 000000X2C30000 000 000000X3B40000 000 000000X5D0 0000000 000000X1A71698 110 000000X1D28301 890 000000X2A0 0000000 000000X2D0 0000000 3036000E 01X3A0 0000000 000000X3D42452 830 000000X4D0 0000000 2640000E 01 课后练习 例3生产计划问题某工厂计划安排生产 两种产品 已知每种单位产品的利润 生产单位产品所需设备台时及A B两种原材料的消耗 现有原材料和设备台时的定额如表所示 问 怎么安排生产使得工厂获利最大 产品 的单位利润降低到1 8万元 要不要改变生产计划 如果降低到1万元呢 产品 的单位利润增大到5万元 要不要改变生产计划 如果产品 的单位利润同时降低了1万元 要不要改变生产计划 2 3敏感性分析 2 3敏感性分析 程序编写model title生产计划问题 maxf max 2 x1 3 x2 TIME x1 2 x2 8 A 4 x1 16 B 4 x2 12 END 2 3敏感性分析 运行结果ModelTitle 生产计划问题VariableValueReducedCostX14 0000000 000000X22 0000000 000000RowSlackorSurplusDualPriceMAXF14 000001 000000A0 0000001 500000B0 0000000 1250000TIME4 0000000 000000 对问题1 安排是生产产品 4单位 产品 2单位 最大盈利为14万元 2 3敏感性分析 目标函数的系数变化的敏感性分析 如果目标函数的系数发生变化 将会影响目标函数f斜率的变化 但是只要f的斜率小于等于 1 2 也就是直线l夹在l1与l2之间时 最优解都在 4 2 上取到 最优解不变 从而生产计划不会变 2 3敏感性分析 要使用敏感性分析必须要在这里选择Prices Ranges然后保存退出 路径 LINGO Options GeneralSolver 通用求解程序 选项卡 2 3敏感性分析 要调出敏感性分析的结果 必须先求解后再在程序窗口下点击LINGO Range 2 3敏感性分析 Rangesinwhichthebasisisunchanged ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX12 000000INFINITY0 5000000X23 0000001 0000003 000000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseA8 0000002 0000004 000000B16 0000016 000008 000000TIME12 00000INFINITY4 000000 当前变量系数 允许增加量 允许减少量 对问题2 产品 的单位利润降低到1 8万元 在 1 5 之间 所以不改变生产计划 如果降低到1万元 不在 1 5 内 要改变生产计划 在程序中将目标函数的系数 2 改为 1 可得新的计划为安排是生产产品 2单位 产品 3单位 最大盈利为11万元 对问题3 要改变生产计划 更改程序得新计划为生产产品 2单位 产品 3单位 最大盈利为19万元 对问题4 因为两个系数同时改变了 所以只有更改程序的数据 重新运行得 不改变生产计划 但是最大利润降低到8万元 2 3敏感性分析 2 3敏感性分析 把y1 y2 y3作为三种原料的定价 定价的目标是在比生产产品获得更多利润的前提下的最小利润 在最优情况下 y的值就是资源的影子价格 影子价格有意义是有范围的 影子价格经济含义是 在资源得到最优配置 使总效益最大时 该资源投入量每增加一个单位所带来总收益的增加量 2 3敏感性分析 Rangesinwhichthebasisisunchanged ObjectiveCoefficientRangesCurrentAllowableAllowableVariableCoefficientIncreaseDecreaseX12 000000INFINITY0 5000000X23 0000001 0000003 000000RighthandSideRangesRowCurrentAllowableAllowableRHSIncreaseDecreaseA8 0000002 0000004 000000B16 0000016 000008 000000TIME12 00000INFINITY4 000000 运行结果ModelTitle 生产计划问题VariableValueReducedCostX14 0000000 000000X22 0000000 000000RowSlackorSurplusDualPriceMAXF14 000001 000000A0 0000001 500000B0 0000000 1250000TIME4 0000000 000000 2 3敏感性分析 50桶牛奶 时间480小时 至多加工100公斤A1 制订生产计划 使每天获利最大 35元可买到1桶牛奶 买吗 若买 每天最多买多少 可聘用临时工人 付出的工资最多是每小时几元 A1的获利增加到30元 公斤 应否改变生产计划 每天 例4加工奶制品的生产计划 2 3敏感性分析 x1桶牛奶生产A1 x2桶牛奶生产A2 获利24 3x1 获利16 4x2 原料供应 劳动时间 加工能力 决策变量 目标函数 每天获利 约束条件 非负约束 线性规划模型 LP 2 3敏感性分析 Max 72 x1 64 x2 x1 x2 50 12 x1 8 x2 480 3 x1 100 OBJECTIVEFUNCTIONVALUE1 3360 000VARIABLEVALUEREDUCEDCOSTX120 0000000 000000X230 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 00000048 0000003 0 0000002 0000004 40 0000000 000000NO ITERATIONS 2 20桶牛奶生产A1 30桶生产A2 利润3360元 2 3敏感性分析 OBJECTIVEFUNCTIONVALUE1 3360 000VARIABLEVALUEREDUCEDCOSTX120 0000000 000000X230 0000000 000000ROWSLACKORSURPLUSDUALPRICES2 0 00000048 0000003 0 0000002 0000004 40 0000000 000000 35元可买到1桶牛奶 要买吗 35 48 应该买 聘用临时工人付出的工资最多每小时几元 2元 2 3敏感性分析 RANGESINWHICHTHEBASISISUNCHANGED OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172 00000024 0000008 000000X264 0000008 00000016 000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250 00000010 0000006 6666673480 00000053 33333280 0000004100 000000INFINITY40 000000 A1获利增加到30元 千克 应否改变生产计划 不变 35元可买到1桶牛奶 每天最多买多少 最多买10桶 2 3敏感性分析 问题 如何下料最节省 例5下料问题 2 4整数规划 按照客户需要在一根原料钢管上安排切割的一种组合 合理切割模式的余料应小于客户需要钢管的最小尺寸 2 4整数规划 为满足客户需要 按照哪些种合理模式 每种模式切割多少根原料钢管 最为节省 xi 按第i种模式切割的原料钢管根数 i 1 2 7 决策变量 2 4整数规划 2 所用原料钢管总根数最少 1 原料钢管剩余总余量最小 目标函数 两种标准 2 4整数规划 约束 整数约束 xi为整数 2 4整数规划 model Title钢管下料 Min 3 x1 x2 3 x3 3 x4 x5 x6 3 x7 4 x1 3 x2 2 x3 x4 x5 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 程序编写 2 4整数规划 按模式2切割12根 按模式5切割15根 余料27米 最优解 x2 12 x5 15 其余为0 最优值 27 最优解 x2 15 x5 5 x7 5 其余为0 最优值 25 按模式2切割15根 按模式5切割5根 按模式7切割5根 共25根 余料35米 当余料没有用处时 通常以总根数最少为目标 2 4整数规划 练习3某服务部门一周中每天需要不同数目的雇