Giáo trình Toán Tối Ưu - Nguyên Văn Long (Chủ biên) - ĐH Giao thông Vận tải

Chuyên khảo toán học phân tích Toán tối ưu, đánh giá các khía cạnh quan trọng, đề xuất hướng nghiên cứu tiếp theo., phục vụ nghiên cứu và ứng dụng thực tiễn

• Đề tài: Toán Tối Ưu

Mục lục chi tiết

• LỜI NÓI ĐẦU
• 1. CHƯƠNG 1: BÀI TOÁN TỐI ƯU HÓA TỔNG QUÁT VÀ CÁC VẤN ĐỀ MÔ HÌNH TOÁN HỌC
• 1.1. BÀI TOÁN TỐI ƯU HÓA TỔNG QUÁT VÀ PHÂN LOẠI BÀI TOÁN
• 1.1.1. Bài toán tối ưu hóa tổng quát
• 1.1.2. Phân loại bài toán
• 1.2. VẤN ĐỀ MÔ HÌNH TOÁN HỌC
• 1.2.1. Xây dựng mô hình hóa toán học
• 1.2.2. Giới thiệu một số bài toán tiêu biểu
• 1.2.2.1. Bài toán lập kế hoạch sản xuất tối ưu
• 1.2.2.2. Bài toán vận tải
• 1.2.2.3. Bài toán người du lịch
• 1.2.2.4. Bài toán cái túi
• 1.3. MỘT SỐ KHÁI NIỆM VÀ KẾT QUẢ TỪ ĐẠI SỐ
• 1.3.1. Không gian Euclide n chiều
• 1.3.2. Các khái niệm cơ bản
• 1.3.3. Các phép toán đối với ma trận
• 2. CHƯƠNG 2: QUY HOẠCH TUYẾN TÍNH
• 2.1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH TỔNG QUÁT DẠNG CHUẨN VÀ DẠNG CHÍNH TẮC
• 2.1.1. Bài toán QHTT tổng quát
• 2.1.2. Dạng chuẩn tắc và dạng chính tắc
• 2.1.3. Đưa bài toán QHTT về dạng chuẩn tắc hoặc chính tắc
• 2.2. GIẢI QHTT DẠNG CHUẨN VỚI 2 BIẾN SỐ BẰNG PHƯƠNG PHÁP HÌNH HỌC
• 2.2.1. Bài toán
• 2.2.2. Ví dụ
• 2.2.3. Các tính chất
• 2.3. TIÊU CHUẨN NHẬN BIẾT PHƯƠNG ÁN CỰC BIÊN
• 2.4. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI QUY HOẠCH TUYẾN TÍNH
• 3. CHƯƠNG 3: BÀI TOÁN VẬN TẢI
• 4. CHƯƠNG 4: QUY HOẠCH ĐỘNG
• 5. CHƯƠNG 5: SƠ ĐỒ MẠNG
• 6. CHƯƠNG 6: QUY HOẠCH PHI TUYẾN

Tóm tắt

I. Khám phá Toán tối ưu Tổng quan và các khái niệm cốt lõi

Toán tối ưu là một nhánh của toán học ứng dụng, tập trung vào việc tìm kiếm giá trị tốt nhất (tối đa hoặc tối thiểu) của một hàm mục tiêu trong một tập hợp các lựa chọn khả thi, được xác định bởi các điều kiện ràng buộc. Lĩnh vực này là nền tảng của nghiên cứu vận hành và khoa học dữ liệu, cung cấp công cụ để ra quyết định hiệu quả trong kinh tế, kỹ thuật, và quản lý. Về bản chất, mọi bài toán tối ưu đều tìm cách trả lời câu hỏi: làm thế nào để đạt được kết quả tốt nhất với nguồn lực hạn chế? Theo tài liệu giáo trình toán tối ưu của Nguyên Văn Long (2007), một bài toán tối ưu hóa tổng quát được phát biểu dưới dạng tìm phương án x* thuộc miền ràng buộc D sao cho giá trị f(x*) là nhỏ nhất hoặc lớn nhất. Miền ràng buộc D là tập hợp các giải pháp thỏa mãn tất cả các giới hạn của bài toán, ví dụ như giới hạn về ngân sách, thời gian, hoặc vật liệu. Các biến quyết định (x) đại diện cho các lựa chọn cần đưa ra, chẳng hạn như số lượng sản phẩm cần sản xuất hoặc lộ trình vận chuyển. Quá trình mô hình hóa toán học là bước đầu tiên và quan trọng nhất, chuyển đổi một vấn đề thực tế thành một cấu trúc toán học rõ ràng. Sự thành công của việc giải quyết bài toán phụ thuộc rất nhiều vào độ chính xác của mô hình này. Lĩnh vực tối ưu hóa được phân loại dựa trên đặc điểm của hàm mục tiêu và các hàm ràng buộc, tạo ra các phương pháp giải quyết chuyên biệt cho từng loại bài toán, từ đơn giản đến phức tạp.

1.1. Phân loại các bài toán tối ưu hóa phổ biến

