Thực đơn
trang chủTiểu sử

Phân bổ nguồn lực tối ưu bằng phương pháp lập trình động. Nguyên lý tối ưu. Phương trình Bellman. Bài toán về thứ tự nhân ma trận: ma trận cho trước,..., cần tối thiểu hóa số phép toán vô hướng để nhân chúng

TRỪU TƯỢNG


Giới thiệu


Lập trình năng động- một phương pháp tối ưu hóa phù hợp với các hoạt động trong đó quá trình ra quyết định có thể được chia thành các giai đoạn (bước). Những hoạt động như vậy được gọi là nhiều bước.

Bắt đầu phát triển lập trình năng động có từ những năm 50 của thế kỷ XX. và gắn liền với tên tuổi của Richard Ernest Bellman.

Nếu các mô hình lập trình tuyến tính có thể được sử dụng trong kinh tế học để đưa ra các quyết định lập kế hoạch quy mô lớn trong các tình huống phức tạp, sau đó các mô hình quy hoạch động được sử dụng để giải quyết các vấn đề ở quy mô nhỏ hơn nhiều:

ü khi xây dựng các quy tắc quản lý hàng tồn kho;

ü khi phân bổ nguồn lực đầu tư giữa các dự án thay thế;

ü khi lập kế hoạch lịch cho hiện tại và xem xét lại thiết bị phức tạp và sự thay thế của nó, v.v.


1. Công thức tổng quát của bài toán quy hoạch động

lập trình phương trình bellman động

Được xem xét quá trình kiểm soát, ví dụ như quá trình phân bổ vốn giữa các doanh nghiệp, sử dụng nguồn lực trong nhiều năm, thay thế thiết bị, v.v. Kết quả của việc điều khiển là hệ thống (đối tượng điều khiển) S được chuyển từ trạng thái ban đầu s 0để nêu rõ s N . Hãy chia điều khiển thành n bước, tức là quyết định được đưa ra tuần tự ở mỗi bước và điều khiển chuyển hệ thống S từ trạng thái ban đầu sang trạng thái cuối cùng là một tập hợp gồm n quyết định quản lý từng bước.

Hãy ký hiệu là X k quyết định quản lý về bước thứ k(k=1, 2, …, n). Biến X k thỏa mãn một số hạn chế và theo nghĩa này được gọi là có thể chấp nhận được (X k có thể là một số, một điểm trong không gian n chiều hoặc một đặc điểm định tính).

Đặt X=(X 1, X 2, …, X N ) - điều khiển chuyển hệ thống S từ trạng thái s 0để nêu rõ s N . Hãy ký hiệu là s k trạng thái của hệ thống (đặc trưng bởi một bộ nhất định tham số và giá trị cụ thể của chúng) sau bước điều khiển thứ k. Hơn nữa, trạng thái của hệ thống k ở cuối bước thứ k chỉ phụ thuộc vào trạng thái trước đó k-1 và quyết định quản lý ở bước thứ k X k (tức là không phụ thuộc trực tiếp vào các điều kiện và quyết định quản lý trước đó). Yêu cầu nàyđược gọi là "không có hệ quả" và có thể được biểu thị bằng các phương trình trạng thái sau:



Như vậy, ta thu được một chuỗi các trạng thái s0, s1, …, sk-1, sk, …, sn-1, sn. Sau đó n bước quy trình quản lý có thể được mô tả sơ đồ như sau:


Giả sử chỉ số hiệu quả của bước thứ k được biểu thị bằng một hàm nào đó:



và hiệu quả của toàn bộ quá trình gồm nhiều bước đang được xem xét là hàm cộng sau:



Khi đó, bài toán tối ưu hóa từng bước (bài toán quy hoạch động) được xây dựng như sau: xác định một điều khiển X được chấp nhận để chuyển hệ thống S từ trạng thái s0 sang trạng thái sn, tại đó hàm mục tiêu Z lấy giá trị lớn nhất (nhỏ nhất).

Một bài toán quy hoạch động có các tính năng sau:

Bài toán tối ưu hóa được hiểu là một quá trình điều khiển n bước.

Hàm mục tiêu bằng tổng các hàm mục tiêu của từng bước.

Việc lựa chọn điều khiển ở bước thứ k chỉ phụ thuộc vào trạng thái của hệ thống ở bước này và không ảnh hưởng đến các bước trước đó (không có nhận xét).

Trạng thái sk sau bước điều khiển thứ k chỉ phụ thuộc vào trạng thái sk-1 trước đó và điều khiển Xk (“không có hậu quả”).

Ở mỗi bước, điều khiển Xk phụ thuộc vào một số hữu hạn các biến điều khiển và trạng thái sk phụ thuộc vào một số hữu hạn các tham số.


2. Nguyên lý tối ưu và phương trình Bellman


Nguyên tắc tối ưuđược Richard Ernest Bellman xây dựng lần đầu tiên vào năm 1953 (được giải thích bởi E.S. Wentzel):

Bất kể trạng thái của hệ thống là kết quả của bất kỳ số bước nào, ở bước tiếp theo, cần phải chọn điều khiển sao cho nó cùng với điều khiển tối ưu ở tất cả các bước tiếp theo sẽ dẫn đến mức tăng tối ưu ở tất cả các bước còn lại, bao gồm cả cái này.

NỐT RÊ. Bellman cũng đưa ra các điều kiện để nguyên lý này đúng. Yêu cầu chính là quá trình kiểm soát phải không có phản hồi, tức là không có phản hồi. kiểm soát ở bước này sẽ không ảnh hưởng đến các bước trước đó.

Hãy xem xét nhiệm vụ chung lập trình động nêu trên. Ở mỗi bước ngoại trừ bước cuối cùng cho bất kỳ trạng thái nào của hệ thống k-1 quyết định quản lý X k cần phải chọn "một cách thận trọng", vì lựa chọn này ảnh hưởng đến trạng thái tiếp theo của hệ thống. .

Ở bước cuối cùng, dựa trên trạng thái của hệ thống n-1 quyết định quản lý X N có thể được lên kế hoạch tối ưu cục bộ, tức là chỉ dựa trên những cân nhắc của bước này.

Hãy xem xét điều cuối cùng bước thứ n:

S n-1 - trạng thái của hệ thống khi bắt đầu bước thứ n;

S N - trạng thái cuối cùng của hệ thống;

X N - kiểm soát ở bước thứ n;

f N (S n-1 , X N ) là hàm mục tiêu (kết quả) của bước thứ n.

Theo nguyên lý tối ưu, X N phải được chọn sao cho đối với bất kỳ trạng thái nào của hệ thống s n-1 đạt được sự tối ưu hàm mục tiêuở bước này.

Chúng ta hãy biểu thị bằng mức tối ưu (để xác định, chúng ta sẽ lấy mức tối đa) của hàm mục tiêu - một chỉ báo về hiệu quả của bước thứ n, với điều kiện là ở đầu bước cuối cùng, hệ S ở trạng thái tùy ý sn-1 , và ở bước cuối cùng sự kiểm soát là tối ưu.

được gọi là cực đại có điều kiện của hàm mục tiêu ở bước thứ n và được xác định theo công thức sau:



Việc tối đa hóa được thực hiện trên tất cả các biện pháp kiểm soát được chấp nhận Xn.

Giải pháp Xn mà tại đó đạt được điều này cũng phụ thuộc vào sn-1 và được gọi là giải pháp tối ưu có điều kiện ở bước thứ n. Hãy biểu thị nó bằng.

Sau khi giải quyết vấn đề tối ưu hóa cục bộ một chiều bằng phương trình (5), chúng tôi xác định hai hàm và cho tất cả các trạng thái có thể có sn-1.

