Quy hoạch tuyến tính: Giải các bài toán tối ưu trong thế giới thực

Các nhà quản lý vận hành thường đối mặt với một thách thức lặp đi lặp lại: quá nhiều quyết định, quá nhiều ràng buộc và không có cách hiển nhiên để tìm lời giải tốt nhất. Một mạng lưới phân phối cần tối thiểu hóa chi phí nhiên liệu trên hàng chục tuyến đường đồng thời tuân thủ khung giờ giao hàng, sức chứa phương tiện và lịch trình tài xế.

Hai vấn đề này có chung một cấu trúc toán học. Khi mục tiêu và các ràng buộc có thể biểu diễn dưới dạng quan hệ tuyến tính, bạn đang làm việc với một bài toán quy hoạch tuyến tính. Chúng ta quan tâm đến quy hoạch tuyến tính vì nó tìm được nghiệm tối ưu khi bạn làm việc với nguồn lực hạn chế và yêu cầu cạnh tranh.

Điều làm quy hoạch tuyến tính trở nên mạnh mẽ là sự đảm bảo của nó: nếu tồn tại nghiệm khả thi, thuật toán sẽ tìm được nghiệm tối ưu. Tất nhiên, các ứng dụng thực tế hiếm khi khớp hoàn hảo với ví dụ trong sách giáo khoa, nhưng hiểu được khung cốt lõi giúp bạn nhận ra khi nào tối ưu hóa có thể thay thế việc phán đoán cảm tính.

Hướng dẫn này đưa bạn đi từ nền tảng đến các triển khai Python hoạt động thực tế. Chúng ta sẽ tiến từ các bài toán hai biến đơn giản có thể trực quan hóa hình học đến những kịch bản phức tạp cần lời giải thuật toán. Bạn sẽ hiểu cả lý thuyết toán học làm nền tảng cho tối ưu hóa và kỹ năng thực hành để tự triển khai lời giải.

Quy hoạch tuyến tính là gì?

Quy hoạch tuyến tính tối ưu hóa một hàm mục tiêu tuyến tính dưới các ràng buộc tuyến tính. Trong một dự án định tuyến phân phối tôi từng làm, mục tiêu là tối thiểu hóa tổng quãng đường lái xe đồng thời tuân thủ các ràng buộc như sức chứa phương tiện và khung giờ giao hàng.

Hiểu cấu trúc cơ bản

Mọi bài toán quy hoạch tuyến tính có ba thành phần: biến quyết định, hàm mục tiêu và các ràng buộc.

Biến quyết định đại diện cho các lựa chọn bạn đưa ra. Trong các bài toán định tuyến, biến nhị phân có thể biểu thị xe nào ghé địa điểm nào. Trong lập kế hoạch sản xuất, biến có thể biểu diễn số lượng sản xuất.

Hàm mục tiêu xác định điều bạn đang tối ưu hóa. Nó phải là tổ hợp tuyến tính của các biến quyết định. Các ràng buộc xác định quy tắc và giới hạn của bài toán. Chúng có ba dạng: đẳng thức, bất đẳng thức nhỏ hơn hoặc bằng, hoặc lớn hơn hoặc bằng.

from scipy.optimize import linprog

c = [10, 15]
A_ub = [[1, 0], [0, 1]]
b_ub = [100, 80]
A_eq = [[1, 1]]
b_eq = [150]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, 
                 bounds=bounds, method='highs')

print(f"Optimal solution: Truck 1 = {result.x[0]:.1f}, Truck 2 = {result.x[1]:.1f}")
print(f"Total cost: ${result.fun:.2f}")Được hỗ trợ bởi

Đoạn mã trên tối thiểu hóa tổng chi phí cho hai biến quyết định, với các giới hạn riêng lẻ và yêu cầu bao phủ tổng. Hệ số mục tiêu [10, 15] biểu thị chi phí mỗi đơn vị, các ràng buộc bất đẳng thức giới hạn phạm vi của từng biến, và ràng buộc đẳng thức đảm bảo bao phủ tổng.

Diễn giải hình học

