Tìm kiếm
Đang tải khung tìm kiếm
Kết quả 1 đến 1 của 1

    THẠC SĨ Một phương pháp xấp xỉ trong giải bài toán quy hoạch nguyên phân tuyến tính theo phương pháp nhánh cận và ứng dụng

    D
    dream dream Đang Ngoại tuyến (18495 tài liệu)
    .:: Cộng Tác Viên ::.
  1. Gửi tài liệu
  2. Bình luận
  3. Chia sẻ
  4. Thông tin
  5. Công cụ
  6. Một phương pháp xấp xỉ trong giải bài toán quy hoạch nguyên phân tuyến tính theo phương pháp nhánh cận và ứng dụng

    i
    Mục lục
    Lời cam đoan iii
    Mở đầu 1
    1 Bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ bất
    phương trình tuyến tính và thuật toán giải 3
    1.1 Một số bài toán thực tế đưa về bài toán quy hoạch phân tuyến
    tính và quy hoạch nguyên phân tuyến tính 3
    1.1.1 Bài toán vận tải phân tuyến tính . 4
    1.1.2 Bài toán cực tiểu giá thành sản phẩm 4
    1.1.3 Bài toán cực đại hiệu suất tiêu diệt mục tiêu địch 5
    1.2 Bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ
    bất phương trình tuyến tính và một vài tính chất của nó . 6
    1.2.1 Bài toán quy hoạch phân tuyến tính với miền ràng buộc
    là hệ bất phương trình tuyến tính . 6
    1.2.2 Một vài tính chất của bài toán quy hoạch phân tuyến
    tính với miền ràng buộc là hệ bất phương trình tuyến tính 7
    1.3 Thuật toán nón xoay xấp xỉ trong giải bài toán quy hoạch phân
    tuyến tính . 10
    1.3.1 Khái niệm về nón đơn hình tuyến tính 11
    1.3.2 Khái niệm về cạnh và phương của cạnh của nón đơn hình 11
    1.3.3 Khái niệm nón xoay M(r,s) sinh ra từ nón M . 18
    1.3.4 Dấu hiệu tối ưu (Điều kiện tối ưu): 22ii
    1.3.5 Thuật toán nón xoay xấp xỉ trong giải bài toán quy
    hoạch phân tuyến tính 23
    1.4 Bảng lặp giải bài toán quy hoạch phân tuyến tính bởi thuật toán
    PTT 25
    1.5 Thuật toán nón xoay tìm một nghiệm của hệ bất phương trình
    tuyến tính . 30
    1.5.1 Thuật toán nón xoay tìm một nghiệm của hệ bất phương
    trình tuyến tính với cơ sở xuất phát từ gốc toạ độ là đỉnh
    của nón R
    n
    + 31
    1.5.2 Bảng lặp tìm một nghiệm của hệ bất phương trình tuyến
    tính với cơ sở xuất phát từ gốc toạ độ là đỉnh của nón R
    n
    + 32
    2 Thuật toán nhánh cận xấp xỉ trong giải bài toán quy hoạch nguyên
    phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến
    tính và ứng dụng 34
    2.1 Bài toán quy hoạch nguyên phân tuyến tính với miền ràng buộc
    là hệ bất phương trình tuyến tính và thuật toán Land-Doig 34
    2.1.1 Bài toán quy hoạch nguyên phân tuyến tính . 35
    2.1.2 Thuật toán Land-Doig giải bài toán quy hoạch nguyên
    phân tuyến tính 36
    2.2 Thuật toán nhánh cận xấp xỉ trong giải bài toán quy hoạch
    nguyên tuyến tính . 40
    2.3 Minh họa ứng dụng thuật toán nhánh cận xấp xỉ trong ILF giải
    bài toán quy hoạch nguyên phân tuyến tính có số chiều nhỏ với
    miền ràng buộc là hệ bất phương trình tuyến tính 42
    Kết luận và Đề nghị 57
    Tài liệu tham khảo 58iii
    Lời cam đoan
    Tôi xin cam đoan đây là công trình nghiên cứu của tôi.
    Thái Nguyên, ngày 20 tháng 04 năm 2015
    Học viên
    Đinh Quang Ngọc1
    Mở đầu
    Nhiều bài toán thực tế trong kinh tế cũng như trong toán học, thường gặp
    trong lý thuyết trò chơi, trong công nghiệp hóa chất, trong cắt nguyên vật liệu,
    trong mạng vận tải và trong định giá thành sản phẩm, . dẫn đến chúng ta
    phải đi giải các bài toán quy hoạch nguyên phân tuyến tính. Một phương pháp
    hiệu quả thường sử dụng để giải bài toán này đó là phương pháp nhánh cận
    Land-Doig.
    Để giải bài toán quy hoạch nguyên phân tuyến tính thông thường là chúng ta
    phải tiến hành giải các bài toán quy hoạch phân tuyến tính tương ứng khi chưa
    có điều kiện nguyên của biến với các ràng buộc bổ sung dạng bất phương trình
    cho các thành phần của biến. Rõ ràng khi sử dụng phương pháp nhánh cận để đi
    tìm các cận dưới tốt hơn (đối với bài toán min) cho bài toán quy hoạch nguyên
    thì ta thường phải giải các bài toán tương ứng khi chưa có điều kiện nguyên
    với miền ràng buộc được bổ sung thêm sau mỗi bước một ràng buộc dạng bất
    phương trình đối với thành phần chưa nguyên của biến.
    Các thuật toán giải bài toán quy hoạch nguyên phân tuyến tính với miền ràng
    buộc là hệ phương trình tuyến tính với các biến không âm đã có nhiều thuật toán
    giải tương tự như thuật toán đơn hình trong quy hoạch tuyến tính (xem [2], [8]).
    Tuy nhiên trên thực tế bài toán thường có miền ràng buộc là hệ bất phương trình
    tuyến tính. Do đó việc sử dụng các thuật toán giải trực tiếp bài toán quy hoạch
    phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính là khá ưu
    việt và hiệu quả hơn (vì không phải thêm vào các biến bù) khi ta phải đi giải
    chúng bởi các phương pháp mà miền ràng buộc đòi hỏi ở dạng chính tắc (tức
    là miền ràng buộc là hệ phương trình tuyến tính đối với các ràng buộc chính).
    Chính vì vậy, luận văn này trình bày việc xây dựng một thuật toán xấp xỉ trong2
    giải bài toán quy hoạch nguyên phân tuyến tính với miền ràng buộc là hệ bất
    phương trình tuyến tính và khai thác đặc thù riêng của hàm mục tiêu có tính đơn
    điệu chứng minh bài toán nếu có lời giải thì nó có lời giải đạt ở biên của miền
    chấp nhận, do đó trong mỗi bước để tìm các cận dưới đúng của bài toán nguyên,
    chúng ta chỉ phải đi giải các bài toán quy hoạch tuyến tính tương ứng khi chưa
    có điều kiện nguyên có số chiều là n ư 1 (n là số chiều của bài toán). Như vậy
    thuật toán sẽ hiệu quả khi giải bài toán quy hoạch nguyên tuyến tính dạng chuẩn
    có số chiều là 2.
    Thái Nguyên, tháng 04 năm 2015
    Đinh Quang Ngọc
    Học viên Cao học Toán K7A
    Chuyên ngành Toán ứng dụng
    Trường Đại học Khoa học - Đại học Thái Nguyên
    Email: ngocdq.c3nguyenhue@gmail.com3
    Chương 1
    Bài toán quy hoạch phân tuyến tính với miền
    ràng buộc là hệ bất phương trình tuyến tính và
    thuật toán giải
    Như chúng ta đã biết, nhiều bài toán thực tế trong kinh tế cũng như trong
    toán học, thường gặp trong lý thuyết trò chơi, trong công nghiệp hóa chất, trong
    cắt nguyên vật liệu, trong mạng vận tải và trong định giá thành sản phẩm, .
    đều có mô hình toán học dạng các bài toán quy hoạch nguyên phân tuyến tính.
    Vì vậy nội dung của chương này sẽ giới thiệu một số mô hình thực tế có dạng
    bài toán này và sau đó trình bày thuật toán xấp xỉ trong giải bài toán quy hoạch
    phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính, làm cơ sở
    để xây dựng thuật toán giải bài toán quy hoạch nguyên phân tuyến tính với miền
    ràng buộc là hệ bất phương trình tuyến tính trình bày trong chương 2.
    1.1 Một số bài toán thực tế đưa về bài toán quy hoạch phân
    tuyến tính và quy hoạch nguyên phân tuyến tính
    Sau đây chúng ta trình bày một số mô hình bài toán thực tế có dạng bài toán
    quy hoạch phân tuyến tính và bài toán quy hoạch nguyên phân tuyến tính với
    miền ràng buộc là hệ bất phương trình tuyến tính.

    Xem Thêm: Một phương pháp xấp xỉ trong giải bài toán quy hoạch nguyên phân tuyến tính theo phương pháp nhánh cận và ứng dụng
    Nội dung trên chỉ thể hiện một phần hoặc nhiều phần trích dẫn. Để có thể xem đầy đủ, chi tiết và đúng định dạng tài liệu, bạn vui lòng tải tài liệu. Hy vọng tài liệu Một phương pháp xấp xỉ trong giải bài toán quy hoạch nguyên phân tuyến tính theo phương pháp nhánh cận và ứng dụng sẽ giúp ích cho bạn.
    #1
  7. Đang tải dữ liệu...

    Chia sẻ link hay nhận ngay tiền thưởng
    Vui lòng Tải xuống để xem tài liệu đầy đủ.

    Gửi bình luận

    ♥ Tải tài liệu

social Thư Viện Tài Liệu

Từ khóa được tìm kiếm

Nobody landed on this page from a search engine, yet!

Quyền viết bài

  • Bạn Không thể gửi Chủ đề mới
  • Bạn Không thể Gửi trả lời
  • Bạn Không thể Gửi file đính kèm
  • Bạn Không thể Sửa bài viết của mình
  •  
DMCA.com Protection Status