优惠券最优使用策略问题建模及求解器求解

 2024-10-06

我们在网上购物，肯定会想着如何用更便宜的价格进行购买。这绕不开使用优惠券。
不过现在的平台把优惠券的使用方法和门槛搞得越来越花里胡哨。什么双11、618 等等“购物节”，买个东西想要算清价格怎么来的，难度堪比高考大题🤦。
本文就针对其中几种简单的情况进行建模，:p。

走，先从最简单的情况入手：手中只有一个打折优惠券，但是该券有使用金额上限。

---

单个有金额上限打折券

此问题描述起来其实很简单
就是说有一个优惠券，其优惠减免百分比为 $w$，最大应用金额不能超过 $c$ 。
(哈，俺为了后面更方便，没使用国内更常见的概念 – “打几折”，而用 “off”，即9折为 $w = 10$)
还有 $N$ 个商品，每个商品价格为 $p_{i}$。目标就是让我们得到最大的优惠金额。

稍微思考一下，我们可知道这里的 $w$ 对我们的使用并没有什么用。
因为只有个优惠券嘛 :)，只要想办法把能塞进用优惠券的商品加起来最贵就行了，越贵打折的金额就越多嘛。 当然，不是说我们能全部塞进去，要满足不能超过优惠券的“容量” $c$。

嗯，没错，我特意用“容量这个词” 😊，显然这就是一个 0-1背包问题换皮:

有 N 个物品和一个容量为 C 的背包，每个物品有重量 $w_{i}$ 和价值 $v_{i}$ 两种属性， 要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。 将其中的 $w_{i}$ 和 $v_{i}$ 都换成我们的商品价格 $p_{i}$ ，就是我们 “0-1 优惠券” 问题了 :P 。

0-1 背包问题网上的解析浩如烟海，俺就省点笔墨, 抄录一下数学模型便略过

\[maximize \quad \sum\limits_{i=1}^{N} p_{i}x_{i}\] \[s.t. \begin{cases} \sum\limits_{i=1}^{N} p_{i}x_{ij} \le c \\ x_{i} \in [0, 1] \quad \forall i \in [1, N] \end {cases}\]

---

多个券且每商品只能用一个券

热身完成了，我们循序渐进，对问题进行拓展：假如我们有多个券的情况下该如何分配？
先考虑一下每个商品只能一个券的情况吧，现实中某些平台确实是这样限制。如一单只能用一个券，这种情况我们现实中要做对操作便是“拆单”。

贪心算法及其局限

我们可以尝试使用简单的贪心算法来求解这个问题：

1. 对优惠券惠减免比例扣进行排序
2. 从比例最高的优惠券开始，使用0-1背包的求算法将其应用商品最大化

这个算法简单，但是有可能得不到最优解。
例如当商品如下

商品	价格
p1	4
p2	3
p3	2

优惠券如下

优惠券	最大可用金额	减免比例
c1	5	0.2
c2	3	0.15

应用该算法，优先填满c1，得到如下结果

优惠券	应用商品	减免比例	商品总金额	优惠金额
c1	p2 p3	0.2	5	1.
c2		0.15	0	0.
合计				1.

但是最优使用方法如下（注意应用到c1的商品金额比该贪心算法少，但最终总优惠反而更多）

优惠券	应用商品	减免比例	商品总金额	优惠金额
c1	p1	0.2	4	0.8
c2	p2	0.15	3	0.45
合计				1.25

可见该贪心算法不一定得到最优解。

很容易想到另一种改进的贪心算法，是考虑的不是简单的用最大可用金额进行优惠券的排序，而是用 减免比例/最大可用金额 来排序，可用叫其为单位优惠金额:)。
但是这样同样在某些情况也得不到最优解:

优惠券	最大可用金额	减免比例	减免比例/最大可用金额
c1	5	0.3	0.06
c2	3	0.15	0.05

应用该算法，优先填满c1，得到如下结果

优惠券	应用商品	减免比例	商品总金额	优惠金额
c1	p2 p3	0.3	5	1.5
c2		0.15	0	0.
合计				1.5

而最优方案其实是这样的:

优惠券	应用商品	减免比例	商品总金额	优惠金额
c1	p1	0.3	4	1.2
c2	p2	0.15	3	0.45
合计				1.65

问题

既然贪心算法不一定凑效，那么我们现在就对问题进行分析建模，然后交给求解器去解决。

开始分析，先列出我们有哪些变量、条件及目标：

• 商品 $N$ 个，每个商品 $i$ 价格为 $p_{i}$
• 优惠券 $M$ 个， 每个优惠券 $j$ 减免比例为 $w_{j}$
• 条件1: 每个优惠券 $j$ 应用的商品金额不能超过 $c_{j}$
• 条件2: 每个商品只能用 1 张优惠券
• 求: 怎样应用优惠券能达到最大优惠

