1-1线规划问题及其数学模型.ppt

第一节 线性规划问题 及其数学模型 问题的提出 例: 生产计划问题 决策变量（Decision variables） 目标函数（Objective function） 约束条件（Constraint conditions） 可行域（Feasible region) 最优解（Optimal solution) 该计划的数学模型 目标函数 Max Z = 2x1 + 3x2 约束条件 x1 + 2x2 ? 8 4x1 ? 16 4x2 ? 12 x1、 x2 ? 0 线性规划问题的共同特征 一组决策变量X表示一个方案,一般X大于等于零。 约束条件是线性等式或不等式。 目标函数是线性的。 求目标函数最大化或最小化 线性规划模型的一般形式 线性规划问题的标准形式 标准形式为: 简写为 用向量表示 用矩阵表示 min Z=CX 等价于 max Z’ = -CX “?” 约束：加入非负松驰变量 min Z=CX 等价于 max Z’ = -CX “?” 约束：加入非负松驰变量 “?” 约束： 减去非负剩余变量； 解 ：标准形为 线性规划模型举例 (一) 运输问题 (二) 布局问题 (三) 分派问题 (四) 生产计划问题 (五) 合理下料问题 线性规划模型的条件 （1）要求解问题的目标函数能用数值指标来反映，且为线性函数； （2）存在着多种方案； （3）要求达到的目标是在一定约束条件下实现的，这些约束条件可用线性等式或不等式来描述。 （二）布局问题 作物布局 在n块地上种植m种作物，已知各块土地 亩数、各种作物计划播种面积及各种作 物在各块的单产（每亩的产量）如表— （与运输问题相似）， 问：如何合理安排种植计划，才使总产量最多。 线性规划模型 单价（元／吨） 销 地 产 地 产量（吨） B1 B2 … Bn A1 A2 ┇ Am 销量（吨） C11 C12 … C1n C21 C22 … C2n ┇ ┇ … ┇ Cm1 Cm2 … Cmn b1 b2 … bn a1 a2 ┇ am （二）布局问题 n块土地 每亩的产量 m种农作物 总产量最多 方法与运输问题类似 (三）分派问题 设有n件工作 分派给n人 去做， 每人只做一件工作且每件工作只分 派一人去做。设Ai完成Bj的工时为 。 问：应如何分派才使完成全部工作的总工时最少。 解：设 为Bj分派给人Ai情况： Bj分派给Ai时， ； 不分派给Ai时， 。 那末这一问题的数学模型为： 求一组变量 的值， 使目标函数 的值最小。 (完成全部工作的总工时最少） (三）分派问题 约束条件 每件工作只分派一人去做 每人只做一件工作 每人对每件工作只有 做与不做两种情况 分派问题的模型 目标函数 (四）生产组织与计划问题 (Ⅰ) 生产的机器最多 (Ⅱ) 总的加工成本最低 （Ⅲ）生产存储问题 (四）生产组织与计划问题 设某车间用机床 生产由 这n个不同零件 构成的机器。如果每架机器需要各 种零件的数目成比例 ; 机床 生产零件 的效率(每日 生产零件数)为 。 (Ⅰ) 生产的机器最多 应如何分配机床负荷，才使生产的机器最多? 求一组变 的值, 解：设 为一天机床 生产零件 的时 间（单位：日） 这一问题的数学模型为： 生产的机器台数 (四）生产组织与计划问题 (Ⅰ) 生产的机器最多 约束条件 各机床一天生产 各种零件总数， 应成已定比例 生产零件时间不能为负数 (