Quy hoạch Tuyến tính (Linear Programming)

Đây là một lĩnh vực quan trọng của Vận trù học (Operations Research) và được ứng dụng rộng rãi trong nhiều ngành khác nhau. Các bài toán quy hoạch tuyến tính có thể được tìm thấy trong lĩnh vực kinh tế, hoạch định sản xuất, lập kế hoạch chuỗi cung ứng, tài chính, kỹ thuật và nhiều lĩnh vực khác nơi cần đưa ra các quyết định tối ưu dựa trên các điều kiện cho trước.

Cấu trúc của một bài toán Quy hoạch tuyến tính

Một bài toán quy hoạch tuyến tính (LP) bao gồm ba thành phần chính: các biến quyết định, hàm mục tiêu, và các ràng buộc. Cấu trúc này có thể được biểu diễn dưới nhiều dạng khác nhau, trong đó dạng tổng quát và dạng chuẩn tắc là phổ biến nhất.

1. Dạng tổng quát (General Form)

Đây là dạng biểu diễn linh hoạt nhất của một bài toán LP, bao gồm cả bất phương trình và phương trình.

Tối ưu hóa (Cực đại hóa hoặc Cực tiểu hóa):
Hàm mục tiêu: $Z = c_1x_1 + c_2x_2 + \dots + c_nx_n$

Với các ràng buộc:
$a_{11}x1 + a{12}x2 + \dots + a{1n}x_n \le b1$
$a{21}x1 + a{22}x2 + \dots + a{2n}x_n \le b2$
$\dots$
$a{m1}x1 + a{m2}x2 + \dots + a{mn}x_n \le b_m$

Và ràng buộc không âm:
$x_1, x_2, \dots, x_n \ge 0$

Trong đó:

• $x_1, x_2, \dots, x_n$ là các biến quyết định (decision variables), đại diện cho các đại lượng mà chúng ta cần xác định.
• $c_1, c_2, \dots, c_n$ là các hệ số của hàm mục tiêu, thường biểu thị lợi nhuận hoặc chi phí tương ứng với mỗi đơn vị của biến quyết định.
• $a_{ij}$ là các hệ số kỹ thuật, biểu thị lượng tài nguyên thứ $i$ được tiêu thụ bởi một đơn vị của biến quyết định thứ $j$.
• $b_1, b_2, \dots, b_m$ là các hằng số giới hạn, đại diện cho lượng tài nguyên có sẵn.
• Các ràng buộc có thể là bất phương trình dạng `≤`, `≥` hoặc phương trình `=`. Ràng buộc không âm là một trường hợp đặc biệt nhưng rất phổ biến.

2. Dạng chuẩn tắc (Standard Form)

Nhiều thuật toán giải LP, điển hình là Phương pháp đơn hình (Simplex Method), yêu cầu bài toán phải được đưa về dạng chuẩn tắc. Một bài toán LP ở dạng chuẩn tắc nếu:

1. Mục tiêu là cực đại hóa (hoặc cực tiểu hóa).
2. Tất cả các ràng buộc đều là phương trình (`=`).
3. Tất cả các biến quyết định đều không âm (`≥ 0`).

Ví dụ về dạng chuẩn tắc (cực đại hóa):

Cực đại hóa: $Z = c_1x_1 + c_2x_2 + \dots + c_nx_n$

Với các ràng buộc:
$a_{11}x1 + a{12}x2 + \dots + a{1n}x_n = b1$
$a{21}x1 + a{22}x2 + \dots + a{2n}x_n = b2$
$\dots$
$a{m1}x1 + a{m2}x2 + \dots + a{mn}x_n = b_m$

Và ràng buộc không âm:
$x_j \ge 0$ cho mọi $j=1, \dots, n$
($b_i \ge 0$ cho mọi $i=1, \dots, m$)

Để chuyển từ dạng tổng quát sang dạng chuẩn tắc, người ta thường sử dụng các biến bù (slack variables) hoặc biến thặng dư (surplus variables). Ví dụ, một ràng buộc dạng $a_1x_1 + a_2x_2 \le b$ có thể được chuyển thành phương trình $a_1x_1 + a_2x_2 + s_1 = b$, với $s_1 \ge 0$ là một biến bù.

3. Các khái niệm cơ bản

• Phương án (Solution): Một bộ giá trị cụ thể $(x_1, x_2, \dots, x_n)$ của các biến quyết định.
• Phương án chấp nhận được (Feasible Solution): Một phương án thỏa mãn tất cả các ràng buộc của bài toán.
• Miền chấp nhận được (Feasible Region): Là tập hợp tất cả các phương án chấp nhận được. Về mặt hình học, miền này là một đa diện lồi (convex polytope). Bài toán LP có thể vô nghiệm nếu miền chấp nhận được là rỗng.
• Phương án tối ưu (Optimal Solution): Là một phương án chấp nhận được mà tại đó hàm mục tiêu đạt giá trị lớn nhất (đối với bài toán cực đại hóa) hoặc nhỏ nhất (đối với bài toán cực tiểu hóa). Một bài toán có thể có một, vô số, hoặc không có phương án tối ưu nào. Nếu tồn tại, phương án tối ưu thường nằm tại một hoặc nhiều đỉnh (vertex) của miền chấp nhận được.
• Giá trị tối ưu (Optimal Value): Là giá trị của hàm mục tiêu tại phương án tối ưu.

4. Các phương pháp giải

Có nhiều thuật toán để giải một bài toán quy hoạch tuyến tính. Các phương pháp này khác nhau về hiệu quả tính toán và trường hợp áp dụng.

• Phương pháp đồ thị (Graphical Method): Đây là phương pháp trực quan nhất, tuy nhiên chỉ áp dụng được cho các bài toán có hai biến quyết định. Phương pháp này bao gồm việc vẽ các đường thẳng biểu diễn ràng buộc trên một mặt phẳng tọa độ để xác định miền chấp nhận được (feasible region). Vì phương án tối ưu luôn nằm tại một đỉnh của miền đa giác lồi này, ta chỉ cần tìm tọa độ các đỉnh, tính giá trị hàm mục tiêu tại mỗi đỉnh và chọn ra giá trị tốt nhất.
• Phương pháp đơn hình (Simplex Method): Được phát triển bởi George Dantzig, đây là thuật toán kinh điển và được sử dụng rộng rãi nhất. Thuật toán bắt đầu từ một đỉnh của miền chấp nhận được, sau đó di chuyển lặp đi lặp lại dọc theo các cạnh đến các đỉnh kề cận có giá trị hàm mục tiêu tốt hơn. Quá trình này dừng lại khi không thể tìm thấy đỉnh nào tốt hơn, và đỉnh hiện tại chính là phương án tối ưu. Mặc dù trong trường hợp xấu nhất, hiệu quả tính toán của nó có thể không cao, nhưng trên thực tế, phương pháp đơn hình rất nhanh và hiệu quả cho hầu hết các bài toán.
• Phương pháp điểm trong (Interior-point Method): Không giống như phương pháp đơn hình di chuyển dọc theo biên của miền chấp nhận được, các phương pháp điểm trong đi xuyên qua phần bên trong của miền này. Các thuật toán này, đặc biệt là sau công trình của Narendra Karmarkar vào những năm 1980, đã chứng tỏ hiệu quả vượt trội đối với các bài toán quy mô rất lớn. Đây là các thuật toán có thời gian đa thức (polynomial-time).

5. Ứng dụng

Quy hoạch tuyến tính là một trong những công cụ tối ưu hóa được ứng dụng nhiều nhất trong thực tế, giúp các tổ chức đưa ra quyết định tốt hơn.

• Hoạch định sản xuất và Quản lý chuỗi cung ứng: Các công ty sử dụng LP để quyết định sản xuất mặt hàng nào, với số lượng bao nhiêu để tối đa hóa lợi nhuận, dựa trên các hạn chế về máy móc, nhân công và nguyên vật liệu. Nó cũng được dùng để tối ưu hóa việc phân phối hàng hóa từ nhà máy đến nhà kho và khách hàng (bài toán vận tải).
• Tài chính và Đầu tư: Trong lĩnh vực tài chính, LP giúp xây dựng danh mục đầu tư tối ưu, nhằm tối đa hóa lợi nhuận kỳ vọng với một mức độ rủi ro chấp nhận được, hoặc tối thiểu hóa rủi ro để đạt được một mức lợi nhuận nhất định.
• Vận tải và Logistics: LP được dùng để giải các bài toán tìm đường đi ngắn nhất, lập lịch trình cho các phương tiện (xe tải, máy bay), và tối ưu hóa mạng lưới vận chuyển để giảm thiểu chi phí và thời gian.
• Năng lượng và Viễn thông: Các công ty năng lượng sử dụng LP để lập kế hoạch sản xuất và phân phối điện. Trong viễn thông, nó giúp thiết kế mạng lưới và tối ưu hóa luồng dữ liệu.
• Nông nghiệp: Nông dân có thể sử dụng LP để quyết định trồng cây gì, nuôi con gì và sử dụng loại thức ăn gia súc nào để tối đa hóa doanh thu từ diện tích đất và nguồn lực có hạn.

