GIỚI THIỆU VÀ MÔ TẢ THƯ MỤC HỌC THUẬT: GIÁO TRÌNH TÍNH TỐI ƯU TUYẾN TÍNH VÀ ỨNG DỤNG

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

Giáo trình Tính tối ưu tuyến tính và ứng dụng (còn được lưu hành với tên gọi Giáo trình Quy hoạch tuyến tính) do tác giả Nguyễn Hữu Điển biên soạn, được Nhà xuất bản Đại học Quốc gia Hà Nội xuất bản vào tháng 01 năm 2018. Tài liệu được xây dựng dựa trên bài giảng học phần Tối ưu hóa tuyến tính được giảng dạy trực tiếp tại Trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội, với khung thời lượng tiêu chuẩn từ 45 đến 60 tiết học.

Trong chương trình đào tạo đại học và sau đại học, môn học giữ vị trí cầu nối quan trọng giữa các ngành Toán học thuần túy (Đại số tuyến tính, Giải tích hàm, Hình học) với các phân ngành Toán ứng dụng, Khoa học máy tính và Kinh tế lượng.

[Mô hình hóa thực tế] ──> [Giải tích lồi & Hình học đa diện] ──> [Thuật toán tối ưu] ──> [Phân tích đối ngẫu & Mở rộng]

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

  • Phương pháp luận chuyển đổi các bài toán thực tiễn về mô hình toán học chuẩn tắc.
  • Khả năng chứng minh, nắm vững cấu trúc giải tích lồi và không gian nghiệm đa diện.
  • Kỹ năng thực thi các thuật toán tối ưu hóa tuyến tính kinh điển và hiện đại trên bảng tính cũng như mã lệnh máy tính.

Cấu trúc tiếp cận của giáo trình đi từ việc xây dựng mô hình bài toán thực tế, làm rõ cơ sở giải tích lồi trong không gian $\mathbb{R}^n$, sau đó triển khai chi tiết các thuật toán giải (thuật toán đơn hình, phân tích đối ngẫu, phân phối vận tải, phương pháp Gomory, thuật toán nhánh cận) và mở rộng sang tối ưu đa mục tiêu cùng lý thuyết trò chơi ma trận. Điểm đặc sắc của tài liệu là tính chính xác về mặt toán học kết hợp với tính hệ thống của các bảng tính đơn hình và tuyển tập bài tập mẫu có lời giải chi tiết.

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

                             GIÁO TRÌNH TÍNH TỐI ƯU TUYẾN TÍNH VÀ ỨNG DỤNG
                                                 │
      ┌────────────────────────┬─────────────────┴───────────────┬────────────────────────┐
      ▼                        ▼                                 ▼                        ▼
