OR Deterministic Operations Research QUY HOẠCH TUYỀN TÍNH
| QUY HOẠCH TUYỀN TÍNH |
|
QUY HOẠCH TUYỀN TÍNH Nguyễn Như Phong Kỹ thuật Hệ thống Công nghiệp Đại học Bách Khoa TPHCM Mô hình QHTT có mục tiêu và ràng buộc là những hàm tuyến tính với các tính chất sau:
Thuộc tính tuyến tính thể hiện ở chỗ đóng góp của mỗi biến vào hàm mục tiêu và các ràng bụôc là tỷ lệ thuận với giá trị biến. Thuộc tính cộng tính thể hiện ở chỗ đóng góp của mọi biến vào hàm mục tiêu và các ràng buộc là tổng của các đóng góp thành phần của các biến. Thuộc tính xác định thể hiện ở chỗ mọi hệ số trong hàm mục tiêu và các ràng buộc đều là các hằng số xác định. Điều này có thể không thực tế vì thực tế các hệ số này thường là biến thiên. Tuy nhiên nếu biến thiên nhỏ ta có thể sử dụng các giá trị kỳ vọng, còn với biến thiên lớn thì có thể phân tích độ nhạy của lời giải theo biến thiên của các tham số đầu vào. Ví dụ: Bài toán cực đại: Max Z = 5x1 + 4x2 St. 6x1 + 4x2 £ 24 x1 + 2x2 £ 6 x2 £ 2 x2 – x1 £ 1 x1 ³ 0 x2 ³ 0 Bài toán cực tiểu: Min z = 3x1 + 9x2 St x1 + x2 ³ 800 0,21 x1 – 0,3x2 £ 0 0,03 x1 – 0,01 x2 ³ 0 x1 ³ 0 x2 ³ 0 Lời giải khả thi là lời giải không vi phạm các ràng buộc, ngược lại lời giải không khả thi là lời giải vi phạm các ràng buộc của bài toán. Lời giải tối ưu là lời giải khả thi tốt nhất. Để tìm lời giải tối ưu đầu tiên ta phải tìm tất cả các lời giải khả thi rồi sử dụng hàm mục tiêu để đánh giá tất cả các lời giải khả thi, xem lời giải nào tốt nhất thì đó là lời giải tối ưu. Thực tế cho thấy số lời giải khả thi của 1 bài toán thường là vô hạn nên không thể sử dụng phương pháp đơn giản trên để xác định lời giải tối ưu. Để tìm lời giải tối ưu ta có thể dùng phương pháp hình học với một số bước hữu hạn có hệ thống. Phương pháp hình học tuy đơn giản và trực quan nhưng chỉ có thể giải các bài toán hai biến với bài toán nhiều biến tổng quát ta có thể dùng phương pháp đại số là phương pháp suy diễn và khái quát hóa từ phương pháp hình học.
TLTK Nguyễn Như Phong. Vận trù xác định. NXBĐHQG. 2010
|
