青山郭外斜的斜读XIE 还是XIA知乎⽤户Devin 化⼯系
线性规划问题中出现多个解的现象是⾮常常见的。代数解释是，⽬标向量是少数约束向量的线性组合；⼏何解释是⽬标向量垂直于那个最优超平⾯。
出现多解问题的⼏种可能性：
1. 问题没有能够得到很好地定义，或者说问题定义得⽐较“松”，导致有多个解。如果约束恰当，那么可能会恰好消除掉多解。 2. 问题的系统⾮常健壮，天然有⼀种灵活性，有多种⽅法得到相同的⽬标。如⽹络，有多个通路可以实现同样的⽬标。
当多解存在时，最优解有⽆穷个，可以分为两类，基本最优解（basic optimum）、⾮基本最优解（nonbasic optimum）。⼏何上看，基本最优解，就是可⾏域⾓点上的最优解，有有限个；⾮基本最优解是⾮⾓点上的解，有⽆穷个。使⽤不同的LP求解器会得到不同的结 联想td800
理论上通常得到基本最优解；内点法，搜索的是中⼼路径（central path）的解析中⼼
allen试验
果，单纯形法及其变种，搜索的是⾓点，所以理论上
理论上通常得到的是⾮基本最优解。相⽐⽽⾔，单纯形法是基本解，所以⼀般⽽⾔⽐内点法稀疏；如果希望是稀(analytical center)，所以理论上
疏解，应该尽量使⽤单纯形法，或者带有crossover的内点法。Crossover，是CPLEX求解LP问题时，求解后默认的⼀个后处理⽅法，这个后处理可以得到近似解最近的基本最优解；多解存在时，如果使⽤了内点法加上crossover的后处理，得到的还是⼀个基本最优解。
精氨酸加压素
如果换个视⾓，最优解集实际上可以看成凸组合，那么基本最优解是凸组合的⾓，所有⾮基本最优解可以看做基本最优解的凸组合。正是因为这样，当多解存在时，求解得到所有基本最优解最关键。Cplex 上有⼀个不错的关于多解的讨论（链接：CPLEX Optimizers）值得⼀看。我不太清楚CPLEX能不能到LP问题的所有最优解，但是好像整数规划CPLEX是可以到所有的最优解的（我曾经搜到过）。
搜索所有基本最优解的常见⽅法有两种，⼀种是把LP问题转化成MILP问题，效率低，个⼈不喜欢；另⼀种⽅法相对简单。单纯形法停⽌时的单纯形表中，⾮基变量如果有系数为零的，那么该⾮基变量进基，不会带来⽬标函数的变化，这就是多个基本最优解。可以通过让该变量进基，然后得到⼀个新的基本最优解。新的基本最优解，可能也存在⾮基变量系数为零的情况，其中⼀个解进基会得到刚才
的解；其他的进基会得到新的基本最优解。通过这样迭代的搜寻，并且排除所有的重复的基本最优解，就得到了所有的基本最优解集。个⼈经验，这种⽅法因可能会搜索到重复的，编程上需要特殊处理（递归调⽤，树状搜索，不太清楚可不可以避免递归），否则⼀个简单的问题因为递归，就会把内存耗尽。我曾经有⼀个原LP问题50个变量左右，经过标准化后搜索出超过2500个基本最优解，然后内存就耗尽了。
Lee, S., Phalakornkule, C., Domach, M. M., & Grossmann, I. E. (2000). Recursive MILP model for finding all the alternate optima in LP models for metabolic networks.Computers & Chemical Engineering,24(2-7), 711-716.
jinjide>黑芝Motamedian, E., & Naeimpoor, F. (2018). LAMOS: A linear algorithm to identify the origin of multiple optimal flux distributions in metabolic networks.Computers & Chemical Engineering,117, 372-377.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议