Hãy xem xét một bài toán gồm hai bước: thêm (n-1) -th vào bước thứ n.

Đối với bất kỳ trạng thái sn-2 nào, các quyết định quản lý tùy ý Xn-1 và điều khiển tối ưu ở bước thứ n, giá trị của hàm mục tiêu tại hai bước cuối cùng x được tính theo công thức:


Theo nguyên lý tối ưu Bellman cho mọi s n-2 Giải pháp phải được chọn sao cho cùng với điều khiển tối ưu ở bước (n) cuối cùng sẽ dẫn đến sự tối ưu của hàm mục tiêu ở hai bước cuối cùng. Vì vậy, cần tìm biểu thức tối ưu (6) cho mọi quyết định quản lý được chấp nhận Xn-1 :



Nó được gọi là cực đại có điều kiện của hàm mục tiêu dưới sự điều khiển tối ưu ở hai bước cuối cùng. Cần lưu ý rằng biểu thức trong ngoặc nhọn trong công thức (6) chỉ phụ thuộc vào sn-2 và Xn-1, vì sn-1 có thể được tìm thấy từ phương trình trạng thái (1) với:



Điều khiển tương ứng Xn-1 ở bước thứ (n-1) được ký hiệu là điều khiển tối ưu có điều kiện ở bước thứ (n-1).

Tối ưu có điều kiện của hàm mục tiêu được xác định tương tự đối với điều khiển tối ưu ở bước (n-k+1), bắt đầu từ bước thứ k đến cuối, với điều kiện là ở đầu bước thứ k hệ thống ở trạng thái sk. -1:



Điều khiển Xk ở bước thứ k, tại đó đạt được mức tối đa theo (8), được ký hiệu và gọi là điều khiển tối ưu có điều kiện ở bước thứ k.

Các phương trình (5) và (8) được gọi là phương trình Bellman hồi quy (sơ đồ đảo ngược). Quá trình giải các phương trình này được gọi là tối ưu hóa có ràng buộc.

Kết quả là tối ưu hóa có điều kiện chúng tôi nhận được hai chuỗi:

, …, - cực đại có điều kiện của hàm mục tiêu ở bậc cuối, hai bậc cuối, …, ở n bước;

, …, - điều khiển tối ưu có điều kiện ở bước thứ n, (n-1) - thứ, …, ở bước 1.

Sử dụng các dãy này, chúng ta có thể tìm ra lời giải cho bài toán quy hoạch động với n và s0:

Kết quả ta thu được lời giải tối ưu của bài toán quy hoạch động: .

Sử dụng lý luận tương tự, chúng ta có thể xây dựng sơ đồ tối ưu hóa có điều kiện trực tiếp:



Giải pháp tối ưu cho vấn đề trong trong trường hợp nàyđược đặt theo sơ đồ sau:


Vì vậy, việc xây dựng mô hình quy hoạch động và giải bài toán dựa trên mô hình đó trong nhìn chung có thể được biểu diễn dưới dạng các giai đoạn sau:

Chọn phương pháp chia quy trình quản lý thành các bước.

Xác định các tham số trạng thái s k và các biến điều khiển X k Ở mỗi bước, phương trình trạng thái được viết.

3. Nhập các hàm mục tiêu của bước thứ k và hàm mục tiêu tổng, cũng như điều khiển tối ưu có điều kiện và điều khiển tối ưu có điều kiện ở bước thứ k ().

Các phương trình hồi quy Bellman được viết theo sơ đồ nghịch đảo hoặc trực tiếp và sau khi thực hiện tối ưu hóa có điều kiện, thu được hai chuỗi: () và ().

Giá trị tối ưu của hàm mục tiêu và lời giải tối ưu được xác định.


3. Vấn đề phân bổ nguồn lực


Có một lượng nguồn lực nhất định s0 phải được phân bổ giữa n thực thể kinh doanh cho các hoạt động hiện tại trong khoảng thời gian được xem xét (tháng, quý, nửa năm, năm, v.v.) để đạt được tổng lợi nhuận tối đa. Quy mô đầu tư nguồn lực xi (;) vào hoạt động của mỗi thực thể kinh tế là bội số của một giá trị h nhất định. Được biết, mỗi thực thể kinh tế tùy thuộc vào khối lượng vốn sử dụng xi trong kỳ được xem xét sẽ mang lại lợi nhuận bằng số fi(xi) (không phụ thuộc vào việc đầu tư nguồn lực vào các thực thể kinh tế khác).

Chúng ta hãy tưởng tượng quá trình phân bổ nguồn lực giữa các thực thể kinh doanh như một quy trình quản lý n bước (số bước trùng với số điều kiện của thực thể kinh doanh). Đặt sk() là tham số trạng thái, tức là số tiền khả dụng sau bước thứ k để phân bổ cho (n - k) đơn vị kinh doanh còn lại. Khi đó phương trình trạng thái có thể được viết dưới dạng mẫu sau:



Chúng ta hãy xem xét hàm - tổng lợi nhuận tối ưu có điều kiện nhận được từ thực thể kinh tế thứ k, (k+1) - thứ, ..., thứ n, nếu nguồn lực ở mức sk-1 () là được phân bổ tối ưu giữa chúng. Tập hợp các quyết định quản lý có thể có liên quan đến quy mô nguồn lực được phân bổ ở bước thứ k có thể được trình bày như sau: .

Khi đó các phương trình hồi quy của R.E. Bellman (sơ đồ ngược) sẽ có dạng:



Ví dụ. Có một lượng nguồn lực nhất định s0=100, phải được phân bổ cho n=4 đơn vị kinh doanh cho các hoạt động hiện tại trong khoảng thời gian được xem xét (tháng) để đạt được tổng lợi nhuận tối đa. Quy mô đầu tư nguồn lực xi (;) vào hoạt động của mỗi thực thể kinh tế là bội số của giá trị h=20 và được xác định bởi vectơ Q. Được biết, mỗi thực thể kinh tế tùy thuộc vào khối lượng vốn được sử dụng xi trong kỳ được xem xét, mang lại lợi nhuận với số tiền fi(xi) () (không phụ thuộc vào việc đầu tư nguồn lực vào đơn vị kinh tế khác):

Cần xác định cần phân bổ bao nhiêu nguồn lực cho mỗi doanh nghiệp để tổng lợi nhuận đạt được lớn nhất.

Giải pháp.Hãy tạo các phương trình hồi quy của Bellman (sơ đồ nghịch đảo):



Hãy xác định các cực đại có điều kiện theo (13); kết quả tính toán được trình bày ở Bảng 1.


Bảng 1. Tính toán tối ưu có điều kiện

S k-1 x k S k k=3k=2k=1 123456789101112000000000000200200+20=20 22 200+22=22 2200+22=22 22020022+0=22 17+0=1714+0=14400400+33=33 42 200+42=42 4200+42=42 420202022+20=42 17+22=3914+22=3640021+0=2120+0=2026+0=26600600+46=46 55 200+55=55 59 20 0+59=59 590204022+33=5517+42=59 14+42=56402021+20=4120+22=4226+22=4860037+0=3732+0=3235+0=35800800+30=30 68 200+68=68 72 200+72=72 73 20206022+46=6817+55=7214+59=73 404021+33=5420+42=6426+42=68602037+20=5732+22=5435+22=5780067+0=6761+0=6152+0=5210001000+42=42 87 800+87=87 8700+87=87 870208022+30=5217+68=8514+72=86406021+46=6720+55=7526+59=85604037+33=7032+42=7435+42=77802067+20=87 61+22=8352+22=74100058+0=5872+0=7261+0=61Dựa trên kết quả tối ưu hóa có điều kiện, chúng ta sẽ xác định cách phân bổ nguồn lực tối ưu:

Vì vậy, việc phân bổ nguồn lực tối ưu là:



sẽ mang lại lợi nhuận lớn nhất với số lượng 87 đơn vị thông thường. cái hang. các đơn vị

Trả lời: phân bổ nguồn lực tối ưu: mang lại lợi nhuận lớn nhất trong số 87 đơn vị thông thường. cái hang. các đơn vị


Phần kết luận


Lập trình động là một lĩnh vực lập trình toán học bao gồm một tập hợp các kỹ thuật và công cụ để tìm kiếm giải pháp tối ưu, cũng như tối ưu hóa từng bước trong hệ thống và phát triển chiến lược quản lý, nghĩa là quy trình quản lý có thể được biểu diễn dưới dạng quy trình gồm nhiều bước. Lập trình động, sử dụng lập kế hoạch từng bước, không chỉ cho phép đơn giản hóa việc giải quyết vấn đề mà còn giải quyết những vấn đề mà phương pháp không thể áp dụng phân tích toán học. Việc đơn giản hóa giải pháp đạt được bằng cách giảm đáng kể số lượng các phương án đang được nghiên cứu, vì thay vì giải quyết một vấn đề phức tạp nhiều biến một lần, phương pháp lập kế hoạch từng bước bao gồm nhiều giải pháp liên quan đến nhiệm vụ đơn giản. Khi lập kế hoạch cho một quy trình từng bước, chúng tôi tiến hành dựa trên lợi ích của toàn bộ quy trình, tức là. Khi đưa ra quyết định ở một giai đoạn cụ thể, luôn phải ghi nhớ mục tiêu cuối cùng. Tuy nhiên, lập trình động cũng có nhược điểm của nó. Không giống như lập trình tuyến tính, trong đó phương pháp đơn giản là phổ quát; không có phương pháp nào như vậy trong lập trình động. Mỗi công việc đều có những khó khăn riêng, trong mỗi trường hợp cần phải tìm ra phương pháp giải quyết phù hợp nhất. Nhược điểm của quy hoạch động còn là sự phức tạp trong việc giải các bài toán đa chiều. Một bài toán quy hoạch động phải thỏa mãn hai điều kiện. Điều kiện đầu tiên thường được gọi là điều kiện không có hậu quả, và điều kiện thứ hai là điều kiện cộng của hàm mục tiêu của bài toán. Trong thực tế, có những bài toán quy hoạch trong đó các yếu tố ngẫu nhiên đóng vai trò quan trọng, ảnh hưởng đến cả trạng thái của hệ thống và độ lợi. Có sự khác biệt giữa các bài toán quy hoạch động xác định và ngẫu nhiên. Trong bài toán xác định, điều khiển tối ưu là duy nhất và được xác định trước dưới dạng chương trình khó khăn hành động. Trong bài toán ngẫu nhiên, điều khiển tối ưu là ngẫu nhiên và được chọn trong suốt quá trình, tùy thuộc vào tình huống ngẫu nhiên. Trong sơ đồ tất định, trải qua quá trình theo từng giai đoạn từ đầu đến cuối, nó cũng ở mỗi giai đoạn toàn bộ dòngđiều khiển tối ưu có điều kiện, nhưng trong số tất cả các điều khiển này, cuối cùng chỉ có một điều khiển được thực hiện. Đây không phải là trường hợp trong một sơ đồ ngẫu nhiên. Mỗi điều khiển tối ưu có điều kiện thực sự có thể được triển khai nếu quá trình trước đó của quy trình ngẫu nhiên dẫn hệ thống đến trạng thái tương ứng. Nguyên lý tối ưu là cơ sở để giải từng bước các bài toán quy hoạch động. Đại diện tiêu biểu nhiệm vụ kinh tế lập trình động là những vấn đề được gọi là vấn đề sản xuất và lưu trữ, vấn đề phân phối đầu tư, vấn đề lập kế hoạch sản xuất và những vấn đề khác. Các bài toán quy hoạch động được sử dụng trong việc lập kế hoạch hoạt động của doanh nghiệp, có tính đến những thay đổi về nhu cầu sản phẩm theo thời gian. Trong việc phân bổ tối ưu nguồn lực giữa các doanh nghiệp theo phương hướng hoặc thời gian. Việc mô tả các đặc điểm của quy hoạch động và các loại vấn đề có thể được xây dựng trong khuôn khổ của nó nhất thiết phải rất chung chung và có phần mơ hồ, vì có rất nhiều loại vấn đề khác nhau. Các nhiệm vụ khác nhau, phù hợp với sơ đồ quy hoạch động. Chỉ học số lượng lớn các ví dụ cung cấp sự hiểu biết rõ ràng về cấu trúc của lập trình động.


Thư mục

  1. Các mô hình và phương pháp kinh tế và toán học. Lập trình tuyến tính: Hướng dẫn dành cho sinh viên chuyên ngành kinh tế / Biên soạn: Smirnov Yu.N., Shibanova E.V., Naberezhnye Chelny: Nhà xuất bản KamPI, 2004, 81 tr.
  2. Nghiên cứu hoạt động trong kinh tế: Sách giáo khoa. cẩm nang cho các trường đại học / N.Sh. Kremer, B.A. Putko, I.M. Trishin, M.N. Friedman; Ed. giáo sư N.Sh. Kremer. - M.: ĐOÀN KẾT, 2000. - 407 tr.
  3. Kuznetsov A.V. và những môn toán cao cấp khác: Mat. lập trình: Sách giáo khoa/A.V. Kuznetsov, V.A. Sakovich, N.I. Lạnh lẽo; Dưới sự chung chung biên tập. A.V. Kuznetsova. - Mn.: Cao hơn. school, 1994. - 286 trang.: bệnh.
Dạy kèm

Cần giúp đỡ nghiên cứu một chủ đề?

Các chuyên gia của chúng tôi sẽ tư vấn hoặc cung cấp dịch vụ dạy kèm về các chủ đề mà bạn quan tâm.
Gửi đơn đăng ký của bạn chỉ ra chủ đề ngay bây giờ để tìm hiểu về khả năng nhận được tư vấn.

Có một lượng nguồn lực nhất định phải được phân bổ giữa n đơn vị kinh doanh cho các hoạt động hiện tại trong khoảng thời gian được xem xét (tháng, quý, nửa năm, năm, v.v.) để đạt được tổng lợi nhuận tối đa. Quy mô nguồn lực đầu tư x i (;) vào hoạt động của mỗi thực thể kinh tế là bội số của một giá trị h nhất định. Được biết, mỗi thực thể kinh tế tùy thuộc vào số vốn sử dụng x i trong kỳ được xem xét sẽ tạo ra lợi nhuận với số tiền f i (x i) (không phụ thuộc vào việc đầu tư nguồn lực vào đơn vị kinh tế khác).

Chúng ta hãy tưởng tượng quá trình phân bổ nguồn lực giữa các thực thể kinh doanh như một quy trình quản lý n bước (số bước trùng với số điều kiện của thực thể kinh doanh). Đặt s k () là một tham số trạng thái, tức là số vốn khả dụng sau bước thứ k để phân bổ cho (n - k) đơn vị kinh doanh còn lại. Khi đó các phương trình trạng thái có thể được viết dưới dạng sau:

Chúng ta hãy xem xét hàm - tổng lợi nhuận tối ưu có điều kiện nhận được từ thực thể kinh tế thứ k, (k+1) - thứ, ..., thứ n, nếu nguồn lực ở mức s k-1 () được phân bổ tối ưu giữa chúng. Tập hợp các quyết định quản lý có thể có liên quan đến quy mô nguồn lực được phân bổ ở bước thứ k có thể được trình bày như sau: .

Khi đó các phương trình hồi quy của R.E. Bellman (sơ đồ ngược) sẽ có dạng:

Ví dụ. Có một lượng nguồn lực nhất định s 0 = 100, phải được phân bổ cho n=4 đơn vị kinh doanh cho các hoạt động hiện tại trong khoảng thời gian được xem xét (tháng) để đạt được tổng lợi nhuận tối đa. Quy mô đầu tư nguồn lực x i (;) vào hoạt động của mỗi thực thể kinh tế là bội số của giá trị h = 20 và được xác định bởi vectơ Q. Được biết, mỗi thực thể kinh tế tùy thuộc vào khối lượng vốn sử dụng x i trong kỳ được xem xét mang lại lợi nhuận với số tiền fi (x i) () (không phụ thuộc vào việc đầu tư nguồn lực vào đơn vị kinh tế khác):

Cần xác định cần phân bổ bao nhiêu nguồn lực cho mỗi doanh nghiệp để tổng lợi nhuận đạt được lớn nhất.

Giải pháp. Hãy tạo các phương trình hồi quy của Bellman (sơ đồ nghịch đảo):

Hãy xác định các cực đại có điều kiện theo (13); kết quả tính toán được trình bày ở Bảng 1.

Bảng 1. Tính toán tối ưu có điều kiện

22+20=42

22+33=55

17+42=59

22+46=68

17+55=72

14+59=73

67+20=87

Dựa trên kết quả tối ưu hóa có điều kiện, chúng ta sẽ xác định cách phân bổ nguồn lực tối ưu:


Vì vậy, việc phân bổ nguồn lực tối ưu là:

sẽ mang lại lợi nhuận lớn nhất với số lượng 87 đơn vị thông thường. cái hang. các đơn vị

Trả lời: phân bổ nguồn lực tối ưu: mang lại lợi nhuận lớn nhất trong số 87 đơn vị thông thường. cái hang. các đơn vị

Phần kết luận

Lập trình động là một lĩnh vực lập trình toán học bao gồm một tập hợp các kỹ thuật và công cụ để tìm ra giải pháp tối ưu, cũng như tối ưu hóa từng bước trong hệ thống và phát triển chiến lược điều khiển, nghĩa là quy trình điều khiển có thể được biểu diễn dưới dạng một quá trình nhiều bước. Lập trình động, sử dụng lập kế hoạch từng bước, không chỉ cho phép đơn giản hóa việc giải quyết vấn đề mà còn giải quyết những vấn đề không thể áp dụng bằng phương pháp phân tích toán học. Việc đơn giản hóa lời giải đạt được bằng cách giảm đáng kể số lượng các phương án đang được nghiên cứu, vì thay vì giải một bài toán nhiều biến phức tạp một lần, phương pháp lập kế hoạch từng bước bao gồm việc giải các bài toán tương đối đơn giản nhiều lần. Khi lập kế hoạch cho một quy trình từng bước, chúng tôi tiến hành dựa trên lợi ích của toàn bộ quy trình, tức là. Khi đưa ra quyết định ở một giai đoạn cụ thể, luôn phải ghi nhớ mục tiêu cuối cùng. Tuy nhiên, lập trình động cũng có nhược điểm của nó. Không giống như quy hoạch tuyến tính, trong đó phương pháp đơn hình là phổ biến, không có phương pháp nào như vậy trong quy hoạch động. Mỗi công việc đều có những khó khăn riêng, trong mỗi trường hợp cần phải tìm ra phương pháp giải quyết phù hợp nhất. Nhược điểm của quy hoạch động còn là sự phức tạp trong việc giải các bài toán đa chiều. Một bài toán quy hoạch động phải thỏa mãn hai điều kiện. Điều kiện đầu tiên thường được gọi là điều kiện không có hậu quả, và điều kiện thứ hai là điều kiện cộng của hàm mục tiêu của bài toán. Trong thực tế, có những bài toán quy hoạch trong đó các yếu tố ngẫu nhiên đóng vai trò quan trọng, ảnh hưởng đến cả trạng thái của hệ thống và độ lợi. Có sự khác biệt giữa các bài toán quy hoạch động xác định và ngẫu nhiên. Trong một bài toán xác định, điều khiển tối ưu là duy nhất và được xác định trước như một chương trình hành động cứng nhắc. Trong bài toán ngẫu nhiên, điều khiển tối ưu là ngẫu nhiên và được chọn trong suốt quá trình, tùy thuộc vào tình huống ngẫu nhiên. Trong sơ đồ xác định, trải qua quá trình theo từng giai đoạn từ đầu đến cuối, cũng có một loạt các điều khiển tối ưu có điều kiện ở mỗi giai đoạn, nhưng trong số tất cả các điều khiển này, cuối cùng chỉ có một điều khiển được thực hiện. Đây không phải là trường hợp trong một sơ đồ ngẫu nhiên. Mỗi điều khiển tối ưu có điều kiện thực sự có thể được triển khai nếu quá trình trước đó của quy trình ngẫu nhiên dẫn hệ thống đến trạng thái tương ứng. Nguyên lý tối ưu là cơ sở để giải từng bước các bài toán quy hoạch động. Đại diện điển hình của các vấn đề kinh tế của quy hoạch động là các vấn đề được gọi là vấn đề sản xuất và lưu trữ, vấn đề phân phối vốn đầu tư, vấn đề lập kế hoạch sản xuất và những vấn đề khác. Các bài toán quy hoạch động được sử dụng trong việc lập kế hoạch hoạt động của doanh nghiệp, có tính đến những thay đổi về nhu cầu sản phẩm theo thời gian. Trong việc phân bổ tối ưu nguồn lực giữa các doanh nghiệp theo phương hướng hoặc thời gian. Việc mô tả các đặc điểm của quy hoạch động và các loại bài toán có thể được xây dựng trong khuôn khổ của nó nhất thiết phải rất chung chung và hơi mơ hồ, vì có vô số các bài toán khác nhau phù hợp với sơ đồ quy hoạch động. Chỉ nghiên cứu một số lượng lớn các ví dụ mới có thể hiểu rõ cấu trúc của quy hoạch động.

Phương pháp lập trình động cho phép bạn giải quyết thành công nhiều vấn đề kinh tế (xem ví dụ). Hãy xem xét một trong những vấn đề đơn giản nhất như vậy. Chúng tôi có sẵn một số quỹ dự trữ (tài nguyên) K, số tiền này phải được phân phối giữa các doanh nghiệp. Mỗi doanh nghiệp, khi một số quỹ được đầu tư vào nó, sẽ tạo ra thu nhập phụ thuộc vào, tức là đại diện cho một số loại chức năng. Tất cả các chức năng đều được đưa ra (tất nhiên, các chức năng này không giảm).

Câu hỏi đặt ra là quỹ K nên được phân bổ như thế nào giữa các doanh nghiệp để tổng thu nhập của họ đạt được tối đa?

Vấn đề này có thể giải quyết dễ dàng bằng phương pháp quy hoạch động. Mặc dù trong công thức của nó không đề cập đến thời gian, nhưng vẫn có thể hình dung hoạt động phân phối vốn theo trình tự nào đó, coi bước đầu tiên là đầu tư vốn vào doanh nghiệp, bước thứ hai, v.v.