建模

建立模型的第一步当然要引入我们的变量：

• 记 $x_{ij}$ 为是否为商品 $i$ 使用优惠券 $j$，使用时 $x_{ij} = 1$，否则 $x_{ij} = 0$。

注意我们这里的 $x$ 是二维的，而单个优惠券的时候是一维的，因为有多个券和多个商品可用产生应用关系。

若商品 $i$ 应用优惠券 $j$，则产生的优惠金额 $p_{i}w_{j}$；且此时$x_{ij}=1$， 故 $x_{ij}$ 乘上该金额，则可表示是有实际获得该优惠。

对于每个优惠券 $j$，其总优惠金额为 $\sum\limits_{i=1}^{N}{p_{i}w_{j}x_{ij}}$ 。
继而所有优惠券优惠总和为 $\sum\limits_{j=1}^{M} \sum\limits_{i=1}^{N} p_{i}w_jx_{ij}$，我们的目标就是将这个值最大化。

---

目标的表达式写出了，我们反过来看看约束条件。

对于条件 1，我们很容易就知道对于每个优惠券 $j$ 而言，其为表达式为 $\sum\limits_{i=1}^{N} p_{i}x_{ij} \le c_{j}$ 。

条件 2 就需要转转脑筋 :P, 对于每个给定的商品 $i$ 其最直接的表述为 对于所有 $j \in [1, M]$ ，$x_{ij}$ 最多只有一个为1。
那么我们对所有 $x_{ij}$ 求和，则可以肯定其和最大值不超过1;反过来，若其最大值不超过1，也可以推出 $x_{ij}$ 最多只有一个1。
因此，条件 2 可以表达为 $\sum\limits_{j=1}^{M} {x_{ij}} \le 1$, 对于 $j \in [1, M]$ 都成立。

---

综上，我们的模型为:

\[maximize \quad \sum\limits_{j=1}^{M} \sum\limits_{i=1}^{N} p_{i}w_{j} x_{ij}\] \[s.t. \quad \begin{cases} \sum\limits_{i=1}^{N} p_{i}x_{ij} \le c_{j} \quad \forall j \in [1, M] \\ \sum\limits_{j=1}^{M} {x_{ij}} \le 1 \quad \forall i \in [1, N] \\ x_{ij} \in [0, 1] \quad \forall i \in [1, N], j \in [1, M] \end{cases}\]

模型有了，我们看看该模型是否可对应到已知的问题类型。既然单个优惠券是0-1背包问题，那么我们这里多个优惠券是不是也是背包问题呢？ 其实这是一个 广义分配问题，背包问题是其的一个特例。

求解器解决

有模型了，就可用开始写代码丢给求解器来帮我们解决问题了。
这里使用 glpk 进行求解。

先定义我们的数据文件 1p_to_1c.dat :

# -*- mode: gmpl;-*-
data;
set Product := p1 p2 p3;
set Coupon := c1 c2;
	
/* 商品价格 */
param p :=
	p1 4
	p2 3
	p3 2 ;

/* c 最大可用 w 折扣  */
param : c w :=
	 c1 5 0.2
	 c2 3 0.15 ;

end;

为了进行求解，我们要有 gmpl 代码 1p_to_1c.mod，其实就是前面的数学模型原样翻译:

set Product;
# 优惠券集合
set Coupon;

# 商品价格
param p{i in Product};

# 优惠券最大可用金额
param c{j in Coupon};

#优惠券减免折扣
param w{j in Coupon};

# x[i][j] 第 i 个商品 使用第 j 张优惠券
var x{i in Product, j in Coupon}, binary;

# 最大化优惠金额
maximize d:
    sum{i in Product, j in Coupon} p[i] * w[j] * x[i,j];

# 每张优惠券不能超过最大可用金额
s.t. cap{j in Coupon}: sum{i in Product} p[i] * x[i, j] <= c[j];

# 一个商品只能用一个优惠券
s.t. only1{i in Product}: sum{j in Coupon} x[i,j] <= 1;

solve;

printf "result start\n";
for {j in Coupon} {
    printf "优惠券 %s, 应用到下列商品:\n", j;
    printf{i in Product: x[i, j] == 1} "%s ", i;
    printf "\n";
}
printf "最大优惠金额: %f\n", d;
printf "result end\n";

end;

运行:

glpsol -m 1p_to_1c.mod -d 1p_to_1c.dat | \
awk '/result end/{flag=0;next} flag; /result start/{flag=1;next;}'

结果:

优惠券 c1, 应用到下列商品:
p1
优惠券 c2, 应用到下列商品:
p2
最大优惠金额: 1.250000

