Bài giảng Toán kinh tế "Thuật toán đơn hình giải bài toán quy hoạch tuyến tính chính tắc" được biên soạn với các nội dung chính sau: Ý tưởng chính của Thuật toán đơn hình; Cơ sở lí thuyết của thuật toán đơn hình. Mời các bạn cùng tham khảo bài giảng! | Thuật toán đơn hình giải bài toán quy hoạch tuyến tính chính tắc Lecturer Phạm Thị Hoài Department of Applied Mathematics - School of Applied Mathematics and Informatics - Hanoi University of Science and Technology 0 9 Content 1 Ý tưởng chính của Thuật toán đơn hình 2 Cơ sở lí thuyết của thuật toán đơn hình 1 9 Ý tưởng chính của Thuật toán đơn hình Dạng chính tắc của bài toán QHTT minimize cx P subject to Ax b x 0 A Rm n m lt n có rankA m kí hiệu Aj j 1 . . . m là và các véc tơ cột của A b Rn b 0. Chú ý hệ Ax b có nghiệm nếu rank A rank A b 2 9 Ý tưởng chính của Thuật toán đơn hình Ý tưởng chính của thuật toán đơn hình Bài toán quy hoạch tuyến tính QHTT nếu có nghiệm sẽ đạt tại đỉnh. Thuật toán đơn hình sẽ xuất phát từ một đỉnh của miền chấp nhận được D x Rn Ax b x 0 . Làm thế nào để tìm nhận dạng đỉnh của D Nghiệm tối ưu địa phương của bài toán QHTT cũng là nghiệm tối ưu toàn cục. Chỉ cần tìm nghiệm tối ưu địa phương. 3 9 Ý tưởng chính của Thuật toán đơn hình Mô tả hình học của thuật toán đơn hình Xuất phát từ x 0 cách tìm một đỉnh của D sẽ học sau nếu giá trị của hàm không giảm trên mọi cạnh xuất phát từ x 0 thì x 0 chính là nghiệm tối ưu toàn cục Tại sao nếu có một cạnh vô hạn xuất phát từ x 0 mà giá trị của hàm giảm trên đó thì bài toán không có nghiệm tối ưu trường hợp còn lại tìm được một đỉnh x 1 kề với x 0 thỏa f x 1 lt f x 0 . 4 9 Cơ sở lí thuyết của thuật toán đơn hình Phương án cực biên Theorem 1 Lấy x0 D kí hiệu J x 0 j 1 . . . m xj0 gt 0 . Khi đó x 0 là phương án cực biên khi và chỉ khi hệ véc tơ Aj j J x 0 độc lập tuyến tính. Chứng minh. In class 5 9 Cơ sở lí thuyết của thuật toán đơn hình Ví dụ Giả sử bài toán P có tập ràng buộc cho bởi hệ sau x1 2x2 x3 3x4 x5 9 2x1 x2 3x4 x6 9 x1 x2 x3 x7 0 xi 0 i 1 . . . 7 Xác định xem các điểm dưới đây có phải là phương án cực biên của bài toán đã cho không v 1 2 2
