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

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… 166 trang.

• Đề 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.

Nội dung chính

Giáo Trình Toán Tối Ưu: Tổng Hợp Lý Thuyết Và Bài Toán Ứng Dụng

---

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

Giáo trình "Toán Tối Ưu" do Nguyễn Văn Long (Chủ biên) cùng ThS. Đỗ Quang Thơ biên soạn, được Nhà xuất bản Giao thông Vận tải xuất bản tại Hà Nội năm 2007 (theo Quyết định xuất bản số 184/163-2007/CXB/61-312-05/GTVT, in 520 cuốn, khổ 14,5 x 20,5 cm tại Công ty in Giao thông, nộp lưu chiểu tháng 9 năm 2007).

Về vị trí đào tạo, tài liệu được biên soạn làm tài liệu học tập và giảng dạy chính thức cho học phần Toán tối ưu (hoặc Nghiên cứu vận hành / Vận trù học), phục vụ trực tiếp cho sinh viên Khoa Công nghệ thông tin - Trường Đại học Giao thông Vận tải. Môn học nằm ở khối kiến thức cơ sở ngành, kết nối giữa toán học đại cương (Đại số tuyến tính, Giải tích) với các học phần chuyên sâu về thuật toán, tối ưu hóa hệ thống và lập trình ứng dụng.

Mục tiêu học tập của giáo trình nhằm trang bị cho người học:

• Tư duy mô hình hóa toán học đối với các bài toán ra quyết định trong sản xuất, quản lý kinh tế và kỹ thuật.
• Nắm vững cơ sở lý thuyết toán học của các dạng bài toán tối ưu từ tuyến tính, phi tuyến đến tối ưu rời rạc và động.
• Thành thạo các giải thuật tối ưu kinh điển (như phương pháp hình học, thuật toán đơn hình, bài toán $M$ lớn).
• Phát triển năng lực thuật toán hóa để cài đặt và giải quyết các bài toán tối ưu quy mô lớn trên máy tính.

Cấu trúc giáo trình gồm 6 chương chuyên đề, được tổ chức theo phương pháp đi từ tổng quan mô hình hóa toán học, hệ thống lại các công cụ đại số cần thiết, đến việc khảo sát chi tiết từng lớp bài toán tối ưu cụ thể và các phương pháp giải tương ứng.

---

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

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

Nội dung toàn văn của giáo trình được cấu trúc thành 6 chương học thuật hoàn chỉnh:

• 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

  • Nội dung cốt lõi: Thiết lập bài toán tối ưu tổng quát dạng $f(x) \to \min (\max)$ với điều kiện $g_i(x) \le 0$ ($i = 1, \dots, m$) và $x \in D$. Khảo sát tối ưu tổ hợp khi tập ràng buộc $D$ là tập hữu hạn.
  • Hệ thống phân loại: Phân loại thành Quy hoạch tuyến tính (QHTT), Quy hoạch phi tuyến (QHPT), Quy hoạch rời rạc (QHRR), Quy hoạch động (QHD), Quy hoạch tham số (QHTS), và Quy hoạch đa mục tiêu (QHĐMT).
  • Quy trình mô hình hóa 4 bước: Xây dựng mô hình định tính $\to$ Thiết lập mô hình toán học (xác định biến, hàm mục tiêu, ràng buộc) $\to$ Sử dụng công cụ toán học và lập trình trên máy tính $\to$ Phân tích, kiểm định kết quả (xác định 4 nguyên nhân sai lệch nếu mô hình không phù hợp).
  • Các bài toán mẫu kinh điển: Bài toán lập kế hoạch sản xuất tối ưu; Bài toán vận tải cân bằng thu phát ($\sum a_i = \sum b_j$); Bài toán người du lịch ($n!$ phương án hoán vị chu trình); Bài toán cái túi với biến nhị phân $x_i \in {0, 1}$.
  • Cơ sở Đại số tuyến tính: Không gian Euclide $n$ chiều $\mathbb{R}^n$, các phép toán vector, ma trận tổng quát $m \times n$, ma trận vuông, ma trận đơn vị, ma trận chuyển vị $A^T$, ma trận đường chéo và các phép toán ma trận.

