线性规划转化为松弛型时生成新极值点为何不引发问题?
线性规划转化为松弛型时生成新极值点为何不引发问题?
我们先明确线性规划的松弛型定义:
当线性规划具有如下形式时,我们称它处于松弛型:
最小化 $c^T\cdot x$
约束条件:$Ax=b \land x\ge 0$
其中给定 $A\in\mathbb{R}^{m\times n}, b\in{\mathbb{R}_{\geq0}}^m, c\in\mathbb{R}n$,$x\in\mathbb{R}n$ 是变量向量。
任何线性规划都可以转化为松弛型。
不过这里有个让我百思不得其解的点:如果一个线性规划原本的解空间是仿射子空间,那它根本没有极值点(或者说不存在足够低维度的面)。但一旦转化为松弛型之后,解空间就会出现任意维度的面,尤其是凭空多出了极值点。
从几何角度来看,这两种形式对应的解空间差异明显,那为什么这种转化不会带来逻辑上的问题呢?
(其实我已经掌握了转化为松弛型的代数方法,也能证明可以通过某种方式将松弛型的解对应回原问题的解……)
备注:内容来源于stack exchange,提问作者ConnFus
相关产品推荐
相关产品推荐

