程序员自然科普@IT·互联网

优化建模之MiniZinc(二) 模型的抽象化 -- 模型与数据

2020-11-18  本文已影响0人  ChaoesLuol

模型的抽象化

具体模型与抽象模型

具体模型

在第一篇文章中我们介绍了MiniZinc程序的基本组成部分。

作为复习，我们可以看一个生产规划问题：

我们在边境和印军相持，因为不能开枪，我们要生产一批冷兵器来武装部队，可选的选项有长矛、剑和锤子；生产武器需要消耗一些资源和工匠的时间，武器对应的资源消耗如下：

木材 铁矿 铁匠工时 木匠工时
长矛 2.5 0.5 1.0 3.7
剑 0.4 4.2 5.1 1.2
锤子 3.5 4.5 7.0 2.7

我们的资源是有限的：

木材 铁矿 铁匠工时 木匠工时
5000.0 2000.0 4000.0 3250.5

每样武器对应一定的战斗力：

长矛 剑 锤子
12.5 17.0 23.8

我们希望充分利用有限的资源来最大化我们的部队战斗力，那么每样武器需要生产多少件呢？

对应的模型如下：

% 混料问题的模型
%--------------------------
% 数据部分
enum RESOURCES = {wood, iron, blacksmith_hour, carpenter_hour}; % 需要的资源
enum WEAPONS = {spear, sword, hammer}; % 生产的武器
array[WEAPONS, RESOURCES] of float: consumption = [|2.5, 0.5, 1.0, 3.7
                                                   |0.4, 4.2, 5.1, 1.2
                                                   |3.5, 4.5, 7.0, 2.7|]; % 生产每种武器需要的资源
array[RESOURCES] of float: res_amount = [5000.0, 2000.0, 4000.0, 3250.5]; % 每种资源的数量
array[WEAPONS] of float: power = [12.5, 17.0, 23.8]; % 每种武器的威力

%--------------------------
% 决策变量
array[WEAPONS] of var int: weapon_amount;

%--------------------------
% 约束
% 每种武器的数量都必须为非负数
constraint forall(w in WEAPONS)(weapon_amount[w] >= 0);
% 武器的资源消耗要不大于最大资源数量
constraint forall(r in RESOURCES)(
                 (sum(w in WEAPONS)(consumption[w, r] * weapon_amount[w])) <= res_amount[r]);

%--------------------------
% 目标函数
var float: total_power = sum(w in WEAPONS)(power[w] * weapon_amount[w]);
solve maximize total_power;

%--------------------------
% 输出
output ["Amount of weapon " ++ show(w) ++ " : " ++ show_int(8, weapon_amount[w]) ++ "\n" | w in WEAPONS]
        ++ ["Total power: " ++ show_float(6, 2, total_power)];

通过求解，我们可以得到答案：

Amount of weapon spear :      603
Amount of weapon sword :        0
Amount of weapon hammer :      377
Total power: 16510.10
----------
==========

模型中关于数组和一些内置函数，可以往下拉到后面看对MiniZinc语法的解释。

抽象模型

上面这个模型看起来没有什么问题，求解也很顺利。但是在很多情况下，我们建模时会面临一系列what-if的问题：如果我资源多一些，会怎么样？如果我增加一些兵器种类供选择，会怎么样？

我们需要不断修改上面的具体模型，来应付不断变动的数据。

如果我们不是在求解一个武器生产问题，而是在规划我们的期末复习计划呢？我们是不是需要重写整个模型呢？

在软件工程的实践中，设计模式给我们的重要启示就是将变动的部分和相对稳定的部分分开，对我们的模型来说也是一样，同一类的生产规划模型中有一些共同点，我们可以抽取其想通部分，然后将数据单独分开。

生产规划模型

在生产规划模型中，我们可以提取一些共同之处：

根据这些共同特点，我们可以生成一个抽象的模型(2_2_AbstractProductionModel.mzn)：

% 抽象的生产问题模型

%--------------------------
% 数据部分
enum RESOURCES; % 用于生产的资源
enum PRODUCTS; % 生产的产品
array[PRODUCTS, RESOURCES] of float: consumption; % 生产每种产品所需要的资源数量
array[RESOURCES] of float: capacity; % 每种资源的额度
array[PRODUCTS] of float: profit; % 每种产品可以提供的收益

%--------------------------
% 决策变量
array[PRODUCTS] of var int: produce_num;

%--------------------------
% 约束
% 资源消耗少于额度
constraint forall(r in RESOURCES)
        (sum(p in PRODUCTS)(consumption[p, r] * produce_num[p]) <= capacity[r]);
% 每种产品数量必须为非负
constraint forall(p in PRODUCTS)(produce_num[p] >= 0);

%--------------------------
% 目标函数
var float: total_profit = sum(p in PRODUCTS)(produce_num[p] * profit[p]);
solve maximize total_profit;

%--------------------------
% 输出
output ["Amount of product " ++ show(p) ++ " : " ++ show_int(8, produce_num[p]) ++ "\n" | p in PRODUCTS]
        ++ ["Total profit: " ++ show_float(6, 2, total_profit)];

我们可以看到在抽象模型中，没有包含任何数据。这样我们就分开了模型和数据，对于同样一个模型，我们可以用来求解性质相同的不同数据集了。

为了验证，我们可以将我们上面的武器生产问题建立一个独立的数据集2_2_WeaponProduction.dzn如下：

RESOURCES= {wood, iron, blacksmith_hour, carpenter_hour};
PRODUCTS = {spear, sword, hammer};
consumption = [|2.5, 0.5, 1.0, 3.7
               |0.4, 4.2, 5.1, 1.2
               |3.5, 4.5, 7.0, 2.7|];
capacity = [5000.0, 2000.0, 4000.0, 3250.5];
profit = [12.5, 17.0, 23.8];

在命令行中运行minizinc --solver CBC 2_2_AbstractProductionModel.mzn 2_2_WeaponProduction.dzn指定数据集和求解器进行求解，得到结果：

Amount of product spear :      603
Amount of product sword :        0
Amount of product hammer :      377
Total profit: 16510.10
----------
==========

可以看到对于武器生产问题，我们得到的结果和前面一样。

自习时间分配问题

抽象模型的好处在于可以用同一个模型处理一类问题。用之前建立的生产问题模型，我们可以来看看下面的一个时间分配问题：

我们面临有三门课的期末考试，分别是运筹学、离散数学和C语言，对于每种课程的复习，一种较理想的方案是分别分配一定的上机复习、讨论和书本自习，各门课程理想复习方案的时间比例如下：

上机 讨论 自习
运筹学 0.3 0.5 0.2
离散数学 0.2 0.4 0.4
C语言 0.6 0.1 0.3

但是由于机房、讨论室和自习室各自有一定时间限制，我们在考试来之前能够约到的时间如下：

上机时间 讨论时间 自习室时间
10.5 7.0 12.0

每花一个小时在不同科目上，我们能够提高不同的平均GPA：

运筹学 离散数学 C语言
0.2 0.15 0.1

假设我们起点很低，这轮复习不会将任何科目的GPA刷满，但是我们希望将GPA尽量刷高一点，那么应该怎么分配剩余的复习时间呢？

我们发现这个问题其实也是生产问题的一类，我们并不需要对模型进行任何的改动，只需要将数据集进行修改即可。我们建立一个数据文件2_2_SwotUp.dzn放入相应的课程、用时和收益：

RESOURCES= {computer_work, discussion_room, desk_work};
PRODUCTS = {operation_research, discrete_math, C_language};
consumption = [|0.3, 0.5, 0.2
               |0.2, 0.4, 0.4
               |0.6, 0.1, 0.3|];
capacity = [10.5, 7.0, 12.0];
profit = [0.2, 0.15, 0.1];

在命令行运行minizinc --solver CBC 2_2_AbstractProductionModel.mzn 2_2_SwotUp.dzn进行求解：

得到结果：

Amount of product operation_research :        6
Amount of product discrete_math :        7
Amount of product C_language :       12
Total profit:   3.45
----------
==========

小节

因此，在建模时，通常建议对模型进行抽象化，将模型文件和数据文件分开来。

