Phương pháp đơn giản với các ví dụ về biến nhân tạo. Giải bài toán quy hoạch tuyến tính bằng phương pháp cơ sở nhân tạo
Giải pháp của vấn đề lập trình tuyến tính Phương pháp đơn giản bắt đầu bằng việc tìm một số kế hoạch tham khảo.
Hãy xem xét trường hợp thứ ba về xây dựng kế hoạch tham chiếu ban đầu (trường hợp thứ nhất và thứ hai được mô tả trong đoạn 2.1).
Cho hệ hữu hạn có dạng
Hãy chuyển sang hình thức kinh điển bằng cách giới thiệu các biến bổ sung 
, mà chúng ta trừ từ vế trái của bất đẳng thức hệ thống. Hãy lấy hệ thống
.
Bây giờ hệ thống ràng buộc không có dạng ưa thích, vì các biến bổ sung x N + Tôi bao gồm trong bên trái(Tại b Tôi
0) với hệ số bằng –1. Trong trường hợp này, cái gọi là cơ sở nhân tạo bằng cách đi đến Nhiệm vụ M.
Các biến nhân tạo được thêm vào vế trái của ràng buộc đẳng thức không có dạng ưu tiên w Tôi. TRONG hàm mục tiêu biến w Tôiđược nhập với hệ số M trong trường hợp giải bài toán ở mức tối thiểu và có hệ số – M– đối với bài toán cực đại, trong đó M là một số dương lớn. Vấn đề kết quả được gọi là nhiệm vụ M, tương ứng với bản gốc. Cô ấy luôn có một cái nhìn ưa thích.
Giả sử bài toán quy hoạch tuyến tính ban đầu có dạng
|
| |
|
| |
|
|
;
;
Tuy nhiên, không có ràng buộc nào có biến ưa thích. nhiệm vụ M sẽ được viết như sau:
|
| |
|
| |
;
Trong trường hợp này, chức năng đăng nhập “–” (10) đề cập đến vấn đề tối đa. Bài toán (10)–(12) có dạng được ưu tiên hơn. Kế hoạch hỗ trợ ban đầu của nó trông giống như
.
Nếu một số phương trình (8) có dạng ưu tiên thì không nên đưa các biến nhân tạo vào chúng.
Định lý 5.
Nếu tối ưu X bán sỉ 
M-bài toán (10)–(12) tất cả các biến nhân tạo 
sau đó kế hoạch 
là phương án tối ưu cho bài toán ban đầu (7)–(9).
Định lý 6 (một dấu hiệu của sự không tương thích của hệ thống hạn chế ) . Nếu tối ưu M-vấn đề có ít nhất một trong các biến nhân tạo khác 0 thì hệ ràng buộc vấn đề ban đầu không tương thích.
Khi M-dòng chỉ mục nhiệm vụ bảng đơn chia nó thành hai. Dòng đầu tiên chứa các thuật ngữ tự do của các biểu thức 
Và 
, và trong phần thứ hai – các hệ số chứa M. Dấu hiệu tối ưu được kiểm tra đầu tiên trên dòng thứ hai. Nó cũng xác định biến được đưa vào cơ sở. Vì các biến nhân tạo bị loại khỏi cơ sở nên các cột phần tử tương ứng có thể bị bỏ qua. Điều này được giải thích là do các biến nhân tạo không được trả về cơ sở và do đó các cột tương ứng sẽ không còn cần thiết nữa. Sau khi loại bỏ tất cả các biến nhân tạo khỏi cơ sở, quá trình tìm phương án tối ưu tiếp tục sử dụng dòng đầu tiên của hàm mục tiêu.
Ví dụ 4. Giải bài toán quy hoạch tuyến tính bằng cơ sở nhân tạo
Ràng buộc đầu tiên có một biến ưa thích X 3, nhưng cái thứ hai thì không. Vì vậy, chúng tôi đưa một biến nhân tạo vào nó w 1 . Chúng tôi đến M- nhiệm vụ
Hãy thêm một điều kiện M- các vấn đề trong bảng đơn. 5. Kế hoạch tham khảo ban đầu trông giống như x 0 = (x 1 ;x 2 ;x 3 ;x 4 ;w 1) = (0; 0; 2; 0; 12),z(x 0) = 0 – 12M.
Bảng 5
|
Với B | |||||||||
|
|
|||||||||
|
z j – c j | |||||||||
|
| |||||||||
Hãy để chúng tôi đưa ra những lời giải thích cần thiết.
Thật thuận tiện khi chia dòng chỉ mục thành hai. Trong phần đầu tiên, số hạng tự do của biểu thức 0 = c B MỘT 0 và j =c B MỘT j –c j, và trong phần thứ hai – các hệ số chứa M. Ví dụ, đối với bảng. 5:
Đầu tiên chúng ta kiểm tra dấu hiệu tối ưu bằng cách sử dụng dòng thứ hai của dòng chỉ số. Vì có những đánh giá tiêu cực trong đó nên kế hoạch x 0 là không tối ưu.
Hãy chuyển sang một bảng mới. 6.
Cột phân giải được tìm thấy bởi max(|–3 M|; |–4M|} = 4M, đường phân giải được xác định bởi 
. Vì vậy, 1 là yếu tố kích hoạt.
Bảng 6
|
Với B | |||||||
|
z j – c j | |||||||
Không có xếp hạng tiêu cực trong dòng chỉ số. Do đó, theo tiêu chí tối ưu thì phương án tham chiếu (0; 2; 0; 0; 4) là tối ưu. Nhưng vì trong kế hoạch tối ưu, biến nhân tạo w 1 không bằng 0 thì theo Định lý 6 hệ ràng buộc của bài toán ban đầu không mâu thuẫn. Vấn đề không có giải pháp.
Trả lời: không có quyết định.
Ví dụ 5. Giải quyết bằng cách sử dụng cơ sở nhân tạo nhiệm vụ
Hãy tổ chức ghi lại nhiệm vụ ban đầu. Nhân bất đẳng thức thứ hai với –1:
Chúng ta hãy rút gọn vấn đề về dạng chính tắc của nó. Chúng tôi nhận được
Ràng buộc thứ nhất và thứ tư có các biến ưu tiên, nhưng ràng buộc thứ hai và thứ ba thì không. Vì vậy, chúng tôi đưa các biến nhân tạo vào chúng w 1 và w 2. Chúng tôi đến M- nhiệm vụ
Hãy thêm một điều kiện M- các vấn đề trong bảng đơn. 7. Kế hoạch tham khảo ban đầu trông giống như x 0 = (0; 0; 10; 0; 0; 4; 3; 9),z(x 0) = 0 + 12M.
Bảng 7
|
Với B | |||||||||||
|
|
|||||||||||
|
z j – c j | |||||||||||
|
| |||||||||||
Chúng tôi giải quyết vấn đề ở mức tối thiểu. Đầu tiên chúng ta kiểm tra dấu hiệu tối ưu bằng cách sử dụng dòng thứ hai của dòng chỉ số. Vì có đánh giá tích cực trong đó nên kế hoạch x 0 là không tối ưu. Hãy chuyển sang một bảng mới. số 8.
Bảng 8
|
Với B | |||||||||||
Hệ thống được giải quyết bằng cách nhập biến nhân tạo R i có dấu tùy thuộc vào loại tối ưu, tức là để loại trừ các biến này khỏi cơ sở, biến sau được đưa vào hàm mục tiêu với hệ số âm M lớn, có nghĩa là “hình phạt” khi đưa ra các biến nhân tạo và vào bài toán tối thiểu hóa - với M dương. Do đó, từ ban đầu một cái chúng tôi có được bài toán M mới(đây là lý do tại sao phương pháp cơ sở nhân tạo còn được gọi là phương pháp M ).
Nếu không có biến nhân tạo nào trong lời giải tối ưu cho bài toán M thì lời giải này là giải pháp tối ưu nhiệm vụ ban đầu. Nếu trong lời giải tối ưu của bài toán M có ít nhất một trong các biến nhân tạo khác 0 thì hệ ràng buộc của bài toán ban đầu không nhất quán và bài toán ban đầu không thể giải được.
Một bảng đơ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 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 và dòng kia cho thành phần M. Khi biên dịch một bảng đơn, người ta giả định rằng các biến ban đầu là không cơ bản và thêm vào(xn+m) và nhân tạo(R i) - cơ bản.
Bảng nguồn cho "Phương pháp cơ sở nhân tạo" có lượt xem tiếp theo:
| x 1 | x 2 | ... | xn-1 | xn | b | |
| F | -a 0,1 | -a 0,2 | ... | -a 0,n-1 | -a 0,n | -b 0 |
| xn+1 | một 1.1 | một 1,2 | ... | một 1,n-1 | một 1, n | b 1 |
| xn+2 | một 2.1 | một 2,2 | ... | một 2,n-1 | một 2, n | b 2 |
| tôi | một tôi, 1 | một tôi, 2 | ... | một tôi,n-1 | một tôi, n | tôi |
| ... | ... | ... | ... | ... | ... | ... |
| x n+m | một m,1 | một m,2 | ... | một m,n-1 | một m, n | b m |
| M | -∑a tôi,1 | -∑a tôi,2 | ... | -∑a i,n-1 | -∑a tôi,n | -∑b tôi |
Yếu tố dòng bổ sung M được tính bằng tổng của các hệ số tương ứng của điều kiện đẳng thức (điều kiện mà sau khi rút gọn về dạng chính tắc, các biến R i được đưa vào) lấy với dấu ngược lại.
Thuật toán của phương pháp cơ sở nhân tạo.
Chúng ta rút gọn bài toán LP về dạng chính tắc
F=a 0,1 x 1 +a 0,2 x 2 +...a 0,n x n +b 0 → tối đa
a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n +x n+1 =b 1
a 2.1 x 1 +a 2.2 x 2 +...a 2.n x n +x n+2 =b 2
.........................................
a i,1 x 1 +a i,2 x 2 +...a i,n x n +R i =b i
.......................................
a m,1 x 1 +a m,2 x 2 +...a m,n x n +x n+m =b m
Nếu trong bài toán ban đầu cần tìm cực tiểu thì dấu các hệ số của hàm mục tiêu F thay đổi ngược lại a 0,n = -a 0,n . Dấu của các hệ số điều kiện giới hạn mang dấu “ ≥” cũng đổi ngược lại. Nếu điều kiện chứa dấu "<" hoặc "=" thì các hệ số sẽ được viết không thay đổi. Với mỗi điều kiện bất đẳng thức, khi chuyển sang dạng chính tắc ta thêm một biến x n+m, với mỗi điều kiện đẳng thức thứ i ta thêm một biến nhân tạo R i.
Bước 0. Tạo bảng đơn tương ứng với bài toán ban đầu
| x 1 | x 2 | ... | xn-1 | xn | b | |
| F | -a 0,1 | -a 0,2 | ... | -a 0,n-1 | -a 0,n | -b 0 |
| xn+1 | một 1.1 | một 1,2 | ... | một 1,n-1 | một 1, n | b 1 |
| xn+2 | một 2.1 | một 2,2 | ... | một 2,n-1 | một 2, n | b 2 |
| tôi | một tôi, 1 | một tôi, 2 | ... | một tôi,n-1 | một tôi, n | tôi |
| ... | ... | ... | ... | ... | ... | ... |
| x n+m | một m,1 | một m,2 | ... | một m,n-1 | một m, n | b m |
| M | -∑a tôi,1 | -∑a tôi,2 | ... | -∑a i,n-1 | -∑a tôi,n | -∑b tôi |
Bước 1. Kiểm tra xác nhận.
Chúng tôi kiểm tra các phần tử của cột b (các thuật ngữ tự do) về tính tích cực; nếu không có phần tử âm nào trong số chúng, thì một giải pháp chấp nhận được sẽ được tìm thấy (một giải pháp tương ứng với một trong các đỉnh của khối đa diện của điều kiện) và chúng tôi chuyển sang bước 2. Nếu có các phần tử âm trong cột các thuật ngữ tự do, thì chúng tôi chọn mô đun tối đa trong số đó - nó chỉ định hàng đầu k. Trong dòng này, chúng ta cũng tìm thấy phần tử âm tuyệt đối lớn nhất a k,l - nó chỉ định cột đầu tiên - l và là yếu tố hàng đầu. Biến tương ứng với hàng đầu được loại khỏi cơ sở, biến tương ứng với cột đầu được đưa vào cơ sở. Ta tính toán lại bảng đơn theo .
Nếu trong số các số hạng tự do có phần tử phủ định - nhưng ở dòng tương ứng - không có phần tử nào thì điều kiện của bài toán không nhất quán và nó không có nghiệm.
Nếu sau khi tính toán lại còn sót phần tử âm trong cột số hạng tự do thì ta tiến hành bước đầu tiên, nếu không có phần tử nào thì chuyển sang bước thứ hai.
Bước 2. Kiểm tra tính tối ưu.
Ở giai đoạn trước, một giải pháp khả thi đã được tìm thấy. Hãy kiểm tra xem nó có tối ưu không, nếu trong số các phần tử của bảng đơn nằm ở hàng M và F (không tính đến phần tử b 0 - giá trị hiện tại của hàm mục tiêu và phần tử -∑ b i) không có phần tử âm, thì giải pháp tối ưu đã được tìm thấy.
2.1 Độ dương của chuỗi M
Nếu chuỗi M chứa các phần tử âm thì giải pháp cần được cải thiện. Chúng tôi chọn trong số các phần tử âm của chuỗi M phần tử lớn nhất theo mô đun (không bao gồm -∑b i)
Khi a i,l >0, b i >0
Chúng tôi tính toán lại bảng đơn bằng cách sử dụng . Nếu ở bảng mới sau khi tính toán lại còn sót phần tử âm ở dòng M, vào bước 2
Nếu ở hàng M và trong cột các số hạng tự do tất cả các phần tử đều dương thì chúng ta đi tới bước 2.2.
2.2 Độ dương của chuỗi F
Chúng ta kiểm tra các phần tử của chuỗi F xem có dương không, nếu có phần tử âm (không tính b 0), chúng ta chọn trong số các phần tử âm của chuỗi F phần tử có giá trị tuyệt đối lớn nhất.
-a 0,l =min(-a 0,i )
l - cột chứa nó sẽ là cột dẫn đầu. Để tìm hàng đầu tiên, chúng ta tìm tỷ lệ của số hạng tự do tương ứng và phần tử ở cột đầu tiên, với điều kiện chúng không âm.
b k /a k,l =min (b i /a i,l ) với a i,l >0, b i >0
k - hàng mà mối quan hệ này là tối thiểu - hàng đầu. Phần tử ak,l là phần tử dẫn đầu (cho phép). Biến tương ứng với hàng đầu (x k) được loại khỏi cơ sở, biến tương ứng với cột đầu (x l) được đưa vào cơ sở.
Chúng tôi tính toán lại bảng đơn bằng cách sử dụng . Nếu trong bảng mới sau khi tính toán lại vẫn còn phần tử âm ở hàng F thì chuyển đến bước 2.2
Nếu không thể tìm thấy hàng đầu tiên vì không có phần tử dương nào trong cột đầu tiên, thì hàm trong vùng các giải pháp khả thi cho bài toán không bị giới hạn - thuật toán kết thúc.
Nếu tất cả các phần tử ở hàng F và cột các số hạng tự do đều dương thì phương án tối ưu đã được tìm thấy.
Khi điều kiện có chứa các hạn chế như đẳng thức. Hãy xem xét vấn đề:
max(F(x)=∑c i x i |∑a ji x i =b j , j=1,m ; x i ≥0).
Cái gọi là “các biến nhân tạo” R j được đưa vào các ràng buộc và vào hàm mục tiêu như sau:
∑a ji x+R j =b j , j=1,m ;F(x)=∑c i x i -M∑R j
Khi đưa các biến nhân tạo theo phương pháp cơ sở nhân tạo vào hàm mục tiêu, chúng được gán một hệ số M đủ lớn, mang ý nghĩa hình phạt cho việc đưa biến nhân tạ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. Việc đưa vào các biến nhân tạo được cho phép nếu trong quá trình giải bài toán, chúng liên tiếp biến mất.
Một bảng đơ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à bảng mở rộng. Nó khác với 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 = ∑c i x i và dòng kia cho thành phần M ∑R j Hãy xem xét quy trình giải quyết vấn đề bằng một ví dụ cụ thể.
Ví dụ 1. Tìm giá trị lớn nhất của hàm số F(x) = -x 1 + 2x 2 - x 3 theo điều kiện ràng buộc:
2x 1 +3x 2 +x 3 =3,
x 1 ≥0, x 2 ≥0, x 3 ≥0.
Hãy sử dụng phương pháp cơ sở nhân tạo. Hãy đưa các biến nhân tạo vào các ràng buộc của bài toán
2x1 + 3x2 + x 3 + R 1 = 3;
x 1 + 3x 3 + R 2 = 2 ;
Hàm mục tiêu F(x)-M ∑R j = -x 1 + 2x 2 - x 3 - M(R 1 +R 2).
Hãy biểu diễn tổng R 1 + R 2 từ hệ giới hạn: R 1 + R 2 = 5 - 3x 1 - 3x 2 - 4x 3 , khi đó F(x) = -x 1 + 2x 2 - x 3 - M (5 - 3x1 - 3x2 - 4x3) .
Khi biên soạn bảng đơn thứ nhất (Bảng 1), chúng ta sẽ giả sử các biến ban đầu x 1, x 2, x 3 là không cơ bản và các biến nhân tạo được đưa vào là cơ bản. Trong các bài toán cực đại hóa, dấu của các hệ số đối với các biến không cơ bản ở hàng F và M bị đảo ngược. Dấu của giá trị không đổi trong đường M không thay đổi. Việc tối ưu hóa được thực hiện đầu tiên dọc theo đường M. Việc lựa chọn các cột và hàng đầu, mọi phép biến đổi đơn giản khi sử dụng phương pháp cơ sở nhân tạo đều được thực hiện như trong phương pháp đơn hình thông thường.
Tối đa bởi giá trị tuyệt đối hệ số âm (-4) xác định cột đầu tiên và biến x 3, sẽ đi vào cơ sở. Tỷ lệ đơn hình tối thiểu (2/3) tương ứng với hàng thứ hai của bảng nên biến R 2 phải bị loại khỏi cơ sở. Yếu tố hàng đầu đượ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ả về nó nữa, do đó các cột phần tử của các biến đó bị bỏ qua. Bàn 2. giảm đi 1 cột. Thực hiện tính toán lại bảng này, chúng ta chuyển sang bảng. 3., trong đó dòng M đã được đặt lại, nó có thể được gỡ 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 giá trị chấp nhận được giải pháp cơ bản của bài toán ban đầu, mà trong ví dụ đang xét là tối ưu:
x 1 = 0; x 2 =7/9; F tối đa = 8/9.
Nếu khi loại bỏ chuỗi M, giải pháp không tối ưu thì quy trình tối ưu hóa sẽ 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ụ trong đó có tất cả các loại hạn chế: ,=, ≥
Ví dụ 2. Tìm thấy giá trị tối thiểu hàm số F(x) = 2x 1 + 3x 2 - x 3 theo các ràng buộc sau
2x 1 +x 2 -3x 3 ≥6,
x 1 -x 2 +2x 3 =4,
x 1 +x 2 +x 3 5,
x 1 ≥0, x 2 ≥0, x 3 ≥0.
Hãy nhân giới hạn đầu tiên với (-1) và đưa vào giới hạn các biến bổ sung x 4, x 5 và biến nhân tạo R như sau:
2x 1 -x 2 +3x 3 +x 4 =-6,
x 1 -x 2 +2x 3 +R=4,
x 1 +x 2 +x 3 +x 5 =5,
Gọi x 4, R và x 5 là các biến cơ bản và x 1, x 2, x 3 – không cơ bản. Hàm mục tiêu F(x)=F(x)+M∑R=2x 1 +3x 2 -x 3 +M(4-x 1 +x 2 -2x 3).
Trong phần đầu tiên (Bảng 4), các hệ số cho các biến không cơ bản trong hàng F và hàng M không đổi dấu, vì hàm đang được cực tiểu hóa. Số hạng tự do trong phương pháp cơ sở nhân tạo ở hàng M được lấy dấu ngược lại. Giải pháp tương ứng với bảng. 4 không hợp lệ vì có số hạng giả phủ định.
Hãy chọn cột và hàng đầu theo bước 2 của thuật toán giải. Sau khi tính toán lại ta được bảng 5. Việc tối ưu hóa lời giải theo phương pháp cơ sở nhân tạo (bước 5 của thuật toán) được thực hiện đầu tiên dọc theo đường M. Kết quả là chúng tôi đưa x 3 vào cơ sở và loại trừ biến R khỏi xem xét, làm giảm số lượng cột. Sau khi tính toán lại ta được bảng 6, tương ứng với giải pháp tối ưu cho vấn đề.
Bảng 4
| biến cơ bản | Thành viên miễn phí | Các biến không cơ bản | ||
| x 1 | x 2 | x 3 | ||
| x 4 | -6 | -2 | -1 | 3 |
| R | 4 | 1 | -1 | 2 |
| x 5 | 5 | 1 | 1 | 1 |
| F | 0 | 2 | 3 | -1 |
| M | -4 | -1 | 1 | -2 |
Bảng 5
| biến cơ bản | Thành viên miễn phí | Các biến không cơ bản | ||
| x 4 | x 2 | x 3 | ||
| x 1 | 3 | -1/2 | 1/2 | -3/2 |
| R | 1 | 1/2 | -3/2 | 7/2 |
| x 5 | 2 | 1/2 | 1/2 | 5/2 |
| F | -6 | 1 | 2 | 2 |
| M | -1 | -1/2 | 3/2 | -7/2 |
Bảng 6
Giá trị tối thiểu cần thiết của hàm F(x) bằng với số hạng tự do của hàng F của bảng. 6, lấy dấu ngược lại, vì min F(x) = -max(-F(x)); x 4 = x 2 = 0;
x 1 = 24/7; x 3 =2/7; x 5 = 9/7; F phút = 46/7;
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Cảnh báo
Xóa tất cả các ô?
Đóng Xóa
Hướng dẫn nhập dữ liệu. Các số được nhập dưới dạng số nguyên (ví dụ: 487, 5, -7623, v.v.), số thập phân (ví dụ: 67., 102,54, v.v.) hoặc phân số. Phân số phải được nhập ở dạng a/b, trong đó a và b (b>0) là số nguyên hoặc số thập phân. Ví dụ 45/5, 6,6/76,4, -7/6,7, v.v.
Phương pháp đơn giản
Ví dụ giải ZLP bằng phương pháp đơn hình
Ví dụ 1. Giải bài toán quy hoạch tuyến tính sau:
 |
