Ma trận chuẩn tắc là gì

ma trận Joocđăng [Jordan] có dạng:

trong đó mỗi Ai là một ma trận vuông [gọi là khung Joocđăng] và có dạng:

Mọi ma trận vuông A bậc n trên một trường K đều đồng dạng với một ma trận Joocđăng 
trên K [nghĩa là tồn tại trên K một ma trận không suy biến C sao cho
= CAC–1] khi và chỉ khi A có n giá trị riêng trên K, mỗi giá trị được tính với số bội của nó.
gọi là DCTJ của A. DCTJ xác định duy nhất nếu không tính đến thứ tự các khung Joocđăng. Trên trường số phức, mọi ma trận vuông đều đưa được về DCTJ.

Posts Tagged ‘dạng chuẩn tắc’

Phương pháp đơn hình [Simplex method] [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

Posted by Trần Quốc Long trên 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 [feasible direction] 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

1. Ma trận cơ sở khả nghịch.
2. .

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ì

1. Nếu thì là nghiệm tối ưu của bài toán QHTT.
2. 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 [nondegenerate basic solution].

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:

1. Đị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ơ ].
2. Đị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à .
3. 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.
4. 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.
5. Nếu tồn tại sao cho [lưu ý: ], thì giá trị của lớn nhất có thể được là

6. 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 [optimal basis].
7. Đị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 [simplex method]:

1. 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.

2. Tính véctơ chứa giá trị thay đổi ở các hướng.
3. Nếu , dừng và kết luận là nghiệm tối ưu.
4. Nếu , chọn một hướng là hướng chấp nhận được thứ nào đó mà , tức là .
5. 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.
6. 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ế].

7. 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:

1. Ta có nghiệm tối ưu và ma trận cơ sở tối ưu .
2. 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:

1. Đị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.
2. 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ọn và 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.

3. 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.

Posted in Quy hoạch tuyến tính | Thẻ: dạng chuẩn tắc, hướng chấp nhận được, nghiệm cơ sở, phương pháp đơn hình, suy biến, điều kiện tối ưu | Leave a Comment »

Phương pháp đơn hình [Simplex method] [1] – Bài toán QHTT, dạng chuẩn tắc và các định lý cơ bản

Posted by Trần Quốc Long trên Tháng Hai 23, 2008

Định nghĩa 1 [Quy hoạch tuyến tính]. Bài toán quy hoạch tuyến tính [linear programming] là bài toán tìm cực tiểu sau

.

Xem thêm ở bài về bài toán đối ngẫu.

Nhận xét:

1. Nếu cỡ của ma trận là , ràng buộc tương đương với ràng buộc nhỏ

   với là dòng thứ của ma trận .

2. Để cho tiện, trong loạt bài này ta kí hiệu [chữ cái thường] là dòng thứ của ma trận , còn cột thứ của ma trận kí hiệu là [chữ cái hoa].

Định nghĩa 2 [Dạng chuẩn tắc]. Bài toán quy hoạch tuyến tính ở dạng chuẩn tắc [standard form] là bài toán tìm cực tiểu sau:

Nhận xét:

1. Dạng chuẩn tắc có thể đưa về dạng gốc bằng cách thiết lập ma trận như sau

   trong đó

2. Dạng gốc có thể đưa về dạng chuẩn tắc bằng cách thiết lập ma trận như sau

   trong đó .

3. Như vậy, hai dạng của bài toán quy hoạch tuyến tính là tương đương. Tuy nhiên, trong phương pháp đơn hình, người ta sử dụng dạng chuẩn tắc bởi dạng này có một số tính chất rất thuận lợi cho việc tìm ra điểm cực biên.

Định lý [hàm tuyến tính bị chặn đạt cực trị trong đa diện lồi]. Nếu hàm tuyến tính bị chặn dưới trong đa diện lồi thì nó đạt cực tiểu trong đa diện lồi đó. Đồng thời nếu đa diện lồi không chứa đường thẳng thì hàm tuyến tính đó đạt cực tiểu tại một trong các điểm cực biên.

Chứng minh:Xem trong bài cấu trúc của đa diện lồi.

Hệ quả: Với bài toán quy hoạch tuyến tính ở dạng chuẩn tắc, do điều kiện nên đa diện lồi tạo nên bởi các ràng buộc không chứa đường thẳng. Do đó, hàm tuyến tính phải đạt giá trị cực tiểu [nếu có] ở một trong các điểm cực biên.

Định nghĩa [nghiệm cơ sở]: Điểm gọi là nghiệm cơ sở [basic solution] của đa diện lồi nếu có ràng buộc được kích hoạt tại độc lập tuyến tính, tức là tồn tại tập chỉ số

và độc lập tuyến tính.

Lưu ý: Nghiệm cơ sở có thể không phải là điểm nằm trong đa diện lồi.

Định nghĩa [nghiệm cơ sở chấp nhận được]: Điểm là nghiệm cơ sở chấp nhận được [basic feasible solution] của nếu và là nghiệm cơ sở của .

Định lý [điều kiện của điểm cực biên của đa diện lồi]: Cho điểm là điểm thuộc đa diện lồi , các mệnh đề sau đây tương đương

1. là điểm cực biên của .
2. là đỉnh của .
3. là nghiệm cơ sở chấp nhận được của .

Chứng minh:

““: Xem trong bài cấu trúc của đa diện lồi.

““: Nếu là nghiệm cơ sở chấp nhận được, tức là tồn tại

và độc lập tuyến tính.

Chọn , ta sẽ chứng minh hàm tuyến tính đạt cực đại duy nhất trên tại . Thật vậy, xét một điểm , ta có