Hệ thống được quản lý S trong trường hợp này là tiền hoặc tài nguyên được phân phối. Trạng thái của hệ thống S trước mỗi bước được đặc trưng bởi một số S - lượng vốn sẵn có chưa được đầu tư. Trong nhiệm vụ này, “quản lý từng bước” là kinh phí được phân bổ cho doanh nghiệp. Cần phải tìm ra sự kiểm soát tối ưu, tức là một tập hợp các số mà tổng thu nhập là tối đa:

Chúng ta hãy giải quyết vấn đề này trước tiên ở dạng tổng quát, dạng công thức và sau đó là dữ liệu số cụ thể. Chúng ta hãy tìm cho mỗi bước mức tăng tối ưu có điều kiện (từ bước này đến cuối), nếu chúng ta đạt được bước này với quỹ dự trữ S. Hãy biểu thị mức tăng tối ưu có điều kiện và kiểm soát tối ưu có điều kiện tương ứng - số tiền đầu tư vào doanh nghiệp -

Hãy bắt đầu tối ưu hóa từ bước cuối cùng. Chúng ta hãy tiếp cận bước này với số dư tiền S. Chúng ta nên làm gì? Rõ ràng, hãy đầu tư toàn bộ số tiền S vào doanh nghiệp. Do đó, điều khiển tối ưu có điều kiện ở bước thứ: cung cấp cho doanh nghiệp cuối cùng tất cả số tiền hiện có S, tức là.

và mức tăng tối ưu có điều kiện

Cho cả một dãy giá trị của S (định vị chúng khá gần nhau), chúng ta sẽ biết từng giá trị của S. Bước cuối cùng được tối ưu hóa.

Hãy chuyển sang bước áp chót. Chúng ta hãy tiếp cận nó với số tiền dự trữ S. Hãy biểu thị mức tăng tối ưu có điều kiện ở hai bước cuối cùng: (đã được tối ưu hóa). Nếu chúng tôi phân bổ vốn cho doanh nghiệp ở bước này thì số tiền thắng của chúng tôi ở hai bước cuối cùng sẽ bằng.

và bạn cần tìm một mức mà mức tăng này là tối đa:

Dấu hiệu này có nghĩa là giá trị lớn nhất được lấy trên tất cả các giá trị có thể (chúng ta không thể đặt nhiều hơn S), từ biểu thức trong dấu ngoặc nhọn. Mức tối đa này là mức tăng tối ưu có điều kiện cho hai bước cuối cùng và giá trị mà mức tối đa này đạt được là điều khiển tối ưu có điều kiện ở bước đó.

và điều khiển tối ưu có điều kiện tương ứng là giá trị đạt được mức tối đa này.

Tiếp tục theo cách này, cuối cùng chúng ta sẽ đến được doanh nghiệp. Ở đây chúng ta sẽ không cần thay đổi các giá trị của S; chúng ta biết chắc chắn rằng lượng vốn trước bước đầu tiên bằng K:

Vì vậy, mức tăng (thu nhập) tối đa từ tất cả các doanh nghiệp đã được tìm thấy. Bây giờ tất cả những gì còn lại là “đọc các khuyến nghị”. Giá trị đạt cực đại (13,4) là điều khiển tối ưu ở bước 1.

Sau khi chúng tôi đầu tư số tiền này vào doanh nghiệp đầu tiên, chúng tôi sẽ còn lại chúng. “Đọc” khuyến nghị cho giá trị S này, chúng tôi phân bổ cho doanh nghiệp thứ hai số lượng tối ưu có nghĩa là: v.v. cho đến hết.

Bây giờ hãy giải một ví dụ số. Lượng vốn ban đầu (đơn vị tiêu chuẩn) và cần phải phân phối nó một cách tối ưu cho năm doanh nghiệp. Để đơn giản, chúng tôi giả định rằng chỉ toàn bộ số tiền được đầu tư. Các hàm thu nhập được cho trong Bảng 13.1.

Bảng 13.1

Trong mỗi cột, bắt đầu từ một khoản đầu tư nhất định, thu nhập sẽ ngừng tăng (trên thực tế, điều này tương ứng với việc mỗi doanh nghiệp chỉ có thể “chấp nhận” một số vốn hạn chế).

Hãy thực hiện tối ưu hóa có điều kiện như mô tả ở trên, bắt đầu từ bước cuối cùng, bước thứ 5. Mỗi khi chúng tôi tiếp cận bước tiếp theo, có nguồn vốn dự trữ?, chúng tôi cố gắng phân bổ số tiền này hoặc số tiền khác cho bước này, lấy tiền thắng ở bước này theo bảng 13.1, cộng chúng với số tiền thắng đã được tối ưu hóa ở tất cả các bước tiếp theo. bước cho đến khi kết thúc (có tính đến việc chúng tôi còn lại ít tiền hơn, chỉ với số tiền mà chúng tôi đã phân bổ) và chúng tôi tìm thấy khoản đầu tư mà số tiền này đạt đến mức tối đa. Khoản đầu tư này là sự kiểm soát tối ưu có điều kiện ở bước này và bản thân mức tối đa là mức tăng tối ưu có điều kiện.

Bảng 13.2 thể hiện kết quả tối ưu hóa có điều kiện cho tất cả các bước. Bảng được xây dựng như sau: cột đầu tiên cung cấp các giá trị của kho quỹ S mà chúng tôi tiếp cận bước này. Bảng này còn được chia thành năm cặp cột, tương ứng với số bước.

Bảng 13.2

Cột đầu tiên của mỗi cặp cung cấp giá trị của điều khiển tối ưu có điều kiện, cột thứ hai - mức tăng tối ưu có điều kiện. Bảng được điền từ trái sang phải, từ trên xuống dưới. Quyết định ở bước thứ năm - bước cuối cùng là bắt buộc: tất cả kinh phí được phân bổ; Ở tất cả các bước khác, giải pháp phải được tối ưu hóa. Là kết quả của việc tối ưu hóa tuần tự các bước thứ 5, 4, 3, 2 và 1, chúng tôi nhận được danh sách đầy đủ tất cả các khuyến nghị để kiểm soát tối ưu và mức tăng tối ưu vô điều kiện W cho toàn bộ hoạt động - trong trường hợp này nó bằng 5,6. Trong hai cột cuối cùng của Bảng 13.2, chỉ có một hàng được điền vào, vì chúng ta biết chính xác trạng thái của hệ thống trước khi bắt đầu bước đầu tiên: . Điều khiển tối ưu Tất cả các bước được đánh dấu bằng một khung. Vì vậy, chúng tôi nhận được kết luận cuối cùng: chúng tôi phải phân bổ hai đơn vị trong số mười đơn vị cho doanh nghiệp thứ nhất, năm đơn vị cho doanh nghiệp thứ hai, hai đơn vị cho doanh nghiệp thứ ba, không có đơn vị nào cho doanh nghiệp thứ tư và một đơn vị cho doanh nghiệp thứ năm. Với cách phân phối này, thu nhập sẽ tối đa và bằng 5,6.

- 1,03 MB

Hãy để chúng tôi đưa ra một công thức toán học của nguyên lý tối ưu. Để đơn giản, chúng ta sẽ giả sử rằng các trạng thái x 0 và x T cuối cùng của hệ thống đã cho. Ta biểu thị bằng z 1 (x 0 , u 1) giá trị của hàm mục tiêu ở giai đoạn đầu với trạng thái ban đầu của hệ x 0 và với điều khiển u 1 , bằng z 2 (x 1 , u 2) tương ứng giá trị của hàm mục tiêu chỉ ở giai đoạn thứ hai, .., thông qua
z tôi (х i -1 ,u i) – trên giai đoạn thứ i, ..., qua z N (x N -1 , u N) -on Giai đoạn thứ N. Hiển nhiên là

