Top 8 # Code Phương Pháp Gauss Xem Nhiều Nhất, Mới Nhất 2/2023 # Top Trend | Sansangdethanhcong.com

Giải Pháp Của Ma Trận Bằng Phương Pháp Gauss Jordan. Giải Hệ Phương Trình Tuyến Tính Bằng Phương Pháp Gauss

Chủ đề 7 “CÁC HỆ THỐNG THIẾT BỊ ĐẠI SỐ TUYẾN TÍNH. PHƯƠNG PHÁP GAUSS – JORDAN. “

(Kỷ luật học tập “Giới thiệu về Đại số tuyến tính và Hình học Giải tích”)

CÁC HỆ THỐNG THIẾT BỊ ĐẠI SỐ TUYẾN TÍNH. PHƯƠNG PHÁP GAUSS – JORDAN. Các khái niệm cơ bản

Một phương trình với n biến được gọi là tuyến tínhnếu tất cả các biến ( x 1 , x 2 , … x n ) được đưa vào nó ở mức độ 1. Dạng tổng quát của một phương trình như vậy được viết chính thức như sau:

=b.

Bằng cách giải phương trình tuyến tính (*),,…,) giá trị của các biến, khi được thay thế vào phương trình (tức là khi x j được thay bằng với tất cả jtừ 1do n biến nó thành bản sắc. Chúng tôi nhấn mạnh rằng nghiệm của một phương trình có n biến luôn là một bộ n số và mỗi bộ n số như vậy là một điều phán quyết. Rõ ràng, nếu ít nhất một hệ số của các biến không bằng 0 thì phương trình (*) có nghiệm. Nếu không, nghiệm chỉ tồn tại với b u003d 0 và đây là tất cả các bộ n số tùy ý.

Xét đồng thời m phương trình có dạng (*), tức là hệ thốngm phương trình đại số tuyến tính vớin biến… Cho mỗi phương trình thứ i, i u003d 1,2,…, m, được cho bởi các hệ số của các biến a i 1, a i 2,…, a in và một số hạng tự do b i, tức là có hình thức

Khi đó, ở dạng tổng quát, hệ gồm m phương trình đại số tuyến tính với n biến có thể được viết dưới dạng:

………………………………………………………………………………

…………………………………………………

hoặc, giống nhau,

=b tôi , tôi = 1,…, m.

Nếu tất cả các số hạng tự do đều bằng 0, thì hệ thống (1) được gọi là đồng nhất, I E. có hình thức

= 0,tôi = 1,…, m, (1 0 )

nếu không thì – không đồng nhất… Hệ thống (1 0 ) là một trường hợp đặc biệt của hệ thống chung (1) .

Bằng cách giải hệ phương trình (1) được gọi là một tập hợp có thứ tự ( ,,…,) giá trị của các biến, khi được thay thế vào các phương trình của hệ (1) (tức là khi x j được thay bằng , j u003d 1,…, n) tất cả chuyển đổi các phương trình này thành danh tính, tức là u003d b i với mọi i u003d 1,…, m.

Hệ phương trình (1) được gọi là chung,nếu cô ấy có ít nhất một giải pháp. Nếu không, hệ thống được gọi là không nhất quán.

Tập hợp tất cả các nghiệm của hệ phương trình (1) sẽ được gọi là nhiều giải pháp của nó và ký hiệu X b (X 0 nếu hệ là thuần nhất). Nếu hệ thống không nhất quán, thì X b u003d .

Nhiệm vụ chính của lý thuyết về hệ phương trình đại số tuyến tính là tìm xem liệu hệ (1) có nhất quán hay không và nếu có thì mô tả tập hợp tất cả các nghiệm của nó. Có những phương pháp phân tích các hệ thống như vậy cho phép bạn mô tả tập hợp tất cả các giải pháp trong trường hợp các hệ thống chung hoặc để đảm bảo rằng chúng không tương thích với nhau. Một phương pháp phổ biến như vậy là phương pháp loại bỏ hoàn toàn tuần tự các ẩn số hoặc phương phápGauss – Jordanmà chúng ta sẽ nghiên cứu chi tiết.

Trước khi tiếp tục mô tả phương pháp Gauss – Jordan, chúng tôi trình bày một số định nghĩa và phát biểu hữu ích cho những gì sau đây.

Hai hệ phương trình được gọi là tương đương nếu họ có cùng một tập hợp các giải pháp. Nói cách khác, mọi giải pháp cho hệ thống này là giải pháp cho hệ thống khác và ngược lại. Tất cả các hệ thống không tương thích được coi là tương đương.

Các định nghĩa về sự tương đương và tập nghiệm của các hệ có dạng (1) ngay lập tức hàm ý tính đúng đắn của các khẳng định sau đây, mà chúng ta xây dựng thành một định lý.

Định lý 1.Nếu hệ (1) chứa một phương trình với sốk, 1k m, như vậy màa kj = 0 jsau đó

Tính hợp lệ của các khẳng định của định lý trở nên hiển nhiên nếu chúng ta nhận thấy rằng phương trình thứ k có dạng

Định lý 2.Nếu ta thêm vào một phương trình của hệ (1) một phương trình khác cùng hệ, nhân với một số bất kỳ, thì ta được một hệ phương trình tương đương với hệ ban đầu.

Chứng cớ. Ví dụ, chúng ta hãy nhân phương trình thứ hai của hệ (1) với một số và thêm nó vào phương trình đầu tiên. Kết quả của phép biến đổi này, chúng ta thu được hệ (1 ‘), trong đó tất cả các phương trình, bắt đầu từ phương trình thứ hai, không thay đổi và phương trình thứ nhất có dạng sau

= b 1 + b 2 .

Rõ ràng, nếu một số bộ ( ,,…,) của các giá trị của biến biến tất cả các phương trình của hệ (1) thành đồng nhất, sau đó nó biến tất cả các phương trình của hệ (1 ‘) thành đồng nhất. Ngược lại, nghiệm (x ‘1, x’ 2,…, x ‘j,…, x’ n) của hệ (1 ‘) cũng là nghiệm của hệ (1), vì hệ (1) nhận được từ hệ (1’) sử dụng một phép biến đổi tương tự, khi phương trình thứ hai của hệ (1 ‘) được thêm vào phương trình thứ nhất của hệ (1’), nhân với số (- ).

Phát biểu sau đây được chứng minh theo cách tương tự.

Định lý 2 ‘. Phép nhân một phương trình tùy ý của hệ (1) với bất kỳ số nào khác 0 biến hệ (1) thành một hệ phương trình tương đương.

Định lý 2 và 2 ‘cho hai loại biến đổi, hệ thống nào (1) đã phải chịu, trong khi vẫn còn tương đương:

và) phép nhân (hoặc chia) một phương trình tùy ý của hệ (1) với bất kỳ số nào khác 0;

b) cộng (hoặc trừ) với một phương trình của một phương trình khác, nhân với một số.

Các phép biến đổi a) và b) như vậy được gọi là biến đổi cơ bản hệ phương trình (1).

Nếu các phép biến đổi cơ bản được áp dụng cho hệ phương trình (1) nhiều lần, thì hệ quả hiển nhiên cũng sẽ tương đương với hệ phương trình ban đầu.

Hệ phương trình (1) có thể được viết dưới dạng bảng:

Một bảng số hình chữ nhật bao gồm các hệ số a ij cho các ẩn số của hệ (1) được gọi là ma trận hệ thống (1) và được ký hiệu là A (nó chứa m hàng và n cột), cột các thành viên tự do được ký hiệu là b. Một bảng hình chữ nhật bao gồm các hệ số a ij cho các ẩn số và từ một cột các số hạng tự do b của hệ thống (1) được gọi là ma trận mở rộnghệ thống (1) và được ký hiệu là (nó chứa m hàng và (n + 1) cột), tức là u003d (A, b). Trong hàng thứ i của ma trận chứa tất cả nổi danh các tham số đặc trưng cho phương trình thứ i của hệ (1), i u003d 1,…, m. Cột thứ j của ma trận A chứa tất cả các hệ số của x j chưa biết xảy ra trong hệ (1).

Các số a ij được gọi là yếu tố ma trận A. Phần tử a ij nằm ở hàng thứ i và trong cột thứ j của ma trận A. Thông thường người ta nói rằng phần tử a ij là ở ngã tưtôi – dòng oh vàj – cột thứ của ma trậnA. Nếu tất cả các phần tử của một hàng (cột) của ma trận A (trừ một) đều bằng 0 và một phần tử khác không bằng một, thì một hàng (cột) như vậy được gọi là Độc thân (Độc thân).

Các phép biến đổi cơ bản sau đây của bảng (2) tương ứng với các phép biến đổi cơ bản của hệ (1):

và) phép nhân (hoặc chia) tất cả các phần tử của một hàng tùy ý trong bảng (2) với bất kỳ số nào khác 0,

b) cộng (hoặc trừ) với một dòng (từng phần tử) của dòng khác, nhân với một số.

Phương pháp loại bỏ hoàn toàn tuần tự các ẩn số (Phương pháp Gauss-Jordan)

Kết quả của bất kỳ biến đổi cơ bản nào, chúng tôi nhận được bàn mới, trong đó thay vì dòng mà họ đã thêm vào (hoặc nhân với bất kỳ số nào khác 0), hãy viếtdòng mớivà các dòng còn lại (kể cả dòng đã được thêm vào) được viết không thay đổi… Bảng mới tương ứng với hệ phương trình, hệ thống ban đầu tương đương.

Áp dụng các phép biến đổi cơ bản, bảng (2) và theo đó, hệ thống (1) có thể được đơn giản hóa để việc giải hệ ban đầu trở nên dễ dàng. Phương pháp được đề xuất dựa trên điều này.

Phương pháp loại bỏ hoàn toàn liên tiếp các ẩn số, hoặc phương pháp Gauss-Jordan, là một phương pháp phổ biến để phân tích bất kỳ hệ phương trình đại số tuyến tính nào (chưa được biết trước, tương thích hay không tương thích). Nó cho phép bạn giải quyết các hệ thống chung hoặc xác minh tính không nhất quán của các hệ thống không nhất quán.

Lưu ý sự khác biệt cơ bản giữa phương pháp được đề xuất để giải hệ phương trình đại số tuyến tính so với phương pháp giải một phương trình bậc hai chuẩn. Nó được giải bằng cách sử dụng các công thức nổi tiếng, trong đó các ẩn số được biểu diễn thông qua các hệ số của phương trình. Trong trường hợp hệ phương trình đại số tuyến tính tổng quát, chúng ta không có công thức nào như vậy và sử dụng để tìm nghiệm phương pháp lặp lại, hoặc là phương pháp lặp lại, hoặc là phương pháp lặp lại… Các phương pháp như vậy không xác định công thức, mà là một chuỗi các hành động.

Phương pháp Gauss – Jordan là một triển khai tuần tự của chuỗi các bước lớn cùng loại (hoặcsự lặp lại). Phương pháp lặp cụ thể này là một trong nhiều phương pháp lặp được đề xuất bởi cho nghiệm của hệ phương trình đại số tuyến tính dạng (1). Nó bao gồm giai đoạn đầu, giai đoạn chính và giai đoạn cuối cùng… Giai đoạn chính chứa lặp đi lặp lại lần lặp là tập hợp các hành động cùng kiểu.

Giai đoạn đầu tiên bao gồm việc xây dựng bảng I (0) của biểu mẫu (2) và sự lựa chọn trong đó yếu tố hàng đầu– bất kỳ nonzero nàohệ số cho các biến từ bảng (2). Cột và hàng tại giao điểm đặt trụ được gọi là dẫn đầu… (Cho phần tử a i 0 j 0 được chọn. Khi đó i 0 là hàng đầu, j 0 là cột đứng đầu.) Chuyển đến màn hình chính. Lưu ý rằng trục xoay thường được gọi là dễ dãi.

Chuyển đổi cột hàng đầu (tức là cột chứa phần tử tổng hợp) thành đơn vịvới 1 ở vị trí của trục bằng cách tuần tự trừ đi hàng đầu (tức là hàng chứa phần tử đứng đầu) nhân với một số số từ các hàng còn lại trong bảng. Chinh no hàng đầu được chuyển đổi bằng cách chia nó thành phần tử bởi trục quay.

Một bảng mới I (k) được viết, (k là số lặp), trong đó tất cả các cột từng dẫn đầu đều là cột duy nhất.

Kiểm tra xem có thể chọn trong bảng I (k) hay không phần tử hàng đầu (phân giải) mới.Theo định nghĩa thì nó là bất kỳ phần tử nào khác không nằm ở giao điểm của một hàng và một cột vẫn còn.

Sân khấu chính gồm các dãy lặp cùng kiểu với các số k u003d 1, 2,…. Hãy để chúng tôi mô tả chi tiết các bước lặp của phương pháp Gauss – Jordan.

Khi bắt đầu mỗi lần lặp, một bảng I nhất định có dạng (2) được biết đến; phần tử đứng đầu (phân giải) và theo đó, cột đứng đầu và hàng đứng đầu được chọn trong đó. Ngoài ra, có thông tin về những hàng và cột đã từng ở dẫn đầu. (Vì vậy, ví dụ: sau giai đoạn đầu, tức là ở lần lặp 1, I (0) đã biết, phần tử đứng đầu (phân giải) a i 0 j 0 và i 0 là hàng đầu, j 0 là cột dẫn đầu.)

Nếu lựa chọn như vậy là có thể, thì cột và hàng, tại giao điểm có phần tử đứng đầu (cho phép), được gọi là dẫn đầu… Sau đó, phép lặp được lặp lại với một bảng mới I (k), tức là các bước từ 1 đến 3 được lặp lại với một bảng I (k) mới. Trong trường hợp này, một bảng mới I (k +1) được xây dựng.

Nếu không thể chọn một phần tử tổng hợp mới, sau đó tiến hành bước cuối cùng.

Giai đoạn cuối cùng. Để thực hiện r lặp lại, thu được bảng I (r), bao gồm ma trận các hệ số cho các biến A (r) và một cột các số hạng tự do b (r), và trong đó không thể chọn một trục mới, tức là phương pháp đã dừng… Lưu ý rằng phương pháp bắt buộco sẽ dừng lại cho số bước hữu hạn từ r không được lớn hơn min (m, n).

Các tùy chọn để dừng phương pháp là gì? Ý bạn là gì “không thể chọn một trục mới”? Điều này có nghĩa là sau lần lặp thứ r trong ma trận A (r) của một hệ thống mới tương đương với hệ thống (1),

a) tất cả các dòng A (r) đều dẫn đầu, tức là mỗi dòng chứa một và chính xác một đơn vị, không còn đứng ở dòng nào khác,

b) có các chuỗi trong A (r), chỉ bao gồm các số không.

Hãy xem xét các tùy chọn này.

a) Trong trường hợp này r u003d m, m n. Bằng cách sắp xếp lại các hàng và đánh số lại các biến (tức là sắp xếp lại các cột), chúng ta có thể biểu diễn bảng I (r) là

Chúng tôi nhấn mạnh rằng trong bảng (3) mỗi biến có số i không vượt quá r chỉ xảy ra trong một hàng. Bảng (3) tương ứng với một hệ phương trình tuyến tính có dạng

