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

Giáo trình Tối ưu hóa: Giáo trình cho ngành Tin học và Công nghệ thông tin do PGS. Nguyễn Hải Thanh biên soạn, được Nhà xuất bản Bách khoa – Hà Nội phát hành (Mã số xuất bản: 920 − 2006 / CBX / 01 − 130 / BKHN). Tài liệu được xây dựng phục vụ công tác giảng dạy và học tập tại Khoa Công nghệ thông tin, Trường Đại học Nông nghiệp I.

Trong khung chương trình đào tạo bậc đại học cho các ngành Tin học, Công nghệ thông tin và Toán – Tin ứng dụng, môn học Tối ưu hóa giữ vai trò là học phần kiến thức cơ sở ngành với thời lượng quy định từ 3 đến 6 học trình. Môn học liên kết trực tiếp với các lĩnh vực như Quy hoạch toán học, Vận trù học (Operations Research), Lý thuyết trò chơi, Điều khiển tối ưu và Khoa học quản lý (Management Science).

Mục tiêu học tập (Learning Outcomes) của giáo trình tập trung vào việc cung cấp cho người học hệ thống kiến thức nền tảng về lý thuyết tối ưu hóa toán học; giúp sinh viên nắm vững nguyên lý vận hành và quy trình tính toán của các thuật toán tối ưu kinh điển. Trên cơ sở đó, người học hình thành năng lực thiết lập mô hình toán học từ bài toán thực tế và kỹ năng lập trình cài đặt thuật toán để giải quyết các bài toán tính toán tối ưu trong kinh tế, kỹ thuật, công nghệ và quản lý.

Cấu trúc giáo trình gồm 6 chương, được phân chia mạch lạc: phần đầu (Chương I đến Chương IV) tập trung vào bài toán tối ưu tổng quát, quy hoạch tuyến tính và quy hoạch nguyên; phần sau (Chương V và Chương VI) mở rộng sang các phương pháp quy hoạch phi tuyến và cơ sở giải tích lồi. Cách tiếp cận của tài liệu chú trọng khía cạnh thủ tục tính toán thông qua các ví dụ mẫu cụ thể từ đơn giản đến phức tạp, được tái sử dụng xuyên suốt qua các phương pháp khác nhau nhằm tạo điều kiện cho sinh viên ngành Tin học tiếp cận thuận lợi với tư duy giải thuật.

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

                             BÀI TOÁN TỐI ƯU TỔNG QUÁT (Chương I)
         QUY HOẠCH TUYẾN TÍNH & NGUYÊN                         QUY HOẠCH PHI TUYẾN & LỒI

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

  • Chương I: Bài toán tối ưu tổng quát và ứng dụng
    Định nghĩa bài toán tối ưu tổng quát $\max (\min) f(x)$ với $x \in D \subset \mathbb{R}^n$; phân loại các bài toán tối ưu (quy hoạch tuyến tính, phi tuyến, lồi, toàn phương, rời rạc/nguyên, quy hoạch động, đa mục tiêu, ngẫu nhiên/mờ); quy trình 6 bước của phương pháp mô hình hóa toán học; giới thiệu các bài toán thực tế điển hình.
  • Chương II: Phương pháp đơn hình giải bài toán quy hoạch tuyến tính
    Mô hình quy hoạch tuyến tính (BTQHTT); phương pháp đồ thị và tính chất nghiệm tại điểm cực biên của tập lồi đa diện; thủ tục xoay bảng đơn hình; cơ sở toán học dạng chính tắc; công thức số gia hàm mục tiêu $\Delta_j = c_j - z_j$ và tiêu chuẩn tối ưu; phương pháp đơn hình mở rộng (phương pháp phạt $M$); phương pháp đơn hình 2 pha; phương pháp đơn hình cải biên (ma trận nghịch đảo $B^{-1}$); kỹ thuật xử lý hiện tượng xoay vòng.
  • Chương III: Bài toán đối ngẫu và một số ứng dụng
    Định nghĩa cặp bài toán gốc – đối ngẫu; quy tắc đối ngẫu hóa tổng quát; ý nghĩa kinh tế của biến đối ngẫu (giá ước định tài nguyên / shadow price); hệ định lý đối ngẫu (định lý đối ngẫu yếu, định lý đối ngẫu mạnh, định lý độ lệch bù); thuật toán đơn hình đối ngẫu; mô hình bài toán vận tải cùng phương pháp phân phối và phương pháp thế vị.
  • Chương IV: Quy hoạch nguyên
    Mô hình bài toán quy hoạch tuyến tính nguyên (BTQHTTN); phương pháp lát cắt Gomory; phương pháp nhánh cận Land – Doig; ứng dụng quy hoạch động giải bài toán tối ưu nguyên và bài toán người du lịch (TSP); kỹ thuật hợp nhất hóa các điều kiện ràng buộc.
  • Chương V: Một số phương pháp quy hoạch phi tuyến
    Khái niệm tối ưu phi tuyến và quy hoạch lồi; các phương pháp tối ưu không ràng buộc (phương pháp đường dốc nhất, phương pháp Newton, phương pháp hướng liên hợp); hệ điều kiện tối ưu Kuhn – Tucker cho bài toán có ràng buộc; các phương pháp giải quy hoạch toàn phương (phương pháp Wolfe, giải bằng bài toán bù); quy hoạch tách và quy hoạch hình học.
  • Chương VI: Một số vấn đề cơ sở của lý thuyết quy hoạch lồi và quy hoạch phi tuyến
    Giải tích lồi (bao đóng, miền trong, siêu phẳng tách, siêu phẳng tựa, nón lồi, nón đối cực); biểu diễn tập lồi đa diện qua điểm cực biên và hướng cực biên; tính chất hàm lồi và dưới vi phân; hệ điều kiện tối ưu Fritz – John và Kuhn – Tucker; các phương pháp hướng chấp nhận (thuật toán Frank – Wolfe, gradient rút gọn, đơn hình lồi Zangwill); giới thiệu phương pháp điểm trong (thuật toán Ellipsoid xấp xỉ).