Việc phân loại các bài toán tối ưu là cần thiết để lựa chọn phương pháp giải phù hợp. Dựa trên tính chất của các hàm số và biến số, các bài toán được chia thành nhiều nhóm chính. Quy hoạch tuyến tính (Linear Programming) là dạng phổ biến nhất, trong đó cả hàm mục tiêu và các điều kiện ràng buộc đều là các hàm tuyến tính. Ngược lại, quy hoạch phi tuyến (Nonlinear Programming) xử lý các bài toán có ít nhất một hàm không tuyến tính, làm tăng độ phức tạp của việc tìm lời giải. Khi các biến quyết định phải nhận giá trị nguyên, bài toán được gọi là quy hoạch nguyên. Một trường hợp đặc biệt là tối ưu hóa tổ hợp, nơi miền ràng buộc là một tập hợp hữu hạn hoặc đếm được các tổ hợp, ví dụ như bài toán người du lịch (TSP). Ngoài ra, lập trình động (Dynamic Programming) là phương pháp giải quyết các bài toán mà quyết định được đưa ra theo từng giai đoạn hoặc theo thời gian. Các loại hình khác bao gồm quy hoạch tham số (khi hệ số phụ thuộc tham số) và quy hoạch đa mục tiêu (khi cần tối ưu nhiều hàm mục tiêu cùng lúc). Mỗi loại hình đòi hỏi một bộ công cụ và thuật toán riêng biệt để tìm ra phương án tối ưu.

1.2. Các thành phần cơ bản của một mô hình tối ưu

Một mô hình tối ưu hóa hoàn chỉnh bao gồm ba thành phần cốt lõi. Thứ nhất là các biến quyết định, ký hiệu là x = (x₁, x₂, ..., xn), đại diện cho các đại lượng có thể kiểm soát và cần được xác định giá trị. Ví dụ, trong bài toán sản xuất, biến quyết định có thể là số lượng mỗi loại sản phẩm cần sản xuất. Thứ hai là hàm mục tiêu, f(x), là hàm số biểu thị mục tiêu cần đạt được, có thể là tối đa hóa lợi nhuận hoặc tối thiểu hóa chi phí. Hàm này phụ thuộc vào các biến quyết định. Mục tiêu của bài toán là tìm bộ giá trị của các biến quyết định để hàm mục tiêu đạt giá trị tối ưu. Cuối cùng là các điều kiện ràng buộc, là các phương trình hoặc bất phương trình biểu diễn các giới hạn về nguồn lực hoặc các quy định phải tuân thủ. Các ràng buộc này xác định một không gian các giải pháp khả thi, hay còn gọi là miền ràng buộc D. Một phương án chỉ được coi là hợp lệ nếu nó thỏa mãn tất cả các điều kiện ràng buộc. Việc xác định chính xác ba thành phần này là bước nền tảng để xây dựng một mô hình hóa toán học phản ánh đúng vấn đề thực tế.

II. Bài toán tối ưu Hướng dẫn mô hình hóa thách thức lớn

Quá trình chuyển đổi một vấn đề thực tế thành một bài toán tối ưu cụ thể được gọi là mô hình hóa toán học. Đây là một nghệ thuật và khoa học, đòi hỏi sự hiểu biết sâu sắc về cả vấn đề thực tiễn và các công cụ toán học. Theo Nguyên Văn Long (2007), quá trình này có thể được chia thành bốn bước cơ bản. Bước đầu tiên là xây dựng mô hình định tính, tức là xác định các yếu tố quan trọng và các quy luật chi phối chúng. Bước tiếp theo là diễn tả mô hình định tính bằng ngôn ngữ toán học, bao gồm việc định nghĩa các biến quyết định, xây dựng hàm mục tiêu và thiết lập các điều kiện ràng buộc. Thách thức lớn nhất trong giai đoạn này là đảm bảo mô hình vừa đủ đơn giản để có thể giải được, vừa đủ phức tạp để phản ánh đúng bản chất của vấn đề. Một mô hình quá đơn giản có thể dẫn đến kết quả sai lệch, trong khi một mô hình quá phức tạp có thể không thể giải quyết được bằng các thuật toán hiện có. Sau khi có mô hình, bước thứ ba là sử dụng các công cụ toán học và máy tính để tìm ra lời giải. Cuối cùng, bước quan trọng không kém là phân tích và kiểm định kết quả. Kết quả tính toán cần được so sánh với thực tế để đánh giá mức độ phù hợp của mô hình. Nếu không phù hợp, cần phải quay lại các bước trước để hiệu chỉnh lại mô hình, số liệu hoặc thuật toán. Quá trình này thể hiện tính lặp và sự tương tác chặt chẽ giữa lý thuyết và thực tiễn trong vận trù học.

2.1. Bốn bước xây dựng mô hình hóa toán học hiệu quả

Quá trình mô hình hóa toán học được chuẩn hóa thành bốn bước tuần tự. Bước 1: Xây dựng mô hình định tính. Ở bước này, cần xác định rõ mục tiêu, các yếu tố ảnh hưởng, và các quy luật quan trọng của vấn đề thực tế. Bước 2: Xây dựng mô hình toán học. Đây là bước chuyển hóa mô hình định tính sang ngôn ngữ toán học. Cần định nghĩa rõ các biến quyết định, công thức hóa hàm mục tiêu (ví dụ: f(x) → max), và xác lập hệ thống các điều kiện ràng buộc dưới dạng phương trình hoặc bất phương trình. Bước 3: Giải bài toán. Sử dụng các thuật toán và công cụ toán học phù hợp, thường là với sự hỗ trợ của máy tính, để tìm phương án tối ưu từ mô hình đã xây dựng. Việc lựa chọn phương pháp giải phụ thuộc vào dạng của bài toán (ví dụ, phương pháp đơn hình cho quy hoạch tuyến tính). Bước 4: Phân tích và kiểm định kết quả. Kết quả thu được cần được kiểm tra về tính hợp lý và độ chính xác so với thực tế. Nếu kết quả không phù hợp, cần rà soát lại toàn bộ quá trình, từ việc thu thập số liệu, xây dựng mô hình, cho đến thuật toán giải. Quá trình này có thể cần lặp lại nhiều lần để hoàn thiện mô hình.

