Các Phương Pháp Tối Ưu Quyển 1 - GS. Trần Vũ Thiệu

Các phương pháp tối ưu hóa là nền tảng toán học cho phép tìm kiếm giải pháp tốt nhất cho một vấn đề trong một tập hợp các lựa chọn khả thi. Như GS. 73 trang.

• Đề tài: Các Phương Pháp Tối Ưu Trong Kinh Tế và Kỹ Thuật

Mục lục chi tiết

• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1: QUI HOẠCH TUYẾN TÍNH DẠNG ĐẶC BIỆT
• 1.1. Qui hoạch tuyến tính với biến bị chặn trên
• 1.2. Qui hoạch tuyến tính tham số
• 1.3. Phân rã qui hoạch tuyến tính
• 1.4. Qui hoạch tuyến tính có cấu trúc khối
• 1.5. Thuật toán điểm trong Karmarkar
• 1.6. Qui hoạch tuyến tính nhiều mục tiêu
• 2. CHƯƠNG 2: PHƯƠNG PHÁP GIẢI QUI HOẠCH NGUYÊN
• 3. CHƯƠNG 3: PHƯƠNG PHÁP TỐI ƯU TRÊN MẠNG VÀ ĐỒ THỊ
• 4. CHƯƠNG 4: PHƯƠNG PHÁP QUI HOẠCH PHI TUYẾN

Tóm tắt

I. Khám phá các phương pháp tối ưu trong kinh tế và kỹ thuật

Các phương pháp tối ưu hóa là nền tảng toán học cho phép tìm kiếm giải pháp tốt nhất cho một vấn đề trong một tập hợp các lựa chọn khả thi. Như GS. Trần Vũ Thiều đã nhấn mạnh trong lời nói đầu của cuốn sách “Các phương pháp tối ưu”, các bài toán này xuất hiện rất phổ biến trong cả lĩnh vực kinh tế và kỹ thuật, với phạm vi ứng dụng rộng rãi và đa dạng. Về bản chất, đây là một nhánh quan trọng của nghiên cứu vận hành (Operations Research), tập trung vào việc sử dụng các mô hình toán học, thống kê và thuật toán để hỗ trợ quá trình ra quyết định. Mục tiêu không chỉ là tìm ra một giải pháp, mà là tìm ra giải pháp cực đại hóa (lợi nhuận, hiệu suất) hoặc cực tiểu hóa (chi phí, rủi ro, thời gian) một hàm mục tiêu cụ thể. Mọi bài toán tối ưu đều được cấu thành từ ba thành phần chính: các biến quyết định (decision variables) là những yếu tố có thể kiểm soát; hàm mục tiêu (objective function) là biểu thức toán học cần tối ưu; và các điều kiện ràng buộc (constraints) là những giới hạn về nguồn lực, thời gian, hoặc các quy định kỹ thuật. Việc áp dụng thành công các phương pháp tối ưu trong kinh tế và kỹ thuật đòi hỏi sự hiểu biết sâu sắc về cách mô hình hóa toán học một vấn đề thực tế, chuyển các mục tiêu kinh doanh hoặc yêu cầu kỹ thuật thành một cấu trúc toán học có thể giải được. Từ việc phân bổ nguồn lực trong một doanh nghiệp, quy hoạch sản xuất trong một nhà máy, đến thiết kế kỹ thuật tối ưu cho một công trình, tất cả đều có thể được hưởng lợi từ việc áp dụng các kỹ thuật này.

1.1. Định nghĩa tối ưu hóa và vai trò trong nghiên cứu vận hành

Tối ưu hóa (Optimization) là quá trình tìm kiếm điểm cực trị (cực đại hoặc cực tiểu) của một hàm số trên một miền xác định, tuân theo các điều kiện ràng buộc cho trước. Đây là công cụ cốt lõi của lĩnh vực nghiên cứu vận hành, giúp chuyển các bài toán quản lý phức tạp thành các mô hình có thể phân tích và giải quyết một cách có hệ thống. Vai trò của nó là cung cấp một cơ sở định lượng để đưa ra các quyết định hiệu quả nhất, thay vì dựa trên kinh nghiệm hoặc phỏng đoán.

1.2. Các thành phần cốt lõi hàm mục tiêu và điều kiện ràng buộc

Một bài toán tối ưu hóa được xác định rõ ràng thông qua ba yếu tố. Thứ nhất là biến quyết định, đại diện cho các lựa chọn cần đưa ra (ví dụ: số lượng sản phẩm cần sản xuất). Thứ hai là hàm mục tiêu, một phương trình toán học biểu diễn mục tiêu cần đạt được (ví dụ: hàm lợi nhuận cần tối đa hóa). Cuối cùng là điều kiện ràng buộc, các bất đẳng thức hoặc phương trình thể hiện giới hạn của hệ thống (ví dụ: nguồn vốn, nhân lực, công suất máy móc).

II. Bài toán tối ưu hóa Từ mô hình hóa đến các thách thức

Thách thức lớn nhất khi áp dụng các phương pháp tối ưu trong kinh tế và kỹ thuật không nằm ở việc giải thuật toán, mà là ở giai đoạn mô hình hóa toán học vấn đề. Việc chuyển một tình huống thực tế, với nhiều yếu tố phức tạp và bất định, thành một mô hình toán học chính xác là bước quyết định sự thành công. Mô hình cần phải đủ đơn giản để có thể giải được trong thời gian hợp lý nhưng cũng phải đủ chi tiết để phản ánh đúng bản chất của vấn đề. Một trong những quyết định quan trọng nhất trong quá trình này là phân loại bài toán. Các bài toán có thể được chia thành quy hoạch tuyến tính (Linear Programming), khi cả hàm mục tiêu và các ràng buộc đều là hàm tuyến tính, và quy hoạch phi tuyến (Nonlinear Programming), khi có ít nhất một trong số chúng không phải là tuyến tính. Ngoài ra còn có quy hoạch nguyên (Integer Programming) khi các biến quyết định phải nhận giá trị nguyên. Theo tài liệu của GS. Trần Vũ Thiều, kinh nghiệm tính toán cho thấy thời gian giải bài toán quy hoạch tuyến tính phụ thuộc chủ yếu vào số lượng ràng buộc. Do đó, việc xác định đúng cấu trúc bài toán và lựa chọn phương pháp giải phù hợp là cực kỳ quan trọng. Các vấn đề như bài toán vận tải hay quy hoạch sản xuất thường thuộc dạng tuyến tính, trong khi các bài toán liên quan đến động lực học hệ thống hay tối ưu hóa danh mục đầu tư với các mô hình rủi ro phức tạp thường là phi tuyến. Thách thức khác là việc thu thập dữ liệu chính xác để xác định các tham số trong mô hình.