[Chương 1: Cơ sở]    [Chương 2-3: QHTT & Đối ngẫu]    [Chương 4-6: Bài toán Vận tải]   [Chương 7-10: Mở rộng]
 - Không gian R^n     - Dạng tổng quát/chính tắc       - Góc Tây Bắc, Min cước, Vogel  - Quy hoạch nguyên
 - Tập lồi, Hàm lồi   - Phương pháp đơn hình           - Thuật toán thế vị, quy không  - Trò chơi ma trận
 - Định lý tách       - Phương pháp 2 pha, M-lớn       - Không cân bằng, ô cấm         - Đa mục tiêu Pareto
 - Nón & Khối đa diện - Đơn hình đối ngẫu, độ nhạy     - Sản xuất đồng bộ, Bổ nhiệm    - Hướng dẫn giải (C.11)

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

  • Chương 1: Giới thiệu bài toán tối ưu và cơ sở giải tích lồi Trình bày các mô hình toán học thực tế điển hình (sản xuất công nghiệp gỗ, phối trộn khẩu phần thức ăn, lập kế hoạch cắt thép, phân bổ danh mục đầu tư tài chính, điều độ sản xuất 3 tháng). Thiết lập nền tảng không gian tuyến tính $\mathbb{R}^n$, hình học tô pô (chuẩn, khoảng cách, tập compact, siêu phẳng, nửa không gian), lý thuyết giải tích lồi (tập lồi, bao lồi $\text{conv}(C)$, điểm cực biên, định lý tách tập lồi, nón lồi, khối lồi đa diện, đơn hình chuẩn), tính chất hàm lồi/lõm, bất đẳng thức Jensen, hàm tựa lồi, hàm lồi mạnh, vector gradient $\nabla f(x)$ và ma trận Hessian.

  • Chương 2: Bài toán quy hoạch tuyến tính (QHTT) Định nghĩa bài toán QHTT tổng quát, dạng chính tắc, dạng chuẩn tắc và các quy tắc biến đổi tương đương. Khảo sát phương pháp hình học, bản chất phương án cơ bản (cực biên, suy biến và không suy biến). Triển khai cấu trúc phương pháp đơn hình, bảng đơn hình, quy tắc xoay trục, bài toán đơn hình 2 pha, phương pháp chữ $M$ (đánh thuế), phương pháp đơn hình cải tiến, xử lý hiện tượng xoay vòng, bài toán phân số tuyến tính và bài toán tham số trên hàm mục tiêu.

  • Chương 3: Lý thuyết bài toán đối ngẫu Xây dựng cặp bài toán gốc – đối ngẫu ở các dạng chuẩn tắc, chính tắc và tổng quát. Chứng minh các định lý đối ngẫu (đối ngẫu yếu, định lý đối ngẫu mạnh, điều kiện bù bù trừ). Ứng dụng thuật toán đơn hình đối ngẫu. Phân tích sau tối ưu (phân tích độ nhạy): đánh giá sự biến động của nguồn lực vế phải $b_i$, hệ số hàm mục tiêu $c_j$ và kỹ thuật bổ sung ràng buộc mới vào bài toán.

  • Chương 4 – 6: Bài toán vận tải và các mô hình phân phối chuyên biệt Mô hình hóa bài toán vận tải cân bằng và không cân bằng thu phát. Các phương pháp xác định phương án xuất phát ban đầu: Phương pháp Góc Tây Bắc, Phương pháp Cước phí nhỏ nhất, Phương pháp Vogel (Fogel). Thuật toán tối ưu hóa trên bảng vận tải: Phương pháp Thế vị ($u_i + v_j = c_{ij}$) và Phương pháp Quy không cước phí. Kỹ thuật xử lý suy biến, ô cấm vận chuyển, bài toán vận tải thông qua hạn chế, bài toán bổ nhiệm (phân công việc) và mô hình bài toán sản xuất đồng bộ bằng phương pháp nhân tử.

  • Chương 7 – 8: Quy hoạch tuyến tính nguyên Khảo sát bài toán tối ưu nguyên toàn phần và nguyên bộ phận. Phương pháp mặt phẳng cắt Gomory (phương pháp hình học và thuật toán Gomory tổng quát trên bảng đơn hình). Phương pháp Nhánh và Cận (Branch and Bound) giải bài toán tối ưu rời rạc.

  • Chương 9 – 10: Trò chơi ma trận và Tối ưu tuyến tính đa mục tiêu Lý thuyết trò chơi ma trận: Hàm thu hoạch, điểm yên ngựa, chiến lược thuần túy và chiến lược hỗn hợp, trò chơi đối xứng, phương pháp chuyển đổi trò chơi ma trận hai người tổng bằng không về bài toán QHTT. Tối ưu hóa đa mục tiêu: Kỹ thuật hàm phạt, tối ưu không ưu tiên, tối ưu có thứ tự ưu tiên, khái niệm nghiệm hiệu quả/tối ưu Pareto và thuật toán tìm điểm hữu hiệu.

  • Chương 11: Lời giải và gợi ý bài tập Cung cấp đáp số, chỉ dẫn giải chi tiết cho hệ thống bài tập lý thuyết giải tích lồi và các bài toán mô hình tính toán số lượng.

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