2.2. Phân tích bài toán lập kế hoạch sản xuất tối ưu

Một ví dụ kinh điển của mô hình hóa toán học là bài toán lập kế hoạch sản xuất. Giả sử một công ty sản xuất hai loại sản phẩm A và B, sử dụng ba loại nguyên liệu I, II, III với trữ lượng có hạn. Mỗi sản phẩm mang lại một mức lợi nhuận khác nhau. Bài toán đặt ra là cần sản xuất bao nhiêu đơn vị sản phẩm mỗi loại để tổng lợi nhuận là lớn nhất. Để mô hình hóa, ta định nghĩa các biến quyết định là x₁ (số lượng sản phẩm A) và x₂ (số lượng sản phẩm B). Hàm mục tiêu là tổng lợi nhuận, ví dụ: f(x) = 4x₁ + 5x₂ → max. Các điều kiện ràng buộc được xác định bởi lượng nguyên liệu dự trữ. Ví dụ, nếu sản xuất 1 đơn vị A cần 2 đơn vị nguyên liệu I, 1 đơn vị B cần 1 đơn vị nguyên liệu I, và tổng dự trữ là 8, ta có ràng buộc: 2x₁ + x₂ ≤ 8. Tương tự, các ràng buộc khác được thiết lập cho các nguyên liệu còn lại. Ngoài ra, còn có ràng buộc không âm: x₁, x₂ ≥ 0. Mô hình này là một bài toán quy hoạch tuyến tính điển hình và có thể được giải bằng các phương pháp như phương pháp đơn hình.

III. Quy hoạch tuyến tính Hướng dẫn giải bằng phương pháp đơn hình

Quy hoạch tuyến tính (QHTT) là một trong những lĩnh vực được nghiên cứu và ứng dụng rộng rãi nhất của toán tối ưu. Đặc điểm nhận dạng của một bài toán QHTT là cả hàm mục tiêu và các điều kiện ràng buộc đều là các hàm tuyến tính của các biến quyết định. Nhờ cấu trúc đơn giản này, các bài toán QHTT có thể được giải quyết một cách hiệu quả bằng các thuật toán chuyên biệt, trong đó nổi bật nhất là phương pháp đơn hình (Simplex Method). Lý thuyết QHTT khẳng định rằng nếu một bài toán có lời giải tối ưu thì lời giải đó phải nằm tại một hoặc nhiều đỉnh (điểm cực biên) của miền ràng buộc lồi. Miền ràng buộc này là một đa diện lồi được tạo bởi giao của các nửa không gian xác định bởi các bất phương trình ràng buộc. Phương pháp đơn hình khai thác tính chất này một cách thông minh. Thuật toán bắt đầu từ một đỉnh bất kỳ của đa diện lồi, sau đó di chuyển dọc theo các cạnh đến một đỉnh kề cận có giá trị hàm mục tiêu tốt hơn. Quá trình này lặp lại cho đến khi không thể tìm thấy đỉnh nào tốt hơn, và đỉnh cuối cùng đó chính là phương án tối ưu. Sự ra đời của phương pháp này đã tạo ra một cuộc cách mạng trong nghiên cứu vận hành, cho phép giải quyết các bài toán phân bổ nguồn lực, lập kế hoạch sản xuất và vận tải quy mô lớn một cách hiệu quả.

3.1. Định nghĩa và dạng chuẩn tắc của một bài toán QHTT

Một bài toán QHTT tổng quát là bài toán tìm giá trị lớn nhất (hoặc nhỏ nhất) của một hàm tuyến tính, với các biến số thỏa mãn một hệ các phương trình hoặc bất phương trình tuyến tính. Để thuận tiện cho việc áp dụng thuật toán, các bài toán thường được đưa về dạng chuẩn tắc hoặc dạng chính tắc. Dạng chuẩn tắc của một bài toán QHTT (bài toán max) có dạng: f(x) → max, với tất cả các ràng buộc đều là dạng '≤' (ví dụ: a₁x₁ + a₂x₂ ≤ b) và tất cả các biến đều không âm (xⱼ ≥ 0). Dạng chính tắc yêu cầu tất cả các ràng buộc phải là phương trình ('=') và các biến không âm. Mọi bài toán QHTT đều có thể được chuyển đổi về hai dạng này thông qua các phép biến đổi tương đương, chẳng hạn như nhân hai vế của một bất phương trình với -1 để đổi chiều, hoặc thêm các biến phụ (biến bù, biến giả) để chuyển bất phương trình thành phương trình. Việc chuẩn hóa này là bước tiền xử lý quan trọng trước khi áp dụng phương pháp đơn hình.

3.2. Thuật toán đơn hình Nguyên lý và các bước thực hiện

