【运筹学】线性规划数学模型 ( 单纯形法 | 迭代原则 | 入基 | 出基 | 线性规划求解示例 )

2023-03-28 16:23:00 浏览数 (1)

文章目录

  • 一、单纯形法计算示例 ( 上篇博客回顾总结 )
  • 二、迭代原则
  • 三、最优解推导
  • 四、出基与入基
  • 五、出基与入基变量选择

一、单纯形法计算示例 ( 上篇博客回顾总结 )

在上一篇博客 【运筹学】线性规划数学模型 ( 单纯形法 | 最优解判定原则 | 线性规划求解示例 ) 博客给出了一个线性规划的示例 , 并进行了 查找初始基可行解 , 和 判定该基可行解是否是最优解 ;

在目标函数中 , 将基可行解代入目标函数中

  • 不是最优解情况 : 非基变量的系数都是大于
0

的数值 , 该基可行解不是最优解 ;

  • 是最优解情况 : 只有当 非基变量的系数都是小于等于
0

的数时 , 该基可行解才是最优解 ;

线性规划标准形式为 :

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}

单纯形表 :

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

c_j
c_j
3
4
0
0
C_B

基变量系数 (目标函数)基变量常数

b
x_1
x_2
x_3
x_4
theta_i
0

( 目标函数

x_3

系数

c_3

)

x_3
40
2
1
1
0
0

( 目标函数

x_4

系数

c_4

)

x_4
30
1
3
0
1
sigma_j
3
4
0
0

选择

begin{bmatrix} &1 & 0 & \\ &0 & 1 & end{bmatrix}

作为基矩阵 , 基变量是

x_3

,

x_4

, 初始基可行解是

begin{pmatrix} quad 0 quad \ quad 0 quad \ quad 40 quad \ quad 30 quad \ end{pmatrix}

, 经过计算 , 其目标函数中

x_1

的系数是

3

,

x_2

的系数是

4

, 都是大于

0

的数 , 该基可行解不是基解 , 继续向下迭代 ;

二、迭代原则

上述解出的基可行解

begin{pmatrix} quad 0 quad \ quad 0 quad \ quad 40 quad \ quad 30 quad \ end{pmatrix}

不是最优解 , 那么 需要迭代下一个基可行解 , 下面开始讲解 , 如何进行迭代 ;

上述的解中 , 非基变量

x_1

和

x_2

取

0

不是最好的选择 , 那么 这两个变量最好取非

0

的值 , 求解线性规划的思路是 :

  • 在无穷多个可行解中迭代 , 得到最优解 ;
  • 上述思路可以转化成在有限个基可行解中迭代 , 得到最优解 ;
  • 无限 -> 有限 : 可行解 是无限个的 , 基可行解 是有限个 ;

三、最优解推导

x_1 , x_2

取值为

0

不是最优解 , 约束条件要求这两个变量必须大于等于

0
x_j geq 0 (j = 1 , 2 , 3 , 4 )

, 那么只能取值大于

0

, 下面讨论这两个变量取值大于

0

的情况 ;

x_1

的系数是

3

,

x_2

的系数是

4

, 如果

x_3 , x_4

取

0

, 目标函数

maxZ = 0 3x_1 4x_2

, 将

x_1 , x_2

任意一个增大 , 其目标函数的值都会增大 ;

  • 增大
x_2

: 此时可以选择将

x_2

增大 ,

x_2

增加

1

, 目标函数就会增加

4

;

  • 增大
x_1

: 也可以选择将

x_1

增大 ,

x_1

增加

1

, 目标函数就会增加

3

, 只要是目标函数随变量增加而增加即可 ;

增大

x_2

,

x_2

不能无限增大 , 其需要受到

begin{cases} 2 x_1 x_2 x_3 0x_4 = 40 \\ x_1 3x_2 0x_3 x_4 = 30 end{cases}

约束方程约束 ,

  • 受第一个方程约束 , 增大
x_2

, 最多是

x_1, x_3, x_4

都取值

0

,

x_2

理论上最大值时

40

;

  • 受第一个方程约束 , 增大
x_2

, 最多是

x_1, x_3, x_4

都取值

0

,

x_2

理论上最大值时

10

;

x_2

最大就能取值到

10

, 否则无法满足第二个约束方程 , 如果

x_2

取

40

, 那么在第二个方程中 , 就会出现有变量为负数 , 就不符合约束条件了 , 因此

x_2

最大只能取到

10

;

那么开始增加

x_2

的值 , 目标函数

maxZ = 0 3x_1 4x_2

, 增大

x_2

, 如果

x_2

从

0

增加到

10

, 目标函数可以增加

40

,

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

4 4 4

0 0 0

0 0 0

c_j
c_j
3
4
0
0
C_B

基变量系数 (目标函数)基变量常数

b
x_1
x_2
x_3
x_4
theta_i
0

( 目标函数

x_3

系数

c_3

)

x_3
40
2
1
1
0
40

(

theta_3

)

0

( 目标函数

x_4

系数

c_4

)

x_4
30
1
3
0
1
10

(

theta_4

)

sigma_j
3
4
0
0

四、出基与入基

基可行解 : 选择可行基 , 自然会产生基变量 ( 可行基对应变量 ) , 与非基变量 , 非基变量取值为

0

, 解出基变量 , 此时基变量的解与

0

组合成基可行解 ;

上一次的初始基可行解选择时 ,

x_3

和

x_4

是基变量 ,

x_1

和

x_2

是非基变量 , 非基变量取值必须为

0

;

如果

x_2

变成了非

0

取值 , 此时就需要将

x_2

设置成基变量 ;

基变量的个数是固定的 , 本示例中是

2

个 , 如果将

x_2

设置成基变量 , 那么就需要将之前的

x_3

和

x_4

中其中一个基变量替换成

x_2

, 被替换的基变量变成非基变量 ;

因此该迭代的过程又称为出基 , 入基过程 ;

  • 出基 :
x_3 , x_4

有一个变量设置成非基变量 , 称为出基 ;

  • 入基 :
x_2

设置成基变量 , 称为入基 ;

五、出基与入基变量选择

入基变量选择 : 具体哪个变量入基 , 是由检验数决定的 , 检验数

sigma_j

较大的入基 ;

x_2

的检验数

sigma_2

是

4

, 大于

sigma_1 = 3

, 因此这里选择

x_2

作为入基变量 ;

出基变量选择 : 系数矩阵中 , 常数列

b =begin{pmatrix} quad 40 quad \ quad 30 quad end{pmatrix}

, 分别除以除以入基变量大于

0

的系数列

begin{pmatrix} quad 1 quad \ quad 3 quad end{pmatrix}

, 得出结果是

begin{pmatrix} quad 40 quad \ quad 10 quad end{pmatrix}

, 然后选择一个最小值

10

, 查看该最小值对应的变量是

x_4

, 选择该变量作为出基变量 ;

这里将出基变量与入基变量选择好了 ,

x_2

的检验数较大 , 选择

x_2

作为入基变量 ,

x_4

的

theta_4

较小 , 选择

x_4

作为出基变量 ;

入基出基操作完成后 , 基变量变成了

x_3, x_2

;

变量 博客 函数

0 人点赞