Lĩnh vực nền tảng Nguyên lý & Định lý cốt lõi trong giáo trình
Đại số tuyến tính Hệ vector độc lập tuyến tính, cơ sở không gian $\mathbb{R}^n$, ma trận đối xứng, dạng toàn phương $f(x) = \langle x, Cx \rangle$, tiêu chuẩn Sylvester kiểm tra nửa xác định dương.
Tô pô & Hình học giải tích Chuẩn Euclidean $|x|$, tập đóng, tập mở, tập compact (Định lý Bolzano-Weierstrass), siêu phẳng $H = {x : \langle a, x \rangle = \alpha}$, nửa không gian đóng/mở.
Giải tích lồi Tổ hợp lồi, bao lồi $\text{conv}(C)$, định lý tách tập lồi bằng siêu phẳng (tách thường và tách mạnh), khối lồi đa diện $Ax \le b$, định lý biểu diễn nghiệm qua điểm cực biên và phương vô hạn.
Vi phân nhiều biến Vector Gradient $\nabla f(x)$, đạo hàm theo hướng $\delta f(x, d)$, ma trận Hessian $P(x)$, định lý điều kiện cực trị: Mọi cực tiểu địa phương của hàm lồi trên tập lồi đều là cực tiểu toàn cục.

Kỹ năng phát triển

  • Kỹ năng mô hình hóa kỹ thuật: Chuyển dịch bài toán thực tế thành ngôn ngữ toán học hình thức, thiết lập hàm mục tiêu và hệ thống ràng buộc bất đẳng thức/đẳng thức (như bài toán pha cắt vật liệu thép nhằm tối thiểu lượng phế liệu thừa: $f = 0.2x_1 + 0.8x_4 + 0.6x_5 \to \min$).
  • Kỹ năng phân tích giải thuật: Vận hành thành thạo các thuật toán bảng đơn hình primal/dual, thiết lập chu trình chuyển giao trên bảng vận tải, phân tích ma trận bù trong bài toán trò chơi ma trận.
  • Kỹ năng đánh giá độ nhạy kinh tế lượng: Ứng dụng lý thuyết đối ngẫu để giải thích giá trị kinh tế của nguồn lực dự trữ (giá bóng/giá mờ - shadow price), kiểm soát rủi ro danh mục đầu tư và điều phối năng lực sản xuất giữa giờ làm việc thông thường ($x_j$) và giờ phụ trội ($y_j$).

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

Giáo trình triển khai quy trình sư phạm chuẩn tắc qua mô hình hóa 4 bước khép kín:

[Bước 1: Khảo sát thực tiễn]
 └─> Xác định biến số, tham số kinh tế, giới hạn tài nguyên
[Bước 2: Xây dựng mô hình toán học]
 └─> Thiết lập hàm mục tiêu max/min và hệ ràng buộc Ax <= b, x >= 0
[Bước 3: Lựa chọn & Thực thi giải thuật]
 └─> Bảng đơn hình, thuật toán thế vị, phương pháp Gomory, nhánh cận
[Bước 4: Phân tích & Kiểm định kết quả]
 └─> Kiểm định tính khả thi, phân tích độ nhạy đối ngẫu, áp dụng thực tế

