Quy hoạch tuyến tính - Nguyễn Phúc Sơn

Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Chương 4: Quy hoạch tuyến tính Tiến sĩ Nguyễn Phúc Sơn Trường Đại học Kinh tế - Luật Đại học Quốc gia Thành phố Hồ Chí Minh Ngày 25 tháng 10 năm 2014 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Table of Contents 1 Bài toán mở đầu 2 Các dạng bài toán quy hoạch tuyến tính 3 Phương pháp đơn hình (simplex method) Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) SilComputers Đề bài SilComputer cần xác định số lượng laptop và desktop sản xuất trong quý tới. Mục tiêu của hãng là tối đa hóa lợi nhuận. Biết rằng bán 1 laptop lời $750 và bán 1 desktop lời $1000. Tuy nhiên, hãng bị các ràng buộc sau: 1 Mỗi máy tính cần 1 CPU và trong kho có 10,000 bộ CPU 2 Trong kho có 15,000 bộ 16MB memory chipset. Mỗi laptop được gắn 16MB và mỗi desktop được gắn 32MB 3 Cần 4 phút để ráp 1 laptop và 3 phút để ráp 1 desktop. Tổng số phút lao động là 25,000 phút. Tìm lời giải tối ưu cho bài toán. Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) SilComputers Đề bài SilComputer cần xác định số lượng laptop và desktop sản xuất trong quý tới. Mục tiêu của hãng là tối đa hóa lợi nhuận. Biết rằng bán 1 laptop lời $750 và bán 1 desktop lời $1000. Tuy nhiên, hãng bị các ràng buộc sau: 1 Mỗi máy tính cần 1 CPU và trong kho có 10,000 bộ CPU 2 Trong kho có 15,000 bộ 16MB memory chipset. Mỗi laptop được gắn 16MB và mỗi desktop được gắn 32MB 3 Cần 4 phút để ráp 1 laptop và 3 phút để ráp 1 desktop. Tổng số phút lao động là 25,000 phút. Tìm lời giải tối ưu cho bài toán. Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Mô hình Đặt x1 là số laptops định sản xuất và x2 là số desktops định sản xuất. (decision variables) Hàm mục tiêu: z = 750x1 + 1000x2 (objective function) Các ràng buộc : (Đơn vị: 1000) (constraints) 1 x1 + x2 ≤ 10 2 x1 + 2x2 ≤ 15 3 4x1 + 3x2 ≤ 25 4 Ràng buộc tự nhiên về dấu x1, x2 ≥ 0 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Mô hình Đặt x1 là số laptops định sản xuất và x2 là số desktops định sản xuất. (decision variables) Hàm mục tiêu: z = 750x1 + 1000x2 (objective function) Các ràng buộc : (Đơn vị: 1000) (constraints) 1 x1 + x2 ≤ 10 2 x1 + 2x2 ≤ 15 3 4x1 + 3x2 ≤ 25 4 Ràng buộc tự nhiên về dấu x1, x2 ≥ 0 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Mô hình Đặt x1 là số laptops định sản xuất và x2 là số desktops định sản xuất. (decision variables) Hàm mục tiêu: z = 750x1 + 1000x2 (objective function) Các ràng buộc : (Đơn vị: 1000) (constraints) 1 x1 + x2 ≤ 10 2 x1 + 2x2 ≤ 15 3 4x1 + 3x2 ≤ 25 4 Ràng buộc tự nhiên về dấu x1, x2 ≥ 0 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Thuật ngữ Phương án (PA): Mỗi bộ giá trị (α1, α2) của (x1, x2) thỏa mãn tất cả các ràng buộc được gọi là 1 phương án (feasible solution). Tập phương án hay miền ràng buộc: Tập hợp tất cả các phương án của bài toán (feasible region). Phương án tối ưu (PATU): PA (α1, α2) làm cho hàm mục tiêu z đạt max được gọi là 1 PATU. Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Thuật ngữ Phương án (PA): Mỗi bộ giá trị (α1, α2) của (x1, x2) thỏa mãn tất cả các ràng buộc được gọi là 1 phương án (feasible solution). Tập phương án hay miền ràng buộc: Tập hợp tất cả các phương án của bài toán (feasible region). Phương án tối ưu (PATU): PA (α1, α2) làm cho hàm mục tiêu z đạt max được gọi là 1 PATU. Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Thuật ngữ Phương án (PA): Mỗi bộ giá trị (α1, α2) của (x1, x2) thỏa mãn tất cả các ràng buộc được gọi là 1 phương án (feasible solution). Tập phương án hay miền ràng buộc: Tập hợp tất cả các phương án của bài toán (feasible region). Phương án tối ưu (PATU): PA (α1, α2) làm cho hàm mục tiêu z đạt max được gọi là 1 PATU. Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Lời giải hình học Ràng buộc 1 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Lời giải hình học (tt) Miền ràng buộc Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Lời giải hình học (tt) Lời giải Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Lời giải hình học (tt) Từ hình vẽ, ta thấy PATU xảy ra tại giao điểm của 2 đường thẳng x1 + 2x2 = 15 4x1 + 3x2 = 25 Từ đó PATU là (1, 7) tương ứng với lợi nhuận tối đa z = $7, 750, 000. Nhận xét PATU chỉ xảy ra trên biên của miền ràng buộc. Trong phần lớn trường hợp, PATU chỉ xảy ra trên đỉnh của đa diện ràng buộc. Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Lời giải hình học (tt) Từ hình vẽ, ta thấy PATU xảy ra tại giao điểm của 2 đường thẳng x1 + 2x2 = 15 4x1 + 3x2 = 25 Từ đó PATU là (1, 7) tương ứng với lợi nhuận tối đa z = $7, 750, 000. Nhận xét PATU chỉ xảy ra trên biên của miền ràng buộc. Trong phần lớn trường hợp, PATU chỉ xảy ra trên đỉnh của đa diện ràng buộc. Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Lời giải hình học (tt) Từ hình vẽ, ta thấy PATU xảy ra tại giao điểm của 2 đường thẳng x1 + 2x2 = 15 4x1 + 3x2 = 25 Từ đó PATU là (1, 7) tương ứng với lợi nhuận tối đa z = $7, 750, 000. Nhận xét PATU chỉ xảy ra trên biên của miền ràng buộc. Trong phần lớn trường hợp, PATU chỉ xảy ra trên đỉnh của đa diện ràng buộc. Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Table of Contents 1 Bài toán mở đầu 2 Các dạng bài toán quy hoạch tuyến tính 3 Phương pháp đơn hình (simplex method) Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Dạng tổng quát (Dạng (G)) Yêu cầu: Tất cả các ràng buộc cũng như hàm mục tiêu đều là phương trình hay bất phương trình tuyến tính của các biến số. Ví dụ f = x1 + 2x2 − 5x3 + 3x4 − 2x5 + 5x6 −→ min 2x1 − x2 + 4x3 − 2x4 − 3x5 + 4x6 = 4 x1 + 3x2 − 2x3 + 6x4 − 4x5 + 2x6 ≤ 6 3x1 − 2x2 + 3x3 ≥ 5 x1 ≥ 0, x2 ≤ 0 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Dạng tổng quát (Dạng (G)) Yêu cầu: Tất cả các ràng buộc cũng như hàm mục tiêu đều là phương trình hay bất phương trình tuyến tính của các biến số. Ví dụ f = x1 + 2x2 − 5x3 + 3x4 − 2x5 + 5x6 −→ min 2x1 − x2 + 4x3 − 2x4 − 3x5 + 4x6 = 4 x1 + 3x2 − 2x3 + 6x4 − 4x5 + 2x6 ≤ 6 3x1 − 2x2 + 3x3 ≥ 5 x1 ≥ 0, x2 ≤ 0 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Dạnh chính tắc - Dạng (C) Yêu cầu: Tất cả các rang buộc đều ở dạng phương trình và tất cả các biến đều không âm Ví dụ f = x1 + 2x2 − 5x3 + 3x4 −→ max 2x1 − x2 + 4x3 − 2x4 = 3 x1 + 3x2 − 2x3 + 6x4 = 8 xj ≥ 0, j = 1, 2, 3, 4 Lưu ý Mọi bài toán max f tương đương với bài min−f Mọi bài dạng (G) đều có thể được biến đổi về dạng (C) Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Dạnh chính tắc - Dạng (C) Yêu cầu: Tất cả các rang buộc đều ở dạng phương trình và tất cả các biến đều không âm Ví dụ f = x1 + 2x2 − 5x3 + 3x4 −→ max 2x1 − x2 + 4x3 − 2x4 = 3 x1 + 3x2 − 2x3 + 6x4 = 8 xj ≥ 0, j = 1, 2, 3, 4 Lưu ý Mọi bài toán max f tương đương với bài min−f Mọi bài dạng (G) đều có thể được biến đổi về dạng (C) Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Dạnh chính tắc - Dạng (C) Yêu cầu: Tất cả các rang buộc đều ở dạng phương trình và tất cả các biến đều không âm Ví dụ f = x1 + 2x2 − 5x3 + 3x4 −→ max 2x1 − x2 + 4x3 − 2x4 = 3 x1 + 3x2 − 2x3 + 6x4 = 8 xj ≥ 0, j = 1, 2, 3, 4 Lưu ý Mọi bài toán max f tương đương với bài min−f Mọi bài dạng (G) đều có thể được biến đổi về dạng (C) Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Dạnh chính tắc chuẩn - Dạng (N) Yêu cầu: Giả sử dạng chính tắc có hệ ràng buộc với m phương trình. Khi đó, ta nói dạng chính tắc là chuẩn nếu Mỗi phương trình đều có vế phải không âm. Ma trận hệ số chứa 1 ma trận con sơ cấp đơn giản cấp m (tức là ma trận có được từ Im bằng cách đổi chỗ các dòng) Lưu ý: Yếu cầu 2 nói rằng hệ các phương trình ràng buộc là độc lập (hay nói cách khác ta không thể bỏ đi bất kỳ ràng buộc nào mà không làm thay đổi nghiệm bài toán) Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Dạnh chính tắc chuẩn - Dạng (N) Yêu cầu: Giả sử dạng chính tắc có hệ ràng buộc với m phương trình. Khi đó, ta nói dạng chính tắc là chuẩn nếu Mỗi phương trình đều có vế phải không âm. Ma trận hệ số chứa 1 ma trận con sơ cấp đơn giản cấp m (tức là ma trận có được từ Im bằng cách đổi chỗ các dòng) Lưu ý: Yếu cầu 2 nói rằng hệ các phương trình ràng buộc là độc lập (hay nói cách khác ta không thể bỏ đi bất kỳ ràng buộc nào mà không làm thay đổi nghiệm bài toán) Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Dạnh chính tắc chuẩn - Dạng (N) Yêu cầu: Giả sử dạng chính tắc có hệ ràng buộc với m phương trình. Khi đó, ta nói dạng chính tắc là chuẩn nếu Mỗi phương trình đều có vế phải không âm. Ma trận hệ số chứa 1 ma trận con sơ cấp đơn giản cấp m (tức là ma trận có được từ Im bằng cách đổi chỗ các dòng) Lưu ý: Yếu cầu 2 nói rằng hệ các phương trình ràng buộc là độc lập (hay nói cách khác ta không thể bỏ đi bất kỳ ràng buộc nào mà không làm thay đổi nghiệm bài toán) Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Phương án cực biên (PACB) Định nghĩa Đối với bài toán (G): Một PA x? = (x?1 , . . . , x ? n ) được gọi là 1 PACB nếu nó thỏa mãn dấu “=" với ít nhất n ràng buộc, trong đó có đúng n ràng buộc độc lập tuyến tính, nghĩa là ma trận hệ số của n ràng buộc đó có hạng bằng n Đối với bài toán (C): Một PA x? = (x?1 , . . . , x ? n ) được gọi là 1 PACB nếu hệ các cột của ma trận hệ số ứng với các x?j > 0 lập thành một hệ độc lập tuyến tính Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Phương án cực biên (PACB) Định nghĩa Đối với bài toán (G): Một PA x? = (x?1 , . . . , x ? n ) được gọi là 1 PACB nếu nó thỏa mãn dấu “=" với ít nhất n ràng buộc, trong đó có đúng n ràng buộc độc lập tuyến tính, nghĩa là ma trận hệ số của n ràng buộc đó có hạng bằng n Đối với bài toán (C): Một PA x? = (x?1 , . . . , x ? n ) được gọi là 1 PACB nếu hệ các cột của ma trận hệ số ứng với các x?j > 0 lập thành một hệ độc lập tuyến tính Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Table of Contents 1 Bài toán mở đầu 2 Các dạng bài toán quy hoạch tuyến tính 3 Phương pháp đơn hình (simplex method) Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Trở lại ví dụ SilComputer Bảng đơn hình bắt đầu Biến cơ sở Hệ số cơ sở PACB x1 x2 x3 x4 x5 λi-0,75 -1 0 0 0 x3 0 10 1 1 1 0 0 10 x4 0 15 1 2 0 1 0 15/2 x5 0 25 4 3 0 0 1 25/3 Bảng 0 0 0,75 1 0 0 0 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Ví dụ (tt) Vị trí xuất phát Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Trở lại ví dụ SilComputer (tt) Biến cơ sở Hệ số cơ sở PACB x1 x2 x3 x4 x5 λi-0,75 -1 0 0 0 x3 0 2,5 0,5 0 1 -0,5 0 5 x2 -1 15/2 1/2 1 0 1/2 0 15 x5 0 2,5 5/2 0 0 -3/2 1 1 Bảng 1 -15/2 1/4 0 0 -1/2 0 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Ví dụ (tt) Sau 1 bước Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Trở lại ví dụ SilComputer (tt) Biến cơ sở Hệ số cơ sở PACB x1 x2 x3 x4 x5 λi-0,75 -1 0 0 0 x3 0 2 0 0 1 1/4 -1/5 x2 -1 7 0 1 0 5/4 -1/5 x1 -0,75 1 1 0 0 -3/5 2/5 Bảng 2 -7,75 0 0 0 -4/5 -1/10 Lời giải tối ưu Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Ví dụ (tt) Nghiệm tối ưu Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Vô số nghiệm - Vô nghiệm Vô số nghiệm Dấu hiệu bài toán vô số nghiệm: Khi kiểm tra điều kiện tối ưu, nếu mọi ∆j ≤ 0 (đối với bài toán MIN) đồng thời tại môt ∆j = 0 ứng với biến phi cơ sở xj thì bài toán có vô số nghiệm. Ví dụ x1 + 1 2 x2 −→ max 2x1 + x2 ≤ 4 x1 + 2x2 ≤ 3 x1, x2 ≥ 0 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Vô số nghiệm - Vô nghiệm Vô số nghiệm Dấu hiệu bài toán vô số nghiệm: Khi kiểm tra điều kiện tối ưu, nếu mọi ∆j ≤ 0 (đối với bài toán MIN) đồng thời tại môt ∆j = 0 ứng với biến phi cơ sở xj thì bài toán có vô số nghiệm. Ví dụ x1 + 1 2 x2 −→ max 2x1 + x2 ≤ 4 x1 + 2x2 ≤ 3 x1, x2 ≥ 0 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Vô nghiệm tối ưu Khi chọn được biến vào (từ phi cơ sở thành cơ sở) nhưng không chọn được biến ra (từ cơ sở thành phi cơ sở) thì bài toán vô nghiệm tối ưu (lưu ý: Đây là trường hợp miền ràng buôc không bị chặn nên vẫn có phương án khả thi). Ví dụ 2x1 + x2 −→ max −x1 + x2 ≤ 1 x1 − 2x2 ≤ 2 x1, x2 ≥ 0 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính Bài toán mở đầu Các dạng bài toán quy hoạch tuyến tính Phương pháp đơn hình (simplex method) Vô nghiệm tối ưu Khi chọn được biến vào (từ phi cơ sở thành cơ sở) nhưng không chọn được biến ra (từ cơ sở thành phi cơ sở) thì bài toán vô nghiệm tối ưu (lưu ý: Đây là trường hợp miền ràng buôc không bị chặn nên vẫn có phương án khả thi). Ví dụ 2x1 + x2 −→ max −x1 + x2 ≤ 1 x1 − 2x2 ≤ 2 x1, x2 ≥ 0 Tiến sĩ Nguyễn Phúc Sơn Chương 4: Quy hoạch tuyến tính