Final report: Applying optimization algorithms in economics PDF

Preview

Summary

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘIVIỆN TOÁN ỨNG DỤNG VÀ TIN HỌCBÁO CÁO TIỂU LU ẬN MÔN HỌCCÁC PHƯƠNG PHÁP TỐI ƯUBÀI TOÁN VẬN T ẢIGiảng viên hướng dẫn: TS. PHẠM THỊ HOÀINhóm thực hiện: NHÓM 3HÀ NỘI – 2 021Tên Mã số sinh viên Danh sách thành viên nhóm Nguyễn Thị Xuân Hồng Nguyễn Tiến Dũng Nguyễn Quang Hiế...

Description

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI VIỆN TOÁN ỨNG DỤNG VÀ TIN HỌC

BÁO CÁO TIỂU LUẬN MÔN HỌC CÁC PHƯƠNG PHÁP TỐI ƯU BÀI TOÁN VẬN TẢI Giảng viên hướng dẫn: TS. PHẠM THỊ HOÀI Nhóm thực hiện:

NHÓM 3

HÀ NỘI – 2021

1

Danh sách thành viên nhóm 3 Tên

Mã số sinh viên

Nguyễn Thị Xuân Hồng

20185364

Nguyễn Tiến Dũng

20185340

Nguyễn Quang Hiếu

20185351

Nguyễn Thị Diệu Linh

20180815

Nguyễn Thanh Long

20185380

Nguyễn Quang Minh

20185385

Nguyễn Ngọc Thìn

20185408

Nguyễn Ngọc Quang

20185395

Nguyễn Thị Bích Ngọc

20185388

Nguyễn Thị Quý

20185396

Nguyễn Thị Lương

20173550

Nguyễn Thành Nam

20185386

Luyện Đức Mạnh

20142854

Nguyễn Văn Long

20142691

Nguyễn Tiến Vĩ

20185426

2

Mục lục I.

Tổng quan bài toán vận tải ...................................................................................................... 4

II. 1.

Thiết lập mô hình .................................................................................................................... 5

2.

Sự tồn tại của phương án tối ưu.............................................................................................. 6

III.

Một số khái niệm trong mô hình bài toán vận tải .............................................................. 7

1.

Bảng vận tải (Transportation Table)....................................................................................... 7

2.

Chu trình ................................................................................................................................. 8

IV.

V.

Mô hình toán học bài toán vận tải ....................................................................................... 5

Phương pháp thế vị giải bài toán vận tải .......................................................................... 10

1.

Cơ sở lý thuyết của phương pháp thế vị ............................................................................... 10

2.

Thuật toán thế vị ................................................................................................................... 16 2.1.

Lý thuyết thuật toán thế vị ............................................................................................ 16

2.2.

Một số chú ý ................................................................................................................. 18

2.3.

Ví dụ minh họa ............................................................................................................. 19

Kết luận.................................................................................................................................... 25

TÀI LIỆU THAM KHẢO .............................................................................................................. 26

3

I.

Tổng quan bài toán vận tải Bài toán vận tải là một trong những ứng dụng thành công và quan trọng nhất của bài toán quy hoạch tuyến tính. Theo thống kê tại Mỹ, có đến 85% các bài toán quy hoạch tuyến tính gặp trong các ứng dụng thực tế có dạng bài toán vận tải hoặc các dạng mở rộng của nó. Bài toán vận tải giải quyết vấn đề phân phối hàng hóa từ một số điểm cung cấp đến một số điểm tiêu thụ sao cho thỏa mãn các tiêu chí sau: • Tổng chi phí ít nhất • Cự ly vận chuyển nhỏ nhất • Tổng tiền lời là nhiều nhất Bài toán vận tải thường được áp dụng trong lĩnh vực lập kế hoạch để tối ưu vận chuyển hàng hóa từ đó ta xác định được vị trí xây dụng các nhà kho, cửa hàng, nhà xưởng mới.

4

II.

Mô hình toán học bài toán vận tải

1. Thiết lập mô hình Đặt vấn đề:

Ta có m điểm phát (kho hàng) với trữ lượng tương ứng của mỗi kho là!𝑎! , 𝑎" , … , 𝑎#

Ta có n điểm thu (Nơi cần vận chuyển hàng đến) với nhu cầu (Lượng hàng cần tiếp nhận) tại các điểm thu là: 𝑏! , 𝑏" , … , 𝑏$

