3

我正在尝试使用目标函数中的最小函数轻松地制定 LP。目标函数类似如下：

maximize sum( R(dvf * Df) ) - sum( min( tsp, ts'p ) * Csp - max(tsp-ts'p,0) * bsp )

R --> 收入函数（我不关心这个问题的这部分）

tsp 表示我在路径 p 上的 orgin-destination 组合上发送了多少辆卡车。ts'p 是反向路线。我在这里对 s 和 p 求和。

我需要知道的是如何将其设置为 LP 的一部分，因为 LP 在其目标陈述中不接受最小化和最大化函数。根据这个问题，需要带有附加变量的大 M 公式，但它并没有真正说明如何去做。

提前感谢您的帮助！

4

1 回答 1

2

这是使用 Big-M 和一组指标变量的方法。

让我仅使用一对路线来说明，您可以对所有路线（s，p）做同样的事情。我们称它们为 Tsp，反之则为 Tps。

线性化 IP 中两个决策变量的最小值

让我们只关注读取的目标函数部分 Min(Tsp, Tps) * Cost_sp

首先将目标函数重写为 Min Xsp * Csp所以我们Xsp为路由 sp 引入了一个新变量，使得：

Xsp = Tsp if Tsp is the minimum of Tsp and Tps
Xsp = Tps if Tps is the minumum of the two values

这可以通过额外的约束来强制执行。

Xsp = Tsp * Y + Tps * (1-Y)其中 Y 是 0-1 指示变量。

如果 Tsp 较大，我们希望 Y 为 1，如果 Tsp 较小，则 Y 为 0。

为了实现这一点，我们添加了约束：计算Tsp - Tps + M*y > 0 出该逻辑，如果 Tsp 很大，则自动满足条件。但如果 Tps 大于 Tsp，则 Y 必须取值 1 才能满足约束。

通过在目标函数中添加一个小的价格，我们可以确保 Y 只有在必须取该值时才为 1。

把它们放在一起：

Objective Maximize Sum(p,s) Xsp * Csp - epsilon.Y

s.t.
     Xsp = Tsp * Y + Tps * (1-Y)
     Tsp - Tps + M*y > 0
     Y = {0,1}

将确保目标函数取 Tsp 和 Tps 两个值中的最小值。

希望这可以帮助您继续前进。

于 2013-10-25T18:54:14.770 回答