Thuật toán đơn hình trong quy hoạch tuyến tính
Đơn hình là phương pháp chỉ các phương pháp tổng quát bài toán quy hoạch tuyến tính bằng phương pháp xoay
trụ (pivoting), giống như phép khử Gauss. Nó tương ứng với thao tác hình học chuyển từ đỉnh này tới đỉnh khác
của đơn hình để tìm lời giải. Các thuật toán chỉ khác nhau ở thứ tự các đỉnh được xét đến.
Bài toán quy hoạch tuyến tính có thể có nhiều dạng. Ví dụ, bài toán mạng dòng chảy có các đẳng thức lẫn các
bất đẳng thức, những ví dụ hình học chỉ sử dụng các bất đẳng thức. Để làm giảm bớt số hạng có thể có của bài
toán, ta sẽ xét một dạng chuẩn, trong đó tất cả các ràng buộc là đẳng thức, ngoại trừ một số bất đẳng thức biểu
thị các biến đều là số không âm. Dạng chuẩn này dường như quá chặt chẽ, tuy nhiên ta có thể chuyển bài tổng
quát về dạng này. Bài toán sau là dạng chuẩn của ví dụ 3 chiều:
Cực đại hoá x
1
+x
2
+ x
3
với các điều kiện
-x
1
+x
2
+y
1
=5x
1
+4x
2
+y
2
=45
2x
1

5
>= 0
Mỗi bất đẳng thức có 2 biến trở nên chuyển thành đẳng thức bằng cách thêm vào một biến. Các biến y gọi là
các biến phụ thêm(slack variable). Ngoài ra, bằng cách đổi biến ta có thể chuyển bất đẳng thức một biến thành
loại ràng buộc không âm. Ví dụ một ràng buộc như x
3
<=-1 chuyển thành dạng chuẩn x’
3
>=0 với x’
3
= -1-x
3
.
Dạng chuẩn tạo ra một tương ứng giữa bài toán quy hoạch tuyến tính và giải hệ phương trình tuyến tính. Ta
có N phương trình với N ẩn (số dương). Trong trường hợp này, chú ý là ta có N biến phụ thêm, mỗi phương
trình một biến (vì ta bắt đầu với một hệ toàn bất đẳng thức). Nếu M>N thì hệ phương trình có nhiều nghiệm:
vấn đề là tìm một cái làm cho hàm mục tiêu cực đại.
Trong ví dụ của ta, các phương trình ràng buộc có một nghiệm tầm thường x
1
=x
2
=x
3
= 0, còn các biến phụ
thêm y
1
, y
2
, y
3

thành 0, rồi dùng nghiệm tầm thường cho trong cơ sở. Trong ví dụ trên, ta cho x
2
và x
3
là 0 vì chúng là biến
không cơ sở và x
1
=8, vậy ma trận tương ứng với điểm (8,0,0) trong đơn hình (chúng ta không chú ý đến giá trị
của các biến phụ thêm). Chú ý rằng gốc trên bên phải của ma trận (hàng 0, cột M+1) chứa giá trị của hàm mục
tiêu tại điểm này.
Bây giờ, giả sử ta thực hiện phép toán xoay trục với p=3, q=2