Hiểu quy hoạch tuyến tính dưới góc nhìn hình học đã thay đổi cách tôi nghĩ về tối ưu hóa. Mỗi ràng buộc xác định một nửa không gian, và giao của chúng tạo thành miền khả thi. Miền này luôn là một đa diện lồi, nghĩa là bất kỳ đoạn thẳng nào nối hai điểm bên trong đều nằm bên trong.

Điều then chốt là: nghiệm tối ưu luôn nằm ở các đỉnh của miền khả thi. Di chuyển dọc theo một cạnh sẽ hoặc cải thiện mục tiêu hoặc không, nên bạn tiếp tục di chuyển cho đến khi chạm một góc. Tính chất này giúp các thuật toán quy hoạch tuyến tính hiệu quả.

import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(0, 8, 400)
y1 = (10 - x) / 2
y2 = 12 - 2*x

plt.figure(figsize=(10, 8))
plt.plot(x, y1, 'r-', label='x + 2y ≤ 10', linewidth=2)
plt.plot(x, y2, 'b-', label='2x + y ≤ 12', linewidth=2)

y_feasible = np.minimum(y1, y2)
y_feasible = np.maximum(y_feasible, 0)
plt.fill_between(x, 0, y_feasible, where=(y_feasible >= 0), 
                 alpha=0.3, color='green', label='Feasible region')

vertices = [(0, 0), (0, 5), (14/3, 8/3), (6, 0)]
for v in vertices:
    plt.plot(v[0], v[1], 'ko', markersize=10)
    obj_value = 3*v[0] + 4*v[1]
    plt.annotate(f'({v[0]:.1f}, {v[1]:.1f})\nObj: {obj_value:.1f}',
                 xy=v, xytext=(v[0]+0.3, v[1]+0.3))

plt.xlim(-0.5, 8)
plt.ylim(-0.5, 8)
plt.xlabel('x')
plt.ylabel('y')
plt.legend()
plt.grid(True, alpha=0.3)
plt.title('Geometric View: Optimal Solution at Vertex (4.7, 2.7)')
plt.show()Được hỗ trợ bởi

Hình trực quan này cho thấy nghiệm tối ưu tại đỉnh (4,7; 2,7) nơi hai ràng buộc giao nhau. Miền khả thi lồi đảm bảo không có “thung lũng ẩn” nơi thuật toán có thể mắc kẹt, nhờ đó cực trị địa phương trùng với cực trị toàn cục.

Chuyển hóa bài toán thực tế

Phần khó nhất không phải giải toán mà là chuyển các vấn đề lộn xộn thành các mô hình gọn gàng. Việc xác định biến và ràng buộc thường tốn nhiều thời gian hơn chính quá trình chạy tối ưu hóa.

Xác định biến quyết định đòi hỏi nhận diện các lựa chọn cốt lõi. Với định tuyến, bạn có thể dùng biến nhị phân cho việc gán phương tiện-địa điểm, hoặc thêm biến liên tục cho thứ tự ghé thăm để đơn giản hóa ràng buộc.

Xây dựng ràng buộc nghĩa là chuyển quy tắc nghiệp vụ thành các bất đẳng thức. Điều này làm lộ các giả định ẩn. Khi một quản lý nói "mỗi địa điểm cần một lần giao hàng", điều đó là đúng một lần hay ít nhất một lần? Những chi tiết này thay đổi hoàn toàn cách mô hình hóa.

Dưới đây là một ví dụ mô hình hóa bằng PuLP:

from pulp import *

prob = LpProblem("Food_Bank_Routing", LpMinimize)

trucks = ['Truck_A', 'Truck_B', 'Truck_C']
centers = ['North', 'South', 'East', 'West', 'Central']

x = LpVariable.dicts("route", 
                     [(i, j) for i in trucks for j in centers],
                     cat='Binary')

distances = {
    ('Truck_A', 'North'): 15, ('Truck_A', 'South'): 20,
    ('Truck_A', 'East'): 10, ('Truck_A', 'West'): 25,
    ('Truck_A', 'Central'): 5,
    ('Truck_B', 'North'): 18, ('Truck_B', 'South'): 15,
    ('Truck_B', 'East'): 12, ('Truck_B', 'West'): 22,
    ('Truck_B', 'Central'): 8,
    ('Truck_C', 'North'): 20, ('Truck_C', 'South'): 25,
    ('Truck_C', 'East'): 15, ('Truck_C', 'West'): 18,
    ('Truck_C', 'Central'): 10,
}