Cần phải tìm điều khiển tối ưu u*= (; ;...;), sao cho nó đạt cực trị của hàm mục tiêu (1) dưới điều kiện hạn chế.

Để giải quyết vấn đề này, chúng tôi đưa nó vào một họ gồm những người tương tự. Hãy để chúng tôi giới thiệu một số ký hiệu. Lần lượt là các diện tích

định nghĩa cho các vấn đề tương tự ở giai đoạn cuối, hai giai đoạn cuối, v.v.;
– Miền định nghĩa của bài toán ban đầu. Ta ký hiệu lần lượt là F 1 (x N -1), F 2 (x N -2), ..., F k (x N -k), ..., F N (x 0), tối ưu có điều kiện các giá trị của hàm mục tiêu ở giai đoạn cuối, hai giá trị cuối cùng, v.v., ở k giá trị cuối cùng, v.v., ở tất cả N giai đoạn.

Hãy bắt đầu với giai đoạn cuối. Gọi x N-1 là các trạng thái có thể có của hệ thống khi bắt đầu giai đoạn thứ N. Chúng ta tìm thấy:

F 1 (x N -1) = z N (x N -1, u N). (2)

Đối với hai giai đoạn cuối cùng, chúng tôi nhận được

F 2 (x N -2) = (Z N -1 (x N -2, u N -1) + F 1 (x N -1)). (3)

Tương tự:

F 3 (x N -3) = (Z N -2 (x N -3, u N -2) + F 2 (x N -2)). (4)

………………………………………………….

F k (x N -k) = (z N-k +1 (x N -k , u N-k +1) + F k- 1 (x N-k +1)). (5)

…………………………………………………..

F N (x 0) = (z 1 (x 0, u 1) + F N -1 (x 1)). (6)

Biểu thức (6) là biểu diễn toán học của nguyên lý tối ưu. Biểu thức (5) là dạng tổng quát viết giá trị tối ưu có điều kiện của hàm mục tiêu cho k giai đoạn còn lại. Biểu thức (2) – (6) được gọi là phương trình Bellman hàm số. Bản chất tuần hoàn (recurrent) của chúng được thể hiện rõ ràng, tức là để tìm điều khiển tối ưu ở N bước, bạn cần biết điều khiển tối ưu có điều kiện ở N – 1 giai đoạn trước đó, v.v. Do đó, phương trình hàm số thường được gọi là hồi quy (recurrent) Quan hệ Bellman

    1. Đặc điểm của bài toán quy hoạch động

Dựa vào những điều trên, chúng ta có thể nêu bật các đặc điểm sau của bài toán quy hoạch động.

  • Chúng ta xem xét một hệ thống có trạng thái ở mỗi bước được xác định bởi vectơ x t. Những thay đổi tiếp theo trong tình trạng của cô ấy chỉ phụ thuộc vào trạng thái này x t và không phụ thuộc vào cách hệ thống đạt đến trạng thái này. Những quá trình như vậy được gọi là quá trình không có hậu quả.
  • Ở mỗi bước, một giải pháp được chọn, dưới ảnh hưởng của hệ thống sẽ đi từ đó trạng thái trước đó x t -1 sang mới x t . Trạng thái mới này là một hàm của trạng thái ở đầu khoảng x t -1 và quyết định u t được thông qua ở đầu khoảng, tức là x t = x t (x t -1 ,u t).
  • Hành động ở mỗi bước gắn liền với một khoản lãi (thu nhập, lợi nhuận) hoặc lỗ (chi phí) nhất định, tùy thuộc vào trạng thái khi bắt đầu bước (giai đoạn) và quyết định được đưa ra.
  • Các hạn chế có thể được áp đặt đối với các vectơ trạng thái và điều khiển, sự kết hợp của chúng tạo thành vùng của các giải pháp khả thi.
  • Cần phải tìm một điều khiển chấp nhận được cho mỗi bước t để đạt được giá trị cực trị của hàm mục tiêu cho tất cả T bước.

Bất kỳ chuỗi hành động hợp lệ nào cho mỗi bước chuyển hệ thống từ trạng thái ban đầu sang trạng thái cuối cùng đều được gọi là chiến lược điều khiển. Chiến lược điều khiển mang lại giá trị cực trị của hàm mục tiêu được gọi là tối ưu.

Giải thích hình học của bài toán quy hoạch động như sau. Gọi n là chiều của không gian trạng thái. Tại mỗi thời điểm, tọa độ của hệ thống hoàn toàn giá trị cụ thể. Với sự thay đổi trong thời gian t, các giá trị tọa độ của vectơ trạng thái có thể thay đổi. Chúng ta gọi sự chuyển đổi của một hệ thống từ trạng thái này sang trạng thái khác là quỹ đạo chuyển động của nó trong không gian trạng thái. Việc chuyển đổi như vậy được thực hiện bằng cách tác động đến tọa độ trạng thái. Không gian trong đó các trạng thái của hệ đóng vai trò là tọa độ được gọi là không gian pha. Bài toán quy hoạch động có thể được giải thích một cách đặc biệt rõ ràng nếu không gian trạng thái là hai chiều. Diện tích của các trạng thái có thể có trong trường hợp này sẽ được mô tả bằng một hình nhất định, trạng thái ban đầu và cuối cùng của hệ thống - theo điểm x 0 (Hình 1). Kiểm soát là tác động chuyển hệ thống từ trạng thái ban đầu sang trạng thái cuối cùng. Đối với nhiều bài toán kinh tế, trạng thái ban đầu hoặc trạng thái cuối cùng không được biết, nhưng vùng X 0 hoặc X T mà các điểm này thuộc về thì được biết.

Bức tranh 1

Khi đó các điều khiển chấp nhận được chuyển điểm từ vùng X 0 sang X T . Bài toán quy hoạch động có thể được phát biểu dưới dạng hình học như sau: tìm quỹ đạo pha bắt đầu trong vùng X 0 và kết thúc trong vùng X T mà hàm mục tiêu đạt giá trị cực trị. Nếu biết trạng thái ban đầu và trạng thái cuối cùng của một bài toán quy hoạch động thì chúng ta nói về bài toán có các đầu cố định. Nếu biết vùng đầu và vùng cuối thì chúng ta nói về bài toán có các đầu tự do.

  1. VẤN ĐỀ PHÂN PHỐI NGUỒN LỰC

2.1 Phát biểu chung của vấn đề

Hãy xem xét việc áp dụng phương pháp quy hoạch động bằng ví dụ về phân bổ vốn giữa sáu đối tượng tái thiết của một công ty cấp nước thành phố:

1. Trạm bơm, lọc trung tâm;

2. Trạm bơm lọc phía Đông;

3. Trạm bơm nước;

4. Trạm sục khí trung tâm;

5. Trạm sục khí phía Đông;

6. Trạm sục khí quốc gia.

Tổng số vốn cung cấp cho việc phát triển không quá 195 nghìn hryvnia. Dựa trên các tính toán kinh tế và kỹ thuật, người ta xác định rằng sau khi tái thiết, tùy thuộc vào số tiền chi tiêu, các cơ sở sẽ có năng suất như trong Bảng 1.1. Cần xác định cách phân bổ kinh phí tối ưu giữa các đối tượng tái thiết, điều này sẽ đảm bảo tăng tối đa năng suất của các đối tượng này. Vì vậy, bài toán này sử dụng tiêu chí tối ưu hóa - tổng năng suất của các doanh nghiệp của các đối tượng tái thiết.

