运筹学教学|Benders Decomposition （二）应用实例及算法实现（附源代码及详细的代码注释）

我们在运筹学教学|Benders Decomposition（一）技术介绍篇中已经介绍了Benders Decomposition的基本原理，下面为大家提供具体的应用实例和相应的代码。

实例

带固定花费的运输问题：

已知某种物资有m个供应点（源点），

，i = 1, 2，…, m，供应量分别为

；有n个需求点（终点），

，j = 1, 2, …, n，需求量分别为

。从

到

运输单位物资的运价为cij，固定费用为

。若用xij表示从

到

的运量，

表示是否有物资从

运送到

，可通过下面的混合型整数优化模型（mixed integer programming model,简称MIP模型）求得总费用最小的运输方案：

其中

为一个足够大的实数，

可以看作是

的一个上界，故可设：

模型（7）可以重写为：

子问题：

则（10）的对偶问题可以写为：

松弛主问题可以写成：

其中（12b）和（12c）是通过Benders算法求解过程中添加的切平面，（12b）是通过极射线添加的切平面，（12c）是通过极点添加的切平面。

算例说明

算例1

sources demands

4 3

supply

10 30 40 20

demand

20 50 30

variable cost

2 3 4

3 2 1

1 4 3

4 5 2

fixed cost

10 30 20

10 30 20

10 30 20

10 30 20

最优解：350

算例2

sources demands

8 7

supply

20 20 20 18 18 17 17 10

demand

20 19 19 18 17 16 16

variable cost

31 27 28 10 7 26 30

15 19 17 7 22 17 16

21 17 19 29 27 22 13

9 19 7 15 20 17 22

19 7 18 10 12 27 23

8 16 10 10 11 13 15

14 32 22 10 22 15 19

30 27 24 26 25 15 19

fixed cost

649 685 538 791 613 205 467

798 211 701 506 431 907 945

687 261 444 264 443 946 372

335 385 967 263 423 592 939

819 340 233 889 211 854 823

307 620 845 919 223 854 656

560 959 782 417 358 589 383

375 791 720 416 251 887 235

最优解：4541

代码（Java版本）展示

注：展示代码分为两部分，第一部分是上述实例Benders求解过程代码，第二部分是cplex内部算例代码。（欲下载本文的java源代码，请移步留言区。）

第一部分

上述算例代码：

第二部分

cplex提供的算法代码：

编辑和代码：黄楠（huangnanhust@163.com，华中科技大学管理学院博士一年级）

指导老师：秦时明月（professor.qin@qq.com）