prob += lpSum([distances[i, j] * x[i, j] 
               for i in trucks for j in centers])

for j in centers:
    prob += lpSum([x[i, j] for i in trucks]) == 1

max_stops = {'Truck_A': 3, 'Truck_B': 2, 'Truck_C': 3}
for i in trucks:
    prob += lpSum([x[i, j] for j in centers]) <= max_stops[i]

prob.solve()

print(f"Status: {LpStatus[prob.status]}")
print(f"Total distance: {value(prob.objective)} miles")
for i in trucks:
    route = [j for j in centers if value(x[i, j]) == 1]
    print(f"{i} visits: {', '.join(route)}")Được hỗ trợ bởi

Mô hình trên dùng biến nhị phân cho việc gán xe-trung tâm, tối thiểu hóa tổng quãng đường, đảm bảo mỗi trung tâm nhận đúng một lần giao, và tuân thủ giới hạn sức chứa của xe.

Các mẫu bài toán kinh điển cung cấp khuôn mẫu. Bài toán khẩu phần ăn tối thiểu hóa chi phí trong khi đáp ứng yêu cầu dinh dưỡng. Bài toán vận tải tối thiểu hóa chi phí vận chuyển. Ví dụ này áp dụng trực tiếp cho thách thức định tuyến của tôi. Nhận diện các mẫu này giúp tăng tốc mô hình hóa vì bạn hiếm khi giải các bài toán thực sự mới hoàn toàn.

Quy hoạch tuyến tính tìm nghiệm tối ưu tại các đỉnh của miền khả thi được xác định bởi các ràng buộc. Ảnh: Tác giả

Phương pháp giải và cách tiếp cận thuật toán

Hiểu cách các thuật toán hoạt động đã thay đổi cách tôi trân trọng việc gọi linprog(). Đây không phải hộp đen mà là những quy trình toán học tao nhã.

Thuật toán đơn hình (Simplex)

Thuật toán simplex, do George Dantzig phát triển năm 1947, là điểm khởi đầu. Ý tưởng của nó: di chuyển có hệ thống từ đỉnh này sang đỉnh kề, luôn cải thiện mục tiêu, cho đến khi đạt nghiệm tối ưu.

Thuật toán duy trì một bảng (tableau) và thực hiện các phép quay trục (pivot) để di chuyển giữa các đỉnh. Mỗi vòng lặp cải thiện mục tiêu hoặc xác định tối ưu bằng cách chọn phần tử pivot và cập nhật qua các phép biến đổi hàng.

from scipy.optimize import linprog
import numpy as np

c = [-3, -2]
A_ub = [[2, 1], [2, 3], [3, 1]]
b_ub = [18, 42, 24]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

print(f"Optimal solution: x1 = {result.x[0]:.2f}, x2 = {result.x[1]:.2f}")
print(f"Maximum value: {-result.fun:.2f}")
print(f"Iterations: {result.nit}")Được hỗ trợ bởi

Đoạn mã trên minh họa cách giải một bài toán tối đa hóa bằng phương pháp simplex bằng cách đổi dấu các hệ số mục tiêu. Bộ giải di chuyển có hệ thống giữa các đỉnh của miền khả thi do các ràng buộc xác định, đạt nghiệm tối ưu chỉ sau vài vòng lặp. Với bài toán lớn hơn, phương pháp simplex có thể tìm tối ưu với số bước ít hơn rất nhiều so với số đỉnh khả thi, thường dưới 20 vòng lặp ngay cả khi có hàng nghìn khả năng.

Phương pháp điểm trong (Interior-point)

Trong khi simplex đi dọc biên, các phương pháp điểm trong di chuyển bên trong miền khả thi. Với các bài toán tối ưu danh mục lớn có hàng trăm tài sản, simplex có thể chậm chạp trong khi phương pháp điểm trong giải trong vài giây.