---

可以叠加

继续往前，我们解决问题的方法都是从简单或者已知问题出发，逐步拓展 :)。 有了多个券，我们自然要处理可以同时应该多个优惠券的情况，即券可以叠加。 Let’s go (^_^)

问题

本问题的要素和前面一样，不过条件变了

• 条件1: 每个优惠券 $j$ 应用的商品金额不能超过 $c_{j}$ (和前面一样)
• 条件2: 每个商品可用多个优惠券，部分优惠券之间存在互斥关系（即同一个商品不能同时应用互斥的券）

---

建模

来创建目标函数吧。这里要求的变量和前面一摸一样，$x_{ij}$ 为是否为商品 $i$ 使用优惠券 $j$。

我们应用单个优惠券后产生的优惠金额也是一样的：$p_{i}w_{j}x_{ij}$。我们不能直接应用这个到我们的目标函数，还要处理叠加。
先考虑叠加两个优惠券 $j_1$ 和 $j_2$，显然叠加后的优惠金额为 $p_{i}w_{j_1}w_{j_2}$。这个表达式没有 $x$，需要把它弄进去。
如果我们直接将 $x$ 乘进去会怎样？
这恐怕行不通: 这样我们的表达式为 $p_{i} w_{i j_1} x_{i j_1} w_{i j_2} x_{i j_2}$。在两个券都用的时候确实是对的。但若只用1个券，则该式的值一定为0，显然不到。

看来想用优惠金额来作为我们的目标函数有点困难。不妨考虑将我们的目标改为最小化最后应付金额 :)。
单个优惠券 $j_1$ 应用到商品 $i$ 后，要付款的金额为 $p_{i}(1-w_{j_{1}}x_{ij_1})$;
和另一个优惠券 $j_2$ 叠加后，则为 $p_{i}(1-w_{j1}x_{ij_{1}})(1-w_{j_{2}}x_{ij_{2}})$ 。(我们不用“折”的概念，而使用 “off”，是为了这儿表达更方便)
可得单个商品 $p_{j}$ 最后要付金额为

\[p_{i}\prod\limits_{j=1}^{M}(1-w_{j}x_{ij})\]

应付总金额则为

\[\sum\limits_{i=1}^{N}p_{i}\prod\limits_{j=1}^{M}(1-w_{j}x_{ij})\]

我们的目标是要令其值最小化。

---

目标函数有了，来解决我们的条件。条件1没变，和前面一样。 下面对条件2（互斥）进行建模 记 $a_{gk}$ 为优惠券 $g$ 和 $k$ 是否互斥，0 为不互斥，1 为互斥

则互斥优惠券 $g$ 和 $k$ 同时应用到一个商品 $i$ 时有 $x_{ig} + x_{ik}=2$

此时若 $a_{gk}=1$ 则 $(x_{ig} + x_{ik})a_{gk}= 2$；反之，若 $a_{gk}=0$ 则 $(x_{ig} + x_{ik})a_{gk}= 0$

所以我们的互斥条件可以表示为 $(x_{ig} + x_{ik})a_{gk} \le 1$

---

综上，我们的模型为

\[minimize \quad \sum\limits_{i=1}^{N}p_{i}\prod\limits_{j=1}^{M}(1-w_{j}x_{ij})\] \[s.t. \quad \begin{cases} \sum\limits_{i=1}^{N} p_{i}x_{ij} \le c_{j} \quad \forall j \in [1, M] \\ (x_{ig} + x_{ik})a_{gk} \le 1 \quad \forall g,k \in [1, M], i \in [1, N] \\ x_{ij} \in [0, 1] \quad \forall i \in [1, N], j \in [1, M] \end{cases}\]

此模型的目标函数和武器目标分配(WTA)问题是一样的（详见论文）。
惊不惊喜，意不意外？！读者可能诧异于为什么我买个东西还跟打仗扯上关系了？ WTA 问题其实是已知敌人们的“血条”，和我们武器（一次性使用）对敌人的攻击力，求如何分配武器进行攻击才能使得敌人的“血条”尽可能清空。这里我们的商品便是“敌人”，“血条”是其价格，“攻击力”即优惠券的减免比例；理念转化后，不难理解两者间的关联了。

如果我们同优惠券有多张，那么 $x_{ij}$ 表示优惠券 $j$ 应用到商品 $i$ 的次数。则目标函数为

\[minimize \quad \sum\limits_{i=1}^{N}p_{i}\prod\limits_{j=1}^{M}(1-w_{j})^{x_{ij}}\]

这就完全和武器目标分配问题的目标函数一样了。不过对于同一类优惠券，可以建模为多张同等价值的优惠券，目标函数就变为上面所设计的了。

---

求解器求解

