Quy tắc 37%

Qui luật 37% (và ứng dụng cho việc tìm người yêu)

(Tác giả: Nguyễn Văn Tuấn – Nguồn: http://tuanvannguyen.blogspot.com)

Nghĩ lại trong thống kê học có những hằng số hết sức lí thú và quan trọng. Chúng ta đã biết những con số như 0.05 (trị số P), 1.96 (hằng số của phân bố chuẩn) có ảnh hưởng đến cuộc sống như thế nào. Nhưng có lẽ ít ai biết đến qui luật 37%. Đây là một qui luật mới được tái khám phá, nhưng có nhiều ứng dụng trong y khoa, khoa học, tìm nhân viên, thậm chí … tình yêu.

Qui luật 37% bắt đầu từ một vấn đề hết sức nan giải, có tên là “The Secretary Problem” (Vấn đề Thư kí) (*). Vấn đề này được phát biểu như sau:

  • Có một vị trí thư kí trống;
  • Công ti có n ứng viên xin vào vị trí đó;
  • Các ứng viên được phỏng vấn tuần tự, nhưng thứ tự hoàn toàn ngẫu nhiên, và do đó, xác suất người thích hợp nhất là 1/n;
  • Một khi ứng viên được phỏng vấn và bị từ chối, thì ứng viên đó sẽ không được quay lại tham gia vào qui trình tìm;
  • Tương tự, khi một ứng viên được chấp nhận, thì qui trình tìm người thư kí sẽ chấm dứt.

Vấn đề là n có thể lớn, và công ti không có đủ thì giờ cũng như tài nguyên để phỏng vấn tất cả. Do đó, câu hỏi đặt ra là công ti cần phải phỏng vấn bao nhiêu người (k) để có xác suất chọn đúng người cao nhất.

Lời đáp cho câu hỏi này hoá ra hết sức đơn giản: 36.79%, hay làm chẵn là 37%. Nói cụ thể hơn, công ti nên phỏng vấn 37% số ứng viên đầu tiên, bỏ qua tất cả số ứng viên đó, và chọn ứng viên đầu tiên sau 37% có kinh nghiệm tốt hơn những ứng viên trước. Đáp số này còn cho phép công ti kết luận rằng xác suất mà công ti chọn được ứng viên tốt nhất là 37%. Con số 37% thật ra là 1/e (e ở đây là hằng số Euler, tức là 2.718). Chi tiết tính toán (không khó) có thể tham khảo qua trang này (1).

Lịch sử cận đại của Vấn đề Thư kí có lẽ bắt đầu từ thập niên 1950s, nhưng người đầu tiên giải vấn đề này thì chưa rõ. Trên tập san khoa học, người đầu tiên chứng minh Qui luật 37% là nhà thống kê học lừng danh Dennis Lindley (2, hình) vào năm 1961. Mới đây, Qui luật 37% được tái khám phá qua cuốn sách rất thú vị có tựa đề là “The Mathematics of Love” (Toán học của tình yêu) của tác giả Hannah Fry (University College of London), và cuốn Risk Savvy của Giáo sư tâm lí học Gerg Gigerenzer (một “hero” của tôi). Đây là hai cuốn sách được viết cho đại chúng, rất dễ hiểu, rất giải trí cho những dịp nghỉ hè. Nhưng tác giả cũng tự chứng tỏ là những người rất am hiểu về xác suất trong cuộc sống, đặc biệt là áp dụng lí thuyết xác suất trong … tình yêu.

Dennis Lindley

Thật vậy, Qui luật 37% cũng có thể ứng dụng trong việc tìm người bạn đời. Như các bạn có thể đoán được, theo Qui luật này, bạn không nên kết hôn với người mình mới quen lần đầu, mà phải cố gắng làm quen và “đánh giá” một số n người. Sau đó, bạn làm quen và “tìm hiểu” n/e người, và chọn người sau n/e có phẩm hạnh tốt nhất so với n/e người kia.

Giả dụ như bạn có “cỡ mẫu” là 50 người (hơi nhiều!), bạn nên làm quen với 18 người trước để thu thập thông tin, sau đó bạn chọn người 19 trở đi có phẩm hạnh tốt hơn 18 người kia. Do đó, “người tình trăm năm” của bạn có thể là người 19, hay 20, hay thậm 25. Dĩ nhiên, sau khi đã chọn được người thích hợp sau người thứ 18 thì phải ngưng, không cần tìm thêm nữa.

Một khó khăn là xác định bạn cần bao nhiêu n ứng viên. Chúng ta có thể áp dụng công thức ước tính cỡ mẫu để xác định n với một sai số mẫu e%. Tuy nhiên, việc chọn bạn tình là chuyện rất nghiêm trọng, nên có thể sai số mẫu phải hạ thấp xuống cỡ e = 1% hay 2%.

Dĩ nhiên, trong giới nghiên cứu y khoa “hardcore”, thì chẳng ai mà không biết đến Qui luật 37%, vì nó đã từng được lí giải và ứng dụng trong thực tế nghiên cứu lâm sàng. Trong y khoa học, qui luật này có tên là “Stopping rule” và được ứng dụng trong các nghiên cứu lâm sàng giai đoạn I, nhưng cái “twist” hơi phức tạp hơn một chút.

Cố nhiên, Qui luật 37% không chỉ ứng dụng trong y khoa, tìm người bạn tình tối ưu, hay tìm nhân viên, mà còn được ứng dụng trong nhiều lĩnh vực và tình huống khác, tuỳ vào sự sáng tạo của người ứng dụng. Nên nhớ rằng Qui luật 37% cho chúng ta kết quả với xác suất tối ưu chỉ 37%, tức vẫn có thể sai 63%. Nhưng với nhiều ứng viên mà chúng ta không biết gì về họ, thì Qui luật 37% vẫn là giải pháp tốt nhất và rẻ nhất để tìm đúng người.

Một ứng dụng sáng tạo khác của Qui luật 37% là tìm tuổi thành hôn tối ưu. Nếu độ tuổi thành hôn trong khoảng 18-40, chúng ta có khoản thời gian 22 năm để chọn. Như vậy Qui luật 37% cho biết chúng ta nên chọn tuổi 27, tức là sau tuổi 26 (0.37*22 + 18). Bởi vì nếu thành hôn trước tuổi 26 sẽ có thể sẽ bỏ mất các ứng viên tốt.

Bởi vì bản chất của kết quả vẫn là xác suất, nên cần phải xem xét các khía cạnh dương tính giả (tức chọn sai người) và âm tính giả (tức bỏ sót người tốt), nhưng đây là chủ đề của một cái note khác. Hi vọng rằng qua Qui luật 37% các bạn đã tiết kiệm thì giờ để tìm nhân viên hay tìm người tình trăm năm.

===

(1) https://plus.maths.org/content/solution-optimal-stopping-problem

(2) Dennis Lindley (1923-2013) là một trong những nhà thống kê học distinguished nhất trên thế giới, đứng chung hàng với các “đại thụ” như David Cox, C. R. Rao, H. Jeffreys, Sam Wilks, I. J. Good, Fred Mosteller. Khác với những người cùng thời theo trường phái tần số, Giáo sư Lindley theo trường phái Bayes và có những đóng góp quan trọng. Trong một bài báo năm 2008 trên Stat Sci, Dennis Lindley đặt nền móng cho khoa học thống kê trong thế kỉ 21: thống kê học là một khoa học của bất định; bất định nên được “đo” bằng xác suất; sự bất định của dữ liệu là điều kiện của tham số; và do đó, suy luận thống kê phải theo trường phái … Bayes. Phải có trải nghiệm thực tế mới thấy ý tưởng này của ông rất đúng và rất thích hợp.


Xem thêm: Toán học chứng minh nếu bạn đang ở tuổi 26, đây là thời điểm tốt nhất để lấy vợ



(*) Trường hợp riêng của Bài toán dừng tối ưu (Optimal stopping problems) – có liên quan đến định giá các quyền chọn kiểu Mỹ.

———–&&&———–

Giải Nevanlinna 2010

Giải Nevanlinna 2010

(Tác giả: Vũ Hà Văn – Nguồn: vuhavan.wordpress.com)

Giải Nevalina năm nay được trao cho bạn Spielman (đại học Yale). Bài dưới đây nói qua về công trình của Spielman. Sáng nay vừa mở máy tính ra thì bạn Tào đã làm ngay hai bài dài ngoằng nói về tất cả các giải thửơng của IMU, bạn nào quan tâm rất nên đọc. Bác Sơn Đàm cũng viết một bài rất hay về các công trình được giải liên quan đến vât lý.

Tôi viêt thêm về chủ đề của Spielman vì chủ đề này có những bài toán mở (open problem) tương đối dễ hiếu và thú vị. Bạn có thể (và nên) đọc song song với bài của Tào, và tham khảo thêm bài của Spielman và Teng trên proceeding của IMU 2002, bài này cũng rất dễ đọc và không cần nhiều kiến thức chuẩn bị.

Công trình tôi muốn nói tới là “Smoothed Analysis” của Spielman và Teng. Hai bạn này chú trọng đến simplex algorithm, nhưng tốt hơn là ta phát biểu khái niệm này một cách tổng quát.

Mục đich của bạn Spielman và Teng là phân tích hiện tượng sau:

Có một dữ liệu (data) M, thường được biểu diến dưới dạng một ma trận rất to. Ta muốn chạy một phép toán T với input là M. ̣Trường hợp cụ thể mà Spielman-Teng phân tích là simplex algorithm rất thông dụng trong quy hoạch tuyến tính.

Câu hỏi cơ bản nhất trong lý thuyết tính toán: Máy chạy mất bao lâu ?

Để trả lời câu hỏi này, người ta thường phân tích trường hợp “xấu nhất” (worst case analysis-worst matrix M). Câu trả lời cho simplex algorithm, và tương đối nhiều phép toán khác, là “Rất lâu !! Chờ nhé !!” (exponential time). Các nhà toán học đã viết ra một số ma trận cụ thể với kích thước không lớn lắm mà phép toán này sẽ phải chạy hàng nghìn năm (trên máy tính xịn) mới ra kết quả.

Nhưng, trong thực tế, simplex algorithm rất hỗn. Nó cười khảy vào các kết quả trên và luôn chạy băng báng. Điều này làm các nhà toán học rất tức tối, phải làm cho ra ngô ra khoai. Muốn vậy, phải dùng một ít xác suất.

Sau một số lớn các cách giải thích chưa được hoàn toàn trọn vẹn, cách đây chừng 10 năm, Spielman và Teng đưa ra cách giải thích sau: Trong tính toán luôn luôn có tiếng ồn, sai số (noise). Khi bạn đo một dữ liệu, mặc dầu kết quả thực là M, nhưng trên thực tế không bao giờ ta nhận được M. Vậy máy tính sẽ không chạy trên input M, mà chạy trên input M+N, trong đó N là sai số. Sai số này thường được biếu diến dưới dạng một ma trận ngẫu nhiên.

Định lý chính của Spielman và Teng nói là nếu N là một ma trận Gauss và M là một ma trận bất kỳ ( cùng có kích thước m \times n ) thì với xác suất cao, simplex algorithm với input M+N sẽ chạy nhanh (polynomial time).

Ma trận Gauss là ma trận ngẫu nhiên với các phần tử là biến Gauss độc lập. Xác suât cao là xác suất tiến tới 1 nếu m, n tiến tới vô cùng. Polynomial time là (m+n)^C, với C là một hằng số.

Cách giải thích của S-T rất hợp lý, vì nó cho phép M có thể là bất kỳ ma trận nào, kể cả những ma trận xấu tính nhất
đến từ worst case analysis. Tôi thấy nó thú vị vì thường trong các ứng dụng dùng đén thuật toán, tiếng ồn và sai số luôn là thủ phạm của các vụ rắc rối khi ta cần tính một cái gì cụ thể, nhưng ở đây nó lại có vai trò “tích cực”. Sai số làm cho các ma trận xấu tính không thể trở nên quá xấu.

Đây là ý tưởng chính trong công trình dẫn tới giải Nevalina của Spielman và giải Godel và Fulkerson chung cho hai người.

Định lý S-T được phát biểu dưới dạng phép toán (algorithmic), vậy mấu chốt toán học của nó ở đâu ? Quan sát quan trọng nhất của S-T có lẽ là bổ đề sau.

Để phát biểu bổ đề này, ta cần một vài khái niệm. Trước hết, để đơn giản hóa vấn đề, ta giả sử cả MN là ma trận vuông (n \times n). Ma trận M có thể coi là một ánh xạ tuyến tính từ R^n đến R^n. Ánh xạ này sẽ làm biến dạng không gian, cụ thể nó sẽ biến hình cầu thành một hình ellip. Hình ellip đại loại giống quả trứng, có trục dài trục ngắn. Độ dài của các trục này là các singular values của M (trong trường hợp M là ma trận đối xứng thì đó là giá trị tuyệt đối của các giá trị riêng). Một ma trận gọi là “tốt” nếu tỷ lệ giữa trục dài nhất và trục ngắn nhât tương đối nhỏ và “xấu” nếu tỷ lệ này lớn. (Nói nôm na là ma trận tốt thì trứng tròn còn ma trận xấu thì trứng dài.) Tỷ lệ này,
ký hiệu là \kappa (M), được gọi là “condition number” của M và nó quyết định thời gian và độ chính xác của các thuật toán cơ bản chạy trên M.

Một ma trận trong trường hợp xấu nhất có thể có condition number rất lớn (thậm chí là vô cùng nếu bậc của ma trận nhỏ hơn n; khi đó trứng sẽ thiếu mất một
hay nhiều chiều, không xơi được).

Bổ đề (S-T). Nếu N là một ma trận Gauss và M là một ma trận bất kỳ thì với mọt hằng số
0″ src=”http://s0.wp.com/latex.php?latex=C+%3E0&bg=ffffff&fg=333333&s=0″ alt=”C >0″ />

P (\kappa (M+N)  \ge n^C \| M + \sqrt n \| ) \le n^{-C +1/2}.

Nội dung của bổ đề này là dù M có láo cỡ nào, chỉ cần nó không quá to, thì trong phần lớn các trường hợp M+N không thể quá xấu. Ngay cả khi \kappa (M) là vô cùng, thì với xác suât xấp xỉ 1, \kappa (M+N) vẫn nhỏ hơn n \|M\| (bất kỳ hàm polynomial nào của n cũng đủ tốt cho ứng dụng). Bạn có thể đọc kỹ thêm trong bài ICM của S-T.

Chứng minh bổ đề trên không khó. Nhưng phần phân tich thuật toán khá phức tạp; một cách chứng minh đơn giản hơn được đưa ra sau đó bởi Vershynin.

Bây giờ nói tới bài toán mở. Ý tưởng của S-T rất hay. Nhưng giả thuyêt N là ma trận Gauss hơi mạnh. Trong các dữ liệu cụ thể, thường các số liệu là sổ nguyên, hoặc được viêt dưới dạng thập phân với một vài chữ số sau dấu phẩy. Bản thân máy tính cũng chỉ làm việc được với các số biểu diến được một cách hữu hạn mà thôi. Các số được sampled từ phân bố Gauss thì luôn là vô tỷ, thậm chí không phải số đại số. Vậy giả thuyết gần với thực tế hơn là các phần tứ của N có phân bố rồi rac trên một số hữu hạn điểm.

Trường hợp đơn giản (vầ đặc trưng) nhất là khi N có phân bố Bernoulli, các phần tứ là 1 hoặc -1 với xác suất 1/2. Bài toán mở ở đây là chứng minh Định lý S-T cho trường hợp này. Vấn đề này bạn Spielman có nói với tôi cách đây chừng năm năm, nhưng hiên nay hình như vẫn chưa ai giải.

Bước đầu tiên là chứng minh bổ đề S-T cho ma trận Bernoulli. Vấn đề này rất gần với Universality (hay Invariance) principle trong toán vật lý (xem bài của Tào về Smirnov). Nôm na mà nói, thường ta tin rằng một định lý đúng với một mô hình (hay phân bố) ngẫu nhiên nào đó thì cũng đúng với các mô hình khác. Nhưng chứng minh điều này nói chung là khó, vì thường các cách chứng minh hay dùng các tính chất cụ thể của phân bố đã cho, chẳng hạn cách ST chứng minh bổ đề dùng tính chất là phân bố Gauss trong không gian nhiều chiều có tính đối xứng rất cao (rotational invariant). Tính chất này không đúng trong trường hợp Bernoulli. Một bài toán con của bổ đề S-T trong trường hợp Bernoulli là bài toán khá nổi tiếng sau:

(Định lý Komlos, 1966): Với n  \rightarrow \infty, P(\kappa (N) =\infty) \rightarrow 0.

Định lý này nói rằng một ma trận ngẫu nhiên \pm 1 có bậc đầu đủ với xắc suất gần 1. Một cách khác nữa, nếu ta lấy n đỉnh ngẫu nhiên của hình lập phương \{-1,1 \}^n thì các đỉnh này không nằm trên cùng một siêu phẳng.
Trong trường hợp ta lấy n điểm từ một hình cầu, định lý này hiển nhiên đúng. Chẳng có lý do gì để n điểm này nằm trên cùng một mặt phẳng. Nhưng với các phân bố rời rạc, thì chuyện lại khác.

Bạn có thể xem các mở rộng của bổ đề S-T tại đây. Công cụ chủ yểu để mở rộng bổ đề này đến từ Additive Combinatorics. Hiện vẫn còn một số vấn đề mở rất thú vị với bổ đề này. Về Định Lý S-T,chỗ vướng mắc, như tôi còn nhớ, là trong phần phân tích thuật toán, có dùng những tính chất khác khá mạnh của phân bố Gauss trong môt số Lemma mang tính kỹ thuật.

(Rolf Nevanlinna Prize : http://www.mathunion.org/general/prizes/nevanlinna/details )

————-&&————-

Hoàng Tuỵ và bộ “Kinh thánh” của tối ưu toàn cục

Hoàng Tuỵ và bộ “Kinh thánh” của tối ưu toàn cục

(Tác giả: Hàm Châu – Nguồn: bee.net.vn)

Giới toán học thế giới coi ông là “cha đẻ của tối ưu toàn cục”, người mở đường cho một chuyên ngành toán học mới.

Hoàng Tuỵ sinh ngày 27/12/1927, vậy mà, ngay từ mấy tháng đầu năm 1997, giới toán học quốc tế trong chuyên ngành của ông đã sốt sắng chuẩn bị một hình thức đầy ý nghĩa mừng ông thọ 70 tuổi: tổ chức một cuộc hội thảo quốc tế ở Thụy Điển.

Đầu năm 1997, tôi được anh bạn tiến sĩ khoa học kia đưa cho xem bản thông báo sau đây mà anh nhận được qua Internet:

Nhân dịp mừng sinh nhật lần thứ 70 của GS Hoàng Tuỵ, người đã có công trình tiên phong trong lĩnh vực tối ưu toàn cục và quy hoạch toán học tổng quát, một cuộc hội thảo ba ngày sẽ được tổ chức tai Viện Công nghệ Linkoping, Thuỵ Điển với chủ đề: Tìm tối ưu từ địa phương đến toàn cục.”

Bản thông báo cho biết đây là cuộc hội thảo nhằm vinh danh GS Hoàng Tuỵ (Workshop in Honor of Prof. Hoang Tuy) diễn ra tại Thuỵ Điển từ ngày 20 đến 22/8/1997. Các nhà toán học muốn dự cần gửi bản tóm tắt công trình của mình chậm nhất vào ngày 1/6/1997 để kịp tập hợp in thành một cuốn sách đề tặng GS Hoàng Tuỵ (dedicated to Prof. Hoang Tuy).

Sau khi hội thảo kết thúc, cuốn sách được Kluwer Academic Publishers, cũng là một nhà xuất bản lớn về khoa học và kỹ thuật trên thế giới, ấn hành ở Boston (Mỹ), London (Anh), Dordrecht (Hà Lan) và nhiều nơi khác.

Năm 2007, mừng GS Hoàng Tuỵ 80 tuổi, giới toán học quốc tế lại tổ chức tại Pháp một cuộc hội thảo về tối ưu toàn cục để vinh danh ông một lần nữa.

Hoàng Tuỵ được coi là “cha đẻ của tối ưu toàn cục” (the father of Global Optimization). Ngày nay, bất cứ ai trên thế giới muốn đi vào chuyên ngành này, đều phải học những điều đã trở thành kinh điển như Tuy’s cut (lát cắt Tuỵ), Tuy-type algorithm (thuật toán kiểu Tuỵ), Tuy’s inconsistency condition (điều kiện không tương thích Tuỵ…

Cuốn sách toán tiếng Anh do GS Hoàng Tuỵ viết chung với GS Reiner Horst (CHLB Đức) nhan đề Global Optimization – Deterministic Approches (Tối ưu toàn cục – tiếp cận tất định) dày 694 trang, được nhà xuất bản Springer – Verlag in lần đầu năm 1990, lần thứ hai năm 1993, lần thứ ba (có sửa chữa) năm 1996. Đây là cuốn sách chuyên khảo đầu tiên có hệ thống về chuyên ngành này. Do vậy, GS Hiroshi Konno, người Nhật Bản, mới nhận xét: Cuốn sách ấy “được nhiều nhà nghiên cứu đánh giá là cuốn Kinh thánh của chuyên ngành tối ưu toàn cục” (was appreciated by many researchers as the Bible of global optimization), và, trên thực tế, nhiều người bắt đầu các công trình nghiên cứu nghiêm túc của mình về tối ưu toàn cục là nhờ “được cuốn sách mở đường ấy cổ vũ” (motivated by this path-breaking book).

Cách đây mấy năm, tờ báo điện tử Operation-Research Bulletin (Bản tin Vận trù học), diễn đàn của các nhà vận trù học châu Á – Thái Bình Dương, số tháng 9/2002, đã ra một chuyên đề về GS Hoàng Tụy, gồm nhiều bài và ảnh: bài của TS Takahito Kuno phỏng vấn GS Hoàng Tuỵ; bài hồi ức của TS Taketomo Mitsui nhan đề Prof. Hoang Tuy – A Prominent Applied Mathematician (GS Hoàng Tuỵ – Nhà toán học ứng dụng lỗi lạc); bài hồi ức của GS Hiroshi Konno nhan đề A Tribute to Prof. Hoang Tuy (Để tỏ lòng tôn kính GS Hoàng Tuỵ); cùng một số bức ảnh GS Tuỵ chụp chung với các nhà toán học Nhật Bản, do TS Takahito Kuno chọn và giới thiệu dưới tiêu đề Santa Claus Coming from a Southern Country (Ông già Noel đến từ một đất nước phương nam). Chẳng là vì GS Tuỵ có mái tóc trắng như tuyết và cứ mỗi lần đến Nhật Bản lại mang tới cho các nhà toán học xứ sở hoa anh đào nhiều ý tưởng mới hấp dẫn như những món quà mà Ông già Noel mang lại. Qua số báo, các nhà toán học Nhật Bản muốn tỏ bày lòng ngưỡng mộ đối với nhà toán học Việt Nam lão thành.

————-&&————-

GS Hoàng Tụy được trao giải thưởng toán học Constantin Caratheodory

http://dantri.com.vn/c728/s728-520760/gs-hoang-tuy-duoc-trao-giai-thuong-toan-hoc-constantin-caratheodory.htm

Tối ưu trong khoa học kỹ thuật kinh tế và đời sống

Tối ưu trong khoa học kỹ thuật kinh tế và đời sống

(Tác giả: Hoàng Tụy – Nguồn: tiasang.com.vn)

Năm 1969, hơn một tháng trước khi Hồ Chủ tịch qua đời, tôi được vinh dự và may mắn gặp Chủ tịch và Thủ tướng Phạm Văn Đồng. Sau buổi làm việc bàn về các biện pháp cải tiến một số dịch vụ trong thành phố lúc bấy giờ, khi bắt tay ra về Chủ tịch căn dặn chúng tôi hãy cố gắng áp dụng vận trù học. Suốt 40 năm qua, tôi không bao giờ quên được hình ảnh vị Chủ tịch nước cho đến những ngày cuối cùng trong đời vẫn còn quan tâm thiết tha tới việc ứng dụng các phương pháp khoa học vào những vấn đề cụ thể phục vụ đời sống của dân. Tuy vậy, đến hôm nay tôi vẫn chưa hết day dứt vì sự thể câu chuyện sau đó đã không có sự tiếp tục xứng đáng. Nếu trước đây hơn 30 năm, trong hoàn cảnh chiến tranh, nước ta vẫn đi đầu ở Đông Nam Á về giáo dục, y tế và một số lĩnh vực khoa học (trong đó có vận trù học và lý thuyết tối ưu) thì ngày nay chúng ta không còn giữ được vị trí đó, thậm chí có mặt đã tụt hậu so với họ và có xu hướng ngày càng tụt hậu xa hơn. Đã đến lúc không còn chỗ để thụt lùi thêm nữa. Tình hình phát triển của khoa học kỹ thuật ngày nay, xu thế toàn cầu hóa và cạnh tranh kinh tế ngày càng gay gắt đang đặt ra cho chúng ta một sự lựa chọn khắc nghiệt: hiệu quả, tối ưu hoặc là sa sút, là lụn bại. Những ý kiến dưới đây xin được phát biểu trong nỗi niềm trăn trở đó.

Lý thuyết tối ưu là một ngành toán học đang phát triển mạnh, và ngày càng có nhiều ứng dụng quan trọng trong mọi lĩnh vực khoa học, kỹ thuật, công nghệ và quản lý hiện đại. Cuộc cách mạng công nghệ thông tin tạo điều kiện thuận lợi chưa từng có để ứng dụng tối ưu hóa một cách rộng rãi và thiết thực. Ngược lại nó cũng nêu lên nhiều vấn đề mới, quan trọng, về khoa học kỹ thuật, công nghệ, quản lý, không thể xử lý tốt nếu không sử dụng công cụ và tư tưởng tối ưu hóa.

Việt Nam là một trong số các nước nghèo nhưng đã ứng dụng vận trù học (chủ yếu là các phương pháp tối ưu) sớm nhất. Những năm 60 đã có thời ngành khoa học này được phổ biến khá rộng rãi ở Miền Bắc, khiến các từ vận trù, tối ưu, hệ thống, đã đi vào ngôn ngữ hàng ngày của người dân lúc bấy giờ. Sau đó, những năm 70, vượt qua nhiều khó khăn trở ngại, các phương pháp tối ưu bắt đầu được nghiên cứu vận dụng vào kế hoạch hóa và quản lý kinh tế vĩ mô. Song, rất tiếc vì những nguyên nhân không thuộc quyền chủ động của anh em khoa học, công việc chưa thu được kết quả cụ thể thì đã không thể tiếp tục duy trì mà ngày càng sút kém qua cuộc khủng hoảng kinh tế xã hội của đất nước rồi gần như tan rã khi chuyển sang kinh tế thị trường. Tuy vậy, cũng phải ghi nhận rằng những nghiên cứu về hệ thống và tối ưu thời kỳ đó đã có đóng góp tích cực vào việc xây dựng một cách nhìn thực tế và một tiếp cận khoa học đối với các vấn đề kinh tế xã hội nhằm đưa đất nước vượt qua các khó khăn, ra khỏi cuộc khủng hoảng. Bây giờ nhìn lại có thể thấy rõ những ý kiến phân tích và các kiến nghị về cải cách quản lý kinh tế của giới toán học thời kỳ đó (như những ý kiến đóng góp ở Đồ Sơn trước Nghị quyết VI (1979), hay những ý kiến đóng góp về chiến lược kinh tế xã hội những năm (1985 – 1989)) là rất đúng đắn và có tác dụng tích cực.

Hơn hai thập kỷ qua, ngành khoa học về các phương pháp tối ưu đã có những bước tiến lớn. Thông qua các phần mềm ứng dụng, quy hoạch tuyến tính đã trở thành công cụ cơ bản của các lĩnh vực khoa học, kỹ thuật, công nghệ, quản lý, thiết kế kỹ thuật, cung cấp dịch vụ nhất là từ khi máy vi tính được phổ biến rộng rãi và có tính năng ngày càng mạnh. Nhờ các thành tựu đột phá của Khachian (1978) và Karmarkar (1983), ngày nay người ta đã có những phương pháp điểm trong (interior point algorithm – Diễn Đàn chú thích), hữu hiệu hơn “phương pháp đơn hình” cổ điển, để giải những bài toán cực lớn trong khoa học, kỹ thuật và quân sự hiện đại (chẳng hạn một bài toán 150.000 biến với 12.000 ràng buộc giải bằng phương pháp Karmarkar chỉ mất 1 giờ trong khi một bài toán tương tự với 36000 biến và 10000 ràng buộc giải theo phương pháp đơn hình mất 4 giờ).

Mặt khác thế giới chúng ta đầy rẫy những hiện tượng phi tuyến và những quan hệ qua lại phức tạp. Trước đây do tầm nhìn hạn hẹp về cả không gian lẫn thời gian nên mọi cái xung quanh ta đều được coi như bằng phẳng, biến thiên tỉ lệ, quan hệ giản đơn mỗi chiều nhưng khi mở rộng tầm mắt và đi sâu hơn vào bản chất sự vật thì ở đâu cũng gặp những quan hệ chằng chịt phức tạp, và các hiện tượng phi tuyến, toàn cục. Càng đi sâu vào tố chức của xã hội, thiên nhiên, vũ trụ ; càng phân tích hoạt động của máy tính, bộ não ; càng thấy sự phổ biến của cấu trúc tổ hợp, rời rạc, cấu trúc mạng phân cấp, liên kết, và phát hiện khả năng biểu diễn mọi hình ảnh âm thanh bằng số. Chính trên nền tảng đó mà cuộc cách mạng số hóa đã bùng nổ và đang làm đảo lộn toàn bộ công nghệ hiện đại đồng thời thúc đẩy sự phát triển mạnh mẽ và liên tục suốt 20 năm qua của các ngành tối ưu phi tuyến , tối ưu rời rạc (tổ hợp), và gần đây nữa là tối ưu toàn cục. Nếu giữa những năm 60 các bài toán phi tuyến khoảng mười biến còn được coi là cỡ quá lớn, rất khó giải, thì nay nhiều bài toán hàng trăm, hàng nghìn biến có thể được xử lý dễ dàng. Cách đây ba mươi năm bài toán “người du lịch” còn được xem như chỉ có tính chất thuần túy lý thuyết, vì chỉ với 50 điểm bài toán đã vượt quá khả năng tính toán thực tế lúc bấy giờ. Thế mà đến giữa những năm 80 đã trở thành bài toán thường ngày trong công nghệ sản xuất vi mạch, với số điểm phải đi qua lên tới mấy vạn hay mấy chục vạn thậm chí cả triệu. Còn nhiều bài toán tối ưu khác, vốn có vẻ viển vông xa thực tế đã có ứng dụng rất thiết thực trong công nghiệp sản xuất vi mạch, rô bốt, viễn thông và nhiều ngành công nghiệp quan trọng khác.

Điều thú vị là bài toán “quy hoạch lõm” mà tôi bắt đầu nghiên cứu năm 1964, xuất phát từ sự suy ngẫm trên các vấn đề giao thông vận tải hồi ấy ở một đất nước kinh tế lạc hậu lại đang có chiến tranh, không ngờ đã có ứng dụng trong nhiều vấn đề kinh tế, kỹ thuật hiện đại. 12 năm sau, trong Hội thảo quốc tế lần thứ IX về quy hoạch toán học ở Budapest năm 1976, mấy bạn đồng nghiệp Nhật ở hãng NEC đã thông báo cho biết họ đã gặp bài toán ấy trong ngành công nghiệp của họ và đã dựa vào các ý tưởng trong bài nghiên cứu của tôi để xử lý. Ngày nay quy hoạch lõm có nhiều ứng dụng và đã trở thành bài toán cơ bản của lý thuyết tối ưu toàn cục tất định. Song song với nó và ít nhiều nhờ sự kích thích của nó, nhiều phương pháp tối ưu toàn cục phi tất định cũng đã ra đời, như phương pháp phỏng tôi (Diễn Đàn : thuật ngữ toán tối ưu : recuit simulé, hay simulated annealing), phương pháp di truyền, phương pháp tabu.

Như chúng ta đều biết, bài toán tối ưu đặt ra trong bất cứ hoạt động nào mà ở đó việc thực hiện mục tiêu phải tuân thủ những điều kiện ràng buộc nhất định và phải hao tốn phương tiện, cho nên cần tìm ra phương án hoạt động sao cho thực hiện được mục tiêu với hiệu quả cao nhất, với những hao tốn phương tiện thấp nhất. Những tình huống như thế rất phổ biến trong các hoạt động kinh tế, kỹ thuật, tổ chức, quản lý. Song ít người biết rằng các phương pháp tối ưu còn được ứng dụng trong nhiều lĩnh vực khoa học kỹ thuật khác nữa, mà thoạt nhìn tưởng chẳng có quan hệ gì đến tối ưu.

Chẳng hạn, trong y học, sau khi thu thập các dữ liệu quan sát về những trường hợp ung thư ở một số bệnh nhân, để phân tích mớ dữ liệu ấy và tìm ra quy luật giúp cho sự chẩn đoán bệnh chính xác nhanh chóng, mà ít phải dùng đến những phương pháp kiểm tra vật lý nặng nề tốn kém; người ta biểu diễn mỗi trường hợp bằng một điểm trong không gian các thông số cơ bản, rồi dùng phương pháp chia cụm để phân tích, rút ra kết luận giúp chẩn đoán trường hợp nào chắc chắn ung thư, trường hợp nào chỉ là u lành. Đó là một bài toán cụ thể về khai thác dữ liệu mà về hình thức toán học là đồng nhất với bài toán định vị (lựa chọn vị trí tối ưu), tức cũng là một bài toán tối ưu toàn cục nằm trong đề tài nghiên cứu mươi năm nay của các chuyên gia tối ưu. Một lần, năm 1994 tôi có dịp trình bày tiếp cận mới đối với bài toán này trong xêmina tại Học viện Công nghệ Tokyo thì chỉ sau đó vài hôm nhận được thư của hãng Toshiba mời đến giảng lại vấn đề đó cho nhóm nghiên cứu của họ, chứng tỏ bài toán đó đang trong tầm theo dõi của các nhà công nghệ điện tử.

Một vấn đề khác liên quan kỹ thuật cao hiện đại dẫn tới tối ưu toàn cục là bài toán cấu hình phân tử hay cũng gọi là bài toán cuộn protein. Số là muốn tổng hợp những hóa chất mới, dược phẩm mới, vật liệu mới, hay protein mới, nhiều khi người ta phải tìm cực tiểu của một hàm thế năng phi tuyến phức tạp, mà phải là cực tiểu toàn cục mới ra được chất mong muốn, còn cực tiểu địa phương sẽ ra chất khác hẳn hoặc không đạt mục tiêu.

Đấy là một bài toán tối ưu toàn cục cực kỳ khó, nếu không có phương pháp nào tốt thì đành phải tính hết các điểm tối ưu địa phương rồi so sánh chọn ra tối ưu toàn cục. Nhưng tìm được một cực tiểu địa phương đã khó, mà số cực tiểu địa phương của các hàm thế năng này lại là con số khổng lồ, cho nên theo cách đó người ta phải dùng máy siêu tính Cray-2 chạy liên tục hàng tháng trời mới giải nổi bài toán trong một trường hợp tương đối đơn giản. Vì bài toán này cũng là mấu chốt giải quyết vấn đề cuộn Protein (một đề tài khoa học được xem như giai đoạn hai của việc giải mã di truyền), cho nên thực tế đây là một trong các vấn đề thời sự hóc búa nhất của một loạt ngành khoa học cơ bản: hóa học, sinh học, vật lý, toán học, có lẽ phải chờ vài thập kỷ nữa mới có được phương pháp xử lý thỏa đáng.

Sự xuất hiên những bài toán thực tế như thế cộng với nhiều ứng dụng khác trong công nghệ và quản lý, là lý do thúc đẩy tối ưu toàn cục phát triển mạnh ở các nước công nghiệp. Nhân đây cũng xin kể thêm một việc để thấy tính thời sự của vấn đề. Tháng ba năm ngoái tôi được mời tham gia một số hội thảo và làm một số xêmina ở Đại học Gainesville và Học viện Công nghệ Atlanta (Mỹ). Tại các hội thảo và xêmina đó tôi đã trình bày lý thuyết mới về tối ưu đơn điệu mà những ý tưởng đầu tiên đã nảy sinh qua một chuyến đi hợp tác và trao đổi ở Úc năm 1998. Các bạn đồng nghiệp Mỹ đã đặc biệt chú ý các kết quả này, họ liền đề nghị và chỉ sau hai tháng được NSF chấp nhận tài trợ một đề tài nghiên cứu ứng dụng tối ưu đơn điệu vào một số vấn đề khoa học kỹ thuật thời sự trong đó có bài toán cấu hình phân tử và tính toán ổn định trong kỹ thuật chế tạo tuốcbin máy bay phản lực. (NSF là cơ quan tài trợ nghiên cứu khoa học của Mỹ thường rất chặt chẽ trong việc xét duyệt các đề tài).

Qua vài việc cụ thể như trên đủ thấy sự nhạy cảm của giới công nghệ trên thế giới đối với từng thành tựu nhỏ của các phương pháp tối ưu, và vai trò ngày càng tăng của các phương pháp ấy trong thời đại kỹ thuật cao hiện nay.

Trở lại tình hình ở nước ta thì dễ thấy rất nhiều lĩnh vực rõ ràng rất lãng phí, hiệu quả hoạt động thấp, khiến nền kinh tế vận hành khá xa trạng thái tối ưu. Các thành tựu kinh tế của ta mười năm qua tuy rất đáng khích lệ nhưng thật ra chưa dựa vào những nhân tố bảo đảm sự tăng trưởng bền vững mà còn chủ yếu dựa vào những nhân tố không tự nhiên và có xu hướng cạn kiệt dần. Nếu ta không nhận thức được điều đó để nhanh chóng cải tiến quản lý, phát huy nội lực bằng cách khai thác tối ưu các tiềm năng, đặc biệt là tiềm năng trí tuệ mà đặc điểm là càng khai thác càng phát triển, thì sự tụt hậu khó tránh khỏi. Quá trình đi lên của các nước công nghiệp bao giờ cũng là quá trình liên tục hạ chi phí và nâng cao chất lượng so với mức trung bình của thế giới. Nhưng ở ta thì thế nào? Chỉ lấy ví dụ tiêu biểu là ngành điện thì tổn thất điện năng hiện nay của ta gấp 1,8 lần Thái Lan, năng suất lao động trong ngành điện của ta chỉ bằng 1/5 của Thái Lan, trước đây 10 năm chỉ tiêu điện năng tính theo đầu người của Thái Lan gấp 5,1 lần của ta, nay gấp 5,3 lần. Vậy làm sao ta đuổi kịp được các nước? Mà Thái Lan đâu phải là nước tiên tiến gì ghê gớm. Nhiều cơ quan quốc tế đánh giá đại bộ phận khoa học của ta chỉ mới ở mức của Thái Lan cách đây 30 năm, không phải chỉ vì ta thiếu điều kiện phát triển, mà chủ yếu vì ta chưa biết khai thác hết tiềm năng. Một cách thẳng thắn họ muốn nói rằng ta chưa sử dụng thông minh các điều kiện nhân tài, vật lực của đất nước.

Từ nhiều năm nay các Công ty trên thế giới đã quen áp dụng quản lý chất lượng toàn diện đi đôi với hạ thấp chi phí, còn ở ta đã làm gì? Tôi thường được nghe giới chuyên gia kinh tế ở các nước nhận định rằng trong nền kinh tế hiện đại, lĩnh vực đòi hỏi nhiều trí tuệ quản lý nhất là lĩnh vực tài chính, tiền tệ (cứ xem sự thăng trầm của kinh tế Nhật Bản, Hồng Kông và các nước ASEAN vừa qua đủ rõ). Đã có cả một ngành gọi là công nghệ tài chính ra đời phục vụ cho quản lý tài chính, đòi hỏi vận dụng khá nhiều tính toán tối ưu. Nhưng ở nước ta đây lại là lĩnh vực rất lạc hậu so với các nước, và không nghi ngờ gì, những khó khăn lớn nhất của chúng ta đã xuất phát từ sự yếu kém trong quản lý nguồn tiền. Không ở đâu trên thế giới lương chính thức chỉ đủ trang trải 1/5 nhu cầu sinh hoạt mà chế độ tài chính lại cho phép rút tiền ngân sách vô tội vạ bằng trăm nghìn cách khác nhau, cả gián tiếp và trực tiếp, hợp pháp và phi pháp, để rồi tuy không ai sống nổi bằng tiền lương mà vẫn có không ít người sống quá ung dung, đồng thời tham nhũng, buôn lậu và bạn đồng hành của chúng là tệ nạn xã hội thì phát triển vượt tầm kiểm soát hữu hiệu của xã hội.

Do đó vận dụng các quan điểm và phương pháp khoa học, bao gồm cả tư duy logic, hiệu quả tối ưu trong quản lý kinh tế, là việc có quan hệ trực tiếp và quyết định đến sự phồn vinh của đất nước. Để nhanh chóng thực hiện mục tiêu dân giàu, nước mạnh, xã hội công bằng, văn minh, không có con đường nào khác là phải dũng cảm phát huy sức mạnh trí tuệ để nâng cao hiệu quả và tính cạnh tranh của nền kinh tế.

Thông thường có hai loại vấn đề, nói đúng hơn hai hình thức ứng dụng, tối ưu:

Một là những vấn đề riêng lẻ, độc lập, không lặp đi lặp lại ở một tổ chức hay đơn vị nào đó. Chẳng hạn, vấn đề chống lũ ở đồng bằng sông Cửu Long và Miền Trung, vấn đề chiến lược phát triển năng lượng… Những vấn đề ấy đòi hỏi nhiều công phu nghiên cứu và thường có tính cách liên ngành chặt chẽ nên phải dùng tiếp cận hệ thống. Hà Lan đã có kinh nghiệm xử lý bằng phân tích hệ thống vấn đề lũ tương tự như ở ĐHSCL của ta (năm 1952 , Hà Lan bị một trận bão ở Bắc Hải gây lũ lớn, làm chết hàng nghìn người, ngập 13 vạn ha, sau đó phải lập cả một tập thể khoa học để nghiên cứu trong nhiều năm mới đề ra được cách xử lý và phòng chống). Đặc điểm các vấn đề này là thường có những hiệu ứng phụ, gọi là phụ nhưng rất quan trọng, nếu không phân tích và tính toán cẩn thận theo quan điểm hệ thống thì khó dự đoán được và có thể bị những bất ngờ tai hại. Điều đáng nói là ở các nước chậm phát triển, chúng ta hầu như chẳng bao giờ quan tâm các hiệu ứng phụ, hơn nữa, nếu có biết thì cái tư duy sống ngày nào lo ngày ấy (theo phương châm “sau đời ta là hồng thủy”!) cũng cản trở, không cho phép các phương pháp khoa học được có tiếng nói ở những nơi và lúc quyết định.

Hai là loại vấn đề có tính chất tác nghiệp, lặp đi lặp lại thường xuyên trong hoạt động của cùng một tổ chức hay đơn vị. Từ khi công nghệ vi tính ra đời và phát triển mạnh, cách xử lý đối với các vấn đề này là xây dựng phần mềm ứng dụng để giải nó theo những thông số đầu vào thay đổi tùy tình hình. Còn nhớ những năm 60, khi chúng tôi giúp các xí nghiệp áp dụng vận trù thì phải tính toán bằng tay từng phương án cụ thể, cho nên hễ cán bộ khoa học rút đi thì xí nghiệp không tự tiếp tục áp dụng được. Ngày nay điều kiện thuận lợi hơn nhiều, và để ứng dụng thành công chỉ cần xây dựng phần mềm giải quyết từng loại vấn đề đó trên máy vi tính. Trong bối cảnh công nghệ thông tin phát triển, nhiều Công ty phần mềm ở các nước đã ra đời không chỉ sản xuất phần mềm ngày càng hiệu quả về các công cụ tổng quát như quy hoạch tuyến tính, phi tuyến, tổ hợp… mà cả những phần mềm ứng dụng từng loại vấn đề thường gặp trong quản lý xí nghiệp và những môđun phần mềm làm sẵn để có thể vận dụng vào từng loại vấn đề đó khiến cho việc áp dụng ngày càng dễ dàng và có hiệu quả. Điều đó mở ra triển vọng rộng lớn đưa các phương pháp vận trù và tối ưu, nói rộng ra là các phương pháp khoa học, vào mọi lĩnh vực kinh tế và đời sống.

Cũng như mọi hoạt động khoa học, ứng dụng toán học cần phải có đầu óc tìm tòi, phân tích, nhất là nhiều trí tưởng tượng sáng tạo. Khi máy sao chụp (photocopy) Xerox mới được phát minh, người ta chỉ nghĩ đến công dụng của nó thay thế giấy cácbon, đến nỗi ngay cả Hãng IBM có tiếng là nhìn xa trông rộng mà cũng đánh giá thấp tác dụng của máy Xerox nên đã từ chối không mua phát minh của họ. Về sau, đầu óc tưởng tượng của người kinh doanh đã nghĩ ra biết bao nhiêu ứng dụng lúc đầu chẳng ai ngờ. Nhờ đó Xerox phát triển mạnh đến mức ngày nay nó đã đi vào đời sống thường ngày cửa mọi xã hội. Nghèo đến như Việt Nam mà gần đến ngày thi Đại học, các máy sao chụp trên mọi miền đất nước đều được huy động hết công suất để phục vụ nhu cầu quay cóp. Đủ biết, khi một phát minh ra đời, dần dần sẽ xuất hiện nhiều cách sử dụng nó mà trước đó đố ai có thể nghĩ đến. Rồi máy vi tính, Internet, cũng theo con đường như vậy: ai có đầu óc tưởng tượng để nghĩ ra những ứng dụng mà người khác không nghĩ đến, kẻ đó cũng có công với khoa học như những nhà phát minh lớn. Và lại chính những ứng dụng mới sẽ kích thích những phát minh mới. Không có những nhân vật như Bill Gates thì làm gì máy vi tính phát triển như ngày nay. Cho nên, cứ làm đi, cứ phát triển tưởng tượng để nghĩ ra những ứng dụng rồi tìm cách thực thi kỳ được, đó là con đường hầu như bắt buộc phải trải qua để đưa các thành tựu khoa học vào thực tế một cách sáng tạo. Trong toán học đã có một kinh nghiệm nối tiếng, thường được nhắc đến như một bài học lớn : ngay từ những năm 20 – 30 các nhà toán học Anh, Mỹ đã có nhiều thành tựu thống kê lý thuyết rất quan trọng (phân tích thống kê, đặc biệt là giải tích dãy) nhưng phải đợi đến những năm 50 người Nhật mới nghĩ ra được việc áp dụng các thành tựu đó vào kiểm tra chất lượng. Kết quả là người Nhật đã đem lại những bước tiến nhảy vọt về chất lượng sản phẩm, khiến chỉ một thời gian ngắn công nghiệp của họ đã cạnh tranh ngang ngửa và đánh bại nhiều đối thủ quan trọng mà trước đó không ai ngờ họ có thể qua mặt được.

Không lạ gì tối ưu toàn cục, khi xuất phát chỉ bó hẹp trong vài vấn đề kinh tế, nay đã mở rộng phạm vi ứng dụng vào nhiều vấn đề khoa học kỹ thuật mới: cuộn protein, NMR (cộng hưởng từ hạt nhân), khai thác dữ liệu (data mining) viễn thông… Tiếc rằng mặc dù ngành tối ưu của Việt Nam đã chiếm được một vị trí đáng nể trong khoa học thế giới nhưng mấy năm qua không không tiến lên được về ứng dụng do thiếu những điều kiện tối thiểu về nhân lực và phương tiện. Điều đáng buồn là những điều kiện này cũng chẳng phải khó khăn gì, chẳng qua do thiếu sự quan tâm cần thiết của các cơ quan hữu trách.

Cần phải nói thêm, ngoài các ứng dụng vào từng việc cụ thể, các khoa học về tối ưu, hệ thống, và các phương pháp toán học nói chung, còn có tác dụng rèn luyện và bồi dưỡng tư duy khoa học rất cần thiết trong cuộc sống hiện đại. Nhiều việc, dù không có kiến thức cụ thể và không biết tính toán chính xác chặt chẽ, song nếu có tư duy logic, có khái niệm về hệ thống tối ưu hiệu quả, có khái niệm về mô hình, về thống kê… thì sẽ có cách suy nghĩ đúng đắn hơn đề tiếp cận hàng loạt vấn đề thực tế hàng ngày, chẳng hạn như cân nhắc lợi hại, tính toán rủi ro, dự trữ, làm các kế hoạch dự phòng trong các môi trường nhiều yếu tố bất định… Chỉ đơn cử vài ví dụ, từ lâu trong khoa học người ta đã biết cái gọi là “nghịch lý Braess” : mở thêm đường trong một mạng giao thông không nhất thiết bao giờ cũng làm giảm ách tắc, tăng hiệu quả, làm cho xe cộ đi lại thông suốt hơn mà có khi có tác dụng ngược lại. Kinh nghiệm thành phố Stuttgart ở CHLB Đức cách đây vài chục năm cho thấy khi người ta mở thêm nhiều đường mới với hy vọng giảm bớt ách tắc giao thông thì trái lại đã làm cho giao thông ách tắc thêm, và chỉ sau khi đóng bớt một đường mới mở thì giao thông mới thật sự được cải thiện. Chúng ta không biết nghịch lý đó nên khi mở thêm đường Chùa Bộc ở Hà Nội cũng tưởng giảm bớt, không ngờ đã làm tăng thêm ách tắc giao thông, và mãi sau khi tích cực giải quyết một số nút chai thì mới giải tỏa được. Trong kinh tế xã hội có những hiện tượng không hoặc rất khó đảo ngược, nhà quản lý phải hết sức tránh và nếu đã lỡ để xảy ra một hiện tượng xấu thuộc loại đó thì ít khi có thể giải quyết bằng cách cố quay về trạng thái cũ. Các tệ nạn tham nhũng trong bộ máy Nhà nước, việc dạy thêm học thêm tràn lan, ma túy trong nhà trường… đều thuộc loại hiện tượng đó. Khi đã thành tật thì như một bản tin mới, không dễ gì thay đổi nếu không kiên quyết.

Để đẩy mạnh ứng dụng toán học nói chung và tối ưu nói riêng, cần:

Có một cơ chế quản lý tốt (trước hết về tài chính tiền tệ) để tạo một môi trường kinh tế xã hội lành mạnh, thuận lợi cho các hoạt động khoa học chân chính, khuyến khích áp dụng khoa học, từ việc nhỏ trở đi (nhiều việc tưởng nhỏ mà thật ra vô cùng quan trọng như có những điểm chi tiết trong cơ chế quản lý hiện nay đủ sức vô hiệu hóa các chủ trương lớn)

Cần nâng cao nhận thức trong các cấp lãnh đạo đối với khoa học, phù hợp với yêu cầu thời đại công nghệ. Làm sao để sự quan tâm của các cấp lãnh đạo đối với khoa học ít ra cũng ngang như thời kỳ những năm 60. Không có gì quan trọng hơn chất lượng và hiệu quả, mà hai thứ đó chỉ đạt được nhờ phát triển khoa học.

Đẩy mạnh đào tạo cán bộ. Phải có những người trẻ đủ kiến thức, tài năng và nhiệt huyết. Đội ngũ khoa học của ta nhiều người tuổi đã cao, khó xông xáo, và ít nhạy cảm với những cái mới, dễ có xu hướng làm theo lối mòn, do lỗi của chúng ta trong nhiều năm đã buộc họ phải vất vả kiếm sống bằng nghề phụ và nhiều việc làm phụ có khi chẳng liên quan gì đến nghề nghiệp. Do đó phải giúp họ quay lại với chuyên môn, đồng thời cần có những hình thức đào tạo mới, mạnh dạn thoát ra khỏi các khuôn khổ hiện tại để có thể nhanh chóng xây dựng được một đội ngũ cán bộ trẻ có năng lực, đáp ứng được nhu cầu phát triển.

Giáo dục là căn bản, không chấn hưng giáo dục bằng những biện pháp kiên quyết để thật sự nâng cao dân trí, đào tạo nhân lực và phát triển nhân tài theo những yêu cầu của thời đại kinh tế tri thức, thì không thể có sáng tạo gì trong khoa học công nghệ, mà ngay cả những điều đã thành thông thường sơ đẳng ở các nước, ta cũng khó ứng dụng có hiệu quả. Singapore đang có kế hoạch cải cách giáo dục để biến đảo quốc này thành một đất nước học thức, lẽ nào truyền thống nghìn năm văn hiến của ta đến thế hệ này là chấm dứt?

Thật đáng mừng mà vừa cũng đáng lo là chưa bao giờ toán học cần cho sự phát triển của các quốc gia như bây giờ. Không phải vô cớ mà UNESCO đã bảo trợ tuyên bố của Hội Toán học Quốc tế lấy năm 2000 làm năm toán học của thế giới. Trong các hành trang để bước sang thế kỷ XXI, toán học nói chung và khoa học tối ưu nói riêng không thể thiếu được. Chúng ta không thể bỏ lỡ cơ hội phát triển trí tuệ của dân tộc vào thời buổi đâu đâu trên thế giới trí tuệ cũng được huy động tối đa để đạt hiệu quả, chất lượng, và tăng sức mạnh cạnh tranh của nền kinh tế. Nếu như phi tuyến, nhảy vọt, là đặc trưng của nhiều hiện tượng kinh tế, xã hội, khoa học, công nghệ, trong thế kỷ tới thì tại sao ta không có quyền hy vọng?

————–&&————–

Tối ưu hóa (toán học)

Tối ưu hóa (toán học)

(Nguồn: wikipedia)

Trong toán học, thuật ngữ tối ưu hóa chỉ tới việc nghiên cứu các bài toán có dạng

Cho trước: một hàm f : A \to R từ tập hợp A tới tập số thực
Tìm: một phần tử x0 thuộc A sao cho f(x0) ≤ f(x) với mọi x thuộc A (“cực tiểu hóa”) hoặc sao cho f(x0) ≥ f(x) với mọi x thuộc A (“cực đại hóa”).

Một phát biểu bài toán như vật đôi khi được gọi là một quy hoạch toán học (mathematical program). Nhiều bài toán thực tế và lý thuyết có thể được mô hình theo cách tổng quát trên.

Miền xác định A của hàm f được gọi là không gian tìm kiếm. Thông thường, A là một tập con của không gian Euclid Rn, thường được xác định bởi một tập các ràng buộc, các đẳng thức hay bất đẳng thức mà các thành viên của A phải thỏa mãn. Các phần tử của A được gọi là các lời giải khả thi. Hàm f được gọi là hàm mục tiêu, hoặc hàm chi phí. Lời giải khả thi nào cực tiểu hóa (hoặc cực đại hóa, nếu đó là mục đích) hàm mục tiêu được gọi là lời giải tối ưu.

Thông thường, sẽ có một vài cực tiểu địa phương và cực đại địa phương, trong đó một cực tiểu địa phương x* được định nghĩa là một điểm thỏa mãn điều kiện:

với giá trị δ > 0 nào đó và với mọi giá trị x sao cho

\|\mathbf{x}-\mathbf{x}^*\|\leq\delta;

công thức sau luôn đúng

f(\mathbf{x}^*)\leq f(\mathbf{x})

Nghĩa là, tại vùng xung quanh x*, mọi giá trị của hàm đều lớn hơn hoặc bằng giá trị tại điểm đó. Cực đại địa phương được định nghĩa tương tự. Thông thường, việc tìm cực tiểu địa phương là dễ dàng – cần thêm các thông tin về bài toán (chẳng hạn, hàm mục tiêu là hàm lồi) để đảm bảo rằng lời giản tìm được là cực tiểu toàn cục.

Mục lục

Ký hiệu

Các bài toán tối ưu hóa thường được biểu diễn bằng các ký hiệu đặc biệt. Ví dụ:

\min_{x\in\mathbb R}\; x^2 + 1

Bài toán trên yêu cầu tìm giá trị nhỏ nhất cho biểu thức x2 + 1, trong đó x chạy trên tập số thực R. Giá trị nhỏ nhất trong trường hợp này là 1, xảy ra tại x = 0.

\max_{x\in\mathbb R}\; 2x

Bài toán trên yêu cầu tìm giá trị lớn nhất cho biểu thức 2x, trong đó x chạy trên tập số thực. Trong trường hợp này, không có giá trị lớn nhất do biểu thức không bị chặn trên, vậy kết quả là “giá trị vô cùng” hoặc “không xác định”.

\operatorname{argmin}_{x\in[-\infty,-1]}\; x^2 + 1

Bài toán trên yêu cầu tìm các giá trị của x trong đoạn [−∞, −1] để cực tiểu hóa biểu thức x2 + 1. (Giá trị nhỏ nhất của biểu thức không quan trọng.) Trong trường hợp này, kết quả là x = −1.

\operatorname{argmax}_{x\in[-5,5],\;y\in\mathbb R}\; x\cdot\cos(y)

Bài toán trên yêu cầu tìm cặp (xy) làm cực đại giá trị của biểu thức x·cos(y), với ràng buộc rằng x nằm trong đoạn [−5, 5]. (Một lần nữa, giá trị nhỏ nhất của biểu thức không quan trọng.) Trong trường hợp này, kết quả là các cặp có dạng (5, 2πk) và (−5, (2k + 1)π), với k chạy trên tập số nguyên.

Các lĩnh vực con chính

  • Quy hoạch tuyến tính (Linear programming) nghiên cứu các trường hợp khi hàm mục tiêu f là hàm tuyến tính và tập A được mô tả chỉ bằng các đẳng thức và bất đẳng thức tuyến tính (A được gọi là một khúc lồi).
  • Quy hoạch số nguyên (Integer programming) nghiên cứu các quy hoạch tuyến tính trong đó một số hoặc tất cả các biến có giới hạn là các số nguyên.
  • Quy hoạch bậc hai (hay quy hoạch toàn phương) (Quadratic programming) cho phép hàm mục tiêu có các toán hạng bậc hai, trong khi tập A phải mô tả được bằng các đẳng thức và bất đẳng thức tuyến tính (A được gọi là một khúc lồi).
  • Quy hoạch phi tuyến (Nonlinear programming) nghiên cứu trường hợp tổng quát khi hàm mục tiêu hay các ràng buộc hoặc cả hai chứa các thành phần không tuyến tính.
  • Quy hoạch ngẫu nhiên (Stochastic programming) nghiên cứu các trường hợp khi một số ràng buộc phụ thuộc vào các biến ngẫu nhiên.
  • Quy hoạch động (Dynamic programming) nghiên cứu các trường hợp khi chiến lược tối ưu hóa dựa trên việc chia bài toán thành các bài toán con nhỏ hơn (nguyên lý quy hoạch động).
  • Tối ưu hóa tổ hợp (Combinatorial optimization) quan tâm đến các bài toán trong đó tập các lời giải khả thi là rời rạc hoặc có thể được rút gọn về một tập rời rạc.
  • Infinite-dimensional optimization nghiên cứu trường hợp khi tập các lời giải khả thi là một tập con của một không gian vô số chiều, chẳng hạn không gian các hàm số (ví dụ bài toán điều khiển tối ưu).
  • Constraint satisfaction nghiên cứu trường hợp khi hàm mục tiêu f là hằng số – đây là vấn đề quan trọng của ngành Trí tuệ nhân tạo, đặc biệt là lĩnh vực Suy luận tự động (Automated reasoning).

Các kỹ thuật

Đối với các hàm khả vi hai lần (twice-differentiable), có thể giải các bài toán không ràng buộc bằng cách tìm các điểm mà tại đó đạo hàm của hàm mục tiêu bằng 0 (điểm dừng) và sử dụng ma trận Hesse để xác định xem đó là cực tiểu, cực đại, hay điểm yên ngựa.

Ta có thể tìm các điểm dừng bằng cách bắt đầu từ một điểm dự đoán là điểm dừng rồi tiến về điểm dừng bằng cách lặp đi lặp lại các phương pháp như

Nếu hàm mục tiêu là hàm lồi trong vùng quan tâm thì cực tiểu địa phương sẽ là cực tiểu toàn cục. Có các phương pháp số nhanh chóng và hiệu quả cho việc tối ưu hóa các hàm lồi khả vi hai lần.

Các bài toán ràng buộc thường có thể được biến đổi thành một bài toán không có ràng buộc bằng phương pháp nhân tử Lagrange (Lagrange multiplier).

Dưới đây là một số phương pháp thông dụng:

Ứng dụng

Các bài toán trong động lực học vật rắn (cụ thể là động lực học vật rắn chính xác) thường đòi hỏi các kỹ thuật quy hoạch toán học, do ta có thể coi động lực học vật rắn như là việc giải các phương trình vi phân thường (ordinary differential equation) trên một đa tạp ràng buộc (constraint manifold); các ràng buộc là các ràng buộc hình học không tuyến tính đa dạng, chẳng hạn “hai điểm này phải luôn trùng nhau”, “bề mặt này không được xuyên qua các bề mặt khác”, hoặc “điểm này phải nằm đâu đó trên đường cong này”. Ngoài ra, vấn đề tính toán các lực tiếp xúc có thể được thực hiện bằng cách giải một bài toán bù tuyến tính (linear complementarity problem). Dạng bài nài cũng có thể được coi là bài toán quy hoạch bậc hai.

Nhiều bài toán thiết kế cũng có thể được biểu diễn dưới dạng các chương trình tối ưu hóa. Áp dụng này được gọi là tối ưu hóa thiết kế. Một lĩnh vực con mới phát triển trong thời gian gần đây là multidisciplinary design optimization. Nó hữu ích cho nhiều bài toán và đã được áp dụng cho các bài toán kỹ nghệ hàng không (aerospace engineering).

Vận trù học (operations research) là lĩnh vực sử dụng rất nhiều đến các kỹ thuật tối ưu hóa.

Xem thêm

Tham khảo

Liên kết ngoài

Phần mềm:

Trang tiếng Việt về Toán tối ưu

http://etintin.com/csstudyfun/

http://csstudyfun.wordpress.com/

http://dangcnd.wordpress.com/bai-giang/quy-hoach-tuyen-tinh/

————–&&————–