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ội tụ của nó. 1. TƯ TƯỞNG PHƯƠNG PHÁP CẮT . 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ải mộ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. | Bùi Thế Tâm Quy hoạch rời rạc Chươ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ội tụ của nó. 1. TƯ TƯỞNG PHƯƠNG PHÁP CẮT . 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ải mộ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 C 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ập hữ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 C 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 C V Ln R Ln C RN . 4 Ta phải chứng minh Rn C Ln 5 Thật vậy giả sử lấy x E Rn 6 vì Ln C L nên R V LN C V L L. Vì vậy x e Rn c R c L 7 Từ 6 và 7 suy ra x E 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 C RN Từ 3 và 1 suy ra 2 đúng. Bùi Thế Tâm 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 quy hoạch tuyến tính nguyên LN C ta đi giải bài toán R C . . Ta sẽ chứng minh R V LN là đa diện nguyên duy nhất mà tập các điểm nguyê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à UN Ln 8 Khi đó U R V LN 9 Chứng minh. Từ 8 trực tiếp suy ra R c U 10 vì R V Ln VUN c U Ta phải chứng minh U c 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 c UN ln suy ra U V U c V LN R. Vậy 11 là đúng. Từ 10 và 11 ta có điều cần chứng minh 9 . . VÍ dụ Bùi Thế Tâm 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 x2 Max x1 x2 Max x1 x2 2x1 11x2 38 2x1 1 1x2 38 a x2 3 x1 x2 7 x1 x2 7 b x1 x
