Bài giảng vận trù học

Chia sẻ: Thi Sms | Ngày: | Loại File: PDF | Số trang:11

Thêm vào BST

Báo xấu

126
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Kế toán là việc thu thập, xử lý, kiểm tra, phân tích và cung cấp thông tin kinh tế, tài chính dưới hình thức giá trị, hiện vật và thời gian lao động. Để cung cấp thông tin về kinh tế tài chính thực sự hữu dụng về một doanh nghiệp, cần có một số công cụ theo dõi những hoạt động kinh doanh hàng ngày của doanh nghiệp, trên cơ sở đó tổng hợp các kết quả thành các bản báo cáo kế toán. Những phương pháp mà một doanh nghiệp sử dụng để ghi chép và tổng hợp...

Chủ đề:

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

Lưu

Nội dung Text: Bài giảng vận trù học

− Ki m th mô hình và ñánh giá phương án tìm ñư c. Trong trư ng h p phương án tìm ñư c kéo theo các k t qu b t thư ng v m t tính toán ho c không phù h p v i th c t , c n ki m tra và ch nh s a l i mô hình, rà soát l i các s li u ñ u vào cũng như các bư c tính toán hay ch n l a phương án. Sau ñó gi i l i mô hình ñ tìm ra phương án phù h p hơn. − Tri n khai phương án tìm ñư c trên th c t . Trong toàn b quá trình ra quy t ñ nh, chuyên gia V n trù h c c n quan h ch t ch v i nhà qu n lí, gi i thích rõ ràng v tác d ng c a mô hình ñã ñ t ra. ð phương án cu i cùng ñư c tri n khai trên th c t , c n có báo cáo chi ti t giúp b máy qu n lí hi u rõ các hi u qu thi t th c mà phương án có th mang l i. Tuy nhiên, cũng c n nêu rõ các ñi u ki n ñ m b o c n thi t cũng như phân tích rõ các y u t l i nhu n/chi phí/r i ro c a phương án. 1.3. Quá trình phát tri n c a V n trù h c Nh ng ti n b nhân lo i ñ t ñư c trong vài th k v a qua và trong giai ño n hi n t i có ph n ñóng góp quan tr ng c a các phương pháp khoa h c trong vi c gi i quy t các v n ñ kinh t , xã h i. Phương pháp lu n khoa h c, trư c ñây thư ng ñư c bi t t i trong các v n ñ c a Khoa h c t nhiên, ngày nay ngày càng ñư c ng d ng r ng rãi trong các lĩnh v c c a Khoa h c qu n lí như: l p k ho ch, t ch c và ki m soát các ho t ñ ng. T hàng vài nghìn năm trư c, các ho t ñ ng ch t o và l p ráp tàu bi n t i Venice ñã ñư c t ch c m t cách khá khoa h c. Vào cu i th k XIX, Frederick W. Taylor ñã gi i quy t thành công bài toán quan tr ng c a Kĩ ngh công nghi p (Industrial Engineering) lúc ñó là ch t o ra các lo i x ng ñ khai thác các lo i qu ng khác nhau v i năng su t cao nh t. Cũng vào th i gian này, Henry L. Gantt gi i quy t thành công bài toán l p ti n trình s n xu t (Production Scheduling) khi s n ph m ñư c ch t o và hoàn thi n qua nhi u công ño n. D n d n, các nhà qu n lí m r ng các bài toán trong m t s ho t ñ ng kĩ ngh công nghi p sang các ho t ñ ng khác c a công ti như: khai thác và s d ng các ngu n nguyên li u, thuê và phát tri n nhân l c, chính sách tài chính, b t ñ ng s n... Các nhà khoa h c t nhiên, xã h i cũng b t ñ u quan tâm t i các bài toán qu n lí và nh n th c ñư c t m quan tr ng c a vi c gi i quy t v n ñ m t cách h th ng, t m quan tr ng c a các nghiên c u liên ngành bao g m khoa h c cơ b n, kĩ ngh và qu n lí. ðó cũng là kh i ngu n c a Khoa h c qu n lí. T ñ u th k XX, V n trù h c/Khoa h c qu n lí ñã ñư c áp d ng khá r ng rãi trong nhi u lĩnh v c. T i nư c Anh vào năm 1914 - 1915 F. W. Lanchester ñã xem xét các ho t ñ ng quân s m t cách ñ nh lư ng khi ñưa ra phương pháp ñánh giá s c m nh quân s thông qua s lư ng b binh và h a l c. Còn t i Mĩ lúc ñó, T. A. Edison nghiên c u và mô ph ng các ho t ñ ng h p lí c a tàu chi n trong t n công và tiêu di t các tàu ng m. Vào năm 1917, nhà bác h c ngư i ðan M ch A. K. Erlang cho công b các công trình v các ho t ñ ng h p lí trong h d ch v ñi n tho i và bưu ñi n, có tên g i t ng Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........10
quát là h th ng hàng ch (Waiting Line System). Năm 1915, Ford W. Harris công b v cách xác ñ nh dung lư ng lô hàng t i ưu trong bài toán qu n lí hàng d tr (Inventory Management). Sau ñó m t lo t công trình ñư c các tác gi khác ti p t c công b v các mô hình ki m soát hàng d tr . Các ng d ng c a lí thuy t xác su t trong ki m ñ nh ch t lư ng (Quality Control) cũng ñư c ñ c p t i trong các bài báo c a Walter Shewhart. Mô hình quy ho ch tuy n tính (Linear Programming) ñư c giáo sư ð i h c Havard Wassily Leontieff áp d ng vào nh ng năm 1930 ñ mô t và phân tích toàn b n n kinh t Mĩ. Các ng d ng c a V n trù h c trong kinh doanh l n ñ u tiên ñư c Horace C. Levinson phát tri n trong giai ño n 1920 - 1930 ñ nghiên c u các m i quan h gi a doanh thu và qu ng cáo, gi a thu nh p và ñ a ñi m sinh s ng c a ngư i tiêu dùng và các m t hàng mua s m. Sau năm 1945, V n trù h c ti p t c ñư c ng d ng ngày càng r ng rãi trong nhi u lĩnh v c. R t nhi u bài toán qu n lí ñư c gi i quy t b ng phương pháp ñơn hình (Simplex Method) do George B. Danzig ñưa ra vào năm 1947. Các mô hình m ng (Network Model) ñư c phát tri n l n ñ u vào năm 1958 v i s tr giúp c a công ti tư v n Booz, Allen và Hamilton. T i Vi t Nam, t nhi u năm trư c ñây các ho t ñ ng gi ng d y và nghiên c u v V n trù h c ñã ñư c ti n hành t i m t s cơ s ñào t o và nghiên c u như ð i h c T ng h p Hà N i, Vi n Toán h c, Vi n ði u khi n kinh t … V n trù h c ñư c ñưa vào ng d ng thành công trong m t s lĩnh v c như giao thông, th y l i, s n xu t nông nghi p và công nghi p, d ch v , qu c phòng, v i các ñóng góp c a các giáo sư Hoàng T y, Tr n Vũ Thi u, Nguy n ðình Ng c, Nguy n Quý H . ðư c thành l p vào năm 2002, T p chí ng d ng Toán h c ñã và ñang công b nhi u bài báo trong lĩnh v c V n trù h c. Ngày nay, t i nhi u nư c trên th gi i, các H i V n trù h c và các Vi n Khoa h c qu n lí ñư c thành l p, v i nhi u t p chí chuyên kh o n i ti ng. Có th gi i thi u ñây m t s t p chí qu c t như: Operations Research, Management Science, A.I.E.E. Transactions, C.O.R.S. Journal, Industrial Engineering, European Journal of Operational Research, Asia-Pacific Journal of Operational Research, Decision Sciences, Decision Support Systems. 2. CÁC NG D NG VÀ PHƯƠNG PHÁP ð NH LƯ NG CƠ B N C A V N TRÙ H C 2.1. M t s ng d ng Các ng d ng cơ b n c a V n trù h c có th ñư c phân lo i theo các l ĩnh v c sau ñây: - L p k ho ch s d ng các phương ti n, bao g m: xác ñ nh quy mô và ñ a ñi m xây d ng xí nghi p, l p k ho ch cho b nh vi n, các h th ng cung ng d ch v qu c t , xác ñ nh s lư ng phương ti n c n thi t, s p x p phương án v n chuy n, b trí kho hàng, phân công nhi m v .
- Ch t o, s n xu t: ki m soát hàng d tr , cân b ng s n xu t và ti p th , l p ti n trình s n xu t, ñ m b o n ñ nh s n xu t. - Xây d ng: phân ph i các d tr tài nguyên cho các d án, xác ñ nh s thành viên c a các ñ i công tác, duy trì ti n trình công tác, l p ti n trình d án. - ð t hàng, mua nguyên li u: chuy n giao v t li u, chính sách mua hàng và ñ t l i hàng t i ưu. - Ti p th : xác ñ nh chi phí ti p th , th i ñi m gi i thi u s n ph m m i, ch n l a danh m c s n ph m h n h p. - Tài chính: chính sách c t c, phân tích ñ u tư và ch n l a danh m c ñ u tư. - K toán: l p k ho ch lu ng ti n, chính sách tín d ng, l p k ho ch cho chi n lư c k toán n . - Chính sách nhân l c: tuy n d ng nhân viên, l p k ho ch nhân l c, l p ti n trình b i dư ng cán b , cân b ng các kĩ năng. - Nghiên c u và phát tri n: Ki m soát các d án nghiên c u và phát tri n, l p k ho ch phát tri n s n ph m m i. Chúng ta hãy xem xét m t cách chi ti t hơn v n ñ trên qua m t vài ng d ng ñi n hình c a V n trù h c/Khoa h c qu n lí như sau: - Bài toán l p k ho ch nhân l c. M t công ti c n thư ng xuyên duy trì 1000 nhân viên, trong s ñó có 70% nhân viên “cũ” (ñã làm vi c t i công ti t m t năm tr lên) và 30% nhân viên “m i” (làm vi c dư i m t năm). Theo các k t qu th ng kê có ñư c, trong s nhân viên m i thông thư ng 50% b vi c trong vòng 4 tháng ñ u, 20% b vi c trong vòng 4 tháng ti p theo, 10% b vi c trong 4 tháng k ti p và ch có 20 % không b vi c trong năm ñ u tiên vào làm vi c. Trong s nhân viên cũ, thông thư ng hàng năm có 30% b vi c (t c là kho ng 10% cho m i kì 4 tháng). V y công ti c n xác ñ nh t l tuy n nhân viên m i hàng năm như th nào ñ : i) duy trì n ñ nh ñư c lư ng lao ñ ng, ii) gi m lư ng lao ñ ng hàng năm theo m t t l ñ nh trư c, iii) tăng lư ng lao ñ ng hàng năm theo m t t l ñ nh trư c. - Bài toán phân công nhi m v . M t nhóm 3 kĩ sư A, B và C ñư c phân công hoàn thành 3 nhi m v 1, 2 và 3. C n giao cho m i kĩ sư m t nhi m v sao cho t ng s ngày công th c hi n 3 nhi m v trên là th p nh t, bi t r ng kĩ sư A có th hoàn thành các nhi m c 1, 2, 3 theo th t trong vòng 2, 6 và 3 ngày, còn s ngày như v y cho các kĩ sư B và C là 8,4, 9 và 5, 7, 8. B ng cách li t kê các phương án phân công nhi m v (có t t c 3! = 6 phương án phân công), có th tìm ñư c ngay phương án phân công t i ưu là: phân công cho kĩ sư A nhi m v 3, kĩ sư B nhi m v 2 và kĩ sư C nhi m v 1. Tuy nhiên, n u bài toán ñư c m r ng khi c n phân công 20 nhi m v cho 20 kĩ sư thì phương pháp li t kê (v i t t c là 20! ≈ 2,433×1018 phương án phân công) t ra r t kém Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........12
tác d ng. Như v y c n ph i nghiên c u m t phương pháp khác ñ gi i quy t bài toán phân công nghi m v t ng quát. 2.2. Các phương pháp ñ nh lư ng Các phương pháp ñ nh lư ng cơ b n thư ng ñư c s d ng trong V n trù h c/Khoa h c qu n lí bao g m: - Các phương pháp t i ưu gi i mô hình quy ho ch tuy n tính và phi tuy n, quy ho ch ñ ng và quy ho ch ña m c tiêu. - Các kĩ thu t/thu t toán chuyên d ng gi i các mô hình m ng như bài toán v n t i, bài toán tìm ñư ng ñi ng n nh t, mô hình m ng PERT, bài toán tìm lu ng c c ñ i. - Kĩ thu t mô ph ng gi i các mô hình hàng ch /d ch v công c ng. - Phân tích Markov ng d ng trong kinh doanh và qu n lí. - Các phương pháp ch n l a quy t ñ nh d a trên Lí thuy t quy t ñ nh và Lí thuy t trò chơi. - Các mô hình qu n lí hàng d tr . Do th i lư ng có h n, m t s phương pháp khác c a V n trù h c như các phương pháp d báo, h chuyên gia, khai phá d li u và tri th c ... không ñư c ñ c p t i trong giáo trình này. 2.3. H thông tin qu n lí Các tiêu chu n v s li u. Các phương pháp ñ nh lư ng hay kĩ thu t tính toán ñư c ñ c p trên ñây thư ng ñòi h i các s li u ñ u vào ph i ñ m b o các tiêu chu n sau: - Chính xác: s li u ph i không có sai sót. - Chi phí hi u qu : chi phí thu th p s li u th p hơn giá tr chúng có th mang l i. - C p nh t: s li u ph n ánh ñúng các ñi u ki n hi n t i. - Tin c y: s li u phát sinh k t qu không có gì b t thư ng. - D s d n g: s l i u c ó th ñ ư c s d n g thân thi n mà không ph i s a ñ i g ì thêm. Các tiêu chu n trên ñây có th có tính ch t “th a hi p”, có nghĩa là n u m t tiêu chu n nào ñó tr nên t t hơn thì cũng d n t i m t tiêu chu n khác x u ñi. Ch ng h n, chi phí l y s li u th p thư ng nh hư ng t i tính chính xác và ñ tin c y c a s li u. Tuy nhiên, năm tiêu chu n này luôn là m c tiêu c n “c c ñ i hóa” khi thu th p s li u. Khái ni m h thông tin qu n lí. Có th coi h thông tin qu n lí là m t h th ng các s li u/d li u ñư c thu th p, t ch c, phân tích, x lí và lưu tr trên máy tính/m ng máy tính dư i d ng thông tin h tr các quy t ñ nh qu n lí. ð ng d ng thành công các phương pháp ñ nh lư ng c a V n trù h c, chúng ta luôn c n thi t l p ñư c m t h thông tin qu n lí ñ t t nh m cung c p các s li u c n thi t cho mô hình toán h c c a v n ñ
c n gi i quy t. Rõ ràng r ng, các s li u thô thu th p ñư c trong bư c kh o sát th c t và phát hi n v n ñ ñư c bi n ñ i m t cách thích h p thành thông tin h tr ra quy t ñ nh. Ch ng h n, các s li u thô v h s l i nhu n c a m t lo i s n ph m ñư c bi n ñ i thành h s l i nhu n (trung bình)/ñơn v s n ph m, là m t d ng thông tin h tr vi c l p k ho ch s n xu t s n ph m này. Máy tính/m ng máy tính có r t nhi u ñi m m nh như: tính chính xác, tính nh t quán, b nh l n, x lí ñư c nhi u s li u và phép toán ph c t p, làm vi c theo các quy t c và chương trình ñ nh s n. Tuy nhiên, ñ thi t l p m t h thông tin qu n lí hi u qu , c n xác ñ nh ñư c các d ng thông tin h tr c n thi t giúp phát huy t t nh t các ưu ñi m suy lu n sáng t o và linh ho t c a ngư i ra quy t ñ nh. M t h thông tin qu n lí “nhi u máy tính quá” thư ng d n ñ n phương án có tính cơ gi i, s ph n ng thi u linh ho t và quy t ñ nh ph m vi h p. Trái l i, m t h thông tin qu n lí “nhi u tính ngư i quá” thư ng d n ñ n s ph n ng ch m ch p và s h n ch trong vi c s d ng s li u cũng như kh năng tìm ki m và ñánh giá các phương án thay th . ðây chính là các v n ñ c n chú tr ng khi các chuyên gia V n trù h c và Công ngh thông tin cùng nhau xem xét và xây d ng m t h thông tin qu n lí. H thông tin qu n lí có th ñư c phân ra ba lo i cơ b n: h th ng cho ñ u ra là các ki u báo cáo, h th ng tr l i các truy v n d ng “what - if” và h h tr ra quy t ñ nh (Decision Support System - DSS). Các h h tr ra quy t ñ nh là lo i h thông tin qu n lí hoàn thi n nh t cho phép tích h p quá trình ra quy t ñ nh tương tác ngư i - máy tính v i các cơ s d li u và các mô hình ñ nh lư ng nh m h tr tr c ti p vi c ñưa ra quy t ñ nh. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........14
Chương II M TS MÔ HÌNH VÀ PHƯƠNG PHÁP T I ƯU 1. MÔ HÌNH QUY HO CH TUY N TÍNH 1.1. Phát bi u mô hình quy ho ch tuy n tính V i m c ñích tìm hi u bư c ñ u, xét mô hình toán h c sau ñây, còn g i là mô hình quy ho ch tuy n tính hay bài toán quy ho ch tuy n tính (BTQHTT), mà trong ñó chúng ta mu n t i ưu hóa (c c ñ i hóa hay c c ti u hoá) hàm m c tiêu: z = c1x1 + c2x2 + cnxn → Max (Min), v i các ñi u ki n ràng bu c: a11x1 + a12x2 +... +a1nxn ≤ b1 a21x1 + a22x2 +... +a2nxn ≤ b2 ... am1x1 + am2x2 +... +amnxn ≤ bm x1, x2,..., xn ≥ 0 (ñi u ki n không âm). Trong trư ng h p t ng quát, BTQHTT có th bao g m các ràng bu c d ng ≥, ≤ ho c d ng =, các bi n có th có d u ≥ 0, ≤ 0 ho c d u tùy ý. Ví d 1: z = 8x1 + 6x2 → Max, v i các ràng bu c: 4x1 + 2x2 ≤ 60 2x1 + 4x2 ≤ 48 x1, x2 ≥ 0. BTQHTT trên ñây chính là m t bài toán quy t ñ nh. C n tìm các giá tr c a các bi n quy t ñ nh x1, x2 ñ các ràng bu c ñư c tho mãn và hàm m c tiêu ñ t giá tr l n nh t. Bài toán này có ý nghĩa kinh t như sau: Gi s m t xí nghi p s n xu t hai lo i s n ph m I và II. ð s n xu t ra m t ñơn v s n ph m I c n có 4 ñơn v nguyên li u lo i A và 2 ñơn v nguyên li u lo i B, các ch tiêu ñó cho m t ñơn v s n ph m lo i II là 2 và 4. Lư ng nguyên li u d tr lo i A và B hi n có là 60 và 48 (ñơn v ). B máy qu n lí c n ñưa ra quy t ñ nh nên l a ch n phương án s n xu t nào ñ tri n khai nh m ñ t l i nhu n l n nh t, bi t l i nhu n trên m i ñơn v s n ph m bán ra là 8 và 6 (ñơn v ti n t ) cho các s n ph m lo i I và II.
Phương pháp ñ th gi i BTQHTT hai bi n Phương pháp ñ th có ý nghĩa minh ho và giúp hi u b n ch t v n ñ . Bư c 1: V mi n ràng bu c/mi n các phương án kh thi, là t p h p các phương án kh thi (các phương án, n u nói m t cách ng n g n). M i phương án ñư c th hi n qua b s (x1, x2) còn g i là véc tơ nghi m, tho mãn t t c các ràng bu c ñã có (xem hình II.1). x2 30 4x1 + 2x2 = 60 1A 8 B 2x1 + 4x2 = 48 4 C O 6 15 24 x1 3 Hình II.1. Phương pháp ñ th gi i bài toán quy ho ch tuy n tính − Trư c h t chúng ta v ñ th 4x1 + 2x2 = 60 b ng cách xác ñ nh hai ñi m trên ñ th : (0, 30) và (15, 0). ð th trên là m t ñư ng th ng chia m t ph ng làm hai n a m t ph ng: m t ph n g m các ñi m (x1, x2) tho mãn 4x1 + 2x2 ≤ 60; m t ph n tho mãn 4x1 + 2x2 ≥ 60. Ta tìm ñư c n a m t ph ng tho mãn 4x1 + 2x2 ≤ 60. − Tương t , có th v ñ th 2x1 + 4x2 = 48 b ng cách xác ñ nh hai ñi m thu c ñ th (0, 12) và (24, 0). Sau ñó tìm n a m t ph ng tho mãn 2x1 + 4x2 ≤ 48. − Lúc này, giao c a hai n a m t ph ng tìm ñư c trên cho ta t p h p các ñi m (x1, x2) tho mãn hai ràng bu c ñ u tiên. Tuy nhiên, ñ tho mãn ñi u ki n không âm c a các bi n, ta ch xét các ñi m n m trong góc ph n tư th nh t. V y mi n các phương án kh thi là mi n gi i h n b i t giác OABC. Bư c 2: Trong mi n (OABC) ta tìm ñi m (x1, x2) sao cho z = 8x1 + 6x2 ñ t giá tr l n nh t. Cách 1: Dùng ñư ng ñ ng m c. Tùy theo giá tr c a x1, x2 mà z có m c giá tr khác nhau. − V ñư ng ñ ng m c: 8x1 + 6x2 = c m c c = 24, (ta có th ch n giá tr c b t kì, nhưng ch n c = 24 là b i s chung c a 6 và 8 ñ vi c tìm to ñ các ñi m c t hai tr c to ñ thu n l i hơn). Chúng ta d dàng tìm ñư c hai ñi m n m trên ñư ng ñ ng m c là (0, 4) và (3, 0). Các ñi m n m trên ñư ng ñ ng m c này ñ u cho giá tr hàm m c tiêu z = 24. Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........16
− Tương t , có th v ñư ng ñ ng m c th hai: 8x1 + 6x2 = 48 ñi qua hai ñi m (0, 8) và (6, 0). Chúng ta nh n th y, n u t nh ti n song song ñư ng ñ ng m c lên trên theo r hư ng c a véc tơ pháp tuy n n (8, 6) thì giá tr c a hàm m c tiêu z = 8x1 + 6x2 tăng lên. V y giá tr z l n nh t ñ t ñư c khi ñư ng ñ ng m c ñi qua ñi m B(12, 6) (tìm ñư c x1 = 12, x2 = 6 b ng cách gi i h phương trình 4x1 + 2x2 = 60 và 2x1 + 4x2 = 48). K t lu n: Trong các phương án kh thi thì phương án t i ưu là (x1, x2) = (12, 6). T i phương án này, giá tr hàm m c tiêu là l n nh t zmax = 8 × 12 + 6 × 6 = 132. Nh n xét: Phương án t i ưu c a bài toán trên (hay các BTQHTT khác, n u có) luôn ñ t ñư c t i m t trong các ñ nh c a mi n phương án kh thi D (là m t t p l i ña di n trong trư ng h p BTQHTT t ng quát) hay còn g i là các ñi m c c biên (chính xác hơn, mi n ñi m c c biên là ñi m thu c mi n D, mà không th tìm ñư c m t ño n th ng nào cũng thu c mi n D nh n ñi m ñó là ñi m trong). Nh n xét trên ñây là m t ñ nh lí toán h c ñã ñư c ch ng minh m t cách t ng quát trong các giáo trình môn h c T i ưu hoá. Nói m t cách hình nh, mu n ñ t ñư c phương án t i ưu cho các BTQHTT thì c n ph i “m o hi m” ñi xét các ñi m c c biên c a mi n phương án kh thi. Cách 2: T nh n xét trên, ñ tìm phương án t i ưu ta ch c n so sánh giá tr c a hàm m c tiêu t i các ñi m c c biên c a mi n phương án. Tính giá tr z t i O(0, 0): z(0, 0) = 0; t i A(0, 12): z(0, 12) = 72; t i C(15,0): z(15, 0) = 120; t i B(12, 6): z(12, 6) = 132 = Max{z(O), z(A), z(B), z(C)}. V y zmax = 132. Nh n xét: Mu n tìm phương án t i ưu c a BTQHTT ta xu t phát t m t ñi m c c biên nào ñó, tìm cách c i thi n hàm m c tiêu b ng cách ñi t i ñi m c c biên k nó. Ti p t c như v y cho t i khi tìm ñư c phương án t i ưu. Trong trư ng h p BTQHTT có phương án t i ưu thì quy trình gi i này bao g m h u h n bư c (do s ñi m c c biên là h u h n). Sơ ñ kh i B tñ u Nh p d l i u Tìm ñi m c c biên xu t phát Tìm Ki m tra Sai ñi m c c biên ñ i u ki n t i ư u k t t h ơn ðúng In và lưu tr k t qu D ng Hình II.2. Sơ ñ kh i gi i BTQHTT
ð i v i BTQHTT ñang xét, quy trình gi i ñư c minh ho như sau: → → O(0, 0) A(0,12) B(12,6) d ng → → z=0 z = 72 z = 132 → → ho c: O(0, 0) C(15, 0) B(12, 6) d ng → → z=0 z = 120 z = 132. Quy trình gi i BTQHTT t ng quát có sơ ñ kh i gi n lư c như trình bày trên hình II.2. Trong sơ ñ trên, vì m c ñích trình bày v n ñ ñơn gi n, chúng ta không ñ c p t i các trư ng h p khi BTQHTT có mi n phương án là t p r ng (lúc ñó ta không tìm ñư c phương án xu t phát) cũng như khi ta không tìm ñư c ñi m c c biên k t t hơn m c dù ñi u ki n t i ưu chưa tho mãn (lúc ñó t p các giá tr hàm m c tiêu z không b ch n). 1.2. Phương pháp ñơn hình gi i BTQHTT d ng chính t c ðây là phương pháp s gi i BTQHTT theo sơ ñ trên. ð gi i ví d 1 trên ñây, trư c h t chúng ta c n ñưa BTQHTT v d ng chính t c b ng cách thêm vào các bi n bù không âm x3 và x4 như sau: z = 8x1 + 6x2 + 0x3 + 0x4 → Max v i các ràng bu c: 4x1 + 2x2 + x3 = 60 2x1 + 4x2 + x4 = 48 x1, x2, x3, x4 ≥ 0. M t cách t ng quát, BTQHTT d ng chính t c là bài toán v i các bi n không âm, các ràng bu c v i d u “=”, h s v ph i c a các ràng bu c không âm. Ngoài ra, m i phương trình b t bu c ph i có m t bi n ñ ng ñ c l p v i h s +1. ð gi i BTQHTT d ng chính t c trên ñây, c n l p m t s b ng ñơn hình như trình bày trong b ng II.1. Trư c h t, c n ñi n s li u c a bài toán ñã cho vào b ng ñơn hình bư c 1: − C t 1 là c t h s hàm m c tiêu ng v i các bi n cơ s ñã ch n. Phương án xu t phát có th ch n là x1 = x2 = 0 (ñây chính là ñi m g c to ñ O(0, 0)), do ñó x3 = 60, x4 = 48). Như v y t i bư c này chúng ta chưa bư c vào s n xu t, nên trong phương án chưa có ñơn v s n ph m lo i I hay II ñư c s n xu t ra (ch “s n xu t” ra các lư ng nguyên li u dư th a, ta cũng nói là các “s n ph m” lo i III và IV) và giá tr hàm m c tiêu z t m th i b ng 0. Các bi n bù có giá tr l n hơn 0 có nghĩa là các nguyên li u lo i tương ng chưa ñư c s d ng h t. Ta g i các bi n x3 và x4 là các bi n cơ s vì chúng có Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........18
giá tr l n hơn 0 còn x1 và x2 là các bi n ngoài cơ s vì chúng có giá tr b ng 0. V i bài toán có hai ràng bu c, t i m i bư c ch có hai bi n cơ s . − C t 2 là c t các bi n cơ s . Trong c t 3 (c t phương án) c n ghi các giá tr c a các bi n cơ s ñã ch n. − Các c t ti p theo là các c t h s trong các ñi u ki n ràng bu c tương ng v i các bi n x1, x2, x3 và x4 c a bài toán ñã cho. B ng II.1. Các b ng ñơn hình gi i BTQHTT c1 = 8 c2 = 6 c3 = 0 c4 = 0 H s hàm m c Bi n cơ s Phương án tiêu cj x1 x2 x3 x4 0 x3 60 4 2 1 0 0 x4 48 2 4 0 1 Hàng z z0 = 0 z1 = 0 z2 = 0 z3 = 0 z4 = 0 Hàng ∆j = cj − zj ∆1 = 8 ∆2 = 6 ∆3 = 0 ∆4 = 0 1/4 8 x1 15 1 1/2 0 −1/2 0 x4 18 0 3 1 Hàng z z0 = 120 z1 = 8 z2 = 4 z3 = 2 z4 = 0 Hàng ∆j = cj − zj ∆1 = 0 ∆2 = 2 ∆3 = −2 ∆4 = 0 −1/6 1/3 8 x1 12 1 0 −1/6 6 x2 6 0 1 1/3 Hàng z z0 = 132 8 6 5/3 2/3 Hàng ∆j = cj − zj −5/3 −2/3 0 0 Phân tích b ng ñơn hình bư c 1 − H s ng v i bi n x1 trên hàng th nh t là a11 = 4 có nghĩa là t l thay th riêng gi a m t ñơn v s n ph m lo i I và m t ñơn v s n ph m lo i III là 4 (gi i thích: xét phương trình/ràng bu c th nh t 4x1 + 2x2 + x3 = 60, x1 tăng m t ñơn v thì x3 ph i gi m b n ñơn v n u gi nguyên x2). Tương t ta có th gi i thích ñư c ý nghĩa c a các h s aij khác cho trên hàng 1 và hàng 2 trong b ng ñơn hình bư c 1. − Chúng ta xét hàng z c a b ng ñơn hình. ð tính z1, c n áp d ng công th c z1 = (c t h s c a hàm m c tiêu) × (c t h s c a bi n x1) = 0×4 + 0×2 = (giá m t ñơn v s n ph m lo i III)×(t l thay th riêng lo i I/lo i III) + (giá m t ñơn v s n ph m lo i IV) × (t l thay th riêng lo i I/lo i IV) = t ng chi phí ph i b ra khi ñưa thêm m t ñơn v s n ph m lo i I vào phương án s n xu t m i = 0. Các giá tr zj, v i j = 1, 2, 3, 4, ñư c tính tương t và chính là các chi phí khi ñưa m t thêm m t ñơn v s n ph m lo i xj vào phương án s n xu t m i. Còn z0 là giá tr c a hàm m c tiêu ñ t ñư c t i phương án ñang xét: z0 = (c t h s c a hàm m c tiêu)× (c t phương án) = 0×60 + 0×48 = 0.
− Trên hàng ∆j c n ghi các giá tr ∆j, j = 1, 2, 3, 4, tính theo công th c ∆j = cj -zj = l i nhu n trên m t ñơn v s n ph m - chi phí trên m t ñơn v s n ph m. V y ∆j là "lãi biên"/m t ñơn v s n ph m khi ñưa thêm m t ñơn v s n ph m lo i j vào phương án s n xu t m i. N u ∆j > 0 thì hàm m c tiêu còn tăng ñư c khi ta ñưa thêm các ñơn v s n ph m lo i j vào phương án s n xu t m i. Có th ch ng minh ñư c ∆j chính là ñ o hàm riêng ∂z/∂xj c a hàm m c tiêu z theo bi n xj. Như v y, x1 tăng lên 1 thì z tăng lên 8 còn x2 tăng lên 1 thì z tăng lên 6. Do ∆1 và ∆2 ñ u dương nên v n còn kh năng c i thi n hàm m c tiêu khi chuy n sang (hay “xoay sang”) m t phương án c c biên k t t hơn (quay l i nh n xét ph n gi i bài toán b ng phương pháp ñ th : ñi m c c biên k c a ñi m (0, 0) có th là A(0, 12) hay C(15, 0)). Th t c xoay Bư c 1: Ch n c t xoay là c t có ∆j > 0 t c là ch n bi n xj làm bi n cơ s m i do xj tăng kéo theo hàm m c tiêu tăng. ñây ta ch n ñưa x1 vào (ñánh d u √ c t ∆1). Bư c 2: Ch n hàng xoay ñ xác ñ nh ñưa bi n nào ra kh i s bi n cơ s (vì t i m i bư c s bi n cơ s là không thay ñ i). ð ch n hàng xoay, ta th c hi n quy t c “t s dương bé nh t" b ng cách l y c t phương án (60, 48)T chia tương ng cho c t xoay (4, 2)T ñ ch n t s bé nh t. M t ñi u c n chú ý là ta ch xét các t s có m u s dương. Vì Min{60/4, 48/2} = 60/4 ñ t ñư c t i hàng ñ u, nên ta ñánh d u √ vào hàng xoay là hàng ñ u (hàng tương ng v i bi n x3). Do ñó c n ñưa x3 ra kh i các bi n cơ s . Bư c 3: Ch n ph n t xoay n m trên giao c a hàng xoay và c t xoay. Bư c 4: Xoay sang b ng ñơn hình m i, xác ñ nh các bi n cơ s m i ñ ñi n vào c t bi n cơ s , ñ ng th i thay các giá tr trong c t h s hàm m c tiêu. Sau ñó, tính l i các ph n t c a hàng xoay b ng cách l y hàng xoay cũ chia cho ph n t xoay ñ có hàng m i tương ng. Bư c 5: Các ph n t còn l i c a b ng ñơn hình m i ñư c tính theo quy t c "hình ch nh t": (1)m i = (1)cũ - (2)cũ× (4)cũ/(3)cũ, trong ñó (3) là ñ nh tương ng v i ph n t xoay (xem hình II.3). (2) (3) Ch ng h n: (1)cũ = 4, 2(cũ) = 2 (3)cũ = ph n t xoay = 4, (4)cũ = 2 ⇒ (1)m i 2 =4−2× = 3. 4 (1) (4) Hình II.3. Quy t c hình ch nh t Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........20