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

BM Khoa học Máy tính • TOÁN RỜI RẠC • Fall 2005 • NGUYỄN ĐỨC NGHĨA

Max Flow Applications

s

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

2

Bộ môn KHMT

t

NỘI DUNG

(cid:0)

Một số bài toán luồng tổng quát –Bài toán với nhiều điểm phát và điểm thu –Bài toán với hạn chế thông qua ở nút

(cid:0)

Một số ứng dụng trong tổ hợp –Bài toán cặp ghép cực đại trong đồ thị hai phía –Độ tin cậy của mạng

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

3

Bộ môn KHMT

Một số bài toán luồng tổng quát

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

4

Bộ môn KHMT

M¹ng  víi nhiÒu ®iÓm ph¸t vµ ®iÓm thu

ng  ph¸t là

ớ ượ

ớ ượ ng  thu là b

a 1,  1, b 2, ..., b q

(cid:0)  XÐt m¹ng  G víi p  ®iÓm ph¸t s 1, s 2,..., s p v i l a 2, ..., a p vµ q  ®iÓm thu t1, t 2,..., t q  v i l (cid:0)  Gi¶ s ö  r»ng  luång  c ã thÓ ®i tõ  mé t ®iÓm ph¸t bÊt kú ®Õn tÊt c ¶  c ¸c  ®iÓm thu.  (cid:0)  T×m luång  c ùc  ®¹i tõ  c ¸c  ®iÓm ph¸t ®Õn c ¸c  ®iÓm thu

s1

t1

s2

t2

sp

tq

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

5

Bộ môn KHMT

M¹ng  víi nhiÒu ®iÓm ph¸t vµ ®iÓm thu

b i là l­îng  thu c ña ®iÓm thu ti.

(cid:0)  Đ­a vµo  mé t ®iÓm ph¸t g i¶ s  vµ mé t ®iÓm thu g i¶ t vµ c ¸c  c ¹nh nè i s  víi  tÊt c ¶ c ¸c  ®iÓm ph¸t vµ c ¸c  c ¹nh nè i c ¸c  ®iÓm thu víi t.  (cid:0)  Kntq c ña c ung  (s ,s i) s Ï b»ng  ai là l­îng  ph¸t c ña s i.  (cid:0)  Kntq c ña (ti, t) s Ï b ng  ằ (cid:0)  Bài to ¸n d n v  bài to ¸n v i 1 đi m ph¸t và m t đi m thu.

ẫ ề ớ ộ ể ể

s1

t1

b1

a1

s2

t2

t

b2

a2

s

ap

bq

sp

tq

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

6

Bộ môn KHMT

Bài toán với hạn chế thông qua ở nút

(cid:0)  Gi¶ s ö  tro ng  m¹ng  G, ng o µi kh¶ n¨ng  th«ng  qua c ña

c ¸c  c ung  c (u, v ), ë  mç i ®Ønh v ˛ V  c ßn c ã kh¶ n¨ng

th«ng  qua c ña ®Ønh lµ d (v ), vµ ®ßi hái tæ ng  luång  ®i

vµo  ®Ønh v  kh«ng  ®­îc  v­ît qu¸ d (v ), tø c  lµ

du

f(w,v) (cid:0)

d(v).

(cid:0)

4

u

w(cid:0) V dt 5 ds

t

s

1

3 2

v

• T×m luång  c ùc  ®¹i t

ừ s  đ n ế t  tro ng  m¹ng  G.

dv

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

7

Bộ môn KHMT

Bài toán với hạn chế thông qua ở nút

(cid:0)  X©y dùng  mé t m¹ng  G' s ao  c ho : mç i ®Ønh v  c ña G t­¬ng  ø ng  víi

2 ®Ønh v +, v ­ tro ng  G', mç i c ung  (u, v ) tro ng  G  ø ng  víi c ung  (u­,

v +) tro ng  G', mç i c ung  (v ,w ) tro ng  G ø ng  víi c ung  (v ­, w +) tro ng

G'. Ng o µi ra, mç i c ung  (v +, v ­) tro ng  G' c ã kh¶ n¨ng  th«ng  qua lµ

d (v ), tø c  lµ b»ng  kh¶ n¨ng  th«ng  qua c ña ®Ønh v  tro ng  G.

du

du

u+

u-

4 5 4

