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

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

15
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

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 hoai.phamthi@hust.edu.vn 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 hoai.phamthi@hust.edu.vn 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 < 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] hoai.phamthi@hust.edu.vn 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. hoai.phamthi@hust.edu.vn 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 ) < f (x 0 ). hoai.phamthi@hust.edu.vn 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 > 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 hoai.phamthi@hust.edu.vn 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, 0, 1, 0, 0, 0)T v 2 = (0, 0, 9, 0, 0, 9, −9)T v 3 = (0, 0, 0, 0, 9, 9, 0)T v 4 = (1, 0, 0, 0, 8, 7, 1)T hoai.phamthi@hust.edu.vn 6/9
Cơ sở lí thuyết của thuật toán đơn hình Nhận xét Số thành phần dương trong mỗi phương án cực biên không vượt quá m Số lượng pacb của bài toán (P) là hữu hạn (Tại sao?) Nếu pacb x 0 có |J(x 0 )| = m, ta nói x 0 là phương án cực biên (pacb) không suy biến ; ngược lại x 0 đgl pacb suy biến Ví dụ: Tìm các pacb của hệ x1 + 2x2 + x3 = 2 2x1 + x2 + 5x3 = 1 hoai.phamthi@hust.edu.vn 7/9
Cơ sở lí thuyết của thuật toán đơn hình Một bộ gồm m véc tơ cột độc lập tuyến tính B = {Aj1 , . . . , Ajm } đgl một cơ sở của ma trận A Mỗi pacb không suy biến x 0 sẽ có một cơ sở duy nhất tương ứng với nó là B = {Aj | j ∈ J(x 0 )} Nếu x 0 là pacb suy biến thì bổ sung thêm các véc tơ vào tập {Aj | j ∈ J(x 0 )} để được một cơ sở của A Phần tiếp theo chúng ta xét bài toán (P) không suy biến, tức là mọi pacb đều không suy biến. Trường hợp bài toán (P) có pacb suy biến sẽ được xét sau. hoai.phamthi@hust.edu.vn 8/9
Cơ sở lí thuyết của thuật toán đơn hình Giả sử ta đã biết 1 pacb ksb x 0 của bài toán (P). Do B = {Aj | j ∈ J(x 0 )} là cơ sở của A nên X Ak = zjk Aj hay Ak = BZk , j∈J(x 0 ) Ta có xj0 Aj = b hay Zk = B −1 Ak X j∈J(x 0 ) X f (x 0 ) = xj0 cj j∈J(x 0 ) hoai.phamthi@hust.edu.vn 9/9