Bảng 1.1 Dữ liệu đầu vào cho năng suất của các đối tượng tái thiết

Số sê-ri đối tượng

Khối lượng nguồn lực được phân bổ cho việc phát triển cơ sở vật chất (nghìn UAH)

Năng suất của các đối tượng do phát triển (nghìn m3)
    1. Sơ đồ khối của chương trình

Hình 1. Chương trình chính

QtObj – số lượng đối tượng


QtRes – số lượng tài nguyên

effMatrix - ma trận hiệu suất đối tượng,


distVector – vector của tài nguyên được phân bổ


Bước 1: Tối ưu hóa có điều kiện

Bước 2. Tối ưu hóa vô điều kiện


I = QtObj-1.0 tạo thành kết quả vectơ

Hình 2. Nhập dữ liệu

distVector – vectơ khoảng cách, effMatrix = ma trận hiệu suất

nếu tất cả các phần tử ma trận được nhập



nếu vectơ hiệu suất không

tiêu cực

Hình 3. Tối ưu hóa có điều kiện,

chúng tôi tạo thành một ma trận đầu ra (cực đại của hàm mục tiêu)


outMatrix - ma trận mục tiêu tối đa

QtObj – số lượng đối tượng

QtRes – số lượng tài nguyên

Ma trận – ma trận hiệu suất

distVect – vector khoảng cách (vector tài nguyên)

không có Nếu doanh nghiệp đầu tiên

Tìm mức tối đa


có maxItem = tạm thời; outMatrix[i][j] = maxItem

    1. Cấu trúc thuật toán chương trình
  1. Dữ liệu đầu vào – lớp DataDlg.

Các thành viên của lớp có thể thay đổi.

//vector lưu trữ số lượng tài nguyên

std::vectơ distVector;

// ma trận hiệu suất đối tượng

int** effMatrix;

//hàm chuyển chuỗi thành số

int StringToInt(CString);

//Hàm kiểm tra tính đúng đắn của dữ liệu nhập vào

BOOL FillMatrix();

// chức năng dọn dẹp tài nguyên sau khi đóng cửa sổ

ảo BOOL DestroyWindow();

//hàm khởi tạo hộp thoại

BOOL ảo OnInitDialog();

  1. Tính kết quả - lớp chính của chương trình khóa họcWorkDlg

Thành viên lớp biến

intValue; // giá trị hiệu suất

int MaxIndex;// chỉ số tối đa trong vectơ tài nguyên

Cơ sở int;//doanh nghiệp

int Resource;//tài nguyên chuyên dụng

Mục ** outMatrix; // ma trận mục tiêu tối đa

std::vectơ resVector; //vectơ kết quả

void BuildOutMatrix(int ​​​​**,std::vector );//hàm tạo ma trận mục tiêu (tối ưu hóa có điều kiện)

afx_msg void OnBnClickedButton1(); // trình xử lý để nhấp vào nút "Tính toán", nút này sẽ bắt đầu quá trình tính toán.

BOOL ảo DestroyWindow();//xóa tài nguyên chương trình

  1. Xuất kết quả lớp Báo cáo

Mục đích của lớp này là xuất ra vectơ kết quả ở dạng bảng.

2.4 Kết quả của chương trình

Nhập dữ liệu ban đầu

  1. Nhập dữ liệu về năng suất của các đối tượng tái thiết
  1. Nếu không phải tất cả các trường đều được điền vào
  1. Nếu nhập sai ký tự

Nhập dữ liệu chính xác

Kết quả cho thấy

  1. Nhập dữ liệu

Kết quả của chương trình

Nhập dữ liệu ban đầu

Nhập năng suất đối tượng

Ứng dụng.

Danh sách chương trình

int DataDlg::StringToInt(CString str)

const wchar_t* s = T2CW(str);

int val = _wtoi(s);

// tất cả các trường đã được điền chưa?

Dữ liệu BOOLDlg::FillMatrix()

cờ bool = đúng;

