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

Tài liệu "Tối ưu hóa" do tác giả Nguyễn Thị Vinh biên soạn năm 2010 là giáo trình giảng dạy chính thức ở bậc đại học tại Trường Đại học Thủy Lợi. Trong chương trình đào tạo kỹ sư và cử nhân thuộc các khối ngành Kỹ thuật, Công nghệ thông tin, Quản trị hệ thống và Kinh tế kỹ thuật, môn học Tối ưu hóa đóng vai trò cầu nối giữa cơ sở toán học thuần túy (Đại số tuyến tính, Giải tích hàm nhiều biến) với các bài toán vận trù, điều độ tài nguyên và thiết kế kỹ thuật thực tế.

Mục tiêu học tập của giáo trình nhằm trang bị cho sinh viên hệ thống lý thuyết chuẩn tắc về mô hình hóa toán học các bài toán ra quyết định; nắm vững bản chất toán học của các lớp bài toán tối ưu (tuyến tính, nguyên, tham số, quy hoạch động, phi tuyến); thành thạo các giải thuật giải tích và số trị; đồng thời hình thành năng lực cài đặt thuật toán trên máy tính cũng như khai thác các công cụ tính toán chuyên dụng.

Cấu trúc giáo trình được thiết kế theo tiến trình logic từ tổng quát đến chuyên sâu: mở đầu bằng các khái niệm cơ sở của bài toán tối ưu và giải tích lồi; tiếp nối bởi lớp bài toán Quy hoạch tuyến tính (QHTT) cùng thuật toán đơn hình; mở rộng sang các dạng bài toán mở rộng (đối ngẫu, vận tải, quy hoạch tham số, quy hoạch nguyên); giới thiệu quy hoạch động và quy hoạch phi tuyến; cuối cùng là hướng dẫn thực hành trên phần mềm máy tính.

Điểm đặc thù của giáo trình là sự kết hợp chặt chẽ giữa việc chứng minh điều kiện tối ưu về mặt giải tích với việc xây dựng sơ đồ khối thuật toán, cung cấp mã nguồn lập trình C++ cụ thể và quy trình thao tác mô hình hóa trên công cụ Solver của MS-Excel.

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

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

Nội dung giáo trình gồm 6 chương với cấu trúc kiến thức liên kết chặt chẽ:

TỐI ƯU HÓA (ĐẠI HỌC THỦY LỢI, 2010)
  • Chương 1: Bài toán tối ưu và các khái niệm: Trình bày mô hình tối ưu tổng quát tìm $\max/\min f(x)$ trên miền ràng buộc $D = {x \in X \mid g_i(x) \ge (\le, =) b_i, i=1,\dots,m}$. Giới thiệu hệ thống thuật ngữ: điểm dừng ($\nabla f(x) = 0$), ma trận Hessian $H(x)$, điểm yên ngựa (saddle points), điều kiện cực trị địa phương và toàn cục. Phân loại thuật toán theo bậc đạo hàm: bậc không (chỉ dùng giá trị hàm), bậc nhất (dùng Gradient), bậc hai (dùng ma trận Hessian). Thiết lập cơ sở giải tích lồi: tổ hợp lồi, tập lồi, siêu phẳng, nửa không gian, đỉnh cực biên, đa diện lồi, hàm lồi/lõm và các định lý nền tảng về cực trị trên tập lồi.
  • Chương 2: Qui hoạch tuyến tính (QHTT): Phân tích các mô hình điển hình: bài toán khẩu phần dinh dưỡng/ăn kiêng, bài toán sử dụng nguyên vật liệu sản xuất, bài toán vận tải tĩnh, bài toán cơ cấu cây trồng. Trình bày phương pháp hình học giải bài toán 2 biến thông qua đường thẳng tựa và véctơ pháp tuyến. Định nghĩa bài toán QHTT dạng chuẩn $\max L = C^T X$ với $AX = b, X \ge 0, b \ge 0, \text{rank}(A) = m$, phương pháp đưa bài toán tổng quát về dạng chuẩn bằng biến chênh lệch (BCL). Trình bày thuật toán đơn hình của George Dantzig (1947), tiêu chuẩn tối ưu $\Delta_k \le 0$, kỹ thuật giải bài toán suy biến, bài toán không bị chặn ($L_{\max} = +\infty$) và phương pháp biến nhân tạo (BNT) thông qua giải thuật hai pha hoặc phương pháp hệ số phạt $M$.
  • Chương 3: Các bài toán khác của QHTT: Trình bày lý thuyết đối ngẫu (cặp bài toán đối ngẫu đối xứng và không đối xứng, mối quan hệ giữa nghiệm tối ưu và véctơ chi phí, điều kiện cân bằng $\max L = \min T$). Phân tích chuyên sâu bài toán vận tải cân bằng và không cân bằng; phương pháp tìm nghiệm xuất phát theo giá cước nhỏ nhất; phương pháp thế vị ($u_i + v_j = c_{ij}$), lượng gia giảm cước phí $\Delta_{ij} = u_i + v_j - c_{ij}$ và kỹ thuật điều chỉnh theo chu trình kín $K$. Trình bày bài toán quy hoạch tham số tuyến tính khi hệ số phụ thuộc tham số $\lambda$, và bài toán quy hoạch nguyên tuyến tính (QHNTT) giải bằng phương pháp Nhánh và Cận (Branch and Bound).
  • Chương 4: Giới thiệu bài toán qui hoạch động (QHĐ): Phân tích các quá trình ra quyết định nhiều giai đoạn thông qua bài toán tìm đường đi ngắn nhất/dài nhất trên đồ thị. Trình bày nguyên lý tối ưu Bellman, thiết lập phương trình hàm truy hồi và phương pháp giải ngược từ giai đoạn cuối về giai đoạn đầu.
  • Chương 5: Quy hoạch phi tuyến (QHPT): Cung cấp các phương pháp dò tìm cực trị địa phương: đối với hàm một biến sử dụng phương pháp lát cắt vàng (phương pháp bậc không với tỷ lệ vàng để thu hẹp khoảng bất định); đối với bài toán không ràng buộc nhiều chiều sử dụng phương pháp tụt dốc/đường dốc nhất (Steepest Descent) và phương pháp Newton; đối với bài toán có ràng buộc sử dụng phương pháp Gradient.
  • Chương 6: Hướng dẫn sử dụng công cụ Solver trong MS-Excel giải các bài toán tối ưu: Trình bày cách thiết lập bảng tính, khai báo ô biến số (Changing Variable Cells), ô hàm mục tiêu (Objective Cell), thiết lập hệ ràng buộc đẳng thức/bất đẳng thức trong Solver và phân tích kết quả đầu ra.

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

Giáo trình củng cố và hệ thống hóa các nguyên lý toán học nền tảng:

  1. Cơ sở giải tích lồi: Tính chất đóng của tập lồi qua phép giao và tổ hợp tuyến tính; định lý khẳng định miền nghiệm của hệ phương trình/bất phương trình tuyến tính là một đa diện lồi; định lý cực tiểu địa phương của hàm lồi trên tập lồi chính là cực tiểu tuyệt đối; cực trị của hàm tuyến tính trên đa diện lồi luôn đạt tại ít nhất một đỉnh cực biên.
  2. Xấp xỉ bậc hai và Khai triển Taylor: Sử dụng khai triển Taylor bậc hai của hàm nhiều biến: $$f(x_0 + \Delta x) \approx f(x_0) + \nabla f(x_0)^T \Delta x + \frac{1}{2} \Delta x^T H(x_0) \Delta x$$ Lý giải vì sao các thuật toán tối ưu phi tuyến bậc cao hội tụ tốt khi tiệm cận dạng mặt bậc hai lồi hoặc lõm.
  3. Lý thuyết đối ngẫu và Thế vị: Nguyên lý đối ngẫu trong đại số ma trận, giải bài toán đối ngẫu để suy ra nghiệm bài toán gốc; phương pháp thế vị trong bài toán vận tải như một trường hợp riêng của bài toán đối ngẫu tuyến tính.
  4. Nguyên lý tối ưu hóa đa giai đoạn của R. Bellman: Bản chất của phương pháp chia nhỏ bài toán lớn thành chuỗi bài toán con theo thời gian hoặc theo không gian trạng thái.

