数学建模算法与应用-线性规划

第2章线性规划 数学建模算法与应用 应用场景 成功的优化例子 最优人员安排 为美国航空每年节约两千万美元 改进的出货流程 每年为YellowFreight公司节约一千七百多万美元 应用场景 成功的优化例子 改进的卡车分派 为Reynolds公司每年节约七百万美元 应用场景 成功的优化例子 最优全局供应链 为数字设备行业节约超过三亿美元 应用场景 成功的优化例子 大阪Hanshin高速的 最优交通控制 每年节约一千七百万小时 为他们带来三亿二千万美圆的收益 应用场景 成功的优化例子 数学规划 线性规划 LP 二次规划 QP 非线性规划 NLP 纯整数规划 PIP 混合整数规划 MIP 整数规划 IP 0 1整数规划一般整数规划 连续规划 如何利用现有资源安排生产 以取得最大经济效益的问题 数学规划 实际问题中的优化模型 x是决策变量 f x 是目标函数 gi x 0是约束条件 优化模型的分类 其中 1 1 1线性规划的实例与定义 1 1线性规划问题 目标函数及约束条件均为线性函数 故被称为线性规划问题 LinearProgramming LP 线性规划问题是在一组线性约束条件的限制下 求一线性目标函数最大或最小的问题 一般研究的问题 1 给定了一定的人力 物力 财力 如何应用这些资源获得最大的经济效益 2 给定了一项任务 如果统筹安排才能以最小的资源去完成它 方法 图解法或单纯形法 线性规划的组成要素 目标函数MaxF或MinF约束条件s t subjectto 满足于决策变量用符号来表示可控制的因素建模步骤1 理解要解决的问题 了解解题的目标和条件 2 定义决策变量 x1 x2 xn 每一组值表示一个方案 3 用决策变量的线性函数形式写出目标函数 确定最大化或最小化目标 4 用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件 1 1 2线性规划问题的标准型 模型转换 目标转换 变量转换 1 等式变不等式 约束转换 2 不等式变等式 松弛变量 剩余变量 3 不等式变不等式 把问题转化为标准形式 1 1 3线性规划的Matlab标准形式及软件求解 1 1 4可以转化为线性规划问题的模型 例1 4数学规划问题 式中 A和b为相应维数的矩阵和向量 例1 5求解下列数学规划问题 计算的MATLAB程序如下 clc clearc 1 4 c c c 构造价值列向量a 1 1 11 1 11 3 1 1 23 a a a 构造变换后新的系数矩阵b 2 1 1 2 y z linprog c a b zeros 8 1 这里没有等式约束 对应的矩阵为空矩阵x y 1 4 y 5 end 变换到原问题的解 x u v 运价表 元 T 表1 例1 6现有A1 A2 A3三个产粮区 可供应粮食分别为10 8 5 万吨 现将粮食运往B1 B2 B3 B4四个地区 其需要量分别为5 7 8 3 万吨 产粮地到需求地的运价 元 吨 如表1所示 问如何安排一个运输计划 使总的运输费用最少 解 设xij i 1 2 3 j 1 2 3 4 为i个产粮地运往第j个需求地的运量 则运输费用为 从产粮区运出去的量 运给需求地的量 这样得到下列运输问题的数学模型 运输问题的一般数学模型 设有m个产地 记作A1 A2 A3 Am 生产某种物资 其产量分别为a1 a2 am 有n个销地 记作B1 B2 Bn 其需要量分别为b1 b2 bn 且产销平衡 即 从第i个产地到j个销地的单位运价为cij 在满足各地需要的前提下 求总运输费用最小的调运方案 设xij i 1 2 m j 1 2 n 为第i个产地到第j个销地的运量 则数学模型为 1 产销平衡 2 当产大于销时 数学模型为 即 2 当销大于产时 即 数学模型为 1 2投资的收益和风险 1 2 1问题提出 1 2 2符号规定和基本假设 1 2 3模型的分析与建立 1 2 4模型一的求解 1 2 5结果分析 第3章整数规划 数学建模算法与应用 2 1概论 1 整数规划的定义数学规划中的变量 部分或全部 限制为整数时 称为整数规划 若在线性规划模型中 变量限制为整数 则称为整数线性规划 2 整数规划的分类 如不加特殊说明 一般指整数线性规划 对于整数线性规划模型大致可分为两类 1 变量全限制为整数时 称纯 完全 整数规划 2 变量部分限制为整数的 称混合整数规划 5 用MATLAB求整数线性规划 MATLAB求解混合整数线性规划的命令为 x fval intlinprog f intcon A b Aeq beq lb ub 对应数学模型 其中 f x intcon b beq lb ub为列向量 A Aeq为矩阵 例2 3 套裁下料问题 某工厂要做100套钢架 每套要用长为2 9m 2 1m和1 5m的圆钢各一根 已知原料每根长7 4m 问如何下料可使所用原料的根数最少 解 问题分析 模型建立 模型求解 MATLAB程序 clc clearf 11111 intcon 1 5 整数变量的地址 x1 x5A 12010 00321 31203 b 100100100 lb zeros 5 x intlinprog f intcon A b lb 例2 4 背包问题 有n个物品 编号为1 2 n 第i件物品重ai 千克 价值为ci元 现有一个载重量不超过a千 应如何装载这些物品 克的背包 为了使装入背包的物品总价值最大 用变量xi表示物品i是否装包 i 1 2 n 并令 解 可得到背包问题的规划模型为 例2 5 指派问题 有n项任务 由n个人来完成 每个人只能做一 件 第i个人完成第j项任务要cij小时 如何合 理安排