我们的目标函数是非线性的。glpk 不支持，故此处用 pyomo 调用 scip 来求解。

数据文件 1p_to_nc_off.dat

# -*- mode: gmpl;-*-
# 多优惠券，存在互斥
data;
set Product := p1 p2 p3;
set Coupon := c1 c2 c3;

/* 商品价格 */
param p :=
    p1 4
    p2 3
    p3 5 ;

/* c 最大可用 w 折扣  */
param : c  w :=
     c1 5  0.2
     c2 4  0.15
     c3 10 0.1 ;

/* 互斥关系 */
param a default 0 :=
     [c1,c3] 1 ;
end;

代码文件 1p_to_nc_off.py

from pyomo.environ import *
import sys

m = AbstractModel()

# 商品集合
m.Product = Set()
# 优惠券集合
m.Coupon = Set()

# 商品价格
m.p = Param(m.Product)

# 优惠券最大可用金额
m.c = Param(m.Coupon)
# 优惠券减免折扣
m.w = Param(m.Coupon)
# 互斥
m.a = Param(m.Coupon, m.Coupon, domain = Binary, default = 0)

#  x[i, j] 第 i 个商品 使用第 j 张优惠券
m.x = Var(m.Product, m.Coupon, domain = Binary)

# 目标: 最小化付款金额
m.d = Objective(
    rule = lambda m: sum(m.p[i] * (prod(1 - m.w[j] * m.x[i, j] for j in m.Coupon)) for i in m.Product),
    sense = minimize
)


# 每张优惠券不能超过最大可用金额
m.cap = Constraint(
    m.Coupon,
    rule = lambda m, j: sum(m.p[i] * m.x[i, j] for i in m.Product) <= m.c[j]
)

m.exclusive = Constraint(
    m.Product, m.Coupon, m.Coupon,
    rule = lambda m, i, g, k: (m.x[i, g] + m.x[i, k]) * m.a[g, k] <= 1
)

data = DataPortal()
filename = sys.argv[1]
data.load(filename=filename)
instance = m.create_instance(data)
#instance.pprint()

opt = SolverFactory('scip')
solution = opt.solve(instance)

for j in instance.Coupon:
    print("优惠券 ", j, "应用到下列商品: ")
    for i in instance.Product:
        if (value(instance.x[i, j]) == 1):
            print(i)

best = value(instance.d)
print("最小付款: ", best)

运行:

python3 1p_to_nc_off.py 1p_to_nc_off.dat

优惠券 c1 应用到下列商品:
p3
优惠券 c2 应用到下列商品:
p1
优惠券 c3 应用到下列商品:
p1
p2
最小付款: 9.76

---

应用顺序问题

细心的读者可能已经发觉，我们没有考虑到优惠券的应用顺序。
优惠券上限的判断，我们一直默认取的商品原价格，而不是上一个券生效后的价格。

例如：订单原价为100，优惠券a让我们的订单价格变为90，而优惠券b的可用上限为95元；此时还可不可以用优惠券b呢？ 如果是用95来计算上限，就得涉及到应用顺序问题。因为先用不同的券，会使得后面的券可用性发生变换。 这个问题不同商家/平台可能不同。根据笔者有限的经验，一般来说，很少有平台允许叠加优惠券。毕竟这样的场景设计起来有点复杂，且不一定能让顾客有更高的购买欲望。

所以这个问题，有点不符合现实场景。纯属“真空中球形鸡”的理论范畴可能性较大。

优惠券是订单维度？

哈，还有一个 bug。我们默认优惠券是可用任意使用到不同商品组合中。 又产生新问题了( ´▽｀)。这里得到的解，一个单可能有商品交叉使用不同券
例如: 订单中商品1、商品2使用券a，商品2和商品3使用券b。这样混合平台不一定支持。 假如券的使用维度不是商品，而是商品，我们的模型会怎么样了？

这需要我们引入新的对象–订单:

• 我们最多可以有 $M+1$ 个订单（极端场景每个优惠券一个单，还有一个没用券的单）;
• $x_{ij}$ 变成表示商品 $i$ 分配到订单 $j$;
• 还需引入新变量 $y_{kj}$，表示券 $k$ 分配到订单 $j$
• 新约束条件1: 每个商品只能在一个订单中 $\sum\limits_{j=1}^{M+1} x_{ij} = 1 \forall i \in [1, N]$
• 新约束条件2: 每个券只能在一个订单中。。。

嗯，假如我们进行一番推理，是能得到一个新的目标函数。这里笔者就不细写，反正本节已经是“真空中球形鸡” :)。

---

满减

