1-1一般线性规划问题的数学模型概论.pptVIP

上页 下页 返回 问题的提出 线性规划问题的数学模型 线性规划问题的标准形式 线性规划问题的解 继续 继续 返回 返回 第一节 一般线性规划问 题的数学模型 问题的提出 例1:用一块边长为a的正方形铁皮做一个容器，应如何裁剪，使做成的容器的容积为最大? a x 容积为 决策变量（Decision variables） 目标函数（Objective function） 约束条件（Constraint conditions） 可行域（Feasible region) 最优解（Optimal solution) 基本概念 问题中要确定的未知量，表明规划中用数量表示的方案、措施，可由决策者决定和控制。 它是决策变量的函数 指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。 满足约束条件的决策变量的取值范围 可行域中使目标函数达到最优的决策变量的值 例2: 生产计划问题 问题的提出 产品 I 产品 II 如何安排生产 使利润最大 ？ 是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。 第1步 -确定决策变量 设 x1——I的产量 x2——II的产量 Z——利润 Max Z = x1 + x2 决策变量 第2步 –定义目标函数 Max Z = 2 x1 + 3 x2 系数 第2步 –定义目标函数 对我们有何限制? 2x1 + 2 x2 ≤12 4x1 ≤ 16 5 x2 ≤ 15 x1、 x2 ? 0 第3步 –表示约束条件 例2的数学模型 目标函数 Max Z = 2x1 + 3x2 约束条件 2x1 + 2x2≤12 4x1 ≤16 5x2≤15 x1、 x2 ? 0 x1 x2 线性规划问题的数学模型 线性规划问题的共同特征 决策变量：一组决策变量X是问题中要确定的未知量,一般X大于等于零 约束条件：含决策变量的约束条件是线性等式或不等式 目标函数：表示为决策变量的函数，是线性的。求目标函数最大值或最小值 线性规划模型的一般形式 标准形式为: 目标函数最大 约束条件等式 决策变量非负 线性规划问题的标准形式 简写为 用向量表示 用矩阵表示 C—价值向量 b—资源向量 X—决策变量向量 min Z=CX 等价于 max Z’ = -CX “?” 约束：加入非负松驰变量 一般线性规划问题的标准形化 例： 目标函数 Max Z = 2x1 + 3x2 约束条件 2x1 + 2x2 ≤12 4x1 ≤16 5x2≤15 x1、 x2 ≥ 0 min Z=CX 等价于 max Z’ = -CX “?” 约束：加入非负松驰变量 例： 一般线性规划问题的标准形化 “?” 约束： 减去非负剩余变量 Max 例 ： xk无约束（即可正可负） 解：标准形为 标准型 可行解:满足AX = b,X ≥ 0的解X称为线性规划问题的可行解。 最优解:使Z = CX达到最大值的可行解称为最优解。 线性规划问题的解 基：若B是矩阵A中m×m阶非奇异子矩阵（B≠0），则B是线性规划问题的一个基。不妨设： 线性规划问题解的概念 Pj, j = 1,2,...,m —— 基向量； Xj, j = 1,2,...,m —— 基变量； Xj, j = m+1,m+2,...,n —— 非基变量。 求解 线性规划问题解的概念 基解：称上面求出的X 解为基解。 基可行解：非负的基解X 称为基可行解 可行基：对应基可行解的基称为可行基 线性规划问题解的概念 上页 下页 返回