x 1 + u003d b (r) 1,

x 2 + u003d b (r) 2,

………………………, (4)

x r + u003d b (r) r,

trong đó mỗi biến với số i, không cao cấpr, được biểu diễn duy nhất dưới dạng các biến x r + 1,…, x n, các hệ số của ma trận a (r) ij, j u003d r + 1,…, n và số hạng tự do b (r) i được trình bày trong bảng (3). Trên các biến x r +1 , … , x n không chồng chéo không hạn chế, I E. họ đang có thể nhận bất kỳ giá trị nào. Do đó, một giải pháp tùy ý cho hệ thống được mô tả bởi bảng (3), hoặc, tương tự, một giải pháp tùy ý cho hệ thống (4), hoặc, tương tự, một nghiệm tùy ý cho hệ thống (1) có dạng

x i u003d b (r) i – a (r) ij x j, i u003d 1,…, r u003d m; x j – bất kỳ với j u003d (r + 1),…, n. (số năm)

Sau đó, tập hợp các giải pháp cho hệ thống (1) có thể được viết dưới dạng

X b u003d (x u003d (x 1, …, x n): x i u003d b (r) i – a (r) ij x j với i u003d 1,…, r u003d m; x j – bất kỳ với j u003d (r + 1),…, n.).

Nếu b (r) k tương ứng bằng 0, thì phương trình thứ k là thừa và có thể bị loại bỏ. Loại bỏ tất cả các phương trình như vậy, chúng ta thấy rằng hệ (1) tương đương với hệ từ r phương trình với n biến, được viết sau r bước bằng bảng có dạng (3), trong đó tất cả các hàng đều đứng đầu. Như vậy, chúng ta đã đến trường hợp a) đã xét ở trên và có thể viết ra một nghiệm ở dạng (5).

Phương pháp Gauss – Jordan được mô tả đầy đủ. Mỗi số lần lặp lại hữu hạn hệ phương trình đại số tuyến tính sẽ được giải (nếu nó tương thích) hoặc hiển nhiên là nó không tương thích (nếu nó thực sự không tương thích).

Các biến tương ứng với các phần tử đứng đầu (cho phép)hoặc đứng trong các cột đầu tiên, theo thói quen gọi căn bảnvà phần còn lại của các biến là miễn phí.

1) Khi chúng ta bắt đầu giải một hệ thống bằng phương pháp Gauss-Jordan, chúng ta có thể không biết liệu hệ thống này có nhất quán hay không. Phương pháp Gauss – Jordan cho một số lần lặp hữu hạn r sẽ trả lời câu hỏi này. Trong trường hợp là một hệ thống chung, giải pháp chung của hệ thống ban đầu được viết ra trên cơ sở của bảng cuối cùng. Trong trường hợp này số lượng biến cơ bản nhất thiết phải bằng số r của lần lặp cuối cùng, tức là số lần lặp được thực hiện. Số r luôn không vượt quá min (m, n), với m là số phương trình trong hệ, và n – số lượng biến hệ thống. Nếu r< n, sau đó (n – r) bằng số biến tự do.

2) Khi ghi lại một quyết định chung không cần thiết đánh số lại các biến như đã làm để dễ hiểu khi mô tả Giai đoạn cuối cùng. Đây là để hiểu rõ hơn.

3) Khi giải hệ (1) bằng phương pháp Gauss – Jordan căn bản các biến sẽ chỉ là các biến tương ứng với các cột mà tại một số lần lặp lại hoạt động như dẫn đầu và ngược lại, nếu tại một số lần lặp, cột đóng vai trò là cột đứng đầu, thì biến tương ứng nhất thiết sẽ nằm trong số các biến cơ bản.

4) Nếu nghiệm tổng quát của hệ (1) chứa ít nhất một biến tự do, thì hệ này có vô số nghiệm riêng nhưng nếu không có biến tự do thì hệ có nghiệm duy nhất trùng với nghiệm chung.

5) Các phần tử hàng đầu có thể được chọn trong mỗi lần lặp theo một cách khác nhau. Điều quan trọng duy nhất là đây là các hệ số khác không ở giao điểm của một hàng và một cột, mà trước đây không đứng đầu. Nhiều lựa chọn các yếu tố hàng đầu có thể cho các mục khác nhau nhiều giải pháp. Nhưng, bản thân tập hợp các giải pháp là giống nhau cho bất kỳ bản ghi nào.

Hãy để chúng tôi giải thích phương pháp bằng cách sử dụng các ví dụ.

Ví dụ I. Giải hệ phương trình đại số tuyến tính sau

bằng phương pháp loại bỏ hoàn toàn ẩn số liên tiếp (phương pháp Gauss – Jordan).

Giai đoạn đầu tiên. Đầu tiên, chúng ta viết hệ phương trình (6) ở dạng thuận tiện hơn – dưới dạng bảng I (0).

Đối với mỗi hệ phương trình tuyến tính, chúng tôi gán ma trận mở rộng thu được bằng cách tham gia ma trận VÀ cột thành viên miễn phí:

Jordan – phương pháp Gauss áp dụng cho giải pháp hệ thống mphương trình tuyến tính với n các loài chưa biết:

Phương pháp này bao gồm thực tế là với sự trợ giúp của các phép biến đổi cơ bản, hệ phương trình được rút gọn thành một hệ phương trình tương đương với một ma trận của một loại nhất định.

Chúng tôi thực hiện các phép biến đổi cơ bản sau trên các hàng của ma trận mở rộng:

1. hoán vị của hai dòng;

2. nhân một chuỗi với bất kỳ số nào khác 0;

3. thêm vào một dòng một dòng khác nhân với một số;

4. loại bỏ hàng rỗng (cột).

Ví dụ 2.11. Giải hệ phương trình tuyến tính bằng phương pháp Jordan – Gauss:

và) X 1 + X 2 + 2X 3 u003d -1

2X 1 – X 2 + 2X 3 u003d -4

4X 1 + X 2 + 4X 3 u003d -2

Giải pháp: Hãy tạo một ma trận mở rộng:

Lặp lại 1

Chọn một phần tử làm phần tử hướng dẫn. Hãy chuyển đổi cột đầu tiên thành một. Để làm điều này, hãy thêm dòng đầu tiên vào dòng thứ hai và thứ ba, nhân với (-2) và (-4), tương ứng. Chúng tôi nhận được ma trận:

Điều này hoàn thành lần lặp đầu tiên.

Chọn phần tử hướng dẫn. Từ đó ta chia dòng thứ hai cho -3. Sau đó, chúng tôi nhân hàng thứ hai tương ứng với (-1) và 3, rồi cộng nó vào hàng thứ nhất và thứ ba tương ứng. Chúng tôi nhận được ma trận

Chọn phần tử hướng dẫn. Từ đó ta chia dòng thứ ba cho (-2). Chuyển đổi cột thứ ba thành một. Để thực hiện việc này, hãy nhân hàng thứ ba với (-4/3) và (-2/3), rồi cộng nó vào hàng thứ nhất và thứ hai, tương ứng. Chúng tôi nhận được ma trận

Sau khi hoàn thành giải pháp, ở giai đoạn huấn luyện, cần thực hiện kiểm tra bằng cách thay thế các giá trị tìm được vào hệ thống ban đầu, các giá trị này sẽ chuyển thành các giá trị bằng nhau.

b) X 1 – X 2 + X 3 – X 4 u003d 4

X 1 + X 2 + 2X 3 + 3X 4 u003d 8

2X 1 + 4X 2 + 5X 3 + 10X 4 u003d 20

2X 1 – 4X 2 + X 3 – 6X 4 u003d 4

Giải pháp: Ma trận mở rộng trông giống như:

Áp dụng các phép biến đổi cơ bản, chúng ta nhận được:

Hệ ban đầu tương đương với hệ phương trình sau:

X 1 – 3X 2 – 5X 4 u003d 0

2X 2 + X 3 + 4X 4 u003d 4

Hai hàng cuối cùng của ma trận A (2) phụ thuộc tuyến tính.

Định nghĩa.Hàng ma trận e 1 , e 2 ,…, e m được gọi là phụ thuộc tuyến tính nếu đồng thời có các số không bằng 0 sao cho kết hợp tuyến tính của các hàng ma trận bằng hàng 0:

Ở đâu 0 u003d (0, 0 … 0). Các hàng ma trận là độc lập tuyến tính khi kết hợp của các chuỗi này bằng 0 nếu và chỉ khi tất cả các hệ số bằng 0.

Trong đại số tuyến tính, khái niệm thứ hạng của ma trận từ nó đóng một vai trò rất quan trọng trong việc giải hệ phương trình tuyến tính.

Định lý 2.3 (về hạng của ma trận). Thứ hạng của ma trận bằng số lượng tối đa các hàng hoặc cột độc lập tuyến tính của nó, qua đó tất cả các hàng (cột) khác của nó được biểu diễn tuyến tính.

Xếp hạng ma trận A (2) bằng 2, bởi vì số hàng độc lập tuyến tính tối đa trong nó là 2 (đây là hai hàng đầu tiên của ma trận).

Định lý 2.4 (Kronecker – Capeli). Hệ phương trình tuyến tính là nhất quán và chỉ khi hạng của ma trận của hệ bằng hạng của ma trận mở rộng của hệ này.

1. Nếu thứ hạng của ma trận của hệ thống tương thích bằng số biến, tức là r u003d n thì hệ có nghiệm duy nhất.

2. Nếu hạng của ma trận của hệ thống nhỏ hơn số biến, tức là r< n, то система неопределённая и имеет бесконечное множество решений.

Trong trường hợp này, hệ thống có 4 biến và hạng của nó là 2, do đó, nó có vô số nghiệm.

Định nghĩa.Để cho được r< n, r biến x 1 , x 2 ,…, x r được gọi là căn bảnnếu định thức của ma trận các hệ số của chúng ( cơ sở nhỏ) là nonzero. Nghỉ ngơi n – r các biến được gọi là miễn phí.

Định nghĩa.Phán quyết hệ thống trong đó tất cả n – r các biến miễn phí bằng 0, được gọi là căn bản.

Hệ thống chung m phương trình tuyến tính với nbiến ( m< n ) có vô số nghiệm, trong đó có vô số nghiệm cơ bản, không vượt quá, ở đâu.

Trong trường hợp của chúng tôi, tức là hệ thống có không quá 6 giải pháp cơ bản.

Giải pháp chung là:

X 1 u003d 3X 2 + 5X 4

X 3 u003d 4 – 2X 2 – 4X 4

Hãy lấy một giải pháp cơ bản khác. Đối với điều này, chúng tôi lấy X 3 và X 4 là ẩn số miễn phí. Hãy biểu diễn các ẩn số X 1 và X 2 thông qua các ẩn số X 3 và X 4:

X 1 u003d 6 – 3 / 2X 2 – X 4

X 2 u003d 2 – 1 / 2X 3 – 2X 4.

Khi đó nghiệm cơ bản có dạng: (6, 2, 0, 0).

Ví dụ 2.12. Giải quyết hệ thống:

X 1 + 2X 2 – X 3 u003d 7

2X 1 – 3X 2 + X 3 u003d 3

4X 1 + X 2 – X 3 u003d 16

Giải pháp: Ta biến đổi ma trận mở rộng của hệ thống

Vì vậy, phương trình tương ứng với hàng thứ ba của ma trận cuối cùng là không nhất quán – dẫn đến sai đẳng thức 0 u003d -1, do đó, hệ thống này không nhất quán. Kết luận này cũng có thể nhận được nếu chúng ta nhận thấy rằng hạng của ma trận hệ thống là 2, trong khi hạng của ma trận mở rộng của hệ thống là 3.

4. Phương pháp Jordan-Gauss.

Như bạn đã biết, hệ phương trình đại số tuyến tính có thể có một nghiệm, nhiều nghiệm hoặc hệ không nhất quán. Với các phép biến đổi cơ bản của các phần tử của ma trận của hệ thống, các trường hợp này được phát hiện như sau:

1. Trong quá trình loại bỏ, vế trái của phương trình bậc I của hệ biến mất, và vế phải bằng một số nào đó khác 0. những, cái đó. 02 + u003d bc0.

Điều này có nghĩa là hệ thống không có nghiệm, vì không có giá trị nào của ẩn số có thể thỏa mãn phương trình bậc I;

2. Vế trái và vế phải của phương trình bậc I biến mất. Điều này có nghĩa là phương trình thứ I là một tổ hợp tuyến tính của các phương trình khác, nó được thỏa mãn bởi bất kỳ nghiệm nào tìm được của hệ, vì vậy nó có thể bị loại bỏ. Trong hệ, số ẩn số lớn hơn số phương trình và do đó, hệ đó có nhiều nghiệm;

3. Sau khi dùng tất cả các phương trình để loại bỏ ẩn số ta thu được nghiệm của hệ.

Do đó, mục tiêu cuối cùng của phép biến đổi Jordan-Gauss là thu được từ một hệ thống tuyến tính đã cho

a11x1 + a12x2 +… + a1nxn u003d b1, n + 1

am1x1 + am2x2 +… + amnxn u003d bm.n + 1

Ở đây x1, x2,…, xn là các ẩn số cần xác định. a11, a12,…, amn là các hệ số của hệ – và b1, b2,… bm – các số hạng tự do – được giả định là đã biết. Chỉ số của các hệ số (aij) của hệ thống cho biết các số của phương trình (i) và ẩn số (j) mà tại đó hệ số này tương ứng.

Hệ (1) được gọi là thuần nhất nếu tất cả các số hạng tự do của nó bằng 0 (b1 u003d b2 u003d… u003d bm u003d 0), ngược lại nó là không thuần nhất.

Hệ (1) được gọi là bình phương nếu số m phương trình bằng số n ẩn số.

Lời giải cho hệ (1) là một tập hợp n số c1, c2,…, cn, sao cho việc thay thế mỗi ci thay cho xi trong hệ (1) biến tất cả các phương trình của nó thành đồng nhất.

Hệ thống (1) được gọi là nhất quán nếu nó có ít nhất một giải pháp và không tương thích nếu nó không có giải pháp.

Một hệ thống liên kết dạng (1) có thể có một hoặc nhiều nghiệm.

Các nghiệm c1 (1), c2 (1),…, cn (1) và c1 (2), c2 (2),…, cn (2) của một hệ đồng dạng (1) được gọi là khác nếu có ít nhất một trong các bằng :

c1 (1) u003d c1 (2), c2 (1) u003d c2 (2),…, cn (1) u003d cn (2).

Một hệ thống liên kết dạng (1) được gọi là xác định nếu nó có một nghiệm duy nhất; nếu nó có ít nhất hai nghiệm khác nhau, thì nó được gọi là vô thời hạn. Nếu có nhiều phương trình hơn ẩn số, nó được gọi là quá xác định.

Hãy giải các hệ phương trình sau:

Chúng tôi viết nó dưới dạng ma trận 3 × 4, trong đó cột cuối cùng là một điểm chặn:

Hãy làm như sau:

· Thêm vào dòng 2: -4 * Dòng 1.

· Thêm vào dòng 3: -9 * Dòng 1.

· Thêm vào dòng 3: -3 * Dòng 2.

Chia dòng 2 cho -2

· Thêm vào dòng 1: -1 * Dòng 3.

