我们在运筹学教学|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)