Kỹ năng phát triển

Tài liệu rèn luyện cho người học ba nhóm năng lực chính:

  • Năng lực mô hình hóa toán học: Chuyển đổi các phát biểu bài toán thực tế dạng ngôn ngữ tự nhiên (bài toán ăn kiêng, kế hoạch sản xuất 2 phân xưởng, phân phối hàng hóa giữa các kho $A_i$ và cửa hàng $B_j$, bố trí cây trồng trên diện tích đất) thành mô hình toán học chuẩn xác với biến quyết định, hàm mục tiêu và hệ ràng buộc kỹ thuật.
  • Năng lực tính toán giải thuật: Thực hiện thành thạo các bước biến đổi trên bảng đơn hình, lập tỷ số chọn hàng trục, xoay trục Gauss-Jordan, xác định biến vào/biến ra, thiết lập chu trình vận tải $K$, giải hệ phương trình thế vị tìm $\Delta_{ij}$, tính toán lát cắt vàng trên từng bước lặp định vị điểm cực tiểu với sai số $\varepsilon$.
  • Năng lực ứng dụng công nghệ và lập trình: Đọc hiểu và triển khai sơ đồ khối thuật toán thành chương trình máy tính; hiểu rõ cấu trúc dữ liệu mảng 2 chiều và con trỏ qua mã nguồn mẫu C++ (qhtt.cpp và bài toán vận tải); vận hành thành thạo công cụ Solver trong MS-Excel để giải tự động các mô hình tối ưu quy mô lớn.

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

Phương pháp sư phạm

Giáo trình áp dụng phương pháp tiếp cận quy nạp kết hợp diễn dịch:

  • Mỗi khái niệm trừu tượng đều được xuất phát từ bài toán thực tế trực quan (ví dụ: giải thích bài toán QHTT từ bài toán phân xưởng cắt - trộn - đóng gói sản phẩm I và II; giải thích thuật toán đơn hình qua hình học trực quan chuyển dịch từ đỉnh này sang đỉnh khác của đa diện lồi).
  • Lý thuyết toán học được phát biểu chính xác dưới dạng Định nghĩa - Định lý - Hệ quả kèm chứng minh hoặc diễn giải bản chất hình học.
  • Trình bày chi tiết từng bước tính toán (step-by-step) của các thuật toán phức tạp (như quy trình biến đổi bảng đơn hình qua từng bảng lặp, bảng thế vị bài toán vận tải qua các bước lặp).

Hệ thống bài tập và thực hành

Mỗi chương đều kết thúc bằng mục bài tập chọn lọc, bao quát các mức độ từ cơ bản đến nâng cao:

  • Bài tập Chương 1: Xác định khoảng lồi/lõm của các hàm số ($y = x^2, y = e^x, y = \sin x$); vẽ và kiểm tra tính lồi của các miền ràng buộc phi tuyến ($x_2^2 - x_1 + 3 < 0, x_1^2 + x_2^2 - 16 < 0$).
  • Bài tập Chương 2: Giải bài toán 2 biến bằng phương pháp hình học; giải bài toán nhiều biến bằng phương pháp đơn hình; thực hành kỹ thuật thêm biến chênh lệch (BCL) và biến nhân tạo (BNT) giải bài toán QHTT với 3-5 ẩn số.
  • Bài tập Chương 3 & 4: Thiết lập bài toán đối ngẫu từ dữ liệu sản xuất thực tế; giải bài toán vận tải cân bằng và không cân bằng; giải bài toán phân phối vốn hoặc tìm đường đi tối ưu bằng quy hoạch động.
  • Bài tập Chương 5: Định vị điểm cực tiểu của hàm $f(x) = x^2 - x$ với độ chính xác $\varepsilon = 0.15$ bằng phương pháp lát cắt vàng; giải bài toán không ràng buộc bằng phương pháp tụt dốc.

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