2.1. Quy trình xây dựng một mô hình hóa toán học hiệu quả

Quy trình này bao gồm các bước: (1) Xác định rõ ràng vấn đề và mục tiêu cần đạt được. (2) Nhận diện các biến quyết định và các tham số không đổi. (3) Xây dựng hàm mục tiêu dưới dạng một biểu thức toán học. (4) Liệt kê và công thức hóa tất cả các điều kiện ràng buộc của hệ thống. (5) Kiểm tra và xác thực mô hình để đảm bảo nó phản ánh chính xác thực tế.

2.2. Phân loại bài toán Tuyến tính phi tuyến và quy hoạch nguyên

Việc phân loại bài toán quyết định phương pháp giải sẽ được sử dụng. Quy hoạch tuyến tính (Linear Programming) là dạng phổ biến và có thuật toán giải hiệu quả nhất. Quy hoạch phi tuyến (Nonlinear Programming) phức tạp hơn, thường yêu cầu các phương pháp lặp và không đảm bảo tìm được nghiệm tối ưu toàn cục. Quy hoạch nguyên xử lý các biến rời rạc, thường gặp trong các bài toán lập lịch hoặc lựa chọn dự án.

III. Quy hoạch tuyến tính Nền tảng của các phương pháp tối ưu

Quy hoạch tuyến tính (Linear Programming) là một trong những công cụ mạnh mẽ và được sử dụng rộng rãi nhất trong nghiên cứu vận hành. Nó giải quyết các bài toán mà ở đó mục tiêu là tối đa hóa hoặc tối tiểu hóa một hàm mục tiêu tuyến tính, trong khi phải tuân thủ một tập hợp các ràng buộc cũng ở dạng tuyến tính. Phương pháp đơn hình (Simplex Method), do George Dantzig phát triển, là thuật toán kinh điển và hiệu quả để giải quyết hầu hết các bài toán quy hoạch tuyến tính. Sức mạnh của nó nằm ở khả năng duyệt qua các đỉnh của miền khả thi một cách có hệ thống để tìm ra nghiệm tối ưu. Tài liệu của GS. Trần Vũ Thiều trình bày chi tiết về các dạng đặc biệt của quy hoạch tuyến tính, chẳng hạn như "quy hoạch tuyến tính với biến bị chặn trên", một vấn đề thường gặp trong thực tế khi các biến số có giới hạn tối đa. Phương pháp xử lý các ràng buộc này một cách riêng biệt giúp giảm đáng kể thời gian tính toán so với việc thêm chúng vào hệ ràng buộc chính. Các ứng dụng kinh điển của quy hoạch tuyến tính bao gồm bài toán vận tải (tìm cách vận chuyển hàng hóa từ nhiều nguồn đến nhiều đích với chi phí thấp nhất) và bài toán phân bổ nguồn lực (phân chia các nguồn lực có hạn như vốn, nhân công, nguyên vật liệu cho các hoạt động khác nhau để đạt lợi nhuận cao nhất).

3.1. Lý thuyết cơ bản và phương pháp đơn hình Simplex method

Phương pháp đơn hình hoạt động trên nguyên tắc di chuyển từ một đỉnh (phương án cực biên) của miền ràng buộc đến một đỉnh kề cận tốt hơn, lặp lại quá trình này cho đến khi không thể cải thiện thêm hàm mục tiêu. Quá trình này được thực hiện thông qua các phép biến đổi trên một bảng gọi là bảng đơn hình, đảm bảo tìm ra lời giải tối ưu sau một số hữu hạn bước.

3.2. Phân tích bài toán vận tải và phân bổ nguồn lực

Bài toán vận tải là một ví dụ điển hình của quy hoạch tuyến tính, với mục tiêu tối thiểu hóa chi phí logistics. Tương tự, bài toán phân bổ nguồn lực giúp các nhà quản lý ra quyết định phân chia ngân sách, nhân sự, hoặc thời gian một cách tối ưu để tối đa hóa hiệu quả hoạt động, đây là ứng dụng trực tiếp và quan trọng trong tối ưu hóa vận hành.

IV. Top phương pháp tối ưu phi tuyến và thuật toán heuristic

Khi các mối quan hệ trong bài toán không còn tuyến tính, chúng ta bước vào lĩnh vực quy hoạch phi tuyến (Nonlinear Programming). Các bài toán này phức tạp hơn đáng kể vì miền khả thi có thể không lồi và hàm mục tiêu có thể có nhiều điểm cực trị địa phương. Việc tìm kiếm nghiệm tối ưu toàn cục trở thành một thách thức lớn. Các phương pháp giải cho quy hoạch phi tuyến thường mang tính lặp, chẳng hạn như phương pháp Gradient Descent, phương pháp Newton, hay các phương pháp dựa trên điều kiện Karush-Kuhn-Tucker (KKT). Tuy nhiên, đối với các bài toán có độ phức tạp cực lớn hoặc cấu trúc không rõ ràng, các thuật toán heuristic và metaheuristic lại tỏ ra vô cùng hiệu quả. Những thuật toán này không đảm bảo tìm ra nghiệm tối ưu tuyệt đối nhưng thường cho kết quả đủ tốt trong thời gian tính toán hợp lý. Thuật toán di truyền (Genetic Algorithm) là một ví dụ nổi bật, mô phỏng quá trình tiến hóa tự nhiên thông qua các cơ chế lựa chọn, lai ghép và đột biến để tìm kiếm giải pháp. Một kỹ thuật khác là mô phỏng Monte Carlo, sử dụng các mẫu ngẫu nhiên để ước tính và tối ưu hóa các hệ thống phức tạp, đặc biệt hữu ích trong phân tích rủi ro và tối ưu hóa danh mục đầu tư. Các thuật toán này là công cụ không thể thiếu khi đối mặt với các bài toán tối ưu hóa tổ hợp hoặc các không gian tìm kiếm khổng lồ.

