Tính chất chung của bài toán quy hoạch tuyến tính

Giải hệ phương trình tuyến tính tổng quátCác bước giải:Lập bảng các hệ số cho hệ đã choXác nhận các ẩn cơ sở đã có3. Tìm thêm ẩn cơ sở mớiChọ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.
Nội dung trích xuất từ tài liệu:
Tính chất chung của bài toán quy hoạch tuyến tínhBÀI 2 ́ lai:Nhăc ̣•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átCác bước giải:1. Lập bảng các hệ số cho hệ đã cho2. Xác nhận các ẩn cơ sở đã có3. Tìm thêm ẩn cơ sở mớiChọ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í du:̣ giaỉ hệ phương trinh: ̀ 2 x1 + x2 − 3x3 + x4 = 2 − x1 + 3 x2 + x3 − 2 x4 = −1Ví du:̣ giaỉ hệ phương trinh: ̀ 2 x1 + 4 x2 + 2 x3 = 15 x1 + 5 x2 + 3 x3 = 17 4 x1 + 5 x2 + 4 x3 = 27GIẢI: b x1 x2 x3 [2] 4 2 15 1 5 3 17 27 4 5 4 15/2 1 2 1 19/2 0 3 [2] -3 0 -3 0 11/4 1 1/2 0 19/4 0 3/2 1 -3 0 [-3] 0 1 0 0 9/4 0 0 1 13/4 0 1 0 1Tìm nghiệm cơ bản không âmThuật toán:1. Làm bi>=0 với ∀I2. 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 âmNếu hệ không cơ bản chuyển qua bước 44. Chọn ẩn cơ sở mới-Chọn xj.-Chọn phần tử chủ yếu-Xét �bk � br min � �= akj > 0 a arj kj-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 b i>0 và aij ≤0với mọi j thì phương trình đó không có nghiệm không âmdo đó 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ìnhtuyến tính sau: −2 x1 − x2 + 3x3 + x4 = 1 − x1 + 2 x2 + x3 + 2 x4 = 5 ́ tinh1. Cac ́ chât́ chung cua ̉ baì toan ́ QHTT : ́* Tinh chât́ 1: sự tôn ̀ taị PACB cua ̉ baì toan. ́ ́ baì toanNêu ́ QHTT có phương an ́ và hang ̣ cua ̉ ma trân ̣hệ rang ̀ buôc ̣ băng ̀ n (n là số biên) ́ thì baì toan ́ 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. ́* Tinh chât́ 2: sự tôn ̀ taị phương an ́ tôí ưu cua ̉ baì toan. ́Baì toan ́ QHTT có PATƯ khi và chỉ khi nó có phương an ́và trị số ham ̀ muc ̣ tiêu bị chăn ̣ dưới (trên) khi f(x) => ̣ phương an.min (max) trên tâp ́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Ư. ́* Tinh chât́ 3: số phương an ́ cực biên cua ̉ baì toan ́ dang ̣ ́ tăcchinh ́ là hữu han. ̣Ví dụ: tìm tất cả các phương án cực biên của bài toán QHTTcó hệ ràng buộc: x1 + 2 x2 + 4 x4 = 4 3 x2 + x3 + 2 x4 = 3 xj 0, ∀j = 1,4xB b x1 x2 x3 x4x1 4 1 2 0 4x3 3 0 3 1 2x1 2 1 0 -2/3 8/3x2 1 0 1 1/3 2/3x4 ¾ 3/8 0 -1/4 1x2 ½ -1/4 1 ½ 0x4 1 ¼ ½ 0 1x3 1 -1/2 2 1 02. Phương phap ́ đơn hinh̀ cho baì toan ́ QHTT:A. Thuâṭ toan ́ đơn hinh̀ cho baì toan ́ QHTT dang ̣ chuân: ̉Ví dụ 1: Giaỉ baì toan ́ QHTT sau băng̀ phương phap ́ đơn ̀hinh: f ( x ) = 2 x1 − x2 + 2 x3 + x4 min x1 + 2 x2 + x5 =2 −3 x1 + 4 x2 + x4 + x6 = 20 x1 + 2 x2 + x3 + 3x4 = 18 xj 0 ( j = 1,...,6 )a. Trường hợp baì toan ́ ...