Giáo trình cung cấp đầy đủ đáp số, bảng lặp mẫu và hướng dẫn giải cho các bài toán phức tạp (như hướng dẫn chọn 3 biến nhân tạo $x_6, x_7, x_8$ để tìm phương án cực biên xuất phát). Người học có thể tự kiểm tra tiến trình giải thủ công bằng cách đối chiếu với kết quả chạy từ mã nguồn C++ hoặc kết quả tính toán tự động từ MS-Excel Solver được hướng dẫn ở Chương 6.

Điểm nổi bật và tính ứng dụng thực tế

  • Tính đầy đủ về mặt cấu trúc giải thuật: Giáo trình bao hàm trọn vẹn từ các giải thuật cổ điển của quy hoạch tuyến tính (Đơn hình của Dantzig) đến các thuật toán quy hoạch động (Bellman) và quy hoạch phi tuyến (Lát cắt vàng, Gradient, Steepest Descent, Newton).
  • Phân loại phương pháp luận theo bậc đạo hàm: Việc phân chia các phương pháp giải tối ưu theo cấp độ thông tin đạo hàm (bậc không, bậc nhất, bậc hai) giúp người học nắm vững chi phí tính toán và điều kiện áp dụng của từng phương pháp đối với các hàm mục tiêu khả vi hoặc không khả vi.
  • Gắn kết thuật toán với mã nguồn thực thi: Khác với các tài liệu toán học thuần túy, giáo trình cung cấp cấu trúc chương trình tính toán hoàn chỉnh bằng ngôn ngữ C/C++ (định nghĩa kiểu dữ liệu matran, mang, các hàm Doc_DL, In_BDH, Tim_cot_chon, Tim_hang_chon, Bien_doi_BDH). Điều này giúp sinh viên ngành kỹ thuật và tin học hiểu rõ cơ chế chuyển dịch từ mô hình toán sang cấu trúc dữ liệu và giải thuật máy tính.
  • Giải quyết các tình huống biên trong thực tế: Hướng dẫn chi tiết cách xử lý khi bài toán tối ưu rơi vào các trường hợp đặc biệt: hàm mục tiêu không bị chặn ($L_{\max} = +\infty$), bài toán suy biến có vô số nghiệm tối ưu, bài toán vận tải không cân bằng cung - cầu bằng cách bổ sung kho phát giả tạo hoặc điểm thu giả tạo với cước phí bằng 0.

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

  • Sinh viên đại học: Giáo trình được biên soạn phục vụ trực tiếp cho sinh viên năm thứ hai, năm thứ ba các ngành Kỹ thuật Công trình, Thủy văn, Tài nguyên nước, Công nghệ thông tin, Quản lý xây dựng, Kinh tế và Quản trị kinh doanh tại Trường Đại học Thủy Lợi và các trường đại học khối kỹ thuật.
  • Yêu cầu kiến thức tiên quyết (Prerequisites): Người học cần hoàn thành các học phần:
    • Đại số tuyến tính: Khái niệm ma trận, định thức, hạng ma trận, hệ phương trình đại số tuyến tính, phép khử Gauss-Jordan, không gian véctơ $\mathbb{R}^n$.
    • Giải tích toán học: Đạo hàm, vi phân, khai triển chuỗi Taylor, đạo hàm riêng, véctơ Gradient, ma trận Hessian và khảo sát hàm nhiều biến.
    • Tin học đại cương / Ngôn ngữ lập trình: Cú pháp cơ bản của ngôn ngữ C/C++ (mảng, con trỏ, hàm, cấu trúc tệp) và kỹ năng sử dụng bảng tính Microsoft Excel.
  • Giảng viên và cán bộ nghiên cứu: Tài liệu đóng vai trò là đề cương bài giảng chuẩn, cung cấp hệ thống ví dụ, sơ đồ khối giải thuật và ngân hàng bài tập phục vụ công tác giảng dạy học phần Tối ưu hóa, Vận trù học (Operations Research) và Toán ứng dụng trong kỹ thuật.

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

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

