Mô hình tối ưu tuyến tính - Quy hoạch tuyến tính

BỐ CỤC BÀI GIẢNG Các ví dụ dẫn đến bài toán Quy hoạch tuyến tính: 1.1 Lập kế hoạch sản xuất: 1.2 Phân bổ vốn đầu tư: 2. Định nghĩa: 1. Các ví dụ dẫn đến bài toán Quy hoạch tuyến tính (QHTT): 1.1 Lập kế hoạch sản xuất: Giả sử rằng sản phẩm sản xuất ra đều có thể tiêu thụ được hết với lợi nhuận khi bán một đơn vị sản phẩm L1, L2, L3 tương ứng là 5000:10000:7000 (đồng). Yêu cầu lập kế hoạch sản xuất tối ưu. Gọi xj là số sản phẩm của Lj (j = 1,2, 3) cần sản xuất (xj ≥ 0, j = 1, 2, 3.) Theo kế hoạch sản xuất phải tìm lượng nguyên liệu tiêu hao là: N1: Mô hình bài toán: Tìm x = (x1, x2, x3) sao cho: Tổng quát: ta có bài toán lập kế hoạch sản xuất dưới dạng bảng số liệu sau đây: Mô hình: Tìm x = (x1, x2,…, xn) sao cho: 2.2 Phân bổ vốn đầu tư: Một nhà đầu tư có 4 tỉ đồng muốn đầu tư vào 4 lĩnh vực Ngoài ra, để giảm thiểu rủi ro, nhà đầu tư cho rằng không nên đầu tư vào cổ phiếu vượt quá 30% tổng số vốn đầu tư; đầu tư vào công trái và gửi tiết kiệm ít nhất 25% tổng vốn đầu tư; gửi tiết kiệm ít nhất 300 triệu đồng. Hãy xác định kế hoạch phân bổ vốn đầu tư sao cho tổng lợi nhuận hàng năm là lớn nhất. Do tổng số tiền đầu tư không được vượt quá số tiền hiện có nên: x1 + x2 + x3 + x4 ≤ 4000 (triệu đồng) Điều kiện về số tiền đầu tư vào chứng khoán: Gọi x1, x2, x3, x4 tương ứng là số tiền (triệu đồng) đầu tư vào chứng khoán, công trái, gửi tiết kiệm, bất động sản ( ) Lãi suất của năm là: Yêu cầu tối ưu: Điều kiện về số tiền đầu tư vào công trái và gửi tiết kiệm: Và Mô hình: Tìm x = ( x1, x2, x3, x4) sao cho: Vậy để lập mô hình toán học của một bài toán thực tế, ta phân tích bài toán đó theo 3 bước sau: Bước 1: Đặt ẩn và điều kiện cho ẩn. Bước 2: Lập hệ ràng buộc chính Bước 3: Lập hàm mục tiêu 2. Định nghĩa: Bài toán quy hoạch tuyến tính dạng tổng quát có dạng: Tìm x = (x1, x2, …,xn) sao cho: Vectơ x=( x1, x2,…, xn) được gọi là phương án (PA) của bài toán QHTT nếu nó thỏa mãn hệ ràng buộc của bài toán Phương án x*=( x1*, x2*, …, xn*) được gọi là phương án tối ưu (PATƯ) của bài toán QHTT nếu giá trị hàm mục tiêu tại đó là tốt nhất. Giải bài toán QHTT tức là tìm phương án tối ưu của nó (nếu có). Một số khái niệm: Bài toán giải được là bài toán có PATƯ. Bài toán không giải được là bài toán không có PATƯ. Khi đó hoặc là bài toán không có phương án hoặc có phương án nhưng hàm mục tiêu không bị chặn ( đối với bài toán max (min)). Nếu phương án x thỏa mãn ràng buộc nào đó với dấu “=” thì ta nói x thỏa mãn chặt ràng buộc đó. Ngược lại nếu thỏa dấu “>” hoặc “<” thì ta nói thỏa mãn lỏng ràng buộc đó. Một số khái niệm: - Ứng với ràng buộc thứ i ta có vectơ Ai* = (ai1, ai2, …,ai3). - Ký hiệu: là vectơ các hệ số của biến xj trong các ràng buộc (không kể ràng buộc dấu). - Hệ vectơ Ai* tương ứng với các ràng buộc chính tạo thành ma trận ràng buộc chính, ký hiệu là A. - Các ràng buộc gọi là ràng buộc độc lập tuyến tính nếu hệ véctơ Ai* tương ứng độc lập tuyến tính. Một số khái niệm: - Phương án cực biên (phương án cơ bản): là phương án thỏa mãn chặt n ràng buộc độc lập tuyến tính. + Phương án cực biên (PACB) thỏa mãn chặt đúng n ràng buộc gọi là PACB không suy biến, PACB thỏa mãn chặt hơn n ràng buộc gọi là PACB suy biến. Một số khái niệm: Ví dụ 1: là một phương án. là một phương án cực biên. Mô hình bài toán: Tìm x = (x1, x2, x3) sao cho: Hàm mục tiêu Hệ ràng buộc chính Hệ ràng buộc dấu 3. Các dạng đặc biệt của bài toán QHTT: a. Bài toán QHTT dạng chính tắc: Định lý: Phương án x của bài toán QHTT dạng chính tắc là phương án cực biên khi và chỉ khi hệ thống các vectơ {Aj} tương ứng với các thành phần dương của phương án là độc lập tuyến tính. Ví dụ 2: Cho bài toán QHTT có hệ ràng buộc: Các phương án x1 = (4; 0; 3; 0); x2 = (2; 1; 0; 0); x3 = (0; 1/2; 0; 3/4) là các PACB theo định lý trên. * Cách biến đổi bài toán QHTT dạng tổng quát về dạng chính tắc: - Nếu có ràng buộc dấu dạng thì đặt x’j = -xj , với . - Nếu xj không có ràng buộc dấu đặt với Nếu có ràng buộc dạng thì thay bằng với Ví dụ 3: đưa bài toán QHTT ở ví dụ 1 về dạng chính tắc. Ví dụ 4: Đưa bài toán QHTT sau về dạng chính tắc. b. Bài toán dạng chuẩn: * Một ma trận chứa các vectơ Aj lập được thành một ma trận đơn vị được gọi là ma trận chứa ma trận đơn vị. * Bài toán QHTT dạng chuẩn là: + Bài toán QHTT dạng chính tắc. + + Ma trận hệ số chứa ma trận đơn vị. Ví dụ: Bằng cách sắp xếp lại bài toán QHTT dạng chuẩn có dạng. Các biến có vecto cột hệ số tạo thành ma trận đơn vị gọi là biến cơ sở. Biến còn lại gọi là biến phi cơ sở. Cách đưa bài toán dạng chính tắc về dạng chuẩn: - Nếu thì nhân hai vế ràng buộc với -1. - Nếu ma trận A chưa có ma trận đơn vị thì thêm vào ẩn giả. Mục tiêu của ẩn giả là để tạo vectơ đơn vị khi chưa có ma trận đơn vị. Nếu trong ma trận A đã có sẵn một số vectơ đơn vị thì chỉ cần thêm ẩn giả vào những phương trình cần thiết để tạo thành bài toán mở rộng có dạng chuẩn. Hệ số của ẩn giả trong hàm mục tiêu là M (-M) nếu f min (max), với M là số dương khá lớn. Ví dụ: Đưa các bài toán QHTT đã được đưa về dạng chính tắc ở các ví dụ 3, 4 về dạng chuẩn.