Phương pháp Ellipsoid cải tiến và ứng dụng giải 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

18
lượt xem 2
download

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

Bài viết Phương pháp Ellipsoid cải tiến và ứng dụng giải bài toán quy hoạch tuyến tính nghiên cứu phương pháp Ellipsoid và phương pháp Ellipsoid cải tiến để tìm một điểm thỏa mãn hệ bất phương trình tuyến tính, và ứng dụng các phương pháp này vào bài toán quy hoạch 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: Phương pháp Ellipsoid cải tiến và ứng dụng giải bài toán quy hoạch tuyến tính

ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 9(94).2015 99 PHƯƠNG PHÁP ELLIPSOID CẢI TIẾN VÀ ỨNG DỤNG GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH MODIFIED ELLIPSOID METHOD AND ITS APPLICATION TO LINEAR PROGRAMMING PROBLEMS 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 Cao đẳng Công nghiệp Tuy Hòa, Phú Yên; phanthinhuquynh@tic.edu.vn Tóm tắt - Trong bài báo này, chúng tôi nghiên cứu phương pháp Abstract - In this paper, we study Ellipsoid method and modified Ellipsoid và phương pháp Ellipsoid cải tiến để tìm một điểm thỏa Ellipsoid method in order to find a point which satisfies a system mãn hệ bất phương trình tuyến tính, và ứng dụng các phương of linear inequalities and apply it to linear programming problems. pháp này vào bài toán quy hoạch tuyến tính. Đầu tiên, chúng tôi We first present Ellipsoid algorithm and prove its convergence . trình bày giải thuật Ellipsoid và chứng minh sự hội tụ của nó. Sau After analyzing the shortcomings of the algorithm, we propose the khi phân tích những hạn chế của giải thuật này, chúng tôi đưa ra new algorithm called the modified Ellipsoid algorithm and prove giải thuật Ellipsoid cải tiến và chứng minh sự hội tụ của giải thuật its convergence. Then, we present how the methods can be mới này. Sau đó, chúng tôi trình bày cách ứng dụng phương applied to find feasible solutions and optimal feasible solutions of pháp này vào giải bài toán tìm phương án chấp nhận được và linear programming problems. Finally, some particular examples phương án tối ưu chấp nhận được trong bài toán quy hoạch are given to illustrate the modified Ellipsoid method. The Matlab tuyến tính. Cuối cùng, một số ví dụ cụ thể được xem xét nhằm codes of modified Elliptisoid method as well as the Matlab codes minh họa phương pháp Ellipsoid. Các chương trình được viết for two numerical examples are also presented in detail. trong phần mềm Matlab cũng được trình bày chi tiết. Từ khóa - bài toán quy hoạch tuyến tính; phương pháp Ellipsoid; Key words - linear programming problem; Ellipsoid method; phương pháp Ellipsoid cải tiến; phương án chấp nhận được; Modified Ellipsoid method; feasible solution; optimal feasible phương án tối ưu chấp nhận được. solution. 1. Đặt vấn đề nhận được, phương trình (2) nhận được từ định lý đối Trong quy hoạch tuyến tính, người ta muốn tìm một ngẫu, xem [1]. nghiệm x  n của bài toán tối ưu tuyến tính: Vì thế, chúng ta trước hết trình bày phương pháp min Axb (c, x) n (1) Ellipsoid để tìm một điểm của P và chứng minh sự hội tụ của nó. Chú ý rằng, phương pháp Ellipsoid đã được trình trong đó, A  mn , c  n và b  m là ma trận và là các bày trong [1] và sự hội tụ của nó được chứng minh khi P vector cho trước. là một tập bị chặn và đủ số chiều (xem định nghĩa ở phần Trong bài toán này, mỗi vector x  n thỏa mãn bất sau).Trong bài báo này chúng tôi chỉ giả sử rằng tập P bị đẳng thức Ax  b được gọi là một phương án chấp nhận chặn và khác rỗng. Chúng ta sẽ nghiên cứu giải thuật được và mỗi nghiệm của bài toán được gọi là một phương Ellipsoid cải tiến trong điều kiện này. Kết quả chính của án tối ưu chấp nhận được. Các bài toán tìm phương án bài báo là đưa ra được giải thuật Ellipsoid cải tiến (Giải chấp nhận được và phương án tối ưu chấp nhận được là thuật 2) và chứng minh sự hội tụ của giải thuật này, xem hai bài toán cơ bản và quan trọng trong nghiên cứu bài Định lí 2. Các kết quả khác là trình bày ứng dụng các giải toán quy hoạch tuyến tính và được nghiên cứu bởi nhiều thuật vào bài toán quy hoạch tuyến tính cũng như các tác giả khác nhau. Đối với bài toán kích thước bé (n  10), chương trình được viết trong môi trường Matlab. Các ví bài toán tìm một phương án chấp nhận được có thể giải dụ số cụ thể sẽ minh họa cho sự thực thi hiệu quả của giải thủ công (bằng tay) và bài toán tìm một phương án tối ưu thuật Ellipsoid cải tiến. chấp nhận được thường được giải bởi phương pháp đơn 2. Kết quả nghiên cứu hình. Những phương pháp như thế có thể tham khảo ở các cuốn sách về bài toán quy hoạch tuyến tính, ví dụ như Phần này chúng tôi trình bày phương pháp Ellipsoid trong các cuốn [1,2]. cho bài toán (2) và chứng minh sự hội tụ của nó.Trước hết, chú ý rằng một Ellipsoid trong không gian k là tập: Trong bài báo này, chúng tôi nghiên cứu phương pháp Ellipsoid và áp dụng nó vào tìm phương án chấp nhận được  E ( z, D ) := x  k  : ( x − z ) D −1 ( x − z )  1 , T và phương án tối ưu chấp nhận được của bài toán (1) khi n và m có giá trị lớn. Ý tưởng chính của bài báo như sau: trong đó D là ma trận đối xứng, xác định dương cấp k  k và z  k được gọi là tâm của ellipsoid. Bài toán tìm phương án chấp nhận được và phương án tối ưu chấp nhận được của (1) có thể quy về việc tìm một Chúng ta cũng cần khái niệm sau: nghiệm của tập P định nghĩa bởi Định nghĩa: Tập P  k được gọi là đủ số chiều nếu P = {u  k : Bu  d} (2) tồn tại r  0 sao cho P chứa quả cầu S ( y* , r ) với tâm tại trong đó, B  l k và d  l là ma trận và vector cho y* và bán kính r. trước tương ứng. Cho bài toán tìm phương án tối ưu chấp 2.1. Ý tưởng của phương pháp Ellipsoid
100 Phạm Quý Mười, Phan Thị Như Quỳnh Ý tưởng của phương pháp Ellipsoid là đi xây dựng sử P  Et đúng với t nào đó. một dãy ellipsoid có thể tích giảm dần và chứa tập P sao Vì xt  P nên sẽ có ràng buộc bị vi phạm: biT(t ) xt  bi (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: với xt là tâm của Et . Với mọi x  P, ta có biT(t ) xt  bi (t )  biT(t ) x. Thuật toán Ellipsoid xây dựng ở mỗi bước lặp thứ t, một ellipsoid Et có tâm xt và chứa tập lồi đa diện P . Nếu xt  P   Do đó :P  Kt := x  R k : biT(t ) x  biT(t ) xt . thì thuật toán kết thúc. Nếu xt  P thì xt sẽ không thỏa mãn ít Vậy P  Et  K t. Gọi Et +1 là ellipsoid E ( xt +1 , Dt +1 ) thì nhất một ràng buộc, tức là sẽ có một hàng b i của B và thành từ [1, Định lí 1] (trang 117) ta có Et  K t  Et +1. Do đó, phần d i của d sao cho biT xt  di . Mọi x  P thỏa ràng buộc P  Et +1. Vậy theo phương pháp quy nạp, ta có : P  Et Bx  d nên biT x  biT xt. Do đó P chứa trong nửa không gian với mọi t . K := x  Rk : biT x  biT xt . Vậy, nếu xt  P thì P chứa Vì P là tập đủ số chiều và P  Et với mọi t nên tồn trong Et  K . Ta gọi Et  K là nửa ellipsoid (chú ý rằng siêu tại y* và r *  0 sao cho S ( y* , r * )  P  Et với mọi t . phẳng xác định nửa ellipsoid đi qua tâm xt của Et). Tính chất Vol ( Et +1 ) −1 hình học của ellipsoid cho phép ta tìm được một ellipsoid Theo [1, Định lí 1] ta có  e 2( k +1) và mới Et +1 chứa nửa ellipsoid của Et và có thể tích nhỏ hơn hẳn Vol ( Et ) Et. Lặp lại quá trình trên ta sẽ thu được dãy điểm {xt } (hữu Vol ( Et ) −t 2( k +1) hạn hoặc vô hạn) sao cho xt  P cho một giá trị t nào đó, e (Vol ( A) là “độ đo” của tập A  n, tức là hoặc xt → x  P. Vol ( E0 ) độ dài, diện tích, thể tích,… với n = 1, 2,3, tương ứng). 2.2. Giải thuật Ellipsoid và sự hội tụ Do đó: 0  Vol ( S ( y* , r * ) )  Vol ( Et ) → 0, Cách xây dựng dãy Ellipsoid Et như được mô tả ở phần trên được trình bày chi tiết trong Giải thuật 1 dưới đây: khi t tiến ra vô cùng. Điều này dẫn đến mâu thuẫn. Vì vậy Giải thuật 1 Giải thuật 1 dừng lai sau hữu hạn bước. Đầu Ma trận B và vectơ d ; Điểm x0 và r  0 sao cho Như vậy sự hội tụ của Giải thuật 1 nhận được khi P là vào: hình cầuE0 = E ( x0 , r 2 I ) thỏa mãn P  E0 . tập đủ số chiều. Điều này hầu như không xảy ra cho bài t =0 ; toán tìm phương án tối ưu chấp nhận được trong quy Vòng WHILE xt  P hoạch tuyến tính vì trong nhiều trường hợp, tập các lặp: phương án tối ưu chấp nhận được của bài toán quy hoạch Tìm hàng i sao cho: biT xt  di . (bi là hàng thứ i tuyến tính là duy nhất hoặc hữu hạn. Trong phần tiếp theo của ma trận B ) chúng ta nghiên cứu giải thuật Ellipsoid cải tiến để nhận 1 Dt bi được nghiệm xấp xỉ của P trong trường hợp P bị chặn và xt +1 = xt + . , 1 + k biT Dt bi khác rỗng. k2  2 Dt bi biT Dt  2.3. Giải thuật Ellipsoid cải tiến và sự hội tụ Dt +1 =  Dt − . , k −1  2 k + 1 biT Dt bi  Giải thuật Ellipsoid cải tiến được trình bày bởi ngôn t = t + 1, ngữ giả lập trình trong Giải thuật 2 sau đây: Giải thuật 2 END WHILE Đầu Ma trận B và vectơ d ; Điểm x0 và r  0 sao cho Đầu ra xt vào: hình cầuE0 = E ( x0 , r 2 I ) thỏa mãn P  E0 . Nhận xét 1: Chú ý rằng phương pháp đơn hình cho t =0 ;   0 và P = {x  k : Bx  d − 2 }. bài toán quy hoạch tuyến tính phải bắt đầu từ một phương án cực biên. Một phương án như thế thường là khó tìm, Vòng WHILE xt  P2 đặc biệt cho các bài toán kích thước lớn. Ngược lại, lặp: Tìm hàng i sao cho: biT xt  di − 2 . (bi là hàng phương pháp Ellipsoid cho phép chúng ta tùy ý lựa chọn thứ i của ma trận B ) điểm khởi tạo. Chỉ cần chọn r  0 đủ lớn, Giải thuật 1 1 Dt bi xt +1 = xt + . , luôn luôn cho kết quả. Đây là một ưu thế của phương 1 + k biT Dt bi pháp Ellipsoid. k2  2 Dt bi biT Dt  Định lý 1. Giả sử P là tập bị chặn và đủ số chiều. Khi Dt +1 =  Dt − . , đó, Giải thuật 1 dừng sau hữu hạn bước. k −1  2 k + 1 biT Dt bi  t = t + 1, Chứng minh: Chứng minh định lí này tương tự như chứng minh [1, Định lí 1] (trang 117). END WHILE Nếu giải thuật dừng lại sau hữu hạn bước thì định lí Đầu ra xt được chứng minh. Ta giả sử Giải thuật 1 lặp vô hạn và đi Kết quả chính của bài báo được đưa ra trong định lý chứng minh rằng điều này đẫn đến mâu thuẫn. sau: Trước hết ta chứng minh bằng phương pháp quy nạp Định lý 2. Giả sử P là tập bị chặn và khác rỗng. rằng P  Et với mọi t . Từ Giải thuật 1, ta có P  E0 . Giả
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 9(94).2015 101 Khi đó, Giải thuật 2 dừng sau hữu hạn bước. Hơn 2 x1 + x2  5 nữa, nếu Giải thuật 1 dừng tại bước thứ t = N ( ), − x + x  −1 thì d ( xN ( ) .P) → 0 khi → 0, trong đó  1 2 − x1  −3 d ( x, P) = inf‖ x − y‖ là khoảng cách từ x đến P .  yP − x2  −4 . Chứng minh: Ta định nghĩa  x − x  −2 P = {x  k : Bx  d − }. Vì P khác rỗng nên tồn tại  1 2  x1  0 x  P . Chọn 1  0 đủ bé sao cho | By − Bx | với mọi  y  S ( x, 1 ) . Khi đó, ta có By  Bx − d − / 2  d − 2 với  x2  0 mọi y  S ( x, 1 ) . Do đó, S ( x, 1 )  P2 . Tức là P2 là tập đủ Bài toán này có duy nhất một nghiệm tối ưu là (2,1). số chiều. Dễ thấy rằng, Giải thuật 2 chính là Giải thuật 1 Giải thuật 2 cho bài toán tìm phương án chấp nhận với P được thay bởi P2 . Vì P là tập bị chặn và khác rỗng, được và phương án tối ưu trong ví dụ này được liệt kê ở nên P2 là tập bị chặn và đủ số chiều. Áp dụng Định lí 1, ta Bảng 1&2. Chú ý rằng, các giá trị được làm tròn đến bốn có Giải thuật 2 dừng tại bước thứ t = N ( ) hữu hạn và chữ số thập phân sau dấu phảy. xN ( )  P2 . Mặt khác, ta có: Bảng 1. Giải thuật 1 với x0 = (0, 0) và r = 10 cho Ví dụ 1 đối d ( xN ( ) , P)  d ( P2 , P) → 0 khi → 0. Vậy định lí với bài toán tìm phương án chấp nhận được được chứng minh. t xt min( Axt − b) 3. Ứng dụng vào bài toán quy hoạch tuyến tính 0 (0,0) -5 Xét bài toán quy hoạch tuyến tính( P ) và bài toán đối 1 (2.9814, 1.4907) -0.4907 ngẫu của nó ( D ): 2 (0.9155, 4.6835) -1.7680  f ( x ) = cT x → min  g ( y ) = bT y → max 3 (0.7056, 1.8449) -1.7439   T ( P) Ax  b và( D ) A y  c 4 (3.2403, 2.5560) -0.2403 x  0 y  0 5 (1.2704, 3.1902) 0.0802   Bảng 1 cho thấy rằng, chỉ với 5 vòng lặp, chúng ta trong đó A  mn, c, x  n và b, y  m. nhận được một phương án chấp nhận được. Trong trường Bài toán tìm một phương án chấp nhận được của ( P )là hợp này, tập P1 = {x : Ax  b, x  0} đủ số chiều và bị tìm một điểm x  n sao cho chặn. Đo đó, kết quả số trong trường hợp này phù hợp với kết quả lý thuyết trong Định lí 2.  Ax  b  A b   hay ( P1 )   x    . Đối với bài toán tìm phương án tối ưu, kết quả số x  0 In  0 được trình bày ở Bảng 2. Giải thuật dừng lại sau 3639 Từ định lý đối ngẫu mạnh thì ( P ) có nghiệm tối ưu xkhi vòng lặp. Chú ý rằng, trong trường hợp này tập nghiệm và chỉ khi ( D ) có nghiệm tối ưu y và điều này xảy ra khi và tối ưu chỉ có một điểm, tức là giả thiết về đủ số chiều không thỏa mãn. Tuy vậy, giải thuật vẫn cho nghiệm xấp chỉ khi ( x, y ) thỏa mãn hệ bất đẳng thức sau : xỉ với độ chính xác cao sau hữu hạn bước.  −cT bT  0 Bảng 2. Giải thuật 1 với x0 = (0, 0) và r = 10 cho Ví dụ 1 đối  c T x − bT y  0      với bài toán tìm phương án tối ưu chấp nhận được  A 0   x  b  Ax  b 0  T hay ( P2 ) − AT      −c  . t xt = ( x, y ) min( Bxt − d ) A y  c    y    x  0, y  0  In 0  0 x  0   0  0 (0,0) -5  Im  1 (0.8944,0.447) -3.1305 Do đó, bài toán tìm phương án chấp nhận được ( P1 ) và 2 (0.7161,0.1104) -3.4573 bài toán tìm phương án tối ưu chấp nhận được ( P2 ) dẫn đến bài toán tìm một nghiệm của bất phương trình (2). 3 (1.5234,0.4967) -1.4565 … … … Trong phần tiếp theo, chúng ta sẽ trình bày kết quả số khi áp dụng Giải thuật 2 cho các ví dụ cụ thể. Chúng ta chon 3637 (2,1) -1.2079e-10 2 = 10−10 và Giải thuật 2 được viết bằng ngôn ngữ lập trình 3638 (2,1) -1.3057e-10 Matlab. Các mã chương trình Matlab cho Giải thuật 2 và các 3639 (2,1) -9.6286e-11 ví dụ sau được trình bày trong phần tiếp theo: Ví dụ 2 : Ví dụ 1 : n Xét bài toán : Tìm min ( x , x ) 2 2 x1 + 3x2 với điều kiện Xét bài toán : Tìm min x n −  xi với điều kiện 1 2 i =1 ( x1 , x2 ) thỏa mãn : 0  xi  1 với mọi i = 1,, n. Phương án tối ưu chấp nhận được của bài toán là x = (1, ,1). Áp dụng Giải thuật 2 để tìm phương án tối ưu chấp nhận được trong ví dụ này được liệt kê ở Bảng 3. Ở đây
102 Phạm Quý Mười, Phan Thị Như Quỳnh chúng ta chọn n = 15. k=check(1); Bảng 3. Giải thuật 1 với x0 = (−1, , −1) và r = 3 cho Ví dụ 2 ak=A(k,:)'; đối với bài toán tìm phương án chấp nhận được x1=x0+D0*ak/((1+n)*(sqrt(ak'*D0*ak))); t xt min( Axt − b) x0=x1; 0 (-1,…,-1) -1 tg1=n^2/(n^2-1); 1 (-0.8125,…,-1) -1 tg2=2/(n+1); … … … D0=tg1*(D0- tg2*(D0*ak)*(ak'*D0)/(ak'*D0*ak)); 90 (0.0905,…,-0.3590) -0.3590 m_min=min(A*x0-b); 91 (0.0905,…, -0.1715) -0.1715 Ax0=[ Ax0 x0]; 92 (0.0905,…, 0.0043) 0.0043 Amin=[ Amin m_min]; Bảng 3 cho thấy sau 92 vòng lặp, chúng ta nhận được end một phương án chấp nhận được. Trong trường hợp này end P1 = {x : Ax  b, x  0} đủ số chiều và bị chặn. Như trong Amin=Amin'; Ví dụ 1, nghiệm số là một phương án chấp nhận được. Ax0=Ax0'; Đối với bài toán tìm phương án tối ưu, kết quả số được end trình bày ở Bảng 4. Giải thuật dừng lại sau 81921 vòng lặp. Giống như Ví dụ 1, trong trường hợp này tập nghiệm tối ưu 4.2. Chương trình Matlab cho Ví dụ 1 chỉ có một điểm, tức là giả thiết về đủ số chiều không thỏa clear all mãn và nghiệm số là nghiệm xấp xỉ của phương án tối ưu chấp nhận được với độ chính xác gần như tuyệt đối. Nmax=10000; Bảng 4. Giải thuật 1 với x0 = (0, , 0) và r = 10 cho Ví dụ 2 %EXAMPLE 1 đối với bài toán tìm phương án tối ưu chấp nhận được A=[2 1; -1 1; -1 0; 0 -1;1 -1;1 0;0 1]; t xt = ( x, y ) min( Bxt − d ) b=[5 -1 -3 -4 -2 0 0]'; x %bài toán tìm phương án chấp nhận được 0 (0,…,0) -1 [m n]=size(A); 1 (0,…,0) -1 x0=zeros(n,1); 2 (0.0397,…,0.0397) -1.0397 R=1e1; 3 (0.0399,…,0.0399) -1.0399 [x0 i Ax0 Amin]=ellipsoid_method(A,b,x0,R,Nmax); … … … %bài toán tìm phương án tối ưu chấp nhận được 81919 (1,…,1) -1.9933e-10 c=[2 3]'; 81920 (1,…,1) -1.0707e-10 B=[-c' b';A zeros(m,m);zeros(n,n) -A';... 81921 (1,…,1) -9.8824e-11 eye(n) zeros(n,m);zeros(m,n) eye(m)]; 4. Chương trình Matlab d=[0; b; -c; zeros(n,1);zeros(m,1)]; Các kết quả nghiệm số trong phần trên nhận được khi k=size(B,2); Giải thuật 1 được mã hóa trong phần mềm Matlab. Phần x0=zeros(k,1); này chúng tôi đưa ra các chương trình Matlab của Giải R=1e1; thuật 1 và hai ví dụ đã trình bày ở phần trước. Giải thuật 1 [xx0 ii Axy0 Aminp]… là hàm “ellipsoid_method”. =ellipsoid_method(B,d,x0,R,Nmax); 4.1. Chương trình Matlab cho Giải thuật 1 4.3. Chương trình Matlab cho Ví dụ 2 function [x0 i Ax0 Amin]… clear all =ellipsoid_method(A,b,x0,R,Nmax) Nmax=100000; %Giải thuật 1 %EXAMPLE 2 [m n]=size(A); n=15; D0=R^2*eye(n,n); A=[-eye(n);eye(n)]; m_min=min(A*x0-b); b=[-ones(n,1);zeros(n,1)]; Ax0=[x0]; %bài toán tìm phương án chấp nhận được Amin=[m_min]; [m n]=size(A); for i=0:Nmax x0=-ones(n,1); check=find(A*x0-b
ISSN 1859-1531 - TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ ĐẠI HỌC ĐÀ NẴNG, SỐ 9(94).2015 103 B=[-c' b';A zeros(m,m);zeros(n,n) -A';... điều kiện khác nhau của tập P . Từ đó, chúng tôi chi tiết eye(n) zeros(n,m); zeros(m,n) eye(m)]; phương pháp Ellipsoid thông qua Giải thuật 1. Chúng tôi cũng đã chỉ ra cách ứng dụng phương pháp Ellipsoid vào d=[0; b; -c; zeros(n,1);zeros(m,1)]; tìm phương án chấp nhận được và phương án tối ưu k=size(B,2); chấp nhận được trong bài toán quy hoạch tuyến tính. x0=-zeros(k,1); Các ví dụ số đã minh họa Giải thuật 1 và các kết quả số R=1e1; phù hợp với các kết quả lí thuyết. [xx0 ii Axy0 Aminp]… =ellipsoid_method(B,d,x0,R,Nmax); TÀI LIỆU THAM KHẢO [1] Luenberger, D. G., & Ye, Y. (2008). Linear and nonlinear 5. Kết luận programming (Vol. 116). Springer Science & Business Media. Bài báo này đã trình bày phương pháp Ellipsoid cho [2] Phan Quốc Khánh, Trần Huệ Nương, 1999. Quy hoạch tuyến tính. bài toán (2) và chứng minh sự hội tụ của nó dưới các NXB Giáo dục. (BBT nhận bài: 24/07/2015, phản biện xong: 31/08/2015)