以最低价格和行驶距离购买购物清单中的所有物品

Question

我有一个清单，里面有20件我想买的东西 i = (1,...,20),镇上有5家超市 j = (1,...5),有两个给定条目：

Cij: the price of item "i" in supermarket "j"

Dj: the cost to travel between my house and the supermarket "j"

为了方便起见，我想购买最多2个市场的所有商品（所有商品都在所有市场）。在去市场旅行后，我总是回到家，我如何制定一个整数线性问题模型来最小化我的成本？

Answer 1

在 MiniZinc 中实现的一个简单的 MILP 模型（为简单起见，只有三个项目）。在模型中 x_ij 表示商品 j 是否从商店 i 购买，z_i 表示是否访问商店 i。

int: Stores = 5;
int: Items = 3;

set of int: STORE = 1..Stores;
set of int: ITEM = 1..Items;

array[STORE,ITEM] of int: C = [| 5, 4, 5
                               | 3, 2, 5 
                               | 5, 5, 2 
                               | 8, 1, 5 
                               | 1, 8, 2 |];

array[STORE] of int: D = [5, 4, 5, 2, 3];
    
array[STORE,ITEM] of var 0..1: x;
array[STORE] of var 0..1: z;

% visit at most two shops
constraint sum(i in STORE)(z[i]) <= 2;

% buy each item once
constraint forall(j in ITEM)
    (sum(i in STORE)(x[i,j]) = 1);

% can't buy from a shop unless visited
constraint forall(i in STORE)
    (sum(j in ITEM)(x[i,j]) <= Items*z[i]);

var int: cost = sum(i in STORE)(2*D[i]*z[i]) + sum(i in STORE, j in ITEM)(C[i,j]*x[i,j]);

solve minimize cost;

output ["cost=\(cost)\n"] ++ 
["x="] ++ [show2d(x)] ++
["z="] ++ [show(z)];

运行给出：

cost=14
x=[| 0, 0, 0 |
     0, 0, 0 |
     0, 0, 0 |
     0, 1, 0 |
     1, 0, 1 |]
z=[0, 0, 0, 1, 1]

以最低价格和行驶距离购买购物清单中的所有物品

Buy all items of a shopping list with minimum price and distance travelled

modeling

linear-programming