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

Chương 4 - Quy hoạch tuyến tính số nguyên. Chương này gồm có những điểm chinhs au: 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í.
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 4 - ThS. Đỗ Thị Xuân LanChương 4 QuyCh Q hoạch h htuyến tính số nguyênTin học trong quản lýChương 4Quy hoạchtuyế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 ợ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 ét đến đế yếu tố chi c p phí ©2010củaĐỗ Thị XuânLan,GVC.Ths.Chương 4 Quy hoạch tuyến tính sốnguyênMÔ HÌNH QUY HOẠCH TUYẾNTÍNH THUẦN NGUYÊN ©2010củaĐỗ Thị XuânLan,GVC.Ths.MÔ HÌNH QUY HOẠCH TUYẾNTÍNH THUẦN NGUYÊNVí dụ d 4.1: 41Để phát triển sản xuất,chủ cơ cở gia công cốppppha dựự định ị mua thêm một ộ số máyy 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áy Má dập dậ chiếm hiế 2m 2 2 , giá iá 6.000 6 000 USD+ Máy tiện chiếm 3m2, giá 5.000 USDVậy số lượng máy mỗi loại nên mua bao nhiêu thì tiền lời nhất. ©2010củaĐỗ Thị XuânLan,GVC.Ths. 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 Tiền 70USD 0USD 60USD Diện tích 2 3 12 Giá 6.000USD 5.000USD 30.000 x1 x2 ©2010củaĐỗ Thị XuânLan,GVC.Ths.MÔ HÌNH QUY HOẠCH TUYẾNTÍNH THUẦN NGUYÊNMô hình toán: Hàm mục tiêu: Z = 70x1 +60x2 USD max Các ràng buộc: 6x1 + 5x2 ≤ 30 (1 (1.000USD) 000USD) 2x1 + 3x2 ≤ 12 (m2 ) Điều kiện biên: x1 ≥ 0, x2 ≥ 0 ©2010củaĐỗ Thị XuânLan,GVC.Ths. X2 Giải bài ttoán á quy hhoạch h ttuyến ế tính số nguyên bằng phương 6 pháp p p đồ thịị 5 6X1 +5X2=30Máy tiệnn 4 3 Lời giải tối ưu X1 =3 3.75 75 ,XX2 =1 1.5 5 D(4,2) lợi nhuận = 352.5 USD 2 1 Z=340 E(4,1) 2X1 +3X + 3X2 =12 B(5,0) Z=350 X1 1 2 3 4 5 6 Máy dập ©2010củaĐỗ Thị XuânLan,GVC.Ths. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH THUẦN NGUYÊNMô hình toán: Hàm mục tiêu: Z = 70x1 +60x2 USD max Các ràng buộc: 6x1 + 5x2 ≤ 30 (1.000USD) (1 000USD) 2x1 + 3x2 ≤ 12 (m2 ) Điều kiện biên: x1 ≥ 0, x2 ≥ 0 bổ sung x1 , x2 nguyên ©2010củaĐỗ Thị XuânLan,GVC.Ths.MÔ HÌNH QUY HOẠCH TUYẾNTÍ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ính í h 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 y tính ©2010củaĐỗ Thị XuânLan,GVC.Ths.Chương 4 Quy hoạch tuyến tính sốnguyênMÔ HÌNH QUY HOẠCHTUYẾN TÍNH NHỊ NGUYÊN ©2010củaĐỗ Thị XuânLan,GVC.Ths. MÔ HÌNH Q ...