Thư mục

Hỗ trợ kỹ thuật

  • (Hotline:
    - (04) 66 745 632
    - 0982 124 899
    Email: hotro@violet.vn
    )

Thống kê

  • lượt truy cập   (chi tiết)
    trong hôm nay
  • lượt xem
    trong hôm nay
  • thành viên
  • Chào mừng quý vị đến với Thư viện Bài giảng điện tử.

    Quý vị chưa đăng nhập hoặc chưa đăng ký làm thành viên, vì vậy chưa thể tải được các tư liệu của Thư viện về máy tính của mình.
    Nếu đã đăng ký rồi, quý vị có thể đăng nhập ở ngay ô bên phải.

    Thuật toán đơn hình trong quy hoạch tuyến tính

    (Tài liệu chưa được thẩm định)
    Nguồn: Sưu tầm
    Người gửi: Trần Trung (trang riêng)
    Ngày gửi: 13h:24' 21-03-2009
    Dung lượng: 164.5 KB
    Số lượt tải: 268
    Số lượt thích: 0 người
    Thuật toán đơn hình trong quy hoạch tuyến tính

    Đơn hình là phương pháp chỉ các phương pháp tổng quát bài toán quy hoạch tuyến tính bằng phương pháp xoay trụ (pivoting), giống như phép khử Gauss. Nó tương ứng với thao tác hình học chuyển từ đỉnh này tới đỉnh khác của đơn hình để tìm lời giải. Các thuật toán chỉ khác nhau ở thứ tự các đỉnh được xét đến.
    Bài toán quy hoạch tuyến tính có thể có nhiều dạng. Ví dụ, bài toán mạng dòng chảy có các đẳng thức lẫn các bất đẳng thức, những ví dụ hình học chỉ sử dụng các bất đẳng thức. Để làm giảm bớt số hạng có thể có của bài toán, ta sẽ xét một dạng chuẩn, trong đó tất cả các ràng buộc là đẳng thức, ngoại trừ một số bất đẳng thức biểu thị các biến đều là số không âm. Dạng chuẩn này dường như quá chặt chẽ, tuy nhiên ta có thể chuyển bài tổng quát về dạng này. Bài toán sau là dạng chuẩn của ví dụ 3 chiều:
    Cực đại hoá x1+x2+ x3 với các điều kiện
    -x1+x2+y1=5x1+4x2+y2=45
    2x1+x2+y3=273x1-4x2+y4=24
    x3+y5=4x1.x2.x3.y1.y2.y3.y4.y5 >= 0
     Mỗi bất đẳng thức có 2 biến trở nên chuyển thành đẳng thức bằng cách thêm vào một biến. Các biến y gọi là các biến phụ thêm(slack variable). Ngoài ra, bằng cách đổi biến ta có thể chuyển bất đẳng thức một biến thành loại ràng buộc không âm. Ví dụ một ràng buộc như x3<=-1 chuyển thành dạng chuẩn x’3>=0 với x’3 = -1-x3.
    Dạng chuẩn tạo ra một tương ứng giữa bài toán quy hoạch tuyến tính và giải hệ phương trình tuyến tính. Ta có N phương trình với N ẩn (số dương). Trong trường hợp này, chú ý là ta có N biến phụ thêm, mỗi phương trình một biến (vì ta bắt đầu với một hệ toàn bất đẳng thức). Nếu M>N thì hệ phương trình có nhiều nghiệm: vấn đề là tìm một cái làm cho hàm mục tiêu cực đại.
    Trong ví dụ của ta, các phương trình ràng buộc có một nghiệm tầm thường x1=x2=x3 = 0, còn các biến phụ thêm y1, y2, y3, y4, y5 thì lấy các giá trị thích hợp. Điều này xảy ra vì (0, 0, 0) là một điểm của đơn hình trong ví dụ này. Trong trường hợp tổng quát, điều này không đúng, tuy nhiên ta sẽ giới hạn sự chú ý vào các bài toán như vậy cũng còn rất lớn: ví dụ, nếu tất cả các số ở vế phải của các bất đẳng thức là dương và tất cả các biến phụ thêm có hệ số dương (như trong ví dụ) thì trở lại trường hợp tổng quát sau.
    Cho một nghiệm với M-N biến là 0, ta có thể tìm các nghiệm khác với cùng tính chất bằng cách sử dụng một phép toán quen thuộc, lặp (pivoting). Nó giống phép khả Gauss: một phần tử a[p,q] được chọn trong ma trận hệ số, rồi lấy hàng thứ p nhân với một số thích hợp và cộng với tất cả các dòng khác để làm cho cột q trở thành 0, ngoại trừ giá trị tại giao điểm của hàng p và cột q là 1.
    Hãy xét ma trận sau (biểu diễn bài toán quy hoạch trên).

    Ma trận (N+1)(M+1) này chứa các hệ số của bài toán dạng chuẩn, với cột thứ (M+1) chứa các số ở vế tay phải của các phương trình (như trong phép khử Gauss) và hàng zero sẽ được xét sau; còn bây giờ chúng được xử lý như các hàng khác.
    Trong ví dụ này, ta chỉ thực hiện các tính toán chính xác đến hai chữ số sau dấu phẩy. Như vậy, ta bỏ qua các vấn đề độ chính xác của tính toán và sai số tích luỹ. Giống như trong phép khử Gauss, các vấn đề này rất quan trọng.
    Các biến tương ứng với một lời giải gọi là biến cơ sở và các biến được chuyển tthành không thể giải gọi là biến không cơ sở. Trong ma trận, các cột tương ứng với biến không cơ sở tương ứng với các cột có nhiều phần tử khác khong hơn.
    Giả sử ta muốn trụ (pivot) ma trận này với p=4, q=1. Ta cộng dòng thứ tư (nhân với số thích hợp) với các dòng khác để tạo thành cột thứ nhất có tất cả là 0, ngoại trừ số 1 ở hàng4. Quá trình này cho kết quả ở bảng số sau:
     
    Phép toán này bỏ cột thứ 7 khỏi cơ sở và thêm cột 1 vào cơ sở. Một cách chính xác, một cột cơ sở đã được chuyển.
    No_avatarf
    các bạn giúp t mấ câu hỏi này được k?câu 1 . cách đưa bài toán quy hoạch tuyến tính về dạng chính tắc, dạng chuẩn , cho ví dụ minh hoạ . câu 2 . phương án cực biên của bài toán quy hoạc tuyến tính , các tính chất của bài toán quy hoạch tuyến tính va ứng dụng .câu 3 . các định lý cơ bản của thuật toán đơn hình , các bước giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình , cho ví dụ minh hoạ . các bướ giải bài toán qhtt bằng phương pháp bài toán M, cho vd minh hoạ 
     
    Gửi ý kiến
    print