Thuật toán đơn hình là một quy trình lặp để giải bài toán quy hoạch tuyến tính. Nguyên lý cốt lõi của nó là di chuyển giữa các phương án cực biên (các đỉnh của miền ràng buộc) để cải thiện dần giá trị hàm mục tiêu. Quá trình bao gồm các bước chính: Bước 1: Tìm một phương án cực biên xuất phát. Điều này tương đương với việc tìm một cơ sở ban đầu, thường được thực hiện bằng cách thêm các biến giả. Bước 2: Kiểm tra tính tối ưu. Tại đỉnh hiện tại, thuật toán kiểm tra xem có thể di chuyển đến một đỉnh kề cận nào để cải thiện giá trị hàm mục tiêu hay không. Điều này được thực hiện bằng cách tính các ước lượng (reduced costs). Nếu tất cả các ước lượng đều thỏa mãn điều kiện tối ưu, thuật toán dừng lại và phương án hiện tại là tối ưu. Bước 3: Chuyển sang phương án cực biên mới. Nếu chưa tối ưu, thuật toán sẽ chọn một biến phi cơ sở để đưa vào cơ sở (entering variable) và một biến cơ sở để đưa ra khỏi cơ sở (leaving variable). Phép biến đổi này, được gọi là phép xoay, sẽ đưa đến một phương án cực biên mới tốt hơn. Quá trình lặp lại từ Bước 2 cho đến khi tìm được lời giải tối ưu hoặc kết luận bài toán không có lời giải.

IV. Các phương pháp cho Quy hoạch phi tuyến Lập trình động

Trong khi quy hoạch tuyến tính giải quyết các vấn đề với mối quan hệ tuyến tính, thực tế lại tồn tại vô số bài toán mà trong đó hàm mục tiêu hoặc các điều kiện ràng buộc là phi tuyến. Những bài toán này thuộc lĩnh vực quy hoạch phi tuyến (QHPT), một nhánh phức tạp và đa dạng hơn của toán tối ưu. Sự phi tuyến có thể xuất phát từ các quy luật vật lý, các mô hình kinh tế với hiệu suất giảm dần, hoặc các công thức hình học. Ví dụ, tối ưu hóa danh mục đầu tư theo mô hình Markowitz là một bài toán QHPT điển hình, trong đó rủi ro (phương sai) là một hàm bậc hai. Việc giải các bài toán QHPT thường khó khăn hơn đáng kể so với QHTT. Không có một thuật toán duy nhất nào có thể giải quyết mọi bài toán QHPT. Thay vào đó, có nhiều phương pháp khác nhau, mỗi phương pháp phù hợp với một lớp bài toán cụ thể, chẳng hạn như tối ưu lồi (convex optimization), nơi các hàm là lồi, đảm bảo rằng mọi điểm cực tiểu địa phương cũng là cực tiểu toàn cục. Các thuật toán như thuật toán gradient descent và các phương pháp dựa trên nhân tử Lagrange là những công cụ nền tảng trong lĩnh vực này. Song song đó, lập trình động cung cấp một cách tiếp cận mạnh mẽ cho các bài toán tối ưu có cấu trúc đa giai đoạn, phá vỡ một vấn đề lớn thành các bài toán con đơn giản hơn.

4.1. Quy hoạch phi tuyến và các thuật toán giải quyết

Quy hoạch phi tuyến (QHPT) bao gồm việc tìm cực trị của một hàm phi tuyến với các ràng buộc cũng có thể là phi tuyến. Một lớp bài toán quan trọng trong QHPT là tối ưu lồi, nơi hàm mục tiêu là hàm lồi và miền ràng buộc là một tập lồi. Đối với các bài toán không ràng buộc, thuật toán gradient descent và các biến thể của nó (như Newton's method, Quasi-Newton methods) là rất phổ biến. Ý tưởng của gradient descent là di chuyển từng bước nhỏ theo hướng ngược lại với gradient của hàm mục tiêu để tiến tới điểm cực tiểu. Đối với các bài toán có ràng buộc, lý thuyết về nhân tử Lagrange được sử dụng để chuyển bài toán có ràng buộc thành bài toán không ràng buộc. Các điều kiện Karush-Kuhn-Tucker (KKT) là sự tổng quát hóa của phương pháp nhân tử Lagrange, cung cấp các điều kiện cần để một lời giải là tối ưu cho hầu hết các bài toán QHPT.

4.2. Lập trình động Giải quyết bài toán tối ưu đa giai đoạn

Lập trình động là một kỹ thuật tối ưu hóa toán học dùng để giải quyết các bài toán phức tạp bằng cách chia chúng thành một chuỗi các bài toán con đơn giản hơn, gối lên nhau. Nguyên lý cốt lõi của nó là Nguyên lý Tối ưu Bellman, phát biểu rằng một chính sách tối ưu có tính chất là dù trạng thái và quyết định ban đầu là gì, các quyết định còn lại phải tạo thành một chính sách tối ưu đối với trạng thái kết quả từ quyết định đầu tiên. Phương pháp này đặc biệt hiệu quả cho các bài toán có cấu trúc tuần tự hoặc đa giai đoạn theo thời gian. Các ứng dụng điển hình bao gồm bài toán đường đi ngắn nhất, bài toán cái túi (knapsack), và các bài toán lập lịch trình. Thay vì giải quyết toàn bộ vấn đề cùng một lúc, lập trình động giải quyết từng bài toán con một lần và lưu trữ kết quả của chúng để tránh tính toán lại, từ đó tăng hiệu quả đáng kể.

V. Ứng dụng của Toán tối ưu Từ vận trù học đến học máy

Sức mạnh của toán tối ưu nằm ở khả năng ứng dụng rộng rãi trong hầu hết mọi lĩnh vực của khoa học, kỹ thuật và kinh doanh. Lĩnh vực vận trù học (Operations Research) là nơi các kỹ thuật tối ưu hóa được áp dụng để giải quyết các vấn đề phức tạp trong logistics, chuỗi cung ứng, và quản lý sản xuất. Các bài toán kinh điển như 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) hay bài toán người du lịch (TSP) (tìm chu trình ngắn nhất đi qua tất cả các thành phố) đều là những ví dụ tiêu biểu. Trong tài chính, các mô hình tối ưu hóa được dùng để xây dựng danh mục đầu tư nhằm tối đa hóa lợi nhuận và giảm thiểu rủi ro. Gần đây, tối ưu hóa đã trở thành trái tim của cuộc cách mạng học máy và khoa học dữ liệu. Quá trình huấn luyện một mô hình học máy, về bản chất, là một bài toán tối ưu. Ví dụ, trong hồi quy tuyến tính hoặc mạng nơ-ron, mục tiêu là tìm một tập hợp các trọng số để tối thiểu hóa hàm mất mát (loss function) – sự khác biệt giữa dự đoán của mô hình và dữ liệu thực tế. Các thuật toán như thuật toán gradient descent và các biến thể của nó được sử dụng rộng rãi để thực hiện quá trình này. Từ việc đề xuất sản phẩm trên các trang thương mại điện tử đến nhận dạng hình ảnh, các ứng dụng của học máy đều dựa trên nền tảng vững chắc của toán tối ưu.

