Bài toán tìm luồng cực đại và ứng dụng trong vận chuyển hàng cứu trợ thiên tai tại tỉnh sekong nước chdcnd lào

Đ萎IăH窺CăĐĨăN允NG

TR姶云NGăĐ萎IăH窺CăS姶ăPH萎M

----------

KEOOUNHUANE VONGPHISITH

BĨIăTOỄNăTỊMăLU唄NGăC衛CăĐ萎IăVĨă永NGăD影NGăTRONGă

V一NăCHUY韻NăHĨNGăC永UăTR営 THIểNăTAIăT萎IăT迂NHă

SEKONGăN姶閏CăC浦NGăHọAăDỂNăCH曳ăNHỂNăDỂNăLĨO

LU一NăV;NăTH萎CăS┃

H烏ăTH渦NGăTHỌNGăTIN

ĐƠăN印ngă- N<mă2020

Đ萎IăH窺CăĐĨăN允NG

TR姶云NGăĐ萎IăH窺CăS姶ăPH萎M

----------

KEOOUNHUANE VONGPHISITH

BĨIăTOỄNăTỊMăLU唄NGăC衛CăĐ萎IăVĨă永NGăD影NGăTRONGă

V一NăCHUY韻NăHĨNGăC永UăTR営ăTHIểNăTAIăT萎IăT迂NHă

SEKONG N姶閏CăC浦NGăHọAăDỂNăCH曳ăNHỂNăDỂNăLĨO

Chuyên ngành: H烏ăTH渦NGăTHỌNGăTIN

Mƣăs嘘:ă8480104

LU一NăV;NăTH萎CăS┃

NG姶云IăH姶閏NGăD郁NăKHOAăH窺C:

TS. NGUY右NăĐỊNHăL井U

ĐƠăN印ngă- N<mă2020

v

M影CăL影C

L云I C謂M 愛N ...................................................................................................................i

L云I CAM ĐOAN ........................................................................................................... ii

TÓM T溢T ...................................................................................................................... iii

M影C L影C ....................................................................................................................... v

DANH M影C CÁC CH頴 VI蔭T T溢T ........................................................................... vii

DANH M影C B謂NG BI韻U ......................................................................................... viii

DANH M影C CÁC HÌNH ..............................................................................................ix

M雲ăĐ井U ......................................................................................................................... 1

1. LỦ do chọn đ隠 tƠi ................................................................................................ 1

2. M映c tiêu vƠ nhiệm v映 ......................................................................................... 2

3. Đối tư嬰ng vƠ ph衣m vi nghiên c泳u ...................................................................... 2

4. Phư挨ng pháp nghiên c泳u .................................................................................... 2

5. ụ nghĩa c栄a đ隠 tƠi ............................................................................................... 3

6. Bố c映c c栄a đ隠 tƠi ................................................................................................. 3

Ch逢挨ngă1. BĨIăTOỄNăLU唄NGăC衛CăĐ萎I ................................................................ 4

1.1. Phát bi吋u bƠi toán ..................................................................................................... 4

1.1.1. M衣ng, Luồng trong m衣ng ............................................................................. 4

1.1.2. BƠi toán luồng cực đ衣i trong m衣ng ............................................................... 4

1.2. Thu壱t toán Ford-Fulkerson ....................................................................................... 5

1.2.1. Đư運ng đi tăng luồng ..................................................................................... 5

1.2.2. Phư挨ng pháp FordFulkerson ...................................................................... 6

Ch逢挨ngă2. BĨIăTOỄNăLU唄NGăC衛CăĐ萎IăV閏IăCHIăPHệăC衛CăTI韻U ................ 17

2.1. Gi噂i thiệu ................................................................................................................ 17

2.1.1. Phát bi吋u bƠi toán ........................................................................................ 17

2.1.2. Các gi違 thi院t ................................................................................................ 18

2.1.3. Đồ thi thăng dư ........................................................................................... 18

2.2. Đi隠u kiện tối ưu c栄a bƠi toán .................................................................................. 18

2.2.1. Đi隠u kiện tối ưu v隠 chu trình ơm ................................................................ 18

2.2.2.Đi隠u kiện tối ưu v隠 chi phí rút gọn .............................................................. 19

2.2.3. Đi隠u kiện tối ưu bổ sung ............................................................................. 20

2.3. Mối quan hệ gi英a luồng tối ưu vƠ kh違 năng thông qua t衣i các đỉnh ...................... 21

2.4. Một số thu壱t toán gi違i bƠi toán luồng cực đ衣i v噂i chi phí cực ti吋u ........................ 22

vi

2.4.1. Thu壱t toán kh穎 chu trình ơm (Cycle canceling) ......................................... 22

2.4.2. Thu壱t toán tìm đư運ng đi ng逸n nhất liên ti院p (Successive shortest Path) .... 27

2.4.3. Thu壱t toán Primal-Dual .............................................................................. 30

2.4.4. Các thu壱t toán c違i ti院n ................................................................................. 33

Ch逢挨ngă 3. XỂYă D衛NGă 永NGă D影NGă TỊMă Đ姶云NGă V一Nă CHUY韻Nă HĨNGă

C永UăTR営ăMINIMUMăCOSTăMAXăFLOW............................................................ 37

3.1. Yêu cầu thực t院 vƠ lí do xơy dựng 泳ng d映ng .......................................................... 37

3.2. M映c tiêu c栄a 泳ng d映ng ........................................................................................... 37

3.3. Ti院p c壱n bƠi toán .................................................................................................... 37

3.3.1. Phát bi吋u bƠi toán ........................................................................................ 37

3.3.2. Mô hình toán học ........................................................................................ 39

3.3.3. Thu壱t toán ................................................................................................... 40

3.4. Phân tích ................................................................................................................. 42

3.4.1. Yêu cầu ch泳c năng ...................................................................................... 42

3.5.4. Giao diện ắThông tin địa đi吋m” .................................................................. 64

3.5.7. Giao diện ắHi吋n thị k院t qu違” ...................................................................... 71

3.6. Đánh giá k院t qu違 ..................................................................................................... 74

K蔭TăLU一N .................................................................................................................. 75

TĨIăLI烏UăTHAMăKH謂O

QUY蔭TăĐ卯NHăGIAOăĐ陰ăTĨI (bản sao)

vii

DANHăM影CăCỄCăCH頴ăVI蔭TăT溢T

Từăvi院tăt逸t ụăngh┄a

USD United States dollar

GDP Gross Domestic Product

HTML HyperText Markup Language

CSS Cascading Style Sheets

SDK Software Development Kit

API Application Programming Interface

SQL Structured Query Language

NNLT Ngôn ng英 l壱p trình

DFS Depth first search

ATNĐ Áp thấp nhiệt đ噂i

UBND 曳y ban nhơn dơn