Một phương pháp chọn điểm khởi đầu trong giải thuật điểm trong cho bài toán quy hoạch tuyến tính

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

Thêm vào BST

Báo xấu

9
lượt xem 2
download

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

Bài viết Một phương pháp chọn điểm khởi đầu trong giải thuật điểm trong cho bài toán quy hoạch tuyến tính đề xuất một phương pháp chọn điểm khởi đầu đảm bảo cho sự hội tụ của giải thuật điểm trong cho bài toán quy hoạch tuyến tính. Phương pháp này dựa trên giải thuật Ellipsoid cải tiến tìm nghiệm của một bất đẳng tuyến tính.

Chủ đề:

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

Lưu

Nội dung Text: Một phương pháp chọn điểm khởi đầu trong giải thuật điểm trong cho bài toán quy hoạch tuyến tính

112 Phạm Quý Mười, Phan Thị Như Quỳnh MỘT PHƯƠNG PHÁP CHỌN ĐIỂM KHỞI ĐẦU TRONG GIẢI THUẬT ĐIỂM TRONG CHO BÀI TOÁN QUY HOẠCH TUYẾN TÍNH A METHOD OF CHOOSING STARTING POINT IN INTERIOR POINT ALGRITHMS FOR LINEAR PROGRAMMING Phạm Quý Mười1, Phan Thị Như Quỳnh2 1 Trường Đại học Sư phạm, Đại học Đà Nẵng; pqmuoi@ud.edu.vn 2 Trường Cao đẳng Công nghiệp Tuy Hòa; phanthinhuquynh@tic.edu.vn Tóm tắt - Phương pháp điểm trong thường được dùng để giải bài Abstract - The interior point Method is commonly used to solve toán quy hoạch tuyến tính. Do tốc độ hội tụ nhanh, phương pháp linear programming problems, especially those of large size due này thường được dùng để giải các bài toán có kích thước lớn. to its fast convergence speed. However, the convergence of the Tuy nhiên, sự hội tụ của giải thuật lại phụ thuộc vào việc chọn algorithm depends on the choice of starting point. Thus, the điểm khởi đầu. Vì thế, phương pháp chọn điểm khởi đầu có yếu method of selecting the starting point determines the operation of tố quyết định cho sự hoạt động của giải thuật và đã được quan the algorithm and has attracted the interest of both domestic and tâm nghiên cứu bởi nhiều tác giả khác nhau ở trong và ngoài internatinal authors. In this paper, the authors propose a method nước. Trong bài báo này, nhóm tác giả đề xuất một phương pháp of selecting the starting point to ensure the convergence of the chọn điểm khởi đầu đảm bảo cho sự hội tụ của giải thuật điểm interior point algorithm for linear programming. This method is trong cho bài toán quy hoạch tuyến tính. Phương pháp này dựa based on the Elliptic algorithm of solving linear inequalities. trên giải thuật Ellipsoid cải tiến tìm nghiệm của một bất đẳng Specific examples will illustrate the effectiveness of the method tuyến tính. Các ví dụ số cụ thể sẽ minh họa tính hiệu quả của proposed by the authors. All Matlab codes of these algorithms are phương pháp được nhóm tác giả đề xuất.Tất cả các mã Matlab also presented in detail in the article. của các giải thuật được trình bày chi tiết trong bài báo. Từ khóa - bài toán quy hoạch tuyến tính; phương pháp chọn Key words - Linear programming; Method of choosing starting điểm khởi đầu; phương pháp điểm trong; phương pháp Ellipsoid; point; Interior point method; Ellipsoid method; feasible solution; phương án chấp nhận được khởi đầu; phương án tối ưu chấp feasible optimal solution. nhận được. 1. Đặt vấn đề bày phương pháp điểm trong cho Bài toán (1). Mục 2.3 Xét bài toán quy hoạch tuyến tính ở dạng chính tắc: trình bày phương pháp chọn điểm khởi đầu cho phương pháp điểm trong. Đây là kết quả chính của bài báo. Trong  min cT x  Mục 3 nhóm tác giả áp dụng phương pháp điểm trong để A x  b , (1) giải một số ví dụ cụ thể và xem xét sự hoạt động của x  0 phương pháp điểm trong với điểm khởi đầu được chọn  bởi phương pháp đưa ra trong Mục 2.3. Cuối cùng, trong trong đó A  Rmn , b  Rm , c  Rncho trước và x  R n Mục 4 nhóm tác giả trình bày mã Matlab cho các giải là vectơ cần tìm. Trong bài báo này, nhóm tác giả giả sử thuật và ví dụ được khảo sát trong bài báo này. rằng tập các nghiệm chấp nhận được (tức là tập các phương án chấp nhận được) có phần trong khác rỗng. 2. Kết quả nghiên cứu Có nhiều phương pháp để giải Bài toán (1) như phương 2.1. Giải thuật Ellipsoid và sự hội tụ pháp hình học, phương pháp đơn hình, phương pháp đơn Trong phần này nhóm tác giả trình bày tóm tắt giải hình đối ngẫu [1,2]. Khi bài toán có kích thước lớn, người thuật Ellipsoid cho bài toán: Tìm một điểm của tập P định ta thường tìm nghiệm xấp xỉ của Bài toán (1)bằng phương nghĩa bởi: pháp điểm trong. Phương pháp điểm trong cho Bài toán (1) rất dễ để lập trình trong các phần mềm toán học như P  {u  Rk : Bu  d}, (2) l k l Matlab, Maple,... Tuy nhiên, một nhược điểm của phương trong đó B  R và d  R là ma trận và vectơ cho trước. pháp này là vấn để tìm điểm khởi đầu đảm bảo cho sự hội Chú ý rằng, phương pháp Ellipsoid đã được nghiên tụ của giải thuật. Vấn đề này đã được quan tâm nghiên cứu trong [1,3] và sự hội tụ của nó được chứng minh khi cứu bởi nhiều nhà toán học trong và ngoài nước [1, 2]. P là một tập bị chặn và đủ số chiều. Trong bài báo này, nhóm tác giả trình bày một phương Định nghĩa 1. Tập P  Rk được gọi là đủ số chiều nếu pháp có tính ứng dụng cao cho việc tìm điểm khởi đầu tồn tại r  0 sao cho P chứa quả cầu S ( y* , r ) với tâm tại y* bảo đảm sự hội tụ của giải thuật điểm trong cho Bài toán và bán kính r . (1). Phương pháp đưa ra ở đây dựa trên giải thuật Ellipsoid Trước hết, chú ý rằng một Ellipsoid trong không gian cải tiến tìm nghiệm của một bất đẳng thức tuyến tính được nghiên cứu trong [3]. Rk là tập Bài báo có bố cục như sau: Các kết quả chính của bài  T  E  z , D  : x  R k :  x  z  D 1  x  z   1 , báo được trình bày trong Mục 2: Mục 2.1 trình bày tóm trong đó D là ma trận đối xứng, xác định dương cấp tắt giải thuật Ellipsoid và Ellipsoid cải tiến. Mục 2.2 trình k  k và z  Rk được gọi là tâm của Ellipsoid.
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 1(98).2016 113 Ý tưởng của phương pháp Ellipsoid là đi xây dựng biT xt  di  2 với   0 được chọn khá bé. một dãy Ellipsoid có thể tích giảm dần và chứa tập P sao 2.2. Giải thuật điểm trong và sự hội tụ cho dãy các điểm tâm của Ellipsoid hội tụ về một điểm nào đó của P. Cụ thể như sau: Xét bài toán quy hoạch tuyến tính ở dạng chính tắc đưa ra bởi Bài toán (1). Ý tưởng đầu tiên trong phương Thuật toán Ellipsoid xây dựng ở mỗi bước lặp thứ t, pháp điểm trong là thay vì trực tiếp giải Bài toán (1), thì một Ellipsoid Etcó tâm xt và chứa tập lồi đa diệnP. Nếu sẽ đi giải một dãy bài toán xấp xỉ mà dãy nghiệm của nó xt  P thì thuật toán kết thúc. Nếu xt  Pthì xt sẽ không hội tụ về một nghiệm của (1). Cụ thể là xét dãy bài toán thỏa mãn ít nhất một ràng buộc, tức là sẽ có một hàng bi tối ưu sau: củaB và thành phần di của d sao cho biT xt  di . Mọi x  P  n T thỏa ràng buộc Bx  d nên biT x  biT xt . Do đó P chứa trong min B ( x) : c x    log x j  j 1 , (3) nửa không gian K :  x  R k : bi T x  bi T xt  .Vậy, nếu  A x  b. xt  P thì P chứa trong Et  K. Ta gọi Et  K là nửa  Ellipsoid (chú ý rằng siêu phẳng xác định nửa Ellipsoid đi Ở đây   0 là tham số và nghiệm của bài toán ký hiệu qua tâm xt của Et). Tính chất hình học của Ellipsoid cho là x(). Hàm B ( x) được gọi là hàm chắn (barrier phép ta tìm được một Ellipsoid mới Et 1 chứa nửa function). Hàm chắn này có một ưu việt là nó lồi chặt nên Ellipsoid của Et và có thể tích nhỏ hơn hẳn Et. Lặp lại quá nghiệm x() của Bài toán (3) là duy nhất. Rõ ràng khi  trình trên ta sẽ thu được dãy điểm {xt }(hữu hạn hoặc vô càng nhỏ (gần 0) thì x()càng gần đến nghiệm tối ưu của hạn) sao cho xt  P cho một giá trị t nào đó, hoặc Bài toán (1). xt  x  P. Bài toán (3) là một bài toán phi tuyến và vì thế vẫn Cách xây dựng dãy Ellipsoid Et như được mô tả ở còn khó giải vì hàm mục tiêu tuy là lồi chặt nhưng không phần trên được trình bày chi tiết trong Giải thuật 1 dưới phải là hàm bậc hai. Ta lại xấp xỉ một lần nữa bài toán đây: này bằng cách thay B ( x) bởi đa thức Taylor bậc hai của Giải thuật 1: nó. Giả sử x  0là nghiệm xấp xỉ hiện hành, tính toán trực tiếp các đạo hàm riêng cấp một và cấp hai, ta có: Phương pháp Ellipsoid cho Bài toán (2) 1 Đầu Ma trận B và vectơ d ; Điểm x0 và r  0 sao cho B ( x  d )  B ( x)   cT   eT X 1  d   d T X 2 d . (4) vào hình cầuE0  E  x0 , r 2 I  thỏa mãn P  E0, t =0; 2 Ở đây ma trận chéo X là ma trận có đường chéo chính Vòng WHILE xt  P làvectơ x. Bây giờ, thay cho Bài toán (3) ta giải bài toán lặp 1. Tìm hàng i sao cho: bT x  d (b là hàng thứ i xấp xỉ với hàm mục tiêu ở bên vế phải của (4)theod.Vì x i t i i của ma trận B ). cố định, bài toán xấp xỉ tương đương với: 1 Dt bi  T T 1 1 T 2 2. xt 1  xt  . , min (c   e X )d   d X d 1  k biT Dt bi  2  Ad  0. k2  2 Dt bi biT Dt  3. Dt 1  2  Dt  . , Điều kiện cần và đủ cho nghiệm tối ưu của bài toán k 1 k  1 biT Dt bi  này là: 4. t  t  1 , c   X 1e   X 2 d  AT y  0  END WHILE  Ad  0. Đầu xt Vì thế, phương pháp điểm trong cho Bài toán(1)được ra trình bày ở Giải thuật 2. Định lý 2. Giả sử P là tập bị chặn và đủ số chiều. Khi đó, Giải thuật 1 dừng sau hữu hạn bước. Giải thuật 2: Phương pháp điểm trong cho Bài toán (3) Chứng minh: Chứng minh định lí này có thể tìm thấy Đầu - Tham số của bài toán: A, b, c. ở [1, Định lí 1] (trang 117). vào - Điểm xuất phát: ( x0 , y 0 , s 0 ). Chú ý 3. Điều kiện P là tập đủ số chiều là một điều - Tiêu chuẩn dừng:  0. kiện khá chặt và trong nhiều trường hợp, điều kiện này - Giá trị tham số chắn: 0và tham số   (0,1). không thỏa mãn, ví dụ như tập nghiệm của bài toán quy Vòng WHILE( s k )T x k   hoạch tuyến tính. Hơn nữa, việc biểu diễn các số trong lặp 1.  k 1   k ; máy tính luôn chứa đựng sai số. Do đó, Giải thuật 1 thường có tính không ổn định. Vì thế, trong [3] nhóm tác 2. Giải hệ tuyến tính ra d và y: giả đã đề xuất một giải thuật thay thế, được gọi là k 1 2 T k 1 1   X k d  A y   X k e  c phương pháp Ellipsoid cải tiến. Phương pháp Ellipsoid  cải tiến hội tụ chỉ dưới điều kiện tậpP khác rỗng và bị  Ad  0, chặn. Giải thuật cho phương pháp Ellipsoid cải tiến hoàn 3. Cập nhật: toàn giống Giải thuật 1 ngoại trừ điều kiện trong Bước 1 x k 1  x k  d (nằm trong vòng lặp Giải thuật 1) được thay bởi điều kiện
114 Phạm Quý Mười, Phan Thị Như Quỳnh 0 0 0 k 1 y y Do đó, x , ( y , s ) lần lượt là điểm chấp nhận được của Bài toán (1) và bài toán đối ngẫu của nó nếu: s k 1  c  AT y  A x0  b k : k 1  T 0 0 END WHILE A y  s  c Đầu ra x k  0 0  x  0, s  0. Chú ý rằng, X k là ma trận chéo mà đường chéo chính là Để thỏa mãn điều kiện x 0  0, s 0  0, xét bài toán: vectơ x k và ở mục đầu vào của giải thuật trên, x0  0 là  A 0 0  b nghiệm chấp nhận được của (3)và ( y 0 , s 0 ),( s 0  0) là  A x0  b  A   b   0 0  0 nghiệm chấp nhận được của bài toán đối ngẫu của nó.  T 0  x    0 A y  s  c  0 AT In   0   c  Sự hội tụ của giải thuật này được đưa ra trong định lí sau:  0  T   y     , (6) Định lý 4. ([1], Định lý hội tụ) x    0  A  I n   s 0   c  Giả sử nghiệm gốc và đối ngẫu chấp nhận được xuất s0    In 0 0          phát là x0 , ( y 0 , s 0 ), với x 0  0, s 0  0 thỏa  0 0 I n     1 trong đó, chọn   0 là một số dương khá bé, ví dụ   1010. 0 X 0 S0 e  e    1. (5)  Dễ thấy rằng Bài toán(6) là một trường hợp cụ thể của   Bài toán(2)và vì thế nghiệm của nó có thể tìm được bằng Nếu tham số   1  thì sau Phương pháp Ellipsoid (Giải thuật 1) hoặc phương pháp  n Ellipsoid cải tiến (tức là Giải thuật 1 cùng với Chú ý 2).   n ( s 0 )T x 0 (1   )  Cuối cùng, xem xét cách chọn  0 . Chú ý rằng: K  log       (1   )  1 1 0 X 0 S0 e  e  X 0 S0  I ‖e‖ bước lặp, Giải thuật 2 sẽ cho cặp nghiệm chấp nhận được  0 gốc x k và đối ngẫu ( y k , s k ) với lỗ hổng đối ngẫu thỏa  x 0 s 0  ( s k )T x k   .  max i 1,,n ∣ i 0i  1∣ n . 2.3. Phương pháp chọn điểm khởi đầu    Từ Định lí 4 nhóm tác giả thấy rằng để Giải thuật 2 1 Do đó, điều kiện đủ cho 0 X 0 S 0 e  e   là: hội tụ thì điểm xuất phát cho giải thuật ( x 0 , y 0 , s 0 ) phải  thỏa mãn hai điều kiện:  x 0 s 0  0 0 0 0 0 (1) x  0, s  0 và x , ( y , s )lần lượt là điểm chấp max i 1,,n ∣ i 0i  1∣ n   , nhận được của Bài toán (3)và bài toán đối ngẫu    của nó. hay (như đã giả sử   1): (2)  0 thỏa mãn điều kiện:  xi0 si0 n xi0 si0 n   a n b n  0   ,  , , 1 X S e  e    1.  n   n     n   n    0 0 0 với mọi i  1,  , n. Ở đây, ký hiệua  min i 1,, n { xi0 si0 } và Trong hai điều kiện này, thì điều kiện thứ nhất là quan b  max i 1,, n { xi0 si0 }. trọng nhất, có vai trò quyết định sự hội tụ của Giải thuật 2. Trong khi đó, thực tế cho thấy, Giải thuật 2 hội tụ với Điều này suy ra: bất kỳ dãy{ k }hội về 0 khik  . Điều này có nghĩa là  b n a n  nếu điểm khởi đầu thỏa mãn Điều kiện (1) thì Giải thuật 2 0   , . hội tụ cho bất kỳ giá trị 0 và tham số  (0,1).Tuy nhiên,  n   n    sự lựa chọn giá trị 0 và  (0,1)ảnh hưởng đến tốc độ hội Do đó, Điều kiện (2) thỏa mãn khi và chỉ khi   1 và tụ của giải thuật. Điều kiện (2) cùng với giá trị cụ thể của  0 tồn tại, tức là:  trong Định lí 4 chỉ là điều kiện đủ để Giải thuật 2 hội tụ  b n a n sau K bước lặp.    n  n  . Do vai trò quan trọng của việc chọn các giá trị khởi  tạo thỏa mãn Điều kiện (1), nhóm tác giả sẽ trình bày một   1 phương pháp để chọn một điểm xuất phát ( x 0 , y 0 , s 0 ) thỏa Điều này tương đương với: mãn Điều kiện (1). ba n    1. Trước hết, chú ý rằng bài toán đối ngẫu của(1)là: ab m ax yT b Bất đẳng thức này chỉ thỏa mãn khi n khá bé hoặca  b  T T T khá bé (gần bằng không). Việc chọn các điểm khởi đầu x0và y A s  c s 0để thỏa mãn Điều kiện (1), đồng thời b  a khá bé thường  s  0.  rất khó. Tuy nhiên, như đã đề cập ở trên, Giải thuật 2 hội tụ
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 1(98).2016 115 0 với mọi   0 và tham số   (0,1). Vì thế, có thể chọn: 4.1. Chương trình Matlab cho giải thuật Ellipsoid cải tiến function [x0 i Ax0 b n 0  ,   0,5 và   0,5. Các ví dụ số ở phần Amin]=modified_ellipsoid_method(A,b,x0,R,Nmax) n  % Giải thuật 1 cùng với Chú ý 2 sau xác nhận rằng với các giá trị tham số này Giải thuật 2 if nargin==3 hội tụ rất nhanh. R=1e2; Nmax=100; 3. Ví dụ số end Trong phần này, nhóm tác giả xem xét hai ví dụ cụ thể [m n]=size(A); và sẽ trình bày kết quả nghiệm số khi áp dụng Giải thuật 2 D0=R^2*eye(n,n); với điểm khởi tạo đưa ra trong Mục 2.3. Ở đây, nhóm tác m_min=min(A*x0-b); giả chọn2  104 cho giải thuật Ellipsoid cải tiến, chọn Ax0=[x0];   1010cho Giải thuật 2 và  1010trong Bài toán (6). Amin=[m_min]; Các giải thuật và chương trình giải hai ví dụ ở đây được for i=0:Nmax viết bằng ngôn ngữ lập trình Matlab và được trình bày check=find(A*x0-b
116 Phạm Quý Mười, Phan Thị Như Quỳnh nu0=(2*sqrt(n)*tg2) /(2*sqrt(n)+1); 4.4. Chương trình Matlab cho Ví dụ 2 Ax0=[x0]; %EXAMPLE 2 fmin=c'*x0; n=15; Amin=[fmin]; X=eye(n); while s0'*x0>=epsilon A=[X X]; nu0=alpha*nu0; b=ones(n,1); tg=1./(x0.^2); c=[-ones(n,1);zeros(n,1)]; tg1=1./x0; %Giai thuat 2 (PP diem trong) BB=[nu0*diag(tg) -A';A zeros(m,m)]; epsilon=1e-10; R=nu0*diag(tg1)*e-c; [u0 fmin Au0 R=[R;zeros(m,1)]; Aumin]=interior_point_method(A,b,c,epsilon); u=BB\R; d=u(1:n); 5. Kết luận y=u(n+1:end); Trong bài báo này, nhóm tác giả đã đề xuất một % Update phương pháp mới cho việc chọn điểm khởi đầu trong x0=x0+d; phương pháp điểm trong để giải bài toán quy hoạch y0=y; tuyến tính. Lý thuyết cũng như các ví dụ số cụ thể chứng s0=c-A'*y; tỏ rằng, phương pháp mà nhóm tác giả đã trình bày hoạt end động tốt và đảm bảo sự hội tụ của phương pháp điểm fmin=c'*x0; trong. Hai ví dụ số cũng cho thấy rằng phương pháp Ax0=[Ax0 x0]; điểm trong có tốc độ hội tụ rất nhanh với các giá trị khởi Amin=[Amin fmin]; tạo nhận được từ phương pháp mà nhóm tác giả đã đề End xuất trong bài báo này. Vì thế, phương pháp chọn điểm 4.3. Chương trình Matlab cho Ví dụ 1 khởi đầu trong bài báo này có tính ứng dụng thực tế cao và có thể dùng kết hợp với phương pháp điểm trong cho clear all bài toán quy hoạch tuyến tính có kích thước lớn. %Ví dụ 1 A=[1 1]; b=[1]; TÀI LIỆU THAM KHẢO c=[2 3]'; [1] D. G. Luenberger &Y. Ye, Linear and nonlinear programming, %Giai thuat 2 (PP diem trong) Springer Science & Business Media, 2008. epsilon=1e-10; [2] Phan Quốc Khánh, Trần Huệ Nương, Quy hoạch tuyến tính, NXB Giáo dục, 1999. [u0 fmin Au0 Phạm Quý Mười, Phan Thị Như Quỳnh, “Phương pháp Ellipsoid Aumin]=interior_point_method(A,b,c,epsilon); cải tiến và ứng dụng giải bài toán quy hoạch tuyến tính”, Tạp chí Khoa học & Công nghệ, Đại học Đà Nẵng, Số 9(94).2015. (BBT nhận bài: 23/10/2015, phản biện xong: 22/11/2015)