Cấu trúc dữ liệu và Giải thuật Bài 141: Luồng chi phí cực tiểu có ràng buộc dung lượng dưới (Min-Cost Flow / Circulation with Lower Bounds) - Khử chu trình âm và tối ưu hóa chi phí.

Ở Bài 139 và Bài 140, chúng ta đã làm chủ kỹ thuật khử cận dưới để tìm Luồng khả thi (Feasible Circulation), Luồng cực đại (Max-Flow), và Luồng cực tiểu (Min-Flow). Tuy nhiên, trên thực tế, việc luân chuyển lưu lượng qua mỗi cung đường luôn đi kèm một đơn giá (chi phí vận chuyển, độ trễ truyền dẫn, tiêu hao năng lượng). Khi bài toán đòi hỏi đồng thời:

1. Mỗi cạnh $e$ phải thỏa mãn hạn mức cận dưới $l(e) \le f(e) \le c(e)$.

2. Mỗi đỉnh $u$ có thể có nhu cầu tiếp nhận hoặc cung cấp $d(u)$.

3. Tổng chi phí toàn mạng $\sum_{e \in E} f(e) \cdot w(e)$ đạt giá trị nhỏ nhất.

Bài toán trở thành Luồng tuần hoàn chi phí cực tiểu có cận dưới (Min-Cost Circulation with Demands and Lower Bounds). Độ phức tạp tăng lên đáng kể vì việc khử cận dưới hoặc sự xuất hiện tự nhiên của các cung có chi phí âm $w(e) < 0$ có thể tạo ra các chu trình chi phí âm (Negative Cost Cycles) trên đồ thị thặng dư, phá hủy tính đúng đắn của các thuật toán đường đi ngắn nhất thông thường như Dijkstra.

1. Mô hình Toán học tổng quát

Cho mạng có hướng $G = (V, E)$. Với mỗi cạnh $e = (u, v) \in E$:

• Cận dưới: $l(e) \ge 0$.

• Cận trên (Dung lượng): $c(e) \ge l(e)$.

• Đơn giá chi phí: $w(e) \in \mathbb{R}$ (chi phí phải trả cho mỗi đơn vị luồng chảy qua $e$).

Mỗi đỉnh $u \in V$ có nhu cầu $d(u)$ thỏa mãn điều kiện bảo toàn tổng thể $\sum_{u \in V} d(u) = 0$.

Mục tiêu là tìm hàm luồng $f: E \to \mathbb{R}^+$ cực tiểu hóa hàm mục tiêu:

$$\min \text{Cost}(f) = \sum_{e \in E} f(e) \cdot w(e)$$

thỏa mãn hai hệ ràng buộc:

$$\forall e \in E: \quad l(e) \le f(e) \le c(e)$$

$$\forall u \in V: \quad \sum_{e \in \text{in}(u)} f(e) - \sum_{e \in \text{out}(u)} f(e) = d(u)$$

2. Thách thức Chu trình âm và Phương pháp Bão hòa trước (Pre-saturation)

Khi giải bài toán Min-Cost Flow tiêu chuẩn (không có cận dưới và không có chu trình âm), thuật toán đường tăng luồng ngắn nhất tuần tự (Successive Shortest Path - SSP) dùng SPFA hoặc Dijkstra kết hợp thế năng Johnson (Bài 118) hoạt động hiệu quả.

Tuy nhiên, trong bài toán có cận dưới và chi phí tùy ý:

• Sau khi khử cận dưới, chi phí của các cạnh giữ nguyên $w(e)$.

• Nếu ban đầu tồn tại các cạnh có chi phí âm $w(e) < 0$, đồ thị thặng dư ban đầu có thể chứa ngay các chu trình âm có dung lượng dương. Nếu chạy SPFA tìm đường đi ngắn nhất, thuật toán sẽ rơi vào vòng lặp vô tận.

Giải pháp 1: Khử chu trình âm (Cycle Canceling Algorithm - Klein 1967)

Bắt đầu từ một luồng khả thi bất kỳ, liên tục tìm chu trình âm trên đồ thị thặng dư (bằng Bellman-Ford/SPFA) và đẩy luồng bão hòa quanh chu trình đó cho đến khi không còn chu trình âm nào. Phương pháp này đúng nhưng độ phức tạp không ổn định vì số lượng chu trình âm có thể rất lớn.

