Mô hình mạng (vận trù học)

From Systems analysis wiki
Jump to navigation Jump to search

Mô hình mạng (trong nghiên cứu vận trù; tiếng Anh: Network models) — là một lớp mô hình toán học biểu diễn bài toán dưới dạng đồ thị (mạng), trong đó các đỉnh (nút) biểu thị các đối tượng hoặc trạng thái, còn các cạnh (cung) biểu thị các mối liên hệ hoặc quá trình giữa chúng[1]. Trong bối cảnh tối ưu hóa, mạng thường được hiểu là đồ thị có hướng, mà trong phân tích vận trù được gọi trực tiếp là "mạng"; các đỉnh của mạng đó được gọi là nút, còn các cạnh được gọi là cung[2].

Mô hình mạng là công cụ mạnh mẽ để phân tích và tối ưu hóa các hệ thống phức tạp trong các lĩnh vực như logistics, viễn thông, quản lý dự án và tài chính. Sức mạnh của chúng nằm ở mức độ trừu tượng hóa cao: một nút có thể đại diện cho một thành phố, một bộ định tuyến máy tính hoặc một giai đoạn của dự án, còn một cung có thể đại diện cho một con đường, một kênh truyền thông hoặc một thao tác công nghệ.

Định nghĩa và thuật ngữ

Nền tảng của mô hình mạng là lý thuyết đồ thị. Các khái niệm then chốt bao gồm:

  • Mạng luồng (tiếng Anh: flow network): đồ thị có hướng trong đó mỗi cạnh có công suất (capacity) và luồng (flow). Trong đồ thị có hai đỉnh đặc biệt: nguồn (source), từ đó luồng xuất phát, và đích (sink), mà vào đó luồng đi đến[1].
  • Định luật bảo toàn luồng: Đối với bất kỳ đỉnh nào không phải nguồn hay đích, tổng luồng vào phải bằng tổng luồng ra. Điều kiện này là dạng rời rạc của các định luật bảo toàn vật lý[3].
  • Lập kế hoạch mạng: Mô hình biểu diễn dự án như một tập hợp các thao tác liên kết với nhau (cung) và các sự kiện (nút). Các mạng như vậy là đồ thị có hướng không chu trình, phản ánh thứ tự thực hiện các công việc[4].

Các tính chất và định lý then chốt

Mô hình mạng có một số tính chất đặc biệt cho phép áp dụng các thuật toán hiệu quả cao để giải chúng.

  • Tính nguyên của nghiệm: Nhiều bài toán tối ưu hóa mạng (ví dụ, bài toán luồng cực đại hay đường đi ngắn nhất) có tính chất unimodular toàn phần của ma trận ràng buộc. Nhờ đó, nếu các tham số bài toán (công suất, độ dài) là số nguyên, thì nghiệm tối ưu tìm được bằng phương pháp quy hoạch tuyến tính cũng sẽ là số nguyên mà không cần thêm các ràng buộc bổ sung[5][6].
  • Định lý về luồng cực đại và lát cắt cực tiểu: Kết quả trung tâm của lý thuyết luồng. Phát biểu rằng giá trị luồng cực đại từ nguồn đến đích bằng công suất cực tiểu trong số tất cả các lát cắt phân tách nguồn và đích. Định lý này thiết lập tiêu chí tối ưu cho luồng và là nền tảng của nhiều thuật toán[6][7].
  • Nguyên lý tối ưu cho đường đi ngắn nhất: Nếu đường đi từ điểm A đến điểm C là ngắn nhất, thì bất kỳ đoạn nào của nó (ví dụ, từ điểm trung gian B đến C) cũng là đường đi ngắn nhất giữa các đỉnh tương ứng. Tính chất này, làm nền tảng cho quy hoạch động, đảm bảo tính đúng đắn của các thuật toán như thuật toán Dijkstra[8].
  • Tính chất của cây khung nhỏ nhất (MST):
  • Tính chất lát cắt: Đối với bất kỳ lát cắt nào của đồ thị, cạnh có trọng số nhỏ nhất cắt qua lát cắt đó thuộc ít nhất một MST.
  • Tính chất chu trình: Trong bất kỳ chu trình nào của đồ thị, cạnh có trọng số lớn nhất không thuộc bất kỳ MST nào.

