網(wǎng)上有很多關(guān)于pos機網(wǎng)絡(luò)顯示c,Python小白的數(shù)學(xué)建模課的知識，也有很多人為大家解答關(guān)于pos機網(wǎng)絡(luò)顯示c的問題，今天pos機之家(www.afbey.com)為大家整理了關(guān)于這方面的知識，讓我們一起來看下吧!
本文目錄一覽：
pos機網(wǎng)絡(luò)顯示c
流在生活中十分常見，例如交通系統(tǒng)中的人流、車流、物流，供水管網(wǎng)中的水流，金融系統(tǒng)中的現(xiàn)金流，網(wǎng)絡(luò)中的信息流。網(wǎng)絡(luò)流優(yōu)化問題是基本的網(wǎng)絡(luò)優(yōu)化問題，應(yīng)用非常廣泛。網(wǎng)絡(luò)流優(yōu)化問題最重要的指標是邊的成本和容量限制，既要考慮成本最低，又要滿足容量限制，由此產(chǎn)生了網(wǎng)絡(luò)最大流問題、最小費用流問題、最小費用最大流問題。本文基于 NetworkX 工具包，通過例程詳細介紹網(wǎng)絡(luò)最大流問題、最小費用流問題、最小費用最大流問題的建模和編程。1. 網(wǎng)絡(luò)流優(yōu)化1.1 網(wǎng)絡(luò)流網(wǎng)絡(luò)流優(yōu)化問題是基本的網(wǎng)絡(luò)優(yōu)化問題，應(yīng)用非常廣泛，遍及通訊、運輸、電力、工程規(guī)劃、任務(wù)分派、設(shè)備更新以及計算機輔助設(shè)計等領(lǐng)域。
流從源點流出、通過路徑輸送、流入到匯點，從而將目標從源點輸送到匯點。流在生活中十分常見，例如交通系統(tǒng)中的人流、車流、物流，供水管網(wǎng)中的水流，金融系統(tǒng)中的現(xiàn)金流，網(wǎng)絡(luò)中的信息流。
現(xiàn)實中的任何路徑都有最大流量（容量）的限制，在網(wǎng)絡(luò)中也是如此，并以邊的容量（Capacity）表示，一條邊的流量不能超過它的容量。
把這些現(xiàn)實問題抽象為網(wǎng)絡(luò)流問題，其特征是：（1）有向圖上的每條邊具有容量限制；（2）從源點流出的流量，等于匯點流入的流量；（3）源點和匯點之外的所有中間節(jié)點，流出的流量等于流入的流量。
注意在網(wǎng)絡(luò)流問題中有幾組概念容易混淆：
源點/匯點，起點/終點，供應(yīng)點/需求點：源點是只進不出的點，匯點是只出不進的點。源點/匯點 可以指定為問題的 起點/終點，但本質(zhì)上源點/匯點是由網(wǎng)絡(luò)結(jié)構(gòu)特征決定的，而不是被指定的。供應(yīng)點的供應(yīng)量和需求點的需求量是固定/確定的，而源點/匯點的目標是發(fā)出/接收的流量最大，不是固定值。容量 與 流量：容量是路徑（邊、?。┰试S的最大流通能力，用 c(i,j) 表示；流量則是路徑（邊、?。┥系膶嶋H流量，用 f(i,j) 表示。1.2 典型的網(wǎng)絡(luò)流優(yōu)化問題網(wǎng)絡(luò)流優(yōu)化問題最重要的指標是每條邊的成本和容量限制，既要考慮成本最低（最短路徑問題），又要滿足容量限制（最大流問題），由此產(chǎn)生了網(wǎng)絡(luò)最大流問題、最小費用流問題、最小費用最大流問題。
最大流問題（Maximun flow problem）：已知每條邊的容量，研究如何充分利用網(wǎng)絡(luò)能力，使從源點到匯點的總流量最大，也即在容量網(wǎng)絡(luò)中求流量最大的可行流。
最小費用流問題（Minimum cost problem）：已知每條邊的容量和單位流量的費用，對于給定的源點、匯點流量，研究如何分配流量和路徑，使總費用最小，也即在容量費用網(wǎng)絡(luò)中求成本最低的可行流。
最小費用最大流問題（Minimum cost maximum flow），已知每條邊的容量和單位流量的費用，研究網(wǎng)絡(luò)的流量最大的路徑中，費用最小的路徑。簡單地說，就是滿足最大流的路徑可能有多條，需要從其中找到成本最低的路徑。
Network 工具包求解網(wǎng)絡(luò)流優(yōu)化，包括最大流算法、最小割算法、最小費用流算法、最小費用最大流算法、容量縮放最小成本流算法。
2. 網(wǎng)絡(luò)最大流問題（MFP）2.1 網(wǎng)絡(luò)最大流算法網(wǎng)絡(luò)最大流問題，是在容量網(wǎng)絡(luò) G(V,E) 中求流量 v(f) 達到最大的可行流 f。在最大流問題中，只能有一個源點和一個匯點。
求解網(wǎng)絡(luò)最大流主要有增廣路法和預(yù)流推進法兩類方法。
增廣路方法從一條可行流開始，用 BFS 或 DFS 從源到匯找到一條增廣路，沿著該路徑修改流量，不斷重復(fù)這個過程，直到找不到增廣路時停止，此時的流就是最大流。增廣路方法有多種的實現(xiàn)算法，如 Ford Fulkerson 標號法的算法復(fù)雜度為 O ( E f ) （不穩(wěn)定），Edmonds Karp 算法的復(fù)雜度為
，Dinic 算法的復(fù)雜度為
，ISAP 算法的復(fù)雜度也是
，但其速度是最快的。
預(yù)流推進方法也稱壓入與重標記方法，算法從源點開始向下推流，通過不斷地尋找活結(jié)點，將流量推向以該點為起點的可推流邊（壓入過程）；如果在該點處找不到可推流邊，則將該點的高度加 1，以實現(xiàn)將過大的流向后推進（重標記過程）。最高標號預(yù)流推進（HLPP）算法的復(fù)雜度為
，改進的 HLPP 算法的復(fù)雜度為
2.2 NetworkX 求解網(wǎng)絡(luò)最大流問題Network 工具包提供了多種求解網(wǎng)絡(luò)最大流問題的算法和函數(shù)。其中 maximum_flow()、maximum_flow_value()、minimum_cut()、minimum_cut_value() 是集成了多種算法的通用函數(shù)，可以設(shè)置算法選項調(diào)用對應(yīng)的算法；其它函數(shù)則是具體的算法實現(xiàn)函數(shù)。
2.3 maximum_flow() 函數(shù)說明maximum_flow()、maximum_flow_value() 是求解網(wǎng)絡(luò)最大流問題的通用方法，集成了多種算法可供選擇。官網(wǎng)介紹詳見：https://networkx.org/documentation/stable/reference/algorithms/flow.html 。
maximum_flow (flowG, _s, _t, capacity=‘capacity’, flow_func=None, *kwargs)
maximum_flow_value (flowG, _s, _t, capacity=‘capacity’, flow_func=None, *kwargs)
主要參數(shù)：
flowG(NetworkX graph)：有向圖，邊必須帶有容量屬性 capacity（不能用 ‘weight’ ）。_s (node)：源點。_t (node)：匯點。capacity (string)：邊的容量屬性 capacity，缺省視為無限容量。flow_func(function)：調(diào)用算法的函數(shù)名，如：‘edmonds_karp’, ‘shortest_augmenting_path’, ‘dinitz’, ‘preflow_push’, ‘boykov_kolmogorov’。缺省值 ‘None’ ，選擇 ‘preflow_push’（HLPP 算法）。返回值：
flow_value(integer, float)：網(wǎng)絡(luò)最大流的流量值flow_dict (dict)：字典類型，網(wǎng)絡(luò)最大流的流經(jīng)路徑及各路徑的分配流量注意：如果要選擇指定算法，需要寫成以下形式 flow_func=nx.algorithms.flow.edmonds_karp，而不是 flow_func=edmonds_karp。也可以寫成：
from networkx.algorithms.flow import edmonds_karpflowValue, flowDict = nx.maximum_flow(G1, 's', 't', flow_func=edmonds_karp) 2.4 案例：輸油管網(wǎng)的最大流量
問題描述：
在輸油管網(wǎng)中，通過輸油管連接生產(chǎn)石油的油井、儲存石油的油庫和轉(zhuǎn)運的中間泵站。各站點之間的連接及管路的容量如圖（參見 2.6 程序運行結(jié)果圖）所示，求從油井到油庫的最大流量和具體方案。
問題分析：
這是一個網(wǎng)絡(luò)最大流問題，可以用頂點表示油井、油庫和泵站，其中油井為源點 s、油庫為匯點 t，用有向邊表示輸油管，有向邊的權(quán) capacity 表示輸油管的最大流量（容量）。
用 NetworkX 的 maximum_flow() 函數(shù)即可求出從從源點 s 到匯點 t 的最大流量。
程序說明：
圖的輸入。本例為稀疏有向圖，使用 nx.DiGraph() 定義一個有向圖。通過 add_edge(‘s’, ‘a(chǎn)’, capacity=6) 定義有向邊和屬性 capacity。注意必須以關(guān)鍵字 ‘capacity’ 表示容量，不能用權(quán)值 ‘weight’ 或其它關(guān)鍵字代替。nx.maximum_flow_value() 返回網(wǎng)絡(luò)最大流的值，nx.maximum_flow() 可以同時返回網(wǎng)絡(luò)最大流的值和網(wǎng)絡(luò)最大流的路徑及分配的流量。maxFlowDict 為字典類型，具體格式參加 2.6 程序運行結(jié)果。為了得到最大流所流經(jīng)的邊的列表edgeLists，要對 maxFlowDict 進行整理和格式轉(zhuǎn)換。在網(wǎng)絡(luò)最大流圖中，以邊的標簽顯示了邊的容量 c 和流量 f。2.5 Python 例程# mathmodel19_v1.py# Demo19 of mathematical modeling algorithm# Demo of network flow problem optimization with NetworkX# Copyright 2021 YouCans, XUPT# Crated：2021-07-15import numpy as npimport matplotlib.pyplot as plt # 導(dǎo)入 Matplotlib 工具包import networkx as nx # 導(dǎo)入 NetworkX 工具包# 1. 最大流問題 (Maximum Flow Problem，MFP)# 創(chuàng)建有向圖G1 = nx.DiGraph() # 創(chuàng)建一個有向圖 DiGraphG1.add_edge('s', 'a', capacity=6) # 添加邊的屬性 "capacity"G1.add_edge('s', 'c', capacity=8)G1.add_edge('a', 'b', capacity=3)G1.add_edge('a', 'd', capacity=3)G1.add_edge('b', 't', capacity=10)G1.add_edge('c', 'd', capacity=4)G1.add_edge('c', 'f', capacity=4)G1.add_edge('d', 'e', capacity=3)G1.add_edge('d', 'g', capacity=6)G1.add_edge('e', 'b', capacity=7)G1.add_edge('e', 'j', capacity=4)G1.add_edge('f', 'h', capacity=4)G1.add_edge('g', 'e', capacity=7)G1.add_edge('h', 'g', capacity=1)G1.add_edge('h', 'i', capacity=3)G1.add_edge('i', 'j', capacity=3)G1.add_edge('j', 't', capacity=5)# 求網(wǎng)絡(luò)最大流# maxFlowValue = nx.maximum_flow_value(G1, 's', 't') # 求網(wǎng)絡(luò)最大流的值# maxFlowValue, maxFlowDict = nx.maximum_flow(G1, 's', 't') # 求網(wǎng)絡(luò)最大流from networkx.algorithms.flow import edmonds_karp # 導(dǎo)入 edmonds_karp 算法函數(shù)maxFlowValue, maxFlowDict = nx.maximum_flow(G1, 's', 't', flow_func=edmonds_karp) # 求網(wǎng)絡(luò)最大流# 數(shù)據(jù)格式轉(zhuǎn)換edgeCapacity = nx.get_edge_attributes(G1, 'capacity')edgeLabel = {} # 邊的標簽for i in edgeCapacity.keys(): # 整理邊的標簽，用于繪圖顯示 edgeLabel[i] = f'c={edgeCapacity[i]:}' # 邊的容量edgeLists = [] # 最大流的邊的 listfor i in maxFlowDict.keys(): for j in maxFlowDict[i].keys(): edgeLabel[(i, j)] += ',f=' + str(maxFlowDict[i][j]) # 取出每條邊流量信息存入邊顯示值 if maxFlowDict[i][j] > 0: # 網(wǎng)絡(luò)最大流的邊（流量>0） edgeLists.append((i,j))# 輸出顯示print("最大流值: ", maxFlowValue)print("最大流的途徑及流量: ", maxFlowDict) # 輸出最大流的途徑和各路徑上的流量print("最大流的路徑：", edgeLists) # 輸出最大流的途徑# 繪制有向網(wǎng)絡(luò)圖fig, ax = plt.subplots(figsize=(8, 6))pos = {'s': (1, 8), 'a': (6, 7.5), 'b': (9, 8), 'c': (1.5, 6), 'd': (4, 6), 'e': (8, 5.5), # 指定頂點繪圖位置 'f': (2, 4), 'g': (5, 4), 'h': (1, 2), 'i': (5.5, 2.5), 'j': (9.5, 2), 't': (11, 6)}edge_labels = nx.get_edge_attributes(G1, 'capacity')ax.set_title("Maximum flow of petroleum network with NetworkX") # 設(shè)置標題nx.draw(G1, pos, with_labels=True, node_color='c', node_size=300, font_size=10) # 繪制有向圖，顯示頂點標簽nx.draw_networkx_edge_labels(G1, pos, edgeLabel, font_color='navy') # 顯示邊的標簽：'capacity' + maxFlownx.draw_networkx_edges(G1, pos, edgelist=edgeLists, edge_color='m') # 設(shè)置指定邊的顏色、寬度plt.axis('on') # Youcans@XUPTplt.show()2.6 程序運行結(jié)果
最大流值: 14最大流的途徑及流量: {'s': {'a': 6, 'c': 8}, 'a': {'b': 3, 'd': 3}, 'c': {'d': 4, 'f': 4}, 'b': {'t': 10}, 'd': {'e': 3, 'g': 4}, 't': {}, 'f': {'h': 4}, 'e': {'b': 7, 'j': 1}, 'g': {'e': 5}, 'j': {'t': 4}, 'h': {'g': 1, 'i': 3}, 'i': {'j': 3}}最大流的路徑： [('s', 'a'), ('s', 'c'), ('a', 'b'), ('a', 'd'), ('c', 'd'), ('c', 'f'), ('b', 't'), ('d', 'e'), ('d', 'g'), ('f', 'h'), ('e', 'b'), ('e', 'j'), ('g', 'e'), ('j', 't'), ('h', 'g'), ('h', 'i'), ('i', 'j')]3. 最小費用流問題（MCP）3.1 最小費用流問題的算法
在實際問題中，我們總是希望在完成運輸任務(wù)的同時，尋求運輸費用最低的方案。最小費用流問題，就是要以最小費用從出發(fā)點（供應(yīng)點）將一定的流量輸送到接收點（需求點）。在最小流問題中，供應(yīng)點、需求點的數(shù)量可以是一個或多個，但每個供應(yīng)點的供應(yīng)量和需求點的需求量是固定的。
最小費用流問題可以用如下的線性規(guī)劃問題描述
KaTeX parse error: No such environment: align* at position 8: \\begin{?a?l?i?g?n?*?}? & min\\;Cost=\\s…
求解最小費用流問題的方法很多，常見的如：連續(xù)最短路算法（Successive shortest path）、消圈算法（Cycle canceling）、原始對偶算法（Primal dual）、網(wǎng)絡(luò)單純性算法（Network simplex）和非均衡網(wǎng)絡(luò)流算法（Out of Kilter法）等。
網(wǎng)絡(luò)單純形是單純形算法的一個特殊應(yīng)用，它使用生成樹基來更有效地解決具有純網(wǎng)絡(luò)形式的線性規(guī)劃問題。網(wǎng)絡(luò)單純性為最小費用流問題提供了標準的解決方法，可以解決數(shù)萬個節(jié)點的大型問題。
最小費用流問題最重要的應(yīng)用是配送網(wǎng)絡(luò)的優(yōu)化，如確定如何從出發(fā)地運送到中轉(zhuǎn)站再轉(zhuǎn)運到客戶的配送方案。運輸問題、指派問題、轉(zhuǎn)運問題、最大流問題、最短路徑問題，都是特殊情況下的最小費用流問題。例如，最短路徑問題是流量 v=1 的最小費用流問題，最大流問題是最大流量下的最小費用流問題。只要選定合適的權(quán)重、容量、流量，解決最小費用流的方法就能用來解決上述問題。
3.2 NetworkX 求解最小費用流問題Network 工具包提供了多個求解最小費用流問題的函數(shù)，所用的基本算法都是網(wǎng)絡(luò)單純性算法。
3.3 min_cost_flow() 函數(shù)說明min_cost_flow()、min_cost_flow_cost() 是求解費用最小流問題的函數(shù)，通過調(diào)用網(wǎng)絡(luò)單純性算法函數(shù) network_simplex() 求解。
min_cost_flow(G, demand=‘demand’, capacity=‘capacity’, weight=‘weight’)
min_cost_flow_cost(G, demand=‘demand’, capacity=‘capacity’, weight=‘weight’)
主要參數(shù)：
G(NetworkX graph)：有向圖，邊必須帶有容量屬性 capacity、單位成本屬性 ‘weight’ 。demand (string)：頂點的需求量屬性 demand，表示節(jié)點的凈流量：負數(shù)表示供應(yīng)點的凈流出量，正數(shù)表示需求點的凈流入量，0 表示中轉(zhuǎn)節(jié)點。缺省值為 0。capacity (string)：邊的容量，缺省視為無限容量。weight (string)：邊的單位流量的費用，缺省值為 0。返回值：
flowDict (dict)：字典類型，最小費用流的流經(jīng)路徑及各路徑的分配流量flowCost(integer, float)：滿足需求的最小費用流的總費用NetworkXUnfeasible：輸入的凈流量(demand)不平衡，或沒有滿足需求流量的可行流時，拋出異常信息。注意：費用最小流函數(shù) min_cost_flow() 中并沒有設(shè)定供應(yīng)點、需求點，而是通過設(shè)置頂點屬性 ‘demand’ 確定供應(yīng)點、需求點及各頂點的凈流量，因而允許網(wǎng)絡(luò)中存在多個供應(yīng)點、需求點。
3.4 案例：運輸費用問題描述：
從 s 將貨物運送到 t。已知與 s、t 相連各道路的最大運輸能力、單位運量的費用如圖所示（參見 3.6 程序運行結(jié)果圖），圖中邊上的參數(shù) (9,4) 表示道路的容量為 9，單位流量的費用為 4。求流量 v 的最小費用流。
問題分析：
這是一個最小費用流問題。用 NetworkX 的 nx.min_cost_flow() 函數(shù)或 nx.network_simplex() 函數(shù)即可求出從供應(yīng)點到需求點的給定流量 v 的最小費用流。
程序說明：
圖的輸入。本例為稀疏的有向圖，使用 nx.DiGraph() 定義一個有向圖，用G.add_weighted_edges_from() 函數(shù)以列表向圖中添加多條賦權(quán)邊，每個賦權(quán)邊以元組 (node1,node2,{‘capacity’:c1, ‘weight’:w1}) 定義屬性 ‘capacity’ 和 ‘weight’。注意必須以關(guān)鍵字 ‘capacity’ 表示容量，以 ‘weight’ 表示單位流量的費用。nx.shortest_path() 用于計算最短路徑，該段不是必須的。將最短路徑的計算結(jié)果與最小費用流的結(jié)果進行比較，可以看到流量 v=1 時最小費用流的結(jié)果與最短路徑結(jié)果是相同的。nx.cost_of_flow() 用于計算最小費用最大流，該段不是必須的。將最小費用最大流的計算結(jié)果與最小費用流的結(jié)果進行比較，可以看到在最大流量 v=14 時最小費用流的結(jié)果與最小費用最大流結(jié)果是相同的。最小費用流是基于確定的流量 v 而言的。流量 v 可以在程序中賦值；例程中 v 從 1 逐漸遞增，計算所有流量下的最小費用流，直到達到網(wǎng)絡(luò)容量的極限（如果再增大流量將會超出網(wǎng)絡(luò)最大容量，沒有可行流，計算最小費用流失?。etworkX 計算最小費用流時不是在函數(shù)中指定源點、匯點和流量，而是通過向源點、匯點添加屬性 demand 實現(xiàn)的。demand 為正值時表示凈輸入流量，demand 為負值時表示凈輸出流量，這使我們可以指定多源多匯。nx.min_cost_flow() 返回最小費用流的路徑和流量分配，字典格式；nx.min_cost_flow_cost() 返回最小費用流的費用值。nx.network_simplex() 也可以求最小費用流，返回最小費用流的費用值，路徑和流量分配。在最小費用流圖中（最大流量 v=14），以邊的標簽顯示了邊的容量 c、單位流量的費用 w 和流量 f，如 (8,4),f=7 表示邊的容量為 8，單位流量的費用為 4，分配流量為 7。在最小費用流圖中（最大流量 v=14），以不同顏色（edge_color=‘m’）和寬度（width="360px",height="auto" />3.5 Python 例程：# mathmodel19_v1.py# Demo19 of mathematical modeling algorithm# Demo of network flow problem optimization with NetworkX# Copyright 2021 YouCans, XUPT# Crated：2021-07-15import numpy as npimport matplotlib.pyplot as plt # 導(dǎo)入 Matplotlib 工具包import networkx as nx # 導(dǎo)入 NetworkX 工具包# 2. 最小費用流問題（Minimum Cost Flow，MCF）# 創(chuàng)建有向圖G2 = nx.DiGraph() # 創(chuàng)建一個有向圖 DiGraphG2.add_edges_from([('s','v1',{'capacity': 7, 'weight': 4}), ('s','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','t',{'capacity': 10, 'weight': 6}), ('v4','v1',{'capacity': 2, 'weight': 1}), ('v4','t',{'capacity': 5, 'weight': 2})]) # 添加邊的屬性 'capacity', 'weight'# 整理邊的標簽，用于繪圖顯示edgeLabel1 = nx.get_edge_attributes(G2, 'capacity')edgeLabel2 = nx.get_edge_attributes(G2, 'weight')edgeLabel = {}for i in edgeLabel1.keys(): edgeLabel[i] = f'({edgeLabel1[i]:},{edgeLabel2[i]:})' # 邊的(容量，成本)# 計算最短路徑---非必要，用于與最小費用流的結(jié)果進行比較lenShortestPath = nx.shortest_path_length(G2, 's', 't', weight="weight")shortestPath = nx.shortest_path(G2, 's', 't', weight="weight")print("\最短路徑: ", shortestPath) # 輸出最短路徑print("最短路徑長度: ", lenShortestPath) # 輸出最短路徑長度# 計算最小費用最大流---非必要，用于與最小費用流的結(jié)果進行比較minCostFlow = nx.max_flow_min_cost(G2, 's', 't') # 求最小費用最大流minCost = nx.cost_of_flow(G2, minCostFlow) # 求最小費用的值maxFlow = sum(minCostFlow['s'][j] for j in minCostFlow['s'].keys()) # 求最大流量的值print("\最大流量: {}".format(maxFlow)) # 輸出最小費用的值print("最大流量的最小費用: {}\".format(minCost)) # 輸出最小費用的值# v = input("Input flow (v>=0):")v = 0while True: v += 1 # 最小費用流的流量 G2.add_node("s", demand=-v) # nx.min_cost_flow() 的設(shè)置要求 G2.add_node("t", demand=v) # 設(shè)置源點/匯點的流量 try: # Youcans@XUPT # 求最小費用流(demand=v) minFlowCost = nx.min_cost_flow_cost(G2) # 求最小費用流的費用 minFlowDict = nx.min_cost_flow(G2) # 求最小費用流 # minFlowCost, minFlowDict = nx.network_simplex(G2) # 求最小費用流--與上行等效 print("流量: {:2d}\最小費用:{}".format(v, minFlowCost)) # 輸出最小費用的值(demand=v) # print("最小費用流的路徑及流量: ", minFlowDict) # 輸出最大流的途徑和各路徑上的流量 except Exception as e: print("流量: {:2d}\超出網(wǎng)絡(luò)最大容量，沒有可行流。".format(v)) print("\流量 v={:2d}：計算最小費用流失敗({})。".format(v, str(e))) break # 結(jié)束 while True 循環(huán)edgeLists = []for i in minFlowDict.keys(): for j in minFlowDict[i].keys(): edgeLabel[(i, j)] += ',f=' + str(minFlowDict[i][j]) # 取出每條邊流量信息存入邊顯示值 if minFlowDict[i][j] > 0: edgeLists.append((i, j))maxFlow = sum(minFlowDict['s'][j] for j in minFlowDict['s'].keys()) # 求最大流量的值print("\最大流量: {:2d},\最小費用:{}".format(maxFlow, minFlowCost)) # 輸出最小費用的值print("最小費用流的路徑及流量: ", minFlowDict) # 輸出最小費用流的途徑和各路徑上的流量print("最小費用流的路徑：", edgeLists) # 輸出最小費用流的途徑# 繪制有向網(wǎng)絡(luò)圖pos={'s':(0,5),'v1':(4,2),'v2':(4,8),'v3':(10,2),'v4':(10,8),'t':(14,5)} # 指定頂點繪圖位置fig, ax = plt.subplots(figsize=(8,6))ax.text(6,2.5,"youcans-xupt",color='gainsboro')ax.set_title("Minimum Cost Maximum Flow with NetworkX")nx.draw(G2,pos,with_labels=True,node_color='c',node_size=300,font_size=10) # 繪制有向圖，顯示頂點標簽nx.draw_networkx_edge_labels(G2,pos,edgeLabel,font_size=10) # 顯示邊的標簽：'capacity','weight' + minCostFlownx.draw_networkx_edges(G2,pos,edgelist=edgeLists,edge_color='m',width="360px",height="auto" />
3.6 程序運行結(jié)果：最短路徑: ['s', 'v1', 'v3', 'v4', 't']最短路徑長度: 9最大流量: 14最大流量的最小費用: 159流量: 1最小費用:9流量: 2最小費用:18流量: 3最小費用:27流量: 4最小費用:36流量: 5最小費用:45流量: 6最小費用:56流量: 7最小費用:67流量: 8最小費用:79流量: 9最小費用:91流量: 10最小費用:103流量: 11最小費用:115流量: 12最小費用:127流量: 13最小費用:143流量: 14最小費用:159流量: 15超出網(wǎng)絡(luò)最大容量，沒有可行流。流量 v=15：計算最小費用流失敗(no flow satisfies all node demands)。最大流量: 14,最小費用:159最小費用流的路徑及流量: {'s': {'v1': 7, 'v2': 7}, 'v1': {'v3': 9}, 'v2': {'v1': 2, 'v4': 5}, 'v3': {'v4': 0, 't': 9}, 'v4': {'v1': 0, 't': 5}, 't': {}}最小費用流的路徑： [('s', 'v1'), ('s', 'v2'), ('v1', 'v3'), ('v2', 'v1'), ('v2', 'v4'), ('v3', 't'), ('v4', 't')]4. 最小費用最大流問題（MCMF）4.1 最小費用最大流問題的算法
最小成本最大流問題可以看做是最短路徑問題和最大流問題的結(jié)合，既要像最短路徑問題那樣考慮成本最小，又要考慮到每條邊上的流量限制。最短路徑問題和最大流問題在本質(zhì)上也是特殊的最小成本最大流問題，是網(wǎng)絡(luò)優(yōu)化中的基本問題。
求解最小費用最大流問題的常用方法有 Bellman-Ford算法、SPFA算法、Dijkstra 改進算法。
在 NetworkX 工具包中，求解最小費用最大流問題的方法與眾不同：先調(diào)用 nx.maximum_flow_value() 函數(shù)求網(wǎng)絡(luò)最大流，再以最大流調(diào)用 min_cost_flow() 函數(shù)求網(wǎng)絡(luò)最大流時的最小費用流。哈哈，這樣的處理方式，與本系列博文的思想十分吻合：容易理解，容易實現(xiàn)，容易掌握。
4.2 max_flow_min_cost() 函數(shù)說明max_flow_min_cost()是求解最小費用最大流問題的函數(shù)。
max_flow_min_cost(G, s, t, capacity=‘capacity’, weight=‘weight’)
cost_of_flow(G, flowDict, weight=‘weight’)
主要參數(shù)：
G(NetworkX graph)：有向圖，邊必須帶有容量屬性 capacity、單位成本屬性 ‘weight’ 。s (node)：流的源點。t (node)：流的匯點。capacity (string)：邊的容量，缺省視為無限容量。weight (string)：邊的單位流量的費用，缺省值為 0。返回值：flowDict (dict)：字典類型，最小費用最大流的流經(jīng)路徑及各路徑的分配流量。使用 cost_of_flow() 函數(shù)，可以由流經(jīng)路徑及各路徑的分配流量 flowDict 計算可行流的成本。
4.3 案例：輸油管網(wǎng)的最大流量和最小費用問題描述：
某輸油網(wǎng)絡(luò) G 中的每段管路允許的容量和單位流量的運輸費用如圖所示（參見4.5 程序運行結(jié)果圖），圖中邊上的參數(shù) (9,5) 表示邊的容量為 9，單位流量的費用為 5。求從網(wǎng)絡(luò)源點 s 到匯點 t 的最大流量，及輸送最大流量的最小費用。
問題分析：
這是一個的最小費用最大流問題。用 NetworkX 的 nx.max_flow_min_cost() 函數(shù)可以求出從網(wǎng)絡(luò)源點到匯點的最小費用最大流。
程序說明：
圖的輸入。用 nx.DiGraph() 定義一個有向圖。用 G.add_weighted_edges_from() 函數(shù)以列表向圖中添加多條賦權(quán)邊，每個賦權(quán)邊以元組 (node1,node2,{‘capacity’:c1, ‘weight’:w1}) 定義屬性 ‘capacity’ 和 ‘weight’。注意必須以關(guān)鍵字 ‘capacity’ 表示容量，以 ‘weight’ 表示單位流量的費用。nx.max_flow_min_cost(G3, ‘s’, ‘t’) 用來計算從源點 ‘s’ 到匯點 ‘t’ 的最小費用最大流，返回最大流的途徑和各路徑上的流量分配，字典格式。nx.cost_of_flow() 計算一個可行流的費用，例程中用來計算最小費用最大流的費用。maxFlow 計算從源點 ‘s’ 發(fā)出的所有路徑上的流量總和，得到最大流量的值。在最小費用最大流圖中，以邊的標簽顯示了邊的容量 c、單位流量的費用 w 和流量 f，如 (13,7),f=11表示邊的容量為 13，單位流量的費用為 7，分配流量為 11。在最小費用最大流圖中，以不同顏色（edge_color=‘m’）和寬度（width="360px",height="auto" />4.4 Python 例程# mathmodel19_v1.py# Demo19 of mathematical modeling algorithm# Demo of network flow problem optimization with NetworkX# Copyright 2021 YouCans, XUPT# Crated：2021-07-15import numpy as npimport matplotlib.pyplot as plt # 導(dǎo)入 Matplotlib 工具包import networkx as nx # 導(dǎo)入 NetworkX 工具包# 3. 最小費用最大流問題（Minimum Cost Maximum Flow，MCMF）# 創(chuàng)建有向圖G3 = nx.DiGraph() # 創(chuàng)建一個有向圖 DiGraphG3.add_edges_from([('s','v1',{'capacity': 13, 'weight': 7}), ('s','v2',{'capacity': 9, 'weight': 9}), ('v1','v3',{'capacity': 6, 'weight': 6}), ('v1','v4',{'capacity': 5, 'weight': 5}), ('v2','v1',{'capacity': 4, 'weight': 4}), ('v2','v3',{'capacity': 5, 'weight': 2}), ('v2','v5',{'capacity': 5, 'weight': 5}), ('v3','v4',{'capacity': 5, 'weight': 2}), ('v3','v5',{'capacity': 4, 'weight': 1}), ('v3','t',{'capacity': 4, 'weight': 4}), ('v4','t', {'capacity': 9, 'weight': 7}), ('v5','t',{'capacity': 9, 'weight': 5})]) # 添加邊的屬性 'capacity', 'weight'# 求最小費用最大流minCostFlow = nx.max_flow_min_cost(G3, 's', 't') # 求最小費用最大流minCost = nx.cost_of_flow(G3, minCostFlow) # 求最小費用的值maxFlow = sum(minCostFlow['s'][j] for j in minCostFlow['s'].keys()) # 求最大流量的值# # 數(shù)據(jù)格式轉(zhuǎn)換edgeLabel1 = nx.get_edge_attributes(G3,'capacity') # 整理邊的標簽，用于繪圖顯示edgeLabel2 = nx.get_edge_attributes(G3,'weight')edgeLabel={}for i in edgeLabel1.keys(): edgeLabel[i]=f'({edgeLabel1[i]:},{edgeLabel2[i]:})' # 邊的(容量，成本)edgeLists = []for i in minCostFlow.keys(): for j in minCostFlow[i].keys(): edgeLabel[(i, j)] += ',f=' + str(minCostFlow[i][j]) # 將邊的實際流量添加到 邊的標簽 if minCostFlow[i][j]>0: edgeLists.append((i,j))print("最小費用最大流的路徑及流量: ", minCostFlow) # 輸出最大流的途徑和各路徑上的流量print("最小費用最大流的路徑：", edgeLists) # 輸出最小費用最大流的途徑print("最大流量: ", maxFlow) # 輸出最大流量的值print("最小費用: ", minCost) # 輸出最小費用的值# 繪制有向網(wǎng)絡(luò)圖pos={'s':(0,5), 'v1':(3,9), 'v2':(3,1), 'v3':(6,5), 'v4':(9,9),'v5':(9,1), 't':(12,5)} # 指定頂點繪圖位置fig, ax = plt.subplots(figsize=(8,6))ax.text(5,1.5,"youcans-xupt",color='gainsboro')ax.set_title("Minimum Cost Maximum Flow with NetworkX")nx.draw(G3,pos,with_labels=True,node_color='c',node_size=300,font_size=10) # 繪制有向圖，顯示頂點標簽nx.draw_networkx_edge_labels(G3,pos,edgeLabel,font_size=10) # 顯示邊的標簽：'capacity','weight' + minCostFlownx.draw_networkx_edges(G3,pos,edgelist=edgeLists,edge_color='m',width="360px",height="auto" />
4.5 運行結(jié)果最小費用最大流的路徑及流量: {'s': {'v1': 11, 'v2': 9}, 'v1': {'v3': 6, 'v4': 5}, 'v2': {'v1': 0, 'v3': 4, 'v5': 5}, 'v3': {'v4': 2, 'v5': 4, 't': 4}, 'v4': {'t': 7}, 'v5': {'t': 9}, 't': {}}最小費用最大流的路徑： [('s', 'v1'), ('s', 'v2'), ('v1', 'v3'), ('v1', 'v4'), ('v2', 'v3'), ('v2', 'v5'), ('v3', 'v4'), ('v3', 'v5'), ('v3', 't'), ('v4', 't'), ('v5', 't')]最大流量: 20最小費用: 3705. 總結(jié)本文基于 NetworkX 工具包，通過例程詳細介紹了網(wǎng)絡(luò)最大流問題、最小費用流問題、最小費用最大流問題的建模和編程。運輸問題、指派問題、轉(zhuǎn)運問題、最大流問題、最短路徑問題，都是特殊情況下的最小費用流問題。通過 3.6 中最短路徑、最小費用最大流的結(jié)果與 v=1、v=14 的最小費用流結(jié)果的比較，可以理解這種關(guān)系。例程給出了對部分指定的邊設(shè)置顏色，為邊設(shè)置指定格式的顯示內(nèi)容，NetworkX 函數(shù)輸出值的數(shù)據(jù)格式轉(zhuǎn)換的編程方法，建議讀者多加留意。網(wǎng)絡(luò)流優(yōu)化問題還有很多變形和衍生問題，將在今后的文中進行介紹。
【本節(jié)完】
————————————————
版權(quán)聲明：本文為CSDN博主「youcans」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/youcans/article/details/118726642
以上就是關(guān)于pos機網(wǎng)絡(luò)顯示c,Python小白的數(shù)學(xué)建模課的知識，后面我們會繼續(xù)為大家整理關(guān)于pos機網(wǎng)絡(luò)顯示c的知識，希望能夠幫助到大家！
