Phương pháp đơn hình cải tiến để giải các bài toán quy hoạch mục tiêu. Phương pháp đơn giản sửa đổi
Ý tưởng cơ bản của phương pháp đơn hình sửa đổi là sử dụng ma trận nghịch đảo hiện tại (và dữ liệu gốc của bài toán) để thực hiện các phép tính cần thiết nhằm xác định các biến cần bao gồm và loại trừ. Biểu diễn ma trận nghịch đảo ở dạng nhân cho phép bạn tính toán một chuỗi ma trận nghịch đảo trực tiếp từ dữ liệu gốc mà không cần sử dụng nhiều phép toán nghịch đảo cho mỗi cơ sở. Như trong phương pháp đơn hình thông thường, trong trường hợp này cơ sở ban đầu luôn là ma trận đơn vị I, nghịch đảo của ma trận này là chính ma trận này. Vì vậy, nếu 
- Dãy ma trận nghịch đảo tương ứng với các lần lặp 1, 2,…,i, và 
là dãy ma trận tương ứng với chúng thì
Trình tự thay thế dẫn đến công thức sau:
(2.23)
Cần nhấn mạnh rằng cách biểu diễn nhân của ma trận nghịch đảo là không thủ tục cần thiếtđể triển khai sơ đồ tính toán của phương pháp đơn hình đã sửa đổi và tại mỗi lần lặp, bạn có thể sử dụng bất kỳ phương pháp nào để đảo ngược cơ sở hiện tại. Khi sử dụng phương pháp đơn hình đã sửa đổi, điều quan trọng là ma trận nghịch đảo được tính toán theo cách làm giảm tác động của lỗi làm tròn máy.
Các bước của thuật toán phương pháp đơn giản sửa đổi về cơ bản giống như các bước của thuật toán phương pháp đơn giản thông thường. Sau khi tìm được cơ sở I ban đầu xác định được vectơ hệ số tương ứng hàm mục tiêu
, các phần tử của chúng được hình thành tùy thuộc vào việc các biến cơ bản ban đầu là dư thừa (dư thừa) hay nhân tạo.
2.7.2. Biểu diễn nhân của ma trận nghịch đảo
Trong biểu diễn nhân của ma trận nghịch đảo, phép toán đại số ma trận được sử dụng để tính các phần tử của ma trận nghịch đảo đối với ma trận mới của các vectơ cơ sở từ ma trận nghịch đảo đã biết của cơ sở trước đó, với điều kiện hai cơ sở đang xét chỉ khác nhau ở điểm vectơ một cột Phương pháp biểu diễn ma trận nghịch đảo này rất thuận tiện khi sử dụng trong sơ đồ tính toán của phương pháp đơn hình, vì các cơ số tương ứng với mỗi hai lần lặp liên tiếp chỉ khác nhau ở một cột (do thay thế vectơ cột bị loại bỏ của cơ sở hiện tại). với một vectơ cột mới). Nói cách khác, ma trận cơ sở hiện tại 
và một ma trận cơ sở mới 
, tương ứng với lần lặp tiếp theo, chỉ khác nhau ở một cột. Với cách biểu diễn nhân của ma trận nghịch đảo 
tương ứng với cơ sở mới, nó được tính bằng cách nhân nghịch đảo của ma trận hiện tại ở bên trái 
thành một ma trận được hình thành theo những quy tắc nhất định 
.
Hãy xác định ma trận nhận dạng 
theo cách sau:
(2.24)
Ở đâu 
- vectơ cột đơn vị với phần tử thứ i, bằng một, và các phần tử khác, bằng 0. Giả sử các ma trận đã biết 
Và 
, và vectơ 
ma trận 
được thay thế bằng một vectơ mới 
; như thông lệ khi mô tả phương pháp đơn hình, vectơ 
được định nghĩa là được bao gồm trong cơ sở và vectơ 
- như bị loại trừ khỏi cơ sở. Để đơn giản hóa việc viết các mối quan hệ toán học, chúng ta sử dụng định nghĩa sau 
,trong đó 
sẽ đại diện cho phần tử thứ k 
. Khi đó ma trận nghịch đảo mới 
có thể được tính bằng công thức sau:
(2.25)
miễn là 
. Nếu như 
, ma trận 
không tồn tại. Lưu ý rằng ma trận 
thu được từ ma trận 
bằng cách thay thế vectơ cột thứ r của nó 
cột 
.
Vấn đề tối ưu hóa trong toán học là bài toán tìm cực trị của một hàm số thực trong một vùng nhất định. Theo quy định, các miền thuộc về và được xác định bởi một tập hợp các đẳng thức và bất đẳng thức sẽ được xem xét.
3.1. Sự miêu tả
Nhiệm vụ lập trình tuyến tính bao gồm thực tế là cần phải cực đại hóa hoặc cực tiểu hóa một số hàm tuyến tính trên một không gian đa chiều dưới các ràng buộc tuyến tính đã cho.
Mỗi bất đẳng thức tuyến tính trong các biến giới hạn một nửa không gian trong không gian tuyến tính tương ứng. Kết quả là mọi bất đẳng thức đều giới hạn một khối đa diện nhất định (có thể là vô hạn), còn gọi là hình nón đa diện.
Phương trình W(x) = c, trong đó W(x) là hàm tuyến tính cần cực đại hóa (hoặc cực tiểu), tạo ra siêu phẳng L(c). Sự phụ thuộc vào c tạo ra một họ các siêu phẳng song song. Trong trường hợp này, bài toán cực trị có công thức sau: cần tìm c lớn nhất sao cho siêu phẳng L(c) cắt khối đa diện ít nhất tại một điểm. Lưu ý rằng giao điểm của một siêu phẳng tối ưu và một khối đa diện sẽ chứa ít nhất một đỉnh và sẽ có nhiều đỉnh nếu giao điểm chứa một cạnh hoặc một mặt k chiều. Do đó, có thể tìm cực đại của hàm số tại các đỉnh của khối đa diện. Nguyên tắc của phương pháp đơn hình là chọn một trong các đỉnh của khối đa diện, sau đó chuyển động bắt đầu dọc theo các cạnh của nó từ đỉnh này sang đỉnh khác theo hướng tăng giá trị của hàm. Khi chuyển đổi dọc theo một cạnh từ đỉnh hiện tại sang đỉnh khác có nhiều hơn giá trị cao chức năng là không thể, người ta giả định rằng giá trị tối ưu của c đã được tìm thấy.
Bản chất của phương pháp đơn hình là nếu số lượng ẩn số số lượng nhiều hơn thì phương trình hệ thống này không chắc chắn với vô số giải pháp. Để giải hệ thống, tất cả các ẩn số được chia tùy ý thành cơ bản và miễn phí. Số lượng biến cơ bản được xác định bởi số phương trình độc lập tuyến tính. Những ẩn số còn lại là miễn phí. Chúng được đưa ra các giá trị tùy ý và sau đó được thay thế vào hệ thống. Bất kỳ tập hợp ẩn số tự do nào cũng có thể được cho vô số giá trị tùy ý, giá trị này sẽ cho vô số nghiệm. Nếu tất cả các ẩn số tự do được đặt thành 0 thì giải pháp sẽ bao gồm các giá trị của các ẩn số cơ bản. Giải pháp này được gọi là cơ bản.
Trong lý thuyết quy hoạch tuyến tính, có một định lý phát biểu rằng trong số các nghiệm cơ bản của hệ thống, người ta có thể tìm ra nghiệm tối ưu, và trong một số trường hợp, một số nghiệm tối ưu, tất cả đều cung cấp một cực trị của hàm mục tiêu. Vì vậy, nếu bạn tìm thấy một số kế hoạch cơ bản và sau đó cải thiện nó, bạn sẽ nhận được giải pháp tối ưu. Phương pháp đơn giản được xây dựng trên nguyên tắc này.
Trình tự tính toán sử dụng phương pháp đơn hình có thể được chia thành hai giai đoạn chính:
1. Tìm đỉnh đầu của tập hợp phương án khả thi;
2. Chuyển đổi tuần tự từ đỉnh này sang đỉnh khác, dẫn đến tối ưu hóa giá trị của hàm mục tiêu.
Trong một số trường hợp, lời giải ban đầu là hiển nhiên hoặc việc xác định nó không yêu cầu tính toán phức tạp, - ví dụ: khi tất cả các ràng buộc được biểu thị bằng các bất đẳng thức có dạng "nhỏ hơn hoặc bằng" (khi đó vectơ 0 hoàn toàn là một giải pháp có thể chấp nhận được, mặc dù rất có thể, nó không còn tối ưu nữa). Trong những bài toán như vậy, giai đoạn đầu tiên của phương pháp đơn hình có thể được bỏ qua hoàn toàn. Phương pháp đơn giản được chia thành một pha Và
hai pha.
3.2. Thuật toán phương pháp đơn giản
Tuyên bố vấn đề tăng cường
Xét bài toán quy hoạch tuyến tính sau:
Bây giờ chúng ta hãy đặt vấn đề này ở dạng tăng cường tương đương. Cần tối đa hóa Z, trong đó:
Ở đây x là các biến từ hàm tuyến tính ban đầu; x s – các biến mới bổ sung cho các biến cũ sao cho bất đẳng thức trở thành đẳng thức; c – hệ số của hàm tuyến tính ban đầu; Z là biến cần được tối đa hóa. Các nửa không gian và tại giao điểm tạo thành một khối đa diện biểu diễn tập hợp các giải pháp khả thi. Sự khác biệt giữa số lượng biến và phương trình cho biết số bậc tự do. Nói một cách đơn giản, nếu chúng ta xem xét đỉnh của một khối đa diện, thì đây là số cạnh mà chúng ta có thể tiếp tục di chuyển.
Sau đó chúng ta có thể gán giá trị 0 cho số biến này và gọi
Cơ quan Giáo dục Liên bang
Tình trạng cơ sở giáo dục giáo dục chuyên nghiệp cao hơn
Đại học Kỹ thuật bang Perm
Chi nhánh Lysvensky
Khoa Kinh tế
Khóa học
trong bộ môn “Phân tích hệ thống và nghiên cứu vận hành”
về chủ đề: “Phương pháp đơn giản trong hình thức trình bày”
Hoàn thành bởi sinh viên nhóm VIVT-06-1:
Startseva N. S.
Giáo viên kiểm tra:
Mukhametyanov I.T.
Lysva 2010
Giới thiệu. 3
Lập trình toán học. 5
Phương pháp đồ họa. 6
Phương pháp đơn giản dạng bảng. 6
Phương pháp cơ sở nhân tạo. 7
Đơn giản sửa đổi- phương pháp. 7
Phương pháp đơn giản kép. 7
Tổng quan về bài toán quy hoạch tuyến tính. 9
Giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình. mười một
Quy trình tính toán của phương pháp đơn hình. mười một
Định lý 1: 13
Định lý 2: 14
Định lý 3: 15
Định lý 4: 15
Định lý 5: 15
Chuyển sang một kế hoạch tham khảo mới. 15
Nhiệm vụ kép. 17
Định lý 1 (định lý nhị nguyên thứ nhất) 18
Định lý 2 (định lý nhị nguyên thứ hai) 18
Phần kết luận. 20
Lời giải tối ưu cho bài toán quy hoạch tuyến tính nằm trong số các lời giải tham khảo. Ý tưởng của phương pháp đơn hình là, theo một quy tắc nhất định, các giải pháp tham chiếu được sắp xếp cho đến khi tìm thấy giải pháp tối ưu trong số đó. Bằng cách sắp xếp qua các giải pháp tham chiếu, về cơ bản, chúng ta đang sắp xếp các biến cơ bản khác nhau, tức là. , ở bước tiếp theo, một số biến được chuyển từ số biến cơ bản và thay vào đó là một số biến từ số lượng biến tự do sang số lượng biến cơ bản.
7x 1 +5x 2 → tối đa
x 3 =19-2x 1 -3x 2 (0;0;19;13;15;18)
x 4 =13-2x 1 -x 2 sơ đồ tham chiếu ban đầu
x 6 =18-3x 1 F(x 1 , x 2)=7*0+5*0=0
x i ≥0, (i=1,…n)
Ở mức độ trực quan, rõ ràng là việc tăng x 1 là điều đương nhiên, vì hệ số của nó lớn hơn của x 2. Để x 2 = 0, ta có thể tăng cho đến khi x 3 , x 4 , x 5 , x 6 không âm.
x 1 =phút(19/2;13/2;∞;18/3)=6
Điều này có nghĩa là khi x 1 = 6, x 6 = 0, tức là x 1 là số lượng cái cơ bản và x 6 là số lượng cái tự do.
x 3 =19-2(6-1/3 x 6)-3 x 2 =19-12+2/3 x 6 -3 x 2 =7+2/3 x 6 -3 x 2
x 4 =13-2(6-1/3 x 6)- x 2 =1+2/3 x 6 - x 2
F(x 2 ; x 6) =42-7/3 x 6 +5 x 2
Với một kế hoạch tham chiếu nhất định (6;0;7;1;15;0) x 2, chuyển từ các biến miễn phí sang các biến cơ bản:
x 2 =phút(∞;7/3;1/11;15/3)=1
Thể hiện x 2 đến x 4
x 2 =1+2/3 x 6 - x 4
Chúng tôi biểu thị các biến chưa biết và hàm mục tiêu theo các biến tự do:
x 3 =7+2/3 x 6 -3(1+2/3x 6 –x 4)= 7+2/3 x 6 -3-2x 6 +3x 4 =4-4/3x 6 +3 x 4
x 5 = 12-2x 6 +3x 4 -
F=42-7/3 x 6 +5(1+2/3x 2 - x 4) =47-7/3x 6 +10/3x 6 -5x 4 =47+x 6 -5x 4
x 6 là dương nên có thể tăng lên
x 6 =phút(18;∞;3;6)=1
x 4 =4/3-4/9 x 6 - 1/3x 3
F=47+x 6 -5(4/3-4/9-1/3x 3)
Trong hàm mục tiêu, tất cả các hệ số của các biến đều âm, giá trị của hàm không thể tăng lên; ta biến đổi tương tự các biến còn lại, tìm phương án tham chiếu, từ đó xác định x 1, x 2.
1. Giao của các tập đóng, tập hợp các giới hạn không tầm thường.
2. Tập nghiệm của hệ bất đẳng thức và phương trình tuyến tính không chặt chẽ là tập đóng.
αX=(αx 1 ,x 2 ,…, αx n)
X+Y=(x 1 +y 1, x 2 +y 2,… x n +y n)
Tọa độ tuyến tính X 1 ,X 2 ,…X n được gọi là điểm P=λ 1 x 1 + λ 2 x 2 +…+ λ k x k
Đặt P=(λ 1 x 1 + λ 2 x 2 +…+ λ k x k ) 0≤ h i ≤1 for i= 1,…k n åR i =1, 1≤ i ≤k tổ hợp tuyến tính lồi của các điểm x 1 ,x 2,…x n . Nếu k=2 thì tập hợp này được gọi là một đoạn. X 1,X 2 – các đầu của đoạn. Điểm góc của một tập đóng là một điểm không phải là tổ hợp tuyến tính không tầm thường của các điểm trong tập hợp (điểm góc).
Tính không tầm thường có nghĩa là ít nhất một trong các λ khác 0 hoặc 1.
 |
Bất kỳ giải pháp tham chiếu nào cho bài toán quy hoạch tuyến tính đều là điểm góc của vùng các giải pháp khả thi.
Nếu một bài toán quy hoạch tuyến tính có nghiệm duy nhất thì nó nằm trong số các điểm góc của ODP. Và nếu có nhiều hơn một nghiệm thì trong số các nghiệm đó có một số nghiệm góc, sao cho tập hợp tất cả các nghiệm là tổ hợp tuyến tính lồi của chúng.
Phương pháp đơn giản trước tiên bao gồm việc tìm ra một giải pháp tham chiếu nhất định cho vấn đề (phương án tham chiếu ban đầu), sau đó, chuyển từ phương án tham chiếu này sang phương án tham chiếu khác một cách có mục đích, tìm kiếm phương án tối ưu. Nếu có một vài trong số chúng, thì tất cả các góc đều được tìm thấy và tập hợp các giải pháp được biểu diễn dưới dạng tổ hợp tuyến tính của chúng.
Chuyển sang kế hoạch tham chiếu mới
F 1 =F(x 1); F 2 =F(x 2) F 2 -F 1 =-υ k Δ k =F 2 có thể được chứng minh, trong đó υ k là giá trị nhỏ nhất được xem xét ở trên, được xác định bằng cách đưa biến thứ k vào cơ sở, và Δ k =åс j x j ( 1) -С k, trong đó n ≤ j 1, X 1 =(x 1 (1) ;x 2 (1) ;…x n (1)) là ước lượng của biến thứ k , vậy nếu giải được bài toán cực đại thì giá trị ΔF 2 phải dương, Δk phải âm. Khi giải các bài toán tối thiểu thì ΔF 2 là âm, Δ k là dương. Các giá trị này được tính toán và nếu trong ΔF 2 tất cả các giá trị đều không dương thì khi giải các bài toán ở mức tối thiểu, điều ngược lại là đúng. Nếu, khi giải cực đại, có một vài số dương trong số ΔF 2, thì chúng ta đưa vào cơ sở vectơ mà tại đó giá trị này đạt cực đại và nếu bài toán được giải ở mức tối thiểu và trong số ΔF 2 thì có một số số âm 1 thì vectơ có giá trị nhỏ nhất ΔF 2 được đưa vào cơ sở, nghĩa là có giá trị lớn nhất giá trị tuyệt đối. Khi những điều kiện này được đáp ứng, sự thay đổi lớn nhất có thể có về giá trị của hàm sẽ được đảm bảo.
Lời giải của bài toán sẽ là duy nhất nếu với bất kỳ vectơ x k nào không có trong cơ sở, ước lượng Δ k ≠0, nếu ít nhất một trong các vectơ này Δ k = 0 thì lời giải không phải là duy nhất, để tìm lời giải khác chúng ta chuyển sang một phương án tham chiếu khác, bao gồm cả cơ sở x k, trong đó Δ k = 0. Việc tìm kiếm qua tất cả các giải pháp hỗ trợ như vậy sẽ tạo thành một tổ hợp tuyến tính, đây sẽ là giải pháp cho vấn đề.
Nếu với bất kỳ Δ k nào đó, các hệ số của biến x k ≤ 0 mâu thuẫn với điều kiện tối ưu thì hệ hạn chế không bị giới hạn, tức là không có phương án tối ưu.
Vấn đề kép
Bài toán kép (DP) là một bài toán quy hoạch tuyến tính phụ được xây dựng bằng cách sử dụng các quy tắc nhất định trực tiếp từ các điều kiện của bài toán trực tiếp. Mối quan tâm đến việc xác định lời giải tối ưu cho một bài toán trực tiếp bằng cách giải bài toán kép của nó là do thực tế là các phép tính khi giải một DP có thể trở nên ít phức tạp hơn so với khi giải một bài toán trực tiếp (DP). Độ phức tạp của phép tính khi quyết định của PPP phụ thuộc nhiều hơn vào số lượng ràng buộc hơn là số lượng biến. Để đi đến điều khiển từ xa, kiến thức kỹ thuật phải được viết theo tiêu chuẩn hình thức kinh điển. Khi trình bày PP ở dạng chuẩn, các biến xj cũng bao gồm các biến dư thừa và dư thừa.
Vấn đề kép có:
1. m biến tương ứng với số ràng buộc của bài toán trực tiếp;
2. n ràng buộc tương ứng với số biến của bài toán trực tiếp.
Bài toán kép thu được bằng cách biến đổi cấu trúc đối xứng các điều kiện của bài toán trực tiếp theo các quy tắc sau:
· Mỗi ràng buộc b i PD tương ứng với một biến y i PD;
· Mỗi biến x j PD tương ứng với một ràng buộc C j PD;
· Các hệ số x j trong ràng buộc PD trở thành các hệ số bên trái của ràng buộc PD tương ứng;
· Các hệ số Cj cho x j trong hàm mục tiêu của PD trở thành hằng số ở vế phải của ràng buộc PD;
· Các hằng số ràng buộc b i PD trở thành hệ số của hàm đích PD.
Hãy xem xét hai vấn đề sau:
F = С 1 x 1 +С 2 x 2 +... +С n x n →max
|
a 21 x 1 + a 22 x 2 + ... + a 2m x n ≤b 2
a m1 x 1 + a m2 x 2 + ... + a mn x n ≤b m
x j ≥0 j=1,…,n
Z = b 1 x 1 +b 2 x 2 +... +b n x n →phút
|
a 12 y 1 + a 22 y 2 + ... + a m 2 y 2 ≤C 2
. . . . . . . . . . . . . . . . . . . . . . .
a 1 n y n + a 2 m y n + ... + a nm y n ≤C n
Trong này khóa học nền móng đã được đặt phương pháp toán học giải các bài toán quy hoạch tuyến tính. Vì vậy, người ta chú ý nhiều hơn đến các phần sau:
1. Cơ sở của các phương pháp toán học và ứng dụng của chúng;
2. Giải bài toán bằng phương pháp đơn hình.
PHƯƠNG PHÁP ĐƠN GIẢN SỬA ĐỔIPhương pháp đơn giản không phải là phương pháp hiệu quả nhất
thủ tục máy tính, vì nó tính toán và
lưu trữ thông tin không cần thiết cho hiện tại
lặp đi lặp lại và có thể không được sử dụng cho
đưa ra quyết định trong các lần lặp tiếp theo. Vì
hệ số của các biến không chính trong phương trình
(0), hệ số của các biến chính được giới thiệu
trong các phương trình khác và vế phải của phương trình tại
Mỗi lần lặp chỉ sử dụng cái có liên quan
thông tin. Vì vậy cần có một quy trình
có thể có được thông tin này một cách hiệu quả mà không cần
tính toán và lưu trữ tất cả các hệ số khác
(đây là phương pháp đơn giản đã được sửa đổi).
cần thiết cho khoảnh khắc này, và dữ liệu quan trọng
truyền tải dưới dạng nhỏ gọn hơn.
Nó sử dụng các phép toán ma trận, vì vậy
cần phải mô tả bài toán bằng ma trận.
CHỮ HOA, được đánh dấu in đậm
biểu thị ma trận, chữ in hoa,
những người in đậm đại diện
vectơ.
Chữ nghiêng là đại lượng vô hướng, được đánh dấu bằng 0
(0) biểu thị vectơ 0 (các phần tử của nó bằng nhau
không, cả hàng và cột), không (0)
đại diện cho số 0 bình thường. Sử dụng
ma trận dạng chuẩn của mô hình tuyến tính
lập trình có dạng: Tối đa hóa Z = c x,
dựa theo
A x ≤ b và x ≥ 0,
trong đó c là một vectơ hàng
vectơ cột x, b và 0 A - ma trận
Đối với dạng mở rộng, vectơ cột
biến giả:
Những hạn chế:
I = (m × m ma trận đồng nhất)
0 = (n + m phần tử của vectơ 0) Tìm giải pháp cơ bản khả thi
Cách tiếp cận chung của phương pháp đơn giản là thu được
trình tự cải thiện các giải pháp OA lên đến
cho đến khi tìm được phương án tối ưu
giải pháp. Một trong những tính năng chính
phương pháp đơn giản đã sửa đổi - nó như thế nào
tìm ra giải pháp OD mới sau khi xác định nó
chính (cơ bản) và không cơ bản (không cơ bản)
biến. Với các biến này, kết quả
nghiệm chính – nghiệm của phương trình m
Trong đó n biến không cơ bản từ n + m
yếu tố
được đặt bằng 0. Loại bỏ n biến này bằng cách đặt chúng về 0,
ta thu được hệ phương trình m với m biến
(biến chính (cơ bản)):
đâu là vectơ của các biến cơ bản:
thu được bằng cách loại trừ không cơ bản (không cơ bản)
biến: Và ma trận cơ sở
Kết quả thu được bằng cách loại trừ các cột tương ứng với
hệ số của các biến không cơ bản từ .
(Ngoài ra, các phần tử xB và cột B có vị trí khác nhau.
được rồi). Phương pháp đơn giản chỉ giới thiệu cơ bản
các biến sao cho B không suy biến, do đó
ma trận nghịch đảo B-1 sẽ luôn tồn tại.
Để giải B x B = b, cả hai vế đều được nhân với B-1:
B-1 B x B = B-1 b. cB là một vectơ có các phần tử là hệ số
các hàm mục tiêu (bao gồm các số 0 cho giả
biến) cho các phần tử xB tương ứng.
Hàm mục tiêu của nghiệm cơ bản này là: Ví dụ:
- Lặp lại 0
Vì thế
Vì thế
10.
- Lặp lại 1Vì thế
Vì thế
11.
- Lặp lại 2Vì thế
Vì thế
12. Dạng ma trận của tập phương trình hiện tại
Dạng ma trận cho một tập hợp các phương trình,xuất hiện trong bảng đơn giản cho bất kỳ lần lặp nào
phương pháp đơn giản ban đầu. Đối với hệ thống nguồn
phương trình, dạng ma trận là:
Các phép tính đại số được thực hiện bằng phương pháp đơn hình (nhân phương trình với một hằng số và cộng
tích của phương trình này với phương trình khác) được biểu thị bằng
dạng ma trận, sau khi nhân cả hai phần
hệ phương trình ban đầu thành hệ phương trình tương ứng
ma trận
13.
14.
Ma trận này sẽ có các phần tử giống như ma trận danh tínhma trận, ngoại trừ mỗi sản phẩm
đối với một phép toán đại số nhất định sẽ mất
không gian cần thiết để thực hiện thao tác này,
sử dụng phép nhân ma trận. Ngay cả sau loạt phim
các phép toán đại số qua nhiều lần lặp,
chúng ta vẫn có thể kết luận rằng ma trận này
nên dành cho toàn bộ loạt bài, sử dụng những gì chúng ta biết về
bên phải hệ thống mới phương trình. Sau bất kỳ
lần lặp, xB = B-1b và Z = cB B-1b, do đó vế phải
hệ phương trình mới có dạng
15.
Vì chúng ta thực hiện cùng một chuỗicác phép toán đại số với cả hai vế
tập hợp ban đầu, để nhân bên phải và
ở phía bên trái, chúng tôi sử dụng cùng một ma trận.
Kể từ đây,
Dạng ma trận mong muốn của hệ phương trình
sau bất kỳ lần lặp nào:
16.
Ví dụ: dạng ma trận thu được sau lần lặp 2cho bài toán nhà máy thủy tinh sử dụng B-1 và cB:
17.
Sử dụng các đại lượng xB = B-1 b và Z = cB B-1 b:18.
Chỉ nhận B-1 để tính toántất cả các số của bảng đơn từ bảng gốc
tham số nhiệm vụ (A, b, cB). Bất kỳ số nào trong số này
có thể được lấy riêng lẻ như
Theo quy định, chỉ phép nhân vectơ được thực hiện
(một hàng trên mỗi cột) thay vì đầy đủ
Phép nhân ma trận. Số cần thiết cho
việc thực hiện các phép lặp của phương pháp đơn giản có thể
nhận khi cần thiết mà không cần chi tiêu
tính toán không cần thiết để có được tất cả các con số.
19. Tổng quan ngắn gọn về phương pháp đơn hình cải tiến
1. Khởi tạo: Như trong phương pháp đơn giản ban đầu.2. Lặp lại: Bước 1 Xác định cơ bản (chính) đã nhập
biến: Như trong phương pháp đơn giản ban đầu.
Bước 2 Xác định các biến cơ sở đầu ra: Như ban đầu
phương pháp đơn giản, ngoại trừ việc chỉ đếm những gì cần thiết cho
của những con số này [hệ số của các biến cơ bản được giới thiệu trong
mỗi phương trình ngoại trừ phương trình. (0), và sau đó, với mỗi
hệ số dương phần bên phải phương trình này].
Bước 3 Xác định nghiệm OD mới: Lấy B-1 và đặt xB=B-1b.
3. Phân tích tối ưu: Như trong phương pháp đơn giản ban đầu, đối với
ngoại trừ việc chỉ đếm những con số cần thiết cho việc phân tích này,
tức là hệ số của các biến không cơ bản (không cơ bản) trong
Phương trình (0).
Ở bước 3 của lần lặp, có thể thu được B-1 mỗi lần sử dụng
tiêu chuẩn chương trình máy tínhđể đảo ngược (đảo ngược)
ma trận. Vì B (sau đó là B-1) thay đổi rất ít từ lần lặp này sang lần lặp khác.
khác, sẽ hiệu quả hơn nếu có được B-1 mới (ký hiệu là B-1 mới) từ
B-1 bật lần lặp trước(B-1 cũ). (Đối với giải pháp OA ban đầu).
Có nhiều phương pháp để giải các bài toán quy hoạch tuyến tính. Hãy xem xét một trong số đó, phương pháp đơn giản được cải tiến (đã sửa đổi)
Đầu tiên, hãy cho bạn biết phương pháp đơn hình là gì. Từ SIMPLEX theo nghĩa thông thường có nghĩa là đơn giản, không phức tạp, trái ngược với COMPLEX.
Phương pháp này có nhiều dạng (sửa đổi) khác nhau và được phát triển vào năm 1947 bởi G. Danzig.
Bản chất của phương pháp đơn hình là nếu số ẩn lớn hơn số phương trình thì hệ đã cho là không chắc chắn với vô số nghiệm. Để giải hệ thống, tất cả các ẩn số được chia tùy ý thành cơ bản và miễn phí. Số lượng biến cơ bản được xác định bởi số phương trình độc lập tuyến tính. Những ẩn số còn lại là miễn phí. Chúng được đưa ra các giá trị tùy ý và được thay thế vào hệ thống. Bất kỳ tập hợp ẩn số tự do nào cũng có thể được cho vô số giá trị tùy ý, giá trị này sẽ cho vô số nghiệm. Nếu tất cả các ẩn số tự do được đặt thành 0 thì giải pháp sẽ bao gồm các giá trị của các ẩn số cơ bản. Giải pháp này được gọi là cơ bản.
Trong lý thuyết quy hoạch tuyến tính, có một định lý phát biểu rằng trong số các nghiệm cơ bản của hệ thống, người ta có thể tìm ra nghiệm tối ưu và trong một số trường hợp có thể tìm ra một số nghiệm tối ưu, nhưng tất cả chúng đều cung cấp một cực trị của hàm mục tiêu. Vì vậy, nếu bạn tìm thấy một số phương án cơ bản và sau đó cải thiện nó, bạn sẽ có được giải pháp tối ưu. Phương pháp đơn giản được xây dựng trên nguyên tắc này.
Một trong những sửa đổi của phương pháp đơn giản là phương pháp đơn giản được cải tiến. Trong tài liệu, phương pháp này còn được gọi là phương pháp ma trận nghịch đảo hoặc phương pháp đơn hình sửa đổi.
Khi giải các bài toán quy hoạch tuyến tính trong đó n (số biến) lớn hơn đáng kể so với m (số ràng buộc), phương pháp đơn giản cải tiến yêu cầu ít hoạt động tính toán và bộ nhớ máy tính hơn đáng kể so với các phương pháp khác.
Phương pháp đơn hình cải tiến thực hiện ý tưởng cơ bản giống như phương pháp đơn giản thông thường, nhưng ở đây, tại mỗi lần lặp, không phải toàn bộ ma trận A -1, nghịch đảo của ma trận ràng buộc A, được tính toán lại mà chỉ phần đó liên quan đến cơ sở hiện tại A x.
Chúng ta hãy xem xét từng bước các bước giải bài toán quy hoạch tuyến tính bằng phương pháp đơn hình cải tiến:
- 1. Đầu chu kỳ đầu tiên ta biết ma trận nghịch đảo (ma trận nhận dạng), giải pháp cơ bản xb = b.
- 2. Đối với mỗi biến không cơ bản, chúng ta xây dựng sai phân đặc trưng j bằng phương trình:
j = c j -- = c j -- P j , (2)
các biến kép ở đâu, có thể được tìm thấy như sau:
trong đó c x là vectơ hệ số của hàm mục tiêu đối với các biến cơ bản.
3. Giả sử sử dụng quy tắc chuẩn để chọn cột đầu vào, chúng ta thấy:
- 4. Nếu s 0, quy trình sẽ dừng. Giải pháp cơ bản hiện nay là tối ưu.
- 5. Nếu s 0 thì tính cột chuyển đổi:
= (, ...,) . (2.4)
Nếu tất cả đều bằng 0 thì quy trình dừng lại: mức tối ưu là không giới hạn.
7. Ngược lại, ta tìm biến suy ra từ cơ số:
8. Chúng tôi xây dựng một ma trận mở rộng:
và biến đổi nó với phần tử hàng đầu. M cột đầu tiên cho ma trận nghịch đảo của cơ sở mới.
9. Chuyển đổi giải pháp cơ bản:
x b i x b tôi -- * , i r, (2.7)
và chuyển sang giai đoạn 2.
Tùy chọn này còn được gọi là phương pháp đơn giản đã sửa đổi vì nó làm giảm số lượng tính toán ở mỗi bước. Ý tưởng là ở mỗi bước, dạng chính tắc của bài toán đối với cơ sở hiện tại có thể được thu được độc lập với các dạng khác trực tiếp từ bản ghi gốc. nhiệm vụ tiêu chuẩn LP.
Để làm điều này bạn cần:
- 1. Duy trì hồ sơ gốc của nhiệm vụ trong suốt quá trình vận hành phương pháp; đây là cái giá bạn phải trả để đạt được hiệu quả cao hơn;
- 2. Sử dụng cái gọi là đơn hình - hệ số nhân p - để chuyển trực tiếp từ bản ghi ban đầu của bài toán sang dạng cơ sở kinh điển hiện tại của nó;
- 3. Sử dụng cơ sở đảo ngược BO№ - ma trận có kích thước m x m, cho phép tính cột đầu aґs ở mỗi bước và cập nhật đơn hình - thừa số p.
Phương pháp đơn giản cải tiến có những ưu điểm đáng kể so với dạng tiêu chuẩn. Điều này áp dụng cho các yêu cầu về độ chính xác, tốc độ và bộ nhớ. Hầu hết những lợi thế này được xác định bởi thực tế là, theo quy luật, các ma trận có kích thước lớn vấn đề tuyến tính(nghĩa là với n>m>100) được lấp đầy yếu, chứa một tỷ lệ nhỏ các phần tử khác 0.
Mật độ từ 5% trở xuống là phổ biến. Một dạng cải tiến của phương pháp đơn giản có khả năng tận dụng tốt hơn những lợi thế phát sinh từ thực tế này. Ở dạng này, các sai phân đặc tính và vectơ dẫn đầu được tính toán trực tiếp từ dữ liệu gốc. Vì ma trận ban đầu được điền kém và phép nhân chỉ nên được thực hiện khi cả hai thừa số khác 0, thời gian tính toán giảm đáng kể.
Ngoài ra, chỉ sử dụng dữ liệu gốc đồng nghĩa với việc giảm khả năng tích lũy lỗi làm tròn. Ngược lại, tiêu chuẩn bảng đơn giản, ngay cả khi ban đầu chúng được lấp đầy yếu, sẽ nhanh chóng được lấp đầy bằng các phần tử khác 0 trong quá trình lặp lại. Do đó, thời gian tính toán tăng lên và vì mỗi bảng được tính từ bảng trước đó nên việc tích lũy các lỗi có thể bắt đầu đóng một vai trò nghiêm trọng hơn.