Vế phải của các ràng buộc của hệ phương trình có dạng:
Hãy viết ra kế hoạch tham khảo hiện tại:
 |
Kế hoạch tham khảo này không tối ưu, vì dòng cuối cùng có những yếu tố tiêu cực. Phần tử âm lớn nhất trong mô đun là (-3), do đó vectơ được đưa vào cơ sở x 
Tại 
. phút(40:6, 28:2)=20/3 tương ứng với dòng 1. Vectơ xuất hiện từ cơ sở x 3. Hãy thực hiện loại bỏ Gaussian cho cột x 2, vì phần tử đứng đầu tương ứng với hàng 1. Hãy đặt lại tất cả các phần tử của cột này ngoại trừ phần tử đứng đầu. Để làm điều này, hãy cộng các dòng của dòng 2, 3, 4 với dòng 1, nhân lần lượt với -1/3, 1/6, 1/2. Tiếp theo, chúng ta chia dòng có phần tử dẫn đầu cho phần tử dẫn đầu.
Sơ đồ tham chiếu này không tối ưu, vì hàng cuối cùng có phần tử âm (-3), do đó cơ sở bao gồm vectơ x 1 . Chúng tôi xác định vectơ nào đi ra khỏi cơ sở. Để làm điều này, chúng tôi tính toán 
Tại 
. min(44/3:11/3, 62/3:5/3)=4 tương ứng với dòng 2. Vectơ xuất hiện từ cơ sở x 4 . Hãy thực hiện loại bỏ Gaussian cho cột x 1, vì phần tử đứng đầu tương ứng với hàng 2. Hãy đặt lại tất cả các phần tử của cột này ngoại trừ phần tử đứng đầu. Để làm điều này, hãy thêm các dòng 1, 3, 4 với dòng 2 nhân lần lượt với 1/11, -5/11, 9/11. Tiếp theo, chúng ta chia dòng có phần tử dẫn đầu cho phần tử dẫn đầu.
Bảng đơn giản sẽ có dạng sau:
Kế hoạch tham chiếu hiện tại là tối ưu, vì ở dòng 4 dưới các biến 
không có yếu tố tiêu cực.
Giải pháp có thể được viết như thế này: 
.
Giá trị của hàm mục tiêu lúc này: F(X)=
.
Ví dụ 2. Tìm cực đại của hàm số
Giải pháp.
Vectơ cơ sở x 4 , x 3 do đó tất cả các phần tử trong cột x 4 , x 3, dưới đây đường chân trời phải bằng không.
Đặt lại tất cả các thành phần cột về 0 x 4, ngoại trừ phần tử hàng đầu. Để thực hiện việc này, hãy cộng hàng 3 với hàng 1 nhân với 4. Đặt lại tất cả các thành phần của cột về 0 x 3, ngoại trừ phần tử hàng đầu. Để làm điều này, hãy thêm dòng 3 với dòng 2 nhân với 1.
Bảng đơn giản sẽ có dạng:
Sơ đồ tham chiếu này không tối ưu, vì hàng cuối cùng có phần tử âm (-11), do đó cơ sở bao gồm vectơ x 2. Chúng tôi xác định vectơ nào đi ra khỏi cơ sở. Để làm điều này, chúng tôi tính toán 
Tại 
. Do đó, hàm mục tiêu không bị chặn từ phía trên. Những thứ kia. bài toán quy hoạch tuyến tính không thể giải được.
Ví dụ giải ZLP bằng phương pháp cơ sở nhân tạo
Ví dụ 1. Tìm giá trị lớn nhất của hàm số
Giải: Vì số vectơ cơ sở phải là 3 nên chúng ta thêm một biến nhân tạo và thêm biến này nhân với −M vào hàm mục tiêu, trong đó M rất con số lớn:
 |
