Cập nhật thông tin chi tiết về Khắc Phục Hiện Tượng Suy Biến Trong Bài Toán Vận Tải (2) mới nhất ngày 24/01/2021 trên website Zdungk.com. Hy vọng nội dung bài viết sẽ đáp ứng được nhu cầu của bạn, chúng tôi sẽ thường xuyên cập nhật mới nội dung để bạn nhận được thông tin nhanh chóng và chính xác nhất. Cho đến thời điểm hiện tại, bài viết này đã đạt được 1,980 lượt xem.
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
TRỊNH XUÂN BÁCH
KHẮC PHỤC HIỆN TƯỢNG SUY BIẾN
TRONG BÀI TOÁN VẬN TẢI
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60.46.01.12
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học:
GS.TS. TRẦN VŨ THIỆU
THÁI NGUYÊN – NĂM 2013
1Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
i
i
Lời cảm ơn
ii
Mở đầu
1
1 Bài toán vận tải tuyến tính
4
1.1
Bài toán và tính chất . . . . . . . . . . . . . . . . . . . . .
4
1.2
Phương pháp tìm phương án cực biên ban đầu . . . . . . .
9
1.2.1
Phương pháp min cước . . . . . . . . . . . . . . . .
9
1.2.2
Phương pháp góc tây bắc . . . . . . . . . . . . . . . 11
1.3
Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . . . . 13
1.4
Thuật toán thế vị . . . . . . . . . . . . . . . . . . . . . . . 14
1.5
Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Bài toán vận tải suy biến và cách khắc phục
20
2.1
Thế nào là suy biến . . . . . . . . . . . . . . . . . . . . . . 20
2.2
Ví dụ xoay vòng . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3
Bài toán nhiễu . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4
Cách khắc phục xoay vòng . . . . . . . . . . . . . . . . . . 32
2.5
Ví dụ minh họa tránh xoay vòng . . . . . . . . . . . . . . . 33
Kết luận.
42
Tài liệu tham khảo
43
2Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
ii
Lời cảm ơn
Trong suốt quá trình làm luận văn, tôi luôn nhận được sự hướng dẫn
và giúp đỡ của chúng tôi Trần Vũ Thiệu (Viện Hàn lâm Khoa học và Công
nghệ Việt Nam). Tôi xin chân thành bày tỏ lòng biết ơn sâu sắc đến thầy.
Tôi xin cảm ơn quý thầy, cô giảng dạy lớp cao học khóa 5 (2011 − 2013)
đã mang đến cho tôi nhiều kiến thức bổ ích trong khoa học và cuộc sống.
Mặc dù đã có nhiều cố gắng nhưng luận văn khó tránh khỏi những thiếu
sót. Tác giả mong nhận được những ý kiến đóng góp của quý thầy, cô và
bạn đọc để luận văn được hoàn thiện hơn.
Xin trân trọng cảm ơn!
Hải Phòng, tháng 01 năm 2013.
Người viết Luận văn
Trịnh Xuân Bách
3Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
1
Mở đầu
Tối ưu hoá (Optimization) là một môn toán học ứng dụng đã và đang
được nghiên cứu, giảng dạy và học tập ở rất nhiều trường đại học, cao
đẳng trong nước cho sinh viên các ngành toán học, tin học, kinh tế và kĩ
thuật. Trong các bài toán tối ưu thì quan trọng nhất và đáng chú ý nhất
là các bài toán tối ưu tuyến tính. Qui hoạch tuyến tính là bài toán tối
ưu đơn giản nhất, được ứng dụng rộng rãi nhất trong nhiều lĩnh vực khác
nhau của kinh tế, đời sống và quốc phòng. Chính vì vậy đây cũng là bài
toán được nghiên cứu đầy đủ và hoàn chỉnh nhất, cả về mặt lí thuyết và
tính toán, cũng đã có nhiều sách và giáo trình viết về vấn đề này, ở đây
tôi xin trình bày một phần nhỏ của bài toán tối ưu.
Bài toán vận tải (Transportation Problem) của qui hoạch tuyến tính là
bài toán tối ưu được ứng dụng rộng rãi trong thực tiễn. Trong bài toán
này hàm mục tiêu là tuyến tính (nghĩa là chi phí vận chuyển tỉ lê thuận với
lượng hàng vận chuyển) và các ràng buộc của bài toán có dạng đặc biệt.
Nhờ khai thác cấu trúc đặc biệt này, người ta đã đề ra các phương pháp
riêng, hiệu quả hơn hẳn so với việc áp dụng phương pháp đơn hình tổng
quát vào bài toán. Đáng chú ý là phương pháp thế vị (xem ), phương pháp thu hẹp chính tắc,…
Mô hình toán học của bài toán vận tải có dạng một bài toán qui hoạch
tuyến tính chính tắc:
min cT x : Ax = b, x ≥ 0
với A ∈ Rm×n , b ∈ Rm , c ∈ Rn cho trước. Ta thường giả thiết rank (A) =
m và m ≤ n. Với bài toán này, các phương án cực biên (còn gọi là lời giải
cơ sở) thường hay “suy biến”, tức là có số thành phần dương nhỏ hơn
4Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
2
5Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
3
Chứng minh mọi phương án cực biên trong bài toán nhiễu đều không suy
biến, do đó không xảy ra hiện tượng xoay vòng khi giải nó theo thuật toán
thế vị.
6Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
4
Chương 1
Bài toán vận tải tuyến tính
Chương này đề cập tới bài toán vận tải tuyến tính (chi phí vận chuyển tỉ
lệ thuận với lượng hàng vận chuyển), đó là dạng bài toán qui hoạch tuyến
tính đơn giản nhất và được ứng dụng rộng rãi nhất trong thực tiễn. Phần
đầu của chương trình bày nội dung và các tính chất cơ bản của bài toán.
Tiếp đó đề cập tới phương pháp tìm phương án cực biên ban đầu của bài
toán. Sau đó trình bày cơ sở lý luận và nội dung thuật toán thế vị (một
biến thể của thuật toán đơn hình) giải bài toán vận tải. Cuối chương nêu
ví dụ số minh họa cho thuật toán giải. Nội dung của chương được tham
khảo chủ yếu từ các tài liệu và [3].
1.1
Bài toán và tính chất
Bài toán vận tải có nội dung như sau: Giả sử có m kho 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
7Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
5
Khi đó mô hình toán học của bài toán vận tải có dạng như sau:
f (x) =
cij xij → min
(cực tiểu tổng chi phí vận chuyển) (1.1)
i=1 j=1
xij = ai , i = 1, 2, …, m (mọi điểm phát giao hết hàng),
(1.2)
xij = bj , j = 1, 2, …, n
(1.3)
(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)
Ở đây, m là số kho chứa hàng (điểm phát),
n là số nơi tiêu thụ hàng (điểm thu),
ai là lượng hàng có (cung) ở điểm phát i (i = 1, 2, …, m),
bj là lượng hàng cần (cầu) ở điểm thu j (j = 1, 2, …n),
cij là chi phí vận chuyển một đơn vị hàng từ điểm phát i tới điểm thu j,
xij biểu thị lượng hàng vận chuyển cần tìm từ điểm phát i tới điểm thu j.
Đ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 bằng thu phát, nghĩa là tổng cung bằng tổng cầu:
α1 + a2 + … + am = b1 + b2 + … + bn .
(1.5)
Bài toán vận tải (1.1)-(1.4) là một dạng đặc biệt của qui hoạch tuyến
tính. Để thấy rõ điều này ta sắp xếp các biến số theo thứ tự
x11 , x12 , …, x1n , x21 , x22 , …, x2n , …, xm1 , xm2 , …, xmn
và viết lại hệ ràng buộc chính (1.2)-(1.3) dưới dạng hệ m + n phương trình
8Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
6
x1n
……
Ký hiệu A là ma trận hệ số của hệ phương trình trên (m + n hàng và
m × n cột ),
x = (x11 , …, x1n , x21 , …, x2n , …, xm1 , …, xmn )T -véctơ cột m×n thành phần,
c = (c11 , …, c1n , x21 , …, c2n , …, cm1 , …, cmn )T -véctơ cột m × n thành phần,
b = (a1 , a2 , …, am , b1 , b2 , …, bn )T -véctơ cột vế phải (m + n thành phần).
Bài toán vận tải (1.1)-(1.4) được viết lại thành bài toán qui hoạch tuyến
tính dạng chính tắc:
f = hc, xi → min,
(1.6)
Ax = b, x ≥ 0.
(1.7)
9Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
7
Với điều kiện (1.5) bài toán vận tải (1.1)-(1.4) có các tính chất sau đây:
1. Bài toán luôn có phương án và tập hợp các phương án của bài toán
là giới nội.
2. Một trong các ràng buộc (1.2)-(1.3) là thừa và hạng của hệ ràng buộc
này bằng m + n − 1.
3. Nếu các lượng cung và cầu ai , bj là các số nguyên thì bài toán sẽ có
lời giải nguyên.
Có thể dùng các phương pháp của qui hoạch tuyến tính để giải bài toán
vận tải. Tuy nhiên do bài toán này có dạng đặc biệt nên người ta đã đề
ra nhiều thuật toán giải hiệu quả. Một trong số đó là thuật toán thế vị.
Thuật toán này được ta xem xét ở phần sau.
Thông thường khi giải bài toán vận tải 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).
Bảng 1.1. Bảng vận tải
Hình 1.1:
Trong đó c = (c11 , …, c1n , x21 , …, c2n , …, cm1 , …, cmn )T là véctơ hệ số
mục tiêu của bài toán vận tải. Bảng gồm m hàng (i = 1, 2, …, m) và n
cột j = (1, 2, …, n). Chỗ giao nhau ở hàng i, cột j kí hiệu là ô (i; j). Mỗi
10Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
8
hàng tương ứng với một trạm phát, mỗi cột tương ứng với một trạ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) biểu thị tuyến đường
vận chuyển từ trạm phát i đến trạm thu j . (Đặt cij = ∞ nếu không thể
chuyển hàng từ i đến j ).
Định nghĩa 1.1. Ta gọi dây chuyền là tập hợp các ô có dạng
(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 ) .
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 trong dây chuyền ở trên cùng một hàng
hay cùng một cột, và số ô trên mỗi dây chuyền có thể chẵn hay lẻ. Một
chu trình bao giờ cũng gồm một số chẵn các ô.
Ví dụ 1.1. Chu trình.
Hình 1.2:
Ta có một số định lý và hệ quả quan trọng sau.
Đị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 tạo thành chu trình.
11Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
9
T một chu trình duy nhất.
1.2
Phương pháp tìm phương án cực biên ban đầu
1.2.1
Phương pháp min cước
Trong bảng vận tải (Bảng 1.1), ta chọn ô (p; q) sao cho cpq = min {cij : ∀(i; j)}.
Nếu cực tiểu đạt tại nhiều ô thì ta chọn một ô bất kỳ trong số các ô đó.
Sau đó phân phối hàng nhiều nhất có thể theo tuyến p → q , nghĩa là đặt
xpq = min {ap , bq } .
Trừ lượng hàng vừa phát vào khả năng thu, phát của hàng p và cột q .
Tiếp đó, ta xóa hàng p nếu điểm phát p đã 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 đồng thời cả hai. Trong bảng còn lại, ta lại tìm
ô có cước phí nhỏ nhất và phân phối tối đa lượng hàng còn lại vào ô này
(lượng này có thể bằng 0). Phương án x thu được có đúng m + n − 1 ô
đã phân hàng, nó là một phương án cực biên vì các ô đã chọn không tạo
thành chu trình.
Ví dụ 1.2. Tìm phương án cực biên của bài toán vận tải.
12Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
10
Bài toán: “Cần vận chuyển xi măng từ 3 kho K1 , K2 , K3 tới 4 công
trường xây dựng T1 , T2 , T3 , T4 . Cho biết lượng xi măng có ở mỗi kho,
lượng xi măng cần ở mỗi công trường va giá cước vận chuyển (ngàn đồng)
một tấn xi măng từ mỗi kho tới mỗi công trường như sau:
Bảng 1.2.
Vấn đề là tìm kế hoạch vận chuyển xi măng từ các kho tới các công
trường sao cho mọi kho phát hết lượng xi măng có, mọi công trường nhận
đủ lượng xi măng cần và tổng chi phí vận chuyển là nhỏ nhất?”
Cước phí nhỏ nhất trong bảng là 15 đạt tại hai ô (2; 1) và (2; 4). Ta chọn
ô thứ nhất và phân vào ô này lượng hàng x21 = min {200, 130} = 130.
Cột 1 đã nhận đủ hàng nên bị loại (không phân hàng vào ô đó nữa). Hàng
2 chỉ còn lại lượng phát a02 = 200 − 130 = 70.
Trong bảng còn lại (ba cột cuối), ta chọn ô (2; 4) có cước phí nhỏ
nhất (bằng 15) và phân vào ô này lượng hàng x24 = min {70, 140} = 70.
Lúc này hàng 2 đã hết hàng nên bị loại. Cột 4 còn thiếu lượng hàng
b04 = 140 − 70 = 70.
Trong bảng còn lại (ba cột cuối hàng 1 và 3), ta chọn ô có cước phí nhỏ
nhất (bằng 18) và phân vào ô này lượng hàng x12 = min {170, 160} = 160.
Cột 2 đã nhận đủ hàng nên bị loại. Hàng 1 còn lại lượng phát a01 =
170 − 160 = 10.
13Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
11
Tiếp đó, ta phân vào ô (1; 3) lượng hàng x13 = min {10, 120} = 10.
Đến đây hàng 1 cũng hết hàng, chỉ có hàng 3 là còn hàng. Cuối cùng, ta
phân vào hai ô cuối của hàng này lượng hàng x13 = 120 − 10 = 110 và
x34 = 180 − 110 = 70. Đến đây mọi hàng (cột) đã phát hết (nhận đủ)
hàng, ta đặt xij = 0 đối với mọi ô (i, j) còn lại.
Kết quả ta nhận được phương án cực biên cho ở bảng (1.2). Giá trị
hàm mục tiêu tương ứng bằng 12950. Sau này ta sẽ thấy giá trị cực tiểu
fmin = 12140.
1.2.2
Phương pháp góc tây bắc
Trước hết ta lập bảng vận tải T với các số liệu ai , bj , cij , i = 1, …, m, j =
1, …, n.
Bắt đầu từ ô ở vị trí góc tây bắc của bảng vận tải T (ô (1; 1)), ta điền
lượng hàng x11 lớn nhất có thể vào đó, tức là chuyển một lượng hàng lớn
nhất có thể từ điểm xuất phát 1 đến điểm thu 1. Dễ thấy
x11 = min {a1 , b1 } .
Có một trong ba khả năng sau có thể xảy ra:
* If x11 = a1 < b1
Then (điểm phát 1 đã hết hàng, điểm thu 1 còn cần b1 − a1 đơn
vị hàng) Xóa hàng thứ nhất của bảng T ta thu được bảng T 0 gồm
(m − 1) hàng và n cột với lượng phát, thu tương ứng:
a0i = ai i = 2, 3, …, m,
b01 = b1 − x11 = b1 − a1 ; b0j = bj j = 2, 3, …, n;
* If x11 = b1 < a1
Then (điểm phát 1 còn dư a1 − b1 đơn vị hàng, điểm thu 1 đã thỏa
mãn nhu cầu) Xóa cột thứ nhất của bảng T ta thu được bảng T 0 gồm
m hàng và (n − 1) cột với lượng phát, thu tương ứng:
a01 = a1 − x11 = a1 − b1 ; a0i = ai i = 2, 3, …, m,
b0j = bj j = 2, 3, …, n,
14Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
12
* If x11 = b1 = a1
Then (điểm phát 1 đã hết hàng, điểm thu 1 đã thỏa mãn nhu cầu )
Ta quy ước chỉ xóa cột thứ nhất của bảng T ta thu được bảng T 0
gồm m hàng và (n − 1) cột với lượng phát, thu tương ứng:
a01 = 0 a01 = ai i = 2, 3, …, m,
b0j = bj , j = 2, 3, .., n;
Đối với bảng T 0 , ta lại thực hiện thủ tục chuyển hàng như đã áp dụng
đối với bảng T : Bắt đầu từ ô ở góc tây bắc của bảng T 0 , xác định khối
lượng vận chuyển lớn nhất có thể (khối lượng hàng có thể bằng 0) từ điểm
phát đến điểm thu tương ứng, tức điền lượng hàng vận chuyển lớn nhất có
thể vào ô này… Cứ tiếp tụ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 phương án cực
biên gồm m + n − 1 ô được chọn, không tạo thành chu trình. Những ô
(i; j) không được phân phối hàng có xij = 0.
Ví dụ 1.3. Xét bài toán vận tải với véctơ lượng phát a, lượng thu b và
ma trận chi phí C như sau
0
0 10 70
Kết quả tìm phương án cực biên ban đầu x0 theo phương pháp góc tây
bắc được trình bày ở bảng trên. Các thành phần dương của phương án x0
được ghi vào góc dưới bên phải mỗi ô tương ứng(các thành phần bằng 0
bỏ qua không ghi). Trình tự phân phối hàng theo chiều mũi tên (đường
nét đứt). Ta thấy rằng, phương án x0 này chính là phương án cực biên của
bài toán.
Nhận xét 1.1. Theo phương pháp góc tây bắc, sau mỗi lần phân phối
hàng, ta sẽ xóa đi được 1 hàng (hoặc 1 cột) của bảng. Do đó, đúng sau
m + n − 1 lần phân phối thủ tục trên phải kết thúc (do ở lần cuối ta xóa
15Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
13
được cả hàng lẫn cột) và phương án xây dựng theo phương pháp góc tây
bắc sẽ có không quá m + n − 1 thành phần dương.
1.3
Tiêu chuẩn tối ưu
Đối ngẫu của bài toán vận tải ban đầu (bài toán (1.1)-(1.4)) là
g(y) =
ai ui +
i=1
bj vj → max
(1.8)
j=1
với điều kiện
ui + vj ≤ cij , i = 1, …, m, j = 1, …, n,
(1.9)
ui + vj ≤ cij , ∀(i; j) ∈ T
(1.10)
.ui + vj = cij , ∀(i; j) ∈ G(x0 ).
(1.11)
Giả sử x0 là phương án cực biên không suy biến. Ta có các véctơ
ui + vj = cij , (i; j) ∈ G(x0 )
có m + n − 1 phương trình độc lập tuyến tính với nhau và m + n biến
ui , i = 1, …, m, và vj , j = 1, …, n. Do đó để giải hệ này, có thể cho một
16Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
14
biến giá trị tùy ý (thông thường cho u1 = 0) và các ẩn còn lại được xác
định duy nhất bằng phương pháp thế. Như vậy, mỗi phương án cực biên
không suy biến x0 = (x0ij ) tương ứng với một bộ số ui , i = 1, …, m và
(1.12)
thì x0 không là phương án tối ưu và từ x0 ta chuyển đến được một phương
án cực biên x1 tốt hơn x0 , tức
1.4
Thuật toán thế vị
Như đã trình bày ở trên, thuật toán thế vị giải bài toán vận tải xuất
phát từ một phương án cực biên. Việc xác định một phương án cực biên
của bài toán vận tải đơn giản hơn rất nhiều so với việc tìm phương án cực
biên của một bài toán quy hoạch tuyến tính tổng quát và việc đó được
trình bày ở trên. Ở đây ta giới thiệu thuật toán thế vị giải bài toán vận tải
không suy biến, tức là các phương án cực biên ban đều có đúng (m+n−1)
thành phần dương, với giả thiết đã biết trước một phương án cực biên.
Thuật toán thế vị
Bước khởi tạo: Dùng phương pháp min cước (hay phương pháp góc tây
bắc) tìm phương án cực biên không suy biến x0 = (x0ij ). Tập ô chọn tương
17Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
15
u1 = 0, ui + vj = cij , ∀(i; j) ∈ G(xk−1 )
Bước 2:Tính các ước lượng: ∆ij = ui + vj − cij , ∀(i; j) ∈
/ G(xk−1 ).
(Để ý là ta luôn có ∆ij = ui + vj − cij = 0, ∀(i; j) ∈ G(xk−1 ) ) Điền
ước lượng ∆ij với (i; j) ∈
/ G(xk−1 ) vào góc bên phải của ô (i; j).
Bước 3: Kiểm tra tối ưu:
If ∆ij ≤ 0, ∀(i; j) ∈
/ G(xk−1 ).
Then dừng thuật toán (x0 là phương án tối ưu theo Định lý(1.3)).
Else Chuyển bước 4.
Bước 4: Điều chỉnh phương án (nếu cần)
Ta có G(xk ) := G(xk−1 ) {(p; q)} ∪ {(r; s)} và G(xk ) không chứa chu
trình, tức là xk là phương án cực biên.
4f) Gán 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.
18Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
16
Mệnh đề 1.1. Nếu các lượng phát ai , i = 1, …, m và các lượng thu bj
, j = 1, …, n đều là các số nguyên thì bài toán vận tải ban đầu sẽ có nghiệm
tối ưu với các thành phần đều nguyên.
Chú ý 1.1. Trong trường hợp bài toán vận tải suy biến, có hai dấu hiệu
để nhận biết:
* 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 cực biên mới xk và xkrs = 0 còn ô (p; q) ∈ K2 ứng
k
với xk−1
pq = 0 sẽ trở thành ô loại đối với phương án x . Tuy nhiên, kết
quả điều chỉnh không làm thay đổi phương án cực biên (xk − 1 = xk )
mà chỉ làm thay đổi tập véctơ cơ sở của phương án đó.
* 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.
Chú ý 1.2. (Dấu hiệu bài toán có phương án tối ưu duy nhất và không
duy nhất)
* Nếu phương án cực biên không suy biến x0 thỏa mãn tiêu chuẩn
∆ij = ui + vj − cij < 0, ∀(i; j) ∈
/ G(x0 )
thì đó là phương án tối ưu duy nhất của bài toán vận tải.
19Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
17
1.5
Ví dụ minh họa
Ví dụ 1.4. Giải bài toán vận tải bằng thuật toán thế vị với véctơ cung a,
véctơ cầu b và ma trận cước phí C như sau:
0
130 70
0
Giải:
Bài toán này có m = 3 điểm phát và n = 4 điểm thu và thỏa mãn điều
kiện cân bằng thu phát (1.5). Phương án cực biên ban đầu x0 được tìm
theo phương pháp min cước có tập ô chọn là
G x0 = {(1; 1) , (1; 4) , (2; 1) , (2; 3) , (3; 2) , (3; 3)} ,
gồm 6 = m + n − 1 ô không chứa chu trình và giá trị hàm mục tiêu
−10
0
0
−9
http://www.lrc-tnu.edu.vn
Bạn đang xem bài viết Khắc Phục Hiện Tượng Suy Biến Trong Bài Toán Vận Tải (2) trên website Zdungk.com. Hy vọng những thông tin mà chúng tôi đã chia sẻ là hữu ích với bạn. Nếu nội dung hay, ý nghĩa bạn hãy chia sẻ với bạn bè của mình và luôn theo dõi, ủng hộ chúng tôi để cập nhật những thông tin mới nhất. Chúc bạn một ngày tốt lành!