Giáo trình được thiết kế làm tài liệu học tập chính thức cho sinh viên bậc đại học khối ngành kỹ thuật, công nghệ và kinh tế; đồng thời là tài liệu tham khảo cho học viên cao học và kỹ sư cần ứng dụng toán tối ưu vào tính toán điều độ, thiết kế công trình và quản lý nguồn lực.

2. Cần trang bị những kiến thức toán học nào trước khi học?

Người học cần nắm chắc kiến thức Đại số tuyến tính (ma trận, hệ phương trình tuyến tính, định thức, không gian $\mathbb{R}^n$) và Giải tích hàm nhiều biến (đạo hàm riêng, gradient, ma trận Hessian, khai triển Taylor).

3. Giáo trình có hướng dẫn sử dụng công cụ phần mềm nào không?

Giáo trình tích hợp hai công cụ bổ trợ tính toán: cung cấp mã nguồn chương trình C++ mẫu (qhtt.cpp và chương trình giải bài toán vận tải) và dành riêng Chương 6 hướng dẫn chi tiết cách sử dụng bộ công cụ Solver trong phần mềm MS-Excel để giải bài toán tối ưu.

4. Thuật toán đơn hình trong giáo trình xử lý bài toán chưa có cơ sở ban đầu như thế nào?

Giáo trình hướng dẫn áp dụng phương pháp biến nhân tạo (BNT). Quá trình giải được chia thành hai giai đoạn (phương pháp 2 pha) hoặc sử dụng phương pháp hệ số phạt $M$ để tìm phương án cực biên xuất phát, sau đó tự động loại bỏ các biến nhân tạo để chuyển sang giải bài toán gốc.

5. Sự khác biệt giữa phương pháp giải bài toán vận tải và thuật toán đơn hình tổng quát là gì?

Mặc dù bài toán vận tải là một dạng đặc biệt của bài toán quy hoạch tuyến tính, giáo trình trình bày phương pháp thế vị ($u_i, v_j$) kết hợp điều chỉnh lượng hàng theo chu trình kín $K$. Phương pháp chuyên biệt này giúp tìm nghiệm tối ưu trực tiếp trên bảng cước phí mà không cần lập bảng đơn hình kích thước lớn, giảm thiểu đáng kể khối lượng tính toán.

Kết luận

Tài liệu giảng dạy "Tối ưu hóa" của tác giả Nguyễn Thị Vinh (Trường Đại học Thủy Lợi, 2010) là công trình học thuật mang tính sư phạm chuẩn mực, bao quát toàn diện các phân ngành trọng yếu của lý thuyết quy hoạch toán học. Từ nền tảng giải tích lồi, quy hoạch tuyến tính, bài toán đối ngẫu, bài toán vận tải cho đến quy hoạch động và quy hoạch phi tuyến, tài liệu cung cấp phương pháp tiếp cận cân bằng giữa tính nghiêm ngặt của toán học lý thuyết và khả năng ứng dụng thực hành thông qua sơ đồ thuật toán, mã nguồn C++ và công cụ bảng tính MS-Excel.

Lộ trình học tập khuyến nghị bắt đầu từ việc nắm vững cấu trúc không gian lồi ở Chương 1, thực hành thành thạo thuật toán đơn hình ở Chương 2 và 3, mở rộng sang quy hoạch động/phi tuyến ở Chương 4 và 5, sau đó hoàn thiện kỹ năng giải quyết bài toán quy mô lớn thông qua công cụ Solver tại Chương 6.