运筹学最大流问题建模

2025-03-10 11:22:18
推荐回答(1个)
回答1:

从左到右,顶点分为4部分:
s:起点
a1、a2、a3、a4:代表4个家庭的4个点
b1、b2、b3、b4:代表4辆车的4个点
t:终点

边:
从s到每个ai,边的容量是家庭人数,也就是说都是4。
从每个ai,到每个bi,一共16条边,容量都是2,因为每个家庭到一辆车上的最多有2人。
从每个bi到t,容量是车的人数限制。

由于每条边都是整数,这个最大流最后解出来也都是整数。