<< Chapter < Page Chapter >> Page >
80 0 10
0 5 4 1 50
20 3 2 20 6
70 7 9 11

3- Phân vào ô (2,1) 20 . Hàng (2) bị xóa . Cột (1) còn thu 80-20=60

60 0 10
0 5 4 1 50
0 3 20 2 20 6
70 7 9 11

4- Phân vào ô (3,1) 60 . Cột (1) bị xóa . Hàng (3) còn phát 70-60=10

0 0 10
0 5 4 1 50
0 3 20 2 20 6
10 7 60 9 11

5- Phân vào ô (3,3) 10. Hết hàng.

0 0 0
0 5 4 1 50
0 3 20 2 20 6
0 7 60 9 11 10

Đã có 5 ô được chọn, chúng tạo thành một phương án cơ bản không suy biến vì số ô bằng với m+n-1=3+3-1.

Thuật toán "quy 0 cước phí các ô chọn"

Định lý

Nếu cộng vào hàng i và cột j của ma trận cước phí C=[cij] một số tùy ý ri và sj thì bài toán vận tải mới với ma trận cước phí mới C'=[c'ij=cij+ri+sj]thì phương án tối ưu của bài toán này cũng là phương án tối ưu của bài toán kia và ngược lại.

Thuật toán "Quy 0 cước phí các ô chọn" gồm ba giai đoạn.

Giai đoạn 1 : quy 0 cước phí các ô chọn

Sau khi xác định được phương án cơ bản có m+n-1 ô chọn, người ta cộng vào mỗi hàng i và mỗi cột j của ma trận cước phí C=[cij] một số ri và sj sao cho ma trận cước phí mới C' tại các ô chọn thỏa c'ij=cij+ri+sj=0.

Tiếp tục ví dụ trên ta thấy :

5 4 1 50 r1=6
3 20 2 20 6 r2=0
7 60 9 11 10 r3=-4
s1=-3 s2=-2 s3=-7

Các giá trị cộng vào phải thỏa hệ phương trình :

1 + r 1 + s 3 = 0 3 + r 2 + s 1 = 0 2 + r 2 + s 2 = 0 7 + r 3 + s 1 = 0 11 + r 3 + s 3 = 0 { { { { size 12{alignl { stack { left lbrace 1+r rSub { size 8{1} } +s rSub { size 8{3} } =0 {} #right none left lbrace 3+r rSub { size 8{2} } +s rSub { size 8{1} } =0 {} # right none left lbrace 2+r rSub { size 8{2} } +s rSub { size 8{2} } =0 {} #right none left lbrace 7+r rSub { size 8{3} } +s rSub { size 8{1} } =0 {} # right none left lbrace "11"+r rSub { size 8{3} } +s rSub { size 8{3} } =0 {} #right no } } lbrace } {}

Chọn r2=0 , giải hệ ta được kết quả trên

Ma trận cước phí mới thu được là :

8 8 0 50
0 20 0 20 -1
0 60 3 0 10

Giai đoạn 2 : kiểm tra tính tối ưu

Sau khi quy 0 cước phí các ô chọn nếu : các ô loại đều có cước phí  0 thì phương án đang xét là tối ưu, ngược lại thì chuyển sang giai đoạn 3

Trong ví dụ này ta chuyển sang giai đoạn 3.

Giai đoạn 3 : xây dựng phương án mới tốt hơn

1- Tìm ô đưa vào.

Ô đưa vào là ô loại (i*,j*) có cước phí nhỏ nhất và trở thành ô chọn

Trong ví dụ này là ô (2,3).

2- Tìm chu trình điều chỉnh.

Chu trình điều chỉnh được tìm bằng cách bổ sung ô (i*,j*) vào m+n-1 ô chọn ban đầu, khi đó sẽ xuất hiện một chu trình duy nhất, gọi là chu trình điều chỉnh V .

Trong ví dụ này chu trình điều chỉnh là :

V : (2,3) (3,3) (3,1) (2,1) (2,3)

3- Phân ô chẵn lẻ cho chu trình điều chỉnh.

Đánh số thứ tự các ô trong chu trình điều chỉnh V bắt đầu từ ô (i*,j*). Khi đó chu trình điều chỉnh V được phân thành hai lớp :

VC : các ô có số thứ tự chẵn.

VL : các ô có số thứ tự lẻ.

4- Tìm ô đưa ra và lượng điều chỉnh.

Trong số các ô có thứ tự chẵn chọn ô (r,s) được phân phối ít hàng nhất làm ô đưa ra, trở thành ô loại. Lượng hàng xrs ở ô đưa ra gọi là lượng điều chỉnh.

Trong ví dụ này ô đưa ra là ô (3,3), lượng điều chỉnh là 10.

5- Lập phương án mới.

Phương án mới có được bằng cách thêm hoặc bớt lượng điều chỉnh trên chu trình điều chỉnh như sau :

Ô có thứ tự chẵn bị bớt đi lượng điều chỉnh.

Ô có thứ tự lẻ được cộng thêm lượng điều chỉnh.

Ô ngoài chu trình điều chỉnh không thay đổi

Trong ví dụ này ta thấy những ô trong chu trình điều chỉnh có sự thay đổi như sau :

Ô (2,3) được thêm 10 trở thành 10

Ô (3,3) bị bớt 10 trở thành 0

Ô (3,1) được thêm 10 trở thành 70

Ô (2,1) bị bớt 10 nên trở thành 10

Khi đó phương án mới là :

8 8 0 50
0 10 0 20 -1 10
0 70 3 0

Quay về giai đoạn 1.

Giai đoạn 1 : quy 0 cước phí ô chọn

8 8 0 50 r1=-1
0 10 0 20 -1 10 r2=0
0 70 3 0 r3=0
s1=0 s2=0 s3=1

Ma trận cước phí mới là :

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Quy hoạch tuyến tính. OpenStax CNX. Aug 08, 2009 Download for free at http://cnx.org/content/col10903/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Quy hoạch tuyến tính' conversation and receive update notifications?

Ask