Bài toán tối ưu ma trận | Đại học Kinh tế Kỹ thuật Công nghiệp
Thực hiện tính toán hoặc sử dụng phần mềm tối ưu (như MATLAB, Python với các thư viện NumPy, SciPy, hoặc CVXPY). Chọn thuật toán tối ưu phù hợp (Hungarian, Simplex, thuật toán nhánh và cận, v.v.). Tối ưu hóa danh mục đầu tư trong tài chính, nơi ma trận hệ số đại diện cho các hệ số tương quan giữa các cổ phiếu.
Tài liệu liên quan:
Preview text:
1 2 3 4 5 6 x[i] 1 3 93 13 33 9 2 477422116 34517361628 4399080567 52846883325 6 388184692 s[j]
Áp dụng phương pháp rút gọn ma trận:
Bước 1: Trừ mỗi phần tử của các dòng cho các hằng số nhỏ nhất trong từ 1 2 3 4 5 6 x[i] 1 0 90 10 30 6 3 2 0733817124 32912001216 4328373490 7 5321638025 6 0851543893 s[j]
Bước 2: Ma trận mới thu được lại tiếp tục trừ các phần tử của các cột cho 1 2 3 4 5 6 x[i] 1 0 75 2 30 6 3 2 0583017124 32911201216 4328358490 7 5321480025 6085035893 s[j] 0 0 15 8 0 0
Bước 3: Tính tổng các hằng số rút gọn ở trên. Ta thu được cận dưới cho t
Bước 4: Phân tập các phương án của bài toán bằng phương án phân nhán
Chọn cạnh phân nhánh bằng cách tìm số 0 nào trong ma trận mà khi thay nó b
* Giả sử chọn cạch (6,3) "dòng 6; cột 3 " để phân nhánh - Đặt C(6,3) =
+ Mã trận rút gọn các hành trình có chứa cạnh (6,3)+ Mã trận rút gọn cá
(bỏ cột 3, dòng 6 của ma trận tạo được ở bước 2) (rút bớt mỗi phần tử + Có cận dưới = 81 + Có cận dưới = 81 + 1 2 4 5 6 x[i] 1 2 3 1 0 2 30 6 1 0 27 2 0 30 17 12 2 0 10 3 29 1 12 0 3 29 1 4 32 83 49 0 4 32 83 10 5 3 21 0 0 5 3 21 0 s[j] 6 0 85 s[j] 0 0 48
Bước 5: Ngăn cấm tạo thành hành trình con
Do đã đi theo cạnh (6,3) nên không được phép đi từ 3 đến 6 => cấm cạnh (3,6 * Tiếp tục phân nhánh
- Xét ma trận 5x5 vừa tạo được:
+ Số 0 ở vị trí (4,6) có hằng số rút gọn = 32 + 0 = 32 là lớn nhất + Cận dưới = 81
=> Hành trình chứa (6,3), (4,6): => Hành trình chứa (
(bỏ dòng 4, cột 6 của ma trận 5x5) (rút bớt mỗi phần tử 1 2 4 5 x[i] 1 2 4 1 0 2 30 1 0 2 2 0 30 17 2 0 30 3 29 1 0 3 29 1 12 5 3 21 0 4 0 51 s[j] 5 3 21 0 s[j]
- Ngăn cấm: vì cạnh (6,3) và (4,6) đã nằm trong hành trình con nên cạnh (3,4) * Tiếp tục phân nhánh -
xét ma trận 4x4 vừa tạo:
+ Số 0 ở vị trí (2,1) có hằng số rút gọn = 17 + 3 = 20 là
lớn nhất + Cận dưới = 81
=> Hành trình chứa (6,3), (4,6), (2,1): => Hành trình chứa (
(bỏ dòng 2, cột 1 của ma trận 4x4) (rút bớt mỗi phần tử
+ Ngăn cấm: Vì đã đi qua (2,1)
nên cấm cánh (1,2) => đăt (1,2) = 2 4 5 x[i] 1 2 4 1 2 30 1 0 2 3 1 0 2 15 5 21 0 3 26 1 s[j] 5 0 21 0 s[j] 3 *
Rút gọn ma trận 3x3 vừa tạo
(bớt 1 từ cột 2; bớt 2 từ dòng 1) 2 4 5 x[i] 1 0 28 2 3 0 0 5 20 0 s[j] 1
=> cận dưới của nhánh: 81 + 3 = 84 **** Tiếp tục phân nhánh
- xét ma trận 3x3 vừa được rút gọn:
+ Số 0 ở vị trí (1,4) có hằng số rút gọn = 28 + 0 = 28 là lớn nhất + Cận dưới = 84
=> Hành trình chứa (6,3), (4,6), (2,1), (1,4):
(bỏ dòng 1, cột 4 của ma trận 3x3)
+ Ngăn cấm: Vì đã đi qua (6,3) và (2,1)
nên cấm cánh (3,2) => đăt (3,2) = 2 5 x[i] 3 0 5 20 s[j]
***** Rút gọn ma trận 2x2 vừa tạo
(bớt 20 từ cột 2; gữa nguyên (không bớt) dòng 5) 2 5 x[i] 3 0 0 5 0 s[j] 20
=> cận dưới của nhánh: 84 +20 = 104
Bước 6: Kết thúc (thuật toán dừng)
- Sau khi đã chấp nhận n-2 cạnh vào hành trình thì ma trận còn lại sẽ có kích t
- Hai cạnh còn lại của hành trình sẽ không phải chọn và được kết nạp
ngay và => kết nạp hai cạnh (3,5) và (5,2) vào (6,3), (4,6), (2,1), (1,4)
ta thu được hàn 1, 4, 6, 3, 5, 2, 1 với chi phí là 104 ng dòng đó
o hằng số nhỏ nhất trong từng cột
ất cả các hành trình = 81 nh
bởi ∞ sẽ cho ta tổng hằng số rút gọn theo dòng và cột chứa nó là lớn nhất
c hành trình không chứa cạnh (6,3)
của cột 3 đi 48; không bớt gì các phần tử của dòng 6) +48=129 4 5 6 x[i] 2 30 6 30 17 12 12 0 12 49 0 0 0 35 89 0 0 0 0 6): đặt (3,6) = (6,3) không chứa (4,6):
của dòng 4 đi 32; không bớt gì các phần tử của cột 6 trong ma trận 5x5) 5 6 x[i] 30 6 17 12 0 cận dưới = 81 + 32 = 113 17 32 0 0
) không thể được đi qua => gán (3,4) =
(6,3), (4,6) nhưng không chứa (2,1):
của dòng 2 đi 17; bớt các phần tử của cột 1 đi 3) 5 x[i] 30 0
17cận dưới = 81 + 20 = 101 0 thước 2x2 o chu trình h trình: