线性规划 (一) 线性规划的基本形式及各种概念

 在最优化中，目标函数和约束函数皆为线性函数的优化问题称为线性规划（LP），它是相对简单的最优化问题。

标准形式

• 线性规划：

 如下形式的线性规划记2-1：

称为线性规划的标准形式。其中c j称为价格系数，b i 称为右端项。

  采用向量－矩阵表示法，标准形式可以简写为如下形式，记为2-2:

• 典范形式：

  在下面进行理论分析时，经常把A 看作由n 个列向量构成的，即：

若A 中有m 个列向量可以合并成单位矩阵，且b ≥ 0 ，则此时2-2称为线性规划的典范形式。

一般形式化标准形

  对于一般形式的线性规划，比如标准形式中是求极小，而有时候给出的是求极大，所以我们需要将其化成标准形，然后对标准形做研究，得到通用的解法。

  那么实际问题中出现的非标准形式如何处理呢？有三个基本原则：

• (1) 极大化极小：

• (2) 松弛变量和剩余变量：
    如约束中出现≤ ，则在该约束中加上一个变量（称为松弛变量），并要求该变量非负；如出现≥ ，则在该约束中减去一个变量（称为剩余变量）。

注意：新引入变量的价格系数全部设为零，因此目标函数中没有出现新变量。

• (3) 自由变量：
    以上讨论都考虑变量的取值是非负的。实际中，如果某些变量没有这种约束，也就是说，某些变量可以任意取值，那么这些变量称为自由变量。自由变量可以通过以下两种方法把它消除。

第一种方法将增加变量的数目，导致问题的维数增大。第二种方法正好相反。

解的性质

  在介绍解的性质之前，先需要了解一下各种各样的解的概念。

简单地说，在确定基之后，所有非基变量取值都为0的解是基本解，所有非基变量取值都为0的容许解是基本容许解。

定义：设B 是2-2的一个基。若2-2存在关于B 的基本容许解，则称B是2-2的容许基；否者称为非容许基。若容许基是单位矩阵，则称为标准容许基。

  上述所涉及到的概念，总结如下，方便复习：

• 解
• 容许解
• 基
• 基向量
• 非基向量
• 基矩阵
• 标准基
• 基变量
• 非基变量
• 基本解
• 基本容许解
• 容许基
• 非容许基
• 标准容许基

定义： 若基本解中基变量的取值都不为0，则该解称为非退化的；否者称为退化的。若2-2的所有基本容许解都是非退化的，则线性规划2-2称为非退化的；否者称为退化的。

  若线性规划是非退化的，则容许基与其基本容许解是一一对应的。相反地，退化地基本容许解可能与多个容许基相对应，也就是说不同的容许基会有相同的容许解。

• 基本容许解与极点地对应关系

  约束：

的基本容许解与这组约束所确定的容许集的极点在一定条件下是一一对应的。

定理： 设A 是秩为m 的m × n 矩阵，D DD是由约束A x = b ,    x ≥ 0 A所确定的容许集，则X XX为A x = b ,    x ≥ 0的基本容许解的充要条件是x xx为D DD的极点。

推论： 容许集D = { x ∣ A x = b ， x ≥ 0 } 的极点个数有限。其中假定A AA是秩为m 的m × n 矩阵。

  这里书上都有证明，这里我引用一位老师的话，定理都是证明给怀疑的人看的，如果你不怀疑，就不需要证明。如果你用过图解法。其实上面这个很好理解的。

定理： 线性规划若有容许解，则必有基本容许解。

定理： 线性规划若有最优解，则必有最优基本容许解。

我的微信公众号名称：深度学习与先进智能决策

微信公众号ID：MultiAgent1024

公众号介绍：主要研究分享深度学习、机器博弈、强化学习等相关内容！期待您的关注，欢迎一起学习交流进步！