𝑐%& là chi phí vận chuyển một đơn vị hàng hóa từ điểm phát 𝑎% đến điểm thu 𝑏& Viết dưới dạng ma trận

𝑐!! 𝐶 =!) ⋮ 𝑐#!

𝑐!" … ⋮ ⋮ 𝑐#" …

𝑐!$ ⋮ + 𝑐#$

𝑥!! 𝑥 = !) ⋮ 𝑥#!

𝑥!" ⋮ 𝑥#"

… ⋮ …

𝑥!$ ⋮ + 𝑥#$

𝑥%& là lượng hàng vận chuyển từ điểm phát 𝑎% đến điểm thu 𝑏& !

Cần xây dựng kế hoạch chở hàng để thỏa mãn các điều kiện sau: • Các điểm phát phải phát hết hàng • Các điểm thu phải thu đủ lượng hàng mong muốn • Chi phí vận chuyển là nhỏ nhất

5

Mô hình toán học (PT) min 𝑓 (𝑥 ) = ! 3 3 𝑐%& 𝑥%& #

$

%'! &'!

với điều kiện 3 𝑥%& = 𝑎% $

&'!

3 𝑥%& = ! 𝑏& #

%'!

999999 99999 𝑥%& ! ≥ 0!!!!!𝑖 = ! 1, 𝑚 , 𝑗 = ! 1, 𝑛

Vector 𝑥 = 0} và mỗi ô (𝑖, 𝑗 )! ∈ !𝐺!được gọi là một ô chọn hay ô sử dụng ; ô (𝑖, 𝑗 ) ∉ !𝐺 gọi là ô loại

Do vậy, một phương án cực biên có không quá (𝑚 + !𝑛 − 1 ) ô chọn và một phương

án cực biên không suy biến có đúng (𝑚 + !𝑛 − 1 ) ô chọn

7

2. Chu trình Định nghĩa: Một tập được sắp thứ tự các ô của bảng vận tải được gọi là chu trình nếu nó thỏa mãn đồng thời ba tính chất sau: i.

Hai ô cạnh nhau nằm trong cùng một hàng hay một cột

ii.

Không có ba ô nằm trên cùng một hàng hay một cột

iii.

Ô đầu tiên nằm trong cùng một hàng hay một cột với ô cuối cùng

Ví dụ về một vài dạng chu trình

Định lý: Phương án 𝑥 = (𝑥%& ) là phương án cực biên khi và chỉ khi tập các ô chọn !𝐺( 𝑥)= {( 𝑖, 𝑗 )! ∈ !𝑇!| 𝑥%& > 0} không chứa chu trình

Ví dụ minh họa: Cho bài toán vận tải với vecto lượng phát 𝑎 = (50, 70, 55)(, vector ( ma trận chi phí lượng thu 𝑏 = ! (30, 60, 60, 25)và

4 𝐶 = ! )5 8

7 9 2

12 7 6 1+ 9 1

8

a) Bài toán vận tải trên có nghiệm hay không? Giải: Bài toán có 3 điểm phát và 4 điểm thu

Tổng lượng phát ! ∑ "!#$ 𝑎! = 50 + 70 + 55 = 175

Tổng lượng thu ∑)&'! 𝑏& = 30 + 60 + 60 + 25 = 175

=> Tổng lượng phát bằng tổng lượng thu. Do vậy, điều kiện cân bằng thu phát được thỏa mãn, bài toán luôn có nghiệm tối ưu

0 30 20 0 b) Chứng minh rằng 𝑥 * = ! ) 0 40 30 0 + là một phương án cực biên 0 0 30 25 Giải:

- Kiểm tra các điều kiện ràng buộc:

) * !!!!∑&'! 𝑥!& = 30 + 20 + 0 + 0 = 50 = ! 𝑎! * = 0 + 40 + 30 + 0 = 70 = ! 𝑎" Q ∑)&'! 𝑥"&

và

* = 0 + 0 + 30 + 25 = 55 = ! 𝑎 ∑)&'! 𝑥+& +

+ * ⎧ !∑%'! 𝑥%! = 30 + 0 + 0 = 30 = ! 𝑏! !!!!∑+%'! 𝑥*%" = 20 + 40 + 0 = 60 = ! 𝑏" + * ⎨!!!!∑%'! 𝑥%+ = 0 + 30 + 30 = 60 = ! 𝑏+ + * ⎩ !!∑ %'! 𝑥%) = 0 + 0 + 25 = 25 = ! 𝑏!

