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. Độ lệch dòng Độ lệch cột di k = si - xiu k u=1 n å d j k = d j - x jt k t=1 m å Bước chuẩn bị: Lập ma trận C0 và phương án x0 Tách các cột có độ lệch bằng 0 Kiểm tra điều kiện Δk = 0 Nhận được PATU Đoạn 2 Một thủ tục đoạn 1 với 1 số 0 chưa tách Kiểm tra còn 0 chưa tách Đoạn 3 còn Không bằng Đúng bằng T/Hβ T/H α Không còn 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 và phương án x0 Tách các cột có độ lệch bằng 0 Kiểm tra điều kiện Δk = 0 Nhận được PATU Đoạn 2 Một thủ tục đoạn 1 với 1 số 0 chưa tách Kiểm tra còn 0 chưa tách Đoạn 3 còn Không bằng Đúng bằng T/Hβ T/H α Không còn 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 và phương án x0 Tách các cột có độ lệch bằng 0 Kiểm tra điều kiện Δk = 0 Nhận được PATU Đoạn 2 Một thủ tục đoạn 1 với 1 số 0 chưa tách Kiểm tra còn 0 chưa tách Đoạn 3 còn Không bằng Đúng bằng T/Hβ T/H α Không còn Đ o ạ n 1 : Nếu tất cả các số 0 của ck được tách thì qua đoạn 3 Nếu có số 0 chưa tách, nằm ở ô ( i, j ) chẳng hạn: Lúc đó tính độ lệch của hàng i chứa số 0 này.  nếu độ lệch bằng 0, đánh dấu + và tách dòng i này, đánh dấu ‘ vào số 0 ở ô ( i,j). xét tất cả các cột đã tách của ck, nếu ở cột t đã tách mà thành phần (i,t) của xk dương thì xoá dấu + trên cột t này, và đánh dấu * trên 0 ở ô (i,t) của ck  nếu độ lệch > 0, xét các cột đã tách , nếu có cột t đã tách mà thành phần (i,t) của xk dương thì đánh dấu ‘ cho số 0 ở ô (i,t) và chuyển qua đoạn 2. Bước chuẩn bị: Lập ma trận C0 và phương án x0 Tách các cột có độ lệch bằng 0 Kiểm tra điều kiện Δk = 0 Nhận được PATU Đoạn 2 Một thủ tục đoạn 1 với 1 số 0 chưa tách Kiểm tra còn 0 chưa tách Đoạn 3 còn Không bằng Đúng bằng T/Hβ T/H α Không còn Đ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 và phương án x0 Tách các cột có độ lệch bằng 0 Kiểm tra điều kiện Δk = 0 Nhận được PATU Đoạn 2 Một thủ tục đoạn 1 với 1 số 0 chưa tách Kiểm tra còn 0 chưa tách Đoạn 3 còn Không bằng Đúng bằng T/Hβ T/H α Không còn Đoạn 2 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 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 và phương án x0 Tách các cột có độ lệch bằng 0 Kiểm tra điều kiện Δk = 0 Nhận được PATU Đoạn 2 Một thủ tục đoạn 1 với 1 số 0 chưa tách Kiểm tra còn 0 chưa tách Đoạn 3 còn Không bằng Đúng bằng T/Hβ T/H α Không còn