Nó xoá cột 6 khỏi cơ sở và thêm cột 2 vào. Bằng cách cho các biến không cơ sở là 0 và giải các biến cơ cở
như trước ta thấy ma trận này tương ứng với điểm (12, 3, 0) của đơn hình, giá trị của hàm mục tiêu tại dó là
15. Chú ý là giá trị của hàm mục tiêu tăng nghiêm ngặt.
Ta làm cách nào để xác định p và q để thực hiện phép toán mà giá trị hàm mục tiêu sẽ tăng lên? Hàng số 0 sẽ
được dùng để xác định p, q. Ta sẽ chọn cột q ở vị trí mà giao điểm của cột q và hàng 0 là một số âm. Sau đó
hàng p sẽ được xác định sao cho phần tử của hàng ở cột q và cột M+1 là các số không âm. Trong thủ tục tìm
q, p này, có hai khó khăn: Thứ nhất, điều gì xảy ra nếu không có phần tử nào của cột q là số dương? Đó là
một trường hợp mâu thuẫn: phần tử âm ở cột q, hàng 0 cho thấy hàm mục tiêu có thể tăng lên được, tuy nhiên
lại không có cách để tăng lên, trường hợp này xảy ra khi và chỉ khi đơn hình là không bị chậm, vậy thuật toán
có thể kết thúc và báo kết quả. Một khó khăn tinh tế khác là phần tử ở cột (M+1) của hàng đã chọn (với phần
tử dương ở cột q) là 0. Hàng này có thể sử dụng, nhưng giá trị của hàm mục tiêu không tăng lên. Nếu có hai
hàng như vậy ta sẽ gặp trường hợp thuật toán lặp vô hạn. Chúng ta có thể tránh những khó khăn như vậy nếu
mô tả phương pháp thật rõ ràng nhưng cần nhấn mạnh rằng các trường hợp suy yếu như vậy có thể xảy ra
trong thực tế. Có nhiều phương pháp để tránh bị lặp. Một phương pháp là ngừng một cách ngẫu nhiên. Một
phương pháp khác chống bị lặp sẽ mô tả dưới đây.
Trong ví dụ, có thể làm một lần nữa với q=3 (vì giá trị ở cột 3, hàng 0 là -1 <0) và p=5 (vì chỉ có 1 là giá trị
dương ở cột 3). Ta được ma trận sau:


số 1 ở hàng p. Cần phải giữ các giá trị cảu a[p,q] không thay đổi trước khi ta kết thúc việc sử dụng nó.
Khác với phép khử Gauss dùng giải hệ tuyến tính, thuật toán đơn hình chỉ bao gồm việc tìm giá trị của p và q
như đã mô tả rồi gọi pivot, lặp lại quá trình này tới khi đạt được cực trị hay là tới lúc đơn hình được xác định
là không bị chặn.
Repeat
q:=0; repeatq:=q+1 until (q:=M+1) or (a[0,q]<0);
p:=0; repeatp:=p+1 until (p=N+1)or(a[p,q]>0);
for i:=p+1 to N do
ifa[i,q]>0 then
if (a[i, M+1]/a[i,q]) then p:=i;
if (qand (pthen pivot(p,q);
until (q=M+1) or (p=N+1);
**_*
Nếu chương trình kết thúc với q=M+1 thì một nghiệm tối ưu đã được xác định, cực đại của hàm mục tiêu sẽ
là a[0, M+1] và giá trị các biến có thể tìm từ cơ sở. Nếu chương trình kết thúc với p=N+1 thì miền đơn hình là
không bị chặn.
Chương trình và ví dụ trên chỉ dùng để mô tả các nguyên lý chính của thuật toán đơn hình, các trường hợp
phức tạp có thể nảy sinh trong áp dụng được bỏ qua. Chương trình yêu cầu ma trận phải có một cơ sở thích
hợp. Chương trình bắt đầu từ giả thiết: có 1 nghiệm với M-N biến trong hàm mục tiêu là 0 còn NxN ma
trận con gồm các biến thêm vào có thể chuyển thành ma trận đơn vị. Nói chung điều này không đúng cho
các trường hợp tổng quát. Nếu ta tìm được một nghiệm, ta có thể dùng một phép biến đổi thích hợp (chuyển
điểm này, tức nghiệm này, thành gốc toạ độ) để chuyển ma trận về dạng yêu cầu, tuy nhiên, thông thường ta
chẳng biết bài toán như vậy có một nghiệm cần thiết hay không.
Thực ra, việc chỉ ra rằng bài toán có nghiệm hay không cũng khó khăn như việc tìm ra được nghiệm tối ưu. Vì
thế, ta không nên ngạc nhiên khi kỹ thuật dùng để chỉ ra sự tồn tại nghiệm cũng chính là phương pháp đơn
hình! Đặc biệt, ta thêm vào một số biến s
1
, s
2
, …s