精华内容
下载资源
问答
  • PHP变量什么

    2021-05-06 01:53:18
    PHP是一门弱类型语言,本身不严格区分变量的类型。PHP在变量申明的时候不需要指定类型。PHP在程序运行期间可能进行变量类型的隐示转换。...以上所有的变量在底层都是同一种结构 zval。Zval主要由三部分组成:...

    PHP是一门弱类型语言,本身不严格区分变量的类型。PHP在变量申明的时候不需要指定类型。

    PHP在程序运行期间可能进行变量类型的隐示转换。 和其他强类型语言一样,程序中也可以进行显示的类型转换。

    PHP变量可以分为简单类型(int、string、bool)、集合类型(array resource

    object)和常量(const)。以上所有的变量在底层都是同一种结构 zval。

    Zval主要由三部分组成:

    type:指定了变量所述的类型(整数、字符串、数组等)

    refcount&is_ref:用来实现引用计数(后面具体介绍)

    value:核心部分,存储了变量的实际数据

    Zvalue是用来保存一个变量的实际数据。因为要存储多种类型,所以zvalue是一个union,也由此实现了弱类型。

    PHP变量是什么?

    引用计数在内存回收、字符串操作等地方使用非常广泛。PHP中的变量就是引用计数的典型应用。Zval的引用计数通过成员变量is_ref和ref_count实现,通过引用计数,多个变量可以共享同一份数据。避免频繁拷贝带来的大量消耗。在进行赋值操作时,zend将变量指向相同的zval同时ref_count++,在unset操作时,对应的ref_count-1。只有ref_count减为0时才会真正执行销毁操作。如果是引用赋值,则zend会修改is_ref为1。

    PHP变量通过引用计数实现变量共享数据,那如果改变其中一个变量值呢?当试图写入一个变量时,Zend若发现该变量指向的zval被多个变量共

    享,则为其复制一份ref_count为1的zval,并递减原zval的refcount,这个过程称为“zval分离”。可见,只有在有写操作发生时

    zend才进行拷贝操作,因此也叫copy-on-write(写时拷贝)对于引用型变量,其要求和非引用型相反,引用赋值的变量间必须是捆绑的,修改一个变量就修改了所有捆绑变量。整数、浮点数是PHP中的基础类型之一,也是一个简单型变量。对于整数和浮点数,在zvalue中直接存储对应的值。其类型分别是long和double。

    从zvalue结构中可以看出,对于整数类型,和c等强类型语言不同,PHP是不区分int、unsigned int、long、long

    long等类型的,对它来说,整数只有一种类型也就是long。由此,可以看出,在PHP里面,整数的取值范围是由编译器位数来决定而不是固定不变的。

    对于浮点数,类似整数,它也不区分float和double而是统一只有double一种类型。在PHP中,如果整数范围越界了怎么办?这种情况下会自动转换为double类型,这个一定要小心,很多trick都是由此产生。

    和整数一样,字符变量也是PHP中的基础类型和简单型变量。通过zvalue结构可以看出,在PHP中,字符串是由由指向实际数据的指针和长度结

    构体组成,这点和c++中的string比较类似。由于通过一个实际变量表示长度,和c不同,它的字符串可以是2进制数据(包含\0),同时在PHP中,

    求字符串长度strlen是O(1)操作。在新增、修改、追加字符串操作时,PHP都会重新分配内存生成新的字符串。后,出于安全考虑,PHP在生成一个字符串时末尾仍然会添加\0

    常见的字符串拼接方式及速度比较:假设有如下4个变量:$strA=‘123’; $strB = ‘456’; $intA=123;

    intB=456;

    PHP的数组通过Zend

    HashTable来天然实现。foreach操作如何实现?对一个数组的foreach就是通过遍历hashtable中的双向链表完成。对于索引数组,通过foreach遍

    历效率比for高很多,省去了key->value的查找。count操作直接调用

    HashTable->NumOfElements,O(1)操作。对于’123’这样的字符串,zend会转换为其整数形

    式。$arr[‘123’]和$arr[123]是等价的

    资源类型变量是PHP中复杂的一种变量,也是一种复合型结构。PHP的zval可以表示广泛的数据类型,但是对于自定义的数据类型却很难充分描述。由于没有有效的方式描绘这些复合结构,因此也没有办法对它们使用传统的操作符。要解决这个问题,只需要通过一个本质上任意的标识符(label)引用指针,这种方式被称为资源。

    PHP变量是什么?

    像我们所熟悉的mysqli、fsock、memcached这一类都是资源,首先我们先了解关于这类资源的专业知识,其次将讲解如何使用这些资源。

    展开全文
  • 前言之前在项目的存储过程中发现有...,这两种类型的变量究竟有什么区别却弄不清楚,赶紧上网查询资料,发现还有@@sql_mode这样的变量,这一个圈俩圈的到底是什么啊?会不会出现三个圈的情况?变量分类与关系经过一...

    前言

    之前在项目的存储过程中发现有通过 DECLARE 关键字定义的变量如DECLARE cnt INT DEFAULT 0;,还有形如 @count 这样的变量,存储过程中拿过来直接就进行设置,像这样set @count=1;,这两种类型的变量究竟有什么区别却弄不清楚,赶紧上网查询资料,发现还有@@sql_mode这样的变量,这一个圈俩圈的到底是什么啊?会不会出现三个圈的情况?

    变量分类与关系

    经过一段时间学习和测试,再配合官方的文档,现在大致弄清楚了这些变量的区别,一般可以将MySQL中的变量分为全局变量、会话变量、用户变量和局部变量,这是很常见的分类方法,这些变量的作用是什么呢?可以从前往后依次看一下。

    首先我们知道MySQL服务器维护了许多系统变量来控制其运行的行为,这些变量有些是默认编译到软件中的,有些是可以通过外部配置文件来配置覆盖的,如果想查询自编译的内置变量和从文件中可以读取覆盖的变量可以通过以下命令来查询:

    mysqld --verbose --help

    如果想只看自编译的内置变量可以使用命令:

    mysqld --no-defaults --verbose --help

    接下来简单了解一下这几类变量的应用范围,首先MySQL服务器启动时会使用其软件内置的变量(俗称写死在代码中的)和配置文件中的变量(如果允许,是可以覆盖源代码中的默认值的)来初始化整个MySQL服务器的运行环境,这些变量通常就是我们所说的全局变量,这些在内存中的全局变量有些是可以修改的。

    当有客户端连接到MySQL服务器的时候,MySQL服务器会将这些全局变量的大部分复制一份作为这个连接客户端的会话变量,这些会话变量与客户端连接绑定,连接的客户端可以修改其中允许修改的变量,但是当连接断开时这些会话变量全部消失,重新连接时会从全局变量中重新复制一份。

    其实与连接相关的变量不只有会话变量一种,用户变量也是这样的,用户变量其实就是用户自定义变量,当客户端连接上MySQL服务器之后就可以自己定义一些变量,这些变量在整个连接过程中有效,当连接断开时,这些用户变量消失。

    局部变量实际上最好理解,通常由DECLARE 关键字来定义,经常出现在存储过程中,非常类似于C和C++函数中的局部变量,而存储过程的参数也和这种变量非常相似,基本上可以作为同一种变量来对待。

    变量的修改

    先说全局变量有很多是可以动态调整的,也就是说可以在MySQL服务器运行期间通过 SET 命令修改全局变量,而不需要重新启动 MySQL 服务,但是这种方法在修改大部分变量的时候都需要超级权限,比如root账户。

    相比之下会话对变量修改的要求要低的多,因为修改会话变量通常只会影响当前连接,但是有个别一些变量是例外的,修改它们也需要较高的权限,比如 binlog_format 和 sql_log_bin,因为设置这些变量的值将影响当前会话的二进制日志记录,也有可能对服务器复制和备份的完整性产生更广泛的影响。

    至于用户变量和局部变量,听名字就知道,这些变量的生杀大权完全掌握在自己手中,想改就改,完全不需要理会什么权限,它的定义和使用全都由用户自己掌握。

    测试环境

    以下给出MySQL的版本,同时使用root用户测试,这样可以避免一些权限问题。

    Welcome to the MySQL monitor. Commands end with ; or \g.

    Your MySQL connection id is 7

    Server version: 5.7.21-log MySQL Community Server (GPL)

    Copyright © 2000, 2018, Oracle and/or its affiliates. All rights reserved.

    Oracle is a registered trademark of Oracle Corporation and/or its

    affiliates. Other names may be trademarks of their respective owners.

    Type ‘help;’ or ‘\h’ for help. Type ‘\c’ to clear the current input statement.

    变量查询与设置

    全局变量

    这些变量来源于软件自编译、配置文件中、以及启动参数中指定的变量,其中大部分是可以由root用户通过 SET 命令直接在运行时来修改的,一旦 MySQL 服务器重新启动,所有修改都被还原。如果修改了配置文件,想恢复最初的设置,只需要将配置文件还原,重新启动 MySQL 服务器,一切都可以恢复原来的样子。

    查询

    查询所有的全局变量:

    show global variables;

    一般不会这么用,这样查简直太多了,大概有500多个,通常会加个like控制过滤条件:

    mysql> show global variables like 'sql%';

    +------------------------+----------------------------------------------------------------+

    | Variable_name | Value |

    +------------------------+----------------------------------------------------------------+

    | sql_auto_is_null | OFF |

    | sql_big_selects | ON |

    | sql_buffer_result | OFF |

    | sql_log_off | OFF |

    | sql_mode | STRICT_TRANS_TABLES,NO_AUTO_CREATE_USER,NO_ENGINE_SUBSTITUTION |

    | sql_notes | ON |

    | sql_quote_show_create | ON |

    | sql_safe_updates | OFF |

    | sql_select_limit | 18446744073709551615 |

    | sql_slave_skip_counter | 0 |

    | sql_warnings | OFF |

    +------------------------+----------------------------------------------------------------+

    11 rows in set, 1 warning (0.00 sec)

    mysql>

    还有一种查询方法就是通过select语句:

    select @@global.sql_mode;

    当一个全局变量不存在会话变量副本时也可以这样

    select @@max_connections;

    设置

    设置全局变量也有两种方式:

    set global sql_mode='';

    或者

    set @@global.sql_mode='';

    会话变量

    这些变量基本来自于全局变量的复制,与客户端连接有关,无论怎样修改,当连接断开后,一切都会还原,下次连接时又是一次新的开始。

    查询

    类比全局变量,会话变量也有类似的查询方式,查询所有会话变量

    show session variables;

    添加查询匹配,只查一部分会话变量:

    show session variables like 'sql%';

    查询特定的会话变量,以下三种都可以:

    select @@session.sql_mode;

    select @@local.sql_mode;

    select @@sql_mode;

    设置

    会话变量的设置方法是最多的,以下的方式都可以:

    set session sql_mode = '';

    set local sql_mode = '';

    set @@session.sql_mode = '';

    set @@local.sql_mode = '';

    set @@sql_mode = '';

    set sql_mode = '';

    用户变量

    用户变量就是用户自己定义的变量,也是在连接断开时失效,定义和使用相比会话变量来说简单许多。

    查询

    直接一个select语句就可以了:

    select @count;

    设置

    设置也相对简单,可以直接使用set命令:

    set @count=1;

    set @sum:=0;

    也可以使用select into语句来设置值,比如:

    select count(id) into @count from items where price < 99;

    局部变量

    局部变量通常出现在存储过程中,用于中间计算结果,交换数据等等,当存储过程执行完,变量的生命周期也就结束了。

    查询

    也是使用select语句:

    declare count int(4);

    select count;

    设置

    与用户变量非常类似:

    declare count int(4);

    declare sum int(4);

    set count=1;

    set sum:=0;

    也可以使用select into语句来设置值,比如:

    declare count int(4);

    select count(id) into count from items where price < 99;

    其实还有一种存储过程参数,也就是C/C++中常说的形参,使用方法与局部变量基本一致,就当成局部变量来用就可以了

    几种变量的对比使用

    操作类型

    全局变量

    会话变量

    用户变量

    局部变量(参数)

    文档常用名

    global variables

    session variables

    user-defined variables

    local variables

    出现的位置

    命令行、函数、存储过程

    命令行、函数、存储过程

    命令行、函数、存储过程

    函数、存储过程

    定义的方式

    只能查看修改,不能定义

    只能查看修改,不能定义

    直接使用,@var形式

    declare count int(4);

    有效生命周期

    服务器重启时恢复默认值

    断开连接时,变量消失

    断开连接时,变量消失

    出了函数或存储过程的作用域,变量无效

    查看所有变量

    show global variables;

    show session variables;

    -

    -

    查看部分变量

    show global variables like 'sql%';

    show session variables like 'sql%';

    -

    -

    查看指定变量

    select @@global.sql_mode、

    select @@max_connections;

    select @@session.sql_mode;、

    select @@local.sql_mode;、

    select @@sql_mode;

    select @var;

    select count;

    设置指定变量

    set global sql_mode='';、

    set @@global.sql_mode='';

    set session sql_mode = '';、

    set local sql_mode = '';、

    set @@session.sql_mode = '';、

    set @@local.sql_mode = '';、

    set @@sql_mode = '';、

    set sql_mode = '';

    set @var=1;、

    set @var:=101;、

    select 100 into @var;

    set count=1;、

    set count:=101;、

    select 100 into count;

    相信看了这个对比的表格,之前的很多疑惑就应该清楚了,如果发现其中有什么疑惑的地方可以给我留言,或者发现有什么错误也可以一针见血的指出来,我会尽快改正的。

    总结

    MySQL 中的变量通常分为:全局变量、 会话变量、 用户变量、 局部变量

    其实还有一个存储过程和函数的参数,这种类型和局部变量基本一致,当成局部变量来使用就行了

    在表格中有一个容易疑惑的点就是无论是全局变量还是会话变量都有select@@变量名的形式。

    select@@变量名这种形式默认取的是会话变量,如果查询的会话变量不存在就会获取全局变量,比如@@max_connections

    但是SET操作的时候,set @@变量名=xxx 总是操作的会话变量,如果会话变量不存在就会报错

    展开全文
  • 单纯法原理 | 单纯法流程 | 单纯表 | 计算检验数 | 最优解判定 | 入基变量 | 出基变量 | 方程组同解变换





    一、单纯形法原理



    参考博客 : 【运筹学】线性规划数学模型 ( 单纯形法原理 | 单纯形法流程 | 查找初始基可行解 )


    单纯形法的理论基础 :


    定理 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 个问题 , 基可行解的算法 , 也就可以得出 ;





    三、单纯形法案例一





    1、线性规划示例


    使用单纯形法求解线性规划最优解 :


    m a x Z = 3 x 1 + 4 x 2 { 2 x 1 + x 2 ≤ 40 x 1 + 3 x 2 ≤ 30 x j ≥ 0 ( j = 1 , 2 ) \begin{array}{lcl} max Z = 3x_1 + 4x_2 \\ \\ \begin{cases} 2 x_1 + x_2 \leq 40 \\\\ x_1 + 3x_2 \leq 30 \\ \\x_j \geq 0 & (j = 1 , 2 ) \end{cases}\end{array} maxZ=3x1+4x22x1+x240x1+3x230xj0(j=1,2)



    2、转化标准形式


    首先将该线性规划转为标准形式 :

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


    ① 变量约束 : 首先查看变量约束 , 两个变量都是 ≥ 0 \geq 0 0 的 , 符合线性规划标准形式要求 ;

    ② 不等式转换 : 两个等式都是 小于等于不等式 , 需要 在不等式左侧加入松弛变量 , 将其转为等式 ;

    • 2 x 1 + x 2 ≤ 40 2 x_1 + x_2 \leq 40 2x1+x240 , 左侧加入松弛变量 x 3 x_3 x3 , 变为 2 x 1 + x 2 + x 3 = 40 2 x_1 + x_2 + x_3 = 40 2x1+x2+x3=40
    • x 1 + 3 x 2 ≤ 30 x_1 + 3x_2 \leq 30 x1+3x230 , 左侧加入松弛变量 x 4 x_4 x4 , 变为 x 1 + 3 x 2 + x 4 = 30 x_1 + 3x_2 + x_4 = 30 x1+3x2+x4=30

    ③ 更新目标函数 : x 3 x_3 x3 x 4 x_4 x4 加入到目标函数中 , 得到新的目标函数 m a x Z = 3 x 1 + 4 x 2 + 0 x 3 + 0 x 4 max Z = 3x_1 + 4x_2 + 0x_3 + 0x_4 maxZ=3x1+4x2+0x3+0x4 ;



    此时线性规划标准形式为 :

    m a x Z = 3 x 1 + 4 x 2 + 0 x 3 + 0 x 4 { 2 x 1 + x 2 + x 3 + 0 x 4 = 40 x 1 + 3 x 2 + 0 x 3 + x 4 = 30 x j ≥ 0 ( j = 1 , 2 , 3 , 4 ) \begin{array}{lcl} max Z = 3x_1 + 4x_2 + 0x_3 + 0x_4 \\ \\ \begin{cases} 2 x_1 + x_2 + x_3 + 0x_4 = 40 \\\\ x_1 + 3x_2 + 0x_3 + x_4 = 30 \\\\ x_j \geq 0 & (j = 1 , 2 , 3 , 4 ) \end{cases}\end{array} maxZ=3x1+4x2+0x3+0x42x1+x2+x3+0x4=40x1+3x2+0x3+x4=30xj0(j=1,2,3,4)



    3、查找初始基可行解


    找基矩阵 :


    上述线性规划标准形式的系数矩阵为 [ 2 1 1 0 1 3 0 1 ] \begin{bmatrix} &2 & 1 & 1 & 0 & \\\\ & 1 & 3 & 0 & 1 & \end{bmatrix} 21131001 , 其中子矩阵中有 [ 1 0 0 1 ] \begin{bmatrix} & 1 & 0 & \\\\ & 0 & 1 & \end{bmatrix} 1001 单位阵 I I I ;


    使用该单位阵 I I I 作为基矩阵 , 单位阵肯定是可逆的 , 其对应的基解 , 解出后的值就是右侧的常数值 , 肯定大于等于 0 0 0 , 是基可行解 ;



    列出单纯形表 :



    c j c_j cj c j c_j cj 3 3 3 4 4 4 0 0 0 0 0 0
    C B C_B CB 基变量系数 (目标函数)基变量常数 b b b x 1 x_1 x1 x 2 x_2 x2 x 3 x_3 x3 x 4 x_4 x4 θ i \theta_i θi
    0 0 0 ( 目标函数 x 3 x_3 x3 系数 c 3 c_3 c3 ) x 3 x_3 x3 40 40 40 2 2 2 1 1 1 1 1 1 0 0 0
    0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4) x 4 x_4 x4 30 30 30 1 1 1 3 3 3 0 0 0 1 1 1
    σ j \sigma_j σj 3 3 3 4 4 4 0 0 0 0 0 0

    基变量是 x 3 x_3 x3 x 4 x_4 x4 , 基变量在约束条件中的系数矩阵 [ 1 0 0 1 ] \begin{bmatrix} &1 & 0 & \\\\ &0 & 1 & \end{bmatrix} 1001 就是基矩阵 , 这是个单位阵 ;

    基变量是 x 3 x_3 x3 x 4 x_4 x4 在目标函数中的系数是 ( 0 0 ) \begin{pmatrix} \quad 0 \quad 0 \quad \end{pmatrix} (00) ;

    此时的基解是 ( 0 0 40 30 ) \begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 40 \quad \\ \quad 30 \quad \\ \end{pmatrix} 004030 , 该解是初始解 , 下面判定该解是否是最优解 ;



    4、初始基可行解的最优解判定


    使用 检验数矩阵 ( C N T − C B T B − 1 N ) ( C_N^T - C_B^T B^{-1}N ) (CNTCBTB1N) 判断上述解 , 是否是最优解 , 该矩阵计算结果中所有的数 , 都是检验数 σ \sigma σ , 如果 所有的数都小于等于 0 0 0 , 说明该解就是最优解 ;


    这里只求非基变量的检验数 , 即 x 1 x_1 x1 , x 2 x_2 x2 的检验数 ;


    列出目标函数非基变量系数 ( C N T − C B T B − 1 N ) ( C_N^T - C_B^T B^{-1}N ) (CNTCBTB1N) 矩阵 :

    • 非基变量在目标函数中的系数矩阵 : C N T = ( 3 4 ) C_N^T=\begin{pmatrix} \quad 3 \quad 4 \quad \end{pmatrix} CNT=(34)

    • 基变量在目标函数中的叙述矩阵 : C B T = ( 0 0 ) C_B^T = \begin{pmatrix} \quad 0 \quad 0 \quad \end{pmatrix} CBT=(00)

    • B − 1 N B^{-1}N B1N 是系数矩阵中经过矩阵变换后 , 基变量系数是单位阵 I I I , 非基变量系数是 B − 1 N B^{-1}N B1N : B − 1 N = [ 2 1 1 3 ] B^{-1}N =\begin{bmatrix} &2 & 1 & \\\\ &1 & 3 & \end{bmatrix} B1N=2113


    ( C N T − C B T B − 1 N ) = C N T = ( 3 4 ) − ( 0 0 ) × [ 2 1 1 3 ] ( C_N^T - C_B^T B^{-1}N ) = C_N^T=\begin{pmatrix} \quad 3 \quad 4 \quad \end{pmatrix} - \begin{pmatrix} \quad 0 \quad 0 \quad \end{pmatrix} \times \begin{bmatrix} &2 & 1 & \\\\ &1 & 3 & \end{bmatrix} (CNTCBTB1N)=CNT=(34)(00)×2113

    = ( σ 1 σ 2 ) = \begin{pmatrix} \quad \sigma_{1} \quad \sigma_{2} \quad \end{pmatrix} =(σ1σ2)


    其中 σ 1 \sigma_{1} σ1 是目标函数中 x 1 x_1 x1 的系数 , σ 2 \sigma_{2} σ2 是目标函数中的 x 2 x_2 x2 的系数 ;

    如果上述两个系数都小于等于 0 0 0 , 那么当 非基变量 X N = ( x 1 x 2 ) X_N =\begin{pmatrix} x_{1} \\ x_{2} \end{pmatrix} XN=(x1x2) 取值为 0 0 0 , 目标函数取值最大 ;


    系数的计算公式为 : σ j = c j − ∑ c i a i j \sigma_j = c_j - \sum c_i a_{ij} σj=cjciaij , 其中 c j c_j cj 对应的是非基变量在目标函数系数 , c i c_i ci 是基变量在目标函数中的系数 , a i j a_{ij} aij B − 1 N B^{-1}N B1N 中的矩阵向量 , 代表一列 ;



    σ 1 = c 1 − ( c 3 a 11 + c 4 a 12 ) \sigma_{1} = c_1 - ( c_3 a_{11} + c_4 a_{12} ) σ1=c1(c3a11+c4a12)

    σ 1 = 3 − ( 0 × 2 ) − ( 0 × 1 ) = 3 \sigma_{1} =3 - (0 \times 2) - (0 \times 1) = 3 σ1=3(0×2)(0×1)=3 , 是从下面的单纯形表中的如下位置提取的数值 ;

    在这里插入图片描述

    σ 2 = c 2 − ( c 3 a 21 + c 4 a 22 ) \sigma_{2} = c_2 - ( c_3 a_{21} + c_4 a_{22} ) σ2=c2(c3a21+c4a22)

    σ 2 = 4 − ( 0 × 1 ) − ( 0 × 3 ) = 4 \sigma_{2} =4 - (0 \times 1) - (0 \times 3) = 4 σ2=4(0×1)(0×3)=4 , 是从下面的单纯形表中的如下位置提取的数值 ;

    在这里插入图片描述


    如果这两个系数 , 如果都小于等于 0 0 0 , 该 基可行解 ( 0 0 40 30 ) \begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 40 \quad \\ \quad 30 \quad \\ \end{pmatrix} 004030 才是最优解 , 这两个系数都大于 0 0 0 , 因此不是最优解 ;



    5、第一次迭代 : 入基与出基变量选择


    入基变量选择 : 具体哪个变量入基 , 是由检验数决定的 , 检验数 σ j \sigma_j σj 较大的入基 ; x 2 x_2 x2 的检验数 σ 2 \sigma_2 σ2 4 4 4 , 大于 σ 1 = 3 \sigma_1 = 3 σ1=3 , 因此这里选择 x 2 x_2 x2 作为入基变量 ;


    出基变量选择 : 系数矩阵中 , 常数列 b = ( 40 30 ) b =\begin{pmatrix} \quad 40 \quad \\ \quad 30 \quad \end{pmatrix} b=(4030) , 分别除以除以入基变量大于 0 0 0 的系数列 ( 1 3 ) \begin{pmatrix} \quad 1 \quad \\ \quad 3 \quad \end{pmatrix} (13) , 得出结果是 ( 40 10 ) \begin{pmatrix} \quad 40 \quad \\ \quad 10 \quad \end{pmatrix} (4010) , 然后选择一个最小值 10 10 10 , 查看该最小值对应的变量是 x 4 x_4 x4 , 选择该变量作为出基变量 ;

    在这里插入图片描述


    这里将出基变量与入基变量选择好了 , x 2 x_2 x2 的检验数较大 , 选择 x 2 x_2 x2 作为入基变量 , x 4 x_4 x4 θ 4 \theta_4 θ4 较小 , 选择 x 4 x_4 x4 作为出基变量 ;


    入基出基操作完成后 , 基变量变成了 x 3 , x 2 x_3, x_2 x3,x2 ;



    6、第一次迭代 : 方程组同解变换


    方程组做同解变换 :



    线性规划原始方程组为 { 2 x 1 + x 2 + x 3 + 0 x 4 = 40 x 1 + 3 x 2 + 0 x 3 + x 4 = 30 \begin{cases} 2 x_1 + x_2 + x_3 + 0x_4 = 40 \\\\ x_1 + 3x_2 + 0x_3 + x_4 = 30 \end{cases} 2x1+x2+x3+0x4=40x1+3x2+0x3+x4=30 , 需要将 x 2 x_2 x2 的系数变为 ( 0 1 ) \begin{pmatrix} \quad 0 \quad \\ \quad 1 \quad \end{pmatrix} (01) , x 3 x_3 x3 的系数保持 ( 1 0 ) \begin{pmatrix} \quad 1 \quad \\ \quad 0 \quad \end{pmatrix} (10) 不变 ;



    方程 2 2 2 同解变换 : x 1 + 3 x 2 + 0 x 3 + x 4 = 30 x_1 + 3x_2 + 0x_3 + x_4 = 30 x1+3x2+0x3+x4=30 中 , 需要将 x 2 x_2 x2 的系数变成 1 1 1 , 在方程两端乘以 1 3 \dfrac{1}{3} 31 , 此时方程变成 1 3 x 1 + x 2 + 0 x 3 + 1 3 x 4 = 10 \dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4 = 10 31x1+x2+0x3+31x4=10 ;


    方程 1 1 1 同解变换 : 将上述方程 2 2 2 作同解变换后 , 方程组变成 { 2 x 1 + x 2 + x 3 + 0 x 4 = 40 1 3 x 1 + x 2 + 0 x 3 + 1 3 x 4 = 10 \begin{cases} 2 x_1 + x_2 + x_3 + 0x_4 = 40 \\\\ \dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4 = 10 \end{cases} 2x1+x2+x3+0x4=4031x1+x2+0x3+31x4=10 , 目前的需求是将方程 1 1 1 x 2 x_2 x2 系数变为 0 0 0 , 使用方程 1 1 1 减去 方程 2 2 2 即可得到要求的矩阵 :

    ( 2 − 1 3 ) x 1 + 0 x 2 + x 3 + ( 0 − 1 3 ) x 4 = 40 − 10 5 3 x 1 + 0 x 2 + x 3 − 1 3 x 4 = 30 \begin{array}{lcl} (2 - \dfrac{1}{3}) x_1 + 0 x_2 + x_3 + (0 - \dfrac{1}{3}) x_4 &=& 40 - 10 \\\\ \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 &=& 30 \end{array} (231)x1+0x2+x3+(031)x435x1+0x2+x331x4==401030


    最终方程 1 1 1 转化为 5 3 x 1 + 0 x 2 + x 3 − 1 3 x 4 = 30 \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 = 30 35x1+0x2+x331x4=30 ;



    同解变换完成后的方程组为 { 5 3 x 1 + 0 x 2 + x 3 − 1 3 x 4 = 30 1 3 x 1 + x 2 + 0 x 3 + 1 3 x 4 = 10 \begin{cases} \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 = 30 \\\\ \dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4 = 10 \end{cases} 35x1+0x2+x331x4=3031x1+x2+0x3+31x4=10





    7、第一次迭代 : 生成新的单纯形表


    单纯形表变成如下形式 : 下面的单纯形表中 , 上面部分是初始基可行解对应的单纯形表 , 下面的部分是本次迭代后生成的新的单纯形表 ;


    将同解变换后的方程组中的 系数矩阵 , 和 常数 , 填入新的单纯形表中 ;


    c j c_j cj c j c_j cj 3 3 3 4 4 4 0 0 0 0 0 0
    C B C_B CB 基变量系数 (目标函数)基变量常数 b b b x 1 x_1 x1 x 2 x_2 x2 x 3 x_3 x3 x 4 x_4 x4 θ i \theta_i θi
    0 0 0 ( 目标函数 x 3 x_3 x3 系数 c 3 c_3 c3 ) x 3 x_3 x3 40 40 40 2 2 2 1 1 1 1 1 1 0 0 0 40 40 40 ( θ 3 \theta_3 θ3 )
    0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4) x 4 x_4 x4 30 30 30 1 1 1 3 3 3 0 0 0 1 1 1 10 10 10 ( θ 4 \theta_4 θ4 )
    σ j \sigma_j σj 3 3 3 ( σ 1 \sigma_1 σ1 ) 4 4 4 ( σ 2 \sigma_2 σ2 ) 0 0 0 0 0 0
    0 0 0 ( 目标函数 x 3 x_3 x3 系数 c 3 c_3 c3 ) x 3 x_3 x3 30 30 30 5 3 \dfrac{5}{3} 35 0 0 0 1 1 1 − 1 3 -\dfrac{1}{3} 31 ? ? ? ( θ 3 \theta_3 θ3 )
    4 4 4 ( 目标函数 x 2 x_2 x2 系数 c 2 c_2 c2) x 2 x_2 x2 10 10 10 1 3 \dfrac{1}{3} 31 1 1 1 0 0 0 1 3 \dfrac{1}{3} 31 ? ? ? ( θ 2 \theta_2 θ2 )
    σ j \sigma_j σj ( 检验数 ) 5 3 \dfrac{5}{3} 35 ( σ 1 \sigma_1 σ1 ) 0 0 0 0 0 0 − 4 3 -\dfrac{4}{3} 34 ( σ 4 \sigma_4 σ4 )


    8、第一次迭代 : 解出基可行解


    新的 基变量是 x 3 , x 2 x_3 , x_2 x3,x2 , 对应的基矩阵是 ( 1 0 0 1 ) \begin{pmatrix} \quad 1 \quad 0 \quad \\ \quad 0 \quad 1 \quad \end{pmatrix} (1001) , 非基变量是 x 1 , x 4 x_1, x_4 x1,x4 , 对应的非基矩阵是 ( 5 3 − 1 3 1 3 1 3 ) \begin{pmatrix} \quad \dfrac{5}{3} \quad -\dfrac{1}{3} \quad \\ \quad \dfrac{1}{3} \quad \dfrac{1}{3} \quad \end{pmatrix} 35313131 , 将非基变量设置为 0 0 0 , 方程组为 { 5 3 × 0 + 0 x 2 + x 3 − 1 3 × 0 = 30 1 3 × 0 + x 2 + 0 x 3 + 1 3 × 0 = 10 \begin{cases} \dfrac{5}{3} \times 0 + 0x_2 + x_3 - \dfrac{1}{3} \times 0 = 30 \\\\ \dfrac{1}{3} \times 0 + x_2 + 0x_3 + \dfrac{1}{3} \times 0 = 10 \end{cases} 35×0+0x2+x331×0=3031×0+x2+0x3+31×0=10 , 解出基变量为 { x 3 = 30 x 2 = 10 \begin{cases} x_3 = 30 \\\\ x_2 = 10 \end{cases} x3=30x2=10 , 基可行解 ( 0 10 30 0 ) \begin{pmatrix} \quad 0 \quad \\ \quad 10 \quad \\ \quad 30 \quad \\ \quad 0 \quad \end{pmatrix} 010300



    9、第一次迭代 : 计算检验数 σ j \sigma_j σj 判定最优解 并选择入基变量


    根据 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 单纯形表 | 系数计算方法 | 根据系数是否小于等于 0 判定最优解 ) 博客中分析 , 检验数计算公式为 :

    • 矩阵形式 : C N T − C B T B − 1 N C_N^T - C_B^T B^{-1}N CNTCBTB1N
    • 单个检验数计算公式 : σ j = c j − ∑ c i a i j \sigma_j = c_j - \sum c_i a_{ij} σj=cjciaij

    基变量的检验数是 0 0 0 , 主要是求非基变量的检验数 σ 1 , σ 4 \sigma_1 , \sigma_4 σ1,σ4 ;


    σ 1 = c 1 − ( c 3 a 11 + c 2 a 12 ) \sigma_{1} = c_1 - ( c_3 a_{11} + c_2 a_{12} ) σ1=c1(c3a11+c2a12)

    σ 1 = 3 − ( 0 × 5 3 ) − ( 4 × 1 3 ) = 5 3 \sigma_{1} =3 - (0 \times \dfrac{5}{3}) - (4 \times \dfrac{1}{3}) = \dfrac{5}{3} σ1=3(0×35)(4×31)=35 , 是从下面的单纯形表中的如下位置提取的数值 ;

    在这里插入图片描述


    σ 4 = c 4 − ( c 3 a 41 + c 2 a 42 ) \sigma_{4} = c_4 - ( c_3 a_{41} + c_2 a_{42} ) σ4=c4(c3a41+c2a42)

    σ 4 = 0 − ( 0 × − 1 3 ) − ( 4 × 1 3 ) = − 4 3 \sigma_{4} =0 - (0 \times -\dfrac{1}{3}) - (4 \times \dfrac{1}{3}) = -\dfrac{4}{3} σ4=0(0×31)(4×31)=34 , 是从下面的单纯形表中的如下位置提取的数值 ;

    在这里插入图片描述


    检验数 { σ 1 = 3 − ( 0 × 5 3 ) − ( 4 × 1 3 ) = 5 3 σ 4 = 0 − ( 0 × − 1 3 ) − ( 4 × 1 3 ) = − 4 3 \begin{cases} \sigma_{1} =3 - (0 \times \dfrac{5}{3}) - (4 \times \dfrac{1}{3}) = \dfrac{5}{3} \\\\ \sigma_{4} =0 - (0 \times -\dfrac{1}{3}) - (4 \times \dfrac{1}{3}) = -\dfrac{4}{3} \end{cases} σ1=3(0×35)(4×31)=35σ4=0(0×31)(4×31)=34 , σ 1 \sigma_1 σ1 是大于 0 0 0 的 , 两个检验数必须都小于等于 0 0 0 , 该基可行解才算作是最优解 , 因此 该基可行解不是最优解 ;


    根据检验数选择入基变量 : 继续迭代 , 选择检验数较大的非基变量 , 作为入基变量 , 这里入基变量是 x 1 x_1 x1 ;



    10、第一次迭代 : 根据入基变量计算并选择出基变量


    参考博客 【运筹学】线性规划数学模型 ( 单纯形法 | 迭代原则 | 入基 | 出基 | 线性规划求解示例 ) 五、出基与入基变量选择


    入基变量 根据检验数 σ \sigma σ 选择的是 x 1 x_1 x1 ;


    出基变量是根据 θ \theta θ 值来选择的 , 选择 θ \theta θ 值较小的值对应的基变量作为出基变量 ;


    θ \theta θ 值计算 : 常数列 b = ( 30 10 ) b =\begin{pmatrix} \quad 30 \quad \\ \quad 10 \quad \end{pmatrix} b=(3010) , 分别除以除以入基变量 x 1 x_1 x1 大于 0 0 0 的系数列 ( 5 3 1 3 ) \begin{pmatrix} \quad \dfrac{5}{3} \quad \\\\ \quad \dfrac{1}{3} \quad \end{pmatrix} 3531 , 计算过程如下 ( 30 5 3 10 1 3 ) \begin{pmatrix} \quad \cfrac{30}{\dfrac{5}{3}} \quad \\\\ \quad \cfrac{10}{\dfrac{1}{3}} \quad \end{pmatrix} 35303110 , 得出结果是 ( 18 30 ) \begin{pmatrix} \quad 18 \quad \\\\ \quad 30 \quad \end{pmatrix} 1830 , 然后选择一个最小值 18 18 18 , 查看该最小值对应的变量是 x 3 x_3 x3 , 选择该变量作为出基变量 ;

    在这里插入图片描述


    x 1 x_1 x1 作入基变量 , x 3 x_3 x3 作出基变量 ; 使用 x 1 x_1 x1 替代基变量中 x 3 x_3 x3 的位置 ;

    迭代后的基变量为 x 1 , x 2 x_1 ,x_2 x1,x2 ;


    更新一下单纯形表 :

    c j c_j cj c j c_j cj 3 3 3 4 4 4 0 0 0 0 0 0
    C B C_B CB 基变量系数 (目标函数)基变量常数 b b b x 1 x_1 x1 x 2 x_2 x2 x 3 x_3 x3 x 4 x_4 x4 θ i \theta_i θi
    0 0 0 ( 目标函数 x 3 x_3 x3 系数 c 3 c_3 c3 ) x 3 x_3 x3 40 40 40 2 2 2 1 1 1 1 1 1 0 0 0 40 40 40 ( θ 3 \theta_3 θ3 )
    0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4) x 4 x_4 x4 30 30 30 1 1 1 3 3 3 0 0 0 1 1 1 10 10 10 ( θ 4 \theta_4 θ4 )
    σ j \sigma_j σj 3 3 3 ( σ 1 \sigma_1 σ1 ) 4 4 4 ( σ 2 \sigma_2 σ2 ) 0 0 0 0 0 0
    0 0 0 ( 目标函数 x 3 x_3 x3 系数 c 3 c_3 c3 ) x 3 x_3 x3 30 30 30 5 3 \dfrac{5}{3} 35 0 0 0 1 1 1 − 1 3 -\dfrac{1}{3} 31 18 18 18 ( θ 3 \theta_3 θ3 )
    4 4 4 ( 目标函数 x 2 x_2 x2 系数 c 2 c_2 c2) x 2 x_2 x2 10 10 10 1 3 \dfrac{1}{3} 31 1 1 1 0 0 0 1 3 \dfrac{1}{3} 31 30 30 30 ( θ 2 \theta_2 θ2 )
    σ j \sigma_j σj ( 检验数 ) 5 3 \dfrac{5}{3} 35 ( σ 1 \sigma_1 σ1 ) 0 0 0 0 0 0 − 4 3 -\dfrac{4}{3} 34 ( σ 4 \sigma_4 σ4 )


    11、第二次迭代 : 方程组同解变换



    当前的方程组为 { 5 3 x 1 + 0 x 2 + x 3 − 1 3 x 4 = 30 1 3 x 1 + x 2 + 0 x 3 + 1 3 x 4 = 10 \begin{cases} \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 = 30 \\\\ \dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4 = 10 \end{cases} 35x1+0x2+x331x4=3031x1+x2+0x3+31x4=10 , 选择 x 1 , x 2 x_1, x_2 x1,x2 作为基变量 , 基矩阵为 ( 5 3 0 1 3 1 ) \begin{pmatrix} \quad \dfrac{5}{3} \quad 0 \quad \\\\ \quad \dfrac{1}{3} \quad 1 \quad \end{pmatrix} 350311 , 进行同解变换 , 将基矩阵转为单位阵 ;





    方程 1 1 1 同解变换 :


    5 3 x 1 + 0 x 2 + x 3 − 1 3 x 4 = 30 \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 = 30 35x1+0x2+x331x4=30 方程中的 x 1 x_1 x1 的系数变为 1 1 1 , x 2 x_2 x2 的系数为 0 0 0 保持不变 ;


    方程的左右变量乘以 3 5 \dfrac{3}{5} 53 :

    5 3 x 1 + 0 x 2 + x 3 − 1 3 x 4 = 30 ( 5 3 x 1 + 0 x 2 + x 3 − 1 3 x 4 ) × 3 5 = 30 × 3 5 x 1 + 0 x 2 + 3 5 x 3 − 1 5 x 4 = 18 \begin{array}{lcl} \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 &=& 30 \\\\ ( \dfrac{5}{3} x_1 + 0x_2 + x_3 - \dfrac{1}{3} x_4 ) \times \dfrac{3}{5} &=& 30 \times \dfrac{3}{5} \\\\ x_1 + 0x_2 + \dfrac{3}{5} x_3 - \dfrac{1}{5}x_4 &=& 18 \end{array} 35x1+0x2+x331x4(35x1+0x2+x331x4)×53x1+0x2+53x351x4===3030×5318


    当前方程组变成 { x 1 + 0 x 2 + 3 5 x 3 − 1 5 x 4 = 18 1 3 x 1 + x 2 + 0 x 3 + 1 3 x 4 = 10 \begin{cases} x_1 + 0x_2 + \dfrac{3}{5} x_3 - \dfrac{1}{5}x_4 = 18 \\\\ \dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4 = 10 \end{cases} x1+0x2+53x351x4=1831x1+x2+0x3+31x4=10




    方程 2 2 2 同解变换 : 将方程 1 1 1 乘以 − 1 3 -\dfrac{1}{3} 31 , 与方程 2 2 2 相加 ;


    ① 方程 1 1 1 乘以 − 1 3 -\dfrac{1}{3} 31 :

    ( x 1 + 0 x 2 + 3 5 x 3 − 1 5 x 4 ) × − 1 3 = 18 × − 1 3 − 1 3 x 1 + 0 x 2 + − 1 5 x 3 + 1 15 x 4 = − 6 \begin{array}{lcl} ( x_1 + 0x_2 + \dfrac{3}{5} x_3 - \dfrac{1}{5}x_4 ) \times -\dfrac{1}{3} &=& 18 \times -\dfrac{1}{3} \\\\ -\dfrac{1}{3} x_1 + 0x_2 + -\dfrac{1}{5}x_3 + \dfrac{1}{15} x_4 &=& -6 \end{array} (x1+0x2+53x351x4)×3131x1+0x2+51x3+151x4==18×316

    ② 与方程 2 2 2 相加 :

    ( − 1 3 x 1 + 0 x 2 + − 1 5 x 3 + 1 15 x 4 ) + ( 1 3 x 1 + x 2 + 0 x 3 + 1 3 x 4 ) = − 6 + 10 0 x 1 + x 2 − 1 5 x 3 + 2 5 x 4 = 4 \begin{array}{lcl} (-\dfrac{1}{3} x_1 + 0x_2 + -\dfrac{1}{5}x_3 + \dfrac{1}{15} x_4) + (\dfrac{1}{3}x_1 + x_2 + 0x_3 + \dfrac{1}{3}x_4)&=& -6 + 10 \\\\ 0x_1 + x_2 -\dfrac{1}{5}x_3 + \dfrac{2}{5} x_4 &=& 4 \end{array} (31x1+0x2+51x3+151x4)+(31x1+x2+0x3+31x4)0x1+x251x3+52x4==6+104


    当前方程组变成 { x 1 + 0 x 2 + 3 5 x 3 − 1 5 x 4 = 18 0 x 1 + x 2 − 1 5 x 3 + 6 15 x 4 = 4 \begin{cases} x_1 + 0x_2 + \dfrac{3}{5} x_3 - \dfrac{1}{5}x_4 = 18 \\\\ 0x_1 + x_2 -\dfrac{1}{5}x_3 + \dfrac{6}{15} x_4 = 4 \end{cases} x1+0x2+53x351x4=180x1+x251x3+156x4=4



    12、第二次迭代 : 生成新的单纯形表



    更新一下单纯形表 : 将第三次迭代的矩阵填入下面的单纯形表中 ;

    c j c_j cj c j c_j cj 3 3 3 4 4 4 0 0 0 0 0 0
    C B C_B CB 基变量系数 (目标函数)基变量常数 b b b x 1 x_1 x1 x 2 x_2 x2 x 3 x_3 x3 x 4 x_4 x4 θ i \theta_i θi
    0 0 0 ( 目标函数 x 3 x_3 x3 系数 c 3 c_3 c3 ) x 3 x_3 x3 40 40 40 2 2 2 1 1 1 1 1 1 0 0 0 40 40 40 ( θ 3 \theta_3 θ3 )
    0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4) x 4 x_4 x4 30 30 30 1 1 1 3 3 3 0 0 0 1 1 1 10 10 10 ( θ 4 \theta_4 θ4 )
    σ j \sigma_j σj 3 3 3 ( σ 1 \sigma_1 σ1 ) 4 4 4 ( σ 2 \sigma_2 σ2 ) 0 0 0 0 0 0
    第一次迭代
    0 0 0 ( 目标函数 x 3 x_3 x3 系数 c 3 c_3 c3 ) x 3 x_3 x3 30 30 30 5 3 \dfrac{5}{3} 35 0 0 0 1 1 1 − 1 3 -\dfrac{1}{3} 31 18 18 18 ( θ 3 \theta_3 θ3 )
    4 4 4 ( 目标函数 x 2 x_2 x2 系数 c 2 c_2 c2) x 2 x_2 x2 10 10 10 1 3 \dfrac{1}{3} 31 1 1 1 0 0 0 1 3 \dfrac{1}{3} 31 30 30 30 ( θ 2 \theta_2 θ2 )
    σ j \sigma_j σj ( 检验数 ) 5 3 \dfrac{5}{3} 35 ( σ 1 \sigma_1 σ1 ) 0 0 0 0 0 0 − 4 3 -\dfrac{4}{3} 34 ( σ 4 \sigma_4 σ4 )
    第二次迭代
    3 3 3 ( 目标函数 x 1 x_1 x1 系数 c 1 c_1 c1 ) x 1 x_1 x1 18 18 18 1 1 1 0 0 0 3 5 \dfrac{3}{5} 53 − 1 5 -\dfrac{1}{5} 51 ? ? ? ( θ 3 \theta_3 θ3 )
    4 4 4 ( 目标函数 x 2 x_2 x2 系数 c 2 c_2 c2) x 2 x_2 x2 4 4 4 0 0 0 1 1 1 − 1 5 -\dfrac{1}{5} 51 2 5 \dfrac{2}{5} 52 ? ? ? ( θ 2 \theta_2 θ2 )
    σ j \sigma_j σj ( 检验数 ) 0 0 0 0 0 0 ? ? ? ( σ 3 \sigma_3 σ3 ) ? ? ? ( σ 4 \sigma_4 σ4 )


    13、第二次迭代 : 计算检验数、最优解判定



    计算检验数 σ \sigma σ :

    σ 3 = 0 − 3 × 3 5 − 4 × ( − 1 5 ) = − 9 5 + 4 5 = − 1 \sigma_3 = 0 - 3 \times \dfrac{3}{5} - 4 \times (-\dfrac{1}{5}) = -\dfrac{9}{5} + \dfrac{4}{5} = -1 σ3=03×534×(51)=59+54=1


    σ 4 = 0 − 3 × ( − 1 5 ) − 4 × 2 5 = 3 5 − 8 5 = − 1 \sigma_4 = 0 - 3 \times (-\dfrac{1}{5}) - 4 \times \dfrac{2}{5} = \dfrac{3}{5} - \dfrac{8}{5} = -1 σ4=03×(51)4×52=5358=1


    两个非基变量的检验数都是小于等于 0 0 0 , 因此该基可行解 ( 18 4 0 0 ) \begin{pmatrix} \quad 18 \quad \\ \quad 4 \quad \\ \quad 0 \quad \\ \quad 0 \quad \end{pmatrix} 18400是最优解 ;





    四、单纯形法案例二





    1、线性规划示例


    线性规划示例 : 使用单纯形法求解下面的线性规划 ;

    m a x Z = x 1 + 2 x 2 + x 3 s . t { 2 x 1 − 3 x 2 + 2 x 3 ≤ 15 1 3 x 1 + x 2 + 5 x 3 ≤ 20 x j ≥ 0 ( j = 1 , 2 , 3 ) \begin{array}{lcl} max Z = x_1 + 2x_2 + x_3 \\ \\ s.t\begin{cases} 2 x_1 - 3x_2 + 2x_3 \leq 15 \\\\ \dfrac{1}{3}x_1 + x_2 + 5x_3 \leq 20 \\ \\x_j \geq 0 & (j = 1 , 2 , 3 ) \end{cases}\end{array} maxZ=x1+2x2+x3s.t2x13x2+2x31531x1+x2+5x320xj0(j=1,2,3)



    2、转化成标准形式


    首先将现行规划转化成标准形式 :

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


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



    2 . 将不等式转为等式 : 两个不等式都是小于等于不等式 , 在左侧加入松弛变量即可 ;


    ① 添加松弛变量 : 上述两个不等式 { 2 x 1 − 3 x 2 + 2 x 3 ≤ 15 1 3 x 1 + x 2 + 5 x 3 ≤ 20 \begin{cases} 2 x_1 - 3x_2 + 2x_3 \leq 15 \\\\ \dfrac{1}{3}x_1 + x_2 + 5x_3 \leq 20 \end{cases} 2x13x2+2x31531x1+x2+5x320 , 在左侧分别添加 x 4 , x 5 x_4 , x_5 x4,x5 松弛变量 ;


    ② 最终结果 : 转化后的结果是 { 2 x 1 − 3 x 2 + 2 x 3 + x 4 = 15 1 3 x 1 + x 2 + 5 x 3 + x 5 = 20 x j ≥ 0 ( j = 1 , 2 , 3 , 4 , 5 ) \begin{cases} 2 x_1 - 3x_2 + 2x_3 + x_4 = 15 \\\\ \dfrac{1}{3}x_1 + x_2 + 5x_3 + x_5 = 20 \\ \\x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 ) \end{cases} 2x13x2+2x3+x4=1531x1+x2+5x3+x5=20xj0(j=1,2,3,4,5)



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



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

    m a x Z = x 1 + 2 x 2 + x 3 + 0 x 4 + 0 x 5 s . t { 2 x 1 − 3 x 2 + 2 x 3 + x 4 + 0 x 5 = 15 1 3 x 1 + x 2 + 5 x 3 + 0 x 4 + x 5 = 20 x j ≥ 0 ( j = 1 , 2 , 3 , 4 , 5 ) \begin{array}{lcl} max Z = x_1 + 2x_2 + x_3 + 0x_4 + 0x_5 \\ \\ s.t\begin{cases} 2 x_1 - 3x_2 + 2x_3 + x_4 + 0x_5 = 15 \\\\ \dfrac{1}{3}x_1 + x_2 + 5x_3 + 0x_4 + x_5 = 20 \\ \\x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 ) \end{cases}\end{array} maxZ=x1+2x2+x3+0x4+0x5s.t2x13x2+2x3+x4+0x5=1531x1+x2+5x3+0x4+x5=20xj0(j=1,2,3,4,5)



    3、初始基可行解


    找初始基可行解 :


    ① 查找单位阵 : 该线性规划标准形的系数矩阵中 , x 4 , x 5 x_4 , x_5 x4,x5 的系数矩阵是 ( 1 0 0 1 ) \begin{pmatrix} \quad 1 \quad 0 \quad \\ \quad 0 \quad 1 \quad \\ \end{pmatrix} (1001) , 该矩阵是单位阵 ;

    ② 可行基 : 选择该矩阵作为可行基 ;

    ③ 初始基可行解 : 其对应的解是基可行解 ( 0 0 0 15 20 ) \begin{pmatrix} \quad 0 \quad \\ \quad 0 \quad \\ \quad 0 \quad \\ \quad 15 \quad \\ \quad 20 \quad \\ \end{pmatrix} 0001520 ;



    ## 4、列出单纯形表

    m a x Z = x 1 + 2 x 2 + x 3 + 0 x 4 + 0 x 5 s . t { 2 x 1 − 3 x 2 + 2 x 3 + x 4 + 0 x 5 = 15 1 3 x 1 + x 2 + 5 x 3 + 0 x 4 + x 5 = 20 x j ≥ 0 ( j = 1 , 2 , 3 , 4 , 5 ) \begin{array}{lcl} max Z = x_1 + 2x_2 + x_3 + 0x_4 + 0x_5 \\ \\ s.t\begin{cases} 2 x_1 - 3x_2 + 2x_3 + x_4 + 0x_5 = 15 \\\\ \dfrac{1}{3}x_1 + x_2 + 5x_3 + 0x_4 + x_5 = 20 \\ \\x_j \geq 0 \quad (j = 1 , 2 , 3, 4, 5 ) \end{cases}\end{array} maxZ=x1+2x2+x3+0x4+0x5s.t2x13x2+2x3+x4+0x5=1531x1+x2+5x3+0x4+x5=20xj0(j=1,2,3,4,5)


    c j c_j cj c j c_j cj 1 1 1 2 2 2 1 1 1 0 0 0 0 0 0
    C B C_B CB 基变量系数 (目标函数)基变量常数 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 θ i \theta_i θi
    0 0 0 ( 目标函数 x 4 x_4 x4 系数 c 4 c_4 c4 ) x 4 x_4 x4 15 15 15 2 2 2 − 1 -1 1 2 2 2 1 1 1 0 0 0 − -
    0 0 0 ( 目标函数 x 5 x_5 x5 系数 c 5 c_5 c5) x 5 x_5 x5 20 20 20 1 3 \dfrac{1}{3} 31 1 1 1 5 5 5 0 0 0 1 1 1 20 20 20
    σ j \sigma_j σj ( 检验数 ) 1 1 1 ( σ 1 \sigma_1 σ1 ) 2 2 2 ( σ 2 \sigma_2 σ2 ) 1 1 1 ( σ 3 \sigma_3 σ3 ) 0 0 0 0 0 0


    5、计算检验数


    计算非基变量的检验数 :

    单个检验数计算公式 : σ j = c j − ∑ c i a i j \sigma_j = c_j - \sum c_i a_{ij} σj=cjciaij , 其中 c j c_j cj 是对应目标函数非基变量系数 , c i c_i ci 是目标函数中基变量系数 , a i j a_{ij} aij 是系数矩阵中对应的 x j x_j xj 非基变量列向量 ;


    σ 1 \sigma_1 σ1 检验数计算 : σ 1 = 1 − ( 0 × 2 + 0 × 1 3 ) = 1 \sigma_1 = 1 - ( 0 \times 2 + 0 \times \dfrac{1}{3} ) = 1 σ1=1(0×2+0×31)=1

    在这里插入图片描述
    σ 2 \sigma_2 σ2 检验数计算 : σ 2 = 2 − ( 0 × ( − 1 ) + 0 × 1 ) = 2 \sigma_2 = 2 - ( 0 \times (-1) + 0 \times 1 ) = 2 σ2=2(0×(1)+0×1)=2
    在这里插入图片描述

    σ 1 3 \sigma_13 σ13 检验数计算 : σ 3 = 1 − ( 0 × 2 + 0 × 5 ) = 1 \sigma_3 = 1 - ( 0 \times 2 + 0 \times 5 ) = 1 σ3=1(0×2+0×5)=1

    在这里插入图片描述



    6、选择入基变量与出基变量


    入基变量选择 : 选择检验数 σ j \sigma_j σj 较大的非基变量作为入基变量 , x 2 x_2 x2 ;


    出基变量是根据 θ \theta θ 值来选择的 , 选择 θ \theta θ 值较小的值对应的基变量作为出基变量 ;


    出基变量选择 : 常数列 b = ( 15 20 ) b =\begin{pmatrix} \quad 15 \quad \\ \quad 20 \quad \end{pmatrix} b=(1520) , 分别除以除以入基变量 x 2 x_2 x2 大于 0 0 0 的系数列 ( − 1 1 ) \begin{pmatrix} \quad -1 \quad \\\\ \quad 1 \quad \end{pmatrix} 11 , 计算过程如下 ( 系 数 小 于 0 不 计 算 20 1 ) \begin{pmatrix} \quad 系数小于0 不计算 \quad \\\\ \quad \cfrac{20}{1} \quad \end{pmatrix} 0120 , 得出结果是 ( 无 效 值 20 ) \begin{pmatrix} \quad 无效值 \quad \\\\ \quad 20 \quad \end{pmatrix} 20 , 如果系数小于等于 0 0 0 , 该值就是无效值 , 默认为无穷大 , 不进行比较 , 选择 20 20 20 对应的基变量作为出基变量 , 查看该最小值对应的变量是 x 5 x_5 x5 , 选择该 x 5 x_5 x5 变量作为出基变量 ;

    在这里插入图片描述



    7、第一次迭代 : 列出单纯形表


    上述已经得到 x 2 x_2 x2 作为入基变量 , 由非基变量转为基变量 , x 5 x_5 x5 作为出基变量 , 由基变量转为非基变量 ; 使用 x 2 x_2 x2 , 替换基变量中的 x 5 x_5 x5 的位置 ;

    基变量为 x 4 , x 2 x_4 , x_2 x4,x2 , 注意顺序不要写反 ;


    c j c_j cj c j c_j cj 1 1 1 2 2 2 1 1 1 0 0 0 0 0 0
    C B C_B CB 基变量系数 (目标函数)基变量常数 b b b x 1 x_1 x1 x 2 x_2 x2 x 3 x_3 x3 x 4 x_4