· Thêm vào dòng 2: -3/2 * Dòng 3.

· Thêm vào dòng 1: -1 * Dòng 2.

Tính chất 1. Định thức sẽ không thay đổi giá trị của nó nếu các phần tử tương ứng của một hàng (cột) song song được thêm vào tất cả các phần tử của bất kỳ hàng (cột) nào của ma trận, nhân với một tùy ý và cùng một số. Tính chất 2. Khi hoán đổi bất kỳ hai cột hoặc hàng nào của ma trận, định thức của nó đổi dấu thành ngược lại và giá trị tuyệt đối của định thức không đổi.

Ở cột bên phải, chúng tôi nhận được giải pháp:

.

Gia tốc hội tụ của quá trình xấp xỉ được quan sát thấy trong phương pháp của Newton. 5. Phương pháp tiếp tuyến (Phương pháp Newton) Phương pháp tiếp tuyến gắn liền với tên tuổi của I. Newton là một trong những phương pháp số hữu hiệu để giải phương trình. Ý tưởng đằng sau phương pháp này rất đơn giản. Lấy điểm xuất phát x0 và viết phương trình tiếp tuyến của đồ thị hàm số f (x): y u003d f (x0) + f ¢ (x) (x-x0) (1.5) Đồ thị …

Giải pháp từ các phương pháp tính toán số. Để xác định gốc của phương trình, không cần kiến u200bu200bthức về lý thuyết của các nhóm Abel, Galois, Lie, v.v. và không cần thuật ngữ toán học đặc biệt: vành, trường, iđêan, đẳng cấu, v.v. Để giải một phương trình đại số bậc n, bạn chỉ cần có khả năng giải phương trình bậc hai và lấy nghiệm nguyên từ một số phức. Rễ có thể được xác định từ …

… “biểu hiện” chỉ trong quá trình biến đổi. Chúng tôi sẽ xem xét tính hiển nhiên và “tính che giấu” của biến mới bằng cách sử dụng các ví dụ cụ thể trong chương thứ hai của tác phẩm này. 2. Khả năng sử dụng phương pháp thay thế ẩn số khi giải phương trình đại số Trong chương này, chúng tôi sẽ trình bày các khả năng sử dụng phương pháp thay thế ẩn số khi giải phương trình đại số ở dạng chuẩn và không chuẩn …

phương pháp Gauss – Jordan là một trong những phương pháp nổi tiếng và được sử dụng rộng rãi nhất để giải hệ phương trình tuyến tính. Phương pháp ma trận và phương pháp Cramer có nhược điểm là chúng không đưa ra câu trả lời trong trường hợp detA u003d 0, nhưng chỉ xác định được một nghiệm duy nhất khi detA không bằng 0. Một nhược điểm khác là số lượng phép tính toán học trong các phương pháp này tăng mạnh với tăng số phương trình. Phương pháp Gauss thực tế không có những nhược điểm này.

Thuật toán phương pháp Gaussian

Dựa trên hệ phương trình tuyến tính, ta lập ma trận mở rộng của hệ;

Ta đưa ma trận về dạng “tam giác”;

Chúng tôi xác định cấp bậc của ma trận chính và ma trận mở rộng, và trên cơ sở này, chúng tôi đưa ra kết luận về tính tương thích của hệ thống và số lượng các giải pháp khả thi;

Nếu hệ có nghiệm duy nhất, ta thực hiện phép thay thế nghịch đảo và tìm, nếu hệ có tập nghiệm: ta biểu diễn các biến cơ bản dưới dạng biến có thể nhận giá trị tùy ý;

Để đưa ma trận mở rộng ban đầu về dạng tam giác, chúng ta sử dụng hai tính chất sau của các định thức:

Dựa trên các tính chất này của định thức, chúng tôi sẽ soạn một thuật toán để chuyển ma trận thành dạng tam giác:

Xét dòng i (bắt đầu bằng dòng đầu tiên). Nếu phần tử a i i bằng 0, chúng ta hoán đổi hàng thứ i và thứ i + của ma trận. Trong trường hợp này, dấu hiệu của định thức sẽ thay đổi thành ngược lại. Nếu 1 1 không phải là số khác, hãy chuyển sang bước tiếp theo;

Đối với mỗi hàng j, bên dưới hàng thứ i, chúng ta tìm giá trị của hệ số K j u003d a j i / a i i;

Chúng ta tính lại các phần tử của tất cả các hàng j nằm bên dưới hàng i hiện tại bằng cách sử dụng các hệ số thích hợp theo công thức: a j k new u003d a j k -K j * a i k; Sau đó, chúng ta quay lại bước đầu tiên của thuật toán và xem xét hàng tiếp theo cho đến khi chúng ta đến hàng i u003d n-1, trong đó n là số chiều của ma trận A

Trong ma trận tam giác kết quả, chúng tôi tính tích của tất cả các phần tử của đường chéo chính Pa i i, sẽ là định thức;

Nói cách khác, bản chất của phương pháp có thể được xây dựng như sau. Chúng ta cần làm cho tất cả các phần tử của ma trận nằm dưới đường chéo chính bằng 0. Đầu tiên chúng ta lấy các số không trong cột đầu tiên. Để thực hiện điều này, chúng ta tuần tự trừ dòng đầu tiên, nhân với số chúng ta cần (sao cho khi trừ chúng ta nhận được số 0 trong phần tử đầu tiên của dòng) từ tất cả các dòng bên dưới. Sau đó, chúng ta làm tương tự đối với hàng thứ hai để lấy các số không ở cột thứ hai bên dưới đường chéo chính của ma trận. Và tiếp tục như vậy cho đến khi chúng ta đi đến dòng áp chót.

Ngày xửa ngày xưa, nhà toán học người Đức Wilhelm Jordan (chúng tôi đang phiên âm sai từ tiếng ĐứcJordan trong vai Jordan) ngồi giải các hệ phương trình tiếp theo. Anh ấy thích làm điều đó và trong thời gian rảnh, anh ấy đã cải thiện kỹ năng của mình. Nhưng rồi cũng đến lúc anh cảm thấy nhàm chán với tất cả các phương pháp giải và phương pháp Gauss kể cả…

Giả sử một hệ có ba phương trình, ba ẩn số được đưa ra, và ma trận mở rộng của nó được viết. Trong trường hợp phổ biến nhất, các bước tiêu chuẩn được thực hiện và cứ như vậy hàng ngày…. Điều tương tự – như cơn mưa tháng mười một vô vọng.

Xua tan khao khát một thời cách khác Giảm ma trận về dạng bậc: hơn nữa, nó hoàn toàn tương đương và có thể không thuận tiện chỉ do nhận thức chủ quan. Nhưng sớm muộn gì mọi thứ cũng trở nên nhàm chán…. Và sau đó tôi nghĩ F trong khoảng rdan – tại sao phải bận tâm đến điều ngược lại của thuật toán Gaussian? Không phải dễ dàng hơn để có ngay câu trả lời với sự trợ giúp của các phép biến đổi sơ cấp bổ sung?

… vâng, điều này chỉ xảy ra cho tình yêu u003d)

Chà, và thật tuyệt vời nếu nó hoạt động thứ tự giảm dần của yếu tố quyết định.

Như mọi người đã hiểu, phương pháp Gauss-Jordan là một sửa đổi phương pháp Gauss và chúng ta sẽ gặp nhau ở các màn tiếp theo với việc triển khai ý tưởng chính đã được nói ở trên. Ngoài ra, trong số ít các ví dụ của bài viết này, ứng dụng quan trọng nhất đã được bao gồm: tìm ma trận nghịch đảo bằng cách sử dụng các phép biến đổi cơ bản.

Nếu không có thêm lời khuyên:

Giải hệ thống bằng phương pháp Gauss-Jordan

Phán quyết: đây là nhiệm vụ đầu tiên của bài Phương pháp Gauss cho hình nộm, nơi chúng tôi đã biến đổi ma trận mở rộng của hệ thống 5 lần và đưa nó về dạng bậc:

Bây giờ thay vì đảo ngược các phép biến đổi cơ bản bổ sung phát huy tác dụng. Đầu tiên, chúng ta cần lấy các số không tại các vị trí sau: , và sau đó là một số 0 khác ở đây: .

Một trường hợp lý tưởng về mặt đơn giản:

(6) Dòng thứ ba được thêm vào dòng thứ hai. Dòng thứ ba đã được thêm vào dòng đầu tiên.

(7) Dòng thứ hai nhân với -2 được thêm vào dòng đầu tiên.

Tôi không thể cưỡng lại việc minh họa hệ thống cuối cùng:

Câu trả lời:

Tôi cảnh báo độc giả chống lại tâm trạng run rẩy – đây là ví dụ demo đơn giản nhất. Phương pháp Gauss-Jordan có các kỹ thuật cụ thể riêng và không phải là các phép tính thuận tiện nhất, vì vậy hãy điều chỉnh để thực hiện nghiêm túc.

Tôi không muốn nghe có vẻ phân loại hay cầu kỳ, nhưng trong phần lớn các nguồn thông tin mà tôi đã thấy, các vấn đề điển hình được coi là cực kỳ tồi tệ – bạn cần phải có bảy nhịp và dành nhiều thời gian / căng thẳng cho một giải pháp khó xử với các phân số. Qua nhiều năm thực hành, tôi đã cố gắng đánh bóng, tôi sẽ không nói rằng kỹ thuật tốt nhất, nhưng hợp lý và khá dễ dàng có sẵn cho tất cả những ai sở hữu các phép toán số học:

Giải hệ phương trình tuyến tính bằng phương pháp Gauss-Jordan.

Phán quyết: Phần đầu tiên của bài tập quen thuộc:

(1) Dòng đầu tiên nhân với -1 được thêm vào dòng thứ hai. Dòng thứ ba được thêm vào dòng thứ nhất nhân với 3. Dòng đầu tiên được thêm vào dòng thứ tư, nhân với -5.

(2) Dòng thứ hai chia 2, dòng thứ ba chia 11, dòng thứ tư chia 3.

(3) Dòng thứ hai và dòng thứ ba tỷ lệ thuận, dòng thứ ba đã bị loại bỏ. Dòng thứ hai được thêm vào dòng thứ tư, nhân với -7

(4) Dòng thứ ba được chia cho 2.

Rõ ràng, hệ thống có vô số giải pháp, và nhiệm vụ của chúng ta là đưa ma trận mở rộng của nó về dạng .

Làm thế nào để tiếp tục? Trước hết, cần lưu ý rằng chúng ta đã mất một phép biến đổi cơ bản ngon lành – hoán vị hàng. Chính xác hơn, bạn có thể sắp xếp lại chúng, nhưng không có ích lợi gì trong việc này (chúng tôi chỉ thực hiện các hành động không cần thiết). Và sau đó, bạn nên tuân thủ các mô hình sau:

Ghi chú: thuật ngữ “cơ sở” có ý nghĩa và khái niệm đại số cơ sở hình học Nó không có gì để làm với nó!

Tìm thấy bội số chung nhỏ nhất các số trong cột thứ ba (1, -1 và 3), tức là – số nhỏ nhất chia hết cho 1, -1 và 3. Trong trường hợp này, tất nhiên, nó là “ba”. Hiện nay trong cột thứ ba, chúng ta cần lấy các số có cùng môđun và những cân nhắc này xác định phép biến đổi thứ 5 của ma trận:

(5) Hàng đầu tiên được nhân với -3, hàng thứ hai được nhân với 3. Nói chung, hàng đầu tiên cũng có thể được nhân với 3, nhưng sẽ không thuận tiện cho bước tiếp theo. Bạn nhanh chóng quen với những điều tốt đẹp:

(6) Dòng thứ ba được thêm vào dòng thứ hai. Dòng thứ ba đã được thêm vào dòng đầu tiên.

(7) Cột thứ hai có hai giá trị khác không (24 và 6) và một lần nữa chúng ta cần lấy các số modulo giống nhau… Trong trường hợp này, mọi thứ diễn ra khá tốt – bội số nhỏ nhất của 24 và cách hiệu quả nhất là nhân hàng thứ hai với -4.

(Rõ ràng là ma trận nghịch đảo phải tồn tại)

(8) Dòng thứ hai được thêm vào dòng đầu tiên.

(9) Lần chạm cuối cùng: dòng đầu tiên được chia cho -3, dòng thứ hai được chia cho -24 và dòng thứ ba được chia cho 3. Hành động này được thực hiện CUỐI CÙNG! Không có phân số sớm!

Kết quả của các phép biến đổi cơ bản, một hệ thống ban đầu tương đương đã thu được:

Chúng ta có thể đơn giản thể hiện các biến cơ bản dưới dạng biến tự do:

và viết:

Câu trả lời: quyết định chung:

Trong các ví dụ như vậy, việc áp dụng thuật toán được xem xét thường hợp lý nhất, vì chuyển động ngược lại phương pháp Gauss thường đòi hỏi các phép tính phân số tốn thời gian và khó chịu.

Đối với một giải pháp độc lập:

Tìm một giải pháp cơ bản bằng cách sử dụng các phép biến đổi cơ bản

Công thức của bài toán này giả định việc sử dụng phương pháp Gauss-Jordan, và trong dung dịch mẫu, ma trận được giảm xuống dạng chuẩn với các biến cơ bản. Tuy nhiên, hãy luôn ghi nhớ rằng các biến khác có thể được chọn làm biến cơ bản… Vì vậy, ví dụ, nếu các số trong cột đầu tiên là cồng kềnh, thì việc đưa ma trận về dạng (biến cơ bản) hoặc ở dạng (biến cơ bản), hoặc thậm chí cho biểu mẫu với các biến cơ bản. Ngoài ra còn có các tùy chọn khác.

Nhưng tất cả đều giống nhau, đây là những trường hợp cực đoan – bạn không nên gây sốc cho giáo viên một lần nữa với kiến u200bu200bthức, kỹ thuật giải và hơn thế nữa, bạn không nên đưa ra kết quả Jordan kỳ lạ như … Tuy nhiên, có thể khó để loại bỏ cơ sở không điển hình khi trong ma trận ban đầu, chẳng hạn, trong cột thứ 4, có hai số không sẵn sàng.

Nếu một cặp đột nhiên được tìm thấy trong ma trận kích thước mở rộng phụ thuộc tuyến tính thì bạn nên cố gắng đưa nó về dạng thông thường với các biến cơ bản. Một ví dụ về quyết định như vậy là trong Ví dụ số 7 của bài báo trên hệ phương trình tuyến tính thuần nhất, với chỗ ấy một cơ sở khác được chọn.

Chúng tôi tiếp tục cải thiện kỹ năng của mình đối với vấn đề được áp dụng sau:

Làm thế nào để tìm nghịch đảo của ma trận bằng phương pháp Gaussian?

Thông thường, điều kiện được xây dựng theo cách viết tắt, nhưng về bản chất, thuật toán Gauss-Jordan cũng hoạt động ở đây. Một phương pháp tìm kiếm dễ dàng hơn ma trận nghịch đảo cho một ma trận vuông mà chúng ta đã xem xét từ lâu trong bài học tương ứng, và trong tiết trời cuối thu khắc nghiệt, các học sinh đã nắm được cách giải thành thạo.

