数学模型1-1线性规划模型.pdf

第一章线性规划模型 应用最广泛的方法之一 最基本的方法之一 网络规划 整数规 划 目标规划和多目标规划都是以线性 规划为基础的 解决稀缺资源最优分配的有效方法 使 付出的费用最小或获得的收益最大 历史背景 1939 康托洛维奇 KOHTOPOBUZ 生产 组织与计划中的 数学方法 解乘数 法 1947 G DANTZIG 单纯形法 1960 康托洛维奇和库伯曼斯 Koopmans 最佳资源利用的经济计算 两人因对资 源最优分配理论的贡献而获1975年诺贝尔 经济学奖 历史背景 Cont 冯 诺伊曼 Von Neuman 和摩根斯坦 Morgenstern 1944年发表的 对策论与 经济行为 涉及与线性规划等价的对策问 题及线性规划对偶理论 从1964年诺贝尔奖设经济学奖后 到1992 年28年间的32名获奖者中有13人 40 从事 过与线性规划有关的研究工作 其中比较 著名的有Simon Samullson Leontief Arrow Miller等 线性规划的数学模型 A B 备用资源 煤1 2 30 劳动日3 2 60 仓库0 2 24 利润40 50 例1 生产计划问题 A B各生产多少 可获最大利润 x1 2x2 30 3x1 2x2 60 2x2 24 x1 x2 0 max Z 40 x1 50 x2 设产品A B产量分别为变量x1 x2 例2 求 最低成本的原料混合方案 原料原料A B 每单位成本 每单位成本 1 4 1 0 2 2 6 1 2 5 3 1 7 1 6 4 2 5 3 8 每单位添 加剂中维生 每单位添 加剂中维生12 14 8 素最低含量素最低含量 设每单位添加剂中原料i的用量为xi i 1 2 3 4 minZ 2x1 5x2 6x3 8x4 4x1 6x2 x3 2x4 12 x1 x2 7x3 5x4 14 2x2 x3 3x4 8 xi 0 i 1 4 线性规划模型特点 决策变量 向量 x1 xn T 决策人要考虑 和控制的因素非负 约束条件 线性等式或不等式 目标函数 Z x1 xn 线性式 求Z极大 或极小 9 一般式 Max min Z C1X1 C2X2 CnXn a11X1 a12X2 a1nXn b1 a21X1 a22X2 a2nXn b2 am1X1 am2X2 amnXn bm Xj 0 j 1 n 隐含的假设 比例性 决策变量变化引起目标的改变量 与决策变量改变量成正比 可加性 每个决策变量对目标和约束的影 响独立于其它变量 连续性 每个决策变量取连续值 确定性 线性规划中的参数aij bi ci为确 定值 线性规划的标准型 a11X1 a12X2 a1nXn b1 a21X1 a22X2 a2nXn b2 am1X1 am2X2 amnXn bm Xj 0 j 1 2 n MaxZ C1X1 C2X2 CnXn 如何划为标准型 约束条件 变量 目标函数 约束条件 引入松弛变量 把不等式条件化为等式条件 例1 maxZ 40 X1 50 X2 0 X3 0 X4 0 X5 X1 2X2 X3 30 3X1 2X2 X4 60 2X2 X5 24 X1 X5 0 无约束变量的处理 3X1 2X2 8 X1 4X2 14 X2 0 令X1 X1 X1 3 X1 3 X1 2X2 8 X1 X1 4X2 14 X1 X1 X2 0 极小化为极大 例 将 min Z X1 2X2 3X3 X1 X2 X3 7 X1 X2 X3 2 X1 X2 0 X3无限制 化为标准型 令X3 X4 X5 加松弛变