Như vậy, hàm tuyến tính đạt cực đại trên tại . Đồng thời ta cũng thấy dấu bằng không thể xảy ra trong bất đẳng thức này nếu , vì nếu như vậy, ta sẽ có , nhưng do độc lập tuyến tính nên điểm thỏa mãn đẳng thức này chỉ có duy nhất 1 điểm . Vậy , tức là là đỉnh của .

““: Xem trong bài siêu phẳng đỡ và điểm cực biên.

Nhận xét:

1. Định lý chứng tỏ 3 khái niệm điểm cực biên, đỉnh, nghiệm cơ sở chấp nhận được là tương đương trong đa diện lồi. Ta có thể sử dụng các tính chất của cả ba khái niệm này cùng lúc.
2. Điểm cực biên là khái niệm có tính chất hình học [điểm không nằm giữa hai điểm nào trong tập] rất khó kiểm tra [vì phải kiểm tra mọi cặp điểm] còn nghiệm cơ sở chấp nhận được lại là khái niệm rất dễ kiểm tra bằng thuật toán [điểm có ràng buộc được kích hoạt].

Hệ quả: Do số tổ hợp chập của là hữu hạn nên ta có một thuật toán đơn giản sau để giải bài toán quy hoạch tuyến tính [dạng gốc]

1. Lần lượt chọn từng bộ ràng buộc, kiểm tra tính độc lập tuyến tính.
2. Nếu bộ ràng buộc không độc lập tuyên tính quay lại bước 1 chọn bộ ràng buộc khác.
3. Nếu bộ ràng buộc độc lập tuyến tính, giải hệ phương trình tương ứng của bộ ràng buộc này [coi như các ràng buộc được kích hoạt] để tìm ra nghiệm cơ sở .
4. Kiểm tra xem có là nghiệm cơ sở chấp nhận được hay không? Nếu đúng thì tính giá trị của hàm tại điểm này, so sánh với giá trị tốt nhất đang có và thay đổi giá trị này nếu cần. Sau đó quay lại bước 1 chọn bộ ràng buộc khác.

Nhận xét:

1. Thuật toán này không phải là thuật toán hiệu quả vì số lượng ràng buộc trong ràng buộc tăng theo hàm mũ.
2. Tuy nhiên, thuật toán này chứng tỏ bài toán QHTT là bài toán giải được [decidable], nghĩa là thuật toán luôn dừng và cho ra kết quả [chỉ ra nghiệm hoặc chỉ ra không có nghiệm].

Định lý [điều kiện của nghiệm cơ sở của đa diện lồi ở dạng chuẩn tắc]: Cho đa diện lồi và giả sử độc lập tuyến tính, điểm là nghiệm cơ sở của nếu và chỉ nếu tồn tại bộ chỉ số sao cho

1. Ma trận gồm các cột tương ứng của ma trận là ma trận khả nghịch.
2. .

Ta gọi ma trận là ma trận cơ sở tương ứng của .
Chứng minh:

““: Giả sử [1] và [2] đều xảy ra, ta sẽ chứng minh là nghiệm cơ sở của . Thật vậy, các ràng buộc được kích hoạt tại là

với là véc tơ thứ trong hệ cơ sở của hệ tọa độ Đềcác.

Các véctơ không thể là tổ hợp tuyến tính của các véctơ vì nếu như vậy, tức là tồn tại sao cho

Suy ra

,

với là các dòng của vì , suy ra mâu thuẫn vì khả nghịch. Vậy tại có ràng buộc độc lập tuyến tính, hay là nghiệm cơ sở của .

““: Giả sử là nghiệm cơ sở của , do có ràng buộc độc lập tuyến tính được kích hoạt nên là điểm duy nhất mà cả ràng buộc này được kích hoạt. Giả sử các chỉ số là các chỉ số mà . Rõ ràng vì có ít nhất ràng buộc dạng được kích hoạt [do chỉ có ràng buộc dạng đã được kích hoạt]. Ta có

Ta sẽ chứng minh các cột độc lập tuyến tính. Thật vậy, giả sử tồn tại bộ số không đồng thời bằng sao cho

Suy ra nếu đặt sao cho thì

Nghĩa là véc tơ không phải là véc tơ duy nhất kích hoạt ràng buộc độc lập tuyến tính, mâu thuẫn. Vậy các cột độc lập tuyến tính. Hơn nữa, do hàng của ma trận độc lập tuyến tính nên không gian tuyến tính tạo bởi các cột của phải là . Suy ra, nếu ta có thể chọn thêm các cột khác để tạo nên một bộ cơ sở của . Bộ chỉ số rõ ràng thỏa mãn hai điều kiện [1] và [2].

Nhận xét: Đối với bài toán QHTT ở dạng chuẩn tắc, thuật toán trên có thể biến đổi như sau:

1. Chọn một bộ chỉ số . Kiểm tra xem ma trận có khả nghịch không.
2. Nếu ma trận khả nghịch, tính với

   .

3. Kiểm tra điều kiện , nếu đúng thì đặt . Khi đó là nghiệm cơ sở chấp nhận được của .
4. Tính giá trị của hàm mục tiêu tại , thay đổi giá trị tốt nhất hiện tại nếu cần. Rồi chuyển về bước 1 chọn bộ chỉ số khác.

Posted in Quy hoạch tuyến tính | Thẻ: dạng chuẩn tắc, ma trận cơ sở, nghiệm cơ sở, nghiệm cơ sở chấp nhận được, Quy hoạch tuyến tính, ràng buộc, Thuật toán, đỉnh, đối ngẫu, độc lập tuyến tính, điểm cực biên | Leave a Comment »