Dựa trên các tính chất này là tính đúng đắn của các thuật toán "tham lam" Prim và Kruskal[9].

Các bài toán chính của tối ưu hóa mạng

  • Bài toán đường đi ngắn nhất: Tìm đường đi có tổng độ dài (trọng số) nhỏ nhất giữa hai nút cho trước. Được giải bằng thuật toán Dijkstra (với trọng số không âm) hoặc thuật toán Bellman-Ford (với trọng số tùy ý)[8].
  • Bài toán luồng cực đại: Xác định luồng lớn nhất có thể từ nguồn đến đích với các công suất cung cho trước. Phương pháp giải cổ điển là thuật toán Ford–Fulkerson[6].
  • Bài toán cây khung nhỏ nhất: Tìm đồ thị con kết nối tất cả các đỉnh của mạng và có tổng chi phí cạnh nhỏ nhất.
  • Phương pháp đường găng (CPM): Trong các mô hình mạng lập kế hoạch, xác định chuỗi công việc dài nhất, thiết lập thời gian hoàn thành toàn bộ dự án ngắn nhất có thể. Các công việc trên đường này có dự trữ thời gian bằng không[10].

Ví dụ

  • Đường đi ngắn nhất: Tìm kiếm tuyến đường tối ưu bằng hệ thống dẫn đường giữa hai điểm trên bản đồ thành phố, trong đó các thành phố là nút, còn các con đường là cung với trọng số bằng độ dài hoặc thời gian di chuyển.
  • Luồng cực đại: Xác định công suất tối đa của mạng đường ống, trong đó các trạm bơm là nút, còn các ống là cung với công suất giới hạn.
  • Cây khung nhỏ nhất: Thiết kế mạng truyền thông (ví dụ, lắp đặt cáp quang) để kết nối nhiều thành phố với tổng chiều dài cáp nhỏ nhất.
  • Đường găng: Trong dự án xây dựng nhà, trong đó các công việc (đổ móng, dựng tường, lắp mái) có thời gian xác định và các ràng buộc công nghệ, đường găng xác định thời hạn hoàn thành xây dựng nhỏ nhất. Bất kỳ sự chậm trễ nào của công việc trên đường này đều sẽ dẫn đến chậm trễ toàn bộ dự án[10].

Xem thêm

  • Nghiên cứu vận trù
  • Lý thuyết đồ thị
  • Bài toán vận tải
  • Phương pháp đường găng
  • PERT

Chú thích

  1. ↑ 1.0 1.1 "Flow network". Wikipedia. [1]
  2. ↑ "Тема 10: Сетевые модели". Учебное пособие. Гомель: БелГУТ. [2]
  3. ↑ "Транспортная сеть". Википедия. [3]
  4. ↑ "Сетевое планирование". Википедия. [4]
  5. ↑ Bradley S. P., Hax A. C., Magnanti T. L. (1977). Applied Mathematical Programming. Addison-Wesley. Ch.8: Network Models. [5]
  6. ↑ 6.0 6.1 6.2 "Задача о максимальном потоке". Википедия. [6]
  7. ↑ Goldberg A. V., Tardos É., Tarjan R. E. (1990). "Network Flow Algorithms". In: Paths, Flows, and VLSI-Layout. Springer. [7]
  8. ↑ 8.0 8.1 "Задача о кратчайшем пути". Википедия. [8]
  9. ↑ "Минимальное остовное дерево". Википедия.
  10. ↑ 10.0 10.1 "Метод критического пути". Википедия. [9]
Retrieved from "https://systems-analysis.ru/int/index.php?title=Mô_hình_mạng_(vận_trù_học)&oldid=11564"