Giải bài toán cấp phát tài nguyên bằng phương pháp quy hoạch động. Giải quyết các vấn đề lập trình động thực tế khác nhau: Phân bổ nguồn lực tối ưu
Lập trình động (DP) là phương pháp tìm lời giải tối ưu trong các bài toán có cấu trúc nhiều bước (multi-stage).
Hãy trình bày công thức tổng quát của bài toán DP. Một quy trình được kiểm soát sẽ được xem xét (phân bổ vốn giữa các doanh nghiệp, sử dụng nguồn lực trong một số năm, v.v.). Kết quả của việc điều khiển là hệ thống (đối tượng điều khiển) được chuyển từ trạng thái ban đầu sang trạng thái 
. Giả sử rằng việc kiểm soát có thể được chia thành 
các bước. Ở mỗi bước, một trong nhiều biện pháp kiểm soát được chấp nhận sẽ được chọn 
, chuyển hệ thống sang một trong các trạng thái của tập hợp 
. Các phần tử của bộ 
Và 
được xác định từ các điều kiện của một nhiệm vụ cụ thể. Trình tự các trạng thái của hệ thống có thể được mô tả dưới dạng biểu đồ trạng thái như trong Hình 2. 3.1.
Mỗi bước của con đường N hiệu quả đạt được 
. Giả sử rằng hiệu ứng tổng thể là tổng của các hiệu ứng đạt được ở mỗi bước. Khi đó bài toán DP được phát biểu như sau: xác định mức kiểm soát chấp nhận được như vậy 
, chuyển hệ thống từ trạng thái 
ở một trạng thái 
, tại đó hàm mục tiêu 
lấy giá trị lớn nhất (nhỏ nhất), tức là
Việc giải các bài toán bằng phương pháp DP được thực hiện trên cơ sở nguyên tắc tối ưu do nhà khoa học người Mỹ R. Bellman đưa ra: bất kể trạng thái của hệ thống là kết quả của bất kỳ bước nào, ở bước tiếp theo cần phải chọn điều khiển sao cho kết hợp với điều khiển tối ưu ở tất cả các bước tiếp theo sẽ dẫn đến thắng lợi tối ưu ở tất cả các bước còn lại, kể cả bước này.
Hãy ký hiệu bằng 
giá trị tối ưu có điều kiện của hàm mục tiêu trong khoảng từ bước N cho đến cuối cùng 
-bao gồm bước thứ, với điều kiện là trước đó NỞ bước thứ 2, hệ thống ở một trong các trạng thái của tập hợp 
, và hơn thế nữa NỞ bước thứ, điều khiển như vậy đã được chọn từ tập hợp 
, cung cấp hàm mục tiêu với giá trị tối ưu có điều kiện, sau đó 
giá trị tối ưu có điều kiện của hàm mục tiêu trong khoảng từ ( N+1
) đến 
-bước thứ bao gồm.
Trong ký hiệu được chấp nhận, nguyên lý tối ưu Bellman có thể được viết dưới dạng toán học như sau
Đẳng thức (3.1) được gọi là phương trình hàm chính lập trình năng động. Cho mỗi nhiệm vụ cụ thể phương trình có dạng đặc biệt.
Quy trình tính toán của phương pháp DP được chia thành hai giai đoạn: tối ưu hóa có điều kiện và vô điều kiện.
Ở sân khấu có điều kiện tối ưu hóa theo phương trình hàm, các điều khiển tối ưu được xác định cho tất cả các trạng thái có thể có ở mỗi bước, bắt đầu từ bước cuối cùng.
Ở sân khấu tối ưu hóa vô điều kiện các bước được coi là bắt đầu từ bước đầu tiên. Kể từ trạng thái ban đầu 
đã biết, điều khiển tối ưu được chọn từ tập hợp 
. Đã chọn kiểm soát tối ưu
đưa hệ thống đến một trạng thái rất cụ thể 
. Vì trạng thái ban đầu 
được biết ở đầu bước thứ hai, có thể chọn điều khiển tối ưu ở bước thứ hai 
vân vân. Như vậy, một chuỗi các giải pháp tối ưu hóa vô điều kiện được kết nối với nhau được xây dựng.
3.1. Bài toán phân bổ nguồn lực tối ưu
Hãy để hiệp hội được phân bổ một lượng tài nguyên vật chất nhất định để tái thiết và hiện đại hóa sản xuất chính X. Có sẵn N giữa các doanh nghiệp cần phân phối tài nguyên này. Hãy ký hiệu bằng 
lợi nhuận mà việc phân bổ mang lại cho nền kinh tế quốc dân j-doanh nghiệp thứ 
các đơn vị tài nguyên Người ta giả định rằng tỷ suất lợi nhuận phụ thuộc vào cả lượng nguồn lực được phân bổ và doanh nghiệp. Hơn nữa, lợi nhuận doanh nghiệp nhận được được tính bằng cùng một đơn vị và tổng lợi nhuận của hiệp hội bao gồm lợi nhuận của từng doanh nghiệp. Cần tìm ra phương án phân bổ nguồn lực tối ưu giữa các doanh nghiệp, sao cho tổng lợi nhuận của hiệp hội là tối đa.
Nhiệm vụ hiện tại phải được coi là một nhiệm vụ gồm nhiều bước.
Ở sân khấu tối ưu hóa có điều kiện chúng ta sẽ xem xét hiệu quả của việc đầu tư vào một (ví dụ: doanh nghiệp thứ nhất), hai doanh nghiệp cùng nhau (thứ nhất và thứ hai), ba doanh nghiệp cùng nhau (thứ nhất, thứ hai và thứ ba), v.v., và cuối cùng là tất cả N doanh nghiệp với nhau. Nhiệm vụ là xác định giá trị lớn nhất của hàm 
miễn là 
.
Chúng ta hãy sử dụng quan hệ truy hồi Bellman (3.1), đối với bài toán này dẫn đến các phương trình hàm sau cho 
:
Đây là chức năng 
xác định lợi nhuận tối đa của doanh nghiệp đầu tiên khi phân bổ xđơn vị tài nguyên, chức năng 
xác định lợi nhuận tối đa của doanh nghiệp thứ nhất và thứ hai khi phân bổ chúng xđơn vị tài nguyên, chức năng 
xác định lợi nhuận tối đa của doanh nghiệp thứ nhất, thứ hai và thứ ba khi phân bổ chúng xđơn vị tài nguyên, v.v., và cuối cùng là hàm 
quyết định lợi nhuận tối đa của tất cả các doanh nghiệp cùng nhau khi phân bổ chúng x các đơn vị tài nguyên
Ở giai đoạn tối ưu hóa vô điều kiện, phương án phân bổ nguồn lực tối ưu giữa các doanh nghiệp được xác định.
Ví dụ 3.1.
Để tăng khối lượng sản xuất các sản phẩm có nhu cầu cao, số tiền 50 triệu rúp đã được phân bổ cho bốn doanh nghiệp của hiệp hội sản xuất. Mỗi doanh nghiệp có thể được phân bổ: 0, 10, 20, 30, 40 hoặc 50 triệu rúp. Đồng thời, mức tăng sản lượng sản xuất hàng năm của mỗi doanh nghiệp 
tùy thuộc vào mức đầu tư được biết và thể hiện trong bảng. 3.1.
Bảng 3.1
|
Khối lượng kinh phí được phân bổ x(triệu rúp) |
Sản lượng sản phẩm tăng hàng năm (triệu rúp), tùy thuộc vào khối lượng vốn được phân bổ |
|||
|
|
|
|
|
|
Tìm phương án phân bổ vốn tối ưu giữa các doanh nghiệp, đảm bảo sản lượng sản xuất hàng năm của liên hiệp sản xuất tăng tối đa.
Kế hoạch bài học
Kỷ luật học tập PHƯƠNG PHÁP VÀ MÔ HÌNH TOÁN TRONG KINH TẾ
Chủ đề bài học Giải các bài toán DP thực tế khác nhau bằng phương pháp toán học.
Mục tiêu bài học
Phát triển kỹ năng giải các bài toán quy hoạch động.
Phát triển chất lượng tư duy, sự chú ý và kỹ năng làm việc học tập của học sinh.
Rèn luyện tính kỷ luật và quyết tâm cho học sinh.
Thiết bị bài học Bài giảng của V.P. Agaltsov " Phương pháp toán học trong lập trình."
Trong các buổi học:
Thời gian tổ chức:
kiểm tra người vắng mặt, điền vào sổ.
Cập nhật kiến thức tham khảo: câu trả lời cho câu hỏi bảo mật
Những nhiệm vụ nào được gọi là nhiều bước?
Công cụ toán học nào được sử dụng để giải các bài toán có nhiều bước?
Điều khiển tối ưu u* là gì?
Thuật toán cho phương pháp xấp xỉ liên tiếp hai vòng tròn là gì?
Cho ví dụ về các bài toán phân bổ nguồn lực tối ưu.
Học tài liệu mới:
Các bài toán lập trình động cổ điển
Bài toán về dãy con chung dài nhất: Cho hai dãy con cần tìm dãy con chung dài nhất.
Bài toán tìm dãy con tăng dài nhất: Cho một dãy con cần tìm dãy con tăng dài nhất.
Bài toán khoảng cách biên tập (khoảng cách Levenshtein): cho hai chuỗi, bạn cần tìm số lần xóa, thay thế và thêm ký tự tối thiểu để biến chuỗi này thành chuỗi khác.
Bài toán tính số Fibonacci
Bài toán về thứ tự nhân ma trận: các 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.
Vấn đề lựa chọn quỹ đạo
Vấn đề ra quyết định tuần tự
Vấn đề sử dụng lao động
Vấn đề quản lý hàng tồn kho
Bài toán về chiếc ba lô: từ một tập hợp các đồ vật không giới hạn với các thuộc tính “giá thành” và “trọng lượng”, cần phải chọn một số lượng đồ vật nhất định sao cho đạt được tổng chi phí tối đa với tổng trọng lượng giới hạn.
Thuật toán Floyd-Warshall: tìm khoảng cách ngắn nhất giữa tất cả các đỉnh của đồ thị có hướng có trọng số.
Thuật toán Bellman-Ford: tìm đường đi ngắn nhất trong đồ thị có trọng số giữa hai đỉnh cho trước.
Tập đỉnh độc lập lớn nhất của một cây: cho một cây, tìm tập đỉnh lớn nhất sao cho không có hai đỉnh nào nối nhau bằng một cạnh.
Ví dụ: Phân bổ nguồn lực tối ưu
Vốn 40 triệu rúp. nhà đầu tư phải đầu tư vào bốn dự án đầu tư để đạt được thu nhập tối đa. Lợi nhuận của các dự án được đưa ra trong bảng (đầu tư là bội số của 8 triệu rúp)
bạn
Lợi nhuận từ việc thực hiện
f4(u)
f3(u)
f2(u)
f1(u)
55
39
120
115
10 0
120
135
134
14 0
145
158
147
Giải pháp:
Đây là một vấn đề lập trình động. Giải pháp bao gồm hai giai đoạn. Ở giai đoạn đầu tiên (từ đầu đến cuối) chúng ta tìm kiếm giải pháp tối ưu có điều kiện, ở giai đoạn thứ hai (từ đầu đến cuối) chúng ta tìm kiếm giải pháp tối ưu cho bài toán.
Giai đoạn 1.
Chúng tôi phân bổ vốn giữa bốn dự án và tính toán lợi nhuận nhận được L (Tôi ), Tôi = 8,16,24,32,40.
1 bước: Vốn được đầu tư vào dự án thứ tư.
L(8)= 55
L(16)=58
L(24)=90
L(32)=100
L(40)=140
Bước 2: Nguồn vốn được đầu tư vào dự án thứ tư và thứ ba.
bạn
Lợi nhuận từ việc thực hiện
1 bước
f3(u)
55
39
10 0
120
14 0
145
Bước 3: Vốn được đầu tư vào các dự án thứ tư, thứ ba (bước 2) và thứ hai.
bạn
Lợi nhuận từ việc thực hiện
Bước 2
f 2(u)
94
108
120
135
135
175
158
175
134
214
147
Giai đoạn 2:
Ở bước thứ tư, chúng tôi chọn giá trị lợi nhuận tối đa thu được L (40) = 214.
Và quay trở lại thứ tự ngược lại Từ bảng này sang bảng khác (từ 4 bước đến 1), chúng tôi chọn các giá trị thu nhập sao cho thu được giá trị 214.
Thu nhập tối đa 214 triệu rúp. từ số tiền đầu tư có thể được nhận bằng cách phân bổ số tiền sau:
1 dự án – 0 triệu rúp.
Dự án số 2 – 24 triệu rúp.
Dự án thứ 3 – 8 triệu rúp.
Dự án số 4 – 8 triệu rúp.
Tổng hợp vật liệu mới:
5. Tóm tắt bài học: kết luận, đánh giá, bài tập về nhà:
(2) khoản 5.1
Ср12: hình thành và đồng hóa nội dung tài liệu lý thuyết
Chư ky của giao viên
Phương pháp lập trình động cho phép bạn giải thành công nhiều mục tiêu 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 loại chức năng nào đó. 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 điều khiển S trong trong trường hợp này- quỹ hoặc nguồn lực đượ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 là đầ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 toàn bộ 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 hoàn trả tối ưu có điều kiện trên hai bước cuối cùng x: (đã được tối ưu hóa). Nếu chúng ta phân bổ vốn cho doanh nghiệp ở bước này thì sẽ còn lại cho bước cuối cùng, số tiền thắng của chúng ta ở 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ụ bằng 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 số tiề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ể “làm chủ” 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. các 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à tìm 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: . Các điều khiển tối ưu ở tất cả các bước được đánh dấu bằng 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.
Gửi công việc tốt của bạn trong cơ sở kiến thức rất đơn giản. Sử dụng mẫu dưới đây
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ổ lượng đ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 không phải là giải pháp duy nhất.Do đó, ở trạng thái S 1 = 3, các đ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 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 phương pháp doanh nghiệp lập trình 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 bài toán tối ưu hóa quy trình sản xuất. Ứ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. Xây dựng mô hình toán học về phân bổ nguồn lực của công ty. Phân tích độ nhạy 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.
Hướng dẫn. Chọn số lượng doanh nghiệp.
Ví dụ số 1. Hoạt động của hai doanh nghiệp được lên kế hoạch trong n năm. Nguồn lực ban đầu bằng s0. Vốn x đầu tư vào doanh nghiệp thứ nhất đầu năm mang lại lợi nhuận f1(x) vào cuối năm và được hoàn trả số tiền g1(x). Vốn y đầu tư vào doanh nghiệp thứ 2 đầu năm sinh ra lãi f2(y) vào cuối năm và được hoàn trả số tiền g2(y). Vào cuối năm, số tiền hoàn lại sẽ được phân phối lại giữa các ngành. Xác định phương án phân bổ quỹ tối ưu và tìm ra lợi nhuận tối đa.
Hãy giải bài toán bằng phương pháp quy hoạch động. Kiểm soát hoạt động Quy trình sản xuất Hãy chia nó thành các giai đoạn. Trên mỗi người trong số họ, chúng tôi sẽ chọn điều khiển để nó dẫn đến tiền thắng cả trên ở giai đoạn này, và trên tất cả những cái tiếp theo cho đến khi kết thúc thao tác. Đây là nguyên lý tối ưu, do nhà toán học người Mỹ A. Bellman xây dựng.
Hãy chia toàn bộ thời kỳ thành ba giai đoạn theo năm và đánh số chúng bắt đầu từ giai đoạn đầu tiên.
Hãy ký hiệu bằng xk Và ồ số vốn được phân bổ cho mỗi doanh nghiệp ở giai đoạn thứ k và sau đó xk + ồ = một k- tổng số tiền ở giai đoạn này. Sau đó doanh nghiệp đầu tiên đưa vào 3 ở giai đoạn này xk, và số thứ hai là 4 ồđơn vị thu nhập. Tổng thu nhập ở giai đoạn thứ k 3 xk + 4ồ.
Hãy ký hiệu bằng f k ( Một k) là thu nhập tối đa mà ngành nhận được từ cả hai doanh nghiệp thứ k và tất cả các doanh nghiệp tiếp theo. Khi đó phương trình hàm phản ánh nguyên lý tối ưu Bellman có dạng:
f k (ak)=tối đa(3x k + 4y k +f k +1 (a k +1)).(1)
Bởi vì x k + y k = a k , thìy k = a k - x k và3x k + 4y k = 3x k + 4(a k - x k) = - x k + 4a k . Đó là lý do tại saof k (a k) = max(-x k + 4a k + f k+1 (ak+1)). (2)
0 x k a k
Ngoài ra, ak là vốn được phân bổ cho doanh nghiệp ở giai đoạn thứ k và được xác định bằng số dư vốn nhận được ở giai đoạn (k-1) trước đó. Vì vậy, tùy theo điều kiện của bài toán mà điều khiển tối ưu ở từng giai đoạn
ak = 0,5xk -1 + 0,2y k -1 = 0,5xk -1 +0.2(a k -1 -x k -1) = 0,3xk -1 +0.2a k -1 . (3)
TÔI. Điều kiện tối ưu hóa
Chúng tôi bắt đầu lập kế hoạch từ giai đoạn thứ ba cuối cùng
Tại k=
3
chúng tôi có được từ (2)
f 3 (a 3) = tối đa (- x 3 + 4a 3 + f 4 (a 4))
0 x 3 a 3
Vì không có giai đoạn thứ tư nên f 4 (a 4)=0 Và
f 3 (a 3) = tối đa (- x 3 + 4a 3 )=4a 3
0 x 3 a 3
(biểu thức cực đại ( -
x 3 + 4số 3) sẽ có mặt tại x 3 = 0)).
Vì vậy đối với cái thứ ba giai đoạn cuối chúng ta có: f 3 (a 3) = 4một 3,x 3 = 0,y 3 =một 3 -x 3 =một 3,
Ở đâu Một 3 = 0,3x 2 + 0,2một 2 , theo công thức (3).
Tại k = 2 từ (2) và (3) chúng ta có được:
f(a 2) = max (-x 2 + 4a 2 + f 3 (a 3))=
0 x a 2
=tối đa (-x 2 + 4a 2 + 4a 3 )= tối đa (-x 2 + 4a 2 + 4( 0,3x 2 + 0,2a 2)) tối đa(0,2x 2 + 4,8a 2 ) 5a
0 x a 2
vì cực đại của biểu thức ( 0,2
x 2 + 4,8một 2) sẽ có mặt tại x 2 =một 2.
Khi đó ở giai đoạn thứ hai, chúng ta có: f 2 (a 2) = 5a 2, x 2 = a 2, y 2 = a 2 x 2 = 0, trong khi
a 2 = 0,3x 1 + 0,2a 1 có tính đến (3).
Tại k = 1 xét đến (2) và (3) ta có:
f 1 (a 1) = tối đa (-x 1 + 4a 1 + f 2 (a 2))=
0 x a 1
= tối đa (-x 1 + 4a 1 + 5a 2 )= tối đa (-x 1 + 4a 2 + 5(0,3x 1 + 0,2a 2))= tối đa (0,5x 1 + 5a 1 )=5, 5a 1
0 x a 1
Tại x 1 = a 1.
Vì vậy, đối với giai đoạn đầu f 1 (a 1) = 5,5một 1,x 1 =một 1,y 1 = 0.
Quá trình này đã kết thúc. Ở giai đoạn đầu tiên, tổng số tiền phân phối đã được biết - một 1= 900 đơn vị Khi đó thu nhập tối đa mà cả hai doanh nghiệp nhận được trong ba năm sẽ là f 1 (a 1) = 5,5*900 = 4950 den. các đơn vị
II. Tối ưu hóa vô điều kiện
Hãy cùng tìm hiểu xem cách quản lý tối ưu quá trình phân bổ vốn giữa doanh nghiệp thứ nhất và doanh nghiệp thứ hai là gì để đạt được thu nhập tối đa với số tiền 4950 den. các đơn vị
Năm thứ nhất. Bởi vì x 1 =một 1 Và ,
y 1 = 0, sau đó tất cả số tiền là 900 den. các đơn vị được trao cho doanh nghiệp đầu tiên.
năm thứ 2. Kinh phí được phân bổ a 2 = 0,3x 1 + 0,2a 1 = 0,5 một 1=450 đơn vị, x 2 = a 2 , y 2 = 0.
Tất cả đều được chuyển giao cho doanh nghiệp đầu tiên.
Năm thứ ba. Kinh phí được phân bổ Một 3 = 0,3x 2 + 0,2một 2 = 0,5 một 2= 225 đơn vị, x 3 = 0,y 3 =số 3. Tất cả đều được chuyển giao cho doanh nghiệp thứ hai.
Chúng tôi trình bày kết quả của giải pháp dưới dạng bảng.
| Giai đoạn | Cơ sở | Doanh nghiệp số 1 | Doanh nghiệp số 2 | còn lại | Thu nhập |
| 1 | 900 | 900 | 0 | 450 | 2700 |
| 2 | 450 | 450 | 0 | 225 | 1350 |
| 3 | 225 | 0 | 225 | 45 | 900 |
| 4950 |
Ví dụ số 2. Phân phối vốn theo từng giai đoạn tối ưu giữa các doanh nghiệp trong giai đoạn lập kế hoạch.
Ban quản lý công ty có thỏa thuận hợp tác với ba doanh nghiệp nhỏ, đã phân bổ vốn lưu động cho họ với số tiền 100.000 USD cho giai đoạn kế hoạch hàng năm. Đối với mỗi doanh nghiệp, chức năng thu nhập hàng quý và cân đối vốn lưu động hàng quý được xác định tùy thuộc vào số tiền x phân bổ trong quý. Vào đầu quý, số tiền này được phân phối đầy đủ giữa ba doanh nghiệp (thu nhập được tính từ các quỹ đầu tư này) và vào cuối quý, số tiền còn lại được ban quản lý công ty tích lũy và lại được phân bổ đầy đủ giữa các doanh nghiệp. doanh nghiệp.
Lập kế hoạch phân bổ vốn hàng quý trong năm (4 quý), cho phép bạn đạt được tổng thu nhập tối đa trong năm.
f 1 (x)=1,2x, f 2 (x)=1,5x, f 3 (x)=2x; g 1 (x)=0,7x, g 2 (x)=0,6x, g 3 (x)=0,1x
