分式规划模型转化为可求解模型的技术求助

阿华AIGC实验室

2026-4-21

分式规划模型转化为可求解模型的技术求助

Hey there! Let's break down how to turn your fractional programming model into something solvable. First, let's restate your original model clearly to make sure we're on the same page:

原模型

目标函数：
$ \min \delta$

约束条件：

$\frac{190(E_j-\sum_ix_{ij})}{P_j-\sum_iQ_ix_{ij}}\leq\delta \ \ \ \ \forall j$
$\sum_j x_{ij} \leq S_i \ \ \ \ \forall i$
$ P_j-\sum_iQ_ix_{ij}\geq0.4P_j\ \ \ \ \forall j$
$ \sum_ix_{ij}\geq0\ \ \ \ \forall j$

其中$x_{ij}$是连续变量，其余均为已知参数。

关键观察：约束3的作用

首先，约束3保证了分式的分母$P_j - \sum_i Q_i x_{ij} \geq 0.4P_j$。只要$P_j>0$（这在实际问题中应该是合理的，否则约束3没有意义），分母就是严格正数。这很重要，因为它允许我们直接对分式约束进行变形，而不用担心不等号方向改变。

转化思路：二分法+线性规划

你的问题本质上是要找到最小的$\delta$，使得所有分式约束都成立，同时满足其他线性约束。直接处理带$\delta$的双线性项（变形后会出现$\delta$和$x_{ij}$的乘积）比较麻烦，所以二分法+线性规划是最直观且容易实现的方案：

步骤1：确定$\delta$的初始范围

我们需要先给$\delta$找一个可行的上下界，方便后续迭代：

下界$\delta_{low}$：可以先尝试一个保守的小值，比如$-10^9$（如果允许$\delta$为负，毕竟分子可能为负），或者根据参数计算一个更合理的下界（比如当$x_{ij}$取最大可能值时的分式结果）。
上界$\delta_{high}$：取所有$j$对应的$\frac{190E_j}{0.4P_j}$中的最大值。因为当$\sum_i x_{ij}=0$时，分式值为$\frac{190E_j}{P_j}$，而分母最小是$0.4P_j$，所以这个上界肯定是可行的。

步骤2：二分迭代求解

重复以下步骤直到$\delta_{high} - \delta_{low}$小于你设定的精度（比如$10^{-6}$）：

计算中间值$\text{mid} = \frac{\delta_{low} + \delta_{high}}{2}$
构建可行性线性规划（LP）：
- 目标函数：任意（比如设为$\min 0$，因为我们只需要判断是否存在可行解）
- 约束条件：
  1. 变形分式约束：将$\frac{190(E_j-\sum_ix_{ij})}{P_j-\sum_iQ_ix_{ij}}\leq\text{mid}$两边乘正数分母，得到：
    $$\sum_i (\text{mid} \cdot Q_i - 190)x_{ij} \leq \text{mid} \cdot P_j - 190 \cdot E_j \quad \forall j$$
  2. 原约束2：$\sum_j x_{ij} \leq S_i \quad \forall i$
  3. 变形原约束3：$\sum_i Q_i x_{ij} \leq 0.6P_j \quad \forall j$
  4. 原约束4：$\sum_i x_{ij} \geq 0 \quad \forall j$
  5. $x_{ij}$为连续变量（如果实际问题中$x_{ij}$非负，可以额外添加$x_{ij} \geq 0$约束）
求解这个LP：
- 如果LP有可行解：说明$\text{mid}$是一个可行的$\delta$，我们可以尝试更小的值，令$\delta_{high} = \text{mid}$
- 如果LP无可行解：说明$\text{mid}$太小，需要增大$\delta$，令$\delta_{low} = \text{mid}$