›

Giáo trình Tin học trong quản lý xây dựng - Chương 8: Quy hoạch động

pdf 31 trang huongle 1760
Download
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Tin học trong quản lý xây dựng - Chương 8: Quy hoạch động", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfgiao_trinh_tin_hoc_trong_quan_ly_xay_dung_chuong_8_quy_hoach.pdf

Nội dung text: Giáo trình Tin học trong quản lý xây dựng - Chương 8: Quy hoạch động

  1. Chương 8QhQuy hoạch động
  2. Chương 8 Quy hoạch động • Giớithii thiệu • Bài toán tìm đường đi ngắn nhất • Bài toán về sứcchc chở hàng • Bài toán về sản xuất và tồn trữ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  3. Chương 8. Quy hoạch động GIỚI THIỆU ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  4. Quy ho ạch động là gì? • Quy ho ạch động là mộtpht phương pháp định lượng gồm nhiều quyết định tuần tự nối tiếp nhau theo không gian hay thời gian. Phương pháp này do Richard Bellman đề ra vào năm 1957. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  5. Đặc điểm của quy hoạch động • Phương pháp quy hoạch động khắc phục được những nhược điểm của phương pháp quy hoạch tuyến tính là: –Hàm mục tiêu và các ràng buộc không yêu cầu là hàm tuyến tính – Bài toán có thể chia ra làm nhiều bài toán nhỏ tương ứng với nhiều giai đoạn (li)(multistage) và mỗiiii giai đoạn có một lời giải tối ưu ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  6. Đặc điểm của quy hoạch động - “ What title, what name could I choose? In the first place, I was interested in planning, in decision making,inthinking.Butthinking is not a good word for various reasons. I decided therefore to use the word, ‘programing.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying –I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic,inthe classical ppyhysical sense.” BELLMAN ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  7. Ba bước để giải bài toán quy hoạch động: • Chia bài toán ban đầu thành những bài toán nhỏ hơn, mỗi bài toán tương đương với một giai đoạn • Xem xét t ấttc cả các điềuuki kiệnvàcácn và các trạng thái ở giai đoạn cuối tìm lời giải tối ưu bắt đầu từ giai đoạn cuối • Giải bài to án bằng phương pháp ngược dòng đi từ giai đoạn cuối trở về giai đoạn đầu tiên. Giai đoạn cuối cùng ký hiệu là 1. Xác địnhhl lờiii giải tối ưu ở giiiai đoạn n dựa vào lời giải tối ưu ở giai đoạn tiếpp( theo (n-1). Lời giải của bài toán được xác định khi giai đoạn đầu tiên đã đượ©2010 củac Đỗ giThị Xuânải Lanxong. , GVC. Ths.
  8. Bài toán đường đi ngắn nhất Ví dụ 8.1 Mỗi ngày công ty xây dựng Kiến An cần phải vận chuyển vữa bê tông tươi từ nhà m áy sản xuất vữa bê t ông t hương phẩm Cửu Long đến công trường xây dựng nhà thi đấu Hoàn Hảo. Hãy tìm đường đi ngắn nhất từ nhà máy sản xuất vữa bê tông Cửu Long (nút 1) đến côtông trường ((út7)Snút 7). Sơ đồ mạng lưới đường với chiều dài các nhánh đường như ttorong hình ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  9. Bài toán đường đi ngắn nhất 10 2 5 4 km 14 12 5 1 3 7 2 4 6 2 10 4 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  10. Bài toán đường đi ngắn nhất Gọi • f(n,s): khoảng cách ngắn nhất hay chi phí vận chuyển thấp nhất khi di chuyển từ nút s đến nút cuối cùng ở giai đoạn n • c(s,j): khoảng cách hay chi phí vận chuyển từ nút s đến nút j • d(n,s): các quyết định ở giai đoạnn(cácn n (các nút sẽ đi qua tư nút xuất phát s) • s: trạng thái, tương ứng với nút xuất phát trong giai đoạnnn n f(n,s) = min [C(s,j) + f(n-1,j)] xét tất cả các nhánh đường xuất phát từ nút s ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  11. Bài toán đường đi ngắn nhất 10 2 5 4 km 14 12 5 1 3 7 2 4 6 2 10 4 6 giai đoạn 3 giai đoạn 2 giai đoạn 1 Bài toán này có 3 giai đoạn ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  12. Bài toán đường đi ngắn nhất Bài toán này có 3 giai đoạn: • Giai đoạn 3 có một trạng thái (nút xuất pp)hát là nút 1) • Giai đoạn 2 có ba trạng thái (nút xuất phát là nút 2 ,,),3,4) • Giai đoạn 1 có hai trạng thái (nút xuất phát là nút 5,6). ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  13. Bài toán đường đi ngắn nhất Lờigii giải bài toán tìm đường đingi ngắnnhn nhất – giai đoạn 1 Trạng thái f(1,s) d(1,s) 5147 627 10 2 5 4 km 14 12 5 1 3 7 2 4 6 2 10 4 6 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  14. Bài toán đường đi ngắn nhất Lờigii giải bài toán tìm đường đingi ngắnnhn nhất – giai đoạn 2 Trạng QQyuyết định f(2,,)s) d(2,,)s) thái D(2,s) nút 5 nút 6 4 4 +14 10+2 12 6 3 12 +14 6 +2 8 6 2 10 +14 24 5 10 2 5 4 km 14 12 5 1 3 7 2 4 6 2 10 ©20104 của Đỗ Thị Xuân Lan , GVC.6 Ths.
  15. Bài toán đường đi ngắn nhất Lờigii giải bài toán tìm đường đingi ngắnnhn nhất – giai đoạn 3 Trạng thái Quyết định D(3,s) f(3,s) d(3,s) nút 4 nút 3 nút 2 1 25+12 +8 4 +24 13 3 Vậy lộ trình ngắn nhất đi từ nút 1 đến nút 7 là 1-3-6-7 với chiều dài là 13 km. 10 2 5 4 km 14 12 5 1 3 7 2 4 6 2 10 ©20104 của Đỗ Thị Xuân Lan , GVC.6 Ths.
  16. Bài toán tận dụng sức chứa Ví d ụ 8.2 Công ty xây lắp Xalaco dùng một xe tải có trọng tải 7 tấn để chở 3 loại cấu kiện nặng 1 tấn, 2 tấn, và 3 tấn. Tiền lời chở cấu kiện nặng 1 tấn là 200.000 đồng, 2 tấn là 500.000 đồng và 3t3 tấn là 800. 000 đồng. Nên c hở bao nhiêu chiếc mỗi loại để được tiền lời nhiềunhu nhất? ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  17. Bài toán tận dụng sức chứa Gọi: •n là số loại cấu kiện • j: cấukiu kiệnnth thứ j(j=1j (j =1÷n) • w(j) là trọng lượng một cấu kiện loại j • x(j) là số lượng cấukiu kiệnlon loại j nên chở • R(j,x(j)) là tiền lời chở x(j) cấu kiện loại j • g(j, w) là tiềnnl lời tích luỹ lớnnhn nhấtkhicht khi chở cấu kiện loại j, j-1, , 1 khi trọng tải của xe còn w. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  18. Bài toán tận dụng sức chứa • Không có trình tự về thời ggqyian ra quyết định nhưng có thể xem quyết định chở bao nhiêu cấu kiện loại j là một giai đoạnLn. Lờigii giảiti tối ưutu tương ứng vớigiái giá trị tiền lời lớn nhất trong điều kiện trọng tải của xe dành để chở cấu kiện j, j- 1, ,1 là w. Khi đã quyết định chở x(j) cấu kiện loại j thì trọng tải xe dành để chở cấukiu kiệnjn j-11ch1, ,1 chỉ còn là w- w(j)x(j). g(j,w ) = m ax [R (j,x(j)) + g(j-1,w, -w(j)x (j))] ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  19. Bài toán tận dụng sức chứa Giai đoạn 1: quyết định chở bao nhiêu cấu kiện 11t tấn Trạng thái g(j,w)) x(j) 000 121 2 4 2 363 4 8 4 5105 6 12 6 7147©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  20. Bài toán tận dụng sức chứa Giai đoạnn2: 2: quyết định chở bao nhiêu cấu kiện 2 tấn Trạng Quyết định (số lượng cấu g(j,w) x(j) thái kiện) 0123 0 0 0 0 1 0 +2 2 0 2 0 +4 5 5 1 3 0 +6 5 +2 7 1 4 0+8 5 +4 10 10 2 5 0+10 5 +610 +2 12 2 6 0+12 5 +8 10 +4 15 15 3 7 0+14©20105 c+10ủa Đỗ Thị Xuân10 Lan+6 , GVC. Ths.15+2 17 3
  21. Bài toán tận dụng sức chứa • Giai đoạn 3: quyết định chở bao nhiêu cấu kiện 3 tấn Trạng Quyết định (số lượng g(j,w) x(j) thái cấu kiện) 012 7 0+17 8 +10 16 +2 18 1 hay 2 Vậy nên chở một cấu kiện 3 tấn và hai cấu kiện 22t tấn hhhay chở hhiai cấu kiện 33t tấn và một cấu kiện 1 tấn để được tiền lời nhiều nhất ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  22. Bài toán kế hoạch sản xuất và tồn trữ • P(n): số lượng hàng được mua hay sản xuất trong thời đoạn n • D(n): Nhu cầu tiêu thụ hàng trong thời đoạn n • I(n-1): lượng hàng tồnntr trữ vào đầuthu thời đoạn (n-1) khi lượng hàng tồn trữ đầu thời đoạn n là I(n), I(n-1) = I(n) + P(n) – D (n) • S(n): chi phí chuẩn bị cho một đợt sản xuất/chi phí đặt hàng cho một lần nhập hàng ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  23. Bài toán kế hoạch sản xuất và tồn trữ • V(P(n),I(n)): chi phí sản xuất/mua sắm và tồn trữ hàng, chi phí này là hàm số củala lượng hàng hoá tồn trữ và sản xuất/mua sắm trong thời đoạn n • C(n,P(n),I(n)): chi phí tổng cộng của thời đoạn n = S(n) + V(P(n), I(n)) n ếu P(n)>0 = V(P(n),I(n)) nếu P(n)=0 •f((,)n,i): tổngpg chi phí mua sắm/sản xuất và tồn trữ từ thời đoạn 1 đến thời đoạn thứ n với mức tồn trữ đầu thời đoạn n là i f(n,i)=min{C(n , P(n), i+P(n)-D(n))+f(n-1i+P(n)1, i+P(n)- D(n))} ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  24. Bài toán kế hoạch sản xuất và tồn trữ Ví dụ 8.3 Công ty xây dựng AMC có nhu cầu sử dụng mỗithái tháng mộtbt bộ máláy lạnhth trung tâ m trong vòng 3 tháng tới. Mỗi đầu tháng cửa hàng điện lạnh Dilaco đều đến công ty AMC để chào hàng. Công ty AMC có thể đặtmuast mua số lượng máy lạnh theo yêu cầu của tháng đó. Do chi phí vận chuyển, Dilaco đề nghị sẽ giảm giá bán tùy theo số lượng máy đặt mua. Nh ưng nếu số máy đặt mua lớn hơn yêu cầu sử dụng trong tháng đó thì lại tốn kém chi phí bảo quản số máy dư chưa dùng đến. Biết rằng giá mua mộtbt bộ máy là 7. 200$, từ hhibai bộ trở lên thì ch ỉ phải trả thêm 7.000$ cho mỗi bộ mua thêm (vì chi phí cho một lần chuyên chở xem như là 200$), chi phí tồntrn trữ mộtbt bộ máy trong vòng một tháng là 150$. Vậy công ty nên đặt mua máy như©2010 thế c ủnàoa Đỗ Thị Xuânđể Lan gi , GVC.ảm Ths. tối đa chi phí.
  25. Bài toán kế hoạch sản xuất và tồn trữ • Bài toán chia làm ba thời đoạn(mn (mỗithi thời đoạn tương ứng 1 bài toán nhỏ ): - Thời đoạn1(nn 1(n= 1) tháng thứ 3 -Thời đoạn 2(n=2) tháng thứ 2 - Thời đoạn3(nn 3(n= 3) tháng thứ 1 Lời giải cho bài toán là lời giải bài toán ở thời đoạn 3(tágt3 (tháng thứ 1). ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  26.  Xét bài toán ở thời đoạn 1()(n=1) ((gtháng thứ 3): Gọi: - i: là mức tồn trữ ở đầu tháng thứ 3.(thời đoạn này i=0,1) - f(1,i) : là tổng chi phí mua sắmvàbm và bảo quản hàng từ giai đoạn cuối cùng đến giai đoạn thứ n với mức tồn trữ đầu giai đoạn n là i cũng là tổng chi p hí mua sắm vààb bảo quản ở tháng thứ 3 - P(1): số máy được mua trong tháng 3 (giai đoạn 1) ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  27. Bài toán kế hoạch sản xuất và tồn trữ • Giai đoạnn1: 1: xét s ố lượng máy còn tồn trữ đầu tháng thứ 3 Trạng thái Quyết định f(1, i) P(1) 0 1 0 - 7,2 727,2 1 1 0 - 0 0 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  28.  Xét bài toán ở Thời đoạn 2 (()n=1) ((gtháng thứ 2): Gọi: - i: là mức tồn trữ ở đầu tháng thứ 2 (thời đoạn này i=0,1, 2) - f(2,i) : là tổng chi phí mua sắmvàbm và bảo quản hàng từ thời đoạn cuối cùng đến thời đoạn thứ n với mức tồn trữ đầu thời đoạn n là i cũng là tổng chi p hí mua sắm vààb bảo quản hàng ở tháng thứ 3 và tháng thứ 2 - P(2): số máy được mua trong tháng 2 (thời đoạn 2) ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  29. Bài toán kế hoạch sản xuất và tồntrn trữ • Giai đoạn 2: xét số lượng máy còn tồn trữ đầu tháng thứ 2 Trạng Quyết định f(2,i) P(2) thái 01 2 0 - (7,2+0) +7,2 (14,2+0,15) + 0 14,35 2 1 (0+0) +7,2+(7,2+0,15) 0- 7,2 0 2 (0+0,15) + 0 - - 0,15 0 Trạng thái Quyết định f(1,i) P(1) 0 1 0 - 7,2 7,2 1 1 ©20100 của Đỗ Thị Xuân Lan- , GVC. Ths. 0 0
  30.  Xét bài toán ở Thời đoạn 3 (()n=3) ((gtháng thứ 1): Gọi: - i: là mứctc tồntrn trữ ở đầu tháng thứ 1.(thời đoạn này i=0) - f(3,i): là tổng chi phí mua sắm và bảo quản hàng từ thời đoạn cuốiùi cùng đến thời đoạn thứ n với mức tồn trữ đầu thời đoạn n là i, là tổng chi phí mua sắm và bảo quản ở tháng thứ 3, tháng thứ 2 v à tháng thứ 1 hàm mục tiêu của bài toán - P(3): số máy được mua trong tháng 1 (thời đoạn 3) ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  31. Bài toán kế hoạch sản xuất và tồntrn trữ • Giai đoạn 3: xét số lượng máy tồn trữ đầu tháng thứ 1 Trạng Quyết định f(3,i) P(3) thái 1 2 3 0 7,2 +14,35 (14,2+0,15)+7,2 (21,2+2x0,15)+0,15 21,55 1,2 Trạng Quyết định f(2,i) P(2) thái 0 12 0 - (7,2+0) +7,2 ((,14,2+0, ,)15) + 0 14,35 2 1 (0+0) +7,2(7,2+0,15) + 0 - 7,2 0 2 (0+0,15) + 0 - - 0,15 0 Vậy: Mua một máy vào tháng thứ 1 và 2 máy vào tháng thứ 2 hay mua 2 máy vào tháng©2010 cthủa Đứỗ Th 1ị Xuân và Lan m , GVC.ộ Ths.t máy vào tháng thứ 3