Tài liệu Thuật toán gomory giải bài toán qui hoạch nguyên tuyến tính và ứng dụng trong pháo binh

BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 TÔ THỊ HƯƠNG LAN THUẬT TOÁN GOMORY GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH VÀ ỨNG DỤNG TRONG PHÁO BINH LUẬN VĂN THẠC SĨ TOÁN HỌC HÀ NỘI - 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC SƯ PHẠM HÀ NỘI 2 TÔ THỊ HƯƠNG LAN THUẬT TOÁN GOMORY GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH VÀ ỨNG DỤNG TRONG PHÁO BINH Chuyên ngành: Toán ứng dụng Mã số: 60 46 01 12 Người hướng dẫn khoa học PGS. TS. NGUYỄN NĂNG TÂM HÀ NỘI - 2017 LỜI CẢM ƠN Lời đầu tiên của luận văn tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất tới PGS.TS Nguyễn Năng Tâm, thầy đã định hướng chọn đề tài và tận tình hướng dẫn, giúp đỡ tôi trong suốt quá trình làm và hoàn thiện luận văn này. Tôi cũng xin bày tỏ lòng biết ơn chân thành tới Phòng sau đại học, các thầy cô giáo khoa Toán Trường Đại học sư phạm Hà Nội 2, các thầy giáo giảng dạy chuyên ngành Toán ứng dụng đã giúp đỡ tôi trong suốt quá trình học tập tại trường. Nhân dịp này tôi cũng xin gửi lời cảm ơn đến các đồng nghiệp ở Bộ môn Toán Tin Khoa Khoa học cơ bản Trường sĩ quan Pháo binh, nơi tôi đang công tác; gia đình và bạn bè đã luôn tạo điều kiện giúp đỡ và động viên tôi trong suốt quá trình học tập và hoàn thành luận văn này. Hà Nội, tháng 6 năm 2017 Tác giả Tô Thị Hương Lan LỜI CAM ĐOAN Tôi xin cam đoan, dưới sự chỉ bảo và hướng dẫn của PGS.TS Nguyễn Năng Tâm, luận văn chuyên ngành Toán ứng dụng với đề tài: “Thuật toán Gomory giải bài toán qui hoạch nguyên tuyến tính và ứng dụng trong Pháo binh” được hoàn thành bởi sự nhận thức và tìm hiểu của bản thân tác giả. Trong quá trình nghiên cứu và thực hiện luận văn, tác giả đã kế thừa những kết quả của các nhà khoa học với sự trân trọng và biết ơn! Hà Nội, tháng 6 năm 2017 Tác giả Tô Thị Hương Lan Mục lục LỜI CẢM ƠN 1 LỜI CAM ĐOAN 2 MỞ ĐẦU 3 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT 6 Chương 1. MỘT SỐ KIẾN THỨC CHUẨN BỊ 7 1.1 7 1.1.1 Bài toán tối ưu [3] . . . . . . . . . . . . . . . . . . . . . 7 1.1.2 Bài toán qui hoạch nguyên tuyến tính . . . . . . . . . . . 9 1.1.3 Điều kiện tối ưu tổng quát . . . . . . . . . . . . . . . . . 11 Phương pháp đơn hình [5] . . . . . . . . . . . . . . . . . . . . . 12 1.2.1 Thuật toán đơn hình dạng bảng . . . . . . . . . . . . . . 12 1.2.2 Thuật toán đơn hình dạng tọa độ . . . . . . . . . . . . . 14 1.2.3 1.2 Một số vấn đề cơ bản về bài toán tối ưu tuyến tính . . . . . . . Phương pháp đơn hình đối ngẫu . . . . . . . . . . . . . . 17 Chương 2. THUẬT TOÁN GOMORY GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH 23 2.1 Cơ sở lí thuyết về thuật toán lát cắt . . . . . . . . . . . . . . . . 23 2.1.1 Cơ sở lý thuyết . . . . . . . . . . . . . . . . . . . . . . . 23 2.1.2 Khái niệm lát cắt . . . . . . . . . . . . . . . . . . . . . . 27 2.1.3 Tư tưởng phương pháp cắt . . . . . . . . . . . . . . . . . 30 2.2 31 2.2.1 Thuật toán Gomory thứ nhất . . . . . . . . . . . . . . . 31 2.2.2 Thuật toán Gomory thứ hai . . . . . . . . . . . . . . . . 35 2.2.3 Thuật toán Gomory thứ ba . . . . . . . . . . . . . . . . 40 Định lí về sự tồn tại nghiệm của bài toán . . . . . . . . . . . . . 47 2.3.1 Điều kiện để sử dụng thuật toán Gomory . . . . . . . . . 47 2.3.2 Tính hữu hạn của thuật toán Gomory . . . . . . . . . . 48 2.3.3 2.3 Thuật toán Gomory . . . . . . . . . . . . . . . . . . . . . . . . Cơ sở xây dựng lát cắt đúng nguyên . . . . . . . . . . . 51 Chương 3. ỨNG DỤNG TRONG PHÁO BINH 3.1 52 Khái niệm . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.1.2 Khái niệm mục tiêu (M) . . . . . . . . . . . . . . . . . . 53 Bài toán . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.1 Bài toán thực tế: . . . . . . . . . . . . . . . . . . . . . . 56 3.2.2 Thiết lập mô hình toán . . . . . . . . . . . . . . . . . . . 57 Phương pháp giải bài toán đặt ra . . . . . . . . . . . . . . . . . 57 3.3.1 Sử dụng thuật toán . . . . . . . . . . . . . . . . . . . . . 57 3.3.2 3.3 52 3.1.1 3.2 Khái niệm chỉ tiêu hiệu quả bắn (CTHQB) . . . . . . . . . . . . Văn bản chương trình [7] . . . . . . . . . . . . . . . . . . 63 KẾT LUẬN 70 TÀI LIỆU THAM KHẢO 71 3 MỞ ĐẦU 1. Lí do chọn đề tài Bài toán tối ưu tuyến tính là một bài toán quan trọng của lý thuyết tối ưu. Đây là mô hình toán học của nhiều bài toán phổ biến trong thực tế, có hình thức toán học đơn giản và dễ giải. Mặt khác, về lý thuyết, ta có thể xấp xỉ với độ chính xác cao các bài toán tối ưu phi tuyến bởi dãy các bài toán tối ưu tuyến tính. Trong lí thuyết tối ưu ta gặp một lớp bài toán mà đối tượng của nó không thể chia cắt nhỏ tùy ý, trong lớp bài toán này tất cả (hoặc một bộ phận) các biến chỉ nhận các giá trị nguyên, đó là bài toán qui hoạch nguyên. Bài toán quy hoạch nguyên có nhiều ứng dụng trong thực tế và trong quân sự, chẳng hạn bài toán dự tính số đạn trúng mục tiêu; số vọng gác ít nhất để có thể đảm bảo an ninh một khu vực; bài toán tìm số chiến sĩ ít nhất để phân công công việc, hay bài toán chiếc ba lô,.. Vì vậy, vấn đề đặt ra là cần nghiên cứu một lớp các bài toán quy hoạch nguyên với phương pháp giải phù hợp để giải quyết các bài toán thực tế và bài toán chuyên ngành. Đối với bài toán qui hoạch nguyên tuyến tính, các thuật toán giải bài toán qui hoạch tuyến tính tổng quát cơ bản hầu hết không thể sử dụng được nữa do yêu cầu về tính nguyên của các biến số. Năm 1958, Gomory (nhà toán học người Mĩ) đã công bố thuật toán cắt nổi tiếng để giải bài toán qui hoạch nguyên tuyến tính, mở đầu cho sự ra đời và phát triển của lí thuyết bài toán qui hoạch nguyên. Lí thuyết tối ưu cũng được ứng dụng nhiều trong trong chuyên ngành chỉ huy của Pháo binh, có nhiều bài toán tối ưu được đưa về bài toán qui hoạch 4 nguyên tuyến tính, chẳng hạn: bài toán dự tính số đạn trúng mục tiêu; bài toán vận tải trong quân sự; bài toán đuổi bắt mục tiêu; ... thuật toán Gomory tỏ ra là một công cụ hữu hiệu trong việc xử lí các bài toán này. Vì vậy, tôi chọn đề tài nghiên cứu: “Thuật toán Gomory giải bài toán qui hoạch nguyên tuyến tính và ứng dụng trong Pháo binh”. 2. Mục đích nghiên cứu Sử dụng thuật toán Gomory giải bài toán qui hoạch nguyên để tìm ra phương án tối ưu cho bài toán. Nghiên cứu lớp bài toán tối ưu diệt mục tiêu pháo binh có yếu tố ngẫu nhiên. 3. Nhiệm vụ nghiên cứu Trình bày một số kiến thức cơ bản về bài toán quy hoạch tuyến tính, bài toán quy hoạch nguyên; Lí thuyết tối ưu; phương pháp cắt; Cơ sở lý thuyết của thuật toán Gomory để giải bài toán quy hoạch nguyên. Nêu bài toán ứng dụng, từ đó mô hình hoá dạng toán học. 4. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu: thuật toán Gomory để giải bài toán quy hoạch nguyên và ứng dụng trong pháo binh. Phạm vi nghiên cứu: Cơ sở lý thuyết của thuật toán lát cắt Gomory để giải bài toán quy hoạch nguyên. 5. Phương pháp nghiên cứu Tìm hiểu các tài liệu liên quan đến bài toán qui hoạch nguyên, bài toán tối ưu tuyến tính, thuật toán Gomory. 5 Phương pháp nghiên cứu lí thuyết, chủ yếu là các phương pháp suy luận toán học. Tổng hợp kiến thức và trình bày một cách hệ thống. 6. Đóng góp của đề tài Xem xét bài toán qui hoạch nguyên tuyến tính trong Pháo binh cả ở khía cạnh thực tế và toán học. Hình thành hướng tiếp cận giải bài toán đã đặt ra. 6 DANH MỤC CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT 7 Chương 1 MỘT SỐ KIẾN THỨC CHUẨN BỊ 1.1. 1.1.1. Một số vấn đề cơ bản về bài toán tối ưu tuyến tính Bài toán tối ưu [3] Trong thực tế và lý thuyết, nhiều bài toán được mô tả dưới dạng: max f (x) với x ∈ C (P ) trong đó f : Rn → R là một hàm cho trước, C ⊂ Rn là một tập con cho trước, Rn là không gian Euclid n-chiều. Ta còn viết bài toán (P ) như sau: max{f (x) : x ∈ C}. Định nghĩa 1.1. Bài toán (P ) được gọi một bài toán tối ưu hay một bài toán quy hoạch toán học. Hàm f gọi là hàm mục tiêu, C là tập ràng buộc (hay miền chấp nhận được của (P )). Các phần tử của C được gọi là các vectơ chấp nhận được của (P ) hoặc các phương án. Nếu C = Rn thì ta nói (P ) là một bài toán không có ràng buộc, ngược lại, (P ) là bài toán có ràng buộc. Định nghĩa 1.2. Điểm x∗ ∈ C mà f (x∗ ) ≥ f (x) với mọi x ∈ C được gọi là nghiệm, hoặc nghiệm tối ưu, hoặc nghiệm tối ưu toàn cục, hoặc cực đại toàn cục của bài toán (P ), ta còn gọi nghiệm tối ưu là phương án tối ưu. Tập các nghiệm tối ưu của (P ) kí hiệu là Sol(P ), tập các nghiệm tối ưu địa phương kí hiệu là loc(P ). 8 Hình 1.1 Cực tiểu địa phương: M2 , M4 . Cực tiểu toàn cục: M2 . Cực đại địa phương: M3 . Cực đại toàn cục: M3 . Hai bài toán tối ưu gọi là tương đương nếu tập nghiệm của chúng trùng nhau. Định nghĩa 1.3. Giá trị tối ưu ν(P ) của (P ) được xác định bởi ν(P ) = sup{f (x) : x ∈ C}. Nếu C = ∅ thì qui ước ν(P ) = +∞. Dễ thấy, Sol(P ) ⊂ loc(P ), và Sol(P ) = {x ∈ C : f (x) = ν(P )}. Lưu ý: Thay cho bài toán (P ) ở trên, ta có thể gặp bài toán tìm giá trị nhỏ nhất sau: min f (x) với x ∈ C. (P1 ) Một điểm x∗ được gọi là một nghiệm tối ưu toàn cục (cực tiểu toàn cục) của (P1 ) nếu f (x) ≥ f (x∗ ) với mọi x ∈ C. Ta nói x∗ là một nghiệm tối ưu địa phương (cực tiểu địa phương) của (P1 ) nếu tồn tại một lân cận U của x∗ sao cho f (x) ≥ f (x∗ ) với mọi x ∈ C ∩ U. Rõ ràng x∗ là một nghiệm tối ưu toàn cục (một nghiệm tối ưu địa phương) của (P1 ) khi và chỉ khi x∗ là một nghiệm tối ưu toàn cục (một nghiệm tối ưu địa phương) của bài toán tìm giá trị lớn nhất sau: max(−f (x)) với x ∈ C.. Do 9 vậy bất kỳ bài toán tìm giá trị nhỏ nhất nào dạng (P1 ) đều có thể đưa về bài toán tìm giá trị lớn nhất dạng (P ) Hiển nhiên rằng, nghiệm tối ưu toàn cục của bài toán (P ) (hay (P1 )) đều là nghiệm tối ưu địa phương của (P ) (hay (P1 )), điều ngược lại không phải lúc nào cũng đúng. Tuy nhiên, nếu C là một tập lồi và f là một hàm lồi trên C thì mọi nghiệm tối ưu địa phương của (P ) đều là nghiệm tối ưu toàn cục của (P ). Khẳng định sau đây chứng minh điều đó. Định lý 1.1. Cho C ⊂ Rn là tập lồi, f : C → R là một hàm lồi. Khi đó, nếu x∗ là một nghiệm tối ưu của bài toán (P ): max{f (x) : x ∈ C}, thì nó cũng là một nghiệm tối ưu toàn cục của bài toán đó. Chứng minh. Giả sử x∗ là nghiệm tối ưu địa phương của (P ). Khi đó x∗ ∈ C và tồn tại lân cận mở V trong Rn của x∗ sao cho: f (x∗ ) ≥ f (x), ∀x ∈ V ∩ C. Lấy x ∈ C tùy ý. Vì C lồi nên với mọi t ∈ (0, 1) đủ nhỏ, ta có xt = tx + (1 − t)x∗ ∈ V ∩ C. Do f lồi trên C nên f (x∗ ) ≥ f (xt ) ≥ tf (x) + (1 − t)f (x∗ ) suy ra f (x∗ ) ≥ f (x). Vì x ∈ C tùy ý, ta suy ra x∗ là nghiệm tối ưu toàn cục của (P ). 1.1.2. Bài toán qui hoạch nguyên tuyến tính Trong các bài toán quy hoạch tuyến tính, các biến số có thể nhận những giá trị thực không âm. Tuy nhiên, trong thực tiễn thường gặp các bài toán mà các biến số chỉ có thể nhận một số hữu hạn hay đếm được giá trị, thường là các giá trị nguyên. Chẳng hạn sẽ là vô nghĩa khi đưa ra câu trả lời: cần sản xuất nửa cái bàn hay cần sử dụng 3,5 người để hoàn thành công việc, hoặc có 1,3 viên đạn bắn trúng mục tiêu. . . Vì thế ta sẽ đề cập đến nội dung và phương 10 pháp giải các bài toán tối ưu trên lưới các điểm nguyên hay trên các tập rời rạc, gọi tắt là bài toán quy hoạch rời rạc hay bài toán quy hoạch nguyên. Bài toán qui hoạch nguyên tuyến tính: n cj xj → min (max) f (x) = (L, C) j=1 aij xj ≤ bi , i = 1, . . . , n1 (1.1) aij xj = bi ; i = n1 + 1, . . . , m (1.2) xj ≥ 0, j = 1, . . . , n (1.3) xj ∈ Z, j = 1, . . . , k (k ≤ n) (1.4) trong đó cj , aij là các số nguyên, bi nguyên không âm. Nếu k = n thì bài toán (L, C) với điều kiện (1.1) - (1.4) gọi là bài toán quy hoạch tuyến tính nguyên hoàn toàn. Nếu k < n thì bài toán gọi là bài toán quy hoạch nguyên bộ phận. Điều kiện (1.4) đôi khi được viết dưới dạng: xj nguyên, j ∈ J ⊂ {1, . . . , n}. Ký hiệu: Bài toán với điều kiện (1.1) - (1.3) ký hiệu (L, C) là bài toán qui hoạch tuyến tính, miền xác định L, phương án tối ưu là X(L, C). Bài toán với điều kiện (1.1) - (1.4) ký hiệu (LN , C) là bài toán qui hoạch nguyên tuyến tính, LN - miền xác định của bài toán qui hoạch nguyên tuyến tính, X(LN , C) là phương án tối ưu. (L, C) là bài toán tối ưu từ vựng với phương án tối ưu mở rộng X = n ( cj xj , x1 , x2 , . . . , xn ). j=1 Véc tơ X thỏa mãn (1.3) - (1.4) được gọi là phương án (hay lời giải chấp nhận được). Phương án X ∗ làm cực tiểu (cực đại) (L, C) gọi là phương án tối ưu. 11 Nếu X ∗ = (x1 , . . . , xn ) là phương án (hay phương án tối ưu) và x0 = n thì vectơ X = ( cj xj cj xj , x1 , x2 , . . . , xn ) gọi là phương án mở rộng (phương án j=1 tối ưu mở rộng). Bài toán quy hoạch tuyến tính nguyên gọi là giải được nếu tồn tại phương án tối ưu X ∗ . Một đa diện L mà tất cả các đỉnh của nó đều là nguyên (mọi thành phần là nguyên) gọi là đa diện nguyên. 1.1.3. Điều kiện tối ưu tổng quát Trong phần này chúng ta sẽ đề cập đến bài toán tối ưu dạng: max{f (x) : x ∈ C} (1.5) trong đó C ⊂ Rn là một tập đóng. Định lý 1.2. [3, tr. 63]. Bài toán (1.5) có nghiệm tối ưu khi và chỉ khi tồn tại x ∈ C sao cho tập M (f0 ) = {α ∈ R : α ≤ f (x)} đóng, khác rỗng và bị chặn trên. Chứng minh. Giả sử (1.5) có nghiệm tối ưu x∗ ∈ C. Khi đó, rõ ràng: M (f ) = {α ∈ R : α ≤ f (x∗ )}. Vậy M (f ) là đóng, khác rỗng, bị chặn trên. Giả sử tập M (f ) đóng, khác rỗng và bị chặn trên. Khi đó, tồn tại α0 = sup M (f ) < +∞ và α0 ∈ M (f ). Vì α ∈ M (f ), theo định nghĩa của M (f ), tồn tại x∗ ∈ C sao cho α0 ≤ f (x∗ ). Mặt khác, f0 (x) ∈ M (f ) với mọi x ∈ C, suy ra α0 thuộc f (x∗ ). Vậy f (x∗ ) = sup M (f0 ) < +∞, suy ra f (x∗ ) ≥ f (x) với mọi x ∈ C. Vậy x∗ là nghiệm tối ưu của bài toán (1.5). 12 1.2. Phương pháp đơn hình [5] Đây là một phương pháp đơn giản và hữu hiệu để giải bài toán tối ưu tuyến tính được Dantzig, nhà toán học Mỹ, tìm ra vào năm 1947. Như đã biết, mọi bài toán tối ưu tuyến tính đều chuyển được về dạng chính tắc. Do đó, trong mục này chỉ xét bài toán dạng chính tắc. 1.2.1. Thuật toán đơn hình dạng bảng Thuật toán đơn hình để giải bài toán qui hoạch tuyến tính chính tắc khi biết một phương án cực biên x0 . Xét bài toán tối ưu tuyến tính dạng chính tắc không suy biến n cj xj → min f (x) = j=1 n aij xj = bi ; i = 1, . . . , n j=1 xj ≥ 0; j = 1, 2, . . . , n • Thuật toán: Bước khởi tạo. Tìm một phương án cực biên x0 và cơ sở J(x0 ) tương ứng. Với mỗi k ∈ J(x0 ), các định các hệ số khai triển xjk của Ak trong J(x0 ) bằng cách / giải hệ: xjk Aj = Ak , k = 1, ..., n j∈J(x0 ) và các ước lượng theo công thức ∆k = sumj∈J(x0 ) xjk cj − ck Tính f (x0 ) = j∈J cj x0 j Chú ý: ∆j = 0, ∀j ∈ J Bước 1. Kiểm tra dấu hiệu tối ưu của phương án cực biên x0 : Nếu ∆k ≤ 0, ∀k ∈ J(x0 ) thì x0 là phương án tối ưu. Thuật toán dừng. 13 Nếu có k ∈ J(x0 ), ∆k > 0 thì x0 chưa phải phương án tối ưu. Chuyển sang / Bước 2. Bước 2. Kiểm tra dấu hiệu bài toán không có nghiệm tối ưu: Với mỗi k ∈ J(x0 ) mà ∆k > 0, kiểm tra hệ số triển khai xjk : nếu có ∆k > 0 / mà xjk ≤ 0, ∀j ∈ J(x0 ), thì kết luận bài toán không có nghiệm tối ưu. Thuật toán dừng. Nếu với mọi k ∈ J(x0 ) mà ∆k > 0 đều có ít nhất một j ∈ J(x0 ) mà xjk ≥ 0 / thì chuyển sang Bước 3. Bước 3. Chọn ẩn đưa vào cơ sở mới và xác định ẩn loại ra: Ẩn xs được chọn đưa vào làm ẩn cơ sở (cột As được chọn đưa vào làm cột của cơ sở mới) theo tiêu chuẩn sau: ∆s = max{k ∈ J(x0 ), ∆k > 0}. / Ẩn xs được chọn đưa ra khỏi cơ sở (cột Ar được chọn đưa ra khỏi cơ sở cũ) theo quy tắc: λ = min x0 j xjs 0 : j ∈ J(x ), xjs > 0 = x0 j xrs . Phần tử xrs được gọi là phần tử trục (phần tử xoay) của phép biến đổi cơ sở. Chuyển sang Bước 4. Bước 4. Lập phương án cực biên mới: Xây dựng phương án cực biên mới, với cơ sở mới J(x1 ) = J(x0 )\{r} ∪ {s}. Tính f (x1 ), ∆1 và x1 theo cơ sở mới J(x1 ). k k Quay về Bước 1. • Bảng đơn hình Để thuận tiện cho việc tính toán người ta thường sắp xếp các số liệu trong mỗi bước lặp của thủ tục đơn hình vào một bảng, gọi là bảng đơn hình. Giả sử tại một bước lặp nào đó ta có x = (x1 , . . . , xn ) là phương án cực biên ứng với cơ sở J(x) = {j1 , . . . , jm } với sắp xếp thỏa mãn E = (Aj1 , . . . , Ajm ) là ma trận đơn vị: Cột ứng với chỉ số jk là véc tơ đơn vị với số 1 nằm trên dòng với chỉ số jk . 14 Bảng đơn hình của bài toán chính tắc dạng: Hệ số Phương án c1 c2 ... cjk ... cn J CJ xJ A1 A2 ... Ajk ... An cj1 Aj1 x0 j1 xj 1 1 xj 1 2 ... 0 ... ... ... ... ... ... ... ... ... ... ... ... ... cjk Ajk x0 jk xj k 1 xj k 2 ... ... ... ... cjm Ajm x0 jm f (x0 ) 1.2.2. Cơ sở λ xj 1 n λj 1 ... ... ... 0 ... ... ... ... 1 ... xj k n λj k ... ... 0 ... ... ... xj m 1 xjm 2 ... ... ... xjm n λjm ∆1 ∆2 ... 0 ... ∆n Thuật toán đơn hình dạng tọa độ Xét bài toán tối ưu tuyến tính dạng chính tắc không suy biến (L, C) n cj xj → max f (x) = j=1 n aij xj = bi , i = 1, . . . , m j=1 xj ≥ 0, j = 1, 2, . . . , n. • Bảng l-chuẩn Bảng đơn hình Tk gọi là chuẩn từ vựng (hay l-chuẩn) nếu (x0j ) ≥ 0, ∀j ∈ Nk . Bảng đơn hình Tk gọi là chấp nhận được nếu mọi (xi0 ) ≥ 0, ∀i = 1, m. Phương án xk là phương án tối ưu nếu bảng đơn hình Tk là l-chuẩn và chấp nhận được. • Thuật toán: Bước lặp xuất phát: Xây dựng phương án tựa xuất phát x0 , tương ứng có bảng đơn hình Tr và các tập Br , Nr . Kiểm tra bảng Tr có chuẩn hay không (tức là x0j ≥ 0, ∀j ∈ Nk ) thì x0 là phương án tối ưu. Thuật toán dừng. Nếu tồn tại x0j < 0, thì x0 chưa là phương án tối ưu. 15 Bước lặp tổng quát: r ≥ 0 Kiểm tra nếu x0 không là tối ưu thì xác định đưa xl vào cơ sở theo công thức x0l = min{x0j | j ∈ Nr }. Đưa xk ra khỏi cơ sở theo tiêu chuẩn xk0 = min xkl xi0 | i = 1, 2, . . . , n; xil > 0 . xil Phần tử xkl gọi là phần tử xoay. ∗ Xây dựng bảng tọa độ Tr mới theo công thức: x∗ = − ik xil xkl x∗ = xij − ij xkj xil . xkl Nếu không có xil > 0 (i = 1, 2, . . . , n) bài toán không giải được. Nhận xét 1.1. Nếu bảng đơn hình xuất phát là l-chuẩn thì chỉ có hai khả năng có thể xảy ra: • (L, C) không có phương án. • (L, C) có phương án tối ưu từ vựng. Ví dụ 1.1. Giải bài toán qui hoạch tuyến tính sau: max(x0 ) = −x1 − 2x2  2x1 + 3x2 ≥ 7   x +x ≤3 2  1  x ≥ 0, j = 1, 2 j Giải. Ta giải bài toán bằng phương pháp đơn hình. • Dạng bảng đơn hình Thêm các biến phụ ta có bài toán trở thành min(f (x)) = x1 + 2x2 + 0x3 + 0x4 + M x5 (x5 là biến giả) 16  2x1 + 3x2 − x3 = 7   x +x +x =3 2 4  1  x ≥ 0, j = 1, 2, 3, 4 j Bảng số Ci Ai P/án 1 2 0 0 A1 A2 A3 λ A4 M 3 −1 0 7/3 0 A4 3 1 1 0 1 3 0 −1 −2 0 0 7 2 3 −1 0 2 A2 7/3 2/3 1 −1/3 0 7/2 0 A4 2/3 1/3 0 1/3 1 2 f (x) 14/3 1/3 0 −2/3 0 M 0 0 0 0 0 2 A2 1 0 1 −1 −2 - 1 A1 2 1 0 1 3 - f (x) III 2 M II 7 f(x) I A5 4 0 0 −1 −1 Phương án tối ưu của bài toán là (2, 1, 0, 0, 0). Trị hàm mục tiêu max(x0 ) = −4. • Dạng tọa độ của phương pháp đơn hình Thêm các biến bù, bài toán được viết lại thành max(x0 ) = −x1 − x2  x3 = −7 + 2x1 + 3x2   x =3−x −x 1 2  4  x ≥ 0 (j = 1, . . . , 4) j