BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI - LÝ THỊ THANH VÂN LÝ THUYẾT DANH SÁCH VÀ Q TRÌNH TỰ ĐỘNG HĨA VẬN CHUYỂN TẠI NHÀ MÁY SẢN XUẤT XI MĂNG VIỆT NAM Chuyên ngành : Toán Tin ứng dụng LUẬN VĂN THẠC SĨ KỸ THUẬT NGƯỜI HƯỚNG DẪN KHOA HỌC GS.TSKH LÊ HÙNG SƠN Hà Nội – 2012 MỤC LỤC DANH MỤC HÌNH VẼ MỞ ĐẦU CHƯƠNG I LÝ THUYẾT DANH SÁCH 1.1 Các phép toán bản( Elementary Operations) 1.1.1 Ký hiệu danh sách(List notation) 1.1.2 Chiều dài danh sách(Length) 1.1.3 Sự ghép vào nhau, nối vào nhau(Concatenation ) 1.1.4 Ánh xạ(Map) 1.1.5 Bộ lọc(Filter) 1.1.6 Phép toán tham chiếu(Operator Precedence) 10 1.1.7 Phép toán rút gọn(The reduction operator) 11 1.1.8 Giá trị giả (Fictitious values) 13 1.1.9 Phép đồng cấu(Homomorphisms) 14 1.1.10 Định nghĩa phép đồng cấu (Definition by homormorphisms) 16 1.2 Rút gọn có hướng đệ quy(Directed reduction and recursion) 17 1.2.1 Rút gọn bên trái phải(Left and right reduction) 17 1.2.2 Đệ quy tính chất (Recursive characterisation) 18 1.2.3 Hiệu việc cân nhắc(Eficiency cónideration) 19 1.2.4 Tính đối ngẫu tính chuyên mơn hóa(Duality and specialisation) 23 1.2.5 Sự tích lũy(Accumulation) 24 1.3 Phân đoạn phân vùng(Segments and Partitions) 25 1.3.1 Định nghĩa(Definitions) 25 1.3.2 Sự phân tích đoạn(Segment decomposition) 27 1.3.3 Cực trị(Extremal problems) 28 CHƯƠNG II CÁC ỨNG DỤNG CỦA LÝ THUYẾT DANH SÁCH 31 2.1 Bài toán lãi tức 31 2.2 Bài toán dự báo 32 2.3 Tính lãi tức hàng năm 32 2.4 Giá trị thời 33 2.5 Tiền chịu nợ hàng năm 33 2.6 Bài toán trả góp 34 2.7 Bài toán dự chi 34 2.8 Dạng chuẩn toán quy hoạch tuyến tính 35 2.9 Bài toán đối ngẫu 35 CHƯƠNG III LÝ THUYẾT DANH SÁCH VÀ QUÁ TRÌNH TỰ ĐỘNG HĨA VẬN CHUYỂN VÀO BÀI TỐN QUẢN LÝ XÍ NGHIỆP XI MĂNG 37 3.1 Đầu vào toán 37 3.2 Giải pháp 38 3.3 Mở rộng 39 CHƯƠNG IV PHÂN TÍCH THIẾT KẾ HỆ THỐNG 42 4.1 Phân tích yêu cầu 42 4.2 Phân tích chức 43 4.3 Mơ hình hóa chức 45 CHƯƠNG V ỨNG DỤNG MÔ PHỎNG 60 5.1 Đăng ký xe vào 60 5.1.1 Quản lý xe vào 61 5.1.2 Quản lý danh sách xe vào 64 5.1.3 Bảng hiển thị 65 5.1.4 Thốt chương trình 66 5.2 Quản lý thông tin 66 5.2.1 Quản lý lái xe 67 5.2.2 Quản lý xe 70 5.2.3 Quản lý loại hàng 74 5.2.4 Quản lý đơn vị nhập hàng 77 5.3 Kết xuất 80 CHƯƠNG VI KẾT QUẢ VÀ HƯỚNG PHÁT TRIỂN 81 TÀI LIỆU THAM KHẢO 83 DANH MỤC HÌNH VẼ Hình Sơ đồ phân tích chức năng……………………………………………… 44 Hình Use case hệ thống quản lý xe vào nhà máy……………………………… 45 Hình Biểu đồ lớp(class diagram)………………………………………………… 55 Hình Sơ đồ mơ hình hoạt động…………………………………………………… 55 Hình Biểu đồ hoạt động (Activity Diagram)……………………………………….56 Hình Biểu đồ …………………………………………………….…………57 Hình Màn hình chức quản lý xe vào ………………………………………60 Hình Màn hình chức quản lý xe vào ………………………………………61 Hình Màn hình chức thêm xe đăng ký vào ra(thành cơng) …………… 62 Hình 10 Màn hình chức thêm xe đăng ký vào ra(lỗi)…………………… 62 Hình 11 Màn hình chức sửa thơng tin xe đăng ký vào …………………… 63 Hình 12 Màn hình chức xóa thơng tin xe đăng ký vào ………………… …64 Hình 13 Màn hình chức chọn xe vào, xí nghiệp ………………………….65 Hình 14 Màn hình liên kết với phần cứng hiển thị danh sách xe vào ……………66 Hình 15 Màn hình quản lý thông tin xe, lái xe, loại hàng, đơn vị nhập hàng……… 67 Hình 16 Màn hình chức quản lý người lái xe………………………………… 67 Hình 18 Màn hình chức thêm người lái xe…………………………………… 68 Hình 19 Màn hình chức sửa thơng tin người lái xe…………………………… 69 Hình 20 Màn hình chức xóa thơng tin người lái xe ……………………………69 Hình 21 Màn hình quản lý xe…………………………………………………………70 Hình 22 Màn hình chức thêm thơng tin xe…………………… ………….71 Hình 23 Màn hình chức sửa thơng tin xe……………………………………….72 Hình 24 Màn hình chức xóa thơng tin xe xí nghiệp………………………73 Hình 25 Màn hình xóa thơng tin lái xe(chưa chọn ghi)………………………….73 Hình 26 Màn hình quản lý loại hàng………………………………………………….74 Hình 27 Màn hình chức sửa thơng tin hàng hóa……………………………… 75 Hình 28 Màn hình chức xóa thơng tin hàng hóa(chưa chọn ghi)………….76 Hình 29 Màn hình xóa thơng tin hàng hóa(đã chọn ghi)…………………………76 Hình 30 Màn hinh quản lý đơn vị nhập hàng…………………………………………77 Hình 31 Màn hình chức sửa thơng tin đơn vị nhập hàng……………………….78 Hình 32 Màn hình chức xóa thơng tin đơn vị nhập hàng(chưa chọn ghi)….79 Hình 33 Màn hình xóa thơng tin đơn vị nhập hàng(đã chọn ghi)……… ………79 MỞ ĐẦU Nguồn gốc Toán học ngành khoa học vấn đề thực tế mà loài người cần tìm hiểu để cải thiện sống Ngày tốn học có nhiều ứng dụng rộng dãi ngành khác Lý thuyết danh sách có nhiều ứng dụng thực tế: ứng dụng vào tốn tài chính(bài tốn lãi tức, tốn dự báo…), tốn vận tải, tốn tính min, max quy hoạch tuyến tính… Đề tài “Lý thuyết danh sách q trình tự động hóa vận chuyển nhà máy sản xuất xi măng Việt Nam”, sản phẩm đề tài ứng dụng thực tế sử dụng nhà máy, xí nghiệp xi măng Việt Nam hay công ty quản lý xe: xe bus, taxi Sản phẩm đề tài ứng dụng thực tế “Lý thuyết danh sách” Vì em chọn đề tài để nghiên cứu phép toán ứng dụng lĩnh vực khác Mục đích luận văn tìm hiểu lý thuyết danh sách ứng dụng thực tế Luận văn gồm chương: Chương I Lý thuyết danh sách Nội dung chương I đưa khái niệm, định lý, bổ đề danh sách phép toán danh sách Chương II Các ứng dụng lý thuyết danh sách Nội dung chương II tìm hiểu ứng dụng lý thuyết danh sách thực tế lĩnh vực khác Chương III Lý thuyết danh sách q trình tự động hóa vận chuyển vào tốn quản lý xí nghiệp xi măng Nội dung chương III đưa đầu vào toán, việc vận dụng lý thuyết danh sách vào tốn quản lý xí nghiệp xi măng Chương IV Phân tích thiết kế hệ thống Sử dụng UML để phân tích chức thiết kế hệ thống tốn quản lý xí nghiệp xi măng Việt nam Chương V Ứng dụng mô Chương V đưa chức từ tổng hợp đến chi tiết ứng dụng, đưa quy trình thực kết hợp với giao diện chương trình Chương VI Kết hướng phát triển Chương VI đưa kết đạt luận văn hướng phát triển mở rộng mặt lý thuyết ứng dụng thực tế Luận văn nghiên cứu góc độ tốn học, tìm hiểu danh sách nghiên cứu phép tốn danh sách Tìm hiểu thực tế giáo trình tốn học ứng dụng, giáo trình sách nước ngồi để đưa ứng dụng thực tế CHƯƠNG I LÝ THUYẾT DANH SÁCH 1.1 Các phép toán bản( Elementary Operations) 1.1.1 Ký hiệu danh sách(List notation) Danh sách(list) giá trị tuyến tính có tính chất chung tương tự bao gồm phần tử: phần tử thứ nhất, phần tử thứ hai,…, phần tử thứ n List(danh sách) gọi Sequence(tuần tự) sử dụng toán học ngành khác Một danh sách hữu hạn biểu thị cách sử dụng dấu ngoặc vng dấu phẩy Ví dụ: [1,2,3) danh sách ba số nguyên [[‘b’,’y’,’e’], [‘b’,’y’,’e’]] danh sách hai phần tử, phần tử danh sách ký tự [] danh sách trống, [a] danh sách chứa phần tử, [[]] danh sách chứa list trống, hình thức đặc biệt [m…n] sử dụng để biểu thị danh sách số nguyên tăng dần theo thứ tự từ m đến n Nếu m> n [m…n]=[] Khơng giống tập, danh sách chứa nhiều giá trị tương tự Ví dụ: [1,1] danh sách chứa hai phần tử 1,1 Danh sách giá trị đặc tính chung Điều có nghĩa có danh sách số, danh sách nhân vật, chí liệt kê chức năng, khơng kết hợp hai loại giá trị khác danh sách Với hạn chế này, loại danh sách xem xét mơ tả cách đơn giản Một danh sách số ký hiệu [Num], danh sách ký tự ký hiệu [Char] Ví dụ: [[Num]] miêu tả danh sách kiểu số danh sách [A  B] miêu tả danh sách chức từ A đến B 1.1.2 Chiều dài danh sách(Length) Chiều dài danh sách số phần tử danh sách Chiều dài tính tốn phương thức # sau: #[a 1, a ,…a n ] = n #[] = For m