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

Ch 4 Q h hương uy oạc tuyến tính số nguyên Tin học trong quản lý 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ắt vật tư • Bài toán rút ngắn thời gian đường găng có xét đến yếu tố chi phí ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Chương 4 Quy hoạch tuyến tính số MÔ HÌNH QUY HOẠCH TUYẾN nguyên TÍNH THUẦN NGUYÊN ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN Ví d 4 1ụ . : Để phát triển sản xuất,chủ cơ cở gia công cốp pha dự định mua thêm một số máy dập và máy tiện.Ước tính mỗi máy dập mỗi ngày cho 70USD tiền lờ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á dậ hiế 2 2 iá 6 000 USD+ y p c m m , g . + Máy tiện chiếm 3m2, giá 5.000 USD Vậy số lượng máy mỗi loại nên mua bao ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. nhiêu thì tiền lời nhất. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊN  Tóm tắt bài toán : Tài nguyên Máy dập(x1) Máy tiện (x2) Khả năng đáp ứng Tiề lời 0USD 60USDn 7 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. 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: 6x + 5x ≤ 30 (1 000USD)1 2 . 2x1 + 3x2 ≤ 12 (m2 ) Điều kiện biên: x1 ≥ 0, x2 ≥ 0 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. X2 Giải bài t á h h t ế 6 o n quy oạc uy n tính số nguyên bằng phương pháp đồ thị 5 6X1 + 5X2 =30 n 4 3M á y t i ệ n Lời giải tối ưu X1 =3 75 X2 =1 5 2 1 2X + 3X =12 . , . lợi nhuận = 352.5 USDD(4,2) 1 2 3 4 5 6 X1 1   2 B(5,0) E(4,1)Z=340 Z=350 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Máy dập 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 +60x USD max 1 2 Các ràng buộc: 6x + 5x ≤ 30 (1 000USD)1 2 . 2x1 + 3x2 ≤ 12 (m2 ) Đ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. 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 ế í h ố êtuy n t n 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. Chương 4 Quy hoạch tuyến tính số MÔ HÌNH QUY HOẠCH nguyên TUYẾN TÍNH NHỊ NGUYÊN ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH NHỊ NGUYÊN Bài toán : Chính quyền thị trấn 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ể thao Số người kỳ vọng sử dụng Kinh phí xây dựng (triệu Diện tích mặt bằng cần 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 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Nhà thi đấu mini 150 9000 3 MÔ HÌNH QUY HOẠCH TUYẾN TÍNH NHỊ NGUYÊN Tổng mặt bằ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ột khu đất có địa thế thích hợp để có thể để xây dựng hoặc hồ bơi hoặc sân quần vợt. Nên xây dựng công trình nào để ấ ểngười dân trong thị tr n có th sử dụng được nhiều nhất? ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. Gọi : là h h á â d hồx1 c ọn p ương n x y ựng bơi . là h h ơ á â d âx2 c ọn p ư ng n x y ựng s n quần vợt . x là chọn phương án xây dựng sân3 điền kinh . x là chọn phương án xây dựng nhà4 thi đấu – Nếu 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. 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 : x + x ≤ 11 2 - Ràng buộc về diện tích đất : 4x1 + 2x2 + 7x3 + 3x4 ≤ 12 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. * Điều kiện biên : x1 , x2 , x3 , x4  0,1 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ần vợ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. Chương 4 Quy hoạch tuyến tính số MÔ HÌNH QUY HOẠCH TUYẾN nguyên TÍNH SỐ NGUYÊN HỖN HỢP ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH SỐ NGUYÊN HỖN HỢP Ví dụ 4.2: Ông Giàu có tiền vốn là 250.000USD định đầu tư theo 3 phương án sau: 1.Mua xe ô tô chở khách, mỗi xe giá 50 000USD cuối năm cho tiền lời 5 000USD. , . . 2.Mua đất vườn, mỗi ha đất giá 12.000USD, cuối năm cho tiền lời 1.500USD. 3 M tí hiế kh b ỗi tí hiế iá. ua n p u o ạc, m n p u g 8.000USD,cuối năm lãnh tiền lời 1.000USD. Vậy ông Giàu nên đầu tư vào dự án như thế nào để tiền lời nhiều nhất? Biết rằng ông Giàu chỉ nên mua tối đa 4 xe ô tô để đảm bảo có kế hoạch sử dụng thường xuyên và khu đất ông Giàu định ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. mua chỉ còn 30ha. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH SỐ NGUYÊN HỖN HỢP • Gọi : x1 là số xe ô tô sẽ mua là ố h đất ẽx2 s a s mua x3 là số tín phiếu sẽ mua • Mô hình toán: – Hàm mục tiêu: (để có tiền lời mỗi năm nhiều nhất) Z = 5.000x1 + 1.500x2 + 1000x3 (USD) axm – Các ràng buộc : 50.000x1 + 12.000x2 + 8.000x3 ≤ 250.000 (USD) x1 ≤ 4 x2 ≤ 30 ề ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. – Đi u kiện biên: x1 ≥ 0 , nguyên; x2 ≥ 0 ; x3 ≥ 0 , nguyên MÔ HÌNH QUY HOẠCH TUYẾN TÍNH SỐ NGUYÊN HỖN HỢP Lời giải tối ưu của bài toán là: – x1 = 0 xe ô tô sẽ mua – x2 = 7,5 ha đất sẽ mua – x3 = 20 tín phiếu sẽ 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ếu sẽ mua ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. – Tiền lời thu được hàng năm Z = 31.250 USD Chương 4 Quy hoạch tuyến tính số BÀI TOÁN PHA CẮT VẬT nguyên TƯ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. 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 đ Ø 16 dài 2 9 176 đ Ø 16 dài oạn , m; oạn 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. 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. Các phương án Số lượng các đoạn Mẫu thừa (m) 2.1m 2.9m 3.2m 4.2m x1 0 0 1 2 0.1 0 1 0 2 0 4x2 . x3 1 0 0 2 1.2 x4 0 0 2 1 1.1 0 1 1 1 1 4x5 . x6 0 2 0 1 1.7 x7 2 1 0 1 0.4 x8 3 0 0 1 1.2 x9 1 0 3 0 0 x10 1 1 2 0 0.3 x11 2 0 2 0 1.1 x12 1 2 1 0 0.6 x13 2 1 1 0 1.4 x14 4 0 1 0 0.1 x15 0 4 0 0 0.1 x16 1 3 0 0 0.9 x17 2 2 0 0 1.7 x18 4 1 0 0 0.4 x19 5 0 0 0 1.2 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 1 19 i i Z x min     Điề kiệ biê ≥ 0 ê ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. u n n: xi , nguy n 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 + 1x9 + 1x10 + 2x11 + 1x12 + 2x13 + 4x14 + 0x15 + Có đủ 161 0x1 + 1x2 + 0x3 + 0x4 + 1x5 + 2x6 + 1x7 + 0x8 + 0x9 + 1 + 0 + 2 + 1 + 0 + 4 + 3 + 1x16 + 2x17 + 4x18 + 5x19 ≥ 210đoạn dài 2.9m Có đủ 176 x10 x11 x12 x13 x14 x15 x16 2x17 + 1x18 + 0x19 ≥ 161 đoạn dài 3.2m 1x1 + 0x2 + 0x3 + 2x4 + 1x5 + 0x6 + 0x7 + 0x8 + 3x9 + 2x10 + 2x11 + 1x12 + 1x13 + 1x14 + 0x15 + 0x16 + 0x17 + 0x18 + 0x19 ≥ 176 Có đủ 48 đoạn dài ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. 2x1 + 2x2 + 2x3 + 1x4 + 1x5 + 1x6 + 1x7 + 1x8 + 0x9 + 0x10 + 0x11 + 0x12 + 0x13 + 0x14 + 0x15 + 0x16 + 0x17 + 0x18 + 0x19 ≥ 48 4.2m 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. 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. BÀI TOÁN PHA CẮT VẬT TƯ G i là ố th h ê h ắt th PA1  Đặt tên biến: ọ x1 s an nguy n p a c eo 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. BÀI TOÁN PHA CẮT VẬT TƯ G i là ố th h ê h ắt th PA1  Đặt tên biến: ọ x1 s an nguy n p a c eo 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. 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 min4x1 + 8x2 + 12x3 + 0x4 + 4x5 + 8x6 Điề kiệ biê Để tổng chiều dài các mẫu thừa là ít nhất ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. u n n : xi ≥ , nguyên 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. 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. Chương 4 Quy hoạch tuyến tính số RÚT NGẮN THỜI GIAN HOÀN nguyên THÀNH DA CÓ XÉT ĐẾN CHI PHÍ ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Ví d 4 6 ụ . : Rút ngắn thời gian của DA xây dựng nhà công nghiệp của công ty ABC. - Thời gian thực hiện DA là 12 tuần ắ ấ ấ- Chi phí rút ng n th p nh t ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ S đồ F3 ơ mạng: A2 C2 E4 H2BĐ G5 D4B3 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. RÚT NGẮN THỜI GIAN HOÀN THÀNH DA CÓ XÉT ĐẾN CHI PHÍ Công Thời gian ( tuần ) Chi phí ( ngàn đồng ) Thời gian út ắ Chi phí út ắ việc r ng n được r ng n đơn vị Bình thường Rút ngắn Bình thường Rút ngắn A 2 1 22,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. 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 X = EF của công việc BB . 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 gian 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 . Y = thời gian rút ngắn của công việc H ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. H 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. 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 gian rút ngắn: Xác định các ràng buộc Công việc Thời gian ( tuần ) Thời gian rút ngắn đ Ràng buộc về thời gian rút ngắn ( Yi) Bì h th ờ Rút ắ ược n ư ng ng n A 2 1 1 YA ≤ 1 B 3 1 2 Y ≤ 2B C 2 1 1 YC ≤ 1 D 4 3 1 YD ≤ 1 E 4 2 2 YE ≤ 2 F 3 2 1 YF ≤ 1 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. G 5 2 3 YG ≤ 3 H 2 1 1 YH ≤ 1 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ệ ó ột à b ộ ề ối hệ ủ ô iệ c ng v c c m r ng u c v m quan c a c ng v 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 việc Ràng buộc về quan hệ trước sau Công việc Ràng buộc về quan hệ trước sau X 0BĐ BD = F XF – XC + YF ≥ 3 A XA - XBD + YA ≥ 2 G XG – XD + YG ≥ 5 B X X Y ≥ 3 X X Y ≥ 5B - BD + B G – E + G C XC – XA + YC ≥ 2 H XH – XF + YH ≥ 2 D X X + Y ≥ 4 X X + Y ≥ 2 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths. D – B D H – G H E XE – XC + YE ≥ 4 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. 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. 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. 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. 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.