Progression logic của giáo trình đi từ việc mô hình hóa hình học trực quan hai chiều, tiến tới công thức hóa đại số ma trận cho không gian nhiều chiều, mở rộng sang các cấu trúc rời rạc/nguyên, và kết thúc bằng nền tảng giải tích lồi trừu tượng kết hợp các thuật toán hiện đại.

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

  • Lý thuyết giải tích lồi và không gian vector: Khái niệm tập lồi, hàm lồi, siêu phẳng tách, nón đối cực, cùng định lý biểu diễn tập lồi đa diện thông qua các điểm cực biên và hướng cực biên.
  • Nguyên lý tối ưu hóa tuyến tính và đối ngẫu: Nguyên lý bù, công thức tính số gia hàm mục tiêu $\Delta_N = c_N^T - c_B^T B^{-1} N$, sự tương đương giữa bài toán gốc và bài toán đối ngẫu, cơ chế định giá biên của các nguồn lực.
  • Hệ điều kiện tối ưu vi phân: Hệ điều kiện đạo hàm bậc một, ma trận Hessian bậc hai, điều kiện dừng Karush – Kuhn – Tucker (KKT) và Fritz – John trong tối ưu phi tuyến có ràng buộc.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật (Technical skills): Thực hiện biến đổi bảng đơn hình, tính toán ma trận nghịch đảo $B^{-1}$ trong đơn hình cải biên, thiết lập phương trình mặt cắt Gomory, phân nhánh cây nhánh cận Land – Doig, tính đạo hàm riêng và vector gradient.
  • Kỹ năng phân tích (Analytical skills): Phân loại chính xác dạng bài toán tối ưu (tuyến tính, phi tuyến, nguyên, đa mục tiêu); phân tích điều kiện ràng buộc và tính khả thi của miền phương án; đánh giá hiện tượng suy biến hoặc hàm mục tiêu không bị chặn.
  • Kỹ năng thực hành tính toán (Practical competencies): Chuyển đổi mô hình toán học thành thuật toán có khả năng lập trình (trên các ngôn ngữ như C, Pascal); sử dụng các công cụ phần mềm chuyên dụng như Microsoft Excel (Solver) hoặc LINGO để giải quyết các bài toán tối ưu quy mô lớn.

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

Giáo trình áp dụng phương pháp sư phạm kết hợp chặt chẽ giữa minh họa trực quan hình học và hệ thống hóa thuật toán đại số. Các khái niệm phức tạp về tập lồi đa diện và điểm cực biên ban đầu được diễn giải trực quan trên không gian hai chiều bằng phương pháp đồ thị và đường đồng mức, sau đó mới khái quát hóa thành các công thức toán học và bảng tính đơn hình nhiều chiều.

Tài liệu cung cấp hệ thống nghiên cứu tình huống (case studies) và bài tập thực tế có số liệu thực nghiệm đầy đủ:

  1. Mô hình quy hoạch tuyến tính: Bài toán quy hoạch sử dụng đất tại xã Đông Dư, huyện Gia Lâm, Hà Nội gồm 25 biến quyết định ($x_1$ đến $x_{18}$ là diện tích các loại cây trồng, $x_{19}$ là diện tích mặt nước, $x_{20}$ đến $x_{23}$ là đầu vật nuôi, $x_{24}$ là lao động thuê, $x_{25}$ là vốn vay) cùng 33 điều kiện ràng buộc.
  2. Mô hình quy hoạch phi tuyến hỗn hợp nguyên: Bài toán cực đại hóa giá trị sản xuất nuôi cá tại huyện Văn Giang, tỉnh Hưng Yên dựa trên hàm sản xuất Cobb – Douglas và thuật toán tối ưu phi tuyến toàn cục RST2ANU.
  3. Mô hình tối ưu động học: Bài toán xác định thông số hình học và động học của cơ cấu sàng phân loại dao động thông qua giải hệ phương trình phi tuyến chuyển về dạng cực tiểu sai số bình phương.
  4. Mô hình quy hoạch phi tuyến đa mục tiêu: Bài toán thiết kế trục máy tối ưu đồng thời thể tích và độ nén tĩnh, sử dụng hàm thuộc mờ ($\mu_1, \mu_2$) và phép quy đổi bài toán Max-Min.

Hệ thống đánh giá và hướng dẫn tự học được bố trí cuối các Chương II, III, IV, V và VI. Các bài tập được phân tầng rõ ràng:

  • Bài tập giải toán bằng tay: Vẽ đồ thị, lập bảng đơn hình, lập bảng đơn hình cải biên, viết bài toán đối ngẫu.
  • Bài tập lý thuyết: Chứng minh định lý (như điều kiện vô số phương án tối ưu khi tồn tại $c_j - c_B B^{-1} a_j = 0$).
  • Bài tập ứng dụng công nghệ: Lập trình thuật toán đơn hình, thuật toán hai pha bằng ngôn ngữ C hoặc Pascal; giải bài toán thực tế bằng phần mềm Excel hoặc LINGO.
  • Hướng dẫn tự học: Các định lý chứng minh phức tạp trong giải tích lồi và các thuật toán điểm trong được tác giả định hướng dành cho sinh viên tự nghiên cứu theo nhóm và thảo luận chuyên đề.

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

  • Tích hợp liên ngành giữa Toán học ứng dụng và Công nghệ thông tin:
    Giáo trình xây dựng cầu nối trực tiếp giữa giải tích toán học thuần túy với khoa học máy tính. Cấu trúc các thuật toán (như đơn hình cải biên ma trận $B^{-1}$) được trình bày dưới dạng khung giải thuật từng bước (khởi tạo, lặp, kết thúc) nhằm tối ưu hóa bộ nhớ lưu trữ và thời gian tính toán khi lập trình.
  • Gắn kết trực tiếp với dữ liệu thực nghiệm tại Việt Nam:
    Khác với các tài liệu thuần lý thuyết, giáo trình đưa vào các mô hình tối ưu được xây dựng từ số liệu điều tra thực địa tại các địa phương (mô hình 112 hộ nuôi cá tại huyện Văn Giang, mô hình nông nghiệp xã Đông Dư).
  • Cập nhật các hướng tiếp cận nâng cao:
    Bên cạnh các thuật toán kinh điển, giáo trình mở rộng sang các phương pháp tối ưu phi tuyến hiện đại như thuật toán Frank – Wolfe cho tập ràng buộc đa diện, phương pháp đơn hình lồi Zangwill, tối ưu đa mục tiêu bằng hàm thuộc mờ, và phương pháp điểm trong (Ellipsoid xấp xỉ) giải quy hoạch tuyến tính.

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

  • Sinh viên đại học: Giáo trình được thiết kế chuẩn hóa cho sinh viên năm thứ hai chuyên ngành Tin học, Công nghệ thông tin và Toán – Tin ứng dụng.
  • 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 Toán cao cấp cơ bản, bao gồm:
    • Đại số tuyến tính: Các phép toán ma trận, ma trận nghịch đảo, hạng của ma trận, hệ phương trình tuyến tính, không gian vector.
    • Giải tích toán học: Đạo hàm riêng, gradient, hàm nhiều biến khả vi cấp 1 và cấp 2, bài toán cực trị tự do.
  • Giảng viên và công tác giảng dạy: Tài liệu là căn cứ biên soạn đề cương bài giảng môn Tối ưu hóa / Vận trù học với thời lượng 3 đến 6 học trình. Giảng viên có thể sử dụng hệ thống ví dụ mẫu để giảng dạy trên lớp và giao các bài toán quy mô lớn cho sinh viên thực hành trên phòng máy tính.
  • Tự học và nghiên cứu: Người học có thể sử dụng giáo trình như một tài liệu tham khảo để phát triển các module thuật toán tối ưu phục vụ xây dựng phần mềm hỗ trợ ra quyết định.

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 phục vụ chính cho sinh viên năm thứ hai ngành Tin học, Công nghệ thông tin và Toán – Tin ứng dụng. Ngoài ra, sinh viên và học viên cao học các ngành kỹ thuật, kinh tế, quản lý hệ thống cần công cụ mô hình hóa tối ưu hóa cũng có thể sử dụng làm tài liệu học tập.

