Luận văn Thạc sĩ Toán học: Một phương pháp xấp xỉ ngoài giải bài toán quy hoạch nguyên tuyến tính theo phương pháp nhánh cận và ứng dụng

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:59

Thêm vào BST

Báo xấu

32
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn trình bày một số mô hình bài toán thực tế có dạng bài toán quy hoạch nguyên tuyến tính, phương pháp nhánh cận Land-Doig và thuật toán nón xoay xấp xỉ ngoài tái tối ưu hóa TTH giải bài toán quy hoạch tuyến tính dạng chuẩn. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Một phương pháp xấp xỉ ngoài giải bài toán quy hoạch nguyên tuyến tính theo phương pháp nhánh cận và ứng dụng

i ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC KHOA HỌC --------------------------------------- ĐÀO MINH BẰNG MỘT PHƢƠNG PHÁP XẤP XỈ NGOÀI GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH THEO PHƢƠNG PHÁP NHÁNH CẬN VÀ ỨNG DỤNG Chuyên ngành: Toán ứng dụng Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
ii MỤC LỤC MỤC LỤC .......................................................................................................i Mở đầu ........................................................................................................... iv Chương 1. BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH VÀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH DẠNG CHUẨN.................................. 1 1.1. Một số mô hình thực tế thuộc dạng bài toán quy hoạch nguyên tuyến tính dạng chuẩn ............................................................................................................................. 1 1.1.1. Bài toán pha cắt vật liệu .................................................................................... 1 1.1.2. Bài toán lập kế hoạch sản xuất .......................................................................... 2 1.1.3. Bài toán cái túi .................................................................................................. 2 1.1.4. Mô hình phân bố máy bay cực tiểu tổng chi phí trên toàn mạng đường bay hàng không ......................................................................................................................... 3 1.1.5. Bài toán mua (thuê) máy bay tối ưu: .................................................................. 6 1.2. Bài toán quy hoạch nguyên tuyến tính dạng chuẩn và phương pháp giải........................... 7 1.2.1. Bài toán quy hoạch nguyên tuyến tính ............................................................... 7 1.2.2. Thuật toán Land-Doig giải bài toán quy hoạch nguyên tuyến tính ..................... 9 1.3. 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 .................................................................................................................................... 15 1.3.1. Phương pháp nón xoay xấp xỉ ngoài tuyến tính ............................................... 16 Thuật toán xấp xỉ ngoài LP ....................................................................................... 16 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 xấp xỉ ngoài tuyến tính ........................................................................................................ 18 1.3.3. Bài toán quy hoạch tuyến tính tái tối ưu hóa và thuật toán TTH....................... 22 Chương 2. THUẬT TOÁN NHÁNH CẬN XẤP XỈ NGOÀI GIẢI BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH VÀ ỨNG DỤNG ............. 28 2.1. Thuật toán nhánh cận xấp xỉ ngoài giải bài toán quy hoạch nguyên tuyến tính ...... 28 2.2. Minh họa ứng dụng thuật toán nhánh cận xấp xỉ ngoài ILP giải bài toán quy hoạch nguyên tuyến tính có số chiều nhỏ với miền ràng buộc là hệ bất phương trình tuyến tính .................................................................................................................................... 31 KẾT LUẬN ................................................................................................... 52 TÀI LIỆU THAM KHẢO ............................................................................. 54 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
iii Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
iv Mở đầu Như chúng ta đã biết, nhiều bài toán thực tế dẫn đến chúng ta phải đi giải các bài toán quy hoạch nguyên tuyến tính, và một trong những phương pháp hiệu quả để giải nó đó là phương pháp nhánh cận Land - Doig. Mỗi bước trung gian để giải bài toán quy hoạch nguyên tuyến tính thông thường là chúng ta phải tiến hành giải các bài toán quy hoạch tuyến tính tương ứng khi chưa có điều kiện nguyên của biến với các ràng buộc bổ sung dạng bất phương trình cho các thành phần của biến. Do đó việ c sử dụng các thuật toán 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 là khá ưu việt và hiệu quả, một trong những thuật toán như vậy là thuật toán nón xoay tuyến tính xấp xỉ ngoài trình bày trong [4]. Nội dung chính của luận văn được trình bày trong hai chương: Chương 1, trình bày một số mô hình bài toán thực tế có dạng bài toán quy hoạch nguyên tuyến tính, phương pháp nhánh cận Land-Doig và thuật toán nón xoay xấp xỉ ngoài tái tối ưu hóa TTH giải bài toán quy hoạch tuyến tính dạng chuẩn. Chương 2, trình bày việc xây dựng thuật toán xấp xỉ ngoài ILP giải bài toán quy hoạch nguyên tuyến tính từ thuật toán nhánh cận Land-Doig và thuật toán nón xoay xấp xỉ ngoài TTH. Thuật toán đã dựa trên một định lý làm cho trong mỗi bước để tìm các cận dưới đúng của bài toán nguyên, chúng ta chỉ phải đi giải các bài toán quy hoạch tuyến tính tương ứng khi chưa có điều kiện nguyên có số chiều là n - 1 (n là số chiều của bài toán). Tiếp đó minh họa ứng dụng thuật toán trình bày giải cho một số ví dụ đã có trong một số tài liệu [2], [3] và [5] để so sánh tính thuận lợi của thuật toán khi trường hợp bài toán có sô chiều hay số ràng buộc chính là nhỏ. Và trong trường hợp bài toán quy hoạch nguyên tuyến tính dạng chuẩn 2 chiều thì việc giải các bài toán quy hoạch tuyến tính tương ứng khi chưa có điều kiện nguyên, trong mỗi bước để Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
v tìm các cận dưới đúng của bài toán chỉ còn là việc kiểm tra tìm giá trị nhỏ nhất của hàm một biến tại hai đầu mút (nếu có). Các thuật toán 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, Basis, Java, ... Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
1 Chƣơng 1 BÀI TOÁN QUY HOẠCH NGUYÊN TUYẾN TÍNH VÀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH DẠNG CHUẨN Trong chương này chúng ta sẽ trình bày một số bài toán thực tế điển hình thuộc dạng bài toán quy hoạch nguyên tuyến tính, giới thiệu một số phương pháp quan trọng thường dùng để giải bài toán quy hoạch nguyên tuyến tính. Và trong quá trình các bước giải bài toán này cần phải giải các bài toán quy hoạch tuyến tính dạng chuẩn trung gian khi thêm vào các siêu phẳng cắt hoặc thêm vào các ràng buộc dạng bất phương trình tuyến tính để chia nhỏ miền chấp nhận sau mỗi bước. Chính vì thế, trong phần cuối của chương này sẽ trình bày một thuật toán xấp xỉ ngoài 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 và thuật toán này khá hiệu quả trong trường hợp tái tối ưu hóa. 1.1. Một số mô hình thực tế thuộc dạng bài toán quy hoạch nguyên tuyến tính dạng chuẩn 1.1.1. Bài toán pha cắt vật liệu Một phân xưởng có những thanh vật liệu (thanh thép, ống nhựa, ….) có độ dài cho trước, chúng ta cần cắt chúng thành những đoạn ngắn theo các mẫu cho trước. Vấn đề đặt ra là ta nên cắt như thế nào cho tổng những phần dư còn thừa lại là tốn ít nhất? Giả sử aij là độ dài đoạn loại i theo mẫu j, bi là số đoạn loại i cần có, cj là rẻo thừa khi cắt theo mẫu j, gọi xj là số thanh cắt theo mẫu j (j= 1,2, …, n). Ta có bài toán quy hoạch nguyên tuyến tính sau: n c j 1 j x j  min Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
2 với các điều kiện n a x j 1 j j  bi , i  1,...,m x j  0 và nguyên, j  1,...,n Đây là một bài toán quy hoạch tuyến tính chính tắc nguyên. 1.1.2. 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 dạng chuẩn sau: n c x j 1 j j  max với các điều kiện n a x j 1 j j  bi , i  1,...,m xj  0 , j  1,...,n Đây là một bài toán quy hoạch tuyến tính dạng chuẩn nguyên. 1.1.3. 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. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
3 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  c j x j  max j 1 n  a jx j  b j 1 x j  0, j  1,...,n x j - nguyên, j  1,...,n Đây là một bài toán quy hoạch tuyến tính dạng chuẩn nguyên. 1.1.4. Mô hình phân bố máy bay cực tiểu tổng chi phí trên toàn mạng đường bay hàng không 1. Các tham số và biến quyết định của bài toán: Giả sử chúng ta đang khai thác sử dụng K loại máy bay (777, 767, A321, A330, A320, AT7,...), M k là số máy bay loại k đang khai thác sử dụng (k=1,2,...,K), giả sử số sân bay (thành phố) tham gia vào mạng là N. Ta sử dụng các ký hiệu sau đây: (i, j) là chặng bay từ sân bay i đến sân bay j (i, j=1,2...,N). Ta giả thiết chiều dài trung bình thực tế Dij và chiều dài thương mại của mỗi chặng bay là bằng nhau. Pij là số lượng khách trung bình dự báo có thu nhập thực tế chuyên chở được trên chặng bay (i, j) (trong mỗi tuần). Sk là số ghế tương ứng (số ghế tối đa được phép xếp khách cho từng chặng bay của loại máy bay k) Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
4 gij là ghế suất (hệ số sử dụng ghế suất) trung bình trên chặng bay (i, j) hmax - số giờ khai thác bay trung bình lớn nhất cho phép của một chiếc k máy bay loại k trong một tuần. v - là vận tốc bình quân thực tế của máy bay loại k. k min(ij ) max(ij ) tương ứng là tần xuất bay ít nhất và nhiều nhất (số F , F k k chuyến bay trong một tuần) của loại máy bay k trên chặng bay (i, j). Cijk là chi phí theo chuyến bay (trong một tuần) trên chặng bay (i, j) của loại máy bay k. fijk là tần suất bay (số chuyến bay trong một tuần) của loại máy bay k trên chặng bay (i, j) (biến quyết định). 2. Hàm mục tiêu: Ta ký hiệu Cost là tổng chi phí theo chuyến bay cho tất cả máy bay đang khai thác sử dụng trong thời kỳ phân tích (một tuần) trên các tuyến bay toàn mạng. Thời kỳ phân tích là khoảng thời gian cần nghiên cứu cần phân tích mà ta có thể quy định là một tuần, một tháng, một quý, sáu tháng, một năm,.... Hàm mục tiêu Cost là tổng chi phí cho chuyến bay trên toàn mạng được xác định như sau: k fk Cost  C    C ij 0 ij k ij (I.1) Trong đó C 0 (chi phí cố định) là tổng chi phí không phát sinh thêm khi chuyến bay được thực hiện như: giá thuê máy bay, bảo hiểm máy bay, bảo dưỡng sửa chữa máy bay, khấu hao thiết bị máy bay, quản lí chung...C ijk là Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
5 chi phí biến đổi theo chuyến bay của loại máy bay k xuất hiện khi thực hiện chuyến bay như: phục vụ hàng khách, giờ bay, hàng hóa, nhiên liệu... 3. Các ràng buộc của bài toán: Ràng buộc về thương mại: min(ij ) max(ij ) 0 F  fijk  F (I.2) k k Ràng buộc này có nghĩa là tần suất bay fijk của loại máy bay k trên chặng bay (i, j) không ít hơn Fkmin(ij) và không nhiều hơn Fkmax(ij ) (ràng buộc về hạn chế thương mại). Ràng buộc về khai thác: Với mỗi vòng bay j (Pairing) ta có: k  f ji =  fijk (I.3) i i (j = 1,2,...N, k = 1,2,...,K) Ràng buộc (I.3) có nghĩa là trong khoảng thời gian phân tích (của một chu kỳ bay) thì các đội bay của loại máy bay k rời sân bay căn cứ j (Crew Base) bay đến sân bay i thì sẽ bay về sân bay j trong vòng bay.  Tijk . fijk  M k .hkmax (i , j ) (I.4) D ij Trong đó Tijk  là thời gian bay trên chặng bay (i, j) của loại máy bay k. v k Ràng buộc (I.4) có nghĩa là số giờ khai thác bay trung bình của một chiếc máy bay loại k không vượt quá số giờ bay cho phép. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
6 Pij gij  1 (i, j = 1,2,...,N) (I.5) K k  S .f k 1 k ij Ràng buộc (I.5) có nghĩa là hệ số sử dụng ghế (ghế suất) thực tế trên chặng bay (i, j) của loại máy bay k phải đạt ít nhất bằng g ij và không vượt quá 100%. Bài toán đặt ra là cựu tiểu hàm mục tiêu (I.1) với ràng buộc thỏa mãn (I.2), (I.3), (I.4) và (I.5). Vậy mô hình bài toán “Phân bố máy bay” cực tiểu tổng chi phí cho chuyến bay như sau: Cost  C0   Cijk f ijk  min (I.6) ij k Với các ràng buộc: min(ij ) max(ij ) 0 F  fijk  F k k  f jik i =  fijk i (j = 1,2,...N, k = 1,2,...,K) k k max  Tij fij  M k .hk (i, j ) Pij gij  1 (i, j=1,2,...,N) K k  S .f k 1 k ij Đây là một bài toán quy hoạch tuyến tính dạng chuẩn nguyên. 1.1.5. 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 (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 dự định mua (thuê) tối đa là N máy bay trong Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
7 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 (thuê) 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 (thuê), khi đó mô hình bài toán đặt ra là: K M   Tk .xk  max (I.7) k 1 Với các ràng buộc: K x k 1 k N K  c .x k 1 k k V xk  0, k  1, 2,..., K , nguyên Đây là một bài toán quy hoạch tuyến tính dạng chuẩn nguyên. 1.2. Bài toán quy hoạch nguyên tuyến tính dạng chuẩn và phƣơng pháp giải Trong mục này, chúng ta giới thiệu về bài toán quy hoạch nguyên tuyến tính dạng chuẩn và phương pháp nhánh cận Land-Doig để giải nó. Nội dung của mục này dựa chủ yếu vào các tài liệu [2], [3], [4] và [5]. 1.2.1. Bài toán quy hoạch nguyên tuyến tính Quy hoạch nguyên tuyến tính (Interger linener Programming, viết tắt ILP), là bài toán tìm cực tiểu (hay cực đại) của một hàm tuyến tính trên một tập hợp điểm rời rạc, thường là tập điểm nguyên: ( ILP) min  f ( x)  c x : Ax  b, x j  0 nguyên, j 1,..., n T trong đó A  R , b  R và c  R cho trước. m.n m n Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
8 Khi có một số, không phải tất cả các biến là nguyên thì ta gọi đó là bài toán qui hoạch nguyên bộ phận. Khi có điều kiện tất cả các biến đều nguyên thì ta gọi đó là bài toán quy hoạch nguyên hoàn toàn. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
9 Cũng như trong quy hoạch tuyến tính, f được gọi là hàm mục tiêu, tập D   x  Rn : Ax  b, x j  0 nguyên, j 1,..., n  gọi là miền ràng buộc hay miền chấp nhận được. Điểm x D gọi là một nghiệm chấp nhận được hay một phương án của bài toán. Một phương án đạt cực tiểu (hay cực đại) của hàm mục tiêu gọi là nghiệm tối ưu hay một phương án tối ưu. Nghiên cứu cấu trúc tập ràng buộc D và xây dựng các thuật toán tìm nghiệm tối ưu của bài toán ILP là đối tượng của quy hoạch nguyên tuyến tính. 1.2.2. Thuật toán Land-Doig giải bài toán quy hoạch nguyên tuyến tính Chúng ta đã biết khi giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình thì nhiều bài toán như bài toán vận tải sẽ cho chúng ta lời giải nguyên. Song cũng có nhiều bài toán cho chúng ta lời giải chưa phải là nguyên, chính vì thế mà một số phương pháp giải bài toán quy hoạch nguyên đã ra đời. Năm 1954, Dantzig, Fulkerson và Johnson đã đưa ra ý tưởng về phương pháp siêu phẳng cắt để giải bài toán quy hoạch nguyên. Ý tưởng chính của phương pháp này là mỗi bước lặp sẽ dùng siêu phẳng cắt để thu nhỏ miền chấp nhận được ở bước trước sao cho nghiệm tối ưu chưa nguyên ở bước này phải bị cắt đi và mọi phương án nguyên chấp nhận được không bị cắt đi. Năm 1958, Ralph Gomory đã xây dựng thuật toán đảm bảo hữu hạn bước nhận được lời giải tối ưu nguyên. Đến năm 1960, Land-Doig đã đưa ra thuật toán nhánh cận giải bài toán quy hoạch nguyên hiệu quả hơn nhiều so với phương pháp siêu phẳng cắt của Gomory. Sau đây chúng ta sẽ trình bày thuật toán Land-Doig là một trong những thuật toán của phương pháp nhánh cận. Sơ đồ tổng quát của phương pháp nhánh cận chúng ta có thể tìm thấy ở các tài liệu [2], [3] và [5]. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
10 Thuật toán Land-Doig giải bài toán quy hoạch nguyên tuyến tính Xét bài toán quy hoạch nguyên tuyến tính sau đây:  n   c j x j  min  j 1   n   aij x j  b j , (i  1,..., m)  j 1 (1.8)  x j  0, ( j  1,..., n)   x j  nguyên( j  1,..., n)  Ký hiệu: x  ( x1,.. , xn )T , c  (c1,.. , cn )T , b  (b1,.. , bn )T , A  (aij ) (với T là ký hiệu chuyển vị vectơ hay ma trận). Khi đó bài toán trên được viết lại dưới dạng ma trận như sau: cT x  min   Ax  b (1.9)  x  0, nguyên  Để áp dụng phương pháp nhánh cận, ta phải xác định hai thủ tục chính đó là phân nhánh và tính cận. Ta xét cách xây dựng hai thủ tục này của Land-Doig. Đặt D  x: Ax  b, x  0, nguyên Ta có miền D là miền chấp nhận được của bài toán (1.9). Ta sẽ ký hiệu P0 là bài toán (1.9). Giải bài toán quy hoạch tuyến tính tương ứng với P0 ta sẽ thu được 0 0 phương án tối ưu x , x nói chung không nguyên. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
11 Ta có: f ( x0 )  min  f ( x): Ax  b, x  0   min{ f ( x) : Ax  b, x  0, nguyên }  f* Vì thế giá trị f ( x 0 ) có thể dùng làm cận dưới cho giá trị tối ưu f * của bài toán P0 . Như vậy ta đã có thủ tục để tính cận dưới: đặt giá trị cận dưới của bài toán quy hoạch nguyên tuyến tính bằng giá trị tối ưu của bài toán quy hoạch tuyến tính tương ứng với nó:  ( D)  min{ f ( x) : Ax  b, x  0 } . Ta phân chia tập chấp nhận được của bài toán P0 thành hai tập bằng cách đưa vào hai ràng buộc loại trừ lẫn nhau như sau: Giả sử xi (1 i  n ) là một thành phần không nguyên nào đó của x . 0 0 Ký hiệu: D1  { x  D : xi  [ xi0 ] } (1.10) D2  { x  D : xi  [ xi0 ]  1} (1.11) 0 0 Trong đó [ xi ] là phần nguyên của xi . Khi đó D  D1  D2 , D1  D2   . (1.12) Như vậy, ta đã xác định được thủ tục phân hoạch theo các công thức (1.10)-(1.12). Gọi P1 là bài toán: min { f ( x) : x  D1 } . Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
12 Gọi P2 là bài toán: min { f ( x) : x  D2 } . Rõ ràng đây là các bài toán quy hoạch nguyên tuyến tính. Khi giải bài toán quy hoạch tuyến tính tương ứng với bài toán Pi (i  1, 2) , để tính cận dưới cho các tập Di , ta có thể gặp một số các tình huống sau đây: 1) Bài toán không có phương án chấp nhận được. i 2) Tìm được phương án tối ưu x nguyên. i 3) Tìm được phương án tối ưu x không nguyên. Trường hợp 1): Bài toán Pi cũng không có phương án chấp nhận được, tức là Di   . Khi đó, ta có thể loại bỏ tập Di khỏi qua trình xét tiếp theo. i i Trường hợp 2): x cũng là phương án của bài toán Pi . Vì vậy x là phương án chấp nhận được của bài toán xuất phát. Trong trường hợp này, ta có thể cải thiện được kỷ lục, còn tập Di cũng sẽ bị loại không cần xét tiếp. Trường hợp 3): Ta thu được cận dưới của tập Di là  ( Di )  f ( x i ) . Tập Di cần xem xét tiếp: Ta có thể mô tả thuật toán Land-Doig để giải bài toán quy hoạch nguyên tuyến tính (1.9) như sau: Thuật toán Land-Doig Bước chuẩn bị: Giải bài toán quy hoạch tuyến tính tương ứng với P0 0 0 và thu được phương án tối ưu x . Giả sử x là không nguyên. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
13 Đặt cận dưới của P0 là f ( x 0 ) và danh mục các bài toán cần xét là P  P0 . Nếu biết x là phương án chấp nhận được của bài toán thì đặt f  f (x ) và ngược lại, ta đặt f  ∞. Bước lặp k = 1, 2, . . . 1) Nếu P   thuật toán kết thúc. Khi đó, nếu f   thì f là giá trị tối ưu và x là phương án tối ưu của bài toán. Trong trường hợp ngược lại, bài toán không có phương án chấp nhận được. 2) Nếu P   : Chọn Pk là bài toán có cận dưới nhỏ nhất trong P . k Gọi Dk là miền chấp nhận được, x là phương án tối ưu của bài toán quy hoạch tuyến tính tương ứng với nó. k k 2.1. Giả sử xt là một thành phần không nguyên nào đó của x . Phân hoạch tập Dk thành hai tập: Dk1  { x Dk : xt [ xtk ]}, Dk2  { x Dk : xt [ xtk ] 1}. Gọi Pk1 là bài toán min { f ( x) : x  Dk1 } . Gọi Pk 2 là bài toán min { f ( x) : x  Dk2 } . Đây là các bài toán quy hoạch nguyên tuyến tính. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
14 2.2. Lần lượt giải các bài toán quy hoạch tuyến tính tương ứng với Pki (i 1, 2) để tính cận dưới đúng cho bài toán Pki . Khi đó, ta có thể gặp một trong các tình huống sau đây: a) Phát hiện bài toán không có phương án chấp nhận được. ki b) Tìm được phương án tối ưu x là nguyên. ki c) Tìm được phương án tối ưu x là không nguyên. Trường hợp a): Bài toán Pki cũng không có phương án chấp nhận được, vì vậy ta loại bỏ việc xem xét tiếp theo. Trường hợp b): Tính lại các kỷ lục theo công thức: f :  min{ f , f ( x ki ) } Gọi x là kỷ lục tương ứng với giá trị này. Bài toán Pki đã xét xong. k Trường hợp c): Đặt cận dưới của Pki là f ( x i ) , và kết nạp nó vào danh sách các bài toán cần xét: P : P  { Pki } 2.3. Loại bỏ khỏi P tất cả các bài toán có cận dưới lớn hơn hoặc bằng giá trị kỷ lục. Đặt: P : P \ { Pki } và chuyển sang bước k + 1. Như vậy chúng ta đã trình bày xong thuật toán nhánh cận Land-Doig giải bài toán quy hoạch nguyên tuyến tính dạng chuẩn. Chúng ta thấy khi giải bài toán quy hoạch nguyên tuyến tính theo thuật toán trên thì các tính toán ở giai đoạn 2.2. để giải các bài toán quy hoạch tuyến tính tương ứng tính cận dưới là khâu quan trọng cần thiết. Rõ ràng sau mỗi bước mỗi bài toán quy hoạch tuyến tính tương ứng cần giải lại thêm một ràng buộc bất phương trình. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn
15 Chính vì vậy khi giải các bài toán này chúng ta nên lựa chọn các thuật toán giải trực tiếp được cho bài toán quy hoạch tuyến tính dạng chuẩn (miền ràng buộc là hệ bất phương trình tuyến tính) nhất là những thuật toán mà có ưu điểm thuận lợi trong trường hợp bài toán là tái tối ưu hóa (sau một bước lại giải lại bài toán khi chỉ bổ sung thêm 1 ràng buộc). Một thuật toán 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 và có ưu điểm khi bài toán là tái tối ưu hóa là thuật toán nón xoay trong [4]. Sau đây chúng tôi sẽ trình bày thuật toán nón xoay và trong trường hợp bài toán cần giải là bài toán tái tối ưu hóa (tức là giải lại bài toán mới khi bổ sung thêm một ràng buộc bất phương trình vào miền ràng buộc của bài toán trước đã biết lời giải của nó). Chứng minh định lý khẳng định bài toán tái tối ưu hóa nếu có lời giải thì sẽ có ít nhất một lời giải thỏa mãn chặt ràng buộc bổ sung. Và nhờ tính chất này mà khi giải các bài toán quy hoạch tuyến tính tương ứng trong bước 2.2. của thuật toán Land- Doig trình bày trên chung ta chỉ phải giải các bải toán quy hoạch tuyến tính với số chiều (số biến nguyên) là n-1 (n là số chiều của bài toán). 1.3. 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 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 trình tuyến tính sau:  n  f ( x)  C , x   ci .xi  min ( L)  i 1  x  P :  x  R :  Ai , x  b  0, i  1,2,..., m n  L i xRn, Ai là véc tơ dòng và AiRn, m n, Ai(ai1, ai2, ..., ain) ≠ O(0,…,0) , Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.ltc.tnu.edu.vn