[最优化理论与技术]线性规划

线性规划

线性规划

线性规划的标准型

线性规划模型 ( LP )

一组决策变量
一个线性目标函数
一组线性约束条件

一般形式：

[min (max ) sum_{i=1}^{n} c_{i} x_{i} \ s.t.left{egin{array}{c}{a_{11} x_{1}+a_{12} x_{2}+cdots+a_{1 n} x_{n} geq(=, leq) b_{1}} \ {a_{21} x_{1}+a_{22} x_{2}+cdots+a_{2 n} x_{n} geq(=, leq) b_{2}} \ {cdots} \ {a_{m 1} x_{1}+a_{m 2} x_{2}+cdots+a_{m n} x_{n} geq(=, leq) b_{m}} \ {x_{i} geq(=, leq) 0, i=1,2, cdots, n}end{array} ight. ]

标准型：

[max sum_{i=1}^{n} c_{i} x_{i} quad ext { s.t. }left{egin{array}{c}{a_{11} x_{1}+a_{12} x_{2}+cdots+a_{1 n} x_{n}=b_{1}} \ {a_{21} x_{1}+a_{22} x_{2}+cdots+a_{2 n} x_{n}=b_{2}} \ {cdots} \ {x_{i} geq 0, i=1,2, cdots, n}end{array} ight. ]

其中，记 (c=left(c_{1}, c_{2}, cdots, c_{n} ight)^{T}, b=left(b_{1}, b_{2}, cdots, b_{m} ight)^{T}, x=left(x_{1}, x_{2}, cdots, x_{n} ight)^{T},oldsymbol{A}=left(a_{i j} ight)_{m imes n})，则线性规划标准型记为

[egin{array}{l}{max quad c^{T} x} \ { ext { s.t. }left{egin{array}{l}{A x=b} \ {x geq 0}end{array} ight.}end{array} ]

化标准型

目标函数

原问题目标函数：(min quad c^{T} x quad Rightarrow max quad-c^{T} x)
约束条件
- 原问题条件：(a_{i 1} x_{1}+a_{i 2} x_{2}+cdots+a_{i n} x_{n} leq b_{i})
  
  (Rightarrowleft{egin{array}{c}{a_{i 1} x_{1}+a_{i 2} x_{2}+cdots+a_{i n} x_{n}+x_{n+i}=b_{i}} \ {x_{n+i} geq 0}end{array} ight.)，(x_{n+i}) 称为松弛变量
- 原问题条件：(a_{i 1} x_{1}+a_{i 2} x_{2}+cdots+a_{i n} x_{n} geq b_{i})
  
  (Rightarrowleft{egin{array}{c}{a_{i 1} x_{1}+a_{i 2} x_{2}+cdots+a_{i n} x_{n}-x_{n+i}=b_{i}} \ {x_{n+i} geq 0}end{array} ight.)，(x_{n+i}) 称为剩余变量
- 原问题：(x_i) 无非负约束，则令(left{egin{aligned} oldsymbol{x}_{i} &=oldsymbol{u}_{i}-oldsymbol{v}_{i} \ oldsymbol{u}_{i}, oldsymbol{v}_{i} & geq mathbf{0} end{aligned} ight.)

图解法

画出可行域范围
利用等值线平移方法求极值点

线性规划解的概念和性质

[egin{array}{c}{(L P) quad max quad z=c^{T} x quad(1)} \ { ext { s.t. }left{egin{array}{cc}{A x=b} & { ext { (2) }} \ {x geq 0} & { ext { (3) }}end{array} ight.}end{array} ]

可行解：满足 (2)(3) 式的解 (x=(x_1,x_2,...,x_n)^T) 称为 ((LP)) 的可行解

可行域：(D={x | A x=b, x geq 0})

线性规划问题的可行域 (D) 是凸集

线性规划解的概念

基：设 (A) 为 (m imes n) 的系数矩阵，秩为 (m) 。若 (B) 为 (A) 中 (m imes m) 阶的非退化子阵，则称 (B) 为 (A) 的 (或 ((LP )) 问题) 一个基。

非退化子阵：又称 “非异矩阵”、“满秩矩阵”，矩阵行列式 (|A| e0)。(n) 阶方阵 (A) 是非退化的充要条件为 (A) 是可逆矩阵。

基向量：设基 (oldsymbol{B}=left(oldsymbol{P}_{i 1}, oldsymbol{P}_{i 2}, cdots, oldsymbol{P}_{i m} ight))，称 (left(oldsymbol{P}_{i 1}, oldsymbol{P}_{i 2}, cdots, oldsymbol{P}_{i m} ight)) 为基向量。

基变量：(oldsymbol{P}_{i m})对应的变量 (x_m)，不是基变量的变量称为非基变量。

基本解：取线性规划的基 (B)，令非基变量取0，(left(B^{-1} b, 0 ight)^{T}) 为对应于基 (B) 的基本解。

基本可行解：满足线性规划 ((LP)) 问题条件(3) 的基本解为基本可行解。

线性规划 ((LP)) 问题的解 (x) 是基本可行解的充要条件是 (x) 是可行域 (D) 的顶点

单纯形法

算法思路

从一个基本可行解开始，判断其是否为最优解，若不是则跳到下一个基本可行解，直到找到最优解。

如何得到第一个基本可行解
如何判断是否是最优解
如何从一个基本可行解变换到另一个基本可行解

初始基本可行解

大 (M) 法：增加人工变量使得 (z=sum_{i=1}^{n} c_{i} x_{i}-M x_{n+1}-cdots-M x_{n+m})，取 (oldsymbol{x}_{n+1}, cdots, oldsymbol{x}_{n+m}) 为初始基变量。

最优解判定条件

[(oldsymbol{L P}) max z=sum_{i=1}^{n} c_{i} oldsymbol{x}_{i} quad ext { s.t. }left{egin{array}{c}{a_{11} x_{1}+a_{12} x_{2}+cdots+a_{1 n} x_{n}=b_{1}} \ {a_{21} x_{1}+a_{22} x_{2}+cdots+a_{2 n} x_{n}=b_{2}} \ {cdots} \ {a_{m 1} x_{1}+a_{m 2} x_{2}+cdots+a_{m n} x_{n}=b_{m}} \ {x_{i} geq 0, i=1,2, cdots, n}end{array} ight. ]

设经过迭代后有

[left{egin{array}{l}{x_{1}=b_{1}^{prime}-sum_{j=m+1}^{n} a_{1 j}^{prime} x_{j}} \ vdots\{x_{m}=b_{m}^{prime}-sum_{j=m+1}^{n} a_{m j}^{prime} x_{j}}end{array} ight.(1) ]

则 (x_1,...,x_m) 为基变量，(x_{m+1},...,x_n) 为非基变量。

代入目标函数有

[z=sum_{i=1}^{m} c_{i} b_{i}^{prime}+sum_{j=m+1}^{n}left(c_{j}-sum_{i=1}^{m} c_{i} a_{i j}^{prime} ight) x_{j} ]

令 (z_0=sum_{i=1}^{m} c_{i} b_{i}^{prime})，(sigma_j=c_{j}-sum_{i=1}^{m} c_{i} a_{i j}^{prime})，则

[z=z_{0}+sum_{j=m+1}^{n} sigma_{j} x_{j} ]

称 (sigma_j) 为检验函数。

若 (x^*=(b_1^*,...,b_m^*,0,...,0)^T) 是对应于基 (B) 的一个基本可行解，且对任意 (m+1 le j le n)，有 (sigma_j le 0)，则 (x^*) 是最优解。
若 (x^*=(b_1^*,...,b_m^*,0,...,0)^T) 是对应于基 (B) 的一个基本可行解，且对任意 (m+1 le j le n)，有 (sigma_j le 0)，且存在 (sigma_{m+k}=0(k ge 0)) ，则线性规划问题有无穷多最优解。

单纯形表

根据上节，将线性规划问题 ((LP)) ，改写成

[(L P) quad max quad z=z_{0}+sum_{i=m+1}^{n} sigma_{i} x_{i} ]

[ ext { s.t. }left{egin{aligned} x_{1}+a_{1, m+1} x_{m+1}+cdots+a_{1 n} x_{n} &=b_{1} \ x_{2}+a_{2, m+1} x_{m+1}+cdots+a_{2 n} x_{n} &=b_{2} \ x_{m}+a_{m, m+1} x_{m+1}+cdots+a_{m n} x_{n} &=b_{m} \ x_{i} geq 0, i =1,2, cdots, n end{aligned} ight. ]

则单纯形表为

(x_ 1)	(x_2)		(x_ m)	(x_ {m+1})		(x_n)	(b)
1	0	(cdots)	0	(a_{1,m+1})	$cdots $	(a_{1n})	(b_1)
0	1	(cdots)	0	(a_{2,m+1})	(cdots)	(a_{2n})	(b_2)
$vdots $	(vdots)		(vdots)		(vdots)	(vdots)	$vdots $
0	0	(cdots)	1	(a_{m,m+1})	(cdots)	(a_{mn})	(b_m)
0	0	$ cdots $	0	(sigma_{m+1})	$ cdots$	(sigma_n)	(-z_0)

包含一个单位子矩阵作为基矩阵，它所对应的变量是基变量
最后一行称为检验数行，其中基变量的检验数为0
最后一列的元素对应当前基变量的取值
第 (m+1) 行、第 (n+1) 列的元素 (-z_0) ，表示当前基本可行解对应的目标函数值的相反数

基变换

入基变量：可选取最大的 (sigma_j) 对应的变量作为入基变量

离基变量：设入基变量 (x_k)，由(1)式计算

[oldsymbol{ heta}=min left{frac{oldsymbol{b}_{i}^{prime}}{oldsymbol{a}_{i k}^{prime}} | oldsymbol{a}_{i k}^{prime}>oldsymbol{0} ight} :=frac{oldsymbol{b}_{l}^{prime}}{oldsymbol{a}_{l k}^{prime}} ]

用 (x:=y) 表示命题 (x) 定义为等于 (y)
结合(1)式计算需注意，(a_{lk}) 前面符号是减号

({x_{m}=b_{m}^{prime}-sum_{j=m+1}^{n} a_{m j}^{prime} x_{j}})

选取 (x_l) 为离基变量。

单纯性法算法步骤

确定初始基本可行解，建立初始单纯形表
看检验数，若 (sigma_j le 0(j=m+1,..,n)) 则当前基本可行解就是最优解，算法结束。否则转(3)
若存在 (sigma_k>0) 使得其对应的变量 (x_k) 的系数列向量 (P_kle0)，则线性规划问题的解无界，算法结束。否则转(4)
设 (max left(sigma_{j}>0 ight)=sigma_{k})，选取 (x_k) 为入基变量。计算

[oldsymbol{ heta}=min left{frac{oldsymbol{b}_{i}}{oldsymbol{a}_{i k}} | oldsymbol{a}_{i k}>oldsymbol{0} ight} :=frac{oldsymbol{b}_{l}}{oldsymbol{a}_{l k}} ]
选取 (x_l) 为离基变量。转(5)
以 (a_{lk}) 为主元旋转。即利用行变换，将第 (k) 个系数列向量变换为只有 (a_{lk}=1) 其他元素都为 0 的列。