Phương pháp đơn giản để giải các bài toán quy hoạch tuyến tính. Một ví dụ về giải bài toán trực tiếp và kép bằng phương pháp đơn giản

Nếu phát biểu bài toán chứa các hạn chế có dấu ≥ thì chúng có thể rút gọn về dạng ∑a ji b j bằng cách nhân cả hai vế của bất đẳng thức với -1. Chúng ta hãy giới thiệu m biến bổ sung x n+j ≥0(j =1,m) và chuyển đổi các ràng buộc về dạng đẳng thức

(2)

Chúng ta hãy giả sử rằng tất cả ban đầu biến nhiệm vụ x 1 , x 2 ,..., x n – không cơ bản. Khi đó các biến bổ sung sẽ là biến cơ bản và lời giải cụ thể cho hệ ràng buộc có dạng

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

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

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

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

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

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

Bước thứ 2. Để tìm ra một giải pháp có thể chấp nhận được, nó được thực hiện và cần phải quyết định biến nào không cơ bản sẽ đưa vào cơ sở và biến nào cần loại bỏ khỏi cơ sở.

Bảng 1.

x n

biến cơ bản	Thành viên miễn phí bị hạn chế	Các biến không cơ bản
biến cơ bản	Thành viên miễn phí bị hạn chế	x 1	x 2	...	xl	...
xn+1	b 1	số 11	số 12	...	một 1l	...	một 1n
xn+2	b 2	21	một 22	...	một 2l	...	một 2n
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+r	b2	một r1	một r2	...	một rl	...	arn
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
.	.	.	.	.	.	.	.
x n+m	b m	một m1	một m2	...	một ml	...	một phút
F(x)tối đa	F 0	-c 1	-c 2	...	-c 1	...	-c n

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

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

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

Đường thẳng tương ứng với biến x n+r được gọi là dẫn đầu hoặc cho phép. Phần tử của bảng đơn a rl, nằm ở giao điểm của hàng đầu và cột đầu, được gọi là phần tử đầu hoặc phần tử phân giải. Việc tìm kiếm phần tử dẫn đầu kết thúc công việc với mỗi bảng đơn giản thông thường.

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

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

Các công thức còn lại có thể được viết dễ dàng bằng cách sử dụng .

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

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

Bước thứ 5. Chúng tôi tin rằng một giải pháp cơ bản có thể chấp nhận được đã được tìm ra. Chúng ta xét các hệ số của đường hàm mục tiêu F(x) . Một dấu hiệu về tính tối ưu của bảng đơn là tính không âm của các hệ số đối với các biến không cơ bản trong hàng F.

Cơm. 1. Quy tắc hình chữ nhật

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

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

Bước thứ 6. theo các quy tắc được nêu ở bước 3. Thủ tục tiếp tục cho đến khi tìm thấy giải pháp tối ưu hoặc được kết luận là nó không tồn tại.

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

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

Ví dụ 1. Giải bài toán

max(F(x) = -2x 1 + 5x 2 | 2x 1 + x 2 ≤7; x 1 + 4x 2 ≥8; x 2 ≤4; x 1,2 ≥0)

Sử dụng phương pháp đơn hình và đưa ra cách giải thích hình học của quá trình giải.

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

Chúng tôi lấy các biến ban đầu x 1 và x 2 là không cơ bản và coi x 3, x 4 và x 5 bổ sung là cơ bản và soạn một bảng đơn giản (bảng đơn giản 2). Lời giải tương ứng với bảng đơn. 2, không hợp lệ; phần tử hàng đầu được phác thảo và chọn theo bước 2 của thuật toán trước. Bảng đơn giản sau đây. 3 xác định một nghiệm cơ bản có thể chấp nhận được; đỉnh của ODZP trong Hình 1 tương ứng với nó. 2 Phần tử chủ đạo được phác thảo và lựa chọn theo bước 5 của thuật toán giải bài toán. Bàn 4 tương ứng với phương án tối ưu của bài toán, do đó: x 1 = x 5 = 0; x 2 = 4; x 3 = 3; x 4 = 8; F tối đa = 20.

Cơm. 2. Giải pháp đồ họa nhiệm vụ

Để đơn giản hóa quá trình giải, dữ liệu ban đầu của bài toán lập trình tuyến tính Khi giải bằng phương pháp đơn hình, chúng được ghi vào các bảng đơn hình đặc biệt. Do đó, một trong những sửa đổi của phương pháp đơn hình được gọi là bảng đơn giản phương pháp. Bài toán quy hoạch tuyến tính ở dạng chính tắc:

a 1,1 x 1 +a 1,2 x 2 +...a 1,n x n + x n+1 =b 1

Bảng nguồn của tác vụ có lượt xem tiếp theo:

	x 1	x 2	...	xn-1	x n	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
...	...	...	...	...	...	...
x n+m	một m,1	một m,2	...	một m,n-1	một m, n	b m

x 1 , x 2 , x n - biến ban đầu, x n+1 , x n+2 , x n+m - biến bổ sung. Chúng tôi lấy tất cả các biến bổ sung như nền tảng và các biến ban đầu là không cơ bản(những cái bổ sung được viết ở cột đầu tiên của bảng đơn và những cái gốc ở hàng đầu tiên). Ở mỗi lần lặp, các phần tử của bảng đơn được tính toán lại theo một số giá trị nhất định.

Thuật toán của phương pháp đơn giản.

Giai đoạn chuẩn bị

Chúng tôi giảm vấn đề LP thành hình thức kinh điển

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 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 giá trị nhỏ nhất - dấu của các hệ số hàm mục tiêu F bị đảo ngược 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 “<” thì các hệ số sẽ được viết không thay đổ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	x n	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
...	...	...	...	...	...	...
x n+m	một m,1	một m,2	...	một m,n-1	một m, n	b m

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 lại phần tử âm trong cột số hạng tự do thì chúng 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 tính tối ưu. Nếu trong số các phần tử của bảng đơn nằm ở hàng 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) không có phần tử âm thì đã tìm được lời giải tối ưu.

Nếu chuỗi F chứa các phần tử âm thì giải pháp cần được cải thiện. Trong số các phần tử âm của chuỗi F ta chọn phần tử có giá trị tuyệt đối lớn nhất (không bao gồm giá trị của hàm b 0)

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 ta tính toán lại bảng đơn bằng . Nếu ở bảng mới sau khi tính toán lại còn phần tử âm ở dòng F, vào bước 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.

Quy tắc chuyển đổi bảng đơn giản.

Khi tạo một bảng đơn giản mới, những thay đổi sau sẽ xảy ra:

Thay vì biến cơ bản x k chúng ta viết x l ; thay vì biến không cơ bản x l chúng ta viết x k.
phần tử đứng đầu được thay thế bằng giá trị nghịch đảo a k,l "= 1/a k,l
tất cả các phần tử của cột đầu tiên (trừ a k,l) được nhân với -1/a k,l
tất cả các phần tử của dòng đầu tiên (trừ ak,l) được nhân với 1/a k,l
các phần tử còn lại của bảng đơn được biến đổi theo công thức a i,j "= a i,j - a i,l x a k,j / a k,l

Lược đồ chuyển đổi các phần tử của bảng đơn (trừ hàng đầu và cột đầu) được gọi là lược đồ “hình chữ nhật”.

Phần tử đã chuyển đổi một tôi, j và ba phần tử tương ứng với nó chính là các đỉnh của “hình chữ nhật”.

Của chúng tôi bảng đơn là một ma trận hệ thống ràng buộc mở rộng với một số cột và hàng bổ sung. Hãy xem xét một ví dụ về bảng đơn giản cho bài toán sau:

Tìm giá trị biến x 1...x 5, trong đó hàm:

Q =

x 1

x 2

chấp nhận tối đa giá trị, tuân theo các hạn chế sau:

x 1

x 2

x 3

(1)

x 1

x 2

x 4

(2)

x 2

x 5

(3)

x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0

Bảng đơn giản trông như thế này:

x 1

x 2

x 3

x 4

x 5

Giải pháp

Thái độ

x 3

x 4

x 5

-1

-2

nhất dòng trên cùng- hoàn toàn mang tính thông tin, nó chỉ ra mục đích của các cột. Cột "BP" cũng mang tính thông tin; mỗi ô của cột này chứa tên của một biến nằm trong phương trình tương ứng của hệ ràng buộc. Trong ví dụ của chúng tôi, trong phương trình đầu tiên, biến X 3, ở X 4 thứ hai, ở X 5 thứ ba.

Cột X 1...X 5 chứa hệ số các biến tương ứng trong các phương trình của hệ ràng buộc (mỗi phương trình viết một dòng riêng). Cột "Giải pháp" ban đầu chứa các số hạng tự do của các phương trình tương ứng. Chúng cũng hiển thị các giá trị cho lời giải hiện tại, được hiển thị bằng bảng đơn giản, ở một bước (lặp lại) nhất định để giải quyết vấn đề.

Các hệ số của hàm mục tiêu được phản ánh trong bảng đơn ở hàng “Q”; số hạng tự do, như trong trường hợp các phương trình của hệ ràng buộc, ban đầu được viết trong cột “Giải pháp”. Nó cũng là giá trị của hàm mục tiêu, nhưng được viết bằng dấu ngược lại (điều này thuận tiện cho phương pháp đơn hình). Trong ví dụ của chúng tôi, bảng đơn giản được hiển thị tương ứng với một giải pháp nhất định trong đó các biến X 3, X 4, X 5 lần lượt bằng 64, 70, 18 (xem cột “Giải pháp”) và các biến còn lại bằng nhau về không. Giá trị của hàm mục tiêu "Q" bằng hai (dễ dàng kiểm tra bằng cách thay thế các giá trị của các biến vào biểu thức của hàm mục tiêu).

Trong ví dụ của chúng tôi, số hạng tự do bằng -2 (trừ hai) vì khi ghi hàm mục tiêu, nó được viết cùng với các biến ở một bên của dấu bằng, và các số hạng tự do trong các phương trình của hệ ràng buộc ở bên kia. Vì vậy trước khi ghi vào bảng phải chuyển nó sang bên phải dấu bằng.

Dòng "Q" trong trong ví dụ nàyđược phân bổ màu vàng, điều này có nghĩa là nó sẽ được sử dụng để đưa ra quyết định liên quan đến việc lựa chọn cột phân giải (đôi khi được gọi là cột hướng dẫn). Cột giải quyết tương ứng với một biến sẽ được nhập vào cơ sở (vào danh sách) ở lần lặp lại giải quyết vấn đề tiếp theo. Mục đích của việc thay thế cơ sở như vậy là để cải thiện giá trị của hàm mục tiêu. Tiêu chí chọn cột giải là hệ số dương lớn nhất ở hàng Q khi giải bài toán ở mức tối đa hoặc hệ số âm nhỏ nhất khi giải bài toán ở mức tối thiểu. Nếu sau lần lặp tiếp theo không có hệ số dương (trong quá trình tối đa hóa) hoặc âm (trong quá trình tối thiểu hóa) trong dòng thì giải pháp tối ưu đã đạt được. Trong ví dụ của chúng tôi, cột phân giải được chọn theo hệ số 7 (dương cực đại vì bài toán là cực đại), nó tương ứng với biến X 2, chính biến này sẽ được nhập vào cơ sở ở lần lặp tiếp theo. Các số trong cột hướng dẫn có màu đỏ.

Dòng phân giải (hướng dẫn) cũng có màu đỏ; nó tương ứng với một biến sẽ bị loại bỏ khỏi cơ sở (danh sách) ở lần lặp tiếp theo. Để xác định nó, cột "Tỷ lệ" được tính toán và điền vào. Các phần tử của nó thể hiện mối quan hệ giữa các phần tử của cột “Giải pháp” với các phần tử tương ứng của cột hướng dẫn (ngoại trừ hàng “Q”). Đường phân giải được chọn theo giá trị tối thiểu từ mọi mối quan hệ. Điều quan trọng là các tỷ lệ này chỉ được tính cho các phần tử dương của cột dẫn hướng. Nếu tại một số lần lặp không có hệ số dương trong cột hướng dẫn thì hàm mục tiêu vấn đề ban đầu không giới hạn, vấn đề không có giải pháp.
Trong ví dụ của chúng tôi, dòng hướng dẫn được chọn theo tỷ lệ tối thiểu là 16, nó tương ứng với X 3 và chính dòng này sẽ bị xóa khỏi cơ sở ở lần lặp tiếp theo (vị trí của nó sẽ được X 2 đảm nhận).

Chúng tôi tạo thành phần tiếp theo của bảng đơn giản. Thay vì biến x6, phương án 1 sẽ bao gồm biến x2.

Hàng tương ứng với biến x2 trong phương án 1 có được bằng cách chia tất cả các phần tử của hàng x6 của phương án 0 cho phần tử phân giải RE=1. Thay cho phần tử phân giải trong phương án 1, chúng ta nhận được 1. Trong các ô còn lại của cột x2 của phương án 1, chúng ta viết số không.

Do đó, trong sơ đồ 1 mới, hàng x2 và cột x2 được điền. Tất cả các phần tử khác của sơ đồ 1 mới, bao gồm các phần tử của hàng chỉ mục, được xác định theo quy tắc hình chữ nhật. Để làm điều này, chúng tôi chọn bốn số từ sơ đồ cũ, nằm ở các đỉnh của hình chữ nhật và luôn bao gồm phần tử phân giải

NỐT RÊ. NE = SE - (A*B)/RE

STE - phần tử của sơ đồ cũ, RE - phần tử phân giải (1), A và B - các phần tử của sơ đồ cũ, tạo thành một hình chữ nhật có các phần tử STE và RE.

Hãy trình bày cách tính của từng phần tử dưới dạng bảng:





(0)-(2 * (-2+2M)):1	(-1-M)-(-2 * (-2+2M)):1	(-2+2M)-(1 * (-2+2M)):1	(-M)-(-1 * (-2+2M)):1	(-M)-(0 * (-2+2M)):1	(0)-(0 * (-2+2M)):1	(0)-(1 * (-2+2M)):1	(0)-(0 * (-2+2M)):1

Chúng tôi nhận được một bảng đơn giản mới

Lặp lại số 1.

1. Kiểm tra tiêu chí tối ưu. Phương án tham chiếu hiện tại không tối ưu vì có các hệ số dương trong hàng chỉ số.
2. Định nghĩa một biến cơ bản mới. Chúng ta sẽ chọn cột tương ứng với biến x1 làm cột đầu tiên vì đây là hệ số lớn nhất.
3. Định nghĩa một biến tự do mới. Hãy tính các giá trị của Di theo hàng làm thương số của phép chia: bi / ai1 và chọn giá trị nhỏ nhất trong số đó:

phút (-, 1:3, -) = 1/3

Vì vậy, dòng thứ 2 là dòng dẫn đầu.

Phần tử phân giải bằng (3) và nằm ở giao điểm của cột đầu và hàng đầu

Chúng tôi tạo thành phần tiếp theo của bảng đơn giản.

Thay vì biến x7, phương án 2 sẽ bao gồm biến x1. Hàng tương ứng với biến x1 trong phương án 2 có được bằng cách chia tất cả các phần tử của hàng x7 của phương án 1 cho phần tử phân giải RE=3

Thay cho phần tử phân giải trong phương án 2, chúng ta nhận được 1. Trong các ô còn lại của cột x1 của phương án 2, chúng ta viết các số 0.

Như vậy, trong phương án 2 mới, hàng x1 và cột x1 được điền. Tất cả các phần tử khác của sơ đồ 2 mới, bao gồm các phần tử của hàng chỉ mục, được xác định theo quy tắc hình chữ nhật.

Hãy trình bày cách tính từng phần tử dưới dạng bảng





(0)-(1 * (-5+3M)):3	(-5+3M)-(3 * (-5+3M)):3	(0)-(0 * (-5+3M)):3	(-2+M)-(1 * (-5+3M)):3	(-M)-(-1 * (-5+3M)):3	(0)-(0 * (-5+3M)):3	(2-2M)-(-1 * (-5+3M)):3	(0)-(1 * (-5+3M)):3

Chúng tôi nhận được một bảng đơn giản mới:

3.1.
3.2.
3.3.
3.4.
3.5.
3.6. Ví dụ(1) giải bài toán LP bằng phương pháp bảng đơn
3.7. Ví dụ(2) giải bài toán LP bằng phương pháp bảng đơn

Ý tưởng của phương pháp bảng đơn giản là liệt kê có mục đích các đỉnh của một đơn hình. Để bắt đầu tìm kiếm, bạn cần chọn một đỉnh tham chiếu để bắt đầu tìm kiếm. Phương pháp đơn hình để giải một bài toán quy hoạch tuyến tính dựa trên sự chuyển đổi từ sơ đồ tham chiếu này sang sơ đồ tham chiếu khác (bằng cách liệt kê các đơn hình của các đỉnh) trong đó giá trị của hàm mục tiêu tăng (giảm). Việc chuyển đổi được chỉ định có thể thực hiện được nếu biết được một số kế hoạch tham chiếu ban đầu. Để lập một sơ đồ như vậy, cần thực hiện phân tích vectơ, trên cơ sở đó xác định đỉnh tham chiếu mà từ đó việc tìm kiếm sẽ bắt đầu.Hệ bất đẳng thức được rút gọn về dạng chính tắc:

x 1 + Một 1,m+1* x m+1 + ... + Một 1s* xs +...+ Một 1n * x n = b 1 ;

x2 + Một 2,m +1* x m+1 + ... + Một 2s * xs +...+ Một 2n* x n = b 2 ;

x m + Một m,m+1* x m+1 + ... + Một ms* x s +...+ Một mn* x n = b m.

Các biến x 1, x 2,...,x m chỉ có hệ số đơn vị trong một phương trình của hệ và không có hệ số bằng 0 ở các phương trình còn lại được gọi là nền tảng. Trong hệ thống chính tắc, mỗi phương trình tương ứng với chính xác một biến cơ bản. Nghỉ ngơi biến n-m(x m+1 , ...,x n) được gọi là các biến không cơ bản.

3.1. Đưa mô hình toán học về dạng chuẩn

Hãy cung cấp cho mô hình toán học vấn đề về dạng kinh điển.Để làm điều này, chúng ta hãy loại bỏ các dấu bất đẳng thức bằng cách đưa vào các biến bổ sung và thay thế dấu bất đẳng thức bằng dấu bằng. Một biến bổ sung được thêm vào riêng cho từng bất đẳng thức và biến này được chỉ định trong hàm mục tiêu với hệ số bằng 0. Quy tắc nhập thêm biến: với ">=" - biến được nhập vào bất đẳng thức có hệ số +1; Tại "<=" - с коэффициентом (-1).

Hơn nữa, đôi khi, khi không có biến cơ bản trong phương trình, để biến một biến âm bổ sung thành một biến cơ bản, bạn có thể nhân toàn bộ phương trình với (-1).

Bạn cũng có thể định hướng lại hàm mục tiêu từ cực tiểu đến cực đại hoặc ngược lại bằng cách nhân tất cả các hệ số của các biến trong hàm này với (-1).

3.2. Phân tích vectơ

Trong phân tích vectơ, vectơ được xây dựng cho từng biến: tọa độ thành phần của vectơ n chiều (n-số phương trình của hệ) sẽ là các hệ số của biến này trong các phương trình tương ứng.

Như đã đề cập ở trên, một vectơ trong đó chỉ có hệ số đơn vị trong một phương trình và không có hệ số trong các phương trình khác được gọi là nền tảng. Trong hệ thống chính tắc, mỗi phương trình tương ứng với chính xác một biến cơ bản. Sau khi kiểm tra tất cả các hạn chế, hệ thống thu được ở dạng chính tắc và có thể điền vào bảng đơn giản ban đầu.

3.3. Phương pháp biến nhân tạo

Điều thường xảy ra là có ít vectơ cơ sở hơn số phương trình, tức là một số phương trình không chứa các biến cơ bản. Trong trường hợp này, hãy sử dụng phương pháp biến nhân tạo để thêm các biến cơ bản.

Vì các biến được giới thiệu không liên quan đến bản chất của bài toán LP trong công thức ban đầu nên cần phải đảm bảo rằng các biến nhân tạo biến mất. Điều này có thể được thực hiện bằng phương pháp đơn giản hai bước.

Giai đoạn 1. Một hàm mục tiêu nhân tạo được xem xét, bằng tổng các biến nhân tạo, được tối thiểu hóa bằng phương pháp đơn hình. Nói cách khác, các biến nhân tạo bị loại trừ. Nếu giá trị nhỏ nhất của bài toán phụ bằng 0 thì tất cả các biến nhân tạo đều biến mất và thu được nghiệm cơ bản có thể chấp nhận được của bài toán ban đầu. Tiếp theo, giai đoạn 2 được thực hiện. Nếu giá trị tối thiểu của bài toán phụ là dương thì ít nhất một trong các biến nhân tạo cũng dương, điều này cho thấy sự không nhất quán của bài toán ban đầu và quá trình tính toán dừng lại.

Giai đoạn 2. Lời giải cơ bản khả thi tìm được ở giai đoạn đầu tiên được cải tiến phù hợp với hàm mục tiêu của bài toán LP ban đầu dựa trên phương pháp đơn hình, tức là. bảng tối ưu của giai đoạn 1 chuyển thành bảng ban đầu của giai đoạn 2 và hàm mục tiêu thay đổi.

3.4. Xây dựng một bảng đơn giản

Chọn giải pháp cơ sở khả thi ban đầu. Giải pháp cơ bản là một giải pháp thu được cho giá trị 0 của các biến không cơ bản, tức là. x i =0, i=m+1,...,n. Giải pháp cơ bản được gọi là giải pháp cơ bản được chấp nhận, nếu giá trị của các biến cơ bản có trong nó không âm, tức là. x j = b j>=0, j=1,2,...,m. Trong trường hợp này, hàm mục tiêu sẽ có dạng sau: S = c b* x b = c 1* b 1+ c 2* b 2 +...+c m* b m . Ta điền vào bảng ban đầu của phương pháp đơn hình:

Bảng 2.3

c b x b c 1 c 2 ... c m c m+1 ... c n tôi
nền tảng x 1 x 2 ... xm xm+1 ... x n
từ 1 x 1 1 0 ... 0 một 1,m+1 ... Một N b 1
từ 2 x 2 0 1 ... 0 Một 2,m+1 ... một 2 N b 2
... ... ... ... ... ... ... ... ... ...
c m xm 0 0 ... 1 một m,m+1 ... một tôi n b tôi
S

3.5. Phân tích bảng đơn giản

Tính vectơ ước lượng tương đối c sử dụng quy tắc tích số chấm

c j = c j - c b* S j,

Ở đâu

Với b - vectơ ước lượng các biến cơ bản;

S j - cột thứ j trong hệ quy chuẩn tương ứng với cơ sở đang xét.

Chúng tôi bổ sung bảng gốc c - đường kẻ.

Bảng 2.4

cơ sở x 1 x 2 ... x m x m+1 ... x n với 1 x 1 1 0 ... 0 Một 1,m+1 ... a 1 n b 1với 2 x 2 0 1 ... 0 Một 2,m+1 ... một 2 N b 2... ... ... ... ... ... ... ... ... ... c m x m 0 0 ... 1 Một m,m+1 ... a m n b m 0 0 ... 0 ... W

c b	x b	c 1	c 2	...	c m	c m+1	...	c n	tôi

c- đường kẻ

3. Nếu tất cả các ước tính c j <=0 (c j >= 0), i=1,...,n thì phương án khả thi hiện tại là lớn nhất (tối thiểu). Giải pháp đã được tìm thấy.

4. Mặt khác, cần phải đưa một biến không cơ bản x r có giá trị lớn nhất vào cơ sở c j thay vì một trong các biến cơ bản (Bảng 2.5).

Sử dụng quy tắc tỷ lệ tối thiểu phút( b Tôi/ Một ir) ta định nghĩa biến x p dẫn xuất từ cơ sở. Nếu hệ số Một ir âm thì b Tôi/ Một ir =vô cực. Kết quả, giao điểm của cột chứa biến cơ bản đầu vào x r và dòng chứa biến cơ bản đầu ra x p sẽ xác định vị trí của phần tử đầu bảng (Bảng 2.6).

Bảng 2.5

		c m+1			tôi
	nền tảng	xm+1
từ 1		một 1,m+1	một 1 r	một 1 n
từ 2		một 2,m+1	2 r	một 2 n

		một m,m+1	một tôi r	một tôi n	b m
c- đường kẻ

Bảng 2.6

c m+1

tôi

b tôi /

không khí

xm+1

từ 1

một 1,m+1

một 1 r

một 1 n

b 1/ Một 1r

từ 2

một 2,m+1

2 r

một 2 n

b 2 / Một 2r

với p

một p,m+1

tháng tư

apn

b p / Một PR

một m,m+1

một tôi r

một tôi n

b m

b m / Một nr

c- đường kẻ

6. Chúng ta áp dụng các phép biến đổi cơ bản để thu được nghiệm cơ bản khả thi mới và một bảng mới. Kết quả là phần tử đứng đầu phải bằng 1 và các phần tử còn lại của cột phần tử đứng đầu phải có giá trị bằng 0.

Chúng tôi tính điểm tương đối mới bằng cách sử dụng quy tắc biến đổi vô hướng và chuyển sang bước 4.