Tóm tắt các hành động sắp tới như sau: đầu tiên, bạn nên viết ma trận vuông song song với ma trận nhận dạng:. Sau đó, sử dụng các phép biến đổi cơ bản, cần có được ma trận đơn vị ở bên trái, trong khi (không đi vào chi tiết lý thuyết) ma trận nghịch đảo được vẽ ở bên phải. Giải pháp trông giống như sau:

Hãy tìm ma trận nghịch đảo cho ma trận bằng cách sử dụng các phép biến đổi sơ cấp. Để làm điều này, chúng tôi sẽ viết nó trong một đội với ma trận đơn vị và “hai con ngựa” đua:

(1) Dòng đầu tiên nhân với -3 được thêm vào dòng thứ hai.

(2) Dòng thứ hai được thêm vào dòng đầu tiên.

(3) Dòng thứ hai được chia cho -2.

Câu trả lời:

Kiểm tra câu trả lời từ bài học ví dụ đầu tiên Làm cách nào để tìm nghịch đảo của ma trận?

Nhưng đó là một nhiệm vụ hấp dẫn khác – trên thực tế, giải pháp này tốn thời gian và công sức hơn nhiều. Thông thường, bạn sẽ được trình bày với ma trận ba nhân ba:

Phán quyết: thêm ma trận nhận dạng và bắt đầu thực hiện các phép biến đổi, theo thuật toán “bình thường” phương pháp Gauss:

(1) Dòng đầu tiên và dòng thứ ba được đảo ngược. Thoạt nhìn, việc hoán vị các hàng có vẻ bất hợp pháp, nhưng trên thực tế, bạn có thể sắp xếp lại chúng – kết quả là bên trái chúng ta cần lấy ma trận nhận dạng và bên phải chúng ta sẽ “cưỡng chế” lấy chính xác ma trận (bất kể chúng ta có sắp xếp lại các dòng trong quá trình giải hay không)… Lưu ý rằng ở đây thay vì hoán vị, bạn có thể sắp xếp “sixes” trong cột đầu tiên (bội số phổ biến nhất (LCM) của 3, 2 và 1)… Giải pháp LCM đặc biệt hữu ích khi không có “cái nào” trong cột đầu tiên.

(2) Hàng thứ nhất được thêm vào hàng thứ 2 và thứ 3, nhân với -2 và -3, tương ứng.

(3) Hàng thứ 2 được thêm vào hàng thứ 3, nhân với -1

Phần thứ hai của giải pháp được thực hiện theo sơ đồ đã biết ở đoạn trước: các hoán vị hàng trở nên vô nghĩa, và chúng tôi tìm thấy bội số chung nhỏ nhất của các số trong cột thứ ba (1, -5, 4): 20. Có một thuật toán nghiêm ngặt để tìm LCM, nhưng thường có đủ lựa chọn. Không sao cả nếu bạn lấy một số lớn hơn chia hết cho 1, -5 và 4, chẳng hạn như số 40. Sự khác biệt sẽ nằm trong các phép tính phức tạp hơn.

Nói về máy tính. Để giải quyết vấn đề, không có gì đáng xấu hổ khi trang bị cho mình một chiếc máy tính vi mô – có những con số đáng kể ở đây, và sẽ rất khó chịu nếu mắc một lỗi tính toán.

(4) Dòng thứ ba nhân với 5, dòng thứ hai nhân 4, dòng thứ nhất nhân “trừ hai mươi”:

(5) Dòng thứ ba được thêm vào dòng thứ nhất và thứ hai.

(6) Dòng thứ nhất và dòng thứ ba đã chia cho 5, dòng thứ hai nhân với -1.

(7) Bội số chung nhỏ nhất của các số khác không ở cột thứ hai (-20 và 44) là 220. Hàng đầu tiên nhân với 11, hàng thứ hai nhân 5.

(8) Dòng thứ hai được thêm vào dòng đầu tiên.

(9) Dòng đầu tiên được nhân với -1, dòng thứ hai được chia “lùi” cho 5.

Giải pháp và câu trả lời: Ví dụ 3: Phán quyết: chúng tôi viết ra ma trận mở rộng của hệ thống và sử dụng các phép biến đổi cơ bản, chúng tôi thu được giải pháp cơ bản:Ví dụ 6: Phán quyết: tìm ma trận nghịch đảo bằng cách sử dụng các phép biến đổi cơ bản:Ví dụ 7: Phán quyết: tìm ma trận nghịch đảo bằng phương pháp Gauss-Jordan:(1) Hàng thứ 3 được thêm vào dòng thứ 1 và thứ 4.(2) Dòng đầu tiên và dòng thứ tư được đảo ngược.(3) Dòng thứ nhất được thêm vào dòng thứ hai. Dòng đầu tiên nhân với 2 được thêm vào dòng thứ 3:(4) Hàng thứ 2 được cộng với hàng thứ 3, nhân với -2. Dòng thứ 2 được thêm vào dòng thứ 4.(5) Hàng thứ 4, nhân với -1, được thêm vào dòng thứ nhất và thứ ba.(6) Dòng thứ hai nhân với -1, dòng thứ ba nhân với -2.Câu trả lời: (1) Hàng thứ nhất nhân với -15, hàng thứ hai nhân với 3, hàng thứ ba nhân với 5.(2) Dòng đầu tiên được thêm vào dòng thứ 2 và 3.(3) Dòng đầu tiên được chia cho -15, dòng thứ hai được chia bởi -3, dòng thứ ba được chia bởi -5.(4) Hàng thứ hai nhân với 7, hàng thứ ba nhân với -9.(5) Dòng thứ hai được thêm vào dòng thứ ba.(6) Dòng thứ hai được chia cho 7.(7) Hàng thứ nhất nhân với 27, hàng thứ hai nhân với 6, hàng thứ ba nhân với -4.(8) Dòng thứ ba được thêm vào dòng thứ nhất và dòng thứ hai.(9) Dòng thứ ba được chia cho -4. Dòng thứ hai nhân với -1 được thêm vào dòng đầu tiên.(10) Dòng thứ hai được chia cho 2.(11) Mỗi u200bu200bdòng được chia cho 27.Kết quả là: Câu trả lời: (1) Dòng thứ nhất và dòng thứ hai được đảo ngược.(2) Dòng đầu tiên nhân với -2 được thêm vào dòng thứ hai. Dòng thứ ba được thêm vào dòng đầu tiên nhân với 5.(3) Dòng thứ ba đã chia hết cho 3.(4) Hàng thứ hai cộng với hàng thứ ba, nhân với 2.(5) Dòng thứ ba được chia cho 7.(6) Bội số nhỏ nhất của cột thứ 3 (-3, 5, 1) là 15. Hàng thứ nhất nhân với 5, hàng thứ hai nhân với -3 và hàng thứ ba nhân với 15.(7) Dòng thứ ba đã được thêm vào dòng đầu tiên. Dòng thứ ba đã được thêm vào dòng thứ hai.(8) Dòng thứ nhất chia cho 5, dòng thứ hai chia cho -3, dòng thứ ba chia cho 15.(9) Bội số nhỏ nhất của các số khác không ở cột thứ 2 (-2 và 1) là: 2. Nhân hàng thứ hai với 2(10) Dòng thứ hai được thêm vào dòng đầu tiên.(11) Dòng thứ hai được chia cho 2.Chúng tôi biểu thị các biến cơ bản dưới dạng các biến tự do:Câu trả lời: quyết định chung:

(10) Bây giờ trên đường chéo chính của ma trận bên trái, bạn nên lấy bội số chung nhỏ nhất của đường chéo (44, 44 và 4). Rõ ràng là con số này là 44. Dòng thứ ba được nhân với 11.

(11) Chia mỗi hàng cho 44. Hành động này được thực hiện sau cùng!

Vậy nghịch đảo của ma trận là:

Về nguyên tắc, việc giới thiệu và loại bỏ -th là những hành động không cần thiết, nhưng điều này được yêu cầu bởi giao thức của nhiệm vụ.

Câu trả lời:

Những người tiên tiến có thể rút ngắn giải pháp phần nào, nhưng tôi phải cảnh báo bạn rằng, việc vội vàng ở đây đầy rủi ro mắc sai lầm TĂNG LÊN.

Một nhiệm vụ tương tự cho một giải pháp độc lập:

Tìm ma trận nghịch đảo bằng phương pháp Gauss-Jordan.

Mẫu gần đúng của nhiệm vụ ở cuối trang. Và vì lợi ích của việc “không trôi qua với các bài hát”, tôi đã thực hiện giải pháp theo phong cách đã được đề cập – độc quyền thông qua LCM của các cột mà không có hoán vị hàng đơn và các phép biến đổi nhân tạo bổ sung. Theo ý kiến u200bu200bcủa tôi, kế hoạch này, nếu không phải là nhất, thì một trong những kế hoạch đáng tin cậy nhất.

Đôi khi, rất tiện lợi khi sử dụng một giải pháp ngắn gọn hơn của “chủ nghĩa hiện đại”, như sau: trong bước đầu tiên, mọi thứ vẫn như bình thường: .

Ở bước thứ hai, bằng kỹ thuật gấp khúc (thông qua LCM của các số của cột thứ 2), hai số không được sắp xếp cùng một lúc trong cột thứ hai: … Đặc biệt khó có thể chống lại hành động này nếu các con số của cùng một mô-đun được vẽ ở cột thứ 2, ví dụ, cùng một “cái” thông thường.

Và cuối cùng, trong bước thứ ba, chúng ta nhận được các số không cần thiết trong cột thứ ba theo cách tương tự: .

Đối với số chiều, trong hầu hết các trường hợp, cần phải giải quyết ma trận “ba nhân ba”. Tuy nhiên, thỉnh thoảng có một phiên bản nhẹ của vấn đề với ma trận hai x hai và khó … – đặc biệt là đối với tất cả độc giả của trang web:

Tìm ma trận nghịch đảo bằng các phép biến đổi cơ bản

Đây là một bài tập từ bài kiểm tra toán và vật lý của chính tôi trong đại số, … ơ, khóa học đầu tiên của tôi ở đâu u003d) 15 năm trước (lá không chuyển sang màu vàng một cách đáng ngạc nhiên), Tôi đã làm điều đó trong 8 bước, và bây giờ – chỉ 6! Nhân tiện, ma trận rất sáng tạo – ngay từ bước đầu tiên, một số giải pháp hấp dẫn đã có thể nhìn thấy. Phiên bản sau của tôi nằm ở cuối trang.

Và một mẹo cuối cùng – sau những ví dụ như vậy, thể dục cho mắt và một số bản nhạc hay để thư giãn rất hữu ích u003d)

Phương Pháp Đơn Giản Để Giải Zlp. Phương Pháp Gauss

Các phép biến đổi trên được thực hiện một cách thuận tiện trong các bảng đặc biệt gọi là bảng đơn giản.

Các khối sau được phân bổ trong một bảng simplex:

Hãy viết lời giải cho vấn đề của ví dụ từ Phần 3.3 trong bảng đơn giản:

Tất cả dữ liệu ban đầu có trong điều kiện toán học của bài toán được chuyển sang bảng đơn giản đầu tiên. Loại bỏ các biến tự do, chúng tôi nhận được một kế hoạch tham khảo

Trong hàng cuối cùng của bảng đơn giản đầu tiên, chúng tôi viết tiêu chí ở dạng ẩn

Chúng tôi loại trừ biến cơ bản x 4 khỏi tiêu chí này, đưa tiêu chí về dạng

Để có giải pháp tối ưu, tất cả các ước tính phải không âm

Giải pháp không tối ưu vì có xếp hạng tiêu cực.

Các ước tính có thể được tính toán bằng công thức. Tích là vectơ hiện tại của ma trận điều kiện, sau đó ước lượng của biến tự do có thể được tính như là tích vô hướng của vectơ hệ số đối với các biến cơ bản bằng vectơ hiện tại của ma trận điều kiện trừ đi hệ số của hàm mục tiêu cho biến này. Vì vậy, chúng tôi nhận được giá trị

Cột giải quyết là cột có ước tính nhỏ nhất (nếu nhiệm vụ là tối đa). Và để chọn dòng phân giải, bạn cần tìm trong số tất cả các dòng, biến mà từ đó, giảm dần, nhanh chóng chuyển về 0.

Kết quả là, chúng tôi nhận được rằng cột phân giải là và hàng phân giải là. Điều này có nghĩa là một biến rời khỏi danh sách các biến cơ bản và một biến đi vào.

Giải pháp không tối ưu vì có đánh giá âm -2.

Giải pháp là tối ưu, bởi vì tất cả các điểm đều lớn hơn 0. Rõ ràng là không thể tăng được.

Quy tắc xây dựng bảng Simplex

Một bảng đơn giản được xây dựng cho một giải pháp tham chiếu.

Hãy để các giải pháp tham khảo. Bảng simplex cho giải pháp này là

Ma trận cơ sở B u003d (A 1, A 2, … A m)

· Đối với các biến cơ bản, ma trận hiện tại là đơn vị.

· Bất kỳ cột nào.

· Véc tơ của các phần bên phải của các ràng buộc.

Các ước lượng cho các biến tự do không bằng 0

Trong ô phía dưới bên phải – giá trị của tiêu chí

Các bước của phương pháp Simplex

1. Kiểm tra tính năng tối ưu ()

2. Nếu vậy thì giải pháp không phải là tối ưu. Sau đó chọn cột có số điểm tối thiểu. Hãy gọi nó là giải quyết.

3. Hàng phân giải được chọn theo tỷ lệ tối thiểu của các thành viên tự do với hệ số dương của cột phân giải. Biến cơ sở được thể hiện từ dòng này nằm ngoài danh sách biến cơ sở. Những, cái đó. x k đi ra ngoài và x s đi vào.

4. Bảng đơn giản hiện tại được chuyển đổi theo quy tắc sau:

Dòng phân giải được chia thành phần tử phân giải:

· Cột phân giải được thay thế bằng một cột duy nhất.

Tất cả các phần tử khác của bảng simplex có thể được tính toán lại theo quy tắc hình tứ giác:

Một tứ giác được xây dựng trên đường chéo nối phần tử được tìm kiếm với phần tử đang phân giải. Khi đó giá trị mới của phần tử bằng giá trị trước đó trừ tích của các phần tử trên đường chéo đối diện chia cho phần tử phân giải.

Hoặc, giá trị mới của một phần tử bằng tích của các phần tử trên đường chéo chính trừ đi tích của các phần tử trên đường chéo đối diện và tất cả giá trị này chia cho phần tử phân giải.

Chúng ta hãy xem xét lời giải của LPP theo phương pháp đơn giản và trình bày nó trong mối quan hệ với bài toán tối đa hóa.

1. Theo điều kiện của bài toán, mô hình toán học của nó được vẽ ra.

2. Mô hình đã biên dịch được chuyển sang dạng chuẩn. Trong trường hợp này, cơ sở với kế hoạch tham khảo ban đầu có thể được phân biệt.

3. Mô hình chính tắc của bài toán được viết dưới dạng một bảng đơn giản sao cho tất cả các số hạng tự do đều không âm. Nếu kế hoạch cơ sở ban đầu được chọn, thì hãy chuyển sang bước 5.

