ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC VŨ THU HUỆ BÀI TOÁN VẬN TẢI DẠNG CHI PHÍ NÚT THẮT VỚI NHIỀU MỤC TIÊU LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên - 2015
i
Mục lục
Danh sách ký hiệu iii
Danh sách bảng iv
Mở đầu 1
1 Bài toán vận tải theo mục tiêu cước phí 4
1.1 Nội dung bài toán và tính chất . . . . . . . . . . . . . . . . . . . 4
1.2 Phương án cực biên ban đầu . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Phương pháp min cước. . . . . . . . . . . . . . . . . . . 7
1.2.2 Phương pháp góc tây bắc. . . . . . . . . . . . . . . . . . 8
1.3 Điều kiện tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4 Thuật toán thế vị . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Bài toán vận tải với hai mục tiêu 14
2.1 Bài toán vận tải theo mục tiêu thời gian . . . . . . . . . . . . . . 14
2.1.1 Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . 14
2.1.2 Thuật toán chắn (Blocking Method). . . . . . . . . . . . 16
2.2 Bài toán vận tải với hai mục tiêu . . . . . . . . . . . . . . . . . . 19
2.2.1 Mô tả bài toán . . . . . . . . . . . . . . . . . . . . . . . 19
2.2.2 Tìm các nghiệm cơ sở hữu hiệu của (MP) . . . . . . . . . 20
ii
3 Bài toán vận tải với ba mục tiêu 25
3.1 Nội dung bài toán . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Tìm tập nghiệm cơ sở hữu hiệu . . . . . . . . . . . . . . . . . . 29
3.3 Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . . . 31
Kết luận 36
Tài liệu tham khảo 37
iii
Danh sách ký hiệu
Trong luận văn này ta dùng những ký hiệu với các ý nghĩa xác định trong bảng
x ∈ D x thuộc tập D
x (cid:54)∈ D x không thuộc tập D
|G(X)|
dưới đây:
∪
số phần tử của tập G
+∞
phép hợp các tập hợp
dương vô cùng
∆ij
(cid:80) hàm tổng
τ
được gọi là ước lượng của biến xij
L
chỉ thời hạn về thời gian
danh sách ghi nghiệm hữu hiệu tìm được
iv
Danh sách bảng
Bảng 1.1. Bảng vận tải T
Bảng 2.1. Dữ liệu bài toán trong ví dụ 2.2
Bảng 2.2. Bảng vận tải theo mục tiêu thời gian
Bảng 2.3. Bảng vận tải theo mục tiêu cước phí
Bảng 2.4. Bảng vận tải theo mục tiêu cước phí với τ = 73
Bảng 2.5. Bảng vận tải theo mục tiêu cước phí với τ = 68
Bảng 2.6. Bảng vận tải theo mục tiêu cước phí với τ = 66
Bảng 2.7. Các nghiệm cơ sở hữu hiệu của bài toán vận tải hai mục tiêu
Bảng 3.1. Bảng vận tải theo mục tiêu cước phí với τ = 63
Bảng 3.2. Nghiệm cơ sở hữu hiệu S2 kề S1
Bảng 3.3. Bảng vận tải theo mục tiêu cước phí với τ = 66
Bảng 3.4. Tập nghiệm cơ sở hữu hiệu của bài toán trong Ví dụ 3.1
1
Mở đầu
Bài toán vận tải theo mục tiêu cước phí (Cost Transportation Problem) là bài . toán cổ điển, quen thuộc trong lý thuyết tối ưu và trong các ứng dụng. Đó là bài
toán tìm phương án vận chuyển hàng từ các nơi cung cấp (gọi là điểm phát) đến
các nơi tiêu thụ (gọi là điểm thu) sao cho tổng chi phí vận chuyển là nhỏ nhất. Bài
toán này đã được nghiên cứu khá chi tiết và đầy đủ, cả về lý thuyết lẫn phương
pháp giải.
Bài toán vận tải theo mục tiêu thời gian hay còn gọi bài toán vận tải dạng nút
thắt (Bottleneck Transportation Problem) là một dạng khác của bài toán vận tải,
trong đó có tính đến thời gian đi trên các tuyến đường có vận chuyển hàng. Thay
vì tìm cực tiểu tổng chi phí, mục tiêu bây giờ là hoàn thành vận chuyển hàng trong
thời gian sớm nhất có thể. Trong bài toán này hàm mục tiêu là phi tuyến. Nhiều
dạng khác nhau của bài toán vận tải theo mục tiêu thời gian đã được đặt ra và
nhiều thuật toán giải đã được đề xuất.
Trong các ứng dụng thực tiễn, để đánh giá hiệu quả hoạt động kinh tế vận tải
và đề ra các quyết định quản lý có căn cứ khoa học, người ta còn gặp các mô hình
bài toán vận tải với hai hay nhiều hàm mục tiêu. Chẳng hạn, bài toán vận tải cực
tiểu cả chi phí lẫn thời gian vận chuyển, gọi là bài toán vận tải dạng chi phí - nút
thắt (Bottleneck - Cost Transportation Problem) và bài toán vận tải dạng nút thắt
với nhiều mục tiêu, trong đó có hàm mục tiêu phân thức. Đã có một số phương
pháp sử dụng cấu trúc đặc thù của bài toán trong tìm nghiệm hữu hiệu của bài toán
vận tải hai hay nhiều mục tiêu.
2
Sau khi được học về Giải tích lồi và các kiến thức toán học có liên quan, với
mong muốn tìm hiểu sâu hơn về những kiến thức đã học, các kiến thức mở rộng
và ứng dụng của những kiến thức này, chúng tôi chọn đề tài luận văn
"Bài toán vận tải dạng chi phí - nút thắt với nhiều mục tiêu"
Luận văn có mục đích tìm hiểu và trình bày một số mô hình bài toán vận tải
nhiều hàm mục tiêu và các thuật toán tìm nghiệm hữu hiệu của bài toán.
Luận văn được viết thành ba chương.
Chương 1 "Bài toán vận tải theo mục tiêu cước phí" trình bày những kiến
thức cơ bản về bài toán vận tải theo mục tiêu cước phí: nội dung và tính chất
nghiệm của bài toán, điều kiện tối ưu và thuật toán thế vị giải bài toán.
Chương 2 "Bài toán vận tải với hai mục tiêu" đề cập tới bài toán vận tải theo
mục tiêu thời gian và bài toán vận tải với hai mục tiêu: cực tiểu cả cước phí lẫn
thời gian vận chuyển và trình bày các thuật toán giải, nhờ đưa về các bài toán vận
tải theo mục tiêu cước phí. Ý tưởng chính của các thuật toán là sử dụng phương
pháp chắn: cấm vận chuyển hàng trên các tuyến có thời gian vượt quá một mức
nào đó và sau đó mở rộng dần các mức thời gian này.
Chương 3 "Bài toán vận tải với ba mục tiêu" trình bày mô hình bài toán vận
tải ba mục tiêu dạng nút thắt, trong đó hai mục tiêu đầu là tỉ số giữa cước phí vận
chuyển và thiệt hại do vận chuyển với thời gian vận chuyển. Bài toán này được
đưa về dạng bài toán ba mục tiêu đơn giản hơn và có thể giải bằng thuật toán tìm
nghiệm cơ sở hữu hiệu của một số bài toán vận tải hai mục tiêu.
Do thời gian và kiến thức còn hạn chế nên chắc chắn luận văn này còn có
những thiếu sót nhất định, kính mong quí thầy cô và các bạn đóng góp ý kiến để
tác giả tiếp tục hoàn thiện luận văn sau này.
Nhân dịp này tác giả luận văn xin bày tỏ lòng biết ơn sâu sắc tới GS. TS. Trần
Vũ Thiệu, người đã tận tình giúp đỡ trong suốt quá trình làm luận văn. Tác giả trân
3
trọng cảm ơn các giảng viên Trường Đại học Khoa học – Đại học Thái Nguyên,
Viện Toán học – Viện Hàn lâm Khoa học và Công nghệ Việt Nam tạo mọi điều
kiện thuận lợi trong quá trình tác giả học tập và nghiên cứu.
Thái Nguyên, tháng 05 năm 2015
Tác giả
Vũ Thu Huệ
4
Chương 1
Bài toán vận tải theo mục tiêu cước phí
Chương này trình bày vắn tắt bài toán vận tải theo mục tiêu cước phí, điều kiện
tối ưu và thuật toán thế vị giải bài toán. Cuối chương, nêu ví dụ số minh họa thuật
toán giải. Nội dung của chương cần cho các chương ở sau và được tham khảo chủ
yếu từ các tài liệu [1], [2] và [3].
1.1 Nội dung bài toán và tính chất
Bài toán vận tải theo mục tiêu cước phí có nội dung như sau: Giả sử có m kho
i = 1, . . . , m có ai > 0 đơn vị hàng (lượng cung). Cần vận chuyển số hàng này
chứa một loại hàng (xi măng chẳng hạn) K1, . . . , Km (gọi là các điểm phát), kho
tới n hộ tiêu thụ H1, . . . , Hn (gọi là các điểm thu), hộ j = 1, . . . , n cần bj > 0
đơn vị hàng (lượng cầu). Cước phí vận chuyển một đơn vị hàng từ điểm phát Ki
tới điểm thu Hj là cij ≥ 0. Vấn đề đặt ra là cần vận chuyển từ mỗi điểm phát tới
mỗi điểm thu bao nhiêu đơn vị hàng sao cho thỏa mãn nhu cầu của mọi điểm thu
và tổng chi phí vận chuyển toàn bộ số hàng là nhỏ nhất?
Ký hiệu xij là lượng hàng cần vận chuyển từ điểm phát i tới điểm thu j. Khi
m (cid:88)
n (cid:88)
f (x) =
(1.1)
cijxij → min (cực tiểu tổng chi phí vận chuyển)
i=1
j=1
đó, mô hình toán học của bài toán vận tải theo mục tiêu cước phí có dạng:
5
n (cid:88)
(1.2)
xij = ai, i = 1, . . . , m (mọi điểm phát giao hết hàng),
j=1
m (cid:88)
(1.3)
xij = bj, j = 1, . . . , n (mọi điểm thu nhận đủ hàng),
i=1
xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n (lượng hàng vận chuyển không âm).
(1.4)
với các điều kiện
Điều kiện cần và đủ để bài toán (1.1) - (1.4) giải được là phải có điều kiện cân
(1.5)
a1 + a2 + · · · + am = b1 + b2 + · · · + bn.
bằng cung cầu (nghĩa là tổng cung bằng tổng cầu):
A tương ứng với biến xij. Dễ thấy rằng véctơ này có hai thành phần bằng + 1 (ở
Ký hiệu A là ma trận hệ số ở vế trái ràng buộc (1.2), (1.3), Aij là véctơ cột của
hàng thứ i và hàng thứ m + j), còn mọi thành phần khác bằng 0.
Định nghĩa 1.1. Ma trận X = {xij}m×n gọi là một phương án của bài toán
vận tải. Phương án đạt cực tiểu của (1.1) gọi là phương án tối ưu hay lời giải của
bài toán. Phương án X là phương án cực biên khi và chỉ khi các véctơ cột Aij của A
tương ứng với biến xij > 0 là độc lập tuyến tính (hay tập hợp ô {(i, j) : xij > 0}
không chứa chu trình).
Một phương án cực biên X = {xij}m×n của bài toán gọi là không suy biến
nếu số phần tử của tập hợp G(X) = {(i, j) : xij > 0} bằng m + n − 1, gọi là suy
biến nếu |G(X)| < m + n − 1.
Với điều kiện (1.5) bài toán (1.1) - (1.4) có các tính chất sau:
1. Tập hợp các phương án của bài toán khác rỗng và bị chặn (giới nội).
2. Hạng của hệ ràng buộc (1.2) - (1.3) bằng m + n − 1.
3. Nếu lượng cung ai và lượng cầu bj là các số nguyên thì bài toán sẽ có lời
giải nguyên (mọi biến xij có giá trị nguyên).
6
Ta ghi lại dữ liệu của bài toán dưới dạng một bảng chữ nhật, gọi là bảng vận tải
(Bảng 1.1). Không kể hàng và cột tiêu đề, bảng bao gồm m hàng (i = 1, . . . , m)
và n cột (j = 1, . . . , n). Chỗ giao nhau ở hàng i cột j gọi là ô (i, j). Mỗi hàng
tương ứng với một điểm phát, mỗi cột tương ứng với một điểm thu. Số ghi ở đầu
mỗi hàng là lượng cung, số ghi ở đầu mỗi cột là lượng cầu. Chi phí vận chuyển cij
ghi ở góc trên bên trái của ô (i, j), lượng hàng vận chuyển xij sẽ ghi ở góc dưới
bên phải của ô (i, j). Ô (i, j) biểu thị tuyến đường vận chuyển từ điểm phát i tới
điểm thu j.
(i1, j1), (i1, j2), (i2, j2), (i2, j3), . . . , (is, js), (is, js+1) hoặc
(i1, j1), (i2, j1), (i2, j2), (i3, j2), . . . , (is, js), (is+1, js).
Định nghĩa 1.2. Ta gọi dây chuyền là một tập hợp các ô có dạng
Một dây chuyền khép kín (js+1 = j1 hoặc is+1 = i1) gọi là một chu trình.
Như vậy, mỗi cặp ô liền nhau trên dây chuyền ở trên cùng một hàng hay trên
cùng một cột và số ô trên dây chuyền có thể là chẵn hay lẻ. Một chu trình bao giờ
cũng gồm một số chẵn các ô.
Ta có mối liên hệ đáng chú ý sau.
7
Định lý 1.1. Hệ véctơ Aij của bài toán vận tải là độc lập tuyến tính khi và chỉ
khi các ô tương ứng với các véctơ này không chứa chu trình.
Hệ quả 1.1. Ma trận X = (xij)m×n là phương án cực biên của bài toán vận
tải khi và chỉ khi tập hợp ô (i, j) mà xij > 0 không chứa chu trình.
Định lý 1.2. Giả sử G là một tập hợp gồm m + n − 1 ô của bảng vận tải không
chứa chu trình. Khi đó, một ô (r, s) (cid:54)∈ G sẽ tạo với các ô thuộc G một chu trình
duy nhất.
1.2 Phương án cực biên ban đầu
Sau đây là hai phương pháp thông dụng và thuận tiện nhất.
1.2.1 Phương pháp min cước.
Trong bảng vận tải, ta chọn ô (p, q) sao cho cpq = min {cij : ∀ (i, j) ∈ T }.
Nếu cực tiểu đạt tại nhiều ô thì ta chọn ô bất kỳ trong số các ô đó. Sau đó phân
xpq = min {ap, bq}.
phối hàng nhiều nhất có thể theo tuyến p → q, nghĩa là đặt
Trừ lượng hàng vừa phân phối vào lượng phát, thu của hàng p và cột q. Tiếp
đó, ta "xóa" (tức không xét tới nữa) hàng p nếu điểm phát p đã giao hết hàng hoặc
cột q nếu điểm thu q đã nhận đủ hàng. Khi cả hàng, cột đều hết và đủ hàng thì
chỉ xóa hàng hoặc cột, không xóa cả hai. Trong bảng vận tải còn lại (bớt một hàng
hoặc một cột), ta lại chọn ô có cước phí nhỏ nhất và phân phối tối đa lượng hàng
m + n − 1 ô đã được phân hàng (gọi là ô chọn), nó là một phương án cực biên vì
còn lại vào ô này (lượng hàng này có thể bằng 0). Phương án X thu được có đúng
các ô đã chọn không tạo thành chu trình.
8
1.2.2 Phương pháp góc tây bắc.
Khác với phương pháp min cước, các ô nằm ở góc tây bắc của bảng vận tải
được ưu tiên chọn trước để phân phối hàng, bắt đầu từ ô (p, q) = (1, 1). Phân vào
x11 = min {a1, b1}.
ô này lượng hàng tối đa
• a1 ≤ b1 (điểm phát 1 hết hàng, điểm thu 1 còn cần b1 − a1 đơn vị hàng).
Có hai khả năng xảy ra:
"Xoá" hàng 1 của bảng T. Trong bảng gồm m − 1 hàng còn lại, ta lại chọn ô nằm
• a1 > b1 (điểm phát 1 còn a1 − b1 đơn vị hàng, điểm thu 1 đủ hàng). "Xoá"
ở góc tây bắc, cụ thể là ô (2, 1) của bảng T để tiếp tục phân phối hàng.
cột 1 của bảng T. Trong bảng gồm n − 1 cột còn lại, ta lại chọn ô nằm ở góc tây
bắc, cụ thể là ô (1, 2) của bảng T để tiếp tục phân phối hàng.
Cứ phân phối hàng như vậy cho đến khi mọi hàng (cột) đã phát hết (nhận đủ)
hàng. Khi đó, ta sẽ nhận được một phương án cực biên gồm m + n − 1 ô được
phân hàng (gọi là ô chọn), không tạo thành chu trình.
1.3 Điều kiện tối ưu
m (cid:88)
n (cid:88)
g(u, v) =
(1.6)
aiui +
bjvj → max
i=1
j=1
Đối ngẫu của bài toán vận tải (1.1) - (1.4) là bài toán
(1.7)
ui + vj ≤ cij, i = 1, . . . , m, j = 1, . . . , n.
với các điều kiện
ij} là một phương án cực biên không suy biến. Ký hiệu
G0 = {(i, j) : x0
ij > 0}. Sau đây là điều kiện để cho X 0 là phương án tối ưu.
Giả sử X 0 = {x0
9
ij} của bài toán
Định lý 1.3. Phương án cực biên không suy biến X 0 = {x0
vận tải (1.1) - (1.4) với điều kiện (1.5) là một phương án tối ưu khi và chỉ khi tìm
(1.8)
được các số ui (i = 1, . . . , m) và vj (j = 1, . . . , n) thỏa mãn:
(1.9)
ui + vj = cij, ∀(i, j) ∈ G0.
(cid:40) ui + vj ≤ cij, ∀(i, j) ∈ T,
Do hệ véctơ {Aij : (i, j) ∈ G0} độc lập tuyến tính nên mỗi phương án cực
ui (i = 1, . . . , m) và vj (j = 1, . . . , n) (xác định sai khác một hằng số khác 0)
biên không suy biến X 0 của bài toán (1.1) - (1.4) sẽ tương ứng với một bộ số
∆ij = ui + vj − cij được gọi là ước lượng của biến xij. Theo Định lý 1.3, phương
thỏa mãn (1.9). Ta gọi các số ui và vj này là các thế vị hàng và thế vị cột. Các số
∆ij ≤ 0, ∀ (i, j).
án X 0 là tối ưu khi và chỉ khi các thế vị này thỏa mãn thêm điều kiện (1.8), tức là
Định lý sau đây khẳng định có tồn tại phương án cực biên mới tốt hơn, nếu các
thế vị xác định theo (1.9) không thỏa mãn (1.8).
ij} là pương án cực biên không suy biến của
Định lý 1.4. Giả sử X 0 = {x0
bài toán vận tải và ui (i = 1, . . . , m) và vj (j = 1, . . . , n) là các thế vị tương
ứng với X 0. Nếu có ô (r, s) ∈ G0 sao cho ∆rs > 0 thì X 0 không phải là phương
f (X 1) < f (X 0).
án tối ưu và có thể tìm được phương án cực biên mới X 1 tốt hơn X 0 theo nghĩa
1.4 Thuật toán thế vị
Bước 0. Dùng phương pháp min cước (hay phương pháp góc tây bắc) tìm
ij} với tập ô chọn G0 gồm đúng m + n − 1
phương án cực biên ban đầu X 0 = {x0
ij > 0}. Đặt chỉ số vòng lặp k = 1.
ô không chứa chu trình và G0 = {(i, j) : x0
Bước 1. Xác định các thế vị ui (i = 1, . . . , m) và vj (j = 1, . . . , n) tương ứng
10
u1 = 0, ui + vj = cij, ∀ (i, j) ∈ Gk−1.
với X k−1 bằng cách giải hệ phương trình dạng tam giác (1.9):
(Để ý là ta luôn có ∆ij = ui + vj − cij = 0, ∀ (i, j) ∈ Gk−1).
Bước 2. Tính các ước lượng ∆ij = ui + vj − cij, ∀ (i, j) ∈ Gk−1.
Bước 3. Kiểm tra tối ưu: Nếu ∆ij ≤ 0, ∀ (i, j) (cid:54)∈ Gk−1 thì dừng thuật toán.
Khi đó, X k−1 là phương án tối ưu (Định lý 1.3). Trái lại, chuyển sang Bước 4.
Bước 4. Điều chỉnh phương án:
∆rs = max {∆ij > 0 : (i, j) ∈ Gk−1}.
4a) Xác định ô điều chỉnh (r, s) với
4b) Tìm chu trình duy nhất K trong Gk−1 ∪ {(r, s)}.
4c) Chia các ô thuộc K thành ô lẻ K1, ô chẵn K2 với qui ước (r, s) ∈ K1.
: (i, j) ∈ K2} = xk−1
pq
ij 4e) Xây dựng phương án cực biên mới X k với
,
. 4d) Xác định lượng điều chỉnh h = min {xk−1
X k
ij =
khi (i, j) (cid:54)∈ K,
khi (i, j) ∈ K1,
khi (i, j) ∈ K2. (cid:40) xk−1 ij xk−1 ij + h, xk−1 ij − h,
Ta có Gk = Gk−1\{(p, q)} ∪ {(r, s)} và Gk không chứa chu trình, tức X k là
phương án cực biên.
4f) Tăng k ← k + 1, quay lại Bước 1 để thực hiện vòng lặp k mới.
Định lý 1.5. Nếu bài toán vận tải không suy biến thì thuật toán thế vị là hữu
hạn, tức là sau hữu hạn bước ta sẽ nhận được phương án tối ưu.
Chú ý 1.1. Có hai dấu hiệu giúp nhận biết phương án cực biên suy biến:
11
(i) Lượng điều chỉnh h = 0 (Bước 4d). Khi đó ta vẫn thực hiện thuật toán một
cách bình thường, nghĩa là ô điều chỉnh (r, s) sẽ trở thành ô chọn của phương án
rs = 0, còn ô (p, q) ∈ K2 ứng với X k−1
pq = 0 sẽ trở thành ô loại đối với phương án X k. Tuy nhiên, kết quả điều chỉnh không làm thay đổi
cực biên mới X k và X k
phương án cực biên (X k−1 = X k) mà chỉ làm thay đổi tập véctơ cơ sở của phương
án đó.
(ii) Lượng điều chỉnh h đạt tại nhiều ô khác nhau thuộc K2. Khi đó ta sẽ loại
một trong những ô này theo qui tắc ngẫu nhiên.
1.5 Ví dụ minh họa
Ví dụ 1.1. Áp dụng thuật toán thế vị giải bài toán vận tải theo mục tiêu cước
phí với véctơ cung a, véctơ cầu b và ma trận cước phí C như sau:
a = (10 12 8), b = (5 6 4 15),
13 12 14 10
0 0 0 10
C =
, X 0 =
.
13 15 12 14
5 2 0 5
14 9
7 10
0 4 4 0
Ví dụ này có m = 3 điểm phát, n = 4 điểm thu và thỏa mãn điều kiện cân
bằng cung cầu (1.5). Phương án cực biên ban đầu X 0 được tìm theo phương pháp
6 = m + n − 1 ô không chứa chu trình và giá trị mục tiêu f (X 0) = 329.
min cước có tập ô chọn G0 = {(1, 4), (2, 1), (2, 2), (2, 4), (3, 2), (3, 3)}, gồm
Vòng lặp 1.
u0 = (0 4 − 2), v0 = (9 11 9 10).
Bước 1. Các thế vị tương ứng với X 0:
12
Bước 2. Các ước lượng ∆ij = ui + vj − cij ghi trong ma trận ∆0 dưới đây.
−4 −1 −5
0
∆0 =
.
0
0
1
0
−7
0
0 −2
Bước 3. Phương án X 0 chưa tối ưu vì còn ∆23 = 1 > 0 và (2, 3) (cid:54)∈ G0.
Bước 4. Điều chỉnh phương án:
∆23 = max {∆ij > 0 : (i, j) (cid:54)∈ G0} = 1 > 0.
4a) Ô điều chỉnh (r, s) = (2, 3) vì
4b) Chu trình điều chỉnh K gồm 4 ô (2, 3), (3, 3), (3, 2), (2, 2).
4c) Các ô lẻ K1 = {(2, 3), (3, 2)} và các ô chẵn K2 = {(3, 3), (2, 2)}.
22 = 2.
22 = 2} = x0
33 = 4, x0
4d) Lượng điều chỉnh h = min {x0
Ô điều chỉnh (p, q) = (2, 2).
4e) Phương án cực biên mới:
0 0 0 10
X 1 =
.
5 0 2 5
0 6 2 0
tương ứng với tập ô chọn G1 = {(1, 4), (2, 1), (2, 3), (2, 4), (3, 2), (3, 3)}, gồm
f (X 1) = 327 < f (X 0) = 329.
6 ô không chứa chu trình và giá trị mục tiêu
Vòng lặp 2.
u1 = (0 4 − 1), v1 = (9 10 8 10).
Bước 1. Các thế vị tương ứng với X 1:
13
Bước 2. Các ước lượng ∆ij = ui + vj − cij ghi trong ma trận ∆1 dưới đây.
−4 −2 −6
0
∆1 =
.
0 −1
0
0
−6
0
0 −1
fmin = 327. Kết thúc thuật toán giải.
Bước 3. Phương án X 1 là tối ưu vì ∆1 ≤ 0. Cước phí vận chuyển nhỏ nhất
Tóm lại, chương này đã đề cập tới bài toán vận tải theo mục tiêu cước phí, trình
bày điều kiện tối ưu và thuật toán thế vị giải bài toán. Thuật toán thế vị nhắc lại
ở chương này sẽ được sử dụng ở các chương sau để giải bài toán vận tải theo mục
tiêu thời gian và các bài toán vận tải với hai hay ba mục tiêu.
14
Chương 2
Bài toán vận tải với hai mục tiêu
Chương này đề cập tới bài toán vận tải theo mục tiêu thời gian và bài toán vận
tải với hai mục tiêu: cực tiểu chi phí lẫn thời gian vận chuyển. Trình bày các thuật
toán giải và nêu các ví dụ minh họa thuật toán. Nội dung của chương được xây
dựng dựa trên các tài liệu tham khảo [4], [5] và [6].
2.1 Bài toán vận tải theo mục tiêu thời gian
2.1.1 Phát biểu bài toán
Trong việc lập kế hoạch vận tải, yếu tố thời gian đôi khi cũng cần được tính
đến. Chẳng hạn, khi cần vận chuyển nhanh chóng một mặt hàng nào đó (hoa quả,
rau tươi, thịt cá ...) từ nơi sản xuất đến nơi tiêu thụ hay khi cần tiếp tế gấp lương
thực, vũ khí, đạn dược ... từ hậu phương ra tiền tuyến thì mục tiêu cực tiểu thời
gian vận chuyển thường được đặt lên hàng đầu.
(P )
(2.1)
tX = max
{tij : xij > 0} → min
i,j
Mục này xét mô hình bài toán vận tải theo mục tiêu thời gian như sau:
n (cid:88)
(2.2)
xij = ai, i = 1, . . . , m,
j=1
m (cid:88)
(2.3)
xij = bj, j = 1, . . . , n,
i=1
(2.4)
xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n.
với các điều kiện
15
trong đó m là số điểm phát, n là số điểm thu, xij là lượg hàng cần chuyển từ điểm
phát i tới điểm thu j, tij là thời gian đi từ điểm phát i tới điểm thu j, ai là lượng
cung của điểm phát i và bj là lượng cầu của điểm thu j.
m (cid:88)
n (cid:88)
(2.5)
ai =
bj.
i=1
j=1
Ta giả thiết (P) thỏa mãn điều kiện cân bằng cung cầu:
Một số tác giả nước ngoài gọi mô hình (2.1) - (2.5) là bài toán vận tải dạng
nút thắt (Bottleneck Transportation Problem - viết tắt là BTP).
Cũng như trong bài toán vận tải theo mục tiêu cước phí xét ở chương 1, hệ
thống số {xij}m×n thỏa mãn (2.2) - (2.4) được gọi là một phương án của (P ).
Phương án đạt cực tiểu của (2.1) được gọi là một phương án tối ưu của (P ).
Trong bài toán vận tải theo mục tiêu thời gian, ma trận thời gian T = [tij]m×n
được cho trước. Thời gian vận chuyển của mỗi phương án X = {xij}m×n được
hiểu theo nghĩa như sau.
Định nghĩa 2.1. Thời gian vận chuyển tX của phương án X là giá trị lớn nhất
của các số tij trên các tuyến (i, j) có vận chuyển hàng, tức xij > 0 (không phụ
thuộc độ lớn xij), nghĩa là thời gian của tuyến đường (từ một điểm phát tới một
điểm thu) dài nhất mà trên tuyến đường đó có vận chuyển hàng.
Dễ dàng kiểm tra tính đúng đắn của nhận xét sau.
Bổ đề 2.1. Thời gian vận chuyển tối thiểu của mọi phương án X là số tmin xác
(2.6)
tij},
tmin = max { max 1≤i≤m
min 1≤j≤n
tij, max 1≤j≤n
min 1≤i≤m
định bởi
(tức tmin bằng số lớn nhất trong các số nhỏ nhất ở mỗi hàng và mỗi cột của T).
16
2.1.2 Thuật toán chắn (Blocking Method).
Thuật toán đơn giản sau cho phép đưa bài toán vận tải theo mục tiêu thời gian
về một dãy bài toán vận tải theo mục tiêu cước phí. Thuật toán bao gồm:
[t1, tmax] với t1 = tmin (xem (2.6)), tq = tmax = max {tij : i = 1, . . . , m, j =
1, . . . , n}. Đặt chỉ số vòng lặp k = 1.
Bước 0. Ký hiệu t1, . . . , tq là các giá trị khác nhau, tăng dần của các tij ∈
ij)m×n, trong đó
Bước 1. Lập ma trận cước phí C k = (ck
(2.7)
ck ij =
1 nếu tij > tk.
(cid:40) 0 nếu tij ≤ tk, với mọi i = 1, . . . , m, j = 1, . . . , n.
Bước 2.Giải bài toán vận tải theo mục tiêu cước phí với ma trận C k và điều
ij}m×n là phương án tối ưu và γk là giá trị mục
kiện (2.2) - (2.4). Giả sử X k = {xk
tiêu tối ưu của bài toán này.
Bước 3. Xét hai khả năng:
a) Nếu γk = 0 thì dừng quá trình giải: X k là phương án tối ưu của bài toán
(2.1) - (2.4) và thời gian vận chuyển tối ưu bằng tX k = tk.
b) Trái lại γk > 0, tăng k thành k + 1 và quay lại thực hiện Bước 1.
Nhận xét 2.1.
a). Mọi phần tử 0 trong ma trận cước phí C k cũng là các phần tử 0 trong ma
trận cước phí C k(cid:48) với 1 ≤ k < k(cid:48) ≤ q, nghĩa là số phần tử 0 trong các ma trận C k
tăng dần theo k. Với k = q thì C q ≡ 0 (ma trận không).
b) Khi giải bài toán vận tải theo mục tiêu cước phí ở vòng lặp sau, ta có thể
dùng phương án tối ưu của bài toán ở vòng lặp trước làm phương án xuất phát, do
đó quá trình giải bài toán vận tải ở mỗi vòng lặp được nhanh hơn.
Định lý 2.1. Thuật toán nêu trên dừng sau không quá q vòng lặp (mỗi vòng
lặp gồm các Bước 1, 2 và 3) và phương án nhận được là tối ưu của (P ).
17
Chứng minh. Theo nhận xét 2.1a, C q ≡ 0 và do đó γq = 0, nghĩa là thuật
toán phải dừng (ở Bước 3) sau nhiều nhất q vòng lặp.
Giả sử thuật toán dừng ở vòng lặp k∗ (1 ≤ k∗ ≤ q). Ta khẳng định rằng tk∗ là
giá trị mục tiêu tối ưu của (P ). Thật vậy, xét hai khả năng xảy ra:
a) k∗ = 1: điều khẳng định này được suy ra từ Bổ đề 2.1, bởi vì tk∗ = tmin.
b) k∗ > 1: theo thuật toán ta có γk∗ = 0 và γk > 0 với mọi k < k∗. Giả sử
tX = tk với chỉ số k nào đó thỏa mãn 1 ≤ k < k∗. Theo cách xây dựng C k và
phản chứng: tồn tại phương án X của (P ) với tX < tk∗. Theo (1.1) và Bổ đề (2.1),
cách tính tX theo (1.1), X là phương án với giá trị mục tiêu bằng 0 của bài toán
vận tải ở vòng lặp k, điều này mâu thuẫn với (γk > 0) như nhận xét ở trên. Vậy
điều khẳng định đã nêu là đúng và định lý được chứng minh đầy đủ.
Ví dụ 2.1. Áp dụng thuật toán chắn giải bài toán vận tải theo mục tiêu thời
gian với véctơ cung a, véctơ cầu b và ma trận thời gian T như sau:
a = (8 19 17), b = (11 3 14 16),
10 68 73 52
.
66 95 30 21
T =
97 63 19 23
Ví dụ này có n = 3 điểm phát, m = 4 điểm thu và thỏa mãn điều kiện cân
bằng cung cầu (2.5).
tmin = max {10, 21, 19, 10, 63, 19, 21} = 63,
tmax = max {tij : i = 1, 2, 3, j = 1, 2, 3, 4} = 97.
Bước 0. Trước hết, tính tmin theo (2.6) ta được
t1 = tmin = 63, t2 = 66, t3 = 68, t4 = 73, t5 = 95, t6 = 97 (q = 6).
Sắp xếp các giá trị khác nhau của tij ≥ tmin theo thứ tự tăng dần:
18
Vòng lặp k = 1
0 1 1 0
C 1 =
.
1 1 0 0
Bước 1. Lập ma trận cước phí C 1 (tương ứng với t1 = 63) theo (2.7):
1 0 0 0
Bước 2. Dùng thuật toán thế vị giải bài toán vận tải theo mục tiêu cước phí với
ma trận C 1 và điều kiện (2.2) - (2.4), ta được phương án tối ưu
8 0 0
0
X 1 =
.
3 0 0 16
0 3 14 0
với giá trị mục tiêu tối ưu γ1 = 3 > 0.
Bước 3. Do γ1 = 3 > 0 nên phương án X 1 chưa tối ưu cho bài toán vận tải
theo mục tiêu thời gian. Quay lại Bước 1 của vòng lặp k = 2.
Vòng lặp k = 2
0 1 1 0
.
C 2 =
0 1 0 0
Bước 1. Lập ma trận cước phí C 2 (tương ứng với t2 = 66) theo (2.7):
1 0 0 0
Bước 2. Dùng thuật toán thế vị giải bài toán vận tải theo mục tiêu cước phí với
ma trận C 2 và điều kiện (2.2) - (2.4), ta được phương án tối ưu
0 0 0 8
.
X 2 =
11 0 0 8
0 3 14 0
với giá trị mục tiêu tối ưu γ2 = 0.
19
Bước 3. Do γ2 = 0 nên phương án X 2 tối ưu cho bài toán vận tải theo mục
tiêu thời gian. Thời gian vận chuyển nhanh nhất bằng tX 2 = t2 = 66. Dừng thuật
toán.
2.2 Bài toán vận tải với hai mục tiêu
2.2.1 Mô tả bài toán
Bài toán tối ưu với hai mục tiêu: cực tiểu chi phí vận chuyển và thời gian vận
m (cid:88)
n (cid:88)
(M P )
(2.8)
min {z1 =
cijxij, z2 = max {tij : xij > 0}},
i=1
j=1
chuyển có nội dung như sau:
n (cid:88)
(2.9)
xij = ai, i = 1, . . . , m,
j=1
m (cid:88)
(2.10)
xij = bj, j = 1, . . . , n,
i=1
(2.11)
xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n.
với các điều kiện
trong đó, m là số điểm phát, n là số điểm thu, xij là lượg hàng cần chuyển từ điểm
i tới điểm thu j, tij ≥ 0 là thời gian đi từ điểm phát i tới điểm thu j, ai là lượng
phát i tới điểm thu j, cij ≥ 0 là cước vận chuyển một đơn vị hàng từ điểm phát
cung của điểm phát i và bj là lượng cầu của điểm thu j.
m (cid:88)
n (cid:88)
(2.12)
ai =
bj.
i=1
j=1
Ta cũng giả thiết (M P ) thỏa mãn điều kiện cân bằng cung cầu:
Trong một số tài liệu tiếng Anh, người ta gọi bài toán dạng (2.8) - (2.11) là bài
toán vận tải hai mục tiêu dạng chi phi - nút thắt (Bottleneck - Cost Transportation
Problem - viết tắt là BCTP).
20
Trong bài toán vận tải dạng chi phí - nút thắt, vận chuyển càng nhanh (chậm)
dẫn đến thời gian vận chuyển càng ít (nhiều), nhưng lại đòi hỏi chi phí vận chuyển
cao (thấp). Điều này đòi hỏi người quản lý dự án cần quan tâm tới nút thắt này. Vì
vậy, với các mốc thời gian khác nhau trong khoảng thời gian xác định, ta cần đưa
ra các kế hoạch vận chuyển với chi phí thấp nhất tương ứng. Cách phân tích này
sẽ giúp các nhà quản lý (người có quyền ra quyết định) lựa chọn một kế hoạch vận
chuyển thích hợp, tùy thuộc khả năng tài chính và qui mô nút thắt mà họ có thể
tác động tới.
Định nghĩa 2.2. Cặp (X, t), trong đó X = (xij)m×n và t chỉ thời gian được
gọi là một nghiệm chấp nhận được (feasible solution) của bài toán (M P ) nếu X
thỏa mãn các ràng buộc (2.9) - (2.11) và z2 = t. Nếu X là phương án cực biên của
bài toán vận tải thì (X, t) gọi là nghiệm cơ sở (basic solution).
Định nghĩa 2.3. Cặp (X 0, t0) gọi là một nghiệm hữu hiệu (efficient solu-
z1(X) ≤ z1(X 0) và t < t0 hoặc z1(X) < z1(X 0) và t ≤ t0.
tion) của (M P ) nếu không tồn tại nghiệm chấp nhận được (X, t) của (M P ) với
Định nghĩa 2.4. Cặp (X 0, t0) gọi là một nghiệm hữu hiệu yếu (weak effi-
z1(X 0) và t < t0.
cient solution) nếu không tồn tại nghiệm chấp nhận được (X, t) sao cho z1(X) <
2.2.2 Tìm các nghiệm cơ sở hữu hiệu của (MP)
Thuật toán sau đây cho phép tìm tất cả các nghiệm cơ sở hữu hiệu của bài toán
vận tải hai mục tiêu dạng chi phí - nút thắt (2.8) - (2.11).
Thuật toán gồm 7 bước:
Bước 1. Từ bài toán (M P ) lập bài toán vận tải theo mục tiêu thời gian.
Bước 2. Dùng thuật toán chắn giải bài toán theo mục tiêu thời gian vừa xây
dựng. Giả sử nghiệm tối ưu nhận được là t0. Lưu ý t0 ≥ t1 = tmin (xem (2.6).
21
Bước 3. Từ bài toán (M P ) lập bài toán vận tải theo mục tiêu cước phí.
Bước 4. Dùng thuật toán thế vị giải bài toán vận tải theo mục tiêu cước phí
vừa thiết lập, đồng thời tính thời gian vận chuyển tương ứng với phương án tối ưu
đã tìm được. Giả sử đó là tm.
Bước 5. Với mỗi thời hạn τ ∈ [t0, tm] tính hệ số α = (tm − τ )/(tm − t0), biểu
thị mức độ hài lòng đối với thời hạn τ .
Bước 6. Với mỗi τ ∈ [t0, tm] xây dựng bài toán vận tải theo mục tiêu cước phí
với hạn chế không chuyển hàng trên ô (i, j) mà tij > τ và giải bài toán theo thuật
toán thế vị.
Bước 7. Với mỗi τ một nghiệm tối ưu của bài toán vận tải theo mục tiêu cước
phí X(τ ) nhận được ở Bước 6 có mức độ hài lòng α. Khi đó, (X(τ ), τ ) là một
nghiệm cơ sở hữu hiệu của bài toán vận tải hai mục tiêu (M P ).
Ví dụ 2.2. Xét bài toán vận tải kích thước 3 × 4 với hai mục tiêu (cước phí và
thời gian) sau đây với dữ liệu của bài toán được cho trong Bảng 2.1: Các số ghi
ở góc trên bên trái mỗi ô (i, j) là thời gian đi từ điểm phát i tới điểm thu j, còn
số ghi ở góc dưới bên phải ô (i, j) là cước vận chuyển một đơn vị hàng từ i tới j.
Lượng cung của các điểm phát ghi ở cột bên trái của bảng và lượng cầu của các
điểm thu ghi ở dòng trên cùng của bảng.
(Trong mỗi ô: dòng trên ghi thời gian, dòng dưới ghi cước vận chuyển).
22
1. Bài toán vận tải theo mục tiêu thời gian của (M P ) cho ở Bảng 2.2.
2. Giải bài toán này theo thuật toán chắn (xem Ví dụ 2.1), ta nhận được phương
án tối ưu với thời gian vận chuyển nhanh nhất là t0 = 66. (Lượng hàng vận chuyển
được ghi ở giữa dòng thứ hai mỗi ô của Bảng 2.2).
3. Bài toán vận tải theo mục tiêu cước phí của (MP) cho ở Bảng 2.3.
4. Giải bài toán này theo thuật toán thế vị (xem Mục 1.4), ta nhận được phương
án tối ưu X ∗ với cước phí vận chuyển nhỏ nhất là f ∗ = 348. (Lượng hàng vận
chuyển được ghi ở giữa dòng thứ nhất mỗi ô của Bảng 2.3). Thời gian vận chuyển
t0 = 66, tm = 95. Đặt M = {66, 68, 73, 95}.
của phương án này là tX ∗ = 95 (xem thời gian ở Bảng 2.2). Như vậy ta thấy
5. Với mỗi τ ∈ M để tìm phương án của (M P ) có thời gian vận chuyển
bằng τ , ta lập và giải bài toán vận tải theo mục tiêu cước phí với điều kiện (2.9) -
cij = +∞ nếu tij > τ ).
(2.11) và có thêm hạn chế: cấm vận chuyển hàng trên các ô (i, j) mà tij > τ (đặt
23
+ Ta bắt đầu với τ = 73 < 95. Bài toán vận tải theo mục tiêu cước phí tương
ứng được cho ở Bảng (2.4).
6. Giải bài toán này theo thuật toán thế vị (xem Mục 1.4), ta nhận được phương
án tối ưu X ∗ với cước phí vận chuyển nhỏ nhất là f ∗ = 351. (Lượng hàng vận
chuyển được ghi ở giữa dòng thứ nhất mỗi ô của Bảng 2.4).
+ Tiếp theo, với τ = 68 < 73 bài toán vận tải theo mục tiêu cước phí tương
ứng được cho ở Bảng 2.5.
Giải bài toán này theo thuật toán thế vị (xem Mục 1.4), ta nhận được phương
án tối ưu X ∗ với cước phí vận chuyển nhỏ nhất là f ∗ = 356. (Lượng hàng vận
chuyển được ghi ở giữa dòng thứ nhất mỗi ô của Bảng 2.5).
+ Cuối cùng, với τ = 66 < 68 bài toán vận tải theo mục tiêu cước phí tương
ứng được cho ở Bảng 2.6.
24
Giải bài toán này theo thuật toán thế vị (xem Mục 1.4), ta nhận được phương
án tối ưu X ∗ với cước phí vận chuyển nhỏ nhất là f ∗ = 381. (Lượng hàng vận
chuyển được ghi ở giữa dòng thứ nhất mỗi ô của Bảng 2.6).
Tóm lại, chương này đã đề cập tới bài toán vận tải theo mục tiêu thời gian và
trình bày thuật toán chắn giải bài toán, nhờ đưa về giải dãy bài toán vận tải theo
mục tiêu cước phí (dùng thuật toán thế vị để giải). Sau đó, xét bài toán vận tải
với hai mục tiêu: cực tiểu chi phí lẫn thời gian vận chuyển. Cuối chương trình bày
cách tìm các nghiệm cơ sở hữu hiệu của bài toán vận tải hai mục tiêu cùng với ví
dụ tính toán cụ thể.
25
Chương 3
Bài toán vận tải với ba mục tiêu
Chương này đề cập tới mô hình bài toán vận tải dạng nút thắt với ba tiêu chuẩn
mục tiêu và trình bày thuật toán tìm tập nghiệm cơ sở hữu hiệu của bài toán. Nội
dung của chương dựa chủ yếu vào tài liệu [6].
3.1 Nội dung bài toán
Xét mô hình bài toán vận tải ba tiêu chuẩn mục tiêu dạng nút thắt với hai hàm
(3.1)
min {z1, z2, z3},
mục tiêu phân thức sau đây:
cijxij
dijxij
m (cid:80) i=1
n (cid:80) j=1
m (cid:80) i=1
n (cid:80) j=1
z1 =
, z2 =
, z3 = max
{tij : xij > 0},
i,j
{tij : xij > 0}
{tij : xij > 0}
max i,j
max i,j
trong đó
n (cid:88)
(3.2)
xij = ai, i = 1, . . . , m,
j=1
m (cid:88)
(3.3)
xij = bj, j = 1, . . . , n,
i=1
(3.4)
xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n.
m (cid:88)
n (cid:88)
(3.5)
ai =
bj.
i=1
j=1
với các điều kiện
26
dij là thiệt hại (hao hụt chẳng hạn) khi vận chuyển một đơn vị hàng từ điểm phát
i tới điểm thu j, tij là thời gian đi từ điểm phát i tới điểm thu j, ai là lượng cung
trong đó cij là cước vận chuyển một đơn vị hàng từ điểm phát i tới điểm thu j,
của điểm phát i, bj là lượng cầu của điểm thu j và xij biểu thị lượng hàng được
z1 biểu thị chi phí vận chuyển trung bình (tính trên một đơn vị thời gian vận
chuyển từ điểm phát i tới điểm thu j. Ở đây (3.5) là điều kiện cân bằng cung cầu.
chuyển), z2 là thiệt hại trung bình trong quá trình vận chuyển (tính trên một đơn vị
thời gian vận chuyển) và z3 là thời gian vận chuyển của phương án X = (xij)m×n.
Điều kiện (3.2) yêu cầu mọi điểm phát giao hết hàng, điều kiện (3.3) đảm bảo
mọi điểm thu nhận đủ hàng và điều kiện (3.4) đòi hỏi lượng hàng vận chuyển
không âm.
Các khái niệm nghiệm hữu hiệu (hữu hiệu yếu), nghiệm cơ sở hữu hiệu của
bài toán vận tải với nhiều hàm mục tiêu được hiểu theo nghĩa thông thường (tương
tự các Định nghĩa 2.2 - 2.4).
Để giải bài toán (3.1) - (3.5) nhằm tìm tập nghiệm cơ sở hữu hiệu, ta đưa bài
m (cid:88)
n (cid:88)
m (cid:88)
n (cid:88)
min {z1 =
cijxij, z2 =
dijxij, z3 = max
{tij : xij > 0}}
i,j
i=1
j=1
i=1
j=1
(3.6)
toán về mô hình sau.
n (cid:88)
(3.7)
xij = ai, i = 1, . . . , m,
j=1
m (cid:88)
(3.8)
xij = bj, j = 1, . . . , n,
i=1
(3.9)
xij ≥ 0, i = 1, . . . , m, j = 1, . . . , n.
n (cid:88)
m (cid:88)
(3.10)
ai =
bj.
i=1
j=1
với các điều kiện
Định lý sau nêu quan hệ giữa hai bài toán (3.1) - (3.5) và (3.6) - (3.10).
27
Định lý 3.1. Tập các nghiệm cơ sở hữu hiệu của bài toán (3.1) - (3.5) và (3.6)
- (3.10) hoàn toàn trùng nhau.
ij)m×n là một nghiệm cơ sở hữu hiệu của bài
Chứng minh. Giả sử X 1 = (x1
{tij : x1
ij > 0}. Từ định nghĩa của nghiệm hữu hiệu
i,j cho thấy rằng với mỗi nghiệm chấp nhận được X 2 = (x2
ij)m×n của (3.1) - (3.5) và
t2 = max
{tij : x2
ij > 0}} thì các bất đẳng thức
i,j
toán (3.1) - (3.5) và t1 = max
z2(X 1) ≤ z2(X 2)
(3.11)
và (cid:40) z1(X 1) < z1(X 2)
z1(X 1) ≤ z1(X 2) và
z2(X 1) < z2(X 2).
hoặc
trong đó 0 ≤ t2 ≤ t1, là đúng.
Giả sử X 1 không phải là một nghiệm hữu hiệu của mô hình (3.6) - (3.10).
Lập luận tương tự như trước, từ định nghĩa của nghiệm hữu hiệu suy ra rằng tồn
tại nghiệm chấp nhận được X 2 của (3.6) - (3.10) và t2 tương ứng sao cho các bất
đẳng thức
z1(X 2) t2
< z1(X 1) t1
z2(X 2) t2
≤ z2(X 1) t1
(3.12)
và (cid:40)
hoặc
< z2(X 1)t1.
z2(X 2) t2
z1(X 2) t2
≤ z1(X 1) t1 trong đó 0 ≤ t2 ≤ t1, là đúng.
và
Nhân các bất đẳng thức (3.12) với t1 và đặt k = t1/t2 ta thấy các bất đẳng
thức sau đây là đúng
(3.13)
và kz2(X 2) ≤ z2(X 1) (cid:40) kz1(X 2) < z1(X 1)
kz1(X 2) ≤ z1(X 1) và kz2(X 2) < z2(X 1).
hoặc
trong đó 0 ≤ t2 ≤ t1.
Rõ ràng k ≥ 1, do đó từ (3.13) suy ra rằng đối với nghiệm X 2 các bất đẳng
28
thức sau đây đúng
z2(X 2) ≤ z2(X 1)
(3.14)
và (cid:40) z1(X 2) < z1(X 1)
z1(X 2) ≤ z1(X 1) và
z2(X 2) < z2(X 1).
hoặc
trong đó 0 ≤ t2 ≤ t1. Điều này trái với (3.11).
Bằng cách tương tự, có thể chứng minh rằng mỗi nghiệm cơ sở hữu hiệu của
(3.6) - (3.10) cũng là một nghiệm cơ sở hữu hiệu của (3.1) - (3.5).
Ý tưởng trên được mở rộng cho mô hình bài toán vận tải dạng nút thắt với p
(p ≥ 2) hàm mục tiêu phân thức. Khi đó, ta cũng có kết luận rằng có thể tìm tập
nghiệm cơ sở hữu hiệu của bài toán ban đầu bằng cách tìm tập nghiệm cơ sở hữu
m (cid:88)
n (cid:88)
m (cid:88)
n (cid:88)
min {z1 =
{tij : xij > 0}}
c1 ijxij, . . . , zp =
cp ijxij, zp+1 = max i,j
i=1
j=1
i=1
j=1
(3.15)
hiệu của mô hình đơn giản hơn:
với cùng các điều kiện (3.7) - (3.10).
ij (k = 1, . . . , p, i = 1, . . . , m, j = 1, . . . , n) được giải
Ở đây, các giá trị ck
thích phù hợp với tiêu chuẩn mục tiêu tương ứng.
Tính đúng đắn của kết luận giống như trong Định lý 3.1 đối với mô hình (3.15),
(3.7) - (3.10) được chứng minh tương tự.
Rõ ràng mô hình (3.6) - (3.10) là một trường hợp riêng của mô hình (3.15),
(3.7) - (3.10). Vì thế, có thể dùng thuật toán giải mô hình (3.15), (3.7) - (3.10) để
giải mô hình (3.6) - (3.10).
Mục tiếp theo sẽ trình bày phương pháp tìm tập nghiệm cơ sở hữu hiệu của mô
hình (3.6) - (3.10).
29
3.2 Tìm tập nghiệm cơ sở hữu hiệu
Theo Bổ đề 2.1, thời gian vận chuyển tối thiểu đối với mọi phương án của bài
toán (3.6) - (3.10) bằng tmin, trong đó tmin được xác định theo (2.6).
Ký hiệu tmax = max {tij : i = 1, . . . , m, j = 1, . . . , n}.
Có thể thấy rằng tmin ≤ z3 ≤ tmax.
tij ∈ [tmin, tmax] với t1 = tmin và tq = tmax.
Ký hiệu t1, . . . , tq là các giá trị khác nhau, xếp theo thứ tự tăng dần của mọi
Thuật toán tìm tập nghiệm cơ sở (tức tập phương án cực biên theo Định nghĩa
2.2) hữu hiệu của mô hình (3.6) - (3.10) là một thuật toán lặp, gồm một số hữu
hạn vòng lặp. Mỗi vòng tìm tập nghiệm cơ sở hữu hiệu của bài toán vận tải thu
m (cid:88)
n (cid:88)
m (cid:88)
n (cid:88)
(3.16)
min {z1 =
cijxij, z2 =
dijxij}
i=1
j=1
i=1
j=1
hẹp hai mục tiêu:
(3.17)
xij = 0 với mọi (i, j) mà tij > τ,
với các điều kiện (3.7) - (3.10) và điều kiện thu hẹp dạng:
q.
trong đó τ là một giá trị nào đó τ ∈ {t1, t2, . . . , tq}. Do đó số vòng lặp tối đa là
Giả sử tk là số nhỏ nhất trong dãy t1, t2, . . . , tq sao cho hệ điều kiện (3.7) -
(3.10) và (3.17) với τ = tk có nghiệm.
(xij)m×n của hệ ràng buộc (3.7) - (3.10) tương ứng với một tập gồm (m + n − 1)
Như đã biết (theo Định nghĩa 1.1 và Định lý 1.1), mỗi nghiệm cơ sở X =
ô của bảng vận tải (Bảng 1.1) không chứa chu trình. Ký hiệu tập ô này là GX.
τ = tk, tk+1, . . . , tq sẽ là một nghiệm cơ sở hữu hiệu của bài toán vận tải dạng
Mỗi nghiệm cơ sở hữu hiệu của bài toán vận tải thu hẹp (3.16), (3.17) với
nút thắt (3.6) - (3.10), với giá trị mục tiêu (z1, z2, τ ).
30
Sau đây là thuật toán thực hiện ý tưởng của phương pháp giải vừa mô tả.
THUẬT TOÁN
Bước 0. (Khởi sự):
Tính tmin theo (2.6), tmax = max {tij : i = 1, . . . , m, j = 1, . . . , n}. Sắp xếp
t1 = tmin < t2 < . . . < tq = tmax.
các giá trị khác nhau của tij ∈ [tmin, tmax] theo thứ tự tăng dần
Đặt k = 1.
Bước 1. Tìm nghiệm cơ sở hữu hiệu ban đầu: Gán τ = tk.
Lập và giải bài toán vận tải theo mục tiêu cước phí với ma trận cước phí (các
ô (i, j) với cij = +∞ xem như bị cấm)
ij nếu tij ≤ τ
C =
(3.18)
+∞ nếu tij > τ.
(cid:40) c1
a. Nếu trị tối ưu bằng +∞ thì quay lai thực hiện Bước 1 với k ← k + 1.
b. Trái lại, tìm tất cả các lời giải của bài toán vận tải theo mục tiêu cước phí
này (nếu bài toán có nhiều lời giải). Lời giải nào có tổng cước phí tính theo C 2
nhỏ nhất sẽ là một nghiệm cơ sở hữu hiệu ban đầu của (3.6) - (3.10), ký hiệu S1.
Lưu giữ (ghi) S1 vào danh sách L. Chuyển sang thực hiện Bước 2.
Bước 2. (Tìm các nghiệm cơ sở hữu hiệu kề S1): Các nghiệm cơ sở hữu hiệu
kề S1 được tìm bằng cách chỉ dùng các ô không bị cấm (cij < +∞) và chỉ phân
hàng vào các ô (i, j) có ∆ij = 0 tính theo C 1 hoặc C 2. Ghi nghiệm hữu hiệu tìm
được vào danh sách L, nếu trước đó nó chưa có trong L.
Bước 3. Nếu k = q thì dừng thuật toán. Trái lại, đặt k ← k + 1. Sửa lại C
theo (3.18) với τ = tk mới và chuyển sang thực hiện Bước 4.
Bước 4. (Khảo sát các nghiệm cơ sở hữu hiệu đã ghi trong L): Mỗi nghiệm cơ
sở hữu hiệu trong L sẽ được xem xét để tìm các nghiệm cơ sở hữu hiệu mới ứng
31
với z3 = τ . Bằng cách lần lượt đưa các ô có cij = τ vào cơ sở và xét các giá trị
mục tiêu tương ứng. Nếu giá trị này không bị vượt trội bởi giá trị mục tiêu của bất
cứ nghiệm hữu hiệu nào đã ghi trong L, thì ta nhận được một nghiệm cơ sở hữu
hiệu mới. Lưu giữ (ghi) nghiệm hữu hiệu này vào danh sách L. Quay lại thực hiện
Bước 3.
Tập nghiệm cơ sở hữu hiệu của bài toán vận tải đa mục tiêu được chọn ra từ
tập nghiệm cơ sở của các ràng buộc vận tải (3.7) - (3.10).
Định lý 3.2. Thuật toán nêu trên sẽ cho tập tất cả các nghiệm cơ sở hữu hiệu
của bài toán vận tải đa mục tiêu dạng nút thắt (3.6) - (3.10).
Chứng minh. Ký hiệu L là danh sách các nghiệm cơ sở hữu hiệu của mô
hình (3.6) - (3.10) tìm được bằng cách áp dụng thuật toán đã nêu. Giả thiết tồn tại
nghiệm cơ sở hữu hiệu S(cid:48) không được tìm bằng thuật toán đó và S(cid:48) (cid:54)∈ L.
Giả sử S(cid:48) tương ứng với thời gian vận chuyển τ (cid:48) = tk với một tk nào đó thuộc
tập {t1, . . . , tq}. Một sự khảo sát rộng khắp nhánh cố định này dẫn tới ghi lại tất
cả các nghiệm cơ sở của nhánh t(cid:48). Như vậy, tất cả các nghiệm cơ sở tương ứng với
thời gian t(cid:48) đều được chứa trong tập này. Ta sẽ tách ra từ đó tập các nghiệm cơ sở
S(cid:48) ∈ Lt(cid:48) thì S(cid:48) là một nghiệm cơ sở hữu hiệu được tìm thấy theo thuật toán đã
hữu hiệu tương ứng với thời gian t(cid:48), ký hiệu Lt(cid:48) . Rõ ràng Lt(cid:48) ⊂ L. Kết quả là nếu
(cid:54)∈ Lt(cid:48) thì S(cid:48) không phải là một nghiệm cơ sở và do đó không là
nêu, còn nếu S(cid:48)
nghiệm cơ sở hữu hiệu. Vì vậy, hoặc S(cid:48) không phải là một nghiệm cơ sở, hoặc S(cid:48)
nằm trong danh sách L và định lý được chứng minh.
Sau đây là một ví dụ cụ thể minh họa cho thuật toán đã trình bày.
3.3 Ví dụ minh họa
Ví dụ 3.1. Tìm tập nghiệm cơ sở hữu hiệu của mô hình bài toán vận tải ba mục
tiêu dạng nút thắt (3.6) - (3.10) với m = 3 điểm phát, n = 4 điểm thu, véctơ cung
32
a, véctơ cầu b, ma trận thời gian T và hai ma trận chi phí C 1 và C 2 cho sau đây:
a = (8 19 17), b = (11 3 14 16),
10 95 73 52
1 2 7 7
4 4 3 4
T =
, C 1 =
, C 2 =
.
68 66 30 21
1 9 3 4
5 8 9 10
37 63 19 23
8 9 4 6
6 2 5 1
tmin = max {10, 21, 19, 10, 63, 19, 21} = 63.
Bước 0. Tính tmin theo (2.6) ta được
t1 = 63, t2 = 66, t3 = 68, t4 = 73, t5 = 95 (q = 5).
Sắp xếp các giá trị khác nhau của tij ≥ tmin theo thứ tự tăng dần:
Đặt k = 1.
Bước 1. (Tìm nghiệm cơ sở hữu hiệu ban đầu): Gán τ = tk. Bài toán vận tải
theo mục tiêu cước phí với ma trận cước phí C tính theo (3.18), được cho ở Bảng
3.1: Cước phí ghi ở góc phải dòng thứ hai mỗi ô của bảng. (Đặt cij = +∞ với
những ô (i, j) có tij > τ trừ các ô tô bóng mờ).
Giải bài toán này theo thuật toán thế vị (xem Mục 1.4), ta nhận được nghiệm cơ
sở tối ưu duy nhất S1 với cước phí z1(S1) = 176 (tính theo C 1) và z2(S1) = 298
(tính theo C 2). Lượng hàng vận chuyển được ghi ở giữa dòng thứ nhất mỗi ô của
Bảng 3.1. Do S1 là nghiệm tối ưu duy nhất, nên S1 là nghiệm cơ sở hữu hiệu của
(cid:96) = 0 và lưu giữ (ghi) S1 vào danh sách L (Bảng 3.4).
(3.6) - (3.10) với giá trị mục tiêu (z1, z2, z3) = (176, 298, 63). Gán cho S1 mức
33
Bước 2. (Tìm nghiệm cơ sở hữu hiệu kề S1): Nghiệm cơ sở kề S1 được tính
bằng cách đưa x14 hoặc x34 vào cơ sở mới. Tuy nhiên, chỉ có nghiệm kề thứ
(187, 243, 63). Gán cho S2 mức (cid:96) = 0 và lưu giữ (ghi) S2 vào danh sách L.
hai ký hiệu S2 (ghi ở Bảng 3.2) là hữu hiệu, với giá trị mục tiêu (z1, z2, z3) =
Bước 3. Do k = 1 < q = 5 nên ta đặt k ← k + 1 = 2 và (cid:96) ← (cid:96) + 1 = 1.
Tính lại ma trận C theo (3.18) ta được bài toán vận tải thu hẹp mới (Bảng 3.3) với
ô không bị cấm mới (2.2). Chuyển sang thực hiện Bước 4.
Bước 4. (Khảo sát các nghiệm cơ sở hữu hiệu đã ghi trongL): Để tìm nghiệm
cơ sở mới kề S1 ta đưa x22 vào cơ sở và nhận được nghiệm cơ sở với giá trị mục
34
S1 (xem Bảng 3.4), vì thế nghiệm này không là hữu hiệu.
tiêu (z1, z2, z3) = (179, 304, 66), giá trị này bị vượt trội bởi giá trị mục tiêu của
Tiếp theo, đưa x22 vào cơ sở của S2 ta nhận được nghiệm cơ sở S3 (cho ở Bảng
3.3), với giá trị mục tiêu (z1, z2, z3) = (193, 234, 66), giá trị này không bị vượt
trội bởi các giá trị mục tiêu đã có, vì thế S3 là một nghiệm cơ sở hữu hiệu của (3.6)
- (3.10). Gán cho S3 mức (cid:96) = 1 và lưu giữ S3 vào danh sách L.
Quay lại thực hiện Bước 3.
Tiếp tục thực hiện các bước của thuật toán, ta tìm được tất cả 14 nghiệm cơ sở
hữu hiệu của (3.6) - (3.10) ghi trong danh sách L (xem Bảng 3.4).
35
Hai nghiệm cơ sở gọi là kề nhau nếu tập biến cơ sở của chúng chỉ khác nhau
ở một biến. Chẳng hạn, S1, S2 kề nhau do x33 là biến cơ sở chỉ của S1, x34 là biến
cơ sở chỉ của S2 (S1 và S2 có chung 5 biến cơ sở còn lại: x11, x23, x24, x31 và x32).
Tóm lại, chương này đã đề cập tới mô hình bài toán vận tải ba mục tiêu dạng
nút thắt, trong đó hai mục tiêu đầu là hàm phân tuyến tính. Bài toán này được đưa
về dạng bài toán ba mục tiêu đơn giản hơn và có thể giải bằng thuật toán tìm tập
nghiệm hữu hiệu của một số bài toán vận tải hai mục tiêu.
36
Kết luận
Luận văn đã đề cập tới một số mô hình bài toán vận tải nhiều hàm mục tiêu,
khái niệm về nghiệm hữu hiệu của mô hình theo tối ưu Pareto và các thuật toán
tìm tập nghiệm cơ sở hữu hiệu của bài toán.
Luận văn đã trình bày một số nội dung cụ thể sau:
1. Các kiến thức cơ bản về bài toán vận tải theo mục tiêu cước phí: nội dung và
tính chất nghiệm của bài toán, điều kiện tối ưu và thuật toán thế vị giải bài toán.
2. Bài toán vận tải theo mục tiêu thời gian và bài toán vận tải với hai mục tiêu:
cực tiểu cả cước phí lẫn thời gian vận chuyển. Các thuật toán chắn giải bài toán,
dựa trên ý tưởng: chỉ vận chuyển hàng trên các tuyến có thời gian nhỏ hơn hay
bằng một mức nào đó, sau đó mở rộng dần các mức thời gian này.
3. Bài toán vận tải ba mục tiêu dạng nút thắt, trong đó hai mục tiêu đầu là tỉ
số giữa cước phí vận chuyển và thiệt hại do vận chuyển với thời gian vận chuyển.
Bài toán này được giải bằng thuật toán tìm tập nghiệm cơ sở hữu hiệu của một số
bài toán vận tải hai mục tiêu.
Có thể xem luận văn như bước đầu tìm hiểu về một số mô hình bài toán vận tải
với nhiều hàm mục tiêu, các thuật toán tiêu biểu xử lý mô hình và khả năng ứng
dụng của chúng trong thức tiễn. Tác giả luận văn hy vọng sẽ có dịp được tìm hiểu
sâu hơn về nhiều dạng mô hình và phương pháp giải khác.
37
Tài liệu tham khảo
Tiếng Việt
[1] Nguyễn Thị Bạch Kim (2014), Giáo trình các phương pháp tối ưu: Lý thuyết
và thuật toán, NXB Bách Khoa, Hà Nội.
[2] Trần Vũ Thiệu (2004), Giáo trình tối ưu tuyến tính, NXB Đại học Quốc gia
Hà Nội.
Tiếng Anh
[3] Bazaraa M. J., Jarvis J. and Sherali H. (2010), Linear Programming and Net-
work Flows, fouth edtion. Wiley.
[4] Nikoli´c I. (2007), Total time minimizing transportation problem, Yugoslav
Journal of Operations Research, 17, pp. 125 - 133.
[5] Pandian P., Natarajan G. (2011), A new method for solving bottleneck - cost
transportation problems, International Mathematical Forum, 6 (10), pp. 451 -
460.
[6] Tkacenko A. I. (2006), The generalized algorithm for solving the fractional
multiobjective transportation problem, Romai J., 2. (1), pp. 197 - 202.
