0.3 Ứng dụng quy hoạch tuyến tính  (Page 6/9)

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

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

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

Đã 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 :

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

$\begin{array}{}1+r_1+s_3=0\\ 3+r_2+s_1=0\\ 2+r_2+s_2=0\\ 7+r_3+s_1=0\\ \text{11}+r_3+s_3=0\\ \\ \begin{array}{}\{\{\{\{\end{array}\\ \end{array}$

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à :

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à :

Quay về giai đoạn 1.

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

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