Quy hoạch tuyến tính là một công cụ mạnh mẽ để giải quyết các bài toán tối ưu hóa trong nhiều lĩnh vực khác nhau.

6. Đối ngẫu trong Quy hoạch tuyến tính (Duality)

Mỗi bài toán quy hoạch tuyến tính (gọi là bài toán gốc – primal problem) đều tồn tại một bài toán LP khác liên quan chặt chẽ, được gọi là bài toán đối ngẫu (dual problem). Lý thuyết đối ngẫu cung cấp những hiểu biết sâu sắc về cấu trúc của bài toán và có ý nghĩa kinh tế quan trọng.

Giả sử bài toán gốc có dạng cực tiểu hóa (dạng đối xứng):

• Bài toán gốc (Primal Problem):
  • Hàm mục tiêu: $min \ Z_P = c^T x$
  • Ràng buộc: $Ax \ge b$, $x \ge 0$
• Bài toán đối ngẫu (Dual Problem):
  • Hàm mục tiêu: $max \ Z_D = b^T y$
  • Ràng buộc: $A^T y \le c$, $y \ge 0$

Trong đó:

• $x$ và $c$ là các vector biến và hệ số của bài toán gốc.
• $y$ và $b$ là các vector biến và hệ số của bài toán đối ngẫu.
• $A$ là ma trận hệ số kỹ thuật, và $A^T$ là ma trận chuyển vị của nó.

Các tính chất quan trọng của cặp bài toán gốc – đối ngẫu:

• Định lý đối ngẫu yếu (Weak Duality Theorem): Đối với mọi phương án chấp nhận được $x$ của bài toán gốc và mọi phương án chấp nhận được $y$ của bài toán đối ngẫu, giá trị hàm mục tiêu của bài toán đối ngẫu luôn nhỏ hơn hoặc bằng giá trị hàm mục tiêu của bài toán gốc: $b^T y \le c^T x$.
• Định lý đối ngẫu mạnh (Strong Duality Theorem): Nếu bài toán gốc có một phương án tối ưu $x^*$, thì bài toán đối ngẫu cũng có một phương án tối ưu $y^*$, và giá trị tối ưu của chúng bằng nhau: $Z_D^* = b^T y^* = c^T x^* = Z_P^*$.
• Ý nghĩa kinh tế: Các biến của bài toán đối ngẫu (thường được gọi là giá bóng – shadow prices) thể hiện sự thay đổi trong giá trị hàm mục tiêu tối ưu khi có một sự thay đổi nhỏ (một đơn vị) trong nguồn lực tương ứng (vế phải $b_i$ của ràng buộc).

7. Bài toán vận tải (Transportation Problem)

Bài toán vận tải là một lớp bài toán quy hoạch tuyến tính đặc biệt, với mục tiêu tìm ra kế hoạch phân phối hàng hóa từ nhiều nguồn cung đến nhiều điểm cầu sao cho tổng chi phí vận chuyển là nhỏ nhất. Do cấu trúc đặc biệt của ma trận ràng buộc, bài toán này có thể được giải quyết bằng các thuật toán hiệu quả hơn nhiều so với phương pháp đơn hình tổng quát.

Mô hình bài toán vận tải cơ bản như sau:

• Các tham số:
  • $m$: số lượng nguồn cung (ví dụ: nhà máy).
  • $n$: số lượng điểm cầu (ví dụ: kho hàng).
  • $s_i$: lượng cung tại nguồn $i$ (với $i=1, \dots, m$).
  • $d_j$: lượng cầu tại điểm $j$ (với $j=1, \dots, n$).
  • $c_{ij}$: chi phí vận chuyển một đơn vị hàng từ nguồn $i$ đến điểm $j$.
