建模-线性规划课件.ppt

1 第一讲 线性规划方法 数学建模方法及其应用 线性规划方法 2 线性规划的一般模型 线性规划解的概念与理论 线性规划的求解方法 线性规划的软件求解方法 线性规划的应用案例分析 3 线性规划研究的是线性目标函数在线性约束条件下的最值问题 在管理科学中有着广泛的应用 第十章线性规划方法 线性规划的两类重要的实际问题 1 给定一定数量的人力 物力资源 问怎样安排运用这些资源 能使完成的任务量最大 或收到的效益最大 2 给定一项任务 问怎样统筹安排 能使完成这项任务所耗费的人力 物力资源最少 一 线性规划的一般模型 4 每种资源的拥有量和每种产品所消耗的资源量 以及单位产品的利润如下表 试问如何安排生产计划使得该企业获利最大 1 问题的提出 5 一 线性规划的一般模型 1 问题的提出 6 一 线性规划的一般模型 1 问题的提出 该模型的特点 1 用一组决策变量表示某一方案 这组决策变量的值就代表一个具体方案 一般这些变量取值是非负的 2 存在一定的约束条件 这些约束条件可以用一组线性等式或线性不等式来表示 3 有一个要求达到的目标 它可用决策变量的线性函数 即目标函数 来表示 按问题的不同 要求目标函数实现最大化或最小化 7 2 线性规划模型的一般形式 一 线性规划的一般模型 8 3 线性规划模型的标准型 一 线性规划的一般模型 标准化方法 9 二 线性规划解的概念与理论 1 解 1 线性规划解的概念 10 1 线性规划解的概念 2 基 11 1 线性规划解的概念 4 基可行解 满足非负约束条件的基解称为基可行解 5 可行基 对应于基可行解的基称为可行基 基解和基可行解实例 12 1 线性规划解的概念 几种解的关系 可行解 基可行解 基解 13 2 线性规划解的基本理论 定理3 1 如果线性规划问题的可行域有界 则问题的最优解一定在可行域的顶点上达到 2 如果线性规划问题的可行域有无界 则问题可能无最优解 若有最优解也一定在可行域的某个顶点上达到 二 线性规划解的概念与理论 图解法 ppt图解法 14 1 单纯形法的基本思想 三 线性规划的求解方法 寻求问题的一个基可行解 即可行域的顶点 检查该基可行解是否为最优解 如果不是 则设法再求另一个没有检查过的基可行解 如此进行下去 直到得到某一个基可行解为最优解为止 单纯形法实例 现在要解决的问题 1 如何求出第一个基可行解 2 如何判断基可行解是否为最优解 3 如何由一个基可行解过渡到另一个基可行解 2 线性规划的MATLAB求解 三 线性规划的求解方法 用MATLAB求解线性规划模型 15 MATLAB MatrixLaboratory 的基本含义是矩阵实验室 它是由美国MathWorks公司研制开发的一套高性能的基数值计算 信息处理 图形显示等于一体的可视化数学工具软件 用MATLAB求解线性规划模型 16 MATLAB的优化工具箱 Optimizationtoolbox 它的基本功能 1 求解线性规划和二次规划问题 2 求解无约束条件非线性规划的极小值问题 3 求解带约束条件非线性规划极小值问题 4 求解非线性方程组 5 求解带约束约束的线性最小二乘问题 6 求解非线性最小二乘逼近和曲线拟合问题 用MATLAB求解线性规划模型 17 LINGO LinearInteractiveandGeneralOptimizer 的基本含义是交互式的线性和通用优化求解器 它是美国芝加哥大学的LinusSchrage教授于1980年开发了一套用于求解最优化问题的工具包 后来经过完善成何扩充 并成立了LINGOSYSTEMINC 3 线性规划的LINGO解法 三 线性规划的求解方法 18 LINGO功能 求解线性规划 二次规划 非线性规划 目标规划 图论与网络优化 整数规划的求解 以及一些线性和非线性方程 组 最大最小和排队论中的最优化问题求解等 用LINGO求解线性规划模型 19 LINGO的特色 它允许优化模型中的决策变量为整数 即可以求解整数规划 而且执行速度快 求解线性和非线性优化问题的简易工具 LINGO内置了一种建立最优化模型的语言 可以简便地表达大规模问题 用LINGO求解线性规划模型 20 用LINGO求解线性规划模型 21 数据段 集合段 目标约束 用LINGO求解线性规划模型 22 23 四 线性规划的应用案例分析 一般讲 一个应用问题凡满足一下条件时 才能建立线性规划模型 1 要求解问题的目标函数能用数值指标来反映且为线性函数 2 存在多种方案 3 要求达到的目标是在一定约束条件下实现的 这些约束条件可以用线性等式或不等式来描述 24 1 合理下料问题 四 线性规划的应用案例分析 1 问题的提出 某单位需要加工制作100套工架 每套工架需用长为2 9米 2 1米和1 5米的圆钢各一根 已知原材料长7 4米 现在的问题是如何下料使得所用的原材料最省 25 模型分析 在每一根原材料上各一根截取2 9米 2 1米和1 5米的圆钢做成一套工架 每根原材料剩下料头0 9米 要完成100套工架 就需要用100根原材料 共剩余90米料头 案例1 合理下料问题 26 案例1 合理下料问题 ABCDEF x1x2x3x4x5x6 决策变量 按第i种模式切割的原料钢管根数 i 1 2 6 28 决策目标 所用的原材料最省 而最省可以有两种标准 一是切割后总余料量最小 二是切割原材料的总根数最少 按照这两种标准建立数学模型如下 案例1 合理下料问题 29 案例1 合理下料问题 30 案例1 合理下料问题 用MATLAB求解模型 问题的MATLAB程序 C 0 0 1 0 2 0 3 0 8 b1 0 0 0 0 0 b2 100 100 100 A1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 A2 1 2 0 1 0 0 0 2 2 1 3 1 2 0 3 x fv linprog C A1 b1 A2 b2 31 案例1 合理下料问题 用LINGO求解模型 以余料最小为目标 MODEL SETS ROW 1 2 3 B ARRANGE 1 5 X C LINKS ROW ARRANGE A ENDSETSDATA B 100 100 100 C 0 0 1 0 2 0 3 0 8 A 1 2 0 1 0 0 0 2 2 1 3 1 2 0 3 ENDDATA OBJ MIN SUM ARRANGE J C J X J FOR ROW I SUM ARRANGE J A I J X J B I FOR ARRANGE J X J 0 END 32 案例1 合理下料问题 用LINGO求解模型 某投资公司拟制定今后五年的投资计划 初步考虑下面的四个投资项目 2 连续投资问题 四 线性规划的应用案例分析 33 问题 现有投资金额100万元 如何使得第五年年末能够获得最大的利润 2 连续投资问题 四 线性规划的应用案例分析 34 案例2 连续投资问题 35 第1年 将100万元资金全部用于项目A和项目D的投资 即 案例2 连续投资问题 36 案例2 连续投资问题 37 案例2 连续投资问题 38 案例2 连续投资问题 连续投资问题的数学模型 39 MODEL sets row 1 5 arrange 1 4 link row arrange c x endsetsdata c 0 0 0 0 0 0 1 40 0 0 1 25 0 0 1 15 0 0 0 0 0 0 1 06 enddata OBJ max sum link i j c i j x i j x 1 1 x 1 4 1000000 1 06 x 1 4 x 2 1 x 2 3 x 2 4 0 1 15 x 1 1 1 06 x 2 4 x 3 1 x 3 2 x 3 4 0 1 15 x 2 1 1 06 x 3 4 x 4 1 x 4 4 0 1 15 x 3 1 1 06 x 4 4 x 5 4 0 x 3 2 0 END 案例2 连续投资问题 用LINGO求解模型 40 问题的连续投资方案 第1年 项目A为716981 1元和项目D为283018 9元第2年 项目C的投资金额为300000元 第3年 项目B的投资为400000元和项目D为424528 3元 第4年 投资项目A的金额为450000元 第5年年末该公司拥有总资金为1437500元 即收益率为43 75 案例2 连续投资问题 41 42 3 南水北调水指标分配问题 四 线性规划的应用案例分析 南水北调中线工程建成后 预计2010年年调水量为110亿立方米 主要用来解决京 津 冀 豫四省 市 的沿线20个大中城市的生活用水 工业用水和综合服务业的用水 分配比例分别为40 38 和22 这样可以改善我国中部地区的生态环境和投资环境 推动经济发展 用水指标的分配总原则是 改善区域的缺水状况 提高城市的生活水平 促进经济发展 提高用水效益 改善城市环境 43 要研究的问题是 1 请你综合考虑各种情况 给出2010年每个城市的调水分配指标 使得各城市的总用水情况尽量均衡 2 由于各城市的基本状况和自然条件不同 对相同的供水量所产生的经济效益不同 请从经济效益的角度 给出调水