线性规划典型习题.ppt

第二章线性规划 本章学习要求 1 线性规划问题及其数学模型 线性规划问题建模方法 线性规划问题标准形式 非标准线性规划问题向标准线性规划问题的转化 2 线性规划问题的图解法及其几何意义 图解法的适用条件与计算过程 通过图解法了解线性规划问题解的几何意义 3 线性规划问题基本性质 掌握描述线性规划问题基本性质的4个定理 4 单纯形法 掌握单纯形法的计算方法 包括寻找初始基本可行解 最优解的判别 基变换 熟练掌握单纯形表的计算过程 5 特殊的线性规划问题 掌握不能直接获得符合要去的初始基本可行解情况下的单纯形法 掌握大M法的计算过程 6 线性规划在道路交通工程的应用 了解线性规划问题在道路交通工程中的主要应用 线性规划典型习题 线性规划建模单纯性表求解大M法 习题一 桥梁工地要制作100套钢筋架子 每套需要长2 9米 2 1米和1 5米的钢筋各1根 现有原材料 钢筋 长7 4米 问如何下料最省 废料最少 在每根7 4米长的原料钢筋上截取2 9米 2 1米和1 5米的料各1根 这样每根原料就都剩下了0 9米长的废料无法利用 所谓合理利用原材料 就是要使废料最少 因此考虑如何在原材料上合理套裁 以下几种方法都是能节省材料的较好方案 为得到100套钢筋架子 需要混合使用各种下料方案 设按第j种方案下料的原材料根数为xj j 1 2 3 4 5 根据表中的数据可以列出约束条件为 X1 2X2 X4 1002X3 2X4 X5 1003X1 X2 2X3 3X5 100Xj 0 j 1 2 3 4 5 目标函数为 MINZ 0 1X2 0 2X3 0 3x4 0 8x5 化标准型 采用大M法 列单纯形表可解 习题二 在下面的线性规划问题中找出满足约束条件的所有基解 指出哪些是基可行解 并确定哪一个是最优解 MAXZ 2X1 3X2 4X3 7X4S T 2X1 3X2 X3 4X4 8 X1 2X2 6X3 7X4 3X1 X2 X3 X4 0 MAXZ 2X1 3X2 4X3 7X4S T 2X1 3X2 X3 4X4 8 X1 2X2 6X3 7X4 3X1 X2 X3 X4 0 基解 基 系数矩阵 基本可行解 取子矩阵D1 D1为一个基 对于D1 基变量为X1 X2 X3 X4为非基变量 令X3 X4 0X1 1 X2 2 P1 P2 可行解 取子矩阵D2 D2为一个基 对于D2 基变量为X1 X3 X2 X4为非基变量 令X2 X4 0X1 45 13 X3 14 13 P1 P3 非可行解 取子矩阵D3 D3为一个基 对于D3 基变量为X1 X4 X2 X3为非基变量 令X2 X3 0X1 34 5 X4 7 5 P1 P4 可行解 取子矩阵D4 D4为一个基 对于D4 基变量为X2 X3 X1 X4为非基变量 令X1 X4 0X2 45 16 X3 7 16 P2 P3 可行解 取子矩阵D5 D5为一个基 对于D5 基变量为X2 X4 X1 X3为非基变量 令X3 X1 0X2 68 29 X4 7 29 P2 P4 非可行解 取子矩阵D6 D6为一个基 对于D6 基变量为X3 X4 X1 X2为非基变量 令X1 X2 0X3 68 31 X4 45