• Mô hình toán học:
  • Biến quyết định: $x_{ij}$ là lượng hàng vận chuyển từ nguồn $i$ đến điểm $j$.
  • Hàm mục tiêu (tối thiểu hóa chi phí): $min \ Z = \sum_{i=1}^{m} \sum_{j=1}^{n} c_{ij}x_{ij}$
  • Ràng buộc:
    • Tổng lượng hàng đi từ mỗi nguồn không vượt quá khả năng cung cấp: $\sum_{j=1}^{n} x_{ij} \le s_i$ cho mọi $i=1, \dots, m$.
    • Tổng lượng hàng đến mỗi điểm cầu phải đáp ứng đủ nhu cầu: $\sum_{i=1}^{m} x_{ij} \ge d_j$ cho mọi $j=1, \dots, n$.
    • Ràng buộc không âm: $x_{ij} \ge 0$ cho mọi $i, j$.

Trong trường hợp tổng cung bằng tổng cầu ($\sum s_i = \sum d_j$), bài toán được gọi là bài toán vận tải cân bằng, và các ràng buộc trên trở thành phương trình.

8. Phần mềm giải Quy hoạch tuyến tính

Hiện nay có rất nhiều công cụ phần mềm (solver) mạnh mẽ để giải các bài toán LP, từ các bài toán nhỏ trong giáo dục đến các bài toán quy mô công nghiệp với hàng triệu biến.

• Phần mềm thương mại:
  • CPLEX: Solver của IBM, được coi là một trong những tiêu chuẩn vàng trong ngành về hiệu suất và độ tin cậy.
  • Gurobi: Một đối thủ cạnh tranh mạnh mẽ của CPLEX, nổi tiếng với tốc độ xử lý vượt trội cho nhiều loại bài toán.
  • LINDO/LINGO: Cung cấp một ngôn ngữ mô hình hóa trực quan (LINGO) và một solver mạnh mẽ, rất phổ biến trong giáo dục và nghiên cứu.
• Phần mềm mã nguồn mở:
  • GLPK (GNU Linear Programming Kit): Một bộ công cụ miễn phí, cung cấp một solver đáng tin cậy và một ngôn ngữ mô hình hóa đơn giản, phù hợp cho các ứng dụng không yêu cầu hiệu suất cực cao.
  • LPSolve: Một solver mã nguồn mở lâu đời và phổ biến khác.
• Thư viện và Công cụ tích hợp:
  • Microsoft Excel Solver: Một add-in có sẵn trong Excel, rất tiện lợi để giải các bài toán quy mô nhỏ và vừa, đặc biệt hữu ích cho mục đích giảng dạy và phân tích nhanh.
  • Thư viện Python: Python đã trở thành một công cụ mạnh mẽ cho Vận trù học nhờ các thư viện như SciPy (hàm `linprog`), PuLP và Pyomo (dùng để mô hình hóa bài toán một cách trực quan trước khi gọi các solver bên ngoài như CPLEX, Gurobi, hoặc GLPK).

9. Một số câu hỏi thường gặp

• Câu hỏi: Điều kiện KKT (Karush-Kuhn-Tucker) là gì và vai trò của nó trong quy hoạch tuyến tính?
  Trả lời: Điều kiện KKT là một tập hợp các điều kiện cần và đủ để một phương án là tối ưu trong các bài toán tối ưu hóa phi tuyến có ràng buộc. Đối với trường hợp đặc biệt của Quy hoạch tuyến tính, điều kiện KKT trở nên đơn giản hơn và cung cấp một “chứng chỉ” cho tính tối ưu.
  Đối với cặp bài toán gốc-đối ngẫu (Primal-Dual) đã nêu ở mục 6, điều kiện KKT cho một cặp phương án $(x^*, y^*)$ là tối ưu bao gồm:
  1. Tính khả thi của bài toán gốc: $Ax^* \ge b$, $x^* \ge 0$.
  2. Tính khả thi của bài toán đối ngẫu: $A^T y^* \le c$, $y^* \ge 0$.
  3. Điều kiện bù lỏng lẻo (Complementary Slackness): Điều kiện này liên kết các ràng buộc của bài toán gốc với các biến của bài toán đối ngẫu và ngược lại. Nó phát biểu rằng:
     • $y_i^*( (Ax^*)_i – b_i ) = 0$ cho mỗi ràng buộc $i$ của bài toán gốc. (Nếu một ràng buộc của bài toán gốc không chặt (còn “lỏng”), biến đối ngẫu tương ứng phải bằng 0).
     • $x_j^*( (A^T y^*)_j – c_j ) = 0$ cho mỗi ràng buộc $j$ của bài toán đối ngẫu. (Nếu một biến gốc khác 0, ràng buộc đối ngẫu tương ứng phải chặt (dấu bằng xảy ra)).

  Về cơ bản, điều kiện KKT và định lý đối ngẫu mạnh khẳng định rằng một khi bạn tìm thấy một cặp phương án chấp nhận được $(x^*, y^*)$ thỏa mãn điều kiện bù lỏng lẻo, bạn đã tìm thấy nghiệm tối ưu.

• Câu hỏi: Bài toán Quy hoạch Tuyến tính Nguyên (Integer Linear Programming – ILP) khác gì so với LP thông thường và tại sao nó lại khó giải hơn?
  Trả lời: Trong bài toán ILP, một số hoặc tất cả các biến quyết định bị ràng buộc phải nhận giá trị số nguyên (ví dụ: $x_j \in \mathbb{Z}$). Điều này khác biệt cơ bản so với LP thông thường, nơi các biến có thể nhận bất kỳ giá trị thực nào.

  ILP khó giải hơn rất nhiều (thuộc lớp bài toán NP-hard) vì hai lý do chính:

  1. Miền chấp nhận được không lồi: Miền chấp nhận được của ILP không còn là một đa diện lồi liên tục, mà là một tập hợp các điểm rời rạc nằm bên trong hoặc trên biên của đa diện lồi của bài toán LP tương ứng (bài toán có được bằng cách bỏ đi ràng buộc số nguyên).
  2. Các thuật toán LP không còn áp dụng được trực tiếp: Các thuật toán hiệu quả như phương pháp đơn hình và điểm trong dựa trên tính lồi của miền chấp nhận được. Việc chỉ đơn giản làm tròn nghiệm của bài toán LP thường không cho ra nghiệm tối ưu, thậm chí có thể không phải là một phương án chấp nhận được của bài toán ILP. Do đó, các thuật toán cho ILP phức tạp hơn nhiều, thường dựa trên các kỹ thuật như Nhánh và Cận (Branch and Bound) hoặc Mặt phẳng cắt (Cutting Plane).
• Câu hỏi: Làm thế nào để mô hình hóa một vấn đề thực tế thành bài toán quy hoạch tuyến tính?
  Trả lời: Quá trình mô hình hóa một vấn đề thực tế thành bài toán LP bao gồm các bước cốt lõi sau:
  1. Bước 1: Xác định các Biến quyết định. Đây là những đại lượng có thể kiểm soát được và cần phải tìm giá trị của chúng. Ví dụ: số lượng sản phẩm A và B cần sản xuất. Đặt tên cho chúng, ví dụ: $x_A, x_B$.
  2. Bước 2: Xây dựng Hàm mục tiêu. Xác định mục tiêu của bài toán là gì (tối đa hóa lợi nhuận, tối thiểu hóa chi phí, v.v.). Biểu diễn mục tiêu này dưới dạng một hàm tuyến tính của các biến quyết định. Ví dụ: Tối đa hóa Lợi nhuận = $50x_A + 60x_B$.
  3. Bước 3: Thiết lập các Ràng buộc. Xác định tất cả các giới hạn, hạn chế hoặc yêu cầu của vấn đề. Đây có thể là giới hạn về tài nguyên (nguyên vật liệu, thời gian máy, nhân công) hoặc các yêu cầu sản xuất. Biểu diễn mỗi ràng buộc dưới dạng một phương trình hoặc bất phương trình tuyến tính. Ví dụ: Thời gian máy móc: $2x_A + 3x_B \le 120$ giờ.
  4. Bước 4: Thêm các Ràng buộc mặc định. Thông thường, các biến quyết định phải không âm (ví dụ: không thể sản xuất số lượng sản phẩm âm). Thêm các ràng buộc như $x_A \ge 0, x_B \ge 0$.
  5. Bước 5: Kiểm tra và Rà soát. Đọc lại toàn bộ mô hình (hàm mục tiêu và tất cả các ràng buộc) để đảm bảo nó phản ánh chính xác vấn đề thực tế và tất cả các giả định (như tính tuyến tính, tính cộng được) là hợp lý.