Á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ệ..

Nội dung tài liệu: Á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ệ..

1. 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 TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT PHẦN MỀM Hà Nội - 2020
2. Công trình được hoàn thành tại: Trường Đại học Bách khoa Hà Nội Người hướng dẫn khoa học: PGS.TS. Huỳnh Quyết Thắng Phản biện 1: PGS.TS. Nguyễn Hữu Quỳnh Phản biện 2: PGS.TS. Nguyễn Long Giang Phản biện 3: TS. Nguyễn Duy Phương Luận án được bảo vệ trước Hội đồng đánh giá luận án tiến sĩ cấp Trường họp tại Trường Đại học Bách khoa Hà Nội Vào hồi giờ, ngày tháng năm Có thể tìm hiểu luận án tại thư viện: 1. Thư viện Tạ Quang Bửu - Trường ĐHBK Hà Nội 2. Thư viện Quốc gia Việt Nam
3. MỞ ĐẦU Lý do chọn đề tài 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, xung đột xảy ra tại từng quá trình của quản lý dự án, hậu quả của xung đột gây 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. 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]. 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. Lý thuyết trò chơi (GT) 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. Các nghiên cứu về lý thuyết trò chơi được chia thành các hướng chủ yếu như sau: ▪ Nghiên cứu về thuật toán giải quyết một bài toán con của lý thuyết trò chơi: trò chơi thông tin không hoàn hảo, hoặc trò chơi tổng khác không [3, 4, 5] ▪ Nghiên cứu cách áp dụng mô hình lý thuyết trò chơi vào các mục đích xã hội, kinh tế: chính trị, chống khủng bố, thiên tai bão lụt, xã hội [4, 6, 7, 8, 9, 10] ▪ Nghiên cứu cách áp dụng mô hình lý thuyết trò chơi vào quản lý dự án: phân tích rủi ro, phân công nhiệm vụ việc, hợp tác, phân phối tài nguyên, lựa chọn dự án [11, 12, 13, 14, 15, 16, 17, 18, 19] ▪ Áp dụng lý thuyết trò chơi vào một số lĩnh vực công nghệ thông tin khác như: bảo mật, an ninh mạng, truyền dẫn dữ liệu, mạng xã hội [15, 20] Trong đó các hướng nghiên cứu về sự liên quan giữa Lý thuyết trò chơi và Quản lý dự án mới dừng lại ở góc độ một số bài báo chuyên sâu phân tích một vài giải pháp dùng lý thuyết trò chơi hoặc cân bằng Nash ở trong một số bài toán nhỏ. Từ việc tìm hiểu các công bố quốc tế cho thấy về lĩnh vực nghiên cứu này đang tồn tại hai vấn đề chính, đầu tiên đó là chưa có một nghiên cứu tổng quan về đặc điểm của tất cả các bài toán xung đột trong Quản lý dự án, thứ hai đó là vẫn còn nhiều vấn đề xung đột có thể chuyển đổi sang mô hình của Lý thuyết trò chơi mà vẫn chưa được nghiên cứu. Vì vậy luận án khai phá giải pháp áp dụng Lý thuyết trò chơi vào trong một số vấn đề của Quản lý dự án và có thử nghiệm trên một số dự án đầu tư Công nghệ thông tin. Mục đích nghiên cứu Mục tiêu chung của đề tài đó là nghiên cứu việc ứng dụng Lý thuyết trò chơi trong việc trợ giúp ra quyết định để giải quyết các một số các xung đột trong Quản lý dự án chưa được khai phá. Để thực hiện, đề tài có các mục tiêu cụ thể như sau: ▪ Đánh giá thực trạng nghiên cứu hiện nay về xung đột trong quản lý dự án nhằm đưa ra giải pháp phù hợp để trợ giúp việc ra quyết định giải quyết xung đột ▪ Đề xuất mô hình hóa một số xung đột chưa được nghiên cứu để đưa về giải quyết bằng các thuật toán tối ưu đa mục tiêu phù hợp ▪ Thực hiện việc thử nghiệm và đánh giá đối với mô hình Trang 1
4. Nhiệm vụ nghiên cứu Với mục tiêu đặt ra ở trên, nhiệm vụ nghiên cứu của đề tài bao gồm: ▪ Tìm hiểu và đánh giá các công trình nghiên cứu trong và ngoài nước có liên quan đến đề tài luận án ▪ Phân tích các đặc điểm, phân loại của xung đột, các trường hợp cụ thể xảy ra xung đột trong quản lý dự án ▪ Phân tích và đề xuất mô hình biểu diễn chung cho toàn bộ các xung đột trong quản lý dự án dưới dạng lý thuyết trò chơi ▪ Áp dụng mô hình biểu diễn chung cho các bài toán cụ thể và thử nghiệm ▪ Phân tích và đánh giá việc áp dụng các thuật toán vào mô hình bài toán Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của đề tài là vấn đề xung đột trong các dự án đầu tư Công nghệ thông tin có quy mô trung bình trở lên. Đề tài nghiên cứu các kiến thức thuộc về lý thuyết trò chơi và cân bằng Nash, cách áp dụng trong việc mô hình hóa các bài toán. Đề tài nghiên cứu mô hình chung của các vấn đề xung đột, tiếp theo đó là lựa chọn ra bốn bài toán khác nhau thuộc các lĩnh vực khác nhau đó là: xếp lịch thanh toán dự án, đấu thầu nhiều vòng, cân bằng nguồn và vấn đề phương pháp xử lý rủi ro. Bốn vấn đề này sẽ mở đường cho các nghiên cứu tương tự khác trong Quản lý dự án. Ý nghĩa khoa học và thực tiễn của đề tài Ý nghĩa khoa học Đề tài phân tích và hệ thống hóa lớp các xung đột trong Quản lý dự án. Đồng thời, luận án đã góp phần bổ sung, làm phong phú cơ sở lý luận khoa học trong việc đưa ra giải pháp cho các xung đột trong Quản lý dự án. Giải pháp này bao gồm mô hình lý thuyết chung theo Lý thuyết trò chơi và giải pháp xử lý tìm kiếm điểm cân bằng Nash. Ý nghĩa thực tiễn Kết quả nghiên cứu là tài liệu có giá trị tham khảo đối với các doanh nghiệp và tổ chức có thực hiện Quản lý dự án, đồng thời cung cấp công cụ hỗ trợ ra quyết định dành cho các vấn đề xung đột nếu xảy ra. Các kết quả mới đạt được Những đóng góp mới của nghiên cứu bao gồm: ▪ Đề xuất mô hình Unified Game-based model trên cơ sở lý thuyết trò chơi và cân bằng Nash để mô hình hoá xung đột trong Quản lý dự án ▪ Thử nghiệm đánh giá hiệu quả của các giải thuật di truyền trong tìm kiếm cân bằng Nash cho từng 4 bài toán điển hình xung đột trong thanh toán dự án, xung đột trong đấu thầu nhiều vòng (mô hình có chủ đầu tư) và xung đột giữa các phương pháp xử lý rủi ro, xung đột trong cân bằng nguồn lực (mô hình không có chủ đầu tư) Cấu trúc luận án Luận án bao gồm 3 chương, trong đó chương 1 giới thiệu tổng quan các lĩnh vực kiến thức liên quan tới đề tài. Chương 2 phân tích các đặc điểm của các bài toán xung đột, giới thiệu mô hình Unified Game-based model cho các bài toán xung đột dựa theo lý thuyết trò chơi. Chương 3 sẽ áp dụng mô hình trên vào 4 bài toán và kết quả thực nghiệm để đưa ra điểm cân bằng Nash cho bài toán nhằm cải tiến việc ra quyết định. Trang 2
5. CHƯƠNG 1: TỔNG QUAN 1.1 Xung đột trong Quản lý dự án và một số bài toán điển hình 1.1.1 Giới thiệu về Quản lý dự án Quản lý dự án là sự áp dụng một cách phù hợp các kiến thức, kỹ năng, công cụ và kỹ thuật vào trong quá trình đề xuất dự án, lập kế hoạch dự án, thực hiện dự án, theo dõi giám sát dự án và kết thúc dự án để đạt được các yêu cầu của dự án. Chất lượng của dự án phụ thuộc vào các ràng buộc như trong Hình 1.1. Thời gian hoàn thành Chất lượng Chi phí Phạm vi dự án (tiền, dự án nhân sự) Hình 1.1: Các ràng buộc của Quản lý dự án [1] 1.1.2 Xung đột trong Quản lý dự án PMBOK đưa ra có 5 kỹ thuật giải quyết xung đột [1]: ▪ Avoiding / Withdrawing: né tránh hay chấp nhận một xung đột ▪ Smoothing / Accommodating: nhấn mạnh vào những điểm đồng thuận ▪ Compromising / Reconcile: thỏa hiệp, hòa giải, đây là kỹ thuật giải quyết xung đột khiến hai bên đều phải thua ▪ Forcing / Directing (win - lose): PM dùng quyền lực để ép giải quyết ▪ Confrontation / Collaborating: hợp tác, mô hình các bên đều hài lòng 1.1.3 Các bài toán điển hình Có thể liệt kê một số bài toán về xung đột trong Quản lý dự án điển hình đã được công bố bao gồm: a. Trong [11], Brent Lagesse (2006) đề cập về xung đột giữa các đối tượng được phân công nhiệm vụ, và xung đột giữa đối tượng đó với đặc thù của nhiệm vụ b. Trong [12], Birgit Heydenreich et al. nghiên cứu xung đột giữa các agent trong mô hình chung của bài toán xếp lịch c. Trong [13], Piotr Skowron, Krzysztof Rzadca (2014) nghiên cứu mô hình lý thuyết trò chơi của các yếu tố ảnh hưởng bài toán xếp lịch [25] d. Trong [14], DENG Ze-min et al (2007) phân tích và lập mô hình cân bằng Nash cho bài toán xếp lịch thanh toán dự án e. Trong [15], Walid Saad et al. (2010) đề cập tới bài toán xử lý xung đột và hợp tác về các ảnh hưởng trong việc quản trị các rủi ro về bảo mật f. Trong [28], Azin Shakiba Barough (2015) đề cập tới việc ứng dụng lý thuyết trò chơi trong việc giải quyết xung giữa các nhóm, tổ chức tham gia dự án xây dựng Trang 3
6. g. Trong [29], Mojtaba Moradi và cộng sự (2018) đề xuất việc xử lý xung đột của các ràng buộc về tài nguyên trong xếp lịch dự án h. Trong [30], Guangdong Wu (2018), đánh giá mô hình ra quyết định cho xung đột giữa chủ đầu tư và nhà thầu trong dự án xây dựng i. Trong [31], Marian W. Kembłowski et al (2019) phân tích bài toán đầu thầu trong xây dựng giữa 2 công ty về giá thành, điều kiện chính trị j. Trong [32], Mahendra Piraveenan (2019) đã có những nghiên cứu kỹ về mặt lý thuyết khi trích dẫn và phân tích tới rất nhiều các bài báo liên quan tới chủ đề ứng dụng lý thuyết trò chơi trong quản lý dự án Bảng 1.1: Phân tích loại bài toán xung đột [3] Nghiên Xung đột từ nội tại / Số lượng tác nhân Tác nhân xảy ra xung đột cứu bên ngoài của xung đột a Nội tại Nhiều Các thành viên của dự án b Nội tại Nhiều Các tác nhân được xếp lịch c Nội tại Nhiều Các tiêu chí xếp lịch d Nội tại 2 Chủ đầu tư và nhà thầu e Nội tại Nhiều Các bộ phận của dự án f Nội tại Nhiều Các bộ phận của dự án g Nội tại Nhiều Các ràng buộc về xếp lịch h Nội tại 2 Chủ đầu tư và nhà thầu i Nội tại và bên ngoài 2 Chủ đầu tư và nhà thầu 1.1.4 Phân loại xung đột trong Quản lý dự án Nguyên nhân và ví dụ xung đột được sắp xếp theo mức độ ảnh hưởng [33]: Bảng 1.3: Nguồn gốc và các xung đột Nguồn gốc Mô tả xung đột Sắp xếp kế hoạch Giữa các điều kiện xếp lịch thực hiện dự án Lịch thanh toán dự án Giữa kế hoạch và các hoạt động Quản lý dự án khác Giữa các thay đổi dự án Xác định mức độ Phân công thực hiện tác vụ ưu tiên thực hiện Giữa các yếu tố ràng buộc của tác vụ dự án tác vụ dự án Mức độ ưu tiên của từng loại nhiệm vụ Triển khai các phương pháp xử lý rủi ro Các nguồn lực Phân công vai trò thực hiện dự án và năng lực Phân bổ nguồn lực dự án Đấu thầu nhiều vòng Đấu thầu Các vấn đề kỹ Giữa các kênh liên lạc thuật Giữa độ phức tạp công nghệ và thời hạn hoàn thành dự án Giữa năng lực nhân viên và công nghệ dự án Giữa công nghệ và quá trình đào tạo Thủ tục hành Giữa các phương thức Quản lý dự án chính Giữa các nhiệm vụ của bộ phận thực hiện dự án Quy trình thực hiện dự án và tốc độ thực hiện dự án Giữa các chuẩn áp dụng dự án Vấn đề cá nhân Giữa các mục tiêu của nhà đầu tư Trang 4
7. Giữa ban quản lý và các thành viên thực hiện dự án Giữa các thành viên dự án Giữa kinh nghiệm dự án và chi phí trả lương thành viên Chi phí Phân bổ chi phí dự án Quản trị tài chính và các thay đổi của dự án Quản trị tài chính và chất lượng dự án Quản trị tài chính và đào tạo nguồn lực nhân sự dự án 1.2 Tổng quan về lý thuyết trò chơi và cân bằng Nash 1.2.1 Giới thiệu về Lý thuyết trò chơi Biểu diễn trò chơi dạng chiến lược (hoặc là dạng chuẩn tắc): là hình thức biểu diễn ma trận thưởng phạt cho các tình huống của người chơi. Dạng chiến lược của một trò chơi là một bộ dữ liệu 〈 , ( 푖)푖∈ , ( 푖)푖∈ 〉, trong đó [35]: N là tập người chơi, Ai là tập chiến lược của người chơi i, ∶= {( | = 푖 ∈ 푖, ∀푖 ∈ )} là tập các chiến lược, 푖: → 푅 là hàm payoff cho người chơi i, trong đó ( 1, , 푛) → 푖( 1, , 푛). Trong đó hàm payoff có thể là lợi nhuận (để tối đa hóa) hoặc là chi phí (để tối thiểu hóa). Ngoài ra cách khác để biểu diễn tập chiến lược là: ( 푗)푗∈ = ( 1, , 푛) = ( 푖, −푖), trong đó, −푖 = ( 푗)푗∈ ,푗≠푖 là chiến lược của các người chơi khác i. Biểu diễn trò chơi dạng mở rộng: sử dụng một cây trò chơi, là dạng biểu đồ cho biết lựa chọn này được thực hiện tại thời điểm khác nhau tương ứng với một nút. 1.2.2 Các loại trò chơi ▪ Trò chơi đồng thời và trò chơi tuần tự. ▪ Trò chơi đối xứng và bất đối xứng ▪ Trò chơi có tổng bằng không và trò chơi có tổng khác không ▪ Trò chơi thông tin hoàn hảo ▪ Trò chơi thông tin không hoàn hảo ▪ Trò chơi hợp tác ▪ Trò chơi không hợp tác 1.2.3 Mô hình cân bằng Nash Nhà khoa học John Nash năm 1950 đã định nghĩa: tập chiến lược được lựa chọn ∗ ∗ ∗ ( 1, 2, , 1) là cân bằng Nash nếu không người chơi nào hưởng lợi từ việc thay đổi chiến lược trong khi những người chơi khác giữ nguyên chiến lược họ đang chọn [35]. ∗ ∗ ∗ ∀푖, 푖 ∈ 푖: 푖( 푖 , −푖) ≥ 푖( 푖, −푖) (1.1) Tương ứng với đó, phương án lựa chọn tốt nhất là: ∗ ∗ ∗ 푖( −푖): = { 푖 ∈ 푖| 푖( 푖 , −푖) = max 푖( 푖, −푖)} (1.2) 푖∈ 푖 Và đồng thời, trong điểm cân bằng Nash, mọi người chơi sẽ chọn phương án tốt nhất: ∗ 푖 ∈ 푖( −푖), ∀푖 ∈ (1.3) ∗ ∗ Trong đó, nếu gọi 푖 , 푖 là chiến lược khác nhau của người chơi i, thì −푖 là chiến ∗ ∗ lược của các người chơi khác i đối phó lại chiến lược của người chơi i, 푖( 푖 , −푖) là ∗ ∗ hàm payoff của chiến lược 푖 , các người chơi khác chọn chiến lược −푖. Trang 5
8. 1.3 Tổng quan về các thuật toán tối ưu đa mục tiêu 1.3.1 Giới thiệu bài toán tối ưu đa mục tiêu Bài toán tối ưu hóa K mục tiêu được định nghĩa như sau [55]: Cho 1 vectơ biến quyết định n chiều x={x1, ,xn} trong không gian giải pháp X, tìm vectơ x* mà nó tối thiểu tập K hàm mục tiêu đã cho z(x*)={z1(x*), , zK(x*)}. Không gian lời giải X nói chung bị hạn chế bởi các ràng buộc có dạng gj(x*)=bj (j=1, ,m). 1.3.2 Các giải thuật tiến hóa đa mục tiêu tiểu biểu Giải thuật tiến hóa là họ giải thuật tìm kiếm dựa trên quần thể. Giải thuật tiến hóa đặc biệt phù hợp để giải quyết các bài toán tối ưu đa mục tiêu. Trong số các giải thuật tối ưu hóa đa mục tiêu (MOEA) dựa vào meta-heuristic, 70% các phương pháp là dựa vào giải thuật di truyền. Điểm khác biệt giữa các giải thuật MOEA nằm ở cách gán độ thích nghi, cách duy trì quần thể ưu tú và các tiếp cận nhằm đa dạng hóa quần thể [41]. 1.3.3 Phương pháp đa dạng hóa quần thể Phương pháp hay dùng để gán độ thích nghi là Xếp hạng Pareto bao gồm việc gán thứ hạng 1 cho các cá thể không bị vượt trội trong quần thể và đưa chúng ra ngoài vòng xem xét; rồi tìm tập cá thể không bị vượt trội mới để gán thứ hạng 2 và tiếp tục như vậy. 1.3.4 Đánh giá một số giải thuật MOEA tiêu biểu Đặc điểm của một số giải thuật MOEA tiêu biểu được mô tả sơ lược trong Bảng 1.5 về các giải thuật: VEGA, MOGA, NSGA, NSGA-II, SPEA, SPEA-2, ε-MOEA, GDE. 1.3.5 MOEA Framework và các giải thuật Qua quá trình nghiên cứu và thử nghiệm cho thấy rằng công cụ MOEA Framework là một công cụ mã nguồn mở trên JAVA phù hợp trong việc trợ giúp giải quyết các bài toán tối ưu đa mục tiêu của đề tài. Luận án sử dụng 6 thuật toán là: NSGA-II, ε-MOEA, GDE3, PESA2, ε-NSGA-II, SMPSO. 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 1.4.1 Tình hình nghiên cứu ngoài nước Từ việc tìm hiểu các công bố quốc tế cho thấy về lĩnh vực nghiên cứu này đang tồn tại hai vấn đề chính, đầu tiên đó là chưa có một nghiên cứu tổng quan về tất cả các bài toán xung đột trong Quản lý dự án, thứ hai đó là vẫn còn nhiều vấn đề xung đột có thể chuyển đổi sang mô hình của Lý thuyết trò chơi cần được khám phá nghiên cứu. 1.4.2 Tình hình nghiên cứu trong nước Trong quá trình làm luận án, qua quá trình tìm hiểu cho thấy hiện tại không có các nghiên cứu việc áp dụng lý thuyết trò chơi vào trong giải quyết các vấn đề cụ thể của Quản lý dự án. Vì vậy việc khai phá các vấn đề này là cần thiết. Trang 6
9. 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 2.1 Phân tích đặc điểm xung đột và vai trò của chủ đầu tư 2.1.1 Các đặc điểm của xung đột Từ các kết quả công bố, luận án phân tích đặc điểm các bài toán xung đột đã được giải quyết, và từ đó đã xác định các dữ liệu liên quan tới đặc điểm theo GT: ▪ Người chơi: (i) xung đột xảy ra giữa những ai, (ii) dữ liệu về người chơi ▪ Chiến lược: (iii) những người chơi này có những hành động gì xảy ra xung đột, (iv) các hành động này có ràng buộc nào liên quan tới việc xảy ra xung, đây là các yếu tố liên quan tới các yếu tố về luật lệ, sự hợp lý khi kết hợp các yếu tố ▪ Hàm thưởng phạt (payoff): (v) với các lựa chọn của người chơi như vậy, việc đánh giá lời giải chung sẽ có giá trị như thế nào, tùy vào tình huống cần tối thiểu hóa chi phí, hàm payoff cho giá trị bé nhất sẽ cho lời giải tốt nhất hoặc tối đa hóa lợi ích, hàm payoff cho giá trị lớn nhất sẽ cho lời giải tốt nhất. Các dữ liệu trên được nhóm lại thành hai đặc điểm chính như sau: ▪ Những đặc điểm dữ liệu chung cần có của xung đột mô tả các thông tin về đối tượng của xung đột, chiến lược của các bên tham gia, và dữ liệu đầu riêng liên quan tới tính toán ra giá trị payoff, làm cơ sở để tính toán ra giá trị thích nghi của điểm cân bằng Nash. Đặc điểm này liên quan tới các mục dữ (i), (ii), (iii), (v) ▪ Ràng buộc về xung đột: bao gồm các điều kiện để xác định phương án lựa chọn cho bài toán là đúng hay sai, nếu điểm cân bằng Nash tìm được vi phạm các ràng buộc này, vậy điểm cân bằng Nash hay chính là lời giải cần tìm là sai, đặc điểm này liên quan tới dữ liệu cần có đã phân tích ở trên là (iv). 2.1.2 Lựa chọn kỹ thuật giải quyết xung đột Trong PMBOK [1] có 5 kỹ thuật để giải quyết xung đột và mô hình Thomas-Kilmann [33] cũng đưa ra 5 vị trí của một người trong cuộc bàn luận hoặc xung đột. Theo Thomas-Kilmann, kỹ thuật khó nhất nhưng tốt nhất cho xung đột về tổng thể chính là kỹ thuật Hợp tác (Collaborating) nhằm mục tiêu các bên đều chiến thắng (win-win). Hình 2.1: Chiến lược quản trị xung đột (mô hình Thomas-Kilmann) [34] Trang 7
10. Đây cũng chính là ý tưởng của lý thuyết trò chơi, trong việc xem xét các giải pháp để các tranh chấp xung đột thành việc hợp tác. Ngoài ra, việc thỏa mãn điều kiện các bên đều chiến thắng tương đương với việc tìm ra điểm cân bằng là điểm mà tại đó các bên đều chiến thắng. Có thể đi tới các phân tích chính rằng: ▪ Phương án phù hợp để giải quyết xung đột trong quản lý dự án là Hợp tác ▪ Có thể dùng Lý thuyết trò chơi để mô tả các giải quyết vấn đề hợp tác của xung đột, phương án lựa chọn cuối cùng cho vấn đề chính là điểm cân bằng Nash Hình 2.2 là mô hình luận án đề xuất về việc xử lý xung đột, trong mô hình này các xung đột hiện tại được xử lý theo kinh nghiệm của chuyên gia, người quản trị nay được phân tích và áp dụng để chuyển sang mô hình lý thuyết trò chơi (GT) để tìm ra điểm cân bằng Nash – điểm cân bằng mà các đối tượng chơi đều hài lòng (win - win), từ đó áp dụng vào các giải thuật tối ưu để tìm ra giải pháp, trợ giúp cho việc ra quyết định. Ràng buộc Thực hiện về xung đột Chạy trên DSS Mô hình GT và Collaboration và ra quyết NE thủ công Dữ liệu về định xung đột Hình 2.2: Giải pháp thông minh dùng DSS 2.1.3 Vai trò của chủ đầu tư trong xung đột Với vai trò chịu trách nhiệm cao nhất về tổng thể dự án như vậy, chủ đầu tư thay mặt cho toàn bộ dự án. Tác giả Agnar Johansen, 2013, trong nghiên cứu về đánh giá lợi ích của chủ đầu tư cũng đã chỉ ra sự quan trọng không thể thay thế của nhân tố chủ đầu tư [25]. Từ việc tìm hiểu các nghiên cứu liên quan tới lĩnh vực này và các phân tích trong phần 1.4 cho thấy rằng: các nghiên cứu trong và ngoài nước khác cho tới thời điểm hiện nay đều chưa đề cập tới vai trò khách quan của chủ đầu tư trong mối liên hệ với xung đột để đảm bảo được lợi ích chung của dự án. 2.1.4 Phân loại xung đột có và không có chủ đầu tư Có thể thấy rằng đa phần các xung đột xẩy ra trong dự án thuộc về loại không có sự liên quan tới chủ dự án, tuy nhiên như đã phân tích tại phần 2.1.2, vai trò của chủ đầu tư trong bất cứ vấn đề xung đột nào là rất cần thiết. Vì vậy cần có một giải pháp chung cho các bài toán xung đột để tránh bỏ sót việc tính toán lợi ích chung của dự. 2.2 Phương pháp mô hình hóa theo lý thuyết trò chơi 2.2.1 Các mô hình biểu diễn Lý thuyết trò chơi Với việc tìm hiểu các nghiên cứu hiện có, và với các phân tích trong luận án, có thể đi tới kết luận là các mô hình trên chưa phù hợp với đặc điểm của bài toán xung đột trong Quản lý dự án ở các yếu tố sau: ▪ Nhiều nghiên cứu chỉ mô tả về việc áp dụng lý thuyết trò chơi, cần thiết phải có một mô hình cụ thể biểu diễn trò chơi và các thông tin về bài toán ▪ Với các nghiên cứu có đề xuất mô hình thì biểu diễn với các ký pháp khác nhau Trang 8
11. ▪ Các mô hình đó thường chỉ đề cập trò chơi với 3 thành phần: người chơi, chiến lược, hàm lợi ích và thiếu đi thông tin về ràng buộc hoặc dữ liệu về xung đột ▪ Khi xét vấn đề xung đột của dự án thì yếu tố quan trọng cần phải tính đến rõ ràng là xung đột sẽ ảnh hưởng ra sao tới tổng thể dự án. Tuy nhiên với loại xung đột chỉ giữa các đối tượng thuộc dự án thì chưa xét tới yếu tố này 2.2.3 Biểu diễn xung đột theo lý thuyết trò chơi Từ đặc điểm của bài toán xung đột nêu ra trong phần 2.1.1 và phần 2.1.2, và đặc điểm của các lớp bài toán lý thuyết trò chơi giới thiệu tại phần 1.2, phân loại mô hình lý thuyết trò chơi cho lớp các bài toán xung đột của Quản lý dự án sẽ thuộc về các phân loại sau: ▪ Loại trò chơi có tổng khác không ▪ Loại trò chơi thông tin không hoàn hảo ▪ Loại trò chơi hợp tác Các tiêu chí của mô hình lý thuyết trò chơi và cân bằng Nash chuyển đổi sang cần có: ▪ Phản ánh được lợi ích trong khái niệm win - win để giải quyết xung đột ▪ Phản ảnh được lợi ích của chủ đầu tư ▪ Mô hình lý thuyết trò chơi cần mang đầy đủ thông tin để làm đầu vào cho các giải pháp thuật toán để đảm bảo được tính kế thừa của các nghiên cứu khác Vì vậy trong phần tiếp theo của nghiên cứu này, luận án sẽ đề xuất mô hình lý thuyết trò chơi cho lớp các bài toán xung đột, giải quyết được các vấn đề đã nêu trên. 2.3 Xây dựng Unified Game-Based Model mô hình hóa xung đột sử dụng lý thuyết trò chơi và cân bằng Nash 2.3.1 Đề xuất cấu trúc dữ liệu xung đột trong mô hình Thông tin của xung đột trong mô hình lý thuyết trò chơi cần có như sau: ▪ Người chơi đặc biệt trong trường hợp bài toán có chủ đầu tư, là các thông tin về chủ đầu tư. Còn với các bài toán không có chủ đầu tư, người chơi đặc biệt là một người chơi ảo đại diện lợi ích của toàn bộ dự án. Thông tin mô tả người chơi đặc biệt là một tập hợp 푃0 gồm các phần tử ∈ 푃0 ▪ Chiến lược của dự án là một tập 푆0 bao gồm các chiến lược 푠0푖 ∈ 푆0 trong đối phó hoặc tương tác với các chiến lược của người chơi i ▪ Hàm thưởng phạt (payoff) tính toán lợi ích của dự án khi chọn chiến lược 푠0푖 ▪ Thông tin về các người chơi khác là một tập hợp 푃푖 gồm các phần tử ∈ 푃푖 là thông tin liên quan tới việc tính toán lợi ích của người chơi này ▪ Chiến lược của từng người chơi i là một tập 푆푖 bao gồm các chiến lược 푠푖 ∈ 푆푖 trong đối phó / tương tác với các chiến lược của người chơi k ▪ Hàm payoff của người chơi i khi tham gia phương án ▪ Thông tin về các ràng buộc của xung đột là một không gian vectơ các cặp xung đột giữa các chiến lược của các người chơi 2.3.2 Đề xuất mô hình Unified Game-Based model Qua phân tích trên về nội dung cần thể hiện trong mô hình lý thuyết trò chơi, dựa vào cấu trúc chung cho các dạng trò chơi thông tin không hoàn hảo, trò chơi hợp tác, trò chơi tổng khác không, luận án đề xuất một mô hình thống nhất cho lớp các xung đột trong Quản lý dự án, mô hình được có tên gọi Unified Game-based model được biểu diễn dưới dạng như sau: = 〈{푃0 , 푃}, {푆0, 푆푖}, { 0, 푖}, 푅 〉 (2.1) Trang 9
12. Trong đó: G: biểu diễn mô hình của trò chơi 푃0 : là người chơi đặc biệt, người chơi này sẽ đại diện cho dự án, hoặc là chủ dự án, Quản lý dự án hoặc là nhà đầu tư, nếu trong trò chơi không xuất hiện những người chơi trên, người chơi đặc biệt mang ý nghĩa trừu tượng, sẽ đại biểu cho lợi ích của toàn bộ dự án khi so sánh với các người chơi bình thường khác 푆0 = {푠01, , 푠0푗, , 푠0 0 }: tập chiến lược của người chơi đặc biệt, trong đó 0 là số lượng chiến lược của người chơi đặc biệt 0: 푆0 → ℝ là hàm thưởng phạt (payoff function) của người chơi đặc biệt tham chiếu chiến lược của người chơi đặc biệt sang dạng số thực : Số lượng người chơi bình thường 푃 = { 1, , 푖, , }: là tập các người chơi bình thường, thường là các đối tượng có xảy ra xung đột trong Quản lý dự án 푆푖 = {푠푖1, , 푠푖푗, , 푠푖 푖 }: là tập các chiến lược của người chơi 푖(1 ≤ 푖 ≤ ) và 푖 là số lượng chiến lược của người chơi i 푖: 푆i → ℝ : là hàm thưởng phạt của người chơi i, tham chiếu chiến lược người chơi i sang 1 giá trị số thực 푅 : là không gian vector biểu diễn tập C các xung đột của bài toán, mà một non- empty vector 푣⃗ ∈ 푅 biểu diễn xung đột giữa K người chơi (1 ≤ 퐾 ≤ ), ở dạng chuẩn tắc của trò chơi (strategic form hoặc normal form), 푣⃗ ∈ 푅 có thể được mô tả như sau: {푠0 , 푠 푞, , 푠 }, trong đó 푠0 ∈ 푆0 đại diện cho người chơi đặc biệt (quyền lợi của dự án) và 푠 푞, 푠 ∈ 푆푖, trong đó (1 ≤ , ≤ ), (1 ≤ 푞 ≤ ) và (1 ≤ ≤ ) Điểm cân bằng Nash của mô hình được xác định như sau: Khi người chơi 푖(1 ≤ 푖 ≤ ) chọn chiến lược 푠푖 ∈ 푆푖, ta gọi 푠−푖 ∈ 푆푖 là chiến lược của những người chơi khác. Hàm payoff của người chơi i có thể được diễn giải như sau: ∗ ∗ ∗ ∗ 푖(푠푖, 푠−푖). Tập các chiến lược 푆 = (푠1, , 푠푖 , , 푠 ) được gọi là điểm cân bằng Nash ∗ ∗ ∗ ∗ ∗ khi ∀(푠푖 , 푠푗 ) ∈ 푆 , (푠푖 , 푠푗 ) ∉ 푅 , (1 ≤ 푖, 푗 ≤ ), và: ∗ ∗ ∗ 푖(푠푖 , 푠−푖) ≥ 푖(푠푖, 푠−푖), ∀푠푖 ∈ 푆푖 (2.2) Điểm cân bằng Nash chính là giải pháp cho xung đột chúng ta cần tìm. Việc xử lý xung đột theo cách thức win-win đã đề cập cũng tương đương với việc giải mô hình lý thuyết trò chơi và tìm ra điểm cân bằng Nash cho bài toán. 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 Các bài toán điển hình về xung đột trong Quản lý dự án dựa trên các công trình đã công bố của luận án đã được mô hình hóa theo Unified Game-based model. Các bài toán này thuộc về một số phân loại khác nhau về xung đột, đồng thời thuộc về các lĩnh vực quản lý dự án khác nhau như: ▪ Quản lý tích hợp: bài toán xếp lịch thanh toán dự án (PSP – Payment Schedule Problem), thuộc về loại trò chơi có hai người chơi và có mặt chủ đầu tư ▪ Quản lý mua sắm, đấu thầu: bài toán đấu thầu nhiều vòng (Multiround Procurement), là loại trò chơi có nhiều người chơi và có mặt chủ đầu tư ▪ Quản lý rủi ro: bài toán xung đột giữa các phương pháp xử lý (Risk Response Conflict), là trò chơi có nhiều người chơi và không có mặt chủ đầu tư Trang 10
13. ▪ Quản lý tài nguyên: bài toán cân bằng nguồn lực (Resource Balancing), thuộc về loại trò chơi có nhiều người chơi và không có mặt chủ đầu tư 2.3.4 Cân bằng Nash của xung đột Bài toán cân bằng lần đầu tiên được giới thiệu bởi bởi H. Nikaido, K. Isoda vào năm 1955 nhằm mục đích tổng quát hoá bài toán cân bằng Nash trong trò chơi không hợp tác [26]. Bài toán cân bằng các yếu tố của vấn đề nói chung là bài toán: tìm x∗ ∈ 퐾 sao cho ( ∗, ) ≥ 0, ∀ ∈ 퐾 [27]. Trong đó K là một tập cho trước và : 퐾 × 퐾 → ℝ là một hàm cho trước thỏa mãn ( , ) = 0. Bất đẳng thức trên được H. Nikaido và K. Isoda đưa ra lần đầu tiên năm 1955 khi tổng quát hóa bài toán cân bằng Nash trong trò chơi không hợp tác [26]. Cụ thể, hàm Nikaido-Isoda định nghĩa điểm cân bằng Nash của bài toán xung đột trong quản lý dự án được mô tả theo Unified Game-based model có dạng như sau: 푛 ∗ ( , ) = ∑( 푖( ) − 푖( [ 푖])) (2.7) 푖=1 Trong đó vectơ [ 푖] là vectơ nhận được bằng cách từ vectơ x thay thành phần xi bởi yi. Ký hiệu 퐾푖 ⊂ ℝ là tập chiến lược của người chơi thứ i. Khi đó tập chiến lược của trò ∗ chơi là: 퐾 ≔ 퐾1 × . × 퐾푛. Một điểm x ∈ 퐾 được gọi là điểm cân bằng Nash của trò chơi nếu: ∗ ∗ 푖( ) = max 푖( [ 푖]) , ∀ 푖 ∈ 퐾푖, ∀푖 (2.8) 푖∈퐾푖 Việc tìm ra điểm cân bằng Nash sử dụng song hàm Nikaido-Isoda tương đương với ∗ việc tìm ra các 푖( ) sao cho thỏa mãn Công thức 2.7. ∗ Trong mô hình Unified Game-based model, việc xác định lợi ích qua các hàm lồi 푖( ) ∗ tương đương với các ký pháp về hàm payoff 푖. Hàm lồi 푖( [ 푖]) cho điểm cân bằng ∗ ∗ ∗ Nash tìm được tương đương với định nghĩa về 푖(푠푖 , 푠−푖) trong Phần 2.3.2 và mô ∗ ∗ ∗ ∗ ∗ hình của Dario Bauso [35], trong đó tập các chiến lược = 푆 = (푠1, , 푠푖 , , 푠 ) được gọi là điểm cân bằng Nash khi: ∗ ∗ ∗ ∗ ∗ ∀(푠푖 , 푠푗 ) ∈ 푆 , (푠푖 , 푠푗 ) ∉ 푅 , (1 ≤ 푖, 푗 ≤ ), và: ∗ ∗ ∗ (2.9) 푖(푠푖 , 푠−푖) ≥ 푖(푠푖, 푠−푖), ∀푠푖 ∈ 푆푖 Vì vậy theo song hàm Nikaido-Isoda trong cân bằng Nash [61], áp dụng vào mô hình Unified Game-based model, khi tìm kiếm được giá trị: ∗ ∗ 푛 ∗ ∗ ∗ ( , ) = (푆 , 푆) = ∑푖=1( 푖(푠푖 , 푠−푖) − 푖(푠푖, 푠−푖)) ≥ 0, , ∀푠푖 ∈ 푆푖 (2.10) Trong thực tế, các điểm cân bằng Nash cần phải thỏa mãn thêm các ràng buộc khác ∗ ∗ ∗ và việc tính 푖( ) hay 푖(푠푖 , 푠−푖) dựa vào nhiều yếu tố, dữ liệu của bài toán, lúc này bài toán tìm cân bằng Nash theo song hàm Nikaido-Isoda có dạng của một bài toán tối ưu đa mục tiêu và có thể giải quyết bằng các giải thuật tối ưu đa mục tiêu [61, 62]. Có thể khẳng định rằng nếu các giải thuật tối ưu đa mục tiêu hội tụ, khi đó sẽ tìm được điểm cân bằng Nash thỏa mãn Công thức 2.9 và Công thức 2.10. Điểm cân bằng Nash chính là giải pháp cho xung đột chúng ta cần tìm. Việc xử lý xung đột theo cách thức win-win đã đề cập cũng tương đương với việc giải mô hình lý thuyết trò chơi và tìm ra điểm cân bằng Nash cho bài toán. Trang 11
14. 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 3.1 Ứng dụng mô hình trên các giải thuật 3.1.1 Các giải thuật lựa chọn Các công cụ khác nhau để tìm ra điểm cân bằng Nash cho xung đột bao gồm: ▪ Công cụ MATLAB tích hợp trong phần mềm viết trên JAVA, công cụ GAMBIT tích hợp trong phần mềm viết trên JAVA ▪ Giải thuật di truyền (trong bài báo CT01, CT02) viết thử nghiệm trên JAVA, PHP ▪ Giải thuật Fictitious play, CFR, CFR+ (trong bài báo CT3) ▪ Giải thuật ε-Origin, WSM, ε-Enhanced, SPEA ▪ Công cụ MOEA framework với các giải thuật NSGA-II, ε-MOEA, GDE3, PESA2, ε-NSGA-II, SMPSO Các giải thuật được hỗ trợ trong công cụ MOEA framework thông qua kết quả chạy thể hiện được tính hiệu quả vượt trội trong thời gian thực thi xác định trước để có thể hội tụ được. Các giải thuật được lựa chọn dựa trên các tiêu chí: ▪ Là tiêu biểu cho các thuật toán khác nhau được hỗ trợ bởi MOEA framework ▪ Hỗ trợ việc định nghĩa các ràng buộc cho xung đột để đánh giá lời giải đưa ra có vi phạm các tập xung đột 푅 . Đầu vào Thư viện mẫu của Hiển thị đầu ra MOEA •Lấy dữ liệu từ JSON •Lựa chọn thuật •Kiểm tra việc vi toán phạm ràng buộc •Định nghĩa tham số bài toán •Xác định tham số •Hiển thị thông tin thuật toán •Định nghĩa các ràng buộc •Tự khởi tạo tập dân số Hình 3.1: Triển khai mô hình trên MOEA framework Các giải thuật tiến hóa tối ưu đa mục tiêu như đã kể trên thường bao gồm các bước lặp chủ yếu như sau [41, 42, 43, 44]: a. Khởi tạo tập dân số c. Tiến hành lai ghép / đột biến b. Lựa chọn các cá thể cho vòng đời d. Đánh giá cá thể dựa trên xếp hạng Các bước b, c ở trên được hỗ trợ bởi MOEA framework ứng dụng các giải thuật tốt và được cập nhật thường xuyên, bởi vì MOEA framework là ứng dụng mã nguồn mở, có cộng đồng sử dụng và hỗ trợ đông đảo. Các bước a, d được xử lý riêng theo từng bài toán cụ thể của luận án dựa trên Unified Game-based model để đảm bảo có thể truyền tải đầy đủ thông tin về mô hình bao gồm: ▪ Thông tin về người chơi ▪ Thông tin về chiến lược người chơi ▪ Cách tính hàm payoff riêng cho từng bài toán và người chơi ▪ Thông tin về tập xung đột 푅 mà điểm cân bằng Nash không được vi phạm Trang 12
15. 3.1.2 Phương thức thử nghiệm Trong chương 3, luận án trình bày 4 bài toán cụ thể và cách áp dụng như sau: ▪ Bài toán cân bằng nguồn lực sử dụng thuật toán Fictitious Play trên ứng dụng tự xây dựng theo thuật toán ▪ Các bài toán toán xung đột trong đấu thầu nhiều vòng, xung đột giữa các phương pháp xử lý rủi ro, xung đột trong cân bằng nguồn lực được cài đặt dựa theo MOEA framework Các thuật toán trong cùng 1 thuật toán được chạy lần lượt trên cùng cấu hình máy tính, mỗi thuật toán sẽ thử nghiệm chạy liên tục 10 lần để so sánh sự hội tụ của kết quả dựa trên giá trị payoff của chiến lược lựa chọn, và thời gian chạy. 3.2 Lớp bài toán mô hình có chủ đầu tư 3.2.1 Bài toán đàm phán giá trong đấu thầu nhiều vòng 3.2.1.1 Giới thiệu bài toán Đối với các dự án lớn, thời gian kéo dài thường được chia thành các hạng mục nhỏ. Chủ dự án (chủ đầu tư) sẽ không tìm nhà thầu cho toàn bộ dự án tại một thời điểm duy nhất mà sẽ tổ chức thầu cho từng hạng mục vào các thời điểm khác nhau. Giai đoạn 1 Giai đoạn k Giai đoạn N • Gói thầu 1 • Gói thầu i • Gói thầu x • Gói thầu 2 • Gói thầu j • Gói thầu y • • • Hình 3.3: Mô hình đấu thầu nhiều vòng Chủ thầu và các nhà thầu khi tham gia vào đấu thầu đều cố gắng thu lại lợi ích lớn nhất cho mình từ gói thầu. Lợi ích giữa chủ đầu tư và các nhà thầu, cũng như giữa các nhà thầu có sự xung đột lẫn nhau. 3.2.1.2 Ứng dụng mô hình Unified Game-Based model cho bài toán Với các đặc điểm của bài toán xung đột trong đấu thầu nhiều vòng được mô tả trong chương 2, áp dụng mô hình Unified Game-Based được giới thiệu trong Phần 2.3.2, ta có mô hình chuẩn tắc cho bài toán này như sau: = 〈{푃0 , 푃}, {푆0, 푆푖}, { 0, 푖}, 푅 〉 (3.1) Trong đó: 푃0 : là chủ đầu tư của gói thầu 푆0 = {푠01, , 푠0푗, , 푠0 0 }: tập chiến lược của chủ đầu tư 0: 푆0 → ℝ là hàm thưởng phạt (payoff function) của chủ đầu tư tham chiếu chiến lược của chủ đầu tư sang dạng số thực 푃 = { 1, , 푖, , }: là tập các nhà thầu tham gia đấu thầu, : Số lượng nhà thầu 푆푖 = {푠푖1, , 푠푖푗, , 푠푖 푖 }: là tập các chiến lược của người chơi 푖(1 ≤ 푖 ≤ ) và 푖 là số lượng gói thầu người chơi i tham gia 푖: 푆i → ℝ : là hàm thưởng phạt của người chơi i, tham chiếu chiến lược người chơi i sang 1 giá trị số thực 푅 : là không gian vector biểu diễn tập C xung đột Trang 13
16. 3.2.1.3 Các tham số của mô hình Chiến lược của chủ đầu tư 푆0 = {푠01, , 푠0푗, , 푠0 0}: tập chiến lược của người chủ đầu tư, trong đó: 0 là số lượng các gói thầu cần đấu thầu, 푠0푗 là cấu trúc thông tin chứa bộ thông tin về gói thầu bao gồm: tên sản phẩm, số lượng đấu thầu, giá dự kiến cho sản phẩm Chiến lược của nhà thầu 푆푖 = {푠푖1, , 푠푖푗, , 푠푖 푖 }: là tập các chiến lược của người chơi 푖(1 ≤ 푖 ≤ ), trong đó: 푖 là số lượng gói thầu người chơi i tham gia, 푠푖푗 là chiến lược của người chơi i với chiến lược (gói thầu) của chủ đầu tư, bao gồm thông tin dự thầu: sản phẩm gói thầu, đơn giá đề nghị, thông tin về giảm giá theo thời gian Công thức tính hàm payoff của chủ đầu tư Giả sử chi phí dự kiến cho toàn bộ các gói thầu tính toán dựa trên là A; chi phí trúng thầu của 1 nhà thầu thực tế là B, khi đó phần chênh lệch 0 = − gọi là hàm payoff của chủ đầu tư. Chi phí thực tế phải thanh toán cho toàn bộ dự án được tính : 0 0 − .푡푗 = ∑ ó푖 푡ℎầ 푖 = ∑ ∑(푠푖푗 ∗ ó푖 푡ℎầ 푖푗)푒 푖=1 푖=1 푗=1 0 − .푡푗 = ∑ ∑(푠푖푗 ∗ (∑ 푃 푗 ))푖푒 (3.3) 푖=1 푗=1 =1 Trong đó: ó푖 푡ℎầ 푖푗: là tổng số tiền phải trả cho gói thầu i và nội dung mua sắm j, 푠푖푗: trạng thái của gói thầu i tại nội dung mua sắm j, xk : số lượng vật liệu k của nội dung mua sắm j, Pkj : là giá bán của vật liệu k tại nội dung mua sắm j, M0: số gói thầu trong toàn bộ dự án, M : là số nội dung mua sắm trong gói thầu, pj: là số vật liệu của nội dung mua sắm j. Như vậy, payoff của chủ dự án so với tính toán ban đầu sẽ là: 0 푗 − .푡퐹푖푛푖푠ℎ − .푡푗 0 = . 푒 − ∑ ∑(푠푖푗 ∗ (∑ 푃 푗 ))푖푒 (3.4) 푖=1 푗=1 =1 Công thức tính hàm payoff đối với từng nhà thầu được lựa chọn Hàm payoff của từng nhà thầu được tính toán theo công thức: 0 푗 − .푡푗 푖 = ∑ ∑(푠푖푗 ∗ (∑ (푃 푗− 푗 − 푗 ))푖푒 (3.5) 푖=1 푗=1 =1 Trong đó: 푗: là giá gốc của vật liệu k tại nội dung mua sắm j, 푗: là chiết khấu % (giảm giá, khuyến mại) của vật liệu k tại nội dung mua sắm j. Công thức tính hàm payoff đối với tất cả nhà thầu nhà thầu được chọn Payoff tổng thu được của các toàn bộ các nhà thầu tham gia đấu thầu: 1 푙푙 = (∑( 푖 − ̅푖)) (3.6) ∑ ( 푖 + 푞푖 + 푛푙푖) 푖=1 푖=1 Trong đó: N: là số nhà thầu tham gia dự án, 푞푖: chỉ số quan hệ của nhà thầu i với chủ đầu tư, 푛푙푖: chỉ số đánh giá năng lực của nhà thầu i. Không gian vector biểu diễn tập xung đột 푅 : là không gian vector biểu diễn tập C xung đột của bài toán, mà một vector 푣⃗ ∈ 푅 biểu diễn xung đột giữa M người chơi tham gia cùng một gói thầu và cạnh tranh với Trang 14
17. nhau (1 ≤ ≤ ), 푣⃗ ∈ 푅 có thể được mô tả như sau: {푠0 , 푠 푞, , 푠 }, trong đó 푠0 ∈ 푆0 đại diện cho người chơi đặc biệt (quyền lợi của dự án) và 푠 푞, 푠 ∈ 푆푖, trong đó (1 ≤ , ≤ ), (1 ≤ 푞 ≤ ) và (1 ≤ ≤ ), trong đó các chiến lược trong 푣⃗ ∈ 푅 đều thuộc về một gói thầu mà có 푠0 là bài thầu do 푃0 tổ chức và các 푠 푞, 푠 ∈ 푆푖 là hồ sơ thầu tham gia. 3.2.1.4 Cài đặt giải thuật và thử nghiệm Thông tin cụ thể về thông tin đấu thầu được mô tả trong Phụ lục A, trong Bảng 3.1. Dưới đây là bảng so sánh thời gian tính (giây) và giá trị payoff của lời giải tốt nhất mà các thuật toán tìm được sau mỗi lần chạy: Bảng 3.2: Kết quả thử nghiệm các thuật toán Lần NSGA-III ε-MOEA GDE3 PESA2 ε-NSGAII SMPSO chạy 4.197s 6.602s 5.981s 3.630s 8.954s 4.300s 1 0.2961 0.2755 0.2805 0.2741 0.2744 0.2805 4.178s 6.633s 5.992s 3.051s 8.921s 4.369s 2 0.3322 0.2714 0.2799 0.2743 0.2765 0.2811 4.209s 6.590s 5.974s 3.555s 8.933s 4.321s 3 0.2911 0.2711 0.2799 0.2747 0.2801 0.2816 4.166s 6.602s 6.000s 3.525s 9.102s 4.256s 4 0.2966 0.2706 0.2811 0.2751 0.2809 0.2796 4.178s 6.613s 5.981s 3.617s 8.990s 4.273s 5 0.2979 0.2754 0.2821 0.2714 0.2712 0.2801 4.184s 6.595s 6.112s 3.504s 9.051s 4.291s 6 0.3025 0.2755 0.2797 0.2777 0.2708 0.2823 4.189s 6.621s 5.969s 3.550s 8.915s 4.315s 7 0.3105 0.2723 0.2797 0.2750 0.2714 0.2841 4.171s 6.608s 5.980s 3.544s 8.956s 4.324s 8 0.2923 0.2746 0.2810 0.2707 0.2721 0.2800 4.190s 6.615s 5.987s 3.601s 8.937s 4.210s 9 0.2940 0.2704 0.2807 0.2721 0.2725 0.2799 4.178s 6.601s 5.994s 3.539s 8.929s 4.356s 10 0.3025 0.2705 0.2805 0.2733 0.2708 0.2796 Liên quan trực tiếp đến nội dung của mục này, có 01 bài báo đã được công bố trên trong Hội nghị quốc tế (CT2 – 2017) và 01 bài báo đang nộp chờ phản biện tại Tạp chí ISI (CT08). 3.2.2 Bài toán xếp lịch thanh toán dự án 3.2.2.1 Giới thiệu bài toán Trong việc thanh toán các khoản tiền của dự án thì cả nhà thầu và chủ đầu tư đều muốn tối đa lợi nhuận hoạt động tài chính và giá trị NPV của họ. Tiến độ thanh toán tối ưu của chủ đầu tư là việc thanh toán một lần duy nhất khi dự án đã được hoàn thành, còn nhà thầu muốn nhận càng nhiều tiền, càng sớm càng tốt. Cả hai lịch trình thanh toán và lịch trình hoạt động có ảnh hưởng đáng kể tới NPV của chủ đầu tư và nhà thầu. Cả Trang 15
18. chủ đầu tư và nhà thầu đều có ý định muốn tối đa hóa NPV của riêng mình nhưng gia tăng NPV của người này lại thường gây ra sự sụt giảm NPV của người khác. 3.2.2.2 Ứng dụng mô hình Unified Game-Based model cho bài toán Áp dụng mô hình Unified Game-Based được đề xuất ở trên, mô hình Lý thuyết trò chơi cho vấn đề xung đột trong xếp lịch thanh toán dự án sẽ được mô tả như sau: = 〈{푃0 , 푃1 }, {푆0, 푆1}, { 0, 1}, 푅 〉 (3.8) Trong đó, 푃0 : người chơi là chủ đầu tư đại diện cho lợi ích của dự án 푆0 = {푆01, . . 푆0푗, . . 푆0퐾}: tập các chiến lược của chủ dự án 0: hàm payoff của chủ dự án 푃1: người chơi là nhà thầu 푆1 = {푆11, . . 푆1푗, . . 푆1 }: tập chiến lược của nhà thầu 1: hàm payoff của người chơi nhà thầu 푅 : là không gian vector biểu diễn tập C xung đột trong đó mỗi xung đột thể hiện bằng một vector không rỗng 푣⃗ ∈ 푅 biểu thị xung đột giữa thứ tự thanh toán mong muốn của 2 người chơi trong chiến lược (푆0퐾, 푆1ℎ), trong đó 푆0 ∈ 푆0 và 푆1ℎ ∈ 푆1, ∈ {1,2, . . , 퐾} và ℎ ∈ {1,2, . . , }. 3.2.2.3 Các tham số của mô hình Chiến lược của chủ đầu tư Có dạng: 푆0 = {푆00, 푆01, . . 푆0푗, . . 푆0퐾} là chiến lược thanh toán của chủ đầu tư, trong đó: 푆0푗 = ({ 0푗1, 0푗1}, . . , { 0푗푖, 0푗푖}, . . , { 0푗 , 0푗 }). Với 0푗푖 là tỷ lệ phần trăm ngân sách mà chủ đầu tư dự định trả cho nhà thầu tại sự kiện 푖, là tổng số lần thanh toán, 0푗푖 là hoạt động lựa chọn. 푆00 là chiến lược ban đầu, từ thỏa thuận hoặc trong hợp đồng. Tỷ lệ thanh toán trên theo tổng số tiền A cần đáp ứng ràng buộc: 푛 ∑푖=1 푖 = 1 (3.10) Chiến lược của nhà thầu Có hình thức tương tự như chiến lược của chủ đầu tư, tuy nhiên số phần tử trong chiến lược có thể khác nhau. Chiến lược của nhà thầu có dạng như sau: 푆1푗 = ({ 1푗1, 1푗1}, . . , { 1푗푖, 1푗푖}, . . , { 1푗 , 1푗 }) với M là số lượng mốc thanh toán cho tổng số tiền A theo đề nghị của nhà thầu. Công thức tính hàm payoff của chủ đầu tư Là sự chênh lệch về giá trị tiền của phương án đang đề xuất lần thứ i của chủ đầu tư so với phương án định ra ban đầu S00: 01 01+ 02 0 = ( . 001)(1 + ) + ( . 002)(1 + ) + ⋯ + 01+ 02+ + 0퐾 푖1 ( . 00퐾)(1 + ) − ( . 0푖1)(1 + ) + ( . 0푖2)(1 + 푖1+ 푖2 푖1+ 푖2+ + 푖 ) + ⋯ + ( . 0푖 )(1 + ) (3.11) Trong đó: N: số lượng các mốc thanh toán của chủ đầu tư, A: tổng số tiền của dự án 푖: thời gian cần thiết để hoàn thành hoạt động i , : lãi suất ngân hàng Công thức tính hàm payoff của nhà thầu Là sự chênh lệch về giá trị tiền của phương án đang đề xuất lần thứ i của nhà thầu so với phương án định ra ban đầu S00: 01 01+ 02 1 = ( . 001)(1 + ) + ( . 002)(1 + ) + ⋯ + 01+ 02+ + 0퐾 푖1 ( . 00퐾)(1 + ) − ( . 1푖1)(1 + ) + ( . 1푖2)(1 + 푖1+ 푖2 푖1+ 푖2+ + 푖 ) + ⋯ + ( . 1푖 )(1 + ) (3.12) Trang 16
19. Công thức tính hàm payoff chung của cả dự án Hàm thích nghi của dự án được tính theo hàm payoff của từng người chơi, sự chênh lệch giữa 2 giá trị payoff càng nhỏ thì lời giải càng tốt. 푖푡푛푒푠푠 = | 0 − 1| (3.13) Trong đó: , : là các hằng số chuyên gia điều chỉnh chất lượng của giá trị fitness Không gian vector biểu diễn tập xung đột Trong không gian vector 푅 , mỗi 푣⃗ ∈ 푅 biểu thị C xung đột trong việc định nghĩa thứ tự thanh toán, mỗi vector được biểu diễn bằng một bộ cặp giá trị các hoạt động dự án cần thanh toán (ri, rj) có xung đột về các tài nguyên yêu cầu và thời gian sử dụng tài nguyên trong trường hợp cả hai hoạt động trong cùng thời điểm. 3.2.2.4 Cài đặt giải thuật và thử nghiệm Xác định điểm cân bằng Nash Từ mô tả về vấn đề, có thể xác định được biểu diễn của nhiễm sắc thể bao gồm thông tin về số lượng hoạt động, số lượng giải pháp cho từng hoạt động thông tin này được chuyển đổi thành nhiễm sắc thể với số lượng gen bằng số lượng hoạt động trong dự án, các gen lấy các giá trị là thứ tự hoạt động trong tập hợp tất cả các hoạt động được thực hiện mỗi ngày: (1 – 4) – (1 – 4) – (2 – 5) – (2 – 5) – (3 – 5) – 3 Mô tả dữ liệu Dữ liệu được sử dụng trong thử nghiệm bao gồm 2 loại: ▪ Dữ liệu từ bài báo [14]. ▪ Dữ liệu từ hai dự án phần mềm gia công từ một công ty phần mềm của Việt Nam. Phân tích kết quả chạy Qua 10 lần chạy lần lượt các thuật toán theo kịch bản áp dụng đã mô tả trong Phần 3.1, dữ liệu thử nghiệm của dự án 1 được mô tả trong Bảng 3.9 và Hình 3.7. Chúng ta có thể thấy NSGA-II là MOEA nhanh nhất để giải quyết vấn đề tìm điểm cân bằng Nash cho Unified Game-based model trong dữ liệu Dự án 1. NSGA-II có thời gian chạy nhanh hơn 10,09% so với thời gian chạy trung bình của năm thuật toán còn lại. Cụ thể, thời gian hoạt động của NSGA-II cao hơn 26,67% so với SMPSO, cao hơn 12,00% so với GDE3 và cao hơn khoảng 7,37% so với ε -MOEA. NSGA-II cho thấy thời gian chạy lần lượt chỉ cao hơn 1,12% và 2,22% so với ε -NSGA-II và PESA2. Điều này có nghĩa là cả NSGA-II và PESA2 cũng là hai thuật toán hiệu quả về tốc độ với bài toán này. 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 No NSGA-II ε-NSGA-II ε-MOEA 1 301343880, 7s 301343880, 9s 301343880, 9s 2 301343880, 8s 301343880, 8s 301343880, 10s 3 301343880, 9s 301343880, 9s 301343880, 10s 4 301343880, 8s 301343880, 8s 301343880, 9s 5 301343880, 11s 301343880, 9s 301343880, 10s 6 301343880, 7s 301343880, 10s 301343880, 9s 7 301343880, 8s 301343880, 10s 301343880, 10s 8 301343880, 10s 301343880, 9s 301343880, 9s 9 301343880, 9s 301343880, 9s 301343880, 9s 10 301343880, 11s 301343880, 8s 301343880, 10s GDE3 PESA2 SMPSO 1 301343880,10s 301343880, 9s 301343880, 13s 2 301343880,10s 301343880, 9s 301343880, 13s Trang 17
20. 3 301343880,10s 301343880, 9s 301343880, 11s 4 301343880,10s 301343880, 9s 301343880, 13s 5 301343880,10s 301343880, 9s 301343880, 11s 6 301343880,10s 301343880, 9s 301343880, 13s 7 301343880,10s 301343880, 9s 301343880, 13s 8 301343880,10s 301343880, 9s 301343880, 11s 9 301343880,10s 301343880, 9s 301343880, 11s 10 301343880,10s 301343880, 9s 301343880, 11s Liên quan trực tiếp đến nội dung của mục này, có 02 công trình đã được công bố, 01 trong Tạp chí trong nước (CT1- 2016) và 01 trong Hội nghị quốc tế (CT6 - 2019). 3.3 Lớp bài toán mô hình không có chủ đầu tư 3.3.1 Bài toán xung đột giữa các phương pháp xử lý rủi ro 3.3.1.1 Giới thiệu bài toán Việc quản lí rủi ro trong các dự án , đặc biệt là dự án công nghệ thông tin cũng là một ứng dụng quan trọng của lí thuyết trò chơi. Tuy nhiên 1 yếu tố chưa được xét tới là bản thân giữa các rủi ro lại xung đột với nhau khi lên kế hoạch giải quyết. Việc giải quyết xử lí rủi ro này bằng phương pháp này lại xung đột với việc xử lí rủi ro kia bằng phương pháp khác, hậu quả có thể từ nhỏ tới không kiểm soát được. Ví dụ như khi có rủi ro là “nhân sự bỏ việc” vì lương thấp, trả không đúng định kì, xử lí rủi ro này bằng cách: tăng tiền lương, trả đúng định kì, đúng hạn. Khi đó rủi ro trên tạm thời được xử lí. Tuy nhiên, với rủi ro tiền đầu tư dự án tăng, có thể giải quyết bằng việc giảm lương nhân viên hay sa thải nhân viên , kêu gọi nhà đầu tư Khi giải quyết rủi ro này bằng phương pháp giảm lương hay sa thải nhân viên thì nó đã vô tình xung đột với việc giải quyết rủi ro nhân sự bỏ việc nêu bên trên. Rủi ro: Rủi ro: Giảm chi Nhân viên phí dự án Xung nghỉ việc Xử lý: giảm Xử lý: tăng đột lương nhân lương sự Hình 3.9: Xung đột giữa các phương pháp xử lý rủi ro 3.3.1.2 Ứng dụng mô hình Unified Game-based model cho bài toán Với các đặc điểm của bài toán xung đột trong các phương pháp đối phó rủi ro như trên, áp dụng Unified Game-base model vào bài toán, ta có mô hình toán học cho bài toán này như sau: = 〈{푃0 , 푃}, {푆0, 푆푖}, { 0, 푖}, 푅 〉 (3.14) Trong đó: 푃0 : là người chơi đặc biệt đại biểu cho lợi ích của toàn bộ dự án khi so sánh với các người chơi bình thường khác 푆0 = {푠01, , 푠0푗, , 푠0 0}: tập chiến lược của người chơi đặc biệt, trong đó 0 là số lượng chiến lược của người chơi đặc biệt 0: 푆0 → ℝ là hàm thưởng phạt (payoff function) của người chơi đặc biệt tham chiếu chiến lược của người chơi đặc biệt sang dạng số thực : Số lượng rủi ro có xảy ra xung đột Trang 18
21. 푃 = { 1, , 푖, , }: là tập các rủi ro có xảy ra xung đột 푆푖 = {푠푖1, , 푠푖푗, , 푠푖 푖 }: là tập các phương pháp đối phó của rủi ro 푖(1 ≤ 푖 ≤ ) và 푖 là số lượng các phương pháp xử lý của rủi ro i 푖: 푆i → ℝ : là hàm thưởng phạt của rủi ro i, tham chiếu chiến lược của rủi ro i sang 1 giá trị số thực 푅 : là không gian vector biểu diễn tập các xung đột của các phương pháp đối phó rủi ro, mà một non-empty vector 푣⃗ ∈ 푅 biểu diễn xung đột giữa M rủi ro (1 ≤ ≤ ), ở dạng chuẩn tắc của trò chơi (strategic form hoặc normal form), 푣⃗ ∈ 푅 có thể được mô tả như sau: {푠0 , 푠 푞, , 푠 }, trong đó 푠0 ∈ 푆0 đại diện cho quyền lợi của dự án khi các rủi ro xảy ra, và khi có đụng độ về phương pháp xử lý, các giá trị 푠 푞, 푠 ∈ 푆푖 là các phương, trong đó (1 ≤ , ≤ ), (1 ≤ 푞 ≤ ) và (1 ≤ ≤ ) 3.3.1.3 Các tham số của mô hình Chiến lược của chủ đầu tư Chiến lược j cho rủi ro của người chơi đặc biệt gồm 4 thành phần: thời gian tối thiểu để xử lý rủi ro, thời gian tối đa xử lý rủi ro, chi phí tối thiểu, chi phí tối đa: 푠0푗 = { 표푠푡푗 푖푛, 표푠푡푗 , 푡푖 푒푗 푖푛, 푡푖 푒푗 } (3.16) Chiến lược của các người chơi Tập chiến lược 푆푖 = {푠푖1, , 푠푖푗, , 푠푖 푖 } là chiến lược chơi của người chơi i , hay được coi là tập các phương pháp đối phó của rủi ro i, mỗi 푠푖푗 gồm các thông tin như sau: cost, diff, priority, time, efficiency. Công thức tính hàm payoff của chủ đầu tư Tập các rủi ro 푃 = { 1, . . , 푖, . . , } với từng rủi ro pi được mô tả bởi vector hiệu năng có chứa các thông tin về: (i) số lượng tiền tổn thất khi xung đột xảy ra (ii) và giá trị level của rủi o, (iii) xác xuất xảy ra (probability). Cụ thể là: 푤⃑⃑⃑⃑ 푖 = (푤푖 푡푖 , 푤푙푒푣푒푙푖 , 푤 표 푖푙푖푡 푖 ) (3.17) Giá trị payoff của chủ dự án: 0 = ∑푖=1 푤⃑⃑⃑⃑ 푖 (3.18) ∑ = 푖=1( 1푤푖 푡푖 + 2푤푙푒푣푒푙푖 ) ∗ 푤 표 푖푙푖푡 푖 Với a1, a2 là các hằng số chuyên gia dùng để điều chỉnh mức độ ảnh hưởng của các yếu tố trong vector hiệu năng: impact, level. Tập các chiến lược của rủi ro pi là 푆푖 = {푠푖1, . . , 푠푖푗, . . , 푠푖 푖 } với mỗi 푠푖푗 được biểu diễn bởi 1 vector hiệu năng ⃑⃑⃑⃑푖푗⃑ = ( 표푠푡푖푗, 푖표 푖푡 푖푗, 푖 푖푗, 푡푖 푒푖푗, 푒 푖 푖푒푛 푖푗) có chứa 5 thông tin quan trọng nhất của phương pháp đối phó với rủi ro i, (1 ≤ i ≤ N). Các thông tin này bao gồm: (i) cost, (ii) priority, (iii) difficult (diff), (iv) time and (v) efficiency. Công thức tính hàm payoff của từng người chơi Giá trị payoff của rủi ro i trong trường hợp lựa chọn phương án đối phó j là tổng hợp của cả 5 yếu tố trên. Cụ thể, hàm payoff sẽ được mô tả như sau: = + + + (3.19) 푖푗 1 표푠푡푖푗 2 푖표 푖푡 푖푗 3 푖 푖 푖 4 푡푖 푒푖푗 Giá trị của hàm payoff uij càng nhỏ có nghĩa rằng lựa chọn phương án đối phó rủi ro càng phù hợp. Trang 19
22. Công thức tính hàm payoff chung của dự án Ràng buộc về giá thành xử lý rủi ro: ∑ 푭 풐풔풕 = 푖=1( 1푤푖 푡푖 + 2푤푙푒푣푒푙푖 ) ∗ 푤 표 푖푙푖푡 푖 ∗ (1 − 푒 푖 푖푒푛 푖푗) + ∑푵 풊= 표푠푡푖푗 (3.21) Ràng buộc thứ 2 của cân bằng Nash cho game G đó là tính hiệu quả của phương pháp xử lý rủi ro. Để mô hình có thể tùy biến, ta đưa thêm các tham số b1, b2, b3, b4 vào các đặc tính của phương pháp xử lý rủi ro theo thứ tự là cost, priority, difficulty, time. Các tham số này (và bao gồm cả a1, a2 trong Công thức 3.18) sẽ được điều chỉnh bởi các chuyên gia quản trị dự, hàm định lượng cho ràng buộc thứ 2 của cân bằng Nash sẽ được xác định như sau: ∑ 푭풓풆풔풑풐풏풔풆 = 푖=1 ( 1 표푠푡푖푗 + 2 푖 푖푗 + 3 푖표 푖푡 푖푗 + 4 푖 푖푗) (3.22) Để đánh giá chất lượng của Nash Equilibrium, việc định nghĩa ra hàm thích nghi là cần thiết, và dựa trên các công thức 3.21, công thức 3.22, ta có: 퐹 푡푖푣푒 = 1 ∗ 퐹 표푠푡 + 2 ∗ 퐹 푒푠 표푛푠푒 (3.23) ∑ = 1 푖=1( 1푤푖 푡푖 + 2푤푙푒푣푒푙푖 ) ∗ 푤 표 푖푙푖푡 푖 ∗ (1 − 1 표푠푡 + 2 푖 + 3 푖표 푖푡 ∑ 푖푗 푖푗 푖푗 푒 푖 푖푒푛 푖푗) + 2 푖=1 ( ) + 4 푖 푖푗 3.3.1.4 Cài đặt giải thuật và thử nghiệm Mô tả dữ liệu Dữ liệu dùng trong thử nghiệm được thu thập từ công ty gia công phần mềm liên doanh với Nhật Bản tại Việt Nam (nơi tác giả luận án làm việc từ 2004 - 2007): Tên dự án: Rentar – hệ thống eCommerce bán và cho thuê Nhà đất cho công ty Bất động sản số 1 của Nhật Bản (www.mec.co.jp) Thời gian bắt đầu: 1.6.2006, thời gian kết thúc: 30.5.2008 Quy mô dự án: 850 man/months Kết quả thử nghiệm Trong Bảng 3.18 mô tả kết quả chạy của 10 lần chạy liên tục. Lưu ý rằng lần đầu tiên chạy, cho đặc điểm về kỹ thuật và môi trường nên bao giờ kết quả chạy cũng chậm hơn một chút so với các lần sau. Mỗi ô trong Bảng 3.18 thể hiện 2 giá trị: ▪ Giá trị thích nghi của điểm cân bằng Nash tìm được của toàn dự án ▪ Thời gian chạy tính theo giây Bảng 3.18: Kết quả chạy các thuật toán 10 lần STT NSGA-II ε-MOEA GDE3 1 7,906,528 - 2,934s 11,416,500 - 4,716s 8,511,612 - 3.493s 2 8,103,832 - 1,503s 10,051,527 - 3,394s 7,600,288 - 1,415s 3 7,908,199 - 1,440s 12,549,423 - 3,521s 7,491,761 - 1,330s 4 9,350,590 - 1,662s 10,679,523 - 3,356s 7,665,245 - 1,458s 5 8,668,416 - 1,585s 9,364,679 - 3,241s 7,876,559 - 1,388s 6 7,901,941 - 1,436s 8,445,130 - 3,356s 7,927,693 - 1,458s 7 7,857,364 - 1,441s 8,971,856 - 3,380s 7,513,919 - 1,374s 8 7,802,405 - 1,508s 10,377,024 - 3,282s 7,995,918 - 1,174s 9 8,004,845 - 1,577s 9,034,573 - 3,254s 7,853,276 - 1,230s 10 7,625,568 - 1,502s 8,792,743 - 3,285s 7,560,075 - 1,344s PESA2 ε-NSGA-II SMPSO Trang 20
23. 1 9,320,717 - 2,726s 7,965,000 - 4,292s 13,318,634 - 1,313s 2 10,636,058 - 1,591s 7,724,390 - 2,360s 12,953,245 - 729s 3 8,409,361 - 1,502s 7,778,545 - 2,328s 14,283,138 - 622s 4 8,997,942 - 1,501s 8,234,220 - 2,322s 12,331,910 - 696s 5 8,645,457 - 1,446s 8,130,270 - 2,446s 13,027,559 - 626s 6 9,702,319 - 1,520s 8,073,367 - 2,242s 11,849,872 - 617s 7 9,684,004 - 1,412s 7,907,211 - 2,143s 14,327,763 - 555s 8 9,435,869 - 1,414s 7,742,396 - 2,099s 15,375,186 - 563s 9 8,796,411 - 1,404s 7,936,860 - 2,353s 15,591,372 - 580s 10 10,056,318 - 1,426s 7,821,593 - 2,090s 14,998,820 - 565s Liên quan trực tiếp đến nội dung của mục này, có 01 công trình đã được công bố trong Tạp chí trong nước (CT4- 2018). Một số nội dung thử nghiệm trình bày trong luận án đã được bổ sung thêm, kết quả mở rộng hơn so với nội dung trong bài báo CT4. 3.3.2 Bài toán cân bằng nguồn lực 3.3.2.1 Giới thiệu bài toán Cân bằng nguồn nhân lực là bài toán về phân phối, chia sẻ các nguồn lực cho các cá nhân hoặc tập thể trong dự án để thực hiện các công việc trong dự án. Bài toán là một trong các nội dung quan trọng của tiến trình Quản lý dự án và là điều kiện cần thiết để đảm bảo tính cân đối giữa các tác nhân dự án trong quá trình hoạt động. 3.3.2.2 Ứng dụng mô hình Unified Game-Based model cho bài toán Với các đặc điểm của bài toán cân bằng nguồn lực không có sự hiện diện của chủ đầu tư, theo như mô hình Unified Game-Based, ta cần thêm vào người chơi ảo – chủ đầu tư để vẫn có thể đảm bảo nguyên tắc là luôn xét tới quyền lợi của toàn bộ dự án. Từ đó ta có mô hình cho bài toán này như sau: = 〈{푃0 , 푃}, {푆0, 푆푖}, { 0, 푖}, 푅 〉 (3.24) Trong đó: 푃0 : là chủ đầu tư của dự án 푆0 = {푠01, , 푠0푗, , 푠0 0 }: tập chiến lược của người chơi đặc biệt, trong đó 0 là số lượng các tài nguyên chưa được phân phối 0: 푆0 → ℝ là hàm thưởng phạt (payoff function) của chủ đầu tư tham chiếu chiến lược của người chơi đặc biệt sang dạng số thực : Số lượng các nhóm/phòng/ban có yêu cầu về nguồn lực 푃 = { 1, , 푖, , }: là tập người chơi - các đơn vị tham gia 푆푖 = {푠푖1, , 푠푖푗, , 푠푖 푖 }: là tập các chiến lược của người chơi 푖(1 ≤ 푖 ≤ ) và 푖 là số lượng tài nguyên người chơi i tham gia 푖: 푆i → ℝ : là hàm thưởng phạt của người chơi i, tham chiếu chiến lược người chơi i sang 1 giá trị số thực 푅 : là không gian vector biểu diễn C các xung đột của bài toán 3.3.2.3 Các tham số của mô hình Chiến lược của người chơi đặc biệt Trang 21
24. Ký hiệu dưới dạng 푆0 = {푠01, , 푠0푗, , 푠0 0}, mỗi 푠0푗 đại diện cho thông tin về nguồn lực bao gồm các thông tin về: loại nguồn lực, các loại kỹ năng, đặc tả riêng của nguồn lực, chi phí sử dụng nguồn lực. Chiến lược của các người chơi khác Chiến lược của người chơi i có dạng: 푆푖 = {푠푖1, , 푠푖푗, , 푠푖 푖 }: là tập các chiến lược của người chơi 푖(1 ≤ 푖 ≤ ) và 푖 là số lượng tài nguyên người chơi i tham gia. Trong một tài nguyên có thêm các yêu cầu khác nhau khác nhau, ví dụ như về khoảng thời gian sử dụng, loại kỹ năng, công nghệ , những thông tin này sẽ được chứa trong các 푠푖푗. Không gian vector biểu diễn tập xung đột Trong không gian xung đột 푅 gồm có các vector 푣⃗ ∈ 푅 có thể được mô tả như sau: {푠0 , 푠 푞, , 푠 }, trong đó 푠0 ∈ 푆0 đại diện cho người chơi đặc biệt (quyền lợi của dự án) và 푠 푞, 푠 ∈ 푆푖, trong đó (1 ≤ , ≤ ), (1 ≤ 푞 ≤ ) và (1 ≤ ≤ ), trong đó các chiến lược trong 푣⃗ ∈ 푅 đều thuộc về một người chơi mà có 푠0 là thông tin phân phối do 푃0 cho phép và các 푠 푞, 푠 ∈ 푆푖 là kết quả chọn lựa việc phân phối tài nguyên này. Trong 푣⃗ ∈ 푅 có tồn tại 푠0 ∈ 푆0 bởi vì ngoài việc các người chơi cạnh tranh với nhau về một loại tài nguyên, giữa chủ đầu tư 푃0 cũng có sự xung đột với chiến lược của các người chơi còn lại. 3.3.2.4 Cài đặt giải thuật và thử nghiệm Dữ liệu thử nghiệm Trong phần thực nghiệm này, luận án sử dụng dữ liệu thông tin của một dự án phần mềm tại Việt Nam, là một module thuộc giải pháp ERP mà doanh nghiệp phần mềm đó sử dụng, thông tin về dự án phần mềm như sau: Tên dự án: module HRM, trong giải pháp cBIZ – hệ thống ERP cho doanh nghiệp nhỏ của công ty NEW CREATION, trụ sở tại Hà Nội. Thời gian bắt đầu: 1.8.2012, thời gian kết thúc: 30.1.2013. Quy mô dự án: 54 man/months Phân tích kết quả Kết quả thực nghiệm được thực hiện ở trong bảng 3.21, các giả trị trong bảng biểu diễn kết quả thu được từ 3 thuật toán kết được ghi nhận khi giá trị Ꜫ đạt ngưỡng 0.0001 và số lượng chiến thuật được giới hạn bằng 5. Kết quả cho thấy thuật toán CFR+ có tốc độ hội tụ nhanh vượt trội, trong khi thuật toán Fictitious Play là tồi nhất. Tuy nhiên việc áp dụng các thuật toán này vào việc xử lý bài toán và giải mô hình Unified Game-based model là khả thi. Liên quan trực tiếp đến nội dung của mục này, có 01 công trình đã được công bố trong Hội nghị trong nước CT3 - 2018. Trang 22
25. KẾT LUẬN VÀ KIẾN NGHỊ Kết luận Theo PMBOK, vấn đề xung đột trong quản lý dự án được nhắc tới như là một công việc nhỏ trong một số lĩnh vực kiến thức chính của quản lý dự án, việc quản lý xung đột như vậy chưa tương xứng với hậu quả mà xung đột gây ra, như đã phân tích tại phần mở đầu [2]. Những thiệt hại về xung đột xảy ra cho quản lý dự án là đáng kể, cùng với đó ảnh hưởng của hoạt động dự án và quản lý dự án với đời sống xã hội cũng vô cùng lớn. Vì vậy hiện trạng về việc không có nhiều nghiên cứu liên quan tới vấn để xử lý các xung đột trong quản lý dự án một cách tổng quan là cần được khắc phục. Có rất ít các nghiên cứu cụ thể đề xuất tới các khía cạnh kỹ thuật như mô hình hóa xung đột, hoặc đưa ra một phương án giải quyết cụ thể cho các vấn đề này. Vì vậy, việc đưa ra phương thức giải quyết cụ thể như trong luận án đã trình bày là cần thiết cho việc giải quyết một vấn đề quan trong của quản lý dự án. Cụ thể, phương thức giải quyết trên đã áp dụng trong một số bài toán hợp xung đột điển hình của các dự án đầu tư về Công nghệ thông tin như: đấu thầu, quản lý rủi ro, thanh toán dự án, cân bằng nguồn lực. Việc ứng dụng và thử nghiệm cho thấy các vấn đề trên đã được giải quyết để tìm ra giải pháp các bên tham gia đều hài lòng. Qua nghiên cứu, luận án đã khẳng định được một số đóng góp cơ bản đối với lĩnh vực nghiên cứu đó là: nghiên cứu thành công một mô hình dựa trên lý thuyết trò chơi, mang tên gọi là Unified Game-based model, có khả năng mô hình các lớp bài toán xung đột trong quản lý dự án. Mô hình mang đầy đủ các thông tin cụ thể, và truyền tải hiệu quả vào các thuật toán tối ưu để giải quyết bằng cách sử dụng khá niệm cân bằng Nash. Với giải pháp cân bằng Nash tìm được, sẽ đem lại một công cụ hữu ích cho người quản lý dự án và các thành viên trong việc ra quyết định liên quan tới các xung đột. Cụ thể hơn, luận án được thực hiện những mục tiêu: ▪ Phân tích tổng quan các vấn đề xung đột tồn tại trong một dự án và các đặc điểm cần có trong mô hình hóa. Trong phần đầu của nghiên cứu đã chỉ ra rằng, các mô hình hiện tại có nhiều vấn đề ở một vài đặc điểm sau như: riêng đối với bài toán trong Quản lý dự án, dù là không liên quan tới những người đại diện dự án hoặc chủ đầu tư dự án thì cũng cần phải xem xét tới lợi ích này, vì rõ ràng rằng các vấn đề riêng lẻ của dự án được giải quyết thì mục tiêu cũng là tốt cho toàn bộ dự án. Thêm nữa, các mô hình trò chơi, nơi cần sự cân bằng giữa lợi ích của người chơi, cũng là nơi sẽ xảy ra tranh chấp về lợi ích thì các mô tả, ràng buộc về tranh chấp (hoăc là xung đột) này chưa được mô tả. Vì vậy, đây là điều kiện bắt buộc của mô hình diễn giải xung đột ▪ Xây dựng mô hình chung về mô hình hóa dựa trên lý thuyết trò chơi cho tất cả các loại xung đột trong quản lý dự án, đồng thời đảm bảo rằng mô hình có thể giải quyết bằng các thuật toán tối ưu đa mục tiêu phù hợp, về việc chứng minh đảm bảo việc có thể giải quyết được mô hình, không chỉ từ các nghiên cứu, phân tích, các bài báo được công bố trong quá trình thực hiện luận án cũng cho thấy rằng kết luận trên là có cơ sở. Các dữ liệu diễn tả trong phần giới thiệu các bài toán: thanh toán dự án, quản lý rủi ro, cân bằng nguồn lực và đấu thầu nhiều vòng được chuyển trọn vẹn sang dữ liệu của thuật toán ▪ Nghiên cứu cụ thể chính về các vấn đề xung đột như: đấu thầu nhiều vòng và phương pháp đối phó rủi ro. Ngoài ra có 1 số vấn đề khác như: thanh toán dự án, Trang 23
26. cân bằng nguồn lực. Các vấn đề trên được chia đồng đều thành 2 loại xung đột như đã phân tích, bài toán đấu thầu nhiều vòng và thanh toán dự án có sự xuất hiện của chủ đầu tư trong xung đột. Hai bài toán còn lại là: quản lý rủi ro và cân bằng nguồn lực là các xung đột giữa các đối tượng nằm trong dự án, và theo như mô hình, cần sự xuất hiện của người chơi đặc biệt. Như vậy, các loại của xung đột được thử nghiệm đồng đều, nằm trên nhiều mảng dự án khác nhau: tài chính, đấu thầu, rủi ro và nhân sự. Có thể kết luận rằng việc thử nghiệm thuật toán do hạn chế về thời gian, tuy nhiên đã được xem xét kỹ càng ▪ Áp dụng thử nghiệm trên một hệ thống phần mềm hỗ trợ tin cậy và đánh giá Từ các kết quả nghiên cứu có thể kết luận là lớp các bài toán xung đột trong quản lý dự án đã được phân tích rõ ràng để đưa ra một mô hình lý thuyết trò chơi phù hợp. Mô hình Unified Game-based dựa trên các nghiên cứu về lý thuyết trò chơi và cân bằng Nash là một công cụ hữu ích trong việc tìm kiếm ra giải pháp win - win của xung đột với các đặc điểm riêng biệt sau: ▪ Mô hình bài toán thống nhất và rõ ràng ▪ Mô hình có tính bao quát với nhiều dạng xung đột trong Quản lý dự án ▪ Mô hình mang đầy đủ đặc điểm và dữ liệu về xung đột ▪ Mô hình có thể ứng dụng vào các giải thuật để tìm ra đáp án ▪ Việc giải quyết mô hình bằng thuật toán đều được thực hiện trong thời gian khả thi ngay kể cả với dữ liệu của những dự án lớn Kiến nghị Các hướng nghiên cứu có thể phát triển là rất rộng, đặc biệt ngay trong lĩnh vực quản lý dự án cũng có rất nhiều tiềm năng, bởi vì quản lý dự án là một trong những hoạt động kinh tế quan trọng nhất. Các mục tiêu phát triển của luận án bao gồm: ▪ Nghiên cứu cần được phát triển lên với các ứng dụng trong nhiều loại xung đột khác để có thể cải tiến Unified Game-based model hoàn thiện hơn ▪ Thử nghiệm thêm với các giải thuật khác để đánh giá thêm sự phù hợp của mô hình Unified Game-based model đối với các thuật toán ▪ Tìm hiểu thêm các công cụ khác ngoài MATLAB, GAMBIT trong việc áp dụng ▪ Tìm hiểu, phát triển thêm các thuật toán phù hợp với bài toán Xung đột trong quản lý dự án nói vào trong thư viện của phần mềm mã nguồn mở MOEA framework ▪ Tích hợp lại các phần mềm riêng rẽ trợ giúp ra quyết định cho các xung đột hiện tại thành một hệ thống phần mềm Trợ giúp ra quyết định ▪ Các phần mềm trợ giúp quyết định riêng rẽ có thể tích hợp vào các công cụ sử dụng trong quản lý dự án, tạo ra một phần mềm quản lý dự án thông minh Ngoài ra, những kết quả nghiên cứu và thử nghiệm cũng cần được truyền tải, công bố lên một hoặc nhiều hệ thống website về lĩnh vực lý thuyết trò chơi. Việc chia sẻ sẽ giúp cho nghiên cứu và Unified Game-based model có thêm các nhận xét, phản biện từ những nhà nghiên cứu khác để góp phần hoàn thiện hơn. Trang 24
27. DANH MỤC CÁC CÔNG TRÌNH ĐÃ CÔNG BỐ CỦA LUẬN ÁN CT1. Trinh Bao Ngoc, Huynh Quyet Thang, Bui Duc Hung, Le Tuan Dung (2016). Modeling and Developing Project Payment Schedule Algorithm Using Genetic Algorithm and Nash Equilibrium. Tạp chí Khoa học và Công nghệ các Trường đại học kỹ thuật số 113 – Năm 2016, trang 137-143, ISSN 2354-1083 (số xuất bản bằng tiếng Anh) CT2. Bao Ngọc Trinh, Quyet Thang Huynh, Thuy Linh Nguyen (2017). Research on Genetic Algorithm and Nash Equilibrium in Multi-Round Procurement. In New Trends in Intelligent Software Methodologies, Tools and Techniques, H. Fujita et al. (Eds.), IOS Press, 2017. Doi:10.3233/978-1-61499-800-6-51, pp. 51-64 Scopus and Web of Science Indexed. CT3. Trịnh Bảo Ngọc, Huỳnh Quyết Thắng, Lê Công Thành, Lê Bá Trường Giang, Trần Quang Huy. Một hướng tiếp cận của thuật toán FICTITIOUS PLAY đối với bài toán phân bổ nguồn lực. Kỷ yếu Hội nghị Quốc gia lần thứ XI về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR) – Hà Nội, Ngày 9-10/8/2018, Trang 297-303, ISBN: 978-604-913-749-5 CT4. Bao-Ngoc Trinh, Quyet-Thang Huynh, Xuan-Thang Nguyen, Van-Quyen Ngo, Thanh- Trung Vu (2018). Application of Nash Equilibrium based Approach in Solving the Risk Responses Conflicts. Journal of Science and Technology (JST) - Le Quy Don Technical University - No. 193 (10-2018), Section on Information and Communication Technology – Number 12 (10-2018), Pages 17-31, ISSN 1859-0209. CT5. Bao Ngoc Trinh, Quyet Thang Huynh, Xuan Thang Nguyen (2019). Nash Equilibrium model for conflicts in project management. Journal of Computer Science and Cybernetics, ISSN: 1813-9663, V.35, N.2 (2019), 167–184; DOI 10.15625/1813-9663/35/2/13095 CT6. Bao Ngoc Trinh, Quyet Thang Huynh, Xuan Thang Nguyen, Phuong Chi Luong and Nguyen Khanh Ho (2019). Applying a Unified Game-Based Model in a Payment Scheduling Problem and Design of Experiments using MOEA Framework. In New Trends in Intelligent Software Methodologies, Tools and Techniques, H. Fujita et al. (Eds.), IOS Press, 2019. Doi:10.3233/FAIA190038, pp. 55-68 Scopus and Web of Science Indexed. CT7. Dac-Nhuong Le, Gia Nhu Nguyen, Trinh Ngoc Bao, Nguyen Ngoc Tuan, Huynh Quyet Thang, Suresh Chandra Satapathy (2020). MMAS Algorithm and Nash Equilibrium to Solve Multi-Round Procurement Problem. International Conference on Emerging Trends and Advances in Electrical Engineering and Renewable Energy (ETAEERE-2020). ISBN 978-981- 10-4762-6 CT8. Bao Ngoc Trinh, Quyet-Thang Huynh , Xuan-Thang Nguyen, Gia Nhu Nguyen, Suresh Chandra Satapathy, Shui-Hua Wang and Dac-Nhuong Le (2020). Solving Multi-Round Procurement Problem with PSO Algorithm and Nash Equilibrium Theory. Manuscript sumbitted for publication, International Journal of Computational Intelligence Systems, ISSN: 1875-6883. ISI, Q2 journal, IF=1.838. CT9. Dac-Nhuong Le, Gia Nhu Nguyen, Harish Garg, Quyet-Thang Huynh, Trinh Ngoc Bao, Nguyen Ngoc Tuan (in press), Optimizing Bidders Selection of Multi-Round Procurement Problem in Software Project Management Using Parallel Max-Min Ant System Algorithm, Journal of Computers, Materials & Continua. ISSN: 1546-2218. DOI:10.32604/cmc.2020. ISI, Q1, IF=4.89.