Các tính chất chung của bài toán quy hoạch tuyến tính và phương pháp đơn hình

BÀI 2 Nhắc lại: Hệ phương trình tuyến tính: Hệ cơ bản Ẩn cơ bản Giải hệ phương trình tuyến tính tổng quát Các bước giải: Lập bảng các hệ số cho hệ đã cho Xác nhận các ẩn cơ sở đã có 3. Tìm thêm ẩn cơ sở mới Chọn ẩn cơ sở xj (xj chưa là ẩn cơ sở) Chọn phần tử chủ yếu aịj trên cột j (điều kiện aij khác 0) Tính các hệ số cho bảng mới theo quy tắc hình chữ nhật. Ví dụ: giải hệ phương trình: Ví dụ: giải hệ phương trình: GIẢI: Tìm nghiệm cơ bản không âm Thuật toán: 1. Làm bi>=0 với I 2. Lập bảng hệ số 3. Xác nhận các ẩn cơ sở đã có Nếu là hệ cơ bản viết nghiệm cơ bản không âm Nếu hệ không cơ bản chuyển qua bước 4 4. Chọn ẩn cơ sở mới Chọn xj. Chọn phần tử chủ yếu Xét Lấy arj làm phần tử chủ yếu Tính các hệ số cho bảng mới theo quy tắc hình chữ nhật. Lặp lại thuật toán từ bước 3. chú ý: nếu như trong quá trình tìm nghiệm cơ bản không âm xuất hiện một dòng nào đó có hệ số tự do bi>0 và aij≤0 với mọi j thì phương trình đó không có nghiệm không âm do đó cả hệ không có nghiệm không âm. Ví dụ: tìm nghiệm cơ bản không âm của hệ phương trình tuyến tính sau: 1. Các tính chất chung của bài toán QHTT : * Tính chất 1: sự tồn tại PACB của bài toán. Nếu bài toán QHTT có phương án và hạng của ma trận hệ ràng buộc bằng n (n là số biến) thì bài toán có PACB. Hệ quả: Bài toán QHTT dạng chính tắc nếu có phương án thì sẽ có PACB. * Tính chất 2: sự tồn tại phương án tối ưu của bài toán. Bài toán QHTT có PATƯ khi và chỉ khi nó có phương án và trị số hàm mục tiêu bị chặn dưới (trên) khi f(x) => min (max) trên tập phương án. Hệ quả: Nếu bài tóan có PACB và thỏa điều kiện trên thì sẽ có PACB tối ưu. Nếu bài toán QHTT dạng chính tắc có PATƯ thì sẽ có một PACB là PATƯ. * Tính chất 3: số phương án cực biên của bài toán dạng chính tắc là hữu hạn. Ví dụ: tìm tất cả các phương án cực biên của bài toán QHTT có hệ ràng buộc: 2. Phương pháp đơn hình cho bài toán QHTT: A. Thuật toán đơn hình cho bài toán QHTT dạng chuẩn: Ví dụ 1: Giải bài toán QHTT sau bằng phương pháp đơn hình: a. Trường hợp bài toán min: Thuật toán: Bước 1: lập bảng đơn hình xuất phát. (cột 1) (Aj) - cj f(x0) = (cột 1) * (cột 3) Chú ý: nếu xj là ẩn cơ bản thì Bước 2: Đánh giá tính tối ưu của PACB xuất phát x0 + Nếu thì x0 là PATƯ Ta có giá trị tối ưu là f(x0). Bài toán kết thúc. + Nếu tồn tại mà > 0 thì x0 không phải là PATƯ chuyển sang bước 3. Bước 3: Kiểm tra tính không giải được của bài toán. + Nếu tồn tại một > 0 mà ajk 0, với (J0 là tập chỉ số cơ sở của phương án x0) Thì bài toán không giải được vì hàm mục tiêu không bị chặn. + Nếu với mỗi > 0 đều có ít nhất ajk > 0 thì chuyển sang bước 4. Bước 4: điều chỉnh PACB. + Chọn vectơ đưa vào cơ sở. Tìm max với > 0. Giả sử max = thì vectơ As dược đưa vào cơ sở. Tính Giả sử: thì vectơ Ar bị loại khỏi cơ sở, phần tử ars gọi là phần tử trục của bảng. Bước 5: lập bảng đơn hình thứ 2. Ở vị trí xr ghi xs và ghi cs thay cr Tính các dòng trong bảng mới (từ dòng thứ ba trở đi) - Để tính dòng ứng với vectơ đưa vào (ứng với xs) lấy dòng ứng với vectơ loại ra (ứng với xr) trong bảng cũ chia phần tử trục. Dòng này được gọi là dòng chuẩn. - Để tính dòng ứng với xj ta sử dụng quy tắc hình chữ nhật. - Để tính dòng cuối trong bảng ta cũng sử dụng quy tắc hình chữ nhật. Sau bảng đơn hình mới ta có PACB mới x1. Đối với x1 quay trở lại bước 1 và lặp lại quá trình sau hữu hạn bước ta có kết luận bài toán. Ví dụ 2: b) Trường hợp bài toán Max: Bài toán 1: f(x) max. Cách 1: Giải bài toán 2: g(x) = - f(x) min gmin = g(x*) thì bài toán 1 có PATƯ là x* và fmax = - g(x*) Cách 2: Sử dụng phương pháp đơn hình, tương tự với bài toán min. Bước 1: giống bài toán min. Bước 2: thì x0 là PATƯ. + Nếu tồn tại thì x0 không phải là PATƯ, sang bước 3. Bước 3: + Nếu tồn tại mà thì bài toán không giải được. + Nếu mỗi tồn tại thì chuyển sang bước 4. Bước 4: + Chọn vectơ đưa vào cơ sở: Tìm min với giả sử thì vectơ được đưa vào cơ sở. + Chọn vectơ đưa ra khỏi cơ sở: giống bài toán min. Bước 5: giống bài toán min. Ví dụ: Đáp số: x* = (15/2, 0, 9/2), f(x*) = 231