【运筹学】线性规划问题的解 ( 可行解

下面是一个 线性规划 数学模型 的 标准形式 :

m a x Z = ∑ j = 1 n c j x j ① 目 标 函 数 s . t { ∑ j = 1 n a i j x j = b i ( i = 1 , 2 , ⋯   , m ) ② 约 束 方 程 x j ≥ 0 , j = 1 , 2 , ⋯   , n ③ 变 量 约 束 \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} maxZ=∑j=1n​cj​xj​s.t⎩⎪⎨⎪⎧​∑j=1n​aij​xj​=bi​(i=1,2,⋯,m)xj​≥0,j=1,2,⋯,n​​②约束方程③变量约束​​①目标函数

线性规划的解 : 满足约束条件 ② 和 ③ 有很多解 , 这些解中肯定有一个或多个解 , 使 ① 目标函数 有最大值 ;

可行解 : 满足 约束方程 , 变量约束 的解是可行解 ;

可行域 : 所有的可行解集合 是可行域 ;

首先 这个解必须是可行解 , 在可行解的基础上 , 使目标函数达到最大值的解 是 最优解 ;

1. 向量 概念 :

2. 向量组 : 由多个向量组成的结构 , 下面的 α 1 \alpha_1 α1​ 就是一个 n n n 维向量 , 该向量由 n n n 个数字组成 ( n > 0 n > 0 n>0 ) ; 多个这种向量组成向量组 ;

3. 极大线性无关组 : 向量组 T T T 中 , 如果有 一部分组 α 1 , α 2 , ⋯   , α 3 \alpha_1 , \alpha_2 , \cdots , \alpha_3 α1​,α2​,⋯,α3​ 满足下面两个条件 :

α 1 , α 2 , ⋯   , α 3 \alpha_1 , \alpha_2 , \cdots , \alpha_3 α1​,α2​,⋯,α3​ 称为向量 T T T 的极大无关组 ;

4. 向量的秩 : 一个向量组的极大线性无关组所包含的向量个数 , 是向量组的秩 ;

5. 矩阵的秩 :

系数矩阵 : 约束方程的 系数 可以组成一个 m × n m \times n m×n 阶 矩阵 , 即 m m m 行 , n n n 列 , 代表 有 m m m 个约束方程 , 每个约束方程有 n n n 个变量 ;

基 :

m m m 阶满秩子矩阵 : 基是满秩子矩阵

基可行解 : 解出的基解 , 有一部分满足 变量的 非负 约束 , 即解大于等于 0 0 0 , 这些解称为基可行解 ;

有些解小于 0 0 0 的 , 显然不满足大于等于 0 0 0 的条件 , 这些基解不是可行解 , 没有用处 ;

可行基 : 基可行解 对应的基 , 称为 可行基 ;

下面的文氏图 描述的是 非可行解 , 基解 , 可行解的 集合关系 ; 总体分为 可行解 与 非可行解 , 基解中一部分是可行解 , 一部分是非可行解

求下列线性规划问题的 基矩阵 :

m a x Z = 4 x 1 − 2 x 2 − x 3 { 5 x 1 + x 2 − x 3 + x 4 = 3 − 10 x 1 + 6 x 2 + 2 x 3 + x 5 = 2 x j ≥ 0 , j = 1 , ⋯   , 5 \begin{array}{lcl} max Z = 4x_1 - 2x_2 - x_3 \\\\ \begin{cases} 5x_1 + x_2 - x_3 + x_4 = 3 \\\\ -10 x_1 + 6x_2 + 2x_3 +x_5 = 2 \\\\ x_j \geq 0 , j = 1 , \cdots , 5 \end{cases} \end{array} maxZ=4x1​−2x2​−x3​⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​5x1​+x2​−x3​+x4​=3−10x1​+6x2​+2x3​+x5​=2xj​≥0,j=1,⋯,5​​

解 :

该约束方程 , 共有 x 1 , x 2 , x 3 , x 4 , x 5 x_1 , x_2 , x_3 , x_4 , x_5 x1​,x2​,x3​,x4​,x5​ , 五个变量 ;

将约束方程补全变量为 : { 5 x 1 + x 2 − x 3 + x 4 + 0 x 5 = 3 − 10 x 1 + 6 x 2 + 2 x 3 + 0 x 4 + x 5 = 2 \begin{cases} 5x_1 + x_2 - x_3 + x_4 + 0x_5= 3 \\\\ -10 x_1 + 6x_2 + 2x_3 + 0x_4 +x_5 = 2 \end{cases} ⎩⎪⎨⎪⎧​5x1​+x2​−x3​+x4​+0x5​=3−10x1​+6x2​+2x3​+0x4​+x5​=2​

其系数矩阵为 : A = [ 5 1 − 1 1 0 − 10 6 2 0 1 ] A=\begin{bmatrix} 5 & 1 & -1 & 1 & 0 \\\\ -10 & 6 & 2 & 0 & 1 \end{bmatrix} A=⎣⎡​5−10​16​−12​10​01​⎦⎤​

该系数矩阵的秩为 m i n ( 2 , 5 ) = 2 min(2, 5) = 2 min(2,5)=2 , 矩阵的基为 2阶满秩子矩阵 ; 每一列都是一个 向量 , 共有 5 个向量 , 选择其中 2 个 , 该问题是 从 5 元集 中选取 2 个的 组合问题 ; 其基的组合方式有 C ( 5 , 2 ) C(5 , 2) C(5,2) 种 : C ( 5 , 2 ) = 5 ! 2 ! ( 5 − 2 ) ! = 5 × 4 × 3 × 2 2 × 3 × 2 = 10 C(5 , 2) = \frac{5!}{2! ( 5 - 2 )!} = \frac{5 \times 4 \times 3 \times 2}{2\times 3\times 2} = 10 C(5,2)=2!(5−2)!5!​=2×3×25×4×3×2​=10

2阶子矩阵有 10 10 10 种 选取方式 ; 基的要求还需要 满秩 , 2阶的满秩子矩阵 才是基 , 满秩 即 其列向量 线性无关 , 两列 向量 不能使用线性表示 ;

① 子矩阵 1 : ( 不是基矩阵 ) B 1 = [ 5 − 1 − 10 2 ] B_1 = \begin{bmatrix} 5 &-1 \\ -10 & 2\end{bmatrix} B1​=[5−10​−12​] 注意 该矩阵 第一列 与 第二列 存在线性关系 , 第一列向量 乘以 − 5 -5 −5 即可得到第二列向量 ; B 11 = [ 5 − 10 ] B 12 = [ − 1 2 ] B_{11} = \begin{bmatrix} 5 \\ -10\end{bmatrix} B_{12} = \begin{bmatrix} -1 \\ 2\end{bmatrix} B11​=[5−10​]B12​=[−12​] B 12 = − 5 × B 11 B_{12} = -5 \times B_{11} B12​=−5×B11​

该矩阵的秩为 1 1 1 , 不是满秩的 , 满秩秩为 m i n ( 2 , 2 ) = 2 min(2 , 2) = 2 min(2,2)=2 , 因此该矩阵不是基矩阵 ;

② 子矩阵 2 ⋯ 9 2 \cdots 9 2⋯9 : 其它矩阵 列向量 之间没有线性关系 , 都是满秩的 , 且都为 2 2 2 阶满秩子矩阵 B 2 = [ 5 1 − 10 6 ] B_2 = \begin{bmatrix} 5 &1 \\ -10 & 6\end{bmatrix} B2​=[5−10​16​] B 3 = [ 5 0 − 10 1 ] B_3 = \begin{bmatrix} 5 &0 \\ -10 & 1\end{bmatrix} B3​=[5−10​01​] B 4 = [ 5 1 − 10 0 ] B_4 = \begin{bmatrix} 5 &1 \\ -10 & 0\end{bmatrix} B4​=[5−10​10​] B 5 = [ 1 − 1 6 2 ] B_5 = \begin{bmatrix} 1 &-1 \\ 6 & 2\end{bmatrix} B5​=[16​−12​] B 6 = [ 1 1 6 0 ] B_6 = \begin{bmatrix} 1 &1 \\ 6 & 0\end{bmatrix} B6​=[16​10​] B 7 = [ 1 0 6 1 ] B_7 = \begin{bmatrix} 1 & 0 \\ 6 & 1\end{bmatrix} B7​=[16​01​] B 8 = [ − 1 1 2 0 ] B_8 = \begin{bmatrix} -1 &1 \\ 2 & 0\end{bmatrix} B8​=[−12​10​] B 9 = [ − 1 0 2 1 ] B_9 = \begin{bmatrix} -1 &0 \\ 2 & 1\end{bmatrix} B9​=[−12​01​] B 10 = [ 1 0 0 1 ] B_{10} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} B10​=[10​01​]

该矩阵 B 2 ⋯ B 10 B_2 \cdots B_{10} B2​⋯B10​ 是系数矩阵的 2阶满秩子矩阵 ;