4.1. Giải quyết bài toán quy hoạch phi tuyến Nonlinear Programming

Giải quyết bài toán quy hoạch phi tuyến đòi hỏi các công cụ toán học cao cấp hơn. Các thuật toán thường bắt đầu từ một điểm ban đầu và lặp đi lặp lại việc tìm kiếm một hướng đi cải thiện và một độ dài bước phù hợp để tiến tới một điểm tốt hơn. Thách thức chính là tránh bị mắc kẹt tại các điểm tối ưu địa phương thay vì tìm ra điểm tối ưu toàn cục.

4.2. Khám phá thuật toán di truyền và mô phỏng Monte Carlo

Thuật toán di truyền thuộc lớp metaheuristic, rất mạnh trong việc giải các bài toán tối ưu hóa tổ hợp như bài toán người bán hàng (Traveling Salesman Problem). Trong khi đó, mô phỏng Monte Carlo thường được áp dụng trong tài chính để mô hình hóa sự biến động của giá tài sản, từ đó giúp xây dựng các chiến lược tối ưu hóa danh mục đầu tư nhằm cân bằng giữa lợi nhuận và rủi ro.

V. Ứng dụng các phương pháp tối ưu trong kinh tế kỹ thuật

Tính ứng dụng thực tiễn là minh chứng rõ ràng nhất cho sức mạnh của các phương pháp tối ưu trong kinh tế và kỹ thuật. Trong lĩnh vực kinh tế và quản trị kinh doanh, quản lý chuỗi cung ứng (Supply Chain Optimization) là một trong những lĩnh vực hưởng lợi nhiều nhất. Các doanh nghiệp sử dụng các mô hình tối ưu để quyết định vị trí đặt nhà kho, lộ trình vận chuyển, mức tồn kho an toàn và chiến lược quy hoạch sản xuất nhằm giảm thiểu chi phí và nâng cao khả năng đáp ứng khách hàng. Trong lĩnh vực tài chính, các mô hình tối ưu hóa danh mục đầu tư giúp các nhà đầu tư xây dựng danh mục tài sản mang lại lợi nhuận kỳ vọng cao nhất với một mức rủi ro chấp nhận được. Trong kỹ thuật, các ứng dụng còn đa dạng hơn. Thiết kế kỹ thuật tối ưu sử dụng các thuật toán để tìm ra hình dạng, kích thước và vật liệu tốt nhất cho các kết cấu (như dầm cầu, cánh máy bay) để chúng vừa nhẹ, vừa bền, vừa tiết kiệm chi phí. Lĩnh vực điều khiển tối ưu (Optimal Control) nghiên cứu cách điều khiển một hệ thống động (ví dụ: robot, tên lửa, quy trình hóa học) theo thời gian để đạt được một mục tiêu nhất định. Để giải quyết các bài toán này, các kỹ sư và nhà kinh tế học thường sử dụng các phần mềm tối ưu hóa chuyên dụng như MATLAB, LINGO, GAMS hoặc các thư viện mạnh mẽ trong các ngôn ngữ lập trình như Python Scipy.

5.1. Tối ưu hóa chuỗi cung ứng và quy hoạch sản xuất

Đây là ứng dụng cốt lõi của tối ưu hóa vận hành. Các mô hình toán học giúp giải quyết các bài toán phức tạp như bài toán vận tải, lập lịch sản xuất, và quản lý tồn kho. Mục tiêu là tạo ra một chuỗi cung ứng linh hoạt, hiệu quả về chi phí và đáp ứng nhanh chóng với sự thay đổi của thị trường, trực tiếp nâng cao năng lực cạnh tranh của doanh nghiệp.

5.2. Các phần mềm tối ưu hóa MATLAB Python Scipy và LINGO

Việc giải các bài toán tối ưu phức tạp trong thực tế không thể thực hiện bằng tay. Các công cụ như MATLAB với Optimization Toolbox, các thư viện mã nguồn mở như Python Scipy (scipy.optimize), hay các phần mềm chuyên dụng như LINGO và GAMS cung cấp các bộ giải (solver) mạnh mẽ, cho phép các chuyên gia tập trung vào việc mô hình hóa toán học vấn đề thay vì lập trình thuật toán từ đầu.

VI. Hướng phát triển mới của các phương pháp tối ưu hiện đại

Lĩnh vực tối ưu hóa không ngừng phát triển, đặc biệt với sự trỗi dậy của khoa học dữ liệu và trí tuệ nhân tạo. Một trong những bước đột phá quan trọng trong lịch sử quy hoạch tuyến tính là sự ra đời của thuật toán điểm trong (Interior-Point Methods), tiêu biểu là thuật toán của Karmarkar vào những năm 1980. Như được đề cập trong tài liệu tham khảo, khác với phương pháp đơn hình di chuyển dọc theo các cạnh của miền ràng buộc, thuật toán điểm trong đi xuyên qua phần bên trong của miền đó. Đối với các bài toán quy mô cực lớn (hàng chục ngàn ràng buộc), thuật toán điểm trong thường tỏ ra nhanh hơn đáng kể so với phương pháp đơn hình. Hướng phát triển tương lai của các phương pháp tối ưu trong kinh tế và kỹ thuật tập trung vào việc kết hợp tối ưu hóa với học máy (Machine Learning). Các mô hình học máy có thể được sử dụng để dự báo các tham số đầu vào cho bài toán tối ưu (ví dụ: dự báo nhu cầu khách hàng), sau đó mô hình tối ưu sẽ đưa ra quyết định dựa trên các dự báo đó. Ngược lại, các kỹ thuật tối ưu cũng được dùng để huấn luyện các mô hình học máy phức tạp. Tương lai của ngành nghiên cứu vận hành sẽ chứng kiến sự tích hợp ngày càng sâu sắc giữa tối ưu hóa xác định (deterministic), tối ưu hóa ngẫu nhiên (stochastic) và các kỹ thuật xử lý dữ liệu lớn để giải quyết các bài toán ngày càng phức tạp và δυναμικ trong thế giới thực.

