精华内容
下载资源
问答
  • 一、唯一最优解、 二、无穷多最优解、 三、无界解、 四、无可行解、 五、线性规划迭代范围、 六、线性规划求解步骤





    一、唯一最优解



    使用单纯形法求解线性规划时 , 得到最优解时 , 所有的非基变量对应的检验数都小于 0 0 0 , 该线性规划有唯一最优解 ;





    二、无穷多最优解



    使用单纯形法求解线性规划时 , 得到最优解时 , 存在一个或多个非基变量对应的检验数等于 0 0 0 , 那么该线性规划有无穷多最优解 ;





    三、无界解



    使用单纯形法求解线性规划时 , 某个非基变量 x j x_j xj , 其对应的检验数 σ j ≤ 0 \sigma_j \leq 0 σj0 , 但是该非基变量的所有系数都是小于等于 0 0 0 的 , 此时该线性规划有 无界解 ;





    四、无可行解



    使用人工变量法 ( 大 M M M 单纯形法 ) 求解线性规划 , 得到最优解时 , 此时基变量中还存在人工变量 , 人工添加的变量没有迭代出去 , 这种情况下 , 该线性规划没有可行解 ;





    五、线性规划迭代范围



    线性规划迭代范围 :

    • 无限范围 : 首先迭代的范围是 无穷多元素的 可行解 的集合 ;

    • 有限范围 : 缩小该迭代范围为 有限个元素的 基可行解 集合 ;





    六、线性规划求解步骤



    线性规划求解步骤 :

    • 初始 : 找到初始基可行解 ;

    • 最优 : 最优解判定准则 ;

    • 迭代 : 如果不是最优解 , 如何进行下一次迭代 ;

    展开全文
  • 大家都知道,线性规划问题的解有三种情况:(1)惟 一最优解;(2)无穷多最优解;(3)无最优解。至于(1)和 (3)此文不做细谈,这里针对无穷多最优解作一些浅 析。
  • 本文构建SimplexMax函数,通过构建单纯型表和循环迭代,求解线性规划问题的最优解 clc;clear; %% 设置变量,调用函数 % 题目参数 A = [0 5 1 0 0; 6 2 0 1 0; 1 1 0 0 1]; b = [15; 24; 5]; c = [2 1 0 0 0]; ind ...

    本文构建SimplexMax函数,通过构建单纯型表和循环迭代,求解线性规划问题的最优解

    clc;clear;
    %% 设置变量,调用函数
    % 题目参数
    A = [0 5 1 0 0;
         6 2 0 1 0;
         1 1 0 0 1];
    b = [15; 24; 5];
    c = [2 1 0 0 0];
    ind = [3 4 5]
    
    % 无界解
    % A = [-2 1 1 0;
    %      1 -1 0 1];
    % b = [4; 2];
    % c = [1 1 0 0];
    % ind = [3 4];
    
    
    % 无穷多最优解
    % A = [-1 -1.9 1 0 0 0;
    %      1 -1.9 0 1 0 0;
    %      1 1.9 0 0 1 0;
    %      -1 1.9 0 0 0 1];
    % b = [-3.8; 3.8; 10.2; 3.8];
    % c = [3 5.7 0 0 0 0];
    % ind = [3 4 5 6];
    
    [x, z, ST, ca] = SimplexMax(c, A, b, ind) % 调用下述构建的方法进行求解
    
    delete('mysimpleMax.xlsx'); % 删除原有的Excel表(如果存在的话)
    fprintf('正在将单纯形表写入Excel...\n');
    writematrix('C1','mysimpleMax.xlsx','Sheet',1,'Range','C1');
    writecell({'cB','xB', 'b'},'mysimpleMax.xlsx','Sheet',1,'Range','A2');
    [~,n] = size(A);
    X = strcat('x', string(1:n));
    writematrix(X,'mysimpleMax.xlsx','Sheet',1,'Range','D2');
    writematrix(c,'mysimpleMax.xlsx','Sheet',1,'Range','D1');
    writematrix(ST,'mysimpleMax.xlsx','Sheet',1,'Range','A3');
    fprintf('单纯性表写入完成\n');
    
    
    
    %% 构造解单纯形法函数
    function [x,z,ST,res_case] = SimplexMax(c,A,b,ind_B)
    % 单纯形法求解标准形线性规划问题: max cx s.t. Ax=b x>=0
    % 输入参数: c为目标函数系数, A为约束方程组系数矩阵, b为约束方程组常数项, ind_B为初始基变量索引
    % 输出参数: x最优解, z最优目标函数值, ST存储单纯形表数据,
    % res_case=0表示有最优解,res_case=1表示有无界解,res_case=2表示有无穷多解
    
    [m,n] = size(A);              % m约束条件个数, n决策变量数
    ind_N = setdiff(1:n, ind_B);  % 非基变量的索引
    ST = [];
    format rat
    % 循环求解
    iteration_round = 0; % 记录迭代次数
    while true
        x0 = zeros(n,1);
        x0(ind_B) = b;               % 初始基可行解
        cB = c(ind_B);               % 计算cB
        Sigma = zeros(1,n);          % 创建Sigma存储检验数并初始化为0
        Sigma(ind_N) = c(ind_N) - cB*A(:,ind_N);   % 计算并存入(非基变量)检验数
        [~, k] = max(Sigma);         % 选出最大检验数, 确定进基变量索引k (注:[a,b]=max(c)中,a为c中的最大值,b为c中最大值的index)
    %     fprintf('确定进基变量索引:%d\n',k)
        Theta = b ./ A(:,k);         % 计算θ(取A的k列,使b./(A的k列))
        
        Theta(Theta == 1/0) = NaN;
        Theta(Theta <= 0) = NaN;
    %     Theta(Theta<=0) = 10000;
    %     [~, q] = min(Theta);         % 选出最小θ
        [~, q] = min(Theta);         % 选出最小正数θ
        el = ind_B(q);               % 确定出基变量索引el, 主元为A(q,k)
    %     fprintf('确定出基变量索引:%d\n',el)
        vals = [cB',ind_B',b,A,Theta];  % 存储单纯形表
        vals = [vals; NaN, NaN, NaN, Sigma, NaN];   % 存储单纯性表Sigma列
        [~,vals_width] = size(vals);    % 创建一个与vals等宽的空矩阵
        vals = [vals; [1:vals_width]* NaN];  % 将该行添加到vals最后作为分隔
        ST = [ST; vals];    % 将上述构建的单纯性表vals添加到ST矩阵中
        if ~any(Sigma > 0)           % 若不存在任何Sigma>0,此基可行解为最优解
            fprintf('得到最优解');
            x = x0;
            z = c * x;
            res_case = 0;
            return
        end
        if all(A(:,k) <= 0)          %有无界解
            fprintf('有无界解');
            x = [];
            z = NaN;
            res_case = 1;
            break
        end
        if ~any(Sigma(ind_B)>0) && any(Sigma(ind_N)==0)     % 有无穷多最优解
            fprintf('有无穷多最优解')
            x = x0;
            z = c * x;
            res_case = 2;
            break
        end
        iteration_round = iteration_round + 1;
        fprintf('迭代第%d次\n',iteration_round)
        fprintf('确定进基变量索引:%d  出基变量索引: %d\n',k,el)
        % 换基
        ind_B(ind_B == el) = k;      %新的基变量索引
        ind_N = setdiff(1:n, ind_B); %非基变量索引(选取了ind_B和[1:n]的差集)
        % 更新A和b
        A(:,ind_N) = A(:,ind_B) \ A(:,ind_N);   % Q1 = inv(A(:,ind_B))  
        b = A(:,ind_B) \ b;     % b2 = inv(Q1) * b1
        A(:,ind_B) = eye(m,m);
    end
    end
    
    

    注意:本文采用的对单纯性表进行操作的方法并不是改进单纯型法,如果需要使用改进单纯型法进行求解请参考其他文章,并对下述操作进行改进

        % 换基
        ind_B(ind_B == el) = k;      %新的基变量索引
        ind_N = setdiff(1:n, ind_B); %非基变量索引(选取了ind_B和[1:n]的差集)
    
    
    展开全文
  • 图解法 处理 线性规划问题 ( 取最大值 有无穷多最优解 ) IV . 图解法 处理 线性规划问题 ( 取最小值 有一个最优解 ) V . 图解法 处理 线性规划问题 ( 无界解 ) VI . 图解法 处理 线性规划问题 ( 无可行解 ) VII . ...



    I . 图解法



    线性规划问题求解有两种方法 : ① 图解法 , ② 单纯形法 ;

    • 1. 图解法 : 适用于 两个 或 三个 变量 , 如果是两个变量 , 需要绘制直角坐标系 , 如果是 三个变量 , 需要绘制立体坐标系 ;
    • 2. 单纯形法 : 适用于任意变量 , 但必须将线性规划数学模型转为标准形式 ;

    本篇只讨论 两个变量的 图解法 , 在直角坐标系中进行绘图 ;

    图解法意义 :

    • 1. 局限性大 : 实际情况下 , 我们都使用单纯形法求线性规划的解 , 图解法只能处理 2 到 3 个变量的线性规划问题 ;
    • 2. 优势 : 图解法 简单 , 直观 , 便于初期对线性规划问题的 原理 和 几何意义 进行深入理解 ;


    II. 图解法 处理 线性规划问题 ( 取最大值 仅有一个最优解的情况 )



    使用图解法解下面的线性规划问题 :

    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

    在这里插入图片描述

    大于等于 不等式 需要取直线 右侧区域 ;
    小宇等于 不等式 需要取直线 左侧区域 ;

    四条直线 形成一个 四边形区域 ;

    绘制目标函数 , 使 2 x 1 + x 2 2x_1 + x_2 2x1+x2 与 上述 四边形相交 , 取最大值 , 经过计算 , 得到的结果最大为 20 20 20 , 此时 x 1 = 7.6 , x 2 = 2 x_1 = 7.6 , x_2 = 2 x1=7.6,x2=2



    III . 图解法 处理 线性规划问题 ( 取最大值 有无穷多最优解 )



    使用图解法解下面的线性规划问题 :

    m a x Z = 3 x 1 + 5.7 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 = 3x_1 + 5.7x_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=3x1+5.7x2s.t=x1+1.9x23.8x11.9x23.8x1+1.9x210.2x11.9x23.8x1,x20

    在这里插入图片描述

    大于等于 不等式 需要取直线 右侧区域 ;
    小宇等于 不等式 需要取直线 左侧区域 ;

    四条直线 形成一个 四边形区域 ;

    绘制目标函数 , 使 3 x 1 + 5.7 x 2 3x_1 + 5.7x_2 3x1+5.7x2 与 上述 四边形相交 , 取最大值 ,
    注意该函数 图像在 坐标系中 与 x 1 + 1.9 x 2 = 10.2 x_1 + 1.9x_2 = 10.2 x1+1.9x2=10.2 图像是平行的 , 即在可行区域内 , 整个线段上所有的点都是最优解 ;
    这个最优解的个数是无穷多个 ;
    经过计算 , 得到的结果最大为 34.2 34.2 34.2 , 此时 ( 3.8 , 4 ) 到 ( 7.6 , 2 ) ( 3.8 , 4 ) 到 ( 7.6 , 2 ) (3.8,4)(7.6,2) 线段之间的所有的点都是最优解



    IV . 图解法 处理 线性规划问题 ( 取最小值 有一个最优解 )



    使用图解法解下面的线性规划问题 :

    m i n Z = 5 x 1 + 4 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} min Z = 5x_1 + 4x_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} minZ=5x1+4x2s.t=x1+1.9x23.8x11.9x23.8x1+1.9x210.2x11.9x23.8x1,x20

    在这里插入图片描述

    大于等于 不等式 需要取直线 右侧区域 ;
    小宇等于 不等式 需要取直线 左侧区域 ;

    四条直线 形成一个 四边形区域 ;

    绘制目标函数 , 使 5 x 1 + 4 x 2 = 0 5x_1 + 4x_2=0 5x1+4x2=0 的 图像的 平行直线 与 上述 四边形相交 , 取最小值 , 经过计算 , 得到的结果最小值为 8 8 8 , 此时 x 1 = 0 , x 2 = 2 x_1 = 0 , x_2 = 2 x1=0,x2=2



    V . 图解法 处理 线性规划问题 ( 无界解 )



    使用图解法解下面的线性规划问题 :

    m a x Z = x 1 + 2 x 2 s . t = { x 1 + 3 x 2 ≥ 6 x 1 + x 2 ≥ 4 3 x 1 + x 2 ≥ 6 x 1 , x 2 ≥ 0 \begin{array}{lcl} max Z = x_1 + 2x_2\\\\ s.t = \begin{cases} x_1 + 3x_2 \geq 6\\\\ x_1 + x_2 \geq 4\\\\ 3x_1 + x_2 \geq 6\\\\ x_1 , x_2 \geq 0 \end{cases} \end{array} maxZ=x1+2x2s.t=x1+3x26x1+x243x1+x26x1,x20

    在这里插入图片描述

    大于等于 不等式 需要取直线 右侧区域 ;
    小宇等于 不等式 需要取直线 左侧区域 ;

    四条直线 无法 形成一个 闭合形区域 , 整体区域是开放的 , 最优解随着 x 1 , x 2 x_1 , x_2 x1,x2 变量增加而增大 , 没有任何限制
    此时该线性规划有无数个解 , 并且其最大值没有边界 ;
    这种情况下称为线性规划的解是无界解 , 同时也没有最优解 ;



    VI . 图解法 处理 线性规划问题 ( 无可行解 )



    使用图解法解下面的线性规划问题 :

    m a x Z = 3 x 1 + 4 x 2 s . t = { 2 x 1 + x 2 ≤ 40 x 1 + 1.5 x 2 ≤ 30 x 1 + x 2 ≥ 50 x 1 , x 2 ≥ 0 \begin{array}{lcl} max Z = 3x_1 + 4x_2\\\\ s.t = \begin{cases} 2x_1 + x_2 \leq 40\\\\ x_1 + 1.5x_2 \leq 30\\\\ x_1 + x_2 \geq 50\\\\ x_1 , x_2 \geq 0 \end{cases} \end{array} maxZ=3x1+4x2s.t=2x1+x240x1+1.5x230x1+x250x1,x20

    在这里插入图片描述

    大于等于 不等式 需要取直线 右侧区域 ;
    小宇等于 不等式 需要取直线 左侧区域 ;

    绘制目标函数 , 绘制 3 x 1 + 4 x 2 ≥ 0 3x_1 + 4x_2 \geq 0 3x1+4x20 的 图像 , 发现 该图像的 任何 平行直线 与 上述 四边形 都不相交 , 这种情况属于没有 可行解 , 同时也没有最优解



    VII . 线性规划解的情况



    线性规划有以下情况的解 : ① 有唯一最优解 , ② 有无穷多最优解 , ③ 无界解 , ④ 无可行解 ;

    使用图解法的关键 :

    • ① 可行域 : 根据 大于等于 或 小宇等于 不等式 , 判断可行区域 ;
    • ② 目标函数绘制 : 目标函数的移动方向 , 其变量必须都大于 0 , 先绘制 等于 0 的直线 , 然后都必须朝着大于 0 的方向移动 ;
    展开全文
  • 【运筹学】线性规划问题的解 ( 可行解 | 可行域 | 最优解 | 秩的概念 | 极大线性无关组 | 向量秩 | 矩阵秩 | 基 | 基变量 | 非基变量 | 基解 | 基可行解 | 可行基 ) 1.3 线性规划求解步骤 1 . 线性...



    1 . 前置概念





    1.1 线性规划向量形式



    线性规划 向量形式 : 其中 矩阵 C C C , 矩阵 X X X , 矩阵 b b b 与上面的矩阵形式内容一致 , 本公式之比上个公式多了一个 向量 P j P_j Pj ;

    m a x Z = C X s . t { ∑ j = 1 n P j x j = b x j ≥ 0 j = 1 , 2 , ⋯   , n \begin{array}{lcl}max Z = CX \\ \\ s.t \begin{cases} \sum_{j = 1}^{n} P_j x_j = b \\ \\ x_j \geq 0 & j=1,2,\cdots,n \end{cases}\end{array} maxZ=CXs.tj=1nPjxj=bxj0j=1,2,,n

    其中

    ∑ j = 1 n P j x j = b \sum_{j = 1}^{n} P_j x_j = b j=1nPjxj=b

    展开后是 :

    P 1 x 1 + P 2 x 2 + ⋯ + P n x n = b P_1x_1 + P_2x_2 + \cdots + P_nx_n = b P1x1+P2x2++Pnxn=b

    其中的 P j P_j Pj 为 :

    P j = [ a 1 j a 2 j ⋮ a m j ] P_j=\begin{bmatrix}\\\\ a_{1j}\\\\ a_{2j}\\\\ \vdots\\\\ a_{mj}\\\\ \end{bmatrix} Pj=a1ja2jamj

    举例 对应的 P 1 P_1 P1 就是

    P 1 = [ a 11 a 21 ⋮ a m 1 ] P_1=\begin{bmatrix}\\\\ a_{11}\\\\ a_{21}\\\\ \vdots\\\\ a_{m1}\\\\ \end{bmatrix} P1=a11a21am1

    对应的 P n P_n Pn 就是

    P n = [ a 1 n a 2 n ⋮ a m n ] P_n=\begin{bmatrix}\\\\ a_{1n}\\\\ a_{2n}\\\\ \vdots\\\\ a_{mn}\\\\ \end{bmatrix} Pn=a1na2namn



    1.2 可行基概念



    1 . 基的概念

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

    基 :

    • ① 矩阵秩 : A A A 为上述 m × n m \times n m×n 阶系数矩阵 ( m < n ) ( m < n ) (m<n) , 其秩 为 m m m ; ( 该矩阵的秩的最大取值是 m i n ( m , n ) min(m , n) min(m,n) )
    • ② 满秩矩阵 : 矩阵 B B B 是矩阵 A A A m m m 阶满秩子矩阵 , 其中 ∣ B ∣ ≠ 0 |B| \not=0 B=0 ,
      B = [ a 11 ⋯ a 1 m ⋮ ⋮ ⋮ a m 1 ⋯ a m m ] = ( p 1 ⋯ p m ) B= \begin{bmatrix} & a_{11} & \cdots & a_{1m} \\ \\ &\vdots &\vdots &\vdots \\ \\ & a_{m1} & \cdots & a_{mm} \end{bmatrix} = ( p_1 \cdots p_m ) B=a11am1a1mamm=(p1pm)
    • ③ 基引入 : 则称 B B B 是线性规划问题的 一个基 ;

    2 . 基解概念

    基解 :

    • ① 确定基 : 确定一个基 B B B , 该矩阵是系数矩阵 A A A 的满秩子矩阵 , 即一个 m × m m \times m m×m 阶矩阵 ;
    • ② 处理非基变量 : 将非基变量 设置成 0 0 0 ;
    • ③ 解出基解 : 将 基 代入约束方程 , 解出对应的变量值 , 即基解 ;
    • ④ 基解个数 : 基解中变量取值 非 0 0 0 个数 , 小于等于 约束方程个数 m m m , 基解的总数 不超过 C n m C_n^m Cnm

    3 . 可行基概念

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

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


    详细的概念参考 : 【运筹学】线性规划问题的解 ( 可行解 | 可行域 | 最优解 | 秩的概念 | 极大线性无关组 | 向量秩 | 矩阵秩 | 基 | 基变量 | 非基变量 | 基解 | 基可行解 | 可行基 )



    1.3 线性规划求解步骤



    1 . 线性规划向量形式为 :

    m a x Z = C X s . t { ∑ j = 1 n P j x j = b x j ≥ 0 j = 1 , 2 , ⋯   , n \begin{array}{lcl}max Z = CX \\ \\ s.t \begin{cases} \sum_{j = 1}^{n} P_j x_j = b \\ \\ x_j \geq 0 & j=1,2,\cdots,n \end{cases}\end{array} maxZ=CXs.tj=1nPjxj=bxj0j=1,2,,n


    2 . 找可行基 : 使用单纯形法求解最优解的第一个步骤 , 就是找到一个可行基 ;


    3 . 构造初始可行基方法 : 已知一个线性规划问题的标准数学模型 , 构造初始可行基的三种方法 :

    • ① 观察 : 通过观察 , 直接从系数矩阵中发现一个可行基 , 即 m m m 阶方阵 ∣ B ∣ ≠ 0 |B| \not= 0 B=0 ;
    • ② 松弛变量法 : 如果约束方程是 ≤ \leq 约束 , 那么加入松弛变量 , 这些松弛变量的每个系数的列向量都是单位向量 ;
    • ③ 人工变量法 : 如果约束方程式 ≥ \geq 约束 , 那么需要加入人工变量 ;

    线性规划问题求解 , 第一步就是根据上面三种方法 , 构造出初始的可行基 ;


    4 . 求线性规划最优解流程 : 先构造初始可行基 , 然后解出该解 , 判定是否是基可行解 , 如果是基可行解 , 那么判断该解是否是最优解 , 如是 , 那么该解就是最优解 , 如果不是 , 那么继续迭代 ;


    5 . 这里就两个问题 : ① 如何判定该解是否是最优解 , ② 如何进行迭代 ;



    2 . 构造初始可行基





    2.1 构造初始可行基 并 解出基解



    1 . 前提条件 : 先做一个假设 , 假设由一个线性规划问题 , 有 m m m 个约束方程 , 有 n n n 个决策变量 , x 1 , x 2 , ⋯   , x m x_1 , x_2 , \cdots , x_m x1,x2,,xm ; 这 m m m 个约束方程都是 ≤ \leq 约束 ;


    2 . 构造可行基方法 ( 添加松弛变量 ) : 给所有的约束方程 , 添加一个松弛变量 , 即需要添加 m m m 个松弛变量 ;

    线性规划的约束方程为 : 该约束方程有 n − m n-m nm 个决策变量 , 有 m m m 个约束不等式 ;

    s . t { a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n − m ≤ b 1 a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n − m ≤ b 2 ⋯ ⋯ ⋯ a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n − m ≤ b m x 1 , x 2 , ⋯   , x n − m ≥ 0 s.t \begin{cases} a_{11} x_1 + a_{12} x_2 + \cdots + a_{1n}x_{n-m} \leq b_1 \\ \\ a_{21} x_1 + a_{22} x_2 + \cdots + a_{2n}x_{n-m} \leq b_2 \\ \\ \cdots\cdots\cdots \\ \\ a_{m1} x_1 + a_{m2} x_2 + \cdots + a_{mn}x_{n-m} \leq b_m \\ \\ x_1, x_2 , \cdots , x_{n-m} \geq 0 \end{cases} s.ta11x1+a12x2++a1nxnmb1a21x1+a22x2++a2nxnmb2am1x1+am2x2++amnxnmbmx1,x2,,xnm0

    由于是 ≤ \leq 约束 , 添加松弛变量 , 有 m m m 个不等式 , 需要添加 m m m 个松弛变量 ; 添加松弛变量后 , ≤ \leq 不等式变成 等式 :

    s . t { x 1 + a 1 m + 1 x m + 1 + a 1 m + 2 x m + 2 + ⋯ + a 1 n x n = b 1 x 2 + a 2 m + 1 x m + 1 + a 2 m + 2 x m + 2 + ⋯ + a 2 n x n = b 2 ⋯ ⋯ ⋯ x m + a m m + 1 x m + 1 + a m m + 2 x m + 2 + ⋯ + a m n x n = b m x 1 , x 2 , ⋯   , x n ≥ 0 s.t \begin{cases} x_1 & & +a_{1 m+1} x_{m+1} + a_{1 m+2} x_{m+2} + \cdots + a_{1n}x_{n} = b_1 & \\ \\ & x_2 & + a_{2 m+1} x_{m+1} + a_{2 m+2} x_{m+2} + \cdots + a_{2n}x_{n} = b_2& \\ \\ \cdots\cdots\cdots \\ \\ & & x_m + a_{m m+1} x_{m+1} + a_{m m+2} x_{m+2} + \cdots + a_{mn}x_{n} = b_m& \\ \\ x_1, x_2 , \cdots , x_{n} \geq 0 \end{cases} s.tx1x1,x2,,xn0x2+a1m+1xm+1+a1m+2xm+2++a1nxn=b1+a2m+1xm+1+a2m+2xm+2++a2nxn=b2xm+amm+1xm+1+amm+2xm+2++amnxn=bm

    修改下标标号 : 上述式子将添加的松弛变量的下标修改成了 x 1 ⋯ x m x_1 \cdots x_m x1xm , 上述公式中下标的次序可以修改 ;


    3 . 构造初始可行基 : 该初始可行基 , 假设由 系数矩阵 前面的 m m m 个向量组成的 方阵 ; 该方阵是 x 1 ⋯ x m x_1 \cdots x_m x1xm 变量的系数矩阵 ;

    x 1 ⋯ x m x_1 \cdots x_m x1xm 就是基变量 ; 该基变量的系数 ( P 1 , ⋯   , P m ) (P_1 , \cdots , P_m) (P1,,Pm) 就是初始可行基 ;


    基是在 线性规划 约束方程组 的系数矩阵 中 的一个 m m m 阶方阵 , 其行列式不等于 0 0 0 , 行列式不等于 0 0 0 的方阵最基本最简单的就是单位阵 , 为了讨论方便 , 假设该初始可行基是单位阵 ; 即构造以下初始可行基 :

    B = [ P 1 P 2 ⋯ P m ] = [ 1 0 ⋯ 0 0 1 ⋯ 0 ⋮ ⋮ ⋮ 0 0 ⋯ 1 ] B=\begin{bmatrix}& P_1 & P_2 & \cdots & P_m & \end{bmatrix}= \begin{bmatrix} & 1 & 0 & \cdots & 0 & \\ & 0 & 1 & \cdots & 0 & \\ & \vdots & \vdots & & \vdots & \\ & 0 & 0 & \cdots & 1 & \\ \end{bmatrix} B=[P1P2Pm]=100010001

    初始可行基 : 上述的松弛变量的系数矩阵 , 刚好构成一个 m × m m \times m m×m 阶 的 单位阵 , 该单位阵是一个可行基 , 因为每个变量只添加一个松弛变量 , 其它 m − 1 m-1 m1 个不等式添加的对应松弛变量在本式子中 系数肯定是 0 0 0 ;

    如在第一个约束方程中 , 添加了 x 1 x_1 x1 , 那么在第一个约束方程中 , 对应的 x 2 ⋯ x m x_2 \cdots x_m x2xm m − 1 m-1 m1 个变量的系数肯定是 0 0 0 ;


    4 . 初始基可行解 : X ( 0 ) = ( x 1 0 , x 2 0 , ⋯   , x m 0 , 0 , ⋯   , 0 ) T X^{(0)}=( x_1^0 , x_2^0, \cdots , x_m^0 , 0 , \cdots , 0 )^T X(0)=(x10,x20,,xm0,0,,0)T , 其中右上角的 0 0 0 表示这是第 0 0 0 次迭代 , 是初始基可行解 ;



    3 . 基变换





    3.1 基变换 概念



    1 . 基变换 引入 : 如果初始可行基的基可行解不是最优解 , 那么就需要进行迭代 , 迭代 就是进行 基变换 ; 整个单纯形法的迭代就是不停的进行基变换 ;


    2 . 基变换 概念 : 如果两个基可行解相邻 , 两者可以变换 , 并且只能变换一个基变量 ;

    举例 : 基可行解对应的基变量是 x 1 , x 2 , x 3 , x 4 x_1 , x_2 , x_3 , x_4 x1,x2,x3,x4 , 将其中的某一个迭代出来 , 使用 x 5 x_5 x5 替换其中的某一个 ;



    3.2 线性规划 向量形式 按照基变量 非基变量 进行拆解



    1 . 解 基可行解 方法 : 令所有的非基变量等于 0 0 0 , 可以得到基解 , 因为是单位阵 , 因此基解的取值是各自右端的常数值 b 1 ⋯ b m b_1 \cdots b_m b1bm ; 即 x 1 = b 1 , x 2 = b 2 , ⋯   , x m = b m x_1 = b_1 , x_2 = b_2 , \cdots , x_m = b_m x1=b1,x2=b2,,xm=bm , 这些值肯定大于 0 0 0 , 因此这些基解是基可行解 ;


    2 . 初始基可行解 : X ( 0 ) = ( x 1 0 , x 2 0 , ⋯   , x m 0 , 0 , ⋯   , 0 ) T X^{(0)}=( x_1^0 , x_2^0, \cdots , x_m^0 , 0 , \cdots , 0 )^T X(0)=(x10,x20,,xm0,0,,0)T , 其中右上角的 0 0 0 表示这是第 0 0 0 次迭代 , 是初始基可行解 ;

    其中 x 1 0 x_1^0 x10 是对应基变量 x 1 x_1 x1 的解 , x m 0 x_m^0 xm0 是对应基变量 x m x_m xm 的解 ;


    3 . 这是线性规划的向量形式 :

    m a x Z = C X s . t { ∑ j = 1 n P j x j = b x j ≥ 0 j = 1 , 2 , ⋯   , n \begin{array}{lcl}max Z = CX \\ \\ s.t \begin{cases} \sum_{j = 1}^{n} P_j x_j = b \\ \\ x_j \geq 0 & j=1,2,\cdots,n \end{cases}\end{array} maxZ=CXs.tj=1nPjxj=bxj0j=1,2,,n


    4 . 拆解约束方程 : 将上面的向量形式的 约束方程 , ∑ j = 1 n P j x j = b \sum_{j = 1}^{n} P_j x_j = b j=1nPjxj=b , 写成两部分 ;

    • ① 前半部分 : ∑ i = 1 m P i x i \sum_{i=1}^{m}P_ix_i i=1mPixi , 由 x 1 ⋯ x m x_1 \cdots x_m x1xm 基变量及其系数组成 ;
    • ② 后半部分 : ∑ j = m + 1 n P j x j \sum_{j=m+1}^{n}P_jx_j j=m+1nPjxj x m + 1 ⋯ x n x_{m+1} \cdots x_n xm+1xn 组成 ;


    3.3 初始基可行解 代入 拆解后的 线性规划 约束方程中



    1 . 拆解后 线性规划的 向量形式为 :

    m a x Z = C X s . t { ∑ i = 1 m P i x i + ∑ j = m + 1 n P j x j = b x j ≥ 0 j = 1 , 2 , ⋯   , n \begin{array}{lcl}max Z = CX \\ \\ s.t \begin{cases} \sum_{i=1}^{m}P_ix_i + \sum_{j=m+1}^{n}P_jx_j = b \\ \\ x_j \geq 0 & j=1,2,\cdots,n \end{cases}\end{array} maxZ=CXs.ti=1mPixi+j=m+1nPjxj=bxj0j=1,2,,n


    2 . 初始基可行解代入约束方程 : 将初始的基可行解 X ( 0 ) = ( x 1 0 , x 2 0 , ⋯   , x m 0 , 0 , ⋯   , 0 ) T X^{(0)}=( x_1^0 , x_2^0, \cdots , x_m^0 , 0 , \cdots , 0 )^T X(0)=(x10,x20,,xm0,0,,0)T 代入上述约束方程 ;

    其中 x 1 0 x_1^0 x10 是对应基变量 x 1 x_1 x1 的解 , x m 0 x_m^0 xm0 是对应基变量 x m x_m xm 的解 ;


    其中后半部分 ∑ j = m + 1 n P j x j \sum_{j=m+1}^{n}P_jx_j j=m+1nPjxj 的变量是非基变量 , 都等于 0 0 0 , 其乘以系数后的结果也等于 0 , 因此有

    ∑ j = m + 1 n P j x j = 0 \sum_{j=m+1}^{n}P_jx_j = 0 j=m+1nPjxj=0

    在约束方程中可以直接消去 ; 约束方程变成如下形式 , 得到 :

    ∑ i = 1 m P i x i 0 = b \sum_{i=1}^{m}P_ix_i^0 = b i=1mPixi0=b



    3.4 系数矩阵的 增广矩阵 概念



    1 . 线性规划 系数矩阵 的 增广矩阵 : 增广矩阵 就是 将 约束方程的右端项 b 1 b_1 b1 b m b_m bm 常数 , 写到矩阵中 , 当做最右侧的向量 ;

    2 . 下面是 线性规划标准形式的 约束方程 :
    s . t { x 1 + a 1 m + 1 x m + 1 + a 1 m + 2 x m + 2 + ⋯ + a 1 n x n = b 1 x 2 + a 2 m + 1 x m + 1 + a 2 m + 2 x m + 2 + ⋯ + a 2 n x n = b 2 ⋯ ⋯ ⋯ x m + a m m + 1 x m + 1 + a m m + 2 x m + 2 + ⋯ + a m n x n = b m x 1 , x 2 , ⋯   , x n ≥ 0 s.t \begin{cases} x_1 & & +a_{1 m+1} x_{m+1} + a_{1 m+2} x_{m+2} + \cdots + a_{1n}x_{n} = b_1 & \\ \\ & x_2 & + a_{2 m+1} x_{m+1} + a_{2 m+2} x_{m+2} + \cdots + a_{2n}x_{n} = b_2& \\ \\ \cdots\cdots\cdots \\ \\ & & x_m + a_{m m+1} x_{m+1} + a_{m m+2} x_{m+2} + \cdots + a_{mn}x_{n} = b_m& \\ \\ x_1, x_2 , \cdots , x_{n} \geq 0 \end{cases} s.tx1x1,x2,,xn0x2+a1m+1xm+1+a1m+2xm+2++a1nxn=b1+a2m+1xm+1+a2m+2xm+2++a2nxn=b2xm+amm+1xm+1+amm+2xm+2++amnxn=bm


    3 . 增广矩阵是 :

    [ 1 0 ⋯ 0 a 1 , m + 1 ⋯ a 1 j ⋯ a 1 n b 1 0 1 ⋯ 0 a 2 , m + 1 ⋯ a 2 j ⋯ a 2 n b 2 ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ ⋮ 0 0 ⋯ 1 a m , m + 1 ⋯ a m j ⋯ a m n b m ] \begin{array}{lcl} \begin{bmatrix} & 1 & 0 & \cdots & 0 & a_{1 , m+1} & \cdots & a_{1j} & \cdots a_{1n} & b_1 \\ & 0 & 1 & \cdots & 0 & a_{2 , m+1} & \cdots & a_{2j} & \cdots a_{2n} & b_2\\ & \vdots & \vdots & & \vdots & \vdots & & \vdots & \vdots & \vdots\\ & 0 & 0 & \cdots & 1 & a_{m , m+1} & \cdots & a_{mj} & \cdots a_{mn} & b_m\\ \end{bmatrix}\end{array} 100010001a1,m+1a2,m+1am,m+1a1ja2jamja1na2namnb1b2bm

    为该增广矩阵中的向量标号 P 1 P_1 P1 P n P_n Pn 方便下面讨论 ;


    4 . 增广矩阵的前 m m m 个向量 : P 1 P_1 P1 P m P_m Pm 是 基变量前的系数 , 基向量 , 也是 单位向量 :

    [ 1 0 ⋯ 0 0 1 ⋯ 0 ⋮ ⋮ ⋮ 0 0 ⋯ 1 ] \begin{array}{lcl} \begin{bmatrix} & 1 & 0 & \cdots & 0 & \\ & 0 & 1 & \cdots & 0 & \\ & \vdots & \vdots & & \vdots & \\ & 0 & 0 & \cdots & 1 &\\ \end{bmatrix}\end{array} 100010001


    5 . 增广矩阵的 第 m + 1 m+1 m+1 n n n 个向量 : P m + 1 P_{m+1} Pm+1 P n P_n Pn 是正常的列向量 , 写到 单位向量右侧 , 常数向量左侧 :

    [ a 1 , m + 1 ⋯ a 1 j ⋯ a 1 n b 1 a 2 , m + 1 ⋯ a 2 j ⋯ a 2 n b 2 ⋮ ⋮ ⋮ ⋮ a m , m + 1 ⋯ a m j ⋯ a m n b m ] \begin{array}{lcl} \begin{bmatrix} & & a_{1 , m+1} & \cdots & a_{1j} & \cdots a_{1n} & b_1 \\ & & a_{2 , m+1} & \cdots & a_{2j} & \cdots a_{2n} & b_2\\ & & \vdots & \vdots & & \vdots & \vdots & \\ & & a_{m , m+1} & \cdots & a_{mj} & \cdots a_{mn} & b_m\\ \end{bmatrix}\end{array} a1,m+1a2,m+1am,m+1a1ja2jamja1na2namnb1b2bm



    3.5 向量间的线性表达



    6 . 向量之间的线性表达 : 使用 P 1 P_1 P1 P m P_m Pm 单位向量 表达 P j P_j Pj 向量 ;

    n n n 维的单位向量可以表示任何 n n n 维向量 ;

    表示公式 : 其中的 P j P_j Pj 向量在下面有解释
    P j = a 1 j P 1 + a 2 j P 2 + a 3 j P 3 + ⋯ + a m j P m = ∑ i = 1 m a i j P i \begin{array}{lcl}P_j & = & a_{1j} P_1 + a_{2j} P_2 + a_{3j} P_3 + \cdots + a_{mj}P_m \\\\ & = & \sum_{i=1}^m a_{ij}P_i \end{array} Pj==a1jP1+a2jP2+a3jP3++amjPmi=1maijPi

    a 1 j P 1 a_{1j} P_1 a1jP1 计算 : 其中 a 1 j a_{1j} a1j 是个常数 , P 1 P_1 P1 是个向量 , 运算方式就是 常数 乘以 向量中每个值 , 然后相加 , P 1 P_1 P1 中只有第一项是 1 , 其它项都是 0 0 0 , 因此结果是 a 1 j a_{1j} a1j ;


    P 1 P_1 P1 P m P_m Pm 单位向量是 :
    [ 1 0 ⋯ 0 0 1 ⋯ 0 ⋮ ⋮ ⋮ 0 0 ⋯ 1 ] \begin{array}{lcl} \begin{bmatrix} & 1 & 0 & \cdots & 0 & \\ & 0 & 1 & \cdots & 0 & \\ & \vdots & \vdots & & \vdots & \\ & 0 & 0 & \cdots & 1 &\\ \end{bmatrix}\end{array} 100010001

    P j P_j Pj 向量是 :
    [ a 1 j a 2 j ⋮ a m j ] \begin{array}{lcl} \begin{bmatrix} & a_{1j} & \\ & a_{2j} & \\ & \vdots & \\ & a_{mj} &\\ \end{bmatrix}\end{array} a1ja2jamj

    7 . 线性表达移项 :

    将上述线性表达式结果进行移项 :

    P j = a 1 j P 1 + a 2 j P 2 + a 3 j P 3 + ⋯ + a m j P m = ∑ i = 1 m a i j P i \begin{array}{lcl}P_j & = & a_{1j} P_1 + a_{2j} P_2 + a_{3j} P_3 + \cdots + a_{mj}P_m \\\\ & = & \sum_{i=1}^m a_{ij}P_i \end{array} Pj==a1jP1+a2jP2+a3jP3++amjPmi=1maijPi

    移项后结果 :

    P j − ∑ i = 1 m a i j P i = 0 P_j - \sum_{i=1}^m a_{ij}P_i = 0 Pji=1maijPi=0

    将上述式子左右两边乘以一个正数 θ \theta θ :

    θ ( P j − ∑ i = 1 m a i j P i ) = 0 \theta ( P_j - \sum_{i=1}^m a_{ij}P_i ) = 0 θ(Pji=1maijPi)=0




    3.6 将 向量线性表达结果 与 初始基可行解代入结果 结合



    1 . 初始基可行解代入 拆解后的向量公式中 : 将线性规划 向量形式 根据 基向量 非基向量 进行拆解 , 并将初始基可行解代入到拆解后的约束方程中 , 结果是 :

    ∑ i = 1 m P i x i 0 = b \sum_{i=1}^{m}P_ix_i^0 = b i=1mPixi0=b


    2 . 向量间线性表达最终结果是 :

    θ ( P j − ∑ i = 1 m a i j P i ) = 0 \theta ( P_j - \sum_{i=1}^m a_{ij}P_i ) = 0 θ(Pji=1maijPi)=0


    3 . 向量线性表达结果 与 初始基可行解代入结果 结合 : 将 上述 二者结合这样我们得到了下面的方程组 :

    { θ ( P j − ∑ i = 1 m a i j P i ) = 0 ∑ i = 1 m P i x i 0 = b \begin{cases} \theta ( P_j - \sum_{i=1}^m a_{ij}P_i ) = 0 \\\\ \sum_{i=1}^{m}P_ix_i^0 = b \end{cases} θ(Pji=1maijPi)=0i=1mPixi0=b

    4 . 将方程组两边分别相加 并计算 :

    θ ( P j − ∑ i = 1 m a i j P i ) + ∑ i = 1 m P i x i 0 = 0 + b θ P j − θ ∑ i = 1 m a i j P i + ∑ i = 1 m P i x i 0 = b ∑ i = 1 m ( x i 0 − θ a i j ) P i + θ P j = b \begin{array}{lcl} \theta ( P_j - \sum_{i=1}^m a_{ij}P_i ) + \sum_{i=1}^{m}P_ix_i^0 & = &0 + b \\\\ \theta P_j - \theta \sum_{i=1}^m a_{ij}P_i + \sum_{i=1}^{m}P_ix_i^0 & = & b \\\\ \sum_{i=1}^{m} ( x_i^0 - \theta a_{ij}) P_i + \theta P_j & = & b \\\\ \end{array} θ(Pji=1maijPi)+i=1mPixi0θPjθi=1maijPi+i=1mPixi0i=1m(xi0θaij)Pi+θPj===0+bbb

    最终结果是 :

    ∑ i = 1 m ( x i 0 − θ a i j ) P i + θ P j = b \sum_{i=1}^{m} ( x_i^0 - \theta a_{ij} ) P_i + \theta P_j = b i=1m(xi0θaij)Pi+θPj=b



    3.7 分析初始的约束方程



    上面得到式子 :

    ∑ i = 1 m ( x i 0 − θ a i j ) P i + θ P j = b \sum_{i=1}^{m} ( x_i^0 - \theta a_{ij} ) P_i + \theta P_j = b i=1m(xi0θaij)Pi+θPj=b

    该结果 正好是 满足 约束方程的 一个解 ; 初始的约束方程组为 :

    ∑ j = 1 n P j x j = b \sum_{j = 1}^{n} P_j x_j = b j=1nPjxj=b

    展开后为 :

    P 1 x 1 + P 2 x 2 + ⋯ + P j x j = b P_1x_1 + P_2x_2 + \cdots + P_jx_j = b P1x1+P2x2++Pjxj=b

    都是 x j x_j xj 取某些值 , 满足 让 ∑ j = 1 n P j x j \sum_{j = 1}^{n} P_j x_j j=1nPjxj 结果等于 b b b ;

    只要满足让 P j P_j Pj 乘以一个数 x_j , 将这些 P j x j P_j x_j Pjxj 相加 , 结果等于 b b b , 那么这些 x j x_j xj 就是其中的一个解 ;

    这个解如果都大于 0 , 那么这些解都是可行解 ;



    3.8 分析 经过 方程组变换后的 式子 引入 变换后的 基可行解



    1 . 向量形式分析 :

    将 向量线性表达结果 与 初始基可行解代入结果 结合 经过各种变换后的 最终结果是 :

    ∑ i = 1 m ( x i 0 − θ a i j ) P i + θ P j = b \sum_{i=1}^{m} ( x_i^0 - \theta a_{ij} ) P_i + \theta P_j = b i=1m(xi0θaij)Pi+θPj=b

    由此发现 , 该形式 与 初始的线性规划向量形式的 约束方程 的 形式 几乎一致 :

    ∑ j = 1 n P j x j = b \sum_{j = 1}^{n} P_j x_j = b j=1nPjxj=b


    2 . 展开式分析 :

    将上面的

    ∑ i = 1 m ( x i 0 − θ a i j ) P i + θ P j = b \sum_{i=1}^{m} ( x_i^0 - \theta a_{ij} ) P_i + \theta P_j = b i=1m(xi0θaij)Pi+θPj=b

    展开后为 :
    ( x 1 0 − θ a 1 j ) P 1 + ( x 2 0 − θ a 2 j ) P 2 + ⋯ + ( x i 0 − θ a i j ) P i + θ P j = b ( x_1^0 - \theta a_{1j}) P_1 + ( x_2^0 - \theta a_{2j}) P_2 + \cdots + ( x_i^0 - \theta a_{ij}) P_i + \theta P_j = b (x10θa1j)P1+(x20θa2j)P2++(xi0θaij)Pi+θPj=b

    线性方程标准形式展开后的结果 :

    P 1 x 1 + P 2 x 2 + ⋯ + P j x j = b P_1x_1 + P_2x_2 + \cdots + P_jx_j = b P1x1+P2x2++Pjxj=b


    3 . 关于解的说明 :

    P 1 , P 2 , ⋯   , P i , P j P_1 , P_2 , \cdots , P_i , P_j P1,P2,,Pi,Pj 都是系数向量 , 前面乘以的数就是 对应的解 ;

    ∑ i = 1 m ( x i 0 − θ a i j ) P i + θ P j \sum_{i=1}^{m} ( x_i^0 - \theta a_{ij}) P_i + \theta P_j i=1m(xi0θaij)Pi+θPj 式子中 P i P_i Pi P j P_j Pj 系数相乘的取值就是满足 约束方程 ∑ j = 1 n P j x j = b \sum_{j = 1}^{n} P_j x_j = b j=1nPjxj=b 的一个解 ;

    即 :

    系数向量 P 1 P_1 P1 对应的解是 ( x 1 0 − θ a 1 j ) ( x_1^0 - \theta a_{1j}) (x10θa1j) ;
    系数向量 P 2 P_2 P2 对应的解是 ( x 2 0 − θ a 2 j ) ( x_2^0 - \theta a_{2j}) (x20θa2j) ;
    ⋮ \vdots
    系数向量 P i P_i Pi 对应的解是 ( x i 0 − θ a i j ) ( x_i^0 - \theta a_{ij}) (xi0θaij) ;
    系数向量 P j P_j Pj 对应的解是 θ \theta θ ;


    第一次迭代后的 解 为 :

    X ( 1 ) = ( x 1 0 − θ a 1 j , x 2 0 − θ a 2 j , ⋯   , x m 0 − θ a m j , 0 , ⋯   , θ , ⋯   , 0 ) T X^{(1)}=( x_1^0 - \theta a_{1j} ,x_2^0 - \theta a_{2j} , \cdots , x_m^0 - \theta a_{mj} , 0 , \cdots , \theta , \cdots , 0 )^T X(1)=(x10θa1j,x20θa2j,,xm0θamj,0,,θ,,0)T

    初始线性规划的基可行解为 X ( 0 ) = ( x 1 0 , x 2 0 , ⋯   , x m 0 , 0 , ⋯   , 0 ) T X^{(0)}=( x_1^0 , x_2^0, \cdots , x_m^0 , 0 , \cdots , 0 )^T X(0)=(x10,x20,,xm0,0,,0)T ;



    3.9 θ \theta θ 的取值分析



    1 . 可行解的非负约束 : 线性规划 解出的基解 , 满足约束方程组的另外一个条件是 , 这一组解是基可行解 , 即这些解都要大于等于 0 , 要满足解的非负约束 ;

    满足所有约束条件的解才是基可行解 , 约束条件除了满足约束方程约束外 , 还要满足变量的非负约束 ;


    2 . 分析解 : 下面是第一次迭代出的解 , 如果下面的解都是可行解 , 则所有的解必须大于等于 0 ;

    X ( 1 ) = ( x 1 0 − θ a 1 j , x 2 0 − θ a 2 j , ⋯   , x m 0 − θ a m j , 0 , ⋯   , θ , ⋯   , 0 ) T X^{(1)}=( x_1^0 - \theta a_{1j} ,x_2^0 - \theta a_{2j} , \cdots , x_m^0 - \theta a_{mj} , 0 , \cdots , \theta , \cdots , 0 )^T X(1)=(x10θa1j,x20θa2j,,xm0θamj,0,,θ,,0)T

    上述解都必须大于等于 0 0 0 , 才是可行解 , 因此有下面的式子 :

    x i 0 − θ a i j ≥ 0 i = 1 , 2 , ⋯   , m x i 0 ≥ θ a i j \begin{array}{lcl} x_i^0 - \theta a_{ij} \geq 0 & i = 1 , 2 , \cdots , m \\\\ x_i^0 \geq \theta a_{ij} \end{array} xi0θaij0xi0θaiji=1,2,,m

    因为 θ \theta θ 是正数 , 可以在等式两边都除以 θ \theta θ , 得到下面的表达式 :

    a i j ≤ x i 0 θ a_{ij} \leq \frac{x_i^0}{\theta} aijθxi0

    a i j a_{ij} aij 要满足上面的条件 , 该解才是可行解 ;


    3 . a i j a_{ij} aij 取值有两种情况 :

    • a i j ≤ 0 a_{ij} \leq 0 aij0 ;
    • a i j > 0 a_{ij} > 0 aij>0 ;

    下面会 根据 a i j a_{ij} aij 的取值 , 分情况讨论 θ \theta θ 取值 ;


    4 . a i j ≤ 0 a_{ij} \leq 0 aij0 的情况 :

    如果 a i j ≤ 0 a_{ij} \leq 0 aij0 , a i j ≤ x i 0 θ a_{ij} \leq \frac{x_i^0}{\theta} aijθxi0 肯定成立 , 因为 x i 0 x_i^0 xi0 θ \theta θ 都是整数 , 两个数相除 , 肯定也是正数 , 正数肯定大于负数 ;

    m m m 个约束不等式 至少有一个等号是成立的 , 当 a i j ≤ 0 a_{ij} \leq 0 aij0 时 , 式子 a i j ≤ x i 0 θ a_{ij} \leq \frac{x_i^0}{\theta} aijθxi0 肯定成立 ;


    5 . a i j > 0 a_{ij} > 0 aij>0 时的情况 :

    假设 a i j , a 2 j , ⋯   , a m j a_{ij} , a_{2j} , \cdots , a_{mj} aij,a2j,,amj 中最小的是第 l l l 个 , 即 a l j a_{lj} alj , 那么有下面的式子 :

    θ = m i n { x i 0 a i j ∣ a i j > 0 } = x l 0 a l j \theta = min\begin{Bmatrix}\\\\ \frac{x_i^0}{a_{ij}} | a_{ij} > 0 \\\\ \end{Bmatrix} =\frac{x_l^0}{a_{lj}} θ=minaijxi0aij>0=aljxl0

    θ \theta θ x i 0 a i j \frac{x_i^0}{a_{ij}} aijxi0 中最小的那个值 , 当 i = l i=l i=l 时 , 该值最小 ;

    这样可以确保 :

    • ① 当 x i 0 − θ a i j = 0 x_i^0 - \theta a_{ij} = 0 xi0θaij=0 时 , i = l i=l i=l ;
    • ② 当 x i 0 − θ a i j ≥ 0 x_i^0 - \theta a_{ij} \geq 0 xi0θaij0 时 , i ≠ l i \not=l i=l ;

    这个 θ \theta θ 是单纯形法中最重要的 最小比值规则 ;

    将上述 θ \theta θ 代入初始的基解 X ( 1 ) X^{(1)} X(1) 得到的就是可行解 : 下面的解都是可行解 ;

    X ( 1 ) = ( x 1 0 − θ a 1 j , x 2 0 − θ a 2 j , ⋯   , x m 0 − θ a m j , 0 , ⋯   , θ , ⋯   , 0 ) T X^{(1)}=( x_1^0 - \theta a_{1j} ,x_2^0 - \theta a_{2j} , \cdots , x_m^0 - \theta a_{mj} , 0 , \cdots , \theta , \cdots , 0 )^T X(1)=(x10θa1j,x20θa2j,,xm0θamj,0,,θ,,0)T



    3.10 验证基矩阵 及 初等行变换



    1 . 判定解是否可行 : 上面的解是可行解 , 下面需要验证这些可行解对应的向量是否能组成一个基 , 即 判定这个解是否是基可行解 ;


    2 . 向量替换 : 将第一次变换的 P j P_j Pj 放到原基中 , 原来的初始基是单位阵 , 即 P 1 , P 2 , ⋯   , P m P_1 , P_2 , \cdots , P_m P1,P2,,Pm , 将其中的 P l P_l Pl 替换成 P j P_j Pj , 已经验证过解出的解是可行解 , 现在要验证 P j P_j Pj 向量替换 P l P_l Pl 后 , 该矩阵是不是基矩阵 ;


    3 . 判定基 : 新的矩阵的行列式值不等于 0 0 0 , 则说明该矩阵是基矩阵 , 因为除 P j P_j Pj 外其余都是单位阵 , 显然该行列式不等于 0 0 0 , 该矩阵是基矩阵 ;


    4 . 单位阵转换 : 该解作为迭代后的新的基可行解 , 为了方便下一步推导 , 我们希望对应的基向量都是单位向量 ; 这里需要使用矩阵的初等行变换 , 将其转为单位向量 ;


    5 . 初等行变换 : P j P_j Pj 列 , 替换成单位列 , P j P_j Pj 向量中 , a l j a_{lj} alj 除以 a l j a_{lj} alj , 变成 1 1 1 ,



    4 . 最优性检验 和 解的判别





    4.1 将 基可行解 代入方程



    将上述 初始基可行解
    X ( 0 ) = ( x 1 0 , x 2 0 , ⋯   , x m 0 , 0 , ⋯   , 0 ) T X^{(0)}=( x_1^0 , x_2^0, \cdots , x_m^0 , 0 , \cdots , 0 )^T X(0)=(x10,x20,,xm0,0,,0)T , 和 第一次迭代后的基可行解 X ( 1 ) = ( x 1 0 − θ a 1 j , x 2 0 − θ a 2 j , ⋯   , x m 0 − θ a m j , 0 , ⋯   , θ , ⋯   , 0 ) T X^{(1)}=( x_1^0 - \theta a_{1j} ,x_2^0 - \theta a_{2j} , \cdots , x_m^0 - \theta a_{mj} , 0 , \cdots , \theta , \cdots , 0 )^T X(1)=(x10θa1j,x20θa2j,,xm0θamj,0,,θ,,0)T , 分别代入约束方程的目标函数 :

    m a x Z = C X = ∑ j = 1 n c j x j max Z = CX = \sum_{j=1}^n c_j x_j maxZ=CX=j=1ncjxj


    代入 X ( 0 ) X^{(0)} X(0) , 因为只有前 m m m 项是非 0 0 0 的 , 后面的解都是 0 0 0 , 代入后的结果 :

    Z ( 0 ) = ∑ i = 1 m c i x i 0 Z^{(0)} = \sum_{i = 1}^m c_i x_i^0 Z(0)=i=1mcixi0


    代入 X ( 1 ) X^{(1)} X(1) , 只有前 m m m 项 , 和第 j j j 项的解是非 0 0 0 的 , 其余的解都是 0 0 0 , 前 m m m 项 解为 ( x i 0 − θ a i j ) (x_i^0 - \theta a_{ij}) (xi0θaij) 其中 ( i = 1 , 2 , ⋯   , m ) ( i = 1 , 2 , \cdots , m) (i=1,2,,m) 代入后为

    ∑ i = 1 m c i ( x i 0 − θ a i j ) \sum_{i = 1}^m c_i ( x_i^0 - \theta a_{ij} ) i=1mci(xi0θaij)

    j j j 项解为 θ \theta θ , 代入后为 θ c j \theta c_j θcj ;

    整体目标函数代入结果 :

    Z ( 1 ) = ∑ i = 1 m c i ( x i 0 − θ a i j ) + θ c j Z^{(1)} = \sum_{i = 1}^m c_i ( x_i^0 - \theta a_{ij} ) + \theta c_j Z(1)=i=1mci(xi0θaij)+θcj



    4.2 引入 检验数



    1 . 合并同类项 :

    在上面的 Z ( 1 ) Z^{(1)} Z(1) 基础上 , 将其中的 ∑ i = 1 m c i x i 0 \sum_{i = 1}^m c_i x_i^0 i=1mcixi0 通过合并同类项 , 提取出来 :

    Z ( 1 ) = ∑ i = 1 m c i ( x i 0 − θ a i j ) + θ c j Z^{(1)} = \sum_{i = 1}^m c_i ( x_i^0 - \theta a_{ij} ) + \theta c_j Z(1)=i=1mci(xi0θaij)+θcj
    Z ( 1 ) = ∑ i = 1 m c i x i 0 − ∑ i = 1 m c i θ a i j + θ c j Z^{(1)} = \sum_{i = 1}^m c_i x_i^0 - \sum_{i = 1}^m c_i \theta a_{ij} + \theta c_j Z(1)=i=1mcixi0i=1mciθaij+θcj
    Z ( 1 ) = ∑ i = 1 m c i x i 0 + θ c j − ∑ i = 1 m c i θ a i j Z^{(1)} = \sum_{i = 1}^m c_i x_i^0 + \theta c_j - \sum_{i = 1}^m c_i \theta a_{ij} Z(1)=i=1mcixi0+θcji=1