• Chương 2: Quy hoạch tuyến tính

  • Nội dung cốt lõi: Khảo sát bài toán QHTT tổng quát dạng cực đại và cực tiểu, chứng minh mối liên hệ $f_{\min} = -f_{\max}$. Định nghĩa điểm cực biên (đỉnh của miền đa diện lồi $D$).
  • Dạng chuẩn tắc và chính tắc: Kỹ thuật biến đổi đưa bài toán về dạng chuẩn ($\sum a_{ij} x_j \le b_i, x_j \ge 0$) hoặc chính tắc ($\sum a_{ij} x_j = b_i, x_j \ge 0$) thông qua nhân hệ số âm, tách biến tự do $x_j = x_j' - x_j''$, đưa vào biến bù hoặc biến phụ.
  • Phương pháp hình học: Áp dụng cho bài toán 2 biến số ($x_1, x_2$), xác định miền chấp nhận $D$ từ giao của các nửa mặt phẳng và tịnh tiến đường mức $c_1 x_1 + c_2 x_2 = \alpha$ theo vector pháp tuyến $n = (c_1, c_2)$.
  • Hệ thống định lý: Định lý 2.1 (tập phương án là tập lồi); Định lý 2.2 (hàm mục tiêu đạt tối ưu tại điểm cực biên); Định lý 2.3 và 2.4 (quan hệ giữa điểm cực biên và tính độc lập tuyến tính của hệ vector cột $A_j$, số thành phần dương không vượt quá $m$); Định lý 2.5 (tiêu chuẩn nhận biết phương án cực biên không thoái hóa $|J|=m$ và thoái hóa $|J|<m$).
  • Thuật toán đơn hình và bảng đơn hình: Tính toán các ước lượng kiểm tra $\Delta_k = z_k - c_k = \sum_{j \in J} z_{jk} c_j - c_k$. Tiêu chuẩn tối ưu $\Delta_k \ge 0, \forall k \notin J$. Quy tắc chọn cột xoay $s$ ($\Delta_s = \min {\Delta_k < 0}$) và dòng xoay $r$ theo tỷ số $\theta_r = \min {x_i / z_{is} \mid z_{is} > 0}$. Biến đổi bảng qua trục xoay $z_{rs}$.
  • Kỹ thuật biến giả tạo $M$ lớn: Giải bài toán mở rộng bằng cách thêm biến giả tạo với trọng số $-M$ vào hàm mục tiêu; Định lý 2.8 chứng minh điều kiện tương đương nghiệm giữa bài toán gốc và bài toán $(M)$.

• Chương 3: Bài toán vận tải

  • Nội dung cốt lõi: Khảo sát cấu trúc bảng vận tải với $m$ điểm phát và $n$ điểm thu; phân tích điều kiện cân bằng cung cầu $\sum a_i = \sum b_j$; các phương pháp lập phương án xuất phát và thuật toán thế vị (hoặc phương pháp cước phí bé nhất) để tìm phương án phân phối tối ưu với tổng chi phí $\sum \sum c_{ij} x_{ij} \to \min$.

• Chương 4: Quy hoạch động

  • Nội dung cốt lõi: Tiếp cận các bài toán tối ưu hóa đa giai đoạn theo thời gian; nguyên lý tối ưu Bellman; phương trình hàm quy hoạch động; ứng dụng giải bài toán phân bổ nguồn lực và bài toán quản lý dự trữ.

• Chương 5: Sơ đồ mạng

  • Nội dung cốt lõi: Lý thuyết đồ thị ứng dụng trong tối ưu hóa; bài toán tìm đường đi ngắn nhất trên mạng lưới; bài toán luồng cực đại trong mạng; phân tích sơ đồ mạng tiến độ dự án (phương pháp CPM và kỹ thuật PERT).

• Chương 6: Quy hoạch phi tuyến

  • Nội dung cốt lõi: Bài toán tối ưu hóa hàm mục tiêu hoặc hệ ràng buộc phi tuyến; bài toán quy hoạch lồi; điều kiện tối ưu Karush-Kuhn-Tucker (KKT); giới thiệu các thuật toán gradient và phương pháp số giải bài toán phi tuyến.

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

Giáo trình hình thành nền tảng giải tích lồi và đại số tuyến tính ứng dụng:

1. Không gian vector $\mathbb{R}^n$ và cấu trúc tập lồi: Định nghĩa tập lồi, tổ hợp lồi, đa diện lồi và điểm cực biên. Chứng minh tập phương án chấp nhận được của bài toán quy hoạch tuyến tính luôn là một tập lồi.
2. Cơ sở đại số ma trận: Phân tích ma trận ràng buộc $A$, tách hệ biến thành biến cơ sở ($x_B$) và biến phi cơ sở ($x_N$), biểu diễn vector phi cơ sở duy nhất qua tổ hợp tuyến tính của hệ vector cột cơ sở độc lập tuyến tính.
3. Cơ sở lý thuyết tối ưu hóa: Chứng minh giá trị tối ưu của bài toán quy hoạch tuyến tính luôn đạt tại ít nhất một đỉnh (điểm cực biên) của miền ràng buộc lồi.
4. Lý thuyết bài toán mở rộng ($M$ lớn): Chứng minh tính tương đương giữa bài toán gốc có ràng buộc đẳng thức và bài toán mở rộng chứa biến giả tạo khi cho tham số phạt $M \to +\infty$.

Kỹ năng phát triển

Thông qua hệ thống bài học và ví dụ tính toán, giáo trình phát triển các kỹ năng chuyên môn:

• Kỹ năng mô hình hóa toán học: Chuyển đổi yêu cầu bài toán thực tế thành ngôn ngữ toán học hình thức (xác định hệ biến $x_j$, xây dựng hàm mục tiêu dạng $\max/\min$ và hệ phương trình/bất phương trình ràng buộc).
• Kỹ năng biến đổi đại số: Chuyển hóa linh hoạt giữa các dạng bài toán (tổng quát $\leftrightarrow$ chuẩn tắc $\leftrightarrow$ chính tắc), xử lý biến không âm, biến tự do và đưa biến bù/biến giả tạo.
• Kỹ năng thuật toán hóa: Thực hiện thành thạo thuật toán đơn hình lặp từng bước trên bảng số liệu, nhận diện trạng thái không giới hạn của hàm mục tiêu hoặc trạng thái không có nghiệm chấp nhận được.
• Kỹ năng phân tích và kiểm định: Đánh giá độ phù hợp của mô hình sau khi giải, phân tích 4 nhóm nguyên nhân gây sai lệch (thuật toán chưa đủ độ chính xác, số liệu thị trường/định mức sai, mô hình định tính thiếu quy luật, thiết lập mô hình toán học sai).

---

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

Giáo trình sử dụng phương pháp sư phạm quy nạp kết hợp diễn dịch: từ bài toán thực tế dẫn dắt vào mô hình toán học hình thức, chứng minh các định lý làm cơ sở lý thuyết, sau đó quy chuẩn hóa thành thuật toán cụ thể có sơ đồ khối minh họa và bảng tính chi tiết.

Bảng tóm tắt các bài toán mẫu và ứng dụng trong giáo trình

