Giáo trình Tin học trong quản lý xây dựng - Chương 3: Quy hoạch tuyến tính

37 trang huongle 1970

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 3: Quy hoạch tuyến tính", để 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:

giao_trinh_tin_hoc_trong_quan_ly_xay_dung_chuong_3_quy_hoach.pdf

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

Chương 3QhQuy hoạch tuyếntínhn tính Tin học trong quản lý xây dựng
Chương 3 Quy hoạch tuyến tíhính • Các yêu cầuchomu cho một bài tốn QHTT •Giải bài tốn QHTT bằng phương pháp đồ thị •Giải bài tốn QHTT cực tiểu hàm mục tiêu • Bài tốn đối ngẫu •Biến bổ sun g, biến bù • Phân tích cảm biến ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Các yêu cầu cho một bài tốQHTTán QHTT • Các bài tốn qqyuy hoạch tuyến 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 tốn quy hoạch tuyến tính đềuucĩ 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 tố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ộccc của bài tốn quy hoạch tuyến tính phải là hàm tuyến tính (hàm bậc nhất) ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Giải bài tốn QHTT bằng phương pháp đồ thị • Ví dụ. Một lị gốm hàng ngày sản xuất hai loại mặthàt hàng cao cấp: bình bơ ng (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). Số đấtséttrt 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ầncĩ4kgn cĩ 4 kg đấtséttrt 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ơng là 50. 000 đồng. Vậy 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? ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Giải bài tốn QHTT bằng phương pháp đồ thị Bài tốn đượcctĩmt tĩm tắtnht như sau: Tài nguyên Nhu cầu để sản xuất một Khả sản phẩmnăng Đơn sứ (x ) Bình bơng (x ) đáp 1 2 ứng Đấtséttrắng 4 3 240 Giờ cơng 2 1 100 Giá bán (10.000 đ)7 5 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Giải bài tốn QHTT bằng phương pháp đồ thị • Bước 1. Đặt tên biến Gọi x1 là số lượng đơn sứ sản xuất mỗi ngày Gọi x2 là số lượng bình bơng sản xuất mỗi ngày • Bước 2. Xác địnhhàh hàm mục tiêu Z = 7x1 + 5x2 max • Bước3.c 3. Xác định các điềukiu kiệnràngbun 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ị ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
X2 100 C(x1 = 0, x2 = 100) Thể hiện các ràng buộc của A(x1 = 0, x2 = 80) bài tốn bằng đồ thị 80 Ràng buộcvề giờ cơng: 2x1 +1x2 ≤ 100 gg 60 Ràng buộc về đất sét: 4x1 + 3x2 ≤ 240 Số bình bôn 40 20 D(x1 = 50, x2 = 0) B(x1 = 60, x2 = 0) X1 20 40 60 80 100 ©2010 của Đỗ Thị Xuân LanSố ,đôn GVC. sứ Ths.
X2 100 C(x1 = 0, x2 = 100) tìm nghiệm của bài tốn A(x1 = 0, x2 = 80) bằng phương pháp đường 80 hàm mụctiêuc tiêu đồng dạng gg 60 Z = 7x1 + 5x2 =410 (x1 = 30, x2 = 40) Số bình bôn 40 Z = 7x1 + 5x2 = 350 20 D(x1 = 50, x2 = 0) B(x1 = 60, x2 = 0) X1 20 40 60 80 100 ©2010 của Đỗ Thị Xuân LanSố ,đôn GVC. sứ Ths.
X2 Cũng cĩ thể giải bài tốn qqyuy 100 C(x1 = 0, x2 = 100) hoạch tuyến tính bằng A(x = 0, x = 80) 1 2 phương pháp điểm gĩc 80 Điểm O(O: (x1 = 0, x2 = 0) Z = 7(0) + 5(0) = 0 A Điểm A: (x1 = 0, x2 = 80) Z = 7(0) + 5(80) = 240 Điểm E: (x1 = 30, x2 = 40) Z = 7(30) + 5(40) = 410 Điểm D: (x = 50, x = 0) Z = 7(()50) + 5( ()0) = 350 gg 60 1 2 ố bình bôn E SS 40 20 D(x1 = 50, x2 = 0) B(x1 = 60, x2 = 0) O D X1 ©201020 của Đỗ Th 40ị Xuân Lan , GVC. 60 Ths. 80 100 Số đôn sứ
Giải bài tốn cực tiểu hàm mục tiêu Ví dụ. Một nơơâng dân cần mua phââĩn bĩn cho mùa trồng trọt tới. Cĩ 2 loại phân đĩng gĩi 10 kg do hãng A và B sảnxun xuấttv, vớiicác các thành phần đạm và lân trong phân của hãng A lần lượt là 3 và 7 kg, của B là 6 và 4 kg. Giá mua một gĩi phân của hãng A là 60.000 đồng, hãng B là 30.000 đồng. Người nơng dân cầntn tốiithi thiểuu16kg 16 kg đạmmvà và 24 kg lân. Hỏi ơng ta nên mua bao nhiêu gĩi của mỗi hãng đề chi phí thấp nhất. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Giải bài tốn cực tiểu hàm mục tiêu Bài tốn đượcctĩmt tĩm tắtnht như sau: Thành phầnLoại Nhu cầu A (x1)B (x2) Đạm (kg/gĩi) 3 6 16 Lân ((gg)kg/gĩi) 74 24 Giá mua (10.000 đồng) 6 3 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Giải bài tốn cực tiểu hàm mục tiêu • Bước1.c 1. Đặt tên biến Gọi x1 là số gĩi phân loại A cần mua Gọi x2 là số ggpĩi phân loại B cần mua • Bước 2. Xác định hàm mục tiêu Z = 6x1 + 3x2 min • Bước 3. Xác định các điều kiện ràng buộc 3x1 + 6x2 ≥ 16 (nhu cầu về đạm) 7x1 + 4x2 ≥ 24 (nhu cầu về lân ) Điều kiện biên là: x1, x2 ≥ 0 • Bước 4. Giải bằng phương pháp đồ thị ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
A (x1 = 0, x2 = 6) là nghiệm tối ưu 7x1 + 4x2 ≥ 24 (lân) Z = 6x1 + 3x2 = 24 3x1 + 6x2 ≥ 16 (đạm) Z=6xZ = 6x1 +3x+ 3x2 =18= 18 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Bài tốn đốingi ngẫu • Ví d ụ. Mộtxt xưởng mộccs sảnxun xuất bàn và tủ. Lượng sản phẩm sản xuất ra được phụ thuộc vào số cơng lao động và diện tích mặt bằng. Nhu cầu sử dụng tài nguyên để sản xuất ra tủ và bàn cũng như lượng tài nguy ên tối đa cung cấp hàng ngày được trình bày trong bảng. Giá gia cơng 500. 000 đ/tủ và 1. 200. 000 đ/bàn. Mỗi ngày nên sản xuất bao nhiêu tủ và bàn để cĩ doanh thu lớn nhất. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Tài nguyên Nhu cầu củaLượng tài Tủ Bàn nguyêncung cấp hàng ngày Lao động (cơng) 2 4 80 Mặtbằng (m2)31 60 Bước 1. Đặt tên biến Gọi x1 là số tủ nên đĩng trong ngày Gọixi x2 là số bàn nên đĩng trong ngày Bước 2. Xác định hàm mục tiêu Z = 50x1 + 120x2 max (10.000 đồng) Bước3c 3. Xác định các điều kiệnràngbn ràng buộc 2x1 + 4x2 ≤ 80 (Khả năng đáp ứng về cơng) 3x1 + 1x2 ≤ 60 (Khả năng đáp ứng về mặt bằng Điều kiện biên là: x1, x2 ≥ 0 Bước4.c 4. Giảibi bằng phương pháp đồ thị x1 = 0, x2 = 20, nên sản xuất 20 bàn và khơng sản xuất tủ mỗi ngày để doanh©2010 c ủthua Đỗ Th caoị Xuân Lan nh , GVC.ấ Ths.t.
Bài tốn đốingi ngẫu Do hai mặt hàng tủ và bàn bán khơng chạy nên ngườichi chủ xưởng sảnnxu xuất khơng định sản xuất chúng nữa mà cho một cơng ty sảnxun xuất đồ gỗ đang cĩ đơn hàng xuất khẩu thuê thợ và cho thuê mặt bằng. Người chủ xưởng phải đặt giá cho thuê một cơng thợ, và một mét vuơng mặt bằng là bao nhiêu để tối thiểu cũng phải đạt được dhthhdoanh thu như khi tự sản xuất. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Bài tốn đốingi ngẫu •Gọi u1 là giá cho thuê một giờ cơng thợ (10.000 đồng) 2 Gọi u2 là giá cho thuê một m mặt bằng (10.000 đồng) •Với điều kiện doanh thu cho thuê ít nhất cũng bằng với doanh thu khi tự sản xuất: 2u1 + 3u2 ≥ 50 (doanh thu thuê tài nguyên để sản xuất 1 tủ) 4u1 +1u+ 1u2 ≥ 120 (doanh thu cho thuê tài nguyên sảnnxu xuất 1 bàn) • Để cĩ thể thực hiện hợp đồng cho thuê, tổng tiền thuê phải cĩ giá trị thấp nhất. Hàm mục tiêu của bài tốn là: Z = 80 u1 + 60 u2 min • Điều kiện biên: u1 ≥ 0 u2 ≥ 0 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
cần đặt giá cho thuê •một cơng thợ là u1 = 30 (10.000 đồng) • mặtbt bằng là u2 =0= 0 để cĩ doanh thu là 2.400 (10.000 đồng). ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Bài tốn đốingi ngẫu Bài tốn ban đầu Bài tốn đối ngẫu x1 là số tủ nên đĩng trong u1 là giá cho thuê một giờ ngày cơng thợ 2 x2 là số bàn n ên đĩtĩng trong u2 là g iá c ho thu ê một m mặt ngày bằng Hàm mục tiêu: Hàm mục tiêu: Z = 50 x1 + 120 x2 max Z = 80 u1 + 60 u2 min Các ràng buộc: Các ràng buộc: 2x2 x1 +4x+ 4 x2 ≤ 80 2u2 u1 +3u+ 3 u2 ≥ 50 3 x1 + 1 x2 ≤ 60 4 u1 + 1 u2 ≥ 120 Điều kiện biên là: Điều kiện biên: x1, x2 ≥ 0 u1, u2≥ 0 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Biếnbn bổ sung, biếnbùn bù Điểm A ((,0, 20) ng hiệm của bài tốn nằm trên ràng buộc cơng lao động cho thấy kế hoạch sản xuất bàn và tủ tối ưu sẽ tậndn dụng hết cơng lao động. ĐiểmA(0m A(0, 20) khơng nằm trên ràng buộc về mặt bằng cho thấy kế hoạch sản xuất bàn và tủ tối ưu khơng sử dụng hết mặt bằng 2x1 + 4x2 ≤ 80 là r àng buộc tận dụng hết 3x1 + 1x2 ≤ 60 là ràng buộc khơng tận dụng hết ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Biếnbn bổ sung, biếnbùn bù Đốivi với ràng buộcchc chưata tậndn dụng hết, chênh lệch giữa vế phải và vế trái (ký hiệu là si) được gọi là biến bổ sung (với ràng buộc ≤) hay biến bù (với ràng buộc ≥). ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Biếnbn bổ sung, biếnbùn bù • Xét ràng buộc về cơng lao động: 2x1 + 4x2 ≤ 80 (1) 2x1 + 4x2 + s1 = 80 s1 =80= 80 - 2(0) - 4(20) s1 = 0 (đã tận dụng hết cơng lao động) • Xét ràng buộc về mặt bằng: 3x1 + 1x2 ≤ 60 3x1 + 1x2 + s2 = 60 s2 =60= 60 - 3(0) - 1(20) 2 s2 = 40 (cịn 40 m mặt bằng chưa tận dụng hết) ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Phân tích c ảmbim biến. • Bài tốn qqyuy hoạch tuyến tính ban đầu được giải trong điều kiện xác định sau đĩ tìm xu hướng thay đổi của nghiệm tối ưu khi dữ liệuuc của bài tốn thay đổiig gọi là phân tích cảm biến • phân tích cảm biến khi cĩ –sự thay đổi của hệ số hàm mục tiêu –sự thay đổi giá trị vế bên phải của ràng buộc (với điều kiện là chỉ thay đổi một thơng số tại một thời điểm) ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Thay đổi hệ số hàm mục nếu đường hàm mụctiêuc tiêu tiêu cĩ độ dốc nhỏ hơn độ dốc của đường ràng buộc thứ nhấtthìt thì điểm A vẫn là nghiệm tối ưu, cĩ nghĩa là nghiệm tối ưu của bài c 1 tốn khơng đổi khi: 1 c2 2 Z = 75x1 + 120x2 khi giữ nguyên c2 là 120. c1 1 Z = 50x + 120x thì c1 ≤ 60 1 2 120 2 Z = 40x1 + 120x2 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
c 1 1 120 2 Thay đổi hệ số hàm mục nếu đường hàm mụctiêuc tiêu tiêu cĩ độ dốc nhỏ hơn độ dốc của đường ràng buộc thứ nhấtthìt thì điểm A vẫn là nghiệm tối ưu, cĩ nghĩa là nghiệm tối ưu của bài c 1 tốn khơng đổi khi: 1 c2 2 Z = 50x 1 + 80x 2 khi giữ nguyên c1 là 50. 50 1 Z = 50x1 + 120x2 thì c2 ≥ 100 c2 2 Z = 50x1 + 150x2 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Thay đổi giá trị vế bên D phảici củaràngbua ràng buộcThay đổi giá trị vế bên phải của ràng buộc khi tăng hay giảm một đơn vị cơng lao động thì hàm mục tiêu thay đổi một giá trị là vùng cảm biến 600/20 = 30. Giá trị này đúng của b1 là bằng giá thuê một cơng th ợ 0 ≤ b ≤ 240. 1 (u1 = 30) của bài tốn đối ngẫu nên được gọi là trị đối ngẫu A’’ hayyg giá mờ 2x1 +4x+ 4x2 = 100 B’’ Z= 50x1 + 120x2 = 3000 2x1 + 4x2 = 60 A’ Z= 50x1 + 120x2 = 2400 B’ Z= 50x1 + 120x2 = 1800 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Thay đổi giá trị vế bên phải của rààbng buộc • Trị đốingi ngẫuuu ui chính là giá trị củaatài tài nguyên thứ i (tương ứng với ràng buộc thứ i) nhằm đảm bảo hàm mục tiêu của bài tốn đối ngẫu đúng bằng giá trị hàm mục tiêu của bài tốn ban đầu. Trị đối ngẫu ui (hay c ịn gọiilà là g iá mờ))là là g iátiá trị thay đổi của hàm mục tiêu khi tăng hay giảmmm một đơnvn vị giá trị vế phảici của ràng buộc. ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Thay đổi giá trị vế bên phải của rààbng buộc •Nếu ký hiệu giá trị vế phải của ràng buộc thứ i là bi, vùng cảm biến của bi là khoảng bi cĩ thể thay đổi mà trị đối ngẫu ui khơng thay đổiNi. Nếuunh như giá trị bi tăng vượtgit giới hạn trên hay giảm đến thấp hơn giới hạn dưới của vùng cảm biến thì cĩ ít nhất một ràng bu ộc khơng phải là ràng buộc tận dụng hết trở thành ràng buộc tận dụng hết hay một ràng buộc tận dụng hết trở thành ràng buộc khơng tận dụng hết làm ảnh hưởng đến hàm mục tiêu và trị đối ngẫu ui.Thay đổi giá trị vế bên phải của ràng buộc ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.
Thay đổi giá trị vế bên phải của ràbàng buộc vùng cảm biến của b2 là 20 ≤ b2 3x1 + 1x2 = 30 3x1 + 1x2 = 20 Z= 50x1 + 120x2 = 2400 ©2010 của Đỗ Thị Xuân Lan , GVC. Ths.