Giải pháp 2: Kỹ thuật Bão hòa trước cạnh âm (Pre-saturating Negative Cost Edges)

Đây là kỹ thuật đại số tối ưu và thanh lịch nhất để quy bài toán về mạng hoàn toàn không có cạnh chi phí âm:

1. Với mọi cạnh $e = (u, v)$ có chi phí âm $w(e) < 0$:

   • Ta giả định bão hòa toàn bộ dung lượng của cạnh này ngay từ đầu: ép $f(e) = c(e)$.

   • Lập tức ghi nhận khoản chi phí cơ sở: $\text{BaseCost} \gets \text{BaseCost} + c(e) \cdot w(e)$.

   • Cạnh $e$ lúc này chỉ còn khả năng "hủy luồng" (giảm luồng từ $c(e)$ xuống $l(e)$). Điều này tương đương với việc tạo một cạnh ngược $(v \to u)$ có dung lượng thặng dư $c(e) - l(e)$ với chi phí đảo dấu:

     $$w_{\text{rev}} = -w(e) > 0$$

   • Vì $-w(e) > 0$, cạnh mới này mang chi phí dương hoàn toàn!

   • Cập nhật lượng luồng đã ép chảy $c(e)$ vào độ mất cân bằng $\Delta(u)$ và $\Delta(v)$.

2. Với mọi cạnh $e = (u, v)$ có chi phí không âm $w(e) \ge 0$:

   • Chỉ ép luồng cơ sở bằng đúng cận dưới: $f(e) = l(e)$.

   • Chi phí cơ sở: $\text{BaseCost} \gets \text{BaseCost} + l(e) \cdot w(e)$.

   • Cạnh xuôi $(u \to v)$ có dung lượng còn lại $c(e) - l(e)$ với chi phí $w(e) \ge 0$.

   • Cập nhật $l(e)$ vào $\Delta(u)$ và $\Delta(v)$.

Nhờ phép chuyển đổi này, mọi cung trên mạng thặng dư phụ trợ đều có chi phí $\ge 0$, loại bỏ hoàn toàn nguy cơ xuất hiện chu trình âm ban đầu.

3. Quy trình Thuật toán Toàn diện qua Siêu nguồn và Siêu đích

           Mạng ban đầu (Cận dưới l(e), cận trên c(e), chi phí w(e))
                                       ||
        [Phân loại w(e) >= 0 (ép l(e)) và w(e) < 0 (ép c(e))]
                                       ||
                                       v
           Mạng phụ trợ G' (Mọi cạnh đều có dung lượng >= 0 và chi phí >= 0)
                 Nối [S* -> u] nếu Δ(u) < 0 (Dung lượng -Δ(u), chi phí 0)
                 Nối [u -> T*] nếu Δ(u) > 0 (Dung lượng  Δ(u), chi phí 0)
                                       ||
                                       v
           Chạy Min-Cost Max-Flow (MCMF) từ S* đến T* trên mạng G'

Bước 1: Tính toán Độ lệch $\Delta(u)$ cho mỗi đỉnh

Khởi tạo $\Delta(u) = d(u)$ với mọi $u \in V$.

Duyệt qua từng cạnh $e = (u, v)$ ban đầu:

• Nếu $w(e) \ge 0$:

  • $\text{BaseCost} \gets \text{BaseCost} + l(e) \cdot w(e)$

  • $\Delta(u) \gets \Delta(u) + l(e)$ (luồng ra khỏi $u$)

  • $\Delta(v) \gets \Delta(v) - l(e)$ (luồng vào $v$)

  • Thêm cạnh $(u \to v)$ vào mạng phụ trợ: $\text{cap} = c(e) - l(e)$, $\text{cost} = w(e)$.

• Nếu $w(e) < 0$:

  • $\text{BaseCost} \gets \text{BaseCost} + c(e) \cdot w(e)$

  • $\Delta(u) \gets \Delta(u) + c(e)$ (ép luồng tối đa ra khỏi $u$)

  • $\Delta(v) \gets \Delta(v) - c(e)$ (ép luồng tối đa vào $v$)

  • Thêm cạnh ngược $(v \to u)$ vào mạng phụ trợ: $\text{cap} = c(e) - l(e)$, $\text{cost} = -w(e) > 0$.

