intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Nguyen Nhi | Ngày: | Loại File: PDF | Số trang:164

Thêm vào BST
Báo xấu
93
lượt xem 16
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

  1. 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 s d ng hi u qu nh t ngu n tài nguyên (Resources) c a t ch c hay cô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ác tà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 n xu 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 n lý trong vi c ho ch đ nh và ra quy t đ nh liên quan đ n vi c p hân b các tài nguyên (resource allocation). Quy ho ch tuy n tính s d ng GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 239
  2. 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 p nê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 i nhà toán h c Xô Vi t n i b t A.N.Kolmogorow. Sau đó m t nhà toán h c ngư i N ga khác, Leonid Kantorovich, đ ã đ t gi i thư ng Nobel kinh t khi đ t n n t ng cho nh ng khái ni m c a b ài toán l p k ho ch s n xu t t i ưu. Và m t ng d ng đ u tiên c a QHTT, phát minh vào năm 1945 b i Stiler, là bài toán mà ngày này chúng ta thư ng g i là bài toán ăn kiêng (Diet problem). Tuy nhiên, s phát tri n c a Q HTT ch th t s bùng n sau khi Geogre D.Dantzig phát tri n m t th t c đ gi i bài toán QHTT thư ng đư c g i là phương phá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 (logistics problem) 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ác nhu c u khác nhau có th di n t dư i m t t p các phương trình và b t phươ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” (Programming in 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ây d ng m t thu t toán còn m nh hơn c phương pháp đơn hình trong r t nhi u ng d ng khác nhau đư c mang tên phương pháp đi m trong Karmarkar (Karmarkar’s interior point method). GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 240
  3. 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 i quy t các v n đ trong các lĩnh v c quân đ i, công nghi p , nông nghi 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 m chí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 c ti u hóa (Minimize) m t đ i lư ng nào đó. Ví d : C c đ i hóa l i nhu 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. + G iám đ c ti p th mu n xác đ nh s p hân b ngân sách c a vi c qu ng cáo đ i v i các phương ti n truy n thông khác nhau như đài, ti vi, báo, hay t p chí…sao cho mang l i hi u qu cao nh t. + N gư i qu n lý mu n xác đ nh s lư ng s n ph m c n p h i t các nhà máy v n chuy n đ n các nơi tiêu th sao cho chi phí v n t i là th p nh t. Chúng ta g i thành ph n này là hàm m c tiêu (Objective function) c a bài toán QHTT. Ví d : GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 241
  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) + M c tiêu chính c a các nhà s n x u t thông thư ng là là c c đ i hóa l i nhu n. + Còn đ i v i các h th ng phân ph i (v n chuy n b ng xe t i hay đư ng s t) thì m c tiêu có th là c c ti u hóa chi phí v n chuy n. Trong b t kỳ trư ng h p nào, m c tiêu đ u c n ph i đ ư c đ nh nghĩa m t cách rõ ràng và đư c xác đ nh b ng các công th c toán. Không quan tâm đ n vi c l i nhu n hay chi phí đư c đo b ng đơn v ti n t gì, tri u đ ng, t đ ng. 2.2. Các ràng bu c (Constraints) Là các hàm ch ra nh ng h n ch v tài nguyên c a t ch c. Nó s gi i h n m c đ đ t đư c m c tiêu c a chúng ta. Bài toán đ t ra cho chúng ta là c c đ i hóa ho c c c ti u hóa m t s đ i lư ng v i nh ng ràng bu c đã cho. Ví d : + S lư ng s n ph m s s n xu t ra m t công ty s b gi i h n b i máy móc và nhân s huy đ ng c a công ty cũng như nhu c u khách hàng. + V i c l a ch n m t chính sách qu ng cáo hay m t t p danh m c đ u tư s b gi i h n b i t ng s ti n s n có đ đ u tư. + Trong bài toán v n t i, vi c c c ti u hóa chi phí v n t i s b ràng bu c b i kh năng cung c p c a các nhà máy cũng như nhu c u t i các nơi tiêu th . V ì v y, chúng ta thư ng mu n c c đ i hóa hay c c ti u hóa các đ i lư ng (hàm m c tiêu) trong đi u ki n gi i h n v tài nguyên (các đi u ki n ràng bu c). 2.3. Ph i có các phương án đ l a ch n (There must be alternatives available). Có m t công ty s n xu t 3 lo i s n ph m khác nhau. Có th công ty t p trung s n xu t ch y u m t trong 3 s n ph m hay s n xu t đ u 3 lo i s n ph m, ho c phân b m t t l b t kỳ nào đó? Nhà qu n lý GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 242
  5. 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) có th s d ng QHTT đ xác đ nh t l phân b c a chúng trong đi u ki n gi i h n v tài nguyên s n xu t (máy móc, công nhân,…) đ c c đ i l i nhu n. N u ch có m t phương án, chúng ta không c n QHTT. 2.4. Hàm m c tiêu và các ràng bu c đ u là hàm tuy n tính. D ng ràng bu c có th là: + B t p hương trình có d ng “≤” ho c “≥”; + Phương trình “=”. Hàm tuy n tính có nghĩa là s mũ c a các bi n quy t đ nh ph i d ng b c nh t (không đư c là b c 2, b c 3 hay các b c khác 1). Ví d : + Phương trình 2a+ 5b = 10 là phương trình tuy n tính, trong khi đó 2a2 + 5b3 + 3ab = 10 không ph i là phương trình tuy n tính b i vì bi n a có b c là 2, bi n b có b c là 3 và tích a.b cũng không kh thi . + H àm m c tiêu Z = 10x1 + 9x2 là hàm tuy n tính, trong khi đó Z = 10x1 + 9 x 2 không ph i là hàm tuy n tính. 2 Chúng ta thư ng g p các d ng ràng bu c b t phương trình khi gi i các bài toán QHTT. Đ i u này có nghĩa là các ràng bu c không ph i lúc nào cũng có d ng phương trình A + B = C. Các nhà khoa h c qu n lý đã nghiên c u và tìm ra l i gi i c a r t nhi u các mô hình toán h c bao g m m t hàm m c tiêu và m t t p các ràng bu c. Các mô hình này đư c g i là các mô h ình quy ho ch toán h c (mathematical programming models). Mô hình QHTT là m t d ng đ c bi t c a các mô hình quy ho ch toán h c, trong đó hàm m c tiêu và các ràng bu c đ u là hàm tuy n. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 243
  6. 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) 3. CÁC GI THI T CƠ B N C A QUY HO CH TUY N TÍNH Thông thư ng các mô hình toán ng d ng trong kinh t đ u có các gi thi t đ i kèm. V y t i sao phái s d ng các gi thi t? Câu tr l i là vì r t khó đ có mô hình toán h c nào mô t m t cách hoàn toàn chính xác đ n chi ti t trong các tình hu ng th c t và n u có thì mô hình đó s r t p h c t p. Vì v y, đ mô hình đư c đơn gi n hóa (nhưng v n ph i đ m b o không m t đ i tính th c t c a b ài toán), chúng ta c n có các gi thi t đ i kèm. Có 5 gi thi t/yêu c u cơ b n c n n m khi gi i các bài toán QHTT: 1. Tính ch c ch n (Certainty): Các con s trong hàm m c tiêu và các đi u ki n ràng bu c đ ư c bi t ch c ch n và không thay đ i trong su t quá trình nghiên c u. 2. Tính t l (Proportionality): Chúng ta ph i gi thi t có tính t l t n t i trong hàm m c tiêu và các ràng bu c. Nghĩa là s đ óng góp đ i v i hàm m c tiêu và giá tr tài nguyên trong m i ràng bu c ph i t l v i giá tr c a các bi n quy t đ nh. Ví d như n u s n xu t m t s n ph m m t 3 gi thì s n xu t 10 s n ph m s m t 30 gi . 3. Tính c ng d n (Additivity): G iá tr c a hàm m c tiêu và t ng tài nguyên s d ng đ ư c tính toán b ng cách l y t ng hàm m c tiêu đóng góp và tài nguyên s d ng c a t t c các bi n q uy t đ nh. Nghĩa là t ng các ho t đ ng s b ng k t qu c ng d n c a t ng ho t đ ng riêng r . Ví d : N u có m c tiêu là c c đ i hóa l i nhu n b ng 8 USD c a s n ph m 1 + 3 USD c a s n p h m 2 thì khi m t s n ph m đư c s n xu t, l i nhu n t ng c ng s là 8 + 3 = 11 USD. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 244
  7. 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) 4. Tính chia đư c (Divisibility): Bi n quy t đ nh là bi n liên t c. Gi thi t này ch p nh n các nghi m s d ng th p p hân (L i gi i không nh t thi t p h i là s nguyên). Nghĩa là có th ch p nh n giá tr như 1/3 cái bàn đư c s n xu t. 5. Tính không âm (Nonnegative): T t c các bi n ph i không âm. S d ng các con s âm đ đ m là không th . B n không th s n xu t m t s âm cái bàn, cái gh , cái đèn, hay máy tính… đư c. B ng 4.1 sau đây trình bày tóm t t các đ c đi m và gi thi t cơ bàn c a bài toán QHTT: B ng 4.1. Các đ c đi m và gi thi t cơ b n c a bài toán QHTT 4 đ c đi m c a QHTT 5 gi thi t c a bài toán QHTT 1. Hàm m c tiêu; 1 . Tính ch c ch n 2. Các ràng bu c; 2 . Tính t l 3. Các phương án l a ch n; 3 . Tính c ng d n 4. Hàm m c tiêu và các ràng 4 . Tính chia đư c bu c là hàm tuy n tính. 5 . Tính không âm 4. THÀNH L P BÀI TOÁN QUY HO CH TUY N TÍNH Thành l p m t bài toán QHTT liên quan đ n vi c xây d ng m t mô hình toán (mathematical model) đ di n t v n đ qu n lý. Vì v y, đ thành l p m t bài toán QHTT, chúng ta c n ph i hi u m t cách sâu s c v n đ qu n lý đang ph i đ i m t. Khi đã n m rõ, chúng ta có th b t đ u xây d ng mô hình toán cho v n đ . Vi c thành l p m t bài toán QHTT bao g m các bư c sau đây: 1. Hi u rõ v n đ qu n lý đang ph i đ i m t. 2. Xác đ nh hàm m c tiêu và các ràng bu c. 3. Đ nh nghĩa các bi n ra quy t đ nh. 4. S d ng các bi n ra quy t đ nh đ vi t các mô hình toán cho hàm m c tiêu và các ràng bu c. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 245
  8. 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 t trong nh ng ng d ng ph bi n c a QHTT là bài toán k ho ch s n xu t nhi u s n ph m (Product mix problem). Hai hay nhi u s n ph m đư c s n xu t trong đi u ki n gi i h n v tài nguyên như lao đ ng, máy móc, nguyên v t li u…L i nhu n mà công ty mu n c c đ i đ ư c d a trên l i nhu n đóng góp c a m i đơn v s n ph m. Công ty s p h i quy t đ nh s n xu t bao nhiêu s n ph m m i lo i đ c c đ i hóa t ng l i nhu n trong ph m vi cho phép v tài nguyên. Ví d v cách thành l p 1 bài toán QHTT: Công ty s n xu t n i th t Phương Nam Công ty Phương Nam s n xu t các lo i bàn và gh g r ti n. Quy trình s n xu t c a m i s n p h m đ u có đi m chung là cùng tr i qua công đo n đóng m c (carpentry work) và sơn, đánh bóng (painting and varnishing): - M i cái bàn c n 4 gi đóng m c, 2 gi sơn và đánh bóng. - M i cái gh c n 3 gi đóng m c, 1 gi sơn và đánh bóng. Trong giai đo n s n xu t hi n t i, chu kỳ 1 tu n, v i l c lư ng công nhân lao đ ng hi n có, công ty Phương Nam có t ng c ng 240 gi đóng m c và 100 gi sơn, đánh bóng (S công nhân * Gi công m i ngày). M i cái bàn và gh khi công ty đem bán s đem l i l i nhu n tương ng là 70 USD và 50 USD. V n đ đ t ra cho công ty này là trong gi i h n v gi đóng m c và gi sơn như trên, công ty c n s n xu t bao nhiêu cái bàn và bao nhiêu cái gh là t i ưu d đem l i l i nhu n cao nh t. Gi i: Th i gian th c h i n t ng công đo n, th i gian có s n và l i nhu n đem l i cho t ng s n ph m (bàn và gh ) đư c tóm t t trong b ng sau đây: B ng 4.2. D li u c a công ty Phương Nam GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 246
  9. 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) Th i gian (gi ) S gi c n thi t đ s n xu t T ng th i g ian m t cái có đư c trong 1 tu n Công đo n Bàn Gh 1. Đóng m c 4 3 240 2. Sơn và đánh 2 1 100 bóng 70 50 L i nhu n (USD) x1 x2 S lư ng c n s n xu t G i: + x1 = S lư ng bàn s s n xu t trong 1 tu n; + x2 = S lư ng gh s s n xu t trong 1 tu n. x1 và x2 đư c g i là các bi n quy t đ nh (decision variables). 1. Hàm m c tiêu (Objective function): Maximize L i nhu n Z = 70 x1 + 50 x2 (USD) Gi i thích: 1 cái bàn thu đư c 70 USD l i nhu n nên x 1 cái bàn s thu đư c 70x 1 U SD l i nhu n; tương t , 1 cái gh thu đư c 50 USD l i nhu n nên x2 cái gh s thu đư c 50x 2 U SD l i nhu n → T ng l i nhu n Z = 70x 1 + 50x2 (USD) 2. Ràng bu c (Constraints): T ng quát, t i m i công đo n ta có: T ng s tài nguyên (s gi ) s d ng ≤ T ng s tài nguyên (s g i ) s n có: 4x1 + 3x2 ≤ 240 + G i đóng m c: (1) 2x1 + 1x2 ≤ 100 + G i sơn và đánh bóng: (2) C 2 đ i u ki n ràng bu c này th hi n gi i h n c a kh năng s n xu t c a công ty, và t t nhiên, tác đ ng đ n t ng l i nhu n. Ví d : + Công ty Phương Nam không th s n xu t 70 cái bàn vì n u như th x1 = 70, khi đó c 2 đi u ki n ràng bu c đ u không th a. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 247
  10. 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) + Tương t , công ty cũng không th s n xu t 50 cái bàn (x1 = 50) và 10 cái gh (x2 =10) vì n u th thì ràng bu c th 2 s không th a mãn. C hú ý: Chúng ta có th nh n th y m t đ c đ i m quan tr ng c a QHTT, đó là t n t i m i quan h tương tác gi a các bi n. N u công ty s n xu t nhi u s n p h m này thì bu c p h i s n xu t ít đi s n ph m còn l i. C th hơn, kh năng c a doanh nghi p b gi i h n. 3. Đi u ki n biên (Ràng bu c m c đ nh): Đ bài toán có ý nghĩa thì giá tr x1 và x2 ph i là s không âm (ràng bu c không âm), nghĩa là: x1≥ 0 (S lư ng bàn s n xu t trong 1 tu n ≥ 0) x2 ≥ 0 (S lư ng gh s n xu t trong 1 tu n ≥ 0) * Tóm l i, ta có mô hình toán c a v n đ l p k ho ch s n xu t c a công ty Phương Nam như sau: - Hàm m c tiêu: Max L i nhu n Z = 70 x1 + 50 x2 (USD) - Ràng bu c: 4x1 + 3x2 ≤ 240 (1) 2x1 + 1x2 ≤ 100 (2) x 1≥ 0 , x 2 ≥ 0 N hư v y: Bài toán có 2 bi n và 4 ràng bu c, trong đó có 2 ràng bu c m c đ nh là: x 1≥ 0 , x 2 ≥ 0 5. GI I BÀI TOÁN QUY HO C H TUY N TÍNH C C Đ I HÓA B N G PHƯƠNG PHÁP Đ TH M t trong nh ng phương pháp đ gi i q uy t các bài toán QHTT đơn gi n là dùng phương pháp đ th . Phương pháp đ th ch s d ng đ i v i bài toán QHTT đơn gi n có 2 bi n quy t đ nh. Ví d : Ch ng h n như s lư ng bàn s s n xu t x1 và s lư ng gh s s n xu t x2 trong v n đ l p k ho ch s n xu t c a công ty Phương Nam. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 248
  11. 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) K hi bài toán QHTT có nhi u hơn 2 bi n, chúng ta không th bi u di n l i gi i b ng đ th trong h t a đ ph ng 2 chi u mà ph i s d ng các phương pháp gi i khác (phương pháp đơn hình). Tuy nhiên, phương pháp đ th s giúp chúng ta hi u rõ đ ư c b n ch t c a bài toán QHTT và trên cơ s đó nghiên c u các phương pháp gi i khác. Các bư c gi i bài toán QHTT b ng phương pháp đ th : + Bư c 1: Bi u d i n các ràng bu c lên đ th + Bư c 2: Tìm nghi m t i ưu, áp d ng 1 trong 2 phương pháp sau: § Phương pháp đư ng đ ng tr § Phương pháp các đi m g c. 5.1. Bư c 1: Bi u di n các ràng bu c lên đ th Đ tìm l i gi i t i ưu cho m t b ài toán QHTT, trư c tiên chúng ta ph i xác đ nh m i n nghi m kh thi (Feasible Solution Region), còn g i là mi n th a mãn các đi u ki n ràng bu c (mi n ràng bu c). Đ th c hi n đi u này, b ư c đ u tiên ta bi u d i n t ng đi u ki n ràng bu c lên đ th . Trong ví d này, bi n x1 (s lư ng bàn s n x u t trong 1 tu n) đư c th hi n trên tr c hoành c a đ th và bi n x2 (s lư ng gh s n xu t trong 1 tu n) đư c th hi n trên tr c tung c a đ th (tuy nhiên không nh t thi t lúc nào cũng như v y, ta v n có th bi u di n ngư c l i, nghĩa là bi n x1 n m trên tr c tung và bi n x2 n m trên tr c hoành). Đ bài toán có ý nghĩa thì giá tr x1 và x2 ph i là s không âm, nghĩa là: x1≥ 0 (S lư ng bàn s n xu t s n xu t trong 1 tu n ≥ 0) x2 ≥ 0 (S lư ng gh s n xu t s n xu t trong 1 tu n ≥ 0) Khi đó, chúng ta ch làm vi c trong góc ph n tư th I c a đ th (xem hình 4.1) GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 249
  12. 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) Hình 4.1. Góc ph n tư I ch g m các giá tr không âm 4x1 + 3x2 ≤ 240 1. Ràng bu c th nh t: (1) * Cách bi u di n: - Chuy n ràng bu c b t phương trình thành d ng phương trình: 4x1 + 3x2 = 240 (1’) - Tìm 2 đi m A và B th a m ãn phương trình (1’) và v đư ng th ng n i 2 đi m đó: + Cho x1 = 0 → 4*(0) + 3*x 2 = 240 → x2 = 80 → A (x1 = 0, x2 = 80) + Cho x2 = 0 → 4* x1 + 3*(0) = 240 → x1 = 60 → B (x1 = 60, x2 = 0) - Xác đ nh mi n nghi m c a ràng bu c th nh t: Vùng phía dư i AB, ph n tô đ m c a hình 4.2. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 250
  13. 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) Hình 4.2. Bi u di n đ th cho ràng bu c th nh t (Gi i h n v Gi đóng m c) 2. Ràng bu c th hai: 2x1 + 1x2 ≤ 100 (2) * Cách bi u di n: - Chuy n ràng bu c b t phương trình thành d ng phương trình: 2x1 + 1x2 = 100 (2’) - Tìm 2 đi m C và D th a mãn phương trình (2’) và v đ ư ng th ng n i 2 đi m đó: + Cho x 1 = 0 → 2*(0) + 1*x 2 = 100 → x2 = 100 → C (x1 = 0, x 2 = 100) + Cho x2 = 0 → 2* x1 + 1 *(0) = 100 → x1 = 50 → D (x 1 = 50, x2 = 0) - Xác đ nh mi n nghi m c a ràng bu c th hai: Vùng phía dư i CD, ph n tô đ m c a hình 4.3. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 251
  14. 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) Hình 4.3: Bi u di n đ th cho ràng bu c 2 (Gi i h n v G i sơn và đánh bóng) 3. Xác đ nh mi n nghi m kh thi th a mãn c 2 ràng bu c: Ph n tô đm Chúng ta bi t r ng đ s n xu t ra bàn ho c gh thì đ u ph i tr i qua 2 công đo n đóng m c và sơn, đánh bóng. V i bài toán QHTT, chúng ta c n p h i tìm t p h p các đi m l i gi i đ ng th i th a mãn t t c các ràng bu c cùng m t lúc (simultaneously). V ì v y. 2 đư ng gi i h n ph i v trên cùng m t đ th (xem hình 4.4). Vùng tô đ m th hi n các s k t h p c a lư ng bàn và gh s n x u t đ ng th i th a mãn c 2 đ i u ki n ràng bu c v th i gian đóng m c và sơn, đánh bóng. Ta g i đó là mi n nghi m kh thi (Feasible Solution Region), g i t t là mi n kh thi. Mi n kh thi c a m t bài toán QHTT là t p h p các đi m th a mãn t t c các đ i u ki n ràng bu c c a bài toán, vì v y nó cũng chính là ph n trùng l p (che ph /ch ng lên nhau) c a t t c các đi u ki n ràng bu c. +Btc đ i m nào n m b ên trong mi n kh thi s cho ta m t nghi m kh thi (feasible solution). GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 252
  15. 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) + B t c đ i m nào n m ngoài mi n kh thi s cho ta m t nghi m không kh thi (infeasible solution). Hình 4.4. Mi n nghi m kh thi cho v n đ c a công ty Phương Nam - Ta xét 3 đi m sau đây đ minh h a. + Đ i m M (x1 = 3 0, x2 = 20), nghĩa là s n xu t 30 cái bàn và 20 cái gh trong 1 tu n. Ta có: § Th i gian đóng m c là: 4*30 + 3*20 = 180 gi < 240 gi nên th a mãn đi u ki n ràng bu c th nh t: 4x1 + 3x2 ≤ 240. § Th i gian sơn và đánh bóng là: 2*30 + 1*20 = 80 gi < 100 gi nên th a mãn đ i u ki n ràng bu c th hai: 2x1 + 1x2 ≤ 100. + Đ i m N (x1 = 70, x2 = 40), nghĩa là s n x u t 7 0 cái bàn và 40 cái gh trong 1 tu n.. Ta có: GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 253
  16. 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) § Th i gian đóng m c là: 4*70 + 3*40 = 400 gi > 240 gi nên không th a mãn đi u ki n ràng bu c th nh t: 4x1 + 3x2 ≤ 240. § Th i gian sơn và đánh bóng là: 2*70 + 1*40 = 180 gi > 100 gi nên không th a mãn đi u ki n ràng bu c th hai: 2x1 + 1x2 ≤ 100. + Đ i m P (x1 = 50, x2 = 5), nghĩa là s n xu t 50 cái bàn và 5 cái gh trong 1 tu n.. Ta có: § Th i g ian đóng m c là: 4*50 + 3*5 = 215 gi < 240 gi nên th a mãn đi u ki n ràng bu c th nh t: 4x1 + 3x2 ≤ 240. § Th i gian sơn và đánh bóng là: 2*50 + 1*5 = 105 gi > 100 gi nên không th a mãn đi u ki n ràng bu c th hai: 2x1 + 1x2 ≤ 100. Chú ý: Đ i m nào đó ch c n không th a mãn m t trong các đi u ki n ràng bu c thì đi m y cũng n m ngo ài mi n kh thi . Ch ng h n như đi m P(x1 = 50, x2 = 5) n m trong gi i h n v th i gian đóng m c nhưng l i vư t quá v th i gian sơn, đánh bóng cho phép nên đi m P cũng không n m trong mi n kh thi . 5.2. Bư c 2: Tìm nghi m t i ưu Cách 1: Phương pháp đư ng đ ng tr 5.2.1. Sau khi đ ã v mi n kh thi, chúng ta s ti n hành tìm nghi m t i ưu c a bài toán. Nghi m t i ưu là đi m n m trong mi n kh thi cho chúng ta giá tr hàm m c tiêu t t nh t (l i nhu n cao nh t). Nhưng có r t nhi u đi m trong mi n kh thi, v y chúng ta ph i làm như th nào đ tìm ra đ i m t t nh t, đi m cho ta l i nhu n cao nh t? B i vì có vô s đi m n m trong mi n kh thi c a bài toán, nên chúng ta không th dùng phương pháp th và sai (trial-and-error) đ đánh giá hàm m c tiêu c a t t c các nghi m kh thi đ x ác đ nh nghi m t i ưu. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 254
  17. 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) Có r t nhi u cách khác nhau đ tìm đư c nghi m t i ưu sau khi mi n kh thi đã đư c v trên đ th . Trong đó, m t trong nh ng cách nhanh nh t đ tìm nghi m t i ưu là ng d ng phương pháp đư ng đ ng tr (đư ng đ ng l i nhu n-isoprofit line method). Chúng ta b t đ u phương pháp b ng cách cho l i nhu n b ng 1 s b t kỳ nào đó (m t s ti n l i nhu n nh ), nghĩa là ta gán m t tr b t kỳ cho v ph i c a phương trình l i nhu n: gi s là 2100 USD. Đây là m c l i nhu n có th d dàng đ t đư c mà v n th a mãn các đi u ki n ràng bu c. Khi đó ta có hàm m c tiêu: 2.100 = 70x1 + 50x2. Phương trình đư ng th ng này đư c g i là đ ư ng đ ng l i nhu n (isoprofit line), vì nó th hi n t t c các s k t h p c a (x1, x2) cho ra l i nhu n t ng c ng là 2.100 USD. Đ v đư ng đ ng l i nhu n 2100 = 70x1 + 50x2, ta tìm 2 đ i m th a mãn phương trình và v đư ng th ng n i 2 đi m đó (gi ng như đã th c hi n cho các ràng bu c bư c 1). Tìm x 1 và x 2: + Cho x1 = 0 → 2100 = 70*(0) + 50*x2 → x2 = 42; và + Cho x2 = 0 → 210= 70*x1 + 50*(0) → x 1 = 30 Sau đó, chúng ta n i 2 đi m này b ng m t đư ng th ng. T t c m i đi m n m trên đư ng này có l i nhu n là 2.100 USD. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 255
  18. 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) Hình 4.5. Đư ng đ ng l i nhu n m c 2.100 USD D d àng nh n th y đư ng đ ng l i nhu n m c 2 .100 USD không ph i là đư ng cho ra l i nhu n cao nh t c a công ty. hình 4.6, ta c g ng v thêm 3 đư ng đ ng l i nhu n m c cao hơn. Trư c tiên ta v đư ng đ ng l i nhu n m c 2.800 USD có phương trình: 2.800 = 70x1 + 50x2 b ng cách: + Cho x 1 = 0 → 2800 = 70*(0) + 50*x2 → x2 = 56; và + Cho x2 = 0 → 2800= 70*x1 + 50*(0) → x1 = 40 Như v y, t t c các s k t h p c a (x 1, x2) n m trên đư ng đ ng l i nhu n 2800 = 70x1 + 50x2 đ u cho ra l i nhu n t ng c ng là 2.800 USD. Bây gi , chúng ta ti p t c v đư ng đ ng l i nhu n th ba mc 3.500 USD. Chúng ta nh n th y r ng càng xa g c t a đ thì thu đư c l i nhu n càng cao. M t đ c đi m quan tr ng n a là các đư ng đ ng l i nhu n đ u song song (parallel) v i nhau. Đi u này giúp chúng ta có th tìm đư c nghi m t i ưu cho bài toán. GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 256
  19. 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) 7 1 Gi i thích: Ta có: Z = 70x1 + 50x 2 ⇒ x2 = − x1 + Z = -1,4x1 5 50 + 0,02Z (3) Phương trình (3) này th hi n đ d c (h s góc) c a hàm m c tiêu thông qua x1 và x2. Trong đó, h s c a bi n x1 = -1,4 là đ d c (slope) c a đư ng th ng hàm m c tiêu; còn h s c a bi n x2 là 0,02 là giá tr ch n (intercept) c a x2, t c là giá tr c a bi n x 2 khi đư ng th ng hàm m c tiêu ng có phương trình (3) đi qua tr c x 2. Thay th các giá tr l i nhu n Z tương ng là 2100, 2800, 3500 USD, ta đư c: + K hi Z = 2100 USD: x2 = -1,4x1 + 42Z (3a) + K hi Z = 2800 USD: x2 = -1,4x1 + 56Z (3b) + K hi Z = 3500 USD: x2 = -1,4x1 + 70Z (3c) Các đư ng đ ng l i nhu n trên đ u có cùng đ d c là -1,4 nên chúng song song v i nhau. Và đư ng th ng nào cho chúng ta giá tr ch n c a x 2 càng l n thu đư c l i nhu n càng cao, nghĩa là các đư ng xa d n g c t a đ . Chúng ta v m t chu i các đư ng th ng song song b ng cách di chuy n c n th n cây thư c v song song v i phương c a đư ng đ ng l i nhu n ban đ u và d n xa g c t a đ . Đư ng l i nhu n cao nh t là đư ng cách xa g c t a đ nh t và v n có đi m chung v i mi n kh thi (đ n khi ti p xúc v i các đi m biên, ta có l i gi i t t nh t). Chúng ta nh n th y đư ng đ ng l i nhu n 4.200 USD thì quá cao (không có đi m chung v i mi n kh thi) nên không xét. Đư ng đ ng l i nhu n cao nh t đư c trình bày trong hình 4.7. Đư ng này ti p xúc v i đi m góc c a mi n nghi m t i đi m I(x1 = 30, x2= 40) và đ t l i nhu n cao nh t là Z = 70*30 + 50*40 = 4.100 USD. Trong đó đi m I (x1 = 30, x2= 40) chính là giao đi m c a 2 đư ng ràng bu c nên t a đ c u nó  4x1 + 3x 2 = 240 chính là nghi m c a h p hương trình:  . Như v y, m i  2x1 + 1x 2 = 100 GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 257
  20. 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) tu n công ty Phương Nam nên s n xu t 30 cái bàn và 40 cái gh thì s đ t c c đ i l i nhu n Z = 4.100 USD. Hình 4.6. B n đư ng đ ng l i nhu n GV. ThS. Nguy n Thanh Phong- Trư ng Đ i h c M Tp. HCM 258
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

LV.15: Bộ Đồ Án Tốt Nghiệp Chuyên Ngành Cơ Khí
65 tài liệu
2431 lượt tải
THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2