5.1. Các bài toán tối ưu hóa tổ hợp kinh điển nhất

Lĩnh vực tối ưu hóa tổ hợp giải quyết các bài toán tìm kiếm một đối tượng tốt nhất từ một tập hợp hữu hạn các đối tượng. Ba trong số các bài toán kinh điển nhất là: Bài toán vận tải, nhằm xác định kế hoạch vận chuyển hàng hóa từ m kho hàng đến n điểm tiêu thụ sao cho tổng chi phí vận chuyển là nhỏ nhất, đồng thời thỏa mãn nhu cầu và nguồn cung. Bài toán người du lịch (TSP), yêu cầu tìm một hành trình ngắn nhất xuất phát từ một thành phố, đi qua tất cả các thành phố khác mỗi nơi đúng một lần, và quay trở lại điểm xuất phát. Bài toán cái túi (knapsack), mô tả tình huống một người cần chọn các vật phẩm để cho vào một chiếc túi có sức chứa giới hạn, sao cho tổng giá trị của các vật phẩm là lớn nhất. Những bài toán này, dù phát biểu đơn giản, lại có độ phức tạp tính toán rất cao và là nền tảng cho nhiều vấn đề trong logistics và lập kế hoạch.

5.2. Tối ưu hóa trong lĩnh vực học máy và khoa học dữ liệu

Tối ưu hóa là một trụ cột không thể thiếu trong học máy và khoa học dữ liệu. Hầu hết các thuật toán học máy đều được xây dựng dựa trên việc tối thiểu hóa một hàm mục tiêu, thường được gọi là hàm mất mát hoặc hàm chi phí. Hàm này đo lường mức độ sai lệch giữa dự đoán của mô hình và kết quả thực tế. Ví dụ, trong các mô hình hồi quy, mục tiêu là tối thiểu hóa tổng bình phương sai số. Trong các mô hình phân loại như Support Vector Machines (SVM), mục tiêu là tìm một siêu phẳng phân tách các lớp dữ liệu với lề lớn nhất. Quá trình này được thực hiện bằng các thuật toán tối ưu, phổ biến nhất là thuật toán gradient descent và các phiên bản nâng cao như Stochastic Gradient Descent (SGD) và Adam. Do đó, sự hiểu biết về toán tối ưu là cực kỳ quan trọng đối với các nhà khoa học dữ liệu và kỹ sư học máy để xây dựng và tinh chỉnh các mô hình hiệu quả.

VI. Tương lai ngành Toán tối ưu và các công cụ lập trình mới

Lĩnh vực toán tối ưu và nghiên cứu vận hành đang tiếp tục phát triển mạnh mẽ, được thúc đẩy bởi sự gia tăng của dữ liệu lớn (Big Data) và sự phức tạp của các bài toán trong thế giới thực. Tương lai của ngành này sẽ tập trung vào việc phát triển các thuật toán hiệu quả hơn, có khả năng giải quyết các bài toán quy mô cực lớn và các mô hình phi tuyến, phi lồi phức tạp. Sự kết hợp giữa tối ưu hóa, học máy và trí tuệ nhân tạo đang mở ra những hướng đi mới, chẳng hạn như sử dụng học máy để tự động hóa việc xây dựng mô hình tối ưu hoặc để tăng tốc các thuật toán giải. Mặc dù kiến thức nền tảng từ các giáo trình toán tối ưu truyền thống vẫn vô cùng quan trọng để hiểu bản chất của vấn đề, việc triển khai thực tế ngày nay phụ thuộc nhiều vào các công cụ phần mềm mạnh mẽ. Các nhà nghiên cứu và kỹ sư không còn phải tự cài đặt các thuật toán phức tạp như phương pháp đơn hình từ đầu. Thay vào đó, họ có thể tận dụng các thư viện và bộ công cụ được tối ưu hóa cao, cho phép tập trung vào việc mô hình hóa toán học và phân tích kết quả. Sự phát triển của các công cụ này đã dân chủ hóa việc tiếp cận các kỹ thuật tối ưu hóa, đưa chúng từ phòng nghiên cứu ra ứng dụng rộng rãi trong công nghiệp.