Các điều kiện ràng buộc thỏa mãn, do đó 𝑥 * là một phương án chấp nhận được. ); (3,)3 ; (3, 4)} - Tính 𝐺 (𝑥 * ) = {(1, 1 ); ( 1, 2 ); ( 2, 2); (2, 3

Dễ thấy 𝐺 (𝑥 * ) không chứa chu trình, do vậy 𝑥 * là một phương án cực biên

c) Tính chi phí phải trả nếu thực hiện theo phương án này Giải:

𝑓( 𝑥 * )= !!4.30 + 7.20 + 9.40 + 6.30 + 9.30 + 1.25 = 1095 9

IV.

Phương pháp thế vị giải bài toán vận tải 1. Cơ sở lý thuyết của phương pháp thế vị Xét bài toán vận tải (PT)! min 𝑓(𝑥)= ! 3 3 𝑐%& 𝑥%& #

$

%'! &'!

với điều kiện 3 𝑥%& = 𝑎% $

&'!

3 𝑥%& = ! 𝑏& #

%'!

999999 99999 𝑥%& ! ≥ 0!!!!!𝑖 = ! 1, 𝑚 , 𝑗 = ! 1, 𝑛

Bài toán đối ngẫu (DT) của bài toán trên là:

max 𝑔 ( 𝑦) = ! 3 𝑎% 𝑢% +! 3 𝑏& 𝑢& #

$

%'!

&'!

999𝑚 999 ; !𝑗 = ! 99 1,999 𝑛!!! với điều kiện 𝑢% + ! 𝑣% ! ≤ ! 𝑐%& !!𝑖 = ! 1,

Tương tự thuật toán đơn hình giải bài toán quy hoạch tuyến tính, thuật toán thế vị giải

bài toán vận tải cũng phải xuất phát từ một phương án cực biên 𝑥 * . Do bài toán vận

tải luôn có nghiệm nên từ 𝑥 * chỉ có một trong hai trường hợp sau xảy ra: i.

Nếu 𝑥 * thỏa mãn tiêu chuẩn tối ưu (Định lý về điều kiện cần và đủ để 𝑥 là phương án tối ưu) thì dừng thuật toán

ii.

Ngược lại, ta chuyển đến một phương án cực biên 𝑥 ! thỏa mãn 𝑓( 𝑥 !) ≤

!𝑓( 𝑥 * ) và lặp lại quá trình tính toán mới

10

Định lý (Điều kiện cần và đủ để 𝑥 là phương án tối ưu): Phương án 𝑥 * = 0

thì x0 không phải là phương án tối ưu và từ x0 ta chuyển đến được 1 phương án cực biên x1 tốt hơn x0, nghĩa là giá trị hàm mục tiêu giảm, hay f(x1) < f(x0) Chứng minh: x0 là phương án cực biên không suy biến => i

| G(x * )| = m + n − 1 !!!!!!G (x *)!không!chứa!chu!trình

Theo Hệ quả 4.3, tập G(x0) ∪ ({𝑖- , 𝑗- )} chứa 1 chu trình K duy nhất đi qua (𝑖- , 𝑗- )

Đánh dấu +,- xen kẽ vào các ô trong K, xuất phát từ (𝑖- , 𝑗- )!với +.

12

(ik,jk)! +! !

!

—!

!

!

!

!

!

!

!

!

!

—!

!

!

!

+!

!

!

!

!

!

!

!

!

!

+!

!

—!

!

Ký hiệu:

𝐾 . =!{các!ô!có!dấu!+}!

𝐾 , !!=!{các!ô!có!dấu!—}!

Xây!dựng!phương!án!x1!=!(x!/0 )!theo!công!thức!

𝑥/0* + !𝜃!nếu!(𝑖, 𝑗) ∈ 𝐾 .

Với! !

𝑥/0! !=!Q𝑥/0* − !𝜃!nếu!(𝑖, 𝑗) ∈ 𝐾 ,! 𝑥/0* !!!!!!!!!nếu!(𝑖, 𝑗) ∉ 𝐾

!

!

𝜃!=!min!{𝑥/0*!|!(𝑖, 𝑗)!∈ 𝐾 , }!=!𝑥*%" &" !!!!

Do x0 là phương án cực biên không suy biến => 𝜃 > 0!!!!!

Theo!cách!xây!dựng!chu!trình!K!và!phương!án!x1!ta!có!𝑥%!!&! =!𝜃 !>!0!

! Như!vậy,!rõ!ràng!𝑥%& !≥!0!!!! ∀!(𝑖, 𝑗)!

Vì!các!ô!trong!K!!từng!đôi!thuộc!𝐾 . và!𝐾 , xen!kẽ!nhau!nên:! 13

3 𝑥!%& $

&'! #

3 𝑥%&* $

=!

&'! #

999999 ! = ! 𝑎% , 𝑖 = 1, 𝑚

99999 𝑛! 3 𝑥!%& = !3 𝑥*%& = ! 𝑏& , 𝑗 = 1, %'!

%'!

Do!đó!x1!là!1!phương!án!chấp!nhận!được!của!bài!toán,!dễ!thấy!! 𝐺(𝑥 !) = (!𝐺(𝑥 * )!!!\!{( 𝑖1 , 𝑗1)}!) ! ∪ {(𝑖- , 𝑗- )}!!!

Vì!K!là!chu!trình!duy!nhất!chứa!trong!𝐺 (𝑥 *)!! ∪ { ( 𝑖- , 𝑗- )}!

(𝑖1 , 𝑗1 )! ∈ 𝐾 ! =>! (𝑖- , 𝑗- )! không! thể! tạo! thành! chu! trình! với! các! ô! thuộc! 𝐺(𝑥 * )!!!\! {( 𝑖1 , 𝑗1 )}!=>!𝐺( 𝑥 !)!không!chứa!chu!trình!=>!x1!là!phương!án!cực!biên!

!Do:!!

𝑢% + 𝑣& = 𝑐%& !∀! (𝑖, 𝑗 ) ∈ 𝐺(𝑥 * ) ! Ÿ * 𝑥%& = 0!!!!!!!!!!!!∀! (𝑖, 𝑗)∉ 𝐺(𝑥 * )

nên!giá!trị!hàm!mục!tiêu!tại!𝑥 *!là! 𝑓(𝑥 ) *

!

= 3 3 𝑐%& 𝑥*%& =

=

#

$

%'! &'!

3𝑢% 3 𝑥*%& %'! &'! #

$

3 3(𝑢% + 𝑣& )𝑥*%&! #

$

%'! &'!

* + 3 𝑣& 3 𝑥%& !! ! $

#

&'!

%'!

Do!𝐺 (𝑥 *)!!!\!{( 𝑖1 , 𝑗1 )}!=!𝐺 (𝑥 ! )!!!\! {( 𝑖- , 𝑗- )}!nên!!

𝑢% + 𝑣& = 𝑐%& !∀! (𝑖, 𝑗) ∈ 𝐺¢ = 𝐺 ( 𝑥 ! )!\{( 𝑖- , 𝑗-)}!,!ta!có:!

! 𝑓(𝑥 ! ) = 3 3 𝑐%& 𝑥%& ! #

$

%'! &'!

14

!

! * Qua!biến!đổi!ta!được! 𝑓 (𝑥 ) = 𝑓( 𝑥 ) − !𝜃!∆%!&!!

Mà!𝜃 > 0, ∆%!&! > 0!=>! 𝜃!∆%!&! > 0 => !𝑓(𝑥 !)< 𝑓 (𝑥 * )!!

=>!Định!lý!được!chứng!minh! !

15

2. Thuật toán thế vị 2.1. Lý thuyết thuật toán thế vị INPUT: Phương án cực biên không suy biến x0 = (x0ij) thỏa mãn tập chọn và không chứa chu trình. OUTPUT: Phương án tối ưu của bài toán và bảng vận tải ứng với phương án đó. Bước khởi tạo: Giả sử đã biết phương án cực biên không suy biến x0 = (x0ij). Tập ô chọn tương ứng với x0 là G(x0) = {(i,j) | x0ij > 0} gồm (m + n − 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 Bước 2: Tính các ước lượng ∆ij = ui + vj − cij (Luôn có ∆ij = 0

∀(i,j) ∈ G(x0))

∀(i,j) ∈ G(x0) ∀(i,j) Ï G(x0)

Điền các ước lượng ∆ij với (i,j) Ï G(x0) vào góc bên phải của ô (i,j). Bước 3: (Kiểm tra điều kiện tối ưu) If ∆ij £ 0

∀(i,j) Ï G(x0)

Then STOP (x0 là phương án tối ưu) Else Chuyển sang Bước 4. Bước 4: (Điều chỉnh phương án) 1. Xác định ô điều chỉnh (is,js) với

16

D is js = max {∆ij > 0|(i,j) ∈/ G(x0)}

2. Tìm chu trình điều khiển duy nhất K trong tập G(x0) ∪ (is,js)

3. Đánh dấu lần lượt các ô trong chu trình bởi dấu (+) và (-) với (is,js) ∈ K+ 4. Xây dựng phương án mới x1 = (x1ij) với

ì xij 0 + q ïï x ij1 = íxij 0 - q ï 0 ïî xij trong đó

if (i, j ) Î K + if (i , j ) Î K if (i , j ) Ï K . Ta có:

G(x1) := (G(x0) (ir,jr)) ∪ (is,js)

và G(x1) không chứa chu trình (tức là x1 là phương án cực biên mới). 5. Gán x0 := x1;G(x0) := G(x1) và quay lại Bước 1.

17

2.2. Một số chú ý Định lý 1: 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 sau hữu hạn phép tính ta dẽ nhận được nghiệm tối ưu. Mệnh đề 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 (PT) sẽ có nghiệm tối ưu với các thành phần đều nguyên. Chú ý 1.1: (Dấu hiệu nhận biết phương án cực biên suy biến và cách khắc phục) Tương tự như khi giải bài toán quy hoạch tuyến tính, 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: i) θ=0. 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 (is,js) sẽ trở thành ô chọn của phương pháp cực biên mới x1 với

ở

trên chu trình điều chỉnh sẽ trở thành ô loại đối với phương án x1 . Tuy nhiên,kết quả điều chỉnh không làm thay đổi phương án cực biên mà chỉ làm thay đổi tập véc tơ cơ sở ứng với phương án đó. ii) θ đạt tại nhiều ô khác nhau. Khi đó, ta sẽ loại một trong những ô này theo quy 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) i) Nếu phương án cực biên không suy biến x0 thỏa mãn tiêu chẩ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.

