Quy hoạch tuyến tính — Phương pháp đơn hình & nghiệm hình học

Quy hoạch tuyến tính là phương pháp tìm giá trị tốt nhất của một mục tiêu tuyến tính, chẳng hạn lợi nhuận lớn nhất hoặc chi phí nhỏ nhất, dưới các ràng buộc tuyến tính. Với bài toán hai biến, cách giải hình học là tìm miền nghiệm khả thi rồi kiểm tra các đỉnh của miền đó. Với các bài toán lớn hơn, phương pháp đơn hình dùng chính ý tưởng về các đỉnh nhưng thực hiện bằng đại số.

Chỉ dùng quy hoạch tuyến tính khi cả hàm mục tiêu và các ràng buộc đều là tuyến tính. Nếu mối quan hệ bị uốn cong, có dạng đường cong, hoặc phụ thuộc vào tích như $xy$, thì mô hình đó không còn là một bài toán quy hoạch tuyến tính.

Định nghĩa quy hoạch tuyến tính

$$\text{maximize or minimize } z = c_1x_1 + c_2x_2 + \cdots + c_nx_n$$

với các ràng buộc như

$$a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \le b_1$$

cùng với các bất đẳng thức tuyến tính tương tự, và các điều kiện như $x_i \ge 0$ khi giá trị âm không có ý nghĩa thực tế.

Tập hợp tất cả các điểm thỏa mãn mọi ràng buộc được gọi là miền nghiệm khả thi. Quy hoạch tuyến tính đặt câu hỏi: trong các điểm khả thi đó, điểm nào cho giá trị hàm mục tiêu tốt nhất?

Cách phương pháp hình học hoạt động

Nếu chỉ có hai biến quyết định, bạn có thể vẽ từng ràng buộc trên mặt phẳng $xy$. Phần giao nhau của tất cả các miền được phép chính là miền nghiệm khả thi.

Mỗi điểm trong miền đó là một nghiệm hợp lệ. Hàm mục tiêu gán một giá trị cho từng điểm.

Với quy hoạch tuyến tính, có một sự thật quan trọng là: nếu tồn tại nghiệm tối ưu, thì sẽ có ít nhất một nghiệm tối ưu nằm tại một đỉnh của miền nghiệm khả thi. Đó là lý do phương pháp hình học tập trung vào các đỉnh thay vì kiểm tra mọi điểm trong miền tô bóng.

Ví dụ mẫu: Giải một bài toán quy hoạch tuyến tính bằng phương pháp hình học

Giả sử một xưởng sản xuất hai sản phẩm, $A$ và $B$.

• Lợi nhuận trên mỗi đơn vị $A$: $3$
• Lợi nhuận trên mỗi đơn vị $B$: $5$
• Giới hạn thời gian máy: mỗi đơn vị $A$ dùng $1$ giờ, mỗi đơn vị $B$ dùng $2$ giờ, và có nhiều nhất $8$ giờ
• Giới hạn lắp ráp: mỗi đơn vị $A$ dùng $1$ giờ, mỗi đơn vị $B$ dùng $1$ giờ, và có nhiều nhất $5$ giờ

Gọi $x$ là số đơn vị của $A$ và $y$ là số đơn vị của $B$.

Tối đa hóa

$$P = 3x + 5y$$

với điều kiện

$$x + 2y \le 8$$ $$x + y \le 5$$ $$x \ge 0,\quad y \ge 0$$

Tìm các đỉnh

Từ các trục tọa độ và các đường ràng buộc, các đỉnh khả thi là

• $(0,0)$
• $(5,0)$
• $(0,4)$
• $(2,3)$

Điểm $(2,3)$ có được bằng cách giải hệ phương trình biên

$$x + 2y = 8,\quad x + y = 5$$

Lấy phương trình đầu trừ phương trình sau, ta được $y = 3$, rồi suy ra $x = 2$.

Kiểm tra hàm mục tiêu tại từng đỉnh

Tính lợi nhuận tại từng đỉnh:

• Tại $(0,0)$, $P = 0$
• Tại $(5,0)$, $P = 15$
• Tại $(0,4)$, $P = 20$
• Tại $(2,3)$, $P = 21$

Vậy lợi nhuận lớn nhất là

$$P = 21$$

tại

$$(x,y) = (2,3)$$

Đó là phương pháp hình học trong một câu: vẽ miền nghiệm khả thi, tìm các đỉnh, rồi tính hàm mục tiêu tại các điểm đó.

Trực giác về phương pháp đơn hình

