Bài toán luồng cực đại với chi phí cực tiểu và ứng dụng trong vận chuyển hàng cứu trợ bão lũ

ĐẠI HỌC ĐÀ NẴNG

TRƯỜNG ĐẠI HỌC SƯ PHẠM

---------------------------------------

HOÀNG VĂN TÁM

BÀI TOÁN LUỒNG CỰC ĐẠI VỚI CHI PHÍ CỰC TIỂU VÀ

ỨNG DỤNG TRONG VẬN CHUYỂN HÀNG

CỨU TRỢ BÃO LŨ

Chuyên ngành: Hệ thống thông tin

Mã số: 8480104

TÓM TẮT LUẬN VĂN THẠC SĨ HỆ THỐNG THÔNG TIN

Đà Nẵng - Năm 2018

Công trình được hoàn thành tại

TRƯỜNG ĐẠI HỌC SƯ PHẠM

Người hướng dẫn khoa học: PGS.TSKH. Trần Quốc Chiến

Phản biện 1: TS. Nguyễn Đình Lầu

Phản biện 2: TS. Nguyễn Quang Thanh

Luận văn đã được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp

thạc sĩ Hệ thống thông tin họp tại Trường Đại học Sư phạm vào ngày

18 tháng 11 năm 2018

Có thể tìm hiểu luận văn tại:

Thư viện Trường Đại học Sư phạm – ĐHĐN

Khoa Tin Học, Trường Đại học Sư phạm – ĐHĐN

1

MỞ ĐẦU

1. Lý do chọn đề tài

Bài toán luồng cực đại trong mạng là một trong số những bài

toán tối ưu trên đồ thị có những ứng dụng rộng rãi trong thực tế cũng

như những ứng dụng thú vị trong lý thuyết tổ hợp. Bài toán được đề

xuất vào đầu những năm 1950, và gắn liền với tên tuổi của hai nhà

bác học Mỹ là Ford và Fulkerson. Bài toán luồng cực đại trong mạng

có nhiều ứng dụng trong thực tế như: Bài toán xác định cường độ

dòng lớn nhất của dòng vận tải giữa hai nút của một bản đồ giao

thông, bài toán tìm luồng dầu lớn nhất có thể bơm từ tàu chở dầu vào

bể chứa của một hệ thống đường ống dẫn dầu…Ngoài ra, ứng dụng

của bài toán còn để giải các bài toán như: Bài toán đám cưới vùng

quê, bài toán về hệ thống đại diện chung, bài toán phân nhóm sinh

hoạt, bài toán lập lịch cho hội nghị …

Với sự xuất hiện ngày càng nhiều của các hệ thống mạng như:

hệ thống mạng điện, mạng sản xuất và phân phối hàng hóa, mạng

giao thông và phổ biến nhất hiện nay là mạng internet đã làm nảy

sinh ra nhu cầu vận chuyển các chất liệu trên các mạng này sao cho

đạt hiệu quả cao nhất; chất liệu ở đây có thể là dòng điện, dữ liệu,

hàng hóa..hiệu quả ở đây có thể xét theo tiêu chuẩn về thời gian, độ

dài quãng đường, chi phí tiền bạc, mức độ an toàn... và bài toán

luồng cực đại trên mạng ngày càng khẳng định được tính quan trọng

của nó trong các ngành khoa học hiện đại. Sự phát triển mạnh mẽ của

ngành công nghệ thông tin cùng với khả năng tính toán rất nhanh của

máy tính đã giúp việc giải quyết bài toán luồng cực đại trên mạng

hiệu quả hơn và đem lại nhiều ứng dụng thực tiễn hơn.

Việt Nam là một những nước chịu ảnh hưởng lớn nhất của hiện

tượng biến đổi khí hậu trong hai thập kỷ trở lại đây. Ở nước ta, mỗi

2

năm thiên tai cướp đi mạng sống của 466 người, thiệt hại trên 1.5 tỷ

USD tương đương 1.5% GDP. Trong đó tần suất xuất hiện cao nhất

phải nói đến là bão lũ, ngập úng (Nguồn: Báo cáo cùa Ban chỉ đạo

Phòng chống lụt bão Trung ương). Một vài trận bão lụt lớn trong thời

gian gần đây có thể kể đến như trận lụt ơ Quảng Ninh (30/7/2015),

