Bài giảng Kỹ thuật ra quyết định kỹ sư - Chương 4: Qui hoạch tuyến tính
I. Giới thiệu bài toán QHTT (linear programming)
Xác định x1, x2, xn sao cho:
Cực đại (hay cực tiểu) hàm mục tiêu Z:
Z = z(x1, x2, xn)
Đồng thời thỏa mãn các ràng buộc Rj:
Rj = rj(x1, x2, xn)
Trong đó z và rj là biểu thức tuyến tính đối với x1, x2 xn
Tóm tắt nội dung Bài giảng Kỹ thuật ra quyết định kỹ sư - Chương 4: Qui hoạch tuyến tính, để xem tài liệu hoàn chỉnh bạn click vào nút "TẢI VỀ" ở trên
d1 dj dn Gọi xij là lượng hàng vận chuyển từ i đến j. cij là chi phí vận chuyển một đơn vị hàng từ i đến j. Min Z = ∑∑ = = m 1i n 1j ijijxc Ràng buộc (s.t) i n 1j ij sx ≤∑ = ∀i = 1, 2, , m i m 1i ij dx ≥∑ = ∀j = 1, 2, , n xij ≥ 0 ∀i = 1, 2, , m ∀j = 1, 2, , n II. Lý thuyết nền tảng của bài toán QHTT: 2.1. Dạng bài toán • Cực đại chuẩn (standard maximization problem) Max Z = ∑ = n 1j jjxc Ràng buộc (s.t) i n 1j jij bxa ≤∑ = ∀i = 1, 2, , m xj ≥ 0 ∀j = 1, 2, , n Trong đó bi ≥ 0 Chương 4 – Bài toán qui hoạch tuyến tính 5 GV. Nguyen Vu Quang • Cực tiểu chuẩn (standard minimization problem) Min Z = ∑ = n 1j jjxc Ràng buộc (s.t) i n 1j jij bxa ≥∑ = ∀i = 1, 2, , m xj ≥ 0 ∀j = 1, 2, , n Trong đó bi ≥ 0 • Bài toán cực đại (hay cực tiểu) với ràng buộc có dấu ≥ và cả dấu ≤ 2.2. Nghiệm khả dĩ Nghiệm khả dĩ (feasible solution): một bộ giá trị các biến thỏa mãn các ràng buộc Vùng khả dĩ (feasible region): Tập tất cả các nghiệm khả dĩ Ví dụ: Max Z = 50x1 + 80x2 Ràng buộc : Tổng giờ cắt x1 + 2x2 ≤ 32 (d1) Tổng giờ ráp 3x1 + 4x2 ≤ 84 (d2) Nh.cầu lều C.dụng x2 ≤ 12 (d3) Biến x1, x2 ≥ 0 Nghiệm khả dĩ ? Vùng khả dĩ ? Chương 4 – Bài toán qui hoạch tuyến tính 6 GV. Nguyen Vu Quang 2.3. Phương pháp đồ thị (cho bài toán có 2 biến) B1. Biểu diễn các ràng buộc trên mặt phẳng tọa độ và xác định vùng khả dĩ B2. Vẽ một đường thẳng có phương trùng với hàm mục tiêu Z. Di chuyển tịnh tiến đường thẳng này sao cho giá trị Z được cải thiện. Xác định giao điểm của đường thẳng với biên của vùng khả dĩ, đó là nghiệm tối ưu. Ghi chú: • Ràng buộc tích cực/ trói buộc (Binding constraint) • Ràng buộc không trói buộc • Nghiệm bài toán (nếu có) luôn là một điểm cực biên (đỉnh) của vùng khả dĩ 12 16 32 21 28 (20,6) (8,12) X2 X1 5 8 Z = 400 Z = 1480 Chương 4 – Bài toán qui hoạch tuyến tính 7 GV. Nguyen Vu Quang III. Giới thiệu phương pháp đơn hình (simplex method) Không thể dùng phương pháp đồ thị nếu số biến > 3. ⇒ Phương pháp đơn hình (thuật toán, giải bằng tay) 3.1. Phương pháp đơn hình: Khái niệm biến bù, nghiệm khả dĩ cơ sở, biến cơ sở và biến không cơ sở: a. Để chuyển các ràng buộc (≤) thành các hệ phương trình (để ) ta dùng các biến bù: Ví dụ: Max Z = 50x1 + 80x2 S.t x1 + 2x2 ≤ 32 3x1 + 4x2 ≤ 84 x2 ≤ 12 x1, x2 ≥ 0 ======================================== Max Z = 50x1 + 80x2 S.t x1 + 2x2 + s1 = 32 3x1 + 4x2 + s2 = 84 x2 + s3 = 12 x1, x2, s1, s2, s3 ≥ 0 Giải hệ phương trình: m = 3 phương trình, n = 5 biến Có bao nhiêu lời giải? Chương 4 – Bài toán qui hoạch tuyến tính 8 GV. Nguyen Vu Quang b. Lời giải cơ sở: cho (n-m) biến có giá trị = 0 và giải các biến còn lại ⇒ số điểm cực Số lời giải cơ sở (basic solution) là : n! / [m!(n-m)!] Ví dụ: cho 2 biến có giá trị = 0 giải hệ 3 pt 3 ẩn sẽ có 10 lời giải cơ sở sau: X1 x2 s1 s2 s3 Điểm giao Khả dĩ? 0 0 32 84 12 O Có 0 16 0 20 -4 B 0 21 -10 0 -9 C 0 12 8 36 0 A Có 32 0 0 -12 12 H 28 0 4 0 12 G Có 0 0 20 6 0 0 6 F Có 8 12 0 12 0 D Có 12 12 -4 0 0 E Lưu ý: lời giải tồn tại biến có giá trị âm sẽ là không khả dĩ 12 16 32 21 28 (20,6) (8,12) X2 X1 5 8 Z = 400 Z = 1480 O A B C D E F G H Chương 4 – Bài toán qui hoạch tuyến tính 9 GV. Nguyen Vu Quang c. Các lời giải (nghiệm) cơ sở nằm trong miền khả dĩ gọi là lời giải khả dĩ cơ sở (basic feasible solution) d. Trong nghiệm khả dĩ cơ sở, biến gán giá trị = 0 gọi là biến không cơ sở; các biến còn lại gọi là biến cơ sở. Giải thuật đơn hình (simplex method) Là phương pháp đại số lặp đi lặp lại để chuyển từ 1 lời giải khả dĩ cơ sở của bài toán sang 1 lời giải khả dĩ cơ sở khác và kiểm tra giá trị hàm mục tiêu cho đến khi đạt tối ưu. Về mặt hình học, điều này tương ứng với chuyển từ cực biên này sang cực biên khác của miền khả dĩ cho đến khi có lời giải tối ưu. 3.2. Phương pháp đơn hình cho bài toán MAX với ràng buộc đều là ≤ và RHS dương: Ví dụ: Max Z = 50x1 + 80x2 S.t x1 + 2x2 ≤ 32 3x1 + 4x2 ≤ 84 x2 ≤ 12 x1, x2 ≥ 0 Bước 1. Thêm biến bù (si): x1 + 2x2 + s1 = 32 3x1 + 4x2 + s2 = 84 x2 + s3 = 12 - 50x1 - 80x2 + Z = 0 Bước 2. Lập bảng đơn hình ban đầu: x1 x2 s1 s2 s3 Z RHS 1 2 1 0 0 0 32 3 4 0 1 0 0 84 0 1 0 0 1 0 12 -50 -80 0 0 0 1 0 Nghiệm khả dĩ cơ sở là (0, 0, 32, 84, 12) *** Z = 0 Biến cơ sở là s1, s2, s3 Chương 4 – Bài toán qui hoạch tuyến tính 10 GV. Nguyen Vu Quang Bước 3. Xác định giá trị xoay + Giao điểm của cột xoay và hàng xoay + Cột xoay là cột có trị âm nhỏ nhất trong hàng dưới cùng + Hàng xoay là hàng có tỷ số dịch chuyển nhỏ nhất + Tỷ số dịch chuyển = RHS / giá trị dương trong cột xoay + Nếu cột xoay không có giá trị dương ⇒ không có lời giải x1 x2 s1 s2 s3 Z RHS 1 2 1 0 0 0 32 3 4 0 1 0 0 84 0 1 0 0 1 0 12 -50 -80 0 0 0 1 0 Bước 4. Thực hiện xoay cho đến khi hàng dưới không âm + Chuyển giá trị xoay thành = 1 + Chuyển các giá trị khác trong cột xoay = 0 x1 x2 s1 s2 s3 Z RHS 1 2 1 0 0 0 32 R1 = R1 + (-2)R3 3 4 0 1 0 0 84 R2 = R2 + (-4)R3 0 1* 0 0 1 0 12 -50 -80 0 0 0 1 0 R4 = R4 + 80R3 x1 x2 s1 s2 s3 Z RHS 1* 0 1 0 -2 0 8 3 0 0 1 -4 0 36 R2 = R2 + (-3)R1 0 1 0 0 1 0 12 -50 0 0 0 80 1 960 R4 = R4 + 50R1 Nghiệm khả dĩ cơ sở mới (0, 12, 8, 36, 0) *** Z = 960 x1 x2 s1 s2 s3 Z RHS 1 0 1 0 -2 0 8 R1 = R1+2R2*1/2 0 0 -3 1 2* 0 12 R2 = R2*1/2 0 1 0 0 1 0 12 R3 = R3 + (-1)R2*1/2 0 0 50 0 -20 1 1360 R4 = R4 + 20R2*1/2 Nghiệm khả dĩ cơ sở mới (8, 12, 0, 12, 0) *** Z = 1360 Chương 4 – Bài toán qui hoạch tuyến tính 11 GV. Nguyen Vu Quang x1 x2 s1 s2 s3 Z RHS 1 0 -2 1 0 0 20 0 0 -3/2 1/2 1 0 6 0 1 3/2 -1/2 0 0 6 0 0 20 10 0 1 1480 Hàng dưới không âm, đạt tối ưu, nghiệm (20, 6, 0, 0, 6), Z=1480 3.3. Phương pháp đơn hình cho bài toán MAX với ràng buộc ≤ và cả ≥ và =: Ví dụ: Giải bài toán QHTT Max Z = x1 – x2 + 3x3 S.t: -x1 - x2 ≥ -20 x1 + x3 = 5 x2 + x3 ≥ 10 x1, x2, x3 ≥ 0 Bước 1. Chuẩn hóa bài toán Làm cho tất cả giá trị RHS thành dương ; (nhân -1, đổi dấu) Với ràng buộc ≤, thêm biến bù (ký hiệu si) Với ràng buộc ≥, thêm biền trừ (-si) và biến nhân tạo Với ràng buộc =, thêm biến nhân tạo (ký hiệu ai) Cộng –Mai vào hàm mục tiêu Z, trong đó M là hằng số rất lớn Tất cả si, ai đều ≥ 0 Ví dụ: Max Z = x1 – x2 + 3x3 – Ma1 – Ma2 x1 + x2 + s1 = 20 x1 + x3 + a1 = 5 x2 + x3 - s2 + a2 = 10 -x1 + x2 - 3x3 +Ma1 +Ma2 + Z = 0 x1, x2, x3, s1, s2, a1, a2 ≥ 0 Chương 4 – Bài toán qui hoạch tuyến tính 12 GV. Nguyen Vu Quang Bước 2. Lập bảng đơn hình sơ bộ và ban đầu Bảng sơ bộ x1 x2 x3 s1 a1 s2 a2 Z RHS 1 1 0 1 0 0 0 0 20 1 0 1 0 1 0 0 0 5 0 1 1 0 0 -1 1 0 10 -1 1 -3 0 M 0 M 1 0 Bảng ban đầu (sau khi loại M trong cột ai) x1 x2 x3 s1 a1 s2 a2 Z RHS 1 1 0 1 0 0 0 0 20 1 0 1* 0 1 0 0 0 5 0 1 1 0 0 -1 1 0 10 R3-R2 -M-1 -M+1 -3-2M 0 0 M 0 1 -15M R4+(3+2M)R2 Nghiệm khả dĩ cơ sở ban đầu (0, 0, 0, 20, 5, 0, 10), Z = -15M Bước 3. Thực hiện xoay đến khi hàng dưới không âm x1 X2 x3 s1 a1 s2 a2 Z RHS 1 1 0 1 0 0 0 0 20 R1-R3 1 0 1 0 1 0 0 0 5 -1 1* 0 0 -1 -1 1 0 5 M+2 -M+1 0 0 2M+3 M 0 1 -5M+15 R4+(M-1)R3 Nghiệm khả dĩ cơ sở (0, 0, 5, 20, 0, 0, 5), Z = -5M+15 x1 X2 x3 s1 a1 s2 a2 Z RHS 2 0 0 1 1 1 -1 0 15 1 0 1 0 1 0 0 0 5 -1 1 0 0 -1 -1 1 0 5 3 0 0 0 M+4 1 M-1 1 10 Hàng dưới không âm, nghiệm khả dĩ (0, 5, 5, 15, 0, 0, 0) Vì các biến nhân tạo a1, a2 đều = 0, bài toán có nghiệm là: x1 = 0, x2 = 5, x3 = 5 và Max Z = 10 (Nếu có một biến nhân tạo ≠ 0 thì bài toán sẽ không có nghiệm) Chương 4 – Bài toán qui hoạch tuyến tính 13 GV. Nguyen Vu Quang 3.4. Phương pháp đơn hình cho bài toán MIN: Chuyển hàm mục tiêu Min Z = Σcjxj thành Max Z* = Σ(–cj)xj và giải như bài toán MAX Ví dụ: Min Z = 2x1 + 4x2 2x1 + x2 ≥ 14 x1 + x2 ≥ 12 x1 + 3x2 ≥ 18 x1, x2 ≥ 0 ⇒ Max Z* = – 2x1 – 4x2 2x1 + x2 ≥ 14 x1 + x2 ≥ 12 x1 + 3x2 ≥ 18 x1, x2 ≥ 0 Bước 1. Chuẩn hóa bài toán (biến bù, trừ, nhân tạo) Max Z* = – 2x1 – 4x2 – Ma1 – Ma2 – Ma3 2x1 + x2 – s1 + a1 = 14 x1 + x2 – s2 + a2 = 12 x1 + 3x2 – s3 + a3 = 18 2x1 + 4x2 + Ma1 + Ma2 + Ma3 +Z = 0 Bước 2. Lập bảng đơn hình sơ bộ và ban đầu Bảng sơ bộ x1 x2 s1 s2 s3 a1 a2 a3 Z RHS 2 1 -1 0 0 1 0 0 0 14 1 1 0 -1 0 0 1 0 0 12 1 3 0 0 -1 0 0 1 0 18 2 4 0 0 0 M M M 1 0 Bảng ban đầu x1 x2 s1 s2 s3 a1 a2 a3 Z RHS 2 1 -1 0 0 1 0 0 0 14 1 1 0 -1 0 0 1 0 0 12 1 3* 0 0 -1 0 0 1 0 18 -4M+2 -5M+4 M M M 0 0 0 1 -44M R1 = R1 - R3*1/3 R2 = R2 - R3*1/3 R3 = R3*1/3 R4 = R4 – (-5M+4)R3*1/3 Chương 4 – Bài toán qui hoạch tuyến tính 14 GV. Nguyen Vu Quang Bước 3. Thực hiện xoay đến khi hàng dưới không âm x1 x2 s1 s2 s3 a1 a2 a3 Z RHS 5/3* 0 -1 0 1/3 1 0 -1/3 0 8 2/3 0 0 -1 1/3 0 1 -1/3 0 6 1/3 1 0 0 -1/3 0 0 1/3 0 6 (-7M+2)/3 0 M M (-2M+4)/3 0 0 (5M-4)/3 1 -14M-24 x1 x2 s1 s2 s3 a1 a2 a3 Z RHS 1 0 -3/5 0 1/5 3/5 0 -1/5 0 24/5 0 0 2/5* -1 1/5 -2/5 1 -1/5 0 14/5 0 1 1/5 0 -2/3 -1/5 0 2/5 0 22/5 0 0 (-2M+2)/5 M (-M+6)/5 (7M-2)/5 0 (6M-6)/5 1 (-14M-136)/5 x1 x2 s1 s2 s3 a1 a2 a3 Z RHS 1 0 0 -3/2 1/2 0 3/2 -1/2 0 9 0 0 1 -5/2 1/2 -1 5/2 -1/2 0 7 0 1 0 1/2 -1/2 0 -1/2 1/2 0 3 0 0 0 1 1 M M-1 M-1 1 -30 Hàng dưới không âm, nghiệm khả dĩ (9, 3, 7, 0, 0, 0, 0, 0) Vì các biến nhân tạo a1, a2, a3 đều = 0, bài toán có nghiệm là: x1 = 9, x2 = 3 và Max Z* = - 30 Vậy bài toán gốc có Min Z = 30 Chương 4 – Bài toán qui hoạch tuyến tính 15 GV. Nguyen Vu Quang IV. Giải bài toán QHTT bằng máy tính: Phương pháp đơn hình: • Khoa học toán • Hiểu rõ bản chất cách giải • Khó thực hiện • Càng khó khi bài toán có từ 5 đến hàng trăm biến Phần mềm máy tính: • Dựa vào thuật toán • Khả năng tính nhanh (hàng triệu phép thử / giây) • ABQM, QSB, LINDO, EXCEL Hướng dẫn sử dụng phần mềm ABQM và Excel: (Sinh viên xem tài liệu phát kèm theo bài giảng)
File đính kèm:
bai_giang_ky_thuat_ra_quyet_dinh_ky_su_chuong_4_qui_hoach_tu.pdf
