数学建模与：线性规划问题(超全) .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时， 。 那末这一问题的数学模型为： ij x 1 = ij x ( ) n j i x ij , , 2 , 1 , 0 L = = 求一组变量 的值， 使目标函数 的值最小。 ? ? = = = n i m j ij ij x c s 1 1 ( ) n j i x ij , , 2 , 1 , L = 分派问题的模型 约束条件 目标函数 ? ? = = = n i m j ij ij x c s 1 1 min ( ) ( ) ( ) n j i x n i x n j x ij ij ij n j n i , , 2 , 1 , 1 0 , , 2 , 1 1 , , 2 , 1 1 1 1 L L L = = = = = = ? ? = = 或 每件工作只分派一人去做 每人只做一件工作 每人对每件工作只有 做与不做两种情况 (四）生产组织与计划问题 (Ⅰ) 总的加工成本最低 (Ⅱ) 生产存储问题 某工厂用机床 加工 种零件。在一个生产周期， 各机床只能工作的机时、工厂必须完成各零件加工数、各机床加工每个零件的时间