TAILIEUCHUNG - Chương 3 PHƯƠNG PHÁP ĐƠN HÌNH VÀ CÁC THUẬT TOÁN CỦA NÓ

TÀI LIỆU VỀ BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH | Chương 3. PHƯƠNG PHÁP ĐƠN HÌNH VÀ CÁC THUẬT TOÁN CỦA NÓ . Cơ sở lí luận Xét bài toán quy hoạch tuyến tính dạng chính tắc f x CTx min 1 Ax b 2 x 0 3 Với A là ma trận m X n b 2 Rm c và x 2 Rn trong đó A có hạng là m m n . Bài toán quy hoạch là không suy biến tất cả phương án cực biên của nó đều có số thành phần dương bằng m và x X01 Xo2 x0n là một phương án cực biên. Ký hiệu J0 j x0j 0 . Hệ véc tơ Aj j 2 J0 độc lập tuyến tính cho nên các véc tơ AZ i 1 . n đều biểu thị duy nhất qua cơ sở Aj j 2 J0 A X xijAj i 1 . n 4 Nếu gọi B là ma trận có các cột là Aj j 2 J0 và đặt x1 xjj 2 Rm j 2 J0 thì A Bx hay x B 1Ai i 1 . n. Nếu đặt x0 x0 2 Rm c0 cj0 2 Rm với j 2 J0 thì f x0 CTx0 2 c0x0j Bx0 b. j2Jo Định nghĩa Ước lương . Ta gọi A C0Tx- C i 1 . n là ước lượng của biến x hay của véc tơ A ứng với cơ sở J0. Định lý Dấu hiệu tối ưu . Nếu phương án cực biên x của quy hoạch tuyến tính có Ai 6 0 i 1 . n thì x là phương án tối ưu của bài toán 1 2 3 . Chứng minh. Xét phương án bất kì y yì ta có b XyA Xhi X X Xxijhi. Aj b X x jAj do 4 i 1 i 1 j 2Jo j2Jo i 1 j 2J0 n x j x Xijhi. j 1 2 . n 5 i 1 Từ Ai 6 0 Vi suy ra c Txi 6 Cị. Do đó ta được . y X Chi X c Txi hi i 1 i 1 n X X xijcj hi X X xij y c jeJo i 1 2 cj x j f x jj Vậy x là phương án tối ưu. Định lý Dấu hiệu hàm mục tiêu không bị chặn . Nếu phương án cực biên x của quy hoạch tuyến tính mà có j sao cho Aj 0 và xj 0 thì bài toán 1 2 3 có hàm mục tiêu không bị chặn. Chứng minh. Ta có Ai X xij Aj Vi theo 4 j2J0 Gọi 8 xij j 2 J di dij dij -1 j ị 0 j 2 J ig Xét véc tơ x ớ x0 dải 0 0 ta có n X xj 0 Aj X x0j - 0xoj Aj 0Ai j i jeJo X x0jAj 0 Ai _ X x0jAj b 0 b. j2Jo j2 J Và Xji 0 nên ải 0 mà x0 0 cho nên x 0 0 với mọi 0 0. Do đó x 0 là phương án của bài toán. Mặt khác ta thấy n f x 0 X cjXj 0 X Cj x0j - 0xij 0Q X cjx0j 0 ci - X cjxj f x0 0Ai 1 khi 0 1 do Ai 0. Do đó hàm mục tiêu không bị chặn. Định lý Dấu hiệu xây dựng được phương án tối hơn . Nếu phương án cực biên x0 của quy hoạch tuyến tính tồn tại j sao .

• Trung học cơ sở
• quy hoạch tuyến tính
• thuật toán
• bài giảng quy hoạch tuyến tính
• ma trận
• phương pháp đơn hình
• Học phần Quy hoạch tuyến tính
• Đề cương Quy hoạch tuyến tính
• Tài liệu Quy hoạch tuyến tính
• Bài toán Quy hoạch tuyến tính
• Phương pháp Quy hoạch tuyến tính
• Lý thuyết quy hoạch tuyến tính
• Quy hoạch tuyến tính tổng quát
• Quy hoạch tuyến tính chính tắc
• Bài toán vận tải
• Giáo trình Quy hoạch tuyến tính
• Quy hoạch tuyến tính đối ngẫu
• Quy hoạch tuyến tính dạng đặc biệt
• Phân loại quy hoạch tuyến tính
• Toán chuyên ngành
• Bài tập quy hoạch tuyến tính
• Ôn tập quy hoạch tuyến tính
• Quy hoạch tuyến tính đồ thị
• Xây dựng bài toán quy hoạch tuyến tính
• Tiểu luận quy hoạch tuyến tính
• Ràng buộc đồ thị
• Lập mô hình bài toán
• Ứng dụng quy hoạch tuyến tính
• Bài toán dòng trên mạng
• Bài toán quy hoạch nguyên
• Tính chất bài toán quy hoạch tuyến tính
• Thuật toán đơn hình
• Phương pháp hình học
• Giải thuật đối ngẫu
• Bài toán trò chơi
• Phân loại bài toán QHTT
• Giải thuật đơn hình cơ bản
• Phương pháp biến giả cải biên
• Tập phương án tối ưu
• Thuật toán đơn hình đối ngẫu
• Luận văn toán học
• Bài toán quy hoạch nguyên tuyến tính
• Quy hoạch nguyên tuyến tính
• Giải bài toán quy hoạch nguyên tuyến tính
• Lý thuyết tối ưu hóa
• Lý thuyết quy hoạch nguyên tuyến tính
• Ôn tập cuối kỳ
• Bài toán kinh tế
• Toán chuyên đề 2
• Quy hoạch tuyến tính về dạng chính tắc
• dự án xây dựng
• kế hoạch sản xuất
• tài liệu về quy hoạch tuyến tính
• các dạng bài toán vận tải
• bài tập tuyến tính
• Biểu thức tuyến tính
• Bài toán về lập kế hoạch sản xuất
• Bài toán về khẩu phần
• Phương trình tuyến tính
• Bài toán lập kế hoạch sản xuất
• Bài giảng Bài toán tối ưu tuyến tính
• Bài toán tối ưu tuyến tính
• Tối ưu tuyến tính
• Bài toán đối ngẫu
• Đối ngẫu trong quy hoạch tổng quát
• Quy hoạch tuyến tính dạng chính tắc
• Quy hoạch tổng quát
• Bài toán vốn đầu tư
• Ma trận cơ sở