6.1. Thuật toán điểm trong Karmarkar và hiệu suất tính toán

Thuật toán Karmarkar là một cột mốc, chứng minh rằng quy hoạch tuyến tính có thể được giải trong thời gian đa thức. Mặc dù mỗi bước lặp của nó phức tạp hơn phương pháp đơn hình, số bước lặp cần thiết cho các bài toán lớn lại ít hơn nhiều. Điều này mở đường cho việc giải quyết các bài toán tối ưu hóa với quy mô chưa từng có, đặc biệt trong các lĩnh vực như viễn thông và logistics.

6.2. Tương lai của ngành nghiên cứu vận hành Operations Research

Ngành nghiên cứu vận hành đang dịch chuyển sang việc xử lý các hệ thống quy mô lớn, bất định và có dữ liệu thời gian thực. Sự kết hợp giữa tối ưu hóa, mô phỏng, và phân tích dữ liệu sẽ là chìa khóa để giải quyết các thách thức toàn cầu như quản lý chuỗi cung ứng bền vững, tối ưu hóa mạng lưới năng lượng thông minh và phát triển các hệ thống giao thông tự hành.

Nội dung chính

Giáo Trình Các Phương Pháp Tối Ưu Trong Kinh Tế Và Kỹ Thuật (Quyển 1)

Tổng quan về giáo trình

Giáo trình Các Phương Pháp Tối Ưu (Quyển 1) của Giáo sư Trần Vũ Thiệu được Nhà xuất bản Bách Khoa Hà Nội phát hành (Mã số ISBN: 978-604-316-131-1; Số ĐKXB: 3935-2023/CXBIPH/29-68/BKHN). Đây là công trình học thuật được tổng hợp và chuẩn hóa từ hệ thống bài giảng nhiều năm của tác giả tại các cơ sở giáo dục đại học, phục vụ trực tiếp cho môn học "Tối ưu hóa" – học phần thường được bố trí giảng dạy ở những năm cuối của bậc đại học và cao đẳng.

Vị trí của học phần này đóng vai trò bản lề trong việc kết nối giữa toán học lý thuyết với các bài toán ứng dụng thực tế trong quản lý kinh tế và giải pháp kỹ thuật. Mục tiêu học tập (learning outcomes) của tài liệu là trang bị cho người học tư duy mô hình hóa các bài toán cực trị có ràng buộc, nắm vững quy trình các thuật toán tối ưu tiêu biểu và phát triển năng lực chuyển đổi các thuật toán đó thành chương trình máy tính.

Cấu trúc giáo trình bao gồm 4 chương trọng tâm:

• Chương 1: Qui hoạch tuyến tính dạng đặc biệt.
• Chương 2: Các phương pháp của quy hoạch nguyên.
• Chương 3: Các phương pháp tối ưu trên mạng và đồ thị.
• Chương 4: Các phương pháp quy hoạch phi tuyến.

Cách tiếp cận của giáo trình tập trung vào tính ứng dụng và khả năng hiện thực hóa thuật toán. Tài liệu giản lược các chứng minh toán học thuần túy phức tạp, ưu tiên diễn giải ý tưởng cơ bản, cấu trúc từng bước của thuật toán, đi kèm ví dụ tính toán số học cụ thể và hệ thống bài tập thực hành. Toàn bộ bản thảo được soạn thảo bằng hệ thống xử lý văn bản chuyên dụng AMSTEX nhằm đảm bảo tính chuẩn xác về mặt ký hiệu toán học.

---

Nội dung kiến thức cốt lõi

Các chương và chủ đề chính

Cấu trúc nội dung của tài liệu được thiết kế theo tiến trình logic từ các mô hình tuyến tính mở rộng đến các lớp bài toán nâng cao:

1. Quy hoạch tuyến tính dạng đặc biệt (Chương 1):

   • Quy hoạch tuyến tính với biến bị chặn trên ($0 \le x_j \le u_j$): Phân tích kỹ thuật tách ràng buộc biên ra khỏi hệ ràng buộc chính để giảm số lượng hàng trong bảng đơn hình, quy tắc xác định bước nhảy $\theta = \min(\theta_1, \theta_2, \theta_3)$ và biến đổi cơ sở khi biến phi cơ sở nhận giá trị tại cận trên.
   • Quy hoạch tuyến tính tham số: Khảo sát bài toán với hàm mục tiêu phụ thuộc tham số $f(t) = \sum (c_j + t d_j)x_j$ hoặc vế phải phụ thuộc tham số $b_i(t) = b_i + t q_i$. Phân tích tính chất lõm tuyến tính từng khúc của hàm giá trị tối ưu $f^*(t)$ và phương pháp xác định các khoảng tối ưu liên tục $[\underline{t}, \bar{t}]$.
   • Phương pháp phân rã quy hoạch tuyến tính (Dantzig-Wolfe): Vận dụng định lý biểu diễn tập lồi đa diện để giải bài toán quy mô lớn thông qua việc giải bài toán phối hợp cấp cao (Master Problem) kết hợp với bài toán con (Subproblem), xử lý trường hợp tập phương án không bị chặn và mô hình ma trận có cấu trúc đường chéo khối.
   • Thuật toán điểm trong Karmarkar: Trình bày nguyên lý giải quy hoạch tuyến tính trong thời gian đa thức thông qua việc di chuyển bên trong miền chấp nhận được bằng phép chiếu gradient và kỹ thuật thay đổi thước đo (rescaling), so sánh hiệu năng với thuật toán đơn hình cổ điển của Dantzig.
   • Quy hoạch tuyến tính nhiều mục tiêu: Kỹ thuật xử lý các mức mục tiêu (cận dưới, cận trên, mức hai phía) bằng biến phụ phân rã $y_j = y_j^+ - y_j^-$, giải quyết bài toán không ưu tiên và bài toán có ưu tiên theo phương pháp tuần tự hoặc phương pháp trực tiếp sử dụng hệ số phạt lớn $M$.

