›
›

Bài giảng Tin học trong quản lý xây dựng - Chương 4: Quy hoạch tuyến tính số nguyên - Đỗ Thị Xuân Lan

pdf 45 trang ngocly 3320
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Tin học trong quản lý xây dựng - Chương 4: Quy hoạch tuyến tính số nguyên - Đỗ Thị Xuân Lan", để 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:

  • pdfbai_giang_tin_hoc_trong_quan_ly_xay_dung_chuong_4_quy_hoach.pdf

Nội dung text: Bài giảng Tin học trong quản lý xây dựng - Chương 4: Quy hoạch tuyến tính số nguyên - Đỗ Thị Xuân Lan

  1. Chương 4 QhQuy hoạch tuyếntínhsn tính số nguyên Tin học trong quản lý
  2. Chương 4Quy hoạch tuyến tính số nguyên • Quy ho ạch tuyến tính thuần nguyên • Quy hoạch tuyến tính số nguyên hỗn hợp • Quy hoạch tuyến tính nhị nguyên • Bài toán pha cắtvt vậttt tư • Bài toán rút ngắn thời gian đường găng có x ét đến yếuut tố ccphi phí ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  3. Chương 4 Quy ho ạch tuyến tính số nguyên MÔ HÌNH QUY HOẠCH TUY ẾN TÍNH THUẦN NGUYÊN ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  4. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN Ví dụ 414.1: Để phát triển sản xuất,chủ cơ cở gia công cốp pha dự định mua thêm mộtsố máy dậpvàmáytiện.Ước tính mỗi máy dập mỗi ngày cho 70USD tiềnlời và máy tiện là 60USD tiền lời.Ông chỉ có 30.000USD và diện tích xưởng có 12 m2. Biết : + Máy dậpchiếm 2m2 , giá 6. 000 USD + Máy tiệnchiếm 3m2, giá 5.000 USD Vậy số lượng máy mỗi loại nên mua bao nhiêu thì tiềnlờinhất. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  5. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN  Tóm tắt bài toán : Khả năng Tài nguyên Máy dập(x1) Máy tiện(x2) đáp ứng Tiền lời 70USD 60USD Diện tích 2 3 12 Giá 6.000USD 5.000USD 30.000 x1 x2 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  6. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN Mô hình toán: Hàm mục tiêu: Z = 70x1 +60x2 USD max Các ràng buộc: 6x1 +5x+ 5x2 ≤ 30 (1. 000USD) 2 2x1 + 3x2 ≤ 12 (m ) Điều kiện biên: x1 ≥ 0, x2 ≥ 0 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  7. X2 Giải bài to án quy hoạchth tuyến tính số nguyên bằng phương 6 pppháp đồ thị 5 6X1 + 5X2 =30 nn ệ 4 Máy ti 3 Lời giải tối ưu X1 =375X3.75 ,X2 =151.5 D(4,2) lợi nhuận = 352.5 USD 2 1 Z=340 E(4,1) 2X1 + 3X2 =12 B(5,0) Z=350 X1 1 2 3 4 5 6 Máy dập ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  8. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN Mô hình toán: Hàm mục tiêu: Z = 70x 1 +60x2 USD max Các ràng buộc: 6x1 +5x+ 5x2 ≤ 30 (1 . 000USD) 2 2x1 + 3x2 ≤ 12 (m ) Điều kiện biên: x1 ≥ 0, x2 ≥ 0 bổ sung x1 , x2 nguyên ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  9. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN + Lợi nhuận =350 Lời giải tối ưu của bài toán quy hoạch tuyến tíhính số nguyên + Lợi nhuận =340 Lời giải khi làm tròn nghiệm tối ưu của bài toán quy hoạch tuyến tính ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  10. Chương 4 Quy ho ạch tuyến tính số nguyên MÔ HÌNH QUY HO ẠCH TUYẾN TÍNH NHỊ NGUYÊN ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  11. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH NHỊ NGUYÊN Bài toán : Chính quyềnthn thị trấnTn Tương Lai đang xem xét sẽ xây dựng những công trình thể thao trong bốn công trình được đề nghị sau đây : Công trình thể Số người kỳ Kinh phí xây Diệntích mặt thao vọng s ử dụng dựng (tri ệu bằng c ầnnthi thiết hàng ngày đồng ) (1000m2 ) Hồ bơi 300 3500 4 Sân quần vợt 90 1000 2 Sân điền kinh 400 2500 7 Nhà thi đấu mini 150 9000 3 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  12. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH NHỊ NGUYÊN Tổng mặtbằng dành cho các công trình không được vượt quá 12000 m2.Tổng kinh phí để xây dựng chỉ có 12 tỷđồng. Thị trấn chỉ có mộtkhuđấtcóđịathế thích hợp để có thểđểxây dựng hoặchồ bơihoặcsân quầnvợt. Nên xây dựng công trình nào để người dân trong thị trấncóthể sử dụng được nhiềunhất? ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  13. Gọi : x1 là c họn phương ááâdn xây dựng hồ bơi . x2 là c họn phương ááâdn xây dựng sân quần vợt . x3 là chọnnph phương án xây dựng sân điền kinh . x4 là chọnphn phương án xây dựng nhà thi đấu – Nếuxu xi = 0 thì ph ương án i không được chọn ngược lại xi = 1 thì phương án i được chọn . ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  14. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH NHỊ NGUYÊN Mô hình bài toán : * Hàm mục tiêu : Z = 300 x1 + 90x2 + 400x3 + 150x4 max * Các ràng buộc : - Ràng buộc về kinh phí : 3500x1 + 1000x2 + 2500x3 + 9000x4 ≤ 12000 - Ràng buộc về địa điểm xây dựng : x1 +x+ x2 ≤ 1 - Ràng buộc về diện tích đất : 4x1 + 2x2 + 7x3 + 3x4 ≤ 12 * Điều kiện biên : x1 , x2 , x3 , x4 0,1 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  15. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH NHỊ NGUYÊN Lời giải tối ưu của bài toán là : x1 = 1 ( xây dựng hồ bơi) x2 = 0 ( không xây dựng sân quầnvn vợt)t ) x3 = 1 ( xây dựng sân điền kinh ) x4 = 0 ( không xây dựng nhà thi đấu mini) Z = 700 người . ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  16. Chương 4 Quy ho ạch tuyến tính số nguyên MÔ HÌNH QUY HOẠCH TUY ẾN TÍNH SỐ NGUYÊN HỖN HỢP ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  17. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH SỐ NGUYÊN HỖNNH HỢP Ví dụ 4.2: Ông Giàu có tiềnvốn là 250.000USD định đầutư theo 3 phương án sau: 1.Muaxeôtôchở khách, mỗixegiá 50.000USD, cuối năm cho tiền lời 5.000USD. 2.Mua đấtvườn, mỗihađất giá 12.000USD, cuốinămchotiềnlời 1.500USD. 3.Mua tínphiếu kho bạc, mỗi tínphiếugiá 8.000USD,cuốinăm lãnh tiềnlời 1.000USD. Vậy ông Giàu nên đầutư vào dự án như thế nào để tiềnlờinhiềunhất? Biếtrằng ông Giàu chỉ nên mua tối đa4xeôtôđể đảmbảocókế hoạch sử dụng thường xuyên và khu đấtông Giàu định mua chỉ còn 30ha. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  18. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH SỐ NGUYÊN HỖNNH HỢP •Gọi : x1 là số xe ô tô sẽ mua x2 là số ha đất sẽ mua x3 là số tín phiếusẽ mua • Mô hình toán: –Hàmmục tiêu: (để có tiềnlờimỗinăm nhiềunhất) Z = 5.000x1 + 1.500x2 + 1000x3 (USD) max – Các ràng buộc: 50.000x1 + 12.000x2 + 8.000x3 ≤ 250.000 (USD) x1 ≤ 4 x2 ≤ 30 – Điều kiện biên: x1 ≥ 0 , nguyên; ©2010x2 ≥ củ a0 Đ ỗ;Th xị Xuân3 ≥ Lan 0 , GVC., nguyên Ths.
  19. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH SỐ NGUYÊN HỖNNH HỢP Lờigiảitối ưucủa bài toán là: –x1 = 0 xe ô tô sẽ mua –x2 = 7,5 ha đất sẽ mua –x3 = 20 tín phiếusẽ mua –Tiền lời thu được hàng năm Z = 31.250 USD Lời giải tối ưu thứ hai của bài toán là: –x1 = 0 xe ô tô sẽ mua –x2 = 20,83 ha đất sẽ mua –x3 = 0 tín phiếusẽ mua –Tiền lời thu được hàng năm Z = 31.250©2010 cUSDủa Đỗ Thị Xuân Lan , GVC. Ths.
  20. Chương 4 Quy ho ạch tuyến tính số nguyên BÀI TOÁN PHA C ẮTTV VẬT TƯ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  21. BÀI TOÁN PHA CẮT VẬT TƯ Ví dụ 4.4 : Có một số thanh cốt thép Ø16 dài 11,7m. Để thi công lắp đặt cốt thép dầm, cột cho một tầng của một tòa nhà bê tông cốt thép thì cần phải có 210 đoạn Ø 16 dài 2,1m; 161 đoạn Ø 16 dài 2, 9m; 176 đoạn Ø 16 dài 3,2m; 48 đoạn Ø 16 dài 4,2m. Vậy nên cắt cốt thép như thế nào để tốn ít thanh nguyên nhất ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  22. BÀI TOÁN PHA CẮT VẬT TƯ  Đặt tên biến: Gọi x1 là số thanh nguyên pha cắt theo PA 1 Gọi xi là số thanh nguyên pha cắt theo PA i Các phương án pha cắt từ thanh nguyên 11,7m được trình bày trong bảng sau : ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  23. Số lượng các đoạn Các phương án Mẫuthừa (m) 2.1m 2.9m 3.2m 4.2m x1 0012 0.1 x2 0 1 0 2 040.4 x3 1002 1.2 x4 0021 1.1 x5 0 1 1 1 141.4 x6 0201 1.7 x7 2101 0.4 x8 3001 1.2 x9 1030 0 x10 1120 0.3 x11 2020 1.1 x12 1210 0.6 x13 2110 1.4 x14 4010 0.1 x15 0400 0.1 x16 1300 0.9 x17 2200 1.7 x18 4100 0.4 x19 5000 1.2
  24. BÀI TOÁN PHA CẮT VẬT TƯ  Đặt tên biến: Gọi x1 là số thanh nguyên pha cắt theo phương án 1 Gọi xi là số thanh nguyên pha cắt theo phương án i  Mô hình toán : Hàm mục tiêu Zxmin  i i 119 Điều kiện biên: xi ≥ 0ê0, nguyên ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  25. BÀI TOÁN PHA CẮT VẬT TƯ Điều kiện ràng buộc: Có đủ 210 đoạn dài 2.1m 0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 0x6 + 2x7 + 3x8 + Có đủ 161 1x9 + 1x10 + 2x11 + 1x12 + 2x13 + 4x14 + 0x15 + 1x + 2x + 4x + 5x ≥ 210 đoạn dài 16 17 18 19 2.9m 0x1 + 1x2 + 0x3 + 0x4 + 1x5 + 2x6 + 1x7 + 0x8 + 0x9 Có đủ 176 +1+ 1x10 +0+ 0x11 +2+ 2x12 +1+ 1x13 +0+ 0x14 +4+ 4x15 +3+ 3x16 + đoạn dài 2x17 + 1x18 + 0x19 ≥ 161 3.2m 1x1 + 0x2 + 0x3 + 2x4 + 1x5 + 0x6 + 0x7 + 0x8 + 3x9 + 2x10 + 2x + 1x + 1x + 1x + 0x + 0x + 0x + 0x + 0x Có đủ 48 11 12 13 14 15 16 17 18 19 ≥ 176 đoạn dài 4.2m 2x1 + 2x2 + 2x3 + 1x4 + 1x5 + 1x6 + 1x7 + 1x8 + 0x9 + 0x10 + 0x11 + 0x + 0x + 0x + 0x + 0x + 0x + 0x + 0x ≥ 48 12 13 14©2010 của15 Đỗ Thị Xuân16 Lan , GVC.17 Ths. 18 19
  26. BÀI TOÁN PHA CẮT VẬT TƯ  Lời giải tối ưu của bài toán: ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  27. BÀI TOÁN PHA CẮT VẬT TƯ Ví dụ 4.5 : Có hai loại thanh cốt thép dài 6m và 8m. Cần phải gia công 100 đoạn dài 2,4m và 150 đoạn dài 2,8m. Nên cắt cốt thép như thế nào để cho tiết kiệm nhất ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  28. BÀI TOÁN PHA CẮT VẬT TƯ  Đặt tên biến: Gọi x1 là số than h nguy ên p ha cắttht theo PA1 Gọi xi là số thanh nguyên pha cắt theo PA i Các phương án pha cắt từ thanh nguyên 6m : ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  29. BÀI TOÁN PHA CẮT VẬT TƯ  Đặt tên biến: Gọi x1 là số than h nguy ên p ha cắttht theo PA1 Gọi xi là số thanh nguyên pha cắt theo PA i Các phương án pha cắt từ thanh nguyên 8m : ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  30. BÀI TOÁN PHA CẮT VẬT TƯ Hàm mục tiêu Để tổng chiều dài các thanh nguyên được sử dụng ít nhất (x1 + x2 + x3)6 + (x4 + x5 + x6)8 min 4x1 + 8x2 + 12x3 + 0x4 + 4x5 + 8x6 min Để tổng chiều dài các mẫu thừa là ít nhất Điều kiện biên : x©2010i ≥ 0, của Đnguyênỗ Thị Xuân Lan , GVC. Ths.
  31. BÀI TOÁN PHA CẮT VẬT TƯ Điều kiện ràng buộc: 0x1 + 1x2 + 2x3 + 1x4 + 2x5 + 3x6 = 100 (100 đoạn dài 2,4m) 2x1 + 1x2 + 0x3 + 2x4 + 1x5 + 0x6 = 150 (150 đoạn dài 2,8m) ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  32. BÀI TOÁN PHA CẮT VẬT TƯ  Lời giải tối ưu của bài toán: ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  33. Chương 4 Quy ho ạch tuyến tính số nguyên RÚT NGẮNNTH THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  34. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Ví d ụ 446.6 : Rút ngắnthời gian củaDA xây dựng nhà công nghiệpcủa công ty ABC. -ThờigianthựchiệnDAlà12 tuần - Chi phí rút ngắnthấpnhất ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  35. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Sơ đồ mạng: F3 A2 C2 E4 BĐ H2 G5 B3 D4 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  36. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Thời gian ( tuần ) Chi phí ( ngàn đồng ) Thời gian Chi phí Công Bình Bình rút ngắn rút ngắn việc Rút ngắn Rút ngắn thường thường được đơn vị A 2122,000 23,000 1 1,000 B 3 1 30,000 34,000 2 2,000 C 2 1 26,000 27,000 1 1,000 D 4 3 48,000 49,000 1 1,000 E 4 2 56,000 58,000 2 1,000 F 3 2 30,000 30,500 1 500 G 5 2 80,000 86,000 3 2,000 H 2 1 16,000 19,000 1 3,000 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  37. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Đặt tên biến Gọi X là thời điểm kết sớm (EF) của một công việc XA = EF của công việc A XB =EFc= EF của công vi ệccB B . XH = EF của công việc H Gọi Y là thời gian rút ngắn (tuần) của từng công việc YA = thời gggian rút ngắn của công việc A YB = thời gian rút ngắn của công việc B . YH =th= thời gian rút ngắncn của công vi ệcHc H ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  38. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Xác định hàm mục tiêu Vì mục tiêu của bài toán là cực tiểu chi phí rút ngắn nên hàm mục tiêu của bài toán quy hoạch tuyến tính là: Z = 1, 000YA + 2, 000YB + 1, 000YC + 1, 000YD + + 1,000YE + 500YF + 2,000YG + 3,000YH → min ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  39. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Xác định các ràng buộc Ràng buộccv về thời gian rút ngắn: Thời gian Ràng buộc về thời Công Thời gian ( tuần ) rút ngắn gian rút ngắn ( Yi) việc Bình th ường Rút ngắn được A2 11 YA ≤ 1 B 3 1 2 YB ≤ 2 C2 11 YC ≤ 1 D 4 3 1 YD ≤ 1 E4 22 YE ≤ 2 F3 21 YF ≤ 1 G5 23 YG ≤ 3 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. H2 11 YH ≤ 1
  40. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Ràng buộc về mối quan hệ giữa các công việc: Mỗiôi công v iệc có mộttà ràng b uộc về mốihi quan hệ của côiông việc đứng trước. Dạng thức của ràng buộc này là: EF của công việc sau ≥ EF của công việc đứng trước + (t-Y) Công Ràng buộc về quan Công Ràng buộc về quan hệ việc hệ trước sau việc trước sau BD BĐ X = 0 FXF – XC + YF ≥ 3 AX-X + Y ≥ 2 X –X + Y ≥ 5 A BD A G G D G B XB - XBD + YB ≥ 3 XG – XE + YG ≥ 5 CXC –XA + YC ≥ 2 XH –XF + YH ≥ 2 D XD – XB +Y+ YD ≥ 4 H XH – XG +Y+ YH ≥ 2 EX–X + Y ≥ 4 E C E©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  41. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Ràng buộc về thời hạn hoàn thành dự án: XH ≤ 12 Xác định các điều kiện biên X, Y ≥ 0, nguyên ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  42. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Giải bài toán bằng WinQSB ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  43. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Giải bài toán bằng WinQSB ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  44. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Giải bài toán bằng WinQSB ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
  45. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Giải bài toán bằng WinQSB Sử dụng bài toán CPM ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.