bão Nari (15/10/2013), bão Wutip (30/9/2013), trận lụt lớn ở miền

Trung (10/2011)... Nhằm giảm nhẹ thiệt hại về người và của do bão

lũ gây ra thì công tác phòng chống và cứu hộ được đặc biệt chú

trọng. Trong đó, vận chuyển hàng cứu trợ cho người dân là một trong

những công việc phải được thực hiện một cách nhanh chóng và hiệu

quả. Chính vì vậy, tôi quyết định chọn đề tài “Bài toán luồng cực đại

với chi phí cực tiểu và ứng dụng trong vận chuyển hàng cứu trợ bão

lũ” làm đề tài tốt nghiệp luận văn cao học.

2. Mục tiêu và nhiệm vụ

2.1. Mục tiêu

- Nắm được các thuật toán giải bài toán luồng cực đại với chi

phí cực tiểu.

- Xây dựng thành công chương trình hỗ trợ công tác vận

chuyển hàng cứu trợ cho người dân các vùng lũ lụt.

2.2. Nhiệm vụ

Về lý thuyết:

- Tìm hiểu lý thuyết bài toán luồng cực đại và một số bài toán

ứng dụng của bài toán luồng cực đại.

- Nghiên cứu kỹ các thuật toán trên bài toán luồng cực đại với

chi phí cực tiểu.

- Nắm được quy trình cài đặt thuật toán, xây dựng ứng dụng

cho smartphone.

Về thực tiễn:

3

- Tìm ra được phương án vận chuyển hàng cứu trợ cho người

dân các vùng lũ lụt hiệu quả và tốn ít chi phí nhất.

- Xây dựng chương trình máy tính thực hiện được chức năng

trên.

3. Đối tượng và phạm vi nghiên cứu

3.1. Đối tượng nghiên cứu

- Bài toán luồng cực đại với chi phí cực tiểu.

- Các ngôn ngữ lập trình: Html, Css, JavaScript, C#, Google

Maps SDK, Google Maps API…

- Hệ quản trị cơ sở dữ liệu: SQL.

3.2. Phạm vi nghiên cứu

- Bài toán luồng cực đại, các thuật toán cơ bản giải bài toán

luồng cực đại với chi phí cực tiểu.

- Chỉ nghiên cứu và phát triển ứng dụng tại tỉnh Quảng Bình.

4. Phương pháp nghiên cứu

Về phương pháp nghiên cứu, tôi sử dụng hai phương pháp

chính là nghiên cứu lý thuyết và nghiên cứu thực nghiệm.

4.1. Phương pháp nghiên cứu lý thuyết

- Nghiên cứu các tài liệu về cơ sở lý thuyết: Bài toán luồng

cực đại với chi phí cực tiểu.

- Các tài liệu cài đặt một số dạng bài toán luồng cực đại.

- Các tài liệu liên quan đến một số nghiên cứu.

- Các tài liệu về quy trình xây dựng, phát triển phần mềm ứng

dụng.

- Các tài liệu về thực trạng công tác cứu trợ người dân các

vùng lũ lụt.

4.2. Phương pháp nghiên cứu thực nghiệm

Sử dụng phương pháp nghiên cứu lý thuyết kết hợp với nghiên

4

cứu thực nghiệm:

- Cài đặt các thuật toán cho bài toán.

- Viết chương trình cho bài toán ứng dụng cụ thể.

- Chạy thử nghiệm, lưu trữ kết quả đạt được và đánh giá lại kết

quả.

5. Ý nghĩa của đề tài

Về mặt khoa học, trên cơ sở nghiên cứu lý thuyết bài toán

luồng cực đại và các phương pháp giải bài toán luồng cực đại với chi

phí cực tiểu, luận văn xây dựng được chương trình hỗ trợ công tác

vận chuyển hàng cứu trợ cho người dân các vùng lũ lụt.

Về mặt thực tiễn: Với việc xây dựng thành công chương trình,

công tác vận chuyển hàng cứu trợ khi có bão lũ xẩy ra sẽ được tiến

hành một cách nhanh chóng, nâng cao hiệu quả và tiết kiệm được chi

phí vận chuyển cho từng chuyến hàng.

6. Bố cục của đề tài

