1

在以下优化问题中，我需要您的帮助。我有一个最大化混合整数线性规划问题。我想考虑最低和最高固定费用。

我是这样弄的。。

cost = max(minimum fixed cost , cost rate * x)
cost >= minimum fixed cost
cost >= cost rate * x
cost = min(maximum fixed cost , cost rate * x)
cost <= maximum fixed cost
cost <= cost rate * x

但是，这变成了不可行的解决方案。请你帮我优化这样的问题。

4

2 回答 2

2

分段线性函数

我认为您的意思如下：

让

A = minimum fixed cost / cost rate
B = maximum fixed cost / cost rate

然后你想对分段线性函数进行建模：

cost = minimum fixed cost   if x < A
       cost rate * x        if A <= x <= B 
       maximum fixed cost   if x > B

在此处输入图像描述

在 MIP 模型中使用分段线性函数不是问题。您可以通过不同的方法做到这一点：

  • 使用额外的二进制变量（见（1））
  • 使用 SOS2 变量（见 (1)）
  • AMPL 和 Gurobi 等系统具有表达分段线性函数的特殊工具。

示例配方

具有 SOS2 变量的公式如下所示：

引入数据点 px 和 py

  px     py
  --------------------------
  0      minimum fixed cost
  A      minimum fixed cost
  B      maximum fixed cost
  C      maximum fixed cost

我们假设的地方0<=x<=C。即 C 是 的上界x。

然后做：

  set p = {1,2,3,4}
  sos2 variables lambda(p)
  sum(p, lambda(p)) = 1
  x = sum(p, lambda(p)*px(p))
  cost = sum(p, lambda(p)*py(p))

参见例如 (2)

你的方法有什么问题

请注意，您的方法（显示在问题中）不正确：

cost >= minimum fixed cost
cost >= cost rate * x
cost <= maximum fixed cost
cost <= cost rate * x

是真的

minimum fixed cost <= cost <= maximum fixed cost
cost = cost rate * x

限制x为A <= x <= B。

参考

(1) H.Paul Williams，“数学编程中的模型构建”，Wiley

(2) GAMS：具有 SOS2 变量的分段线性函数

于 2017-04-06T00:51:36.930 回答
1

分段线性函数：

cost = 0.02 x  if 0   <= x <= 500
       0.03 x  if 500 <= x <= 1500 
       0.04 x  if 1500<= x <= 10000

SOS2 解决方案：

x[a, b, c, d, e] = (x1[a, b, c, d, e] * 0)    + 
                   (x2[a, b, c, d, e] * 500)  + 
                   (x3[a, b, c, d, e] * 1500) +
                   (x4[a, b, c, d, e] * 10000) 

cost[a, b, c, d, e] = (x1[a, b, c, d, e] * 0       * 0   )+ 
                      (x2[a, b, c, d, e] * 500     * 0.02)+
                      (x3[a, b, c, d, e] * 1500    * 0.03)+
                      (x4[a, b, c, d, e] * 10000   * 0.04)

x1[a, b, c, d, e] + x2[a, b, c, d, e] + x3[a, b, c, d, e] + x4[a, b, c, d, e]>= 0

x1[a, b, c, d, e] <= y1[a, b, c, d, e]
x2[a, b, c, d, e] <= y1[a, b, c, d, e] + y2[a, b, c, d, e]
x3[a, b, c, d, e] <= y2[a, b, c, d, e] + y3[a, b, c, d, e]
x4[a, b, c, d, e] <= y3[a, b, c, d, e]    

y1[a, b, c, d, e] + y2[a, b, c, d, e] + y3[a, b, c, d, e]  = 1

我已经这样做了。但是，求解器仍然显示不可行的解决方案。你能看出这个公式有什么问题吗？！

于 2017-04-07T19:53:22.177 回答