yeliye
作者yeliye2018-08-30 14:42
数据库管理员, 某农信

IBM ILOG CPLEX Optimization Studio: 一个整数规划的案例

字数 3428阅读 5500评论 1赞 3

Integer programming, 整数规划是指规划中的变量(全部或部分)限制为整数;如果所有决策变量均要求为整数,则是纯整数规划pure integer programming;如果部分决策变量要求为整数,则是混合整数规划,mixedinteger programming.

一、业务问题描述:这是一个仓库选址和配送的问题,具体要求如下:

  1. 有10家商店编号0-9需要由某仓库配送商品,为简化问题,每个商店需要相同的一个单位的商品,必须都满足;
  2. 有5个待选的仓库,分别名称是: Bonn、Bordeaux、London、Paris、Rome;
  3. 这5个仓库的最大容量分别是Bonn是1个单位,Bordeaux是4个单位,London是2个单位,Paris是1个单位,Rome是3个单位,不可以超过最大容量;
  4. 为简化问题,每个仓库开设的成本是固定值30$;
  5. 这5个待选仓库配送到这10家商店的成本是不同的(单位是$);

8ftysn7bs9oq

8ftysn7bs9oq

二、业务目标:

  1.  总成本最小化,成本有两部分构成,仓库成本和配送成本;
  2. 每一个商店都必须配送到。

三、从数学的角度理解和定义该问题:

该案例演示用IBM ILOG CPLEX OptimizationStudio来解答该问题,该软件以OPL语言为核心集建模和求解为一体的一个软件平台。
Optimization Programming Language 是一种针对数学规划问题和组合优化问题的建模语言,是调用算法引擎CPLEX和CP Optimizer的最方便的数学建模工具。OPL模型就是寻找决策变量,使得决策变量满足约束条件并取得目标函数最值得过程。下面是求解该问题的几个步骤:

1.定义该问题的数据变量:

(1)Fixed 代表开设一个仓库的成本,
int Fixed =…;
即定义了变量名为“Fixed”的整型数据变量。

(2)Warehouses 代表可能的仓库名称,
{string} Warehouses = ...;
即定义了数组名为“Warehouse”的字符串数组,一维数组。

(3)NbStore 代表商店的数量,
int NbStores = ...;
range Stores =0..NbStores-1;
即定义了变量名为“Nbstores”的整型数据变量,并定义了“Stores”的最小值和最大值。

(4)Capacity 代表对应的仓库的容量,
int Capacity[Warehouses] =...;
即定义了数组变量名为“Warehouses”的整型数组,一维数组。

(5)SupplyCost 代表从Warehouses配送到Stores的费用,
int SupplyCost[Stores][Warehouses] = ...;
即定义了数组变量名为“SupplyCost”的整型数组,二维数组。

2.数据的初始化;

定义了数据变量之后,要进行数据的初始化,所谓初始化就是给数据变量赋值,下面依次给上述定义的数据变量赋值;
Fixed = 30
Warehouses = {Bonn,Bordeaux,London,Paris,Rome};
NbStores = 10;
Capacity = [1,4,2,1,3];
SupplyCost = [
[ 20, 24, 11, 25, 30 ],

[ 28, 27, 82, 83, 74 ],

[ 74, 97, 71, 96, 70 ],

[ 2, 55,73, 69, 61 ],

[ 46, 96, 59, 83, 4 ],

[ 42, 22, 29, 67, 59 ],

[ 1, 5, 73, 59, 56 ],

[ 10, 73, 13, 43, 96 ],

[ 93, 35, 63, 85, 46 ],

[ 47, 65, 55, 71, 95 ] ];

3.定义决策变量,这个问题需要做两个决策,定义了两个决策变量,分别是:

(1) 开设哪些仓库相关的决策变量?
dvar boolean Open[Warehouses];
dvar是定义决策变量的一个最常用的关键字,基本格式是:dvar 数据类型变量名。此处定义的决策变量Open[Warehouses]是一维数组,数据类型是boolean,即Open[w]=1, if the warehouse is opened; 0, otherwise; for all w in nw.

(2)每个商店由哪个仓库配送的决策变量?
dvar boolean Supply[Stores][Warehouses];
此处定义的决策变量Supply[Stores][Warehouses]是二维数组,数据类型也是boolean,即Supply[s][w]= 1, if store s is supplied by warehouse w; 0, otherwise; for all w in nw and s in ns.

4.目标函数的定义,即最小化总成本:

    minimize
      sum( w in Warehouses )
                 Fixed* Open[w] +
   sum( w in Warehouses , s in Stores )
      SupplyCost[s][w]* Supply[s][w];

5.约束条件的定义,这个问题有三个约束条件,分别是:

约束条件1:一个商店只能由一个仓库配送;
subject to{
forall( s in Stores )
ctEachStoreHasOneWarehouse:
sum( w in Warehouses )
Supply[s][w] == 1;
}

约束条件2:开设的仓库才能用;
subject to{
forall( w in Warehouses, s inStores )
ctUseOpenWarehouses:
Supply[s][w] <= Open[w];
}

约束条件3:每个仓库都不能超过最大容量;
subject to{
forall( w in Warehouses )
ctMaxUseOfWarehouse:

sum( s in Stores )
Supply[s][w] <= Capacity[w];
}

四、用IBM ILOG CPLEX Optimization Studio 12.8来求解该问题

IBM ILOG CPLEX Optimization Studio 12.8来求解该问题的具体操作过程如下:
1.打开软件界面,有四个常用的窗口,分别是OPL项目导航窗口、编辑窗口、问题浏览器窗口、输出窗口;
vl3ts8mz82lz

vl3ts8mz82lz

2.新建一个OPL项目,项目名称是“storehouse”,勾选“Adda default Run Configuration”、“Create Model”和“CreateData”,即该OPL项目包含一个模型文件和一个数据文件;
cry4icbd9u8c

cry4icbd9u8c

3.编辑模型文件的内容,即“storehouse.mod”文件
xj1j3do6deub

xj1j3do6deub

该模型文件的内容包含五个部分内容:
(1)定义数据变量;
(2)定义决策变量;
(3)设定目标函数;
(4)设定约束条件;
(5)定义输出变量并执行输出。

4.编辑数据文件的内容,即“storehouse.dat”,该内容就是变量的初始化,当然变量的初始化也可以通过编辑mod文件完成,在这个例子中是通过编辑dat文件来完成。
v4eaxlky37wi

v4eaxlky37wi

5.然后在”Configuration1(default)”上执行:

6.执行完成之后,得到如下主要输出结果:
yc9yoi7rk9it

yc9yoi7rk9it

五、业务解读

从IBM ILOG CPLEX Optimization Studio 12.8的运行结果,可以将问题的答案列在以下表格的紫色部分来突出:
u58t8ubpigai

u58t8ubpigai

解释如下:

  • Bonn仓库负责配送3号商店;

  • Bordeaux仓库负责配送1、5、6、8号商店;

  • London仓库负责配送7、9号商店;

  • Paris仓库没有开设;

  • Rome仓库负责配送0、2、4号商店;

    这样的安排可以实现总成本最小,并满足所有约束条件。

如果觉得我的文章对您有用,请点赞。您的支持将鼓励我继续创作!

3

添加新评论1 条评论

#wuwenpin软件开发工程师, 南京
2018-08-30 18:46
感谢分享。。
Ctrl+Enter 发表

关于TWT  使用指南  社区专家合作  厂商入驻社区  企业招聘  投诉建议  版权与免责声明  联系我们
© 2019  talkwithtrend — talk with trend,talk with technologist 京ICP备09031017号-30