Tài liệu Một phương pháp xấp xỉ trong giải bài toán quy hoạch phân tuyến tính

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC ---------------------------- BÙI QUỐC ĐỘ MỘT PHƢƠNG PHÁP XẤP XỈ TRONG GIẢI BÀI TOÁN QUY HOẠCH PHÂN TUYẾN TÍNH Chuyên ngành : TOÁN ỨNG DỤNG Mã số : 60.46.01.12 LUẬN VĂN THẠC SĨ TOÁN HỌC Ngƣời hƣớng dẫn khoa học: TS . NGUYỄN ANH TUẤN Thái Nguyên – 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Mục lục Nội dung TT Trang 1 Mở đầu 2 2 Chương 1: Bài toán qui hoạch tuyến tính và bài toán qui hoạch phân tuyến tính 4 3 1.1Bài toán tối ưu tổng quát 4 4 1.2 Bài toán quy hoạch tuyến tính dạng chuẩn 4 5 1.3 Bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính 5 6 1.4 Một số mô hình bài toán thực tế đưa về bài toán quy hoạch tuyến tính và phân tuyến tính 6 7 1.5 Một số khái niệm và tính chất của hàm gần lồi-gần lõm 8 8 Chương 2:Thuật toán nón xoay giải bài toán quy hoạch tuyến tính và thuật toán kiểu đơn hình giải bài toán quy hoạch phân tuyến tính 17 9 2.1. Thuật toán nón xoay giải bài toán quy hoạch tuyến tính dạng chuẩn 17 10 2.2. Thuật toán kiểu đơn hình giải bài toán quy hoạch phân tuyến tính 20 11 Chương 3:Phương pháp nón xoay xấp xỉ trong giải bài toán quy hoạch phân tuyến tính 28 12 3.0. Bổ trợ 28 13 3.1. Bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính 30 14 3.2.Khái niệm về nón đơn hình tuyến tính, cạnh và phương của cạnh 32 15 3.3. Bảng lặp nón xoay giải bài toán quy hoạch phân tuyến tính bởi thuật toán PTT 47 16 3.4. Nhận xét về độ phức tạp tính toán của thuật toán nón xoay PTT và kết luận 56 17 Tài liệu tham khảo 58 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Mở đầu Bài toán quy hoạch phân tuyến tính là một bài toán có ý nghĩa trong kinh tế. Rất nhiều bài toán thực tế trong công nghệ hóa chất, trong lý thuyết trò chơi, mạng vận tải, bài toán cắt nguyên vật liệu, định giá thành sản phẩm, …đều đưa về bài toán quy hoạch phân tuyến tính. Như chúng ta đã biết, hàm mục tiêu của bài toán quy hoạch phân tuyến tính là một hàm đơn điệu theo đoạn thẳng, nửa đường thẳng và cả đường thẳng nằm trên miền xác định của nó. Vì vậy ta có thể xây dựng thuật toán kiểu đơn hình giải bài toán quy hoạch phân tuyến tính. Trong cuốn sách “Các phương pháp tối ưu hóa”([6]) đã đưa ra một thuật toán kiểu đơn hình giải bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ phương trình tuyến tính. Luận văn này xây dựng một thuật toán xấp xỉ trong giải bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính. Thuật toán này được xây dựng dựa trên khái niệm nón xoay trình bày trong sách “quy hoạch tuyến tính với phương pháp nón xoay” ([1]), nó gần giống với thuật toán nón xoay tuyến tính (thuộc lược đồ xấp xỉ ngoài) giải bài toán quy hoạch tuyến tính dạng chuẩn đã đề nghị, chỉ khác là các đỉnh của nón xoay dịch chuyển trong thuật toán này nằm trong miền ràng buộc (thuộc lược đồ xấp xỉ trong). Cơ sở lý luận để xây dựng thuật toán là dựa trên tính gần lồi-gần lõm của hàm mục tiêu bài toán quy hoạch phân tuyến tính. Vì vậy trong hai chương đầu của luận văn sẽ đề cập đến các khái niệm cơ bản và các tính chất của hàm gần lồi-gần lõm và thuật toán nón xoay tuyến tính giải bài toán quy hoạch tuyến tính dạng chuẩn. Nội dung chính của luận văn là đề nghị thuật toán giải bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính. Luận văn gồm 3 chương: Chương 1 trình bày bài toán quy hoạch tổng quát, các khái niệm cơ bản về tập lồi, một số mô hình bài toán thực tế đưa về bài toán quy hoạch tuyến tính dạng chuẩn và quy hoạch phân tuyến tính cùng với một số khái niệm và tính chất của hàm gần lồi-gần lõm mà các hàm tuyến tính và phân tuyến tính đều thuộc lớp hàm đăc biệt này. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Chương 2 trình bày thuật toán nón xoay tuyến tính[1] giải trực tiếp bài toán quy hoạch tuyến tính dạng chuẩn khi biết một nón-min của hàm mục tiêu bài toán và thuật toán kiểu đơn hình giải bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ phương trình tuyến tính[6]. Chương 3 dựa trên khái niệm nón xoay xây dựng thuật toán xấp xỉ trong giải trực tiếp bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính và các ví dụ bằng số minh hoạ cho thuật toán. Trong trường hợp đặc biệt mẫu số của hàm mục tiêu bài toán đồng nhất bằng một thì hàm mục tiêu bài toán trở thành hàm tuyến tính và thuật toán đề nghị trở thành một thuật toán giải trực tiếp bài toán quy hoạch tuyến tính dạng chuẩn tổng quát. Thuật toán nón xoay này thuộc lược đồ xấp xỉ trong giải bài toán quy hoạch phân tuyến tính khi biết một điểm chấp nhận được của miền ràng buộc là hệ bất phương trình tuyến tính. Nó được xây dựng chi tiết, các bước của thuật toán được trình bày sao cho chúng ta có thể dễ dàng lập trình chuyển sang các chương trình trên máy tính bằng các ngôn ngữ như Pascal, C, Java, ... Luận văn này hoàn thành dựa trên các cuốn sách “Quy hoạch gần lồi - gần lõm ứng dụng vào quy hoạch tuyến tính” [2] và cuốn “Quy hoạch tuyến tính với phương pháp nón xoay” [1] và trên các sách, tài liệu có trong phần tài liệu tham khảo. Tác giả Bùi Quốc Độ Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ CHƢƠNG 1 BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VÀ BÀI TOÁN QUY HOẠCH PHÂN TUYẾN TÍNH 1.1Bài toán tối ƣu tổng quát Bài toán tối ưu tổng quát được phát biểu như sau . Cực đại hoá (cực tiểu hoá) hàm : f(x) với các điều kiện gi x x X , , max ( min ) (1.1) (1.2) bi , i 1,..., m n (1.3) Bài toán (1.1 ) – (1.3) được gọi là một quy hoạch, hàm f( ) được gọi là hàm mục tiêu, các hàm gi x , i 1,..., m được gọi là các hàm ràng buộc, mỗi đẳng thức trong hệ (1.2) được gọi là một ràng buộc. Tập hợp : D x X / gi x , , bi , i 1,..., m (1.4) Được gọi là miền ràng buộc ( hay miền chấp nhận được ) . Mỗi điểm : x x1, x2 ,..., xn D được gọi là một phương án ( hay một lời giải chấp nhận được ). Một phương án x* thể là: D đạt cực đại ( hay cực tiểu ) của hàm mục tiêu, cụ f x* f x , x D ( đối với bài toán Max ) f x* f x , x D ( đối với bài toán Min ) Được gọi là phương án tối ưu ( lời giải tối ưu ). Khi đó giá trị f x* được gọi là giá trị tối ưu của bài toán . 1.2. Bài toán quy hoạch tuyến tính dạng chuẩn Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Bài toán qui hoạch tuyến tính sau đây gọi là bài toán quy hoạch tuyến tính dạng chuẩn tổng quát: n f ( x) C, x ci .xi ( L) min i 1 x PL : x R n : Ai , x bi x  n , Ai là véc tơ dòng và Ai 0, i 1,2,..., m  n , m n, Ai (ai1, ai2, ..., ain) ≠ O(0,…,0) , C(c1, c2, …, cn), bi  1 , i=1, 2, ..., m. Hạng của hệ Ai (i=1, 2, …, m) bằng n, giả thiết này rất bình thường bởi miền ràng buộc PL của bài toán quy hoạch tuyến tính bao giờ cũng có ràng buộc về dấu của biến x. Rõ ràng bài toán quy hoạch tuyến tính bất kỳ đều dễ dàng đưa về dạng trên để giải 1.3. Bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ bất phƣơng trình tuyến tính Bài toán quy hoạch sau đây gọi là bài toán quy hoạch phân tuyến tính với miền ràng buộc là hệ bất phương trình tuyến: f ( x) ( P) x P: Trong đó L1 x A0 , x L1 ( x) L2 ( x) min x  n : Ai , x b0 , L2 x C0, x bi 0, i 1,2,..., m d 0 , A0,Ai,C0, x  n , A0,Ai,C0 là các véc tơ dòng , m n,A0(a01, a02 , …, a0n), C0(c01, c02 , …, c0n), Ai (ai1, ai2, ..., ain) ≠ O(0,…,0) , bi  1 , i=1, 2, ..., m. Hạng của hệ Ai (i=1, 2, …, m) bằng n, giả thiết này rất bình thường bởi miền ràng buộc P của bài toán quy hoạch phân tuyến tính bao giờ cũng có ràng buộc về dấu của biến x. Rõ ràng các bài toán quy hoạch phân tuyến tính bất kỳ đều có thể đưa về dạng trên với một vài giả thiết thông thường khác như là L2(x) ≠ 0 trên miền xác định P. 1.4. Một số mô hình bài toán thực tế đƣa về bài toán quy hoạch tuyến tính và phân tuyến tính: Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1.4.1. Bài toán lập kế hoạch sản xuất Giả sử một xí nghiệp sản xuất n loại sản phẩm và sử dụng m loại nguyên liệu khác nhau, cj là lãi suất (hay giá bán) đối với một đơn vị sản phẩm j (j =1,…, n), aij là suất chi phí tài nguyên loại i để sản xuất một đơn vị sản phẩm loại j, bi là lượng dự trữ tài nguyên loại i (i = 1,…,m). Gọi xj là lượng sản phẩm loại j (j = 1,…, n) mà xí nghiệp sản xuất. Trong các điều kiện đã cho, hãy xác định các giá trị x j (j = 1,…, n) sao cho tổng tiền lãi (hay tổng giá trị sản lượng hàng hóa) là lớn nhất với số tài nguyên hiện có. Mô hình toán học có dạng bài toán quy hoạch tuyến tính sau: n cjxj max j 1 với các điều kiện n ajxj bi 0, j 1,..., n i 1,..., m j 1 xj 1.4.2. Bài toán cái túi Một người du lịch muốn đem theo một cái túi có thể đựng được các đồ vật nặng không quá b kilogam. Có n loại đồ vật mà anh ta dự định đem theo. Mỗi một đồ vật loại j có khối lượng a j kilogam và giá trị c j . Người du lịch muốn chất vào túi các đồ vật sao cho tổng giá trị đồ vật đem theo là lớn nhất. Ký hiệu x j là số đồ vật loại j sẽ chất vào túi. Ta có bài toán sau: n cjxj max j 1 n ajxj b j 1 xj Số hóa bởi Trung tâm Học liệu 0, j 1,..., n http://www.lrc-tnu.edu.vn/ x j - nguyên, j 1,..., n Đây là một bài toán quy hoạch nguyên. 1.4.3. Bài toán mua (thuê) máy bay tối ƣu: Để mở rộng hoạt động, hãng hàng không dự định mua hoặc thuê K loại máy bay (B777, B767, A321, A330, A320, AT7,...) ta gọi tương ứng là loại máy bay k (k=1, 2, …, K). máy bay loại k có giá mua (thuê) là ck và có thời gian sử dụng là Tk năm. Hãng đự định mua (thuê) tối đa là N máy bay trong các loại máy bay trên với số vốn đầu tư hiện có là V , Bài toán cần giải quyết là hãng hàng không nên mua bao nhiêu máy bay mỗi loại để tổng thời gian sử dụng là nhiều nhất? Ta gọi xk là số lượng máy bay loại k cần mua, khi đó mô hình bài toán đặt ra là: K M Tk .xk (1.5) max k 1 Với các ràng buộc: K xk N k 1 K ck .xk V k 1 xk 0, k 1,2,..., K , nguyên Đây là một bài toán quy hoạch nguyên. 1.4.4. Bài toán định giá thành sản phẩm[6] Giả sử pj là năng suất của phương pháp Tj (j=1, 2, …, n) (tức là số lượng sản phẩm được sản xuất trong một đơn vị thời gian), rj là chi phí trong một đơn vị thời gian đối với phương pháp Tj , xj là số đơn vị thời gian sản xuất theo phương pháp TJ. như vậy giá thành của một đơn vị sản phẩm là: n c( x) j 1 Số hóa bởi Trung tâm Học liệu n cj xj / pj xj j 1 http://www.lrc-tnu.edu.vn/ Bài toán đặt ra là cực tiểu hàm c(x) với các ràng buộc về vật tư, lao động, kỹ thuật, vốn, …. 1.4.5. Bài toán vận tải phân tuyến tính Giả sử ta có m địa điểm phát hàng (kho hàng) Ai (i=1, 2, …, m), mỗi địa điểm phát hàng i có thể cung cấp tối đa ai đơn vị hàng . Và n địa điểm nhận hàng (nơi tiêu thụ) Bj (j=1, 2, …,n), mỗi địa điểm nhận hàng j cần phải nhận tối thiểu bj đơn vị hàng. pij là lợi nhuận thu được khi vận chuyển một đơn vị hàng từ Ai đến Bj dij là chi phí vận chuyển một đơn vị hàng từ Ai đến Bj. p0 và d0 là các lợi nhuận và chi phí khác ngoài vận chuyển. Gọi xij là số lượng hàng cần vận chuyển từ Ai đến Bj. khi đó bài toán đặt ra là: m L1 ( x) L2 ( x) ( L) f ( x) n pij xij p0 i 1 j 1 m n min dij xij d0 i 1 j 1 Với các ràng buộc n xij ai , i 1.2,..., m j 1 m xij b j , j 1,2,..., n i=1 xij 0, i 1,2,..., m; j 1,2,..., n. 1.5. Một số khái niệm và tính chất của hàm gần lồi-gần lõm Trong mục này chúng ta nhắc lại một số khái niệm và tính chất cơ bản của một lớp hàm có liên quan mật thiết với hàm tuyến tính và phân tuyến tính. Như chúng ta đã biết một hàm gần lồi liên tục (không nhất thiết khả vi) thì cực tiểu địa phương là cực tiểu tuyệt đối trên miền xác định của nó, còn một hàm gần lõm thì nếu nó có cực tiểu trên miền xác định của nó và miền xác định có điểm cực biên thì cực tiểu sẽ đạt tại ít nhất một đỉểm cực biên của miền xác định. Chính vì thế ta có thể dựa trên các khái niệm và tính chất của hàm gần lồi-gần lõm nhắc lại dưới xây dựng các thuật toán kiểu đơn hình để giải bài toán cực tiểu hàm gần lồi-gần lõm trên Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ miền ràng buộc thuyến tính ([1],[2]). Rõ ràng hàm tuyến tính và phân tuyến tính đều thuộc lớp hàm gần lồi-gần lõm trên miền xác định. Chính vì thế ta có thể cải tiến các thuật toán đã đề nghị trong [1] và [2] để xây dựng các thuật toán giải cho bài toán quy hoạch phân tuyến tính và tuyến tính. 1.5.1. Tập lồi đa diện Định nghĩa : Một tập lồi mà là giao của một số hữu hạn nửa không gian đóng gọi là tập lồi đa diện.Nói cách khác, đó là tập nghiệm của một hệ hữu hạn các bất phương trình tuyến tính : ai , x bi , i 1,..., m(a i  n ,bi nghĩa là tập các nghiệm đúng Ax b với ) (1.4) là một ma trận cấp m*n và b  m Vì một phương trình tuyến tính có thể biểu diễn tương đương bằng hai bất phương trình tuyến tính nên một tập lồi đa diện cũng là tập nghiệm của một hệ các phương trình và bất phương trình tuyến tính : ai , x ai , x bi , = 1,…, bi , i p 1,..., m Hạng của hệ bất phương tuyến tính (1.4) được định nghĩa bằng hạng của ma trận A. Nếu hạng của hệ này bằng thì ta nói hệ độc lập tuyến tính. Một tập lồi đa diện có thể không bị chặn ( không giới nội ). Một tập lồi đa diện mà đồng thời là một nón lồi ( tương ứng với trường hợp b=0) gọi là một nón lồi đa diện.Một tập lồi đa diện bị chặn còn được gọi là một đa diện lồi. Các đa giác lồi theo nghĩa thông thường trong  2 là những ví dụ cụ thể về đa diện lồi. Mỗi điểm cực biên của một tập lồi đa diện còn được gọi là một đỉnh của nó. .. Tập các đỉnh của C ký hiệu là c . Mỗi cạnh vô hạn của một tập lồi đa diện tương ứng với một phương cực biên của nó. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Cho tập lồi đa diện D xác định bởi hệ bất phương trình tuyến tính (1.4). Khi đó mỗi bất phương trình (1.4) gọi là một ràng buộc của D. Ta nói điểm x0 * D thoả mãn chặt ràng buộc i * nếu a i , x0 i : ai , x Với mỗi x D ký hiệu I x bi . bi là tập chỉ số của những ràng buộc thoả mãn chặt tại x. Ký hiệu I0 bi x D . Tính chất đặc trưng của các diện ( nói i : ai , x riêng, các đỉnh và cạnh ) của D được cho trong định lý sau : Định lý 1.5.1 Một tập con khác rỗng F khi x : ai , x F Với I là một tập chỉ số sao cho I 0 D là một diện thực sự của D khi và chỉ bi , x a i , x bi , i I 1,..., m (I – tập chỉ số xác định diện F). I1 Hơn nữa ,ta có : dimF=n- rank a i I và dimD n rank a i I0 Hệ quả : Nếu D là một tập lồi đa diện xác định bởi hệ (1.4) thì : Điểm a) x0 rank a i : ix I x0 D là một đỉnh của D khi và chỉ khi n nghĩa là x 0 thoả mãn chặt n ràng buộc độc lập tuyến tính của hệ (1.4). b) Nếu một đoạn thẳng ( nửa đường thẳng hay cả đường thẳng ) T D là một cạnh của D thì T được xác định bởi một tập chỉ số I sao cho : rank a i I n 1 Tức là mọi x T cùng thoả mãn chặt n-1 ràng buộc độc lập tuyến tính của hệ (1.4). Mỗi tập lồi đa diện chỉ có một sô hữu hạn đỉnh và cạnh ( hữu hạn hay vô hạn ). Trong  n một đa diện lồi có k 1(0 k n) đỉnh độc lập afin gọi là một k – đơn hình. Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Định lý 1.5.2 a) Mỗi đa diện lồi C bằng bao lồi của tất cả các đỉnh của nó C=convC hay x C khi và chỉ khi : 2 p x 1v1 ... với mọi i 0, 1 ... p 1 và vi 1,..., p là 2v pv các đỉnh của C. b) Với tập lồi đa diện không giới nội , mỗi có thể biểu diễn dưới dạng một tổ hợp lồi của các đỉnh của cộng với một tổ hợp tuyến tính không âm của các phương cực biên của C , nghĩa là : 2 1 2 p x C x 1v1 ... p v p ... 2v 1u 2u pu Với mọi i 0, 1 ... p 1, j 0, p, q 0 là số nguyên, v i là các đỉnh của C i 1,..., p , u i j 1,..., q là phương của các cạnh vô hạn của C Với tập lồi đa diện ui không có đỉnh thì biểu diễn trên chỉ cần các v i C và các recC . Định lý trên cho thấy ứng với mỗi tập lồi đa diện cho trước có hai nhóm hữu hạn véctơ, sao cho tập lồi ấy chính là tập tất cả các điểm có thể biểu diễn thành tổng của một tổ hợp lồi của các véctơ thuộc nhóm thứ nhất và một tổ hợp tuyến tính không âm của các véctơ thuộc nhóm thứ hai. Các véctơ trong nhóm thứ nhất đều thuộc ,các véctơ trong nhóm thứ hai đều là các phương vô hạn của . Ngược lại, có thể chứng minh được rằng nếu cho trươc hai nhóm hữu hạn véctơ thì tập tất cả các điểm có thể biểu diễn như trên xác định một tập lồi đa diện. 1.5.2. Một số khái niệm cơ bản liên quan đến hàm gần lồi-gần lõm Hàm phân tuyến tính và tuyến tính là các hàm gần lồi – gần lõm trên miền xác định trong Rn ([1], [2]). Do đó các kết quả lý thuyết cũng như phương pháp tìm cực tiểu đối với hàm gần lồi-gần lõm đưa ra trong sách “Quy hoạch gần lồi-gần lõm ứng dụng vào quy hoạch tuyến tính” ([1]) có thể áp dụng đối với hàm phân tuyến tính và hàm tuyến tính. Chính vì vậy, trước khi trình bày bài toán quy hoạch phân tuyến tính và thuật toán nón xoay giải nó, chúng ta nhắc lại một số khái niệm, định nghĩa, các định lý, hệ quả và các tính chất cơ bản của hàm gần lồi-gần lõm đã trình bày trong sách “Quy hoạch gần lồi-gần lõm ứng dụng vào quy hoạch tuyến tính” Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ([1]). Việc chứng minh các định lý, hệ quả và các tính chất này đã trình bày trong cuốn sách nói trên. Định nghĩa 1.1: Hàm f:  n  1 là một hàm tựa lõm (quasi-concave) nếu x, y  n , và [0, 1] ta luôn có: f( .x +(1- ).y ) min{f(x), f(y)} Định nghĩa 1.2: Hàm f:  n  1 là một hàm tựa lồi (quasi-convex) nếu x, y  n , và [0, 1] ta luôn có: f( .x + (1- ).y ) max{f(x), f(y)} Định nghĩa 1.3:  1 là một hàm gần lõm (almost-concave) nếu nó là một hàm tựa Hàm f:  n lõm và thoả mãn f( .x + (1- ).y )>min{f(x), f(y)} x, y Rn, f(x) f(y) và (0, 1). Định nghĩa 1.4:  1 là một hàm gần lồi (almost-convex) nếu nó là một hàm tựa lồi Hàm f:  n và thoả mãn f( .x + (1- ).y )0, hay ta nói f tăng theo hướng z từ x0. 2. Điểm z ≠ 0 được gọi là một hướng giảm từ x0 của hàm gần lồi – gần lõm f nếu 0 0 f(x ) > f( x + .z ) >0, hay ta nói f giảm theo hướng z từ x0 . Từ các định nghĩa trên ta suy ra một vài tính chất sau 3. Điểm z ≠0 gọi là hướng không đổi của f từ x0, nếu f(x0)=f(x0+ .z ), α  1 . Định lý 1.5.6. Nếu tồn tại của hàm gần lồi-gần lõm f . 1 > 0 mà f(x) < f(x+ Số hóa bởi Trung tâm Học liệu 1.z) thì z là một hướng tăng từ x http://www.lrc-tnu.edu.vn/ Hệ quả 1.2:Nếu f(x) 0 mà f(x) > f(x+ của hàm gần lồi-gần lõm f . 1.z) thì z là một hướng giảm từ x Hệ quả 1.3: Nếu f(x)>f(x+z) thì z là một hướng giảm từ x của hàm gần lồi-gần lõm f Định nghĩa 1.8. Hàm gần lồi – gần lõm f được gọi là không bị chặn trên  n nếu z 0 và x  n ta có: 1) lim f( x+ .z ) = +∞ , với z là hướng tăng từ x của hàm f. 2) lim f( x+ .z ) = -∞ , , với z là hướng giảm từ x của hàm f. Định lý 1.5.8 f:  n f(x) ≤ f( x+ .z ),  1 là hàm gần lồi-gần lõm, nếu f(x0) ≤ α >0, x 0 f( x + z ). thì  n. Định lý 1.4.8 cho ta kết luận rằng nếu z là một hướng không giảm của f tại x0 thì nó cũng là một hướng không giảm của f tại mọi điểm x thuộc  n . Do đó ta gọi z là một hướng không giảm của hàm f. Từ định lý 1.4.8 ta dễ dàng chứng minh được hệ quả sau.  1 là hàm gần lồi-gần lõm,nếu f(x0) > f( x0+ z) ,. thì z là một Hệ quả 1.4: f:  n hướng giảm của hàm f , x  n , tức là f(x)>f(x+ .z), 0, x  n . Và ta gọi z là một hướng giảm của hàm f.  1 là hàm gần lồi-gần lõm, z≠0 .là một hướng giảm của hàm Hệ quả 1.5: f:  n f khi và chỉ khi: f(0)>f( .z), 0  1 là hàm gần lồi-gần lõm,nếu f(x0) < f( x0+ z) ,. thì z là một Hệ quả 1.6: f:  n hướng tăng của hàm f , x  n , tức là f(x)f(y) thì z = x – y là một hướng tăng f:  n của hàm f và z= y - x là một hướng giảm của hàm f. Từ định lý 1.4.8 và hệ quả 1.4, chúng ta dễ dàng có hệ quả dưới đây.  1 là hàm gần lồi-gần lõm, nếu z≠0 và f(x0)= f( x0+ z ), tức z Hệ quả 1.9. f:  n là một hướng không đổi của f tại x0 thì z là một hướng không đổi của hàm f tại mọi  1 , x  n . Và ta nói z là một hướng điểm x thuộc  n , tức là f(x)=f(x + .z), không đổi của hàm f.  1 là hàm gần lồi-gần lõm, z≠0 .là một hướng không đổi Hệ quả 1.10. f:  n của hàm f khi và chỉ khi: f(0)=f( .z), 0.  1 và Từ tính chất thứ 1.2 và hệ quả 1.9 ta có thể chứng minh dễ dàng hệ quả sau: Hệ quả 1.11 R1 , Nếu x ≠ y mà f(x)=f(y) thì 0 chúng ta có z = α.( x – y), là hướng 1 không đổi của hàm f và f (u ) f (u .( x y )), u  n ,  1 là hàm gần lồi-gần lõm, z≠0 .là một hướng không giảm Hệ quả 1.12. f:  n của hàm f khi và chỉ khi: f(0)≤f( .z), 0  1 và Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ CHƢƠNG 2 THUẬT TOÁN NÓN XOAY GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VÀ THUẬT TOÁN KIỂU ĐƠN HÌNH GIẢI BÀI TOÁN QUY HOẠCH PHÂN TUYẾN TÍNH Trước khi xây dựng thuật toán xấp xỉ ngoài giải bài toán quy hoạch phân tuyến tính dựa trên khái niệm nón xoay đề nghị trong [1] và [2], chúng ta trình bày thuật toán nón xoay tuyến tính giải bài toán quy hoạch tuyến tính dạng chuẩn dựa trên khái niệm nón xoay đề nghị trong [1] và thuật toán kiểu đơn hình giải bài toán quy hoạch phân tuyến tính với ràng buộc là hệ phương trình tuyến tính trình bày trong [4]. 2.1. Thuật toán nón xoay giải bài toán quy hoạch tuyến tính dạng chuẩn Xét bài toán qui hoạch tuyến tính sau đây gọi là bài toán quy hoạch tuyến tính dạng chuẩn tổng quát: n f ( x) C, x ( L) ci .xi min i 1 x PL : x  n : Ai , x bi 0, i 1, 2,..., m x  n , Ai là véc tơ dòng và Ai ,  n m n, Ai (ai1, ai2, ..., ain) ≠ O(0,…,0) , C(c1, c2, …, cn), bi  1 , i=1, 2, ..., m. Hạng của hệ Ai (i=1, 2, …, m) bằng n, giả thiết này rất bình thường bởi miền ràng buộc PL của bài toán quy hoạch tuyến tính bao giờ cũng có ràng buộc về dấu của biến x. 2.1.1 Phƣơng pháp nón xoay tuyến tính: Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Một áp dụng hay chính xác hơn là một biến thể quan trọng của phương pháp nón – min giải bài toán qui hoạch gần lồi-gần lõm đề nghị trong cuốn sách “Quy hoạch gần lồi-gần lõm ứng dụng vào quy hoạch tuyến tính” (NXB Khoa học và kỹ thuật năm 2011) ([1]) trình bày dưới đây sẽ cho chúng ta một phương pháp giải trực tiếp bài toán quy hoạch tuyến tính dạng chuẩn với cơ sở xuất phát từ đỉnh một nón-min của hàm mục tiêu gọi là phương pháp nón xoay tuyến tính được thể hiện dưới dạng thuật toán chi tiết. Thông thường việc biết một nón-min của bài toán nói chung không khó khăn gì. Chẳng hạn trong trường hợp miền ràng buộc PL của bài toán (L) là đa diện, ta có thể dễ dàng chỉ ra được một chóp đơn hình với n+1 đỉnh đã biết chứa PL , đỉnh nào của chóp đơn hình này có giá trị của hàm mục tiêu nhỏ nhất tại đó so với các giá trị của hàm mục tiêu tại các đỉnh còn lại của chóp thì nón chứa chóp đơn hình tương ứng với đỉnh này chính là một nón-min của bài toán (L). Thuật toán đề nghị giải trực tiếp bài toán quy hoạch tuyến tính dạng chuẩn trình bày ở đây chính là một biến thể của thuật toán nón-min giải bài toán quy hoạch gần lồi - gần lõm nói trên với miền ràng buộc thuộc dạng bất phương trình tuyến tính( [1]). Xét bài toán (L) trong trường hợp biết một nón – min của bài toán (L). Ý tưởng của thuật toán nón xoay tuyến tính giải bài toán (L) như sau: Xuất pháp từ một nón-min M ban đầu của hàm mục tiêu bài toán, chúng ta kiểm tra xem đỉnh của nó có thuộc miền chấp nhận của bài toán không (tức là đỉnh này có thoả mãn tất cả các ràng buộc không) nếu đỉnh này thuộc miền chấp nhận thì nó là một lời giải của bài toán (L). Ngược lại ta xây dựng nón xoay mới M(r,s) (vẫn là nón-min) từ nón cũ M của bài toán (L) và lặp lại quá trình kiểm tra nón xoay mới này tương tự như đối với nón M, quá trình này được thực hiện cho đến khi đỉnh của nón xoay mới M(r,s) thuộc miền chấp nhận của bài toán (L) ( khi miền ràng buộc của bài toán (L) có phương án) hoặc sẽ phát hiện ra miền ràng buộc của bài toán (L) là rỗng. 2.1.2. Thuật toán nón xoay tuyến tính Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Bước chuẩn bị (bước 0).Giả sử ta đã biết M0 là nón - min của bài toán (L) với tập chỉ số cơ sở là I0:={ i10 , i20 ,..., in0 }, x0 = x M là đỉnh của M0 và các véc tơ chỉ phương 0 của các cạnh i của nón M0 là z0i = z Mi (i I0). 0 Bước k ( k=0, 1, 2, ...). Giả sử Mk là nón - min của bài toán (L) (đã được xây dựng), với tập chỉ số cơ sở , đỉnh và các véc tơ chỉ phương của các cạnh của nón Mk tương ứng là Ik:= i1k , i2k ,..., ink ; xk = x M và zki = z Mi . k k Xác định tập J+(xk) như sau: J ( xk ) : 1, 2,..., m : A j , x k j bj 0 1. Nếu J+(xk) = thì dừng. xk chính là một lời giải của bài toán (L), 2. Nếu J+(xk) , ta chọn chỉ số đưa vào cơ sở theo một trong hai cách sau: Ta chọn sk là một chỉ sô tuỳ ý thuộc J+(xk) hoặc ta chọn sk=min{j:j J+(xk)} (gọi là qui tắc chọn min) hoặc sk = max{j: j J+(xk) (gọi là qui tắc chọn max) và xác định: I sk : i I sk : i I sk : Ask , zki 2.1. Nếu I s = k 2.2. NÕu I s Gọi V sk 0 0 ; iskk 1 , iskk 2 ,..., iskk qk , (2.2) thì dừng lại, suy ra bài toán (L) không có phương án. : k :={ v I k : Ask , zki (2.1) sk I : C , zkv Ask , zkv C , zki min{ sk Ask , zki i I (2.3) }} và chọn chỉ số đưa ra khỏi cơ sở theo một trong hai cách sau: Ta chọn rk là chỉ số tuỳ ý thuộc V s . k hoặc ta chọn rk = min{v: v V sk } hoặc rk = max{v: v Số hóa bởi Trung tâm Học liệu V sk } (2.4) http://www.lrc-tnu.edu.vn/