Nội dung

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Trịnh Bảo Ngọc ÁP DỤNG LÝ THUYẾT TRÒ CHƠI VÀ CÂN BẰNG NASH XÂY DỰNG PHƯƠNG PHÁP MÔ HÌNH HÓA XUNG ĐỘT TRONG QUẢN LÝ DỰ ÁN ĐẦU TƯ CÔNG NGHỆ THÔNG TIN VÀ THỬ NGHIỆM TRONG MỘT SỐ BÀI TOÁN ĐIỂN HÌNH LUẬN ÁN TIẾN SĨ KỸ THUẬT PHẦN MỀM Hà Nội – 2020 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI Trịnh Bảo Ngọc ÁP DỤNG LÝ THUYẾT TRÒ CHƠI VÀ CÂN BẰNG NASH XÂY DỰNG PHƯƠNG PHÁP MÔ HÌNH HÓA XUNG ĐỘT TRONG QUẢN LÝ DỰ ÁN ĐẦU TƯ CÔNG NGHỆ THÔNG TIN VÀ THỬ NGHIỆM TRONG MỘT SỐ BÀI TOÁN ĐIỂN HÌNH Ngành: Kỹ thuật phần mềm Mã số: 9480103 LUẬN ÁN TIẾN SĨ KỸ THUẬT PHẦN MỀM NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS. TS. Huỳnh Quyết Thắng Hà Nội – 2020 LỜI CAM ĐOAN Tôi cam đoan đề tài: “Áp dụng Lý thuyết trò chơi và Cân bằng Nash xây dựng phương pháp mô hình hóa xung đột trong quản lý dự án đầu tư Công nghệ thông tin và thử nghiệm trong một số bài toán điển hình” là công trình nghiên cứu của bản thân tôi, các kết quả nghiên cứu trong luận án là trung thực và chưa từng được tác giả khác công bố. Hà Nội, ngày 20 tháng 08 năm 2020 Tác giả Trịnh Bảo Ngọc Trang 1 LỜI CẢM ƠN Tôi xin bày tỏ lòng biết ơn sâu sắc nhất tới PGS.TS. Huỳnh Quyết Thắng là người định hướng và hướng dẫn khoa học, đã tận tình giúp đỡ tôi trưởng thành trong công tác nghiên cứu và hoàn thành luận án. Trong suốt quá trình học tập và nghiên cứu tại trường, tôi đã nhận được sự hướng dẫn và giúp đỡ tận tình của tập thể các thầy, cô giáo tại Viện Công nghệ thông tin và truyền thông, Trường Đại học Bách khoa Hà Nội, các thầy cô tại Phòng đào tạo, Trường Đại học Bách khoa Hà Nội. Tôi xin ghi nhận và biết ơn sự đóng góp quý báu của các thầy, cô. Tôi xin trân trọng cám ơn Ban giám hiệu Trường Đại học Hà Nội cùng các thầy cô tại trường đã tạo điều kiện về thời gian, chuyên môn và nhiều hỗ trợ khác giúp đỡ tôi thực hiện luận án. Hà Nội, ngày 20 tháng 08 năm 2020 Tác giả Trịnh Bảo Ngọc Trang 2 MỤC LỤC LỜI CAM ĐOAN…………………………………………………………………………………………………………………………………..1 LỜI CẢM ƠN……………………………………………………………………………………………………………………………………….2 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT............................................................................................ 5 DANH MỤC CÁC BẢNG ............................................................................................................................ 6 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ........................................................................................................... 7 MỞ ĐẦU .................................................................................................................................................. 8 Lý do chọn đề tài ................................................................................................................................. 8 Mục đích nghiên cứu ........................................................................................................................... 9 Nhiệm vụ nghiên cứu ........................................................................................................................ 10 Đối tượng và phạm vi nghiên cứu ..................................................................................................... 10 Phương pháp nghiên cứu .................................................................................................................. 10 Phương pháp lý thuyết .................................................................................................................. 10 Phương pháp thực nghiệm ........................................................................................................... 11 Ý nghĩa khoa học và thực tiễn của đề tài .......................................................................................... 11 Ý nghĩa khoa học ........................................................................................................................... 11 Ý nghĩa thực tiễn ........................................................................................................................... 11 Các kết quả mới đạt được ................................................................................................................. 11 CHƯƠNG 1: TỔNG QUAN ...................................................................................................................... 12 1.1 Xung đột trong quản lý dự án và một số bài toán điển hình ............................................... 12 1.1.1 Giới thiệu về quản lý dự án ............................................................................................. 12 1.1.2 Xung đột trong quản lý dự án.......................................................................................... 14 1.1.3 Các bài toán điển hình ..................................................................................................... 16 1.1.4 Phân loại xung đột trong quản lý dự án .......................................................................... 18 1.2 Lý thuyết trò chơi và cân bằng Nash.................................................................................... 20 1.2.1 Giới thiệu về Lý thuyết trò chơi ....................................................................................... 20 1.2.2 Các loại trò chơi ............................................................................................................... 22 1.2.3 Mô hình cân bằng Nash ................................................................................................... 25 1.3 Tổng quan về các thuật toán tối ưu đa mục tiêu................................................................. 27 1.3.1 Giới thiệu bài toán tối ưu đa mục tiêu ............................................................................ 27 1.3.2 Các giải thuật tiến hóa đa mục tiêu tiểu biểu.................................................................. 28 1.3.3 Đánh giá một số giải thuật MOEA tiêu biểu .................................................................... 29 1.3.4 MOEA framework và các giải thuật ................................................................................. 29 1.4 Tổng hợp và đánh giá các nghiên cứu ứng dụng lý thuyết trò chơi trong quản lý dự án ... 34 1.4.1 Tình hình nghiên cứu ngoài nước.................................................................................... 34 1.4.2 Tình hình nghiên cứu trong nước .................................................................................... 39 1.5 Tiểu kết chương .......................................................................................................................... 39 Trang 3 CHƯƠNG 2: MÔ HÌNH HÓA XUNG ĐỘT TRONG QUẢN LÝ DỰ ÁN VÀ GIẢI PHÁP ÁP DỤNG LÝ THUYẾT TRÒ CHƠI VÀ CÂN BẰNG NASH ............................................................................................................. 40 2.1 Phân tích đặc điểm xung đột và vai trò của chủ đầu tư ...................................................... 40 2.1.1 Các đặc điểm của xung đột.............................................................................................. 40 2.1.2 Lựa chọn kỹ thuật giải quyết xung đột ............................................................................ 42 2.1.3 Vai trò của chủ đầu tư trong xung đột ............................................................................ 43 2.1.4 Phân loại xung đột có và không có chủ đầu tư ............................................................... 44 2.2 Phân tích mô hình biểu diễn theo lý thuyết trò chơi ........................................................... 46 2.2.1 Các mô hình biểu diễn lý thuyết trò chơi ........................................................................ 46 2.2.2 Phân loại vấn đề theo dạng bài toán lý thuyết trò chơi .................................................. 48 2.3 Xây dựng Unified Game-Based Model mô hình hóa xung đột ............................................ 49 2.3.1 Đề xuất cấu trúc của xung đột trong mô hình ................................................................. 49 2.3.2 Đề xuất mô hình Unified Game-Based model ................................................................. 50 2.3.3 Mô tả một số bài toán điển hình về xung đột sử dụng Unified Game-Based model........... 52 2.3.4 Cân bằng Nash của xung đột ................................................................................................ 54 2.4 Tiểu kết chương .................................................................................................................... 55 CHƯƠNG 3: ỨNG DỤNG MÔ HÌNH UNIFIED GAME-BASED MODEL TRONG MỘT SỐ LỚP BÀI TOÁN ĐIỂN HÌNH ............................................................................................................................................. 56 3.1 Ứng dụng mô hình trên các giải thuật ................................................................................. 56 3.1.1 Các giải thuật lựa chọn .................................................................................................... 56 3.1.2 Phương thức thử nghiệm ................................................................................................ 57 3.2 Lớp bài toán mô hình có chủ đầu tư.................................................................................... 57 3.2.1 Bài toán đàm phán giá trong đấu thầu nhiều vòng ......................................................... 57 3.2.2 Bài toán xếp lịch thanh toán dự án ................................................................................. 68 3.3 Lớp bài toán mô hình không có chủ đầu tư ......................................................................... 80 3.3.1 Bài toán xung đột giữa các phương pháp xử lý rủi ro ..................................................... 80 3.3.2 Bài toán cân bằng nguồn lực ........................................................................................... 92 3.4 Tiểu kết chương ................................................................................................................... 99 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN MỞ RỘNG CỦA LUẬN ÁN ........................................................... 100 Kết luận ........................................................................................................................................... 100 Hướng phát triển của luận án ......................................................................................................... 102 DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN ............................................................... 103 TÀI LIỆU THAM KHẢO .......................................................................................................................... 105 PHỤ LỤC .............................................................................................................................................. 111 Phụ lục A - Thông tin đấu thầu ........................................................................................................ 111 Phụ lục B - Danh sách rủi ro ............................................................................................................ 135 Trang 4 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT Từ viết tắt CSDL DMOEA DSS EMO GA GT MOEA MOGA NE NPGA NPV NSGA NSGA-II PAES PESA PM PSP RDGA RWGA SPEA VEGA WBGA Nghĩa tiếng Anh Nghĩa tiếng Việt Dynamic Multi-Objective Evolutionary Algorithm Decision Support System Evolutionary Multi-objective Optimization Genetic Algorithm Game Theory Multiobjective Evolutionary Algorithm Multi-objective Genetic Algorithm Nash Equilibrium Niched Pareto Genetic Algorithm Net Presnet Value Nondominated Sorting Genetic Algorithm Fast Non-dominated Sorting Genetic Algorithm Pareto-Archived Evolution Strategy Pareto Enveloped-based Selection Algorithm Project Manager Payment Schedule Problem Rank-Density Based Genetic Algorithm Random Weight Genetic Algorithm Strength Pareto Evolutionary Algorithm Vector Evaluated Genetic Algorithm Weight-Based Genetic Algorithm Trang 5 Cơ sở dữ liệu Giải thuật tiến hóa đa mục tiêu động Hệ trợ giúp quyết định Tối ưu tiến hóa đa mục tiêu Giải thuật di truyền Lý thuyết trò chơi Giải thuật tiến hóa đa mục tiêu Giải thuật di truyền đa mục tiêu Cân bằng Nash Giải thuật di truyền Lỗ hổng Pareto Giá trị hiện tại dòng tiền thuần Giải thuật di truyền sắp xếp không trội Giải thuật di truyền sắp xếp không trội cải tiến Chiến lược tiến hóa Lưu trữ Pareto Giải thuật lựa chọn dựa trên Pareto Bao phủ Người quản lý dự án Vấn đề xếp lịch thanh toán dự án Giải thuật di truyền dựa trên phân bổ thứ hạng Giải thuật di truyền theo trọng số ngẫu nhiên Giải thuật tiến hóa Pareto mạnh Giải thuật di truyền dựa trên đánh giá vector Giải thuật di truyền theo trọng số DANH MỤC CÁC BẢNG Bảng 1.1: Phân tích loại bài toán xung đột [3]..........................................................17 Bảng 1.2: Nguồn của xung đột và xếp hạng theo mức độ ảnh hưởng [33] ..............19 Bảng 1.3: Nguồn gốc và các xung đột [33] ...............................................................19 Bảng 1.4: Biểu diễn trò chơi dạng chiến lược [1] .....................................................21 Bảng 1.5: Đánh giá một số giải thuật MOEA ...........................................................29 Bảng 2.1: Phân loại xung đột theo sự liên quan trực tiếp tới chủ đầu tư [33] ..........44 Bảng 2.2: Phân loại bài toán Xung đột theo loại bài toán Lý thuyết trò chơi ...........48 Bảng 3.1: Thông tin về gói thầu ................................................................................65 Bảng 3.2: Kết quả thử nghiệm các thuật toán ...........................................................67 Bảng 3.3: Lịch trình thực hiện ..................................................................................73 Bảng 3.4: Thông tin dự án của hai dự án phần mềm ................................................74 Bảng 3.5: Các tham số của các nhiệm vụ trong dự án 1 ...........................................74 Bảng 3.6: Các tham số quan hệ giữa các nhiệm vụ trong dự án 1 ............................75 Bảng 3.7: Các tham số của các nhiệm vụ trong dự án 2 ...........................................76 Bảng 3.8: Các tham số quan hệ giữa các nhiệm vụ trong dự án 2 ............................76 Bảng 3.9: Kết quả thử nghiệm từ bộ dữ liệu của dự án 1 sau 10 lần chạy ...............78 Bảng 3.10: Kết quả thử nghiệm từ bộ dữ liệu của dự án 2 sau 10 lần chạy .............79 Bảng 3.11: Các phương án xử lý rủi ro [1] ...............................................................82 Bảng 3.12: Điểm cân bằng Nash hợp lý ...................................................................87 Bảng 3.13: Thông tin về rủi ro ..................................................................................88 Bảng 3.14: Thông tin về phương pháp đối phó rủi ro ...............................................88 Bảng 3.15: Kết quả chạy các thuật toán 10 lần .........................................................90 Bảng 3.16. Dữ liệu nhân sự của dự án ......................................................................96 Bảng 3.17: Yêu cầu kỹ năng của từng dự án. ...........................................................97 Bảng 3.18: Kết quả chạy thực nghiệm trên Fictitious play, CFR, CFR+ .................98 Trang 6 DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 1.1: Các ràng buộc của quản lý dự án [1] ........................................................12 Hình 1.2: 10 lĩnh vực kiến thức của quản lý dự án [1] .............................................13 Hình 1.3: Biểu diễn trò chơi dạng mở rộng [1] .........................................................22 Hình 1.4: Trò chơi thông tin hoàn hảo [5] ................................................................24 Hình 1.5: Trò chơi thông tin không hoàn hảo [5] .....................................................25 Hình 1.6: Biểu diễn các lời giải trên không gian mục tiêu .......................................31 Hình 1.7: Biểu diễn quá trình chọn lọc trong thuật toán ε-MOEA ...........................31 Hình 1.8: Mô tả phương pháp chọn lọc trong các thuật toán MOEA hiện đại [56] .33 Hình 1.9: Mô phỏng các vectơ vị trí của một cá thể trong quần thể .........................34 Hình 2.1: Chiến lược quản lý xung đột (mô hình Thomas-Kilmann) [34] ...............42 Hình 2.2: Giải pháp thông minh trợ giúp việc ra quyết định cho người quản lý ......43 Hình 2.3: Cân bằng Nash trong Unified Game-based model ...................................52 Hình 3.1: Triển khai mô hình trên MOEA framework .............................................56 Hình 3.2: Quy trình đấu thầu [20][38] ......................................................................59 Hình 3.3: Mô hình đấu thầu nhiều vòng ...................................................................59 Hình 3.4: Quan hệ giữa các nhiệm vụ [20] ...............................................................69 Hình 3.5: Chiến lược của nhà đầu tư ........................................................................70 Hình 3.6: Chiến lược của đội ngũ phát triển .............................................................71 Hình 3.7: So sánh thời gian chạy các thuật toán của dự án 1 ...................................79 Hình 3.8: So sánh thời gian chạy các thuật toán của dự án 2 ...................................80 Hình 3.9: Xung đột giữa các phương pháp xử lý rủi ro ............................................81 Hình 3.10: Mạng dự án biểu diễn xung đột giữa các phương án đối phó rủi ro .......83 Hình 3.11: So sánh thời gian chạy giữa các thuật toán .............................................91 Hình 3.12: So sánh giá trị thích nghi của điểm cân bằng Nash tìm được .................91 Trang 7 MỞ ĐẦU Lý do chọn đề tài Theo PMBOK [1], các hoạt động kinh doanh lớn chia tách thành nhiều mảng việc, trong đó mỗi dự án thực thi một nhiệm vụ riêng biệt, được thực hiện trong một khoảng thời gian và có vai trò quan trọng trong việc thúc đẩy trạng thái của tổ chức sang một trạng thái khác với các mục tiêu đặc biệt. Trong đó, các kiến thức, kỹ năng về quản lý dự án đóng vai trò sống còn tới hoạt động dự án. Quản lý dự án là một vấn đề cốt yếu của nền kinh tế nhân loại, hầu như các hoạt động tại các tổ chức, doanh nghiệp hiện nay được tổ chức theo mô hình các dự án. Các khía cạnh trong quản lý dự án được nghiên cứu và công bố trong nhiều công trình khác nhau, nổi bật trong đó là tài liệu PMBOK được viện Quản lý dự án công bố, tuy nhiên vấn đề xung đột xảy ra trong dự án là một khía cạnh quan trọng nhưng lại chưa được đề cập và xử lý thích đáng. Xung đột trong định nghĩa của PMBOK [1] là sự khác nhau về mục tiêu và hành vi giữa hai hoặc nhiều đối tượng, sự khác nhau về mục tiêu và hành vi dẫn tới sự khác nhau về kết quả hoặc lợi ích đạt được của đối tượng. Cũng theo PMBOK, trong quản lý dự án, vấn đề xung đột xảy ra trong quá trình quản lý là đa dạng, xung đột xảy ra tại từng quá trình của quản lý dự án, những hậu quả của xung đột gây ra trong quản lý dự án là to lớn và chưa được kiểm soát thậm chí trong quá trình quản lý rủi ro. Trong một vài nghiên cứu khác nhau, có một số thống kê thú vị như: 60% thời gian của quản lý nhân sự chỉ để dành ra xử lý các xung đột, người lao động dành ra mỗi tuần 2,8 giờ để đối phó với xung đột. Con số này tương đương với thiệt hại quy đổi xấp xỉ 359 tỉ USD tiền lương (theo thống kê năm 2008 với tiền lương trung bình là 17,95 USD một giờ tại Mỹ), hoặc tương đương 385 triệu ngày làm việc [2]. Về góc độ lý thuyết, các vấn đề xung đột đã được nhắc tới trong PMBOK 6 nhiều hơn so với các phiên bản khác, cụ thể là ngoài các định nghĩa, PMBOK đã đề xuất kế hoạch quản lý xung đột, tuy nhiên các giải pháp cụ thể là không rõ ràng. Việc tìm kiếm một giải pháp kỹ thuật để mô hình hóa và giải các vấn đề xung đột một cách tổng quan là một yêu cầu cần thiết và chưa được giải quyết. Trong việc tìm hiểu các phương thức giải quyết triệt để các loại xung đột trong quản lý dự án, lý thuyết trò chơi cho thấy sự phù hợp về ý nghĩa lý thuyết và tính khả thi bằng các nghiên cứu, công bố của luận án. Lý thuyết trò chơi là một nhánh của toán học ứng dụng, nghiên cứu các tình huống chiến thuật trong đó các đối thủ lựa chọn các hành động khác nhau để cố gắng làm tối đa kết quả nhận được. Lý thuyết trò chơi được đưa ra trong những năm 50 của thế kỷ 20 bởi nhiều học giả, lý thuyết đã được áp dụng vào rất nhiều lĩnh vực khác nhau của xã hội như: sinh học, kinh tế, chính trị, công nghệ thông tin, và đóng góp nhiều vai trò quan trọng. Những năm gần đây, việc ứng dụng công nghệ thông tin đã được thúc đẩy rất nhanh, đặc biệt trong việc xây dựng các ứng dụng hỗ trợ các nghiệp vụ xã hội, kinh doanh. Có nhiều loại ứng dụng công nghệ thông tin khác nhau, trong đó ở mức độ khó và phức tạp về hỗ trợ tác nghiệp là các hệ thống thông minh trợ giúp việc ra quyết định cho các vấn đề kinh tế, xã hội. Lý thuyết trò chơi, trong các nghiên cứu hiện nay, đã đóng góp không nhỏ trong việc xây dựng mô hình lý thuyết và sản phẩm ứng dụng cho các hệ thống thông minh đó. Có rất nhiều trường đại học hoặc viện nghiên cứu hợp tác với các công ty, tổ chức có các nhóm nghiên cứu về lý thuyết trò chơi. Có thể kể tới: Game theory & computation seminar series tại Đại học Havard, Optimization and network Game theory group tại Đại học MIT, CS Theory Research group tại Đại học Pennsylvania, Stony Brook center Trang 8