1. Suy biến là gì?
Suy biến là Hao hụt đi trong quá trình chuyển hoá: Năng lượng suy biến theo nguyên lí Carnot.
2. Suy biến trong toán học?
Trở ngại cuối cùng trong thuật toán đơn hình là tình huống lặp vô hạn khi gặp phải nghiệm cơ sở bị suy biến. Có hai nguyên nhân dẫn đến có thể xảy ra lặp vô hạn khi tiến hành thuật toán đơn hình:
- Khi tính toán
, có hai giá trị
mà
nên khi cập nhật, ta có
. Tức là ta đi đến một nghiệm cơ sở bị suy biến.
- Thuật toán đi đến một nghiệm cơ sở bị suy biến (có it nhất một biến cơ sở bằng 0) và
do
. Như vậy, nghiệm cơ sở không thay đổi mà chỉ có hệ cơ sở thay đổi. Có thể xảy ra trường hợp các véctơ cơ sở bị tráo đổi theo cách vòng tròn mà nghiệm cơ sở không hề thay đổi, dẫn tới tình huống lặp vô hạn (mặc dù khả năng này rất hiếm khi xảy ra).
Để ý rằng, trong phương pháp đơn hình, ta có quyền chọn cặp chỉ số chốt miễn là
Người ta chứng minh được rằng, nếu chọn theo những luật nhất định thì sẽ tránh được tình huống lặp vô hạn. Trong bài này, ta sẽ xem xét hai phương pháp đơn giản để khử vòng lặp vô hạn, đó là luật từ điển và luật Bland.
Định nghĩa (thứ tự từ điển): Ta nói véctơ có thứ tự từ điển nhỏ hơn véctơ
, kí hiệu là
hay
nếu
nghĩa là ở chỉ số đầu tiên mà thì
Lưu ý: định nghĩa có thể mở rộng cho hai véc tơ không có cùng số chiều, nhưng trong bài này ta chỉ quan tâm đến các véctơ có cùng số chiều.
Định nghĩa (thứ tự từ điển dương): Ta nói véctơ có thứ tự từ điển dương (gọi tắt là thứ tự dương) nếu
hay
.
Định nghĩa (luật từ điển): Luật từ điển là cách chọn chỉ số dòng tại mỗi bước lặp sao cho dòng được chọn có thứ tự từ điển nhỏ nhất khi chia cho phần tử chốt
.
Định lý (tính dừng của luật từ điển): Nếu trong bước chọn dòng , ta luôn chọn dòng có thứ tự từ điển nhỏ nhất khi chia cho phần tử chốt
thì
- Nếu các dòng của bảng (trừ dòng đầu tiên) đều có thứ tự dương, thì sau phép biến đổi dòng, các dòng này vẫn có thứ tự dương.
- Nếu các dòng của bảng (trừ dòng đầu tiên) đều có thứ tự dương, thì sau phép biến đổi dòng, thứ tự từ vựng của dòng đầu tiên tăng.
- Nếu các dòng của bảng ban đầu (trừ dòng đầu tiên) có thứ tự dương thì thuật toán đơn hình luôn dừng.
Chứng minh (1): Với những dòng mà thì
nên nhân dòng
với
rồi cộng vào dòng
ta vẫn có thứ tự dương.
Với những dòng mà thì
, tức là dòng
vẫn có thứ tự dương vì
là giá trị đầu tiên trong dòng thứ
).
Với những dòng mà thì sau biến đổi dòng, dòng
vẫn có thứ tự dương vì dòng
chia cho
có thứ tự từ điển nhỏ hơn dòng
chia cho
. Thật vậy, giả sử cột
là cột đầu tiên mà
Trong đó lần lượt là các giá trị ở cột
tại các hàng
. Suy ra
Vì là giá trị đầu tiên khác
trên dòng
sau khi biến đổi dòng nên dòng
có thứ tự dương.
Chứng minh (2): vì nên
. Do vậy, khi nhân dòng thứ
với
rồi cộng vào dòng đầu tiên, thứ tự từ điển của dòng đầu tiên sẽ tăng lên (do dòng
có thứ tự dương).
Chứng minh (3): Do số bảng đơn hình là hữu hạn (bằng số bộ cơ sở có thể có), mà thứ tự từ điển của dòng đầu tiên lại luôn tăng, nên đến lúc nào đó, thuật toán đơn hình phải dừng.
Nhận xét: Để tạo được các dòng có thứ tự dương trong bảng ban đầu, ta có thể đảo chỗ các biến bù lên đầu, như vậy ma trận , hơn nữa,
(cột đầu tiên của bảng) nên tất cả các dòng của bảng (trừ dòng đầu tiên) đều có thứ tự dương.
Định nghĩa (Luật Bland): Cách lựa chọn cặp chỉ số chốt sau đây gọi là luật Bland:
- Trong bước chọn cột, chọn chỉ số
nhỏ nhất sao cho
.
- Trong bước chọn dòng, chọn chỉ số
nhỏ nhất sao cho
.
Định lý (tính dừng của luật Bland): Nếu lựa chọn cặp chỉ số chốt theo luật Bland thì thuật toán đơn hình luôn dừng.
Phương pháp đơn hình (2) – Hướng làm giảm hàm mục tiêu, điều kiện tối ưu, phương pháp đơn hình
Tháng Hai 25, 2008
Định nghĩa (hướng chấp nhận được): Xét một điểm thuộc đa diện lồi
. Ta gọi hướng
là hướng chấp nhận được của
tại
nếu tồn tại
sao cho
.
Nhận xét: Trong phương pháp đơn hình, thay vì chọn một nghiệm cơ sở bất kì, ta sẽ đi từ nghiệm cơ sở chấp nhận được này đến một nghiệm cơ sở chấp nhận được khác theo một hướng chấp nhận được sao cho hàm mục tiêu sẽ giảm đi.
Nhớ lại rằng, nếu là một nghiệm cơ sở chấp nhận được của đa diện lồi ở dạng chuẩn tắc
thì tồn tại một bộ chỉ số
sao cho
- Ma trận cơ sở
khả nghịch.
.
Một nghiệm cơ sở chấp nhận được khác phải tương ứng với một bộ chỉ số khác. Như vậy nếu ta xét một chỉ số , và chọn một hướng chấp nhận được
sao cho
thì đi theo hướng này, ta sẽ có
tức là mọi nghiệm cơ sở chấp nhận được trên hướng này sẽ là nghiệm cơ sở tương ứng với một bộ chỉ số chỉ khác bộ chỉ số cũ ở duy nhất một chỉ số. Bây giờ ta sẽ tính các giá trị sao cho
là hướng chấp nhận được. Ta gọi đây là hướng chấp nhận được tương ứng với biến
(gọi tắt là hướng chấp nhận được thứ
).
Định lý (hướng chấp nhận được thứ ): Xét nghiệm cơ sở chấp nhận được
của đa diện lồi dạng chuẩn tắc
và bộ chỉ số cơ sở
tương ứng của
. Hướng chấp nhận được thứ
là hướng
, trong đó
với và
Chứng minh: Để với
nào đó, ta có
vì . Suy ra
Nhận xét: Với hướng chấp nhận được thứ , hàm mục tiêu bị thay đổi như sau
với . Mục tiêu của ta là phải chọn
sao cho
thì hàm mục tiêu sẽ giảm trên hướng chấp nhận được thứ
.
Định nghĩa (thay đổi ở hướng chấp nhận được thứ ): Xét nghiệm cơ sở chấp nhận được
của đa diện lồi dạng chuẩn tắc
và ma trận cơ sở tương ứng
của
, thay đổi ở hướng chấp nhận được thứ
là đại lượng
Véctơ chứa giá trị thay đổi ở tất cả các hướng
Nhận xét: Nếu thì
Tức là với mọi chỉ số thuộc vào bộ chỉ số cơ sở của
thì không có thay đổi trên hướng
.
Định lý (điều kiện tối ưu của nghiệm cơ sở chấp nhận được): Nếu là nghiệm cơ sở chấp nhận được của đa diện lồi dạng chuẩn tắc
và
là véc tơ chứa giá trị thay đổi trên các hướng thì
- Nếu
thì
là nghiệm tối ưu của bài toán QHTT.
- Nếu
là nghiệm tối ưu và
thì
. Trong đó
.
Lưu ý: Khi ta còn gọi
là nghiệm cơ sở không suy biến.
Chứng minh (1): Xét một điểm , ta có
, suy ra
vì và
theo giả thiết. Suy ra
.
Chứng minh (2): Giả sử ngược lại tồn tại sao cho
. Xét hướng
là hướng chấp nhận được thứ
. Do
và
nên nếu đi theo hướng
, các tọa độ
. Mặt khác, do
nên ta có thể chọn
đủ nhỏ sao cho
. Như vậy, đi theo hướng
ta vẫn nằm trong
nhưng lại giảm được giá trị hàm mục tiêu do
, mâu thuẫn vì
là nghiệm tối ưu.
Nhận xét:
- Định lý cung cấp một điều kiện có thể kiểm tra nghiệm tối ưu bằng tính toán (tính véctơ
).
- Định lý vẫn để ngỏ khả năng
có thể là nghiệm tối ưu khi
là nghiệm cơ sở suy biến và
.
- Nếu
là nghiệm cơ sở không suy biến và
, ta có thể chọn hướng
chấp nhận được thứ
nào đó sao cho
. Xuất phát từ
đi theo hướng này ta sẽ giảm được giá trị của hàm mục tiêu.
- Nếu
thì ta có thể cho
mà vẫn có
, nghĩa là hàm mục tiêu không bị chặn.
- Nếu tồn tại
sao cho
(lưu ý:
), thì giá trị của
lớn nhất có thể được là
- Nếu ta có
và
, ta có nghiệm cơ sở
là nghiệm tối ưu và ta nói
là ma trận cơ sở tối ưu.
- Định lý sau đây còn cho biết nếu chọn giá trị của
lớn nhất có thể được thì ta sẽ được một nghiệm cơ sở chấp nhận được tương ứng với ma trận cơ sở khác.
Định lý: Nếu là nghiệm cơ sở chấp nhận được của đa diện lồi dạng chuẩn tắc
, hướng
là hướng chấp nhận được thứ
và
thì là nghiệm cơ sở chấp nhận được tương ứng với bộ chỉ số
. Nghĩa là trong hệ cơ sở mới, ta thay
bằng
.
Chứng minh: Rõ ràng , hơn nữa do
và
nên
. Như vậy
. Ta chỉ còn cần chứng minh ma trận cơ sở mới
là ma trận khả nghịch. Xét ma trận
trong đó là véc tơ cơ sở thứ
trong hệ tọa độ Đềcác của
và
. Dễ thấy
do đó
hay
khả nghịch.
Phương pháp đơn hình:
-
Xuất phát từ một nghiệm cơ sở chấp nhận được và ma trận cơ sở
tương ứng.
- Tính véctơ
chứa giá trị thay đổi ở các hướng.
- Nếu
, dừng và kết luận
là nghiệm tối ưu.
- Nếu
, chọn một hướng
là hướng chấp nhận được thứ
nào đó mà
, tức là
.
- Nếu
, dừng và kết luận bài toán QHTT không bị chặn và không có nghiệm.
- Nếu
, chọn
Cặp chỉ sốcòn gọi là chốt (nó chỉ ra cột ra khỏi ma trận cơ sở và cột thay thế).
- Thay
bằng nghiệm cơ sở chấp nhận được
và ma trận cơ sở mới
và quay lại bước 1.
Định lý (tính đúng đắn của phương pháp đơn hình): Nếu tất cả các nghiệm cơ sở chấp nhận được của bài toán QHTT
đều là nghiệm cơ sở không suy biến thì phương pháp đơn hình luôn dừng và khi đó có hai khả năng xảy ra:
- Ta có nghiệm tối ưu
và ma trận cơ sở tối ưu
.
- Ta tìm được véctơ
sao cho
và
và kết luận bài toán QHTT không bị chặn nên không có nghiệm tối ưu.
Chứng minh: Vì tất cả các nghiệm cơ sở chấp nhận được đều không suy biến nên ta luôn có
Nghĩa là sau mỗi bước của thuật toán, giá trị hàm mục tiêu bị thay đổi một lượng bằng
Tức là không có nghiệm cơ sở chấp nhận được nào bị lặp lại, hơn nữa, số lượng nghiệm cơ sở chấp nhận được là hữu hạn nên thuật toán phải dừng. Nếu thuật toán dừng ở bước 3 thì ta có nghiệm tối ưu theo định lý về điều kiện tối ưu của nghiệm cơ sở ở trên. Nếu thuật toán dừng ở bước 5, ta có và
do đó bài toán QHTT không bị chặn và không có nghiệm tối ưu (từ
đi theo hướng
thì
.
Nhận xét:
- Định lý trên cho thấy tính dừng của phương pháp đơn hình khi mọi nghiệm cơ sở chấp nhận được của
đều không suy biến. Trong trường hợp tồn tại nghiệm cơ sở bị suy biến, phương pháp đơn hình có thể bị lặp vô hạn (mặc dù khả năng này rất hiếm khi xảy ra). Trong các bài sau, ta sẽ tìm hiểu hiện tượng này và cách khắc phục.
- Lựa chọn chỉ số
và
là hoàn toàn tự do miễn là
và
Ta sẽ thấy nếu lựa chọnvà
hợp lý sẽ tránh được hiện tượng lặp vô hạn khi có nghiệm cơ sở suy biến.
- Tại mỗi bước lặp ta cần tính toán nghịch đảo của
, ta sẽ thấy cùng với việc thay đổi ma trận cơ sở, ta có thể tính nghịch đảo của ma trận cơ sở mới rất hiệu quả bởi ma trận cơ sở mới chỉ khác ma trận cơ sở cũ ở duy nhất 1 cột.