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

字数 3490阅读 13407评论 1赞 4

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

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

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

8ftysn7bs9oq

二、业务目标：

总成本最小化，成本有两部分构成，仓库成本和配送成本；
每一个商店都必须配送到。

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

该案例演示用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 SupplyCostStores = ...;
即定义了数组变量名为“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 SupplyStores;
此处定义的决策变量SupplyStores是二维数组，数据类型也是boolean,即Supplys= 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];

}