u

dt 5 ds ds dt 1

t-

t+

t

s+

s-

s

1

3 2 dv 2 3

v

v+

v-

dv

Qui về bài toán tìm luồng cực đại trong G’ Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

8

Bộ môn KHMT

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

ỨNG DỤNG TRONG TỔ HỢP

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

9

Bộ môn KHMT

Bài toán ghép cặp (Matching Problems)

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

10

Bộ môn KHMT

Cặp ghép (Matching)

Cho G = (V, E) là đồ thị vô hướng. Cặp ghép trong đồ thị G là tập các cạnh của đồ thị đôi một không có đỉnh chung

Bài toán cặp ghép cực đại : Tìm cặp ghép với lực lượng lớn nhất

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

11

Bộ môn KHMT

Bài toán cặp ghép cực đại trên đồ thị hai phía

1

6

2

7

Đồ thị vô hướng G=(V,E) là hai phía nếu V có thể phân hoạch thành 2 tập X và Y sao cho mỗi cạnh e(cid:0) E đều có thể biểu diễn e=(x, y) với x(cid:0) X và y(cid:0) Y.

3

8

Cặp ghép là tập các cạnh đôi một không có đỉnh chung.

4

9

5

10

Bài toán cặp ghép cực đại : Tìm cặp ghép có lực lượng lớn nhất

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

12

Bộ môn KHMT

Qui dẫn về bài toán luồng cực đại

Xây dựng mạng G’

6

1

Mỗi cung (j, t) có kntq là 1.

1

7

2

8

3

s

t

9

4

1

Mỗi cung (s, i) có kntq là 1.

5

10

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

Mỗi cạnh (x,y) thay bởi cung (x,y) với kntq +∞.

13

Bộ môn KHMT

Tìm luồng cực đại

1

6

2

7

3

8

s

t

4

9

5

10

Giá trị luồng cực đại từ s đến t là 4.

Cặp ghép cực đại có lực lượng là 4.

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

14

Bộ môn KHMT

Bipartite Matching: Tính đúng đắn

Đinh lý. Lực lượng của cặp ghép cực đại trong G = giá trị của luồng cực đại trong G'. CM. Chỉ cần chứng minh G có cặp ghép lực lượng k khi và chỉ khi G’ có luồng với giá trị k.

(cid:0) Xét luồng f đẩy luồng 1 đơn vị dọc theo mỗi một trong k đường đi.

(cid:0) ) Cho cặp ghép M có lực lượng k.

(cid:0) f là luồng có giá trị k. ■

1

1'

1

1'

1

1

2

2'

2

2'

3

3'

s

3

3'

t

4

4'

4

4'

G'

G

5

5'

5

5'

(cid:0)

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

15

Bộ môn KHMT

Bipartite Matching: Tính đúng đắn

(cid:0)

) Cho f là luồng giá trị k trong G'. (cid:0) Từ định lý về tính nguyên (cid:0) tìm được luồng nguyên: f(e) chỉ là 0

(cid:0) Gọi M = tập các cạnh e từ X sang Y với f(e) = 1.

hoặc 1.

– mỗi đỉnh trong X và Y là đầu mút của (cid:0) – |M| = k, do luồng có giá trị k nên có đúng k cạnh từ X sang Y với

một cạnh trong M

giá trị luồng trên cung là 1 ■

1

1'

1

1'

1

1

2

2'

2

2'

3

3'

3

s

3'

t

4

4'

4

4'

G'

G

5

5'

5

5'

(cid:0)

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

16

Bộ môn KHMT

Cặp ghép hoàn hảo (Perfect Matching)

E được gọi là hoàn hảo (perfect) nếu mỗi

ĐN. Cặp ghép M (cid:0) đỉnh của đồ thị là đầu mút của đúng 1 cạnh trong M.

Câu hỏi. Khi nào đồ thị hai phía có cặp ghép hoàn hảo?

Cấu trúc của đồ thị hai phía có cặp ghép hoàn hảo.

(cid:0) Rõ ràng ta phải có |X| = |Y|.

(cid:0) Điều kiện nào là cần nữa?

(cid:0) Các điều kiện đủ là gì?

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

17

Bộ môn KHMT

Cặp ghép hoàn hảo

(S) là tập các đỉnh kề