6.1. Xu hướng nghiên cứu và phát triển trong tối ưu hóa

Tương lai của tối ưu hóa gắn liền với việc giải quyết ba thách thức chính: quy mô, độ phức tạp và tính không chắc chắn. Các nhà nghiên cứu đang phát triển các thuật toán phân tán và song song để xử lý các bài toán với hàng triệu biến và ràng buộc. Đồng thời, các phương pháp mới cho quy hoạch phi tuyến và tối ưu hóa toàn cục đang được tìm kiếm để giải quyết các mô hình phi lồi, nơi tồn tại nhiều điểm cực tiểu địa phương. Một xu hướng quan trọng khác là tối ưu hóa dưới điều kiện không chắc chắn (stochastic optimization và robust optimization), cho phép ra quyết định hiệu quả khi các tham số đầu vào của mô hình không được biết chính xác. Sự giao thoa với học máy cũng tạo ra các lĩnh vực mới như tối ưu hóa siêu tham số (hyperparameter optimization) và kiến trúc mạng nơ-ron (neural architecture search), tự động hóa quá trình thiết kế các mô hình học máy hiệu quả.

6.2. Công cụ giải toán tối ưu MATLAB và Python SciPy

Để giải quyết các bài toán tối ưu trong thực tế, việc sử dụng các công cụ phần mềm là không thể thiếu. MATLAB, với Optimization Toolbox, cung cấp một môi trường mạnh mẽ để mô hình hóa và giải quyết nhiều loại bài toán, từ quy hoạch tuyến tính, phi tuyến đến quy hoạch nguyên. Nó được sử dụng rộng rãi trong giới học thuật và kỹ thuật. Trong khi đó, hệ sinh thái Python đã trở thành một lựa chọn hàng đầu trong khoa học dữ liệu nhờ các thư viện mã nguồn mở mạnh mẽ. Python SciPy, cụ thể là mô-đun scipy.optimize, cung cấp một bộ sưu tập đa dạng các thuật toán tối ưu, bao gồm các phương pháp như phương pháp đơn hình, BFGS, và Nelder-Mead. Ngoài ra, các thư viện chuyên dụng như CVXPY (cho tối ưu lồi) và PuLP (cho quy hoạch tuyến tính) giúp người dùng dễ dàng phát biểu và giải các bài toán tối ưu một cách trực quan và hiệu quả, làm cho việc ứng dụng lý thuyết từ giáo trình toán tối ưu vào thực tiễn trở nên dễ dàng hơn bao giờ hết.

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

đặt vấn đề, mô trình, cách chuẩn hình toán học, thuật toán tối ưu, chương việc cần bị số liệu đưa vào máy tính nghĩa là toàn bộ công thiết cho việc áp dụng mô hình và kết quả để giải quyết vấn đề đặt ra. Khả năng 2: Mô hình và kết quả tính toán không phù hợp với thực tế, cần xem xét lại quá trình xây dựng. Có thể nêu ra 4 nguyên nhân: 1. Các kết quả tính toán trong bước 3 chưa có đủ độ chính xác cần thiết.

Khi đó cần phải xem lại các thuật toán cũng như các chương trình tính toán đã viết và sử dụng. Các số liệu ban đầu không phản ánh đúng thực tế giá cả hoặc chỉ phí trên thị trường hoặc các định mức vật tư, hoặc các số liệu khác về công suất, khả năng máy móc, dự trữ tài nguyên,.Do đó cần điều chỉnh một cách nghiêm túc và chính xác. Mô hình định tính xây dựng chưa phản ánh được đầy đủ hiện tượng thực tế. Nếu vậy cần rà soát lại bước 1 xem có yếu tố hoặc quy luật nào còn bị bỏ sót không.

Việc xây dựng mô hình toán học ở bước 2 chưa đúng. Cần phải xây dựng lại cho phù hợp. Giới thiệu một số bài toán tiêu biểu 1. Bài toán lập kế hoạch sản xuất tỗi wu Một công ty cần sản xuất 2 loại sản phẩm A, B bằng các loại nguyên liệu J; Il, II.

Suất chi phí nguyên liệu để sản xuất các sản phẩm được cho trong bảng sau: Sản phẩm A B Dự trữ Nguyên liệu 1 2 1 II 1 2 7 Il 0 1 3 Tức là để sản xuất một đơn vị sản phẩm A cần dung 2 đơn vị nguyên liệuI va 1 đơn vị nguyên liệu II. Đê sản xuât một đơn vị sản phẩm B cần dùng 1 đơn vị nguyên liệu I, 2 đơn vị nguyên liệu II và 1 đơn vị nguyên liệu III. Lượng dự trữ các loại I, II và II của công ty tương ứng là 8, 7 và 3. Biết tiền lãi 1 đơn vị sản phẩm A là 4 (đơn vị tiền), 1 đơn vị sản phẩm B là 5 (don vị tien).