读者看到这里，可能会跃跃欲试，打开手中的各种 app，准备买买买。
结果看到自己的卡包，只想大骂笔者。“啊，楼主你也没讲优惠券有使用门槛呀！还有我都是满减券，也没有折扣券呀！你这是不是在闹着玩？整这么多数学公式和代码，还真空球形。”

咳咳。没错，一般的商家都会设置优惠券使用门槛。这种情况涉及到如何用线性不等式表示逻辑关系，有点绕，才暂且搁置。现在就开始抛砖引玉。

问题

我们回到不可叠加的情况来考虑。毕竟对于有门槛的券，叠加场景需要明确优惠券使用顺序，相对复杂，忽略掉。这里的问题是，对应现实购买时，一张订单只能使用一个优惠券，如果要使用多个优惠券则需要考虑拆单。

• 商品 $N$ 个，每个商品 $i$ 价格为 $p_{i}$
• 优惠券 $M$ 个， 每个优惠券 $j$ 减免金额为 $w_{j}$
• 条件1: 每个优惠券 $j$ 应用的商品金额不能超过 $h_{j}$
• 条件2: 每个商品只能用 1 张优惠券
• 条件3: 每个优惠券 $j$ 最小可以应用的金额为 $l_{j}$
• 求: 怎样应用优惠券能达到最大优惠

---

建模

同理，记 $x_{ij}$ 为是否为商品 $i$ 使用优惠券 $j$，使用时 $x_{ij} = 1$，否则 $x_{ij} = 0$ 条件1和条件2与前面讨论的并无不同，可以直接套用。不同点便是目标函数和条件3（优惠门槛）

目标函数

直接减金额和折扣类型的优惠计算不一样。前者无论应用到多少商品，都只能扣一次，后者却是会累计扣减所有商品的优惠金额。我们的模型要表达出只扣一次，和前面的模型构建方式会有很大的不同。

对于优惠券 $j$， 只要一个商品应用了，则表明该优惠券的扣减金额可以累计。 如果我们在目标函数中可以使用逻辑表达，则目标函数是这样

\[maximize \sum\limits_{j=1}^{M} w_{j}(if \quad any \quad x_{ij} = 1 \quad \forall i \in [1,N])\]

但是嘛，线性模型不能用 if、or 之类的逻辑。那么我们只能另辟蹊径。 先引入一个中间变量 $y_{j} \in [0, 1]$ 来表示后面的逻辑，即 $y_{j} = x_{0j} \; or \; x_{1j} \; or …$ 则目标函数为

\[maximize \sum\limits_{j=1}^{M} w_{j}y_{j}\]

剩下的就是如何将 $y_{j}$ 的逻辑用 $x_{ij}$ 的算术条件表达出。

分两种情况讨论，$y_{j} = 1$ 和 $y_{j} = 0$

对于前者，至少有一个 $x_{ij} = 1$ 成立， 又因为 $y_{j}$ 和 $x$ 都是二元变量，所有 $y_{j}$ 为 $maximize(x_{ij} \forall i \in [1,N])$ 则约束条件可以表达为

\[s.t. \quad y_{j} \ge x_{ij} \quad \forall j \in [1,M] \quad \forall i \in [1,N]\]

对于后一种情况，所有 $x$ 都为 0。我们是不是可以让 $y_{i} \le x_{ij} \forall i \in [1, N]$ 呢？ 答案其实是不行的。因为这和前面一种情况显然冲突。当有部分 $x$ 为 1，部分为 0 时，$y$ 无法同时满足该两个条件。
我们可以换个思路，当 $x$ 都为 0 时，其和为 0，$y_{i} = 0$ 满足 $y_{j} \le \sum\limits_{i=1}^{N}x_{ij} \tag{4.1}$

反过来，部分 $x$ 为 1 时， 其和必然大于或等于 1，$y_{i} = 1$ 也满足式 4.1。 综上 $y_{i}$ 的约束条件可以表示如下:

\[s.t. \begin{cases} y_{j} \ge x_{ij} \quad \forall j \in [1,M] \quad \forall i \in [1,N] \\ y_{j} \le \sum\limits_{i=1}^{N}x_{ij} \end{cases}\]

优惠门槛条件

对于每个优惠券的最小可用金额，我们可以模仿最大可用金额的方式得到一下条件:

\[\sum\limits_{i=1}^{N} p_{i}x_{ij} \ge l_{j} \quad \forall j \in [1, M]\]

但是，这个条件并不是要直接应用，因为这个条件全部满足，则意味着每个优惠券都要得到使用，而我们并不要求每次用上所有优惠券。

直接理解我们的约束条件，对于每个优惠券 $j$ ，当 $y_{j} = 1$时，即使用该券，必须有应用该券的商品金额总和大于$l_{j}$: $\sum\limits_{i=1}^{N} p_{i}x_{ij} \lt l_{j}$
用 if 语句可以这样表示 \(if \quad y_{j} = 0 \quad then \quad \sum\limits_{i=1}^{N} p_{i}x_{ij} \lt l_{j} \tag{4.2}\)