Ngoài phần mở đầu và kết luận. Toàn bộ nội dung của luận

văn được chia làm 3 chương sau:

Chương 1: Bài toán luồng cực đại

Chương 2: Bài toán luồng cực đại với chi phí cực tiểu

Chương 3: Xây dựng ứng dụng

5

CHƯƠNG 1

BÀI TOÁN LUỒNG CỰC ĐẠI

1.1. Phát biểu bài toán

1.1.1. Mạng, Luồng trong mạng

Định nghĩa 1. Ta gọi mạng là đồ thị có hướng G = (V,E), trong

đó có duy nhất một đỉnh s không có cung đi vào gọi là điểm phát,

duy nhất một đỉnh t không có cung đi ra gọi là điểm thu và mỗi cung

e = (v,w) E được gán với một số không âm c(e) = c(v,w) gọi là

khả năng thông qua của cung e.

Để thuận tiện cho việc trình bày ta sẽ quy ước rằng nếu không

có cung (v,w) thì khả năng thông qua c(v,w) được gán bằng 0.

Định nghĩa 2. Giả sử cho mạng G = (V,E). Ta gọi luồng f trong

mạng G = (V,E) là ánh xạ f: E  R+ gán cho mỗi cung e =(v,w)

E một số thực không âm f(e) = f(v,w), gọi là luông trên cung e, thoả

mãn các điều kiện sau:

1. Luồng trên mỗi cung e E không vượt quá khả năng thông

qua của nó:

0 ≤ f (e) ≤ c(e),

2. Điều kiện cân bằng luồng trên mỗi đỉnh của mạng: Tổng

luồng trên các cung đi vào đỉnh v bằng tổng luồng trên các cung đi ra

khỏi đỉnh v, nếu v ≠ s,t:

Trong đó E-

(v) và E+

(v) tương ứng là tập các cung đi vào và đi

ra khỏi đỉnh v.

3. Giá trị của luồng f là số

( ) ( )

( ) ( ) ( )

e E v e E v

val f f e f e

 

 

   

( ) ( )

( ) ( )

e E v e E v

f e f e

 

 

 

6

1.1.2. Bài toán luồng cực đại trong mạng

1.1.2.1. Phát biểu bài toán luồng cực đại

Trong thực tế ta thường gặp bài toán gọi là bài toán tìm luồng

cực đại như sau: Cho mạng G với nguồn a, đích z và khả năng thông

qua cij, (i,j)G. Trong số các luồng trên mạng G tìm luồng có giá trị

lớn nhất.

Bài toán luồng cực đại có thể biểu diễn như bài toán quy hoạch

tuyến tính

v(f) = 

a i G

ai f

( , )

 

i a G

ia f

( , )

 max

với điều kiện

0  fij  cij (i,j)G



i k G

ik f

( , )

=



k j G

kj f

( , )

k  V \ {a; z}

Vì giá trị luồng v(f) 



a i G

ai c

( , )

và tồn tại luồng {fij = 0, (i,j)G},

nên, theo lý thuyết quy hoạch tuyến tính, tồn tại luồng cực đại.

1.1.2.2. Luồng cực đại và lát cắt cực tiểu

Định nghĩa

Cho mạng G =(V,E,c) với nguồn a và đích z. Với mọi S, T 

V, ký hiệu tập các cung đi từ S vào T là (S,T), tức

(S,T) = {(i, j)  E  i  S & j  T}

Nếu S, T  V là phân hoạch của V ( ST = V & ST =  ) và

a S, zT, thì cặp (S,T) gọi là lát cắt (nguồnđỉnh) .

Khả năng thông qua của lát cắt (S, T) là giá trị

C(S, T) =



iS jT

ij c

Cho luồng f và lát cắt (S,T) trên mạng G. Với mọi S, T  V,

ký hiệu

7

f(S,T) =



(i, j)(S ,T )

ij f

1.2. Thuật toán Ford-Fulkerson

1.2.1. Đường đi tăng luồng

1.2.2. Phương pháp FordFulkerson

Phương pháp này được Ford và Fulkerson đưa ra năm 1962. Ý

tưởng xây dựng luồng cực đại như sau: xuất phát từ luồng nào đó, ta

tìm đường đi tăng luồng từ a đến z cho phép hiệu chỉnh giá trị luồng