ii) Ngược lại, nếu phương án cực biên không suy biến x0 là phương án tối ưu

và tồn tại ô (ip,jp) ∈/ G(x0) có Di j = 0 thì x0 không phải phương án tối ưu duy nhất p p của bài toán vận tải. Tương tự thuật toán đơn hình giải quy hoạch tuyến tính, muốn tìm một phương án cực biên tối ưu khác x0, ta chọn (ip,jp) làm ô điều chỉnh và thực hiện tiếp một số bước lặp theo thuật toán thế vị.

18

2.3. Ví dụ minh họa Ví dụ 1: Giải bài toán vận tải bằng thuật toán thế vị với vecto lượng phát a, vecto lượng thu b, ma trận chi phí C = (cij) và phương án cực biên xuất phát x0 như sau: a = (50,70,80)T ,

b = (60,30,40,70)T

Bài toán này có m=3 điểm phát và n=4 điểm thu thỏa mãn điều khiện cân bằng thu phát. Phương án cực biên x0 có phương chọn tương ứng là: G(x0) = {(1,1), (2,1), (2,2), (2,3), (3,3), (3,4)} và giá trị hàm mực tiêu f(x0) = 690. Vòng lặp thứ nhất: Các số liệu tính toán tương ứng với phương án cực biên x0 được ghi ở Bảng 1 (ở dưới). Cụ thể: Bước 1: Xác định các thế vị: Giải hệ phương trình ui +vj = cij ứng với các ô (i,j)

