本節接續流筆記。供需已指定流量平衡,現在要最小化輸送費用;內容涵蓋消負環、運輸交換及原始—對偶指派法。
動機
兩個流可送達相同數量,卻使用不同資源。排程器在處理器網絡分配工作時,傳送成本可以不同。每個頂點供出或收取的量已固定,因此不再追求更多源流值,而是重新安排現有可行流,直到沒有更便宜方案。
固定供需下,兩個可行流之差在每點淨平衡為零,所以改善對象是環,不是額外源匯路。反向殘量弧仍表示取消舊決策,其費用必須是原費用的負數。若漏掉此負號,便不能把環解釋成真正的成本交換。
頂點勢能把全局負環問題轉成局部不等式。弧成本加上頂點價格差,沿環會抵消,因此環成本不變。非負約化成本遂證明沒有改善循環。指派問題把這想法化成行列標籤,零約化成本邊構成尋找最佳配對的圖。
定義
定義 6.1.1
(固定平衡的最小費用流)
有限有向網絡有有限容量 ,頂點 的淨流出指定為 ,且 。最小化 ;除非明確檢查不可行,先假設有可行流。
原弧 的正向殘量容量為 、成本為 ;反向殘量容量為 、成本為 。勢能 定義剩餘約化成本
平行及反向原弧保留各自標籤。殘量有向環可含反向弧,瓶頸是沿環最小殘量容量。按瓶頸增廣保持各頂點指定平衡;若環成本負,總目標便嚴格下降。
運輸模型有非負供給 、需求 ,總量相等; 的行和為供給、列和為需求,目標 。指派是行列數相同且各總量為一的特例。完美匹配在每行每列各選一邊;完整指派模型假設每個配對都有有限成本。
定理/命題
定理 6.1.2
(負環及勢能刻畫最優性)
固定平衡的可行容量流為最小費用,當且僅當其殘量網絡沒有負成本有向環。這又等價於存在勢能,使每條正殘量容量弧的約化成本非負。
定理 6.1.3
(緊邊匹配證明指派最優)
若行標籤 、列標籤 滿足 ,每個可行指派成本至少為 。全由緊邊構成的完美匹配取得此界,故最優。下述交替樹標籤更新法對有限完整成本矩陣有限步找到它。
證書不要求成本整數。整數供需及容量則支持整數流;成本也整數時,更可用每次至少下降一來估計步數。首先仍須取得可行流,例如另作容量可行性計算;沒有實際可行決策,單有勢能不算最優證書。
證明思路
負殘量環容許正瓶頸增廣,平衡不變,費用改變是瓶頸乘環成本,故最優流不能有負環。
反過來,比較現流與任一競爭流。某原弧增加的差額放在正向殘量弧,減少的差額放在反向弧,均以非負量表示;容量界保證改動合法。由於兩流供需相同,這些差額形成非負殘量循環流。
任何有限非負循環流都可分解成非負倍數的有向環。由一條正流弧出發,守恆容許沿正弧繼續,直到頂點重複;抽出環,減去其最小弧量,至少一條正弧消失。反覆有限次便完成。成本差等於各環成本乘其非負權重;無負環便無更便宜競爭者。
勢能差沿環抵消,所以全弧非負約化成本排除負環。反向存在性則加臨時頂點,以零成本弧通往所有原頂點。沒有負環時,每個遊走可刪環而不增長度,最短距離可從有限個簡單路徑取得且有限。其標籤滿足 ,恰是所需約化不等式。臨時源避免漏掉與某個原源不連通的分量。
證明透視
全局比較如何化為環的總和
反方向的證明從不逐一檢查競爭流,而是改寫它與現流的差。容量界使這個差成為殘量弧上的非負分配;反向弧在此不可缺少:某弧上的減少以成本 記錄。供需相同使這個差在每個頂點守恆,分解中的遊走因此總能繼續。有限性令分解終止,因為每次抽出環都刪去一條弧。收尾一步是線性:成本差是各環成本的非負組合。勢能只在其後出場,作為「沒有負環」的最短路徑證書。
指派下界把每個標籤不等式乘以非負指派量後相加。行列和都一,便留下標籤總和;緊完美匹配取等號。只有緊邊但未能完美匹配仍不足夠,因多行可能爭用同一列。
有限原始—對偶指派法
初設 、。也可把每列剩餘約化成本的最小值加到該列標籤,這保持全部對偶不等式,就是下例額外的列縮減。再在緊邊圖找匹配。從未匹配行開始交替搜尋:行沿緊邊到列,已匹配列沿匹配邊回其行。到未匹配列便得到增廣路,翻轉邊的匹配狀態使匹配數加一。
若尚無增廣路,令到達行集為 、列集為 。每個到達列都配到到達行,加上未匹配根,故 。匹配未完整,所以至少一列不在 。取
內行標籤加 , 內列標籤減 。由 到外列的餘量減少但不負;外行到 的餘量增加;其餘不變。匹配邊及現有交替樹仍緊,至少一條新緊邊離開 。
繼續搜尋,新邊不是到自由列而增廣,就是到已配列並帶來新行,令樹增大。同次增廣之前到達集只增不減,所以更新有限次;增廣最多等於行數,故算法有限且以緊匹配證最優。若有禁止配對,必須另行處理不可行性,不可任意塞入一個未證足夠大的成本。
運輸消環算法
完整平衡運輸可先逐行逐列盡量分配,每步耗盡一個尚餘供給或需求,然後移往下一行或列;零供需跳過,有限步得到可行起點。每個矩形交換是增加與減少單元交替的殘量環。
找到負環就增廣至瓶頸再重複。整數供需配整數起點時,每次保持整數。每項運量都受總運量限制,故整數可行表只有有限個;嚴格成本下降不會重訪,因此即使成本為實數也有限終止。成本若也整數,每次至少降一,再有目標範圍步數界。但這些推理尚未證明多項式時間。
例題詳解
例題 6.1.4
(一次運輸交換降低五)
供給 、需求 ,成本
起始 成本十一。增加 ,減少 ;環成本 ,瓶頸一。新表 成本六。
取行標籤 、列標籤 ,逐項和不超成本,全部正運量單元都緊。下界 ,因此已最優,而不只是有所改善。
例題 6.1.5
(Hungarian 更新補出匹配邊)
取
行最小值給 ,再扣列最小值給 ,約化矩陣
先配第一行至第二列、第三行至第一列。未配第二行的搜尋到 ,跨界餘量為 ,故 。更新成 ,下界五。新緊邊由第二行到第一列,再沿原匹配到第三行,最後到未匹配第三列;沿這條增廣路翻轉邊,得到緊匹配 ,其成本 ,證明最優。負列標籤合法,無須額外非負限制。
例題 6.1.6
(負原成本仍可有非負約化成本)
兩點 各平衡零,雙向容量一,成本 。零流的唯一兩弧環成本一,無法改善。取 , 的約化成本為 , 的為 ,故零流最優。
若逆向成本改為一,環成本負一,兩弧各送一便得總成本負一。此時兩個剩餘方向都反轉,環成本正一,證明新最小值。阻礙最優的是負環,不是某條負原弧。
概念視角組合
價格更新修補匹配障礙
更新前,到達行沿緊邊只能到達已到達列,而且行多一個。零成本圖缺少足夠選擇;最小跨界餘量正是暴露新選擇所需價格變化,同時保留既有樹邊。數值標籤更新於是對應一個明確組合障礙,而非任意調價。
常見錯誤
固定供需時,任意源匯增廣路會改平衡,不是合法改善;殘量環才保平衡。反向成本永遠取原成本的負數,不能只檢查未使用正向弧。勢能必須涵蓋全部正殘量弧及所有分量。
緊邊存在不等於緊完美匹配存在。行列標籤也不必非負,只有其和受成本上界限制。把多餘符號限制加上去,可破壞正確對偶更新。整數供需給整數決策的存在及算法不變量,不代表任意實數最優表每項都整數。
總結
固定平衡下,所有改善都可分解為殘量環;非負約化成本等價於無負環。運輸以此交換運量,指派把對偶邏輯化為緊邊及有限交替樹更新。整數性、終止性與多項式複雜度仍是分開的結論。
練習
快速檢查
(核驗運輸例四個標籤不等式,找未用單元並解釋為何可不緊。)
解答 · 答案
標籤和為 ,逐項不超 。未用 有正餘量,但乘零運量後仍零,所以不影響原始對偶同值。
快速檢查
(對成本 ,找緊完美匹配及證書標籤。)
解答 · 答案
選 成本三。行標籤 、列標籤 給和 ,不超 ;選邊都緊,總下界三,證最優。
快速檢查
(殘量環成本有 ,負環瓶頸半。費用改變多少?零成本環是否證明不唯一?)
解答 · 答案
費用改變 。正瓶頸零成本環給不同而同值可行流;原流若最優,便證不唯一。若未證原最優,只能得到另一個同樣可能次優的流。
快速檢查
(與主要供給頂點不連通的負殘量環,為何仍影響固定平衡最小費用?)
解答 · 答案
循環流在每點淨平衡零,包括沒有供需的點。任何分量的負環都能降低總成本而不動其他交付。只從一個原源求勢能可能漏掉它,證明中臨時全可達源正是為避免此問題。