Hệ thống case studies và bài toán thực tế được tích hợp xuyên suốt:

  • Bài toán sản xuất công nghiệp đồ gỗ: Xác định cơ cấu sản phẩm bàn ($x_1$), ghế ($x_2$), tủ ($x_3$) với 500 ngày công, 40 triệu đồng chi phí và tỷ lệ sản phẩm cố định để tối đa hóa doanh thu: $$\max f(x) = 260x_1 + 120x_2 + 600x_3$$
  • Bài toán phối trộn khẩu phần dinh dưỡng: Tối thiểu hóa chi phí thức ăn cho gia súc ($20x_1 + 15x_2 \to \min$) đảm bảo định mức chất béo, chất xơ, chất đạm.
  • Bài toán phân bổ vốn đầu tư: Tối ưu hóa danh mục 2 tỷ đồng vào 4 kênh: Chứng khoán (20%), Công trái (12%), Gửi tiết kiệm (10%), Bất động sản (15%) kèm ràng buộc khống chế tỷ lệ rủi ro.
  • Bài toán điều độ sản xuất liên hoàn 3 tháng: Cân đối sản xuất giờ thường ($x_j \le 100$), giờ phụ trội ($y_j \le 15$), tồn kho ($z_j$) với chi phí lưu kho 2.000 đồng/đơn vị/tháng.

Giáo trình thiết kế hai cấp độ bài tập: bài toán chứng minh giải tích lồi giải bằng phương pháp thuần túy và bài toán số học tính toán trực tiếp trên bảng biểu, thuận lợi cho việc kiểm tra trên máy tính. Phần đánh giá kết quả học tập được định hướng qua các bài thi tự luận giải thuật và kiểm tra kỹ năng phân tích độ nhạy.

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

  • Hệ thống hóa lịch sử phát triển học thuật: Giáo trình ghi nhận mốc lịch sử từ các nghiên cứu tiên phong của Viện sĩ L. Kantorovich (Liên Xô) năm 1939 về kế hoạch hóa sản xuất, đến sự kiện nhà toán học George Dantzig đề xuất phương pháp đơn hình vào năm 1947, đặt nền móng cho lý thuyết quy hoạch tuyến tính hiện đại.
  • Tính tương thích với công nghệ tính toán hiện đại: Giáo trình gắn liền cấu trúc giải thuật với các gói lệnh tối ưu hóa trên phần mềm máy tính, giúp người học dễ dàng chuyển đổi từ bảng tính tay sang việc lập trình giải tự động.
  • Mở rộng toàn diện các phân nhánh tối ưu: Không giới hạn ở quy hoạch tuyến tính liên tục cổ điển, tài liệu mở rộng sang:
    • Tối ưu hóa phân thức tuyến tính.
    • Tối ưu hóa có chứa tham số trên hàm mục tiêu và vế phải.
    • Tối ưu hóa rời rạc và quy hoạch nguyên (Gomory, Nhánh cận).
    • Tối ưu hóa đa mục tiêu theo nguyên lý Pareto.
    • Ứng dụng lý thuyết trò chơi ma trận đối kháng.
  • Chuẩn hóa hệ thống ký hiệu toán học: Bảng ký hiệu đầu sách quy định chi tiết từ các tập hợp số ($\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}$), ký hiệu bài toán (QHTT, BTVT), các phần tử trục $[m]$, phần tử chọn $(n)$ trên bảng đơn hình, giúp bảo đảm tính đồng nhất và chính xác trong học thuật.

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

