我正在尝试解决一个最小化问题,我想最小化一个表达式
a/b
其中 a 和 b 都是变量。因此,这不是一个线性问题......我怎样才能将这个函数转换为另一个函数(作为一个线性函数)。
我正在尝试解决一个最小化问题,我想最小化一个表达式
a/b
其中 a 和 b 都是变量。因此,这不是一个线性问题......我怎样才能将这个函数转换为另一个函数(作为一个线性函数)。
有几种方法可以做到这一点,但最简单的解释需要您求解一系列线性程序。首先,移除目标并添加约束
a <= c * b
其中 c 是解的已知上限。然后在 c 上进行二进制搜索,您可以在 c_l、c_u 的范围内解决问题
a <= c_l * b
但对于
a <= c_u * b
在lpsolve网站上有一个关于如何在线性规划中处理比率的详细部分。它应该足够通用以适用于 AMPL 和 CPLEX。
obj 的一般形式应该是一个线性分数函数,类似于 f_{0}(x)=(c^Tx+d)/(e^Tx+f)。对于您的情况,X=(a,b),c=(1,0),(e=0,1),d=f=0。为了解决这种选择,可以使用称为线性分数规划的东西。这就像线性分数函数的线性约束版本,并且应用 Charnes-Cooper 变换来转换为 LP。您可以从 wiki 找到主要思想。许多 OR 书籍对此进行了更多讨论,例如 Boyd 的“凸优化”(免费下载)中的 pp53、pp165。