Ký hiệu. Gỉa sử S là tập con các đỉnh, ký hiệu (cid:0) với các đỉnh trong S.

Y, E) có cặp ghép hoàn hảo, thì

(S)| (cid:0) X.

1

1'

2

2'

Không có c p ghép hoàn h o:

3

3'

S = { 2, 4, 5 }

Nhận xét. Nếu đồ thị hai phía G = (X (cid:0) | (cid:0) |S| với mọi tập con S (cid:0) CM. Hai đỉnh bất kỳ trong S gắn với hai đỉnh khác nhau trong (cid:0) (S).

(S) = { 2', 5' }.

4

4'

5

5'

(cid:0)

X

Y

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

18

Bộ môn KHMT

Định lý về các đám cưới (Marriage Theorem)

Marriage Theorem. [Frobenius 1917, Hall 1935] Giả sử G = (X (cid:0) Y, E) là đồ thị hai phía với |X| = |Y|. Khi đó, G có cặp ghép hoàn hảo khi và chỉ khi | (cid:0) |S| với mọi tập con S (cid:0) (S)| (cid:0) X.

1

1'

2

2'

3

3'

ặ Không có c p ghép hoàn  h o:ả

S = { 2, 4, 5 }

4

4'

CM. (cid:0) ) Vừa chứng minh ở trên.

(S) = { 2', 5' }.

5

5'

(cid:0)

X

Y

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

19

Bộ môn KHMT

Chứng minh định lý về các đám cưới

) Giả sử G không có cặp ghép hoàn hảo.

CM. (cid:0) (cid:0) Xét bài toán luồng cực đại tương ứng và (A, B) là lát cắt nhỏ nhất trong G'.

A.

(cid:0) Theo định lý luồng cực đại và lát cắt nhỏ nhất, cap(A, B) < | X |. B , YA = Y (cid:0) (cid:0) Gọi XA = X (cid:0)

A, XB = X (cid:0)

(cid:0)

|.

cap(A, B) = | XB

| + | YA (cid:0) Do lát cắt nhỏ nhất không sử dụng cạnh (cid:0)

: (cid:0)

(XA) (cid:0)

YA. Suy ra:

(cid:0)

|(cid:0)

|.

| + | YA

|) - | XB

| = cap(A, B) - | XB

| < | X | - | XB

| = | XA

1

(cid:0) (cid:0)

(S)| < |S| ?! ■

