关于线性规划在实际应用中的一些问题

这是最近在做新enigma机的项目时候遇到的一点问题。

主要研究对象的实质是线性规划。

因 为线性规划存在在可数学函数化前提下的固定解法，所以这一问题本身可以认为是基本上存在最优解。但在实际应用中出现的问题在于，在面对极大线性规划的时 候，一般采用的单纯型算法的理论时间是指数级，即不可解，而在此时只能用内点法来进行尝试，理论上内点法可以在多项式时间内可解，但涉及具体问题的时候容 易成为NP型，也就是说实际上是一个LP问题，即是否能在强多项式时间内可解。这也就是这个问题的核心数学问题。当然这一问题目前没有解决。

但 涉及实际问题的时候存在另外的问题，即在最优化的过程中花掉的时间（利益）多于达到最优化而产生的利益的时，这个优化则没有实际意义。即使是在强多项式时 间内可解。而对于一个量“利益”的判断是涉及社会性的量，这个量没有没有固定的定理来判断，于是总体原则上来说实际性的极大线性规划的实际考量是不存在理 论上的特定最优解。

当然必须考量到涉及实际性的时候极大的实际大小定义，即模型中顶点的数量问题。这个在目前的工作中已经有遇到。另外这 其中涉及到实际问题与函数模型的转换的复杂度问题，这又是一个需要论证的方面。但总体可以这样说，在一个比较复杂的实际问题且其以线性规划为基本模型的前 提下，实际中不存在理论上的最优解。