最优化

线性规划 (二) 单纯形法

2019-12-07  本文已影响0人  小小何先生

问题描述

  标准线性规划的容许集是凸多面体,有有限个极点,若有容许解,则必有基本容许解若有最优解,则必有最优基本解。由此看来,为求最优解,只须关心基本容许解。又因为基本容许解与极点是一一对应的,所以从几何上,容易想出:先求出一个极点,再沿凸多面体的棱求出另一个使目标函数值所有下降的极点。因为极点的总数是有限的,所以在一定条件下,总可以迭代到最优的极点,因为极点的总数是有限的,所以在一定条件下,总可以迭代到最优的极点。

  那么你想依次循环迭代每个极点的话,你需要知道已下三点:1. 怎样求第一个基本容许解? 2. 求出来了这个解怎么判断是不是最优解? 3. 怎么从一个基本容许解迭代到下一个?用官方术语来表示就是:

  1. 怎样求得标准线性规划的一个初始基本容许解?
  2. 怎样判别一个基本容许解是否为最优解?
  3. 怎样从一个基本容许解迭代出使目标函数值下降的另一个基本容许解?

求解思路

  我们先看后面两个,也就是怎么判别一个基本容许解是否为最优解:
  考虑下面的线性规划问题:
\left.\begin{array}{c}{\min c^{T} x} \\ {\text {s.t. } A x=b} \\ {x \geq 0}\end{array}\right\}

  其中A是秩为mm \times n矩阵。设B是已知的容许基,不妨设A = [B, N]相应地,把xc分解为:
x =\begin{bmatrix}x_{B}\\ x_{N}\end{bmatrix} ,c=\begin{bmatrix}c_{B}\\ c_{N}\end{bmatrix}
  于是可以写成下式:

\left.\begin{array}{c}{\min c^{T}_{B} x_{B}+c_{N}^{T}x_{N}^{T}} \\ {\text {s.t. } Bx_{B} + Nx_{N}=b} \\ {x_{B} \geq 0,x_{N} \geq 0}\end{array}\right\}

  令所有非基变量的取值为零,即x_{N}=0,那么由上面的这个等式约束立刻得到基变量向量的取值为x_{B}=B^{-1}b。因此关于B的基本容许解是:

  其目标函数值是:

\overline{z}=c_{B}^{T}B^{-1}b

  现在考虑对于上述的线性规划的任意一个解呢?其容许解可表示为x=[x_{B}^{T},x_{N}^{T}]^{T},其目标函数值是:
z=c_{B}^{T}x_{B}+c_{N}^{T}x_{N}

  由此可以求解出x_{B}=B^{-1}b-B^{-1}Nx_{N}并代入上式,再利用\overline{z}=c_{B}^{T}B^{-1}b可得:

z = c_{B}^{T}(B^{-1}b-B^{-1}Nx_{N})+c_{N}^{T}x_{N} \\ =\overline{z}-(c_{B}^{T}B^{-1}N-c_{N}^{T})x_{N}

  如令\sigma_{N}^{T}=c_{B}^{T}B^{-1}N-c_{N}^{T}

z=\overline{z}-\sigma_{N}^{T}x_{N}

  由于x是容许解,故必有x_{N} \geq 0,因此,只要\sigma_{N} \leq 0,由z=\overline{z}-\sigma_{N}^{T}x_{N}立刻得知z \geq \overline{z},即关于B的基本容许解是最优解。由此得到关于基B的基本容许解是最优解的一个充分条件为

\sigma_{N}^{T}=c_{B}^{T}B^{-1}N-c_{N}^{T} \leq 0^{T}

N=[a_{m+1},···,a_{n}]代入\sigma_{N}中,得:

\sigma_{j}=c_{B}^{T}B^{-1}a_{j}-c_{j},j=m+1,···,n

一些定义

  因为上面这个公式比较重要,所以我们有必要给其下一个定义:

定义:在标准线性规划中,设B是一个基,则:

\sigma_{j}=c_{B}^{T}B^{-1}a_{j}-c_{j},j=1,2,···,n

  称为变量x_{j}关于基B判别数

  按此定义,\sigma^{T}=c_{B}^{T}B^{-1}A-c^{T}所有变量x的判别数向量\sigma_{N}^{T}=c_{B}^{T}B^{-1}N-c_{N}^{T}是所有非基变量x_{N}的判别数向量。而所有基本变量x_{B}的判别数向量是:
\sigma_{B}^{T}=[\sigma_{1},\sigma_{2},\cdots , \sigma_{m}] \\ = c_{B}^{T}B^{-1}B-c_{B}^{T} = 0^{T}

  由此可以看到,所有非基变量的判别数都等于零

定理:在标准线性规划中,设B是容许基,若所有变量关于B的判别数都非正,则关于B的基本容许解是最优解。

  之后你就可以刷题了。emmm。

我的微信公众号名称:深度学习与先进智能决策
微信公众号ID:MultiAgent1024
公众号介绍:主要研究分享深度学习、机器博弈、强化学习等相关内容!期待您的关注,欢迎一起学习交流进步!

上一篇 下一篇

猜你喜欢

热点阅读