运筹学经典问题（四）：多商品网络流问题

2023-12-13 10:30:10

问题描述

多商品网络流问题（Multicommodity Network Flow, MCNF）是指在一个图网络中，多个商品从各自起点运输到各自终点的问题。

在这里插入图片描述

更具体的，给定一个图网络 G = ( V , A ) G=(V, A) G=(V,A)：

K K K：表示商品的集合；

( s k , t k , d k ) (s_k,t_k, d_k) (sk?,tk?,dk?)：表示商品 k k k的起点、终点和需求量；

u i j u_{ij} uij?：弧段 ( i , j ) ∈ A (i, j) \in A (i,j)∈A的容量；

c i j k c_{ij}^k cijk?：商品 k k k在弧段 ( i , j ) ∈ A (i, j) \in A (i,j)∈A上流动的单位成本。

MCNF问题的目标就是在图网络中，找到一条使得总运输成本最低，且能满足各个商品需求量的路径。

数学建模

变量：
x i j k x_{ij}^k xijk?：商品 k k k在弧段 ( i , j ) (i, j) (i,j)上运输的货量；

m i n ∑ ( i , j ) ∈ A ∑ k ∈ K c i j x i j s . t . ∑ j x i j ? ∑ j x j i = { d k , i = s k , k ∈ K ? d k , i = t k , k ∈ K 0 , e l s e , ? i ∈ V , k ∈ K , i ≠ s k , j ≠ t k ∑ k ∈ K x i j k ≤ u i j , ? ( i , j ) ∈ A min \sum_{(i, j)\in A}\sum_{k \in K}c_{ij}x_{ij}\\ s.t. \sum_jx_{ij} - \sum_jx_{ji} =\begin{cases} d_k, i=s_k,k\in K\\ -d_k, i=t_k, k\in K\\ 0, else, \forall i \in V, k \in K, i \neq s_k, j \neq t_k \end{cases}\\ \sum_{k\in K} x_{ij}^k \leq u_{ij}, \forall (i,j) \in A min(i,j)∈A∑?k∈K∑?cij?xij?s.t.j∑?xij??j∑?xji?=? ? ??dk?,i=sk?,k∈K?dk?,i=tk?,k∈K0,else,?i∈V,k∈K,i=sk?,j=tk??k∈K∑?xijk?≤uij?,?(i,j)∈A

目标函数表示最小化运输成本；

第一个约束为流量平衡约束，对于每个商品，分别对于其起点、终点和途径点做了约束（起点：流出-流入=需求量，终点：流出-流入= -需求量，途径点：流出-流入=0）；

第二个约束对网络中的每条边的流量做了约束，不得超过最大容量。

性质

当MCNF中的决策变量可以为小数时，该问题为一个线性规划问题；当MCNF中的决策变量仅能取整数时，该问题是一个NP-complete（也是NP-hard）问题。todo: 补一篇文章梳理一下NP-hard、NP-complete的含义。

问题求解

todo：python代码补充

参考资料

  1. 运筹优化常用算法、模型及案例实战：Python+Java 实现. 刘兴禄，熊望祺，臧永森，段宏达，曾文佳，陈伟坚.

文章来源:https://blog.csdn.net/JESSIENOTCAR/article/details/134958297
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。