Đề tài Thuật toán Frank-Wolfe

Lời mở đầu Tất cả các ngành, các lĩnh vực dù hoạt động ở phương diện nào thì mục đích cuối cùng cũng là giải các bài toán tối ưu của đơn vị mình. Việt Nam là một minh chứng. Trong xu thế hội nhập hiện nay, đặc biệt sau kí kết hiệp định thương mại thế giới WTO, Việt Nam đang đứng trước nhiều thử thách mới. Và cạnh tranh trên thương trường quốc tế là bài toán hàng đầu đối với các doanh nghiệp trong nước. Do tính cấp thiết của thực tế nên em đã quyết định chọn đề tài: “Thuật toán Frank-Wolfe”- đây là thuật toán giải các bài toán quy hoạch lồi với các ràng buộc tuyến tính. Em hi vọng nó có thể góp một phần làm phong phú hơn kho tàng thuật toán giải các bài toán tối ưu. Bài viết của em gồm 3 phần lớn (ngoài phần mục lục và phần tài liệu tham khảo): Thứ nhất : Lời mở đầu Thứ hai : Nội dung Thứ ba : Kết luận Trong phần nội dung,em sẽ trỡnh bày 4 vấn đề chớnh: Tổng quan về quy hoạch phi tuyến Thuật toỏn Frank-Wolfe Thớ dụ Chương trỡnh Gamside Cuối cựng, em xin chõn thành cảm ơn cỏc thầy giỏo,cụ giỏo khoa Toỏn kinh tế đó tạo mụi trường cho em được học tập và rốn luyện. Em hết sức biết ơn thầy giỏo Ngụ Văn Mỹ đó giỳp em hoàn thành đề ỏn mụn học này. Nội dung: 1. Tổng quan về quy hoạch phi tuyến 1.1. Giới thiệu chung về QHFT Bài toỏn QHFT sẽ núi ở dưới đõy khụng phải là bài toỏn QHFT thực tổng quỏt, mà ta chỉ xột lớp bài toỏn QHFT cú hàm mục tiờu là hàm khả vi liờn tục( tới bậc tuỳ ý) trờn tập mở bao tập phương ỏn D; bản thõn tập phương ỏn cũng được xỏc định bởi cỏc hàm số trong cỏc ràng buộc là cỏc hàm khả vi liờn tục n biến. Cụ thể ta cú bài toỏn tổng quỏt sau: (1) Trong đú: và là cỏc hàm n biến độc lập. Ngoài ra: trong cỏc hàm và phải cú ớt nhất một hàm phi tuyến; luụn giả thiết cỏc hàm là cỏc hàm liờn tục; hàm mục tiờu khả vi liờn tục trờn tập mở bao tập phương ỏn D. Tuy bài toỏn QHFT đó được giới hạn như trờn, nhưng tớnh phi tuyến của bài toỏn luụn tạo ra những phức tạp đỏng kể khi tiệm cận với nú. Với bài toỏn QHFT người ta cũng sử dụng phương phỏp tiệm cận giống như bài toỏn cực trị cú ràng buộc cổ điển trong giải tớch-tức là tỡm cỏch đưa bài toỏn cực trị cú ràng buộc về bài toỏn cực trị tự do rồi tỡm cỏch đưa ra điều kiện Kunh- Tucker. Với một nhóm điều kiện bổ sung đủ mạnh thì điều kiện Kunh-Tucker cú thể trở thành điều kiện cần và đủ đối với lời giải của (1). 1.2. Bài toỏn QHFT Bài toỏn tổng quỏt QHFT cú dạng như (1); tuy nhiờn đụi khi để thuận tiện trong việc giải thớch ý nghĩa kinh tế ta cú thể biểu diễn cỏc dạng cụ thể sau: (1.1) (1.2) Về mặt hỡnh thức thỡ ba bài toỏn (1),(1.1), (1.2) khỏc nhau, song cũng giống như QHTT ta cú thể dựng cỏc phộp biến đổi tương đương để đưa bài toỏn này về bài toỏn kia. Cụ thể như sau: a. b. c. d. e. 1.3. Điều kiện Kuhn-Tucker Trở lại bài toỏn tổng quỏt (1) ban đầu: với cỏc giả thiết đó cú về và, nếu cả m ràng buộc của (1) đều cú dạng đẳng thức; m<n và cỏc hàm là hệ hàm độc lập thỡ bài toỏn (1) cú thể xem là bài toỏn tỡm cực trị tổng thể cú ràng buộc đẳng thức trong giải tớch toỏn học. Giải tớch đó giải quyết bài toỏn này bằng cỏch đưa bài toỏn về bài toỏn cực trị tự do của hàm Lagrange cú nghiệm luụn được xem là điều kiện cần đối với cực trị địa phương cú điều kiện của f(x). Tuy vậy, thuật toỏn này đụi khi cũng khụng thể giải quyết được một bài toỏn bất kỳ, trừ phi hàm f(x) cú cỏc tớnh chất giải tớch bổ sung cần thiết. Đối với bài toỏn (1), hai nhà toỏn học H. W.Kuhn và A. W.Tucker cũng sử dụng cỏch tiệm cận tương tự và đó đưa ra một nhúm điều kiện gọi là điều kiện Kuhn-Tucker. Điều kiện Kuhn-Tucker được viết cho cỏc bài toỏn : (1.2) Lập hàm Lagrange: ( nhõn tử Lagrange) Khi đú điều kiện Kuhn-Tucker được thiết lập như sau: Ngược lại nếu bài toỏn cú dạng tổng quỏt như sau: (1.1) Thỡ điều kiện Kuhn-Tucker cú dạng: hoặc là chuyển bài toỏn dạng (1.1) về bài toỏn dạng (1.2) rồi viết giống như với bài toỏn (1.2). 1.4. Cỏc vấn đề cần giải quyết khi giải bài toỏn QHFT Trước khi đi vào chi tiết, ta đề cập đến bản chất của cỏc thuật toỏn giải cỏc bài toỏn QHFT núi chung. Bài toỏn tổng quỏt dạng: (*) Với bài toỏn (*) tuỳ theo cấu trỳc của nú mà người ta đưa ra cỏc thuật toỏn khỏc nhau. Cho tới thời điểm này, số phương phỏp được đề xuất là rất lớn và đa dạng. Song cỏc phương phỏp này đều cú ý tưởng chung là thuật toỏn xiết chặt dần. Tuỳ theo dóy điểm nằm trong hay nằm ngoài tập D mà được chia thành hai nhúm phương phỏp lớn là phương phỏp điểm trong hay điểm ngoài hoặc phối hợp cả hai phương phỏp trờn. Ở đõy ta xột kỹ phương phỏp điểm trong. Người ta xuất phỏt từ một điểm ; khi đú là hướng tăng nhanh nhất của f(x) tại x0 (hay cũn được gọi là hướng tăng cục bộ của f(x) tại x0). Ta lại cú ở phần trước tập là tập hợp cỏc hướng chấp nhận được tại x0 và nếu lấy thỡ cú: là đạo hàm theo phương d của hàm f(x) tại x0, nú cho biết mức thay đổi của hàm f(x) tại x0 theo phương d. Rừ ràng: Nếu cú thỡ d được gọi là hướng chấp nhận được tăng của f(x) tại x0. Nếu cú thỡ d được gọi là hướng chấp nhận được giảm của f(x) tại x0. Nếu cú thỡ d được gọi là hướng chấp nhận được khụng đổi của f(x) tại x0. Phương phỏp xiết chặt dần trờn dóy điểm trong cú thể được mụ tả như sau: Chọn một điểm và kiểm tra xem tại x0 cú hướng chấp nhận được giảm của f(x) tại đú hay khụng? Trong trường hợp tại đú cú hướng chấp nhận được giảm của f(x) ta tỡm cỏch điều chỉnh x0 sang sao cho: Thuật toỏn cứ như vậy tiếp diễn trờn một dóy phương ỏn dạng: hay thoó món: (**) Dóy phương ỏn thoó món (**) gọi là phương ỏn xiết chặt dần. Như vậy, thuật toỏn xiết chặt dần nờu trờn là sự kết hợp hai khỏi niệm Gradient và hướng chấp nhận được tại một phương ỏn. Cú rất nhiều phiờn bản thuật toỏn khỏc nhau được đưa ra cho cỏc dạng bài toỏn khỏc nhau. Ta gọi phương phỏp loại này là phương phỏp hướng cú thể. Khi đú cỏc vấn đề cần giải quyết: Vấn đề 1: Tỡm phương ỏn xuất phỏt x0 như thế nào? Rừ ràng việc tỡm phương ỏn xuất phỏt x0 cú liờn quan tới vấn đề khảo sỏt xem tập phương ỏn hay . Đõy là bài toỏn khú, thậm chớ rất khú khi cỏc ràng buộc của bài toỏn cú tớnh chất giải tớch phức tạp. Vấn đề 2: Với mộtđiểm thỡ bằng cỏch nào xỏc định được tại đú khụng cú hướng chấp nhận được giảm của f(x); và nếu tại xk khụng cú hướng chấp nhận được giảm của f(x) thỡ xk cú tớnh chất gỡ? Liệu xk cú phải là lời giải của bài toỏn hay khụng? Nếu tại xk cú hướng chấp nhận được giảm của f(x) thỡ việc điều chỉnh xk sang xk+1 được thực hiện như thế nào? Vấn đề 3: Nếu quỏ trỡnh điều chỉnh trờn diễn ra với dóy thỡ liệu dóy cú hội tụ khụng? Giả sử lim f(xk) tồn tại () và hữu hạn thỡ giới hạn này cú phải là trị tối ưu của f(x) trờn D? Cả ba vấn đề trờn là hiện hữu và rất phức tạp. Với bài toỏn QHFT người ta đó giải quyết được cỏc vấn đề trờn với nhiều lớp bài toỏn cụ thể, nhưng cú thể khẳng định chung là lược đồ điều chỉnh trờn chỉ dẫn đến cực trị địa phương của f(x) trờn D và cú thể khụng hội tụ. Mặc dự điều kiện Kuhn-Tucker đó chỉ ra điều kiện tồn tại nghiệm của bài toỏn quy hoạch lồi, nhưng khụng đưa ra một thuật toỏn cụ thể nào để giải một bài toỏn. Cú rất nhiều phương phỏp khỏc nhau được ỏp dụng cho cỏc bài toỏn quy hoạch lồi với cấu trỳc khỏc nhau. Một trong cỏc thuật toỏn đú thỡ cú thuật toỏn Frank-Wolfe. 2. Giới thiệu thuật toỏn Frank-Wolfe 2.1. Mụ hỡnh toỏn Bài toỏn tổng quỏt cú dạng: (2.1) Trong đú: Khi đú tập phương ỏn là tập lồi đa diện. Thuật toỏn Frank-Wolfe là thuật toỏn dựng để giải bài toỏn QHL với cỏc ràng buộc tuyến tớnh. Cỏc giả thiết của thuật toỏn: D giới nội tức là một đa diện lồi. Hàm f(x) khả vi liờn tục, lồi trờn tập phương ỏn. Bổ sung khỏi niệm hàm lồi: , xỏc định trờn tập D lồi. Khi đú y=f(x) được gọi là một hàm lồi nếu : với ta cú: Đụi khi người ta thay điều kiện a. bằng điều kiện c. sau: , cú nghĩa là tại đều khụng tồn tại hướng chấp nhận được giảm vụ hạn của f(x) tại a. Với cỏc giả thiết nờu trờn thỡ bài toỏn (2.1) luụn cú phương ỏn tối ưu; nếu f(x) lồi ngặt trờn D thỡ phương ỏn tối ưu là duy nhất. 2.2. Thuật toỏn Bước 0: Chọn phương ỏn cú 2 cỏch: Cỏch 1: do cỏc bất phương trỡnh là tuyến tớnh nờn ta cú thể tỡm x0 bằng cỏch giải bài toỏn phụ P(x,xg) khi đú x0 là phương ỏn cực biờn(PACB) Cỏch 2: cú thể tỡm bằng cỏch mũ ngẫu nhiờn , khụng nhất thiết là đỉnh của D. Khi đú x0 khụng phải là PACB. Sau khi chọn được x0 ta giải bài toỏn quy hoạch tối ưu thứ 0: (1) Với giả thiết đó cú bài toỏn thứ 0 luụn cú phương ỏn tối ưu. Gọi là phương ỏn tối ưu của bài toỏn (1). Khi đú cú hai khả năng sau: Th1: Nếu thỡ là phương ỏn tối ưu. Thuật toỏn kết thỳc, x0 là cực trị địa phương nhưng do f(x) là hàm lồi nờn x0 là cực trị địa phương(phần chỳ ý 1) Th2: Nếu thỡ -là hướng chấp nhận được giảm của f(x) tại x0. Khi đú trờn đoạn xột phương trỡnh: với cần tỡm ra điểm mà f(x) nhận giỏ trị nhỏ nhất. Tức là ta đi giải bài toỏn: với (2) là hàm lồi theo , nờn sẽ đạt tại một điểm duy nhất gọi là lời giải của (2) ta nhận được phương ỏn mới: Làm điểm xuất phỏt cho bước sau. Và do phương mới nhận được là phương giảm nờn ta cú: f(x1)<f(x0) cứ tiếp tục như vậy cho tới bước k. Bước k: Khi đú phương ỏn xuất phỏt là xk và bài toỏn quy hoạch tuyến tớnh cần giải là: (2) Phương ỏn tối ưu là Phương nhận được là: cú hai trường hợp xảy ra: Th1: nếu =>xk là phương ỏn tối ưu và thuật toỏn kết thỳc. Thật vậy: Khi bài toỏn QHFT thứ k cú dạng: theo giả thiết f(x) lồi khả vi nờn ta cú: => điều phải chứng minh. Th2: nếu => là phương giảm của f(x). Ta xột Và là hàm lồi theo và đặt: Và cứ tiếp tục như vậy thỡ thuật toỏn hội tụ. Bởi tập xỏc định của nú là tập lồi đa diện lồi. Tuy nhiờn cú thể dừng lại ở một bước bất kỳ,và chấp nhận một sai số nào đú. Qua nội dung của thụõt toỏn ta thấy rằng bản chất của thuật toỏn Frank-Wolfe là biến bài toỏn quy hoạch phi tuyến thành bài toỏn quy hoạch tuyến tớnh thụng qua tuyến tớnh hoỏ từng điểm một. 3. Thớ dụ Giải bài toỏn quy hoạch lồi sau: Lời giải: 2 2 1 0 x* Bước 0: Với điểm xuất phỏt ta cú: Bài toỏn cú dạng: Vỡ là hướng tăng, hướng ngược lại là hướng giảm nờn với tập ràng buộc trờn ta cú phương ỏn tối ưu là Khi đú: với . Khi đú để giải bài toỏn ban đầu ta giải bài toỏn đối với Điều kiện cần: Ta thấy với Bước 1: với ràng buộc Khi đú xột với cú kết quả sau: Bước 2: Bài toỏn mới cú dạng: Kết luận: là PATƯ và trị tối ưu. 4. Phần mềm hỗ trợ: GAMS 4.1. Khỏi quỏt về GAMS Để hỗ trợ cho việc giải cỏc bài toỏn tối ưu một cỏch nhanh nhất và cỏc bài toỏn cú số bước giải lớn, ta cú phần mềm hỗ trợ GAMS. GAMS(General Algebraic Modeling System) là một hệ thống cỏc chương trỡnh giải cỏc bài toỏn quy hoạch toỏn học.GAMS bao gồm nhiều thủ tục khỏc nhau trong đú xin giới thiệu một số thủ tục sau: LP Tỡm nghiệm đỳng của bài toỏn quy hoạch tuyến tớnh MIP Tỡm nghiệm đỳng của bài toỏn quy hoạch nguyờn tuyến tớnh …. Trong đú cú thủ tục NLP( Nonlinear Programming) để giải cỏc bài toỏn QHFT cỏc hàm trơn. 4.2. Cỏc nguyờn tắc khi làm việc với GAMS GAMS yờu cầu phải khai bỏo chớnh xỏc cấu trỳc của chương trỡnh đầu vào. Toàn bộ khai bỏo ghi thành một tệp với phần mở rộng .gms (vớ dụ: bt.gms). Sau khi chạy chương trỡnh, GAMS tạo ra tệp kết quả cú cựng tờn tệp với phần mở rộng .list (vớ dụ: bt.list). Mỗi chương trỡnh cú thể chứa một hay nhiều mụ hỡnh và được giải nhờ cỏc dũng lệnh khỏc nhau. Một chương trỡnh đỳng cú thể chạy nhiều lần với cỏc mụ tả biến theo những kớch thước khỏc nhau. GAMS khụng phõn biệt chữ hoa và chữ thường. 4.3. Dũng lệnh của GAMS Một dũng lệnh của GAMS cú thể bắt đầu ở đầu dũng với một từ khoỏ và kết thỳc bởi dấu “;”. Mỗi dũng lệnh cú thể gồm nhiều cõu lệnh và mỗi cõu lệnh cú thể viết trờn nhiều dũng lệnh khỏc nhau. Nếu một dũng lệnh bắt đầu từ dấu* hoặc $title sẽ được bỏ qua khi thực hiện chương trỡnh và mỏy coi đõy là một chỳ thớch. Một đoạn văn bản nằm giữa cặp lệnh sau là đoạn văn bản chỳ thớch:$ontext.. $offtext 4.4. Những nội dung cơ bản của một chương trỡnh giải bằng GAMS 4.4.1. Khai bỏo biến Biến tự do được khai bỏo với từ khoỏ: variable tờn biến nhón biến; Biến định dạng được khai biến với cỏc từ khoỏ: Free variable tờn biến nhón biến; (với biến liờn tục khụng cú ràng buộc) Positive variable tờn biến nhón biến;(với biến liờn tục khụng õm) Negative variable tờn biến nhón biến;(với biến nguyờn khụng õm) 4.4.2. Khai bỏo cỏc hàm mục tiờu và cỏc ràng buộc Khai bỏo tờn và nhón với từ khoỏ: Equation tờn phương trỡnh 1 nhón,…,tờn ràng buộc 1 nhón,…; Khai bỏo biểu thức xỏc định hàm và cỏc ràng buộc với cấu trỳc sau: Tờn phương trỡnh 1… biểu thức xỏc định phương trỡnh 1; ………………………………………………………….. Tờn ràng buộc 1… biểu thức xỏc định ràng buộc 1; …………………………………………………………... Dấu của cỏc phương trỡnh và bất phương trỡnh trong GAMS: dấu (=): =e= dấu khụng lớn hơn(≤): =l= dấu khụng nhỏ hơn(≤): =g= Cỏc phộp toỏn cơ bản trong GAMS: Phộp cộng: + Phộp trừ: - Phộp nhõn: * Phộp chia: / Phộp lấy luỹ thừa: ** Cỏc hàm thụng dụng trong GAMS: Exp(x): ex Log(x): ln(x) Log10(x): log10(x) Sqr(x): x2 Sqrt(x): Sin(x): sin(x) Cos(x): cos(x) Arctang(x): arctg(x) Power(x): xn 4.4.3. Đặt giỏ trị ban đầu cho cỏc biến Đõy là giỏ trị tạm thời của biến, nú sẽ thay đổi khi chương trỡnh thực hiện. Trong nhiều bài toỏn thuật toỏn sẽ tự động gỏn giỏ trị xuất phỏt cho cỏc biến, cú thể là giỏ trị cận biờn hoặc giỏ trị bằng khụng nếu chỳng thoả món hệ ràng buộc. chắc chắn rằng trong mọi bài toỏn việc chủ động đặt cho cỏc biến giỏ trị ban đầu một cỏch hợp lý(nếu cú thể) sẽ trỏnh được hiện tượng bài toỏn xuất phỏt từ điểm khụng xỏc định hàm mục tiờu hoặc cỏc vộc tơ gradient của hàm đú, khi đú thuật toỏn sẽ cho ta lời giải tốt nhất. Ta cú thể đặt giỏ trị ban đầu cho cỏc biến bằng một trong ba cỏch sau: Đặt giỏ trị đỳng(=) cho biến: tờn biến.l=…; Đặt giỏ trị khụng thấp hơn(≥) cho biến: tờn biến.lo=…; Đặt giỏ trị khụng cao hơn(≤) cho biến: tờn biến.up=…; Đặt tờn cho mụ hỡnh Model tờn mụ hỡnh/ all/; 4.4.5. Chỉ định thủ giải Một bài toỏn QHPT viết trờn GAMS phải được giải bằng thủ tục NPL.Trong GAMS cú ba thuật toỏn nào để giải bài toỏn QHPT đú là: Conopt, Minos và Snopt.Việc sử dụng thuật toỏn nào để giải một bài toỏn QHPT cụ thể tuỳ vào cấu trỳc, đặc điểm của bài toỏn đú. Nếu ta khụng chọn thuật toỏn để giải thỡ thuật toỏn được chỉ định là Conopt. Cấu trỳc lệnh để chỉ thủ tục giải như sau: Solve tờn mụ hỡnh minizing(maximizing) tờn hàm mục tiờu using NPL-; Khai bỏo hiển thị kết quả Nếu như việc giải bài toỏn cho ta lời giải đỳng thỡ ta chọn cỏch hiển thị kết quả đỳng giỏ trị của lời giải bằng lệnh cú cấu trỳc như sau: Display tờn biến 1.l, tờn biến 2.l,…,tờn biến n.l; Nếu như việc giải bài toỏn cho ta lời giải gần đỳng thỡ ta cú thể chọn cỏch hiển thị kết quả thấp hơn hoặc cao hơn giỏ trị đỳng của lời giải bằng lệnh cú cấu trỳc như sau: Display tờn biến 1.lo, tờn biến 2.lo,…,tờn biến n.lo;(thấp hơn) Display tờn biến 1.up, tờn biến 2.up,…,tờn biến n.up;(cao hơn) Chạy và sửa lỗi mụ hỡnh Chạy mụ hỡnh Trước khi yờu cầu GAMS dịch chương trỡnh ta cần ghi lại thành một tệp chẳng hạn bt.gms. Nhấn nỳt Run( biểu tượng mũi tờn màu đỏ) trờn thanh cụng cụ để chỉ thị cho GAMS dịch chương trỡnh và ghi lại kết quả với tệp bt.list. Quỏ trỡnh dịch nếu cú lỗi GAMS sẽ bỏo lỗi chi tiết trong từng dũng lệnh với dũng bỏo lỗi chữ đỏ và nếu click double vào dũng chữ đỏ này dấu nhắc sẽ đặt tại dũng lệnh cú lỗi trong cửa sổ chương trỡnh. Cỏc lỗi và thụng bỏo lỗi Unkown symbol: một biến, một tập hợp,… khụng được khai bỏo hoặc khụng được khai bỏo đỳng quy cỏch. Suffix is missing: toỏn tử đối với biến thiếu phần chỉ định(.l, .up, .lo…). No solution: mụ hỡnh sai hoặc sử dụng thủ tục khụng hợp lệ. =l=, =e=, or =g=oprator expected: lỗi dấu phộp toỏn. Variable wrong type: biến ngoài giới hạn khai bỏo. Log of negative number division by zero gardient too big: loga và căn bậc hai của số õm, chia cho số khụng. Uncontrolled set: một ký hiệu khụng cú trong cỏc tập đó khai bỏo. Endog arguments: mụ hỡnh cú phần tử phi tuyến khụng tồn tại nhưng cú mặt trong chỉ định giải. Ứng dụng GAMS để giải vớ dụ. variable f bien ham muc tieu; positive variable x1 bien x1 khong am x2 bien khong am; equation rb ten rang buoc la rb hsmt ten ham so muc tieu la hsmt; * Khai bao bieu thuc ham so muc tieu va rang buoc cua bai toan rb..2*x1+x2=l=2; hsmt..f=e=sqr(x1-2)+sqr(x2-2); * Dat gia tri dung cho phuong an xuat phat x1.l=0; x2.l=0; * Dat ten mo hinh la qhft model qhft/all/; * Lua chon thu tuc de giai solve qhft minizing f using nlp; * Lua chon cach thuc hien thi ket qua Display x1.l,x2.l,f.l; Kết quả: 18 VARIABLE x1.L = 0.400 bien x1 khong am VARIABLE x2.L = 1.200 bien khong am VARIABLE f.L = 3.200 bien ham muc tieu Như vậy kết quả chạy mỏy cũng cho ta kết quả giống giải bằng tay. Kết luận Trờn đõy là một số nghiờn cứu và tổng kết của em về thuật toỏn Frank-Wolfe. Qua nội dung trờn, ta thấy thuật toỏn Frank-Wolfe đó đúng gúp một phần vào việc giải quyết cỏc bài toỏn tối ưu. Đồng thời với phần mềm chuyờn dụng GAMS chỳng ta đó mở rộng thờm được cỏc bài toỏn QHFT, rỳt ngắn thời gian giải bằng tay. Tuy nhiờn với những giả thiết mà thuật toỏn Frank-Wolfe đưa ra đặc biệt là giả thiết: “cỏc ràng buộc phải là tuyến tớnh”; đú là một hạn chế của thuật toỏn này. Bởi vỡ, thực tế khụng phải lỳc nào cỏc ràng buộc cũng là cỏc ràng buộc tuyến tớnh. Nờn ứng dụng của nú vào trong thực tế cũng cũn hạn hẹp. Hoặc muốn ỏp dụng thuật toỏn này thỡ phải tốn thời gian quy đổi cỏc ràng buộc phi tuyến về ràng buộc tuyến tớnh. Do đú, để trang bị cho mỡnh kiến thức giải cỏc bài toỏn QHFT, chỳng ta cần tỡm hiểu nhiều phương phỏp khỏc như: thuật toỏn quy hoạch lồi tổng quỏt, quy hoạch lồi toàn phương vv… Bài viết của em cú gỡ sai sút kớnh mong thầy giỏo thụng cảm và mong thầy đúng gúp ý kiến để bài viết của em được hoàn thiện hơn. Cuối cựng, em xin chõn thành cảm ơn thầy giỏo Ngụ Văn Mỹ đó tận tỡnh giỳp em hoàn thành đề ỏn mụn học này./. Danh mục tài liệu tham khảo Bài giảng tối ưu hoỏ – Tỏc giả: Ngụ Văn Mỹ, khoa Toỏn kinh tế. Giỏo trỡnh: Mụ hỡnh toỏn ứng dụng – Tỏc giả: Ngụ Văn Thứ, khoa Toỏn kinh tế. Toỏn cao cấp dành cho cỏc nhà kinh tế - Phần 2: Giải tớch toỏn học – Tỏc giả: Lờ Đỡnh Thuý. Trang web: www.goole.toiưuhoa.vn