Giáo trình tin học trong quản lý xây dựng - Chương 4

Tài liệu tham khảo Giáo trình điện tử môn học tin học trong quản lý xây dựng ( GV. ThS. Nguyễn Thanh Phong - Khoa kỹ thuật và công nghệ ) - Chương 4 Quuy hoạch tuyến tính
Nội dung trích xuất từ tài liệu:
Giáo trình tin học trong quản lý xây dựng - Chương 4 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only.Chương 4 - QUY HO CH TUY N TÍNH (LINEAR PROGRAMING) CHƯƠNG 4 QUY HO C H TUY N TÍNH (LP-LINEAR PROGRAMMING)* M C TIÊU H C T P :Sau khi hoàn t t h c t p chương 4, sinh viên s có kh năng: 1. Mô t nh ng gi thuy t c a bài toán QHTT. 2. Li t kê các thành ph n và yêu c u c a bài toán QHTT. 3. Mô t cách thành l p bài toán QHTT. 4. Áp d ng p hương pháp đ th đ gi i bài toán QHTT có 2 bi n. 5. Nh n bi t 4 trư ng h p đ c bi t trong bài toán QHTT. 6. Th c hi n vi c phân tích đ nh y trong QHTT. 7. S d ng các công c tin h c đ gi i bài toán QHTT.1. GI I THI U V QUY HO CH TUY N TÍNH R t nhi u quy t đ nh trong qu n lý liên quan đ n vi c c g ng sd ng hi u qu nh t ngu n tài nguyên (Resources) c a t ch c haycông ty mình. Tài nguyên thông thư ng bao g m: Máy móc, thi t b ,lao đ ng, ti n, th i gian, không gian (kho bãi), và nguyên v t li u. Cáctài nguyên này có th s d ng đ s n x u t t o ra s n ph m (ví d nhưmáy móc, v t li u trang trí n i th t, th c ăn hay qu n áo) ho c cũng cóth t o ra d ch v (chính sách marketing, k ho ch đi u đ trong s nxu t hay trong hàng không, ho c các quy t đ nh đ u tư). Q uy ho ch tuy n tính (QHTT)-LP (Linear Programming) làm t phương pháp toán đư c s d ng r t r ng rãi giúp cho ngư i qu nlý trong vi c ho ch đ nh và ra quy t đ nh liên quan đ n vi c p hân bcác tài nguyên (resource allocation). Quy ho ch tuy n tính s d ngGV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 239 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only.Chương 4 - QUY HO CH TUY N TÍNH (LINEAR PROGRAMING)máy tính r t nhi u vì nh ng bài toán th c thư ng r t l n và ph c t pnên không th gi i b ng tay đư c. Có th cho r ng QHTT đ ã đư c phát minh trư c Th chi n II b inhà toán h c Xô Vi t n i b t A.N.Kolmogorow. Sau đó m t nhà toánh c ngư i N ga khác, Leonid Kantorovich, đ ã đ t gi i thư ng Nobelkinh t khi đ t n n t ng cho nh ng khái ni m c a b ài toán l p kho ch s n xu t t i ưu. Và m t ng d ng đ u tiên c a QHTT, phátminh vào năm 1945 b i Stiler, là bài toán mà ngày này chúng tathư ng g i là bài toán ăn kiêng (Diet problem). Tuy nhiên, s pháttri n c a Q HTT ch th t s bùng n sau khi Geogre D.Dantzig pháttri n m t th t c đ gi i bài toán QHTT thư ng đư c g i là phươngpháp đơn hình (Simplex Method). Dantzig và nhà toán h c Air Forceđư c phân công các công tác liên quan đ n h u c u (logisticsproblem) trong quân s . Các ông đã nh n ra r ng có rât nhi u v n đtrong quân s liên quan đ n s gi i h n v tài nguyên và th a mãn cácnhu c u khác nhau có th di n t dư i m t t p các phương trình và b tphương trình. M c dù ng d ng ban đ u trong quân s , QHTT cũngđã phát tri n vô cùng nhanh chóng trong các lĩnh v c công nghi p vàqu n lý khi có s ra đ i c a máy tính. Th t ra, thu t ng QHTT banđ u đư c g i là “Chương trình có c u trúc tuy n tính” (Programmingin a linear structure). Tuy nhiên, vào năm 1948, Tjalling Koopmans đãđ ngh G eorge Dantzig đ i nó thành m t cái tên ng n g n hơn, đóchính là QHTT. V ào năm 1984, nhà toán h c ngư i M N .Karmarkar đã xâyd ng m t thu t toán còn m nh hơn c phương pháp đơn hình trong r tnhi u ng d ng khác nhau đư c mang tên phương pháp đi m trongKarmarkar (Karmarkar’s interior point method).GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 240 Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only.Chương 4 - QUY HO CH TUY N TÍNH (LINEAR PROGRAMING)2. CÁC THÀNH PH N C A BÀI TOÁN QUY HO C H TUY N TÍNH Trong hơn 50 năm qua, QHTT đã đư c ng d ng r ng rãi đ gi iquy t các v n đ trong các lĩnh v c quân đ i, công nghi p , nôngnghi p , tài chính, và marketing. Dù đa d ng, các bài toán QHTT đ u có 4 thành ph n/đ c đi mchính như sau: 1. Hàm m c tiêu; 2. Các ràng bu c; 3. Các phương án l a ch n; 4. Hàm m c tiêu và các ràng bu c là hàm tuy n tính. 2.1. Hàm m c tiêu (Objective function) T t c các bài toán là nh m đ c c đ i hóa (Maximize) ho c c cti u hóa (Minimize) m t đ i lư ng nào đó. Ví d : C c đ i hóa l inhu n ho c c c ti u hóa chi phí + N gư i qu n lý s n xu t mu n l p m t k ho ch s n xu t và đưa ra m t chính sách t n kho đáp ng nhu c u khách hàng sao cho chi phí s n xu t và t n kho là ít nh t. + Chuyên gia phân tích tài chính mu n đ ưa ra quy t đ nh l a ch n các danh m c đ u tư sao cho s ti n thu đư c là nhi u nh t. ...