QUY HOẠCH RỜI RẠC - CHƯƠNG 3

THUẬT TOÁN GOMORY THỨ NHẤTTrong chương này sẽ trình bày thuật toán Gomory thứ nhất và chứng minh sự hội tụ của nó.1. TƯ TƯỞNG PHƯƠNG PHÁP CẮT 1.1. Việc giải bài toán quy hoạch tuyến tính nguyên (LN ,C ) có dẫn tới việc giảimột bài toán quy hoạch tuyến tính (A,C ) không ?Định lý 1. Giả sử L là một đa diện lồi, LN là tập các điểm nguyên của nó,R ≡ V (LN ) là bao lồi tuyến tính của tập các điểm nguyên LN . Khi đó:1) R ≡ V (LN ) là một...
Nội dung trích xuất từ tài liệu:
QUY HOẠCH RỜI RẠC - CHƯƠNG 3Bùi Thế Tâm III.1 Quy hoạch rời rạcChương 3 THUẬT TOÁN GOMORY THỨ NHẤT Trong chương này sẽ trình bày thuật toán Gomory thứ nhất và chứng minh sự hộitụ của nó.1. TƯ TƯỞNG PHƯƠNG PHÁP CẮT 1.1. Việc giải bài toán quy hoạch tuyến tính nguyên (LN ,C ) có dẫn tới việc giảimột bài toán quy hoạch tuyến tính (A,C ) không ? Định lý 1. Giả sử L là một đa diện lồi, LN là tập các điểm nguyên của nó,R ≡ V (LN ) là bao lồi tuyến tính của tập các điểm nguyên LN . Khi đó: 1) R ≡ V (LN ) là một đa diện nguyên (các đỉnh đều là nguyên) 2) RN = LN (1) 3) Tập R* các phương án tựa của đa diện R chứa trong RN : R* ⊆ RN (2) Chứng minh 1) Chứng minh R là một đa diện nguyên ? Vì L là một đa diện lồi nên LN là tậphữu hạn ⇒ R ≡ V (LN ) là tổ hợp lồi tuyến tính của một tập hữu hạn . Vì vậy, R làmột đa diện , đồng thời R* ⊆ LN (3)(tức là R là đa diện nguyên). 2) Chứng minh RN = LN ? Từ định nghĩa bao lồi tuyến tính suy ra LN ⊆ V (LN ) ≡ R ⇒ LN ⊆ RN . (4)Ta phải chứng minh: RN ⊆ LN ? (5)Thật vậy, giả sử lấy x ∈ RN , (6)vì LN ⊆ L nên R = V (LN ) ⊆ V (L) = L . Vì vậy x ∈ RN ⊆ R ⊆ L (7)Từ (6) và (7) suy ra x ∈ LN (vì x là nguyên thuộc L), vậy (5) được chứng minh. Từ (4) và (5) suy ra đẳng thức (1) đúng. 3) Chứng minh R* ⊆ R N ? Từ (3) và (1) suy ra (2) đúng. http://www.ebook.edu.vnBùi Thế Tâm III.2 Quy hoạch rời rạc Hệ quả 1. Giả sử X (R,C ) là phương án tựa tối ưu của bài toán (R,C ) , khi đóX (R,C ) cũng là phương án tối ưu của bài toán (LN ,C ) . Vì vậy để giải bài toán quyhoạch tuyến tính nguyên (LN ,C ) ta đi giải bài toán (R,C ) . 1.2. Ta sẽ chứng minh: R = V (LN ) là đa diện nguyên duy nhất mà tập các điểmnguyên của nó trùng với LN . Định lý 2. Giả sử L là một đa diện lồi, U là một đa diện lồi nguyên và U N = LN (8)Khi đó U = R = V (LN ) (9) Chứng minh. Từ (8) trực tiếp suy ra R ⊆U (10)( vì R = V ( LN ) = V (U N ) ⊆ U ) Ta phải chứng minh: U ⊆R ? (11)Vì U là đa diện nguyên (tất cả các đỉnh của nó là nguyên) và (8) nên U * ⊆ U N = LN ,suy ra U =V (U * ) ⊆ V (LN ) ≡ R . Vậy (11) là đúng.. Từ (10) và (11) ta có điều cần chứng minh (9). 1.3.Ví dụ http://www.ebook.edu.vnBùi Thế Tâm III.3 Quy hoạch rời rạc BÀI TOÁN (LN ,C ) BÀI TOÁN (L,C ) BÀI TOÁN R ≡ V (LN ,C ) Max x1 + x 2 Max( x1 + x 2 ) Max( x1 + x 2 ) 2x1 + 11x 2 ≤ 38 (a) x 2 ≤ 3 2x1 + 11x 2 ≤ 38 (b) x1 + x 2 ≤ 5 x1 + x 2 ≤ 7 x1 + x 2 ≤ 7 (c) x1 − x 2 ≤ 1 4x1 − 5x 2 ≤ 5 4x1 − 5x 2 ≤ 5 xj ≥ 0 xj ≥ 0 xj ≥ 0 x j nguyên Max=5. Max=7 Max=5 Tối ưu là 2 điểm Tối ưu là một đoạn Tối ưu là đoạn 13 8 40 23 (2,3); (3,2) [( ; ); ( ; )] [(2,3);(3,2) ] 33 99 1.4. Từ Hệ quả 1 chỉ ra khả năng xấp xỉ đúng bài toán (LN ,C ) bằng bài toán quyhoạch tuyến tính (R,C ) nhưng không cho phương pháp xác định bài toán R = V (LN ) .Do đó xuất hiện vấn đề: cho một đa diện lồi L , tìm bao lồi V (LN ) các điểm nguyên củanó ? Vấn đề này nói chung cũng khó như chính việc giải bài toán quy hoạch tuyến tínhnguyên. 1.5. Khi xây dựng V (LN ) ta đã không sử dụng thông tin về hàm mục tiêu CXcủa bài toán quy hoạch tuyến tính nguyên. Vậy có nên tìm một bài toán quy hoạchtuyến tính (A,C ) theo bài toán (LN ,C ) sao cho thoả mãn 3 điều kiện: 1) CX (LN ,C ) = CX (A,C ) (các trị tối ưu trùng nhau) (12) http://www.ebook.edu.vnBù ...