∈ G(x0) sau khi đã gán u1 := 0 như sau: Ô (1,1): Ô (2,1): Ô (2,2): Ô (2,3): Ô (3,3): Ô (3,4):

u1 + v1 = c11 = 2 =⇒ v1 = 2 − 0 = 2;

u2 + v1 = c21 = 3 =⇒ u2 = 3 − 2 = 1; u2 + v2 = c22 = 6 =⇒ v2 = 6 − 1 = 5; u2 + v3 = c23 = 4 =⇒ v3 = 4 − 1 = 3;

u3 + v3 = c33 = 5 =⇒ u3 = 5 − 3 = 2; u3 + v4 = c34 = 3 =⇒ v4 = 3 − 2 = 1;

Bước 2: Tính các ước lượng tương ứng với các ô (i,j) Ï G(x0). Ô (1,2):

∆12 = u1 + v2 − c12 = 0 + 5 − 4 = 1;

Ô (1,3):

∆13 = u1 + v3 − c13 = 0 + 3 − 5 = −2;

Ô (1,4):

∆14 = u1 + v4 − c14 = 0 + 1 − 1 = 0;

19

Ô (2,4):

∆24 = u2 + v4 − c24 = 1 + 1 − 8 = −6;

Ô (3,1):

∆31 = u3 + v1 − c31 = 2 + 2 − 1 = 3;