(XA )| (cid:0) | = (| XB | YA Chọn S = XA ta có |(cid:0)

1

G'

1'

A

2'

(cid:0) (cid:0)

XA = {2, 4, 5}

2

1

s

XB = {1, 3}

3'

1

3

YA = {2', 5'}

4

(cid:0)

t

4'

(XA) = {2', 5'}

5

1

5'

(cid:0)

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

20

Bộ môn KHMT

Ví dụ

Boys Girls

1 5

2 6

3 7

4 8

Có cách tổ chức các đám cưới?

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

21

Bộ môn KHMT

Qui về bài toán luồng cực đại

Boys Girls

1 5

1 1

2 6 1

s t 1 1 1

3 7 1 1

4 8

Tồn tại luồng cực đại với giá trị 4?

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

22

Bộ môn KHMT

Bipartite Matching: Thời gian tính

Sử dụng thuật toán luồng cực đại nào để tìm cặp ghép? (cid:0) Đường tăng luồng tuỳ ý: O(m val(f*) ) = O(mn).

(cid:0) Thang độ hoá kntq: O(m2 log C ) = O(m2).

(cid:0) Đường tăng ngắn nhất: O(m n1/2).

Cặp ghép trên đồ thị tổng quát. (cid:0) Thuật toán trổ hoa (Blossom algorithm): O(n4). [Edmonds 1965]

(cid:0) Thuật toán tốt nhất hiện biết: O(m n1/2). [Micali-Vazirani 1980]

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

23

Bộ môn KHMT

Đối ngẫu: Bài toán phủ đỉnh tối tiểu

1 1

6 6 6

2 2

7

Bài toán phủ đỉnh tối tiểu: Tìm phủ đỉnh với lực lượng nhỏ nhất

3 3

8 8 8

Phủ đỉnh là tập đỉnh C(cid:0) V sao cho mỗi cạnh của đồ thị có ít nhất một đầu mút trong C

4 4

9

5 5

10

Ví dụ: C = {2, 5, 6, 8} là một phủ đỉnh

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

24

Bộ môn KHMT

Tìm luồng cực đại

1

6

2

7

3

8

s

t

4

9

5

10

Giá trị luồng cực đại từ s đến t là 4.

Cặp ghép cực đại có lực lượng là 4.

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

25

Bộ môn KHMT

Xác định lát cắt nhỏ nhất

1 1

6 6

2

7

3 3

8 8

s s

t

4 4

9

5

10

S = {s, 1, 3, 4, 6, 8}. T = {2, 5, 7, 9, 10, t}.

Không có cung từ {1, 3, 4} đến {7, 9, 10} hoặc từ {6, 8} đến {2, 5}.

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

26

Bộ môn KHMT

Ý nghĩa của lát cắt nhỏ nhất

1 1

6 6 6

2 2

7

ss s s

t t

3 3

8 8 8

4 4

9

10

5 5 Xét tập đỉnh C = (X \ S) (cid:0)

(T\t).

Mỗi cạnh của đồ thị xuất phát G kề với một đỉnh như vậy.

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

27

Bộ môn KHMT

Đối ngẫu

1 1

6 6 6

2 2

7

3 3

8 8 8

Phủ đỉnh là tập đỉnh C(cid:0) V sao cho mỗi cạnh của đồ thị có ít nhất một đầu mút trong C

4 4

9

Tập đỉnh C = (X \ S) (cid:0) (T\ t) = { 2, 5, 6, 8 } là một phủ đỉnh

5 5

10

Lực lượng của cặp ghép cực đại là bằng lực lượng của phủ đỉnh nhỏ nhất.

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

28

Bộ môn KHMT

Độ tin cậy của mạng Network Reliability

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

29

Bộ môn KHMT

Độ tin cậy của mạng

(cid:0) Xét mạng truyền thông (Communication Network) (cid:0) Hỏi có bao nhiêu đường đi không giao nhau cạnh từ s đến t?

(cid:0) Xác định số này bằng cách nào?

Định lý. Giả sử G = (V,E) là đồ thị có hướng. Khi đó số lớn nhất các đường đi không giao nhau cạnh từ s đến t là bằng số ít nhất các cạnh cần loại bỏ khỏi G để không còn đường đi từ s đến t.

s t

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

30

Bộ môn KHMT

Có 3 đường đi không giao nhau cạnh từ s đến t

1

5

9

2

6

10

t

s

3

7

11

4

8

12

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

31

Bộ môn KHMT

Xoá 3 cạnh để tách s và t

Đặt S = {s, 3, 4, 8}. 3 cạnh cần xoá là tất cả các cạnh từ S sang T = N\S.

1

5

9

2

6

10

t

s

3

7

11

4

8

12

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

32

Bộ môn KHMT

Đường đi không giao nhau đỉnh

(cid:0) Hai đường đi từ s đến t được gọi là không giao nhau đỉnh nếu chúng có duy nhất hai đỉnh chung là s và t.

(cid:0) Bằng cách nào có thể xác định số lượng đường đi từ s đến t không giao nhau đỉnh?

Trả lời: Tách nút

Định lý. Giả sử G = (V,E) là mạng không có cung trực tiếp từ s đến t. Số lớn nhất các đường đi không giao nhau đỉnh là bằng số nhỏ nhất các đỉnh mà việc loại bỏ chúng làm gián đoạn mọi đường đi từ s đến t.

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

33

Bộ môn KHMT

Có 2 đường đi không giao nhau đỉnh từ s đến t

1

5

9

2

6

10

t

s

3

7

11

4

8

12

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

34

Bộ môn KHMT

Xoá đỉnh 5 và 6 tách t khỏi s?

Gọi S = {s, 1, 2, 3, 4, 8}

Gọi T = {7, 9, 10, 11, 12, t}

1

5

9

2

6

10

t

s

3

7

11

4

8

12

Không có cung từ S sang T.

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

35

Bộ môn KHMT

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

36

Bộ môn KHMT

Bài toán đường đi không giao nhau cạnh (Edge Disjoint Paths)

Định nghĩa. Hai đường đi được gọi là không giao nhau cạnh nếu chúng không có cạnh chung.

Bài toán đường đi không giao nhau cạnh. Cho đồ thị có hướng G = (V, E) và hai đỉnh s và t, tìm số lượng lớn nhất các đường đi từ s đến t không giao nhau cạnh.

2

5

s

t

3

6

4

7

Ví dụ: mạng truyền thông

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

37

Bộ môn KHMT

Bài toán đường đi không giao nhau cạnh (Edge Disjoint Paths)

Định nghĩa. Hai đường đi được gọi là không giao nhau cạnh nếu chúng không có cạnh chung.

Bài toán đường đi không giao nhau cạnh. Cho đồ thị có hướng G = (V, E) và hai đỉnh s và t, tìm số lượng lớn nhất các đường đi từ s đến t không giao nhau cạnh.

2

5

s

t

3

6

4

7

Ví dụ: mạng truyền thông

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

38

Bộ môn KHMT

Bài toán đường đi không giao nhau cạnh

1

1

1

1

1

1

1

1

s

t

1

1

1

1

1

1

Quy về bài toán luồng cực đại: gán cho mỗi cạnh kntq là 1.

(cid:0) Giả sử có k đường đi không giao nhau cạnh P1, . . . , Pk. (cid:0) Đặt f(e) = 1 nếu e thuộc vào ít nhất một trong số các đường đi; và

Định lý. Số lượng lớn nhất các đường đi từ s đến t không giao nhau cạnh là bằng giá trị của luồng cực đại. CM. Điều kiện cần

(cid:0) Do các đđ không có cạnh chung nên f là luồng có giá trị k. ■

f(e) = 0, nếu trái lại.

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

39

Bộ môn KHMT

Bài toán đường đi không giao nhau cạnh

Quy về bài toán luồng cực đại: gán cho mỗi cạnh kntq là 1.

1

1

1

1

1

1

1

1

s

t

1

1

1

1

1

1 Định lý. Số lượng lớn nhất các đường đi từ s đến t không giao nhau cạnh là bằng giá trị của luồng cực đại. CM. Điều kiện đủ

(cid:0)

(cid:0)

tồn tại f là luồng 0-1 với giá trị k.

(cid:0)

Giả sử luồng cực đại có giá trị k. Theo định lý về tính nguyên (cid:0) Xét cạnh (s, u) với f(s, u) = 1.

theo đk cân bằng luồng, tồn tại cạnh (u, v) với f(u, v) = 1 tiếp tục cho đến khi đạt tới t, luôn sử dụng cạnh mới

(cid:0)

Tạo được k đường đi (không nhất thiết là đơn) không giao nhau cạnh. ■

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA nếu cần, có thể cắt chu trình để thu được đường đi đơn

40

Bộ môn KHMT

Bài toán về độ liên kết của mạng (Network Connectivity)

E được gọi là tách t với s nếu mọi đường đi

ĐN. Tập cạnh F (cid:0) từ s đến t đều đi qua ít nhất một cạnh trong F.

Liên kết mạng. Cho đồ thị có hướng G = (V, E) và hai đỉnh s và t, tìm số lượng cạnh ít nhất cần loại bỏ để tách t với s.

2

5

s

t

3

6

4

7

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

41

Bộ môn KHMT

Đường đi không giao nhau cạnh và Độ liên kết mạng

Định lý. [Menger 1927] Số lớn nhất các đường đi không giao nhau cạnh từ s đến t là bằng số nhỏ nhất các cạnh cần loại bỏ để tách t với s.

E ngăn cách t từ s, và |F| = k.

CM. Điều kiện đủ (cid:0) Giả sử loại bỏ F (cid:0) (cid:0) Do mọi đường đi từ s đến t đều có ít nhất một cạnh trong F, suy ra số

2

5

2

5

s

t

3

6

s

t

3

6

4

7

4

7

lượng đường đi không giao nhau cạnh không vượt quá k. ■

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

42

Bộ môn KHMT

Đường đi không giao nhau cạnh và Độ liên kết mạng

(cid:0) Giả sử k là số lượng lớn nhất các đường đi không giao nhau cạnh.

Định lý. [Menger 1927] Số lớn nhất các đường đi không giao nhau cạnh từ s đến t là bằng số nhỏ nhất các cạnh cần loại bỏ để tách t với s. CM. Điều kiện cần

(cid:0) Khi đó giá trị luồng cực đại là k. (cid:0) Từ định lý Max-flow min-cut (cid:0) (cid:0) Gọi F là tập các cạnh từ A sang B.

lát cắt nhỏ nhất (A, B) có kntq k.

2

5

2

5

A

s

t

3

6

s

3

6

t

4

7

4

7

(cid:0) |F| = k và F tách t với s. ■

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

43

Bộ môn KHMT

Bài toán giao hàng

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

44

Bộ môn KHMT

Bài toán giao hàng

kho hàng đại lý bán lẻ

6 1

6 5 6 2

7 7 4 3

8 6 5 4

9 5 4 5

Có cách chuyển hàng từ các kho đáp ứng yêu cầu của các đại lý bán lẻ?

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

45

Bộ môn KHMT

Quy về bài toán luồng cực đại

kho hàng đại lý bán lẻ

6 1

6

6 5 6 6 2 5 tổng yêu cầu của các đại lý là 24

7 7 7 4 4 3

s

t 5

8 6 6 5 4 4

9 5 5 4 5

Tồn tại tương ứng 1-1 giữa luồng từ s đến t với giá trị 24 với một cách chuyển hàng đáp ứng yêu cầu của các đại lý bán lẻ.

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

46

Bộ môn KHMT

Bài toán lập lịch

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

47

Bộ môn KHMT

Bài toán

(cid:0) Có n chi tiết (job) cần được gia công. (cid:0) Có M máy (giống hệt nhau) để thực hiện việc gia công. (cid:0) Đối với chi tiết j biết:

(cid:0)

(cid:0)

(cid:0) tj - thời gian hoàn thành rj - thời điểm sẵn sàng dj - thời hạn hoàn thành

(cid:0)

(cid:0) Tìm cách bố trí việc thực hiện gia công n chi tiết trên M máy: Mỗi chi tiết j được bắt đầu gia công ở thời điểm không sớm hơn rj

(cid:0) Thời điểm hoàn thành việc gia công chi tiết j không muộn hơn dj (cid:0) Tại mỗi thời điểm có không quá 1 máy thực hiện việc gia công chi tiết j và tổng thời gian thực hiện gia công chi tiết j trên M máy là bằng tj

(cid:0) Cách bố trí thoả mãn các điều kiện vừa nêu gọi là lịch

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

48

Bộ môn KHMT

Lập lịch trên các máy song song

Job ( j )

1

3

4

2

1.5

4.5

5

3

Thời gian hoàn thành ( tj )

2

2

4

0

Thời điểm sẵn sàng ( rj )

5

7

9

4

Thời hạn ( dj )

Giả sử có M = 2 máy song song

4

2

1

3

Không có lịch ngoại trừ khi cho phép ngắt quãng

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

49

Bộ môn KHMT

Lập lịch trên các máy song song

Job ( j )

1

2

3

4

1.5

3

4.5

5

Thời gian hoàn thành ( tj )

2

0

2

4

Thời điểm sẵn sàng ( rj )

5

4

7

9

Thời hạn ( dj )

Giả sử có M = 2 máy song song

2

1

4

3

4

3

Có lịch nếu cho phép ngắt quãng

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

50

Bộ môn KHMT

Qui về bài toán luồng cực đại

jobs

0-2

cung đỏ: thời lượng gia công job j trong khoảng thời gian t nhiều nhất là t.

2

1 4

1.5 2-4 4 2 3

cung xanh lá cây: thời lượng của khoảng thời gian t nhiều nhất là M(cid:0) t. (M là số máy có thể dùng)

2 s 4.5 1 t 4-5 3 5 4

4 4 5-7

2

7-9

cung xanh da trời: tổng thời lượng dành cho gia công job j trong mọi khoảng là pj.

khoảng thời gian

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

51

Bộ môn KHMT

Luồng cực đại – Lịch

0-2

Cần phân rã luồng để đưa ra lịch

1

Lịch tồn tại (cid:0) tìm được luồng bão hoà mọi cung ra khỏi s

1 .5 4,2

1.5 2-4 2 1 4,4 2 3

2 s 4.5 2,2 .5 t 4-5 3 5 4,4

4 4,2 5-7 2 1 2 2

7-9

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

52

Bộ môn KHMT

Questions?

Toán rời rạc – Fall 2005 NGUYỄN ĐỨC NGHĨA

53

Bộ môn KHMT