vì (int i = 0; tôi< Cells.GetSize(); i ++){

vì (int j = 0 ; j< Cells.GetAt(i)->Chỉnh sửa.GetSize(); j++)(

CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j) ;

if (temp->m_hWnd != NULL)(

tạm thời->GetWindowText(str);

if (str.IsEmpty())(

MessageBox(L"Bạn cần điền vào tất cả các trường", L"Lỗi", MB_ICONERROR | MB_OK);

Mô tả công việc

Mục đích của công việc này là thực hiện trên máy tính một giải pháp cho vấn đề phân bổ vốn tối ưu cho việc mở rộng sản xuất.
Mục tiêu môn học:
Coi như khía cạnh lý thuyết giải quyết các bài toán quy hoạch động; tính chất thường xuyên của nhiệm vụ thuộc loại này; Nguyên lý tối ưu của Bellman.
Phát triển thuật toán. Sơ đồ khối. Cấu trúc thuật toán.
Máy tính thực hiện thuật toán đã phát triển bằng ngôn ngữ lập trình đã chọn.

Nội dung

GIỚI THIỆU……………………………………………………2
Lập trình năng động
Các khái niệm cơ bản……………4
Nguyên lý của quy hoạch động. Phương trình hàm Bellman………….5
Đặc điểm của bài toán quy hoạch động………….10
Vấn đề phân bổ nguồn lực………….12
Phát biểu chung của vấn đề………….13
Sơ đồ khối của chương trình
Cấu trúc thuật toán chương trình
Kết quả của chương trình
Phần kết luận
Thư mục

Gửi công việc tốt của bạn trong cơ sở kiến ​​thức thật đơn giản. Sử dụng mẫu dưới đây

Làm tốt lắm vào trang web">

Các sinh viên, nghiên cứu sinh, các nhà khoa học trẻ sử dụng nền tảng kiến ​​thức trong học tập và công việc sẽ rất biết ơn các bạn.

Đăng trên http://www.allbest.ru/

Bài toán cấp phát tài nguyên bằng phương pháp quy hoạch động

Để mở rộng năng lực sản xuất của 3 doanh nghiệp A, B và C, một số đơn vị điện năng bổ sung nhất định được phân bổ với số lượng x 0 = 8 đơn vị. Điện có thể được giải phóng dưới dạng 1, 2, 3, 4, 5, 6, 7 và 8 đơn vị. Bằng cách đầu tư x i đơn vị điện vào sự phát triển của doanh nghiệp thứ i, bạn có thể nhận được thu nhập từ i đơn vị điện tại doanh nghiệp. Hiện hữu các biến thể khác nhau x i (k) phân bổ điện bổ sung. Chúng mang lại thu nhập cho i(k), k=1,n. Tùy chọn có thể phát triển của doanh nghiệp được trình bày ở Bảng 1. Tổng thu nhập của tất cả các doanh nghiệp phải là tối đa, tức là y=? y i (k)>max

Bàn 1. Các phương án phát triển doanh nghiệp

Tùy chọn k

Doanh nghiệp A

Doanh nghiệp B

Doanh nghiệp C

Toán học dàn dựng nhiệm vụ:

y=? Tại Tôi (k)> tối đa

?X Tôi (k)?x 0

Giải pháp:

Hãy bắt đầu xem xét quy trình giải quyết vấn đề từ giai đoạn (3 bước) cuối cùng (Bảng 2), tại đó các khoản đầu tư được phân bổ cho doanh nghiệp C. Kiểm soát tối ưu có điều kiện ở giai đoạn thứ ba được tìm kiếm như một giải pháp cho phương trình

g C (S 2)=max k f c , x C (k)?S 2 , k=1,2,3,4

Bàn 2. Giải pháp tối ưu có điều kiện (bước 3)

Tình trạng

Điều khiển

Có bốn khả năng đầu tư vốn - kiểm soát bốn bước x C (1) = 0 đơn vị, x C (2) = 1 đơn vị, x C (3) = 2 đơn vị, x C (4) = 3 đơn vị. và chín trạng thái có thể có về mặt lý thuyết của hệ thống S 2 trước khi phân bổ vốn cho doanh nghiệp C - khối lượng đầu tư không được phân bổ cho giai đoạn 3: 0,1,2,3,4,5,6,7,8.

Giả sử hệ thống ở trạng thái S 2 = 2. Khi đó, với điều khiển bước x C (2) = 1, thu nhập của C (2) sẽ bằng 3 đơn vị. (Bảng 3) và điều khiển bước x C (3) = 2 sẽ tối ưu cho trạng thái này, mang lại mức tăng tối đa có điều kiện g c (S 2) = 5. Nếu hệ thống ở trạng thái S 2 =3 thì cho phép tất cả các điều khiển bước: x C (1) = 0 đơn vị, x C (2) = 1 đơn vị, x C (3) = 2 đơn vị, x C (4) = 3 đơn vị, và điều khiển tối ưu sẽ là x C (4) = 3, mang lại mức tăng tối đa có điều kiện g c (S 2) = 6.

Bảng 3 phân bổ đầu tư lập trình động

Tất cả các trạng thái có thể có trước giai đoạn thứ 3 đều được điền tương tự. Giá trị tối ưu các chỉ số được tô đậm trong các bảng.

Tiếp theo, giai đoạn thứ hai được xem xét theo cách tương tự (Bảng 4), bao gồm việc phân bổ đầu tư cho doanh nghiệp A. Ở giai đoạn thứ hai, tổng số tiền thu được là tổng số tiền thắng được nhận được ở giai đoạn thứ ba và thứ hai, và được tính theo tỉ lệ:

g A (S 1)=max k f A +g c], x A (k)?S 1, k=1,2,3,4

Do đó, đối với trạng thái S 1 = 3 với điều khiển bước x A (2) = 1, chúng ta thu được:

g A (S 1)=max k f A +g c ]

Max k 4+g c =4+5=9, trong đó chúng ta tìm thấy từ Bảng 1, và g c từ Bảng 3. Tất cả các trạng thái được điền tương tự.

Bàn 4. Giải pháp tối ưu có điều kiện (bước 2)

Tình trạng

f A +g c

Điều khiển

Ở đây nảy sinh các tình huống trong đó giải pháp tối ưu sẽ không phải là giải pháp duy nhất. Do đó, ở trạng thái S 1 = 3, điều khiển bước x A (2) = 1 và x A (3) = 2 sẽ tối ưu có điều kiện, cho kết quả tương tự. tăng g A (S 1)=9

Bàn 5. Giải pháp tối ưu vô điều kiện (bước 1)

Ở giai đoạn đầu tiên (Bảng 5) - phân bổ đầu tư cho doanh nghiệp B - chỉ có một trạng thái trước đó của hệ thống, tương ứng với trạng thái ban đầu S 0 =8. Độ lợi tối ưu vô điều kiện được xác định bằng biểu thức:

y * = g B (S 0)= max k (f A +g A) x in (k)?S 0 =x 0, k=1,2,3,4,5

Kiểm soát tối ưu vô điều kiện để đảm bảo thu nhập tối đa có thể khác nhau.

Kế hoạch tìm kiếm mọi người lựa chọn tối ưu phân bổ đầu tư giữa các doanh nghiệp (Bảng 6) được trình bày trong Hình 1.

Bàn 6. Phân phối đầu tư tối ưu.

Hình 1. Sơ đồ phân bổ đầu tư tối ưu giữa các doanh nghiệp

Kết luận: Sau khi xem xét bài toán phân bổ nguồn lực bằng phương pháp quy hoạch động, đã xác định được hai phương án phân bổ nguồn lực tối ưu.

Đăng trên Allbest.ru

...

Tài liệu tương tự

    đặc điểm chung và các chỉ số hiệu quả kinh tế của ba doanh nghiệp được nghiên cứu. Giải quyết bài toán lập kế hoạch sản xuất cũng như phân bổ đầu tư bằng lập trình tuyến tính và động. Phân tích so sánh kết quả.

    bài tập khóa học, được thêm vào ngày 25/04/2015

    Quy trình gồm nhiều bước trong nhiệm vụ năng động. Nguyên lý tối ưu và quan hệ truy hồi. Phương pháp lập trình động. Các vấn đề về phân bổ vốn tối ưu cho việc mở rộng sản xuất và lập kế hoạch chương trình sản xuất.

    bài tập khóa học, được thêm vào ngày 30/12/2010

    Phương pháp quy hoạch động và các giai đoạn chính của nó. Chiến lược thay thế thiết bị tối ưu. Giảm thiểu chi phí xây dựng và vận hành của doanh nghiệp. Phân phối tối ưu các nguồn lực trong STROYKROVLYA LLC và đầu tư vào PKT Khimvolokno.

    bài tập khóa học, được thêm vào ngày 08/01/2015

    Mô hình toán học lập kế hoạch sản xuất. Lập phương án tối ưu hoạt động sản xuất doanh nghiệp sử dụng phương pháp quy hoạch tuyến tính. Phát hiện cách tốt nhất phân bổ nguồn lực tiền tệ trong thời kỳ kế hoạch.

    luận văn, bổ sung 07/08/2013

    Tính chi phí vận chuyển theo phương pháp chi phí tối thiểu. Tìm sự bình đẳng tối ưu có điều kiện trong quá trình quy hoạch động. tuyến tính phương trình đại số Kolmogorov về thời gian không xảy ra sự cố trung bình của một hệ thống dự phòng.

    bài tập khóa học, được thêm vào ngày 14/01/2011

    Phương pháp đồ họa giải quyết một vấn đề tối ưu hóa quy trinh san xuat. Ứng dụng thuật toán đơn hình để giải bài toán quản lý sản xuất tối ưu về mặt kinh tế. Phương pháp lập trình động để chọn cấu hình đường dẫn tối ưu.

    kiểm tra, thêm vào 15/10/2010

    Kế hoạch phân phối tối ưu Tiền bạc giữa các doanh nghiệp. Xây dựng kế hoạch cho từng doanh nghiệp trong đó lợi tức đầu tư sẽ được giá trị cao nhất. Sử dụng phương pháp quy hoạch tuyến tính và động.

    bài tập khóa học, được thêm vào ngày 16/12/2013

    Đặc điểm tính cách các bài toán quy hoạch tuyến tính. Tổng hợp bài toán lập kế hoạch sản xuất. Sự thi công mô hình toán học phân phối nguồn lực của công ty. Phân tích độ nhạy của giải pháp tối ưu. Lập báo cáo tính bền vững.

    trình bày, thêm vào ngày 02/12/2014

    Tìm danh mục chứng khoán tối ưu. Nhận xét các phương pháp giải quyết vấn đề. Xây dựng mô hình toán học. Vấn đề lập trình hình nón. Sự phụ thuộc của vectơ phân phối vốn ban đầu vào một trong các tham số ban đầu.

    luận văn, bổ sung 11/02/2017

    Mô hình lập trình động. Nguyên lý tối ưu và phương trình Bellman. Mô tả quá trình mô hình hóa và xây dựng sơ đồ lập trình động tính toán. Bài toán giảm thiểu chi phí xây dựng và vận hành của doanh nghiệp.