Python小白的数学建模课20。网络流优化案例

　　在实际工作和数模竞赛中，网络最大流问题、最小费用流问题和最小费用最大流问题都有很多延伸和推广的应用。本文介绍了常见的网络最大流问题、最小费用流问题的应用与推广，及其解题方法。本文选择多源多汇物流转运问题、多商品流问题案例，详细介绍网络流问题的分析方法和解决方案，并使用线性规划方法建模和编程。1。网络流问题的应用与推广
　　流在生活中十分常见，例如交通系统中的人流、车流、物流，供水管网中的水流，金融系统中的现金流，网络中的信息流。网络流优化问题是基本的网络优化问题，应用非常广泛，遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等领域。
　　网络流优化问题最重要的指标是每条边的成本和容量限制，既要考虑成本最低（最短路径问题），又要满足容量限制（最大流问题），由此产生了网络最大流问题、最小费用流问题和最小费用最大流问题。在《Python小白的数学建模课19。网络流优化》一文中，我们详细介绍了网络最大流问题、最小费用流问题和最小费用最大流问题的算法、编程和案例。
　　不论在实际工作中，还是在数模竞赛中，网络最大流问题、最小费用流问题和最小费用最大流问题都有很多延伸和推广的应用。小白同学对于网络图的概念和思维逻辑比较生疏，面对变换和深化的题型往往对题目能有基本判断和思路、但找不到具体的解决方法，觉得应该能做出来但就是差一点。
　　本文选择多源多汇物流转运问题、多商品流问题案例，详细介绍网络流问题的分析方法和解决方案，并使用线性规划方法建模和编程。
　　对于小白同学来说，这两个案例的建模和编程都有些复杂。别急，也别怕，问题分析和程序说明都很详细，只要静下来慢慢读，将程序说明、源程序和运行结果对照着读，相信小白同学也能看懂。2。网络最大流问题的应用与推广2。1指定流量的可行流
　　我们在《19。网络流优化》一文讨论了网络最大流的算法。如果不是计算最大流，而是要计算指定流量v的可行流，可以用如下图所示的增广路（相当于辅助线）方法处理。
　　（1）在容量网络G上增加一个顶点t’和一条边（t，t’），构建一个新的容量网络G’，令边（t，t’）的容量为v；
　　（2）对于容量网络G‘，计算从源点s到汇点t’的最大流fmax显然fmaxv；
　　（3）若vfmax，则容量网络G不存在满足流量v的可行流；若vfmax，则从最大流fmax的路径中去掉边（t，t’）即得到容量网络G满足流量v的可行流。
　　另一种思路是，设置源点s汇点t的流量为v，再按最小费用流即可。这种方法不仅得到了流量v的可行流，而且是最小费用流，但该方法的计算量较大。主要程序如下，完整程序详见《Python小白的数学建模课19。网络流优化》。G2。addnode（s，demandv）nx。mincostflow（）的设置要求G2。addnode（t，demandv）设置源点汇点的流量求最小费用流（demandv）minFlowCostnx。mincostflowcost（G2）求最小费用流的费用minFlowDictnx。mincostflow（G2）求最小费用流
　　2。2多源点多汇点的最大流
　　《19。网络流优化》一文讨论的网络流优化问题，都是单源点、单汇点的网络。对于多源点单汇点、单源点多汇点、多源点多汇点的容量网络的最大流问题，可以通过如下图所示的增加一个超级源点和或超级汇点的方法处理。
　　（1）在容量网络G上增加一个超级源点s和一个超级源点t；从超级源点s向网络G中的每个源点连一条容量为infty的边，从网络G中的每个汇点向超级汇点t连一条容量为infty的边。于是得到了一个新的容量网络G’。
　　（2）对于容量网络G‘，计算从超级源点s到超级汇点t的最大流fmax，即为多源多汇容量网络G的最大流。
　　使用NetworkX工具包，也有另一种特殊方法可以解决多源多汇最大流问题。
　　NetworkX中求解费用最小流问题的函数mincostflow（）、mincostflowcost（）是求解费用最小流问题的函数，并不是设定供应点、需求点，而是通过设置顶点属性‘demand’确定供应点、需求点及各顶点的净流量，因而允许网络中存在多个供应点、需求点。mincostflow（G，demand‘demand’，capacity‘capacity’，weight‘weight’）
　　mincostflowcost（G，demand‘demand’，capacity‘capacity’，weight‘weight’）
　　因此，对于指定流量的多源多汇网络可行流问题，只要在每个源点、汇点的顶点属性‘demand’设置对应的供应量、需求量，再按最小费用流即可。这种方法不仅得到了流量v的可行流，而且是最小费用流。类似地，对于多源多汇网络的最大流问题，可以参考《19。网络流优化》中3。4案例：运输费用的方法，v从1逐渐递增，计算所有流量下的最小费用流，直到达到网络容量的极限，即得到容量网络的最大费用流。该方法不需要构造新的容量网络，编程实现简单，而且可以获得最大流量的最小费用流，但计算量很大。2。3带顶点容量约束的最大流
　　标准形式的网络流优化问题，只有边的容量约束，没有顶点的容量约束。在实际问题中，顶点所表示的工厂、仓库、销售点，都存在最大储存量，因而带有顶点的容量约束。
　　对于顶点容量约束的网络流问题，可以通过如下图所示的将每个带约束的顶点N分拆为两个顶点（入顶点Nin和出顶点Nout）的方法处理：
　　（1）将指向顶点N的边，改为指向入顶点Nin；
　　（2）将顶点N所指向的边，改为出顶点Nout所指向的边；
　　（3）增加一条从入顶点Nin指向出顶点Nout的边，边的容量为顶点N的容量，单位费用为0。
　　于是得到了一个新的容量网络G’。由此，原有网络G的顶点N的容量限制，转化为网络G’的边（Nin，Nout）的容量限制。带顶点约束的容量网络G的最大流问题，转化为新的标准形式的容量网络G’的最大流问题。
　　3。最小费用流问题的应用与推广3。1运输问题
　　有出发地（供应点、供应量）和目的地（需求点、需求量），没有转运点，没有路段（边）的容量限制，目标是总运输成本最小或总利润最大。3。2指派问题
　　出发地（供应点、供应量1）是人，目的地（需求点、需求量1）是任务，没有转运点，没有路段（边）的容量限制，目标是总指派成本最小或总利润最大。3。3转运问题
　　有出发地（供应点、供应量）和目的地（需求点、需求量），有转运点，没有路段（边）的容量限制（或带有容量限制），目标是总流量费用最小或总利润最大。3。4最大流问题
　　最大流问题是特殊的最小费用流问题：有供应点、需求点、转运点，有路段（边）的容量限制，没有供应量和需求量的限制，目标是通过网络到目的地的总流量最大。3。5最短路问题
　　有供应点（供应量1）、需求点（需求量1）、转运点，没有路段（边）的容量限制，目标是通过网络到目的地的总距离最短。4。案例：多源多汇的物流转运问题4。1问题描述
　　如图所示，某公司的工厂（供应点）位于F1、F2，仓库（中转点）位于W1、W2，零售商（需求点）位于R1、R2、R3、R4。从工厂生产的产品先送到仓库，再由仓库发到零售商。图中给出了各供应点和需求点的流量、每条发货线路的最大流量、单位流量的运输成本，要求在产销平衡的条件下，找出总运输费用最小的运输方案。
　　4。2问题分析
　　这是一个运输路径规划问题，也是一个多源点、多汇点的最小费用流问题。
　　对于多源多汇的最小费用流问题，构造一个费用网络G，网络G的各条边没有容量限制，单位流量的运输成本为边的权值w。F1、F2是网络G的源点（供应点），R1R4是汇点（需求点），W1、W2是中间节点。F1、F2的供应量与R1R4的需求量是平衡的。因此可以用NetworkX的maximumflow（）函数求出最小费用流。
　　该问题也是一个典型的线性规划问题，可以用线性规划方法求解。
　　式中：f（i，j）表示路段（i，j）的流量，w（i，j）表示路段（i，j）的单位流量运输成本，S表示源点（供应点），T表示汇点（需求点）。
　　对于上式描述的线性规划问题，可以用PuLP工具包求解（参见《Python小白的数学建模课03。线性规划》），编程步骤如下：
　　（1）导入PuLP库函数；
　　（2）定义一个线性规划问题；
　　（3）定义决策变量，决策变量的上下限：f11：F1W1流量，0f11600f12：F1W2流量，0f12600f21：F2W1流量，0f21400f22：F2W2流量，0f22400w11：W1R1流量，0w11200w12：W1R2流量，0w12150w13：W1R3流量，0w13350w14：W1R4流量，0w14300w21：W2R1流量，0w21200w22：W2R2流量，0w22150w23：W2R3流量，0w23350w24：W2R4流量，0w24300
　　（4）定义目标函数：mincost2f113f123f21f222w116w123w136w144w214w226w235w24
　　（5）定义约束条件：f11f12600f21f22400f11f21w11w12w13w14f12f22w21w22w23w24w11w21200w12w22150w13w23350w14w24300
　　注意，f11f12600，f21f22400，意味着允许存在产销不平衡的情况。
　　（6）求解规划问题，输出优化结果
　　本文给出了基于NetworkX工具包和基于PuLP工具包的两种方法的程序，以便小白理解图论中的最小费用流问题与线性规划问题的联系。4。3Python例程mathmodel21v1。pyDemo21ofmathematicalmodelingalgorithmDemoofnetworkflowproblemoptimizationwithNetworkXCopyright2021YouCans，XUPTCrated：20210718importnumpyasnpimportmatplotlib。pyplotasplt导入Matplotlib工具包importnetworkxasnx导入NetworkX工具包importpulp导入pulp库4。多源多汇最小费用流问题（Capacitynetworkwithmultisourceandmultisink）4。1费用网络创建有向图G1nx。DiGraph（）创建一个有向图DiGraphG1。addedgesfrom（〔（F1，W1，｛capacity：9e5，weight：2｝），F1F2：工厂（F1，W2，｛capacity：9e5，weight：3｝），W1W2：仓库（F2，W1，｛capacity：9e5，weight：3｝），（F2，W2，｛capacity：9e5，weight：1｝），（W1，R1，｛capacity：9e5，weight：2｝），R1R4：零售店（W1，R2，｛capacity：9e5，weight：6｝），（W1，R3，｛capacity：9e5，weight：3｝），（W1，R4，｛capacity：9e5，weight：6｝），（W2，R1，｛capacity：9e5，weight：4｝），（W2，R2，｛capacity：9e5，weight：4｝），（W2，R3，｛capacity：9e5，weight：6｝），（W2，R4，｛capacity：9e5，weight：5｝）〕）添加边的属性capacity，weightG1。addnode（F1，demand600）nx。mincostflow（）的设置要求G1。addnode（F2，demand400）设置源点的流量，负值表示净流出G1。addnode（R1，demand200）设置汇点的流量，正值表示净流入G1。addnode（R2，demand150）G1。addnode（R3，demand350）G1。addnode（R4，demand300）pos｛F1：（2，6。5），F2：（2，3。5），W1：（5，6。5），W2：（5，3。5），R1：（9，8），R2：（9，6），R3：（9，4），R4：（9，2）｝指定顶点绘图位置4。2用NetworkX求最小费用流求最小费用流（demandv）minFlowCostnx。mincostflowcost（G1）求最小费用流的费用minFlowDictnx。mincostflow（G1）求最小费用流minFlowCost，minFlowDictnx。networksimplex（G2）求最小费用流与上行等效整理边的标签，用于绘图显示数据格式转换edgeCapacitynx。getedgeattributes（G1，weight）edgeLabel｛｝边的标签foriinedgeCapacity。keys（）：整理边的标签，用于绘图显示edgeLabel〔i〕fw｛edgeCapacity〔i〕：｝边的容量edgeLists〔〕foriinminFlowDict。keys（）：forjinminFlowDict〔i〕。keys（）：edgeLabel〔（i，j）〕，fstr（minFlowDict〔i〕〔j〕）取出每条边流量信息存入边显示值ifminFlowDict〔i〕〔j〕0：edgeLists。append（（i，j））print（1。NetworkX网络与图（最小费用流优化结果）：）NetworkX工具包print（最小费用：｛｝。format（minFlowCost））输出最小费用的值print（最小费用流的路径及流量：，minFlowDict）输出最小费用流的途径和各路径上的流量print（最小费用流的路径：，edgeLists）输出最小费用流的途径绘制有向网络图fig，axplt。subplots（figsize（8，6））ax。text（1。2，6。4，600，colornavy）ax。text（1。2，3。4，400，colornavy）ax。text（9。3，7。9，200，colornavy）ax。text（9。3，5。9，150，colornavy）ax。text（9。3，3。9，350，colornavy）ax。text（9。3，1。9，300，colornavy）ax。settitle（Capacitynetworkwithmultisourceandmultisink）nx。draw（G1，pos，withlabelsTrue，nodecolorskyblue，nodesize300，fontsize10）绘制有向图，显示顶点标签edgeLabel1nx。getedgeattributes（G1，weight）nx。drawnetworkxnodes（G1，pos，nodelist〔F1，F2〕，nodecolororange）设置指定顶点的颜色、宽度nx。drawnetworkxnodes（G1，pos，nodelist〔W1，W2〕，nodecolorc）设置指定顶点的颜色、宽度nx。drawnetworkxedgelabels（G1，pos，edgeLabel，fontsize10，labelpos0。25）显示边的标签：capacity，weightminCostFlownx。drawnetworkxedges（G1，pos，edgelistedgeLists，edgecolorm，width2）设置指定边的颜色、宽度plt。xlim（0。5，10。5）plt。ylim（1，9）plt。axis（on）plt。show（）4。3用线性规划求最小费用流（1）建立优化问题TransportCost：求最小值（LpMinimize）transportLPpulp。LpProblem（TransportCostProblem，sensepulp。LpMinimize）定义问题，求最小值（2）定义决策变量f11f22，w11w24f11pulp。LpVariable（F1W1，lowBound0，upBound600，catContinuous）定义f11f12pulp。LpVariable（F1W2，lowBound0，upBound600，catContinuous）定义f12f21pulp。LpVariable（F2W1，lowBound0，upBound400，catContinuous）定义f21f22pulp。LpVariable（F2W2，lowBound0，upBound400，catContinuous）定义f22w11pulp。LpVariable（W1R1，lowBound0，upBound200，catContinuous）定义w11w21pulp。LpVariable（W2R1，lowBound0，upBound200，catContinuous）定义w21w12pulp。LpVariable（W1R2，lowBound0，upBound150，catContinuous）定义w12w22pulp。LpVariable（W2R2，lowBound0，upBound150，catContinuous）定义w22w13pulp。LpVariable（W1R3，lowBound0，upBound350，catContinuous）定义w13w23pulp。LpVariable（W2R3，lowBound0，upBound350，catContinuous）定义w23w14pulp。LpVariable（W1R4，lowBound0，upBound300，catContinuous）定义w14w24pulp。LpVariable（W2R4，lowBound0，upBound300，catContinuous）定义w24（3）定义目标函数costtransportLP（2f113f123f21f222w116w123w136w144w214w226w235w24）运输费用（4）设置约束条件transportLP（f11f12600）等式约束transportLP（f21f22400）等式约束transportLP（w11w21200）等式约束transportLP（w12w22150）等式约束transportLP（w13w23350）等式约束transportLP（w14w24300）等式约束transportLP（f11f21w11w12w13w14）等式约束transportLP（f12f22w21w22w23w24）等式约束（5）求解线性规划问题transportLP。solve（）（6）输出优化结果print（2。PuLP线性规划（最小费用的优化结果）：）PuLP工具包print（transportLP）输出问题设定参数和条件print（Optimizationresult）PuLP工具包forvintransportLP。variables（）：print（v。name，，v。varValue）输出每个变量的最优值print（最小运输费用，pulp。value（transportLP。objective））输出最优解的目标函数值plt。show（）
　　4。4程序运行结果1。NetworkX网络与图（最小费用流优化结果）：最小费用：5200最小费用流的路径及流量：｛F1：｛W1：600，W2：0｝，W1：｛R1：200，R2：0，R3：350，R4：50｝，W2：｛R1：0，R2：150，R3：0，R4：250｝，F2：｛W1：0，W2：400｝，R1：｛｝，R2：｛｝，R3：｛｝，R4：｛｝｝最小费用流的路径：〔（F1，W1），（W1，R1），（W1，R3），（W1，R4），（W2，R2），（W2，R4），（F2，W2）〕2。PuLP线性规划（最小费用的优化结果）：MINIMIZE2F1W13F1W23F2W11F2W22W1R16W1R23W1R36W1R44W2R14W2R26W2R35W2R40SUBJECTTOC1：F1W1F1W2600C2：F2W1F2W2400C3：W1R1W2R1200C4：W1R2W2R2150C5：W1R3W2R3350C6：W1R4W2R4300C7：F1W1F2W1W1R1W1R2W1R3W1R40C8：F1W2F2W2W2R1W2R2W2R3W2R40VARIABLESF1W1600ContinuousF1W2600ContinuousF2W1400ContinuousF2W2400ContinuousW1R1200ContinuousW1R2150ContinuousW1R3350ContinuousW1R4300ContinuousW2R1200ContinuousW2R2150ContinuousW2R3350ContinuousW2R4300ContinuousOptimizationresultF1W1550。0F1W250。0F2W10。0F2W2400。0W1R1200。0W1R20。0W1R3350。0W1R40。0W2R10。0W2R2150。0W2R30。0W2R4300。0最小运输费用5200。0
　　5。案例：多商品流问题
　　多商品流问题（MultiCommodityFlowProlem）是多种商品（物流、人流、数据流等）在具有容量限制的网络中从供应点流到需求点的网络流问题，通常是NP问题。多商品流问题的优化目标是以最小的成本实现商品在网络中的流通，约束条件主要是每条边的容量。
　　多商品流路径优化问题具有广泛的实际应用，如交通运输、物流网络、电信网络以及产销系统。一些实际问题带有特殊要求，如在电信网络中要考虑时间延迟和可靠性问题，在零担货运中需要考虑配货拼车，有时需要综合考虑运输的时间和成本。5。1问题描述
　　将城市v0生产的商品A、B通过铁路网分别运送到城市v6、v5，商品A、B的需求量分别为6。0、5。0单位。铁路网的结构如图所示，每条线路（边）上的数值表示该线路的容量和单位运费。求完成商品运输任务的最小费用的运输方案。
　　5。2问题分析
　　这是一个多商品流问题，具有1个供应点V0和2个需求点V5、V6。
　　对于多源多汇的多商品流最小费用流问题，构造一个费用网络G，网络G的各条边具有容量限制，单位流量的运输成本为边的权值w。源点（供应点）为流量净输出，汇点（需求点）为流量净输入；中间节点不带存储，每种商品的净流量都为0。所有线路的商品总流量不超过边的容量限制。
　　该问题也是一个典型的线性规划问题，可以用如下模型描述：
　　式中：M表示商品品种，S表示源点（供应点），T表示汇点（需求点），w（i，j）表示路段（i，j）的单位流量运输成本，f（i，j，m）表示商品m在路段（i，j）的流量，
　　NetworkX工具包中没有多商品流问题的解决方法，在Python其它图与网络工具包也没有找到多商品流问题的函数。网络流问题本质上是线性规划问题，对于上式描述的线性规划问题，可以用PuLP工具包求解（参见《Python小白的数学建模课03。线性规划》）。
　　多商品流的目标是各种商品从供应点运送到需求点的总费用最小。定义各商品m在各路段（i，j）的流量f（i，j，m）为决策变量，则目标函数为商品m在各路段（i，j）的运输费用之和mi，jEwijfij。多商品流的模型主要包含流守恒约束和容量限制。
　　本案例的问题中，不同商品A、B是从同一供应点发出，运送到不同需求点。但本案例的数学模型和例程，并不限定从不同商品从同一供应点发出，也就是说可以适用于多源多汇的多商品流问题。另外，如果如果不同商品在各条边的运费单价不同，只要相应修改例程的目标函数即可处理。
　　5。3程序说明
　　本程序并不复杂，但有些地方的处理可能会令小白感到困惑，详细说明如下：图的输入：稀疏有向图，使用nx。DiGraph（）定义有向图，使用G。addweightededgesfrom（）函数以列表向图中添加多条赋权边，每个赋权边以元组（node1，node2，｛‘capacity’：c1，‘weight’：w1｝）定义属性‘capacity’和‘weight’。注意必须以关键字‘capacity’表示容量，以‘weight’表示单位流量的成本。supplyA、supplyB表示商品A、B的供应量，来自题目要求。注意网络的最大流量必须大于等于各种商品的总供应量或总需求量，否则将没有可行解。绘制网络图，以边的标签显示边的容量‘capacity’和单位流量的成本‘weight’。用PuLP求解多商品流线性规划问题：
　　（1）定义一个线性规划问题MCFproblem。
　　（2）定义决策变量fA、fB，并设置决策变量类型和上下限：fA、fB都是一维数组，表示商品A、B在网络G2各条边的实际流量。根据题意将决策变量设为连续变量，如果问题要求整车配货等条件，可以相应地设为整数变量。fA、fB的下限为0，上限应为各条边的容量。但由于pulp。LpVariable。dicts函数中定义上限upBound为实数类型，不能是数组，无法对每个决策变量设定不同的上限值。因此，在定义决策变量fA、fB时，将上限设为所有边的容量的最大值maxCapacity。每条边的具体容量约束，则作为约束条件处理。
　　G2。edges（）表示遍历网络G2的边，因此fA、fB是A、B在所有边edges的流量：｛（v0，v1）：FlowA（v0，v1），（v0，v2）：FlowA（v0，v2），（v1，v3）：FlowA（v1，v3），（v2，v1）：FlowA（v2，v1），（v2，v4）：FlowA（v2，v4），（v3，v4）：FlowA（v3，v4），（v3，v5）：FlowA（v3，v5），（v3，v6）：FlowA（v3，v6），（v4，v1）：FlowA（v4，v1），（v4，v5）：FlowA（v4，v5），（v4，v6）：FlowA（v4，v6）｝｛（v0，v1）：FlowB（v0，v1），（v0，v2）：FlowB（v0，v2），（v1，v3）：FlowB（v1，v3），（v2，v1）：FlowB（v2，v1），（v2，v4）：FlowB（v2，v4），（v3，v4）：FlowB（v3，v4），（v3，v5）：FlowB（v3，v5），（v3，v6）：FlowB（v3，v6），（v4，v1）：FlowB（v4，v1），（v4，v5）：FlowB（v4，v5），（v4，v6）：FlowB（v4，v6）｝
　　（3）定义目标函数：
　　目标函数是A、B在所有边edges的总运费，即流量fA、fB与单位流量成本‘weight’的乘积的总和。
　　需要说明的是：（1）通过edgeWeightnx。getedgeattributes（G2，‘weight’）将所有边的属性‘weight’转换为字典类型，就可以用foredgeinG2。edges遍历操作。（2）如果不同商品在各条边的运费单价不同，只要将目标函数中的KaTeXparseerror：Undefinedcontrolsequence：atposition8：w（edge）〔fA（edge）fB（e修改为KaTeXparseerror：Undefinedcontrolsequence：atposition9：wA（edge）fA（edge）wB（edg即可。（3）。设置目标函数MCFproblempulp。lpSum（〔edgeWeight〔edge〕（fA〔edge〕fB〔edge〕）foredgeinG2。edges〕）总运输费用
　　（4）定义约束条件：
　　（4）定义约束条件：
　　多商品流的模型主要包含边的容量约束和顶点的流守恒约束和两个方面。
　　1。边的容量约束，即每条边上各种商品流量之和不大于边的容量。
　　2。顶点的流守恒约束，分为源点（供应点）、汇点（需求点）和中间节点三种情况：通过fornodeinG2。nodes可以遍历网络的所有顶点。indegree（node）计算顶点node的入度，入度为0的顶点是源点；outdegree（node）计算顶点node的出度，出度为0的顶点是汇点。由此可以判断网络的源点、汇点和中间节点；也可以根据题目直接判断各中商品的供应点、需求点进行定义。inedges（nbunchnode）返回顶点node的所有入边，outedges（nbunchnode）返回顶点node的所有出边。源点：对于每种商品，所有输出边的流量之和不大于该顶点该商品的供应量。对于供应量、需求量相等的问题，也可以将该约束条件设为输出流量等于供应量。汇点：对于每种商品，所有输入边的流量之和等于该顶点该商品的供应量。案例问题有多个需求点，并对应了不同品种的商品，因此需要分别进行设置。中间节点：对于每种商品，中间节点的总流入量与总流出量相等。注意，如果供应点、需求点也是流通线路而不是源点、汇点，则不必分作三种情况，都按照中间节点处理，但对每个节点需要设置每种商品的净流量。源点：v0，出边：〔（v0，v1），（v0，v2）〕中间点：v1，入边：〔（v0，v1），（v2，v1），（v4，v1）〕，出边：〔（v1，v3）〕中间点：v2，入边：〔（v0，v2）〕，出边：〔（v2，v1），（v2，v4）〕中间点：v3，入边：〔（v1，v3）〕，出边：〔（v3，v4），（v3，v5），（v3，v6）〕中间点：v4，入边：〔（v2，v4），（v3，v4）〕，出边：〔（v4，v1），（v4，v5），（v4，v6）〕汇点：v5，入边：〔（v3，v5），（v4，v5）〕汇点：v6，入边：〔（v3，v6），（v4，v6）〕
　　（6）求解规划问题，输出优化结果5。4Python例程mathmodel21v1。pyDemo21ofmathematicalmodelingalgorithmDemoofnetworkflowproblemoptimizationwithNetworkXCopyright2021YouCans，XUPTCrated：20210722importnumpyasnpimportmatplotlib。pyplotasplt导入Matplotlib工具包importnetworkxasnx导入NetworkX工具包importpulp导入pulp库5。多商品流问题（MulticommodityFlowProblem）5。1创建有向图G2nx。DiGraph（）创建一个有向图DiGraphG2。addedgesfrom（〔（v0，v1，｛capacity：7，weight：4｝），（v0，v2，｛capacity：8，weight：4｝），（v1，v3，｛capacity：9，weight：1｝），（v2，v1，｛capacity：5，weight：5｝），（v2，v4，｛capacity：9，weight：4｝），（v3，v4，｛capacity：6，weight：2｝），（v3，v5，｛capacity：10，weight：6｝），（v3，v6，｛capacity：10，weight：6｝），（v4，v1，｛capacity：2，weight：1｝），（v4，v5，｛capacity：5，weight：2｝），（v4，v6，｛capacity：5，weight：2｝）〕）添加边的属性capacity，weightpos｛v0：（0，5），v1：（4，2），v2：（4，8），v3：（10，2），v4：（10，8），v5：（15，3），v6：（15，7）｝指定顶点绘图位置supplyA6。0商品A供应量supplyB5。0商品B供应量print（SupplyA：｛｝SupplyB：｛｝。format（supplyA，supplyB））整理边的标签edgeLabel1nx。getedgeattributes（G2，capacity）edgeLabel2nx。getedgeattributes（G2，weight）edgeLabel｛｝foriinedgeLabel1。keys（）：edgeLabel〔i〕f（｛edgeLabel1〔i〕：｝，｛edgeLabel2〔i〕：｝）边的（容量，成本）5。2绘制有向网络图fig，axplt。subplots（figsize（8，6））nx。draw（G2，pos，withlabelsTrue，nodecolorskyblue，nodesize400，fontsize10）绘制有向图，显示顶点标签nx。drawnetworkxnodes（G2，pos，nodelist〔v0〕，nodecolororange，nodesize400）设置指定顶点的颜色、宽度nx。drawnetworkxnodes（G2，pos，nodelist〔v5，v6〕，nodecolorc，nodesize400）设置指定顶点的颜色、宽度nx。drawnetworkxedgelabels（G2，pos，edgeLabel，fontsize10）显示边的标签：capacity，weightax。settitle（MulticommodityFlowProblembyyoucansxupt）ax。text（1。8，5。2，A：｛｝。format（supplyA），colorm）ax。text（1。8，4。6，B：｛｝。format（supplyB），colornavy）ax。text（15。8，7。0，A：｛｝。format（supplyA），colorm）ax。text（15。8，2。8，B：｛｝。format（supplyB），colornavy）plt。xlim（3，18）plt。ylim（1，9）plt。axis（on）plt。show（YouCansXUPT）5。3用PuLP求解多商品流最小费用问题（MulticommodityFlowProblemYouCansXUPT）edgeWeightnx。getedgeattributes（G2，weight）weight，单位流量的成本edgeCapacitynx。getedgeattributes（G2，capacity）capacity，边的容量maxCapacitymax（edgeCapacity。values（））边的容量的最大值print（edgeWeight）print（max（Weight），max（edgeWeight。values（）））print（max（Capacity），max（edgeCapacity。values（）））（1）建立优化问题MCFproblem：求最小值（LpMinimize）MCFproblempulp。LpProblem（MultiCommodityFlowProb，sensepulp。LpMinimize）定义问题，求最小值（2）定义决策变量fA（edges），fB（edges）itemsG2〔A，B〕商品种类fApulp。LpVariable。dicts（FlowA，G2。edges（），lowBound0。0，upBoundmaxCapacity，catContinuous）fBpulp。LpVariable。dicts（FlowB，G2。edges（），lowBound0。0，upBoundmaxCapacity，catContinuous）print（fA）print（fB）（3）。设置目标函数MCFproblempulp。lpSum（〔edgeWeight〔edge〕（fA〔edge〕fB〔edge〕）foredgeinG2。edges〕）总运输费用（4）设置约束条件foredgeinG2。edges：边的最大流量约束MCFproblem（fA〔edge〕fB〔edge〕edgeCapacity〔edge〕0）edgeCapacity〔edge〕，边的容量fornodeinG2。nodes：顶点的净流量约束ifG2。indegree（node）0：入度为0，判断是否为源点print（源点：｛｝，出边：｛｝。format（node，G2。outedges（nbunchnode）））MCFproblem（sum（fA〔edge〕foredgeinG2。outedges（nbunchnode））supplyA）A供应量约束MCFproblem（sum（fB〔edge〕foredgeinG2。outedges（nbunchnode））supplyB）B供应量约束elifG2。outdegree（node）0：出度为0，判断是否为汇点print（汇点：｛｝，入边：｛｝。format（node，G2。inedges（nbunchnode）））ifnodev6：题目条件，v6需求为BMCFproblem（sum（fA〔edge〕foredgeinG2。inedges（nbunchnode））supplyA）A需求量约束ifnodev5：题目条件，v5需求为AMCFproblem（sum（fB〔edge〕foredgeinG2。inedges（nbunchnode））supplyB）B需求量约束else：中间节点，每种商品都是流量平衡print（中间点：｛｝，入边：｛｝，出边：｛｝。format（node，G2。inedges（nbunchnode），G2。outedges（nbunchnode）））MCFproblem（sum（fA〔edge1〕foredge1inG2。outedges（nbunchnode））sum（fA〔edge2〕foredge2inG2。inedges（nbunchnode））0）总流出总流入MCFproblem（sum（fB〔edge1〕foredge1inG2。outedges（nbunchnode））sum（fB〔edge2〕foredge2inG2。inedges（nbunchnode））0）总流出总流入（5）求解线性规划问题MCFproblem。solve（）（6）输出优化结果print（2。PuLP线性规划（最小费用的优化结果）：）PuLP工具包print（MCFproblem）输出问题设定参数和条件print（Optimizationresult）PuLP工具包forvinMCFproblem。variables（）：print（v。name，，v。varValue）输出每个变量的最优值print（最小运输费用，pulp。value（MCFproblem。objective））输出最优解的目标函数值plt。show（）
　　5。5程序运行结果2。PuLP线性规划（最小费用的优化结果）：MultiCommodityFlowProb：MINIMIZE4FlowA（v0，v1）4FlowA（v0，v2）1FlowA（v1，v3）5FlowA（v2，v1）4FlowA（v2，v4）2FlowA（v3，v4）6FlowA（v3，v5）6FlowA（v3，v6）1FlowA（v4，v1）2FlowA（v4，v5）2FlowA（v4，v6）4FlowB（v0，v1）4FlowB（v0，v2）1FlowB（v1，v3）5FlowB（v2，v1）4FlowB（v2，v4）2FlowB（v3，v4）6FlowB（v3，v5）6FlowB（v3，v6）1FlowB（v4，v1）2FlowB（v4，v5）2FlowB（v4，v6）0SUBJECTTOC1：FlowA（v0，v1）FlowB（v0，v1）7C2：FlowA（v0，v2）FlowB（v0，v2）8C3：FlowA（v1，v3）FlowB（v1，v3）9C4：FlowA（v2，v1）FlowB（v2，v1）5C5：FlowA（v2，v4）FlowB（v2，v4）9C6：FlowA（v3，v4）FlowB（v3，v4）6C7：FlowA（v3，v5）FlowB（v3，v5）10C8：FlowA（v3，v6）FlowB（v3，v6）10C9：FlowA（v4，v1）FlowB（v4，v1）2C10：FlowA（v4，v5）FlowB（v4，v5）5C11：FlowA（v4，v6）FlowB（v4，v6）5C12：FlowA（v0，v1）FlowA（v0，v2）6C13：FlowB（v0，v1）FlowB（v0，v2）5C14：FlowA（v0，v1）FlowA（v1，v3）FlowA（v2，v1）FlowA（v4，v1）0C15：FlowB（v0，v1）FlowB（v1，v3）FlowB（v2，v1）FlowB（v4，v1）0C16：FlowA（v0，v2）FlowA（v2，v1）FlowA（v2，v4）0C17：FlowB（v0，v2）FlowB（v2，v1）FlowB（v2，v4）0C18：FlowA（v1，v3）FlowA（v3，v4）FlowA（v3，v5）FlowA（v3，v6）0C19：FlowB（v1，v3）FlowB（v3，v4）FlowB（v3，v5）FlowB（v3，v6）0C20：FlowA（v2，v4）FlowA（v3，v4）FlowA（v4，v1）FlowA（v4，v5）FlowA（v4，v6）0C21：FlowB（v2，v4）FlowB（v3，v4）FlowB（v4，v1）FlowB（v4，v5）FlowB（v4，v6）0C22：FlowB（v3，v5）FlowB（v4，v5）5C23：FlowA（v3，v6）FlowA（v4，v6）6VARIABLESFlowA（v0，v1）10ContinuousFlowA（v0，v2）10ContinuousFlowA（v1，v3）10ContinuousFlowA（v2，v1）10ContinuousFlowA（v2，v4）10ContinuousFlowA（v3，v4）10ContinuousFlowA（v3，v5）10ContinuousFlowA（v3，v6）10ContinuousFlowA（v4，v1）10ContinuousFlowA（v4，v5）10ContinuousFlowA（v4，v6）10ContinuousFlowB（v0，v1）10ContinuousFlowB（v0，v2）10ContinuousFlowB（v1，v3）10ContinuousFlowB（v2，v1）10ContinuousFlowB（v2，v4）10ContinuousFlowB（v3，v4）10ContinuousFlowB（v3，v5）10ContinuousFlowB（v3，v6）10ContinuousFlowB（v4，v1）10ContinuousFlowB（v4，v5）10ContinuousFlowB（v4，v6）10ContinuousOptimizationresultFlowA（v0，v1）6。0FlowA（v0，v2）0。0FlowA（v1，v3）6。0FlowA（v2，v1）0。0FlowA（v2，v4）0。0FlowA（v3，v4）5。0FlowA（v3，v5）0。0FlowA（v3，v6）1。0FlowA（v4，v1）0。0FlowA（v4，v5）0。0FlowA（v4，v6）5。0FlowB（v0，v1）1。0FlowB（v0，v2）4。0FlowB（v1，v3）1。0FlowB（v2，v1）0。0FlowB（v2，v4）4。0FlowB（v3，v4）1。0FlowB（v3，v5）0。0FlowB（v3，v6）0。0FlowB（v4，v1）0。0FlowB（v4，v5）5。0FlowB（v4，v6）0。0最小运输费用105。0
　　【本节完】
　　版权声明：本文为CSDN博主youcans的原创文章，遵循CC4。0BYSA版权协议，转载请附上原文出处链接及本声明。
　　原文链接：https：blog。csdn。netyoucansarticledetails118882174