嗯，没错，又是一个逻辑条件。

分类讨论

⚠️ 这里的推导流程可能有点牵强，笔者是知道具体的方法后，尝试凑出了的流程。 读者可以直接跳到下一节

同样，我们进行分类讨论。当 $y_{j} = 1$ 时，要求 $\sum\limits_{i=1}^{N} p_{i}x_{ij} \ge l_{j}$ 必须成立。我们可以想办法在后者中凑一个 1 出了。简单变换可得: \(1 - 1 \; \ge \; l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij} \tag{4.3}\) 这里出现了两个 1，我们要替换哪个呢？来考虑一下 $y_{j}=0$ 的情况。
由$y$的定义可知，当 $y_{i} = 0$ 时， 对于所有 $i\in[1,N]$ ， 有 $x_{ij} = 0$ 都成立。(不用该券，所有商品都不用咯) 此时 $l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij} = l_{j} - 0 = l_{j}$ 。 则 $l_{j} \ge l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij}$必定成立。同理，我们对此式凑出 0 可得:

\[l_{j}(1-0) \ge l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij}\]

用 $y_{j}$ 替换 0，得

\[l_{j}(1-y_{j}) \ge l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij} \tag{4.4}\]

对比式4.3：我们在式4.3左边乘以 $l_{j}$，不会影响结果，因为左边是 0

\[l_{j}(1-1) \ge l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij}\]

1-1 替换为 $1-y_{j}$ 则可得到式4.4。

---

这样分类讨论得到的式子可行？ 我们来验证式4.4是否可以表达出式 4.2 的逻辑: 若 $y_{j} = 1$ 则 $\sum\limits_{i=1}^{N} p_{i}x_c{ij} \ge l_{j}$。
对于该命题，将 $y_{j} = 1$ 代入 4.4 中, 得

\[l_{j}(1-1) \ge l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij} \\\] \[0 \ge l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij} \\\] \[\sum\limits_{i=1}^{N} p_{i}x_{ij} \ge l_{j}\]

即原命题成立。

---

虽然前面我们推导时利用了 $y$ 和 $x$ 的关系，其实就算没有此处的特殊关系，这种表示法依旧适用。这是一个通用的技巧 “大 M 表示法”

大 M 表示法

利用算术条件实现逻辑条件的方法为 大M 表示法。

M 为 $f$ 的上界 M，可用 $M(1-y_{j}) \ge f$ 为约束条件，来实现“当 $y_{j} = 1$ 时，必有 $f \le 0$” 的逻辑。 我们这里的 $f$ 就是优惠券门槛减去应用商品的金额：$l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij}$（要求当 $y_{j}$ 时，金额总和大于其门槛嘛，这个式就是小于0咯）。
又易知 $f$ 的上确界为 $l_{j}$, 代入大 M 表示法的

\[l_{j}(1-y_{j}) \ge l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij}\]

---

模型

综上所述，我们的模型如下

\[maximize \sum\limits_{j=1}^{M} w_{j}y_{j}\] \[s.t. \begin{cases} \sum\limits_{j=1}^{M} x_{ij} \le 1 \quad \forall i \in [1,N] \\ y_{j} \ge x_{ij} \quad \forall j \in [1,M] \quad \forall i \in [1,N] \\ y_{j} \le \sum\limits_{i=1}^{N}x_{ij} \\ \sum\limits_{i=1}^{N} p_{i}x_{ij} \le h_{j} \quad \forall j \in [1, M] \\ l_{j}(1-y_{j}) \ge l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij} \quad \forall j \in [1,M] \\ \end{cases}\]

求解器求解

fixed_amount.dat

# -*- mode: gmpl;-*-
# 多满减优惠券，每一个商品只能应用一个券
data;
set Product := p1 p2 p3;
set Coupon := c1 c2 c3;

# 商品价格
param p :=
    p1 4
    p2 3
    p3 2 ;

# 优惠券
param : l  h  w :=
     c1 6  6  2
     c2 4  5  1
     c3 7  8  4
     ;

end;

fixed_amount.mod

set Product;
set Coupon;


param p{Product}; # 商品价格

param l{Coupon};                     # 优惠券下限
param h{j in Coupon}, >= l[j];       # 优惠券上限
param w{j in Coupon}, >= 0, <= h[j]; # 优惠金额

var x{Product, Coupon} binary;
var y{Coupon} binary;

maximize t:
    sum{j in Coupon} w[j] * y[j];