Hay lap ké hoach san xuất sao cho tổng tiên lãi là lớn nhất. Ki hiéu x, x2 1a số đơn vị sản phẩm A, B cần sản xuất. Ta có mô hình toán học của bài toán như sau: f(x) = 4x; + 5x. — max với các ràng buộc như sau: 2x, +x, <8 x, +2x, <7 x, <3 X,,x, 20 1.

Bài toán vận tải Giả sử có m địa điểm (kho hàng) cùng sản xuất cùng sản lượng của 1 loại sản phẩm (đánh số thứ tự 1, 2. m) với điểm thứ¡ là ai. nhu Có n điểm tiêu thụ sản phẩm (đánh số 1, 2,., n) với cầu tiêu thụ ở điểm thứ j là bị. Biết cước phí vận chuyển I đơn vị hàng hóa từ điểm i đến j là cụ (= 1,m; j = 1,n).

Hàng hóa có thể vận chuyển từ điểm ¡ đến điểmj bat ky. Để đơn giản ta gọi: “ Điểm sản xuất thứ ¡ là điểm phát thứ ¡. " Điểm tiêu thụ thứ j là điểm thu thứ j. Hãy lập kế hoạch vận chuyển sao cho tổng chỉ phí chuyên chở là nhỏ nhất trên cơ sở, điểm phát thì phát hết hàng, điểm thuj thì thỏa mãn nhu cầu.

Giả thiết rằng tổng số lượng phát bằng tổng số lượng thu. Ta có mô hình toán học của bài toán như sau: mn 35 ”c¡x¡ — min i=l jal 10 1. Bài toán người (lu lịch f Một người đi tham quan n thành phố Đuz¿y Pn xuất phát lại từ một thành phố nào đó rồi qua tất cả các thành phố còn phát. mỗi thành phố đúng một lần rồi trở về thành phố xuất tông chỉ Hãy tìm thứ tự tham quan các thành phố sao cho phí bỏ ra là it nhất.

Gọi Cụ là chỉ phí đi từ Pị đến Pị. Giả sử có một hành trình Pị, > —>. iạ) là hoán vị của Pi,. Khi đó phải tim hoan vi (ii, in, n-l Xe, fgg Chet — min.

v'j+ el Oe tính Từ bài toán trên ta thấy có tất cả n! phương án để toán hàm mục tiêu. Bài toán cái túi có trọng Một người di du lịch cần đem theo một cái túi n đô lượng không quá m, người đó được phép mang theo sử dụng là c¡ vật. Đồ vật thứ ¡ có trọng lượng là mị và giá trị Œ=1,2. Hỏi người du lịch cân đem theo những đồ vật nào để giá trị sử dụng là lớn nhât? Đưa bài toán trên về dạng bài toán tối ưu như sau: Ký hiệu một phương án mang đồ vật đi theo là x = (Xi, Xz,., Xa) với xị e {0, 1}, i= 1,n, trong đó xị = Ì nếu đồ vật ngược lại.

thứ ¡ được mang theo, xị = 0 trong trường hợp Khi đó giá trị đồ vật mang theo là: f(x) = Sem, yl 11 Tổng trọng lượng của đồ vật mang theo là: ax) = ax, il Bài toán cái túi có thể phát biểu thành bài toán tối ưu sau: Tìm phương án x thoả mãn điều kiện g(x) < b sao cho f{x) nhỏ nhật. MỘT SÓ KHÁI NIỆM VÀ KÉT QUẢ TỪ ĐẠI SÓ 1. Không gian Euclide n chiều Một véctơ n chiều là 1 hệ được sắp thứ tự gồm n số thực XỊ, Xa›. Với x = (Xa, Xa,.

Xa) Và Y = (Vi, Y2», yn) khi đó ta có một sô khái niệm cơ bản sau: x>0©x,>0, Vj (phép so sánh) x=y©x,=y, Vj x+y=(Xi +YI;X; +Y¿s«.„Xa +Yn) (phép cộng) ax = (ax,,ax,,.,0x,) (phép nhân với một số thực œ) (y)= Š xơ, (phép tích vô hướng) i=l Tập hợp tất cả các véctơ n chiều trong đó có các phép toán kể trên cùng với các tính chất của chúng gọi là không gian Euclide n chiều, kí hiệu R". Biểu diễn véctơ x thông qua các véctơ đơn vị cơ sở 12 e¡= (0, 0,. Các khái niệm cơ bản Ma trận là một bảng chữ nhật gồm m xn số sắp thành m hàng và n cột dưới dạng: ân Ay ain A=l?2 an Sạn a A = (A¡j)m„ạ ma trận có kích thước m x n. Ma trận có số hàng bằng số cột (m =n) được gọi là ma trận vuông.

Lúc đó ta nói ma trận có câp n. Ma trận mà các cột của nó là các hàng tương ứng của A được gọi là ma trận chuyển vị của A, ký hiệu là A". Ma trận chỉ có một cột được gọi là véctơ cột, còn ma trận chỉ có một hàng gọi là véctơ hàng. Ma trận vuông có dạng: được gọi là ma trận đường chéo.

