第五章 线性规划方法 Linear Programming

【资料图】

5.1 线性规划问题的一般形式5.2 线性规划问题的解5.2.1 基本解的产生与转换5.2.2 基本可行解的产生与转换5.2.3 基本可行解的变换条件1. 最优性条件2. 非负性条件 5.3 单纯形算法 The Simplex Method

5.1 线性规划问题的一般形式

5.2 线性规划问题的解

基本解：只满足约束方程的解。 基本可行解：同时满足约束方程和变量非负约束的解。 最优解：使目标函数取得最小值的基本可行解。

5.2.1 基本解的产生与转换

线性规划问题的约束方程实际上是一个包括n个变量和m个方程（n>m）的线性方程组，由于变量个数多于方程数，故有多个满足方程的解。 若取n-m个变量并令其等于0，解出另外的m个不为0的变量，就可得到一个基本解。 在这样的基本解中，称n-m个为0的变量为非基本变量，另外的m个变量为基本变量。

5.2.2 基本可行解的产生与转换

根据线性规划问题的不同特征，一个初始基本可行解的获得可分为以下两种情况：

如果除变量非负约束之外的约束条件全是“ ≤ \leq ≤”的不等式约束，而且对应的常数向量中的元素均为正数，此时只要引入松弛变量，并以松弛变量为基本变量，得到的解就是一个基本可行解。如果除变量非负约束之外的约束条件中还包含等式约束，此时可以在各个等式约束中分别引进一个与松弛变量类似的变量，称为人工变量，然后建立一个辅助规划问题求解此辅助规划问题，就可以得到一个基本可行解。

5.2.3 基本可行解的变换条件

1. 最优性条件

2. 非负性条件

5.3 单纯形算法 The Simplex Method

SIMPLEXTABLEx 1    x 2    ⋯    x n x_1 \ \ x_2 \ \ \cdots \ \ x_n x1  x2  ⋯  xnx n + 1    x n + 2    ⋯    x n + m x_{n+1}\ \ x_{n+2}\ \ \cdots\ \ x_{n+m} xn+1  xn+2  ⋯  xn+mb i b_i bi

Basic VariableCoefficientsc 1      c 2    ⋯    c n c_1\ \ \ \ c_2\ \ \cdots\ \ c_n c1    c2  ⋯  cn0              0      ⋯      0 0 \ \ \ \ \ \ \ \ \ \ \ \ 0\ \ \ \ \cdots \ \ \ \ 0 0            0    ⋯    0c 0 c_0 c0

x n + 1 x_{n+1} xn+10a 11    a 12 ⋯ a 1 n a_{11} \ \ a_{12} \cdots a_{1n} a11  a12⋯a1n1              0      ⋯      0 1 \ \ \ \ \ \ \ \ \ \ \ \ 0 \ \ \ \ \cdots \ \ \ \ 0 1            0    ⋯    0b n + 1 b_{n+1} bn+1

x n + 2 x_{n+2} xn+20a 11    a 12 ⋯ a 1 n a_{11} \ \ a_{12} \cdots a_{1n} a11  a12⋯a1n0              1      ⋯      0 0 \ \ \ \ \ \ \ \ \ \ \ \ 1\ \ \ \ \cdots\ \ \ \ 0 0            1    ⋯    0b n + 1 b_{n+1} bn+1

⋮ \vdots ⋮⋮ \vdots ⋮⋮          ⋮              ⋮ \vdots\ \ \ \ \ \ \ \ \vdots \ \ \ \ \ \ \ \ \ \ \ \ \vdots ⋮        ⋮            ⋮0              0      ⋯      0 0 \ \ \ \ \ \ \ \ \ \ \ \ 0\ \ \ \ \cdots\ \ \ \ 0 0            0    ⋯    0⋮ \vdots ⋮

x n + m x_{n+m} xn+m0a 11    a 12 ⋯ a 1 n a_{11}\ \ a_{12} \cdots a_{1n} a11  a12⋯a1n0              0      ⋯      1 0 \ \ \ \ \ \ \ \ \ \ \ \ 0\ \ \ \ \cdots\ \ \ \ 1 0            0    ⋯    1b n + 1 b_{n+1} bn+1

Judgementnumber σ j \sigma_j σjσ 1     σ 2    ⋯ σ n \sigma_1 \ \ \ \sigma_2 \ \ \cdots \sigma_n σ1   σ2  ⋯σn0              0      ⋯      1 0 \ \ \ \ \ \ \ \ \ \ \ \ 0\ \ \ \ \cdots\ \ \ \ 1 0            0    ⋯    1f ( X ) f(X) f(X)

单纯形表法的计算步骤：

给定一个初始基本可行解 X 0 X^0 X0，并置k=0；计算判别数： σ j = c j − ∑ i = 1 m c i a i j         ( j = 1 , 2 , ⋯   , n ) \sigma_j=c_j-\sum^m_{i=1}c_ia_{ij} \ \ \ \ \ \ \ (j=1,2,\cdots,n) σj=cj−i=1∑mciaij       (j=1,2,⋯,n) 若 σ j ≥ 0 ( j = 1 , 2 , ⋯   , n ) \sigma_j\geq 0(j=1,2,\cdots,n) σj≥0(j=1,2,⋯,n)，令 X ∗ = X k ,   f ( X ∗ ) = f ( X k ) X^*=X^k,\ f(X^*)=f(X^k) X∗=Xk, f(X∗)=f(Xk)，结束计算；否则转步骤3;选主元 a l k a_{lk} alk σ k = m i n { σ j ∣ σ j < 0 , j = 1 , 2 , ⋯   , n } b l a l k = m i n { b i a i k ∣ a i k > 0   ( i = 1 , 2 , ⋯   , m ) } \sigma_k=min \{\sigma_j|\sigma_j<0,j=1,2,\cdots,n\} min="">0 \ (i=1,2,\cdots,m)\} σk=min{σj∣σj<0,j=1,2,⋯,n}alkbl=min{aikbi∣aik>0 (i=1,2,⋯,m)}以 a l k a_{lk} alk为主元进行消元变换，得到新的基本可行解 X k + 1 X^{k+1} Xk+1，令k=k+1，转步骤2。

其中，判别式： σ j = c j − ∑ i = 1 m c i a i j         ( j = 1 , 2 , ⋯   , n ) \sigma_j=c_j-\sum^m_{i=1}c_ia_{ij} \ \ \ \ \ \ \ (j=1,2,\cdots,n) σj=cj−i=1∑mciaij       (j=1,2,⋯,n) i代表行 j代表列（基本变量对应的各列判别式为0，非基本变量对应的各列判别式等于该列顶端的系数减去各列中各个系数 a i j a_{ij} aij与左侧系数 c i c_{i} ci的乘积 ）