Bước 2: Thiết lập Siêu nguồn $S^*$ và Siêu đích $T^*$

Tạo hai đỉnh mới $S^* = \vert{}V\vert{}$ và $T^* = \vert{}V\vert{} + 1$:

• Với mỗi đỉnh $u \in V$:

  • Nếu $\Delta(u) < 0$: Thêm cạnh $(S^* \to u)$ với dung lượng $-\Delta(u)$ và chi phí $0$.

  • Nếu $\Delta(u) > 0$: Thêm cạnh $(u \to T^*)$ với dung lượng $\Delta(u)$ và chi phí $0$.

Bước 3: Thực thi Min-Cost Max-Flow

Chạy thuật toán Min-Cost Max-Flow (MCMF) từ $S^*$ đến $T^*$ trên mạng phụ trợ:

• Nếu $\text{MaxFlow} < \sum_{\Delta(u) > 0} \Delta(u)$: Không tồn tại luồng khả thi (Hệ thống vô nghiệm).

• Nếu bão hòa hoàn toàn:

  $$\text{MinCost}_{\text{optimal}} = \text{BaseCost} + \text{MCMF\_Cost}$$

4. Hiện thực hóa Thuật toán bằng Golang

Chương trình Golang dưới đây cài đặt hoàn chỉnh:

1. Bộ giải Min-Cost Max-Flow (MCMF) sử dụng thuật toán SPFA tìm đường tăng luồng có chi phí nhỏ nhất (Successive Shortest Path).

2. Module MinCostCirculationSolver thực hiện kỹ thuật bão hòa cạnh âm, khử cận dưới, cân bằng $\Delta(u)$, và khôi phục luồng thực tế.

Go

package main

import (
	"fmt"
	"math"
)

const INF = math.MaxInt64 / 4

type MCMFEdge struct {
	to   int
	rev  int
	cap  int64
	flow int64
	cost int64
}

type MCMF struct {
	n     int
	adj   [][]MCMFEdge
	dist  []int64
	prevV []int
	prevE []int
	inQ   []bool
}

func NewMCMF(n int) *MCMF {
	return &MCMF{
		n:     n,
		adj:   make([][]MCMFEdge, n),
		dist:  make([]int64, n),
		prevV: make([]int, n),
		prevE: make([]int, n),
		inQ:   make([]bool, n),
	}
}

func (m *MCMF) AddEdge(from, to int, cap, cost int64) int {
	fwd := MCMFEdge{to: to, rev: len(m.adj[to]), cap: cap, flow: 0, cost: cost}
	bwd := MCMFEdge{to: from, rev: len(m.adj[from]), cap: 0, flow: 0, cost: -cost}
	m.adj[from] = append(m.adj[from], fwd)
	m.adj[to] = append(m.adj[to], bwd)
	return len(m.adj[from]) - 1
}

// SPFA tìm đường tăng luồng có chi phí nhỏ nhất
func (m *MCMF) spfa(s, t int) bool {
	for i := 0; i < m.n; i++ {
		m.dist[i] = INF
		m.prevV[i] = -1
		m.prevE[i] = -1
		m.inQ[i] = false
	}

	queue := []int{s}
	m.dist[s] = 0
	m.inQ[s] = true

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		m.inQ[u] = false

		for i, e := range m.adj[u] {
			if e.cap-e.flow > 0 && m.dist[u]+e.cost < m.dist[e.to] {
				m.dist[e.to] = m.dist[u] + e.cost
				m.prevV[e.to] = u
				m.prevE[e.to] = i
				if !m.inQ[e.to] {
					queue = append(queue, e.to)
					m.inQ[e.to] = true
				}
			}
		}
	}

	return m.dist[t] < INF
}

func (m *MCMF) Solve(s, t int) (int64, int64) {
	var totalFlow int64 = 0
	var totalCost int64 = 0

	for m.spfa(s, t) {
		var push int64 = INF
		for curr := t; curr != s; curr = m.prevV[curr] {
			p := m.prevV[curr]
			edgeIdx := m.prevE[curr]
			e := m.adj[p][edgeIdx]
			if e.cap-e.flow < push {
				push = e.cap - e.flow
			}
		}

		for curr := t; curr != s; curr = m.prevV[curr] {
			p := m.prevV[curr]
			edgeIdx := m.prevE[curr]
			m.adj[p][edgeIdx].flow += push
			rev := m.adj[p][edgeIdx].rev
			m.adj[curr][rev].flow -= push
		}

		totalFlow += push
		totalCost += push * m.dist[t]
	}

	return totalFlow, totalCost
}