2. Quy hoạch nguyên (Chương 2): Cung cấp các phương pháp giải bài toán tối ưu với điều kiện ràng buộc các biến nhận giá trị nguyên (phương pháp lát cắt Gomory, phương pháp nhánh và cận).

3. Tối ưu trên mạng và đồ thị (Chương 3): Khảo sát các bài toán tối ưu cấu trúc mạng (bài toán luồng cực đại trong mạng, đường đi ngắn nhất, cây khung nhỏ nhất, bài toán vận tải mở rộng).

4. Quy hoạch phi tuyến (Chương 4): Xây dựng phương pháp giải các bài toán tối ưu có hàm mục tiêu hoặc hệ ràng buộc phi tuyến (điều kiện Karush-Kuhn-Tucker, quy hoạch lồi, quy hoạch toàn phương, các phương pháp gradient).

Kiến thức nền tảng được xây dựng

Giáo trình thiết lập hệ thống lý thuyết nền tảng vững chắc bao gồm:

• Lý thuyết tối ưu và tập lồi: Định lý biểu diễn tập lồi đa diện qua các đỉnh cực biên và tia hướng vô hạn; tính chất đối ngẫu trong quy hoạch tuyến tính.
• Nguyên lý tiệm cận và quy hoạch rời rạc: Bản chất hình học của các phương pháp đi theo biên (đơn hình) đối chiếu với phương pháp đi qua không gian bên trong (thuật toán điểm trong Karmarkar).
• Lý thuyết xấp xỉ và đa mục tiêu: Xử lý sai số, mô hình hóa bài toán hồi quy tuyến tính theo tiêu chuẩn tối thiểu hóa tổng độ lệch tuyệt đối $\sum |a x_i + b - y_i|$.

Kỹ năng phát triển

• Kỹ năng mô hình hóa: Chuyển đổi các bài toán kinh tế - kỹ thuật thực tế (lập kế hoạch sản xuất 3 loại sản phẩm tối ưu vốn và lao động, phân phối tài nguyên, xác định tham số hồi quy) thành mô hình toán học chuẩn xác.
• Kỹ năng tính toán giải thuật: Thực hiện thành thạo các bước tính bảng đơn hình mở rộng, bảng đơn hình đối ngẫu, kiểm tra dấu ước lượng $\Delta_k(t)$ và phân tích độ nhạy.
• Kỹ năng lập trình thuật toán: Cấu trúc thuật toán được chuẩn hóa từng bước (Bước 0 đến Bước 5) giúp người học dễ dàng chuyển mã trực tiếp sang các ngôn ngữ lập trình như Pascal, C, FoxPro, Basic hoặc Java.

---

Phương pháp giảng dạy và học tập

Tiếp cận sư phạm

Giáo trình áp dụng phương pháp sư phạm định hướng thực hành (algorithmic and practical approach). Thay vì tập trung vào hệ thống tiên đề và các chứng minh giải tích phức tạp, tác giả chú trọng vào:

1. Trình bày bản chất hình học và ý tưởng cốt lõi của giải thuật.
2. Quy chuẩn hóa các bước thực thi thuật toán một cách tường minh.
3. Cung cấp ví dụ mẫu có số liệu đầy đủ, minh họa rõ ràng qua các bảng tính trung gian.

+--------------------------+
| Ý tưởng cơ bản & Mô hình |
+--------------------------+
             |
             v
+--------------------------+
| Thuật toán chi tiết bước |
+--------------------------+
             |
             v
+--------------------------+
|  Ví dụ tính toán số học  |
+--------------------------+
             |
             v
+--------------------------+
| Cài đặt code máy tính &  |
|     Bài tập tự giải      |
+--------------------------+

Bài tập và ví dụ minh họa

Tài liệu tích hợp hệ thống ví dụ số chi tiết cho từng dạng toán:

• Ví dụ giải bài toán biến bị chặn trên qua 2 bước lặp bảng đơn hình.
• Ví dụ giải quy hoạch tham số $P(t)$ với miền tham số được phân rã thành các khoảng $(-\infty, -4/19]$, $[-4/19, 2/3]$ và $[2/3, +\infty)$.
• Mô hình hóa bài toán kinh tế đa mục tiêu với số liệu thực tế về sản lượng, hạn mức lao động và vốn đầu tư kèm đáp số đối chứng cụ thể.

Hướng dẫn tự học và đánh giá

Người học được khuyến nghị thực hiện quy trình tự học 3 giai đoạn:

• Giai đoạn 1: Tái hiện lại phép tính của các ví dụ mẫu trên bảng đơn hình để hiểu cơ chế đổi cơ sở và tính vector ước lượng.
• Giai đoạn 2: Tự giải hệ thống bài tập ở cuối mỗi mục và đối chiếu với đáp số được cung cấp trong sách.
• Giai đoạn 3: Viết mã nguồn chương trình máy tính dựa trên mô tả thuật toán chi tiết để kiểm tra kết quả tự động.

---

Điểm nổi bật và cập nhật học thuật

Tích hợp các thuật toán hiện đại

Tài liệu cập nhật các bước tiến quan trọng của lý thuyết tối ưu hóa thế kỷ 20:

• Thuật toán Karmarkar (1984): Giới thiệu chi tiết giải thuật điểm trong với độ phức tạp đa thức, khắc phục hạn chế số bước lặp tăng theo hàm mũ trong trường hợp xấu nhất của phương pháp đơn hình (chứng minh bởi Klee và Minty, 1972).
• Phương pháp phân rã Dantzig-Wolfe: Cung cấp công cụ giải quyết bài toán quy hoạch tuyến tính cỡ lớn có cấu trúc khối liên kết, mở đường cho việc áp dụng tính toán song song trên hệ thống máy tính.

