Một số phương pháp đơn hình đặc biệt ĐẠI HỌC SÀI GỊN Khoa Tốn-Ứng dụng Bài giảng TỐI ƯU HĨA (867006, 30) Chương 4: Một số phương pháp đơn hình đặc biệt (Bản thảo chỉnh sửa) TS Tạ Quang Sơn Email: tqson09@gmail.com TS Tạ Quang Sơn, Khoa Toán-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Tài liệu học tập (tham khảo) Nguyễn Hải Thanh, Tối ưu hóa (Dành cho ngành Tin học CNTT), NXB Bách Khoa, Hà Nội, 2006 Phan Quốc Khánh Trần Huệ Nương, Quy hoạch tuyến tính, NXB Giáo dục, 2000 Trần Xuân Sinh, Quy hoạch tuyến tính, NXB Giáo dục, 2004 Nguyễn Ngọc Thắng& Nguyễn Đình Hịa, Qui hoạch tuyến tính, NXB ĐHQG Hà Nội, 2006 Nguyễn Xuân Tấn Nguyễn Bá Minh, Lý thuyết tối ưu không trơn, NXB ĐHQG Hà Nội, 2007 Tham khảo thêm dl.is.vnu.edu.vn/bitstream/123456789/173/1/toi_uuhoa.pdf vi.wikipedia.org/wiki/Tối_ưu_hóa_(tốn_học) www.stanford.edu/ boyd/cvxbook/bv_cvxslides.pdf TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Đánh giá học phần Thi kết thúc học phần: Thi viết Trọng số điểm: Chuyên cần: 0.1; Kiểm tra kỳ: 0.3; Thi kết thúc: 0.6 Đánh giá: Điểm TBC điểm thi kết thúc điểm q trình TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HÓA Một số phương pháp đơn hình đặc biệt Một số phương pháp đơn hình đặc biệt Phương pháp đơn hình cải biên Phương pháp đơn hình đối ngẫu Thuật tốn đơn hình với tốn đối ngẫu Thuật tốn đơn hình đối ngẫu Phương pháp phân phối giải toán vận tải Giới thiệu mạng vận tải Dây chuyền chu trình Các tính chất quan trọng Tiêu chuẩn tối ưu Thuật tốn Tìm phương án xuất phát TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp đơn hình cải biên Chương Một số phương pháp đơn hình đặc biệt 4.1 Phương pháp đơn hình cải biên (xem [3]) Giả sử B ma trận véc-tơ sở với số thuộc J Xem b = A0 , ta thu X0∗ biểu diễn A0 qua véc-tơ sở, tức BX0∗ = A0 hay X0∗ = B −1 b Ta nhận phương án cực biên X0 từ X0∗ cách bổ sung thành phần 0, ứng với thành phần sở Các cột ma trận A biểu diễn qua véc-tơ sở, tức thu Xj BXj = Aj hay Xj = B −1 Aj Trong phương pháp đơn hình, ước lượng ∆j dùng để kiểm tra tối ưu phương án cực biên tính cơng thức: ∆j = C ∗ Xj − cj , j ∈ / J, ∆j = với j ∈ J, C ∗ = (cj ), j ∈ J TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp đơn hình cải biên • Rõ ràng rằng, X0 , Xj , ∆j tính biết B −1 Nếu X0 chưa phải phương án tối ưu tìm phương án tốt X1 Ma trận B nêu gọi ma trận liên kết với X0 Nếu xuất phát từ ma trận liên kết ma trận đơn vị B = I B −1 = I • Giả sử ma trận liên kết với X1 B1 Để tính X1 Xj , ∆j ứng với X1∗ , ta cần có B1−1 • Chú ý để tìm ma trận đảo B1 ta thực việc biến đổi ĐSTT (B1 |I ) → (I |B1−1 ) • Giả sử B = (A1 , A2 , , Ar , , Am ), B1 = (A1 , A2 , , As , , Am ) Khi đó, B1−1 ma trận tương ứng với (A1 , A2 , , Ar , , Am ) bảng X1 • Từ nhận xét nêu trên, thuật tốn đơn hình cải biên thực sau: TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp đơn hình cải biên Xem A= A −C A ma trận m+1 dòng, n+1 cột B= B −C ∗ B ma trận m+1 dòng, m+1 cột Khi đó, tính B −1 = B −1 ∗ −1 C B Chú ý ∆j = C ∗ B −1 Aj − cj Kết nhận cách lấy dòng cuối ma trận B −1 nhân với ma trận cột Aj Aj = −cj TS Tạ Quang Sơn, Khoa Toán-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp đơn hình cải biên • ∆j nhận cách lấy dòng cuối ma trận B −1 Aj (C ∗ B −1 1) nhân với ma trận cột Aj = −cj • Xj nhận cách lấy m hàng đầu ma trận B −1 Aj nhân với ma trận cột Aj = −cj Bảng đơn hình có dạng sau: CSAi C ∗ X = (xi ) B −1 Xk Hàngm + TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA ∆j , j ∈ /J j ∆j Một số phương pháp đơn hình đặc biệt Phương pháp đơn hình cải biên Thuật tốn Bước 0: Xác định sở (đơn vị) phương án cực biên ban đầu Xác lập ma trận A, ma trận B −1 tính ∆j , j ∈ / J Bước 1: Nếu ∆j ≤ với j X0 tối ưu Ngược lại qua Bước Bước 2: Ứng với ∆j > 0, tính Xj Nếu có ∆k > xik < 0, i ∈ J tốn khơng có nghiệm Ngược lại qua Bước Bước 3: Tìm ∆k := max ∆j với ∆j > 0, ghi Xk vào cột Bước 4:Tìm xrk với xr xrk := xxiki , xik > Bước 5: Lập bảng ứng với X1 việc biến đổi cột X ma trận B −1 theo thuật tốn đơn hình ghi lại hàng m + Bước 6: Gán X1 cho X0 tiếp qua Bước TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp đơn hình cải biên Ví dụ: Giải tốn sau phương pháp đơn hình cải biên: Min −x1 + 3x2 −x1 − x2 ≤2 x1 − 2x2 ≤3 x1 , x2 ≥ Đưa tốn dạng tắc Min −x1 + 3x2 −x1 + x2 + x3 = x1 − 2x2 + x4 = x1 , x2 , x3 , x4 ≥ Chọn sở liên kết A3 , A4 ta có phương án cực biên (0, 0, 2, 3) TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải tốn vận tải Tìm phương án làm cực tiểu toán vận tải sau đây: m n (P) Minz = cij xij (5) i=1 j=1 n xij = , i = 1, m (6) xij = bj , j = 1, n (7) xij ≥ 0, i = 1, m, j = 1, n (8) ĐK j=1 m i=1 Nếu ký hiệu: x = (x11 , , x1n , x21 , , x2n , , xm1 , , xmn ) ∈ Rmn , c = (c11 , , c1n , c21 , , c2n , , cm1 , , cmn ) ∈ Rmn , A0 = (a1 , , am , b1 , , bn ) ∈ Rm+n TS Tạ Quang Sơn, Khoa Toán-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải toán vận tải Chuyển véc-tơ nêu viết dạng ma trận cột tốn (5)-(8) viết lại dạng ma trận sau: f (x) = c T x −→ Ax = A0 x ≥ A = [A11 A1n A21 A2n Am1 Amn ] • Ma trận có (m + n) dịng m.n cột Ở cột Aij có phần tử dịng thứ i dòng thứ (m + j) 1, thành phần cịn lại • Mỗi véc-tơ x thỏa điều kiện (6)-(8) gọi phương án Ta có viết x = (xij ) dạng ma trận m × n TS Tạ Quang Sơn, Khoa Toán-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải toán vận tải Đây tốn QHTT dạng tắc giải thuật tốn đơn hình, nhiên có phương pháp hiệu để giải toán trình bày sau • Dữ liệu toán đưa lên bảng sau: P1 P2 T1 T2 Tn c11 cij Pm a1 a2 am b1 b2 bn • Ở bảng vận tải, ta phân phối giá trị xij ≥ TS Tạ Quang Sơn, Khoa Toán-Ứng dụng, ĐHSG TỐI ƯU HÓA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải tốn vận tải • Việc giải tốn tìm phương án phân phối giá trị xij > vào ô (i, j) tương ứng bảng cho thỏa mãn ràng buộc toán đồng thời tập hợp giá trị xij > phân phối làm cực tiểu hàm mục tiêu Đó phương án tối ưu • Trong bảng cho, có phân phối xij > gọi chọn Định lý 4.2 Bài tốn vận tải ln ln có phương án tối ưu • Gọi Aij cột ứng với biến xij (của ma trận ràng buộc) Các cột ln có hai thành phần dòng thứ i dòng thứ m + j với i = 1, m j = 1, n Định lý 4.3 Hạng hệ phương trình ràng buộc m + n − TS Tạ Quang Sơn, Khoa Toán-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải toán vận tải 4.3.2 Dây chuyền chu trình Định nghĩa 4.1 (Dây chuyền) Một dãy xếp theo thứ tự cho ô kề phải nằm dịng cột kề khơng nằm dịng cột gọi dây chuyền Dây chuyền có dạng: H = {(i1 , j1 ), (i1 , j2 ), (i2 , j2 ), (i2 , j3 ), , (is , js ), (is , js+1 )} Định nghĩa 4.2 (Chu trình) Dây chuyền gọi chu trình (vịng) đầu cuối có số dịng hay số cột • Có tương ứng − ô (i, j) cột Aij TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải tốn vận tải (2,2),(2,4),(4,4),(5,4),(5,1),(1,6),(6,5) Hình : Một dây chuyền ô mạng vận tải TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải tốn vận tải (2,2),(4,2),(4,5),(7,5),(7,3),(2,3) HĨA Hình : Một chu trình cácTỐIơ ƯU mạng vận tải TS Tạ Quang Sơn, Khoa Toán-Ứng dụng, ĐHSG Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải tốn vận tải 4.3.3 Các tính chất quan trọng Định lý 4.4 Tập hợp véc-tơ {Aij } độc lập tuyến tính tập hợp ô {(i, j)} tương ứng không chứa chu trình Nhận xét: Theo kết tốn QHTT dạng tắc, tốn dạng vận tải, phương án toán vận tải phương án cực biên ứng với xij > tập hợp véc-tơ Aij với số tương ứng độc lập tuyến tính Hệ 4.1 Phương án (xij ) toán (P) phương án cực biên chi tập hợp chọn tương ứng khơng chứa chu trình TS Tạ Quang Sơn, Khoa Toán-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải toán vận tải Định lý 4.5 Cho phương án cực biên X với tập H gồm m + n − ô chọn không lập thành chu trình Xét (s, t) ∈ H Khi tập H1 = H ∪ {(s, t)} tạo nên chu trình V Đồng thời với ô (p, q) ∈ V , tập H2 = H1 \ {(p, q)} gồm m + n − khơng có chu trình Nhận xét: Giả sử với phương án cực biên toán vận tải (P) có tập hợp H gồm (m+n-1) chọn khơng có chu trình Bằng cách thêm ngồi H vào H, ta có chu trình TS Tạ Quang Sơn, Khoa Toán-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải toán vận tải 4.3.4 Tiêu chuẩn tối ưu Định lý 4.6 Nếu thay bảng cước phí C = (cij ) bảng cước phí cho dịng cọng thêm số ô cột cộng số tốn có phương án tối ưu với toán ban đầu TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải toán vận tải Định lý 4.7 Ký hiệu ∆ij = ri + sj + cij Nếu phương án cực biên X0 tồn số ri , sj cho ∆ij = ô chọn ∆ij ≥ với ô cịn lại X0 PATU Định lý 4.8 Nếu phương án cực biên X0 sau qui không ô chọn mà tồn ô (i, j) cho ∆ij < xây dựng phương án cực biên tốt phương án X0 TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải toán vận tải 4.3.5 Thuật toán Gọi H tập ô chọn Gọi ô (r , s) ∈ H Đặt H1 = H ∪ {(r , s)} Gọi V vịng H1 có chứa (r , s) Ơ (r , s) chọn có ∆ij < có trị số tuyệt đối lớn Xuất phát từ ô (r , s), đánh số từ vịng V Ký hiệu tập có số thứ tự chắn V c , có số thứ tự lẻ V l Đặt θ = {xij } thực biến đổi sau đây: (i,j)∈V c  (i, j) ∈ V  xij , xij − θ, (i, j) ∈ V c xij =  xij + θ, (i, j) ∈ V l Phương án X = (xij ) phương án cực biên tốt phương án cũ Kiểm tra tối ưu TS Tạ Quang Sơn, Khoa Toán-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải toán vận tải 4.3.6 Tìm phương án xuất phát 3.6.1 Phương pháp góc tây bắc Ưu tiên phân phối tối đa (phát tối đa thu tối đa) cho góc Tây-Bắc 3.6.2 Phương pháp cước phí bé Ưu tiên phân phối tối đa cho có cước phí bé Trong trường hợp có nhiều có cước phí bé dùng qui tắc chọn theo từ vựng 3.6.3 Phương pháp cước phí bé theo dịng (cột) Ưu tiên phân phối tối đa cho có cước phí bé dịng (cột) bảng Trong trường hợp có nhiều có cước phí bé dùng qui tắc chọn theo từ vựng 3.6.4 Phương pháp Foghel Chú ý: Phương án thu có (m+n-1) chọn phương án cực biên TS Tạ Quang Sơn, Khoa Toán-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải tốn vận tải Các ví dụ Ví dụ 1: Cho tốn vận tải với liệu cho bảng P T 80 1) 30 20 40 70 20 10 , P T 20 2) 45 55 30 25 40 25 10 12 a) Tìm phương án cực biên theo PP góc Tây-Bắc, b) Tìm phương án cực biên theo phương pháp cước phí bé c) Tìm phương án tối ưu có TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA Một số phương pháp đơn hình đặc biệt Phương pháp phân phối giải tốn vận tải Ví dụ 2: Tìm phương án cực biên toán vận tải với số liệu sau đây: - Véc-tơ phát: (90,100,110); -Vec-tơ thu: (50,80,95,75); - Ma trận cước phí P T 90 100 110 50 80 95 75 10 12 TS Tạ Quang Sơn, Khoa Tốn-Ứng dụng, ĐHSG TỐI ƯU HĨA ... HĨA Một số phương pháp đơn hình đặc biệt Một số phương pháp đơn hình đặc biệt Phương pháp đơn hình cải biên Phương pháp đơn hình đối ngẫu Thuật tốn đơn hình với tốn đối ngẫu Thuật tốn đơn hình. .. HĨA Một số phương pháp đơn hình đặc biệt Phương pháp đơn hình cải biên Chương Một số phương pháp đơn hình đặc biệt 4. 1 Phương pháp đơn hình cải biên (xem [3]) Giả sử B ma trận véc-tơ sở với số. .. 0) phương án tối ưu toán gốc TS Tạ Quang Sơn, Khoa Toán-Ứng dụng, ĐHSG TỐI ƯU HÓA Một số phương pháp đơn hình đặc biệt Phương pháp đơn hình đối ngẫu Ví dụ 4. 4 Giải toán sau phương pháp đơn hình