Tên bài toán thực tế	Cấu trúc mô hình toán học	Dữ liệu đầu vào điển hình trong giáo trình	Phương pháp giải quyết
Kế hoạch sản xuất tối ưu (2 biến)	$f(x) = 4x_1 + 5x_2 \to \max$ $2x_1 + x_2 \le 8$ $x_1 + 2x_2 \le 7$ $x_2 \le 3;\ x_1, x_2 \ge 0$	2 sản phẩm A, B; 3 loại nguyên liệu I, II, III với lượng dự trữ 8, 7, 3; lãi suất 4 và 5 đơn vị.	Phương pháp hình học (đường mức $4x_1+5x_2=\alpha$) hoặc Bảng đơn hình. Nghiệm: $x^*=(3,2), f_{\max}=22$.
Phân bổ thiết bị cơ bản (4 biến)	$f(x) = 0,4x_1 + 0,2x_2 + 0,5x_3 + 0,8x_4 \to \max$ $x_1 + 2x_2 + 4x_3 + 8x_4 \le 24.500$ $x_j \ge 0$	4 sản phẩm A, B, C, D gia công trên 3 nhóm máy; giới hạn 24.500 giờ làm việc; tiền lãi $0,4; 0,2; 0,5; 0,8$.	Bảng đơn hình 3 lần lặp với biến bù $x_5, x_6, x_7$. Xác định cột xoay $s=4$, dòng xoay $r=5$, trục xoay $z_{54}=8$.
Sản xuất đồng bộ theo tỷ lệ (Bài toán M)	$x_0 \to \max$ $x_1 - 0,1x_2 - 0,75x_0 = 0$ $x_2 - 0,25x_0 = 0$ $0,2x_1 + 0,4x_2 \le 100;\ x_j \ge 0$	2 sản phẩm A, B sản xuất đồng bộ tỷ lệ $3:1$; định mức lao động $0,2$ và $0,4$; quỹ lao động 100 đơn vị.	Biến đổi bài toán $(M)$ với biến bù $x_3$ và biến giả tạo $x_4, x_5$ mang hệ số $-M$ trong hàm mục tiêu.
Bài toán vận tải	$\sum_{i=1}^m \sum_{j=1}^n c_{ij} x_{ij} \to \min$ Ràng buộc phát hết hàng và thu đủ nhu cầu	$m$ trạm phát sản lượng $a_i$, $n$ trạm thu nhu cầu $b_j$, cước phí đơn vị $c_{ij}$. Điều kiện $\sum a_i = \sum b_j$.	Lập bảng vận tải, phân phối phương án cơ sở, kiểm tra tối ưu bằng phương pháp thế vị.
Bài toán cái túi (Knapsack)	$f(x) = \sum c_i x_i \to \max$ $\sum m_i x_i \le b;\ x_i \in {0, 1}$	$n$ đồ vật với trọng lượng $m_i$, giá trị sử dụng $c_i$, khả năng chứa tối đa $b$.	Thuật toán nhánh cận, quy hoạch động hoặc tối ưu tổ hợp.
Bài toán người du lịch (TSP)	$\sum c_{i_k, i_{k+1}} \to \min$ Hoán vị qua $n$ thành phố	$n$ thành phố $P_1, \dots, P_n$, ma trận chi phí di chuyển $c_{ij}$. Có tổng cộng $n!$ phương án hoán vị.	Sơ đồ mạng, nhánh cận hoặc duyệt tổ hợp.

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

1. Thực hành tính toán bảng đơn hình bằng tay: Người học cần tự thực hiện từng bước lặp: tính ước lượng $\Delta_k$, xác định phần tử trục xoay $z_{rs}$, áp dụng công thức biến đổi cơ sở $x_j' = x_j - \frac{x_r}{z_{rs}} z_{js}$ để hiểu rõ bản chất đại số của thuật toán lặp.
2. Cài đặt chương trình máy tính: Sau khi làm chủ các bước giải thủ công trên ma trận nhỏ, sinh viên thực hiện lập trình hóa thuật toán (trên C/C++, Python hoặc các ngôn ngữ lập trình khác) cho bài toán tổng quát dạng ma trận cỡ $m \times n$ nhằm giải quyết các bài toán thực tế có quy mô lớn.
3. Đánh giá kết quả: Đánh giá thông qua năng lực xây dựng đúng mô hình toán học từ đề bài thực tế, tính toán chính xác bảng đơn hình, và khả năng giải trình các trường hợp suy biến của bài toán.

---

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

• Hệ thống hóa quy trình mô hình hóa toán học: Giáo trình không chỉ cung cấp thuật toán đơn thuần mà chuẩn hóa 4 bước mô hình hóa từ thực nghiệm, gắn liền với việc phân tích 4 nguyên nhân lỗi sai khi kết quả tính toán không tương thích với thực tế sản xuất.
• Xử lý trọn vẹn kỹ thuật biến đổi đại số: Trình bày chi tiết các kỹ thuật chuẩn hóa bài toán quy hoạch tuyến tính: từ việc chuyển đổi hàm mục tiêu $\min \leftrightarrow \max$, kỹ thuật bù biến, kỹ thuật khử biến tự do, đến việc sử dụng biến giả tạo trong bài toán $M$ lớn.
• Cơ sở toán học chặt chẽ: Các định lý về tập lồi, đỉnh cực biên, tính độc lập tuyến tính của hệ vector cột $A_j$, và điều kiện dừng của thuật toán đơn hình đều có phần chứng minh giải tích toán học rõ ràng.
• Định hướng ứng dụng công nghệ thông tin và logistics: Các ví dụ và bài toán được thiết kế bám sát các bài toán quản lý sản xuất, vận tải hàng hóa, điều độ mạng lưới và đóng gói, phù hợp với định hướng đào tạo công nghệ thông tin ứng dụng trong ngành giao thông vận tải.