type UserEdge struct {
	from, to int
	lower    int64
	upper    int64
	cost     int64
	auxFrom  int
	auxIdx   int
	isNeg    bool
}

type MinCostCirculationSolver struct {
	n        int
	edges    []UserEdge
	demands  []int64
	baseCost int64
}

func NewMinCostCirculationSolver(n int) *MinCostCirculationSolver {
	return &MinCostCirculationSolver{
		n:       n,
		demands: make([]int64, n),
	}
}

func (s *MinCostCirculationSolver) SetDemand(u int, d int64) {
	s.demands[u] = d
}

func (s *MinCostCirculationSolver) AddEdge(from, to int, lower, upper, cost int64) {
	s.edges = append(s.edges, UserEdge{
		from:  from,
		to:    to,
		lower: lower,
		upper: upper,
		cost:  cost,
	})
}

func (s *MinCostCirculationSolver) Solve() (bool, int64, []int64) {
	delta := make([]int64, s.n)
	copy(delta, s.demands)
	s.baseCost = 0

	sStar := s.n
	tStar := s.n + 1
	mcmf := NewMCMF(s.n + 2)

	for i := range s.edges {
		e := &s.edges[i]
		if e.cost >= 0 {
			// Chi phí không âm: Ép luồng cơ sở = lower
			s.baseCost += e.lower * e.cost
			delta[e.from] += e.lower
			delta[e.to] -= e.lower
			e.auxFrom = e.from
			e.auxIdx = mcmf.AddEdge(e.from, e.to, e.upper-e.lower, e.cost)
			e.isNeg = false
		} else {
			// Chi phí âm: Bão hòa trước = upper để loại bỏ chi phí âm
			s.baseCost += e.upper * e.cost
			delta[e.from] += e.upper
			delta[e.to] -= e.upper
			// Tạo cạnh ngược có chi phí dương (-cost) để cho phép hủy luồng
			e.auxFrom = e.to
			e.auxIdx = mcmf.AddEdge(e.to, e.from, e.upper-e.lower, -e.cost)
			e.isNeg = true
		}
	}

	var expectedFlow int64 = 0
	for u := 0; u < s.n; u++ {
		if delta[u] > 0 {
			mcmf.AddEdge(u, tStar, delta[u], 0)
			expectedFlow += delta[u]
		} else if delta[u] < 0 {
			mcmf.AddEdge(sStar, u, -delta[u], 0)
		}
	}

	flow, mcmfCost := mcmf.Solve(sStar, tStar)
	if flow != expectedFlow {
		return false, 0, nil // Không tồn tại luồng khả thi
	}

	optimalCost := s.baseCost + mcmfCost

	// Khôi phục luồng thực tế
	actualFlows := make([]int64, len(s.edges))
	for i, e := range s.edges {
		flowOnAux := mcmf.adj[e.auxFrom][e.auxIdx].flow
		if !e.isNeg {
			actualFlows[i] = e.lower + flowOnAux
		} else {
			// Với cạnh âm, luồng thực tế = upper - luồng đẩy ngược
			actualFlows[i] = e.upper - flowOnAux
		}
	}

	return true, optimalCost, actualFlows
}

