Áp dụng quy hoạch tuyến tính vào lập tiến trình và điều chỉnh dự án

Nội dung text: Áp dụng quy hoạch tuyến tính vào lập tiến trình và điều chỉnh dự án

1. Vietnam J. Agri. Sci. 2021, Vol. 19, No. 11: 1499-1508 Tạp chí Khoa học Nông nghiệp Việt Nam 2021, 19(11): 1499-1508 www.vnua.edu.vn ÁP DỤNG QUY HOẠCH TUYẾN TÍNH VÀO LẬP TIẾN TRÌNH VÀ ĐIỀU CHỈNH DỰ ÁN Nguyễn Hải Thanh Khoa Quốc tế, Đại học Quốc gia Hà Nội Tác giả liên hệ: nhthanh@vnu.edu.vn Ngày nhận bài: 07.07.2021 Ngày chấp nhận đăng: 16.09.2021 TÓM TẮT Kĩ thuật đánh giá và xem xét dự án và Phương pháp đường găng là các công cụ tính toán nền tảng trong lập tiến trình và điều chỉnh các hoạt động của dự án. Tuy nhiên, ở Việt Nam, về phương diện mô hình hóa và tính toán, các công cụ trên đây còn ít được tìm hiểu, trình bày một cách hệ thống, kể cả trong đào tạo, nghiên cứu và thực tế quản lí các dự án trong lĩnh vực sản xuất - kinh doanh nông nghiệp cũng như nhiều lĩnh vực khác. Cùng với việc trình bày một số kiến thức nền tảng về Kĩ thuật đánh giá và xem xét dự án và Phương pháp đường găng, bài báo này đề xuất một cách thức áp dụng quy hoạch tuyến tính vào việc lập tiến trình dự án, xác định các hoạt động găng và đường găng của dự án, cũng như vào việc điều chỉnh rút ngắn thời lượng thực hiện các hoạt động của dự án để đẩy nhanh tiến độ dự án với tổng chi phí điều chỉnh thấp nhất. Dựa trên phương pháp mô hình hóa và tính toán khoa học, các khung thuật toán mới có áp dụng quy hoạch tuyến tính được thiết lập nhằm tới mục tiêu là hỗ trợ một cách hiệu quả cho việc phân tích và quản lí dự án với Kĩ thuật đánh giá và xem xét dự án và Phương pháp đường găng. Từ khóa: Kĩ thuật đánh giá và xem xét dự án, phương pháp đường găng, quy hoạch tuyến tính, lập tiến trình dự án, điều chỉnh dự án. Application of Linear Programming to Project Scheduling and Project Crashing ABSTRACT Program evaluation and review technique and critical path method are powerful computing tools in project scheduling and project crashing. However, in Vietnam, modeling and computing aspects of program evaluation and review technique and critical path method have not yet been considered sufficiently and systematically in university education and applied research as well as in project management of agricultural production and business and many other fields. Besides reviewing fundamental knowledge of program evaluation and review technique and critical path method, this paper proposed the application of linear programming in project scheduling for determining project’s critical activities and critical path as well as for crashing project’s activities in order to shorten project completion time with a minimum total crashing cost. As a result, utilizing the modeling method and the scientific computing method, new linear-programming-based algorithm frames were constructed for efficiently supporting project analysis and management with program evaluation and review technique and critical path method. Keywords: Program evaluation and review technique, critical path method, linear programming, project scheduling, project crashing. đþąng gëng (CPM) đþợc phát triển læn đæu cüng 1. ĐẶT VẤN ĐỀ vào nhĂng nëm 50 cûa thế kî trþĆc bći têp đoàn Kï thuêt đánh giá và xem xét dă án (PERT) Dupont cûa Hoa Kỳ, sau này đþợc tích hợp vĆi læn đæu tiên đþợc phát triển bći Hâi quân Hoa PERT và đþợc coi là một thành phæn không Kỳ trong nhĂng nëm 1950. Cý thể hĄn, vào nëm tách rąi cûa PERT (Anderson & cs., 2010; 1957, Phòng các dă án đặc biệt cûa Hâi quân Nguyễn Hâi Thanh, 2019). Trên thế giĆi, cùng Hoa Kỳ đã phát triển PERT để quân lí một dă vĆi việc phát triển các công cý quân trð dĂ liệu án phát triển tàu ngæm hät nhån. PhþĄng pháp lĆn và các công cý tính toán hiện đäi, đáp Āng 1499
2. Áp dụng quy hoạch tuyến tính vào lập tiến trình và điều chỉnh dự án nhĂng yêu cæu cûa Cuộc cách mäng 4.0, PERT tuyến tính để giâi quyết một cách đồng bộ câ hai và CPM ngày càng đþợc hoàn thiện trên phþĄng bài toán kinh điển trong quân lí dă án dăa trên diện mô hình hóa và tính toán khoa học để täo PERT và CPM: bài toán lêp tiến trình dă án và ra công cý mänh cho việc phân tích và quân trð bài toán điều chînh dă án, nhìm täo ra một một cách hiệu quâ các dă án phĀc täp vĆi các dĂ khung thuêt toán cho phép giâi quyết câ hai bài liệu đæu vào bao gồm các dĂ liệu số thông toán một cách đồng bộ, gín kết vĆi nhau. Cách thþąng và câ các dĂ liệu có tính mą và tính ngéu tiếp cên mĆi này cüng giúp cho việc giâi quyết nhiên (Gouda & cs., 2006; Hsiau & Lin, 2009; các bài toán trên đåy đþợc hoàn thiện về khía Ramadan, 2014; Wallace, 2015; Yerkezhan, cänh mô hình hòa cüng nhþ về khía cänh tính 2016). Trong nhĂng nëm gæn đåy, một số bài toán, thông qua việc áp dýng thuêt toán đĄn báo trên các täp chí chuyên ngành đã đề cêp hình để giâi quyết các bài toán quy hoäch tuyến bþĆc đæu tĆi việc áp dýng quy hoäch tuyến tính tính, là các thuêt toán đã đþợc đòng gòi trong thay vì kï thuên tính toán mäng (network Microsoft Excel Solver hay trong các phæn mềm computing) cổ điển để giâi quyết các bài toán thþĄng phèm thông dýng khác. PERT hay CPM (Wallace, 2015; Elmarbrouk, Các mýc tiếp theo cûa bài báo có nội dung 2011; Karmaker & Halder, 2017). Trong lïnh nhþ sau: Mýc 2 tổng hợp một cách hệ thống và văc sân xuçt - kinh doanh nông nghiệp, PERT ngín gọn một số kiến thĀc nền tâng về PERT và và CPM cüng đþợc nghiên cĀu và áp dýng để CPM, cüng nhþ nêu ra khung thuêt toán giâi quân lí các dă án (Duft, 1970, 1979; Fahimifard quyết bài toán tìm thąi gian hoàn thành dă án & Kehkha, 2009). sĆm nhçt, xác đðnh các hoät động gëng và đþąng Ở Việt Nam, các phþĄng pháp PERT và gëng cûa dă án cüng nhþ phát biểu bài toán CPM đþợc đþa vào các chþĄng trình, giáo trình điều chînh rút ngín thąi lþợng thăc hiện các đào täo bêc đäi học và sau đäi học cho các ngành hoät động cûa dă án để đèy nhanh tiến độ dă án kinh doanh, quân lí, tài chính, công nghệ vĆi tổng chi phí điều chînh thçp nhçt. Tiếp theo, (Nguyễn Hâi Thanh, 2005; 2019; Taha, 2007; dăa trên phþĄng pháp mô hình hòa và tính toán Anderson & cs., 2010) đồng thąi đþợc Āng dýng khoa học, Mýc 3 trình bày cách xây dăng các khá rộng rãi trong thăc tế triển khai các dă án ć khung thuêt toán mĆi nhìm tĆi mýc tiêu là giâi Việt Nam (Nguyễn Thanh Phong & Lê Thanh quyết câ hai bài toán trên thông qua việc áp Vân, 2015; Tổng Công ty Điện lăc Miền Trung, dýng quy hoäch tuyến tính để hỗ trợ một cách 2015). Tuy nhiên, hæu nhþ chþa cò các nghiên hiệu quâ cho việc phân tích và quân lí dă án vĆi cĀu, tổng kết, tài liệu chuyên ngành về việc áp PERT và CPM. Cuối cùng, Mýc 4 đþa ra các kết dýng PERT và CPM trong quân trð dă án trong luên và một số phþĄng hþĆng cho các nghiên lïnh văc sân xuçt - kinh doanh nông nghiệp. cĀu tiếp theo. Các kiến thĀc nền tâng về PERT và CPM chþa đþợc đề cêp tĆi một cách hệ thống và rõ ràng, 2. KIẾN THỨC NỀN TÂNG VỀ KĨ THUẬT đặc biệt về khía cänh mô hình hóa và tính toán ĐÁNH GIÁ VÀ XEM XÉT DỰ ÁN VÀ khoa học. PHƯƠNG PHÁP ĐƯỜNG GĂNG Vì vêy, việc däy và học quân trð dă án còn chþa chú trọng tĆi thăc hành tính toán, việc giâi 2.1. Một số thuật ngữ thông dụng và khái quyết các trþąng hợp nghiên cĀu hay quân trð dă niệm cơ bân án trong thăc tế sân xuçt - kinh doanh không sā Kĩ thuật đánh giá và xem xét dự án là tên dýng PERT hay CPM, hoặc có sā dýng vĆi các gọi đþợc dðch tÿ cým tÿ tiếng Anh Program hiểu biết không thçu đáo dén tĆi nhiều hän chế Evaluation and Review Technique, thþąng trong việc Āng dýng và nghiên cĀu các phþĄng đþợc viết tít là PERT. PERT chú trọng nhiều pháp quân trð dă án tiên tiến ć Việt Nam. nhçt tĆi yếu tố thąi gian cûa dă án, cý thể là Bài báo này có mýc tiêu là trình bày một chú trọng tĆi thąi lþợng thăc hiện các hoät cách tiếp cên mĆi, áp dýng mô hình quy hoäch động cûa dă án và thąi gian hoàn thành dă án 1500
3. Nguyễn Hải Thanh sĆm nhçt, mà không chú trọng nhiều tĆi yếu tố nhanh tiến độ dă án, PERT và CPM cüng đþợc chi phí. PERT thþąng đþợc áp dýng trong các áp dýng để tìm ra phþĄng án điều chînh dă án dă án phĀc täp, có nhiều hoät động thành phæn (project crashing) nhìm xác đðnh nhĂng hoät vĆi thąi lþợng thăc hiện cæn đþợc kiểm soát động nào trong dă án cæn đþợc điều chînh rút một cách chặt chẽ. Các dă án nhþ vêy phát ngín về mặt thąi lþợng thăc hiện sao cho tổng sinh trong nhiều lïnh văc, trong đò cò lïnh văc chi phí điều chînh dă án là thçp nhçt. nông nghiệp, đặc biệt là các dă án nghiên cĀu Có thể tìm hiểu thêm các thuêt ngĂ thông và phát triển. Phương pháp đường găng là tên dýng và các kiến thĀc nền tâng trên trong các gọi đþợc dðch tÿ cým tÿ tiếng Anh Critical Path sách giáo trình, tham khâo và tài liệu chuyên Method, thþąng đþợc viết tít là CPM. CPM là ngành (Nguyễn Hâi Thanh, 2005; 2019; Taha, să bổ sung cæn thiết cho PERT, hiện nay đþợc 2007; Anderson & cs., 2010). Đåy cüng là các tài coi là một thành phæn không tách rąi cûa liệu tham khâo cho các tiểu mýc 2.2 và 2.3. PERT. Đò là do CPM chú trọng đồng thąi câ yếu tố thąi gian và yếu tố chi phí cûa các hoät 2.2. Bài toán lập tiến trình dự án động cûa dă án. PERT và CPM đþợc sā dýng kết hợp song hành vĆi sĄ đồ mäng trong quân lí Để đĄn giân hóa vçn đề, xét một ví dý cý thąi gian dă án, tÿ đò cò tên gọi sơ đồ mạng thể có tính chçt minh họa. PERT (PERT network). Bài toán 1: Một doanh nghiệp sân xuçt - PERT và CPM là các công cý để lêp tiến kinh doanh trong lïnh văc nông nghiệp cæn thăc trình dă án một cách hiệu quâ nhçt nhìm xác hiện một dă án bao gồm 8 hoät động. Doanh đðnh thąi gian sĆm nhçt và muộn nhçt để bít nghiệp muốn áp dýng PERT và CPM để quân lí đæu, thąi gian sĆm nhçt và muộn nhçt để kết dă án nhìm xác đðnh: thąi gian hoàn thành dă thúc mỗi một hoät động cûa dă án. Xét một dă án sĆm nhçt, nhĂng hoät động nào cûa dă án là án có n hoät động, thì đối vĆi hoät động j cûa dă hoät động gëng, thąi gian sĆm nhçt và muộn án, các thąi gian trên đþợc kí hiệu một cách nhçt để kết thúc mỗi một hoät động cûa dă án. tþĄng Āng là ESj, LSj, EFj, LFj. Lúc đò, EFj – ESj Nói cách khác, doanh nghiệp muốn sā dýng = LFj – LSj = tj chính là thąi lþợng thăc hiện PERT và CPM để lêp tiến trình dă án một cách hoät động j, vĆi j = 1, 2, , n. Gọi sj = LFj – EFj = tối þu. LS – ES là độ trễ thąi gian cho phép đối vĆi j j Sau đåy là khung thuêt toán xác đðnh đþąng hoät động j. Lúc đò các hoät động cò độ trễ thąi gëng trong lêp tiến trình dă án (Nguyễn Hâi gian bìng 0 là đþợc gọi là hoạt động găng Thanh, 2019) dăa trên phþĄng pháp tính toán (critical activity) không cho phép một să chêm mạng (network computing) đang đþợc sā dýng: trễ nào về mặt thąi gian thăc hiện. Nói cách khác, nếu một trong các hoät động gëng bð thăc Bước 1: Lêp danh mýc các hoät động cûa dă hiện chêm trễ thì thąi gian hoàn thành dă án sẽ án, trong đò đối vĆi mỗi hoät động j cûa dă án bð chêm läi. Đường găng (critical path) là têp cæn chî rõ thąi lþợng thăc hiện và các hoät động hợp các hoät động gëng cûa dă án, đþợc síp xếp kề trþĆc cûa nó (là nhĂng hoät động phâi đþợc theo thĀ tă thąi gian thăc hiện. hoàn thành trþĆc khi hoät động j đþợc bít đæu thăc hiện), vĆi j = 1, 2, , 8 (Bâng 1). Nhþ vêy áp dýng PERT và CPM trong quân lí dă án cò nghïa là phâi lêp đþợc tiến trình thăc Bước 2: Phát triển quan hệ liền kề cho các hiện các hoät động dă án, hay nói ngín gọn, là hoät động cûa dă án và vẽ sĄ đồ mäng PERT lập tiến trình dự án (project scheduling), nhìm (Bâng 2 và Hình 1). xác đðnh khi nào thì một hoät động cûa dă án Để hiểu mối quan hệ liền kề là gì, có thể lçy cæn đþợc bít đæu và khi nào cæn đþợc kết thúc, ví dý: A và B đþợc nói là có mối quan hệ liền kề các hoät động nào là các hoät động gëng cæn và kí hiệu A > B vì A là hoät động kề trþĆc hoät đþợc chú trọng thăc hiện để thąi gian hoàn động B (Bâng 2), lúc này B đþợc gọi là hoät động thành dă án là sĆm nhçt có thể. Khi cæn đèy kề sau cûa A. 1501
4. Áp dụng quy hoạch tuyến tính vào lập tiến trình và điều chỉnh dự án Bâng 1. Các hoạt động của dự án, hoạt động kề trước và thời lượng thực hiện Tên hoạt động Đánh số hoạt động Hoạt động kề trước Thời lượng thực hiện (tuần) A 1 3 B 2 A 3 C 3 A 2 D 4 B 3 E 5 C 7 F 6 B, C 3 G 7 D, E 6 H 8 C 2 Bâng 2. Quan hệ liền kề Bắt đầu A B C D E F G H Kết thúc Bắt đầu > A > > B > > C > > > D > E > F > G > H > Kết thúc Hình 1. Sơ đồ mạng PERT Bước 3: Sā dýng quan hệ liền kề/sĄ đồ mäng gian hoàn thành dă án sĆm nhçt. Để thăc hiện PERT và thąi lþợng thăc hiện các hoät động cûa tính toán tiến, đối vĆi j = 1, 2, , 8, cæn thăc hiện dă án để tìm thąi gian bít đæu sĆm nhçt ESj và các tính toán theo công thĀc: thąi gian kết thúc sĆm nhçt EF cho mỗi một j ES Max EF ; EF ES t j ipred(j) i j j j hoät động j cûa dă án, vĆi j = 1, 2, , 8, bìng cách thăc hiện tính toán tiến (forward Trong đò pred(j) là têp hợp các hoät động kề computing). Giá trð lĆn nhçt trong số các giá trð trþĆc cûa hoät động j. Nếu hoät động j không có cûa thąi gian kết thúc sĆm nhçt cûa các hoät hoät động kề trþĆc thì đặt pred(j) = , và quy động không có hoät động kề sau đþợc coi là thąi þĆc ESj = 0. 1502
5. Nguyễn Hải Thanh Kết quâ thăc hiện tính toán tiến để tìm ESj gëng đþợc síp xếp theo thĀ tă thąi gian thăc và EFj, vĆi j = 1, 2, , 8, đþợc tổng hợp täi cột 2 hiện (đþợc phân ánh qua quan hệ liền kề). và cột 3 cûa Bâng 3. Bâng 3 cüng cho biết, thąi Bâng 3 cho biết các hoät động gëng cûa dă gian hoàn thành dă án sĆm nhçt là T = Max án là các hoät động A, C, E, G. Bâng 2 cho biết {EF6, EF7, EF8} = Max {9, 18, 7}= 18 (tuæn). quan hệ liền kề cûa các hoät động này, tÿ đò Bước 4: Sā dýng quan hệ liền kề/sĄ đồ mäng đþąng gëng cûa dă án đþợc xác đðnh là: A C PERT và thąi lþợng thăc hiện các hoät động cûa E G. Kết quâ tính toán BþĆc 3, BþĆc 4 và dă án để tìm thąi gian bít đæu muộn nhçt LSj BþĆc 5, nhþ đþợc tổng hợp trong bâng 3, cüng và thąi gian kết thúc muộn nhçt LFj cho mỗi đþợc thể hiện trên hình 2. Trên hình 2, vĆi mỗi một hoät động j cûa dă án, vĆi j = 1, 2, , 8, bìng hoät động cûa dă án có ghi rõ thąi lþợng thăc cách thăc hiện tính toán lùi (backward hiện, các thąi gian bít đæu sĆm nhçt và kết thúc computing) theo công thĀc sau: sĆm nhçt ghi ć ô phía trên, bên phâi, còn thąi LF Min LS ; LS LF t j isucc(j) i j j j gian bít đæu muộn nhçt và kết thúc muộn nhçt đþợc ghi ć ô phía dþĆi bên phâi. Trong đò succ(j) là têp hợp các hoät động kề sau cûa hoät động j. Nếu hoät động j không có 2.3. Bài toán điều chînh dự án hoät động kề sau thì đặt succ(j) = , và quy þĆc LFj = T. Bài toán 2: Xét Bài toán 1 ć tiểu mýc 2.2 vĆi Kết quâ thăc hiện tính toán lùi để tìm LSj thąi gian hoàn thành dă án sĆm nhçt là 18 tuæn và LFj, vĆi j = 1, 2, , 8, đþợc tổng hợp täi cột 4 đã biết. Do một số điều kiện phát sinh, doanh và cột 5 cûa bâng 3. Bâng 3 cüng cho biết, nghiệp muốn đèy nhanh tiến độ dă án bìng cách LF6 = LF7 = LF8 = T = 18. điều chînh rút ngín thąi gian hoàn thành dă án Bước 5: Tìm độ trễ sj = LSj – ESj = LFj – EFj, xuống 16 tuæn. Vêy doanh nghiệp cæn điều chînh vĆi j = 1, 2, , 8. Hoät động cò độ trễ bìng 0 là rút ngín thąi lþợng thăc hiện cûa các hoät động hoät động gëng. Đþąng gëng gồm các hoät động nào để tổng chi phí điều chînh là thçp nhçt? Bâng 3. Thời gian bắt đầu và kết thúc sớm nhất và muộn nhất của dự án Các hoạt động ES EF LS LF Độ trễ Hoạt động găng A 0 3 0 3 0 x B 3 6 6 9 3 C 3 5 3 5 0 x D 6 9 9 12 3 E 5 12 5 12 0 x F 6 9 15 18 9 G 12 18 12 18 0 x H 5 7 16 18 11 Hình 2. Kết quâ tính toán tiến và tính toán lùi trên sơ đồ mạng PERT 1503
6. Áp dụng quy hoạch tuyến tính vào lập tiến trình và điều chỉnh dự án Bâng 4. Thời lượng thực hiện và chi phí bình thường và điều chînh tối đa Hoạt động TLBT CPBT TLĐCTĐ CPĐCTĐ TLRNTĐ CPRN A 3 20 2 30 1 10 B 3 100 2 150 1 50 C 2 50 2 50 0 N/A D 3 250 3 250 0 N/A E 7 180 5 300 2 60 F 3 30 2 40 1 10 G 6 100 4 140 2 20 H 2 150 2 150 0 N/A Để thăc hiện điều chînh dă án vĆi tổng chi thuêt toán mĆi có thể đþợc đòng gòi một cách dễ phí điều chînh thçp nhçt cæn thu thêp các thông dàng để täo ra các phæn mềm chuyên dýng. Mặt tin sau: i) Chi phí thăc hiện hoät động (CPBT) khác, vĆi Microsoft Excel Solver, các BTQHTT khi thąi lþợng thăc hiện hoät động là bình phát sinh trong khung thuêt toán này có thể thþąng (TLBT); ii) Thąi lþợng thăc hiện hoät đþợc giâi quyết một cách tþĄng đối dễ dàng. động điều chînh tối đa (TLĐCTĐ) iii) Chi phí điều chînh hoät động ć mĀc tối đa (CPĐCTĐ). 3.1. Áp dụng quy hoạch tuyến tính trong Các kí hiệu sau đþợc sā dýng cho hoät động j lập tiến trình dự án cûa dă án, j = 1, 2, , 8: t = TLBT đþợc bâo đâm j Để áp dýng quy hoäch tuyến tính trong lêp vĆi chi phí dă kiến ban đæu cj = CPBT; tiến trình dă án (thông qua việc giâi Bài toán 1 t’j = TLĐCTĐ đþợc bâo đâm vĆi chi phí điều nhþ đþợc phát biểu ć tiểu mýc 2.2), một khung chînh c’j = CPĐCTĐ; thąi lþợng rút ngín tối đa thuêt toán mĆi (KTT2) để xác đðnh đþąng gëng (TLRNTĐ) Mj = tj – tj'; chi phí trên một đĄn vð sẽ đþợc xem xét. So sánh vĆi khung thuêt toán thąi lþợng rút ngín (CPRN) là Kj. Kết quâ thu (KTT1) để xác đðnh đþąng gëng ć tiểu mýc 2.2, thêp các thông tin trên đþợc tổng hợp trong KTT2 gồm 6 bþĆc tÿ 1 tĆi 6, trong đò BþĆc 1 và bâng 4, trong đò Kj đþợc tính theo công thĀc BþĆc 2 cûa KTT2 vén giĂ nguyên nhþ trong Kj = CPRN = (cj' – cj)/Mj, vĆi j = 1, 2, ., 8. KTT1, BþĆc 6 cûa KTT2 giống vĆi BþĆc 5 cûa KTT1, cñn BþĆc 3, BþĆc 4 và BþĆc 5 cûa KTT2 3. TIẾP CẬN QUY HOẠCH TUYẾN TÍNH nhþ sau: CHO LẬP TIẾN TRÌNH VÀ ĐIỀU CHỈNH Bước 3: Tìm thąi gian kết thúc, đþợc kí hiệu DỰ ÁN là xj cho hoät động j, vĆi j = 1, 2, , 8, và thąi gian hoàn thành dă án sĆm nhçt T bìng cách Mô hình quy hoäch tuyến tính có thể đþợc giâi BTQHTT sau: áp dýng để giâi quyết hai bài toán kinh điển trong quân lí dă án dăa trên PERT và CPM: bài BTQHTT1: Min (Căc tiểu hóa) z = x9, vĆi toán lêp tiến trình dă án và bài toán điều chînh các ràng buộc: dă án, nhìm täo ra một khung thuêt toán cho x1 ≥ 3; x6 ≥ x2 + 3; phép giâi quyết câ hai bài toán một cách đồng x2 ≥ x1 + 3; x6 ≥ x3 + 3; bộ, gín kết vĆi nhau. Cách tiếp cên mĆi này x3 ≥ x1 + 2; x7 ≥ x4 + 6; cüng giúp cho việc giâi quyết các bài toán trên x ≥ x + 3; x ≥ x + 6; đåy đþợc hoàn thiện về khía cänh mô hình hóa 4 2 7 5 cüng nhþ về khía cänh tính toán, thông qua việc x5 ≥ x3 + 7; x8 ≥ x3 + 2; áp dýng thuêt toán đĄn hình để giâi quyết bài x6 ≤ x9; x7 ≤ x9; x8 ≤ x9; xj ≥ 0 và nhên giá trð toán quy hoäch tuyến tính (BTQHTT). Khung nguyên, vĆi j = 1, 2, , 8; 1504
7. Nguyễn Hải Thanh Trong đò xj = thąi gian kết thúc hoät động j thuêt toán (KTT3) sẽ đþợc xem xét vĆi các bþĆc (thóa mãn điều kiện: EFj ≤ xj ≤ LFj), tÿ 1 đến 11, trong đò 6 bþĆc đæu giống nhþ trong KTT2. Điều này có nghïa rìng trþĆc khi vĆi j = 1, 2, , 8 và x9 = T. điều chînh để đèy nhanh tiến độ dă án cæn giâi Có thể thçy rìng các ràng buộc trên đåy đþợc thiết lêp dăa trên các dĂ liệu đæu vào quyết bài toán lêp tiến trình dă án vĆi các dĂ liệu trong các bâng 1 và bâng 2. Trong trþąng trong bâng 1 và bâng 2. Ngoài ra, T = x9 = Max hợp cæn điều chînh dă án vĆi tổng chi phí điều {x6, x7, x8}. PhþĄng án tối þu cûa BTQHTT1 là: chînh thçp nhçt, BþĆc 7, BþĆc 8, BþĆc 9, BþĆc x1 = 3, x2 = 9, x3 = 5, x4 = 12, x5 = 12, x6 = 12, x7 = 10 và BþĆc 11 sẽ đþợc tiến hành nhþ sau đåy. 18, x8 = 7, x9 = 18. Bước 4: Tìm thąi gian kết thúc sĆm nhçt Bước 7: Tìm thąi lþợng rút ngín cho các hoät động cûa dă án để tổng chi phí điều chînh EFj cho hoät động j, vĆi j = 1, 2, , 8 bìng cách giâi BTQHTT sau: dă án là thçp nhçt bìng cách giâi BTQHTT sau đåy (Nguyễn Hâi Thanh, 2005; 2019; Anderson BTQHTT2: Min (Căc tiểu hóa z = x1 + x2 + & cs., 2010): x3 + x4 + x5 + x6 + x7 + x8, vĆi các ràng buộc nhþ trong BTQHTT1 có bổ sung thêm một ràng buộc BTQHTT4: Min (Căc tiểu hóa) z = 10y1 + x9 = 18. 50y2 + 60y5 + 10y6 + 20y7, vĆi các ràng buộc: Có thể chĀng minh chặt chẽ về mặt toán x1 ≥ 0 + (3 – y1); x6 ≥ x2 + (3 – y6); học (xem Bổ đề 1 phæn Phý lýc) rìng phþĄng án x2 ≥ x1 + (3 – y2); x6 ≥ x3 + (3 – y6); tối þu cûa BTQHTT2 thóa mãn xj = EFj, vĆi j = 1, 2, , 8. PhþĄng án tối þu này hoàn toàn x3 ≥ x1 + (2 – y3); x7 ≥ x4 + (6 – y7); trùng vĆi phþĄng án đþợc cho trong cột 3 cûa x4 ≥ x2 + (3 – y4); x7 ≥ x5 + (6 – y7); Bâng 3. Ngoài ra có thể tính thąi gian bít đæu x5 ≥ x3 + (7 – y5); x8 ≥ x3 + (2 – y8); sĆm nhçt cûa hoät động j bìng công thĀc x6 ≤ x9; x7 ≤ x9; x8 ≤ x9; xj ≥ 0 và nhên giá trð ESj = EFj – tj, vĆi j = 1, 2, , 8. Các giá trð này trùng vĆi các giá trð cho trong cột 2 cûa bâng 3. nguyên vĆi j = 1, 2, , 8; Bước 5: Tìm thąi gian kết thúc muộn nhçt x9 = 16 (thąi gian hoàn thành dă án đþợc rút ngín tÿ 18 tuæn xuống 16 tuæn); LFj cho hoät động j, vĆi j = 1, 2, , 8 bìng cách giâi BTQHTT sau: y1 ≤ 1; y2 ≤ 1; y3 = 0; y4 = 0; y5 ≤ 2; y6 ≤ 1; y7 ≤ BTQHTT3: Max (Căc đäi hóa) z = x1 + x2 + 2; y8 = 0; x3 + x4 + x5 + x6 + x7 + x8, vĆi các ràng buộc nhþ yj ≥ 0 và nhên giá trð nguyên vĆi j = 1, 2, , 8; trong BTQHTT2. Trong đò xj = thąi gian kết thúc hoät động j, Có thể chĀng minh chặt chẽ về mặt toán y = thąi lþợng rút ngín cûa hoät động j, vĆi học (xem Bổ đề 2 phæn Phý lýc) rìng phþĄng án j j = 1, 2, , 8. tối þu cûa BTQHTT3 thóa mãn xj = LFj, for j = 1, 2, , 8. PhþĄng án tối þu này hoàn toàn trùng BTQHTT4 trên đåy đþợc phát biểu dăa trên vĆi phþĄng án đþợc cho trong cột 5 cûa Bâng 3. các dĂ liệu đæu vào cho trong bâng 1, bâng 2 và Ngoài ra có thể tính thąi gian kết thúc sĆm nhçt bâng 4. Các biến quyết đðnh tÿ y1, y2, .y8 có thể cûa hoät động j bìng công thĀc LSj = LFj – tj vĆi đþợc kí hiệu läi, một cách tþĄng Āng, là x10, j = 1, 2, , 8. Các giá trð này trùng vĆi các giá trð x11, , x17. Nhþ vêy BTQHTT4 là BTQHTT vĆi 17 cho trong cột 4 cûa bâng 3. biến quyết đðnh. PhþĄng án tối þu cûa BTQHTT4 là: x1 = 2, x2 = 5, x3 = 4, x4 = 11, 3.2. Áp dụng quy hoạch tuyến tính trong x5 = 11, x6 = 8, x7 = 16, x8 = 16, x9 = 16, y1 = 1, điều chînh dự án y2 = 0, y3 = 0, y4 = 0, y5 = 0, y6 = 0, y7 = 1, y8 = 0, Để áp dýng quy hoäch tuyến tính trong và zmin = 30. Điều đò cò nghïa rìng để điều chînh điều chînh dă án (thông qua việc giâi Bài toán 2 dă án nhìm rút ngín thąi gian hoàn thành dă nhþ đþợc phát biểu ć tiểu mýc 2.3), một khung án tÿ 18 tuæn xuống 16 tuæn, cæn rút ngín thąi 1505
8. Áp dụng quy hoạch tuyến tính vào lập tiến trình và điều chỉnh dự án lþợng thăc hiện cûa các hoät động A và G, mỗi EFj cho hoät động j, vĆi j = 1, 2, , 8, vĆi điều hoät động 01 tuæn vĆi tổng chi phí điều chînh dă kiện đã biết về thąi lþợng rút ngín cho các hoät án thçp nhçt là zmin = 1*10 + 1*20 = 30. Thąi động nhþ tìm đþợc ć BþĆc 7, bìng cách giâi lþợng thăc hiện tj cûa hoät động j sau khi điều BTQHTT sau đåy: chînh, vĆi j = 1, 2, , 8, hoàn toàn giống nhþ các BTQHTT6: Min (Căc tiểu hóa) z = x1 + x2 + giá trð đþợc cho ć cột 4 ć bâng 1 chî vĆi 02 điểm x3 + x4 + x5 + x6 + x7 + x8, vĆi các ràng buộc nhþ sai khác: t1 = 2 và t7 = 5 (trþĆc đây là 3 và 6), các trong BTQHTT5 có bổ sung thêm ràng buộc thąi lþợng thăc hiện cûa hoät động khác vén x9 = 16 (nhþ tìm đþợc tÿ BTQHTT5). giĂa nguyên: t2 = 3, t3 = 2, t4 = 3, t5 = 7, t6 = 3, PhþĄng án tối þu cûa BTQHTT6 là: t8 = 2. Cæn chú ý rìng, nếu trong BTQHTT4 ta x1 = EF1= 2, x2 = EF2 = 5, x3 = EF3 = 4, x4 = EF4 thay điều kiện ràng buộc x9 = 16 bìng điều kiện = 8, x5 = EF5 = 11, x6 = EF6 = 8, x7 = EF7 = 16, x9 = 12 chîng hän, thì BTQHTT4 không có x8 = EF8 = 6, x9 = 16, y1 = 1, y2 = 0, y3 = 0, y4 = 0, phþĄng án. y5 = 0, y6 = 0, y7 = 1, y8 = 0. Thąi gian bít đæu Thay vì sā dýng phþĄng pháp tính toán sĆm nhçt cho hoät động j đþợc tính theo công mäng (tĀc là áp dýng BþĆc 1, BþĆc 2, BþĆc 3 và thĀc ESj = EFj – tj, trong đò tj có giá trð nhþ tìm BþĆc 4 ć tiểu mýc 2.2 vĆi các giá trð tj mĆi tìm đþợc ć BþĆc 7, vĆi j = 1, 2, , 8. đþợc ć trên, j = 1, 2, , 8, chúng ta thăc hiện Bước 10: Tìm thąi gian kết thúc muộn nhçt BþĆc 8, BþĆc 9 và BþĆc 10 nhþ sau đåy: LFj cho hoät động j, vĆi j = 1, 2, , 8, vĆi điều Bước 8: Tìm thąi gian kết thúc xj cho hoät kiện đã biết về thąi lþợng rút ngín cho các hoät động j, j = 1, 2, , 8, và thąi gian hoàn thành dă động nhþ tìm đþợc ć BþĆc 7, bìng cách giâi án sĆm nhçt T, vĆi điều kiện đã biết về thąi BTQHTT sau đåy: lþợng rút ngín cho các hoät động nhþ tìm đþợc BTQHTT7: Max (Căc đäi hóa) z = x1 + ć BþĆc 7, bìng cách giâi BTQHTT sau đåy: x2 + x3 + x4 + x5 + x6 + x7 + x8, vĆi các ràng buộc BTQHTT5: Min z = x9, vĆi các ràng buộc nhþ trong BTQHTT6. nhþ trong BTQHTT4 cò bổ sung thêm các ràng PhþĄng án tối þu cûa BTQHTT6 là: x1 = LF1 buộc y1 = 1, y2 = 0, y3 = 0, y4 = 0, y5 = 0, y6 = 0, = 2, x2 = LF2 = 8, x3 = LF3 = 4, x4 = LF4 = 11, y7 = 1, y8 = 0 và bó bĆt ràng buộc x9 = 16. x5 = LF5 = 11, x6 = LF6 = 6, x7 = LF7 = 16, VĆi các dĂ liệu đæu vào cûa Bài toán 1 x8 = LF8 = 16, x9 = 16, y1 = 1, y2 = 0, y3 = 0, (Bâng 1), phþĄng án tối þu cûa BTQHTT5 hoàn y4 = 0, y5 = 0, y6 = 0, y7 = 1, y8 = 0. Thąi gian bít toàn trùng vĆi phþĄng án tối þu cûa BTQHTT4 đæu muộn nhçt cho hoät động j đþợc tính theo nhþ tìm đþợc ć trên vĆi x = T = 16. 9 công thĀc LSj = LFj – tj, trong đò tj có giá trð nhþ Bước 9: Tìm thąi gian kết thúc sĆm nhçt tìm đþợc ć BþĆc 7, vĆi j = 1, 2, , 8. Bâng 5. Thời gian bắt đầu và kết thúc sớm nhất và muộn nhất sau điều chînh Các hoạt động ES EF LS LF Thời lượng thực hiện Độ trễ Hoạt động găng A 0 2 0 2 2 0 x B 2 5 5 8 3 3 C 2 4 2 4 2 0 x D 5 8 8 11 3 3 E 4 11 4 11 7 0 x F 5 8 13 16 3 8 G 11 16 11 16 5 0 x H 6 8 14 16 2 8 1506
9. Nguyễn Hải Thanh Bước 11: VĆi giá trð đã tìm đþợc cûa thąi nhþ chþa đþợc đề cêp tĆi trong các tài liệu gian bít đæu và kết thúc sĆm nhçt và muộn chuyên ngành về PERT và CPM. nhçt sau khi điều chînh nhþ tìm thçy ć BþĆc 9 Khung thuêt toán KTT3 dăa trên mô hình và BþĆc 10, tìm độ trễ sj = LSj – ESj = LFj – EFj, quy hoäch tuyến tính sẽ là một nền tâng quan vĆi j = 1, 2, , 8. Hoät động cò độ trễ bìng 0 là trọng để tiếp týc hoàn thiện và phát triển PERT hoät động gëng. Đþąng gëng gồm các hoät động và CPM nhìm xā lí các dĂ liệu đæu vào có tính gëng đþợc síp xếp theo thĀ tă thąi gian thăc mą và ngéu nhiên. Một trong các phþĄng hþĆng hiện (đþợc phân ânh qua quan hệ liền kề). cho các nghiên cĀu lí thuyết và Āng dýng tiếp Bâng 5 cho biết các hoät động gëng cûa dă theo là câi tiến KTT3 nhìm mýc đích phån tích án sau khi điều chînh là các hoät động A, C, E, G. và quân trð các dă án vĆi thąi lþợng thăc hiện Dăa trên quan hệ liền kề cûa các hoät động này các hoät động dă án là các dĂ liệu có tính mą. (xem Bâng 2), đþąng gëng cûa dă án sau khi điều chînh đþợc xác đðnh là: A C E G. TÀI LIỆU THAM KHÂO Anderson D.R., Sweeney D.J., Williams T.A., Camm 4. KẾT LUẬN J.D., Cochran J.J., Fry M.J. & Ohlmann J.W. th Bài báo đã trình bày một cách hệ thống và (2010). Quantitative methods for business (12 edit.). South-Western, Cengage Learning. ngín gọn kiến thĀc nền tâng về PERT và CPM, Duft K.D. (1970). PERT Time/Cost: An Aid to cüng nhþ phát biểu khung thuêt toán KTT1 Agribusiness Management. E-book, Coop. Ext. gồm 05 bþĆc nhìm xác đðnh các hoät động gëng, Serv., Coll. Agric., Wash. St. University. đþąng gëng và thąi gian hoàn thành dă án sĆm Duft K.D. (1979). Principles of management in nhçt. Bài báo cüng đề xuçt 02 khung thuêt toán agribusiness. Reston Pub. Co. mĆi KTT2 và KKT3. Bài toán 1 (lêp tiến trình Elmarbrouk O.M. (2011). A Linear Programming dă án) cüng nhþ Bài toán 2 (điều chînh dă án) Technique for the Optimization of the Activities in Maintenance Projects. International Journal nhþ đþợc trình bày trong bài báo này chî là of Engineering & Technology IJET-IJENS. nhĂng ví dý có tính minh họa nhìm trình bày 11(1): 24 -29. vçn đề dễ dàng và trăc quan hĄn thay vì trình Fahimifard S.M. & Kehkha A.A. (2009). Application bày các bài toán tổng quát. Có thể nhên thçy of Project Scheduling in Agriculture (Case Study: KTT2 có mýc đích giâi quyết Bài toán 1 (xem Grape Garden Stabilization). American-Eurasian J. Agric. & Environ. Sci. 5(3): 313-321. tiểu mýc 2.2) và gồm 6 bþĆc đæu tiên cûa KTT3. Gouda A., Monhor D. & Szántai T. (2006). Stochastic Trong khi đò, KTT3 gồm 11 bþĆc đþợc xây dăng Programming Based PERT Modeling. In: Coping nhìm mýc đích giâi quyết câ hai bài toán: Bài with Uncertainty. Lecture Notes in Economics and toán 1 và Bài toán 2 (xem tiểu mýc 2.3). Nhþ Mathematical Systems. 581: 241-255. Springer, vêy, kết quâ chính cûa nghiên cĀu là đã xåy Berlin, Heidelberg. DOI: 10.1007/3-540-35262-7_14. dăng đþợc khung thuêt toán KKT3, một công cý Hsiau H.J. & Lin C.W.R. (2009). A fuzzy pert mänh trong lêp tiến trình dă án và điều chînh approach to evaluate plant construction project scheduling risk under uncertain resources capacity. để đèy nhanh tiến độ dă án vĆi tổng chi phí điều Journal of industrial engineering and management. chînh thçp nhçt dăa trên việc áp dýng mô hình 2(1): 31-47. quy hoäch tuyến tính täi BþĆc 3, BþĆc 4, BþĆc 5, Karmaker C.L. & Halder P. (2017). Scheduling Project BþĆc 7, BþĆc 8, BþĆc 9 và BþĆc 10. Trong đò, Crashing Time Using Linear Programming ngoäi trÿ việc áp dýng mô hình quy hoäch tuyến Approach: Case Study. International Journal of tính ć BþĆc 7 đã đþợc đề cêp tĆi tÿ trþĆc, việc áp Research in Industrial Engineering. 6(4): 283-292. dýng mô hình quy hoäch tuyến tính ć các bþĆc Nguyễn Hải Thanh (2005). Toán ứng dụng (Giáo trình sau đại học). Nhà xuất bản Đại học Sư phạm, khác chþa đþợc đề cêp tĆi trong các sách dùng Hà Nội. làm giáo trình hay tài liệu tham khâo cho các Nguyễn Hải Thanh (2019). Các phương pháp định chþĄng trình đào täo đäi học và sau đäi học, và lượng trong quản lí và kinh doanh (Bài giảng sau theo nhĂng thông tin chúng tôi ním đþợc, hæu đại học). Khoa Quốc tế, Đại học Quốc gia Hà Nội. 1507
10. Áp dụng quy hoạch tuyến tính vào lập tiến trình và điều chỉnh dự án Nguyễn Thanh Phong & Lê Thanh Vân (2015), Phương HĄn nĂa, yE là phþĄng án tối þu duy nhçt pháp định lượng trong quản lí kinh doanh và dự án E xây dựng. Nhà xuất bản Xây dựng, Hà Nội. cûa BTQHTT2. Giâ sā x = (x1, x2, , x8, x9) là Ramadan M.R. (2014). Fuzzy PERT for project phþĄng án tối þu cûa BTQTTT2, ta sẽ chî ra rìng management. International Journal of Advances in (x1, x2, , x8, x9) ≡ (EF1, EF2, , EF8, T), tĀc là Engineering & Technology. 7(4): 1150-1160. xj = EFj vĆi j = 1, 2, , 8 và x9 = T = 18. Thêt vêy, Taha A.H. (2007). Operations research: an introduction nếu trái läi, tồn täi một chî số j Є {1, 2, , 8} sao (8th edit.). Pearson Education, Inc. and Dorling Kindersley Publishing Inc. cho xj EFj. Nếu xj EFj thì tồn täi một chî số i Є {1, 2, , 8} INVEST: Ứng dụng phương pháp PERT để lập và sao cho xi LF1 + LF2 + + LF8. Lúc đò tồn täi ít Chứng minh: nhçt một chî số j sao cho xj > LFj, đåy là điều vô TrþĆc hết dễ thçy mọi phþĄng án cûa lí, vì nhþ đã biết ć trên: các phþĄng án tối þu BTQHTT2 là phþĄng án tối þu cûa BTQHTT1. cûa BQQHTT1 đều thóa mãn EFj ≤ xj ≤ LFj, vĆi E Kí hiệu vector y = (EF1, EF2, , EF8, T) vĆi j = 1, 2, , 8. T = 18 và EF là thąi gian kết thúc sĆm nhçt j HĄn nĂa, yE là phþĄng án tối þu duy nhçt hoät động j cûa dă án, j = 1, 2, , 8. Dễ thçy, yE cûa BTQHTT3. Giâ sā xE = (x , x , , x , x ) là là phþĄng án cûa BTQHTT2. Ta đi chĀng minh 1 2 8 9 phþĄng án tối þu cûa BTQTTT3, ta sẽ chî ra yE cüng là phþĄng án tối þu cûa BTQHTT2. Bći E rìng (x1, x2, , x8, x9) ≡ (LF1, LF2, , LF8, T), tĀc nếu trái läi, gọi x = (x0, x1, x2, , x8, x9) là là xj = LFj vĆi j = 1, 2, , 8 và x9 = T = 18. Thêt phþĄng án tối þu cûa BTQHTT2 thì x1 + x2 + vêy, nếu trái läi, tồn täi một chî số j Є {1, 2, , 8} + x8 LF thì đåy là điều vô nhçt một chî số j sao cho xj LFi do LF1 + LF2 + + LF8 = j = 1, 2, , 8. x1 + x2 + + x8, và đåy cüng là điều vô lí. 1508