精华内容
下载资源
问答
  • 一、单纯形法总结、 二、人工变量引入、 三、人工变量法案例、 四、线性规划标准型、 五、人工变量法、 六、人工变量法解分析、





    一、单纯形法总结



    求解线性规划 , 使用的是单纯形法 ;


    迭代转化 : 其将 在无穷多个可行解中迭代 , 转化为了 在有限个基可行解中进行迭代 ;

    单纯形法理论基础 : 将迭代范围由大集合转为小集合 , 不会漏掉最优解 , 根据线性规划定理 , 只要有最优解 , 该最优解一定是基可行解 ;



    单纯形法求解流程 :


    • ① 找到单位阵
    • ② 最优准则 : 计算检验数
    • ③ 迭代准则 : 先根据检验数找到入基变量 , 再根据常量除以入基变量大于 0 0 0 系数 , 选择小的值对应的基变量作为出基变量 ;
    • ④ 中心元 : 找到 入基变量 与 出基变量 交叉点元素 , 这是中心元 , 中心元转为 1 1 1 , 同一列另一个系数转为 0 0 0 ; 然后继续根据最优准则计算检验数 , 转到步骤 ② ;




    二、人工变量法引入



    上述单纯形的解法是 从单位阵出发的 , 所有的前提是有单位阵 , 线性规划中可能不存在单位阵 , 如果线性规划转化为单位阵时 , 没有单位阵 , 就需要使用 人工变量法 , 构造一个单位阵 ;


    下面通过一个案例来介绍人工变量法的使用 ;





    三、人工变量法案例



    求解线性规划 : 使用人工变量法求解线性规划 ;

    m a x Z = 3 x 1 + 2 x 2 − x 3 s . t { − 4 x 1 + 3 x 2 + x 3 ≥ 4 x 1 − x 2 + 2 x 3 ≤ 10 − 2 x 1 + 2 x 2 − x 3 = − 1 x j ≥ 0 ( j = 1 , 2 , 3 ) \begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 \\ \\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 \geq 4 \\\\ x_1 - x_2 + 2x_3 \leq 10 \\\\ -2x_1 + 2x_2 - x_3 = -1 \\\\ x_j \geq 0 & (j = 1 , 2 , 3 ) \end{cases}\end{array} maxZ=3x1+2x2x3s.t4x1+3x2+x34x1x2+2x3102x1+2x2x3=1xj0(j=1,2,3)





    四、线性规划标准型



    参考 【运筹学】线性规划数学模型标准形式 ( 标准形式 | 目标函数转化 | 决策变量转化 | 约束方程转化 | 固定转化顺序 | 标准形式转化实例 ) 线性规划 普通形式 -> 标准形式 转化顺序说明 博客 , 先处理变量约束 , 再将不等式转为等式 , 最后更新目标函数 ;


    1 . 处理约束变量 : 所有的约束变量都大于等于 0 0 0 , 这里无需处理 ;



    2 . 将不等式转为等式 :


    ① 方程 1 1 1 转为等式 : 方程 1 1 1 是大于等于不等式 , 需要在方程左侧减去剩余变量 x 4 x_4 x4 ;

    − 4 x 1 + 3 x 2 + x 3 − x 4 = 4 -4 x_1 + 3x_2 + x_3 - x_4 = 4 4x1+3x2+x3x4=4


    ② 方程 2 2 2 转为等式 : 方程 2 2 2 是小于等于不等式 , 需要在方程左侧加上松弛变量 x 5 x_5 x5 ;

    x 1 − x 2 + 2 x 3 + x 5 = 10 x_1 - x_2 + 2x_3 + x_5 = 10 x1x2+2x3+x5=10


    3 . 方程 3 3 3 转为符合要求的等式 : 方程 3 3 3 是等式 , 但是其右侧的常数小于 0 0 0 , 这里需要在等式两边都乘以 − 1 -1 1 , 使右侧的常数大于等于 0 0 0 ;

    2 x 1 − 2 x 2 + x 3 = 1 2x_1 - 2x_2 + x_3 = 1 2x12x2+x3=1



    4 . 处理目标函数取最大值 : 目标函数就是取最大值 , 无需处理 ;



    5 . 最终的标准形结果是 :

    m a x Z = 3 x 1 + 2 x 2 − x 3 s . t { − 4 x 1 + 3 x 2 + x 3 − x 4 = 4 x 1 − x 2 + 2 x 3 + x 5 = 10 2 x 1 − 2 x 2 + x 3 = 1 x j ≥ 0 ( j = 1 , 2 , 3 , 4 , 5 ) \begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 \\ \\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 = 4 \\\\ x_1 - x_2 + 2x_3 + x_5 = 10 \\\\ 2x_1 - 2x_2 + x_3 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 ) \end{cases}\end{array} maxZ=3x1+2x2x3s.t4x1+3x2+x3x4=4x1x2+2x3+x5=102x12x2+x3=1xj0(j=1,2,3,4,5)





    五、人工变量法



    将上述转化完毕的标准型的系数矩阵补全 :

    m a x Z = 3 x 1 + 2 x 2 − x 3 + 0 x 4 + 0 x 5 s . t { − 4 x 1 + 3 x 2 + x 3 − x 4 + 0 x 5 = 4 x 1 − x 2 + 2 x 3 + 0 x 4 + x 5 = 10 2 x 1 − 2 x 2 + x 3 + 0 x 4 + 0 x 5 = 1 x j ≥ 0 ( j = 1 , 2 , 3 , 4 , 5 ) \begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 \\ \\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 = 4 \\\\ x_1 - x_2 + 2x_3 + 0x_4 + x_5 = 10 \\\\ 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 ) \end{cases}\end{array} maxZ=3x1+2x2x3+0x4+0x5s.t4x1+3x2+x3x4+0x5=4x1x2+2x3+0x4+x5=102x12x2+x3+0x4+0x5=1xj0(j=1,2,3,4,5)


    上述约束方程中没有单位阵 , 无法找到初始基可行解 , 创建初始的单纯形表 ;


    上述线性规划中 , 需要找到 3 × 3 3 \times 3 3×3 的单位阵 ( 1 0 0 0 1 0 0 0 1 ) \begin{pmatrix} \quad 1 \quad 0 \quad 0 \quad \\ \quad 0 \quad 1 \quad 0 \quad \\ \quad 0 \quad 0 \quad 1 \quad \\ \end{pmatrix} 100010001 , 目前只有 x 5 x_5 x5 的系数列向量是 ( 0 1 0 ) \begin{pmatrix} \quad 0 \quad \\ \quad 1 \quad \\ \quad 0 \quad \\ \end{pmatrix} 010 , 这里需要进行如下操作 ;



    人工变量法 : 目的是人为制造单位阵 , 添加 2 2 2 个或 3 3 3 个人工变量 ;

    • 方程 1 1 1 构造变量 x 6 x_6 x6 : 该变量只出现在第 1 1 1 个方程中 ;

    − 4 x 1 + 3 x 2 + x 3 − x 4 + 0 x 5 + x 6 = 4 -4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 = 4 4x1+3x2+x3x4+0x5+x6=4

    • 方程 2 2 2 构造变量 x 7 x7 x7 : 该变量只出现在第 3 3 3 个方程中 ;

    2 x 1 − 2 x 2 + x 3 + 0 x 4 + 0 x 5 + x 7 = 1 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + x_7 = 1 2x12x2+x3+0x4+0x5+x7=1


    添加了人工变量后 , 变量就变成了 7 7 7 ( x 1 x 2 x 3 x 4 x 5 x 6 x 7 ) \begin{pmatrix} \quad x_1 \quad \\ \quad x_2 \quad \\ \quad x_3 \quad \\ \quad x_4 \quad \\ \quad x_5 \quad \\ \quad x_6 \quad \\ \quad x_7 \quad \\ \end{pmatrix} x1x2x3x4x5x6x7 , 原来的变量只有 5 5 5 ( x 1 x 2 x 3 x 4 x 5 ) \begin{pmatrix} \quad x_1 \quad \\ \quad x_2 \quad \\ \quad x_3 \quad \\ \quad x_4 \quad \\ \quad x_5 \quad \\ \end{pmatrix} x1x2x3x4x5 ; 如果解出该线性规划的 7 7 7 个解 , 去掉后面的 x 6 , x 7 x_6 , x_7 x6,x7 之后 , 该最优解不一定满足 5 5 5 个变量的线性规划 ;


    如果解出的 7 7 7 个解中 , x 6 , x 7 x_6 , x_7 x6,x7 都等于 0 0 0 , 此时该最优解的前 5 5 5 个变量 , 满足最初的线性规划解 ;


    引入大 M M M : 在目标函数中 , x 6 , x 7 x_6 , x_7 x6,x7 加上系数 − M -M M , M M M 是一个抽象数值 , 没有具体的值 , 其大于给定的任何一个值 ;

    m a x Z = 3 x 1 + 2 x 2 − x 3 + 0 x 4 + 0 x 5 − M x 6 − M x 7 max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 - M x_6 - Mx_7 maxZ=3x1+2x2x3+0x4+0x5Mx6Mx7


    引入大 M M M 后最优解 x 6 , x 7 x_6 , x_7 x6,x7 必须为 0 0 0 : 如果上述 x 6 , x 7 x_6 , x_7 x6,x7 只要大于 0 0 0 , 即使很小 , 但是乘以一个很大的负数值 − M -M M , 也会极大降低目标函数大小 , 因此只有两个变量取值为 0 0 0 时 , 才能使该解称为最优解 ;


    添加 2 2 2 个人工变量后 , 得到 人工变量单纯形法 线性规划模型 :

    m a x Z = 3 x 1 + 2 x 2 − x 3 + 0 x 4 + 0 x 5 − M x 6 − M x 7 s . t { − 4 x 1 + 3 x 2 + x 3 − x 4 + 0 x 5 + x 6 + 0 x 7 = 4 x 1 − x 2 + 2 x 3 + 0 x 4 + x 5 + 0 x 6 + 0 x 7 = 10 2 x 1 − 2 x 2 + x 3 + 0 x 4 + 0 x 5 + 0 x 6 + x 7 = 1 x j ≥ 0 ( j = 1 , 2 , 3 , 4 , 5 , 6 , 7 ) \begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 - M x_6 - Mx_7 \\\\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 + 0x_7 = 4 \\\\ x_1 - x_2 + 2x_3 + 0x_4 + x_5 + 0x_6 + 0x_7 = 10 \\\\ 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + 0x_6 + x_7 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 , 6 , 7 ) \end{cases}\end{array} maxZ=3x1+2x2x3+0x4+0x5Mx6Mx7s.t4x1+3x2+x3x4+0x5+x6+0x7=4x1x2+2x3+0x4+x5+0x6+0x7=102x12x2+x3+0x4+0x5+0x6+x7=1xj0(j=1,2,3,4,5,6,7)

    其中的 M M M 是一个很大的数值 , 没有具体的值 , 可以理解为正无穷 + ∞ +\infty + , 具体使用单纯形法进行计算时 , 将其理解为大于给出的任意一个确定的数值 ;





    六、人工变量法解分析



    原来的线性规划称为 L P LP LP , 添加了人工变量后的新线性规划为 L P A LPA LPA ;

    • 目标函数值有限 : 只要 L P LP LP 线性规划 , 可行域不为空集 ∅ \varnothing , 那么 L P A LPA LPA 线性规划一定能找到一个解 x x x , 使得 f ( x ) f(x) f(x) 是一个有限的数 , 该有限的数是与 负无穷 − ∞ -\infty 进行对比区分的 ;

    • 只要 L P LP LP 线性规划 有可行解 , 那么 L P A LPA LPA 线性规划中的目标函数一定不是 负无穷 − ∞ -\infty ;

    • 两个线性规划解的关系 : ( x 0 ) \begin{pmatrix} \quad x_0 \quad \\ \end{pmatrix} (x0) 是线性规划 L P LP LP 的可行解 , ( x 0 0 0 ) \begin{pmatrix} \quad x_0 \quad \\ \quad 0 \quad \\ \quad 0 \quad \\ \end{pmatrix} x000 一定是 L P A LPA LPA 线性规划的可行解 , 将该解代入目标函数 , 目标函数一定是一个有限的数 , 不是负无穷 − ∞ -\infty ;

    • L P A LPA LPA 线性规划 : 构造的 L P A LPA LPA 辅助线性规划问题有单位阵 , 选取该单位阵为可行解 , 得到基可行解 , 然后开始进行迭代 ;


    只要线性规划有初始基可行解 , 那么只可能有以下情况

    • ① 有最优解
    • ② 没有最优解

    最优解情况 : 在有最优解的前提下 ;

    • ① 如果人工变量等于 0 0 0 , 将人工变量去掉 , 剩余的解就是原来线性规划 L P LP LP 的最优解 ;
    • ② 如果有一个或多个人工变量大于 0 0 0 , 那么说明 原线性规划 L P LP LP 没有可行解 ;

    没有最优解的情况 :如果 L P A LPA LPA 线性规划没有最优解 , 那么 L P LP LP 线性规划也没有最优解 ;

    展开全文
  • 一、生成初始单纯形表、 二、计算非基变量检验数、 三、最优解判定、 四、选择入基变量、 五、选择出基变量、 六、更新单纯形表、



    上一篇博客 【运筹学】线性规划 人工变量法 ( 单纯形法总结 | 人工变量法引入 | 人工变量法原理分析 | 人工变量法案例 ) 中 , 介绍了人工变量法 , 主要用于解决线性规划标准形式中 , 初始系数矩阵中没有单位阵的情况 , 并给出一个案例 , 本篇博客中继续使用人工变量法解解上述线性规划问题 ;





    一、生成初始单纯形表



    添加 2 2 2 个人工变量后 , 得到 人工变量单纯形法 线性规划模型 :


    m a x Z = 3 x 1 + 2 x 2 − x 3 + 0 x 4 + 0 x 5 − M x 6 − M x 7 s . t { − 4 x 1 + 3 x 2 + x 3 − x 4 + 0 x 5 + x 6 + 0 x 7 = 4 x 1 − x 2 + 2 x 3 + 0 x 4 + x 5 + 0 x 6 + 0 x 7 = 10 2 x 1 − 2 x 2 + x 3 + 0 x 4 + 0 x 5 + 0 x 6 + x 7 = 1 x j ≥ 0 ( j = 1 , 2 , 3 , 4 , 5 , 6 , 7 ) \begin{array}{lcl} max Z = 3x_1 + 2x_2 - x_3 + 0x_4 + 0x_5 - M x_6 - Mx_7 \\\\ s.t\begin{cases} -4 x_1 + 3x_2 + x_3 - x_4 + 0x_5 + x_6 + 0x_7 = 4 \\\\ x_1 - x_2 + 2x_3 + 0x_4 + x_5 + 0x_6 + 0x_7 = 10 \\\\ 2x_1 - 2x_2 + x_3 + 0x_4 + 0x_5 + 0x_6 + x_7 = 1 \\\\ x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 , 6 , 7 ) \end{cases}\end{array} maxZ=3x1+2x2x3+0x4+0x5Mx6Mx7s.t4x1+3x2+x3x4+0x5+x6+0x7=4x1x2+2x3+0x4+x5+0x6+0x7=102x12x2+x3+0x4+0x5+0x6+x7=1xj0(j=1,2,3,4,5,6,7)


    其中的 M M M 是一个很大的数值 , 没有具体的值 , 可以理解为正无穷 + ∞ +\infty + , 具体使用单纯形法进行计算时 , 将其理解为大于给出的任意一个确定的数值 ;


    生成初始基可行表 :

    c j c_j cj c j c_j cj 3 3 3 2 2 2 − 1 -1 1 0 0 0 0 0 0 − M -M M − M -M M
    C B C_B CB 基变量系数 (目标函数) X B X_B XB 基变量常数 b b b x 1 x_1 x1 x 2 x_2 x2 x 3 x_3 x3 x 4 x_4 x4 x 5 x_5 x5 x 6 x_6 x6 x 7 x_7 x7 θ i \theta_i θi
    − M -M M ( 目标函数 x 6 x_6 x6 系数 c 6 c_6 c6 ) x 6 x_6 x6 4 4 4 − 4 -4 4 3 3 3 1 1 1 − 1 -1 1 0 0 0 1 1 1 0 0 0 ? ? ? ( θ 6 \theta_6 θ6)
    0 0 0 ( 目标函数 x 5 x_5 x5 系数 c 5 c_5 c5) x 5 x_5 x5 10 10 10 1 1 1 − 1 -1 1 2 2 2 0 0 0 1 1 1 0 0 0 0 0 0 ? ? ? ( θ 5 \theta_5 θ5 )
    − M -M M ( 目标函数 x 7 x_7 x7 系数 c 7 c_7 c7) x 7 x_7 x7 1 1 1 2 2 2 − 2 -2 2 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 ? ? ? ( θ 7 \theta_7 θ7 )
    σ j \sigma_j σj ( 检验数 ) ? ? ? ( σ 1 \sigma_1 σ1 ) ? ? ? ( σ 2 \sigma_2 σ2 ) ? ? ? ( σ 3 \sigma_3 σ3 ) ? ? ? ( σ 3 \sigma_3 σ3 ) 0 0 0 0 0 0 0 0 0

    注意基变量顺序 : 初始基可行解的单位阵的顺序 , 是 ( 1 0 0 0 1 0 0 0 1 ) \begin{pmatrix} \quad 1 \quad 0 \quad 0 \quad \\ \quad 0 \quad 1 \quad 0 \quad \\ \quad 0 \quad 0 \quad 1 \quad \\ \end{pmatrix} 100010001 , 对应的基变量顺序是 ( x 6 x 5 x 7 ) \begin{pmatrix} \quad x_6 \quad x_5 \quad x_7 \quad \\ \end{pmatrix} (x6x5x7)

    • x 6 x_6 x6 系数是 ( 1 0 0 ) \begin{pmatrix} \quad 1 \quad \\ \quad 0 \quad \\ \quad 0 \quad \\ \end{pmatrix} 100

    • x 5 x_5 x5 系数是 ( 0 1 0 ) \begin{pmatrix} \quad 0 \quad \\ \quad 1 \quad \\ \quad 0 \quad \\ \end{pmatrix} 010

    • x 7 x_7 x7 系数是 ( 0 0 1 ) \begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 1 \quad \\ \end{pmatrix} 001





    二、计算非基变量检验数



    1 . 计算非基变量 x 1 x_1 x1 的检验数 σ 1 \sigma_1 σ1 :


    σ 1 = 3 − ( − M 0 − M ) × ( − 4 1 2 ) = 3 − ( − M × − 4 + 0 × 1 + − M × 2 ) = 3 − 2 M \sigma_1 = 3 - \begin{pmatrix} \quad -M \quad 0 \quad -M \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad -4 \quad \\\\ \quad 1 \quad \\\\ \quad 2 \quad \end{pmatrix} = 3- ( -M \times -4 + 0 \times 1 + -M \times 2) =3 - 2M σ1=3(M0M)×412=3(M×4+0×1+M×2)=32M

    其中 M M M 是正无穷 + ∞ +\infin + , 3 − 2 M 3 - 2M 32M 是负数 ;

    在这里插入图片描述



    2 . 计算非基变量 x 2 x_2 x2 的检验数 σ 2 \sigma_2 σ2 :


    σ 2 = 2 − ( − M 0 − M ) × ( 3 − 1 − 2 ) = 2 − ( − M × 3 + 0 × − 1 + − M × − 2 ) = 2 + M \sigma_2 = 2 - \begin{pmatrix} \quad -M \quad 0 \quad -M \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad 3 \quad \\\\ \quad -1 \quad \\\\ \quad -2 \quad \end{pmatrix} = 2- ( -M \times 3 + 0 \times -1 + -M \times -2) = 2 + M σ2=2(M0M)×312=2(M×3+0×1+M×2)=2+M

    其中 M M M 是正无穷 + ∞ +\infin + , 2 + M 2 + M 2+M 是正数 ;

    在这里插入图片描述



    3 . 计算非基变量 x 3 x_3 x3 的检验数 σ 3 \sigma_3 σ3 :


    σ 3 = − 1 − ( − M 0 − M ) × ( 1 2 1 ) = − 1 − ( − M × 1 + 0 × 2 + − M × 1 ) = − 1 + 2 M \sigma_3 = -1 - \begin{pmatrix} \quad -M \quad 0 \quad -M \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad 1 \quad \\\\ \quad 2 \quad \\\\ \quad 1 \quad \end{pmatrix} = -1- ( -M \times 1 + 0 \times 2 + -M \times 1) =-1 + 2M σ3=1(M0M)×121=1(M×1+0×2+M×1)=1+2M

    其中 M M M 是正无穷 + ∞ +\infin + , − 1 + 2 M -1 + 2M 1+2M 是正数 ;

    在这里插入图片描述



    4 . 计算非基变量 x 4 x_4 x4 的检验数 σ 4 \sigma_4 σ4 :


    σ 4 = 0 − ( − M 0 − M ) × ( − 1 0 0 ) = 0 − ( − M × − 1 + 0 × 0 + − M × 0 ) = − M \sigma_4 = 0 - \begin{pmatrix} \quad -M \quad 0 \quad -M \quad \\ \end{pmatrix} \times \begin{pmatrix} \quad -1 \quad \\\\ \quad 0 \quad \\\\ \quad 0 \quad \end{pmatrix} = 0- ( -M \times -1 + 0 \times 0 + -M \times 0) =-M σ4=0(M0M)×100=0(M×1+0×0+M×0)=M

    其中 M M M 是正无穷 + ∞ +\infin + , − M -M M 是负数 ;

    在这里插入图片描述





    三、最优解判定



    根据上述四个检验数 { σ 1 = 3 − 2 M ( 负 数 ) σ 2 = 2 + M ( 正 数 ) σ 3 = − 1 + 2 M ( 正 数 ) σ 4 = − M ( 负 数 ) \begin{cases} \sigma_1 = 3 - 2M \quad ( 负数 )\\\\ \sigma_2= 2 + M \quad ( 正数 )\\\\ \sigma_3= -1 + 2M \quad ( 正数 ) \\\\ \sigma_4 = -M \quad ( 负数 ) \end{cases} σ1=32M()σ2=2+M()σ3=1+2M()σ4=M() 的值 , 其中 σ 2 , σ 3 \sigma_2 , \sigma_3 σ2,σ3 检验数大于 0 0 0 , 该基可行解不是最优解 ;

    只有当检验数都小于等于 0 0 0 时 , 该基可行解才是最优解 ;





    四、选择入基变量



    根据上述四个检验数 { σ 1 = 3 − 2 M σ 2 = 2 + M σ 3 = − 1 + 2 M σ 4 = − M \begin{cases} \sigma_1 = 3 - 2M\\\\ \sigma_2= 2 + M\\\\ \sigma_3= -1 + 2M \\\\ \sigma_4 = -M \end{cases} σ1=32Mσ2=2+Mσ3=1+2Mσ4=M 的值 , 选择检验数最大的非基变量作为入基变量 , σ 3 = − 1 + 2 M \sigma_3= -1 + 2M σ3=1+2M 最大 , 这里选择 x 3 x_3 x3 ;





    五、选择出基变量



    出基变量选择 : 常数列 b = ( 4 10 1 ) b =\begin{pmatrix} \quad 4 \quad \\ \quad 10 \quad \\ \quad 1 \quad \\ \end{pmatrix} b=4101 , 分别除以除以入基变量 x 3 x_3 x3 大于 0 0 0 的系数列 ( 1 2 1 ) \begin{pmatrix} \quad 1 \quad \\\\ \quad 2 \quad \\\\ \quad 1 \quad \end{pmatrix} 121 , 计算过程如下 ( 4 1 10 2 1 1 ) \begin{pmatrix} \quad \cfrac{4}{1} \quad \\\\ \quad \cfrac{10}{2} \quad \\\\ \quad \cfrac{1}{ 1} \quad \end{pmatrix} 1421011 , 得出结果是 ( 4 5 1 ) \begin{pmatrix} \quad 4 \quad \\\\ \quad 5 \quad \\\\ \quad 1 \quad \end{pmatrix} 451 , 如果系数小于等于 0 0 0 , 该值就是无效值 , 默认为无穷大 , 不进行比较 , 选择 1 1 1 对应的基变量作为出基变量 , 查看该最小值对应的变量是 x 7 x_7 x7 , 选择该 x 7 x_7 x7 变量作为出基变量 ;

    在这里插入图片描述





    六、更新单纯形表



    c j c_j cj c j c_j cj 3 3 3 2 2 2 − 1 -1 1 0 0 0 0 0 0 − M -M M − M -M M
    C B C_B CB 基变量系数 (目标函数) X B X_B XB 基变量常数 b b b x 1 x_1 x1 x 2 x_2 x2 x 3 x_3 x3 x 4 x_4 x4 x 5 x_5 x5 x 6 x_6 x6 x 7 x_7 x7 θ i \theta_i θi
    − M -M M ( 目标函数 x 6 x_6 x6 系数 c 6 c_6 c6 ) x 6 x_6 x6 4 4 4 − 4 -4 4 3 3 3 1 1 1 − 1 -1 1 0 0 0 1 1 1 0 0 0 4 4 4 ( θ 6 \theta_6 θ6)
    0 0 0 ( 目标函数 x 5 x_5 x5 系数 c 5 c_5 c5) x 5 x_5 x5 10 10 10 1 1 1 − 1 -1 1 2 2 2 0 0 0 1 1 1 0 0 0 0 0 0 5 5 5 ( θ 5 \theta_5 θ5 )
    − M -M M ( 目标函数 x 7 x_7 x7 系数 c 7 c_7 c7) x 7 x_7 x7 1 1 1 2 2 2 − 2 -2 2 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 ( θ 7 \theta_7 θ7 )
    σ j \sigma_j σj ( 检验数 ) 3 − 2 M 3-2M 32M ( σ 1 \sigma_1 σ1 ) 2 + M 2+M 2+M ( σ 2 \sigma_2 σ2 ) − 1 + 2 M -1 + 2M 1+2M ( σ 3 \sigma_3 σ3 ) − M -M M ( σ 3 \sigma_3 σ3 ) 0 0 0 0 0 0 0 0 0
    展开全文
  • 十一、 人工变量之 “大M” 法

    千次阅读 2021-03-04 12:31:14
    因为引入了新的变量,使得原始约束变化,因此需要对... 结论:再使用“大M”法时,人工变量一旦出基,就一定不会再进基,因此可以不用再计算检测数(只有人工变量有这个性质、松弛变量和非基变量不适用) ...

       因为引入了新的变量,使得原始约束变化,因此需要对目标函数进行改变

     

    大 M 法

            

                         M: 罚因子,是一个很大很大的正实数  \rightarrow \infty

                             

             结论:再使用“大M”法时,人工变量一旦出基,就一定不会再进基,因此可以不用再计算检测数(只有人工变量有这个性质、松弛变量和非基变量不适用)

                  

                            

                              

     

    结论

    (1)若终表中,基中人工变量,由最优解  x^*

    (2)若终表中,基中人工变量,原无解

     

                    因为原先价值系数中,有一列单位列,因此只需引入两个人工变量

           

             

              

     

     

    展开全文
  • 决策变量非负化 约束条件等式化 目标函数最大化 然后我们要寻找一个初始可行解,但是有些时候完成标准化的模型并不能照当初始解。如: max⁡Z=x1+x2{2x1+x2≤6x1+2x2≥8x2=2 \begin{array}{c} \max Z=x_{1}+x_{2} \...

    问题标准化

    将一般形式的线性规划模型变为标准形式的三个步骤:

    1. 决策变量非负化
    2. 约束条件等式化
    3. 目标函数最大化

    然后我们要寻找一个初始可行解,但是有些时候完成标准化的模型并不能照当初始解。如:
    max ⁡ Z = x 1 + x 2 { 2 x 1 + x 2 ≤ 6 x 1 + 2 x 2 ≥ 8 x 2 = 2 \begin{array}{c} \max Z=x_{1}+x_{2} \\ \left\{\begin{array}{r} 2x_{1}+ x_{2} \leq 6 \\ x_{1}+2 x_{2} \geq 8 \\ x_{2} = 2 \end{array}\right. \end{array} maxZ=x1+x22x1+x26x1+2x28x2=2
    变换:
    max ⁡ Z = x 1 + x 2 { 2 x 1 + x 2 + x 3 = 6 x 1 + 2 x 2 − x 4 = 8 x 2 = 2 \begin{array}{c} \max Z=x_{1}+x_{2} \\ \left\{\begin{array}{r} 2x_{1}+ x_{2} + x_{3}= 6 \\ x_{1}+2 x_{2} -x_{4}= 8 \\ x_{2} = 2 \end{array}\right. \end{array} maxZ=x1+x22x1+x2+x3=6x1+2x2x4=8x2=2
    添加的 x 3 , x 4 x_{3},x_{4} x3,x4分别为松弛变量和剩余变量,但是此时无法找到一个合适的初始解,于是我们引入人工变量的概念:在已经是等式的条件下,为了凑得单位子矩阵人为加入的新变量,如果其值不为0,说明相应的条件没有被满足,故如果是可行解必须保证所有人工变量为0。添加的方法:
    4. 如果原先是 ≤ \leq ,左边加上非负松弛变量。
    5. 如果原先是 ≥ \geq ,左边减去非负剩余变量,再加上非负人工变量。
    6. 如果原先是 = = =,左边加上非负人工变量。
    7. 令在目标函数中的松弛和剩余变量系数为0,人工变量为 − M -M M
    max ⁡ Z = x 1 + x 2 − M 1 x 5 − M 2 x 6 { 2 x 1 + x 2 + x 3 = 6 x 1 + 2 x 2 − x 4 + x 5 = 8 x 2 + x 6 = 2 x i ≥ 0 ( i = 1 , 2...6 ) \begin{array}{c} \max Z=x_{1}+x_{2}-M_1x_{5}-M_2x_{6} \\ \left\{\begin{array}{r} 2x_{1}+ x_{2} + x_{3}= 6 \\ x_{1}+2 x_{2} -x_{4}+x_{5}= 8 \\ x_{2} +x_{6}= 2 \\ x_i \geq 0(i=1,2...6) \end{array}\right. \end{array} maxZ=x1+x2M1x5M2x62x1+x2+x3=6x1+2x2x4+x5=8x2+x6=2xi0(i=1,2...6)
    M M M意为很大的整数。这就是所谓大M法。

    展开全文
  • 十二、 人工变量之“两阶段法”

    千次阅读 2021-03-04 14:18:06
    (基变量和非基变量系数为“0”,对人工变量进行累加) 第一阶段: 出现结果时,需要讨论: (1)= 0 ,原问题有解 (2), 原问题无解 第二阶段: 应讨论不同情况再开始运算,讨论:首先,切入点...
  • 文章目录人工变量法1. 大M法1.1. 题目1.2. 求解过程1.3. 添加人工变量2. 两阶段法3. 参考 人工变量法 在一些模型中并不包含单位矩阵,为了得到一组基向量和初始可行解,在约束条件的等式左端添加一组虚拟变量,得到...
  • 对单纯形法与对偶单纯形法及其思想结合运用,针对约束条件全为不等式的线性规划问题。...从线性规划间翘的任一个初始基出发,最多引入一个人工变量,即可求出问题的初始可行基,能有效地节约计算机的存储量和计算量。
  • 文章目录系列文章目录js引入方式变量数据类型 js引入方式 <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> <script type="text/javascript"&...
  • Python的虚拟变量及因子型变量构建

    千次阅读 2019-07-03 17:28:37
    虚拟变量(DummyVariables)又称虚设变量、名义变量或哑变量,用以反映质的属性的一个人工变量,是量化了的自变量,通常取值为0或1。引入哑变量可使线形回归模型变得更复杂,但对问题描述更简明,一个方程能达到两个...
  • 从本篇文章开始,作者正式开始研究Python深度学习、神经网络及人工智能相关知识。前一篇文章讲解了TensorFlow基础和一元直线预测的案例;本篇文章将详细介绍Session、变量、传入值和激励函数。主要结合作者之前的...
  •     虚拟变量 ( Dummy Variables) 又称虚设变量、名义变量或哑变量,用以反映质的属性的一个人工变量,是量化了的自变量,通常取值为0或1。引入哑变量可使线形回归模型变得更复杂,但对问题描述更简明,一个方程...
  • 导航 上一章:放款基本假定的模型 文章目录导航经典单方程计量 经济学模型:专门问题5.1虚拟变量模型一、虚拟变量...●根据因素的属性类型,构造只取 “0”或“1”的人工变量。通常称为虚拟变量,且记为D。 ●一般...
  • 松弛变量

    千次阅读 2020-02-28 13:35:19
    若所研究的线性规划模型的约束条件全是小于类型,那么可以通过标准化过程引入M个非负的松弛变量。松弛变量引入常常是为了便于在更大的可行域内求解。若为0,则收敛到原有状态,若大于零,则约束松弛。 对线性...
  • 变量详解

    千次阅读 2019-06-26 11:11:00
    变量(DummyVariable),也叫虚拟变量引入变量的目的是,将不能够定量处理的变量量化,在线性回归分析中引入变量的目的是,可以考察定性因素对因变量的影响, 它是人为虚设的变量,通常取值为0或1,来反映...
  • R语言与虚拟变量模型

    千次阅读 2020-04-16 10:05:19
    学习笔记 参考书籍:《计量经济学》-李子奈;《统计学:从数据到结论》-吴喜之; 虚拟变量模型 ...根据这些因素的属性类型,构造取’0’或’1’的人工变量。通常称为虚拟变量,记为D。 例如:反映性别的...
  • GMM之隐变量

    2020-03-14 01:15:44
    1. 为什么要引入变量Z? 如图所示,这是一个二维的高斯混合模型,图上为很多的样本,我们以红色的样本为例。我们想知道红色的样本属于哪一个高斯分布(C1还是C2),事实上,这个红色样本是既属于C1也属于C2的,只...
  • Pandas类别型变量因子化原因及方法总结 参考线性回归分析中的哑变量 哑变量(Dummy Variable),也叫虚拟变量,引入哑变量的目的是...根据这些因素的属性类型,构造只取“0”或“1”的人工变量,通常称为哑变量...
  • 类别型变量因子化原因及方法总结

    千次阅读 2018-03-22 11:58:45
    参考线性回归分析中的哑变量哑变量(Dummy Variable),也叫虚拟变量,引入哑变量的目的是,...根据这些因素的属性类型,构造只取“0”或“1”的人工变量,通常称为哑变量(dummy variables),记为D。举一个例子,...
  • 介绍了线性规划的相关概念和数学模型的建立, 以及解决该模型的两种方法: 图解法, 单纯形法的相关原理和过程. 对单纯形法还做了更深入的讨论, 在引入人工变量的前提下介绍了大M法和二阶段法.
  • 单纯形法是求解线性规划问题的...此法不须引入人工变量、不须处理约束方程,而直接对等式约束进行初等变换,得到一基本可行解,并在求解过程中剔除多余的约束,判断问题是否有解,同时将线性规划的约束方程化为典式。
  • 变量引入使得回归模型变得更复杂,但对问题描述更简明而且接近现实。 对于二分类变量,实际在模型中的取值只有“0”和“1”两个值,无论是以连续型还是哑变量变量纳入模型结果都是一样的,无非是参照水平是0...
  • 从本专栏开始,作者正式研究Python深度学习、神经网络及人工智能相关知识。前一篇文章详细讲解了无监督学习Autoencoder的原理知识,然后用MNIST手写数字案例进行对比实验及聚类分析。本篇文章将分享《人工智能狂潮》...
  • 本文将文献[1]中提出的对目标函数系数与...并将系数矩阵A的同时变化一起考虑在内,重点针对可行性和对偶可行性都不满足情况下,将文献[1]采取的引入人工变量及参数大M的传统方法,改用联合算法进行处理,简单方便多了。
  • AI技术押人工智能考试题

    千次阅读 2021-01-05 11:20:06
    选择、填空 人工智能的提出 ...利用状态变量和操作符号,表示系统问题或问题的有关知识的符号体系,状态空间是一个四元组,(S,O,S0S_0S0​,G) 遗传算法 生物学基础是生物进化理论 Holland 提出了遗传算法
  • 临时添加环境变量 用export, 加:PATH是将此变量添加在后面exportPATH=/home/john/bitbake−1.40/bin:PATH是将此变量添加在后面 export PATH=/home/john/bitbake-1.40/bin:PATH是将此变量添加在后面exportPATH=/home/...
  • 人工智能是什么?很多人都知道,但大多又都说不清楚。 事实上,人工智能已经存在于我们生活中很久了。 比如我们常常用到的邮箱,其中垃圾邮件过滤就是依靠人工智能; 比如每个智能手机都配备的指纹识别或...
  • 人工神经网络简介

    万次阅读 多人点赞 2015-12-12 14:20:37
    人工神经网络简介
  • 人工神经网络

    千次阅读 2018-08-20 00:12:00
    人工神经网络在本质上是由许多小的非线性函数组成的大的非线性函数,反映的是输入变量到输出变量间的复杂映射关系。 人工神经网络是一个并行和分布式的信息处理网络结构,该网络结构一般由许多个神经元组成,每个...
  • 最近偶尔在重温统计学,发现自己工作后用了各种高级的统计分析方法,各种统计模型...哑变量(Dummy Variable),也叫虚拟变量引入变量的目的是,将不能够定量处理的变量量化,如职业、性别对收入的影响,战争、...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 39,639
精华内容 15,855
关键字:

引入人工变量