MiniZinc中的一些语法知识

数组和推导式

在上面的程序中，我们用到了如下语句：

array[WEAPONS, RESOURCES] of float: consumption = [|2.5, 0.5, 1.0, 3.7
                                                   |0.4, 4.2, 5.1, 1.2
                                                   |3.5, 4.5, 7.0, 2.7|]; % 生产每种武器需要的资源

这条语句定义了一个二维数组consumption，其维度分别为WEAPONS和RESOURCES。

数组是一个比较常用的数据结构，下面我们会介绍一下数组的相关知识：

数组的声明

数组可以是一维或者多维的，在声明时使用如下格式：

array[index_set1, index_set2,...] of <type>

数组下标的集合可以是枚举类型或者是某个集合表达式。

数组内的元素可以是除了数组以外的任何内置类型，也就是说MiniZinc不支持数组嵌套。

数组的初始化

一维数组

对于一维数组，我们可以用列表的方式进行初始化，这和大多数其他语言一样，比如下面这些例子：

profit = [100, 200, 300];
cost = [0.2, 0.3, 0.5];

二维数组

MiniZinc中二维数组的初始化有特定的语法：

一个例子就是我们上面定义的二维数组：

consumption = [|2.5, 0.5, 1.0, 3.7
                     |0.4, 4.2, 5.1, 1.2
                             |3.5, 4.5, 7.0, 2.7|];

特别需要注意结尾，不要忘记|符号。

内置函数初始化任意维度数组

对于任何维度k不大于6的数组，我们都可以用内置函数arraykd来进行初始化，例如：

profit = array1d(1..3, [100, 200, 300]);
consumption = array2d(1..3, 1..4,
                            [2.5, 0.5, 1.0, 3.7,
                     0.4, 4.2, 5.1, 1.2,
                             3.5, 4.5, 7.0, 2.7]);

分别等价于我们上面的一维和二维数组初始化方式。

推导式

除了使用内置函数或者列表形式来进行初始化意外，MiniZinc也提供了和Python一样的推导式方式对数组进行初始化。其语法为：

[<expression>| <generator-expr1>, <generator-expr2>,...]

在推导过程中我们也可以进行一些检验：

[<expression>| <generator-expr1>, <generator-expr2>, ..., where <bool-expr>]

例如

array[int] of int: u = [i + j | i in 1..3, j in 2..5];
array[int] of int: v = [i * j | i in 2..6, j in 3..7 where i * j <= 20];

会生成下面的两个数组

[3, 4, 5, 6, 4, 5, 6, 7, 5, 6, 7, 8]
[6, 8, 10, 12, 14, 9, 12, 15, 18, 12, 16, 20, 15, 20, 18]

注意这里因为我们事先不知道数组的长度，我们用了array[int]来让求解器自己推导数组长度。

相应的，集合也可以用推导式的方式生成，唯一的不同就是用{}替换[]。

获得数组的下标

因为在列表推导式的运用，我们可能产生不知道列表下标范围的情况。此时我们可以使用内置函数index_set来获得一维数组的下标范围。

例如：

array[int] of int: u = [i + j | i in 1..3, j in 2..5];
set of int: k = index_set(u);

这里我们的k会得到范围1..12。

对于多维数组，我们需要指定数组的总维度k和我们想知道具体哪个维度m的下标。

MiniZinc中内置了一系列函数index_set_<m>of<k>来帮助我们得到下标，其中k<=6。例如我们想得到二维数组第二个维度的下标，我们就可以使用函数index_set_2of2。

基础运算

四则运算

MiniZinc中支持的整数运算有基础的四则运算加减乘除：+, -, *, div。对于浮点数，除法表示为/。

<u>注意这里的整数除法是div而非/，/在MiniZinc中特指浮点数的除法</u>，处理整数时可能得到意料之外的结果。

除此之外还有我们常用的取余mod，整数的取余运算a mod b会得到和a同号的结果，也就是说一定有a = b * (a div b) + (a mod b)。

内置的运算函数

下面给出一些在MiniZinc中常用的内置运算函数。

对于数字：

对于数组：

上一篇下一篇

猜你喜欢

热点阅读