Bảng Simplex: phù hợp với hệ phương trình hạn chế và hàm mục tiêu ở dạng biểu thức được giải quyết so với cơ sở ban đầu. Dòng ghi các hệ số của hàm mục tiêu F được gọi là dòng F hay dòng của hàm mục tiêu.

4. Tìm thiết kế tham chiếu ban đầu bằng cách thực hiện các phép biến đổi simplex với các phần tử có độ phân giải dương tương ứng với các quan hệ simplex tối thiểu, và không tính đến dấu hiệu của các phần tử của hàng F. Nếu trong quá trình biến đổi gặp phải một chuỗi 0, tất cả các phần tử của chúng, ngoại trừ số hạng tự do, đều là số không, thì hệ phương trình hạn chế của bài toán là không tương thích. Nếu tồn tại một hàng 0 mà ngoài số hạng tự do không có phần tử dương nào khác thì hệ phương trình có giới hạn không có nghiệm không âm.

Việc giảm hệ thống (2.55), (2.56) đến một cơ sở mới sẽ được gọi là một phép biến đổi đơn giản. Nếu phép biến đổi simplex được coi là một phép toán đại số chính thức, thì có thể lưu ý rằng do kết quả của phép toán này, các vai trò được phân phối lại giữa hai biến có trong một hệ thống hàm tuyến tính nhất định: một biến từ phụ thuộc sang độc lập và biến kia, ngược lại, từ độc lập sang phụ thuộc. Một phép toán như vậy được gọi là bước khử Jordan trong đại số.

5. Kế hoạch cơ sở ban đầu được tìm thấy được điều tra để có tính tối ưu:

a) nếu không có phần tử âm nào trong hàng F (ngoài số hạng tự do) thì thiết kế là tối ưu. Nếu không có số 0, thì phương án tối ưu là phương án duy nhất; nếu có ít nhất một số 0 thì có vô hạn phương án tối ưu;

b) nếu hàng F chứa ít nhất một phần tử âm, tương ứng với một cột gồm các phần tử không dương, thì<

c) nếu có ít nhất một phần tử âm trong hàng F và có ít nhất một phần tử dương trong cột của nó, thì chúng ta có thể chuyển sang một phương án tham chiếu mới, gần với phương án tối ưu hơn. Để làm điều này, cột đã chỉ định phải được chỉ định là cho phép, bằng quan hệ đơn giản tối thiểu để tìm chuỗi cho phép và thực hiện một phép biến đổi đơn giản. Kiểm tra lại kế hoạch tham chiếu kết quả để có tính tối ưu. Quá trình được mô tả được lặp lại cho đến khi có được phương án tối ưu hoặc cho đến khi vấn đề không thể giải quyết được.

Cột các hệ số cho một biến được bao gồm trong cơ sở được gọi là phân giải. Do đó, việc chọn biến được đưa vào cơ sở (hoặc chọn cột phân giải) bởi phần tử âm của hàng F, chúng ta đảm bảo hàm F tăng.

Khó hơn một chút để xác định biến bị loại trừ khỏi cơ sở. Để thực hiện điều này, quan hệ của các phần tử tự do với các phần tử tích cực của cột phân giải được thực hiện (quan hệ như vậy được gọi là đơn giản) và trong số đó tìm thấy quan hệ nhỏ nhất, xác định dòng (phân giải) chứa biến bị loại trừ. Việc lựa chọn biến được loại trừ khỏi cơ sở (hoặc lựa chọn đường phân giải), theo quan hệ đơn giản tối thiểu, đảm bảo, như đã được thiết lập, tính tích cực của các thành phần cơ sở trong kế hoạch tham chiếu mới.

Trong bước 3 của thuật toán, giả định rằng tất cả các phần tử của cột thành viên tự do là không âm. Yêu cầu này là không cần thiết, nhưng nếu nó được đáp ứng, thì tất cả các phép biến đổi simplex tiếp theo chỉ được thực hiện với các phần tử phân giải tích cực, thuận tiện cho tính toán. Nếu có số âm trong cột thành viên tự do, thì phần tử phân giải được chọn như sau:

1) xem qua một hàng tương ứng với một số hạng tự do phủ định, ví dụ, một hàng t, và chọn bất kỳ phần tử phủ định nào trong đó, và cột tương ứng được coi là cột cho phép (chúng tôi giả định rằng các ràng buộc của vấn đề là tương thích);

2) tạo thành tỷ lệ giữa các phần tử của cột các phần tử tự do với các phần tử tương ứng của cột phân giải có cùng dấu (quan hệ đơn giản);

3) quan hệ đơn giản nhất được chọn. Nó sẽ xác định đường phân giải. Ví dụ: p -string;

4) tại giao điểm của cột và hàng phân giải, phần tử phân giải được tìm thấy. Nếu phần tử của chuỗi y đang phân giải, thì sau khi biến đổi simplex, phần tử tự do của chuỗi này sẽ trở thành số dương. Nếu không, bước tiếp theo là tham chiếu lại chuỗi t. Nếu bài toán có thể giải được, thì sau một số bước nhất định trong cột số hạng tự do sẽ không còn phần tử phủ định nào.

Tìm kế hoạch tham chiếu ban đầu, dạng chuẩn của LPP

Ý tưởng cải tiến tuần tự của giải pháp đã hình thành cơ sở của một phương pháp phổ quát để giải các bài toán lập trình tuyến tính – phương pháp simplex hoặc phương pháp cải tiến tuần tự của phương án.

Phương pháp simplex lần đầu tiên được đề xuất bởi nhà khoa học Mỹ J. Danzig vào năm 1949, nhưng ngay từ năm 1939, những ý tưởng của phương pháp này đã được phát triển bởi nhà khoa học Nga L.V. Kantorovich.

Phương pháp simplex, cho phép giải bất kỳ bài toán lập trình tuyến tính nào, là phổ biến. Hiện tại, nó được sử dụng để tính toán trên máy tính, tuy nhiên, các ví dụ đơn giản sử dụng phương pháp simplex có thể được giải bằng tay.

Để thực hiện phương pháp simplex – cải tiến nhất quán của giải pháp – cần phải nắm vững ba yếu tố cơ bản:

Một phương pháp để xác định bất kỳ giải pháp cơ bản có thể chấp nhận ban đầu cho một vấn đề;

Quy tắc chuyển đổi sang giải pháp tốt nhất (chính xác hơn, không phải là giải pháp tồi tệ nhất);

Tiêu chí để kiểm tra tính tối ưu của giải pháp tìm được.

Để sử dụng phương pháp simplex, bài toán lập trình tuyến tính phải được rút gọn về dạng chuẩn, tức là hệ thống các ràng buộc cần được biểu diễn dưới dạng phương trình.

Tài liệu mô tả đầy đủ chi tiết: tìm kế hoạch cơ sở ban đầu (giải pháp cơ sở khả thi ban đầu), cũng như – bằng phương pháp cơ sở nhân tạo, tìm kế hoạch cơ sở tối ưu, giải quyết vấn đề bằng cách sử dụng bảng đơn giản.

58. Định lý chính của phương pháp đơn giản.

???????????????????????????????????????????????????????????????????????

59. Tối ưu thay thế trong ZLP, suy biến trong ZLP.

Tính thoái hóa trong các bài toán lập trình tuyến tính

Xem xét phương pháp simplex, chúng tôi giả định rằng bài toán lập trình tuyến tính là không suy biến, tức là mỗi kế hoạch cơ sở chứa đúng m thành phần dương, trong đó m là số ràng buộc trong bài toán. Trong thiết kế tham chiếu suy biến, số thành phần tích cực ít hơn số ràng buộc: một số biến cơ bản tương ứng với thiết kế tham chiếu đã cho nhận giá trị bằng không. Sử dụng cách giải thích hình học cho trường hợp đơn giản nhất, khi n – m u003d 2 (số biến không cơ bản là 2), có thể dễ dàng phân biệt một bài toán suy biến với bài toán không suy biến. Trong bài toán suy biến, nhiều hơn hai đường thẳng cắt nhau tại một đỉnh của đa diện điều kiện, được mô tả bằng phương trình có dạng xi u003d 0. Điều này có nghĩa là một hoặc một số cạnh của đa giác điều kiện được quy ước thành một điểm. Tương tự, đối với n – m u003d 3 trong bài toán suy biến, có hơn 3 mặt phẳng xi u003d 0 cắt nhau tại một đỉnh. Theo giả thiết bài toán là không sinh

chỉ một giá trị được tìm thấy, được sử dụng để xác định chỉ số của vectơ điều kiện xuất phát từ cơ sở (suy ra từ số lượng các biến cơ bản). AT

vấn đề suy biến có thể đạt được ở một số chỉ số cùng một lúc (đối với một số hàng). Trong trường hợp này, một số biến cơ sở sẽ bằng 0 trong kế hoạch tham chiếu được tìm thấy. Nếu bài toán lập trình tuyến tính trở nên suy biến, thì với sự lựa chọn sai vectơ điều kiện xuất phát từ cơ sở, một chuyển động vô hạn dọc theo cơ sở của cùng một phương án tham chiếu có thể xảy ra. Đây được gọi là hiện tượng lặp lại. Mặc dù trong các vấn đề thực tế của lập trình tuyến tính lặp lại là khá hiếm, khả năng của nó không bị loại trừ. Một trong những phương pháp xử lý suy biến là biến đổi bài toán bằng cách thay đổi “không đáng kể” véc tơ của các vế phải của hệ các ràng buộc về giá trị để bài toán trở nên không suy biến, đồng thời để sự thay đổi này không thực sự ảnh hưởng đến phương án tối ưu của bài toán. Các thuật toán được triển khai phổ biến hơn bao gồm một số quy tắc đơn giản để giảm khả năng xảy ra hoặc vượt qua các vòng lặp. Để biến xj là cơ bản. Xem xét

tập hợp các chỉ số E0 bao gồm các chỉ số i đã đạt được. Tập hợp các chỉ số i thỏa mãn điều kiện này sẽ được ký hiệu là E0,. Nếu E0, bao gồm một phần tử, thì vectơ điều kiện Ai bị loại trừ khỏi cơ sở (biến xi được tạo thành không cơ bản). Nếu E0 bao gồm nhiều hơn một phần tử, thì tập E1 được bao gồm, bao gồm, mà nó đạt tới. Nếu E1 bao gồm một chỉ số k, thì biến xk được suy ra từ cơ sở. Nếu không, tập E2 được biên dịch, v.v. Trong thực tế, quy tắc nên được sử dụng nếu vòng lặp đã được phát hiện.

Tối ưu thay thế trong ZLP ???????????????????????????

60. Phương pháp cơ sở nhân tạo. Nhiệm vụ M. Định lý về mối liên hệ giữa các nghiệm của bài toán ban đầu và bài toán M.

Phương pháp cơ sở nhân tạo.

Phương pháp cơ sở nhân tạo được sử dụng để tìm một giải pháp cơ bản có thể chấp nhận được cho một bài toán lập trình tuyến tính khi điều kiện chứa các ràng buộc kiểu đẳng thức. Xem xét vấn đề:

Cái gọi là “biến nhân tạo” Rj được đưa vào các ràng buộc và hàm mục tiêu như sau:

∑ajix + Rj u003d bj, j u003d 1, m; F (x) u003d ∑cixi-M∑Rj

Khi các biến nhân tạo được đưa vào hàm mục tiêu trong phương pháp cơ sở nhân tạo, chúng được gán một hệ số M đủ lớn, điều này có nghĩa là một hình phạt cho việc đưa các biến nhân tạo vào. Trong trường hợp tối thiểu hóa, các biến nhân tạo được thêm vào hàm mục tiêu với hệ số M. Cho phép sử dụng các biến nhân tạo nếu chúng biến mất liên tục trong quá trình giải bài toán.

Một bảng đơn giản, được biên dịch trong quá trình giải bằng phương pháp cơ sở nhân tạo, được gọi là mở rộng. Nó khác với dòng thông thường ở chỗ nó chứa hai dòng cho hàm mục tiêu: một dòng cho thành phần F u003d ∑cixi và một dòng cho thành phần M ∑Rj Hãy xem xét quy trình giải bài toán bằng một ví dụ cụ thể.

Ví dụ 1. Tìm cực đại của hàm F (x) u003d -x1 + 2×2 – x3 theo các ràng buộc:

x1≥0, x2≥0, x3≥0.

Hãy để chúng tôi áp dụng phương pháp cơ sở nhân tạo. Chúng tôi đưa các biến nhân tạo vào các ràng buộc của bài toán

2×1 + 3×2 + x3 + R1 u003d 3;

x1 + 3×3 + R2 u003d 2;

Mục tiêu hàm F (x) -M ∑Rj u003d -x1 + 2×2 – x3 – M (R1 + R2).

Hãy biểu diễn tổng R1 + R2 từ hệ thức: R1 + R2 u003d 5 – 3×1 – 3×2 – 4×3, khi đó F (x) u003d -x1 + 2×2 – x3 – M (5 – 3×1 – 3×2 – 4×3).

Khi biên dịch bảng đơn giản đầu tiên (Bảng 1), chúng ta sẽ giả định rằng các biến ban đầu x1, x2, x3 là không cơ bản và các biến nhân tạo được giới thiệu là cơ bản. Trong các bài toán tối đa hóa, dấu của hệ số của các biến không cơ bản trong hàng F và M bị đảo ngược. Dấu của giá trị không đổi trong đường thẳng M không thay đổi. Việc tối ưu hóa được thực hiện đầu tiên dọc theo hàng M. Việc chọn cột và hàng đứng đầu, tất cả các phép biến đổi simplex khi sử dụng phương pháp cơ sở nhân tạo được thực hiện như trong phương pháp simplex thông thường.

Hệ số âm lớn nhất (-4) ở giá trị tuyệt đối xác định cột đứng đầu và biến x3, sẽ đi vào phần cơ sở. Tỷ lệ đơn giản tối thiểu (2/3) tương ứng với hàng thứ hai của bảng, do đó, biến R2 nên được loại trừ khỏi cơ sở. Phần tử trục được phác thảo.

Trong phương pháp cơ sở nhân tạo, các biến nhân tạo bị loại khỏi cơ sở không còn được trả lại cho nó nữa, do đó, các cột phần tử của các biến đó bị bỏ qua. Chuyển hướng. 2. giảm đi 1 cột. Tính lại bảng này, sang bảng. 3., trong đó dòng M là không, nó có thể được loại bỏ. Sau khi loại bỏ tất cả các biến nhân tạo khỏi cơ sở, chúng ta thu được một giải pháp cơ bản có thể chấp nhận được của bài toán ban đầu, trong ví dụ được coi là tối ưu:

x1 u003d 0; x2 u003d 7/9; Fmax u003d 8/9.

Nếu khi loại bỏ chuỗi M, giải pháp không phải là tối ưu, thì quy trình tối ưu hóa tiếp tục và được thực hiện bằng phương pháp đơn giản thông thường. Hãy xem xét một ví dụ với các ràng buộc thuộc tất cả các loại: ≤, u003d, ≥

Nhiệm vụ

