Đăng ký Đăng nhập
Trang chủ Một phương pháp xấp xỉ ngoài giải bài toán quy hoạch tuyến tính với hàm mục tiêu...

Tài liệu Một phương pháp xấp xỉ ngoài giải bài toán quy hoạch tuyến tính với hàm mục tiêu có hệ số không âm và ứng dụng

.PDF
55
136
91

Mô tả:

ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC BÙI THỊ HỒNG HẠNH MỘT PHƢƠNG PHÁP XẤP XỈ NGOÀI GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VỚI HÀM MỤC TIÊU CÓ HỆ SỐ KHÔNG ÂM VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN – 2014 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC BÙI THỊ HỒNG HẠNH MỘT PHƢƠNG PHÁP XẤP XỈ NGOÀI GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VỚI HÀM MỤC TIÊU CÓ HỆ SỐ KHÔNG ÂM VÀ ỨNG DỤNG 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/ LỜI CẢM ƠN Để hoàn thành luận văn này, tôi đã nhận đƣợc sự động viên đóng góp nhiệt tình từ các thầy cô giáo của trƣờng Đại học Khoa học – Đại học Thái Nguyên, tôi xin gửi lời cảm ơn chân thành tới các thầy cô giáo. Đặc biệt tôi gửi lời cảm ơn sâu sắc tới TS. Nguyễn Anh Tuấn là ngƣời thầy đã đề xuất các hƣớng nghiên cứu, động viên thƣờng xuyên và tận tâm chỉ bảo nghiêm túc về chuyên môn trong suốt thời gian qua để tôi hoàn thành luận văn này. Tôi cũng xin bày tỏ lòng biết ơn đối với gia đình, bạn bè và ngƣời thân đã động viên khuyến khích và giúp đỡ tôi trong suốt quá trình hoàn thành luận văn này. Tôi xin chân thành cảm ơn! Thái Nguyên, tháng 08 năm 2014 Tác giả i Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ MỤC LỤC LỜI CẢM ƠN ............................................................................................................ i MỤC LỤC ................................................................................................................. ii MỞ ĐẦU .................................................................................................................. iv Chƣơng 1 ................................................................................................................... 1 PHƢƠNG PHÁP NÓN XOAY 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 VỚI HÀM MỤC TIÊU CÓ HỆ SỐ KHÔNG ÂM ....................................................................................................... 1 1.1. Bài toán quy hoạch tuyến tính ........................................................................ 1 1.2. Khái niệm về nón đơn hình tuyến tính, cạnh và phƣơng của nón và Nón – min (nón cực tiểu) .................................................................................................. 2 1.2.1. Khái niệm về nón đơn hình tuyến tính ..................................................... 2 1.2.2. Khái niệm về cạnh của nón đơn hình ....................................................... 2 1.2.3. Khái niệm nón xoay M(r,s) sinh ra từ nón M .......................................... 5 1.2.4. §Þnh nghÜa Nón – min (Nón cực tiểu) ..................................................... 7 1.3. Phƣơng pháp nón xoay tuyến tính .................................................................. 8 1.3.1. Thuật toán nón xoay tuyến tính ................................................................ 9 1.3.2. Bảng lặp giải bài toán quy hoạch tuyến tính bởi thuật toán nón xoay tuyến tính và ví dụ minh hoạ ............................................................................ 12 1.4. Thuật toán nón xoay giải bài toán quy hoạch tuyến tính dạng chuẩn với hàm mục tiêu có hệ số không âm ................................................................................ 17 1.4.1. Bài toán quy hoạch tuyến tính dạng chuẩn với hàm mục tiêu có hệ số không âm .......................................................................................................... 17 1.4.2 Xây dựng nón – min (nón cực tiểu) xuất phát......................................... 18 1.4.3. Thuật toán nón xoay tuyến tính LD giải bài toán quy hoạch tuyến tính với hàm mục tiêu có hệ số không âm ............................................................... 18 ii Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1.4.4. Giải bài toán quy hoạch tuyến tính dạng chuẩn với hàm mục tiêu có hệ số không âm bằng thuật toán nón xoay LD dƣới dạng bảng nón xoay thu gọn và các ví dụ minh hoạ ....................................................................................... 19 1.4.5. Minh hoạ hình học thuật toán nón xoay tuyến tính LD ......................... 20 Chƣơng 2 ................................................................................................................. 26 ỨNG DỤNG THUẬT TOÁN NÓN XOAY LD GIẢI MỘT VÀI LỚP BÀI TOÁN QUY HOẠCH TUYẾN TÍNH THƢỜNG GẶP..................................................... 26 2.1. Bài toán quy hoạch tuyến tính dạng chuẩn có tổng các biến bị chặn trên.... 26 2.1.1. Bài toán................................................................................................... 26 2.1.2. Ví dụ minh họa ....................................................................................... 33 2.2. Thuật toán nón xoay LD giải bài toán quy hoạch tuyến tính dạng chính tắc khi biết một cơ sở đối ngẫu.................................................................................. 36 KẾT LUẬN ............................................................................................................. 47 TÀI LIỆU THAM KHẢO ....................................................................................... 48 iii 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 tuyến tính có hai dạng cơ bản là dạng chuẩn và dạng chính tắc, hai dạng này có quan hệ mật thiết với nhau. Bài toán quy hoạch tuyến tính dạng chuẩn là bài toán có miền ràng buộc là một hệ bất phương trình tuyến tính với các biến không âm, còn bài toán quy hoạch tuyến tính dạng chính tắc là bài toán quy hoạch có miền ràng buộc là một hệ phương trình tuyến tính với các biến của nó có dấu không âm. Thuật toán đơn hình và đơn hình đối ngẫu do George Dantzig và Lemke đề xuất vào những năm 1947 và 1954 đã giải bài toán quy hoạch tuyến tính ở dạng chính tắc. Nhiều bài toán quy hoạch tuyến tính trên thực tế thường bắt đầu ở dạng chuẩn tắc, do vậy luận văn này trình bày phương pháp nón xoay giải trực tiếp bài toán quy hoạch tuyến tính với miền ràng buộc là hệ bất phương trình tuyến tính, từ đó xây dựng 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 với hàm mục tiêu có hệ số không âm và một vài ứng dụng của nó. Luận văn gồm 2 chương: Chương 1 trình bày phương pháp nón xoay 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 với hàm mục tiêu có hệ số không âm với cơ sở xuất phát ban đầu là gốc tọa độ O(0,0,…,0). Chương 2 trình bày ứng dụng của thuật toán nón xoay tuyến tính trình bày trong chương 1 giải cho hai lớp bài toán quy hoạch tuyến tính thường gặp sau khi đã đưa hai lớp bài toán này về dạng bài toán quy hoạch tuyến tính với hàm mục tiêu có hệ số không âm. Các thuật toán nón xoay trình bày trong luận văn này đượ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 tài liệu [5]. [6], và các tài liệu có trong phần tài liệu tham khảo. Tác giả iv Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Bùi Thị Hồng Hạnh v Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Chƣơng 1 PHƢƠNG PHÁP NÓN XOAY 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 VỚI HÀM MỤC TIÊU CÓ HỆ SỐ KHÔNG ÂM Nội dung chƣơng này, chúng tôi trình bày một phƣơng pháp giải bài toán quy hoạch 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ộc lƣợc đồ xấp xỉ ngoài (vì nó xuất phát giải từ đỉnh của một nón đơn hình tuyến tính ngoài miền chấp nhận đƣợc) gọi là thuật toán nón xoay tuyến tính [5]. Từ đó trình bày một trƣờng hợp riêng biến thể của nó giải bài toán quy hoạch tuyến tính dạng chuẩn khi hàm mục tiêu có các hệ số không âm, đây là lớp bài toán thƣờng hay gặp trong thực tế. 1.1. Bài toán quy hoạch tuyến tính XÐt bài toán quy hoạch tuyến tính với miền ràng buộc là hệ bất phƣơng trinh tuyến tính sau: n f ( x) C, x ( L) ci .xi min i 1 x PL : x R n : Ai , x bi 0, i 1,2,..., m x R n , Ai là véc tơ dòng và Ai R n , m n, Ai (ai1, ai2, ..., ain) ≠ O(0,…,0) , C(c1, c2,…, cn), bi R1 , 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 nói chung bao giờ cũng có ràng buộc về dấu của biến x. 1 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1.2. Khái niệm về nón đơn hình tuyến tính, cạnh và phƣơng của nón và Nón – min (nón cực tiểu) 1.2.1. Khái niệm về nón đơn hình tuyến tính Xét tập M ®-îc x¸c ®Þnh tõ n rµng buéc tuyÕn tÝnh nµo ®ã cña PL , cô thÓ lµ: M:={x R n : + bi 0 i I} (1.1) {1, 2, ..., m}, /I/ = n (ở đây /I/ là số đo hay là số phần tử trong ®ã I:= i1, i2 ,..., in của tập I) vµ Ai với i I lµ mét hệ ®éc lËp tuyÕn tÝnh. Tập M gọi là nón đơn hình tuyến tính của hệ ràng buộc PL víi ®Ønh xM lµ nghiÖm (®-îc x¸c ®Þnh) thoả mãn hÖ sau: + bi = 0, Hệ véc tơ Ai víi i i I (1.2) I đƣợc gọi là cơ sở của nón M, hay còn gọi là cơ sở của đỉnh xM. Tập I gọi là tập chỉ số của cơ sở của nón M. 1.2.2. Khái niệm về cạnh của nón đơn hình Với mỗi i I, tập hợp các điểm x Rn thỏa mãn hệ: + br = 0, r I\{i} (1.3) gọi là đƣờng thẳng i của nón M. Tập các điểm x thoả mãn hệ: Ar , x br 0, r Ai , x bi 0 I\ i gọi là cạnh i của nón M. Với mỗi i (i I), VÐc t¬ zMi (i I), x¸c ®Þnh bëi hệ: Ar , zMi i A ,z i M 0, r I,r i (1.4) 1 gọi là véc tơ chỉ phƣơng của cạnh i của nón M. 2 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Đỉnh xM của nón M có thể xác định từ (1.2), trong trƣờng hợp biết hệ véc tơ chỉ phƣơng zMi (i I) thì chúng ta có thể sử dụng công thức sau: xM bi .zMi (1.5) i I 3 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Định lý 1.1 [5] Nếu xM là đỉnh của nón đơn hình M đƣợc xác định từ (1.2), và hệ véc tơ chỉ phƣơng z Mi (i I) của cạnh i của nón M xác định từ (1.4) thì chúng ta có thể xác định đỉnh xM từ công thức sau: xM bi .zMi i I Từ định lý 1.1 ta suy ra trong trƣờng hợp biết hệ véc tơ chỉ phƣơng z Mi (i I) thì chúng ta có thể xác định đỉnh xM từ công thức sau: xM bi .zMi i I Ta ký hiÖu: J+(xM):= {j {1, 2, ..., m}: + bj > 0} (1.6) Râ rµng khi J+(xM) = th× xM chÝnh lµ mét ®iÓm chÊp nhËn cña bµi to¸n (L). Chóng ta gi¶ sö J+(xM) . Víi mçi s Is := {i I: < As, z Mi > 0} I: I0 := {i I: < As, z Mi > = 0} } J+(xM), chóng ta ký hiÖu nh- sau: i1, i2 ,..., in I: (1.7) i1, i2 ,..., in (1.8) Ta thấy: I = I0 I s . Víi mçi i Is th× ®-êng th¼ng x=xM+α. z Mi sÏ giao với siªu ph¼ng + bs=0 xi = xM + t¹i ®iÓm: i =- Trong ®ã: As , x M As , zMi . z Mi . (1.9) i bs (1.10) Ta gäi I s := {i Is : i >0} = i I s : As , zMi và I s := {i Is : Rõ ràng I s §Þnh lý 1.2 Is i 0 ={ is1, is 2 ,..., isq } <0}. I. s J ( x M ) thì I s 4 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ (1.11) Chứng minh (xem [5]) §Þnh lý 1.3 [5] thì tập phƣơng án của bài toán (L) là rỗng. Is §Þnh lý nµy cho ta kÕt luËn r»ng, nÕu bài toán (L) cã Ýt nhÊt mét ®iÓm chÊp nhËn ®-îc th× I s lµ mét tËp kh¸c rçng. 1.2.3. Khái niệm nón xoay M(r,s) sinh ra từ nón M Giả sử M là một nón đơn hình tuyến tính của hệ ràng buộc PL xác định bởi (1.1) và J+(xM)≠Ø, khi đó với mỗi r I s , tËp hîp c¸c ®iÓm x tho¶ m·n hÖ bÊt ®¼ng thøc: Ai , x bi 0, i s bs 0 A ,x I ,i r (1.12) x¸c ®Þnh mét nãn đơn hình tuyến tính gọi là nón xoay M(r,s), ®Ønh lµ: xM(r,s) =x r = xM + trong ®ã r . z Mr (1.13) r x¸c ®Þnh tõ (1.10) §Ønh xr tho¶ m·n: + bi = 0 i I(r,s) = (I {s}\{r}). TËp chØ sè c¬ së míi I(r,s) nhËn ®-îc tõ tËp chØ sè c¬ së cò I b»ng c¸ch lo¹i chØ sè r ra khái tËp c¬ së cò, ®-a chØ sè s vµo thay. Ta nói nón xoay M(r,s) sinh ra từ nón M. Bổ đề 1.1 Hệ Ai với i I(r,s) là một hệ độc lập tuyến tính. Chứng minh Thật vậy, nếu ngƣợc lại hệ Ai với i I(r,s) là phụ thuộc tuyến tính thì dễ dàng suy ra tồn tại biểu diễn: βiAi As = i I \{ r } βiAi, z Mr >= < As, z Mr >=< i I \{ r } βi=0 i I \{r } 5 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Điều này mâu thuẫn với 0 (vì r I s ). Bổ đề này cho ta thấy nón xoay M(r,s) vẫn là một nón đơn hình. C¸c vÐc t¬ chØ ph-¬ng zMi ( r ,s ) , i I(r,s) cña nãn xoay mới M(r,s) ®-îc x¸c ®Þnh tõ (1.4) víi tËp chØ sè cơ sở míi I(r,s), hoặc x¸c ®Þnh từ một trong các c«ng thøc ®¬n gi¶n dƣới đây theo các xi, xr, zMi , zMr (xác đinh từ (1.4), (1.9), (1.10)) với i, r thuộc I là tập chỉ số của cơ sở cũ: zMi zMi ( r , s ) zMi r zMr khi i I0 khi i I s,i khi i s r (1.14) i 1 A , zMr s .zMr Hay: zMi z i M ( r ,s ) z As , zMi As , zMr i M 1 As , zMr zMr .zMr khi i I0 khi i I s ,i khi i r (1.15) s Các công thức này gọi là các công thức đổi cơ sở, bổ đề dƣới đây chứng minh các công thức trên. Bổ đề 1.2 [5] Giả sử M là nón xác định bởi: M:={x Rn : + bi 0 i I } với các véc tơ chỉ phƣơng zMi của các cạnh xác định theo (1.4), các giao điểm xi xác định theo (1.9), (1.10). Khi đó nón xoay M(r,s) có đỉnh là xM(r,s) = xr xác định từ (1.12) với cơ sở tƣơng ứng là I(r,s) = (I 6 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ {s}\{r}) và các véc tơ chỉ phƣơng của các cạnh tƣơng ứng là zMi ( r ,s ) đƣợc xác định bởi (1.15). 1.2.4. §Þnh nghÜa Nón – min (Nón cực tiểu) Nãn ®¬n h×nh tuyÕn tÝnh M víi ®Ønh lµ xM ®-îc gäi lµ nãn - min cña hàm f(x)= của bài toán (L) nÕu f(xM) f(x) , x M. Ta nãi M lµ mét nãn - min cña bµi to¸n (L) khi M là một nón – min của hàm mục tiêu f của bài toán (L). Giả sử M là một nón đơn hình xác định từ hệ (1.1) đỉnh là xM, víi vÐc t¬ chỉ phƣơng của cạnh i là zMi (i I), x¸c ®Þnh bëi (1.4), ta có định lý sau. Định lý 1.4 Nếu f(xM) f(xM + z Mi ) I thì M là một nón - min của hàm f. Chứng i minh (xem [1]) Hệ quả 1.1 M là một nón - min của hàm f(x)= khi và chỉ khi: ≥ 0, i I. Gi¶ sö M lµ mét nón - min của hàm mục tiêu f(x)= của bài toán (L). Gäi Vs := {v {f(xi)}} I s : f(xv) = min s (1.16) i I Vậy Vs= {v {}} I s : = min s i I Thay xv và xi xác định từ công thức (1.9) vào trên ta có: Vs := {v {}}= I s : = min s i I ={ v I s : C , x M ={ v I s : v v .zMv min{ C, xM s i I . C , zMv i .zMi } }= min{ C , zMi } }= i. s i I 7 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ s s ={ v I : ( A , x C , zMv bs ). As , zMv M s ={ v I : s C , zMv As , zMv Vậy, V :={ v I : s s min{ ( A ,x s i I C , zMv As , zMv min{ s i I M C , zMi bs ). } }= As , zMi C , zMi }} As , zMi C , zMi }} As , zMi min{ s i I (1.17) Định lý 1.5 Với mçi r Vs xác định từ (1.17), nếu M là một nón – min của hàm mục tiêu của bài toán (L) thì nãn M(r,s) xác định từ (1.12) cũng lµ mét nãn - min của hàm mục tiêu bµi to¸n (L) Chøng minh (xem [5]) Đỉnh x M ( r ,s ) của nón xoay M(r,s) còn có thể xác định công thức sau đây khi biết các véc tơ chỉ phƣơng các cạnh của nón xoay M(r,s): x M ( r ,s ) bi .zMi ( r ,s ) (1.18) i I ( r ,s ) PhÇn d-íi ®©y chóng ta sÏ xây dựng thuật toán nón xoay giải bài toán (L) dựa vào c¬ së lý thuyết trình bày ở các phần trên vµ ®Þnh lý 1.5. 1.3. Phƣơng pháp nón xoay tuyến tính Một áp dụng hay nói đúng hơn là một biến thể của phƣơng pháp nón – min giải bài toán quy hoạch gần lồi-gần lõm đề nghị 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” (Nxb Khoa học và kỹ thuật năm 2011) ([6]) 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. 8 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 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). 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át 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. 1.3.1. Thuật toán nón xoay tuyến tính 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 M0 lµ ®Ønh cña M0 vµ c¸c vÐc t¬ chØ ph-¬ng của các cạnh i của nón M0 là z0i = z Mi 0 (i I0). 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 k vµ zki = z Mi k . X¸c ®Þnh tËp J+(xk) theo (1.6): J ( x k ) : j 1,2,..., m : A j , x k bj 0 9 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1. NÕu J+(xk) = th× dõng l¹i. 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à quy tắc chọn min) hoặc sk = max{j: j J+(xk) (gọi là quy tắc chọn max) vµ x¸c ®Þnh: I sk : i I sk : i I sk : Ask , zki I k : Ask , zki 0 0 ; iskk 1, iskk 2 ,..., iskk qk , (1.20) 2.1. NÕu I sk = th× dõng l¹i, suy ra bµi to¸n (L) kh«ng cã ph-¬ng ¸n. 2.2. NÕu I sk : Gäi V sk :={ v I sk : C , zkv Ask , zkv (1.19) C , zki }} Ask , zki min{ sk i I (1.21) 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 V sk } (1.22) (cách chọn chỉ số này gọi là quy tắc chọn min (hoặc là quy tắc chọn max)) . Vµ ta x©y dùng nón xoay Mk+1 = Mk(rk, sk) sinh ra từ nón-min Mk (xem mục 1.2.3), tập chỉ số cơ sở là Ik+1= Ik(rk, sk) = (Ik {sk}) \ {rk}; vµ c¸c vÐc t¬ chØ ph-¬ng zki (sö dông (1.15)): 10 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ 1 zki zki 1 khi i I k0 Ask , zki Ask , zkrk ( zki 1 A , zkrk sk .zkrk ) .zkrk khi i I ksk , i rk (1.23) khi i sk Tõ (1.5) và (1.13): k+1 x =x M k ( rk , sk )= rk k k x =x + k rk Quay trë l¹i b-íc k víi k rk k k .z = x - Ask , x k sk bsk A ,z rk k bi .zki . zkrk = i Ik (1.24) 1 1 k+1 Một số chó ý: 1) Tõ ®Þnh lý 1.5 ta dễ dàng có bổ đề 1.3 dƣới đây và do đó dÔ thÊy nãn xoay Mk+1 ®-îc x©y dùng (trong thuật toán) sinh ra từ nón-min Mk vÉn lµ mét nãn - min cña bµi to¸n (L). 2) Sù lùa chän chỉ số đƣa vào sk = min{j: j J+(xk)} và chỉ số đƣa ra rk = min{v: v Vks } sÏ lµm cho thuËn to¸n ®Ò nghÞ trªn kÕt thóc sau mét sè h÷u h¹n b-íc lÆp (kh«ng x¶y ra xoay vßng). §iÒu nµy ®-îc chứng minh bëi ®Þnh lý 1.6 dƣới đây. 3) Công thức (1.23) gọi là công thức xoay cơ sở và phần tử Ask , zkrk đƣợc gọi là phần tử xoay, nó là trung tâm để đổi các véc tơ chỉ phƣơng zki của hệ cơ sở cũ sang hệ cơ sở mới zki 1 theo công thức xoay (1.23). 4) Để cho gọn chúng ta đặt Ai , xk bi Ai ( xk ), i 1,2,..., m Dựa trên định lý 1.5, chúng ta dễ dàng chứng minh đƣợc bổ đề sau: Bổ đề 1.3 Tại mỗi bƣớc lặp k, khi giải bài toán (L) theo thuật toán nón xoay tuyến tính với quy tắc chọn chỉ số đƣa vào cơ sở và đƣa ra khỏi cơ sở là (1.19), (1.20) và 11 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ (1.21) thì nón xoay Mk+1 đƣợc xây dựng trong thuật toán vẫn là một nón – min của hàm mục tiêu và ta có: Sù lùa chän sk = min{j: j J+(xk)} và rk(sk)= max{v: v f ( xk ) f ( xk 1 ), k 1,2,... J+(xk)} và rk(sk)= min{v: v V sk }( hoặc sk = max{j: j V sk }) sÏ lµm cho thuËn to¸n ®Ò nghÞ trªn kÕt thóc sau mét sè h÷u h¹n b-íc lÆp (kh«ng x¶y ra xoay vßng). §iÒu nµy ®-îc chøng minh bëi ®Þnh lý sau. §Þnh lý 1.6 Giải bài toán (L) theo thuËt to¸n nón xoay với chỉ số chọn đƣa vào cơ sở là sk = min{j: j J+(xk)} (hoặc sk = max{j: j sở tƣơng ứng là rk(sk)= min{v: v J+(xk)}) và chỉ số chọn đƣa ra khỏi cơ V sk } (hoặc tƣơng ứng là rk(sk)= max{v: v V sk }) sẽ kÕt thóc sau mét sè h÷u h¹n b-íc lÆp vµ cho ta lêi gi¶i cña bµi to¸n (L), hoÆc ph¸t hiÖn ra miÒn rµng buéc PL cña bµi to¸n (L) lµ rçng. Chứng minh định lý này có thể tìm thấy trong [5] Định lý này vẫn đúng khi giải bài toán quy hoạch gần lồi-gần lõm theo thuật toán nón-min đã đƣợc chứng minh trong [6]. Năm 1977 RG. Bland đã đề xuất quy tắc tránh xoay vòng tƣơng tự nhƣ trên cho việc giải bài toán quy hoạch tuyến tính dạng chính tắc. 1.3.2. Bảng lặp giải bài toán quy hoạch tuyến tính bởi thuật toán nón xoay tuyến tính và ví dụ minh hoạ Để dễ tính toán, trong mỗi bƣớc lặp k ta thiết lập bảng dƣới đây gọi là bảng nón xoay thu gọn giải 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 của bài toán. 12 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/ Bảng lặp nón xoay thu gọn: Bảng A Chỉ số cơ sở bj c1 +bi c2 … c j … cn +bi k=1,2,… 1 b1 a11 a12 … a1 j … a1n +b1 +b1 2 b2 a 21 a22 … a2 j … a2n +b2 +b2 … … …… …… bsk ( sk ) … … … … ask 1 …. …. as 2 … as j … as n k k … … … am1 i1k k bik zki11 1 am 2 … amj ... amn k 2 i bik z 2 … ( rk= isk p ) k k … i i2k kj i2k kn … … … … brk rk k1 … ... +bm +bm 0 z n xk z …z …z rk k2 rk kj sk rk kn - i2k k C , zksk 1 ik Ask , zksk 1 … [ As , zkr k ] (- … C , zkrk Ask , zkrk ) … zkin1 zkin2 … z kjin … zknin x1k x2k … x kj … xnk k ik A ,z sk k k … … … … … k k k Ask , zki1 k bik Bƣớc z …z …z i2k k2 k k … … k n i2k k1 zki12 … z kji1 … zkni1 k ( As , x k >+ bs ) 0 k bm m (< As , x 0 >+ bs ) k ink k A ,z ik - C , zksk qk ik Ask , zksk qk k=0,1,2,… Bảng lặp nón xoay thu gọn A gồm 2 phần (xem bảng A): Các số liệu ban đầu đƣợc đƣa vào bảng và các số liệu cần tính toán theo các công thức trong thuật toán nón xoay đƣợc xây dựng thứ tự theo các bƣớc từ trên xuống dƣới và từ trái sang phải nhƣ sau: 13 Số hóa bởi Trung tâm Học liệu http://www.lrc-tnu.edu.vn/
- Xem thêm -

Tài liệu liên quan