func main() {
	// Mô phỏng mạng lưới vận tải gồm 4 nút (0 đến 3)
	// Nút 0: Nhà máy sản xuất (Cung cấp 4 đơn vị -> Demand = -4)
	// Nút 3: Trung tâm phân phối (Tiêu thụ 4 đơn vị -> Demand = +4)
	// Nút 1, 2: Trạm trung chuyển (Demand = 0)
	n := 4
	solver := NewMinCostCirculationSolver(n)
	solver.SetDemand(0, -4)
	solver.SetDemand(1, 0)
	solver.SetDemand(2, 0)
	solver.SetDemand(3, 4)

	// Danh sách các cung vận chuyển: (from, to, lower, upper, unit_cost)
	// Có cung chi phí âm (ví dụ: được trợ giá vận chuyển hoặc hoàn tiền ưu đãi tuyến)
	solver.AddEdge(0, 1, 1, 3, 2)  // 0 -> 1: [1, 3], cost = 2
	solver.AddEdge(0, 2, 1, 3, 5)  // 0 -> 2: [1, 3], cost = 5
	solver.AddEdge(1, 2, 0, 2, -1) // 1 -> 2: [0, 2], cost = -1 (Được trợ giá!)
	solver.AddEdge(1, 3, 1, 4, 4)  // 1 -> 3: [1, 4], cost = 4
	solver.AddEdge(2, 3, 1, 3, 1)  // 2 -> 3: [1, 3], cost = 1

	feasible, minCost, flows := solver.Solve()
	if !feasible {
		fmt.Println("Hệ thống không thể đáp ứng ràng buộc khả thi!")
		return
	}

	fmt.Println("=== KẾT QUẢ TỐI ƯU HÓA LUỒNG CHI PHÍ CỰC TIỂU CÓ CẬN DƯỚI ===")
	fmt.Printf("Chi phí tối thiểu toàn mạng: %d\n", minCost)
	fmt.Println("\nChi tiết luồng phân bổ trên từng cung:")
	for i, e := range solver.edges {
		fmt.Printf("- Cung %d -> %d: Luồng = %d / [%d, %d] | Đơn giá = %d | Thành tiền = %d\n",
			e.from, e.to, flows[i], e.lower, e.upper, e.cost, flows[i]*e.cost)
	}

	// Kiểm tra tính cân bằng luồng tại từng đỉnh
	fmt.Println("\nKiểm tra điều kiện cân bằng luồng (Flow Conservation):")
	net := make([]int64, n)
	for i, e := range solver.edges {
		net[e.to] += flows[i]
		net[e.from] -= flows[i]
	}
	for u := 0; u < n; u++ {
		fmt.Printf("Đỉnh %d: Luồng vào ròng = %d (Kỳ vọng: %d)\n", u, net[u], solver.demands[u])
	}
}

5. Phân tích Độ phức tạp và Tính chất

• Đảm bảo không chu trình âm: Nhờ kỹ thuật bão hòa trước (Pre-saturation) mọi cạnh có $w(e) < 0$, đồ thị mạng phụ trợ ban đầu có trọng số cạnh strictly không âm ($w \ge 0$). Do đó, ta có thể khởi tạo thế năng Johnson $h(u) = 0$ cho mọi nút và thay thế toàn bộ SPFA bằng Dijkstra, hạ thời gian mỗi pha tăng luồng xuống $O(E \log V)$.

6. Ứng dụng Thực tế

• Quy hoạch Hàng không & Luân chuyển Máy bay (Airline Tail Assignment with Maintenance Deadlines): Mỗi tàu bay phải hoàn thành các chặng bay bắt buộc ($l(e) = 1$) và trở về căn cứ bảo dưỡng định kỳ đúng hạn. Một số chặng bay đem lại doanh thu cao (chi phí âm $w(e) < 0$), trong khi việc đỗ tàu bay tại các sân bay trung chuyển phát sinh phí lưu bãi. Min-Cost Flow with Lower Bounds giải quyết bài toán xếp lịch có lợi nhuận ròng lớn nhất.

• Tối ưu hóa Lưới điện Phân phối Đa nguồn (Economic Dispatch in Microgrids): Các nhà máy điện truyền thống có công suất phát điện tối thiểu ($l(e)$) để duy trì lò hơi, trong khi nguồn năng lượng tái tạo (điện gió, mặt trời) có chi phí cận biên gần như bằng 0 hoặc được trợ giá âm. Thuật toán phân bổ dòng công suất đáp ứng phụ tải các trạm biến áp với chi phí phát điện thấp nhất.

• Quản trị Chuỗi cung ứng Đa phương thức có Hợp đồng Nguyên tắc (Supply Chain with Minimum Volume Commitments - MVC): Doanh nghiệp ký cam kết khối lượng vận chuyển tối thiểu với các hãng tàu hỏa và tàu biển để nhận mức giá ưu đãi. Việc không đạt sản lượng cam kết sẽ bị phạt hợp đồng. Mô hình này giúp tìm ra phương án vận chuyển tối ưu tổng chi phí thực tế.