So sánh hai trường phái thuật toán trong giáo trình:
- Phương pháp Đơn hình (Dantzig, 1947):
  + Không gian duyệt: Đi dọc theo các đỉnh cực biên trên biên của miền ràng buộc lồi.
  + Quy mô tối ưu: Rất hiệu quả với các bài toán dưới vài trăm ràng buộc.
  + Phân tích độ nhạy: Rất thuận tiện để phân tích sau tối ưu.
- Thuật toán Điểm trong (Karmarkar, 1984):
  + Không gian duyệt: Đi xuyên qua phần bên trong (nội biên) của miền ràng buộc.
  + Quy mô tối ưu: Vượt trội với bài toán cỡ lớn (hàng chục ngàn ràng buộc).
  + Tính chất toán học: Thuật toán thời gian đa thức đã được chứng minh.

Ứng dụng thực tế đa dạng

Giáo trình liên hệ trực tiếp toán tối ưu với các bài toán thực tiễn:

• Bài toán điều hành xí nghiệp đa mục tiêu (cân đối giữa tối đa hóa lợi nhuận, duy trì quy mô lao động 4.000 người và hạn mức ngân sách đầu tư 55 triệu đồng).
• Xử lý bài toán thống kê thực nghiệm bằng mô hình quy hoạch tuyến tính để tìm phương trình hồi quy $y = ax + b$ đạt cực tiểu tổng độ lệch tuyệt đối.

---

Đối tượng sử dụng giáo trình

Phân loại người học và điều kiện tiên quyết

• Sinh viên đại học/cao đẳng: Sinh viên năm 3, năm 4 thuộc các nhóm ngành Khoa học tự nhiên (Toán ứng dụng, Tin học), Khoa học kỹ thuật (Công nghệ thông tin, Hệ thống công nghiệp, Điện tử) và Kinh tế (Kinh tế học, Quản trị sản xuất, Vận trù học).
• Học sinh chuyên Tin: Đối tượng ôn luyện các kỳ thi lập trình thuật toán cần nắm vững cấu trúc các mô hình quy hoạch tuyến tính và luồng mạng.
• Kỹ sư và Lập trình viên: Kỹ sư vận hành cần công cụ tối ưu hóa chi phí sản xuất và phân bổ nguồn lực; lập trình viên cần thuật toán chuẩn hóa để xây dựng phần mềm tối ưu.

Kiến thức tiên quyết (Prerequisites)

Để tiếp thu hiệu quả giáo trình, người học cần có kiến thức nền tảng về:

1. Đại số tuyến tính: Không gian vector, phép tính ma trận, hệ phương trình đại số tuyến tính, hạng của ma trận.
2. Giải tích cổ điển: Đạo hàm, vi phân, cực trị hàm nhiều biến.
3. Quy hoạch tuyến tính cơ bản: Khái niệm phương án cực biên, dạng chính tắc và phương pháp đơn hình cơ sở.

---

Câu hỏi thường gặp

1. Giáo trình này phù hợp nhất với những đối tượng nào?

Tài liệu được biên soạn phục vụ sinh viên năm cuối các khối ngành kỹ thuật, kinh tế, khoa học tự nhiên, các kỹ sư phân tích hệ thống và lập trình viên cần triển khai giải thuật tối ưu trên máy tính.

2. Cần chuẩn bị những kiến thức nền tảng nào trước khi học?

Người học cần hoàn thành các học phần toán đại cương bao gồm Đại số tuyến tính, Giải tích toán học và nắm được nguyên lý giải bài toán quy hoạch tuyến tính cơ bản bằng phương pháp đơn hình.

3. Giáo trình này có điểm gì khác biệt so với các sách lý thuyết tối ưu hóa khác?

Tài liệu tập trung vào tính toán số trị và cấu trúc giải thuật thực thi thay vì trình bày các chứng minh giải tích thuần túy; các thuật toán được mô tả từng bước rõ ràng để có thể lập trình trực tiếp trên các ngôn ngữ máy tính.

4. Phương pháp nào giúp tự học giáo trình đạt hiệu quả cao nhất?

Người học nên kết hợp giải tay các bảng số liệu ví dụ mẫu, đối chiếu kết quả bài tập ở cuối chương và viết chương trình máy tính (C/Java/Python) để tự động hóa thuật toán.

5. Giáo trình có cung cấp đáp số cho các bài tập tự rèn luyện không?

Có. Hệ thống bài tập sau mỗi chuyên đề (quy hoạch biến bị chặn, quy hoạch tham số, quy hoạch nhiều mục tiêu) đều đi kèm đáp số về phương án tối ưu $x^$ và giá trị mục tiêu tối ưu $f^$ tương ứng trên từng khoảng tham số.

---

Kết luận

Giáo trình Các Phương Pháp Tối Ưu (Quyển 1) của GS. Trần Vũ Thiệu là tài liệu chuẩn mực về phương pháp số và thuật toán tối ưu hóa ứng dụng. Bằng việc kết hợp chặt chẽ giữa mô hình toán học, ví dụ số trị và cấu trúc lập trình, cuốn sách cung cấp một lộ trình học tập khoa học từ quy hoạch tuyến tính mở rộng đến quy hoạch phi tuyến và mạng đồ thị. Đây là tài liệu tham khảo giá trị phục vụ cho công tác đào tạo đại học, nghiên cứu chuyên sâu và xây dựng các phần mềm tối ưu hóa trong kinh tế và kỹ thuật.

Trích đoạn nội dung tài liệu

Chương 1. Qui hoạch tuyến tính dạng đặc biệt. Qui hoạch tuyến tính với biến bị chặn trên. Nội đung vấn đề.

Phương pháp xử lý biến bị chặn trên. Ví dụ minh họa. Qui hoạch tuyến tính tham số. Nội dung bài toán .- -:sc Sc St ssikeirrrerrsrrke 17 2.

Phương pháp giải. Ví dụ minh họa. Về phải phụ thuộc tham số. Phân rã qui hoạch tuyến tính.

Tư tưởng cơ bản của phương pháp phân rã. Phân rã khi miền G không bị chặn. Xác định phương án tựa xuất phát. Qui hoạch tuyến tính có cau trúc khối §4.