---

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

• Sinh viên đại học:
  • Sinh viên năm thứ hai hoặc năm thứ ba ngành Công nghệ thông tin, Khoa học máy tính, Hệ thống thông tin quản lý.
  • Sinh viên khối ngành Kinh tế vận tải, Quản trị logistics, Kỹ thuật điều khiển và Tự động hóa.
• Kiến thức tiên quyết: Người học cần có kiến thức nền tảng về Đại số tuyến tính (không gian vector, ma trận, định thức, hệ phương trình tuyến tính), Giải tích toán học (đạo hàm, cực trị hàm nhiều biến) và Kỹ thuật lập trình cơ bản.
• Giảng viên: Sử dụng làm giáo trình giảng dạy chính khóa, tài liệu tham khảo để biên soạn đề cương môn học, thiết kế bài tập lớn và đề thi học phần Toán tối ưu / Nghiên cứu vận hành.
• Cán bộ kỹ thuật và nghiên cứu: Kỹ sư phần mềm, chuyên viên phân tích dữ liệu, chuyên viên kế hoạch sản xuất cần tài liệu chuẩn để tham khảo mô hình thuật toán tối ưu hóa.

---

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

1. Giáo trình này phù hợp với ai?

Giáo trình được biên soạn chuyên biệt cho sinh viên đại học ngành Công nghệ thông tin, Kinh tế vận tải, Logistics và các ngành kỹ thuật có học phần Toán tối ưu hoặc Quy hoạch toán học.

2. Cần kiến thức nền nào để học giáo trình này?

Người học cần nắm vững kiến thức Đại số tuyến tính (phép toán ma trận, vector, hệ phương trình đại số tuyến tính) và Giải tích cơ bản. Giáo trình cũng dành một phần trong Chương 1 để nhắc lại các khái niệm không gian $\mathbb{R}^n$ và đại số ma trận.

3. Điểm khác biệt của giáo trình so với các tài liệu khác?

Giáo trình kết hợp đồng thời giữa tính chứng minh toán học giải tích chặt chẽ (định lý tập lồi, vector cực biên, bài toán $M$ lớn) với quy trình 4 bước mô hình hóa thực tế và định hướng chuyển giao thuật toán lên máy tính.

4. Làm sao để tự học giáo trình hiệu quả?

Người học nên học tuần tự từ Chương 1 đến Chương 6. Với mỗi chương, cần đọc kỹ định nghĩa và định lý, tự giải lại các ví dụ mẫu (bài toán sản xuất, bài toán phân bổ thiết bị, bài toán vận tải) trên bảng đơn hình, sau đó viết code triển khai thuật toán trên máy tính.

5. Có tài liệu bổ trợ nào kèm theo trong chương trình?

Giáo trình tham khảo và kết nối với các tài liệu chuyên khảo về Quy hoạch tuyến tính, Quy hoạch phi tuyến, Lý thuyết đồ thị và tài liệu hướng dẫn lập trình giải thuật tối ưu trên máy tính.

---

Kết luận

Giáo trình "Toán Tối Ưu" của tác giả Nguyễn Văn Long (Chủ biên) và ThS. Đỗ Quang Thơ là tài liệu học thuật có tính hệ thống cao, kết hợp toàn diện giữa lý thuyết giải tích lồi, đại số ma trận và các giải thuật tối ưu hóa kinh điển.

Lộ trình học tập được thiết kế khoa học: xây dựng tư duy mô hình hóa ở Chương 1, làm chủ quy hoạch tuyến tính và thuật toán đơn hình ở Chương 2, mở rộng sang các lớp bài toán chuyên biệt (vận tải, quy hoạch động, sơ đồ mạng) ở Chương 3, 4, 5 và nâng cao với quy hoạch phi tuyến ở Chương 6. Đây là tài liệu chuẩn mực phục vụ đào tạo cử nhân và kỹ sư công nghệ thông tin, kinh tế kỹ thuật trong việc giải quyết các bài toán tối ưu hóa thực tiễn.

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.