Luận văn Áp dụng mô hình đấu giá qua mạng cho bài toán ghép cặp có trọng

TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN HỆ THỐNG THÔNG TIN W X NGUYỄN THANH BÌNH ĐÀO LÊ TÍN ÁP DỤNG MÔ HÌNH ĐẤU GIÁ QUA MẠNG CHO BÀI TOÁN GHÉP CẶP CÓ TRỌNG KHÓA LUẬN CỬ NHÂN TIN HỌC 07/2005 TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN KHOA CÔNG NGHỆ THÔNG TIN BỘ MÔN HỆ THỐNG THÔNG TIN NGUYỄN THANH BÌNH - 0112175 ĐÀO LÊ TÍN – 0112453 ÁP DỤNG MÔ HÌNH ĐẤU GIÁ QUA MẠNG CHO BÀI TOÁN GHÉP CẶP CÓ TRỌNG KHÓA LUẬN CỬ NHÂN TIN HỌC GIÁO VIÊN HƯỚNG DẪN Th.S LÊ THỊ NHÀN NIÊN KHÓA 2001 - 2005 1 Lời cảm ơn Trong quá trình thực hiện đề tài chúng em đã gặp rất nhiều khó khăn. Tuy nhiên chúng em đã nhận được rất nhiều sự giúp đỡ của mọi người xung quanh. Chính nhờ vậy mà chúng em có thể hoàn thành tốt luận văn. Đầu tiên chúng em xin gửi lời cảm ơn đến cô Lê Thị Nhàn, người trực tiếp hướng dẫn chúng em trong quá trình làm luận văn. Trong thời gian vừa qua cô luôn tận tình hướng dẫn chúng em với tất cả những gì có thể. Một lần nữa chúng em chân thành cảm ơn sự giúp đỡ của cô. Trong suốt thời gian học tập tại Trường Đại Học Khoa Học Tự Nhiên, để có được như ngày hôm nay chúng em luôn ghi nhớ sự tận tình truyền thụ kiến thức của các thầy cô, cũng như sự động viên giúp đỡ của bạn bè. Và sau cùng, chúng con xin cảm ơn cha mẹ, những người đã sinh thành, dưỡng dục và nuôi dạy chúng con nên người. Cha mẹ luôn là nguồn động viên trong những lúc chúng con gặp khó khăn nhất. Cha mẹ luôn vất vả để mang lại cho chúng con điều kiện vật chất tốt nhất, giúp chúng con có thể thuận lợi trong học tập và nghiên cứu. 2 Mục Lục Lời cảm ơn................................................................................................................1 Mục Lục....................................................................................................................2 Chương 1. Giới Thiệu..............................................................................................5 1.1 Tổng quan...........................................................................................................5 1.2 Vấn đề đặt ra......................................................................................................5 1.3 Mục tiêu của đề tài ............................................................................................6 Chương 2. Đấu giá điện tử ......................................................................................7 2.1 Giới thiệu............................................................................................................7 2.2 Các hình thức đấu giá .......................................................................................9 2.2.1 Phân loại chung .......................................................................................... 9 2.2.2 Đấu giá kiểu Anh (Enghlish Auction)...................................................... 10 2.2.3 Đấu giá kiểu Hà Lan (Dutch Auction) ..................................................... 12 2.2.4 Đấu giá kín và chọn giá cao nhất (Sealed-bid first-price auction)........... 13 2.2.5 Đấu giá kín và chọn giá thấp thứ hai (Sealed-bid second-price auction) 13 2.2.6 Đấu giá hai phía kép (Double Auction) ................................................... 13 2.3 Đấu giá điện tử.................................................................................................14 2.3.1 Giới thiệu.................................................................................................. 14 2.3.2 Các thành phần tham gia vào đấu giá điện tử .......................................... 15 2.3.3 Quy trình hoạt động chung....................................................................... 16 2.3.4 Các luật trong đấu giá điện tử .................................................................. 17 2.4 Đấu giá nghịch (Reverse-Auction) .................................................................18 2.4.1 Khái niệm................................................................................................. 18 2.4.2 Một số đặc điểm....................................................................................... 19 2.4.2.1 Đối tượng tổ chức .............................................................................19 2.4.2.2 Các mặt hàng và điều kiện cho đấu giá nghịch ................................19 2.4.2.3 Ưu điểm của đấu giá ngược ..............................................................20 2.4.2.4 Khuyết điểm của đấu giá ngược .......................................................20 2.5 Sự phát triển của đấu giá - đấu giá nghịch điện tử tại Việt Nam ...............21 Chương 3. Khảo sát một số sàn đấu giá điện tử hiện hành.................................22 3.1 Priceline.com....................................................................................................22 3.2 UBid.Com .........................................................................................................23 3.3 Ebay.com ..........................................................................................................25 3.4 Heya.com.vn.....................................................................................................26 3.5 Skyauction.com................................................................................................27 3.6 Luxurylink.com ...............................................................................................29 3.7 Lastminute.com ...............................................................................................31 3 3.8 Viet-bid.com.....................................................................................................32 3.9 Chodaugia.bancanbiet.com ............................................................................33 3.10 Bảng đánh giá chung ....................................................................................34 Chương 4. Phương pháp thực hiện đề tài ............................................................35 4.1 Mô tả bài toán ..................................................................................................35 4.2 Hướng giải quyết cho bài toán .......................................................................35 4.2.1 Định nghĩa bài toán .................................................................................. 35 4.2.2 Giới thiệu thuật giải di truyền [3] ............................................................ 37 4.2.3 Áp dụng thuật giải di truyền .................................................................... 39 4.3 Triển khai hệ thống .........................................................................................45 Chương 5.Phân tích và thiết kế .............................................................................48 5.1 Usecase của ứng dụng ....................................................................................48 5.1.1 Lược đồ Usecase ...................................................................................... 48 5.1.2 Diễn giải cho lược đồ Usecase................................................................. 49 5.1.2.1 Các Actor ..........................................................................................49 5.1.2.2 Các Usercase.....................................................................................50 5.2 Sequence Diagram cho một số Use Case chính.............................................52 5.2.1 Đăng nhập (Login) ................................................................................... 52 5.2.1.1 Luồng xử lý chính.............................................................................52 5.2.1.2 Luồng xử lý phụ - Đăng nhập sai .....................................................52 5.2.1.3 Luồng xử lý phụ - Đã đăng nhập rồi.................................................53 5.2.2 Đăng ký tài khoản (Register Account)..................................................... 53 5.2.3 Gởi yêu cầu (Post requirement for room) ................................................ 54 5.2.4 Đặt phòng trực tiếp (Booking) ................................................................. 55 5.2.5 Đấu giá (bidding) ..................................................................................... 56 5.2.5.1 Luống xử lý chính.............................................................................56 5.2.5.2 Luồng xử lý phụ - Chưa tới giờ đấu giá ...........................................57 5.2.6 Điều khiển đấu giá(Auction Process)....................................................... 57 5.3 Sơ đồ kiến trúc .................................................................................................58 Chương 6.Cài đặt ...................................................................................................59 6.1 Dữ liệu...............................................................................................................59 6.1.1 Sơ đồ dữ liệu ............................................................................................ 59 6.1.2 Mô tả chi tiết các thành phần dữ liệu ....................................................... 60 6.1.2.1 KHACHHANG.................................................................................60 6.1.2.2 THANHPHO ....................................................................................61 6.1.2.3 DIADANH........................................................................................61 6.1.2.4 LOAIKHACHSAN...........................................................................61 6.1.2.5 KHACHSAN ....................................................................................62 6.1.2.6 LOAIPHONG ...................................................................................63 6.1.2.7 HANGPHONG .................................................................................63 6.1.2.8 DICHVUKHACHSAN.....................................................................64 4 6.1.2.9 YEUCAUPHONG............................................................................64 6.1.2.10 DATPHONGTRUCTIEP ..............................................................66 6.1.2.11 TIENTRINHDAUGIA ..................................................................66 6.1.2.12 KETQUADAUGIA .......................................................................67 6.1.2.13 FEEDBACK ..................................................................................67 6.1.2.14 NHANVIEN ..................................................................................68 6.1.2.15 QUYENHAN.................................................................................69 6.1.2.16 PHANQUYEN...............................................................................69 6.1.2.17 CONGVIEC...................................................................................69 6.1.2.18 DANHSACHLIENKET ................................................................70 6.1.2.19 TINTUC.........................................................................................70 6.2 Giao diện...........................................................................................................72 6.2.1 Màn hình chính ........................................................................................ 72 6.2.2 Màn hình đăng ký khách hàng ................................................................. 73 6.2.3 Màn hình đăng nhập................................................................................. 74 6.2.4 Màn hình đăng yêu cầu bước 1 ................................................................ 75 6.2.5 Màn hình đăng yêu cầu bước 2 ................................................................ 76 6.2.6 Màn hình đăng yêu cầu bước 3 ................................................................ 76 6.2.7 Màn hình đăng yêu cầu bước 4 ................................................................ 77 6.2.8 Màn hình đăng yêu yêu cầu bước 5 ......................................................... 78 6.2.9 Màn hình thiết lập thông số hệ thống....................................................... 79 6.2.10 Màn hình đấu giá bước 1....................................................................... 80 6.2.11 Màn hình đấu giá bước 2....................................................................... 81 6.2.12 Màn hình thống kê kết quả đấu giá ....................................................... 82 Chương 7.Tổng kết ................................................................................................83 7.1 Kết luận ............................................................................................................83 7.2 Hướng phát triển .............................................................................................84 Tài liệu tham khảo .................................................................................................85 5 Chương 1. Giới Thiệu 1.1 Tổng quan Ngày nay khoa học kỹ thuật ngày càng phát triển mạnh mẽ trên nhiều phương diện trong đó có Công nghệ thông tin và Viễn thông. Sự ra đời của Internet đã làm cho thương mại điện tử (E_commerce) phát triển nhanh hơn và chi phối sâu sắc đến đời sống của con người trên nhiều lĩnh vực khác nhau. Một trong những lĩnh vực có truyền thống lâu đời đạt được nhiều thành công rực rỡ là đấu giá (Auction). Điển hình cho sự thành công đó không thể không kể tới các sàn đấu giá nổi tiếng như ebay, ubid, lastminute... Ở Việt Nam, tuy thương mại điện tử vẫn còn mang tính trải nghiệm nhưng cũng đã xuất hiện một số các sàn giao dịch đấu giá tiên phong như heya.com, chodaugia.bancanbiet.com, vietbid.com… Không phải ngẫu nhiên mà đấu giá điện tử lại thành công đến như vậy. Điều này có thể giải thích bằng những lợi ích mà đấu giá điện tử đem lại nhờ sự kết hợp những ưu điểm của đấu giá truyền thống và sức mạnh của thương mại điện tử. Đó là khả năng tạo ra một môi trường cạnh tranh công bằng trong quá trình mua bán. Người mua và người bán đều được đối xử bình đẳng trong quá trình đấu giá. Người mua dễ dàng tiếp cận với nhiều loại hàng hóa và có cơ hội được ra giá, còn người bán có thể giới thiệu hàng hóa cho nhiều người mua và bán được hàng hóa với giá mong muốn. Và kết quả của mỗi giao dịch đấu giá phản ánh đúng đắn quy luật cung cầu tự nhiên của thị trường. Ngoài ra, đấu giá lại rất dễ áp dụng cho nhiều mặt hàng khác nhau, có hình thức đa dạng, có thể phục vụ cho nhiều mục đích. Do đó việc phổ biến của hình thức đấu giá trên mạng là cần thiết. 1.2 Vấn đề đặt ra Trong bối cảnh nền kinh tế phát triển nhanh, người tiêu dùng rất khó khăn trong việc mua một món hàng hợp ý mà giá cả lại vừa túi tiền từ rất nhiều các nhà cung cấp trên thị trường. Các mô hình kinh doanh qua mạng trong thực tế rất ít quan tâm tới việc đáp ứng hết các nhu cầu này. Thông thường chúng chỉ đặt nặng việc mời gọi khách hàng qua hình thức quảng cáo và giới thiệu hàng hóa nhằm phục vụ cho lợi ích của người bán mà thôi. Trong các loại đấu giá có một hình thức có thể giải 6 quyết được vấn đề trên đó là đấu giá ngược (reverse auction). Với đấu giá ngược người bán sẽ cạnh tranh giành quyền bán hàng cho người mua. Khi đó người mua sẽ có nhiều cơ hội mua được món hàng với giá mình cần. Tuy nhiên đấu giá ngược nếu áp dụng không khéo có thể dẫn đến hiện tượng phá giá do những người bán có thực lực mạnh gây nên. Vậy thì làm sao có thể tạo ra một môi trường giúp người mua có thể mua được món hàng với giá họ mong muốn, người bán có thể bán được hàng với số lượng lớn và đồng thời đảm bảo lợi nhuận tồn tại cho sàn giao dịch? Để có thể đáp ứng được nhu cầu trên, một sàn đấu giá ngược với mô hình kinh doanh phù hợp sẽ được xây dựng nhằm phát huy những thế mạnh và hạn chế một số nhược điểm của đấu giá điện tử. 1.3 Mục tiêu của đề tài Luận văn được thực hiện với những mục tiêu như sau: 1. Tìm hiểu các kiến thức căn bản về thương mại điện tử. 2. Nghiên cứu về đấu giá, đấu giá điện tử, và đấu giá ngược. 3. Khảo sát các sàn giao dịch đấu giá trên thế giới và Việt Nam. 4. Xây dựng bài toán ứng dụng cho đấu giá điện tử và giải quyết bài toán. 5. Cài đặt hệ thống đấu giá ngược, hệ thống đấu giá B&T. 7 Chương 2. Đấu giá điện tử Bán đấu giá từ rất lâu đã là hình thức kinh doanh, mua bán quen thuộc đối với các nền kinh tế phát triển trên thế giới. Với sự phát triển nhanh chóng của công nghệ thông tin và mạng Internet, bán đấu giá đã chuyển sang một tầm vóc mới: hình thức đấu giá qua mạng hình thành và ngày càng phát triển. 2.1 Giới thiệu Với một lịch sử lâu đời, đấu giá là một hoạt động thương mại mang tính truyền thống. Có lẽ bạn đã từng thấy hoạt động đấu giá qua phim ảnh hoặc đọc về chúng, bạn cũng có thể đã tham gia và tin rằng không gì có thể đơn giản hơn? Nó đơn giản chỉ là một vài người ra giá cho một vật gì đó, giá nâng lên rồi một người nào khác lại đưa ra một giá khác cao hơn, và khi mọi người đều im lặng thì điều đó có nghĩa là vật rao bán được bán. Có lẽ điều này đúng nhưng chỉ bấy nhiêu thôi mà muốn mô tả hết về một hoạt động kinh doanh có trị giá nhiều tỉ đô la thì thật là sai lầm. Những gì bạn thấy có thể chỉ là một hình thức kinh điển và thường thấy của đấu giá. Trong thực tế có rất nhiều các dạng đấu giá khác nhau, bên cạnh hình thức quen thuộc với giá đưa ra tăng dần (ascending bid) còn bao gồm các dạng khác như đấu giá giảm, đấu giá kín (sealed-bid), đấu giá đồng thời (simultaneous-bid), đấu giá bắt tay (handshake-bid), đấu giá gợi ý bí mật (whispered bid). Ngoài ra còn các hình thức khác rất hiếm gặp ngày nay dù đã trải qua hàng trăm năm lịch sử và đã tham gia trong việc bán một khối lượng tài sản khổng lồ. Các hình thức đấu giá rất hữu ích trong việc bán các sản phẩm hàng hóa mà giá trị của nó chưa được xác định một cách rõ ràng hoặc có giá thị trường không cố định. Đấu giá có thể được áp dụng cho nhiều loại mặt hàng, có thể là các loại mặt hàng mà số lượng chỉ là một như một bức tranh gốc, một tác phẩm nghệ thuật, hoặc cho các loại hàng hóa có số luợng lớn như vàng hay cổ phần. Đối với các quốc gia có sự chuyển đổi từ sở hữu tập trung bao cấp sang nền kinh tế thị trường, đấu giá cung cấp khả năng cho việc định giá trị hàng hóa hay cơ sở hạ tầng sẵn có. Trong thực tế các nguồn có thể đưa ra đấu giá gần như là mọi thứ, từ đất công, thú nuôi, 8 rượu vang, hoa, cá, xe hơi, hợp đồng xây dựng đến cổ phần. Đặc điểm chung của những thứ này là giá trị của hàng hóa phải biến thiên đủ để ngăn ngừa trường hợp giá bị đứng lại một cách hoàn toàn trong quá trình đấu giá. Xem xét một cách đơn giản, đấu giá nói chung là một phương pháp phân phối những loại hàng hóa khan hiếm về mối tương quan giữa cung và cầu, một phương pháp được xây dựng dựa trên sự cạnh tranh. Đây có thể nói là loại thị trường trong sáng, minh bạch và rõ ràng nhất: một người bán sẽ tìm cách giành được nhiều tiền nhất có thể, và người mua muốn trả ít tiền nhất trong phạm vi cho phép. Đấu giá cung cấp lợi ích của sự giản đơn trong việc quyết định giá dựa vào thị trường. Nó thật sự hiệu quả trong ngữ cảnh thị trường cạnh tranh gắt gao và không biết đích xác giá trị hàng hóa. Một phiên đấu giá không giống với các phương pháp bán hàng khác, thông thường người chủ trì phiên đấu giá không sở hữu món hàng mang đấu giá họ chỉ đứng ra với tư cách đại diện cho một nhóm người nào đó, có thể là bên bán, bên mua hoặc đối tác thứ ba. Thông thường người mua biết rõ hơn người bán về giá trị hàng hóa. Vậy hình thức đấu giá nào là tốt nhất? Đây là câu hỏi không có đáp án chính xác. Bởi như đã nói có rất nhiều loại đấu giá với các đặc tính khác nhau, tùy theo từng hoàn cảnh và các loại đấu giá bạn sẽ thu được các kết quả thích hợp khác nhau. Chỉ có đi vào nghiên cứu các loại hình đấu giá cụ