Ma trận hệ số của hệ phương trình có dạng:
Do đó, vectơ cơ sở tất cả các phần tử trong các cột bên dưới đường ngang phải bằng 0.
Hãy đặt lại tất cả các phần tử của cột ngoại trừ phần tử đứng đầu. Để làm điều này, hãy thêm dòng 5 với dòng 3 nhân với -1.
Bảng đơn giản sẽ có dạng:
Phương án tham chiếu này không tối ưu vì có những phần tử âm ở hàng cuối cùng. Phần tử âm tuyệt đối lớn nhất là (-5), do đó vectơ được đưa vào cơ sở. Chúng ta xác định vectơ nào ra khỏi cơ sở. Để làm điều này, chúng tôi tính toán 
Tại 
tương ứng với hàng 3. Một vectơ xuất hiện từ cơ sở. Hãy thực hiện một ngoại lệ Gaussian cho cột, với điều kiện là phần tử đứng đầu tương ứng với hàng 3. Hãy đặt lại tất cả các phần tử của cột này, ngoại trừ phần tử đứng đầu. Để thực hiện việc này, hãy cộng các dòng dòng 5 với dòng 3 nhân với 1. Tiếp theo, chia dòng có phần tử đứng đầu cho phần tử đứng đầu.
Bảng đơn giản sẽ có dạng sau:
Phương án tham chiếu này không tối ưu vì có những phần tử âm ở hàng cuối cùng. Phần tử âm tuyệt đối lớn nhất là (-3), do đó vectơ được đưa vào cơ sở.Chúng ta xác định vectơ nào đi ra khỏi cơ sở. Để làm điều này, chúng tôi tính toán 
Tại 
tương ứng với hàng 1. Vector xuất hiện từ cơ sở x 2. Hãy thực hiện loại bỏ Gaussian cho cột x 1 , với điều kiện là phần tử đứng đầu tương ứng với hàng 1. Hãy đặt lại tất cả các phần tử của cột này ngoại trừ phần tử đứng đầu. Để thực hiện, bạn cộng các dòng của dòng 2, 3, 4 với dòng 1, nhân lần lượt với 3/2, -1/10, 3/2. Tiếp theo, chúng ta chia dòng có phần tử dẫn đầu cho phần tử dẫn đầu.
Bảng đơn giản sẽ có dạng sau:
Phương án tham chiếu này không tối ưu vì có những phần tử âm ở hàng cuối cùng. Phần tử âm lớn nhất trong mô đun (-13/2), do đó cơ sở bao gồm vectơ x 3. Chúng tôi xác định vectơ nào đi ra khỏi cơ sở. Để làm điều này, chúng tôi tính toán 
Tại 
tương ứng với dòng 3. Vector xuất hiện từ cơ sở x 5 . Hãy thực hiện loại bỏ Gaussian cho cột x 3, vì phần tử đứng đầu tương ứng với hàng 3. Hãy đặt lại tất cả các phần tử của cột này ngoại trừ phần tử đứng đầu. Để làm điều này, hãy cộng các dòng của dòng 1, 2, 4 với dòng 3, nhân lần lượt với 5/3, 25/9, 65/9. Tiếp theo, chúng ta chia dòng có phần tử dẫn đầu cho phần tử dẫn đầu.
Bảng đơn giản sẽ có dạng sau:
Kế hoạch tham chiếu hiện tại là tối ưu vì không có phần tử âm nào dưới các biến ở dòng 4−5.
Lời giải của bài toán ban đầu có thể được viết như sau:
Ví dụ 2. Tìm phương án tối ưu cho bài toán quy hoạch tuyến tính:
Ma trận hệ số của hệ phương trình có dạng:
Vectơ cơ sở x 4 , x 5 , x 6 do đó tất cả các phần tử trong cột x 4 , x 5 , x 6, bên dưới đường ngang phải bằng không.
Đặt lại tất cả các thành phần cột về 0 x 4, ngoại trừ phần tử hàng đầu. Để làm điều này, hãy thêm dòng 4 với dòng 1 nhân với -1. Đặt lại tất cả các thành phần cột về 0 x 5, ngoại trừ phần tử hàng đầu. Để làm điều này, hãy thêm dòng 5 với dòng 2 nhân với -1. Đặt lại tất cả các thành phần cột về 0 x 6, ngoại trừ phần tử hàng đầu. Để làm điều này, hãy thêm dòng 5 với dòng 3 nhân với -1.
Bảng đơn giản sẽ có dạng:
Ở dòng 5 các phần tử tương ứng với các biến x 1 , x 2 , x 3 , x 4 , x 5 , x 6 không âm và là số nằm ở giao điểm của một hàng và cột nhất định x 0 là âm. Khi đó bài toán ban đầu không có phương án tham khảo. Vì vậy nó là không thể quyết định được.
Trong trường hợp các biến cơ sở không được xác định ngay lập tức (và chúng chỉ được xác định ngay sau khi đưa bài toán về dạng chính tắc, trong đó chỉ có các bất đẳng thức loại “<” với vế phải không âm), có thể sử dụng cái gọi là phương pháp cơ sở nhân tạo , về cơ bản là một loại phương pháp đơn giản.
Đưa bài toán về dạng chính tắc (1.6), trong đó trong một số phương trình, chẳng hạn như Tôi 1m, Tôi lần 2, …, là -m, các biến cơ bản không được xác định rõ ràng. Hãy thêm vào các phương trình này biến nhân tạox m +1 , xm +2 , …, xm + S , và vào hàm mục tiêu - các số hạng ± Mx m +1 , ± Mx m +2 , …, ± Mx m + S , Ở đâu M >>1 (M - một số dương khá lớn) và “±” là “+” nếu vấn đề được giải quyết trong thời gian tối thiểu và “±” là “-” nếu vấn đề được giải quyết trong thời gian tối đa. Điều này dẫn đến một vấn đề mới gọi là thêm vào hoặc phụ trợ .
Ví dụ, một bài toán phụ (bổ sung) có biến nhân tạo cho bài toán (1.5) sẽ có dạng
c 1 x 1 +c 2 x 2 +…+c n x n +Mx n + tôi +1 +Mx n + tôi +2 +…+Mx n +2 tôi ® phút
Tương tự, nếu bài toán (2.1) được giải với giá trị max và cần đưa các biến nhân tạo vào tất cả các ràng buộc thì chúng ta thu được bài toán phụ trợ sau:
c 1 x 1 +c 2 x 2 +…+c n x n -Mx n +1 -Mx n +2 -…-Mx n + tôi ®tối đa
(5.1)
5.1.1. Nếu như( , , …, , , …, ) lời giải tối ưu cho một bài toán phụ, Ở đâu , …, - giá trị của biến nhân tạo, , , …, - giá trị của các biến trong bài toán ban đầu hình thức kinh điển , Cái đó =…= =0 Và ( , , …, ) -giải pháp tối ưu cho vấn đề ban đầu. Trong trường hợp này, giá trị của hàm mục tiêu của bài toán gốc và bài toán phụ trùng nhau.
Từ đây chúng ta hiểu rằng để giải bài toán quy hoạch tuyến tính bằng phương pháp cơ sở nhân tạo là đủ:
1. Đưa vấn đề về dạng chính tắc.
2. Nếu bài toán ở dạng chính tắc không có cơ sở là vectơ đơn vị thì tạo một bài toán phụ (nếu bài toán ở dạng chính tắc có cơ sở là vectơ đơn vị thì bài toán được giải bằng phương pháp đơn hình thông thường).
3. Giải bài toán phụ và nếu ( , , …, , , …, ) là lời giải tối ưu của bài toán phụ, trong đó x 1 , x 2 , …, xm - các biến chính và bổ sung (từ bài toán ở dạng chính tắc), xm +1 , xm +2 , …, xm + S - các biến nhân tạo thì ( , , …, ) - lời giải của bài toán ở dạng chính tắc. Giá trị tối ưu của hàm mục tiêu của bài toán phụ bằng giá trị tối ưu nhiệm vụ ban đầu.
Trong trường hợp này, phương pháp đơn hình thông thường với một số đặc điểm riêng của nó được áp dụng cho bài toán phụ trợ:
1. Vì hàm mục tiêu của bài toán phụ có các số hạng với hệ số ± M , sau đó ước tính D k trông giống như ± M , Và M - một con số khá lớn. Do đó, với ≠0 dấu của D k thực sự được xác định bởi dấu hiệu tại . Về vấn đề này, trong bảng đơn ở giai đoạn đầu (trong khi cơ sở bao gồm các biến nhân tạo), thay vì một hàng D k ghi hai dòng và , còn khi áp dụng tiêu chí tối ưu chỉ tập trung vào dòng .
2. Các biến nhân tạo, vì chúng bị loại bỏ khỏi cơ sở, nên không được xem xét thêm.
3. Sau khi loại bỏ tất cả các biến nhân tạo khỏi cơ sở, hệ số D k Tại M sẽ bằng 0, chỉ còn lại hàng trong bảng =D k .
Ví dụ. Giải ví dụ ở đoạn trước bằng phương pháp cơ sở nhân tạo.
Giải pháp. Chúng tôi nhắc nhở bạn về nhiệm vụ:
3x 1 +x 2 +2x tối đa 3 ® (phút)
1. Đưa bài toán về dạng chính tắc:
3x 1 +x 2 +2x tối đa 3 ® (phút)
2. Cơ sở dưới dạng vectơ đơn vị chỉ bao gồm vectơ tại x 4, tức là biến trong phương trình thứ hai. Chúng tôi đưa các biến nhân tạo vào phương trình thứ nhất và thứ ba của hệ ràng buộc x 6 và x 7:
Chúng sẽ được đưa vào hàm mục tiêu với các hệ số M hoặc - M tùy thuộc vào việc vấn đề được giải quyết với mức tối thiểu hay tối đa.
Hãy giải quyết vấn đề ở mức tối đa. Sau đó, nhiệm vụ phụ trợ là như sau:
3x 1 +x 2 +2x 3 -Mx 6 -Mx 7®max
3. Chúng ta giải bài toán phụ thu được bằng cách sử dụng bảng đơn:
| Nền tảng | VỚI b | Miễn phí thành viên | -3 | -M | -M | q 2 | q 3 | ||||||
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | |||||||
| x 6 | -M | -1 | phút | ||||||||||
| x 4 | - | ||||||||||||
| x 7 | -M | -1 | |||||||||||
| -1 | -2 | ||||||||||||
| -8 | -2 | -3 |
Ở đây D 2 =-2 M -1, D 3 =-3 M -2. Hệ số tại M được viết trong dòng. Chúng ta có D 2 đó<0 и D 3 <0, то есть для переменных x 2 và x 3 tiêu chí tối ưu bị vi phạm. Vì vậy, chúng tôi sẽ giới thiệu vào cơ sở x 2 hoặc x 3. Biến nào trong số những biến này và thay vì biến số nhân tạo nào (thay vì x 6 hoặc thay vào đó x 7), được xác định bằng cột q 2 và q 3. Tại giao điểm của cột q 2 và dòng và số 2 và 4 tương ứng có nghĩa là nếu đưa vào cơ sở x 2 giá trị của hàm sẽ tăng thêm - q 2D 2 =4 M +2, và nếu được bao gồm trong cơ sở x 3 giá trị của hàm sẽ tăng thêm - q 3D 3 =3 M +2<-q 2 D 2 . Vì vậy, chúng tôi đưa vào cơ sở x 2 (cung cấp sự gia tăng lớn hơn về chức năng và cuối cùng là tăng tốc quá trình giải quyết vấn đề). Vì đạt được min = 2 trong dòng x 6 thì chúng tôi loại trừ khỏi cơ sở x 6. Chúng tôi xây dựng một bảng đơn giản mới, đã chứa một cột có biến nhân tạo x 6 bị thiếu (bị gạch bỏ) vì đây là biến nhân tạo x 6 được loại trừ khỏi quá trình tiếp theo. Trong bảng mới hệ số tại x 2 ở dòng đầu tiên (bây giờ tương ứng với biến cơ sở mới x 2) bằng 1, và trong giây thứ hai nó bằng 0. Do đó, chúng tôi viết lại hai hàng đầu tiên vào bảng mới từ bảng cũ. Để cho dòng x 7 giờ x 2 nhận 0, từ chuỗi x 7 ở bảng cũ ta trừ đi cái mới trước. Chúng ta nhận được bảng tiếp theo như sau:
| Nền tảng | VỚI b | Miễn phí thành viên | -3 | -M | -M | q 1 | ||||||
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | ||||||
| x 2 | -1 | - | ||||||||||
| x 4 | ||||||||||||
| x 7 | -M | -1 | -1 | phút | ||||||||
| -4 | -2 |
Vì D k <0 только для одного значения k =1, cụ thể là D 1 =-2 M +2<0 (напоминаем, что M - một con số khá lớn nên -2 M <2 и D 1 <0), то ищем только отношения q 1 . Mức tối thiểu của các mối quan hệ này đạt được trong dòng x 7: phút = 2. Do đó, biến nhân tạo bị loại khỏi cơ sở và thay vào đó nó được đưa vào cơ sở. x 1 .
Các biến nhân tạo bây giờ được loại trừ khỏi cơ sở. Do đó, chúng tôi tiếp tục làm việc với bảng đơn giản thông thường, trong đó hàng thứ ba mới (tương ứng với biến x 1) thu được bằng cách chia dòng thứ ba cũ cho 2. Sau đó, chúng ta cộng dòng thứ ba mới này với dòng đầu tiên cũ và trừ đi dòng thứ hai cũ. Kết quả là trong bảng mới ở cột x 1 sẽ lần lượt xuất hiện 0, 0 và 1:
| Nền tảng | VỚI b | Miễn phí thành viên | -3 | ||||
| x 1 | x 2 | x 3 | x 4 | x 5 | |||
| x 2 | 3/2 | -1/2 | |||||
| x 4 | 3/2 | 1/2 | |||||
| x 7 | -3 | -1/2 | -1/2 | ||||
| D k | -2 |
Trong bảng kết quả D k ³0 cho mọi người k X 0 =(2; 4; 0) là nghiệm tối ưu trong đó giá trị của hàm mục tiêu là -2 ( x 4 không được tính đến trong câu trả lời cuối cùng vì đây là một biến bổ sung và không có trong bài toán ban đầu).
Hãy giải quyết vấn đề ở mức tối thiểu (phút). Sau đó, nhiệm vụ phụ trợ là như sau:
3x 1 +x 2 +2x 3 -Mx 6 -Mx 7®max
Như trên, chúng ta giải bài toán phụ thu được bằng cách sử dụng bảng đơn:
| Nền tảng | VỚI b | Miễn phí thành viên | -3 | M | M | q 2 | q 3 | ||||||
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | |||||||
| x 6 | M | -1 | phút | ||||||||||
| x 4 | - | ||||||||||||
| x 7 | M | -1 | |||||||||||
| -1 | -2 | ||||||||||||
| -1 |
Tiêu chí tối ưu bị vi phạm đối với các biến x 2 và x 3: D 2 =2 M -1>0, D 3 =3 M -2>0. Bởi vì - q 2 D 2 =-4 M +2 có giá trị tuyệt đối cao hơn - q 3 D 3 =-3 M +2, sau đó chúng tôi đưa vào cơ sở x 2. Trong trường hợp này, đạt được min = 2 ở dòng x 6 , và loại trừ khỏi cơ sở x 6. Việc chuyển sang bảng mới cũng tương tự như chuyển đổi khi giải bài toán max:
| Nền tảng | VỚI b | Miễn phí thành viên | -3 | -M | -M | q 1 | ||||||
| x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | ||||||
| x 2 | -1 | - | ||||||||||
| x 4 | ||||||||||||
| x 7 | -M | -1 | -1 | phút | ||||||||
| -1 | -1 |
Bây giờ D 1 >0. Vì vậy, việc chuyển sang bảng mới cũng tương tự như chuyển đổi tương ứng khi giải bài toán ở mức max: cơ sở được nhập x 1 thay thế x 7:
| Nền tảng | VỚI b | Miễn phí thành viên | -3 | q 3 | q 5 | ||||
| x 1 | x 2 | x 3 | x 4 | x 5 | |||||
| x 2 | 3/2 | -1/2 | 8/3 | - | |||||
| x 4 | 3/2 | 1/2 | 4/3 | ||||||
| x 7 | -3 | -1/2 | -1/2 | - | - | ||||
| D k | -2 | -4/3 | -4 |
Chúng ta có D 3 =1>0 và D 5 =1>0. Kể từ |- q 5 D 5 |=|- q 3 D 3 |, sau đó ta giới thiệu vào cơ sở x 5 (thay vì x 4): đầu tiên chúng ta nhân dòng thứ 2 với 2, sau đó thêm dòng thứ hai mới, nhân với ½, với dòng thứ nhất và thứ ba (trên thực tế, chúng ta thêm dòng thứ hai cũ vào dòng thứ nhất và thứ ba):
Trong bảng kết quả D k £0 cho mọi người k =1, 2, …, 5 tức là đạt tiêu chí tối ưu. Đó là lý do tại sao X 0 =(4; 6; 0) là nghiệm tối ưu mà giá trị của hàm mục tiêu là -6.
Trả lời: F min =-6, mức tối thiểu đạt được tại điểm X 2 =(4; 6; 0);
F max =-2, đạt mức tối đa tại điểm X 1 =(2; 4; 0).
5.2. Bài tập. Giải các bài toán quy hoạch tuyến tính tương ứng từ Bài tập 1.3 phương pháp cơ sở nhân tạo.
Lý thuyết nhị nguyên
