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

Giáo trình Phương pháp tối ưu do giảng viên Lê Đức Nhượng biên soạn phục vụ công tác giảng dạy và học tập bậc đại học tại Trường Đại học Hải Phòng. Môn học Phương pháp tối ưu (Tối ưu hóa / Quy hoạch tuyến tính) giữ vị trí then chốt trong khối kiến thức toán ứng dụng và tin học tính toán, thuộc chương trình đào tạo của các ngành Công nghệ thông tin, Toán ứng dụng, Kỹ thuật và Quản lý kinh tế.

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:

  • Khả năng phân loại và nhận diện cấu trúc toán học của các dạng bài toán tối ưu (tuyến tính, phi tuyến, rời rạc, liên tục, tất định, ngẫu nhiên, tĩnh, động).
  • Kỹ năng toán học hóa các vấn đề thực tiễn trong kinh tế và kỹ thuật thành mô hình quy hoạch tuyến tính.
  • Nắm vững cơ sở giải tích và hình học của tập phương án, từ đó làm chủ các thuật toán giải như phương pháp đồ thị, phương pháp đơn hình dạng bảng, thuật toán đơn hình hai pha, phương pháp đánh thuế ($M$-phương pháp), thuật toán đơn hình đối ngẫu và thuật toán thế vị trong bài toán vận tải.
  • Kỹ năng ứng dụng công nghệ thông tin và phần mềm máy tính để giải quyết các bài toán tối ưu quy mô lớn.

Cấu trúc tài liệu được thiết kế gồm 6 chương lý thuyết kèm bài tập và phụ lục tài liệu tham khảo chuẩn mực. Cách tiếp cận của tác giả kết hợp chặt chẽ giữa tính chặt chẽ của giải tích toán học (hệ thống định lý, bổ đề, chứng minh giải tích) với tính tường minh của các thuật toán dạng bảng và ví dụ số trị thực hành. Điểm đặc sắc của giáo trình là việc kết nối lý thuyết quy hoạch tuyến tính cổ điển với lý thuyết độ phức tạp thuật toán hiện đại (các lớp $P$, $NP$, $NP\text{-Hard}$, $NP\text{-Complete}$), đồng thời giải quyết thấu đáo vấn đề thoái hóa và hiện tượng xoay vòng trong phương pháp đơn hình.

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

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

Cấu trúc nội dung giáo trình được triển khai qua 6 chương tuần tự:

[Chương 1: Mô hình bài toán tối ưu]
[Chương 2: Tập phương án của bài toán tối ưu]
[Chương 3: Phương pháp đơn hình]
[Chương 4: Lý thuyết đối ngẫu và bài toán tối ưu đối ngẫu]
[Chương 5: Bài toán vận tải]
[Chương 6: Giải bài toán tối ưu trên máy tính]
  • Chương 1: Mô hình bài toán tối ưu
    • Key concepts: Phân lớp bài toán theo độ phức tạp tính toán (lớp $P$, $NP$, quan hệ dẫn về đa thức $\propto$, lớp $NP\text{-Hard}$, $NP\text{-Complete}$, bài toán SATISFYABILITY của Cook và Karp 1971); Lịch sử tối ưu hóa từ công trình của L. Kantorovich (1938) và G. Dantzig (1947); Quy trình 5 bước xây dựng mô hình toán học; Các mô hình kinh tế - kỹ thuật thực tế (bài toán vốn đầu tư/khẩu phần dinh dưỡng, bài toán lập kế hoạch sản xuất, bài toán vận tải, bài toán cắt vật liệu thanh thép); Dạng tổng quát, dạng chính tắc ($Ax = b, x \ge 0$), dạng chuẩn tắc ($Ax \le b, x \ge 0$) và các quy tắc biến đổi đại số tương đương (sử dụng biến phụ, biến bù, hiệu hai biến không âm $x_j = x_j' - x_j''$).
  • Chương 2: Tập phương án của bài toán tối ưu
    • Key concepts: Vector hệ số hàm mục tiêu $c$, vector giới hạn $b$, ma trận ràng buộc $A$; Phương án chấp nhận được ($D$), phương án cơ sở chấp nhận được, biến cơ sở, biến phi cơ sở, phương án không thoái hóa; Hình học không gian lồi ($R^n$): tổ hợp lồi, tập lồi, điểm cực biên, đa diện lồi, siêu phẳng ($A_i x = b_i$), nửa không gian ($A_i x \le b_i$), tập lồi đa diện; Định lý phương án tối ưu luôn đạt tại ít nhất một điểm cực biên; Phương pháp hình học (đồ thị) giải bài toán 2 biến trên mặt phẳng tọa độ $x_1Ox_2$ dựa trên vector pháp tuyến và họ đường mức $c_1x_1 + c_2x_2 = z$.
  • Chương 3: Phương pháp đơn hình
    • Key concepts: Thuật toán đơn hình dạng bảng; Tiêu chuẩn tối ưu qua hệ số ước lượng kiểm tra $\Delta_k = \sum_{j \in J} z_{jk} c_j - c_k$; Tiêu chuẩn hàm mục tiêu không bị chặn; Quy tắc chọn cột xoay $A_s$, dòng xoay $A_r$, phần tử trục $z_{rs}$ và phép xoay ma trận; Phân tích tính hữu hạn của thuật toán đơn hình; Hiện tượng xoay vòng (cycling); Biện pháp chống xoay vòng gồm Phương pháp cực tiểu từ vựng ($\text{lex-min}$) và Quy tắc Bland (1976); Thuật toán đơn hình hai pha (sử dụng vector biến giả $x_u$, giải bài toán phụ $e'x_u \to \min$) và Phương pháp đánh thuế ($M$-phương pháp).
  • Chương 4: Lý thuyết đối ngẫu và bài toán tối ưu đối ngẫu
    • Key concepts: Quy tắc chuyển đổi bài toán tối ưu tổng quát sang bài toán đối ngẫu tương ứng; Ý nghĩa kinh tế của các biến đối ngẫu (giá bóng / shadow price); Các định lý đối ngẫu cơ bản (định lý đối ngẫu yếu, định lý đối ngẫu mạnh, điều kiện độ lệch bù); Thuật toán đơn hình đối ngẫu.
  • Chương 5: Bài toán vận tải
    • Key concepts: Mô hình toán học của bài toán vận tải cân bằng thu phát ($\sum a_i = \sum b_j$) và không cân bằng; Điều kiện tồn tại nghiệm và tiêu chuẩn nhận biết phương án cực biên; Các phương pháp tìm phương án xuất phát: Phương pháp góc Tây Bắc, Cực tiểu cước phí (theo dòng, theo cột, toàn bảng), Phương pháp Vogel (Fôghen), Phương pháp Larson; Tiêu chuẩn tối ưu và thuật toán thế vị ($u_i + v_j = c_{ij}$); Kỹ thuật thêm trạm thu giả/phát giả cho trường hợp mất cân bằng.
  • Chương 6: Giải bài toán tối ưu trên máy tính
    • Key concepts: Ứng dụng phần mềm chuyên dụng và công cụ tính toán tin học để giải bài toán quy hoạch tuyến tính tổng quát và bài toán vận tải tự động.

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

Giáo trình thiết lập hệ thống nền tảng học thuật qua ba trụ cột:

  1. Lý thuyết độ phức tạp tính toán (Computational Complexity): Cung cấp nền móng lý thuyết phân loại bài toán $P$, $NP$, $NP\text{-Complete}$, giúp người học hiểu rõ giới hạn của các thuật toán thời gian đa thức so với bài toán hàm mũ.
  2. Lý thuyết tập lồi và đa diện lồi (Convex Analysis & Polyhedral Sets): Chứng minh cấu trúc hình học của miền ràng buộc là tập lồi đa diện trong không gian $n$ chiều, xác lập cơ sở toán học cho việc thu hẹp không gian tìm kiếm nghiệm tối ưu về tập hữu hạn các điểm cực biên.
  3. Lý thuyết đối ngẫu (Duality Theory): Xây dựng mối quan hệ tương hỗ giữa bài toán gốc (Primal) và bài toán đối ngẫu (Dual), làm sáng tỏ ý nghĩa kinh tế của tài nguyên và giá trị biên định lượng.

Kỹ năng phát triển

  • Kỹ năng kỹ thuật (Technical Skills): Biến đổi đại số tuyến tính ma trận, đưa bài toán về dạng chuẩn tắc/chính tắc; lập và biến đổi bảng đơn hình, bảng đơn hình hai pha; tính toán bảng thế vị cho mạng lưới phân phối vận tải.
  • Kỹ năng phân tích (Analytical Skills): Phân tích tính tương thích của mô hình, phát hiện các điều kiện suy biến/thoái hóa, xác định nguyên nhân bài toán không có lời giải hoặc hàm mục tiêu không bị chặn; phân tích độ nhạy qua bài toán đối ngẫu.
  • Kỹ năng ứng dụng thực tế (Practical Competencies): Khả năng mô hình hóa 5 bước cho các bài toán tối ưu hóa chi phí sản xuất, phân bổ nguyên vật liệu gia công, tối ưu hóa kích thước cắt phôi kim loại và điều phối logistics.

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

Giáo trình triển khai phương pháp sư phạm diễn dịch kết hợp quy nạp trực quan:

  • Đi từ trực quan hình học 2 chiều (Chương 2) để người học nắm bắt trực giác về miền chấp nhận được và đường mức, sau đó tổng quát hóa sang không gian đại số đa chiều $R^n$ và phương pháp đơn hình dạng bảng (Chương 3).
  • Mọi thuật toán đều được mô tả theo 2 định dạng: sơ đồ khối logic giải thuật (lưu đồ thuật toán) và quy trình tính toán số trị từng bước trên bảng biểu.

Hệ thống bài tập và nghiên cứu tình huống trong giáo trình bám sát các kịch bản thực nghiệm:

  • Bài toán gia công cơ khí: Xí nghiệp vận hành 510 giờ máy cán, 360 giờ máy tiện, 150 giờ máy mài để sản xuất 3 loại sản phẩm $A, B, C$ với đơn giá lợi nhuận 48, 16, 27 nghìn đồng/đơn vị.
  • Bài toán công nghiệp luyện kim: Nhà máy cán thép tấm và thép cuộn với giới hạn 40 giờ công/tuần và năng suất định mức (200 tấn tấm/h hoặc 140 tấn cuộn/h), giới hạn sức tiêu thụ thị trường (6000 tấn thép tấm, 4000 tấn thép cuộn).
  • Bài toán cắt vật liệu tối ưu: Xưởng cơ khí cắt các thanh thép nguyên chiều dài chuẩn (12m hoặc 3m) thành các quy cách ngắn hơn (1.2m, 1.5m, 4m, 5m, 7m) nhằm tối thiểu hóa phần thép thừa.
  • Bài toán khẩu phần và nông nghiệp: Tối ưu hóa chi phí mua thức ăn chăn nuôi đáp ứng đủ định lượng dinh dưỡng $D_1, D_2$; phân bổ 100 gà mái đẻ trứng hoặc ấp trứng để tối đa hóa doanh thu sau chu kỳ 8 tuần.
  • Bài toán điều phối vận chuyển: Bài toán 3 người đi quãng đường 10km chia sẻ 1 xe đạp đơn với tốc độ đi bộ (4km/h, 2km/h) và tốc độ xe đạp (16km/h, 12km/h) nhằm cực tiểu hóa thời gian người cuối cùng về đích.

Phương pháp đánh giá kết quả học tập dựa trên 3 tiêu chí:

  1. Độ chính xác trong việc chuyển ngữ đề bài thực tế sang mô hình giải tích dạng chính tắc.
  2. Kỹ năng thực hiện các phép lặp trên bảng đơn hình/bảng thế vị và áp dụng đúng quy tắc chống xoay vòng.
  3. Kỹ năng biện luận nghiệm tối ưu và kết luận phương án ứng dụng.

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

  • Tính hệ thống hóa học thuật: Giáo trình kế thừa và chuẩn hóa hệ thống kiến thức tối ưu tuyến tính từ 15 công trình giáo khoa và chuyên khảo tiêu chuẩn tại Việt Nam, bao gồm các tài liệu của Nguyễn Đức Nghĩa, Bùi Minh Trí, Trần Vũ Thiệu, Hoàng Tụy, Phan Quốc Khánh, Đặng Văn Uyên, Lê Mậu Dũng, Phạm Trí Cao.
  • Tích hợp lý thuyết độ phức tạp tính toán: Giáo trình đặt trọng tâm ngay từ Chương 1 vào việc phân loại bài toán $P$, $NP$, $NP\text{-Hard}$, $NP\text{-Complete}$, giải thích nguyên lý dẫn về đa thức và chứng minh thực tế của Cook - Karp năm 1971 qua bài toán SATISFYABILITY. Cách tiếp cận này giúp sinh viên tiếp cận tối ưu hóa dưới góc độ thuật toán học máy tính hiện đại.
  • Giải quyết triệt để bài toán suy biến và xoay vòng: Thay vì bỏ qua trường hợp thoái hóa như một số tài liệu nhập môn, giáo trình phân tích chi tiết hiện tượng xoay vòng và trình bày toán học chặt chẽ hai giải pháp giải tích:
    • Phương pháp cực tiểu từ vựng: Chứng minh định lý vector từ vựng giảm ngặt đảm bảo thuật toán dừng sau hữu hạn bước.
    • Quy tắc Bland (1976): Nguyên tắc chọn chỉ số nhỏ nhất cho dòng xoay và cột xoay để loại bỏ chu trình lặp vô hạn.
  • Gắn kết thực tiễn kinh tế và công nghiệp: Hệ thống mô hình bao quát từ quy hoạch sản xuất công nghiệp, cắt phôi vật liệu cơ khí, định lượng dinh dưỡng chăn nuôi đến bài toán mạng lưới vận tải $m$ trạm phát - $n$ trạm thu.

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

  • Sinh viên đại học:
    • Sinh viên từ năm thứ 2 hoặc năm thứ 3 thuộc các ngành Công nghệ thông tin, Khoa học máy tính, Kỹ thuật phần mềm, Toán ứng dụng.
    • Sinh viên khối ngành Kinh tế, Quản trị sản xuất, Quản lý chuỗi cung ứng, Hệ thống thông tin quản lý có học phần Quy hoạch toán học hoặc Tối ưu hóa.
  • Học viên cao học: Dùng làm tài liệu củng cố nền tảng lý thuyết tối ưu hóa, chuẩn bị cho các học phần nâng cao về Tối ưu phi tuyến, Tối ưu tổ hợp và Lý thuyết điều khiển tối ưu.
  • Kiến thức tiên quyết (Prerequisites):
    • Đại số tuyến tính: Ma trận, định thức, hạng ma trận, hệ phương trình đại số tuyến tính, không gian vector $R^n$, khái niệm độc lập và phụ thuộc tuyến tính, cơ sở không gian.
    • Giải tích cơ bản: Hàm số nhiều biến, đạo hàm riêng, cực trị tự do và cực trị có điều kiện.
  • Giảng viên: Sử dụng làm đề cương bài giảng chuẩn mực, khai thác hệ thống chứng minh định lý, lưu đồ thuật toán và nguồn bài tập phong phú để thiết kế bài giảng, bài tập lớn và đề thi học phần.
  • Tự học và tra cứu chuyên môn: Tài liệu tham khảo hữu ích cho kỹ sư phần mềm, lập trình viên phát triển thuật toán và chuyên viên phân tích vận hành (Operations Research Analyst).

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ụ trực tiếp cho sinh viên đại học ngành Công nghệ thông tin, Toán tin ứng dụng, Kỹ thuật và Quản lý kinh tế; đồng thời là tài liệu tham khảo cho học viên cao học và chuyên viên nghiên cứu vận trù học.

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

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, giải hệ phương trình tuyến tính, vector độc lập tuyến tính) và tư duy thuật toán cơ bả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 khác là gì?

Giáo trình tích hợp lý thuyết độ phức tạp thuật toán hiện đại ($P, NP, NP\text{-Complete}$), phân tích chi tiết hiện tượng suy biến - xoay vòng cùng các thuật toán chống xoay vòng chuẩn mực (Bland, cực tiểu từ vựng), đồng thời cung cấp đầy đủ phương pháp đơn hình 2 pha, phương pháp đánh thuế và thuật toán thế vị.

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

Người học nên tuân thủ lộ trình: Đọc hiểu 5 bước xây dựng mô hình $\to$ Tự giải bài toán 2 biến bằng đồ thị hình học $\to$ Thực hành thuần thục các bước lặp biến đổi bảng đơn hình trên các ví dụ mẫu $\to$ Kiểm tra kết quả bằng các công cụ tính toán trên máy tính.

5. Có tài liệu bổ trợ nào được khuyến nghị kèm theo?

Giáo trình dẫn xuất 15 tài liệu tham khảo tiêu chuẩn, trong đó có sách bài tập của GS. Bùi Minh Trí, TS. Phí Mạnh Ban, TS. Phạm Trí Cao và chuyên đề hướng dẫn giải bài toán tối ưu trên Excel của TS. Bùi Thị Tâm.

Kết luận

Giáo trình Phương pháp tối ưu của tác giả Lê Đức Nhượng là tài liệu học thuật hoàn chỉnh, cấu trúc khoa học và chuẩn mực về quy hoạch tuyến tính và tối ưu hóa toán học. Giá trị cốt lõi của giáo trình thể hiện ở sự cân bằng giữa lý thuyết giải tích lồi nghiêm ngặt và các thuật toán tính toán thực hành dạng bảng biểu rõ ràng.

Lộ trình học tập đề xuất:

  1. Tiếp cận bản chất bài toán qua phân lớp độ phức tạp và quy trình mô hình hóa (Chương 1).
  2. Nắm vững hình học không gian tập phương án và phương pháp đồ thị (Chương 2).
  3. Làm chủ thuật toán đơn hình, đơn hình hai pha và quy tắc chống xoay vòng (Chương 3).
  4. Phân tích bài toán qua lý thuyết đối ngẫu và thuật toán đơn hình đối ngẫu (Chương 4).
  5. Thực hành giải thuật toán thế vị trên bài toán vận tải chuyên biệt (Chương 5).
  6. Ứng dụng phần mềm máy tính để giải quyết bài toán quy mô thực tế (Chương 6).

Người học có thể tham khảo thêm các giáo trình chuyên sâu của GS. Hoàng Tụy (Lý thuyết tối ưu), PGS.TS. Nguyễn Đức Nghĩa (Tối ưu hóa: Quy hoạch tuyến tính và rời rạc) và tài liệu ứng dụng của TS. Bùi Thị Tâm để mở rộng năng lực giải quyết các bài toán tối ưu hóa phức tạp.