Tài liệu Phương pháp điểm trong giải bài toán quy hoạch tuyến tính

Trần Hải Yến – K32 CN Toán MỤC LỤC Lời cảm ơn Lời cam đoan Mở đầu Chƣơng I Bài toán quy hoạch tuyến tính và phƣơng pháp đơn hình 1.1 Bài toán quy hoạch tuyến tính và quy hoạch tuyến tính đối ngẫu 1.2. Tập lồi và các điểm cực biên 1.3 Phương pháp đơn hình 1.4. Thời gian thực hiện thuật toán Chƣơng II Phƣơng pháp điểm trong 2.1 Tƣ tƣởng của phƣơng pháp điểm trong 2.1.1 Nội dung của ý tưởng 2.1.2 Xác đinh hướng giảm 2.1.3 Thành phần hướng tâm 2.2 Một số thuật toán của phƣơng pháp điểm trong 2.2.1 Phương pháp tỷ lệ affin 2.2.2 Thuật toán giảm thế 2.2.3 Thuật toán theo đường trung tâm 2.2.4 Thuật toán theo đường trung tâm – đối ngẫu 2.2.5 So sánh các phương pháp điểm trong Kết luận Tài liệu tham khảo Khóa luận tốt nghiệp 1 Trần Hải Yến – K32 CN Toán LỜI CẢM ƠN Trong suốt quá trình thực hiện khóa luận cũng như học tập tại trường em đã nhận được sự quan tâm, giúp đỡ và tạo điều kiện của các thầy cô giáo trong Khoa Toán, nhất là các thầy cô giáo trong tổ Toán ứng dụng, cùng với sự động viên khích lệ của các bạn sinh viên. Em xin chân thành cảm ơn sự giúp đỡ quý báu này. Đặc biệt em xin bày tỏ lòng biết ơn sâu sắc đến thầy giáo Trần Minh Tước, người đã tận tình hướng dẫn, giúp đỡ em trong suốt thời gian qua để em có thể hoàn thành khóa luận này. Trong quá trình thực hiện đề tài, do điều kiện về thời gian và sự hạn chế về kiến thức, khó tránh khỏi những thiếu sót khi hoàn thành khóa luận này. Vì vậy em rất mong nhận được những ý kiến đóng góp của thầy cô và bạn bè để đề tài của em được hoàn thiện hơn . Em xin chân thành cảm ơn! Hà Nội, ngày 05 tháng 05 tháng 2010 Sinh viên thực hiện Trần Hải Yến Khóa luận tốt nghiệp 2 Trần Hải Yến – K32 CN Toán LỜI CAM ĐOAN Tôi xin cam đoan những vấn đề em trình bày trong khóa luận là những kết quả nghiên cứu của riêng bản thân tôi dưới sự hướng dẫn tận tình của thầy giáo Trần Minh Tước, bản khóa luận này không trùng với kết quả nghiên cứu của các tác giả khác. Nếu không tôi xin hoàn toàn chịu trách nhiệm. Hà Nội, ngày 05 tháng 05 năm 2010 Sinh viên thực hiện Trần Hải Yến Khóa luận tốt nghiệp 3 Trần Hải Yến – K32 CN Toán MỞ ĐẦU 1. Lý do chọn đề tài Bài toán quy hoạch tuyến tính là bài toán giải quyết những vấn đề khó khăn thường gặp trong cuộc sống và trong lao động sản xuất. Việc giải những bài toán Quy hoạch tuyến tính này giúp ta tìm được phương án tối ưu nhất, hợp lý nhất nhằm mang lại hiệu quả cao nhất trong sản xuất. Thông thường chúng ta dùng phương pháp đơn hình để giải bài toán Quy hoạch tuyến tính. Đây là một cách giải nhanh và hiệu quả. Tuy nhiên với những bài toán có độ phức tạp lớn thì phương pháp đơn hình không còn thực sự hiệu quả nữa. Với những bài toán này người ta thường sử dụng một phương pháp khác là phương pháp điểm trong. Để tìm hiểu kỹ hơn về phương pháp điểm trong tôi đã chọn đề tài: “Phương pháp điểm trong giải bài toán quy hoạch tuyến tính” . cho khóa luận tốt nghiệp. 2. Mục đích, nhiệm vụ nghiên cứu Mục đích nghiên cứu: Tìm hiểu các thuật toán của phương pháp điểm trong để giải bài toán Quy hoạch tuyến tính. Nhiệm vụ nghiên cứu: Trình bày khái quát và đánh giá hiệu quả các thuật toán của phương pháp điểm trong. 3. Phƣơng pháp nghiên cứu Trong đề tài sử dụng những phương pháp chính như: phương pháp tìm kiếm, phân tích, thống kê, tổng hợp, so sánh,…. 4. Bố cục khóa luận Khóa luận gồm mở đầu, hai chương và kết luận Chương I: Bài toán quy hoạch tuyến tính và phương pháp đơn hình Chương II: Phương pháp điểm trong Khóa luận tốt nghiệp 4 Trần Hải Yến – K32 CN Toán Chƣơng I BÀI TOÁN QUY HOẠCH TUYẾN TÍNH VÀ PHƢƠNG PHÁP ĐƠN HÌNH 1.1 Bài toán quy hoạch tuyến tính và quy hoạch tuyến tính đối ngẫu 1.1.1 Bài toán quy hoạch tuyến tính a) Dạng tổng quát Tìm véc tơ x   x1 , x2 ,..., xn    n sao cho t n f(x) = c x j 1 j j  min(max) với các điều kiện:  n  aij x j  b j  j 1  n  aij x j  b j  j 1  D: n aij x j  b j  j 1   xj  0  x 0 j   xj (i  1,..., m) (i  m1  1,..., m2 ) (i  m2  1,..., m) ( j  1,..., n1 ) ( j  n1  1,..., n2 ) ( j  n2  1,..., n) b) Dạng chính tắc n   f ( x)   c j x j  min j 1   n (i  1, 2,..., m)  aij x j  b j  j 1 x j  0 ( j  1, 2,..., n)   Hay dưới dạng ma trận Khóa luận tốt nghiệp 5 Trần Hải Yến – K32 CN Toán  f  x   c t x  min   Ax  b x  0  Trong đó c, x   n , b   m , A là ma trận cấp m  n . c) Dạng chuẩn tắc n   f ( x)   cij x j  min j 1  n  aij x j  b j   (i  1,2,..., m) j 1   xj  0 ( j  1,2,..., n)   Hay dưới dạng ma trận  f  x   c t x  min   Ax  b x  0  1.1.2 Bài toán quy hoạch tuyến tính đối ngẫu a) Đối ngẫu của bài toán quy hoạch tuyến tính dạng chuẩn tắc bt x  max  t A x  c y  0  b) Đối ngẫu của bài toán quy hoạch tuyến tính dạng chính tắc bt y  max  t A y  c y  có dấu tùy ý c) Đối ngẫu của bài toán quy hoạch tuyến tính dạng tổng quát Khóa luận tốt nghiệp 6 Trần Hải Yến – K32 CN Toán bt y  min m    a  y  c ij i j  i 1  n    aij  yi  c j  i 1  yi  0   yi tự do   j  1, n  1  j  n  1, n  i  1, m  i  m  1, m  1 1 1 1.2 Tập lồi và các điểm cực biên. a) Tập C   n gọi là tập lồi nếu lấy 2 điểm bất kỳ x’ và x”  C thì đoạn thẳng [x’,x”] nối 2 điểm này hoàn toàn thuộc C. b) Điểm x0 thuộc tập lồi C được gọi là điểm cực biên của C nếu nó không là điểm trong của bất kỳ đoạn nào nối 2 điểm khác nhau của C tức là không tồn tại x’, x” C, x’ ≠ x” sao cho x0= x’+ (1- )x” với  nào đó thuộc (0,1). c) Một tổ hợp lồi của các điểm xi   n (i  1,2,...m) là điểm x   n có dạng: x  1x1   2 x2  ....   n xn trong đó  i  0(i  1, m), m  i 1 i  1. 1.3 Phƣơng pháp đơn hình 1.3.1 Tƣ tƣởng của phƣơng pháp đơn hình Xét bài toán quy hoạch tuyến tính dạng chính tắc:  f  x   c t x  min   Ax  b x  0  Với x, c   n , b   m , A là ma trận cấp m  n . Giả thiết rằng hạng A  m (m là số rằng buộc của bài toán). Khóa luận tốt nghiệp 7 Trần Hải Yến – K32 CN Toán Đã biết rằng: - Nếu bài toán có phương án thì có phương án cực biên. - Nếu bài toán có phương án tối ưu thì cũng có phương án cực biên tối ưu - Số phương án cực biên là hữu hạn. Do đó ta có thể tìm một phương án tối ưu hay lời giải của bài toán trong tập hợp các phương án cực biên. Do tập này là hữu hạn nên Dantzig đã đề xuất một thuật toán gọi là thuật toán đơn hình: Xuất phát từ một phương án cực biên x 0 . Sau đó kiểm tra xem x 0 có phải là phương án tối ưu hay không. Nếu x 0 chưa phải là phương án tối ưu thì tìm cách cải tiến nó để được một phương án cực biên khác là x 0 tốt hơn x 0 theo nghĩa f  x1   f  x0  . Quá trình này lặp lại nhiều lần. vì số phương án cực biên là hữu hạn nên sau một số hữu hạn bước lặp ta tìm được phương án cực biên tối ưu. Để thực hiện thuật toán đề ra ở trên ta cần làm rõ hai vấn đề: - Làm thế nào để biết một phương án cực biên đã cho là tối ưu hay chưa? Tức là đi tìm dấu hiệu tối ưu. - Làm thế nào để một phương án cực biên chưa tối ưu tìm được một phương án cực biên mới tốt hơn nó? 1.3.2 Dạng ma trận của thủ tục đơn hình Xét bài toán quy hoạch tuyến tính dạng chính tắc  f  x   c t x  min   Ax  b x  0  Khóa luận tốt nghiệp 8 Trần Hải Yến – K32 CN Toán Với x, c   n , b   m , A là ma trận cấp m  n . Để đơn giản ta giả thiết cơ sở J đang xét gồm đúng m cột đầu tiên của ma trận A, tức J={1,2,....,m}. Đặt K={1,2,....,n}\J. Ma trận A được tách làm 2 : ma trận cơ sở AJ và phần ngoài cơ sở AK. các véc tơ cũng được tách làm 2 phần tương ứng trong và ngoài cơ sở J. x  c  A   AJ AK  x   J  , c   J  .  xK   cK  Ta có thủ tục đơn hình dưới dạng ma trận như sau: Bước 1: Tính phương án cực biên tương ứng cơ sở J theo công thức: X j  AJ1b . Tính véc tơ ước lượng  k   AJ 1 AK  cJ  cK . t Bước 2: Kiểm tra dấu của các thành phần  k của véc tơ  K :  Nếu tất cả các thành phần của véc tơ ước lượng  K đều  0 thì kết luận phương án đang xét là phương án tối ưu.  Nếu có thành phần  k của véc tơ  K dương thì chọn s thỏa mãn  s = max{  k >0, k  J } và chuyển sang bước 3. Bước 3: Tính cột z s theo các hệ số z js theo công thức: z s  AJ1a s Kiểm tra điều kiện: cột z s  0 tức là z js  0j  J . Nếu - Đúng: thì kết luận hàm mục tiêu giảm vô hạn trên miền ràng buộc. Kết thúc thuật toán. - Sai: chuyển sang bước 4. Bước 4:  Chọn chỉ số r thỏa mãn: Khóa luận tốt nghiệp 9 Trần Hải Yến – K32 CN Toán  x  xr  min  j , j  J , z js  0  zrs  z js   Lập cơ sở mới J j   J \ r   s . Bước 5: Tính ma trận nghịch đảo AJ11 và lặp lại từ bước 1. 1.4 Thời gian thực hiện thuật toán. 1.4.1 Định nghĩa Một thuật toán được gọi là tốt hơn nếu thời gian thực hiện để giải bài toán là ngắn hơn. Thời gian thực hiện thuật toán được đo bằng số các phép toán cần tiến hành để giải bài toán bằng thuật toán này. Tuy nhiên số phép toán lại phụ thuộc vào “kích thước” của bài toán, là một số n nguyên dương, chính là “số lượng” dữ liệu đầu vào. Do đó thời gian thực hiện thuật toán thường được biểu diễn dưới dạng T(n) là một hàm số dương của n, đồng biến theo n. Để tiện so sánh thời gian thực hiện của các thuật toán, người ta đưa ra ký hiệu O (đọc là O lớn). Giả sử f  n  là hàm số không âm. Ta viết T  n   O  f  n   nghĩa là tốc độ tăng của T  n  khi n tiến đến vô cùng không vượt quá tốc độ tăng của f  n  . Khi n lớn , f  n  cho ta hình dung được mức lớn của T  n  , f  n  là thước đo độ lớn của T  n  1.4.2 Thời gian thực hiện thuật toán đơn hình. Trong mỗi bước lặp của phương pháp đơn hình cần thực hiện O(m.n) phép toán số học để tính giá trị hàm mục tiêu, các biến cơ sở và O(m2) phép Khóa luận tốt nghiệp 10 Trần Hải Yến – K32 CN Toán toán để tính lại ma trận cơ sở. Tổng số phép toán số học trong một phép lặp đơn hình là O(m.n + m3). Nói chung, người ta thấy cần O(m) phép lặp đơn hình để giải bài toán quy hoạch tuyến tính. Về trung bình, thời gian giải bài toán quy hoạch tuyến tính bằng thuật toán đơn hình là một đa thức theo m và n. Khóa luận tốt nghiệp 11 Trần Hải Yến – K32 CN Toán Chƣơng II PHƢƠNG PHÁP ĐIỂM TRONG 2.1 Tƣ tƣởng của phƣơng pháp điểm trong 2.1.1 Nội dung của ý tƣởng Phương pháp đơn hình tìm lời giải bài toán quy hoạch tuyến tính bằng cách di chuyển qua các điểm cực biên, nằm trên biên của miền rằng buộc. Phương pháp điểm trong xuất phát từ một điểm nằm bên trong miền rằng buộc và di chuyển dần đến lời giải tối ưu nhưng vẫn luôn ở bên trong miền rằng buộc. Tên gọi của phương pháp này cũng đã cho thấy ý tưởng này. Từ một điểm đang xét ta di chuyển dần đến một điểm mới tốt hơn theo hướng d. Hướng di chuyển là tổ hợp của hai thành phần. Thành phần thứ nhất là hướng giảm hàm mục tiêu. Thành phần thứ hai nhằm hướng vào bên trong để không chạm vào biên của miền rằng buộc, gọi là thành phần hướng tâm. Như vậy để giải quyết bài toán quy hoạch tuyến tính bằng phương pháp này chúng ta phải tìm được 2 thành phần. Việc xác định 2 thành phần đó được trình bày dưới đây. 2.1.2 Xác định hƣớng giảm Xét miền rằng buộc của bài toán quy hoạch tuyến tính  Ax  b  x  0 Xuất phát từ điểm x0 nằm bên trong miền rằng buộc, ta di chuyển đến điểm mới x1= x0+  d . Để không vi phạm các rằng buộc phải có Ad = 0 và  đủ bé. Giả sử z là hướng giảm nhanh nhất hàm mục tiêu tại điểm đang xét. Chiếu gướng giảm này lên không gian con Ax = 0 ta được hướng giảm hàm mục tiêu mà không vi pham ràng buộc. Khóa luận tốt nghiệp 12 Trần Hải Yến – K32 CN Toán Giả thiết rằng rankA = m. Toán tử chiếu lên không gian con Ax là : P  I  At  AAt  A 1 vì z, A( Pz)  A( I  At ( AAt )1 A) z  ( A  AAt ( AAt )1 A) z  Az  Az  0 . Vậy hướng di chuyển là d = Pz. Trong trường hợp hàm mục tiêu là hàm tuyến tính f  x   ct x thì tại mọi điểm x hướng giảm nhanh nhất là hướng ngược gradient –c. Ta cần tính  Pc . Đặt   ( AAt )1 Ac hay nói cách khác  là nghiệm của hệ phương trình đại số tuyến tính: AAt  Ac . Ta có: Pc  ( I  At ( AAt )1 A)c  c  At ( AAt )1 Ac  c  At . Để tính Pc thay cho việc nghịch đảo ma trận ta giải hệ phương trình đại số tuyến tính AAt  Ac , sau đó tính theo công thức ở trên. 2.1.3 Thành phần hƣớng tâm Để dãy điểm đang xét nhằm hướng vào bên trong không chạm vào biên của miền rằng buộc ta có hai cách: Cách một (phương pháp hàm chắn): Ta cộng thêm vào hàm mục tiêu một hàm số dương, dần tới  mỗi khi dãy điểm gần tiến tới biên miền ràng buộc. Một hàm chắn hay dùng là là hàm logarit: n  ( x)   ln x j j 1 do các ràng buộc bất đẳng thức có dạng x  0 nên khi x  0 thì các hàm chắn trên dần tiến đến  . Cách hai (phương pháp căn chỉnh ellipsoid): Ta xây dựng một elip có tâm tại điểm đang xét và nội tiếp trong miền ràng buộc. Biên của miền ràng buộc xác định bằng các đẳng thức xj= 0, nên nếu một ràng buộc sắp vi phạm Khóa luận tốt nghiệp 13 Trần Hải Yến – K32 CN Toán tại điểm đang xét thì bán trục của elip tương ứng với biến này sẽ ngắn, hướng di chuyển sẽ được điều chỉnh để nghiêng về phía bán trục dài hơn của elip. Hướng di chuyển Khóa luận tốt nghiệp 14 Trần Hải Yến – K32 CN Toán 2.2 Một số thuật toán của phƣơng pháp điểm trong 2.2.1 Phƣơng pháp tỷ lệ affin 2.2.1.1 Ý tƣởng của thuật toán Tại mỗi bước lặp, khi đã có môt nghiệm trong, ta thay bài toán quy hoạch tuyến tính bằng bài toán có cùng hàm mục tiêu nhưng tập ràng buộc là một elip có tâm là nghiệm trong đã có, xấp xỉ với tập lồi đa diện ràng buộc của quy hoạch tuyến tính. Nghiệm của bài toán mới sẽ được chứng minh là nghiệm trong của bài toán của bài toán quy hoạch tuyến tính và sẽ được dùng làm tâm của elip ở bước lặp tiếp theo. Cứ tiếp tục quá trình này đến khi khoảng cách đối ngẫu nhỏ hơn một ngưỡng   0 nào đó. 2.2.1.2 Xây dựng thuật toán Ta có hình trên là quá trình chạy thuật toán tỷ lệ affin cho bài toán dưới đây Khóa luận tốt nghiệp 15 Trần Hải Yến – K32 CN Toán min  x1  x2  x  2 x  8 2  1 2 x1  x2  9 3x  x  6  1 2  x1 , x2  0 Bây giờ ta đi xét chi tiết từng bước của thuật toán. Xét bài toán quy hoạch tuyến tính chính tắc min ct x, Ax  b, x  0. (1.1) Trước tiên ta đi xây dựng elip với tâm là nghiệm trong x0 đã có: 2 n    xi  xi0  n 2 E  x   :     0 x i 1  i    (1.2) Bài toán elip xấp xỉ là bài toán nhận được từ bài toán quy hoạch tuyến tính (1.1) với nghiệm trong x 0 đã cho và thay các ràng buộc x  0 bằng ràng buộc elip (1.2). Ta có bài toán elip xấp xỉ: min ct x, Ax  b, (1.3) 2  xi  x  2     0 xi  i 1  0 i n 0 Đổi biến x  X x ' , X0 là ma trận đường chéo với các phần tử thứ I ở đường   0 0 0 chéo là X ii  xi , X  diag x1 ,..., xn . 0 0 Bài toán elip xấp xỉ trở thành bài toán cực tiểu hàm tuyến tính trên hình cầu: Khóa luận tốt nghiệp 16 Trần Hải Yến – K32 CN Toán min ct X 0 x ' AX 0 x '  b n   x ' 1 i 1 2 i (1.4)  2 n   2 0 0 Vì e là tâm hình cầu B   x '   n :   x 'i  1   2  , X e  x , và e i 1   thuộc đa tập tuyến tính H  x ': AX 0 x '  b cho nên e cũng là tâm của hình cầu với số chiều ít hơn số chiều của B  H và có cùng bán kính  . Ở bài (1.4) hình cầu ràng buộc nằm trong đa tạp tuyến tính H song song   với không gian con Ker( AX 0 ) : x '   n : AX 0 x '  0 do đó đóng vai trò hướng –c ở đây phải là hướng P( ct X 0 ), với P là phép chiếu  n lên Ker( AX 0 ). Áp dụng công thức nghiêm tối ưu của bài toán tìm cực tiểu hàm tuyến tính trên hình cầu ta có nghiệm tối ưu là : PX 0c x'  e   PX 0c  * (1.5) Để tính PX0c ta cần sử dụng bổ đề (1.1) sau đây: BỔ ĐỀ(1.1): Giả sử A là ma trận cấp m  n với rank A = m. Khi đó với n t t 1 mọi x   : P( x) : A ( AA ) Ax là hình chiếu của x lên không gian hàng R(At) và x - P(x) là hình chiếu của x lên không gian KerA. CHỨNG MINH: Theo định nghĩa của hình chiếu P lên R(At) ta phải tính P(x)= arg min ||x – Atu||. u n t Do đó ta phải tìm minn || x  A u || hoặc bài toán tương đương là u min( x  At u)t ( x  At u) , đây là bài toán cực tiểu hàm cấp hai: n u Khóa luận tốt nghiệp 17 Trần Hải Yến – K32 CN Toán min( xt x  2 xt At u  u t AAt u ) . n u Nghiệm của bài toán chính là điểm dừng u*= (AAt)-1Ax. Do đó ta có: P(x)=Atu*=At(AAt)-1Ax. Vì KerA là phần bù trực giao ( R( At )) nên x-P(x) là hình chiếu của x lên không gian nhân KerA. Vì P là ma trận chiếu lên không gian con Ker( AX 0 ) nên theo bổ đề trên ta có PX 0  ( I  X 0 At ( A( X 0 )2 At ) 1 AX 0 ) X 0c Vậy ta đã có nghiệm tối ưu của bài toán (1.4) biếu diễn qua A, c của bài toán quy hoạch và nghiệm trong x 0 đã biết. Ta dùng phép đổi biến x=X0x‟ vào (1.5) để được nghiệm tối ưu: X 0 PX 0c x  x  . || PX 0c || * 0 (1.6) Ta thấy nghiệm tối ưu x* của bài toán elip xấp xỉ là nghiệm chấp nhận được của bài toán quy hoạch tuyến tính. Hơn nữa nó đạt cực tiểu hàm mục tiêu c t x trong elip. Nhưng elip chỉ là một phần của tập lồi đa diện ràng buộc của bài toán quy hoạch tuyến tính nên x * chưa phải là nghiệm tối ưu của bài toán quy hoạch tuyến tính. Để x* là nghiệm tối ưu của bài toán quy hoạch tuyến tính thì x * phải rơi vào biên của tập lồi hay nói cách khác: “nếu x j  0 * với j nào đó thì x* cho bởi (1.6) là nghiêm tối ưu của bài toán quy hoạch tuyến tính”. Ta đi chứng minh khẳng định trên. Ta có bổ đề: Nếu x  E thì x>0 khi  <1 và x  0 khi  =1. Bổ đề được minh họa bằng hình học sau và chứng minh được bằng giả tích: Khóa luận tốt nghiệp 18 Trần Hải Yến – K32 CN Toán  2  1 Ta biến đổi PX 0c như sau: PX 0c  ( I  X 0 At ( A( X 0 )2 At )1 AX 0 ) X 0c  X 0 ( I  At ( A( X 0 ) 2 At ) 1 A( X 0 ) 2 )  X 0 (c  At y ) (1.7) X s 0 0 2 t 1 0 2 Với y  ( A( X ) A ) A( X ) c và s  c  At y Ta đang xét bài toán quy hoạch tuyến tính chính tắc và bài toán quy hoạch đối ngẫu của nó là: max y t b, yt A  c Ta sẽ chứng minh nếu j{0, . . . , n} để x*j  0 thì x* và (y,s) tương ứng là cặp nghiệm tối ưu của hai bài toán quy hoạch tuyến tính đối ngẫu nhau. Thay (1.6) vào (1.7) ta có ( X 0 )2 s x x  || X 0 s || * 0 Vì X0 là ma trận đường chéo nên ta có: 0x  x  * j Khóa luận tốt nghiệp 0 j ( x 0j )2 s j || X 0 s || 19 Trần Hải Yến – K32 CN Toán 0 0 Do đó x j s j  X s  > 0, suy ra sj > 0, mặt khác theo định nghĩa chuẩn || X 0 s|| thì phải có xi si  0i  j . Mà 0 xio  0 nên si  0i  j . Như vậy ( y, s ) thỏa mãn mọi ràng buộc của bài toán đối ngẫu. Đồng thời cặp x* và (y,s) thỏa mãn điều kiện độ lệch bù. Do đó chúng là cặp nghiệm tối ưu. 2.2.1.3 Mô tả thuật toán * Đầu vào của thuật toán: - Dữ liệu của bài toán A, b, c - Một nghiệm trong tức là nghiệm chấp nhận được gốc x0 > 0; - Cỡ nới lỏng tối ưu   0 ; - Tham số   (0,1]. * Thật toán Xuất phát từ x0. bước lặp điển hình xuất phát từ xk > 0 gồm các đoạn sau: 1. Tính nghiệm đối ngẫu ứng viên y k  ( A( X k ) 2 At ) 1 A( X k ) 2 c k k Với Xk = diag( x1 ,..., xn ) 2. Tính biến bù đối ngẫu ứng viên s k  c  At y k k 3. Kiểm tra điều kiện tối ưu: nếu s  0 và et X k s k   thì ngừng. Nghiệm hiện hành gốc x k là  - tối ưu và y k là ngiệm đối ngẫu  - tối ưu. k 2 k 4. Kiểm tra tính không giới nội: nếu ( X ) s  0 thì ngừng, mục tiêu tối ưu là  5. Tính nghiệm trong tiếp theo Khóa luận tốt nghiệp 20