Danh mục

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

Số trang: 10      Loại file: pdf      Dung lượng: 23.89 MB      Lượt xem: 28      Lượt tải: 0    
tailieu_vip

Phí tải xuống: 19,000 VND Tải xuống file đầy đủ (10 trang) 0
Xem trước 1 trang đầu tiên của tài liệu này:

Thông tin tài liệu:

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!
Nội dung trích xuất từ tài liệu:
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 ...

Tài liệu được xem nhiều: