Bối cảnh và vấn đề nghiên cứu

Quy hoạch tuyến tính nguyên (Integer Linear Programming) là một bộ phận cốt lõi của tối ưu hóa rời rạc. Trong thực tiễn điều khiển, kinh tế, thiết kế kỹ thuật, tin học và sinh học, nhiều bài toán quản lý và phân bổ nguồn lực đòi hỏi các biến quyết định phải nhận giá trị nguyên do đối tượng nghiên cứu mang tính đơn vị, không thể phân chia tùy ý (chẳng hạn như số lượng máy kéo, chuyến xe, nhân sự hay các lựa chọn nhị phân đóng/mở dự án). Khi đó, việc áp dụng các phương pháp tối ưu hóa liên tục truyền thống rồi làm tròn số học thường dẫn đến phương án không khả thi hoặc cách xa điểm tối ưu thực tế.

Lịch sử phát triển của quy hoạch tuyến tính nguyên ghi nhận dấu mốc quan trọng vào năm 1958 khi Ralph E. Gomory công bố thuật toán lát cắt để giải quyết bài toán quy hoạch tuyến tính nguyên toàn phần, kế thừa tư tưởng nền tảng được đề xuất năm 1954 bởi George Dantzig, Ray Fulkerson và Selmer Johnson. Khóa luận tốt nghiệp của tác giả Trịnh Anh Tuấn (ngành Toán - Tin học, Trường Đại học Sư phạm TP. Hồ Chí Minh, khóa 2005 - 2009, dưới sự hướng dẫn của TS. Trịnh Công Diệu) tập trung giải quyết bài toán quy hoạch tuyến tính nguyên toàn phần thông qua các nhiệm vụ nghiên cứu cụ thể:

  1. Hệ thống hóa các kiến thức nền tảng của quy hoạch tuyến tính liên tục, bao gồm thuật toán đơn hình gốc, thuật toán đơn hình đối ngẫu và kỹ thuật tái tối ưu hóa làm công cụ giải quyết bài toán nguyên.
  2. Xây dựng cơ sở lý thuyết, chứng minh tính đúng đắn và thiết lập quy trình thực hiện của hai thuật toán kinh điển: Thuật toán nhánh cận (Branch and Bound) và Thuật toán cắt Gomory (Gomory's Cutting Plane).
  3. Chứng minh tính hữu hạn của thuật toán nhánh cận và thuật toán cắt Gomory khi miền phương án chấp nhận được là tập lồi đa diện.
  4. Nghiên cứu mô hình toán học và phương pháp giải cho các bài toán ứng dụng thực tế gồm: bài toán quy hoạch nhị phân, bài toán cái túi loại 2, bài toán phân việc, bài toán pha cắt vật liệu, bài toán xếp hàng lên tàu và bài toán người du lịch.

Đối tượng nghiên cứu xuyên suốt khóa luận là bài toán quy hoạch tuyến tính nguyên toàn phần dạng thu nhỏ và tổng quát trong không gian hữu hạn chiều, với các hệ số ma trận thuộc tập số thực $\mathbb{R}$ và số hữu tỷ $\mathbb{Q}$.

Cơ sở lý thuyết và phương pháp

Khóa luận sử dụng khung lý thuyết tối ưu hóa toán học và phương pháp đại số tuyến tính kết hợp lý thuyết tập lồi đa diện. Cụ thể:

  • Mô hình toán học nền tảng:
    • Bài toán quy hoạch tuyến tính (QHTT) dạng tổng quát: $\langle c, x \rangle \to \min (\max)$ với hệ ràng buộc $Ax \ge b$ (hoặc $Ax \le b$).
    • Bài toán QHTT dạng chính tắc: $\langle c, x \rangle \to \min$ với $Ax = b, x \ge 0$.
    • Bài toán QHTT dạng chuẩn tắc: $\langle c, x \rangle \to \min$ với $Ax \ge b, x \ge 0$.
    • Bài toán QHTT nguyên toàn phần: $(P_0): \langle c, x \rangle \to \min$ với $Ax = b, x \ge 0, x \in \mathbb{Z}^n$.
  • Phương pháp nghiên cứu:
    • Phương pháp giải tích và đại số tuyến tính: Khảo sát cấu trúc tập phương án chấp nhận được, ma trận cơ sở $B$, xác định tính khả nghịch và tính toán véc-tơ nghiệm cơ sở thông qua biến đổi bảng đơn hình.
    • Phương pháp đơn hình đối ngẫu và tái tối ưu hóa: Sử dụng quan hệ đối ngẫu để tái thiết lập phương án tối ưu sau khi bổ sung thêm ràng buộc mới mà không cần giải lại bài toán từ đầu.
    • Phương pháp phân nhánh và đánh giá cận: Phân hoạch không gian nghiệm của bài toán liên tục tương ứng thành các bài toán con và loại trừ các nhánh không chứa nghiệm tối ưu nguyên.
    • Phương pháp lát cắt giải tích: Thiết lập các bất đẳng thức phụ (mặt cắt Gomory) từ phần thập phân của nghiệm cơ sở chưa nguyên để thu hẹp tập phương án liên tục về phía bao lồi của các điểm nguyên.
  • Nguồn dữ liệu: Các bài toán tối ưu mẫu, hệ phương trình và ma trận hệ số trong không gian số hữu tỷ $\mathbb{Q}^{m \times n}$.

Nội dung chính theo từng chương

Chương I: Một số kiến thức chuẩn bị

Chương I đóng vai trò chuẩn bị công cụ toán học phục vụ việc giải quyết bài toán quy hoạch tuyến tính nguyên ở các chương sau. Tác giả tổng hợp các định lý và thuật toán giải quy hoạch tuyến tính liên tục:

  • Điều kiện tồn tại phương án tối ưu:
    • Định lý 1: Nếu tập phương án chấp nhận được $M \ne \emptyset$ và $M$ bị chặn thì bài toán QHTT có phương án tối ưu.
    • Định lý 2: Nếu $M \ne \emptyset$ thì bài toán có phương án tối ưu khi và chỉ khi hàm mục tiêu $f(x) = \langle c, x \rangle$ bị chặn dưới trên $M$.
  • Thuật toán đơn hình gốc: Xét bài toán dạng chính tắc với ma trận $A \in \mathbb{R}^{m \times n}$ có hạng $\text{rank}(A) = m$. Thuật toán xác định ma trận cơ sở $B$, lập bảng đơn hình, tính các ước lượng kiểm tra tối ưu $\Delta_j = z_j - c_j$. Tiêu chuẩn dừng: nếu $\Delta_j \le 0$ với mọi $j$ thì phương án cơ sở là tối ưu; nếu tồn tại $\Delta_j > 0$ mà mọi hệ số $u_{ij} \le 0$ thì bài toán không có phương án tối ưu (hàm mục tiêu không bị chặn).
  • Thuật toán đơn hình đối ngẫu: Áp dụng khi tìm được cơ sở chấp nhận được đối ngẫu $B$ thỏa mãn $c^T - c_B^T(B^{-1}A) \ge 0$. Bảng đơn hình đối ngẫu cho phép giải bài toán khi véc-tơ vế phải $x_B = B^{-1}b$ có thành phần âm. Nếu mọi $(x_B)_i \ge 0$, phương án là tối ưu. Nếu tồn tại $(x_B)i < 0$ mà mọi $u{ij} \ge 0$ thì bài toán không có phương án chấp nhận được.
  • Kỹ thuật tái tối ưu hóa: Khi bài toán đã có phương án tối ưu $x^$ với cơ sở $B$, nếu bổ sung thêm một ràng buộc mới $\sum_{j=1}^n a_{m+1, j} x_j \le b_{m+1}$ mà $x^$ không thỏa mãn, kỹ thuật này thêm biến bù $x_{n+1} \ge 0$, biến đổi dòng thứ $m+1$ để đưa về bảng đơn hình chấp nhận được đối ngẫu và áp dụng thuật toán đơn hình đối ngẫu giải tiếp, tiết kiệm khối lượng tính toán.
  • Quy đổi dạng chuẩn tắc sang chính tắc: Thêm biến phụ để đưa bài toán chuẩn tắc về chính tắc, giải bài toán chính tắc rồi suy ra kết luận nghiệm cho bài toán chuẩn tắc.

Chương II: Giải bài toán quy hoạch tuyến tính nguyên

Chương II là trọng tâm lý thuyết của khóa luận, đi sâu vào bài toán quy hoạch tuyến tính nguyên toàn phần $(P_0)$ thông qua bài toán quy hoạch tuyến tính nới lỏng $(P)$ tương ứng.

                  Bài toán nguyên (P0)
             Giải bài toán nới lỏng (P)
Nghiệm x* nguyên                        Nghiệm x* chưa nguyên
                        Thuật toán Nhánh Cận          Thuật toán Cắt Gomory
                        (Phân nhánh xr <= [xr]        (Tạo lát cắt Gomory
                         hoặc xr >= [xr] + 1)          từ phần phân số fr)

1. Cơ sở lý luận cơ bản

Tác giả thiết lập và chứng minh 4 mệnh đề nền tảng:

  • Mệnh đề 1: Nếu bài toán nới lỏng $(P)$ không có phương án chấp nhận được ($D = \emptyset$) thì bài toán nguyên $(P_0)$ cũng không có phương án chấp nhận được ($D_0 = \emptyset$).
  • Mệnh đề 2: Nếu bài toán $(P)$ không có phương án tối ưu (tập phương án không bị chặn và hàm mục tiêu không bị chặn dưới) thì $(P_0)$ cũng không có phương án tối ưu.
  • Mệnh đề 3: Nếu bài toán $(P)$ có phương án tối ưu $x^$ thỏa mãn $x^ \in \mathbb{Z}^n$ thì $x^*$ cũng là phương án tối ưu của $(P_0)$.
  • Mệnh đề 4: Nếu bài toán QHTT liên tục có phương án tối ưu trên tập lồi đa diện $M$ thì trên tập con lồi đa diện $M' \subset M$ ($M' \ne \emptyset$), bài toán cũng có phương án tối ưu.

2. Thuật toán nhánh cận (Branch and Bound)

  • Ý tưởng và thuật toán: Giải bài toán liên tục $(P)$. Nếu nghiệm $x^$ có thành phần $x_r^$ chưa nguyên, chọn $x_r^$ và phân nhánh thành hai bài toán con: $(P_1)$ bổ sung ràng buộc $x_r \le [x_r^]$ và $(P_2)$ bổ sung ràng buộc $x_r \ge [x_r^] + 1$. Quá trình duyệt nhánh duy trì kỷ lục cận trên $f^$ cho bài toán cực tiểu, cập nhật cận dưới tại các nút và cắt tỉa các nhánh không triển vọng (khi bài toán con vô nghiệm, khi nghiệm nguyên tìm được có giá trị không tốt hơn $f^$, hoặc khi cận dưới lớn hơn hoặc bằng $f^$).
  • Cơ sở lý luận: Được bảo đảm bởi Mệnh đề 5 (phân hoạch tập phương án $D = D_1 \cup D_2$ với $D_1 \cap D_2 = \emptyset$ khi chia theo phần nguyên $[a]$ và $[a]+1$) và Mệnh đề 6 (tính chất bảo toàn thứ tự giá trị nhỏ nhất trên tập con).
  • Ví dụ minh họa: Giải bài toán $\min f(x) = 3x_1 + x_2$ với các ràng buộc $3x_1 - 2x_2 \le 3$, $-5x_1 - 4x_2 \le -10$, $2x_1 + x_2 \le 5$, $x_1, x_2 \ge 0, x_1, x_2 \in \mathbb{Z}$. Kết quả sau các bước phân nhánh và tái tối ưu hóa xác định được nghiệm tối ưu nguyên là $(x_1, x_2) = (0, 3)$ với giá trị tối ưu $f^* = 3$.

3. Thuật toán cắt Gomory (Gomory's Cutting Plane)

  • Ý tưởng và thiết lập lát cắt: Từ bảng đơn hình tối ưu của bài toán liên tục, nếu phương án $x^$ chưa nguyên, chọn một dòng $r$ có $x_r^$ chưa nguyên. Biểu diễn dòng $r$: $x_r + \sum_{j \notin I} u_{rj} x_j = x_r^$. Tách mỗi hệ số thành phần nguyên và phần phân số: $u_{rj} = [u_{rj}] + f_j$ với $0 \le f_j < 1$, và $x_r^ = [x_r^*] + f_r$ với $0 < f_r < 1$. Lát cắt Gomory được thiết lập dưới dạng: $$\sum_{j \notin I} (-f_j) x_j \le -f_r$$
  • Cơ sở lý luận: Tác giả chứng minh hệ thống 6 mệnh đề khẳng định: (i) Phương án $x^*$ hiện tại không thỏa mãn lát cắt này; (ii) Mọi phương án nguyên chấp nhận được của $(P_0)$ đều thỏa mãn lát cắt; (iii) Bổ sung lát cắt không làm mất nghiệm nguyên tối ưu; (iv) Kỹ thuật tái tối ưu hóa áp dụng trên bảng đơn hình đối ngẫu bảo đảm tính hội tụ.
  • Ví dụ thực nghiệm tính toán: Khóa luận trình bày 3 ví dụ tính toán hoàn chỉnh:
    • Ví dụ 1: Bài toán tối ưu với hàm mục tiêu $-x_1 - 4x_2 \to \min$, ràng buộc $2x_1 + 4x_2 + x_3 = 7$ và $10x_1 + 3x_2 + x_4 = 15$.
    • Ví dụ 2: Bài toán $-x_1 - x_2 \to \min$, xác định nghiệm tối ưu nguyên tại $(1, 2, 1, 3, 0)$ với giá trị tối ưu $-3$.
    • Ví dụ 3: Bài toán $-x_1 - 2x_2 \to \min$ với hệ ràng buộc tài nguyên, tìm lát cắt và giải bằng đơn hình đối ngẫu.

4. Tính hữu hạn của các thuật toán

Tác giả chứng minh định lý về tính dừng: Nếu bài toán quy hoạch tuyến tính liên tục tương ứng có tập phương án chấp nhận được $D$ là tập lồi đa diện và tồn tại phương án tối ưu, thì cả thuật toán nhánh cận và thuật toán cắt Gomory đều kết thúc sau một số hữu hạn bước lặp. Chứng minh dựa trên việc bao bọc tập nghiệm tối ưu trong một hình hộp compact hữu hạn $B \subset \mathbb{R}^n$, trong đó số lượng điểm nguyên $B \cap \mathbb{Z}^n$ là hữu hạn.

Chương III: Ứng dụng của quy hoạch tuyến tính nguyên

Chương III mở rộng lý thuyết sang các bài toán tối ưu rời rạc điển hình trong thực tế. Mỗi bài toán đều được khảo sát theo hai hướng tiếp cận: phương pháp giải tổng quát (nhánh cận, lát cắt Gomory) và phương pháp giải chuyên biệt.

Tên bài toán Đặc điểm mô hình toán học Phương pháp giải chuyên biệt
Bài toán quy hoạch nhị phân Biến quyết định $x_j \in {0, 1}$, đại diện cho quyết định lựa chọn/loại bỏ. Thuật toán cộng Balas (Balas Additive Algorithm): Tìm kiếm cây nhị phân, thử nghiệm các phép gán biến, kiểm tra tính khả thi và cắt tỉa nhánh. Khóa luận phân tích tính hữu hạn, ưu điểm và hạn chế so với nhánh cận/Gomory.
Bài toán cái túi (loại 2) Tối đa hóa tổng giá trị đồ vật đưa vào túi dưới giới hạn dung lượng/trọng lượng $W$. Phương pháp quy hoạch động: Thiết lập phương trình truy toán tối ưu Bellman, giải tuần tự qua các giai đoạn dung lượng.
Bài toán phân việc (Assignment Problem) Phân chia $n$ công việc cho $n$ người thực hiện với ma trận chi phí $C = (c_{ij})$, mỗi người chỉ làm 1 việc. Thuật toán Hungary (Hungarian Algorithm): Biến đổi ma trận chi phí thông qua giảm trừ dòng/cột, tìm hệ phần tử 0 độc lập cực đại để phân công tối ưu.
Bài toán pha cắt vật liệu Cắt phôi nguyên liệu tiêu chuẩn thành các chi tiết nhỏ sao cho tổng lượng phế liệu là nhỏ nhất. Thiết lập mô hình quy hoạch tuyến tính nguyên với các biến là số lượng thanh cắt theo từng sơ đồ.
Bài toán xếp hàng lên tàu Xếp các kiện hàng có khối lượng, thể tích khác nhau lên phương tiện vận tải có tải trọng giới hạn. Mô hình quy hoạch nguyên đa ràng buộc (Multidimensional Knapsack Problem).
Bài toán người du lịch (TSP) Tìm chu trình Hamilton có tổng độ dài ngắn nhất đi qua $n$ thành phố, mỗi thành phố đúng một lần. Mô hình quy hoạch nguyên với ràng buộc loại trừ chu trình con (subtour elimination constraints).

Kết quả và đóng góp

  1. Hệ thống hóa toàn diện phương pháp giải quy hoạch nguyên: Khóa luận đã hệ thống hóa từ lý thuyết liên tục đến các phương pháp rời rạc, thiết lập mối liên hệ giải tích chặt chẽ giữa nghiệm của bài toán nới lỏng liên tục và bài toán nguyên toàn phần.
  2. Chứng minh toán học tường minh: Tác giả đã hoàn thành chứng minh chi tiết các mệnh đề cơ sở cho phương pháp phân nhánh, cấu trúc lát cắt Gomory và đặc biệt là chứng minh tính hữu hạn của thuật toán nhánh cận và thuật toán cắt Gomory trên tập lồi đa diện.
  3. Quy trình hóa thuật toán và thực nghiệm số học: Xây dựng quy trình từng bước kết hợp giữa thuật toán đơn hình đối ngẫu và kỹ thuật tái tối ưu hóa, kèm theo các ví dụ giải chi tiết từng bước trên bảng đơn hình, cho thấy cơ chế loại bỏ nghiệm không nguyên mà không làm mất phương án thực tế.
  4. Tổng hợp đa dạng mô hình ứng dụng: Khóa luận không chỉ dừng lại ở bài toán lý thuyết mà đã đối sánh hiệu quả giữa các thuật toán tổng quát và các thuật toán đặc thù (thuật toán cộng Balas, quy hoạch động, thuật toán Hungary) trên các mô hình kinh tế - vận tải thực tiễn.

Hạn chế và hướng nghiên cứu tiếp

  • Hạn chế:
    • Phạm vi nghiên cứu của đề tài tập trung chủ yếu vào bài toán quy hoạch tuyến tính nguyên toàn phần (Pure Integer Linear Programming), chưa mở rộng chi tiết sang bài toán quy hoạch tuyến tính nguyên hỗn hợp (Mixed Integer Linear Programming - MILP) hoặc bài toán quy hoạch phi tuyến nguyên.
    • Các ví dụ minh họa và thực nghiệm trong luận văn được thực hiện thủ công bằng bảng đơn hình với số chiều nhỏ ($n \le 5$), chưa khảo sát thực nghiệm trên máy tính đối với các bài toán quy mô lớn phát sinh hiện tượng suy biến hoặc bùng nổ tổ hợp.
  • Hướng mở rộng:
    • Mở rộng nghiên cứu thuật toán Gomory hỗn hợp (Mixed Integer Gomory Cut) và phương pháp nhánh và cắt (Branch and Cut) hiện đại.
    • Xây dựng chương trình máy tính cài đặt các thuật toán (Balas, Gomory, Hungary) để thử nghiệm trên tập dữ liệu thực tế quy mô lớn.

Giá trị tham khảo

Khóa luận là tài liệu tham khảo hữu ích cho sinh viên, học viên cao học và giảng viên thuộc các ngành:

  • Toán học, Sư phạm Toán và Toán ứng dụng: Phục vụ học tập và nghiên cứu các học phần Tối ưu hóa, Quy hoạch tuyến tính, Nghiên cứu vận hành (Operations Research).
  • Công nghệ thông tin và Khoa học máy tính: Tham khảo thiết kế thuật toán tổ hợp, phương pháp quy hoạch động, thuật toán Hungary và kỹ thuật duyệt nhánh cận trong tối ưu hóa thuật toán.
  • Kinh tế lượng, Quản lý công nghiệp và Logistics: Tham khảo mô hình hóa các bài toán quản lý sản xuất, xếp dỡ hàng hóa, tối ưu chi phí phân việc và lộ trình vận tải.

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

1. Tại sao không thể giải bài toán quy hoạch nguyên bằng cách giải bài toán liên tục rồi làm tròn số thông thường?
Trong các bài toán quy hoạch nguyên, việc làm tròn số học thuần túy từ nghiệm liên tục $x^*$ thường dẫn đến vi phạm hệ ràng buộc kỹ thuật (phương án không chấp nhận được) hoặc dẫn đến giá trị hàm mục tiêu kém hơn rất nhiều so với nghiệm tối ưu nguyên thực sự. Điều này đặc biệt nghiêm trọng khi các biến quyết định có giá trị nhỏ nhưng ảnh hưởng kinh tế lớn (như sản xuất máy kéo thay vì bi xe đạp).

2. Bản chất toán học của lát cắt Gomory là gì?
Lát cắt Gomory là một bất đẳng thức tuyến tính phụ $\sum_{j \notin I} (-f_j) x_j \le -f_r$ được rút ra từ phần thập phân của nghiệm trên dòng bảng đơn hình chưa nguyên. Bất đẳng thức này có đặc tính: phương án tối ưu liên tục hiện tại $x^*$ không thỏa mãn (bị cắt bỏ), nhưng toàn bộ các phương án nguyên khả thi của bài toán ban đầu đều thỏa mãn (không làm mất nghiệm thực tế).

3. Kỹ thuật tái tối ưu hóa đóng vai trò gì trong việc giải bài toán sau khi thêm lát cắt Gomory hoặc phân nhánh?
Khi thêm một ràng buộc mới (nhánh hoặc lát cắt), phương án tối ưu cũ trở nên không chấp nhận được nhưng cơ sở hiện tại vẫn duy trì tính chấp nhận được đối ngẫu. Kỹ thuật tái tối ưu hóa cho phép chuyển trực tiếp bảng đơn hình hiện tại thành bảng đơn hình đối ngẫu và tiếp tục giải bằng thuật toán đơn hình đối ngẫu mà không cần phải thiết lập lại ma trận và giải từ bước đầu tiên.

4. Thuật toán nào được trình bày chuyên biệt cho bài toán quy hoạch nhị phân (0-1) trong khóa luận?
Khóa luận trình bày Thuật toán cộng Balas (Balas Additive Algorithm). Đây là thuật toán chuyên biệt dựa trên việc duyệt cây tìm kiếm nhị phân, thực hiện các phép cộng đại số đơn giản để kiểm tra tính khả thi của các biến nhận giá trị 0 hoặc 1 mà không cần biến đổi ma trận phức tạp như đơn hình.

5. Điều kiện để thuật toán nhánh cận và thuật toán cắt Gomory kết thúc sau hữu hạn bước là gì?
Hai thuật toán được chứng minh chắc chắn dừng sau một số hữu hạn bước lặp khi tập phương án chấp nhận được của bài toán liên tục tương ứng là tập lồi đa diện bị chặn (compact) và bài toán tồn tại phương án tối ưu, do số lượng điểm nguyên nằm trong tập lồi đa diện bị chặn luôn là một tập hữu hạn.

Kết luận

Khóa luận tốt nghiệp "Nghiên Cứu Quy Hoạch Tuyến Tính Nguyên: Phương Pháp và Ứng Dụng" của tác giả Trịnh Anh Tuấn là một công trình tổng quan và phân tích chuyên sâu về lý thuyết tối ưu hóa rời rạc. Tác giả đã giải quyết trọn vẹn từ cơ sở lý thuyết quy hoạch tuyến tính liên tục, các định lý chứng minh tính đúng đắn và tính hữu hạn của thuật toán nhánh cận, thuật toán cắt Gomory, cho đến việc giải quyết các mô hình ứng dụng kinh tế thực tế như bài toán phân việc, cái túi và quy hoạch nhị phân. Công trình cung cấp hệ thống phương pháp luận toán học chặt chẽ và tường minh, phục vụ hiệu quả cho công tác nghiên cứu, giảng dạy và ứng dụng tối ưu hóa toán học.