ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN TRÀ GIANG
BÀI TOÁN VẬN TẢI
PHÂN TUYẾN TÍNH
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - Năm 2012
Số 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 HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
NGUYỄN TRÀ GIANG
BÀI TOÁN VẬN TẢI
PHÂN TUYẾN TÍNH
Chuyên ngành:
TOÁN ỨNG DỤNG
Mã số : 60.46.36
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 2012
Số 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
Mục lục
Mục lục . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
i
LỜI NÓI ĐẦU
1
Nội dung
4
1 BÀI TOÁN VẬN TẢI VỚI HÀM MỤC TIÊU TUYẾN
TÍNH
4
1.1
Bài toán và các tính chất . . . . . . . . . . . . . . . . . . .
4
1.2
Tìm phương án cực biên ban đầu
9
1.3
Tiêu chuẩn tối ưu . . . . . . . . . . . . . . . . . . . . . . . 13
1.4
Phương pháp thế vị . . . . . . . . . . . . . . . . . . . . . . 17
1.5
Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 19
. . . . . . . . . . . . . .
2 BÀI TOÁN VẬN TẢI VỚI HÀM MỤC TIÊU PHÂN TUYẾN
TÍNH
25
2.1
Phát biểu bài toán . . . . . . . . . . . . . . . . . . . . . . . 25
2.2
Phương pháp giải . . . . . . . . . . . . . . . . . . . . . . . 28
2.3
Ví dụ minh họa . . . . . . . . . . . . . . . . . . . . . . . . 38
2.4
Bài toán đối ngẫu . . . . . . . . . . . . . . . . . . . . . . . 45
Kết luận
50
Tài liệu tham khảo
52
Số 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
LỜI NÓI ĐẦU
Bài toán vận tải đã khá quen thuộc trong lý thuyết qui hoạch tuyến
tính. 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 giải 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ị, phương pháp qui không ô chọn, phương pháp thu hẹp chính tắc.
Có thể xét mở rộng bài toán vận tải theo nhiều hướng khác nhau, như
thay đổi điều kiện ràng buộc: vận tải khi không có cân bằng cung cầu
(cung vượt quá cầu hoặc cầu vượt quá cung), vận tải có trung chuyển, vận
tải có hạn chế năng lực thông qua, vận tải có vận chuyển ngược; hoặc thay
đổi dạng của hàm mục tiêu: vận tải với hàm mục tiêu phân tuyến tính (tỉ
số của hai hàm tuyến tính), vận tải với hàm mục tiêu lồi hay lõm, v.v ...
Chẳng hạn, bài toán vận tải phân tuyến tính tìm phương án vận chuyển
làm cực tiểu tỉ số của chi phí vận chuyển hàng hoá trên tổng lợi nhuận
thu được khi vận chuyển toàn bộ số hàng đó. Tuy hàm mục tiêu của bài
toán là phi tuyến, nhưng các ràng buộc của bài toán vẫn có cùng cấu trúc
như của bài toán vận tải thông thường, vì thế có thể vận dụng các phương
pháp giải bài toán vận tải đã biết cho bài toán vận tải mở rộng.
Bài toán vận tải tuyến tính có dạng một qui hoạch tuyến tính chính
tắc, vì thế các kiến thức về qui hoạch tuyến tính chính tắc nói chung đều
có thể áp dụng vào bài toán vận tải tuyến tính nói riêng. Ràng buộc của
bài toán vận tải tuyến tính và phân tuyến tính có cấu trúc vận tải nên
Số 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
miền ràng buộc của các bài toán này có các tính chất đặc biệt. Có thể khâi
thác các tính chất đó để xây dựng thuật toán giẩi riêng, hiệu quả.
Luận văn này đề cập tới bài toán vận tải với hàm mục tiêu tuyến tính
và phân tuyến tính: giới thiệu nội dung, mô hình và các tính chất cơ bản
của bài toán; giới thiệu thuật toán thế vị giải bài toán vận tải tuyến tính
và dạng mở rộng của nó để giải bài toán vận tải phân tuyến tính. Vấn đề
đối ngẫu và các quan hệ đối ngẫu của bài toán vận tải tuyến tính và phân
tuyến tính cũng được đề cập tới.
Nội dung luận văn được chia thành hai chương.
Chương 1 với tiêu đề "Bài toán vận tải với hàm mục tiêu tuyến tính"
trình bày nội dung và các tính chất cơ bản của bài toán vận tải tuyến tính.
Tiếp đó, đề cập tới phương pháp "min cước" và phương pháp "góc Tây
- Bắc" để 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 hiệu quả 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.
Các kiến thức về bài toán vận tải nói chung và thuật toán thế vị nói
riêng sẽ cần đến ở chương sau, khi xét bài toán vận tải phân tuyến tính.
Chương 2 với tiêu đề "Bài toán vận tải với hàm mục tiêu phân tuyến
tính" đề cập tới một mở rộng bài toán vận tải tuyến tính, bằng cách thay
hàm mục tiêu tuyến tính bằng hàm mục tiêu phân tuyến tính (tỉ số của
hai hâm tuyến tính), hàm này có tính chất đơn điệu theo từng phương.
Dựa vào cấu trúc đặc biệt của bài toán, chương này nêu ra điều kiện để
phương án của bài toán là tối ưu và nêu thuật toán thế vị mở rộng giải
bài toán. Thuật toán có kèm theo ví dụ số để minh họa. Cuối chương đề
cập tới bài toán đối ngẫu của bài toán vận tải phân tuyến tính và nêu
các quan hệ đối ngẫu giữa hai bài toán gốc và đối ngẫu, tương tự như lý
thuyết đối ngẫu trong qui hoạch tuyến tính.
Do thời gian và kiến thức còn hạn chế nên luận văn này mới chỉ đề cập
Số 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
tới những nội dung cơ bản của bài toán vận tải phân tuyến tính, chưa đi
sâu vào các chi tiết thực thi thuật toán. Trong quá trình viết luận văn
cũng như trong xử lý văn bản chắc chắn không tránh khỏi những sai sót
nhất định. Tác giả luận văn rất mong nhận được sự góp ý của các thầy cô
và các bạn đồng nghiệp để luận văn được hoàn thiện hơn.
Nhân dịp này, tác giả xin bày tỏ lòng biết ơn sâu sắc đến thầy hướng
dẫn GS-TS Trần Vũ Thiệu đã tận tình giúp đỡ trong suốt quá trình làm
luận văn.
Tác giả xin trân trọng cảm ơn các thầy, cô giáo Trường Đại học Khoa
học- Đại học Thái Nguyên, Viện Toán học-Viện Khoa học và Công nghệ
Việt Nam, đã giảng dạy và 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 07 năm 2012.
Người thực hiện
Nguyễn Trà Giang
Số 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 VỚI HÀM
MỤC TIÊU TUYẾN TÍNH
Chương này xét bài toán vận tải với hàm mục tiêu 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 áp dụng rộng rãi trong thực
tiễn.
Mục 1.1 giới thiệu mô hình bài toán và các tính chất cơ bản. Mục 1.2
nêu phương pháp min cước và phương pháp góc Tây-Bắc tìm phương án
cực biên ban đầu của bài toán. Điều kiện tối ưu được đưa ra ở Mục 1.3 và
thuật toán thế vị cùng cơ sở lý luận của thuật toán được trình bày ở Mục
1.4. Ví dụ số được xây dựng ở Mục 1.5.
Nội dung của chương chủ yếu tham khảo từ các tài liệu [1] , [2] và [4].
1.1
Bài toán và các tính chất
Mô hình toán học của bài toán vận tải có dạng như sau:
m X
n
X
cij xij → min (cực tiểu tổng chi phí vận chuyển)
i=1 j=1
với các điều kiện:
Số 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.1)
5
n
X
xij = ai , i = 1, 2, ..., m (mọi điểm phát giao hết hàng)
(1.2)
j=1
m
X
xij = bj , j = 1, 2, ..., n (mọi điểm thu nhận đủ hàng)
(1.3)
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à kho hàng (điểm phát), n là 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 đến đ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:
a1 + 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 của m × n biến số xij như sau:
Số 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
x11 + x12 + ... + x1n
x21 + x22 + ... + x2n
...
...
xm1 + xm2 + ... + xmn
x11
+ x21
...
+ xm1
x12
+ x22
...
+ xm2
...
...
...
...
x1n
+ x2n
... + xmn
= a1 ,
= a2 ,
= am ,
= b1 ,
= b2 ,
= bn .
Ký hiệu A là ma trận hệ số của hệ phương trình trên (gồm m + n hàng
và m × n cột).
x = (x11 , x12 , ..., x1n , x21 , x22 , ..., x2n , ..., xm1 , xm2 , ..., xmn )T
là véctơ cột m × n thành phần,
c = (c11 , c12 , ..., c1n , c21 , c22 , ..., c2n , ..., cm1 , cm2 , ..., cmn )T
là véc tơ cột m × n thành phần,
b = (a1 , a2 , ..., am , b1 , b2 , ..., bn )T
là 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 quy hoạch
tuyến tính dạng chính tắc:
f = < c, x > → min,
Ax = b, x ≥ 0.
Ta gọi Aij là véctơ cột của ma trận A ứng với biến xij . Dễ thấy rằng
véctơ này có hai thành phần bằng 1 tại dòng thứ i và dòng thứ m + j, còn
các thành phần khác bằng 0.
Véctơ x thỏa mãn (1.2) - (1.4) gọi là một phương án của bài toán vận
tải. Một phương án đạt cực tiểu (1.1) gọi là phương án tối ưu hay lời giải.
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
ma trận A ứng với các xij > 0 là độc lập tuyến tính.Sau đây ta sẽ giả thiết
là có điều kiện cân bằng thu phát (1.5).
Số 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
Do bài toán vận tải có m+n ràng buộc chính, nên ta nghĩ rằng mỗi
phương án cực biên cũng có m+n thành phần dương, nhưng thực tế nó chỉ
có nhiều nhất m+n-1 thành phần dương, vì trong số các ràng buộc này có
một ràng buộc là thừa (có thể bỏ đi mà không làm ảnh hưởng tới lời giải
của bài toán). Một phương án cực biê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 = {(i, j) : xij > 0} bằng m+n-1, gọi là suy
biến nếu |G| < m+n-1.
Để cho gọn, 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 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 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.
Bảng 1.1. Bảng vận tải
Thu
b1
···
bj
···
bn
Phat
a1
c11
..
.
···
..
.
..
.
···
cin
xij
..
.
···
cm1
x1n
···
cij
xi1
..
.
c1n
x1j
···
ci1
..
.
am
···
x11
..
.
ai
···
c1j
···
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
..
.
···
cmj
xm1
xin
···
xmj
cmn
xmn
http://www.lrc-tnu.edu.vn
8
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 quan
trọng sau đây.
Định lý 1.1.
a)Bài toán vận tải luôn luôn có phương án tối ưu.
b) Hạng của hệ phương trình (1.2) - (1.3) của bài toán bằng m + n 1.
c) Nếu lượng cung cầu ai , bj là các số nguyên thì bài toán này sẽ có lời
giải nguyên.
Có thể dùng các phương pháp của quy 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ả. Trong số đó có thuật toán thế vị sẽ xét ở
mục 1.4 dưới đây. Đị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. Dãy ô đánh dấu "•" trong Hình 1.1 a) và b) lập thành các dây
chuyền, còn các ô với dấu • trong Hình 1.1 c) - e) lập thành các chu trình.
a)
b)
c)
d)
Hình 1.1 Dây chuyền: a) - b).Chu trình: c) - e).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
e)
9
Cho G là một tập hợp ô bất kỳ của bảng vận tải. Một ô thuộc G gọi
là ô treo nếu nó là ô duy nhất của G trên hàng hay trên cột của ô đó. Với
tập hợp ô cho ở Hình 1.1 a) thì ô (1,1) và ô (4,3) là các ô treo. Nếu loại
khỏi G ô treo (1,1) thì ô (1,2) sẽ trở thành ô treo của tập hợp ô còn lại.
Ta có mối liên hệ quan trọng sau đây.
Định lý 1.2. Hệ véctơ {Aij : (i, j) ∈ G} của bài toán vận tải (1.1) - (1.4)
là độc lập tuyến khi và chỉ khi tập hợp các ô thuộc G không tạo thành chu
trình.
Hệ quả 1.1. Véctơ x = {xij }m×n là một phương án cực biên của bài toán
khi và chỉ khi tập hợp các ô (i, j) mà xij > 0 không lập thành chu trình.
Hệ quả 1.2. Giả sử T là một tập hợp gồm m + n - 1 ô của bảng vận tải,
không tạo thành chu trình. Khi đó, mỗi ô (p, q) ∈
/ T sẽ tạo với các ô thuộc
T một chu trình duy nhất.
Chu trình nói tới trong hệ quả trên có thể tìm bằng cách loại dần các ô
treo của tập hợp ô G = T ∪ {(p, q)}. Ví dụ, tập hợp ô T ở Hình 1.1 b) gồm
m + n -1 = 7 ô, không tạo thành chu trình. Bổ sung vào T ô (4, 2) ∈
/T
(ô đánh dấu ? ) ta được G = T ∪ {(4, 2)}. Khi đó, bằng cách loại khỏi G
ô treo (3,3) (ô duy nhất của G trên cột 3), rồi ô treo (3,2) đối với tập ô
G0 = G\{3, 3} (ô duy nhất của G’ trên hàng 3), ta nhận được chu trình
(gồm 6 ô):
C = {(4, 2), (4, 1), (2, 1), (2, 4), (1, 4), (1, 2)}
1.2
Tìm phương án cực biên ban đầu
Để giải bài toán vận tải (1.1) - (1.4) với điều kiện (1.5) theo phương
pháp thế vị, trước hết ta cần biết một phương án cực biên của bài toán.
Có nhiều cách để tìm một phương án như thế. Sau đây là một vài phương
pháp thông dụng và có hiệu quả.
a) Phương pháp min cước
Số 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
Trong bảng vận tải 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ân phối 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 đã phát hết hàng, hoặc cột thu
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 chọn ô 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 ô đã được 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.
Tìm phương án cực biên ban đầu của bài toán vận tải với các số liệu
cho ở bảng 1.2.
Bảng 1.2. Phương án cực biên xây dựng theo phương pháp min cước
Thu
130
160
120
140
Phát
20
18
22
25
170
160
15
25
10
30
15
200
130
45
70
30
40
35
180
110
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
70
http://www.lrc-tnu.edu.vn
11
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ỉ
0
còn lại lượng phát a1 = 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 đã phát hết hàng nên bị loại. Cột 4 chỉ còn thiếu lượng hàng
0
b4 = 140 − 70 = 70.
Trong bảng còn lại (ba cột cuối hàng 1 và 3), ta chọn ô (1,2) 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 chỉ còn lại lượng phát
0
a1 = 170 − 160 = 10.
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 x33 = 120 − 10 = 110 và
x34 = 180 − 110 = 140 − 70 = 70. Đến đây mọi hàng (cột) đã phát hết
(nhận đủ) hàng, ta dặt xij = 0 đối với mọi ô (i,j) còn lại.
Kết quả ta được phương án cực biên cho ở bảng trên. 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.
b) 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 T (ô(1,1)), ta điền lượng hàng
x11 lớn nhất có thể vào đó, tức cho chuyển một lượng hàng lớn nhất có
thể từ điểm 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:
Số 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
♦ Nếu x11 = a1 < b1 thì đ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’
gồm (m - 1) hàng và n cột với lượng phát, thu tương ứng:
0
ai = ai ; i = 2, 3, ..., m,
0
0
b1 = b1 − x11 = b1 − a1 ; bj = bj , j = 2, 3, ..., n;
♦ Nếu x11 = b1 < a1 thì điểm phát 1 còn 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’ gồm m hàng và n-1 cột với lượng phát, thu tương ứng:
0
0
a1 = a1 − x11 = a1 − b1 ; ai = ai , i = 2, 3, ..., m,
0
bj = bj ; j = 2, 3, ..., n;
♦ Nếu x11 = b1 = a1 thì đ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’ gồm m hàng và n - 1 cột với lượng phát, thu tương ứng:
0
0
a1 = 0; ai = ai ; i = 2, 3, ..., m,
0
b1 = bj , j = 2, 3, ..., n;
• Đới với bảng T’, 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’, xác định khối
lượng vận chuyển lớn nhất có thể (khối lượng hàng này 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 đến khi loại hết được tất cả các hàng
và các cột của bảng vận tải. Những ô (i, j) không được phân phối hàng có
xij = 0
Ví dụ: Xét lại bài toán vận tải cho ở Ví dụ 1.2
Bảng 1.3
Số 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
bj
130
ai
160
20
120
18
140
22
25
30
15
170
130
15
40
25
200
120
45
30
80
40
35
180
40
140
Kết quả tìm phương án cực biên xuất phát x0 theo phương pháp góc tây
bắc được trình bày ở bảng 1.3. 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 đứt
nét). Giá trị hàm mục tiêu tương ứng bằng 15200.
1.3
Tiêu chuẩn tối ưu
Xét bài toán vận tải
min f (x) =
m P
n
P
cij xij (P T )
i=1 j=1
v.đ.k
n
P
xij = ai , i = 1, ..., m
j=1
m
P
xij = bj , j = 1, ..., n
i=1
xij ≥ 0, i = 1, ..., m, j =
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1, ..., n.
http://www.lrc-tnu.edu.vn
14
Bài toán đối ngẫu của bài toán này là
max g(y) =
m
P
i=1
ai ui +
n
P
bj vj (DT )
j=1
với điều kiện ui + vj ≤ cij , i = 1, ..., m, j = 1, ..., n,
trong đó y = (u1 , ..., um , v1 , ..., vn )T .
Để đơn giản việc trình bày, giả sử rằng bài toán (1.1) - (1.4) không suy
biến, tức mọi phương án cực biên của nó đều không suy biến. Cách nhận
biết và khắc phục khi gặp phương án cực biên suy biến sẽ trình bày ở phần
sau
Cho phương án x0 . Ký hiệu G(x0 ) = {(i, j) ∈ T x0ij > 0}. Sau đây là điều
kiện cần và đủ để phương án x0 = (x0ij ) là phương án tối ưu.
Phương án x0 = (xij 0 ) của bài toán vận tải là phương án tối ưu khi và
chỉ khi tồn tại các số ui , i = 1, ... , m, và vj , j = 1, ..., n thỏa mãn
ui + vj ≤ cij , ∀(i, j) ∈ T
(1.6)
ui + vj = cij , ∀(i, j) ∈ G(x0 )
(1.7)
Chứng minh.
(⇒) Giả sử phương án x0 = (x0ii ) là phương án tối ưu của bài toán vận
tải (1.1) - (1.4). Theo định lý đối ngẫu mạnh, bài toán đối ngẫu có phương
án tối ưu y 0 = (u1 , ..., um , v1 , ..., vn )T . Do y 0 là phương án chấp nhận được
của bài toán đối ngẫu nên nó thỏa mãn mọi ràng buộc của bài toán, tức
ui + vj ≤ cij ; i = 1, ..., m; j = 1, ..., n.
Đây chính là điều kiện (1.6). Hơn nữa, vì x0 là phương án tối ưu của bài
toán gốc và y 0 là phương án tối ưu của bài toán đối ngẫu nên theo định
lý về độ lệch bù ta có
c − AT y 0 , x0 = 0 ⇒ nếu x0ij > 0 thì ui + vj = cij
Số 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
hay điều kiện (1.7) được thỏa mãn.
(⇐) Cho phương án x0 = (x0ii ). Giả sử tồn tại các số ui ; i = 1, ..., m và
vj ; j = 1, ..., n thỏa mãn (1.6) và (1.7). Ta phải chứng minh x0 là phương
án tối ưu. Thật vậy, do có (1.7) và do x0ij = 0 với (i, j) ∈
/ G(x0 ) nên giá trị
hàm mục tiêu tại x0 là
0
f (x ) =
m X
n
X
cij x0ij
=
i=1 j=1
m X
n
X
(ui + vj )x0ij
(1.8)
i=1 j=1
Giả sử x = (xij ) là một phương án bất kỳ của bài toán vận tải. Ta có
f (x) =
m P
n
P
=
cij xij
i=1 j=1
m
n
P
P
=
i=1
m
P
=
i=1
m
P
=
i=1
≥
xij +
ui
i=1
m
(1.8) P
m P
n
1.6 P
vj
j=1
j=1
ui ai +
n
P
(ui + vj )xij
i=1 j=1
n
m
P
P
xij
i=1
vj bj (vì x là một phương án)
j=1
ui
n
P
j=1
x0ij +
n
P
j=1
vj
m
P
i=1
x0ij (vì x0 là một phương án)
(ui + vj )x0ij = f (x0 )
Vậy x0 là phương án tối ưu của bài toán vận tải đang xét.
Chú ý 1.1 : Giả sử x0 là phương án cực biên không suy biến. Ta có các
véc tơ {Aij (i, j) ∈ G(x0 ) } độc lập tuyến tính và G(x0 ) = m + n − 1.
Do đó hệ (1.8) tương ứng
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
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 các bộ số ui , i = 1, ..., m và
vj , j = 1, ..., n. (sai khác một hằng số) thỏa mãn (1.8). Ta gọi các số ui , vj
Số 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
này là các thế vị. Các đại lượng ∆ij := ui + vj − cij được gọi là các ước
lượng. Khi đó, điều kiện (1.4) được viết lại là
∆ij ≤ 0, ∀(i, j) ∈ T
Định lý 1.3. Giả sử x0 là phương án cực biên không suy biến của bài
toán vận tải và ui , vj , i = 1, ..., m, j = 1, ..., n là bộ các thế vị tương ứng
với nó. Nếu
∃ ô (ik , jk ) ∈
/ G(x0 ) sao cho ∆ik jk > 0
(1.9)
thì x0 không phải 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
f (x1 ) < f (x0 )
Cách xây dựng x1 như sau:
Do x0 là phương án cực biên không suy biến nên G(x0 ) = m + n −
1 và G(x0 ) không chứa chu trình. Tập G(x0 ) ∪ {(ik , jk )} chứa một chu
trình K duy nhất đi qua (ik , jk ). Lần lượt đánh dấu các ô trong K bởi các
dấu + và -, xuất phát từ ô (ik , jk ) với dấu +, sao cho không có hai ô nào
cạnh nhau trong K lại dược đánh dấu bởi cùng một dấu. Ký hiệu
K + := {các ô trong K được đánh dấu +},
K − := {các ô trong K được đánh dấu -},
Xây dựng x1 = (x1ij ) theo công thức
0
+
xij + θ nếu (i, j) ∈ K
x1ij = x0ij − θ nếu (i, j) ∈ K −
0
xij , nếu (i, j) ∈
/K
(1.10)
với
θ = min{x0ij |(i, j) ∈ K − } = x0ir jr .
Số 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.11)
17
Vì x0 là phương án cực biên không suy biến nên θ > 0.
Có thể thấy x1 là một phương án cực biên của bài toán với x1ir jr = θ > 0
và G(x1 ) = (G(x0 )\{(ir ,jr )}) ∪ {(ik ,jk )}
Hơn nữa,
f (x1 ) = f (x0 ) − θ∆ik jk < f (x0 ).
Ô (ik , jk ) được gọi là ô điều chỉnh và K được gọi là chu trình điều chỉnh.
1.4
Phương pháp thế vị
Mục này giới thiệu phương pháp thế vị giải bài toán vận tải. Thuật
toán xuất phát từ một phương án cực biên ban đầu không suy biến x0 .
Do bài toán vận tải luôn có nghiệm nên từ x0 chỉ có một trong hai trường
hợp sau xảy ra:
i) Nếu x0 thỏa mãn tiêu chuẩn tối ưu thì dừng thuật toán: x0 là phương
án tối ưu của bài toán.
ii) Ngược lại, ta chuyển đến phương án cực biên x1 thỏa mãn f (x1 ) ≤
f (x0 ); Gán x0 := x1 và lặp lại quá trình tính toán với x0 mới.
Thuật toán thế vị
Bước khởi tạo. Giả sử đã biết phương án cực biên không suy biến x0 =
(x0 ). Tập ô chọn tương ứng với x0 là G(x0 ) = {(i, j) x0 > 0 } gồm m+nij
ij
1 phần tử và không chứa chu trình.
Bước 1. Xác định các thế vị ui , i = 1, ..., m, và vj , j = 1, ..., n tương ứng
với phương án cực biên x0 bằng việc giải hệ phương trình.
ui + vj = cij ∀(i, j) ∈ G(x0 ).
Bước 2. Tính các ước lượng
∆ij = ui + vj − cij ∀(i, j) ∈
/ G(x0 ) (Luôn có ∆ij = 0∀(i, j) ∈ G(x0 ))
Điền ước lượng ∆ij với (i, j) ∈
/ G(x0 ) vào góc dưới bên phải của ô (i,j).
Bước 3. (Kiểm tra điều kiện tối ưu)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
http://www.lrc-tnu.edu.vn
- Xem thêm -