精华内容
下载资源
问答
  • 运筹学求非基变量的检验数新方法的实现运筹学求非基变量的检验数新方法的实现运筹学求非基变量的检验数新方法的实现运筹学求非基变量的检验数新方法的实现运筹学求非基变量的检验数新方法的实现
  • I . 基矩阵 B II . 基向量 P_jP j ​ III . 基变量 IV . 非基矩阵 NN V ....VI .... 非基变量向量 X_NX N ​ 及 分块形式 VII . 分块形式的计算公式 VIII . 逆矩阵 IX . 解基变量 X . 基解 XI . 基可行解



    I . 基矩阵 B



    线性规划标准形式 , 约束方程的系数矩阵是 A A A , 如下 :

    A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n ] A = \begin{bmatrix}\\\\ & a_{11} & a_{12} & \cdots & a_{1n} &\\\\ & a_{21} & a_{22} & \cdots & a_{2n} &\\\\ & \vdots & \vdots & \ddots & \vdots &\\\\ & a_{m1} & a_{m2} & \cdots & a_{mn} &\\\\ \end{bmatrix} A=a11a21am1a12a22am2a1na2namn

    该矩阵 A A A m × n m \times n m×n 阶矩阵 , 有 m m m 行 , n n n 列 , 代表 m m m 个约束方程 , n n n 个变量 , 并且 n > m n > m n>m ;


    基矩阵 B B B :

    • ① 满秩子矩阵 : 矩阵 A A A 的 满秩子矩阵 B B B , 矩阵 B B B 的秩是 m m m ;
    • ② 列向量线性无关 : 该矩阵中的 列向量 线性无关 , 即 每一列不能通过 乘以系数 加减的方式得到另外一列列向量 ,
    • ③ 基矩阵 B B B : 这样的 系数矩阵 A A A m × m m \times m m×m 阶满秩矩阵 B B B 就是基矩阵 ;

    B = [ a 11 a 12 ⋯ a 1 m a 21 a 22 ⋯ a 2 m ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m m ] = [ P 1 P 2 ⋯ P m ] B= \begin{bmatrix}\\\\ & a_{11} & a_{12} & \cdots & a_{1m} &\\\\ & a_{21} & a_{22} & \cdots & a_{2m} &\\\\ & \vdots & \vdots & \ddots & \vdots &\\\\ & a_{m1} & a_{m2} & \cdots & a_{mm} &\\\\ \end{bmatrix} = \begin{bmatrix} & P_1 & P_2 & \cdots & P_m & \end{bmatrix} B=a11a21am1a12a22am2a1ma2mamm=[P1P2Pm]



    II . 基向量 P j P_j Pj



    基向量 :

    • ① 概念 : 基矩阵 B B B 中的每个列向量 , 都是一个 基向量 , 记作 P j P_j Pj , 其中 j = 1 , 2 , ⋯   , m j = 1 , 2 , \cdots , m j=1,2,,m ;
    • ② 基向量个数 : 每个基矩阵中有 m m m 个列向量 ;


    III . 基变量



    基变量 : 每个基向量都对应一个变量 , 基向量是列向量 , 该列向量是 x j x_j xj 变量的系数组成 , 这个对应的 x j x_j xj 变量就是基变量 ;



    IV . 非基矩阵 N N N



    非基矩阵 N N N : 确定一个基矩阵 , 剩下的列向量就是 非基向量 , 这些非基向量 组成 非基矩阵 N N N ;

    N = [ a 1 m + 1 a 1 m + 2 ⋯ a 1 n a 2 m + 1 a 2 m + 2 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m m + 1 a m m + 2 ⋯ a m n ] = [ P m + 1 P m + 2 ⋯ P n ] N= \begin{bmatrix}\\\\ & a_{1m+1} & a_{1m+2} & \cdots & a_{1n} &\\\\ & a_{2m+1} & a_{2m+2} & \cdots & a_{2n} &\\\\ & \vdots & \vdots & \ddots & \vdots &\\\\ & a_{mm+1} & a_{mm+2} & \cdots & a_{mn} &\\\\ \end{bmatrix} = \begin{bmatrix} & P_{m+1} & P_{m+2} & \cdots & P_{n} & \end{bmatrix} N=a1m+1a2m+1amm+1a1m+2a2m+2amm+2a1na2namn=[Pm+1Pm+2Pn]



    V . 系数矩阵分块形式 A = ( B N ) A = ( B N ) A=(BN)



    系数矩阵 A A A , 可以写成分块形式 :

    A = [ a 11 a 12 ⋯ a 1 n a 21 a 22 ⋯ a 2 n ⋮ ⋮ ⋱ ⋮ a m 1 a m 2 ⋯ a m n ] = [ B N ] A = \begin{bmatrix}\\\\ & a_{11} & a_{12} & \cdots & a_{1n} &\\\\ & a_{21} & a_{22} & \cdots & a_{2n} &\\\\ & \vdots & \vdots & \ddots & \vdots &\\\\ & a_{m1} & a_{m2} & \cdots & a_{mn} &\\\\ \end{bmatrix} = \begin{bmatrix} & B & N & \end{bmatrix} A=a11a21am1a12a22am2a1na2namn=[BN]



    VI . 基变量向量 X B X_B XB 非基变量向量 X N X_N XN 及 分块形式



    基变量向量 X B X_B XB :

    X B = [ x 1 x 2 ⋮ x m ] X_B = \begin{bmatrix}\\\\ & x_1 &\\\\ &x_2&\\\\ &\vdots& \\\\ &x_m&\\\\ \end{bmatrix} XB=x1x2xm

    非基变量向量 X N X_N XN :

    X B = [ x m + 1 x m + 2 ⋮ x n ] X_B = \begin{bmatrix}\\\\ & x_{m + 1} &\\\\ &x_{m + 2}&\\\\ &\vdots& \\\\ &x_n&\\\\ \end{bmatrix} XB=xm+1xm+2xn

    向量 X X X 可以写成 X B X_B XB X N X_N XN 分块形式 :

    X = [ x 1 x 2 ⋮ x n ] = [ x B x N ] X = \begin{bmatrix}\\\\ & x_1 &\\\\ &x_2&\\\\ &\vdots& \\\\ &x_n&\\\\ \end{bmatrix} = \begin{bmatrix}\\\\ & x_B &\\\\ &x_N &\\\\ \end{bmatrix} X=x1x2xn=xBxN



    VII . 分块形式的计算公式



    矩阵分块形式方程代入 : 约束方程组 A X = b AX = b AX=b ;

    b b b 是大于 0 0 0 的常数组成的向量 ;

    将上述分块形式的 矩阵 A A A 和 矩阵 X X X 代入 上述 A X = b AX = b AX=b 公式 ;

    A = [ B N ] A = \begin{bmatrix} & B & N & \end{bmatrix} A=[BN]
    X = [ X B X N ] X = \begin{bmatrix}\\\\ & X_B &\\\\ &X_N &\\\\ \end{bmatrix} X=XBXN

    得到

    [ B N ] × [ X B X N ] = b \begin{bmatrix} & B & N & \end{bmatrix} \times \begin{bmatrix}\\\\ & X_B &\\\\ & X_N &\\\\ \end{bmatrix} = b [BN]×XBXN=b

    B X B + N X N = b BX_B + NX_N = b BXB+NXN=b



    VIII . 逆矩阵



    逆矩阵 : 其中矩阵 B B B 是满秩的 m × m m \times m m×m 阶矩阵 , 该矩阵是可逆的 ( 非奇异矩阵 ) , 必定存在一个 B − 1 B^{-1} B1 , 使得
    B × B − 1 = E B \times B^{-1} = E B×B1=E

    单位矩阵 : 这里的 矩阵 E E E 是单位矩阵 , 即 左上角到右下角 对角线 上 的元素 为 1 1 1 , 其它元素为 0 0 0 ;
    主对角线 : 左上角 到 右下角 的对角线称为 主对角线 ;
    单位矩阵 示例 如下 :
    E = [ 1 0 0 0 1 0 0 0 1 ] E=\begin{bmatrix} & 1 & 0 & 0 & \\\\ & 0 & 1 & 0 &\\\\ & 0 & 0 & 1 & \end{bmatrix} E=100010001



    IX . 解基变量



    解基变量 :

    B X B + N X N = b BX_B + NX_N = b BXB+NXN=b

    N X N NX_N NXN 提到公式右边 :

    B X B = b − N X N BX_B = b - NX_N BXB=bNXN

    公式两边乘以 B − 1 B^{-1} B1 :

    B X B × B − 1 = ( b − N X N ) × B − 1 BX_B \times B^{-1} = ( b - NX_N ) \times B^{-1} BXB×B1=(bNXN)×B1

    X B = B − 1 b − B − 1 N X N X_B = B^{-1}b - B^{-1}NX_N XB=B1bB1NXN



    X . 基解



    引入基解 : 令非基变量 X N X_N XN 中所有变量为 0 0 0 , 此时上述公式为 :

    X B = B − 1 b X_B = B^{-1}b XB=B1b
    约束方程的解为
    X = [ X B 0 ] = [ B − 1 b 0 ] X = \begin{bmatrix} & X_B & \\\\ & 0 & \end{bmatrix}=\begin{bmatrix} & B^{-1}b & \\\\ & 0 & \end{bmatrix} X=XB0=B1b0
    上述解为基解 , 矩阵 B B B 是满秩的 , 其秩为 m m m , 将非基变量赋值 0 0 0 , 剩余的 m m m 个变量 , m m m 个等式 , 必能解出一组唯一解 ; 即
    ∑ j = 1 m p j x j = b \sum_{j = 1}^{m}p_j x_j = b j=1mpjxj=b
    方程组有唯一解

    X B = [ x 1 x 2 ⋮ x m ] X_B = \begin{bmatrix} & x_1 & \\\\ & x_2 &\\\\ & \vdots &\\\\ & x_m & \end{bmatrix} XB=x1x2xm
    该解 X B X_B XB 是线性规划的一个基解 ;



    XI . 基可行解



    基可行解 : 如果上述解出的基解 X B X_B XB , 满足线性规划数学模型 标准形式 的变量非负约束 , 即所有的变量都大于等于 0 0 0 , 该解称为基可行解 ;

    并不是所有的基解都是基可行解 , 只有部分基解是基可行解 ;

    展开全文
  • 一、线性规划求解、 二、根据非基变量的解得到基变量解、 三、基解、 四、基可行解、 五、可行基





    一、线性规划求解



    在上一篇博客 【运筹学】线性规划数学模型 ( 求解基矩阵示例 | 矩阵的可逆性 | 线性规划表示为 基矩阵 基向量 非基矩阵 非基向量 形式 ) 中 , 将线性规划的等式表示为以下形式 :

    B X B + N X N = b BX_B + NX_N = b BXB+NXN=b


    写成上述形式之后 , 就可以表示出上述等式的解 , 如果上述等式解满足线性规划约束变量的要求 , 即所有的变量都大于等于 0 , 那么该解就是线性规划的解 ;


    上述式子中 , X N X_N XN 非基变量 , 是可以随意取值的变量 ;

    只要非基变量 X N X_N XN 取定一组解 , 基变量 X B X_B XB 就可以被唯一确定 ;

    ( X B X N ) \begin{pmatrix} X_B \\ X_N \\ \end{pmatrix} (XBXN) 就是 方程组完整的解 ;





    二、根据非基变量的解得到基变量解



    如何根据非基变量 X N X_N XN 的解 , 确定基变量 X B X_B XB 的解 ?


    基矩阵 B B B 是可逆的 , 那么 B B B 的逆矩阵 B − 1 B^{-1} B1 是存在的 , 上述方程 B X B + N X N = b BX_B + NX_N = b BXB+NXN=b 左右两端 , 都乘以 B − 1 B^{-1} B1 , 如下计算 :


    B X B + N X N = b ( B X B + N X N ) × B − 1 = B − 1 b I × X B + B − 1 N X N = B − 1 b X B = B − 1 b − B − 1 N X N \begin{array}{lcl} BX_B + NX_N &=& b\\\\ ( BX_B + NX_N ) \times B^{-1} &=& B^{-1}b \\\\ I \times X_B + B^{-1}NX_N &=& B^{-1}b\\\\ X_B & = & B^{-1}b - B^{-1}NX_N \end{array} BXB+NXN(BXB+NXN)×B1I×XB+B1NXNXB====bB1bB1bB1bB1NXN


    其中 I I I 是单位阵 , 单位阵乘以矩阵 X B X_B XB 其结果还是 X B X_B XB ;

    关于单位阵 , 参考 单位矩阵 - 百度百科


    上述式子最终得到 X B = B − 1 b − B − 1 N X N X_B = B^{-1}b - B^{-1}NX_N XB=B1bB1NXN , 此时 如果非基变量的值 X N X_N XN 已经解出来 , 那么 基变量 X B X_B XB 可以通过上述表达式表示出来 ;





    三、基解



    给定一个基矩阵 B B B , 约束方程可以转化成 X B = B − 1 b − B − 1 N X N X_B = B^{-1}b - B^{-1}NX_N XB=B1bB1NXN 形式 , 只要给定一组 X N X_N XN 的解 , 就可以 得到一组 X B X_B XB 的解 ;


    非基变量 O O O 解 : 找到 X N X_N XN 的一组最简单的解 , 这里随意找一组 X N X_N XN 的解都可以 , 最简单的一组解就是 X N X_N XN 的所有值都是 0 0 0 , 即让所有的非基变量等于 0 0 0 , 此时 X N X_N XN 为零矩阵 , 使用 O O O 表示 ;


    对应基变量的解 : 将所有的非基变量等于 0 0 0 , 即 X N = O X_N = O XN=O 的条件代入 X B = B − 1 b − B − 1 N X N X_B = B^{-1}b - B^{-1}NX_N XB=B1bB1NXN 中 , 有 :

    X B = B − 1 b X_B = B^{-1}b XB=B1b


    此时线性规划的解为 : ( B − 1 b O ) \begin{pmatrix} B^{-1}b \\ O \\ \end{pmatrix} (B1bO) , 其中 O O O 是零矩阵 ; 该解就是线性规划的基解 ;


    基矩阵 B B B -> 非基变量解 O O O -> 基变量解 B − 1 b B^{-1}b B1b : 基解最根本是先确定基矩阵 B B B , 确定 基矩阵 B B B 之后 , 就可以将变量分为基变量 和 非基变量 , 此时将非基变量取值为零矩阵 O O O , 得到基变量的解 B − 1 b B^{-1}b B1b ;


    基解 X B X_B XB 是由基矩阵 B B B 唯一确定的 ; 只要给定基矩阵 , 就可以唯一确定基解 ;


    基解个数 : 一个线性规划中的基解个数 , 就是基矩阵可数 , 就是可逆矩阵个数 ;


    通常情况下的基解个数 : 系数矩阵 A A A , 是 m × n m \times n m×n 维的矩阵 , m m m 行等式 , n n n 个变量 , 其任意 m m m 列向量 , 组成的 m m m 阶方阵 , 都是可逆矩阵 , 其有 C ( n , m ) C(n,m) C(n,m) 个基矩阵 , 也有 C ( n , m ) C(n,m) C(n,m) 组基解 ;


    基解定义 : 确定一个 m × n m \times n m×n 阶系数矩阵的基矩阵 B B B , 令非基变量 X N X_N XN 等于 0 0 0 , 有约束条件 X B = B − 1 b − B − 1 N X N X_B = B^{-1}b - B^{-1}NX_N XB=B1bB1NXN 可以解出其基变量 X B X_B XB , 这组 ( B − 1 b O ) \begin{pmatrix} B^{-1}b \\ O \\ \end{pmatrix} (B1bO) 解 , 称为基解 ; 基解中的变量取非 0 0 0 值的个数 , 不超过等式个数 m m m , 基解总数不超过 C ( n , m ) C(n,m) C(n,m) ;





    四、基可行解



    完整的线性规划标准形式如下 :

    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=1ncjxjs.tj=1naijxj=bixj0i=1,2,,mj=1,2,,n


    上述的基解 , 只是根据 ∑ j = 1 n a i j x j = b i ( i = 1 , 2 , ⋯   , m ) \sum_{j = 1}^{n} a_{ij} x_j = b_i \quad ( i = 1,2,\cdots,m) j=1naijxj=bi(i=1,2,,m) 约束条件等式解出的 ;

    还需要满足 x j ≥ 0 ( j = 1 , 2 , ⋯   , n ) x_j \geq 0 \quad ( j= 1, 2,\cdots,n) xj0(j=1,2,,n) 条件 ;


    基可行解定义 : 满足线性规划中的 x j ≥ 0 ( j = 1 , 2 , ⋯   , n ) x_j \geq 0 \quad ( j= 1, 2,\cdots,n) xj0(j=1,2,,n) 约束条件的 基解 , 称为 基可行解 ;


    给定线性规划系数矩阵 m × n m \times n m×n 阶 :

    • 其可行解个数是无限的 , 因为其非基变量 X N X_N XN 可以有无限种取值 , 对应的基变量 X B X_B XB 也有无限种取值 ;
    • 其基解个数是有限的 , 因为非基变量只能取 O O O 零矩阵 , 对应的基变量也是有限的 , 不超过 C n m C_n^m Cnm 个 ;

    可行解有无穷多个 , 基解是有限个 , 如果一个解既是基解 , 又是可行解 , 那么称该解是基可行解 ;

    基解个数是有限的 , 基可行解 是 基解 与 可行解 的交集 , 基可行解的个数必然也是有限的 ;


    迭代思想 : 在解里面找到一个解 , 看该解是否是最优的 , 如果不是 , 就迭代到下一个解 , 继续重复查看该解是否是最优 ; 如果迭代的集合是有限的 , 其肯定要比无限的集合简单很多 ;

    因此线性规划中 , 在有限个基可行解中 , 迭代查找最优解 , 将搜索范围从无限个可行解 , 变成了有限个基可行解 ;

    在这里插入图片描述





    五、可行基



    可行基 : 基可行解 对应的 基矩阵 B B B , 就是 可行基 ;


    使用 X B = B − 1 b − B − 1 N X N X_B = B^{-1}b - B^{-1}NX_N XB=B1bB1NXN , 代入 X N = O X_N = O XN=O , 解出其基变量 X B X_B XB , 这组 ( B − 1 b O ) \begin{pmatrix} B^{-1}b \\ O \\ \end{pmatrix} (B1bO) 基解 , X N X_N XN 中的非基变量解肯定是大于等于 0 0 0 的 , 如果 B − 1 b B^{-1}b B1b 中有负分量 , 那么该解不是基可行解 , 对应的基矩阵 X B X_B XB 不是可行基 ;

    展开全文
  • \left.\begin{array}{c} x_{1} \geq 0 \\ x_{2} \geq 0 \\ \vdots \\ x_{n} \geq 0 \end{array}\right\} \text {决策变量具有非负约束} x1​≥0x2​≥0⋮xn​≥0​⎭⎪⎪⎪⎬⎪⎪⎪⎫​决策变量具有非负约束 min⁡( ...

    前言

    此总结参考 清华 王焕刚老师的课,本人只是渣渣辉。

    最优化—线性规划

    模型问题

    线性规划模型的一般形式(min)

    min ⁡ ∑ j = 1 n c j x j  s.t.  ∑ j = 1 n a i j x j = b i , ∀ 1 ≤ i ≤ p ∑ j = 1 n a i j x j ≥ b i , ∀ p + 1 ≤ i ≤ m x j ≥ 0 , ∀ 1 ≤ j ≤ q ∞ > x j > − ∞ , ∀ q + 1 ≤ j ≤ n \begin{array}{l} \min \sum_{j=1}^{n} c_{j} x_{j} \\ \text { s.t. } \quad \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \quad \forall 1 \leq i \leq p \\ \quad \sum_{j=1}^{n} a_{i j} x_{j} \geq b_{i}, \quad \forall p+1 \leq i \leq m \\ \quad x_{j} \geq 0, \forall 1 \leq j \leq q \\ \quad \infty>x_{j}>-\infty, \forall q+1 \leq j \leq n \end{array} minj=1ncjxj s.t. j=1naijxj=bi,1ipj=1naijxjbi,p+1imxj0,1jq>xj>,q+1jn

    线性规划规范形式

    在这里插入图片描述

    线性规划标准型

    max ⁡ c 1 x 1 + c 2 x 2 + ⋯ + c n x n  目标函数   s.t.  a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n = b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n = b 2 ⋮ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n = b m }  等式约束  \left.\begin{array}{ll} \max \quad c_{1} x_{1}+c_{2} x_{2}+\cdots+c_{n} x_{n} & \text { 目标函数 } \\ \text { s.t. } \quad a_{11} x_{1}+a_{12} x_{2}+\cdots+a_{1 n} x_{n}=b_{1} \\ \quad \quad \quad a_{21} x_{1}+a_{22} x_{2}+\cdots+a_{2 n} x_{n}=b_{2} \\ \quad \quad \quad \quad \quad \quad \quad \vdots \\ \quad \quad \quad a_{m 1} x_{1}+a_{m 2} x_{2}+\cdots+a_{m n} x_{n}=b_{m} \end{array}\right\} \text { 等式约束 } maxc1x1+c2x2++cnxn s.t. a11x1+a12x2++a1nxn=b1a21x1+a22x2++a2nxn=b2am1x1+am2x2++amnxn=bm 目标函数  等式约束 

    x 1 ≥ 0 x 2 ≥ 0 ⋮ x n ≥ 0 } 决策变量具有非负约束 \left.\begin{array}{c} x_{1} \geq 0 \\ x_{2} \geq 0 \\ \vdots \\ x_{n} \geq 0 \end{array}\right\} \text {决策变量具有非负约束} x10x20xn0决策变量具有非负约束

    min ⁡ (  or  max ⁡ ) ∑ j = 1 n c j x j min ⁡ (  or  max ⁡ ) C T X  s.t.  ∑ j = 1 n a i j x j = b i , ∀ 1 ≤ i ≤ m ⇒  s.t.  A X = b ⃗ x j ≥ 0 , ∀ 1 ≤ j ≤ n X ≥ 0 C = ( c 1 ⋮ c n ) X = ( x 1 ⋮ x n ) A = ( a 11 ⋯ a 1 n ⋮ ⋱ ⋮ a m 1 ⋯ a m n ) b ⃗ = ( b 1 ⋮ b m ) \begin{array}{l} \min (\text { or } \max ) \sum_{j=1}^{n} c_{j} x_{j} \quad\quad\quad\quad\quad\quad\quad\quad \min (\text { or } \max ) C^{T} X \\ \text { s.t. } \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \quad \forall 1 \leq i \leq m \quad \Rightarrow \quad \text { s.t. } \quad A X=\vec{b} \\ x_{j} \geq 0, \forall 1 \leq j \leq n \quad \quad \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad X\geq0\\ C=\left(\begin{array}{c} c_{1} \\ \vdots \\ c_{n} \end{array}\right) \quad X=\left(\begin{array}{c} x_{1} \\ \vdots \\ x_{n} \end{array}\right) \quad A=\left(\begin{array}{ccc} a_{11} & \cdots & a_{1 n} \\ \vdots & \ddots & \vdots \\ a_{m 1} & \cdots & a_{m n} \end{array}\right) \quad \vec{b}=\left(\begin{array}{c} b_{1} \\ \vdots \\ b_{m} \end{array}\right) \end{array} min( or max)j=1ncjxjmin( or max)CTX s.t. j=1naijxj=bi,1im s.t. AX=b xj0,1jnX0C=c1cnX=x1xnA=a11am1a1namnb =b1bm

    以后我们所考虑的线性规划标准型为:
    max ⁡ C T X  s.t.  A X = b ⃗ X ≥ 0 \begin{array}{c} \max C^{T} X \\ \text { s.t. } A X=\vec{b} \\ X \geq 0 \end{array} maxCTX s.t. AX=b X0
    其中 C ∈ R n , X ∈ R n , A ∈ R m × n , b ⃗ ∈ R m , C \in R^{n}, X \in R^{n}, A \in R^{m \times n}, \vec{b} \in R^{m}, CRn,XRn,ARm×n,b Rm, 并假定

    1. n > m n>m n>m
    2. A A A 的行向量线性无关

    模型的转换

    对于模型间的转换,其实就是一些变量的添加和符号的改变
    在这里插入图片描述
    在这里插入图片描述

    线性规划中的规律

    一维、二维、三维规划中:

    1. 可行集中任意两点的连线都在可行集内:凸集
    2. 最优解都不在两个不同点的连线上:顶点
    3. 所有顶点的个数有限:有限集

    线性规划的可行集是凸集,标准线性规划问题也是凸集。

    所以高纬要解决的问题是:1 可行集是否是凸集,2 顶点集为有限集 3 在顶点集中找到最优解

    如果这些问题确定了后,关键就是找到顶点了

    规范形式顶点的数学描述

    规范形式可行集 Ω : ∑ j = 1 n a i j x j ≥ b i , ∀ 1 ≤ i ≤ m \Omega: \sum_{j=1}^{n} a_{i j} x_{j} \geq b_{i}, \quad \forall 1 \leq i \leq m Ω:j=1naijxjbi,1im
    x j ≥ 0 , ∀ 1 ≤ j ≤ n x_{j} \geq 0, \forall 1 \leq j \leq n xj0,1jn
    对任意的 X ∈ Ω , X \in \Omega, XΩ, 将所有的线性不等式进行如下划分
    ∑ j = 1 n a i j x j = b i , i = k ( 1 ) , ⋯   , k ( m ^ ) , x j = 0 , j = k ( m ^ + 1 ) , ⋯   , k ( n ^ ) ∑ j = 1 n a i j x j > b i , ∀ i ∉ { k ( 1 ) , ⋯   , k ( m ^ ) } , x j > 0 , ∀ j ∉ { k ( m ^ + 1 ) , ⋯   , k ( n ^ ) } \begin{array}{l} \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, i=k(1), \cdots, k(\hat{m}), x_{j}=0, j=k(\hat{m}+1), \cdots, k(\hat{n}) \\ \sum_{j=1}^{n} a_{i j} x_{j}>b_{i}, \forall i \notin\{k(1), \cdots, k(\hat{m})\}, x_{j}>0, \forall j \notin\{k(\hat{m}+1), \cdots, k(\hat{n})\} \end{array} j=1naijxj=bi,i=k(1),,k(m^),xj=0,j=k(m^+1),,k(n^)j=1naijxj>bi,i/{k(1),,k(m^)},xj>0,j/{k(m^+1),,k(n^)}
    那么当且仅当等式方程组的解唯一时 X X X Ω \Omega Ω 的顶点

    标准形式顶点的数学描述

    Ω : ∑ j = 1 n a i j x j = b i , ∀ 1 ≤ i ≤ m x j ≥ 0 , ∀ 1 ≤ j ≤ n \begin{aligned} \Omega: & \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \quad \forall 1 \leq i \leq m \\ & x_{j} \geq 0, \forall 1 \leq j \leq n \end{aligned} Ω:j=1naijxj=bi,1imxj0,1jn

    由于由等式方程约束条件产生的只能是等式,所以 对任意的 X ∈ Ω X \in \Omega XΩ 可进行如下划分(注意 n > m ) n>m ) n>m
    ∑ j = 1 n a i j x j = b i , ∀ 1 ≤ i ≤ m , x j > 0 , j = k ( 1 ) , ⋯   , k ( m ^ ) x j = 0 , j = k ( m ^ + 1 ) , ⋯   , k ( n ) \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \forall 1 \leq i \leq m, \begin{array}{c} x_{j}>0, j=k(1), \cdots, k(\hat{m}) \\ x_{j}=0, j=k(\hat{m}+1), \cdots, k(n) \end{array} j=1naijxj=bi,1im,xj>0,j=k(1),,k(m^)xj=0,j=k(m^+1),,k(n)
    当且仅当上面的等式方程组解唯一时 X X X Ω \Omega Ω 的顶点

    总结:如果一个点 X ∈ Ω X \in \Omega XΩ,使得一些约束求作用(使得一些不等式的等号成立),若对于这些成立的约束构成的线性方程组来说,它的解不只是 X X X,那么 X X X不是 Ω \Omega Ω的顶点。

    [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Yh711aPx-1607047943335)(最优化—线性规划.assets/image-20201204092908344.png)]

    标准形式顶点的等价描述之一

    ∑ j = 1 n a i j x j = b i , ∀ 1 ≤ i ≤ m ⇒ ∑ j = 1 n ( a 1 j ⋮ a m j ) x j = ( b 1 ⋮ b m ) ⇒ ∑ j = 1 n P j x j = b ⃗ P j = ( a 1 j , ⋯   , a m j ) T , ∀ 1 ≤ j ≤ n x j > 0 , j = k ( 1 ) , ⋯   , k ( m ^ ) ∑ j = 1 n a i j x j = b i , ∀ 1 ≤ i ≤ m , x j = 0 , j = k ( m ^ + 1 ) , ⋯   , k ( n ) ⇒ x k ( j ) > 0 , ∀ 1 ≤ j ≤ m ^ , ∑ j = 1 m P k ( j ) x k ( j ) = b ⃗ \begin{array}{l} \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \forall 1 \leq i \leq m \Rightarrow \sum_{j=1}^{n}\left(\begin{array}{c} a_{1 j} \\ \vdots \\ a_{m j} \end{array}\right) x_{j}=\left(\begin{array}{c} b_{1} \\ \vdots \\ b_{m} \end{array}\right) \\ \Rightarrow \sum_{j=1}^{n} P_{j} x_{j}=\vec{b} \quad P_{j}=\left(a_{1 j}, \cdots, a_{m j}\right)^{T}, \forall 1 \leq j \leq n \\ \qquad \begin{array}{c} x_{j}>0, \quad j=k(1), \cdots, k(\hat{m}) \\ \sum_{j=1}^{n} a_{i j} x_{j}=b_{i}, \forall 1 \leq i \leq m, x_{j}=0, \quad j=k(\hat{m}+1), \cdots, k(n) \\ \Rightarrow x_{k(j)}>0, \forall 1 \leq j \leq \hat{m}, \quad \sum_{j=1}^{m} P_{k(j)} x_{k(j)}=\vec{b} \end{array} \end{array} j=1naijxj=bi,1imj=1na1jamjxj=b1bmj=1nPjxj=b Pj=(a1j,,amj)T,1jnxj>0,j=k(1),,k(m^)j=1naijxj=bi,1im,xj=0,j=k(m^+1),,k(n)xk(j)>0,1jm^,j=1mPk(j)xk(j)=b

    当且仅当 X ∈ Ω X \in \Omega XΩ 的正分量对应的系数向量线性无关

    标准形式顶点的等价描述之二

    如果 ( P 1 , ⋯   , P n ) \left(P_{1}, \cdots, P_{n}\right) (P1,,Pn) 是行满秩矩阵,那么 X X X 是可行集
    Ω = { X = ( x 1 , ⋯   , x n ) T ∣ ∑ j = 1 n P j x j = b ⃗ , x j ≥ 0 , ∀ 1 ≤ j ≤ n } \Omega=\left\{X=\left(x_{1}, \cdots, x_{n}\right)^{T} \mid \sum_{j=1}^{n} P_{j} x_{j}=\vec{b}, x_{j} \geq 0, \forall 1 \leq j \leq n\right\} Ω={X=(x1,,xn)Tj=1nPjxj=b ,xj0,1jn}
    的顶点充要条件是:存在可逆方阵 ( P k ( 1 ) , ⋯   , P k ( m ) ) \left(P_{k(1)}, \cdots, P_{k(m)}\right) (Pk(1),,Pk(m)), 可以把 X X X 的分量划分为 x k ( j ) , j = 1 , ⋯   , n , x_{k(j)}, j=1, \cdots, n, xk(j),j=1,,n, 使满足
    ( x k ( 1 ) ⋮ x k ( m ) ) = ( P k ( 1 ) , ⋯   , P k ( m ) ) − 1 b ⃗ ≥ 0 , x k ( j ) = 0 , ∀ m + 1 ≤ j ≤ n \left(\begin{array}{c}x_{k(1)} \\ \vdots \\ x_{k(m)}\end{array}\right)=\left(P_{k(1)}, \cdots, P_{k(m)}\right)^{-1} \vec{b} \geq 0, \quad x_{k(j)}=0, \forall m+1 \leq j \leq n xk(1)xk(m)=(Pk(1),,Pk(m))1b 0,xk(j)=0,m+1jn
    主要理由 : ∑ j = 1 m P k ( j ) x k ( j ) = b ⃗ ⇒  正分量对应的系   数向量线性无关  \large : \sum_{j=1}^{m} P_{k(j)} x_{k(j)}=\vec{b} \Rightarrow \begin{array}{l}\text { 正分量对应的系 } \\ \text { 数向量线性无关 }\end{array} :j=1mPk(j)xk(j)=b  正分量对应的系  数向量线性无关 

    线性规划标准形式的一些基本概念

    基阵、基本解、基本可行解、基变量、非基变量
    称可逆矩阵 ( P k ( 1 ) , ⋯   , P k ( m ) ) \left(P_{k(1)}, \cdots, P_{k(m)}\right) (Pk(1),,Pk(m))基阵
    称其分量由下式决定的 X X X基本解
    ( x k ( 1 ) ⋮ x k ( m ) ) = ( P k ( 1 ) , ⋯   , P k ( m ) ) − 1 b ⃗ , x k ( j ) = 0 , ∀ m + 1 ≤ j ≤ n \left(\begin{array}{c} x_{k(1)} \\ \vdots \\ x_{k(m)} \end{array}\right)=\left(P_{k(1)}, \cdots, P_{k(m)}\right)^{-1} \vec{b}, x_{k(j)}=0, \forall m+1 \leq j \leq n xk(1)xk(m)=(Pk(1),,Pk(m))1b ,xk(j)=0,m+1jn
    称可行的基本解为基本可行解 称基阵对应变量为基变量,其余变量为非基变量
    标准线性规划的基本可行解就是可行集的顶点
    标准线性规划的可行集的顶点个数总是有限的

    线性规划标准形式的基本定理

    【定理1】 一个标准形式线性规划问题若有可行解,则至少存在一个基本可行解
    【定理2】 一个标准形式线性规划问题若有有限的最优目标值,则一定存在一个基本可行解是最优解
    【定理3】 如果标准线性规划问题的某个基可行解的相邻的基可行解都不比它好,那么这个基可行解就是最优解

    综上所述:对于线性规划,只用求得它的基本可行解,就能在有限的基本可行解中找到最优解。

    展开全文
  • 文章目录退化和某个非基变量检验数为零退化问题退化问题的本质某个非基变量检验数为零 退化和某个非基变量检验数为零 退化问题 ​ 基本可行解的基变量数值等于0。 退化问题的本质 ​ 多个可行基阵对应于一个基本可行...

    退化和某个非基变量检验数为零

    退化问题

    ​ 基本可行解的基变量数值等于0。

    退化问题的本质

    ​ 多个可行基阵对应于一个基本可行解。

    某个非基变量检验数为零

    ​ 对于求max的线性规划问题,如果所有检验数均满足 则说明已经得到最优解, 若此时某非基变量的检验数为零 ,则说明该优化问题有无穷多最优解。

    展开全文
  • :若在约束方程组系数矩阵中找到一个基,令其非基变量为零,再求解该m元线性方程组可得到唯一解,该解称之为线性规划的基本解。 基解,基可行解,可行基 所以需要注意的是 基本解不一定是可行解,非负的基解才...
  • I . 线性规划问题解 II . 可行解 与 可行域 III . 最优解 IV . 秩 的 概念 V . 基 的概念 VI . 基变量 与 非基变量 VII . 基解 VIII . 基可行解 与 可行基 IX . 示例 求基矩阵
  • 一、线性规划模型三要素、 二、线性规划一般形式和标准形式、 三、线性规划普通形式转为标准形式、 1、目标函数、 2、决策变量约束、 3、等式约束方程、 ...五、线性规划 基、基向量、基变量、非基变量
  • 一、知识点回顾、 1、线性规划三要素、 2、线性规划一般形式、 3、线性规划标准形式、 二、线性规划解、可行解、最优解、 三、阶梯型矩阵、 四、阶梯型矩阵向量、 五、基、基向量、基变量、非基变量
  • 一、运输规划基变量个数、 二、运输规划问题一般形式、 三、运输规划中的产销( 不 )平衡问题
  • 在学习《线性规划与目标规划》的过程中,课程的主讲老师郭韧给出了对于概念的定义如下图 图片来源:运筹学(中国大学mooc网) 由此我产生了几个疑惑:1.如何理解B是线性规划问题的一个?2.为什么说最多有CnmC_n...
  • 1. 简单情况 第一阶段目标是找可行解。例如: {x1=x3−1x2=x3+2 \left\{ \begin{array}{} x_1& = &x_3-1\\ x_2&...显然非基变量
  • 一、第一次迭代 : 中心元变换、 二、第一次迭代 : 单纯形表、 三、第一次迭代 : 计算检验数、 ...五、第一次迭代 : 选择入基变量、 六、第一次迭代 : 选择出基变量、 七、第一次迭代 : 更新单纯形表、
  • {m+1},x_{m+2},\cdots,x_nxm+1​,xm+2​,⋯,xn​ 为非基变量,当非基变量取值均为零时且满足约束(2)的一个解 xxx 称为关于基 B\bf BB的一个基本解,线性规划问题最多只有 CnmC{^m_n}Cnm​个基本解 基本可行解 若一...
  • 一、线性规划示例、 二、转化成标准形式、 三、初始基可行解、 四、列出单纯形表、 五、计算检验数、 六、选择入基变量与出基变量、 七、第一次迭代 : 列出单纯形表、
  • 一、第一次迭代 : 进行行变换、 二、第一次迭代 : 计算检验数、 三、第一次迭代 : 最优解判定、 四、第一次迭代 : 入基变量、 五、第一次迭代 : 出基变量
  • 一、初始基可行解后第一次迭代、 二、迭代后新的单纯形表、 三、方程组同解变换、 四、生成新的单纯形表、 五、解出基可行解、 六、计算检验数并选择入基变量、 七、选择出基变量
  • 一、生成初始单纯形表、 二、计算非基变量检验数、 三、最优解判定、 四、选择入基变量、 五、选择出基变量、 六、更新单纯形表、
  • 运筹学笔记 运输问题

    千次阅读 2021-05-08 11:20:32
    闭回路法的原理: 通过寻找闭回路来找到非基变量的检验数 闭回路判别某基本可行解是否为最优的经济解释为: 若用闭回路计算某个非基变量检验数小于零,则必存在对现行调运方案的改进方法,可使总费用进一步降低。...
  • 单纯形法原理 | 单纯形法流程 | 单纯形表 | 计算检验数 | 最优解判定 | 入基变量 | 出基变量 | 方程组同解变换
  • 当目标函数用非基变量的线性组合表示时,所有的系数均不大于0,则表示目标函数达到最优。 如果,有一个非基变量的系数为0,其他的均小于0,表示目标函数的最优解有无穷多个。这是因为目标函数的梯度与某一边界...
  • 一、求解基矩阵示例、 二、矩阵的可逆性分析、 三、基矩阵、基向量、基变量、 四、线性规划等式变型
  • 线性规划总结

    千次阅读 2020-03-12 18:11:47
    注:等式约束中的决策变量要求负数,而不等式约束中的决策变量时自由的。 标准模型 引入冗余的决策变量,使得不等式约束转化为等式约束。这里的每个决策变量都具有负性。 把上述模型用矩阵表示就是 min(or ...
  • 当目标函数用非基变量的线性组合表示时,所有的系数均不大于0,则表示目标函数达到最优。 如果,有一个非基变量的系数为0,其他的均小于0,表示目标函数的最优解有无穷多个。这是因为目标函数的梯度与某一边界正交...
  • 运筹学期末复习2020年

    千次阅读 多人点赞 2020-08-29 16:28:29
    所以只要在目标函数(2-14)的表达式中还存在有正系数的非基变量,这表示目标函数值还有增加的可能,就需要将非基变量与基变量进行对换。 2.3.2 初始基可行解的确定 为了确定初始基可行解,要首先找出初始可行基,其...
  • python递归 全局变量 全局变量

    千次阅读 2018-10-12 17:14:02
    # 优先读取局部变量,能读取全局变量,无法对全局变量重新赋值 NAME=“fff”, # 但是对于可变类型,可以对内部元素进行操作 # 如果函数中有global关键字,变量本质上就是全局的那个变量,可读取可赋值 NAME=“fff”...
  • 阶段总结 , 人工变量法求解线性规划全过程
  • 10分钟也不一定学会的灵敏度分析

    千次阅读 多人点赞 2020-10-31 13:50:22
    就是令CBB-1a - c,在该题中的解决过程如下图所示: 三、约束条件发生变化 这类问题暂时只考虑非基变量x的系数发生变化(我们专业是这样),如何使最优解不变。例如非基变量x12的系数由2变为2 + △a12,求x12检验数...
  • 在选择保留进基变量所在行的过程中不用考虑进基变量的系数不是正数的行 ,选择进基变量系数非负的行保留进基变量 思路:①假设已知一个基本可行解➡️②选择能够使目标函数改进的进基变量➡️③判断目前的基本可行解...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 50,700
精华内容 20,280
关键字:

非基变量