Tìm giá trị tối ưu của sản xuất sản phẩm loại A, B và C. Chi phí nguyên vật liệu trên một đơn vị sản xuất: A – 5, B – 2, C – 4. Khối lượng nguyên vật liệu – 2000 đơn vị. Chi phí thiết bị trên một đơn vị sản xuất: A – 4, B – 5, C – 4. Khối lượng thiết bị – 1000 chiếc. Lợi nhuận từ việc bán một đơn vị sản xuất: A – 10, B – 8, C – 12. Tiêu chí – lợi nhuận tối đa của doanh nghiệp. Việc sản xuất sản phẩm A ít nhất phải là 100 chiếc. Sản xuất sản phẩm B ít nhất phải có 50 đơn vị.

Lời giải của bài toán M simplex bằng phương pháp

1) Xác định kế hoạch sản xuất tối ưu

Gọi x1, x2, x3 lần lượt là lượng sản phẩm sản xuất loại A, B, C. Khi đó mô hình toán học của bài toán có dạng:

F u003d 10 x1 + 8 x2 + 12 x3 -u003e cực đại

Chúng tôi giới thiệu thêm các biến x4 ≥ 0, x5 ≥ 0, x6 ≥ 0, x7 ≥ 0 để biến bất phương trình thành bất phương trình.

Để chọn cơ sở ban đầu, chúng tôi đưa ra các biến nhân tạo x8 ≥ 0, x9 ≥ 0 và một số rất lớn M (M -u003e ∞). Ta giải bằng phương pháp M.

F u003d 10 x1 + 8 x2 + 12 x3 + 0 x4 + 0 x5 + 0 x6 + 0 x7- M x8- M x9 -u003e max

Lấy x4 u003d 2000 làm cơ sở; x5 u003d 1000; x8 u003d 100; x9 u003d 50.

Chúng tôi nhập dữ liệu vào bảng simplex

Bảng Simplex số 1

Hàm mục tiêu:

0 2000 + 0 1000 + (- M) 100 + (- M) 50 u003d – 150M

Chúng tôi tính điểm bằng công thức:

Δ1 u003d 0 5 + 0 4 + (- M) 1 + (- M) 0 – 10 u003d – M – 10

Δ2 u003d 0 2 + 0 5 + (- M) 0 + (- M) 1 – 8 u003d – M – 8

Δ3 u003d 0 4 + 0 4 + (- M) 0 + (- M) 0 – 12 u003d – 12

Δ4 u003d 0 1 + 0 0 + (- M) 0 + (- M) 0 – 0 u003d 0

Δ5 u003d 0 0 + 0 1 + (- M) 0 + (- M) 0 – 0 u003d 0

Δ6 u003d 0 · 0 + 0 · 0 + (- M) · (-1) + (- M) · 0 – 0 u003d M

Δ2 u003d 0 0 + 12 0 + 10 0 + 8 1 – 8 u003d 0 Δ3 u003d 0 0 + 12 1 + 10 0 + 8 0 – 12 u003d 0 Δ4 u003d 0 1 + 12 0 + 10 0 + 8 0 – 0 u003d 0 Δ5 u003d 0 · (-1) + 12 · 1/4 + 10 · 0 + 8 · 0 – 0 u003d 3 Δ6 u003d 0 · 1 + 12 · 1 + 10 · (-1) + 8 · 0 – 0 u003d 2 Δ7 u003d 0 · (-3) + 12 · 5/4 + 10 · 0 + 8 · (-1) – 0 u003d 7 Vì không có xếp hạng tiêu cực, kế hoạch là tối ưu. Lời giải bài toán: x1 u003d 100; x2 u003d 50; x3 u003d 175/2 u003d 87,5; x4 u003d 1050; x5 u003d 0; x6 u003d 0; x7 u003d 0; Fmax u003d 2450 Đáp số: x1 u003d 100; x2 u003d 50; x3 u003d 175/2 u003d 87,5; x4 u003d 1050; x5 u003d 0; x6 u003d 0; x7 u003d 0; Fmax u003d 2450 Tức là cần sản xuất x1 u003d 100 đơn vị sản phẩm loại A, x2 u003d 50 đơn vị sản phẩm loại B và x3 u003d 87,5 đơn vị sản phẩm loại B. Lợi nhuận tối đa sẽ là Fmax u003d 2450 đơn vị.

Δ7 u003d 0 · 0 + 0 · 0 + (- M) · 0 + (- M) · (-1) – 0 u003d M

???????????????????????

Định lý về mối quan hệ giữa các nghiệm của bài toán ban đầu và bài toán M.

V2: DE 57 – Hệ thống nghiệm cơ bản của phương trình vi phân tuyến tính thuần nhất

B1 2. Toán tử tuyến tính trong không gian hữu hạn chiều, ma trận của nó. Đa thức đặc trưng của một toán tử tuyến tính. Eigenvalues u200bu200bvà eigenvectors.

Các cấu trúc điều khiển cơ bản của lập trình có cấu trúc

Vé số 13 Góc giữa 2 đường thẳng, điều kiện song song và vuông góc. Chuyển đổi toán tử tuyến tính khi chuyển sang cơ sở mới

Vé 13. Các nhà khai thác tuyến tính. Ma trận toán tử tuyến tính.

Vé 26. Không gian con gốc. Tách một không gian tuyến tính thành một tổng trực tiếp của các không gian con gốc.

Vé 27. Cơ sở Jordan và ma trận Jordan của toán tử tuyến tính trong không gian phức.

Vé 35. Toán tử Hermitian và ma trận Hermitian. Phân rã Hermitian của một toán tử tuyến tính.

Vé 7 Tích của vectơ, hình chiếu của vectơ này lên vectơ khác. Khái niệm về không gian tuyến tính và không gian con, tiêu chí cho không gian con

Định lý (về sự lựa chọn của phần tử phân giải)

Nếu có các phần tử âm trong một số cột của hàng thứ z, thì cột phân giải phải là cột có tích lớn nhất của giá trị tuyệt đối của hệ số trong hàng thứ z và tỷ lệ đơn giản tối thiểu của cột này.

Chứng cớ:

Hãy để phần tử là phần tử được phép. Theo kết quả của bước ngoại lệ Jordan đã sửa đổi, số hạng tự do trong chuỗi z sẽ là một số bằng. Vì và, dấu ngoặc đơn trong biểu thức này sẽ luôn dương. Và vì giá trị của hàm luôn bằng với số hạng tự do, nên dấu ngoặc này biểu thị phần bổ sung vào hàm thu được do bước thực hiện.

Hàm càng lớn sẽ nhận được gia số ở mỗi bước, thì càng ít bước (tức là tính toán) sẽ được yêu cầu để đạt được tối ưu. Độ lớn của gia số này phụ thuộc vào giá trị tuyệt đối của hệ số và độ lớn của tỷ lệ đơn giản nhỏ nhất. Tức là cột phân giải sẽ là cột có sản phẩm tối đa.

Ví dụ: lập trình tuyến tính:

Tìm cực đại của hàm

với những hạn chế

Giải pháp: soạn một bảng Jordan.

Vì các điều khoản miễn phí trong đó là tích cực, nên kế hoạch này là tài liệu tham khảo. Tuy nhiên, nó không phải là tối ưu vì hệ số hàng z là âm. Chúng tôi chọn một trong những tích có giá trị tuyệt đối lớn nhất và tỷ lệ đơn giản nhỏ nhất. Cột thứ ba được coi là đang phân giải, vì nó có giá trị tuyệt đối lớn nhất là 8 và tỷ lệ đơn giản: tương ứng (do đó, phần tử 1 trong cột thứ ba sẽ được phân giải). Chúng tôi thực hiện bước ngoại lệ Jordan đã sửa đổi và đi đến bảng sau.

Đánh giá theo hệ số hàng z, trong bảng kết quả chưa đạt được phương án tối ưu. Lấy cột thứ hai có hệ số âm trong hàng z làm cột phân giải (chỉ cột đầu tiên có thể là hàng phân giải). Với phần tử 5 tìm được, chúng ta thực hiện bước tiếp theo.

Trong hàng z, tất cả các hệ số đều dương, thiết kế thu được bằng cách cân bằng các biến phía trên với 0 và các biến phụ cho các phần tử tự do là tối ưu. Chúng tôi viết ra các giá trị của ẩn số chính từ bảng: Chúng tôi tính giá trị lớn nhất của hàm trong ô cuối cùng của bảng:

Trong bảng cuối cùng, tất cả các định thức đều không âm. Điều này cho thấy rằng đối với các giá trị của ẩn số thì hàm đạt cực đại

Người ta thường giả định rằng trên tập các phương án bài toán không có điểm nào tại đó mẫu số của hàm mục tiêu bằng không. Không mất tính tổng quát, chúng ta có thể giả định rằng.

Trong một bài toán lập trình phân số tuyến tính, cực trị của hàm mục tiêu đạt được ở đỉnh của đa diện nghiệm. Sự tương đồng này với lập trình tuyến tính cho phép giải các bài toán phân số tuyến tính bằng phương pháp Stiefel.

Các phép tính được thực hiện dưới dạng bảng Jordan. Trong trường hợp này, hai dòng dưới cùng được phân bổ cho hàm: ở dòng đầu tiên chúng ta viết các hệ số của tử số và ở dòng thứ hai – mẫu số. Bảng 1 tương ứng với nhiệm vụ ban đầu:

Băng qua y tôi sự khác biệt giữa phần bên phải và bên trái của hệ thống hạn chế được biểu thị:

Chúng ta sẽ gọi các biến tự do là các biến nằm ở hàng tiêu đề trên cùng của bảng Jordan. Cho các biến tự do có giá trị bằng không, ta được nghiệm cơ bản ban đầu:. Vectơ này không thể là một mặt phẳng tham chiếu, vì mẫu số của hàm mục tiêu trên nó bằng 0 ( z 2 u003d 0). Do đó, trong số các thành viên tự do của hệ thống hạn chế a 1 ,…, là nhất thiết phải có số âm (nếu không thì nghiệm cơ bản sẽ là đường cơ sở).

Bằng các bước của ngoại lệ Jordan đã sửa đổi, giống như khi giải một bài toán lập trình tuyến tính (xem), chúng ta tìm ra phương án ban đầu của bài toán. Kết quả là k các bước chúng ta đến với bảng 2:

Trong bảng 2, tất cả các thành viên miễn phí b tôi không âm, đảm bảo rằng các biến cơ sở x 1 ,…, y m… Ngoài ra (do tính tích cực của mẫu số của hàm mục tiêu z 2 trên nhiều đường cơ sở). Phương án tham chiếu ban đầu là một vector có tọa độ. Giá trị hàm mục tiêu trên đường cơ sở ban đầu là.

Lưu ý rằng nếu tại một trong các bước của Jordan ngoại lệ bất kỳ điều khoản miễn phí nào b tôi hóa ra là tiêu cực, và tất cả các yếu tố khác tôi-th lines là không âm, sau đó vấn đề sẽ không có một giải pháp do thiếu kế hoạch.

Chúng ta hãy theo dõi hàm mục tiêu thay đổi như thế nào khi chuyển từ phương án cơ bản của bài toán sang phương án khác. Nó chỉ ra rằng dấu của sự khác biệt giữa các giá trị mới và cũ của hàm số trùng với dấu của định thức. Nếu. Bởi vì polytope giải pháp chỉ chứa một số lượng hữu hạn các thiết kế hỗ trợ, sau đó trong một số bước hữu hạn, chúng tôi sẽ đi đến thiết kế hỗ trợ tối ưu.

Quá trình này chỉ có thể bị cản trở bởi tính không liên kết của khối đa diện giải pháp. Trong trường hợp này, hàm mục tiêu có thể có một điểm được gọi là cực trị (trong trường hợp này là cực đại). Tiệm cận cực đại của một bài toán lập trình phân số tuyến tính là giới hạn trên chính xác của hàm mục tiêu trên tập hợp các thiết kế, không đạt được đối với bất kỳ thiết kế nào. Trong trường hợp bài toán có một tiệm cận cực đại, trong miền thiết kế, luôn có thể tìm thấy một thiết kế như vậy (không phải một tham chiếu) mà trên đó hàm mục tiêu nhận một giá trị gần với tiệm cận cực đại một cách tùy ý.

Phương pháp của Stiefel cho phép người ta không chỉ tìm thấy cực đại mà còn cả tiệm cận cực đại của bài toán lập trình phân số tuyến tính. Chúng ta hãy xem xét kỹ hơn quá trình chuyển đổi từ kế hoạch sang kế hoạch và tìm hiểu. Chọn một yếu tố cho phép trong jcột -th, chúng ta nên được hướng dẫn bởi nguyên tắc của mối quan hệ đơn giản tối thiểu. Những, cái đó. yếu tố cho phép trong j cột -th phải ở hàng mà tỷ lệ đơn giản là dương và nhỏ nhất.

Bởi vì sau khi tìm thấy kế hoạch tham chiếu ban đầu, tất cả các phần phù hợp b tôi trở thành không âm, sau đó là phần tử phân giải j Cột thứ có thể là một trong những phần tử dương của nó (). Nếu tại mỗi bước của giai đoạn tìm phương án cơ sở tối ưu trong cột giải quyết đã chọn có (ít nhất một) phần tử dương, thì bài toán đó có cực đại (có thể nhiều hơn một).

Tuy nhiên, nếu ở một trong các bước, một số ước tính nhỏ hơn 0 và tất cả các phần tử jcột thứ. Sau đó, trong cột này, được hướng dẫn bởi nguyên tắc của quan hệ đơn giản tối thiểu, phần tử phân giải không thể được chọn. Tăng giá trị của một biến tự do x j từ 0 trở lên (xem Bảng 2), chúng tôi luôn nằm trong vùng kế hoạch. Điều này là do thực tế là tăng biến x j không thay đổi dấu thành trừ trong bất kỳ biến cơ bản nào.

Hãy để chúng tôi biểu thị bằng M giới hạn mà, tăng đơn điệu, hàm mục tiêu có xu hướng tại:. Số này là tiệm cận cực đại.

Chúng ta hãy xem xét chi tiết cách tính toán lại các bảng simplex (sử dụng ví dụ về một lần lặp). Để có một bảng đơn giản được trình bày trên Hình 1… Bài toán tối đa hóa hàm mục tiêu được giải quyết. Cột được phép khớp với biến x 2và chuỗi phân giải là biến x 3 (số màu đỏ), tại giao điểm của chúng có một phần tử cho phép (một ô có nền màu xám). Điều đầu tiên chúng ta cần làm là thay thế. Dòng giải quyết cho biết biến nào nên được suy ra từ cơ sở (trong trường hợp của chúng tôi x 3) và cột giải quyết cho biết biến nào nên được đưa vào cơ sở (trong trường hợp của chúng tôi x 2). Trên Hình 2 thực tế thay thế được đánh dấu bằng một đường màu xanh lam.

Bức tranh 1

Bây giờ hãy đếm các phần tử trong dòng phân giải. Để làm điều này, chỉ cần chia mỗi người trong số họ thành một phần tử cho phép (trong ví dụ của chúng tôi 4 ). Và tất cả các phần tử của cột phân giải sẽ bằng 0, ngoại trừ phần tử trong hàng phân giải. (Nhìn Hình 2)

Hình 2