trên đường đi đó sao cho luồng mới có giá trị lớn hơn. Nếu không tìm

được đường đi như vậy thì ta có luồng cực đại.

Sau đây là mô tả thuật toán tổng quát. Thuật toán này có thể

cải tiến để tăng hiệu năng.

 Đầu vào. Mạng G = (V, E) với nguồn a, đích z, khả năng

thông qua C = (cij), (i,j)G.

Các đỉnh trong G được sắp xếp theo thứ tự nào đó.

 Đầu ra. Luồng cực đại F = (fij), (i,j)G

 Các bước.

1. Khởi tạo

Luồng xuất phát: fij := 0 (i,j)G

Đặt nhãn cho đỉnh nguồn

a( , )

Tạo lập tập S gồm các đỉnh đã có nhãn nhưng chưa được dùng

để sinh nhãn, S’ là tập đỉnh được gán nhãn nhờ các đỉnh của tập S

S : = { a }, S’ := 

2. Sinh nhãn

2.1. Chọn đỉnh sinh nhãn

 Trường hợp S  : Chọn đỉnh u  S nhỏ nhất (theo thứ tự).

Loại u khỏi S, S:= S \ {u}. Ký hiệu nhãn của u là (p, ) và A là tập

8

các đỉnh chưa có nhãn và kề đỉnh sinh nhãn u.

Qua bước 2.2.

 Trường hợp S =  và S’  : Gán S := S’ và S’ := . Quay

lại bước 2.1.

 Trường hợp S =  và S’ = , thì kết thúc, luồng F là cực đại.

2.2. Gán nhãn cho đỉnh chưa có nhãn và kề đỉnh sinh nhãn

 Trường hợp A = : Quay lại bước 2.1.

 Trường hợp A  : Chọn t  A nhỏ nhất (theo thứ tự). Loại t

khỏi A, A:= A \ { t }. Gán nhãn cho t như sau:

Nếu (u,t)E và fu,t < cu,t , đặt nhãn đỉnh t là ( u, min{, cu,t 

fu,t}).

Nếu (t, u)E và ft,u > 0, đặt nhãn đỉnh t là (u, min{, ft,u}).

Nếu t không được gán nhãn thì quay lại bước 2.2.

Nếu t được gán nhãn và t = z thì sang bước 3.

Nếu t được gán nhãn và t  z thì bổ sung t vào S’, S’ := S’

{t}, và quay lại bước 2.2.

3. Hiệu chỉnh tăng luồng

Giả sử z có nhãn (q, ). Ta hiệu chỉnh luồng f như sau.

3.1. Khởi tạo

j := z, i := q

3.2. Hiệu chỉnh

Nếu cung (i, j)  G, thì hiệu chỉnh fij = fij + .

Nếu cung (j, i)  G, thì hiệu chỉnh fji = fji  .

3.3. Tịnh tiến

Nếu i = a thì xoá tất cả nhãn của các đỉnh trên mạng, trừ đỉnh

nguồn a, và quay lại bước 2.

Nếu i  a, thì đặt j := i và i := p, với p là thành phần thứ nhất

của nhãn đỉnh j. Sau đó quay lại bước 3.2.

9

CHƯƠNG 2

BÀI TOÁN LUỒNG CỰC ĐẠI VỚI CHI PHÍ CỰC TIỂU

2.1. Giới thiệu

2.1.1. Phát biểu bài toán

Trong thực tế ta thường phải giải quyết bài toán: trong các

luồng cực đại tìm luồng có chi phí nhỏ nhất, trong đó chi phí là tổng

chi phí thực hiện luồng trên tất cả các cung.

Định nghĩa. Mạng chi phí cung G = (V,E,c,p) là mạng

(V,E,c) với pij là đơn giá chi phí luồng trên cung (i. j), i,j  V.

Chi phí luồng của luồng fij trên cung (i,j) là tích fij.pij.

Chi phí của luồng f trên mạng G là tổng chi phí luồng của tất

cả các cung.



i j E

ij pij f

( , )

.

Giả thiết: Khả năng thông qua của các cung nguyên dương và

không lớn hơn hằng số M và đơn giá chi phí của các cung nguyên

dương và không lớn hơn hằng số C.

Ví dụ:

Hình 2.1. Ví dụ mạng vận tải