Đăng ký Đăng nhập
Trang chủ ứng dụng excel giải từng bước bài toán vận tải...

Tài liệu ứng dụng excel giải từng bước bài toán vận tải

.PDF
73
415
86

Mô tả:

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Nguyễn Thị Hoàng Oanh ỨNG DỤNG EXCEL GIẢI TỪNG BƯỚC BÀI TOÁN VẬN TẢI KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC Hà Nội – Năm 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 KHOA TOÁN Nguyễn Thị Hoàng Oanh ỨNG DỤNG EXCEL GIẢI TỪNG BƯỚC BÀI TOÁN VẬN TẢI Chuyên ngành: Toán ứng dụng KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: Th.S. Phạm Văn Duẩn Hà Nội – Năm 2017 Lời cảm ơn Trước khi trình bày nội dung chính của khóa luận, em xin bày tỏ lời biết ơn sâu sắc tới thầy giáo Th.S Phạm Văn Duẩn người đã tận tình hướng dẫn em để hoàn thành khoá luận này. Em cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô trong tổ Toán ứng dụng nói riêng và các thầy cô khoa Toán trường Đại học Sư Phạm Hà Nội 2 nói chung đã quan tâm động viên khích lệ và dạy bảo em tận tình trong suốt quá trình hoàn thành khóa luận và học tập tại khoa. Hà Nội, ngày 22 tháng 4 năm 2017 Sinh viên thực hiện Nguyễn Thị Hoàng Oanh Lời cam đoan Khoá luận tốt nghiệp này của em được hoàn thành dưới sự hướng dẫn nhiệt tình của thầy giáo, Thạc sĩ Phạm Văn Duẩn cùng với sự cố gắng của bản thân. Trong quá trình nghiên cứu, em đã tham khảo và kế thừa những thành quả nghiên cứu của các nhà khoa học và các nhà nghiên cứu với sự trân trọng và lòng biết ơn. Em xin cam đoan những kết quả nghiên cứu của đề tài Ứng dụng Excel giải từng bước bài toán vận tải không có sự trùng lặp với kết quả của các đề tài khác. Nếu sai em xin hoàn toàn chịu trách nhiệm. Hà Nội, ngày 22 tháng 4 năm 2017 Sinh viên thực hiện Nguyễn Thị Hoàng Oanh Mục lục 1 Kiến thức chuẩn bị 3 1.1 Thiết lập bài toán vận tải . . . . . . . . . . . . . . . . 3 1.2 Bảng vận tải . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Cách phá vỡ vòng và xây dựng vòng . . . . . . . . . . 12 1.4 Tìm phương án cơ sở xuất phát . . . . . . . . . . . . . 14 1.4.1 Phương pháp góc tây bắc . . . . . . . . . . . . 15 1.4.2 Phương pháp cực tiểu cước phí . . . . . . . . . 16 1.5 Các thuật toán giải bài toán vận tải . . . . . . . . . . . 16 1.5.1 Thuật toán quy 0 cước phí các ô chọn . . . . . 16 1.5.2 Thuật toán thế vị . . . . . . . . . . . . . . . . . 19 2 GIỚI THIỆU, TÌM HIỂU VỀ VBA 2.1 23 Ghi và thực hiện macro . . . . . . . . . . . . . . . . . 23 2.2 Cách thực hiện một Macro đơn giản . . . . . . . . . . . 24 2.2.1 Thực hiện macro từ một đối tượng đồ họa trong worksheet . . . . . . . . . . . . . . . . . . . . . 25 2.2.2 Chạy macro từ nút lệnh trên thanh công cụ . . 25 2.2.3 Chạy macro từ lệnh trong menu của Excel . . . 27 2.2.4 Thay đổi lựa chọn trong Macro . . . . . . . . . 29 ii Khóa luận tốt nghiệp Đại học 2.3 Nguyễn Thị Hoàng Oanh Ngữ pháp VB (Visual Basic Grammar) . . . . . . . . 29 2.3.1 Các đối tượng (Objects) . . . . . . . . . . . . . 29 2.3.2 Các phương thức (Methods) . . . . . . . . . . . 30 2.3.3 Các thuộc tính (Properties) . . . . . . . . . . . 31 2.3.4 Các biến Variables . . . . . . . . . . . . . . . . 32 2.4 Viết macro . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.4.1 Viết macro . . . . . . . . . . . . . . . . . . . . 35 2.4.2 Sửa chữa lỗi . . . . . . . . . . . . . . . . . . . . 38 2.5 Câu trúc điều khiển . . . . . . . . . . . . . . . . . . . . 39 2.5.1 Câu lệnh IF . . . . . . . . . . . . . . . . . . . . 39 2.5.2 Xây dựng câu điều kiện . . . . . . . . . . . . . 41 2.5.3 Hành động lặp (Loop) . . . . . . . . . . . . . . 44 3 Giải từng bước bài toán vận tải bằng Excel 54 3.1 Tìm phương án cơ sở xuất phát bằng phương pháp góc tây bắc . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.2 Sử dụng thuật toán thế vị giải bài toán vận tải . . . . . 58 iii Lời cảm ơn Trước khi trình bày nội dung chính của khóa luận, em xin bày tỏ lời biết ơn sâu sắc tới thầy giáo Th.S Phạm Văn Duẩn người đã tận tình hướng dẫn em để hoàn thành khoá luận này. Em cũng xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô trong tổ Toán ứng dụng nói riêng và các thầy cô khoa Toán trường Đại học Sư Phạm Hà Nội 2 nói chung đã quan tâm động viên khích lệ và dạy bảo em tận tình trong suốt quá trình hoàn thành khóa luận và học tập tại khoa. Hà Nội, ngày 22 tháng 4 năm 2017 Sinh viên thực hiện Nguyễn Thị Hoàng Oanh 1 Lời cam đoan Khoá luận tốt nghiệp này của em được hoàn thành dưới sự hướng dẫn nhiệt tình của thầy giáo, Thạc sĩ Phạm Văn Duẩn cùng với sự cố gắng của bản thân. Trong quá trình nghiên cứu, em đã tham khảo và kế thừa những thành quả nghiên cứu của các nhà khoa học và các nhà nghiên cứu với sự trân trọng và lòng biết ơn. Em xin cam đoan những kết quả nghiên cứu của đề tài Ứng dụng Excel giải từng bước bài toán vận tải không có sự trùng lặp với kết quả của các đề tài khác. Nếu sai em xin hoàn toàn chịu trách nhiệm. Hà Nội, ngày 22 tháng 4 năm 2017 Sinh viên thực hiện Nguyễn Thị Hoàng Oanh i Mục lục ii Lời mở đầu 1. Lý do chọn đề tài Quy hoạch tuyến tính là một trong số những môn học bắt buộc đối với sinh viên nhiều ngành học khác nhau từ ngành học cơ bản như toán học cho đến các ngành khoa học kĩ thuật và kinh tế. Bài toán vận tải là một dạng đặc biệt của quy hoạch tuyến tính. Song song với nghiên cứu lý thuyết, việc phát triển các chương trình máy tính giải bài toán vận tải với kích thước đủ lớn để áp dụng được vào thực tiễn cũng đã đạt được nhiều thành tựu đáng kể. Với mong muốn được nghiên cứu và tìm hiểu sâu hơn về bộ môn này đồng thời giúp sinh viên có công cụ để kiểm tra các bước làm của bài toán vận tải, bước đầu làm quen với công việc nghiên cứu khoa học, dưới góc độ là một sinh viên chuyên ngành Toán, trong phạm vi của một khoá luận tốt nghiệp em đã chọn đề tài Ứng dụng Excel giải từng bước bài toán vận tải. 2. Mục đích và nhiệm vụ nghiên cứu - Nghiên cứu về Lập trình trong Excel để giải các bước của bài toán vận tải. - Ứng dụng phần mềm Excel giải từng bước bài toán vận tải. 1 Khóa luận tốt nghiệp Đại học Nguyễn Thị Hoàng Oanh 3. Phương pháp nghiên cứu - Nghiên cứu tổng hợp tài liệu, phân tích, tổng hợp kiến thức phục vụ cho mục đích nghiên cứu. - Sử dụng phần mềm Excel. 4. Đối tượng nghiên cứu - Các bước giải bài toán vận tải . - Sử dụng phần mềm VBA (Visual Basic for Application). 5. Phạm vi nghiên cứu Phần mềm lập trình trong Excel để giải từng bước bài toán vận tải . 6. Cấu trúc của khoá luận Ngoài mục lục, phần mở đầu, phần kết luận và tài liệu tham khảo, khoá luận gồm 3 chương: Chương 1: Kiến thức chuẩn bị. Chương 2: Giới thiệu, tìm hiểu về VBA. Chương 3: Giải từng bước bài toán vận tải bằng Excel. 2 Chương 1 Kiến thức chuẩn bị 1.1 Thiết lập bài toán vận tải Bài toán vận tải là một trong những mô hình có nhiều ứng dụng trong thực tế. Trước hết ta xét bài toán vận tải cân bằng thu- phát. Bài toán được phát biểu như sau: Có m điểm A1, A2, A3, ..., Am cung cấp một lợi mặt hàng nào đó có khối lượng tương ứng a1 , a2 , a3, ..., am(ai ≥ 0, i = 1, m) và n điểm B1, B2, B3, ..., Bn tiêu thụ loại hàng đó với khối lượng tương ứng b1, b2, b3, . . . , bn (bj ≥ 0, j = 1, n). Ta gọi Ai (i = 1, m) là điểm phát thứ i, Bj (j=1, n) là điểm thu thứ j. Giả thiết rằng tổng lượng hàng cần phát đi m n X X ở các điểm phát bằng tổng thu về ở các điểm thu ( ai = bj .Điều kiện này gọi là cân bằng thu phát. i=1 j=1 Giả sử chi phí vận chuyển một đơn vị(chẳng hạn: tấn) hàng từ Ai đến Bj là cij đơn vị tiền (chẳng hạn: đồng). Ma trận C=(cij )m×n gọi là ma trận cước phí. Hãy lập kế hoạch vận chuyển từ mỗi điểm phát tới mỗi điểm thu bao nhiêu đơn vị sao cho: 3 Khóa luận tốt nghiệp Đại học Nguyễn Thị Hoàng Oanh + Các điểm phát đều hết hàng. + Các điểm thu đều nhận đủ hàng. + Tổng cước phí vận chuyển là nhỏ nhất. Ta sẽ xây dựng mô hình toán học cho bài toán trên. Gọi xij là số đơn vị hàng chuyển từ Ai đến Bj , tất nhiên xij ≥ 0(i = 1, m, j = 1, n). Tổng lượng hàng phát đi từ Ai đến mọi Bj bằng ai , n X tức là xij = ai (i = 1, m), tổng lượng hàng thu về Bj từ mọi j=1 Ai(i = 1, m) bằng bj , tức là m X xij = bj (j = 1, n). i=1 Tổng cước phí phải trả là m X n X cij xij , tổng này càng nhỏ càng tốt. i=1 j=1 Mô hình toán học của bài toán có dạng  n X    xij = ai (i = 1, m)       j=1 m X xij = bi (j = 1, n)     i=1     xij ≥ 0(i = 1, m, j = 1, n) (1.1) Ma trận X = (xij )m×n thỏa mãn hệ trên gọi là một phương án của bài tóan vận tải và nếu nó làm cho tổng cước phí phải trả là nhỏ nhất thì gọi là một phương án tối ưu của bài toán vận tải. Rõ ràng bài toán vận tải là bài toán quy hoạch tuyến tính dạng chính tắc, vì thế có thể giải nó bằng các thuật toán của quy hoạch tuyến tính. Nhưng khi đó số ẩn thường khá lớn (m × n ẩn và m + n ẩn phụ), số ràng buộc cũng nhiều(m + n ràng buộc) và việc đó thường dẫn đến những chi phí tính toán không cần thiết. Tuy nhiên lợi dụng cấu trúc đặc biệt 4 Khóa luận tốt nghiệp Đại học Nguyễn Thị Hoàng Oanh của bài toán vận tải ta có thể cụ thể hơn nữa thuật toán đơn hình và thu được thuật toán đơn giản và hiệu quả để giải nó. Ta viết lại các ma trận phương án, ma trận cước phí thành các véc tơ: X = (x11, x12, ..., x1n; x21, x22, ..., x2n; ...; xm1, xm2, ..., xmn) c = (c11, c12, ..., c1n; c21, c22, ..., c2n; ...; cm1, cm2, ..., cmn) và ký hiệu b = (a1 , a2, ..., am; b1, b2, ..., bn) A là ma trận ràng buộc gồm m+n hàng m.n cột, thành phần thứ i và thành phần thứ j bằng 1 còn các thành phần còn lại đều bằng 0. Khi đó bài toán vận tải có thể viết lại như sau:     f (X) = ct X → min    AX = b      X ≥ 0 (1.2) Dễ thấy tổng m hàng đầu và tổng n hàng cuối của ma trận A là bằng nhau(cùng bằng véc tơ e=(1,1,1,...,1))do đó rankA ≤ m + n − 1. Kí hiệu A11, A12, A1n; A21, A22, ..., A2n; ...; Am1, Am2, ..., Amn theo thứ tự từ trái sang phải là các cột của A và di , i = 1, m + n là dòng thứ i của ma trận A. Ta thấy định thức của ma trận vuông cấp m+n−1của A gồm các phần tử nằm ở vị trí giao của các cột Aii, i = 1, m − 1 và Amj ; j = 1, n của A dòng d1 , d2, ..., dm−1, dm+1, ..., dm + n bằng 1. Vậy rankA = m + n − 1. Định lý 1.1. Điều kiện cân bằng thu phát ( m X i=1 5 ai = n X j=1 bj ) là điều kiện Khóa luận tốt nghiệp Đại học Nguyễn Thị Hoàng Oanh cần và đủ để bài toán vận tải có phương án tối ưu. Chứng minh. Giả sử bài toán vận tải có phương án tối ưu X ∗ =x∗ij , khi đó n X x∗ij = ai (i = 1, m) m X x∗ij = bj (j = 1, n) j=1 i=1 . Vì vậy m X ai = i=1 Ngược lại, giả sử có m X ai = i=1 n X bj j=1 n X bj ,ta cần chứng minh bài toán vận j=1 tải có phương án tối ưu, tức là cần chứng minh tập hợp các phương án của bài toán khác rỗng và hàm mục tiêu bị chặn dưới. m n X X ab Thật vậy, đặt Q= ai = bj > 0, xét véc tơ X = ( Qi j ), (i = i=1 j=1 1, m; j = 1, n) có thành phần xij = Ta có n X ai bj j=1 Q m X ai bj i=1 Q = ai n X bj = ai (i = 1, m) m X ai = bj (j = 1, n) j=1 = bj ai b j Q i=1 Q Q và rõ ràng xij ≥ 0, (i = 1, m, j = 1, n). Vậy X là một phương án của bài toán vận tải, tức là bài toán vận tải có tập hợp các phương án 6 Khóa luận tốt nghiệp Đại học Nguyễn Thị Hoàng Oanh khác rỗng. Xét phương án bất kỳ của bài toán X = (xij ), (i = 1, m, j = 1, n) n X từ điều điện các xij ≥ 0 và xij = ai suy ra j=1 0 ≤ xij ≤ ai (i = 1, m, j = 1, n) Vì vậy   cij xij ≥ 0 nếucij ≥ 0  cij xij ≥ cij ai nếucij < 0 (1.3) suy ra cij xij ≥ min(0, cij ai ) (i=1, m, j=1, n). m X n m X n X X Do đó f (x) = cij xij ≥ min(0, cij ai )= const. i=1 j=1 i=1 j=1 Vậy hàm mục tiêu bị chặn dưới trên miền chấp nhận được, suy ra bài toán có phương án tối ưu. 1.2 Bảng vận tải Để ghi các số liệu của bài toán vận tải và để giải nó bằng các thuật toán, ta xây dựng một bẳng vận tải gồm (m+1) dòng, (n+1) cột. Trong bảng , mỗi hàng đặc trưng cho một điểm phát, mỗi cột đặc trưng cho một điểm thu: hàng trên cùng ghi các bi, (i = 1, n) cột đầu tiên ghi các ai (i = 1, m). Trừ hàng trên cùng và cột dầu tiên, phần còn lại gọi là phần chính của bảng vận tải. Ô nằm trên hàng thứ i , cột j đặc trưng cho tuyến đường từ Ai đến Bj gọi là ô (i, j). Phần chính U của bảng vận tải là U = ((i, j) : i = 1, m, j = 1, n). Ở mỗi ô (i,j) trong phần chính của bảng vận tải ta ghi cước phí vận chuyển cij 7 Khóa luận tốt nghiệp Đại học Nguyễn Thị Hoàng Oanh vào góc trên phía trái và lượng vận chuyển xij trong phương án X vào góc dưới phía phải. Định nghĩa 1.1. Những ô (i, j) ∈ U với xij > 0 gọi là những ô chọn ứng với phương án X. Những ô còn lại gọi là những ô loại. Ô chọn đặc trưng cho tuyến đường có vận tải hàng hóa qua. Định nghĩa 1.2. Một dãy các ô (i, j) ∈ U mà hai ô (và không quá 2) liên tiếp của dãy luôn nằm trên cùng một hàng hoặc cùng một cột gọi là dây chuyền. Định nghĩa 1.3. Một dây chuyền khép kín gọi là một vòng (hoặc một chu trình). Định nghĩa 1.4. Ta nói rằng L là chứa vòng nếu từ các ô của L ta có thể xây dựng ít nhất một vòng. Ngược lại, ta nói rằng L không chứa vòng. Ta có thể nhận biết được tập L có chứa vòng hay không nhờ Định lý 1.2: Định lý 1.2. Nếu trong mỗi dòng và mỗi cột của bảng vận tải hoặc không có ô nào của L hoặc có ít nhất hai ô của L thì L chứa vòng. Chứng minh. Bắt đầu từ một ô nào đó(i1, j1 ) thuộc L. Vì trên dòng i1 còn ít nhất một ô khác của L, chẳng hạn (i1, j2 ), nên ta di chuyển theo dòng i1 đến ô đó. Vì (i2, j2 ) không phải ô duy nhất của L trên cột này nên ta di chuyển theo cột j2 đến ô L(i2, j2 ) ∈ L nằm trên cột này. Tiếp tục từ ô (i2, j2 ) ta dịch chuyển theo dòng i2 đến ô khác của L thuộc cột khác của bảng vận tải ...Qúa trình này không thể kéo dài 8 Khóa luận tốt nghiệp Đại học Nguyễn Thị Hoàng Oanh vô tận vì L ⊂ U gồm hữu hạn các ô, vì vậy đến một bước nào đó ta sẽ quay lại một ô mà ta đã đi qua, tức là đã thực hiện được vòng. Khái niệm vòng liên quan chặt chẽ với tính độc lập tuyến tính của các véc tơ cột Aij của ma trận ràng buộc A trong bài toán vận tải. Định nghĩa 1.5. Tập L ⊂ U các ô của bảng vận tải được gọi là độc lập tuyến tính(phụ thuộc tuyến tính) nếu tập các véc tơ cột (Aij , (i, j) ∈ L) của ma trận A lập thành hệ véc tơ độc lập tuyến tính(phụ thuộc tuyến tính). Định lý 1.3. Tập L ⊂ U các ô của bảng vận tải là độc lập tuyến tính khi và chỉ khi nó không chứa vòng. Chứng minh. Giả sử L độc lập tuyến tính. Cần chứng minh L không chứa vòng. Giả sử ngược lại L chứa vòng và gọi V là một vòng trong nó. Điền vào các ô trong vòng V các số +θ, −θ một cách xen kẽ nhau(tức là sao cho không có hai ô cạnh nhau nào của V lại được điền cùng một số giống nhau) và điền 0 vào tất cả các ô còn lại. Khi θ = 1 thì tổng các số đã điền trong mỗi hàng và mỗi cột của bảng vận tải đều bằng 0. Điều đó có nghĩa là nếu ta đem các cột của ma trận A tương ứng với các ô được điền +θ trong V nhân với 1 và các ô của A tương ứng với các ô được điền −θ trong V nhân với -1, các cột còn lại nhân với 0 rồi cộng tất cả lại ta sẽ thu được véc tơ không. Từ đó suy ra các véc tơ cột Aij của A ứng với (i, j) ∈ L lập thành một hệ véc tơ phụ thuộc tuyến tính, trái với giả L thiết độc lập tuyến tính. Ngược lại, giả sử L không chứa vòng, cần chứng minh L độc lập tuyến 9 Khóa luận tốt nghiệp Đại học Nguyễn Thị Hoàng Oanh tính. Giả sử ngược lại L phụ thuộc tuyến tính. Khi đó, tồn tại các số λij ∈ L không đồng thời bằng 0 sao cho X λij Aij = 0 (i,j)∈L Điều này có nghĩa là nếu điền các số λij , (i, j) ∈ L trong biểu diễn trên vào các ô tương ứng của bảng vận tải , các ô khác điền số 0. Khi đó, tổng các số trong các ô được điền trong mỗi dòng và mỗi cột của bảng vận tải thu được đều bằng 0. Ký hiệu K là tập các ô của bảng vận tải với các số được điền khác 0: K = ((i, j) : λij 6= 0) Do tổng lượng được điền trong mỗi dòng và mỗi cột của bảng vận tải đều bằng 0 nên mỗi dòng hoặc mỗi cột của nó hoặc không chứa ô nào của K hoặc phải chứa ít nhất hai ô của K. Theo Định lý 1.2, khi đó K phải là vòng. Vì K ⊂ L nên suy ra L chứa vòng, trái với giả thiết. Vậy L độc lập tuyến tính. Định lý được chứng minh. Ký hiệu G(X) là tập các ô chọn trong bảng vận tải tương ứng với phương án X: G(X) = (i, j) : xij > 0 Hệ quả 1.1. Phương án X = (xij ) của bài toán vận tải là phương án cơ sở chấp nhận được khi và chỉ khi tập các ô chọn G(X) tương ứng với nó không chứa vòng. Chứng minh. Ta đã biết rằng phương án X = (xij )của bài toán là phương án cơ sở chấp nhận được khi và chỉ khi hệ các véc tơ cột của 10 Khóa luận tốt nghiệp Đại học Nguyễn Thị Hoàng Oanh ma trận ràng buộc A ứng với các thành phần khác rỗng của nó lập thành hệ độc lập tuyến tính. Theo Định lý 1.2, điều đó tương đương với G(x) không chứa vòng. Do có hệ quả trên mà người ta còn hay gọi phương án cơ sở chấp nhận được của bài toán vận tải là phương án không chứa vòng. Vì rankA = m + n − 1 nên phương án cơ sở chấp nhận được là phương án không suy biến nếu số ô chọn là m + n − 1. Trong trường hợp suy biến, ta có thể bổ sung một số ô loại sao cho phương án cơ sở chấp nhận đượccó m + n − 1 ô chọn. Các ô loại được bổ sung này được gọi là các "ô chọn 0". Ta thấy điều này tương ứng với các định lý nêu trong bài toán quy hoạch tuyến tính: Phương án cơ sở chấp nhận được là không suy biến nếu số véc tơ cột của A tương ứng với các thành phần dương của nó ( Khi đó các véc tơ cột này lập thành hệ độc lập tuyến tính) đúng bằng rankA. Do đó ứng với mỗi phương án cơ sở chấp nhận được có duy nhất một cơ sở. Trường hợp số véc tơ đó nhỏ hơn rankA thì phương án cơ sở chấp nhận được đó gọi là suy biến và ta có thể bổ xung một số cột của A vào hệ véc tơ đó để được một hệ đúng bằng rankA các véc tơ cột độc lập tuyến tính.(Tương ứng với mỗi phương án cơ sở chấp nhận được có nhiều hơn một cơ sở). Hệ quả 1.2. Giả sử có bảng vận tải m hàng, n cột và L là một tập gồm m + n − 1 ô của bản không chứa vòng. Giả sử ô (i, j) của bảng không thuộc L. Nếu ta bổ xung ô (i, j) vào L để được L1 thì L1 chứa một vòng duy nhất V . Cuối cùng, nếu loại khỏi L1 một ô tùy ý của vòng V thì được L2 thì L2 lại gồm m + n − 1 ô của bảng không chứa vòng. 11
- Xem thêm -

Tài liệu liên quan