Phần còn lại của các ô trong bảng (ngoại trừ cột “Tỷ lệ”) được tính toán lại theo cái gọi là quy tắc hình chữ nhật, nghĩa của nó dễ hiểu nhất với một ví dụ. Giả sử bạn cần tính toán lại phần tử được khoanh tròn bởi Hình 1 phác thảo màu đỏ. Nhẩm vẽ các đường dọc và ngang từ nó đến giao lộ, với đường phân giải và cột phân giải. Các phần tử đứng tại các điểm giao nhau được khoanh tròn trong đường viền màu xanh lam (Xem Hình 1). Giá trị mới của phần tử “đỏ” sẽ bằng giá trị hiện tại của phần tử trừ đi tích của phần tử “xanh lam” chia cho phần tử phân giải (“xám”) (Xem Hình 1). I E: 18 – (64 * -1) / 4 = 34 , đây dấu ” * “hoạt động của phép nhân được hiển thị. Chúng tôi ghi giá trị mới vào vị trí trước đó (Xem Hình 2 viền đỏ).

Hình 3

Sử dụng quy tắc này, chúng tôi điền vào tất cả các phần tử trống của bảng (ngoại trừ cột “Mối quan hệ”) Hình 3… Sau đó, chúng tôi xác định một cột cho phép mới. Để làm được điều này, hãy phân tích dòng “Q” và vì nhiệm vụ của chúng tôi là tối đa, chúng tôi sẽ tìm thấy trong đó phần tử tích cực tối đa, nó sẽ xác định cột phân giải. Trong trường hợp của chúng tôi, nó là 3/2 … Tất cả các phần tử của cột phân giải được hiển thị bằng phông chữ màu đỏ (Xem Hình 3). Nếu sau lần lặp tiếp theo trong dòng “Q” sẽ không có phần tử tích cực – điều này có nghĩa là đã đạt được giải pháp tối ưu, các bước lặp được chấm dứt. Nếu nhiệm vụ của chúng ta là ở mức tối thiểu, thì cột phân giải sẽ được xác định bởi phần tử phủ định tối thiểu và nếu sau lần lặp tiếp theo trong hàng “Q” không có yếu tố tiêu cực, khi đó giải pháp tối ưu đã đạt được.

Bây giờ chúng ta hãy điền vào cột “Mối quan hệ”. Để thực hiện việc này, hãy chia phần tử tương ứng (trong cùng một hàng) của cột “Quyết định” thành phần tử tương ứng của cột phân giải (Xem Hình 3). Ghi chúrằng hoạt động này được thực hiện chỉ cho tích cực yếu tố cột và hàng cho phép “Q” không tham gia vào hoạt động này. Nếu, sau một số lần lặp, không có phần tử tích cực nào trong cột giải quyết, thì vấn đề này là không thể giải quyết được do tính không liên kết của hàm mục tiêu và các lần lặp bị chấm dứt.

Sau khi điền vào cột “Mối quan hệ”, hãy xác định một hàng giải quyết mới. Nó được xác định bởi mục nhỏ nhất trong cột Mối quan hệ. Trong trường hợp của chúng tôi, nó là 32 , tất cả các phần tử của dòng quyền được hiển thị bằng màu đỏ (Xem Hình 3). Tại thời điểm này, lần lặp tiếp theo kết thúc, ở lần lặp tiếp theo, biến x 2 sẽ được suy ra từ cơ sở (dòng phân giải mới cho chúng ta biết về điều này), vị trí của nó sẽ được thay thế bởi biến x 1 (cột giải quyết mới cho chúng ta biết về điều này) và tất cả các phép tính sẽ được lặp lại một lần nữa.

Nếu câu lệnh chứa các ràng buộc có dấu ≥, thì chúng có thể được rút gọn về dạng ∑a ji b j bằng cách nhân cả hai vế của bất đẳng thức với -1. Chúng tôi đưa thêm m biến x n + j ≥0 (j u003d 1, m) và biến đổi các ràng buộc về dạng cân bằng

(2)

Giả sử rằng tất cả các biến ban đầu của bài toán x 1, x 2, …, x n là không cơ bản. Khi đó, các biến bổ sung sẽ là cơ bản và giải pháp cụ thể của hệ thống các ràng buộc có dạng

x 1 u003d x 2 u003d … u003d x n u003d 0, x n + j u003d b j, j u003d 1, m. (3)

Vì trong trường hợp này giá trị của hàm mục tiêu F 0 u003d 0, chúng ta có thể biểu diễn F (x) như sau:

F (x) u003d ∑c i x i + F 0 u003d 0 (4)

Bảng đơn giản ban đầu (bảng đơn giản 1) được biên soạn dựa trên các phương trình (2) và (4). Nếu các biến bổ sung x n + j đứng trước dấu “+”, như trong (2), thì tất cả các hệ số trước biến x i và số hạng tự do b j được nhập vào bảng simplex không thay đổi. Khi hàm mục tiêu được tối đa hóa, các hệ số của hàm mục tiêu được nhập vào dòng dưới cùng của bảng đơn giản với các dấu hiệu ngược lại. Các điều khoản miễn phí trong bảng simplex xác định giải pháp cho vấn đề.

Thuật toán để giải quyết vấn đề như sau:

Bước đầu tiên. Các phần tử của cột thành viên miễn phí được quét. Nếu tất cả chúng đều dương, nghĩa là một giải pháp cơ bản khả thi đã được tìm thấy và người ta sẽ chuyển sang bước 5 của thuật toán, tương ứng với việc tìm ra giải pháp tối ưu. Nếu bảng đơn giản ban đầu có các số hạng tự do âm, thì giải pháp không hợp lệ và bạn nên chuyển sang bước 2.

Bước thứ 2. Để tìm ra một giải pháp khả thi được thực hiện, trong khi cần phải quyết định biến nào không cơ bản được đưa vào cơ sở và biến nào cần suy ra từ cơ sở.

Bảng 1.

biến cơ bản

Thành viên tự do trong các ràng buộc

Biến nonbasis

Để thực hiện việc này, hãy chọn bất kỳ phần tử phủ định nào của cột thành viên tự do (để nó đứng đầu b 2 hoặc phân giải. Nếu không có phần tử phủ định nào trong hàng có phần tử tự do phủ định, thì hệ thống ràng buộc không tương thích và vấn đề không có giải pháp).

Đồng thời, biến đầu tiên đổi dấu với mức tăng NP x l đã chọn sẽ bị loại trừ khỏi BP. Đây sẽ là x n + r, chỉ số r được xác định từ điều kiện

những, cái đó. biến tương ứng với tỷ lệ nhỏ nhất của phần tử tự do với phần tử của cột xoay đã chọn. Mối quan hệ này được gọi là quan hệ đơn giản. Chỉ các mối quan hệ đơn giản tích cực mới nên được xem xét.

Chuỗi tương ứng với biến x n + r được gọi là dẫn đầu, hoặc dễ dãi. Phần tử của bảng simplex a rl, đứng ở giao điểm của hàng đầu và cột hàng đầu, được gọi là phần tử đầu hoặc phần tử phân giải. Tìm phần tử pivot kết thúc hoạt động với mỗi bảng đơn giản liên tiếp.

Bước thứ 3. Một bảng đơn giản mới được tính toán, các phần tử của chúng được tính toán lại từ các phần tử của bảng đơn giản của bước trước đó và được đánh dấu bằng một số nguyên tố, tức là b “j, a” ji, c “i, F” 0. Các phần tử được tính toán lại theo các công thức sau:

Đầu tiên, bảng simplex mới sẽ điền vào hàng và cột đứng đầu trong bảng simplex trước đó. Biểu thức (5) có nghĩa là phần tử a “rl ở vị trí của phần tử đứng đầu bằng nghịch đảo của phần tử của bảng simplex trước đó. Các phần tử của hàng a ri được chia cho phần tử đứng đầu và các phần tử của cột a jl cũng được chia cho phần tử đứng đầu nhưng lấy dấu ngược lại. b “r và c” l được tính theo cùng một cách.

Phần còn lại của các công thức rất dễ sử dụng.

Hình chữ nhật được xây dựng theo bảng simplex cũ theo cách mà một trong các đường chéo của nó được hình thành bởi các phần tử được tính toán lại (a ji) và (a rl) (Hình 1). Đường chéo thứ hai được xác định duy nhất. Để tìm một phần tử mới a “ji, tích của các phần tử của đường chéo đối diện chia cho phần tử đứng đầu được trừ đi phần tử a ji (như được chỉ ra bởi dấu” – “bên cạnh ô). Các phần tử b” j, (j ≠ r) và c “i, (tôi ≠ l).

Bước thứ 4. Việc phân tích một bảng đơn giản mới bắt đầu với bước đầu tiên của thuật toán. Hành động tiếp tục cho đến khi tìm được giải pháp cơ bản khả thi, tức là tất cả các thành viên của cột thành viên miễn phí phải tích cực.

Bước thứ 5. Chúng tôi tin rằng một giải pháp cơ bản khả thi đã được tìm thấy. Nhìn vào các hệ số của dòng của hàm mục tiêu F (x). Một tiêu chí cho tính tối ưu của một bảng đơn giản là độ không âm của các hệ số đối với các biến không cơ bản trong hàng F.

Nhân vật: 1. Quy tắc hình chữ nhật

Nếu trong số các hệ số của hàng F có những hệ số âm (ngoại trừ hệ số chặn), thì bạn cần chuyển sang một giải pháp cơ bản khác. Khi tối đa hóa hàm mục tiêu, cơ sở bao gồm giá trị của các biến không cơ bản (ví dụ: x l), cột tương ứng với giá trị tuyệt đối lớn nhất của hệ số âm c l ở hàng dưới cùng của bảng đơn giản. Điều này giúp bạn có thể chọn biến có mức tăng dẫn đến cải thiện hàm mục tiêu. Cột tương ứng với biến x l được gọi là cột đầu. Đồng thời, biến x n + r đó bị loại ra khỏi cơ sở, chỉ số r của biến đó được xác định bởi quan hệ đơn giản tối thiểu:

Hàng tương ứng với x n + r được gọi là hàng đầu và phần tử của bảng đơn giản a rl tại giao điểm của hàng đầu và cột đứng đầu được gọi là yếu tố hàng đầu.

Bước thứ 6. theo các quy tắc đã nêu ở bước thứ 3. Quy trình tiếp tục cho đến khi một giải pháp tối ưu được tìm thấy hoặc người ta kết luận rằng nó không tồn tại.

Nếu trong quá trình tối ưu hóa giải pháp trong cột đầu tiên, tất cả các phần tử đều không tích cực, thì hàng đầu tiên không thể được chọn. Trong trường hợp này, hàm trong miền các giải pháp khả thi của bài toán không bị giới hạn ở trên và F max -u003e & ∞.

Nếu ở bước tiếp theo trong quá trình tìm kiếm cực trị, một trong các biến cơ bản trở thành bằng 0, thì nghiệm cơ bản tương ứng được gọi là suy biến. Trong trường hợp này, cái gọi là lặp lại xảy ra, được đặc trưng bởi thực tế là với một tần số nhất định, tổ hợp BP giống nhau bắt đầu lặp lại (giá trị của hàm F được bảo toàn) và không thể đi đến một giải pháp cơ bản mới có thể chấp nhận được. Looping là một trong những nhược điểm chính của phương pháp simplex, nhưng nó tương đối hiếm. Trên thực tế, trong những trường hợp như vậy, họ thường từ chối nhập biến cơ sở, cột tương ứng với giá trị tuyệt đối lớn nhất của hệ số âm trong hàm mục tiêu và chọn ngẫu nhiên một nghiệm cơ bản mới.

Ví dụ 1. Giải quyết vấn đề

Phương pháp Simplex và đưa ra một diễn giải hình học của quá trình giải.

Giải thích bằng hình ảnh của giải pháp cho vấn đề được hiển thị trong Hình. 2. Giá trị lớn nhất của hàm mục tiêu đạt được ở đầu ODZP có tọa độ. Hãy giải quyết vấn đề bằng cách sử dụng bảng simplex. Chúng ta nhân ràng buộc thứ hai với (-1) và đưa vào các biến bổ sung để đưa bất đẳng thức về dạng bình đẳng, sau đó

Các biến ban đầu x 1 và x 2 được coi là không cơ bản, và x 3, x 4 và x 5 bổ sung được coi là cơ bản và chúng tôi tạo ra một bảng simplex (bảng simplex 2). Giải pháp tương ứng với bảng simplex. 2 là không hợp lệ; trục được vạch ra và được chọn theo bước 2 của thuật toán trước đó. Bảng đơn giản tiếp theo. 3 xác định giải pháp cơ bản có thể chấp nhận được; nó tương ứng với đỉnh của ODZP trong Hình. 2 Phần tử xoay được phác thảo và lựa chọn phù hợp với bước thứ 5 của thuật toán để giải quyết vấn đề. Chuyển hướng. 4 tương ứng với phương án tối ưu của bài toán, do đó: x 1 u003d x 5 u003d 0; x 2 u003d 4; x 3 u003d 3; x 4 u003d 8; F cực đại u003d 20.

Nhân vật: 2. Giải pháp đồ họa của bài toán

Phương Thức Equals() Và Hashcode() Trong Java

Bài viết này giúp bạn hiểu khái niệm 2 phương thức quan trọng: Phương thức equals() và hashCode() trong Java.

Khi sử dụng các collection, Để nhận được các hành vi mong muốn, chúng ta nên ghi đè các phương thức equals() và hashCode() trong các lớp của các phần tử được thêm vào collection.

Lớp Object (lớp cha của tất cả các lớp trong Java) định nghĩa hai phương thức equal() và hashCode(). Điều đó có nghĩa là tất cả các lớp trong Java (bao gồm cả các lớp bạn đã tạo) thừa kế các phương thức này. Về cơ bản, lớp Object thực hiện các phương thức này cho mục đích chung.

Tuy nhiên, bạn sẽ phải ghi đè chúng một cách cụ thể cho các lớp có đối tượng được thêm vào các collection, đặc biệt là các collection dựa trên bảng băm như HashSet và HashMap.

Phương thức equals() trong Java

Khi so sánh hai đối tượng với nhau, Java gọi phương thức equals() của chúng trả về true nếu hai đối tượng bằng nhau hoặc false nếu hai đối tượng là khác nhau. Lưu ý rằng phép so sánh sử dụng phương thức equals() so với sử dụng toán tử == là khác nhau.

Đây là sự khác biệt:

Phương thức equals() được thiết kế để so sánh hai đối tượng về mặt ngữ nghĩa (bằng cách so sánh các thành viên dữ liệu của lớp), trong khi toán tử == so sánh hai đối tượng về mặt kỹ thuật (bằng cách so sánh các tham chiếu của chúng, nghĩa là địa chỉ bộ nhớ).

LƯU Ý: Việc cài đặt phương thức equals() trong lớp Object so sánh các tham chiếu của hai đối tượng. Điều đó có nghĩa là bạn nên ghi đè nó trong các lớp của bạn để so sánh ngữ nghĩa. Hầu hết các lớp trong JDK ghi đè phương thức equals() của riêng chúng, chẳng hạn như String, Date, Integer, Double, v.v.

Ví dụ phương thức equals() của đối tượng String

Ví dụ điển hình so sánh chuỗi trong Java, để thấy sự khác nhau giữa phương thức equal() và toán tử ==.