Phương pháp hình học chỉ thực sự tiện khi có hai biến, và đôi khi là ba biến nếu bạn sẵn sàng hình dung một miền trong không gian 3D. Các bài toán tối ưu thực tế thường có nhiều biến, nên việc vẽ miền nghiệm khả thi không còn khả thi nữa.

Phương pháp đơn hình vẫn giữ nguyên logic về các đỉnh, nhưng thực hiện bằng đại số. Nói một cách khái quát, nó di chuyển từ một đỉnh khả thi sang một đỉnh khả thi khác làm cải thiện hàm mục tiêu, và dừng lại khi không còn bước đi lân cận nào cho giá trị tốt hơn.

Vì vậy, một cách hình dung tốt là:

• Phương pháp hình học: nhìn thấy các đỉnh
• Phương pháp đơn hình: đi qua các đỉnh mà không cần vẽ chúng

Mô tả này chỉ là trực giác, không phải toàn bộ thuật toán. Quy trình đơn hình thực tế dùng bảng đơn hình hoặc một dạng đại số tương đương để quyết định biến nào vào cơ sở và biến nào ra khỏi cơ sở ở mỗi bước.

Vì sao các đỉnh quan trọng

Các hàm mục tiêu tuyến tính tạo ra các đường mức như

$$3x + 5y = k$$

ứng với các giá trị khác nhau của $k$. Khi bạn tịnh tiến đường thẳng đó theo hướng làm lợi nhuận tăng lên, điểm cuối cùng mà nó còn chạm vào miền nghiệm khả thi là nơi giá trị lớn nhất đạt được.

Trong nhiều hình vẽ, lần chạm cuối đó xảy ra tại một đỉnh duy nhất. Nếu đường mục tiêu song song với một cạnh biên, thì nhiều điểm trên cạnh đó đều có thể là tối ưu. Trong trường hợp đó, vẫn luôn có ít nhất một đỉnh tối ưu.

Những lỗi thường gặp

Nhầm lẫn giữa khả thi và tối ưu

Một điểm có thể thỏa mãn mọi ràng buộc nhưng vẫn không làm cực đại hoặc cực tiểu hàm mục tiêu. Khả thi chỉ có nghĩa là được phép.

Quên điều kiện không âm

Nếu $x$ và $y$ biểu diễn số lượng bạn sản xuất hoặc vận chuyển, thì giá trị âm thường không có ý nghĩa. Bỏ qua $x \ge 0$ hoặc $y \ge 0$ có thể làm thay đổi bài toán.

Cho rằng mọi đáp án đều phải là số nguyên

Quy hoạch tuyến tính thông thường cho phép các giá trị phân số. Nếu các biến bắt buộc phải là số nguyên, chẳng hạn số xe tải hoặc số công nhân, thì bạn cần mô hình quy hoạch nguyên hoặc thêm điều kiện nguyên.

Cho rằng bài toán nào cũng có đáp án tốt nhất

Một số bài toán quy hoạch tuyến tính là vô nghiệm, nghĩa là không có điểm nào thỏa mãn mọi ràng buộc. Một số bài toán khác là không bị chặn, nghĩa là hàm mục tiêu có thể cải thiện mãi không giới hạn. Bạn chỉ có nghiệm tối ưu hữu hạn khi các ràng buộc thực sự giới hạn bài toán đủ chặt.

Dùng phương pháp hình học khi có quá nhiều biến

Khi số biến lớn, vẽ hình không còn là công cụ phù hợp. Đó là lúc phương pháp đơn hình hoặc các phương pháp tối ưu khác trở nên cần thiết.

Khi nào dùng quy hoạch tuyến tính

Quy hoạch tuyến tính được dùng khi các quyết định phải cạnh tranh cho những nguồn lực có hạn, và cả mục tiêu lẫn các giới hạn đều có thể được mô hình hóa bằng quan hệ tuyến tính. Những ví dụ điển hình gồm lập kế hoạch sản xuất, bài toán vận tải, bố trí nhân sự, phối trộn, lập lịch và phân bổ ngân sách.

Mô hình chỉ tốt bằng chính các giả định của nó. Nếu quan hệ thực tế không gần tuyến tính, hoặc nếu các biến phải là số nguyên, thì một bài toán quy hoạch tuyến tính thông thường có thể chỉ là điểm khởi đầu.

Hãy thử một bài tương tự

Hãy lấy một bài toán lời văn nhỏ với hai sản phẩm, hai giới hạn nguồn lực và một hàm lợi nhuận. Tự viết các biến, vẽ các ràng buộc và kiểm tra các đỉnh. Khi bạn thật sự nắm được ý tưởng đó, phương pháp đơn hình sẽ dễ hiểu hơn nhiều vì nó chỉ mở rộng cùng một logic sang không gian nhiều chiều hơn.