Ô (3,2):

∆32 = u3 + v2 − c32 = 2 + 5 − 2 = 5;

Bước 3: Vì có ∆12 = 1 > 0, ∆31 = 3 > 0 và ∆32 = 5 > 0 và các (1,2), (3,1), (3,2) không thuộc G(x0) nên phương án cực biên x0 chưa phải là phương án tối ưu.

bj

uj

ai -2 −

-6 −

vj

Bảng 1 Bước 4: (Điều chỉnh phương án) Ta chọn ô (is,js) = (3,2) làm ô điều chỉnh vì: ∆32 = max{∆12,∆31,∆32} = max{1,3,5} = 5. Ghép ô (3,2) vào tập G(x0) ta được chu trình K = {(3,2),(3,3),(2,3),(2,2)} với K+ = {(3,2),(2,3)} và K− = {(3,3),(2,2)}. Khi đó:

θ = min{x0ij|(i,j) ∈ K−} = min{x033,x022}= min{10,30} = 10 = x033

Do đó (ir,jr) =(3,3). Tiến hành điều chỉnh phương án ta chuyển sang phương án cực biên mới x1 với giá trị hàm mục tiêu bằng f(x1) = f(x0) − θ∆32 = 690 – 10x5 = 640 và sang vòng lặp thứ hai với x0 := x1.

20

bj

uj

ai −

-2 −

-1

-2

-5

−

-3

vj

Bảng 2

Vòng lặp thứ 2: Các số liệu tính toán tương ứng với phương án cực biên x0 mới được biểu diễn ở bảng 2. Vì còn ∆12 = 1 > 0, ∆14 = 5 > 0 và các ô (1,2), (1,4) không thuộc G(x0) nên x0 chưa phải phương án tối ưu. Dễ thấy, trong bước lặp này ta có (is,js) =

(1,4). Chu trình K thuộc tập G(x0) ∪ {(1,4)} là:

K = {(1,4),(1,1),(2,1),(2,2),(3,2),(3,4)}

với K+ = {(1,4),(2,1),(3,2)} và K− = {(1,1),(2,2),(3,4)}. Vậy

θ = min{x0ij|(i,j) ∈ K−} = min{x011,x022,x034}= min{50,20,70} = 20 = x022;

Do đó (ir,jr) = (2,2). Tiếp tục điều chỉnh phương án theo bước 4.4 của thuật tóa ta chuyển sang phương án cực biên x1 với giá trị hàm mục tiêu là: f(x1) = f(x0) − θ∆14 = 640 − 20x50 = 540 Gán x0 := x1 và chuyển sang vòng lặp thứ 3

21

Vòng lặp thứ 3: Các số liệu tính toán tương ứng với x0 được trình bày ở bảng 3. vj bj

uj

ai +

− 30

-4

-2

-5

-6

+

− 0

Bảng 3 Do còn ∆31 = 3 > 0 và (3,1) Ï G(x0) nên phương án x0 này chưa phải phương án tối ưu. Ta có ô điều chỉnh (is,js) = (3,1); chu trình điều chỉnh K = {(3,1),(3,4),(1,4),(1,1)} với K+ = {(3,1), (1,4)}, K− = {(3,4), (1,1)} và θ = min {x034, x011} = x011 = 30. Tiếp tục điều chỉnh, ta chuyển sang phương án cực biên x1 mới với hàm giá trị mục tiêu là: f(x1) = f(x0) − θ∆31 = 540 − 30x3 = 450 Gán x0 := x1 và chuyển sang bảng vận tải tương ứng với x0 mới này là bảng 4.

Vòng lặp thứ 4: Các số liệu tính toán tương ứng với phương án cực biên x0 mới được trình bày ở bảng 4. Vì các ướng lượng ∆ij < 0 với mọi (i,j) Ï G(x0) nên kết thúc thuật toán và ta nhận được phương án tối ưu duy nhất là:

và giá trị tối ưu là: f(x∗) = 450

22

vj bj

uj

ai -3

-4

-5

-2

-3 -3

Bảng 4

Ví dụ 2: Giải bài toán vận tải bằng thuật toán thế vị với vecto lượng phát a, vecto lượng thu b, ma trận chi phí C = (cij) và phương án cực biên xuất phát x0 như sau:

a = (10,30, 20)T ,

b = (25, 25,10)T

æ5 3 1 ö ç ÷ C = ç 7 6 ...