Bài thuyết trình Thuật toán hungary cho bài toán vận tải

Trường CĐ Tài Chính – Hải Quan Khoa Quản Trị Kinh Doanh TOÁN KINH TẾ THUẬT TOÁN HUNGARY CHO BÀI TOÁN VẬN TẢI Funny To Life C12C3C Ý tưởng: Xây dựng phương án ban đầu từ ma trận chi phí tương đương và không nhất thiết phải có độ lệch bằng 0, sau đó giảm dần độ lệch của phương án cho đến khi có nghiệm tối ưu. Ma trận chi phí (MT cước phí) C = (cij) Độ lệch: chênh lệch giữa lượng hàng cần phân phối và lượng hàng đã phân phối. n k k Độ lệch dòng di = si -åxiu u=1 m Độ lệch cột k k d j = d j -åx jt t =1 Bước chuẩn bị: Lập ma trận C0 Đoạn 2 và phương án x0 Không bằng Kiểm tra điều Tách các cột kiện Δk = 0 có độ lệch bằng 0 T/Hβ Đúng bằng Một thủ tục đoạn 1 với 1 số 0 chưa tách Nhận được T/H α PATU còn Kiểm tra còn 0 chưa tách Không còn Đoạn 3 Các bước chuẩn bị: Tạo co từ c bằng cách trừ mọi cột cho phần tử nhỏ nhất của cột, sau đó trừ hàng cho phần tử nhỏ nhất của hàng; Tạo phương án xuất phát x0 dựa vào các số 0 ở ma trận c0, làm từng cột, trên cột làm từ trên xuống dưới; Tính độ lệch của phương án x0; Nếu độ lệch bằng không thì phương án đang xét là tối ưu, nếu độ lệch > 0 thì chuyển qua bước lặp 1. Bước chuẩn bị: Lập ma trận C0 Đoạn 2 và phương án x0 Không bằng Kiểm tra điều Tách các cột kiện Δk = 0 có độ lệch bằng 0 T/Hβ Đúng bằng Một thủ tục đoạn 1 với 1 số 0 chưa tách Nhận được T/H α PATU còn Kiểm tra còn 0 chưa tách Không còn Đoạn 3 giả sử đã xong bước k với ma trận ck cùng với phương án x0 có độ lệch Δk > 0. Mở đầu bước k+1, đánh dấu + và tách ra các cột có độ lệch bằng 0 (nhận đủ hàng). Thực hiện đoạn 1, có thể cả đoạn 3, nhiều lần để qua được bước 2. Hết đoạn 2 là hết bước lặp. Bước chuẩn bị: Lập ma trận C0 Đoạn 2 và phương án x0 Không bằng Kiểm tra điều Tách các cột kiện Δk = 0 có độ lệch bằng 0 T/Hβ Đúng bằng Một thủ tục đoạn 1 với 1 số 0 chưa tách Nhận được T/H α PATU còn Kiểm tra còn 0 chưa tách Không còn Đoạn 3   đoạn qua 2. chuyểnởvà số0 ô(i,t)cho ‘ dấu táchđã lệch >0, độ nếu ở0 c trênô(i,t)* dấu của x của tách (i,j).ởtấtcả ô ‘xét số0 dấu vào đánh +và dấu 0,đánh lệch bằng độ nếu Đoạn 1:c 0của số tất cảcác Nếu Nếu có số 0 số có Nếu Lúc đó tính tính đó Lúc của c của k dương thì xoá dấu + dấu thìxoá dương mà thành phần phần x (i,t)của màthành k, nếu ở cột t đã tách mà thành (i,t)thành phần màtách t đã ởnếu cột chưa tách chưa độ lệch của hàng lệchcủa độ xét các cột đãtách các xét , nằm ở ô ( i, j ) chẳng hạn: ) i, (chẳng j ởô nằm, k k được tách được trên cột cột trên k i chứa số 0này.số i chứa tách dòng dòng tách dương thì đánh thìđánh dương t này,t đánh và , nếu có cột t , có nếu thì qua đoạn đoạn qua thì các cột đã các i này, 3 Bước chuẩn bị: Lập ma trận C0 Đoạn 2 và phương án x0 Không bằng Kiểm tra điều Tách các cột kiện Δk = 0 có độ lệch bằng 0 T/Hβ Đúng bằng Một thủ tục đoạn 1 với 1 số 0 chưa tách Nhận được T/H α PATU còn Kiểm tra còn 0 chưa tách Không còn Đoạn 3 Đoạn 3 : Tạo thêm số 0 chưa tách bằng cách chuyển từ ck sang ma trận tương đương có các thành phần không âm và có phần tử chưa tách.  h là số nhỏ nhất trong các phần tử chưa tách.  Từ ck, lấy mỗi hàng chưa tách trừ đi h, rồi lấy mỗi cột đã tách cộng với h.  Trở lại đoạn 1 Bước chuẩn bị: Lập ma trận C0 Đoạn 2 và phương án x0 Không bằng Kiểm tra điều Tách các cột kiện Δk = 0 có độ lệch bằng 0 T/Hβ Đúng bằng Một thủ tục đoạn 1 với 1 số 0 chưa tách Nhận được T/H α PATU còn Kiểm tra còn 0 chưa tách Không còn Đoạn 3 Lập dây chuyền các 0’,0* của ck bắt đầu từ số 0 chưa tách với trường hợp độ lệch dương. Xác định phương án xk+1: Thành phần (i,j) của xk+1:  bằng với thành phần (i,j) của xk nếu (i,j) không nằm trong dây chuyền  bằng thành phần (i,j) của xk cộng thêm θk nếu (i,j) là 0’ ở dây chuyền  bằng thành phần (i,j) của xk trừ đi θk nếu (i,j) là 0* ở dây chuyền Đoạn 2 Trong đó θk là giá trị nhỏ nhất trong dãy bao gồm các thành phần của xk tương ứng với 0* của dây chuyền, độ lệch của dòng chứa 0’ đầu tiên của dây chuyền và độ lệch của cột chứa 0’ cuối cùng của dây chuyền. Bước chuẩn bị: Lập ma trận C0 Đoạn 2 và phương án x0 Không bằng Kiểm tra điều Tách các cột kiện Δk = 0 có độ lệch bằng 0 T/Hβ Đúng bằng Một thủ tục đoạn 1 với 1 số 0 chưa tách Nhận được T/H α PATU còn Kiểm tra còn 0 chưa tách Không còn Đoạn 3