optimization - 线性优化程序中的最小值/最大值

Question

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

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

R --> Revenue function(这道题我不关心这部分)

tsp 表示我在路径 p 上的起点-目的地组合上发送了多少辆卡车。 ts'p 是反向路由。我在这里对 s 和 p 进行总结。

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

提前感谢您的帮助!

Answer 1

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

我只用一对路由来说明，你可以对所有路由对 (s,p) 做同样的事情。我们称它们为 Tsp，反之称为 Tps。

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

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

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

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 才为一。

综合起来:

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 中的最小值。

希望这能帮助您继续其余的工作。