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 đồ...
Nội dung trích xuất từ tài liệu:
Các phương pháp giải bài toán qui hoạch tuyến tính 2.3. Những phương pháp giải bài toán QHTT 50 2.3.1. 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 2.3.2. 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 2.3.1. Phương pháp đồ thị 51 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 đồ thị 52 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 hoạch. a. Tiếp 53 70 Nguyên liệu 3 Số tấn chất bazơ hoà tan 60 50 40 30 Nguyên liệu 2 20 Vùng chấp nhận Nguyên liệu 1 10 0 0 10 20 30 40 50 Số tấn chất phụ gia b. Tìm giá trị của hàm mục tiêu trên miền chấp nhận 54 70 Số tấn chất bazơ hoà tan Phương án tối ưu 60 F=25, B=20 50 40 30 20 10 0 0 10 20 30 40 50 Số tấn chất phụ gia Tóm tắt về phương pháp đồ thị 55 Vẽ đồ thị các ràng buộc: Mỗi ràng buộc vẽ một đường thẳng và xác định miền chấp nhận được của mỗi ràng buộc; Xác định vùng chấp nhận được: Giao của các miền chấp nhận của tất cả những ràng buộc của bài toán; Vẽ đường mục tiêu Cho hàm mục tiêu bằng một giá trị bất kỳ và vẽ đường mục tiêu. Đối với bài toán cực đại, tịnh tiến đường mục tiêu trong vùng chấp nhận theo hướng làm giá trị của hàm mục tiêu lớn hơn cho đến khi giá trị của hàm mục tiêu lớn nhất (đối với bài toán cực tiểu thì ngược lại); Bất kỳ phương án trên đường mục tiêu với giá trị lớn nhất (đối với bài toán cực đại) là phương án tối ưu. 2.3.2. Phương pháp đơn hình 56 Cơ sở toán học của phương pháp 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 d. Cơ sở toán của phương pháp 57 Tính chất 1: Nếu bài toán có phương án tối ưu thì cũng có phương án cơ bản tối ưu. Tính chất 2: Số phương án cơ bản là hữu hạn. Tính chất 3: Điều kiện cần và đủ để bài toán có phương án tối ưu là hàm mục tiêu của nó bị chặn dưới khi f(x)→min và bị chặn trên khi f(x)→max trên tập phương án. Thuật toán bài toán Min 58 Bước 1: Chuyển bài toán về dạng chuẩn Bước 2: Lập bảng đơn hình đầu tiên Biến x1 x2 … xr … xm xm+1 … xv … xn Tỷ số cơ H ệ P.án λi bản số c ...