┌────────────────────────────────────────────────────────────────────────┐
│                        ĐỐI TƯỢNG SỬ DỤNG                               │
├──────────────────────────────────┬─────────────────────────────────────┤
│ Sinh viên & Học viên Cao học     │ Giảng viên & Nhà nghiên cứu         │
│ - Ngành: Toán học, Toán tin      │ - Giáo trình giảng dạy (45-60 tiết) │
│ - Ngành: Kinh tế lượng, Data     │ - Thiết lập đề thi, bài tập chuẩn   │
│ - Ngành: Quản lý vận hành        │ - Tài liệu tra cứu thuật toán       │
└──────────────────────────────────┴─────────────────────────────────────┘
  • Sinh viên đại học: Sinh viên từ năm thứ hai hoặc năm thứ ba thuộc các ngành: Toán học, Toán tin ứng dụng, Khoa học dữ liệu, Kinh tế học số lượng, Hệ thống thông tin quản lý, Logistics và Quản lý chuỗi cung ứng.
  • Học viên cao học và nghiên cứu sinh: Sử dụng làm tài liệu tra cứu các định lý cơ sở về tính lồi, định lý tách đa diện và các giải thuật tối ưu hóa rời rạc/đa mục tiêu.
  • Kiến thức tiên quyết (Prerequisites):
    • Đại số tuyến tính: Phép toán ma trận, định thức, hệ phương trình đại số tuyến tính, không gian vector.
    • Giải tích cổ điển: Khái niệm không gian $\mathbb{R}^n$, giới hạn dãy điểm, đạo hàm riêng, gradient.
  • Giảng viên: Sử dụng làm đề cương chi tiết và tài liệu giảng dạy chính khóa cho học phần Quy hoạch tuyến tính / Tối ưu hóa với thời lượng phân bổ từ 45 đến 60 tiết.
  • Tự học và tra cứu chuyên nghiệp: Phù hợp cho kỹ sư vận hành, chuyên viên tối ưu hóa chi phí sản xuất muốn nghiên cứu bản chất toán học của các thuật toán tối ưu.

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

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

Giáo trình được biên soạn phục vụ sinh viên đại học, học viên cao học chuyên ngành Toán học, Toán tin, Kinh tế học, Khoa học dữ liệu và Quản lý sản xuất cần nắm vững phương pháp tối ưu tuyến tính.

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

Người học cần hoàn thành khối kiến thức cơ sở về Đại số tuyến tính (không gian vector, ma trận, hệ phương trình tuyến tính) và Giải tích toán học nhiều biến (chuẩn, tích vô hướng, đạo hàm riêng, gradient).

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

Tài liệu liên kết chặt chẽ giữa giải tích lồi thuần túy (định lý tách, khối đa diện, nón lồi) với kỹ thuật giải thuật toán thực hành (bảng đơn hình, bảng vận tải, thuật toán Gomory, nhánh cận), đồng thời mở rộng đầy đủ sang các chuyên đề tối ưu nguyên, đa mục tiêu và trò chơi ma trận.

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

Người học nên tuân thủ quy trình: Nghiên cứu các bước xây dựng mô hình toán học $\to$ Tự thực hiện các phép biến đổi bảng đơn hình bằng tay $\to$ Lập trình kiểm tra nghiệm trên máy tính $\to$ Đối chiếu lời giải và gợi ý chi tiết tại Chương 11.

5. Giáo trình có tài liệu bổ trợ nào kèm theo không?

Tài liệu cung cấp hệ thống ký hiệu chuẩn hóa ở phần mở đầu, các bảng định mức số liệu thực tế tại các chương và toàn bộ phần chỉ dẫn giải, gợi ý bài tập ứng dụng tại Chương 11 của cuốn sách.

Kết luận

Giáo trình Tính tối ưu tuyến tính và ứng dụng của tác giả Nguyễn Hữu Điển (NXB Đại học Quốc gia Hà Nội) là tài liệu học thuật hoàn chỉnh, chuẩn mực về lý thuyết quy hoạch tuyến tính và tối ưu hóa toán học. Cuốn sách định hình lộ trình học tập khoa học: đi từ cơ sở giải tích lồi, hình học không gian $\mathbb{R}^n$, qua các giải thuật đơn hình, phương pháp đối ngẫu, bài toán vận tải kinh điển, đến các chủ đề nâng cao như quy hoạch nguyên, trò chơi ma trận và tối ưu hóa đa mục tiêu Pareto.

Với hệ thống bài tập phong phú kèm lời giải chi tiết tại Chương 11 và các liên kết học thuật cùng cộng đồng học thuật VietTeX, giáo trình đáp ứng đầy đủ yêu cầu giảng dạy, học tập và nghiên cứu trong các cơ sở giáo dục đại học.