精华内容
下载资源
问答
  • 方程组变为: 此时的解,称为基解 (唯一) (基可以为若干个) 基可行解 其中的 称为可行基 注:基解的几何意义是:强约束方程(“=”)下,图形的所有交点 基可行解的几何意义: (1)方程的交点(基解) (2)...

    原视频:https://www.bilibili.com/video/BV194411y7sA?p=7

    线性规划问题的标准形式

    一般情况下,  Z=f(x,y )        min Z / max Z

     

    对于一般的线性规划问题,容易得到:

      Z=f(x_1,x_2,\cdots,x_n)=c_1x_1+c_2x_2+\cdots+c_nx_n(c_i\in R)x_i\in R\\

    \left \{ \begin {matrix} a_{11}_x_1+a_{12}x_2+\cdots+a_{1n}x_n=(\leq,\geq)b_1\: \:\:\:\:\:\:a_i\in R\\ a_{21}_x_1+a_{22}x_2+\cdots+a_{2n}x_n=(\leq,\geq)b_2\:\:\:\:\:\:b_i\in R\\ \vdots\\ a_{n1}_x_1+a_{n2}x_2+\cdots+a_{nn}x_n=(\leq,\geq)b_n\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\: \end {matrix}

     

    通过恒等变形,将一般形式写为标准形式,从而方便之后的求解

    (1)目标函数统一为:  max Z                 min Z\Rightarrow  令  Z^{'}=-Z     求max Z{'}

    (2)b_i  :原问题中  b_i\in R(b_i>0)       \left \{ \begin{matrix} b_i>0 \\ b_i<0 \\ bi=0 \end{matrix}         

                当“ < ”,\Rightarrow等式两边同时添“负号”

                当 “ = ”,表示出现了退化

    (3)      约束符号= \:\: \leq \:\:\geq”                      

                              “ \leq ”     加入新的变量 → 松弛变量   “ \leq \:\Rightarrow \:= ”

                              “ \geq ”     减去新的变量 → 剩余变量   “ \geq \:\Rightarrow \:= ”

    (4)   统一“决策变量 \geq 0”    :  \left \{ \begin{matrix} x_i\geq0 \\ x_i\leq0 \\ x_i=0 \\x_i\in R \end{matrix}       

            当 “ = ”,直接写为“ \geq ”                   

            当 “ \leq ” , 令x_i^{'} = -x_i,\:\:\:\:x_i^{'}\geq 0 带入约束方程

            当“ x_i \in R ”,  x_i = x_i^{'} - x_i^{''},       x_i^{'} \geq0,\:\:\:\: x_i^{''}\geq0

     

     

               

              (5)形式上调整目标函数,将新引入的变量写回目标函数中去

     

         

         

      

    线性规划的讨论

      max Z=c_1x_1+c_2x_2+\cdots+c_nx_n(c_i\in R)x_i\geq0

    \left \{ \begin {matrix} a_{11}_x_1+a_{12}x_2+\cdots+a_{1n}x_n=b_1\: \:\:\:\:\:\:a_i\in R\\ a_{21}_x_1+a_{22}x_2+\cdots+a_{2n}x_n=b_2\:\:\:\:\:\:b_i\in R\\ \vdots\\ a_{n1}_x_1+a_{n2}x_2+\cdots+a_{nn}x_n=b_n\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\\ x_i\geq0, b_i>0 \end {matrix}

    \begin{bmatrix} a_{11} &a_{12} &\cdots &a_{1n} \\ a_{21}&a_{22} &\cdots &a_{2n} \\ \vdots& &\vdots &\vdots \\ a_{n1}& a_{n2} & \cdots & a_{nn} \end{bmatrix}\begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix} =\begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_n \end{bmatrix}                           max Z = c_1x_1+c_2x_2+\cdotsc_nx_n\\ = [c_1 \:\:\:c_2\:\:\:\cdots\:\:\:c_n] \begin{bmatrix} x_1\\x_2\\ \vdots\\x_n \end{bmatrix}

                            A \:\:\:X \:\:\:=b                                                      max \:\:Z\:\:=\:C \:\:X

    将A矩阵的每一列看成一个整体,记做列P,即A=(p_1\:\:\:p_2\:\:\cdots \:\:p_n)

    (1)可行解(满足约束方程

      能使  AX=b成立的所有  X=(x_1,x_2,\cdots,x_n)^T(公式中,X为列向量,因此加转置T)

    (2)AX=b  提出更多的信息

      基、基可行解、可行基

    \begin{bmatrix} a_{11} &a_{12} &\cdots &a_{1n} \\ a_{21}&a_{22} &\cdots &a_{2n} \\ \vdots& &\vdots &\vdots \\ a_{m1}& a_{m2} & \cdots & a_{mn} \end{bmatrix}  (m < n)         

    假设 R(A)= m, 从n列中选出 m列作为

    B = \begin{bmatrix} a_{11} \:\:\: \cdots \:\:\:a_{1m}\\ \vdots\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\vdots\\ a_m1\:\:\: \cdots \:\:\:a_{mm} \end{bmatrix} =(p_1,p_2,p_3,\cdots,p_m)

    (p_1,\cdots,p_n) \begin{pmatrix} x_1\\\vdots\\x_n \end{pmatrix}=\begin{pmatrix} b_1\\\vdots\\b_m \end{pmatrix} \Rigtarrow \:\:\:\:\:\:p_1x_1+p_2x_2+\cdots+ p_nx_n = \begin{pmatrix} b_1\\\vdots\\b_m\end{pmatrix}

    \Rightarrow \begin{pmatrix} a_{11}\\\vdots\\a_{m1} \end{pmatrix}x_1+ \begin{pmatrix} a_{12}\\\vdots\\a_{m2} \end{pmatrix}x_2+ \cdots+ \begin{pmatrix} a_{1m}\\\vdots\\a_{mm} \end{pmatrix}x_m+ \cdots+ \begin{pmatrix} a_{1n}\\\vdots\\a_{mn} \end{pmatrix}x_n= \begin{pmatrix} b_1\\\vdots\\b_m \end{pmatrix}

                   1\cdots m     基向量                           m+1 \cdots n  非基向量

           \begin{pmatrix} a_{11} \:\:\: \cdots \:\:\:a_{1m}\\ \vdots\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\vdots\\ a_{m1}\:\:\: \cdots \:\:\:a_{mm} \end{pmatrix} \begin{pmatrix} x_1\\ \vdots\\x_m \end{pmatrix} + \begin{pmatrix} a_{m+1,m+1} \:\:\: \cdots \:\:\:a_{m+1,n}\\ \vdots\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\vdots\\ a_{n,m+1}\:\:\: \cdots \:\:\:a_{n,n} \end{pmatrix} \begin{pmatrix} x_m+1\\ \vdots\\x_n \end{pmatrix} =\begin{pmatrix} b_1\\ \vdots\\b_m \end{pmatrix}

        \Rightarrow \sum^m_{j=1}P_jx_j\:\:=b\:\:-\:\:\sum^n_{j=m+1}P_jx_j

       当非基向量对应的x取0时,方程组变为:

               \begin{pmatrix} a_{11}\\\vdots\\a_{m1} \end{pmatrix}x_1+ \begin{pmatrix} a_{12}\\\vdots\\a_{m2} \end{pmatrix}x_2+ \cdots+ \begin{pmatrix} a_{1m}\\\vdots\\a_{mm} \end{pmatrix}x_m = \begin{pmatrix} b_1\\\vdots\\b_m \end{pmatrix}

                            B\:\:\:\:X \:\:\:= \:\:\:b\:\:\:\:(m<n)           此时的解,称为基解 (唯一)    (基可以为若干个)

                x_B^T=(x_1.x_2,\cdots,x_m,0,0,0,0,0) (x_i\geq 0)         基可行解          其中的 x_i 称为可行基

                                                      x_{m+1},\cdots,x_n=0

    注:基解的几何意义是:强约束方程(“=”)下,图形的所有交点

          基可行解的几何意义: (1)方程的交点(基解) (2)可行域的顶点

     

     

     

     

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





    一、线性规划求解



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

    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 不是可行基 ;

    展开全文
  • 最优化理论线性规划的基,基解,基可行解,退化基可行解基基解基可行解退化基可行解 基 在一个线性规划中,写出约束条件的系数矩阵,如: 其中任意一个非退化子矩阵为A的一个基,如: (非退化矩阵就是行列式非0的...

    最优化理论线性规划的基,基解,基可行解,退化基可行解

    在一个线性规划中,写出约束条件的系数矩阵,如:
    在这里插入图片描述
    其中任意一个非退化子矩阵为A的一个基,如: (非退化矩阵就是行列式非0的矩阵)
    在这里插入图片描述
    注意:要明确Pi是哪几个。

    基解

    确定基后,把除了基解之外对应的变量置零,这里假如以P1,P2,P3为基,则X4,X5赋值为0,代入原约束条件,解出X1,X2,X3。得到一个基解。

    基可行解

    在得到基解后,得到的所有Xi>=0的基解为基可行解

    退化基可行解

    得到的基可行解有>=1个变量为0的,则称该基可行解为退化基可行解。

    展开全文
  • 一、单纯形法原理、 二、单纯形法流程、 三、初始的基可行解查找、





    一、单纯形法原理



    单纯形法的理论基础 :


    定理 1 1 1 ( 可行域是凸集 ) : 如果线性规划的问题 存在可行解 , 其 可行域 必定是 凸集 ;

    定理 2 2 2 ( 基可行解是凸集顶点 ) : 线性规划的 基可行解 X B X_B XB 对应了上述 可行域 ( 凸集 ) 的顶点位置 ;

    定理 3 3 3 ( 某个基可行解是最优解 ) : 如果线性规划问题 存在最优解 , 那么 一定存在一个基可行解是最优解 ;


    参考上一篇博客 【运筹学】线性规划 图解法 ( 唯一最优解 | 无穷最优解 | 无界解 | 无可行解 ) 进行分析 :


    给定线性规划 :

    m a x Z = 2 x 1 + x 2 s . t = { x 1 + 1.9 x 2 ≥ 3.8 x 1 − 1.9 x 2 ≤ 3.8 x 1 + 1.9 x 2 ≤ 10.2 x 1 − 1.9 x 2 ≥ − 3.8 x 1 , x 2 ≥ 0 \begin{array}{lcl} max Z = 2x_1 + x_2\\\\ s.t = \begin{cases} x_1 + 1.9x_2 \geq 3.8\\\\ x_1 - 1.9x_2 \leq 3.8\\\\ x_1 + 1.9x_2 \leq 10.2\\\\ x_1 - 1.9x_2 \geq -3.8\\\\ x_1 , x_2 \geq 0 \end{cases} \end{array} maxZ=2x1+x2s.t=x1+1.9x23.8x11.9x23.8x1+1.9x210.2x11.9x23.8x1,x20


    使用图解法进行分析 , 得到如下结果 ;

    在这里插入图片描述

    使用迭代的思想进行求解 :

    • 无限个解中迭代 : 上图中的 可行域 D D D 中的点是无限的 , 可以在所有的无限个可行域 D D D 解中进行迭代 , 逐个迭代很难 ;

    • 有限个解中迭代 : 因此选取 可行域 ( 凸集 ) 的顶点 , 也就是 基可行解 进行迭代 , 该线性规划问题的基可行解是有限的 , 只有 4 4 4 个 , 即该凸集有 4 4 4 个顶点 ;

    上图的凸集中的 4 4 4 个顶点 , 必然有一个是最优解 , 因此迭代的时候 , 不用从 D D D 可行域中的无限个点中进行迭代 , 只需要在有限个基可行解中进行迭代 , 即可找到最优解 ;


    单纯形法的原理的基础就是源自上述理论 , 在线性规划的有限个基可行解中 , 必定存在一个解释最优解 , 逐个迭代 , 将这个最优解找出即可 ;


    从无限个可行解中进行迭代 , 到有限个基可行解中进行迭代 , 简单了很多 ;

    但是对于 m × n m \times n m×n 阶的线性规划系数矩阵 , 其基可行解的个数可能有 C n m C_n^m Cnm 个 , 如果 n n n m m m 很大的话 , 基可行解的数目还是很大 , 这是一个指数级的数 , 因此使用多项式算法 , 完成上述操作 , 计算量还是很大的 ;


    这里使用单纯形法 , 进行迭代 , 要比使用多项式法计算量更少 ;





    二、单纯形法流程



    在这里插入图片描述

    单纯形法的基本流程 :


    ① 初始基可行解 : 首先找到初始的基可行解 ;

    ② 判定是否最优解 : 需要一个准则 , 判定该初始基可行解 , 是否是最优解 ; 这里是单纯形法最核心问题 ;

    ③ 是最优解 : 如果该基可行解是最优解 , 那么结束迭代 ;

    ④ 不是最优解 : 如果该基可行解不是最优解 , 那么迭代到下一个基可行解 , 继续判定是否是最优解 ; 如何迭代也需要一个准则 ;



    这里涉及到了两个准则 :

    • 判断最优解 : 判断一个 基可行解 是否是最优解 ;
    • 迭代原则 : 如何从一个 基可行解 迭代到下一个基可行解 ;


    单纯形法涉及到的问题 :


    ① 初始解 : 如何找到初始基可行解 ;

    ② 最优解 : 如何找到一个准则 , 用于判定基可行解是否是最优解 ;

    ③ 迭代解 : 如果一个基可行解不满足准则 , 如何去选择下一个基可行解进行迭代 ;

    解决上述 3 3 3 个问题 , 基可行解的算法 , 也就可以得出 ;





    三、初始的基可行解查找



    如何去找初始的基可行解 , 首先要找到一个 , 并且该基是 可行基 ;



    对于 m × n m \times n m×n 阶的系数矩阵 :


    基 : C ( n , m ) C(n, m) C(n,m) 个子矩阵中找到基矩阵 , 基矩阵的条件是 m m m 阶方阵是可逆的 ;

    参考 【运筹学】线性规划数学模型 ( 求解基矩阵示例 | 矩阵的可逆性 | 线性规划表示为 基矩阵 基向量 非基矩阵 非基向量 形式 ) 一、求解基矩阵示例 博客章节 , [ 5 1 − 1 1 0 − 10 6 2 0 1 ] \begin{bmatrix} &5 & 1 & -1 & 1 & 0 & \\\\ & -10 & 6 & 2 & 0 & 1 & \end{bmatrix} 51016121001 系数矩阵 , 有 C ( 5 , 2 ) = 10 C (5 , 2) = 10 C(5,2)=10 个子矩阵 , 但是只有 9 9 9 个是可逆的 ;


    基矩阵如下 :


    B 1 = [ 5 1 − 10 6 ] B_1 = \begin{bmatrix} &5 & 1 & \\\\ & -10 & 6 & \end{bmatrix} B1=51016 , B 2 = [ 1 − 1 6 2 ] B_2 = \begin{bmatrix} &1 & -1 & \\\\ & 6 & 2 & \end{bmatrix} B2=1612 , B 3 = [ 5 0 − 10 1 ] B_3 = \begin{bmatrix} &5 & 0 & \\\\ & -10 & 1 & \end{bmatrix} B3=51001 ,

    B 4 = [ 1 1 6 0 ] B_4 = \begin{bmatrix} &1 & 1 & \\\\ & 6 & 0 & \end{bmatrix} B4=1610 , B 5 = [ 5 1 − 10 0 ] B_5 = \begin{bmatrix} &5 & 1 & \\\\ & -10 & 0 & \end{bmatrix} B5=51010 , B 6 = [ − 1 0 2 1 ] B_6 = \begin{bmatrix} &-1 & 0 & \\\\ & 2 & 1 & \end{bmatrix} B6=1201 ,

    B 7 = [ − 1 1 2 0 ] B_7 = \begin{bmatrix} &-1 & 1 & \\\\ & 2 & 0 & \end{bmatrix} B7=1210 , B 8 = [ 1 10 6 1 ] B_8 = \begin{bmatrix} &1 & 10 & \\\\ & 6 & 1 & \end{bmatrix} B8=16101 , B 9 = [ 1 0 0 1 ] B_9 = \begin{bmatrix} &1 & 0 & \\\\ & 0 & 1 & \end{bmatrix} B9=1001 ;



    选择一个基矩阵 , 每个基矩阵都唯一对应一个基解 , 如果该解大于等于 0 0 0 , 说明该解是基可行解 , 那么该选择的基矩阵 , 就是可行基 ;


    参考 【运筹学】线性规划数学模型 ( 线性规划求解 | 根据非基变量的解得到基变量解 | 基解 | 基可行解 | 可行基 ) 三、基解 博客章节 , 基解的公式是

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


    使用 B 1 = [ 5 1 − 10 6 ] B_1 = \begin{bmatrix} &5 & 1 & \\\\ & -10 & 6 & \end{bmatrix} B1=51016 矩阵作为基矩阵 , 求出其对应的基可行解 , 代入上述公式 :


    X B = B − 1 b X B = [ 5 1 − 10 6 ] − 1 × [ 3 2 ] \begin{array}{lcl} X_B = B^{-1}b\\\\ X_B = \begin{bmatrix} &5 & 1 & \\\\ & -10 & 6 & \end{bmatrix}^{-1} \times \begin{bmatrix} &3 & \\\\ & 2 & \end{bmatrix} \end{array} XB=B1bXB=510161×32


    如果上述 X B X_B XB 的两个分量 ( x 1 x 2 ) \begin{pmatrix} x_1\\ x_2 \\ \end{pmatrix} (x1x2) 都大于 0 , 说明该解释基可行解 , 该基矩阵 B 1 B_1 B1 是可行基 ;



    使用算法进行迭代 , 一个个判断太浪费时间 , 选择 B 1 B_1 B1 作为基矩阵 , 计算很复杂 , 这里选择 B 9 = [ 1 0 0 1 ] B_9 = \begin{bmatrix} &1 & 0 & \\\\ & 0 & 1 & \end{bmatrix} B9=1001 作为基矩阵 , 这是个单位阵 , 其逆矩阵还是其单位阵本身 ;

    B 9 B_9 B9 基矩阵对应的基变量是 X B = ( x 4 x 5 ) X_B = \begin{pmatrix} x_4\\ x_5 \\ \end{pmatrix} XB=(x4x5) , 将基矩阵代入 X B = B − 1 b X_B = B^{-1}b XB=B1b 公式 ;

    X B = B − 1 b X B = [ 1 0 0 1 ] − 1 × [ 3 2 ] X B = [ 1 0 0 1 ] × [ 3 2 ] X B = [ 3 2 ] \begin{array}{lcl} X_B = B^{-1}b\\\\ X_B = \begin{bmatrix} &1 & 0 & \\\\ & 0 & 1 & \end{bmatrix}^{-1} \times \begin{bmatrix} &3 & \\\\ & 2 & \end{bmatrix}\\\\ X_B = \begin{bmatrix} &1 & 0 & \\\\ & 0 & 1 & \end{bmatrix}\times \begin{bmatrix} &3 & \\\\ & 2 & \end{bmatrix}\\\\ X_B = \begin{bmatrix} &3 & \\\\ & 2 & \end{bmatrix} \end{array} XB=B1bXB=10011×32XB=1001×32XB=32


    由上述计算过程得到 X B = ( x 4 x 5 ) = ( 3 2 ) X_B = \begin{pmatrix} x_4\\ x_5 \\ \end{pmatrix} = \begin{pmatrix} 3\\ 2 \\ \end{pmatrix} XB=(x4x5)=(32) 结果 , x 4 x_4 x4 x 5 x_5 x5 都大于 0 0 0 , ( 0 0 0 3 2 ) \begin{pmatrix} 0\\ 0\\ 0\\ 3\\ 2 \\ \end{pmatrix} 00032是基可行解 , 该 X B X_B XB 是可行基 ;


    使用 B 1 B_1 B1 作为基矩阵 , 不好计算 , 还需要求 B 1 B_1 B1 矩阵的逆矩阵 , B 9 B_9 B9 是单位阵 , 所有的 单位阵 I I I 都是可行基 , 初始基可行解选取时 , 优先选择单位阵 ;

    展开全文
  • I . 线性规划问题解 II . 可行解 与 可行域 III . 最优解 IV . 秩 的 概念 V . 基 的概念 VI . 基变量 与 非基变量 VII . 基解 VIII . 基可行解 与 可行基 IX . 示例 求基矩阵
  • 一、运输规划问题、 二、找初始基可行解、 三、计算检验数、 四、调整运量 ( 换基 )
  • 深入理解线性规划中的基可行解

    千次阅读 2018-10-13 12:43:45
    运筹学的书上给了基可行解的定义以及一系列线性空间的理论,但读者可能会觉得这个定义给的很突兀并且个别理论的证明 也显得太数学化了,难以从形象上去理解。 先说说基可行解的定义,B是原矩阵a的一个m阶满秩矩阵...
  • 一、表上作业法 第一步 : 确定初始基可行解、 二、最小元素法
  • 三、查找初始基可行解、 四、初始基可行解的最优解判定、 五、第一次迭代 : 入基与出基变量选择、 六、第一次迭代 : 方程组同解变换、 七、第一次迭代 : 生成新的单纯形表、 八、第一次迭代 : 解出基可行解、 九、第...
  • 一、最优解判别、 二、初始基可行解、 三、运费修改可行性方案、 四、闭回路法
  • 线性规划里面的基本解、基可行解,一张图看懂

    万次阅读 多人点赞 2020-05-07 16:06:13
    书上给的是定义是 ![在这里插入图片描述](https://img-blog.csdnimg.cn/20200507155550297.png) 说了半天没有一个直观的理解,下面一张图展示了什么是基本解,什么是基本可行解 ...
  • 一、运输规划问题、 二、找初始基可行解
  • 基可行解 严格约束与基可行解的关系 我们在本节前半部分使用了极点,顶角等几何手段来描述凸集的几何构造,然后又引入了严格约束,现将二者联系起来,从几何与代数两个角度来描述基解,基可行解等概念 Definition ...
  • 线性规划做为运筹学中较大板块知识点而言,理清这5种概念至关重要 ...基可行解:非基变量=0+约束条件等式+决策变量非负 基最优解:非基变量=0+约束条件等式+决策变量非负+目标函数最优 五种概念相互关
  • 每个极点都对应着一个基可行解,且每个基可行解都对应着一个极点 。有了这个定理,再结合可行域有解情况下最优解一定可以在极点取到,我们只要枚举基可行解,就能找到最优解了(至于如何优雅地枚举下节课再说- -)。...
  • #运输问题求解:使用Vogel逼近法寻找初始基本可行解import numpy as npimport pandas as pdimport copy#定义函数TP_vogel,用来实现Vogel法寻找初始基可行解def TP_vogel(c,a,b):#函数含有3个变量,分别是成本系数...
  • Vogel法一般能得到一个比用西北角法和最小元素法所得的初始基本可行解更好的初始基本可行解。使用Vogel法时,先计算出各行各列中的罚数(最小的成本系数cij和次小的成本系数cij之间的差的绝对值),在具有最大罚数的...
  • 文章目录 可行解 向量和非向量 变量、非变量、解 基本可行解 图解 首先我们先列出线性规划的数学模型,通过该模型来一一说明每个概念的含义。 maxZ=cx(1)max Z= \bf cx \tag 1maxZ=cx(1) s.t.   Ax=b...
  • I . 基矩阵 B II . 基向量 P_jP j ​ III . 基变量 IV . 非基矩阵 NN V . 系数矩阵分块形式 A = ( B N )A=(BN) VI . 基变量向量 X_BX B ​ 非基变量向量 X_NX ...VII ....VIII ....IX ....X ....XI . 基可行解
  • * 计算womiga的值,用来判断原来的线性规划问题是否具有可行解 */ public double womiga(){ double womiga=0;//定义变量womiga for(int i=0;i;i++){ womiga=womiga+b[i]*c()[Integer.parseInt(Xb[i]....
  • 基本可行解

    千次阅读 2020-12-30 13:12:05
    基本概念 线性规划问题的标准形式为: 式中: 是目标化函数,称为约束方程,为变量非负约束。一般情况下,应有m<...此时约束方程有无穷多组解,线性规划就是...线性规划问题如果有可行解,则必有基可行解,...
  • 其实就是一些变量的添加和符号的改变 线性规划中的规律 一维、二维、三维规划中: 可行集中任意两点的连线都在可行集内:凸集 最优都不在两个不同点的连线上:顶点 所有顶点的个数有限:有限集 线性规划的可行集是...
  • 一、线性规划示例、 二、转化成标准形式、 三、初始基可行解、 四、列出单纯形表、 五、计算检验数、 六、选择入基变量与出基变量、 七、第一次迭代 : 列出单纯形表、
  • 基解,基可行解,可行基 所以需要注意的是 基本解不一定是可行解,非负的基解才是可行解 奇异矩阵和非奇异矩阵 :有时候我们还会听到奇异矩阵和非奇异矩阵这两个概念,首先明确肯定要明确的是, 奇异矩阵和非...
  • 目录 1. 基本可行解 ...可行域的极点 对应 基可行解。 2.3 单纯形法例子 无界解 : Z > C 有约束不取等。 如果<,说明非基变量检验数小于0,有最优解。 如果非基变量检验数=0,有多个...
  • 单纯形法原理 | 单纯形法流程 | 单纯形表 | 计算检验数 | 最优判定 | 入变量 | 出变量 | 方程组同变换
  • 【运筹学】线性规划问题的解 ( 可行解 | 可行域 | 最优解 | 秩的概念 | 极大线性无关组 | 向量秩 | 矩阵秩 | 基 | 基变量 | 非基变量 | 基解 | 基可行解 | 可行基 ) 1.3 线性规划求解步骤 1 . 线性...
  • https://www.zhihu.com/question/376709897
  • 包含有最小元素法、Vogel法、西北角法的MATLAB实现。包含补零函数,内有pdf文件介绍

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,395
精华内容 2,558
关键字:

基可行解