s.t. y_min{j in Coupon, i in Product}: y[j] >= x[i, j];
s.t. y_max{j in Coupon}: y[j] <= sum{i in Product} x[i, j];

# 一个商品只能用一个优惠券
s.t. only1{i in Product}: sum{j in Coupon} x[i,j] <= 1;

# 不能超优惠券上限
s.t. cap_height{j in Coupon}:
    sum{i in Product}p[i] * x[i, j] <= h[j];

# 达到优惠券下限 y[j] 才 =1
s.t. cap_low{j in Coupon}:
    l[j] * (1 - y[j]) >= l[j] - sum{i in Product} p[i] * x[i, j];


solve;

printf "result start\n";
for {j in Coupon} {
    printf "优惠券 %s, 应用到下列商品:\n", j;
   
    printf{i in Product: x[i, j] == 1} "%s ", i;
    
    printf "\n";
}
printf "最大优惠金额: %f\n", t;
printf "result end\n";


end;

glpsol -m fixed_amount.mod -d fixed_amount.dat | \
awk '/result end/{flag=0;next} flag; /result start/{flag=1;next;}'

优惠券 c1, 应用到下列商品:
优惠券 c2, 应用到下列商品:
优惠券 c3, 应用到下列商品:
p1 p2
最大优惠金额: 4.000000

优惠溢出问题

对于满减券，有可能会出现扣减金额大于订单金额。在现实中出现这里情况时，一般会当作免单计算，避免负数。
满减金额我们以优惠金额为目标时，会出现只要一个商品就可以得到优惠金额，但是应付金额不是最优。
例如: 商品a 4元，商品b 1元，商品c 2元，券c 满4元减8元；最高可用金额为8元 ；对于我们的模型，有4个可行解:

1. 券c应用：a
2. 券c应用：a b
3. 券c应用：a c
4. 券c应用：a b c

因为上面4个解都能用上8元优惠券。但从实际情况来看，解4是完全免单，解1只能优惠4元，同理解2、3也不是免单，解4是唯一最优解。

---

所有我们要将目标改为“应付金额”最小化。
这里用拆单的方式来进行：

• 每一张优惠券对应一张单，单可以没有商品
• 额外加一张券 zero，其门槛为 0，上限无限大（可以用全部商品金额来表示），用来表示不用优惠券的订单
• 每个商品必须属于一张单

为表示扣减金额大于订单金额是免单（而不是负金额），我们引入 max 函数，每张单应付金额可以只要表示（$j=0$ 表示 zero 券）:

\[max(\sum\limits_{i=1}^{N}x_{ij}p_{i} - w_{j}y_{j}, 0)\]

所有订单的金额和为:

\[\sum\limits_{j=0}^{M} max(\sum\limits_{i=1}^{N}x_{ij}p_{i} - w_{j}y_{j}, 0)\]

目标是要将其最小化。

max 函数其实这个也可用大 M 表示法处理为线性算术不等式组。
不过这里有一个小技巧。引入一个变量 $z$, 另其满足一下条件:

\[z_{j} \ge 0\] \[z_{j} \ge \sum\limits_{i=1}^{N}x_{ij}p_{i} - w_{j}y_{j}\]

那么我们的目标就是:

\[minimize \quad \sum\limits_{j=0}^{M}z_{j}\]

原因是我们的目标是最小化，每个 $z_{j}$ 都要试图最小化，根据上面的约束，z_{j} 自动会选 $\sum\limits_{i=0}^{N}x_{ij}p_{i} - w_{j}y_{j}$ 和 0 两个值中的最大值。 *** 加上每个商品必须属于某张订单，可得模型：

\[minimize \quad \sum\limits_{j=0}^{M}z_{j}\] \[s.t. \begin{cases} \sum\limits_{j=0}^{M} x_{ij} = 1 \quad \forall i \in [1,N] \\ y_{j} \ge x_{ij} \quad \forall j \in [1,M] \quad \forall i \in [1,N] \\ y_{j} \le \sum\limits_{i=1}^{N}x_{ij} \\ \sum\limits_{i=1}^{N} p_{i}x_{ij} \le h_{j} \quad \forall j \in [0, M] \\ l_{j}(1-y_{j}) \ge l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij} \quad \forall j \in [0,M] \\ z_{j} \ge 0 \forall j \in [0, M] \\ z_{j} \ge \sum\limits_{i=1}^{N}x_{ij}p_{i} - w_{j}y_{j} \quad \forall j \in [0, M] \end{cases}\]

代码:

# -*- mode: gmpl;-*-
# 多满减优惠券，每一个商品只能应用一个券
# 以订单维度计算应付金额最小化
set Product;
set Coupon;

# 加入 zero 券
set cz := {"zero"} union Coupon;

param p{Product}; # 商品价格

