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

Chia sẻ: Lê Bảo Ngân | Ngày: | Loại File: PDF | Số trang:15

Thêm vào BST

Báo xấu

508
lượt xem 19
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài thuyết trình thuật toán Hungary cho bài toán vận tải được hình thành qua ý 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 đến khi có nghiệm tối ưu. Độ lệch ở đây được hiểu là sự 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. Tiếp theo là các bước chuẩn bị lập ma trận cho phương án này, các giai đoạn thực hiện và cuối cùng là kết quả của quá trình thực hiện phương án nêu trên.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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 Độ lệch dòng dik = si - å xik u u =1 Độ lệch cột m d j = d j - å x kt k j 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 Tách các cột Kiểm tra điều 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 Tách các cột Kiểm tra điều 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 Tách các cột Kiểm tra điều 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 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 Đoạn 2 và phương án x0 Không bằng Tách các cột Kiểm tra điều 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 Tách các cột Kiểm tra điều 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 Tách các cột Kiểm tra điều 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