2

我正在尝试解决一个最小化问题,我想最小化一个表达式

a/b

其中 a 和 b 都是变量。因此,这不是一个线性问题......我怎样才能将这个函数转换为另一个函数(作为一个线性函数)。

4

3 回答 3

1

有几种方法可以做到这一点,但最简单的解释需要您求解一系列线性程序。首先,移除目标并添加约束

a <= c * b

其中 c 是解的已知上限。然后在 c 上进行二进制搜索,您可以在 c_l、c_u 的范围内解决问题

a <= c_l * b

但对于

a <= c_u * b
于 2012-07-19T15:42:44.303 回答
1

在lpsolve网站上有一个关于如何在线性规划中处理比率的详细部分。它应该足够通用以适用于 AMPL 和 CPLEX。

于 2012-07-19T20:29:24.647 回答
0

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。

于 2012-08-03T04:33:36.917 回答