Suy Biến Trong Toán Học Là Gì? - Blog Tổng Hợp Tin Tức định Nghĩa "là Gì"
Có thể bạn quan tâm
- Tin tổng hợp
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.
Nhãn:luật Bland, luật từ điển, phương pháp đơn hình, suy biến, thứ tự từ điển Posted in Quy hoạch tuyến tính | Leave a Comment »
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ọ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.
- 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.
RELATED ARTICLESMORE FROM AUTHOR
Tin tổng hợpBảng khối lượng nguyên tử là gì? Bảng khối lượng nguyên tử
Tin tổng hợpNguyên tử là gì? Cấu tạo của hạt nguyên tử
Tin tổng hợpFavorite nghĩa là gì? Sử dụng Favorite trong tiếng Anh như thế nào?
Phổ biến nhất
Ai phát minh ra toán học? Ai tạo ra môn Toán
November 2, 2024Hobby nghĩa là gì? Hobby nghĩa tiếng việt
November 2, 2024Trai 2d là gì? Trai 2d 3d 4d là gì?
November 2, 2024ups là gì? ups được phân chia như thế nào?
November 2, 2024 Load moreLiên kết bạn bè
Kiemtienspeed cook-ad.com đăng nhập w88 ABOUT USBlog sieutonghop.com luôn chia sẻ những tin tức thú vị trong cuộc sống. Hãy đến với blog và chia sẻ mỗi ngày nhé. Liên hệ quảng cáo với sieutonghop qua email bên dưới hoặc telegram: https://t.me/dungna1994Contact us: muadongvinhcuu@gmail.comFOLLOW US © Thiết kế bởi Sieutonghop MORE STORIESPhép chia trong toán học gọi là gì?
November 2, 2024wbc là gì?
November 2, 2024Mực Khô Vân Đồn 18-20 con/1kg giá 1tr2. Ưu đãi 5% cho các bạn đến từ website của mình
Từ khóa » Suy Biến Có Nghĩa Là Gì
-
Từ điển Tiếng Việt "suy Biến" - Là Gì?
-
Suy Biến Là Gì? Hiểu Thêm Văn Hóa Việt - Từ điển Tiếng Việt
-
" Suy Biến Là Gì ? Nghĩa Của Từ Suy Biến Trong Tiếng Việt Suy ...
-
Từ Điển - Từ Suy Biến Có ý Nghĩa Gì - Chữ Nôm
-
Suy Biến Nghĩa Là Gì?
-
Vật Chất Suy Biến – Wikipedia Tiếng Việt
-
Định Thức – Wikipedia Tiếng Việt
-
Ý Nghĩa Từ BẬC SUY BIẾN - Cuộc Sống Online
-
Suy Biến | My Weblog
-
Top 14 Hàm Số Suy Biến Là Sao
-
Quy Hoạch Tuyến Tính Suy Biến - VOER
-
Khắc Phục Hiện Tượng Suy Biến Trong Bài Toán Vận Tải (2) | Xemtailieu
-
17.1. Phương Pháp Phân Tích Suy Biến — Deep AI KhanhBlog