Lợi thế then chốt là độ phức tạp đa thức. Thuật toán của Karmarkar (1984) đã khiến phương pháp điểm trong trở nên thực tiễn, cân bằng giữa cải thiện mục tiêu và giữ khoảng cách với biên ràng buộc. Các bộ giải hiện đại như Gurobi tự động chọn giữa simplex và điểm trong dựa trên đặc trưng bài toán.

Phương pháp đồ thị cho bài toán hai biến

Với bài toán hai biến, tôi luôn giải đồ thị trước. Điều này xây dựng trực giác có thể chuyển sang không gian nhiều chiều hơn. Vẽ ràng buộc, xác định miền khả thi và tìm đỉnh nào tối ưu hóa mục tiêu.

from scipy.optimize import linprog

c = [-30, -40]
A_ub = [[2, 1], [1, 2]]
b_ub = [100, 80]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

print(f"Bread loaves: {result.x[0]:.0f}")
print(f"Cakes: {result.x[1]:.0f}")
print(f"Maximum profit: ${-result.fun:.0f}")Được hỗ trợ bởi

Bài toán sản xuất bánh mì này tối đa hóa lợi nhuận từ bánh mì và bánh ngọt, với ràng buộc giờ lò nướng và trang trí. Lời giải cho thấy điểm góc nào là tối ưu dưới góc nhìn hình học, giúp hành vi “nhảy giữa các đỉnh” của thuật toán trở nên cụ thể.

Ứng dụng trong nhiều ngành

Quy hoạch tuyến tính áp dụng cùng một khuôn khổ toán học để giải các vấn đề ở những lĩnh vực rất khác nhau.

Sản xuất và vận hành

Lập kế hoạch sản xuất là ứng dụng nghiêm túc đầu tiên của tôi. Bài toán phối thức sản xuất xác định số lượng chế tạo, với biến đại diện sản lượng, mục tiêu tối đa hóa lợi nhuận và ràng buộc phản ánh giới hạn nguồn lực.

from pulp import *

products = ['Phone', 'Tablet', 'Laptop']

profits = {'Phone': 120, 'Tablet': 200, 'Laptop': 350}
assembly_time = {'Phone': 2, 'Tablet': 3, 'Laptop': 5}
testing_time = {'Phone': 1, 'Tablet': 1.5, 'Laptop': 2}

assembly_available = 500
testing_available = 200
min_production = {'Phone': 50, 'Tablet': 30, 'Laptop': 20}

model = LpProblem("Production_Planning", LpMaximize)
production = LpVariable.dicts("produce", products, lowBound=0, cat='Integer')

model += lpSum([profits[p] * production[p] for p in products])
model += lpSum([assembly_time[p] * production[p] for p in products]) <= assembly_available
model += lpSum([testing_time[p] * production[p] for p in products]) <= testing_available

for p in products:
    model += production[p] >= min_production[p]

model.solve()

print(f"Status: {LpStatus[model.status]}")
for p in products:
    print(f"{p}: {production[p].varValue:.0f} units")
print(f"Total profit: ${value(model.objective):,.0f}")Được hỗ trợ bởi

Mô hình trên tối ưu hóa sản xuất điện tử trên ba dòng sản phẩm, cân bằng năng lực lắp ráp và kiểm thử với yêu cầu sản lượng tối thiểu.

Các bài toán pha trộn tối ưu hóa hỗn hợp đáp ứng tiêu chuẩn với chi phí tối thiểu, như pha trộn thực phẩm để đáp ứng yêu cầu dinh dưỡng trong khi giảm chi phí.

Vận tải và logistics

Bài toán vận tải là một ví dụ được nghiên cứu kỹ. Cấu trúc kinh điển có nguồn cung tại các điểm xuất và nhu cầu tại các điểm đến, tối thiểu hóa tổng chi phí vận chuyển.

warehouses = ['Warehouse_A', 'Warehouse_B', 'Warehouse_C']
supply = {'Warehouse_A': 300, 'Warehouse_B': 400, 'Warehouse_C': 200}

