线性规划模型和数学建模竞赛PPT.pptVIP

每辆平板车有10.2米长的地方可用来装包装箱 为在第 节车上装载第 件包装箱的 解 令 建立整数规划模型。 1) 约束条件 两节车的装箱数不能超过需要装的件数 每节车可装的长度不能超过车皮的长度： 每节车可装的重量不超过车能够承受的重量： 对于C5, C6, C7类包装箱的总数的特别限制： 2) 目标函数 浪费空间最小，即包装箱的总厚度最大： 3) 整数线性规划模型 求解结果可以看出， 4) 模型求解 运用LINGO软件求解得到： 5) 最优解的分析说明 装箱总长度为1019.7cm， 两节车共装箱的总长度为2039.4cm. 为最优装车方案 上述求解结果只是一种最优的装车方案 此答案并不唯一. 0-1整数规划是整数规划的特殊情形 要求规划模型的决策变量xij只能取0或1. 0-1整数规划模型的求解没有非常好的算法 四、0-1整数规划模型 变量较少情形 - 简单隐枚举法 利用软件,求解0-1整数规划模型. 背包问题 有 n 个物品，编号为1, 2, …, n，第 i 件物品 重 ai 千克，价值为 ci 元，现有一个载重量不超过 大，应如何装载这些物品？ a 千克的背包，为了使装入背包的物品总价值最 变量 xi 表示物品 i 是否装包，i =1, 2, …, n 解 背包问题的规划模型： 下 回 停 一、规划引言 二、线性规划模型 三、整数线性规划模型 线性规划理论及模型 四、0-1整数规划模型 五、非线性规划模型 六、多目标规划模型 七、动态规划模型 一、引言 1, 如何分配有限资源 2, 达到期望目标的优化分配方案 3, 运筹学这类问题数学规划模型. 二、线性规划模型 设有 n 种食物，各含 m 种营养素， 第 j 种食物中第 i 中营养素的含量为 aij , n 种食物价格分别为c1, c2, …, cn， 确定食谱中n 种食物的数量x1, x2, …, xn， 线性规划模型的标准形式 - 食谱问题 要求 m 种营养的含量不低于b1, b2, …, bm ， 使得总的费用最低. 根据食物数量和价格 - 食谱费用为 食谱中第 i 种营养素的含量为 食谱问题问题 (蛋白质含量, 维生素) 食谱问题 - 典型规划问题 单目标, 多目标 线性规划,整数规划 (1) 决策变量，该问题要求解的那些未知量。 （2）目标函数，该问题要优化的目标函数。 （3）约束条件，该问题对决策变量的限制条件 糖尿病患者营养配餐的数学模型 线性规划问题有解：指能找出一组满足约束条件的向量-可行解。线性规划问题无解：指不存在可行解或最优趋向无限大。可行域：指全部可行解组成的集合。最优解：指可行域中使目标函数值达到最优的可行解。 线性规划基本概念 线性规划模型的三种形式 ⑴ 一般形式 非负约束 自由变量 ⑵ 规范形式 ⑶ 标准形式 三种形式的LP问题全都是等价的 一般形式化成规范形式和标准形式. 目标函数的转化 x o z -z 约束条件和变量的转化 ①．一般形式的LP问题变换为规范形式 可用下述两个不等式约束去替代 一般形式的LP变换为规范形式. 对于一个无符号限制变量 ，引进两个非负变量 和 ，并设 ②．一般形式的LP问题变换为标准形式， 消除不等式约束和符号无限制变量. 对于一个不等式约束 代替上述的不等式约束. 可引入一个剩余变量 ， 用 对于不等式约束 一般形式的LP变换为标准形式 . 引入一个松弛变量 ，用 标准形式的线性规划问题 单纯形方法是线性规划问题的基础 算法——图形方法 算法——单纯形方法 算法——软件计算, LINGO和LINDO 2.2 线性规划模型的求解 图形是凸型 算法步骤 ♂返回 单纯形算法 运输问题 甲调出2000吨物资 ，乙调出1100吨物资 供给 A-1700K、B-1100K、C-200K、D-100K 假定运费与货运数量成正比. 已知每吨运费如下表所示. 现在问：找出一个运费最省的调拨计划？ 15 7 25 21 甲 15 37 51 51 乙 D C B A 表 1.1 销 地 运 费 产 地 乙 甲 D C B A 运输问题的一般表述 数学模型： 若各产地的总产量等于各销地的总销量 将线性规划问题转化为其标准 否则，称为不平衡的运输问题 平衡的运输问题. 总产量总销量和总产量总销量. 决策变量取整数值-整数