2. Cần chuẩn bị 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 nhân ma trận, tìm ma trận nghịch đảo, giải hệ phương trình tuyến tính) và Giải tích toán học (tính đạo hàm riêng, ma trận Hessian, vector gradient của hàm nhiều biến).

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

Giáo trình tập trung vào việc mô tả chi tiết quy trình tính toán số học và cấu trúc dữ liệu ma trận (đặc biệt là phương pháp đơn hình cải biên và thuật toán nhánh cận) nhằm phục vụ trực tiếp cho việc viết code cài đặt trên máy tính, kết hợp các case study thực tế có số liệu định lượng chi tiết.

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

Người học nên tuân thủ tiến trình: (1) Đọc hiểu bản chất hình học qua phương pháp đồ thị; (2) Giải tuần tự từng bước các bảng đơn hình đối với các ví dụ mẫu; (3) Tự lập trình giải thuật bằng ngôn ngữ C/Pascal hoặc sử dụng công cụ Excel Solver/LINGO để kiểm chứng kết quả; (4) Thảo luận nhóm các phần lý thuyết nâng cao trong Chương VI.

5. Có những tài liệu tham khảo nào được tác giả giới thiệu kèm theo?

Giáo trình giới thiệu các tài liệu tham khảo bổ trợ gồm:

  • Nguyễn Đức Nghĩa, Tối ưu hóa, Nxb. Giáo dục, 2002.
  • Phan Quốc Khánh – Trần Huệ Nương, Quy hoạch tuyến tính.
  • Bazaraa M.M, Nonlinear programming: Theory and algorithms, John Wiley and Sons, 1990.
  • Horst R, Hoàng Tụy, Global optimization: Deterministic approaches, Springer Verlag, 1993.
  • Bùi Thế Tâm – Trần Vũ Thiệu, Các phương pháp tối ưu hóa, Nxb. Giao thông vận tải, 1998.

Kết luận

Giáo trình Tối ưu hóa: Giáo trình cho ngành Tin học và Công nghệ thông tin của PGS. Nguyễn Hải Thanh hệ thống hóa toàn diện các phương pháp tối ưu tuyến tính, tối ưu nguyên và tối ưu phi tuyến, gắn liền với lý thuyết giải tích lồi. Tài liệu cung cấp cơ sở phương pháp luận để người học chuyển đổi bài toán thực tế thành mô hình toán học và cài đặt giải thuật trên máy tính. Lộ trình học tập được định hình từ nắm bắt thuật toán đơn hình cổ điển đến tiếp cận các phương pháp điểm trong và giải tích lồi hiện đại, kết hợp tham khảo các công trình chuyên sâu của các tác giả Nguyễn Đức Nghĩa, Bazaraa, Hoàng Tụy để mở rộng năng lực nghiên cứu.