XSTK

Ai (i =1,…m): các trạm phát

Bj (j = 1,…n): các trạm thu

ai: lượng rác có ở trạm phát Ai

bj: lượng rác yêu cầu ở trạm thu Bj

cij: chi phí vận chuyển một đơn vị rác từ trạm phát Ai (i = 1,.,m) đến trạm thu Bj (j = 1, 2,..., n) (cij > 0)

xij: lượng rác vận chuyển từ trạm phát Ai đến trạm thu Bj , xij ≥ 0 (với mọi i, j)

Bài toán:

Ta có :

3 khu vực A1, A2, A3 (phát) với lượng rác thải ra là (80, 55, 45) (tấn)

4 nhà máy xử lý rác B1, B2, B3, B4 (thu) là (40, 30, 60, 50) (tấn)

Cước phí vận chuyển rác từ khu vực Ai đến nhà máy Bj là cij (triệu/tấn .ngày)

Lượng rác vận chuyển từ trạm Ai đến đường Bj là xij

Tổng chi phí vận chuyển hết lượng rác từ các khu vực đến các nhà máy là Z

=> Tính cước phí vận chuyển là thấp nhất?

Ta viết lại bảng như sau:

Bước 2: Xác định hệ số thế vị

+Tính các giá trị ui+Vj=Cij

Bước 3: Kiểm tra điều kiện

+Tìm phương án tối ưu

Bước 1 : Tìm điểm xuất phát

+Tính cước phí vận chuyển thấp nhất

Bước 1: Tìm điểm xuất phát theo phương pháp cước phí bé nhất

Số ô được chọn = m + n - 1 = 4 +3 – 1= 6 (thỏa)

Bước 2: Xác định hệ số thế vị theo phương trình: ui +vj=cij

Tính đại lượng ∆ịj = vj + ui – cij

q(min)={các ô chẳn}

chẳn trừ, lẻ cộng

q(min)={30,10} = 10

Z=

0 20 60 0

40 10 0 5

0 0 0 45

Zmin = (4*40+20*1+5*10+2*60+7*5+2*45) = 475triệu

Zchưa tối ưu hóa= (4*40+1*30+9*10+2*50+7*5+2*45) = 505triệu

Tiết kiệm chi phí trong 1 năm: (505triệu – 475triệu)*365 =10,950tỷ

THANKS FOR LISTENING !!!