【运筹学】线性规划数学模型 ( 线性规划三要素 | 您所在的位置:网站首页 › 线性规划模型不包括下列哪些要素 › 【运筹学】线性规划数学模型 ( 线性规划三要素 |
文章目录一、线性规划模型三要素二、线性规划一般形式和标准形式三、线性规划普通形式转为标准形式1、目标函数2、决策变量约束3、等式约束方程4、总体顺序说明5、线性规划标准形式转化案例四、线性规划解、可行解、最优解五、线性规划 基、基向量、基变量、非基变量一、线性规划模型三要素 线性规划数学模型三要素 : ( 1 ) 决策变量 : 上述 产品甲乙 的个数 x_1 , x_2就是决策变量 , 直接关系到利润的多少 ; ( 示例参考 【运筹学】线性规划数学模型 ( 三要素 | 一般形式 | 向量形式 | 矩阵形式 ) II . 线性规划示例 ) ( 2 ) 目标条件 : 多个决策变量的线性函数 , 通常是求 最大值 或 最小值 问题 ; 上述示例中的 max Z = 2x_1 + 3x_2就是目标条件 ; ( 3 ) 约束条件 : 一组多个 决策变量 的线性等式 或 不等式 组成 , 如上述 3 ~ 7 的四种设备的使用时间限制 和 决策变量的取值范围 ;参考博客 : 【运筹学】线性规划数学模型 ( 三要素 | 一般形式 | 向量形式 | 矩阵形式 ) 二、线性规划一般形式和标准形式线性规划一般形式 : \begin{array}{lcl}max (min) z = \sum_{j=1}^{n}c_j x_j\\ \\ \begin{cases} \sum_{j=1}^{n} a_{ij}x_j = b_i & (i = 1 , 2 \cdots m) \\ \\x_j \geq 0 & (i = 1 , 2 \cdots n) \end{cases}\end{array}线性规划标准形式 : max Z = \sum_{j = 1}^{n} c_j x_js.t \begin{cases} \sum_{j = 1}^{n} a_{ij} x_j = b_i & i = 1,2,\cdots,m \\ \\ x_j \geq 0 & j= 1, 2,\cdots,n \end{cases}线性规划标准形式特点 : 1. 目标函数 : 目标函数都是求最大值 , 如果出现最小值 , 那么将其转为求最大值的形式 ;2. 约束条件 : 约束条件都是等式方程 , 等式右侧的常数项 b_i大于等于 0; 3. 决策变量 : 决策变量 x_j大于等于 0 ; 约定 : 决策变量个数为 n个 , 约束条件不等式个数为 m个 , 约束条件不等式的系数为一个 m \times n矩阵 , m行 n列的矩阵 ; 三、线性规划普通形式转为标准形式参考博客 : 【运筹学】线性规划数学模型标准形式 ( 标准形式 | 目标函数转化 | 决策变量转化 | 约束方程转化 | 固定转化顺序 | 标准形式转化实例 ) ★★ 1、目标函数目标函数 转换 : 求 极小值 转为 求 极大值 ; 如果目标函数是 \rm min W = \sum c_j x_j可以将目标函数乘以 -1, \rm - min W = -\sum c_j x_jW是大于 0的数 , W的最小值时 , -W是最大值 , W是最大值时 , -W是最小值 , 这里令 Z = -W, 可以得到 \rm max Z = -minW = -\sum c_j x_j2、决策变量约束1 . 针对没有约束的变量 无约束变量 转换 : 所有的决策变量必须 \geq 0如果某个决策变量 x_j没有任何约束 , 在标准形式中 , 所有的决策变量必须都大于等于 0 ; 这里令 x_j = x_j' - x_j'', 其中 x_j' \geq 0, x_j'' \geq 02 . 针对小于等于 0的变量 如果出现 变量约束 x_j \leq 0, 需要将该变量约束转为大于等于 0 ( \geq 0) 的情况 ; 当前 x_j \leq 0, 令 x_j' = -x_j, 此时 x_j' \geq 0; 3、等式约束方程约束方程 转换 : 在线性规划中 , 约束方程都是等式 , 需要将不等式 ( \leq, \geq) 转为 等式 ( =) ; 1. 针对小于等于的不等式 : \sum a_{ij} x_j \leq b_i等式左边比右边小 , 左侧加上一个 变量 x_{n+i}与右侧相等 ; \sum a_{ij} x_j + x_{ni} = b_i这个 x_{n+i}称为松弛变量 ; 2. 针对大于等于的不等式 : \sum a_{ij} x_j \geq b_i等式左边比右边小 , 左侧加上一个 变量 x_{n+i}与右侧相等 ; \sum a_{ij} x_j - x_{ni} = b_i这个 x_{n+i}称为剩余变量 ; 4、总体顺序说明① 先处理变量没有约束的问题 , 需要用两个 \geq 0的变量替换原来的变量 ; 这里特别注意 , 之后处理 约束方程 , 每个步骤都要讲该变量替换掉 ; 该步骤优先级最高 ; ② 在处理约束方程 , 如果是 \leq不等式 , 需要在不等式左侧加入松弛变量 , 将不等式转为等式 ; 如果是 \geq不等式 , 不等式左侧需要减去一个 剩余变量 , 将不等式转为等式 ; 该处理过程会增加新的变量 , 如松弛变量或剩余变量 , 优先级 低于 处理没有变量约束 的问题 ; ③ 约束方程等式右侧常数必须大于 0, 如果右侧的常数小于 0, 在等式左右两侧都乘以 -1; ④ 先将之前 替换 或 新增的变量加入到目标函数中 , 在处理最大值最小值的问题 , 如果目标函数求最大值 , 什么都不用做 , 如果目标函数求最小值 , 需要将 求最小值的目标函数转为求最大值的目标函数 , 两边乘以 -1; 目标函数需要将之前所有的变量都总结到一起 , 上述两个步骤都会增加新的变量 , 因此转换目标函数的工作放在最后 ; 自下而上 : 变量约束都大于等于 0, 约束不等式转等式 , 约束方程右侧大于 0, 目标函数必须求最大值 ; 5、线性规划标准形式转化案例下面是线性规划问题模型 , 将其转化为标准形式 : \begin{array}{lcl}min W = -2x_1 + x_2 + 3x_3 \\ \\ \\ \begin{cases} 5x_1 + x_2 + x_3 \leq 7 \\ \\ x_1 - x_2 - 4x_3 \geq 2 \\ \\ -3x_1 + x_2 + 2x_3 = -5 \\ \\ x_1 \geq 0 , x_2 \geq 0 , x_3 无约束 \end{cases} \end{array}1. 处理变量无约束的问题 ( 变量必须大于 0 ) 处理决策变量 x_3无约束的问题 , 在标准形式中 , 所有的变量必须都 \geq 0; 这里使用 x_3' - x_3''代替 x_3, 新增加的两个变量 x_3' , x_3'' \geq 0注意之后的每个步骤都要考虑 将 x_3转为 ( x_3' - x_3'' ); 2. 约束方程 5x_1 + x_2 + x_3 \leq 7转化 ( 松弛变量 ) 该约束条件是 \leq不等式 , 需要在左侧加上 松弛变量 x_4, 将 小于等于不等式 转为等式 ; 5x_1 + x_2 + ( x_3' - x_3'' ) + x_4 = 73. 约束方程 x_1 - x_2 - 4x_3 \geq 2转化 ( 剩余变量 ) 该约束条件是 \geq不等式 , 需要在左侧减去 剩余变量 x_5, 将 大于等于不等式 转为等式 ; x_1 - x_2 - 4( x_3' - x_3'' ) - x_5 = 24. 约束方程 -3x_1 + x_2 + 2x_3 = -5转化 ( 右侧常数转正数 ) 该式子是等式 , 但是右侧常数小于 0, 这里需要将右侧的常数转化为正数 , 在方程两边乘以 -1; \begin{array}{lcl}\\ 原式 : & -3x_1 + x_2 + 2x_3 = -5 \\ \\ 两边乘以 -1 : & (-1) \times ( -3x_1 + x_2 + 2x_3 ) = (-1) \times ( -5 ) \\ \\ 最终结果 : & 3x_1 - x_2 - 2( x_3' - x_3'' ) = 5 \end{array}5. 目标函数转化 转化顺序说明 : 在处理上述转化时 , 需要加入新的变量 , 如 无约束的变量需要增加两个变量 , 约束方程的 松弛变量 和 剩余变量 , 因此目标函数最后转化 ; ( 1 ) 将新增的变量加入 原目标函数为 : min W = -2x_1 + x_2 + 3( x_3' - x_3'' )新增的变量 : ① 之前 x_3没有约束变量 , 使用 x_3' , x_3''代替 ; ② 处理 \leq不等式时 , 加入了 x_4松弛变量 ; ③ 处理 \geq不等式时 , 加入了 x_5剩余变量 ; 此时加入 新增变量 后的 目标函数 为 : min W = -2x_1 + x_2 + 3 ( x_3' - x_3'' ) + 0x_4 + 0x_5( 2 ) 最小值 转 最大值 标准形式的目标函数是求最大值 , 这里在上面加入变量的结果的基础上 , 两边乘以 -1, 得到如下公式 : max Z = 2x_1 - x_2 - 3( x_3' - x_3'' ) + 0x_4 + 0x_56. 最终结果 : \begin{array}{lcl} max Z = 2x_1 - x_2 - 3( x_3' - x_3'' ) + 0x_4 + 0x_5 \\ \\ \\ \begin{cases} 5x_1 + x_2 + ( x_3' - x_3'' ) + x_4 = 7 \\ \\ x_1 - x_2 - 4( x_3' - x_3'' ) - x_5 = 2 \\ \\ 3x_1 - x_2 - 2( x_3' - x_3'' ) = 5 \\ \\ x_1 , x_2 , x_3' , x_3'', x_4 , x_5 \geq 0 \end{cases} \end{array}参考博客 : 【运筹学】线性规划数学模型标准形式 ( 标准形式 | 目标函数转化 | 决策变量转化 | 约束方程转化 | 固定转化顺序 | 标准形式转化实例 ) ★★ 四、线性规划解、可行解、最优解线性规划标准形式如下 : \begin{array}{lcl}max Z = \sum_{j = 1}^{n} c_j x_j\\\\ s.t \begin{cases} \sum_{j = 1}^{n} a_{ij} x_j = b_i & i = 1,2,\cdots,m \\ \\ x_j \geq 0 & j= 1, 2,\cdots,n \end{cases}\end{array}可行解 : 满足约束条件的解 , 称为可行解 ; 可行域 : 所有的可行解组成的集合 , 称为可行域 ; 最优解 : 使目标函数达到最大值的可行解 , 称为最优解 ; 线性规划求解就是在 可行解 中找出一个 最优解 ; 将线性规划转化为标准形式 , 就可以使用求解方程组的方法 , 求解线性规划的可行解 ; 五、线性规划 基、基向量、基变量、非基变量A矩阵是 m \times n维的矩阵 , m行 , n列 , 线性规划中 , 有 n个变量 , m个等式 ; 矩阵 A的秩是 m, 即等式个数 ; 矩阵 A中肯定能找到一个可逆的方阵 , 矩阵 B; 矩阵 B是矩阵 A中的满秩子矩阵 , 则称该 矩阵 B是线性规划问题的一个 基 ; P_1x_1 + P_2 x_2 + P_3x_3 = b上述示例中的 \bigl( \ P_1 \ P_2 \ \bigr)就是线性规划中的基 ; \bigl( \ P_1 \ P_2 \ \bigr), \bigl( \ P_1 \ P_3 \ \bigr), \bigl( \ P_2 \ P_3 \ \bigr)都是线性规划的基 ; 基向量 : 上述 基矩阵 中的 P_1 , P_2 , P_3列向量 , 称为 基向量 ; 基变量 : 与基向量相乘的 x_1 , x_2, x_3变量 , 称为 基变量 ; 非基变量 : 基变量之外的其它变量 , 称为非基变量 ; |
CopyRight 2018-2019 实验室设备网 版权所有 |