param l{cz} default 0;                     # 优惠券下限
param h{j in cz}, >= l[j], default 0;      # 优惠券上限
param w{j in cz}, >= 0, <= h[j] default 0; # 优惠金额

var x{Product, cz} binary;
var y{cz} binary;
var z{cz};

minimize t:
    sum{j in cz} z[j];

s.t. y_min{j in cz, i in Product}: y[j] >= x[i, j];
s.t. y_max{j in cz}: y[j] <= sum{i in Product} x[i, j];

# 每个商品必须属于某个订单
s.t. only1{i in Product}: sum{j in cz} x[i,j] = 1;

# 不能超优惠券上限
s.t. cap_height{j in cz}:
    sum{i in Product}p[i] * x[i, j] <= h[j];

# 达到优惠券下限 y[j] 才 =1
s.t. cap_low{j in cz}:
    l[j] * (1 - y[j]) >= l[j] - sum{i in Product} p[i] * x[i, j];

# z 关联应付金额
s.t. z_not_negative{j in cz}:
    z[j] >= 0;
    
s.t. pay_amount{j in cz}:
    z[j] >= (sum{i in Product} x[i,j] * p[i]) - w[j] * y[j];

solve;

printf "result start\n";
for {j in cz} {
    printf "优惠券 %s, 应用到下列商品:\n", j;
   
    printf{i in Product: x[i, j] == 1} "%s ", i;
    
    printf "\n";
}
printf "最小应付金额: %f\n", t;
printf "result end\n";


data;
set Product := p1 p2 p3;
set Coupon := c1 c2;

# 商品价格
param p :=
    p1 4
    p2 2
    p3 1 ;

# 优惠券 门槛  最高  扣减金额
param : l     h    w :=
    c1  4     10    8
    c2  7     10    6
     ;

end;

result start 优惠券 zero, 应用到下列商品:

优惠券 c1, 应用到下列商品:
p1 p2 p3
优惠券 c2, 应用到下列商品:

最小应付金额: 0.000000
result end

融合：满减和满折同时存在

现在，打折券和满减券都讨论完了。
那么～～～～，我的回合。发动魔法卡～融合，将满减满折券合并，用了表示同时有两种类型券的情况:

• 每个券有两个属性 $w_j$ 固定减免金额和 $d_j$ 减免比例；两者最多有一个不为 0, 可以程序对输入检查。

应付金额表达式超进化～～～

\[z_{j} \ge \sum\limits_{i=1}^{N}x_{ij}p_{i} - w_{j}y_{j} - d_{j} \sum\limits_{i=1}^{N}x_{ij}p_{i} \quad \forall j \in [0, M]\]

简化:

\[z_{j} \ge (1-d_{j}) \sum\limits_{i=1}^{N}x_{ij}p_{i} - w_{j}y_{j} \quad \forall j \in [0, M]\]

综上，模型为：

\[minimize \quad \sum\limits_{j=0}^{M}z_{j}\] \[s.t. \begin{cases} \sum\limits_{j=0}^{M} x_{ij} = 1 \quad \forall i \in [1,N] \\ y_{j} \ge x_{ij} \quad \forall j \in [1,M] \quad \forall i \in [1,N] \\ y_{j} \le \sum\limits_{i=1}^{N}x_{ij} \\ \sum\limits_{i=1}^{N} p_{i}x_{ij} \le h_{j} \quad \forall j \in [0, M] \\ l_{j}(1-y_{j}) \ge l_{j} - \sum\limits_{i=1}^{N}p_{i}x_{ij} \quad \forall j \in [0,M] \\ z_{j} \ge 0 \forall j \in [0, M] \\ z_{j} \ge (1-d_{j}) \sum\limits_{i=1}^{N}x_{ij}p_{i} - w_{j}y_{j} \quad \forall j \in [0, M] \end{cases}\]

这里考虑的是非叠加情况。 若要建模可以先用满减券，后叠加最多一张折扣券，且后叠加的券金额门槛用前一张券算完再判断的话，可这么尝试：

• 满减券 $M$ 张，折扣券 $Q$ 张，则我们的订单总共有 $(M+1) * (Q+1)$ 张(笛卡尔积)
• 中间变量 $z_{jk}$ 表示每张单用满减券后的金额($j \in [0, (M+1)]$，$k \ in [0, Q+1]$), 需要用 大 M 表示法精确描述出 max 逻辑
• 利用 ${z_{jk}}$ 判断是否达到折扣券门槛
• 最终优惠金额 $z’_{jk}$，表示每张单的最终金额

哈哈，我先留坑，不一定会补，再见。

非 ai 创作: 本博客不含任何 ai 创作内容，为纯人工写作。

版权声明:

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。

转载请注明出处!