Từ 1 tới 4 trên tổng số 4 kết quả

Đề tài: Lý thuyết quy hoạch động cơ sở

  1. #1
    Ngày gia nhập
    08 2006
    Nơi ở
    Hải Phòng
    Bài viết
    218

    Mặc định Lý thuyết quy hoạch động cơ sở

    Xin lỗi các bác, bữa trước em định đưa lên vấn đề về đồ thị, tuy nhiên xét thấy nó dài và lại quá phức tạp, nên em xin chuyển sang đề tài khác đó là " Quy hoạch động ". Do tài liệu về vấn đề này không có nhiều, lý thuyết trong trường học đề cập không rõ ràng nên gây nhiều khó khăn khi giải quyết bài toán bằng quy hoạch động so với các phương pháp khác. Vì vậy em xin trình bày lý thuyết của nguyên lý này để các bác hiểu tường tận và áp dụng được nó. Tuy nhiên đây cũng chỉ là lý thuyết, chỉ có thể giúp cho moị người hiểu được cách thức nó làm việc nên rất mong các bác góp ý những kinh nghiệm thực tế khi xây dựng, cài đặt phương trình quy hoạch.


    Quy hoạch động
    Qui hoạch động là một trong những phương pháp tối ưu hiện đại. Đối tượng của qui hoạch động là các quá trình tối ưu nhiều bước nói chung và các quá trình phát triển theo thời gian nói riêng.
    Sự xuất hiện của qui hoạch động gắn liền với tên tuổi của nhà toán học Mỹ R.Bellman mà trong những năm 50 của thế kỉ này đã áp dụng cho một loạt các bài toán thực tế, một công cụ mà sau này gọi là nguyên tắc tối ưu. Chính nhờ tính đơn giản và tính tường minh của nguyên tắc này mà phương pháp qui hoạch động tỏ ra đặc biệt hấp dẫn.
    Bên cạnh nguyên tắc tối ưu, nguyên tắc quan trọng thứ hai là nguyên tắc lồng bài toán tối ưu đang xét vào một họ các bài toán tương tự. Việc áp dụng nguyên tắc tối ưu và nguyên tắc lồng dẫn đến các phương trình hàm truy toán đối với giá trị tối ưu. Những phương trình thu được cho phép lần lượt viết ra các điều khiển tối ưu cho bài toán xuất phát. Cái hay ở đây là bài toán tính toán điều khiển của cả quá trình chia ra thành một dãy các bài toán tính toán điều khiển đơn giản cho các giai đoạn của quá trình.
    Lĩnh vực áp dụng của qui hoạch động rất rộng: Các quá trình kỹ thuật công nghiệp, tổ chức sản xuất, kế hoạch hóa kinh tế, trong các vấn đề khác nhau của vật lý, sinh vật, và quân sự.
    $1. PHƯƠNG PHÁP PHƯƠNG TRÌNH TRUY TOÁN VÀ CÁC NGUYÊN TẮC CƠ BẢN CỦA QUI HOẠCH ĐỘNG
    1.1 Bài toán phân phối một chiều và phương pháp phương trình truy toán.
    1. Bài toán phân phối
    Trong thực tế có nhiều tài nguyên khác nhau: Nhân công, tiền máy, nhiên liệu…Mõi tài nguyên có thể sử dụng theo nhiều cách và cho nhiều hiệu quả khác nhau. Vấn đề đặt ra là cần phân phối các tài nguyên đó như thế nào để hiệu quả sử dụng tổng cộng là lớn nhất.
    Ta xét quá trình phân phối một tài nguyên với trữ lượng là a. Có n cách sử dụng. Nếu sử dụng đơn vị theo cách thứ i (i=1…N) thì sẽ đạt hiệu quả đo bằng hàm . Hãy qui định số đơn vị cần dùng theo mỗi cách i để tổng hiệu quả là lớn nhất.
    Mô hình của bài toán có dạng
    (1.1)
    (1.1)
    (1.2)
    và thường được biểu thị bởi những đơn vị đo khác nhau: Chẳng hạn là nhiêu liệu thì là tốc độ, là tiền thì là máy, độ tin cậy… Độ lớn của hiệu quả phụ thuộc vào số lượng tài nguyên sử dụng (a) và vào quá trình được chọn lựa (N).
    2. Phương pháp phương trình truy toán
    Để nghiên cứu bài toán trên, ta lồng nó vào một họ các quá trình phân phối nào đó. Thay cho một bài toán với số lượng tài nguyên a cho trước và số các cách sử dụng N cố định, ta xét một họ các bài toán như vậy, trong đó a và N thay đổi, tức là ta chuyển quá trình tĩnh thành quá trình động.
    Vì cực đại của hàm chỉ phụ thuộc vào a và N, ta gọi giá trị tối ưu là thì

    trong đó thỏa mãn (1.2) và (1.3). Khi N thay đổi, ta hãy tìm mối liên hệ giữa các hàm …., Vì ở đây ta biết ngay …. nên có thể nói rõ hơn là : Biết …. với a thay đổi, hãy tìm mối liên hệ giữa …. … ?
    Giả sử …… là lượng tài nguyên quyết định đối với quá trình thứ N. Khi đó bất kì … như thế nào, số lượng còn lại … sẽ được sử dụng sao để cho nhận được thu nhập cực đại của N-1 quá trình còn lại. Vì thu nhập tối ưu của N -1 quá trình theo định nghĩa là …. nên sự quyết định … cho quá trình thứ N đi đến thu nhập tổng cộng đối với N quá trình : …..
    Phương trình truy toán là
    …….
    Như vậy ta đã đưa bài toán cực trị của N biến về N bài toán cực trị một biến và phương tình (1.4) gọi là phương trình truy toán của qui hoạch động. Đó là ý cơ bản của phương pháp qui hoạch động giải bài toán cực trị bằng phương pháp phương trình truy toán.
    Biết ….. dựa vào phương trình truy toán (1.4) ta tìm được …., sau đó lại thay …. vào (1.4) ta tìm được …..v.v…. Cứ như vậy cho tới khi tìm được ….
    Cơ sở của việc làm này là nguyên lý tối ưu tổng quát mà ta sé xét trong mục dưới đây
    1.2 Các nguyên tắc cơ bản của qui hoạch động
    Qui hoạch động là việc qui hoạch từng giai đoạn của quá trình nhiều giai đoạn mà trong đó mỗi giai đoạn ta chỉ tối ưu hóa một bước. Tuy nhiên khi qui hoạch một quá trình nhiều giai đoạn, ở mỗi bước ta phải lựa chọn điều khiển trên cơ sở không phải xuất phát từ lợi ích nhỏ hẹp của chính bước đó mà từ lợi ích chung của toàn bộ quá trình.
    1. Nguyên tắc đánh số các giai đoạn từ dưới lên.
    Đối với giai đoạn cuối có thể làm cho nó tốt nhất và không lo hậu quả. Khi đó giai đoạn này trở nên ổn định và ta có thể xét giai đoạn ở trước đó và cứ tiếp tục cho tới lúc ta đi được tới giai đoạn đầu của quá trình.
    2. Nguyên tắc thông số hóa bài toán
    Ở giai đoạn sát giai đoạn cuối cùng, ta chưa biết kết quả nên ta phải đặt giả thiêt cho giai đoạn này rồi ứng với giả thiết đó ta tìm điều khiển tối ưu cho giai đoạn cuối cùng. Ở các bước khác tình hình cũng xảy ra như vậy. Do đó quá trình điều khiển tối ưu sẽ phụ thuộc vào các thông số đặc trưng cho kết quả ở bước trước.
    3. Nguyên tắc lồng
    Lồng bài toán ban đầu vào một bài toán rộng hơn hay một họ các bài toán và do đó bài toán ban đầu là một trường hợp riêng của họ bài toán này.
    Họ bài toán này nhờ có các thông số nên ta giải được. Ta sẽ thử kết quả của bài toán với các thông số khác nhau cho tới một lúc được thông số của bài toán ban đầu thì dừng lại.
    4. Nguyên tắc tối ưu (Bellman)
    Dáng điệu tối ưu có tính chất là: dù trạng thái ban đầu và điều khiển ban đầu có dạng như thế nào thì điều khiển tiếp theo cũng là tối ưu đối với trạng thái thu được trong kết quả tác động những điều khiển ban đầu.

    (Còn tiếp)

  2. #2
    Ngày gia nhập
    11 2006
    Bài viết
    633

    Bài toán ứng dụng cho quy hoạch động - bài toán knapsack 0-1 hay bài toán cái túi xách:
    Cho m là kích thước cái túi, n là số lượng đồ vật, w[i] là kích thước của đồ vật thứ i (i = 1..n), ứng với mỗi w[i] ta có v[i] là giá trị của đồ vật đó. c[i,m] sẽ là giá trị mà cái túi đạt được lớn nhất ứng với i.
    c[i,m] = 0 nếu i == 0 hoặc m == 0
    c[i,m] = c[i-1,m] nếu w[i] > m
    c[i,w] = max(c[i-1,m] , k*v[i]+c[i-1,m-k*w[i]) với k*w[i] <= m, k >= 1

  3. #3
    Ngày gia nhập
    11 2007
    Bài viết
    9

    bạn nào có code bài toán cái túi viết trên C k ?

  4. #4
    Ngày gia nhập
    04 2008
    Nơi ở
    Bốn bề là nhà
    Bài viết
    703

    Tại sao tác giả lại bỏ dở câu chuyện ở đây nhỉ???

Các đề tài tương tự

  1. Visual Studio 2005 bản quyền cài hoặc kích hoạt được bao nhiêu lần ?
    Gửi bởi shizuoka trong diễn đàn Thắc mắc chung
    Trả lời: 0
    Bài viết cuối: 08-11-2012, 11:24 AM
  2. Lý thuyết đồ hoạ | Lập trình đồ họa với openGL
    Gửi bởi rox_rook trong diễn đàn Thủ thuật, Tutorials và Mã nguồn C/C++/C++0x
    Trả lời: 120
    Bài viết cuối: 01-09-2012, 09:21 AM
  3. Kế hoạch chuyển một doanh nghiệp hoặc Văn phòng.
    Gửi bởi thanhhung2013 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 20-06-2011, 09:35 AM
  4. [Lý Thuyết quy hoạch động] Lỗi phụ thuộc tiền sử
    Gửi bởi huynguyen trong diễn đàn Thủ thuật, Tutorials CTDL & Giải thuật
    Trả lời: 4
    Bài viết cuối: 11-12-2008, 10:47 PM
  5. Lập trình đồ hoạ trên nền C++ (Full time hoặc Cộng tác viên)
    Gửi bởi bachthuchi trong diễn đàn Tuyển dụng - Việc làm CNTT
    Trả lời: 1
    Bài viết cuối: 05-05-2008, 12:24 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn