Phương pháp cơ sở nhân tạo quy hoạch tuyến tính. 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
Cho đến nay, chúng ta đã xem xét một cách toàn diện bài toán, lời giải của bài toán được thực hiện trên cơ sở thuật toán đơn giản nhất của phương pháp đơn hình, vì tất cả các ràng buộc đều có dạng nhỏ hơn hoặc bằng. Trong trường hợp này, bổ sung biến nhiệm vụ tạo thành một cơ sở đơn vị. Nhưng có thể hóa ra hệ thống các hạn chế được trình bày ở dạng kinh điển, nhưng nó không được rút gọn thành một đơn vị.
Khi giải quyết những vấn đề như vậy, người ta đã đưa ra phương pháp cơ sở nhân tạo . Nó đặc biệt thuận tiện khi số lượng biến vượt quá đáng kể số lượng phương trình.
Thuật toán để giải quyết vấn đề phương pháp đơn giản Hãy xem xét một ví dụ với cơ sở nhân tạo.
ví dụ 1
Tìm giá trị lớn nhất Z=4X1+2X2+X3
3Х1+2Х2+Х3=15
Хj³0, j=1,...,3
Hãy chuyển sang dạng kinh điển:
X1+X2+X3-X4=8
2Х1+Х2+Х3+Х5=8
3Х1+2Х2+Х3=15
Хj³0, j=1,...,5
Zmax=4X1+2X2+X3+0×X4+0×X5
Hệ thống này các giới hạn không có cơ sở đơn vị, vì biến bổ sung X4 có hệ số trừ một, và ràng buộc thứ ba được biểu diễn bằng một phương trình và không có biến cơ sở. Để có cơ sở đơn vị, ta đưa vào các ràng buộc tương ứng biến nhân tạo y1 và y2 có hệ số dương (+1).
Cần lưu ý rằng các biến nhân tạo chỉ được đưa vào để hình thức hóa toán học của bài toán. Vì vậy, sơ đồ tính toán phải sao cho không thể đưa các biến nhân tạo vào nghiệm cuối cùng trong số các biến cơ bản. Để đạt được mục đích này, đối với các biến nhân tạo trong hàm mục tiêu giới thiệu hệ số M, biểu thị rất con số lớn. Trong thực tế (đặc biệt khi giải một bài toán trên máy tính), thay vì M, họ lấy một số lớn cụ thể, ví dụ 10000. Hơn nữa, khi giải bài toán ở mức tối đa, hệ số này được nhập vào hàm mục tiêu với một dấu trừ dấu và khi giải ở mức tối thiểu, bằng dấu cộng. Bây giờ chúng ta sẽ giải bài toán T (M), hàm mục tiêu của nó chứa hàm mục tiêu của tác vụ Z và các biến nhân tạo có hệ số ±M, tức là.
T=Z-M S yi, khi giải tìm cực đại của hàm mục tiêu và
T=Z+M S y, khi giải tìm cực tiểu của hàm mục tiêu
Trong trường hợp của chúng ta:
X1+X2+X3-X4+y1=8
2Х1+Х2+Х3+Х5=8
3Х1+2Х2+Х3+y2=15
Хj³0, j=1,...,5
Тmax= 4X1+2X2+X3+0×X4+0×X5 - M(y1+y2)
Bài toán này được giải bằng bảng đơn, nhưng để thuận tiện, hàm mục tiêu được chia thành 2 dòng:
Ở dòng đầu tiên, chúng ta viết ra các ước tính không chứa hệ số M;
Dòng thứ hai chứa các ước tính cho mỗi biến tự do, chứa hệ số M.
Việc tính các phần tử (điểm) của hai dòng này được thực hiện theo công thức (2). Sự khác biệt duy nhất:
Khi tính toán ước lượng hàng Z phải tính đến các hệ số Cj có trong hàm Z;
Khi tính toán ước lượng đường M, hệ số này không được tính đến và M được lấy làm hệ số chung.
Để nhiệm vụ T và nhiệm vụ Z bằng nhau thì yi cần phải bằng 0. Do đó, miễn là y i không bằng 0, cột phân giải được chọn dựa trên các ước tính ở hàng thứ hai bằng thuật toán phương pháp đơn hình.
Chỉ sau khi tất cả y i bằng 0, việc tính toán tiếp theo sẽ được thực hiện bằng cách sử dụng dòng chỉ mục đầu tiên, tức là. - nhiệm vụ Z thông thường.
Hơn nữa, khi biến nhân tạo được dẫn xuất từ cơ sở, chúng ta sẽ loại nó ra khỏi bảng đơn, và bảng đơn tiếp theo sẽ không có cột phân giải trước đó.
Có mối liên hệ giữa lời giải tối ưu của bài toán M và bài toán Z, được thiết lập bởi phương trình sau: định lý:
1. Nếu ở giải pháp tối ưu Trong bài toán M, tất cả các biến nhân tạo (y i) đều bằng 0 thì nghiệm này sẽ là lời giải tối ưu cho bài toán Z.
2. Nếu trong lời giải tối ưu của bài toán M có ít nhất một biến nhân tạo khác 0 thì bài toán Z không có lời giải do hệ ràng buộc không tương thích.
3. Nếu bài toán M không thể giải được (T®+¥ hoặc -¥), thì vấn đề ban đầu cũng không thể giải quyết được do sự không nhất quán của hệ giới hạn hoặc do hàm Z không bị chặn.
Hãy soạn bài đầu tiên bảng đơn. Khi giải bằng phương pháp M, cột phân giải có thể được chọn trong hàng M không phải lớn nhất giá trị tuyệt đốiước tính âm (khi giải tìm giá trị lớn nhất) và không theo ước tính dương lớn nhất (khi giải tìm giá trị tối thiểu), mà theo ước tính loại bỏ Y khỏi cơ sở nhanh hơn. TRONG trong ví dụ này cột phân giải sẽ là cột của biến tự do X2 có điểm là (-3).
Bảng 3.1.
Bảng đơn giản đầu tiên
Việc điền đường Z được thực hiện theo công thức (2):
a00 = 0 × 8– 0 = 0
a01 =0 × 2– 4 = -4
a02 =0 × 1– 2 = -2
a03 =0 × 1– 1 = -1
a02 =0 × 0– 0 = 0
Điền vào dòng M:
а¢00 = -М × 8 + (–М) × 15 = -23М
а¢01 = -М × 1 + (–М) × 3= -4М
а¢02 = -М × 1 + (–М) × 2= -3М
а¢03 = -М × 1+ (–М) × 1 = -2М
а¢04 = -М ×(-1)+ (–М) × 0 = 1М
Ta lấy M làm nhân tử chung.
Cột cuối cùng trong dòng phân giải chứa 0, do đó cột của biến tự do X4 được truyền mà không thay đổi.
Bảng 3.2.
Bảng đơn giản thứ hai
Trong bảng thứ hai, chúng ta thu được nghiệm suy biến, vì chúng ta thu được hai quan hệ đơn giản giống hệt nhau. Do đó, chúng tôi tìm mối quan hệ của các phần tử của cột bên cạnh cột phân giải với các phần tử của cột phân giải, có tính đến dấu.
Bảng 3.3.
Bảng đơn thứ ba
Bây giờ chúng ta giải bằng phương pháp đơn hình thông thường.
Bảng 3.4.
Bảng đơn thứ tư
| St.P | Cj | |||
| B.P. | Ci | ai0 | X5 | X4 |
| X3 | -1 | |||
| X1 | ||||
| X2 | -2 | -1 | ||
| Z |
Trong dòng đánh giá, tất cả các phần tử đều có giá trị không âm, do đó thu được giải pháp tối ưu:
Zmax=15 Xopt(0,7,1,0,0)
Ví dụ2
Bài toán đã được giải quyết ở mức tối thiểu (Z®min) của hàm mục tiêu. Ở lần lặp cuối cùng, chúng tôi nhận được bảng sau:
Bảng 3.5.
Bảng đơn giản mới nhất
| St.P | Cj | ||||
| B.P. | Ci | ai0 | X1 | X3 | X4 |
| U1 | M | -1/2 | -1/2 | -1/2 | -1 |
| X5 | 1/2 | 1/2 | 1/2 | ||
| X2 | 15/2 | 3/2 | 1/2 | ||
| Z | -1 | ||||
| M | -1/2 | -1/2 | -1/2 | -1 |
Trong bài toán T, người ta đã thu được một giải pháp tối ưu vì không có ước tính nào dương hơn trong hàng M, tức là việc lựa chọn cột phân giải là không thể và U1 là cơ sở. Trong trường hợp này, bài toán ban đầu không có lời giải do sự không tương thích của hệ thống hạn chế.
Trong trường hợp các biến cơ bản không được phân bổ ngay lập tức (và chúng chỉ được phân bổ ngay sau khi giảm xuống hình thức kinh điển bài toán trong đó chỉ có bất đẳng thức loại “<” với vế phải không âm), ta 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. Hóa ra nhiệm vụ mới, được 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 +Mxn + tôi +1 +Mxn + tôi +2 +…+Mxn +2 tôi ® phút
Tương tự, nếu bài toán (2.1) giải được 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ì ta thu được bài toán phụ trợ sau:
c 1 x 1 +c 2 x 2 +…+c n x n -Mxn +1 -Mxn +2 -…-Mxn + 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 ở dạng chính tắc, 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ừ đó ta có được điều đó để giải quyết vấn đề lập trình tuyến tính, 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 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 tôi nhận được bảng sau, tiếp theo:
| 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
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” Rj đượ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.
Hệ số âm tối đa ở giá trị tuyệt đối (-4) xác định cột đầu 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 một giải pháp cơ sở có thể chấp nhận được cho bài toán ban đầu, mà trong ví dụ đang xem 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 giá trị nhỏ nhất của 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 thêm các biến x 4, x 5 và biến nhân tạo R vào các giới hạn 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;
Thuật toán phương pháp cơ sở nhân tạo có các tính năng sau:
1. Do nghiệm tham chiếu ban đầu của bài toán mở rộng chứa các biến nhân tạo nằm trong hàm mục tiêu với hệ số - M(trong một nhiệm vụ tối đa) hoặc + M(trong bài toán tối thiểu), ước lượng khai triển của vectơ điều kiện bao gồm hai số hạng và 
, một trong số đó không phụ thuộc vào M, và điều khác 
phụ thuộc M. Bởi vì M lớn tùy ý so với đơn vị ( M>> 1), thì ở giai đoạn tính toán đầu tiên để tìm các vectơ được đưa vào cơ sở, chỉ sử dụng các số hạng của ước lượng 
.
2. Các vectơ tương ứng với các biến nhân tạo có nguồn gốc từ cơ sở của lời giải tham chiếu bị loại khỏi việc xem xét.
3. Sau khi loại trừ tất cả các vectơ tương ứng với các biến nhân tạo khỏi cơ sở, phép tính tiếp tục sử dụng phương pháp đơn giản thông thường sử dụng các ước tính không phụ thuộc vào M.
4. Việc chuyển từ giải bài toán mở rộng sang giải bài toán ban đầu được thực hiện bằng các định lý 4.1-4.3 đã được chứng minh ở trên.
Ví dụ 4.4. 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. Hãy tạo một nhiệm vụ mở rộng. Chúng tôi đưa các biến nhân tạo không âm có hệ số (luôn luôn) +1 vào vế trái của các phương trình của hệ ràng buộc. Sẽ thuận tiện hơn khi viết các biến nhân tạo đã giới thiệu ở bên phải phương trình. Trong phương trình đầu tiên chúng ta nhập , trong phương trình thứ hai - . Bài toán này là bài toán tìm cực đại nên chúng được đưa vào hàm mục tiêu với hệ số - M. Chúng tôi nhận được
Vấn đề đã có lời giải tham khảo ban đầu 
với cơ sở đơn vị 
.
Chúng ta tính toán ước lượng các vectơ điều kiện dựa trên nghiệm tham chiếu và giá trị của hàm mục tiêu trên nghiệm tham chiếu.
. 
.
Chúng tôi ghi lại dữ liệu nguồn trong một bảng đơn giản (Bảng 4.6).
Bảng 4.6
Đồng thời, ước tính và 
để dễ tính toán, chúng tôi viết thành hai dòng: ở dòng đầu tiên - các thuật ngữ không phụ thuộc vào M, trong phần thứ hai - các điều khoản 
, phụ thuộc vào M. Giá trị 
thuận tiện để chỉ ra mà không cần M, tuy nhiên, hãy nhớ rằng nó hiện diện ở đó.
Giải pháp hỗ trợ ban đầu không phải là tối ưu vì bài toán cực đại có ước lượng âm. Chúng ta chọn số vectơ được nhập vào cơ sở của nghiệm tham chiếu và số vectơ dẫn xuất từ cơ sở. Để làm điều này, chúng tôi tính toán số gia của hàm mục tiêu khi đưa từng vectơ có ước tính âm vào cơ sở và tìm mức tối đa của số gia này. Trong trường hợp này, các điều khoản của ước tính (không có M) bị bỏ qua miễn là có ít nhất một số hạng 
(Với M) sẽ không khác 0. Về vấn đề này, hàng có các thuật ngữ đánh giá có thể không có trong bảng miễn là có hàng đó 
. Chúng tôi tìm thấy ở k= 3.
Trong cột thứ ba " ", chúng tôi chọn hệ số 1 ở hàng thứ hai làm phần tử phân giải và thực hiện phép biến đổi Jordan.
Vectơ dẫn xuất từ cơ sở bị loại khỏi việc xem xét (gạch bỏ). Chúng tôi thu được giải pháp tham khảo 
có cơ sở 
(Bảng 4.7). Lời giải không tối ưu vì có ước lượng âm 
= —
1.
Bảng 4.7
Trong cột " ", chúng tôi lấy phần tử dương duy nhất làm độ phân giải và chuyển sang giải pháp tham chiếu mới 
có cơ sở 
(Bảng 4.8).
Bảng 4.8
Lời giải tham chiếu này là lời giải tối ưu duy nhất cho bài toán mở rộng, vì trong bài toán cực đại, ước lượng cho tất cả các vectơ không có trong cơ sở đều dương. Theo Định lý 4.1, bài toán ban đầu cũng có nghiệm tối ưu thu được từ nghiệm tối ưu của bài toán mở rộng bằng cách loại bỏ các biến nhân tạo bằng 0, tức là. X* = (0,0,6,2).
Trả lời:tối đa Z(X) = -10 tại 
.
Ví dụ 4.5. Giải bài toán quy hoạch tuyến tính có ràng buộc hỗn hợp bằng phương pháp cơ sở nhân tạo
Giải pháp. Chúng tôi đưa bài toán quy hoạch tuyến tính về dạng chính tắc. Để làm điều này, chúng tôi lần lượt giới thiệu các biến bổ sung vào ràng buộc thứ nhất và thứ ba. Chúng tôi nhận được
.
Chúng tôi soạn một bài toán mở rộng, trong đó chúng tôi lần lượt đưa các biến nhân tạo vào phương trình thứ hai và thứ ba. Chúng tôi nhận được
Bài toán mở rộng này đã có giải pháp hỗ trợ ban đầu
Với cơ sở đơn vị 
, 
. Chúng ta tính toán các ước lượng của vectơ điều kiện dựa trên nghiệm tham chiếu và viết chúng vào bảng đơn theo cách tương tự như trong ví dụ trước. Giải pháp này không tối ưu, vì trong bài toán tối thiểu các vectơ có ước lượng dương. Cải tiến các giải pháp hỗ trợ. Mỗi giải pháp tham khảo có bảng riêng. Tất cả các bảng có thể được viết bên dưới bảng kia, kết hợp chúng thành một bảng duy nhất (Bảng 4.9).
Bảng 4.9
Chúng tôi xác định vectơ nào hoặc vào cơ sở của giải pháp hỗ trợ ban đầu sẽ dẫn đến giảm nhiều hơn chức năng mục tiêu. Chúng tôi tìm thấy tại k= 2, tức là tốt hơn nên đưa vectơ vào cơ sở. Chúng ta có được giải pháp hỗ trợ thứ hai với cơ sở 
. Hàm mục tiêu 
. Giải pháp này cũng không tối ưu vì vectơ có đánh giá tích cực 
. Ta đưa vectơ vào cơ sở, ta thu được nghiệm tham chiếu thứ ba với cơ sở 
. Hàm mục tiêu 
. Giải pháp này là tối ưu, nhưng không phải là giải pháp duy nhất, vì vectơ không có trong cơ sở có ước tính bằng 0. Vì vậy, cần phải chuyển sang giải pháp tham chiếu mới, giải pháp này cũng sẽ tối ưu. Để làm điều này, bạn cần đưa vectơ vào cơ sở.
Hãy chuyển sang giải pháp tham chiếu (tối ưu) thứ tư
Với cơ sở 
, trong đó 
. Lời giải tối ưu cho bài toán mở rộng không có biến nhân tạo. Do đó (theo Định lý 4.1) bài toán ban đầu cũng có hai nghiệm tối ưu 
Và 
. Chúng ta không viết thêm các biến vào nghiệm tối ưu của bài toán ban đầu.
Trả lời: 
Tại 
, 
, 
, 
.
Từ đơn giản
Từ simplex trong chữ cái tiếng Anh (dịch) - simpleks
Từ đơn gồm 8 chữ cái: e và k l m p s s
Ý nghĩa của từ đơn giản. Đơn giản là gì?
một mặt
Simplex (từ Latin simplex - đơn giản) (toán học), khối đa diện lồi đơn giản nhất số đã cho kích thước n. Khi n = 3, cấu trúc ba chiều là một cấu trúc tùy ý, bao gồm cả tứ diện không đều.
TSB. - 1969-1978
Một đơn hình là một đa giác lồi trong không gian n chiều với n+1 đỉnh không nằm trong cùng một siêu phẳng. S. được tách ra thành một lớp riêng biệt vì trong không gian n chiều n điểm luôn nằm trong cùng một siêu phẳng.
slovar-lopatnikov.ru
SIMPLEX là một đa giác lồi trong không gian n chiều với n+1 đỉnh không nằm trong cùng một siêu phẳng. S. được tách ra thành một lớp riêng biệt vì trong không gian n chiều n điểm luôn nằm trong cùng một siêu phẳng.
Lopatnikov. - 2003
Sub đơn giản
Sub simplex Hướng dẫn sử dụng và liều lượng: Uống, trong hoặc sau bữa ăn và nếu cần thiết, trước khi đi ngủ. Lắc mạnh chai trước khi sử dụng.
Giải ZLP bằng phương pháp đơn hình có cơ sở nhân tạo
Để huyền phù bắt đầu chảy ra từ pipet...
Sab simplex Hoạt chất >>>> Simethicone* (Simethicone*) Tên Latin Sab simplex ATX:>>A02DA Thuốc chữa bệnh Nhóm dược lý…
Từ điển thuốc. - 2005
SAB® SIMPLEX (SAB® SIMPLEX) Hỗn dịch uống có màu từ trắng đến trắng xám, hơi nhớt, có mùi trái cây đặc trưng (vani-quả mâm xôi). 100ml simethicone 6,919g…
SỐC SIMPLEX
CHOQUET SIMPLEX là tập lồi compact không rỗng X trong không gian lồi cục bộ E, có tính chất sau: khi E được nhúng dưới dạng siêu phẳng trong không gian thì tồn tại một hình nón chiếu.
Sheffield đơn giản
"Sheffield-Simplex" - xe bọc thép súng máy hạng nhẹ Lực lượng vũ trangĐế quốc Nga. Được phát triển bởi công ty Sheffield-Simplex của Anh dựa trên khung gầm của chiếc xe khách của chính hãng...
vi.wikipedia.org
Norditropin Simplex
Norditropin Simplex Chỉ định: Chậm tăng trưởng ở trẻ em do thiếu hụt hormone tăng trưởng hoặc suy thận mãn tính (ở lứa tuổi tiền dậy thì), hội chứng Shereshevsky-Turner...
NORDITROPIN® SIMPLEX® (NORDITROPIN SimpleXx) Dung dịch tiêm dưới da 1,5 ml (1 hộp) somatropin 10 mg 1,5 ml - hộp mực (1) - bao bì tế bào đường viền (1) - gói bìa cứng.
Danh mục thuốc Vidal
TIÊU CHUẨN SIMPLEX
ĐƠN GIẢN TIÊU CHUẨN - 1) S. s. - một đơn hình có chiều n trong không gian với các đỉnh tại các điểm e i=(0,..., 1,..., 0), i=0,..., n ( thiết bị đang bật vị trí thứ i), I E.
Bách khoa toàn thư toán học. — 1977-1985
Phương pháp đơn giản kép
Phương pháp đơn giản kép có thể được sử dụng để giải một bài toán quy hoạch tuyến tính, các số hạng tự do của hệ phương trình có thể là số bất kỳ. Trong thuật toán đơn giản thông thường, kế hoạch phải luôn khả thi.
vi.wikipedia.org
Ngôn ngữ Nga
Đơn giản/.
Từ điển chính tả hình thái. - 2002
Tìm kiếm bài giảng
Một ví dụ về giải bài toán bằng phương pháp cơ sở nhân tạo.
Tìm cực tiểu của hàm số F=-2×1+3×2 – 6×3 – x4 trong những điều kiện
Giải pháp. Hãy viết nó ra nhiệm vụ nàyở dạng bài toán chính: tìm cực trị của hàm số F1=2×1 – 3×2 + 6×3 + x4 trong những điều kiện
Trong hệ phương trình của bài toán cuối, xét vectơ các hệ số của ẩn số:
A1= A2= MỘT 3= MỘT 4= MỘT 5= MỘT 6=
Trong số các vectơ A1,…, MỘT 6 chỉ có hai cái duy nhất ( MỘT 4 và MỘT 5). Vì thế ở bên trái của phương trình thứ ba của hệ giới hạn, ta thêm một biến không âm bổ sung x 7 và xét bài toán mở rộng là cực đại hóa hàm số
F=2×1 – 3×2 + 6×3 + x4 – Mx7
trong những điều kiện
Bài toán mở rộng có sơ đồ tham chiếu X=(0; 0; 0; 24; 22; 0; 10), được xác định bởi hệ ba vectơ đơn vị: MỘT 4 , A5 , A7 .
Bảng 1
| Tôi | Nền tảng | Сσ | A0 | -3 | —M | |
| A1 | A2 | A3 | A4 | A5 | A6 | P7 |
| A4 | -2 | |||||
| A5 | ||||||
| A7 | —M | -1 | -1 | |||
| tôi+1 | -8 | |||||
| tôi+2 | -10 | -1 | -2 |
Chúng tôi biên soạn bảng (1) của lần lặp I, chứa năm hàng. Để điền vào dòng thứ 4 và thứ 5, chúng tôi tìm thấy F 0 và giá trị chênh lệch zj – cj(j=):
F 0 = 24–10M;
z1–c1= 0–M;
z2–c2 = 4+M;
z3–c3= –8–2M;
z4–c4=0+M;
z5–c5=0+M;
z6–c6= 0+M;
z7–c7=0+M;
Giá trị F 0 và zj–cj bao gồm hai thuật ngữ, một trong số đó chứa M, còn cái kia thì không.
Để thuận tiện cho quá trình lặp lại, số bao gồm M, viết vào dòng thứ 5 và thuật ngữ không chứa M, – ở dòng thứ 4.
Tại dòng thứ 5 của bảng 1 trong các cột vectơ Аj (j= ) có hai số âm (-1 Và -2). Sự hiện diện của những con số này cho thấy kế hoạch tham khảo này cho bài toán mở rộng là không tối ưu. Hãy chuyển sang sơ đồ tham chiếu mới của bài toán mở rộng.
Phương pháp cơ sở nhân tạo.
Chúng tôi đưa vectơ vào cơ sở A3. Để xác định vectơ bị loại khỏi cơ sở, chúng ta tìm θ=min(22/4; 10/2)=10/2. Do đó, vectơ A7 loại trừ khỏi cơ sở. Sẽ vô nghĩa khi nhập vectơ này vào bất kỳ cơ sở nào tiếp theo, vì vậy trong tương lai cột của vectơ này sẽ không được điền vào (Bảng 2 và 3).
Chúng tôi soạn bảng II của lần lặp (Bảng 2). Nó chỉ chứa bốn hàng vì vectơ nhân tạo bị loại khỏi cơ sở.
ban 2
| Tôi | Nền tảng | Сσ | A0 | -3 | |
| A1 | A2 | A3 | A4 | A5 | A6 |
| A4 | -1 | ||||
| A5 | -1 | ||||
| A3 | 1/2 | -1/2 | -1/2 | ||
| tôi+1 | -4 |
Như có thể thấy từ bảng. 2, đối với vấn đề ban đầu, tài liệu tham khảo là kế hoạch X=(0;0;5;34;2).
Hãy kiểm tra nó để tối ưu. Để làm điều này, hãy xem xét các yếu tố của dòng thứ 4. Ở hàng này trong cột vectơ A6 có số âm (-4). Do đó, sơ đồ tham chiếu này không tối ưu và có thể được cải thiện bằng cách đưa vào vectơ A6. Vectơ được loại trừ khỏi cơ sở A5. Chúng tôi biên soạn bảng III của phép lặp.
bàn số 3
Ở dòng thứ 4 của bảng 3 trong số các số ∆j không có tiêu cực. Điều này có nghĩa là sơ đồ tham chiếu mới tìm được của bài toán ban đầu X*=(0; 0; 11/2; 35; 0; 1) là tối ưu. Về vấn đề này, giá trị hình tuyến tínhFmax = 68.
Giải pháp cho vấn đề này có thể được thực hiện bằng cách sử dụng một bảng trong đó tất cả các lần lặp được ghi lại một cách tuần tự.
©2015-2018 poisk-ru.ru
Tất cả các quyền thuộc về tác giả của họ. Trang web này không yêu cầu quyền tác giả, nhưng cung cấp sử dụng miễn phí.
Vi phạm bản quyền và vi phạm dữ liệu cá nhân
Phương pháp cơ sở nhân tạo (bài toán M).
Đối với nhiều bài toán quy hoạch tuyến tính viết dưới dạng bài toán chính và có sơ đồ tham chiếu thì không phải lúc nào cũng có m vectơ đơn vị trong số các vectơ P j.
Hãy xem xét vấn đề sau:
Giả sử chúng ta cần tìm cực đại của hàm
F = c 1 x 1 + c 2 x 2 + ……+ c N x N (1)
trong những điều kiện
……………………………………… (2)
Ở đâu b Tôi 0 ( Tôi=l, m), tôi<.>N và trong số các vectơ P 1 , P 2 , …, P n không có m đơn vị nào.
Sự định nghĩa. Nhiệm vụ xác định giá trị lớn nhất của hàm số
F= c 1 x 1 + c 2 x 2 + ……+ c N x N -Mx N +1 - ... - Mx N + tôi (3)
trong những điều kiện
……………………………………… (4)
trong đó M là một số dương đủ lớn, giá trị cụ thể của nó thường không được xác định, được gọi là bài toán mở rộng (M-task) liên quan đến bài toán (1) - (2).
Nhiệm vụ mở rộng có kế hoạch tham khảo
X=(0; 0; ...; 0; b 1 ; b 2 ; ...;bm).
được xác định bởi hệ vectơ đơn vị P n +1 ; R n+2 , … R p+t , tạo thành cơ sở của không gian vectơ m-ro, được gọi là nhân tạo. Bản thân các vectơ cũng như các biến x n + tôi ( Tôi= tôi, tôi), được gọi là nhân tạo. Vì bài toán mở rộng có sơ đồ tham chiếu nên lời giải của nó có thể được tìm ra bằng phương pháp đơn hình.
Định lý Nếu tối ưu X*=( x* 1 , x* 2 , ...; x*N , x* n +1 ; ...; x*n+m) nhiệm vụ mở rộng (3) - (4) giá trị của biến nhân tạo x* n + tôi =0 ( Tôi=1, tôi), Cái đó X*=( x* 1 , x* 2 , ...; x*N) là phương án tối ưu cho vấn đề (1) - (2).
Do đó, nếu trong phương án tối ưu tìm được cho bài toán mở rộng, giá trị của các biến nhân tạo bằng 0 thì thu được phương án tối ưu cho bài toán ban đầu.
Các giá trị dòng chỉ số ∆ 0 , ∆ 1 , …, ∆ n gồm hai phần, một phần phụ thuộc vào M, nhưng cái kia thì không. Điền vào một bảng đơn giản - một bảng chứa nhiều hàng hơn một bảng đơn giản thông thường. Trong trường hợp này, dòng thứ (m+2) chứa các hệ số của M, và trong (m+1)th – các số hạng không chứa M. Khi di chuyển từ sơ đồ tham chiếu này sang sơ đồ tham chiếu khác, một vectơ tương ứng với giá trị tuyệt đối lớn nhất sẽ được đưa vào cơ sở số âm(m+2) dòng thứ. Một vectơ nhân tạo bị loại khỏi cơ sở không được ghi lại trong bảng đơn sau. Việc tính toán lại các bảng đơn khi chuyển từ sơ đồ tham chiếu này sang sơ đồ tham chiếu khác được thực hiện theo quy tắc chung phương pháp đơn giản.
Quá trình lặp lại dọc theo đường (m+2) tiếp tục cho đến khi:
hoặc tất cả các vectơ nhân tạo sẽ không bị loại khỏi cơ sở;
hoặc không phải tất cả các vectơ nhân tạo đều bị loại trừ, nhưng hàng thứ (m+2) không chứa thêm phần tử âm nào trong các chỉ số ∆ 1, …, ∆ n.
Trong trường hợp đầu tiên, cơ sở tương ứng với một số phương án tham chiếu của bài toán ban đầu và việc xác định phương án tối ưu của nó tiếp tục dọc theo đường thứ (m+1).
Trong trường hợp thứ hai, nếu giá trị ∆ 0 âm thì bài toán ban đầu không có lời giải; nếu ∆ 0 = 0 thì sơ đồ tham chiếu tìm được của bài toán ban đầu bị suy biến và cơ sở chứa ít nhất một trong các vectơ cơ sở nhân tạo.
Các giai đoạn tìm lời giải của bài toán (1) - (2)
phương pháp cơ sở nhân tạo:
Soạn bài toán mở rộng (3) - (4).
Tìm sơ đồ tham chiếu của bài toán mở rộng.
Sử dụng các phép tính thông thường của phương pháp đơn hình, các biến nhân tạo được loại trừ khỏi cơ sở. Kết quả là, kế hoạch tham chiếu của bài toán ban đầu (1) - (2) được tìm thấy hoặc tính không thể giải được của nó được thiết lập.
Sử dụng phương án tham chiếu tìm được của bài toán (1) - (2), họ có thể tìm ra phương án tối ưu của bài toán ban đầu bằng phương pháp đơn hình hoặc thiết lập tính không giải được của nó.
Ví dụ.
Tìm cực tiểu của hàm số F= - 2x 1 + 3x 2 - 6x 3 - x 4
P 
với những hạn chế:
2x 1 +x 2 -2x 3 +x 4 =24
x 1 +2x 2 +4x 3 22
x 1 -x 2 +2x 3 ≥10
x Tôi ≥0, Tôi=1,4
Giải pháp.
Hãy viết bài toán này dưới dạng bài toán chính: tìm cực đại của hàm số F= 2x 1 - 3x 2 + 6x 3 + x 4
với những hạn chế:
2x 1 +x 2 -2x 3 +x 4 =24
x 1 +2x 2 +4x 3 +x 5 =22
x 1 -x 2 +2x 3 - x 6= 10
x Tôi ≥0, Tôi=1, 6
Trong hệ phương trình của bài toán cuối, xét vectơ các hệ số của ẩn số:
Trong số các vectơ P 1, R 2 , ... P 6 chỉ có 2 cái duy nhất (P 4 và P 5). Do đó, ta thêm một biến không âm x vào vế trái của phương trình thứ ba của hệ ràng buộc bài toán 7 và xem xét bài toán mở rộng về việc cực đại hóa hàm
F= 2x 1 - 3x 2 + 6x 3 + x 4 - Мх7
với những hạn chế:
2x 1 +x 2 -2x 3 +x 4 =24
x 1 +2x 2 +4x 3 +x 5 =22
x 1 -x 2 +2x 3 - x 6 +x 7= 10
Bài toán mở rộng có sơ đồ tham chiếu X = (0; 0; 0; 24; 22; 0; 10), được xác định bởi hệ ba vectơ đơn vị: P 4 , P 5 , P 7 .
Khái niệm về bài toán quy hoạch tuyến tính kép (phù hợp).
Nội quy xây dựng vấn đề kép.
Với mỗi bài toán quy hoạch tuyến tính (LPP) được gọi là bài toán đối ngẫu (hay bài toán phụ) đối với bài toán ban đầu, bài toán này gọi là bài toán trực tiếp.
Bài toán kép được xây dựng liên quan đến bài toán trực tiếp, viết dưới dạng chuẩn:
F=c 1 x 1 +c 2 x 2 +…+c n x n max (3,6)
a 11 x 1 +a 12 x 2 +…+a 1n x n ≤ b 1,
a 21 x 1 +a 22 x 2 +…+a 2n x n ≤ b 2,
………………………………
a k1 x 1 +a k2 x 2 +…+a kn x n ≤ =b k , (3.7)
a k+1.1 x 1 +a k+1.2 x 2 +…+a k+1,n x n =b k+1 ,
………………………………
a m1 x 1 +a m2 x 2 +…+a mn x n =b m ,
xj ≥ 0, , tôi≤ n (3,8)
Bài toán tìm giá trị nhỏ nhất của hàm số
L = b 1 y 1 + b 2 y 2 + … + b m y m (3.9)
trong những điều kiện
a 11 y 1 + a 12 y 2 +…+ a m1 y m ≥ c 1
a 21 y 1 + a 22 y 2 +…+ a m2 y m ≥ c 2
………………………………
một 1 tôi y 1 + a 2 tôi y 2 +…+ a m tôi y m ≥ c tôi (3.10)
Một tôi+1,1 y 1 + a tôi+1,2 y 2 +…+ a tôi+1,m y m = c tôi+1
………………………………
a m1 y 1 + a m2 y 2 +…+ a mn y m = c m
y i ≥ 0, , k ≤ m (3.11)
được gọi là bài toán đối ngẫu (3.6) – (3.8).
Các quy tắc xây dựng một bài toán kép được cho trong bảng:
|
Đặc điểm cấu trúc của ZLP |
Bài toán quy hoạch tuyến tính |
|
|
Hai |
||
|
1. Hàm mục tiêu |
Tối đa hóa (tối đa) |
Giảm thiểu (phút) |
|
2. Số lượng biến |
n biến |
Bằng số ràng buộc của bài toán trực tiếp (3.7), y i , tức là tôi |
|
3. Số lượng hạn chế |
m hạn chế |
Bằng số biến của bài toán trực tiếp x j , tức là n |
|
4. Ma trận hệ số trong hệ hạn chế |
|
|
|
5. Hệ số các biến trong hàm mục tiêu |
c 1 ,c 2, …,c n |
b 1 ,b 2,…,b m |
|
6. Phần bên phải hệ thống hạn chế |
b 1 ,b 2,…,b m |
c 1 ,c 2, …,c n |
|
7. Biển báo trong hệ thống hạn chế |
a) x j ≥ 0 - điều kiện không âm |
Ràng buộc thứ j có dấu “ ≥” |
|
b) điều kiện không âm không được áp đặt cho biến x j |
Ràng buộc thứ j có dấu “=” |
|
|
c) ràng buộc thứ i có dấu “<” |
biến y i ≥0 |
|
|
d) ràng buộc thứ i có dấu “=” |
điều kiện không âm không được áp đặt cho biến y i |
|
Ghi chú
Bài toán cực đại trực tiếp và bài toán cực tiểu kép là những bài toán đối ngẫu lẫn nhau. Do đó, ta có thể coi bài toán (3.9) – (3.11) là bài toán ZLP trực tiếp và bài toán (3.6) – (3.8) là bài toán kép của nó. Trong trường hợp này, các quy tắc xây dựng PLP kép được giữ nguyên, chỉ với bởi sự thay đổi đó, rằng bài toán tối thiểu được coi là bài toán ban đầu.
Nếu bài toán ban đầu được giải ở mức tối đa (tối thiểu) và trong hệ ràng buộc) Tôi-e ( j-f) ràng buộc có dấu “<” (“>”) thì để xây dựng bài toán đối ngẫu cần:
a) hoặc nhân cả hai phần Tôi th ( j-th) bất đẳng thức theo (-1) và đổi dấu thành “<” (“>”)
b) hoặc mang theo Tôi-e ( j-e) ràng buộc sự bình đẳng bằng cách đưa ra một biến bổ sung x n+ Tôi ≥0
