Khắc Phục Hiện Tượng Suy Biến Trong Bài Toán Vận Tải (2)

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!