Thuật toán điểm trong Karmarkar. Vài nét lịch sử phát triỂn. Nội dung phương pháp Karmarkar. So sánh với phương pháp đơn hình.

Qui hoạch tuyến tính nhiều mục tiêu. Qui hoạch nhiều mục tiêu không ưu tiên. Qui hoạch nhiều mục tiêu có ưu tiên.--------- 65 Đài LẬP sázt19006160160601E0G19E0E1E14A4153535363143838SIX411EEES14G1S1348813388 71 Chương1 QUI HOẠCH TUYỂN TÍNH DANG DAC BIET §1. QUI HOACH TUYEN TiNH VOI BIEN BI CHAN TREN 1.

Nội dung vấn đề Xét bài toán qui hoạch tuyến tính dạng bất kỳ (chính tắc, chuẩn tắc, tổng quát), trong đó một số biến hay tất cả các biến số có thêm ràng buộc dạng sau đây, gọi là rằng buộc cận trên: ø S Mị,J€ư/ € {1\2,:::¡n}; (1.1) trong đó +; là hằng số dương cho trước biểu thị giá trị tối đa mà biến z; có thể nhận. Kinh nghiệm tính toán giải các bài toán qui hoạch tuyến tính bằng phương pháp đơn hình cho thấy thời gian giai phụ thuộc chủ yếu vào số ràng buộc chính m, còn các ràng buộc không âm (ràng buộc về dấu) có ảnh hưởng không đáng kể. Vì thế, nếu ghép thêm các ràng buộc cận trên (1.1) vào các ràng buộc chính sẽ làm tăng đáng kể thời gian tính toán. Để khắc phục nhược điểm này, ta hãy tạm gác bỏ các ràng buộc cận trên khỏi các ràng buộc chính và sẽ xử lý chúng một cách riêng biệt, tương tự như đã làm đối với các ràng buộc về dấu.

Việc tạm bỏ qua các ràng buộc cận trên như thế sẽ không anh hưởng tới kết qua giải, nếu như không có biến số nào tăng vượt quá cận trên của nó. Chi khi đưa một biến mới vào cơ sở (tăng giá trị của nó) để chuyển sang phương án cực biên mới, thì phương pháp đơn hình có thể sẽ làm tăng một số biến cơ sở. Vì thế, cần có biện pháp xử lý đảm bảo cho các biến cơ sở không tăng vượt quá cận trên của chúng. Phương pháp xử lý biến bị chặn trên Xét bài toán qui hoạch tuyến tính với các biến bị chặn trên có dạng như sau: n j= Sot —> mịn, (1.2) j=l với các điều kiện So airy = bi, i=1,2,.5) trong đó u; là các hằng số dương hữu hạn, cho trước.

Khi mị < n thì chỉ một số biến có cận trên, còn nếu mị = n thì mọi biến đều bị chặn trên. Ký hiệu 4; = (a1j;,42j,---;@mj)? là véctơ cột thứ7 cua ma trận ràng buộc (1. Cũng như trước đây, vécto 2? = (21, 22,.,2n) thoa man các điều kiện (1.5) được gọi là một phương án. Một phương án đạt cực tiểu của hàm mục tiêu (1.2) gọi là một phương án tối ưu hay lời giải của bài toán (1.

Về đại thể phương pháp giải bài toán (1.5) tương tự như phương pháp đơn hình giải qui hoạch tuyến tính, nghĩa là ta sẽ xuất phát từ một phương án cực biên nào đó, mỗi phương án cực biên sẽ tương ứng với một cơ sở, dựa vào cơ sở này ta sẽ tính ước lượng cho các biến phi cơ sở, nếu các ước lượng thoả mãn tiêu chuẩn tối ưu thì dừng thuật toán. Trái lại, ta sẽ tìm cách thay đổi cơ sở để chuyển sang một phương án cực biên mới tốt hơn. Quá trình này được tiếp tục cho đến khi nhận được phương án tối ưu. Các khái niệm phương án cực biên, cơ sở, tiêu chuẩn tối uu.

về cơ bản vẫn tương tự như cũ, tuy nhiên cần có đôi chút sửa đổi cho phù hợp với bài toán mới (1. Phương án z được gọi là phương án cực biên nếu hệ véctơ {Aj:0<2; <u;, j7 Sn1}U{A; tT7 >Ũ, 7 >m}. là độc lập tuyến tính. Cơ sở cuả một phương án cực biên ở đây được hiểu là tập chỉ số J C {1,2,.,n} thoa mãn |J| = m, {A;;j € J} độc lap tuyén tinh va dD {7 20 = a < ty, f Sy} Us op 30, 2 Soni fe Cac bién x;,j € J goi la biến cơ sở, còn biến z;,7 ¢ J gọi là biến phi cơ sở.

Khác với phương pháp đơn hình thông thường, biến phi cơ sở ở đây có thể nhận giá trị dương: z; = Uj. Biến thể sau đây của phương pháp đơn hình cho phép giải bài toán (1.5) sau một số hữu hạn bước lặp. Bước 0: Xây dựng phương án cực biên ban đầu z1 (chẳng hạn theo phương pháp phạt hay đánh thuế như trong qui hoạch tuyến tính). Ký hiệu cơ sở của phương an a! là J).

Tìm các hệ số khai triển z;¿ (7 € J, k # 7¡) của véctơ 4¿ từ hệ phương trình: Ax = »` #/kÂ;, k ¢ Jy. JEN và tính các ước lượng (Cũng như trước đấy, A; = 0 với mọi j € Jy nén khong can tính). Giá trị biến cơ sơ còn được tính từ hệ phương trình sau: b— ». = ÀmJẢ,, J¢ J JEN trong đó b = (b,b;,.,b„)” là véctơ các hệ số ở vế phải ràng buộc (1.

Bang don hình tương ứng với phương án cực biên z 1 có dạng như sau: T10 T11 #12 tee Zin #20 T21 T22 tee Z2n #m0 #Ÿm1 #m2 tae Tmmn #m+10 |ŸØm+1l Lm4+12 --- Tm+ln trong đó z;, là giá trị biến thứ ¿ trong cơ sơ (biến s;), #m+1,0 là giá trị hàm mục tiêu, zm+¡,; là các ước lượng A¡. Đặt k = 1 và tiến hành Bước 1 của vòng lặp thứ È. Bước 1: kiểm tra tối ưu. Phương án hiện có zẺ là tối ưu nếu điều kiện sau đây được thoa mãn A¿ < 0 với mọi j ý J¿ và z‡ =0, ges Š 3 Ñ k A; > 0 với mọi j ý J¿ và z; = u¿, 10 Nếu tiêu chuẩn tối ưu trên không thoa mãn, ta chuyển sang Bước 2.

Bước 2: tìm cột quay. Chọn biến phi cơ sở z¿ đưa vào cơ sở (nếu cần) theo qui tắc: A = max(AT,A~) với AT = max {A;:j ¢ Jz, xf = 0}, A™~ = max {-A;:j ¢ Jk, +} =u;}, (Theo qui ước chung, max trên tập rỗng bằng —os). Ký hiệu s ý 7; là chỉ số sao cho A = A,. Có hai trường hợp xay ra: a) A, > 0: giá trị biến phi cơ sở z; với z‡ = 0 sẽ tăng và biến này sẽ trở thành biến cơ sở nếu giá trị mới cuả nó chưa đạt tới cận trên u;.

b) A, <0: gid trị biến phi cơ sở z, với z‡ = u¿ sẽ giảm và biến này sé trở thành biến cơ sở nếu giá trị mới cuả nó vẫn dương. Bước 3: tìm dòng quay. Ký hiệu Ø = min (41, 42, 93) với (1.6) +oœ_ nếu s >7, Øy —= ty nếu s < mm, e Truong hop A, >0: 6, = min ce : Lis > OF, Tis 11 e Truong hop A, <0: T¡0 6, = min{ tis < O}, Tis š tạ; — T¡0 6; = min {— tis > 0,5; <r} Lis (Nếu s;¿ > mị với mọi ? = 1,2,.,m, nghĩa là mọi biến cơ sở đều không bị chặn trên thì đặt 0; = +oo. Điều này phù hợp với qui ước chung là min trên tập rỗng bằng +œ).

