tailieunhanh - Các phương pháp giải bài toán qui hoạch tuyến tính

Trong các phương pháp giải bài toán qui hoạch tuyến tính, phương pháp đồ thị (Phương pháp hình học) thường được sử dụng. Phương pháp này có ưu điểm là trực quan, dễ hiểu. Tuy nhiên, phương pháp này chỉ dùng để giải những bài toán hai biến quyết định. Về cơ bản phương pháp này gồm hai bước sau: Xác định miền phương án chấp nhận được; Từ đó tìm phương án tối ưu trên miền chất nhận đó. a. Xác định miền chấp nhận bằng đồ. | . Những phương pháp giải bài toán QHTT 50 Phương pháp đồ thị a. Xác định miền chấp nhận được b. Tìm giá trị của hàm mục tiêu trên miền chấp nhận Phương pháp đơn hình a. Thuật toán đơn hình giải bài toán dạng chuẩn b. Thuật toán đơn hình giải bài toán mở rộng c. Giải bằng máy tính . Phương pháp đồ thị Trong các phương pháp giải bài toán qui hoạch tuyến tính phương pháp đồ thị Phương pháp hình học thường được sử dụng. Phương pháp này có ưu điểm là trực quan dễ hiểu. Tuy nhiên phương pháp này chỉ dùng để giải những bài toán hai biến quyết định. Về cơ bản phương pháp này gồm hai bước sau Xác định miền phương án chấp nhận được 0 Từ đó tìm phương án tối ưu trên miền chất nhận đó. a. Xác định miền chấp nhận bằng đồ thị A A Ã 1 Ẳ 1 V A J 1 Ẩ Ấ Ằ 4- 1 Môi trục thê hiện một biên quyêt định Môi ràng buộc vẽ một đường thẳng đê xác định miền chấp nhận Môi đường thẳng chỉ cần vẽ 2 điêm và nối chúng với nhau Chọn một điêm bất kỳ thoả mãn ràng buộc miền chứa điêm đó sẽ là miền chấp nhận thỏa mãn ràng buộc đang xét Giao tất cả các miền chấp nhận của các ràng buộc hình thành vùng chấp nhận của bài toán. Bất cứ điêm nào nằm trên đường biên của vùng chấp nhận hoặc trong vùng chấp nhận được gọi là điêm phương án chấp nhận được đối với bài toán qui .