13 1n thì được gọi là Ma trận đường chéo có 0¡ = 1Vi= ma trận đơn vị. g có cùng Hai ma trận được gọi là bằng nhau nếu chún nhau. kích thước và các phần tử tương ứng bằng 2. Các phép toản đối với ma trận cùng kích " Phép cộng: Tổng của.

hai ma trận A và B có bằng tổng các thước là ma trận C mà mỗi phần tử của nó B. phần tử tương ứng của ma trận A và ma trận được là "= Phép nhân ma trận với l số thực: Kết quả đạt của nó một ma trận có cùng kích thước mà mỗi phần tử ứng của ma bằng tích của hằng số nhân với phân tử tương trận ban đầu. ma " Phép nhân 2 ma trận: Ma trận A nhân được với A bằng số trận B chỉ-trong trường hợp số cột của ma trận hàng của ma trận B. A= (Ay) waa B= (Di ng C= (Cy Mor = dap ik 14 Chương 2 QUY HOẠCH TUYẾN TÍNH 2.

BÀI TOÁN QUY HOẠCH TUYẾN TÍNH TONG QUÁT DẠNG CHUĂN VÀ DẠNG CHÍNH TAC 2. Bài toán QHTT tổng quát Để thống nhất trong quá trình lập luận, ta chỉ xét bài toán tim cực đại, sau đó ta xét cách chuyên bài toán tìm cựu tiêu sang bài toán tìm cực đại. Bài toán tổng quát của QHTT có dạng: n Des — max 5 anitj <,=,>)b,,¡ =l,m 2.1) x;> 0,j=1n - Đối với bài toán min mô hình là:. f(x) = Sex, —> min jel 9 tent (<,=,2)b,,i=1,m Jel x;>0,j=l,n 15 bài toán Khi đó giữ nguyên ràng buộc, đưa nó về dạng max như sau: f(x)=—>c;x¡ — max el Nếu bài toán max có phương án tối ưu 1a x” thi bai toán min cũng có phương án tối ưu là x” và fai, = —Fmax.

That vay: Vi x’ la phuong 4n tối ưu của bài toán max nên: f(&x) =—Ề'e,x)> “Ler, Vx eD jel = Yor < Lexxvà VxeD Chứng tỏ x' là phương án tối ưu của bài toán min đồng thời: => ©xÌi= —F max jel Định nghĩa 2.z | 4 Điểm cực biên của miền D: x là điểm cực biên của D (hay còn gọi là đỉnh của D) nếu x = œ.Z với y, Z c D thì œ = 0 hoặc œ = 1. 16 Về mặt hình học: Điểm cực biên của D chính là đỉnh của đa giác lồi D. Dạng chuẩn tắc và dạng chính tắc Khi xét bài toán QHTT, chúng ta thường đưa bài toán về đạng chuẩn tắc hoặc chính tắc. Dạng chuẩn tắc: em — max Sa gOx,<b,i=lm @2) x,20,j=1,n Dạng chính tắc: i Ðc;x; —> max sử, tem đút; =),.

Đưa bài toán QHTT về dạng chuẩn tắc hoặc chính tắc Bắt kỳ QHTT nào cũng có thể đưa về 1 trong 2 dạng chuẩn tắc hoặc chính tắc nhờ các phép biến đổi tuyến tinh sau: TRƯỜNG ĐẠI HỌC GIAO THONG VAN TAI-CO SỞ 2 THU VIEN |1 a. Một ràng buộc Dar >b, có thể đưa về ràng buộc - Nay x, <=b, bằng cách nhân 2 về với (-1) và sau đó ta Jel viết lại ở dạng: >) a'jx; <bi. Một ràng buộc đẳng thức Sa Xj= b,c6 thé thay thé m bằng 2 ràng buộc bất đẳng thức >,ax,<b, và ` jel -Sa,x, gj <--b; Jel c. Một biến x¡ không bị ràng buộc dấu có thể thay bởi hiệu của 2 biến không âm bằng cách đặt: x)= xỶ¡—X ¡ với x”;>0 và x';>0.

Một ràng buộc bất đẳng thức Ÿ`a,x, <b, có thể đưa il về ràng buộc đẳng thức bằng cách đưa vào biến phụ y¡ > 0, Yayx ity =). GIẢI QHTT DẠNG CHUẢN VỚI 2 BIEN SO BẰNG PHƯƠNG PHÁP HÌNH HỌC 2. Bài toán Xét bài toán Gert mae dang athe tắc với 2 biến số như sau: ~ --~ ˆ = B14 i 18 €,X, +€;X; —> max pla tanks <b,i=lLm (2.4) x; 20,j=12 trình Tir y nghia hinh hoc ta biết rằng mỗi bất phương tuyến tính a,x,+a„x;<b,i=lm xác định l nửa mặt chính là phẳng. Do đó, tập D (miền ràng buộc của QHTT) lôi trên mặt giao của m nửa mặt phẳng và sẽ là 1 đa giác phăng.

Mặt khác xị, xạ > 0 nên đa giác lồi D nằm ở góc vuông I. Phương trình e,x,+c,xạ =œ khi œ thay đổi sẽ xác định ta trên mặt phẳng các đường thẳng song song với nhau mà gọi dây là các đường mức.