Nếu Ø < Ø¡, thì biến tương ứng với dòng đạt min cua 6 trong (1.6) sẽ bị loại khỏi cơ sở. Bước 4: biến đổi cơ sở. Nếu 0 = 0, thi co so khong thay đổi, chỉ có phương án và giá trị mục tiêu cuả bài toán biến đổi. Trái lại, ký hiệu r là dòng cuả bảng đơn hình đạt min cua Ø trong (1.6), khi đó biến ¿„ sẽ bị loại khỏi cơ sở và biến s sẽ trở thành biến cơ sở.

Cơ sở mới sẽ là: Tei = (Je \ {ir}) U {5}. Bước 5: biến đổi phương án và giá trị mục tiêu. e Trường hợp A, >0: Giá trị các biến cơ sơ: tig = #¡o — Ö2¡¿, ¡ = 1,2,. Giá trị biến cơ sở mới khi Ø < đị : z; = Ø.

Giá trị biến phi cơ sở: nếu Ø = Ø¡ thì: z¡ t8 = u¿, còn nếu 0 <0) thì: z; = tro —Ô7y;. Giá trị mục tiêu: #„ tp = #m+1o — Ô¡. e Truong hop A, <0: Giá trị các biến cơ sơ: Tịp = #;o +Ôz¡;, ¿ = 1,2,. Giá trị biến cơ sở mới khi Ø < Ổi : vig = tu; — Ô.

12 Giá trị biến phi cơ sở: nếu Ø = Ø; thì: x! = 0, con néu 8 <0) thì: zi, = #rọ +Ôz;;. Giá trị mục tiêu: #„¡ọ = #m+lo +ÓÁ,. Biến đổi dòng quay (dòng P)¿ fj = Laz / Prey J Hy Qyevegns Biến đổi các dòng khác cua bang don hình: ! — ae. 1 — Tịj — Tis, = ¡j — #r7Tis; ¿ =1,2,.

Như vậy, n cột cuối cuả bảng được biến đổi hoàn toàn giống như trong phương pháp đơn hình thông thường, chỉ có điều khác là ở đây phần tử chính (phần tử quay) có thể là số âm. Quay lại Bước 1 cuả vòng lặp k + 1. Vi du minh hoa Giải bài toán qui hoạch tuyến tính sau: f = zy +22. +23 —> min, với các điều kiện 47 + T2 = 8, —271 + z3 =4, 0<z¡<4,0<z;<10,0<z <6.

Trong bài toán này cả 3 biến đều bị chặn trên (uị = 4,uạ = 10, us = 6). Phương án cực biên ban dau: c! = (0 8 4) (không cần thêm biến gia). z;,+; là biến cơ sở : Jy = {2,3}. z¡ là biến phi cơ sở.

(4 - 2) là các hệ số khai triển cua véctơ điều kiện 4i theo các vếctơ cơ so Aj, A3. Bang don hình ban đầu có dạng: cq = 1 = #7 cy x! Ty = 0 |z;=8 „=4 zs |cạ=2 |zio= 8 | = 4|Zi¿=Ll|ziz¿=0 T3 ca = Ì #20 —= 4 T21 =—2 +23 — 23 = l 30 = 20 03, = 5 +32 —= +33 — 0 Bước 1. Kiểm tra tối ưu: phương án z! hiện có chưa phải là tối ưu, vì biến phi cơ sở z¡ có z = 0 và A¡ =5 >Ũ. Tìm cột quay: biến z¡ được chọn đưa vào cơ sở.

Chọn dòng quay: 6¡ = uị = 4, 0 = 8/4 = 2, 63 = (6—4)/2 = 1. Bién x3 tuong ứng bị loại khỏi cơ sở (r = 2). Phần tử quay là zại = —2. Đổi cơ sở: Do Ø = 1 < 6¡ = 4 nên biến z¡ vào cơ sở thay cho biến cơ sở ở dòng 2 (biến z¿): J; = {2,1}.