customers = ['Customer_1', 'Customer_2', 'Customer_3', 'Customer_4']
demand = {'Customer_1': 200, 'Customer_2': 150, 'Customer_3': 250, 'Customer_4': 200}

costs = {
    ('Warehouse_A', 'Customer_1'): 8,  ('Warehouse_A', 'Customer_2'): 6,
    ('Warehouse_A', 'Customer_3'): 10, ('Warehouse_A', 'Customer_4'): 7,
    ('Warehouse_B', 'Customer_1'): 9,  ('Warehouse_B', 'Customer_2'): 12,
    ('Warehouse_B', 'Customer_3'): 8,  ('Warehouse_B', 'Customer_4'): 11,
    ('Warehouse_C', 'Customer_1'): 14, ('Warehouse_C', 'Customer_2'): 7,
    ('Warehouse_C', 'Customer_3'): 10, ('Warehouse_C', 'Customer_4'): 12,
}

model = LpProblem("Transportation", LpMinimize)

routes = [(w, c) for w in warehouses for c in customers]
shipments = LpVariable.dicts("ship", routes, lowBound=0)

model += lpSum([costs[i, j] * shipments[i, j] for (i, j) in routes])

for w in warehouses:
    model += lpSum([shipments[w, c] for c in customers]) <= supply[w]

for c in customers:
    model += lpSum([shipments[w, c] for w in warehouses]) >= demand[c]

model.solve()Được hỗ trợ bởi

Các bài toán dòng chảy trên mạng tổng quát hóa vận tải lên đồ thị với các nút trung chuyển. Tôi từng đọc rằng các hãng hàng không sử dụng rộng rãi điều này cho lập lịch phi hành đoàn và định tuyến máy bay.

Dịch vụ tài chính và chăm sóc sức khỏe

Trong tài chính, phân bổ vốn chọn các dự án tối đa hóa lợi nhuận dưới ràng buộc ngân sách:

projects = {
    'Project_A': {'return': 25000, 'cost': 100000, 'staff': 5},
    'Project_B': {'return': 30000, 'cost': 150000, 'staff': 7},
    'Project_C': {'return': 20000, 'cost': 80000, 'staff': 4},
}

budget = 300000
staff_available = 15

model = LpProblem("Capital_Budgeting", LpMaximize)
select = LpVariable.dicts("select", projects.keys(), cat='Binary')

model += lpSum([projects[p]['return'] * select[p] for p in projects])
model += lpSum([projects[p]['cost'] * select[p] for p in projects]) <= budget
model += lpSum([projects[p]['staff'] * select[p] for p in projects]) <= staff_available

model.solve()Được hỗ trợ bởi

Hệ thống y tế đối mặt với vô vàn thách thức tối ưu hóa. Tôi từng tư vấn một bài toán lập lịch phòng khám, phân công y tá vào ca trực đồng thời tuân thủ yêu cầu kỹ năng và cân bằng khối lượng công việc.

Ứng dụng công nghệ hiện đại

Quy hoạch tuyến tính cũng xuất hiện một cách bất ngờ trong machine learning. Chọn đặc trưng có thể mô hình hóa thành tối thiểu hóa lỗi dự đoán dưới các ràng buộc độ thưa. Điện toán đám mây dùng nó để phân bổ tài nguyên trong hệ thống phân tán.

Độ phức tạp tính toán và hiệu năng

Độ phức tạp rất quan trọng khi bài toán mở rộng từ ví dụ nhỏ đến hệ thống sản xuất.

Độ phức tạp của thuật toán simplex

Simplex có mức độ phức tạp thú vị. Trường hợp xấu nhất là hàm mũ nhưng hiệu năng trung bình lại rất tốt. Các trường hợp bệnh lý như khối lập phương Klee-Minty buộc nó duyệt mọi đỉnh, nhưng bài toán điển hình chỉ duyệt một phần nhỏ, tỷ lệ xấp xỉ bậc hai.

Tôi đã kiểm chứng bằng cách giải các bài toán ngẫu nhiên với kích thước tăng dần:

import time
import numpy as np
from scipy.optimize import linprog

def benchmark_simplex(num_vars, num_constraints):
    c = np.random.randn(num_vars)
    A_ub = np.random.randn(num_constraints, num_vars)
    b_ub = np.random.rand(num_constraints) * 10
    
    start = time.time()
    result = linprog(c, A_ub=A_ub, b_ub=b_ub, method='simplex')
    elapsed = time.time() - start
    
    return elapsed, result.nit

problem_sizes = [(10, 20), (50, 100), (100, 200), (200, 400)]

for n_vars, n_const in problem_sizes:
    times, iterations = [], []
    for _ in range(10):
        t, it = benchmark_simplex(n_vars, n_const)
        times.append(t)
        iterations.append(it)
    print(f"{n_vars}x{n_const}: {np.mean(times):.4f}s, {np.mean(iterations):.1f} iterations")Được hỗ trợ bởi

Kết quả cho thấy khi tăng gấp đôi kích thước bài toán, thời gian tăng ít hơn 4 lần, xác nhận hành vi gần đa thức với các phân phối điển hình.

Cải thiện hiệu năng

Các bộ giải hiện đại đạt hiệu năng ấn tượng nhờ tiền xử lý, xử lý song song và chọn thuật toán tự động. Tiền xử lý có thể giảm kích thước bài toán 30% hoặc hơn một cách tự động trước khi giải.

Suy biến xảy ra khi nhiều ràng buộc cùng chặt tại nghiệm tối ưu, có thể gây lặp vòng. Tôi từng gặp khi hai tuyến đường có chi phí giống hệt. Các bộ giải dùng kỹ thuật nhiễu nhỏ để tránh lặp vòng, dù bài toán suy biến sẽ giải chậm hơn.

Bất ổn số xảy ra với các bài toán tỉ lệ kém. Việc trộn lẫn giá trị tiền tệ (hàng nghìn đô) với số lượng (đơn vị lẻ) đã gây cảnh báo. Chuẩn hóa lại tỉ lệ đã khắc phục ngay lập tức.

So sánh hiệu năng bộ giải: giải pháp thương mại vượt trội ở các bài toán quy mô lớn. Ảnh: Tác giả

Công cụ phần mềm và triển khai

Lựa chọn công cụ ảnh hưởng lớn đến năng suất. Tôi đã chuyển từ tự viết simplex sang dùng các bộ giải chuyên nghiệp xử lý những bài toán lớn hơn rất nhiều.

Bộ giải thương mại và ngôn ngữ mô hình hóa

CPLEX và Gurobi thống lĩnh tối ưu hóa công nghiệp, cho hiệu năng tốt hơn bậc độ lớn so với nguồn mở ở các bài toán lớn. Tôi dùng giấy phép học thuật của Gurobi cho công việc chuỗi cung ứng. Những bài toán mất vài phút với SciPy được giải trong vài giây.

PuLP là lựa chọn Python ưa thích của tôi. Nó cung cấp API gọn để mô hình hóa chạy với nhiều backend:

from pulp import *

model = LpProblem("my_problem", LpMaximize)

x = LpVariable("x", lowBound=0)
y = LpVariable("y", lowBound=0)

model += 3*x + 2*y
model += x + y <= 100
model += 2*x + y <= 150

model.solve()

print(f"Used solver: {model.solver}")
print(f"Status: {LpStatus[model.status]}")Được hỗ trợ bởi

Lớp trừu tượng này cho phép mã độc lập bộ giải chạy trên các hệ thống khác nhau. Pyomo cung cấp nhiều tính năng nâng cao cho tối ưu hóa phức tạp, gồm cả phi tuyến và ngẫu nhiên.

Đám mây và lựa chọn nguồn mở

Nền tảng đám mây cung cấp tối ưu hóa như một dịch vụ cho các bài toán lớn không thường xuyên. Bạn tải dữ liệu bài toán lên và nhận lời giải qua API. Kiến trúc không máy chủ rất gọn dù chậm hơn so với bộ giải cục bộ cho bài toán nhỏ.

GLPK (GNU Linear Programming Kit) là “ngựa thồ” nguồn mở đáng tin cậy. Tôi dùng nó cho giảng dạy và dự án cá nhân. HiGHS là bộ giải mới cho hiệu năng ấn tượng. SciPy gần đây đã chọn HiGHS làm backend mặc định, và các chuẩn đo của tôi cho thấy nó sánh ngang Gurobi trong nhiều bài toán.

Ví dụ về quy hoạch tuyến tính

Làm việc qua các ví dụ hoàn chỉnh giúp hiểu tốt hơn là chỉ có lý thuyết.

Ví dụ 1: Bài toán khẩu phần ăn

Bài toán khẩu phần ăn kinh điển tối thiểu hóa chi phí trong khi đáp ứng yêu cầu dinh dưỡng:

from pulp import *

foods = {
    'Oatmeal': {'cost': 0.50, 'calories': 110, 'protein': 4, 'vitamin': 2},
    'Chicken': {'cost': 2.50, 'calories': 250, 'protein': 30, 'vitamin': 0},
    'Eggs':    {'cost': 0.80, 'calories': 155, 'protein': 13, 'vitamin': 1},
    'Milk':    {'cost': 1.20, 'calories': 150, 'protein': 8, 'vitamin': 4},
    'Bread':   {'cost': 0.30, 'calories': 80, 'protein': 3, 'vitamin': 0}
}

min_calories, min_protein, min_vitamin = 2000, 50, 10

model = LpProblem("Diet_Optimization", LpMinimize)
servings = LpVariable.dicts("servings", foods.keys(), lowBound=0)

model += lpSum([foods[f]['cost'] * servings[f] for f in foods])
model += lpSum([foods[f]['calories'] * servings[f] for f in foods]) >= min_calories
model += lpSum([foods[f]['protein'] * servings[f] for f in foods]) >= min_protein
model += lpSum([foods[f]['vitamin'] * servings[f] for f in foods]) >= min_vitamin

model.solve()

print(f"Total cost: ${value(model.objective):.2f}")
for food in foods:
    if servings[food].varValue > 0.01:
        print(f"{food}: {servings[food].varValue:.2f} servings")Được hỗ trợ bởi

Mô hình trên tìm tổ hợp thực phẩm rẻ nhất đáp ứng nhu cầu dinh dưỡng hằng ngày. Điều này cho thấy nghiệm LP tối ưu không phải lúc nào cũng thực tiễn nếu thiếu các ràng buộc bổ sung về đa dạng, khẩu vị, hoặc sở thích ăn uống.

Cùng khung này cũng có thể là nền tảng cho quyết định kinh doanh như tối ưu lịch sản xuất hoặc phân bổ ngân sách marketing.

Ví dụ 2: Hoạch định đa kỳ

Hoạch định đa kỳ xét cách mức tồn kho ảnh hưởng đến nhu cầu tương lai qua nhiều giai đoạn thời gian:

days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday']

centers = {
    'North': {'daily_demand': [100, 80, 90, 110, 85], 'capacity': 250},
    'South': {'daily_demand': [120, 100, 95, 105, 130], 'capacity': 300},
}

delivery_cost = {'Monday': 50, 'Tuesday': 50, 'Wednesday': 50,
                 'Thursday': 50, 'Friday': 70}

model = LpProblem("Multiperiod_Routing", LpMinimize)

deliveries = LpVariable.dicts("deliver",
                              [(c, d) for c in centers for d in days],
                              lowBound=0)
inventory = LpVariable.dicts("inventory",
                            [(c, d) for c in centers for d in days],
                            lowBound=0)

model += lpSum([delivery_cost[d] * deliveries[c, d] 
                for c in centers for d in days])

for c in centers:
    for i, day in enumerate(days):
        if i == 0:
            model += inventory[c, day] == deliveries[c, day] - centers[c]['daily_demand'][i]
        else:
            prev_day = days[i-1]
            model += (inventory[c, day] == inventory[c, prev_day] + 
                     deliveries[c, day] - centers[c]['daily_demand'][i])
        model += inventory[c, day] <= centers[c]['capacity']

model.solve()Được hỗ trợ bởi