package vn.viettuts; public class EqualExample1 { public static void main(String[] args) { String s1 = new String("This is a string"); String s2 = new String("This is a string"); System.out.println("s1 == s2: " + (s1 == s2)); System.out.println("s1.equals(s2): " + (s1.equals(s2))); } }

Kết quả:

s1 == s2: false s1.equals(s2): true

So sánh tham chiếu (toán tử ==) trả về false vì s1 và s2 là hai đối tượng khác nhau được lưu trữ ở các vị trí khác nhau trong bộ nhớ. Trong khi so sánh ngữ nghĩa trả về true bởi vì s1 và s2 có cùng giá trị (“THis is a string”) có thể được coi là bằng nhau về mặt ngữ nghĩa.

Ví dụ ghi đè phương thức equals()

Tương tự như vậy, giả sử chúng ta có lớp Student và cài đặt phương thức equal() như sau:

Trong thực tế, chúng ta có thể xem xét hai đối tượng Student có ngữ nghĩa tương đương nhau nếu chúng có cùng thuộc tính (id, name, email và age). Bây giờ, hãy xem cách ghi đè phương thức equals() trong lớp này để xác nhận rằng hai đối tượng Student có các thuộc tính giống nhau được coi là bằng nhau:

package vn.viettuts; public class Student { private String id; private String name; private String email; private int age; public Student(String id, String name, String email, int age) { chúng tôi = id; chúng tôi = name; this.email = email; chúng tôi = age; } public String toString() { String studentInfo = "Student " + id; studentInfo += ": " + name; studentInfo += " - " + email; studentInfo += " - " + age; return studentInfo; } public boolean equals(Object obj) { if (obj instanceof Student) { Student another = (Student) obj; if (this.id.equals(another.id) && this.name.equals(another.name) && this.email.equals(another.email) && chúng tôi == chúng tôi { return true; } } return false; } }

Tạo ra lớp chúng tôi để kiểm tran phương thức equal() trong lớp Student.

package vn.viettuts; public class EqualStudent { public static void main(String[] args) { Student student1 = new Student("123", "Cong", "cong@gmail.com", 22); Student student2 = new Student("123", "Cong", "cong@gmail.com", 22); Student student3 = new Student("456", "Dung", "dung@gmail.com", 18); System.out.println("student1 == student2: " + (student1 == student2)); System.out.println("student1.equals(student2): " + (student1.equals(student2))); System.out.println("student2.equals(student3): " + (student2.equals(student3))); } }

Kết quả:

student1 == student2: false student1.equals(student2): true student2.equals(student3): false

Ví dụ ghi đè phương thức equals() của phần tử của collection

Ta có lớp chúng tôi có nội dung như sau:

package vn.viettuts; public class Student { private String id; private String name; private String email; private int age; public Student(String id) { chúng tôi = id; } public Student(String id, String name, String email, int age) { chúng tôi = id; chúng tôi = name; this.email = email; chúng tôi = age; } public String toString() { String studentInfo = "Student " + id; studentInfo += ": " + name; studentInfo += " - " + email; studentInfo += " - " + age; return studentInfo; } public boolean equals(Object obj) { if (obj instanceof Student) { Student another = (Student) obj; if (this.id.equals(another.id)) { return true; } } return false; } }

Ở đây, phương thức equals() này chỉ so sánh thuộc tính ID của hai đối tượng Student.

Chúng ta sẽ coi mỗi đối tượng Student có một ID duy nhất, và xem hai đối tượng sinh viên là bằng nhau nếu chúng có ID giống nhau.

Phương thức contains(Object) của interface List trong java có thể được sử dụng để kiểm tra nếu đối tượng được chỉ định tồn tại trong danh sách. Về bản chất, phương thức equal() được gọi bên trong phương thức contains(Object).

package vn.viettuts; import java.util.ArrayList; import java.util.List; public class EqualStudent2 { public static void main(String[] args) { Student student1 = new Student("123", "Cong", "cong@gmail.com", 22); Student student2 = new Student("123", "Cong", "cong@gmail.com", 22); Student student3 = new Student("456", "Dung", "dung@gmail.com", 18); listStudents.add(student1); listStudents.add(student2); listStudents.add(student3); Student searchStudent1 = new Student("123"); Student searchStudent4 = new Student("789"); System.out.println("Search student1: " + listStudents.contains(searchStudent1)); System.out.println("Search student4: " + listStudents.contains(searchStudent4)); } }

Kết quả:

Search student1: true Search student4: false

Phương thức hashCode() trong Java

Định nghĩa phương thức hashCode() trong lớp Object:

public native int hashCode();

Bạn có thể thấy phương thức này trả về một số nguyên. Vậy nó được sử dụng ở đâu?

Đây là bí mật:

Số băm này được sử dụng bởi các collection dựa trên bảng băm như Hashtable , HashSet và HashMap để lưu trữ các đối tượng trong các container nhỏ được gọi là “nhóm”. Mỗi nhóm được liên kết với mã băm và mỗi nhóm chỉ chứa các đối tượng có mã băm giống hệt nhau.

Nói cách khác, một bảng băm nhóm các phần tử của nó bằng các giá trị mã băm của chúng. Sự sắp xếp này giúp cho bảng băm định vị một phần tử một cách nhanh chóng và hiệu quả bằng cách tìm kiếm trên các phần nhỏ của collection thay vì toàn bộ collection.

Nhận giá trị mã băm của phần tử được chỉ định bằng cách gọi phương thức hashCode().

Tìm nhóm thích hợp được liên kết với mã băm đó.

Bên trong nhóm, tìm phần tử chính xác bằng cách so sánh phần tử được chỉ định với tất cả các phần tử trong nhóm. Bằng phương thức equals() của phần tử đã chỉ định được gọi.

Có nói rằng, khi chúng ta thêm các đối tượng của một lớp vào một collection dựa trên bảng băm (HashSet, HashMap ), phương thức hashCode() của lớp được gọi để tạo ra một số nguyên (có thể là một giá trị tùy ý). Con số này được sử dụng bởi bộ sưu tập để lưu trữ và định vị các đối tượng một cách nhanh chóng và hiệu quả, vì collection dựa trên bảng băm không duy trì thứ tự các phần tử của nó.

LƯU Ý: Việc thực thi phương thức mặc định hashCode() trong lớp Object trả về một số nguyên là địa chỉ bộ nhớ của đối tượng. Bạn nên ghi đè phương thức trong các lớp của bạn. Hầu hết các lớp trong JDK ghi đè phương thức hashCode() của riêng chúng, chẳng hạn như String , Date , Integer , Double , v.v.

Các quy tắc cho phương thức equals() và hashCode() trong Java

Như đã giải thích ở trên, collection dựa trên bảng băm xác định một phần tử bằng cách gọi phương thức hashCode() và equals() của nó, vì vậy khi ghi đè các phương thức này chúng ta phải tuân theo các quy tắc sau:

Khi phương thức equals() được ghi đè, phương thức hashCode() cũng phải được ghi đè.

Nếu hai đối tượng bằng nhau, mã băm của chúng phải bằng nhau.

Nếu hai đối tượng không bằng nhau, không có ràng buộc về mã băm của chúng (mã băm của chúng có thể bằng nhau hay không).

Nếu hai đối tượng có mã băm giống nhau, thì không có ràng buộc nào về sự bình nhau của chúng (chúng có thể bằng nhau hay không).

Nếu hai đối tượng có mã băm khác nhau, chúng không được bằng nhau.

Nếu chúng ta vi phạm các quy tắc này, các collection sẽ hoạt động có thể không đúng như các đối tượng không thể tìm thấy, hoặc các đối tượng sai được trả về thay vì các đối tượng chính xác.

Ví dụ ghi đề phương thức equals(), không ghi đè hashCode()

Hãy xem phương thức hashCode() và equals() ảnh hưởng như thế nào đến hành vi của một đối tượng Set.

Lớp chúng tôi

package vn.viettuts; public class Student { private String id; private String name; private String email; private int age; public Student(String id) { chúng tôi = id; } public Student(String id, String name, String email, int age) { chúng tôi = id; chúng tôi = name; this.email = email; chúng tôi = age; } public String toString() { String studentInfo = "Student " + id; studentInfo += ": " + name; studentInfo += " - " + email; studentInfo += " - " + age; return studentInfo; } public boolean equals(Object obj) { if (obj instanceof Student) { Student another = (Student) obj; if (this.id.equals(another.id)) { return true; } } return false; } }

Lớp EqualStudent3 .java

package vn.viettuts; import java.util.HashSet; import java.util.Set; public class EqualStudent3 { public static void main(String[] args) { Student student1 = new Student("123", "Cong", "cong@gmail.com", 22); Student student2 = new Student("123", "Cong", "cong@gmail.com", 22); Student student3 = new Student("456", "Dung", "dung@gmail.com", 18); setStudents.add(student1); setStudents.add(student2); setStudents.add(student3); for (Student student : setStudents) { System.out.println(student); } } }

Kết quả:

Student 456: Dung - dung@gmail.com - 18 Student 123: Cong - cong@gmail.com - 22 Student 123: Cong - cong@gmail.com - 22

Hãy nhìn xem, bạn có nhận thấy rằng có 2 sinh viên trùng lặp (ID: 123), phải không?

Đây là lý do:

Tập Set gọi các phương thức equals() và hashCode() trên mỗi đối tượng được thêm vào để đảm bảo không có sự trùng lặp. Trong trường hợp của chúng ta, lớp Student chỉ ghi đè phương thức equals(). Và phương thức hashCode() thừa kế từ lớp Object trả về các địa chỉ bộ nhớ của mỗi đối tượng không nhất quán với phương thức equals(). Do đó, đối tượng Set xử lý đối tượng student1 và student2 thành hai phần tử khác nhau.

Bây giờ, chúng ta hãy ghi đè phương thức hashCode() trong lớp Student như sau:

public int hashCode() { return 31 + id.hashCode(); }

Kết quả:

Student 123: Cong - cong@gmail.com - 22 Student 456: Dung - dung@gmail.com - 18

Good! Phần tử trùng lặp hiện đã bị xóa. Đó chính là điều chúng tôi muốn.

Với các phương thức equals() và hashCode() được ghi đè đúng cách, chúng ta cũng có thể thực hiện tìm kiếm trên tập hợp như sau:

Student searchStudent = new Student("456"); boolean found = setStudents.contains(searchStudent); System.out.println("Search student: " + found);

Kết quả:

Để tự mình thử nghiệm nhiều hơn, hãy thử loại bỏ phương thức equals() hoặc hashCode() và quan sát kết quả.

Tham khảo

https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#equals-java.lang.Object-https://docs.oracle.com/javase/8/docs/api/java/lang/Object.html#hashCode–

Check Code Giày Michael Kors

Michael Kors là một thương hiệu giày nổi tiếng và luôn chiếm phần lớn trái tim yêu thích của nhiều chị em. Tuy nhiên, hiện nay nhiều nhà sản xuất lại tận dụng cơ hội này và lừa dối người tiêu dùng bằng cách bán những đôi Michael Kors giả với giá ngang ngửa giày chính hãng.

Tuy nhiên, bạn cũng nên lưu ý bởi có những trường hợp hộp đựng giày Auth cũng vẫn có thể bị méo mó, ọp ẹp do quá trình vận chuyển bị va chạm.

Nếu bạn thấy giày không gắn tag thì bạn cũng đừng hoang mang vì một số hãng không có gắn tag vào sản phẩm. Việc có gắn tag hay không, không phải là yếu tố tiên quyết để xác định sản phẩm là auth hay fake.

Đối với các sản phẩm giày Michael Kors, hãng không sản xuất tag gắn vào sản phẩm.

3. Cách check code giày Michael Kors

Trên mỗi hộp giày Michael Kors luôn có thông tin sản phẩm rất cụ thể nên đây là một yếu tố quan trọng để giúp bạn xác định được đâu là thật đâu là giả.

Mỗi kiểu giày sẽ có 1 mã code sản phẩm. Khi xác định được mã code, bạn hãy kiểm tra qua như sau:

3.1. Check code giày qua chúng tôi

Nhập mã code vào tìm kiếm tại website của Michael Kors để xem mã code style có tồn tại. Nếu sản phẩm còn hàng thì bạn sẽ nhìn thấy sản phẩm trên website. Nếu mã sản phẩm không tìm thấy thì bạn cũng đừng quá lo lắng bởi sản phẩm có thể đã hết hàng hoặc mã đó không tồn tại trên website.

3.2. Check code giày qua chúng tôi

Search mã code trên google. Nếu hiển thị đúng chính xác tên giày, kiểu giày như sản phẩm thì bạn có thể yên tâm. Còn không hiển thị hoặc hiển thị những kết quả khác thì cần xem xét lại sản phẩm vì rất có thể là hàng giả.

4. Cách check mã vạch (mã UPC)

Bên cạnh mã code sản phẩm, trên hộp giày còn có một loạt mã khác mà bạn rất cần quan tâm khi muốn xác định giày chính hãng đó là mã vạch hay còn gọi là mã UPC. Với mã này bạn có thể kiểm tra giày auth hay fake bằng cách:

4.1. Check qua các website check mã UPC uy tín

Sử dụng mã UPC kiểm tra thông tin sản phẩm thông qua các website tin cậy như https://www.upcindex.com/ hoặc https://www.upcitemdb.com/… Hệ thống sẽ cung cấp cho bạn phần lớn những thông tin về sản phẩm, giúp bạn yên tâm hơn về sản phẩm.

4.2. Check bằng phần mềm quét QR code

Với các phần mềm quét QR code thì độ chính xác thường không cao do database của phần mềm check code thường cập nhật chậm hơn so với thị trường hiện tại hoặc không có đầy đủ thông tin của các sản phẩm hoặc không có dữ liệu sản phẩm từ hãng Michael Kors. Nên nhiều khi quét mã vạch sẽ không có thông tin về sản phẩn. Vì vậy, cách kiểm tra này chỉ nên được xem là một biên pháp có tính chất tham khảo, bổ sung thông tin.

Lưu ý: Cùng với sự phát triển của các ứng dụng QR code và trang web check mã vạch cũng là sự phát triển của công nghệ làm giả mã vạch ngày càng tinh vi và chuyên nghiệp. Vậy nên, hãy nhớ rằng mã vạch hay mã QR không hoàn toàn là công cụ để kiểm tra hàng giả hàng nhái.

Vì vậy lời khuyên cho các bạn mua hàng là tốt nhất nên tìm những kênh bán uy tín, đừng ham rẻ mà mua nhầm phải hàng nhái. Hy vọng qua bài viết này sẽ giúp các bạn có thêm kinh nghiệm check code giày, để tránh mua phải những hàng giả, hàng kém chất lượng và lựa chọn được kênh mua hàng uy tín, chất lượng.

Pumi Store vẫn luôn là cầu nối uy tín nhất giúp bạn mua được những sản phẩm chính hãng một cách an tâm và dễ dàng nhất. Hãy truy cập ngay https://pumistore.com/ hoặc Fanpage Pumi Store hoặc gọi theo Hotline 0995 84 5555 để tham khảo các sản phẩm chính hãng và được tư vấn nhiệt tình! từ đội ngũ chăm sóc khách hàng của Pumi Store.