TAILIEUCHUNG - 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. | 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

• Toán học
• chứng minh tính hữu hạn
• thuật toán Gomory
• lập trình bằng ngôn ngữ C
• quy hoạch tuyến tính
• phương pháp đơn hình
• Ebook Lý thuyết ngôn ngữ
• Lý thuyết ngôn ngữ và tính toán
• Văn phạm phi ngữ cảnh
• Ôto mát hữu hạn
• Phép chứng minh quy nạp
• Phương pháp mạng đơn hình
• Mạng đơn hình
• Tìm hiểu mạng đơn hình
• Tham khảo mạng đơn hình
• Ma trận mạng đơn hình
• Cấu tạo mạng đơ hình
• Mô hình hồi qui đơn giản
• Bài giảng Mô hình hồi qui đơn giản
• Giả thiết của mô hình hồi quy
• Phương pháp bình quân cực tiểu
• Ước lượng phương pháp bình quân cực tiểu
• Ước lượng tham số Beta
• Thể loại âm nhạc
• Hình thức âm nhạc
• Phương pháp diễn tả cơ bản
• Hình thức một đoạn đơn
• Hình thức hai đoạn đơn
• Hình thức ba đoạn đơn
• Bài giảng Mô hình hồi quy tuyến tính đơn
• Mô hình hồi quy tuyến tính đơn
• Lý thuyết xác suất và thống kê toán
• Thống kê toán
• Phương pháp bình phương tối thiểu
• Hồ sơ đơn phương chấm dứt hợp đồng
• Nghiệp vụ luật sư
• Đơn phương chấm dứt hợp đồng
• Bài giảng pháp luật đại cương
• Quy phạm pháp luật
• Hình thức pháp luật
• Kinh tế lượng
• Nhập môn Kinh tế lượng
• Ứng dụng kinh tế lượng
• Ước lượng mô hình
• Phương pháp thích hợp cực đại
• Đo đạc bản đồ
• Trắc địa bản đồ
• Mô hình TIN
• Lưới tam giác không quy chuẩn
• Phương pháp đơn tia
• Công tác đo sâu hồi âm đơn tia
• Lý thuyết tối ưu
• Bài toán tối ưu
• Phương pháp đơn hình đối ngẫu
• Phương pháp phân phối
• Tối ưu hóa
• Phương pháp định lượng trong quản lý
• Phương pháp định lượng
• Phương pháp quản lý
• Phương pháp đồ thị
• Quy hoạch nguyên
• Quy hoạch nhị nguyên
• Lý thuyết quy hoạch tuyến tính
• Giải thuật đơn hình
• Giải thuật đơn hình cải tiến
• Phương pháp biến giả cải biên
• Quy hoạch tuyến tính suy biến
• Nghiên cứu y học
• Phương pháp giải trình tự gen Sanger
• Đa hình đơn gen ABCB1
• Đa hình đơn gen OPRD1
• Liều điều trị Methadone
• Nghiện chất dạng thuốc phiện
• Giáo dục đào tạo
• cao đẳng đại học
• đánh giá phương án cực biên
• giáo trình toán cao cấp
• Qui hoạch tuyến tính
• Tạp chí Pháp luật và thực tiễn
• Bài viết về pháp luật
• Mô hình chính quyền địa phương
• Đơn vị hành chính kinh tế đặc biệt
• Văn bản pháp luật
• Phương pháp hiệu quả sinh dữ liệu
• Dữ liệu kiểm thử mức đơn vị
• Kiểm chứng mô hình
• Kiểm thử đơn vị
• Hiệu quả sinh dữ liệu
• Phương pháp tỉ lệ vàng
• phương pháp newton
• phương pháp parabol
• phương pháp thế vị
• thuật toán tối ưu hóa
• Bài giảng Phương pháp định lượng
• phương pháp hình đơn mở rộng
• tuyến tính hai pha
• thuật toán
• bài giảng quy hoạch tuyến tính
• ma trận
• Bài toán quy hoạch tuyến tính
• Tính chất bài toán quy hoạch tuyến tính
• Sư phạm toán
• Phương pháp đơn hình đặc biệt
• Bài giảng Toán Kinh tế
• Toán Kinh tế
• Bài toán đối ngẫu
• Bài giảng Hồi quy tuyến tính đơn
• Hồi quy tuyến tính đơn
• Mô hình hồi quy
• Phương pháp luận của kinh tế lượng
• Mô hình hồi quy tuyến tính
• Sinh kế của phụ nữ làm mẹ đơn thân
• Phụ nữ làm mẹ đơn thân
• Phương pháp phát triển sinh kế
• Loại hình và phương thức chuyển đổi sinh kế
• Nghiên cứu về sinh kế của phụ nữ
• Vi cấu trúc
• Cơ chế khuếch tán
• Nhiệt độ chuyển pha
• Mô hình khối Fe2O3
• Phương pháp động lực học phân tử
• Số nguyên tử trong mô hình Fe2O3
• Đơn vị cấu trúc trong mô hình Fe2O3
• Phương pháp đẳng hình học
• Đẳng hình học
• Áp suất khí thuốc
• Mô hình toán học
• Hệ thống vũ khí