Mô hình đa kỳ làm tăng kích thước bài toán nhưng mở khóa tối ưu hóa tinh vi. Mô hình gom các lần giao vào ngày rẻ hơn, tận dụng sức chứa kho để giảm tổng chi phí.

Quy hoạch nguyên hỗn hợp (MIP)

Nhiều bài toán liên quan đến quyết định rời rạc: xây hay không xây một cơ sở, phân công hay không phân công một nhân sự. Điều này cần quy hoạch nguyên hỗn hợp, mở rộng quy hoạch tuyến tính với biến nguyên và nhị phân.

Giới thiệu và phân nhánh - cận (branch-and-bound)

Các bài toán định tuyến cần quyết định dạng nguyên. Biến nhị phân x[i][j] cho biết liệu phương tiện i có ghé địa điểm j hay không. Phương tiện không thể ghé theo kiểu phân số.

Branch-and-bound tìm kiếm có hệ thống trong không gian nghiệm rời rạc bằng cách giải các bài toán LP thư giãn liên tục:

from pulp import *

model_continuous = LpProblem("Continuous", LpMaximize)
x_cont = LpVariable("x", lowBound=0)
y_cont = LpVariable("y", lowBound=0)

model_continuous += 3*x_cont + 4*y_cont
model_continuous += x_cont + 2*y_cont <= 10
model_continuous += 2*x_cont + y_cont <= 12

model_continuous.solve()
print(f"Continuous: x={x_cont.varValue:.2f}, y={y_cont.varValue:.2f}")

model_integer = LpProblem("Integer", LpMaximize)
x_int = LpVariable("x", lowBound=0, cat='Integer')
y_int = LpVariable("y", lowBound=0, cat='Integer')

model_integer += 3*x_int + 4*y_int
model_integer += x_int + 2*y_int <= 10
model_integer += 2*x_int + y_int <= 12

model_integer.solve()
print(f"Integer: x={x_int.varValue:.0f}, y={y_int.varValue:.0f}")Được hỗ trợ bởi

Nghiệm nguyên khác với việc làm tròn nghiệm liên tục. Branch-and-bound tìm nghiệm nguyên tối ưu, nhưng với chi phí tính toán cao hơn đáng kể.

Khi nào dùng quy hoạch nguyên

Dùng biến nguyên khi quyết định vốn dĩ là rời rạc: mở cơ sở, phân công nhân sự, định tuyến phương tiện nơi hoặc là ghé hoặc là không. Tối ưu hóa trên thị trường trái phiếu thường cần nghiệm nguyên hỗn hợp. Biến liên tục có thể tạo ra các phương án phân số vô nghĩa, trong khi biến nhị phân cho lời giải có thể triển khai.

Tuy nhiên, quy hoạch nguyên tốn kém hơn rất nhiều. Các bài toán với hàng trăm biến nguyên có thể mất hàng giờ, so với vài giây cho LP liên tục. Nếu số lượng sản xuất lớn, tính nguyên ít quan trọng hơn vì làm tròn hầu như không ảnh hưởng đến lời giải. Luôn giải bài toán thư giãn liên tục trước để kiểm tra cận trước khi theo đuổi mô hình nguyên đầy đủ.

Kết luận

Quy hoạch tuyến tính thay đổi cách bạn tiếp cận các bài toán tối ưu. Cùng một khuôn khổ toán học áp dụng cho những lĩnh vực rất khác nhau, từ định tuyến đến lập kế hoạch sản xuất và quản lý danh mục đầu tư.

Bắt đầu với các bài toán hai biến đơn giản có thể trực quan hóa hình học. Tự triển khai simplex cơ bản để hiểu những gì bộ giải thương mại làm phía sau màn hình. Làm việc với các mô hình thực tế, chuyển yêu cầu nghiệp vụ thành các ràng buộc toán học.

Để đào sâu chuyên môn, hãy khám phá các khóa học Giới thiệu về Tối ưu hóa bằng Python và Đại số tuyến tính cho Khoa học Dữ liệu để củng cố nền tảng toán học. Lộ trình nghề nghiệp Nhà khoa học Machine Learning với Python cũng là một lựa chọn tuyệt vời.