Bài giảng Tin học trong quản lý xây dựng: Chương 3 - ThS. Đỗ Thị Xuân Lan

Chương 3 - Quy hoạch tuyến tính (QHTT). Các nội dungc hính trong chương này gồm: Các yêu cầu cho một bài toán QHTT, giải bài toán QHTT bằng phương pháp đồ thị, giải bài toán QHTT cực tiểu hàm mục tiêu, bài toán đối ngẫu, biến bổ sung, biến bù, phân tích cảm biến, phương pháp đơn hình.
Nội dung trích xuất từ tài liệu:
Bài giảng Tin học trong quản lý xây dựng: Chương 3 - ThS. Đỗ Thị Xuân LanChương 3QuyCh 3Q hoạch h htuyến tínhTin học trong quản lý xây dựngChương 3 Quy hoạchtuyến ế tính í h• Các yêu cầu cho một bài toán QHTT• Giải bài toán QHTT bằng phương pháp đồ thịị• Giải bài toán QHTT cực tiểu hàm mục tiêu• Bài toán đối ngẫu ế bổ su• Biến sung, g, b biến ế bù• Phân tích cảm biến ©2010củaĐỗ Thị XuânLan,GVC.Ths.Chương3 QuyhoạchtuyếntínhCÁCYÊUCẦUCHOMỘTBÀICÁC YÊU CẦU CHO MỘT BÀITOÁNQHTT ©2010củaĐỗ Thị XuânLan,GVC.Ths.Các yêu cầu cho một bàitoán á QHTT• Các bài toán qquyy hoạch ạ tuyến y tính đều tìm lời giải để cực đại hay cực tiểu hàm mục tiêu• Các bài toán quy hoạch tuyến tính đều có các ràng buộc làm hạn chế khả năng cực đại hay cực tiểu hàm mục tiêu.• Các bài toán quy hoạch tuyến tính luôn có nhiều khả năng để lựa chọn.• Hàm mục tiêu và các ràng buộc của bài toán quy hoạch tuyến tính phải là hàm tuyến tính (hàm bậc nhất) ©2010củaĐỗ Thị XuânLan,GVC.Ths.Chương3 QuyhoạchtuyếntínhGIẢIBÀITOÁNQHTTBẰNGGIẢI BÀI TOÁN QHTT BẰNGPHƯƠNGPHÁPĐỒ THỊ ©2010củaĐỗ Thị XuânLan,GVC.Ths.Giải bài toán QHTT bằngphương h pháp há đồ thị hị• Ví dụ. Một lò gốm hàng ngày sản xuất hai loại mặt ặt hàng hà cao cấp:ấ bình bì h bông bô (B) và à đôn đô sứứ (Đ), sản lượng bị giới hạn bởi nguyên liệu là đất sét trắng và số thợ lành nghề (tính theo giờ công lao động) động). Số đất sét trắng hàng ngày được cung cấp: 240kg. Số giờ công lao động lành nghề hàng ngày: 100 giờ. Để làm được một đôn sứ cần có 4 kg đất sét trắng và 2 giờ công lao động. Để làm được một bình bông thì cần phải có 3 kg đất sét trắng, 1 giờ công. Đơn giá bán một đôn sứ là 70.000 đồng, một bình bô là 50 bông 50.000 000 đồ đồng. Vậy Vậ mỗi ỗi ngày à nên ê sản ả xuất bao nhiêu đôn sứ và bao nhiêu bình bông để doanh thu cao nhất? ©2010củaĐỗ Thị XuânLan,GVC.Ths. Giải bài toán QHTT bằng phương h pháp há đồ thị hị Bài toán được tóm tắt như sau:Tài nguyên Nhu cầu để sản xuất một Khả sản ả phẩm hẩ năng ă Đôn sứ (x1) Bình bông (x2) đáp ứngĐất sét trắng 4 3 240Giờ công 2 1 100Giá bán (10.000 đ) 7 5 ©2010củaĐỗ Thị XuânLan,GVC.Ths.Giải bài toán QHTT bằngphương h pháp há đồ thị hị• Bước 1. Đặt tên biếnGọi x1 là số lượng đôn sứ sản xuất mỗi ngàyGọi x2 là số lượng bình bông sản xuất mỗi ngày• Bước B ớ 2. 2 Xác Xá định đị h hà hàm mục tiêu tiê Z = 7x1 + 5x2 max• Bước 3. Xác định các điều kiện ràng buộc 4x1 + 3x2 ≤ 240 (kg đất sét) (1) 2x1 + 1x2 ≤ 100 (giờ công) (2) Điều ề kiện biên: x1 ≥ 0 x2 ≥ 0• Bước 4. Giải bằng phương pháp đồ thị ©2010củaĐỗ Thị XuânLan,GVC.Ths. X2 100 C( 1 = 0, C(x 0 x2 = 100) Thể hiện các ràng buộc của A(x1 = 0, x2 = 80) bài toán bằng đồ thị 80 Ràng buộc về giờ công: 2x1 + 1x2 ≤ 100Soá bình boâng 60 Ràng buộc về đất sét: 4x1 + 3x2 ≤ 240 40 20 D(x1 = 50, x2 = 0) B(x1 = 60, x2 = 0) X1 20 ...