首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >极小分段线性函数

问极小分段线性函数
EN

Stack Overflow用户
提问于 2020-06-08 04:59:10
回答 1查看 103关注 0票数 0

我有一个成本最小化problem.In的问题,我们有3个供应商。它们是S1,S2 & S3,这里的成本是按购买价格x计算的。

3家供应商的价格价值如下。

代码语言:javascript
复制
price=[10,15,20]

如果我有一个作为array[1..3] of var int:purchase的决策变量,我将从优化问题中得到答案,从哪个供应商那里,我需要购买多少个单元。

示例代码如下。

代码语言:javascript
复制
enum suppliers={s1,s2,s3};
int: len_sup=length(suppliers);
set of int:range_sup=1..len_sup;

array[range_sup] of int:price=[10,15,20];
int:demand=40;

array[range_sup] of int:moq=[5,0,5];
array[range_sup] of int:maxoq=[8,20,30];

array[range_sup] of var 0..100:purchase;

constraint sum(i in range_sup)(
purchase[i])=demand
;

constraint forall(i in range_sup)(
purchase[i]>=moq[i] \/ purchase[i]=0
);

constraint forall(i in range_sup)(
purchase[i] <= maxoq[i]
);

var int:cost;

constraint sum(i in range_sup)(
purchase[i]*price[i])=cost;

solve minimize cost;

现在我有一个新的要求嵌入价格折扣的this.This价格折扣将肯定会有所不同的数量,我们购买。

在这个例子中,假设我们从任何供应商那里购买了1到5的数量,那么我们就会在价格上得到5%的折扣(价格从5%下降)。如果我们购买6到10,我们会得到10%的价格折扣。如果我们购买超过11,我们得到15%的价格折扣。

你是如何通过分段线性函数将这个东西集成到model.Is中的(因为它看起来像是变成非线性的问题)?有人能说明如何使用分段线性函数吗?

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-06-08 07:42:14

也许这并不能真正回答您的问题,但是对于一些求解者(例如Gecode、JaCoP和OptiMathSAT),您可以使用查找表来解决这个问题。

您可以添加一个简单的折扣表:

代码语言:javascript
复制
array[1..3,1..3] of float: discount = array2d(1..3,1..3,
[
 1,5,0.05,  % between 1 and 5: 5% discount
 6,10,0.10, % between 6 and 10: 10% discount
 11,1000,0.15, % 11.. 5: 15% discount
]);

并将成本约束更改为

代码语言:javascript
复制
constraint
cost >= 0 /\
cost =
sum(i in range_sup) (
   purchase[i]*price[i]
    % lookup the discount 
    - purchase[i]*price[i]*sum(r in 1..3) (
          discount[r,3]*(purchase[i] >=  discount[r,1] /\
          purchase[i] <= discount[r,2]
      )
 ;

然后,最优解将是

代码语言:javascript
复制
purchase = array1d(1..3, [8, 20, 12]);
cost = 531;

如前所述,这只适用于支持变量浮点变量的求解器和非线性float_times。

Update:suresh_chinthy询问了piecewise_linear。下面是一个如何使用它的例子。请注意,它将与Gecode、JaCoP、OptiMathSAT一起工作,但不适用于线性求解器(如CBC ),因为piecewise_linear返回一个var float,该var float与决策变量purchase[i] (即var inte)相乘,这在CBC中是不允许的。

使用这两个数组从上面的代码中更改discount表。在这里,我们假设可以购买0到40件商品。

代码语言:javascript
复制
% the amount of purchase
array[0..40] of float: discount_base = array1d(0..40,[i | i in 0..40]);
% the discounts for each purchase
array[0..40] of float: discount =
   array1d(0..40,
           [0.0, % 0
            0.05, 0.05, 0.05, 0.05, 0.05, % 1-5
            0.10,0.10,0.10,0.10,0.10, % 6-10,
            0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15, % 11-20
            0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15, % 21-30
            0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15,0.15, % 31-40                        
            ]);

然后将cost约束更改为

代码语言:javascript
复制
constraints
  cost > 0 /\
  cost = 
       sum(i in range_sup) (
       purchase[i]*price[i] - purchase[i]*price[i]* piecewise_linear(1.0*purchase[i], discount_base, discount)
  );

其结果与上述相同:

代码语言:javascript
复制
purchase = array1d(1..3, [8, 20, 12]);
cost = 531;
票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/62255290

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档