代码之家 › 专栏 › 技术社区 › fglez

组合优化建模?问题

combinatorics puzzle theory algorithm

fglez · 技术社区 · 14 年前

我无法将这个问题与一些规范的问题匹配起来,我希望有一些指南来构建/使用一个算法并解决它。说明如下:

我们有些人想吃早餐。每人可以点任意数量的咖啡、果汁和吐司。我们为所有小组积累订单。

InitialOrder = { C1, J1, T1 } with C1, J1, T1 being integer non-negative numbers.

每个组件都有一个给定的价格,所以初始订单的总价格是

InitialPrice = C1 * Pc + J1 * Pj + T1 * Pt with Pc, Pj, Pt being rational positive numbers

自助餐厅还提供“早餐菜单”,包括标准项目组合。

full breakfast = coffee + juice + toast
normal breakfast = coffee + toast
bread breakfast = 2 toast

选择这些菜单比单独选择每个组件便宜,所以我们有

Pf < Pc + Pj + Pt
Pn < Pc + Pt
Pb < 2 * Pt
with Pf, Pn, Pb being rational positive numbers

人们希望将初始订单分组到菜单中,以最小化总花费。然后

FinalOrder = { C2, J2, T2, F, N, B } with C2, J2, T2, F, N, B integer non-negative numbers

我们会有一个最后的价格

FinalPrice = C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb with Pc, Pj, Pt, Pf, Pn, Pb as rational positive numbers

所有价格(PC、PJ、PT、PF、PN和PB)都是预先知道的。

拜托,你知道我应该采用哪种方法来建立一种算法来最小化给定首字母顺序的最终值吗?请随时询问您需要的更多详细信息。

提前谢谢。

3 回复 | 直到 14 年前

Aryabhatta 14 年前

你有六个变量和一个线性方程(最终价格),你需要最小化,给定的线性约束(必须匹配初始订单)。限制条件是变量为非负并取整数值。

例如,在您的示例中,它将是(我假设您的实际问题比您的示例更复杂):-)

减少

C2 * Pc + J2 * Pj + T2 * Pt + F * Pf + N * Pn + B * Pb

(将pc等乘以适当的整数,使其成为整数,如果需要的话)

受以下限制:

   C2 + F + N = C1
   T2 + F + N + 2B = T1
   J2 + F = J1

在一般情况下,整数规划是NP困难的,但是考虑到问题的规模小和约束条件,标准的求解技术可能很快就能为您解决问题。

希望有帮助。

Rafe 14 年前

如果您不想进行完整的搜索(整数线性规划,这是一个相当复杂的区域),可以考虑使用分支和绑定进行详尽的树搜索。bnb基本上是深度优先搜索,您可以在当前分支的成本大于或等于迄今为止找到的最佳解决方案的任何点进行回溯。

但正如白痴所说,对于任何大问题,你都需要ILP。

Suresh 14 年前

由于您的问题与装箱(或者至少是它的向量版本)密切相关,因此一些相关的启发式方法可能也很有用。具体来说,一个贪婪的启发式方法,即先贪婪地打包全套早餐(或2份*正常+吐司,具体取决于相对成本),然后继续这样做,可能就足够了。