Chương III BÀI TOÁN VẬN TẢI pot

Chương III

BÀI TOÁN VẬN TẢI

§1. ĐỊNH NGHĨA VÀ MỘT SỐ TÍNH

CHẤT

1.Định nghĩa 1:

Trong §1, chương 1 ta đã giới thiệu về

bài toán vận tải. Dạng tổng quát có thể định

nghĩa như sau:

( )

( )

1 1

1

1

min (1)

1, (2)

1, (3)

0 (4)

m n

ij ij

i j

n

ij i

j

m

ij j

i

ij

f c x

x a i m

x b j n

x

= =

=

=

= →

= =

= =

≥

∑∑

∑

∑

Đây chính là bài toán Quy hoạch tuyến tính

dạng chính tắc ẩn và m+n ràng

buộc.

m n × ij x

3. Định lý 2: Điều kiện cân bằng thu phát

là điều kiện cần và đủ để bài toán vận tải có

tập phương án khác rỗng.

Hơn nữa, nếu bài toán vận tải có điều

kiện cân bằng thu phát thì có phương án tối

ưu.

1 1

m n

i j

i j

a b

= =

∑ ∑=

Tổng lượng hàng thu bằng tổng lượng

hàng phát.

Ví dụ: Xét lại bài toán vận tải đã biết ở

chương 1.

11 12 13 21 22 23

11 12 13

21 22 23

11 21

12 22

13 23

5 2 3 2 min

30

75

35

25

45

0, , ij

f x x x x x x

x x x

x x x

x x

x x

x x

x i j

= + + + + + →

 + + =



+ + = 

 + =



+ = 

 + = 

 ≥ ∀ 

Đây là bài toán vận tải cân bằng thu phát.