Thuật Toán Đơn Hình Đối Ngẫu Khi Không Biết Cơ Sở Đối Ngẫu

Ta thấy các ẩn cơ bản đều nhận giá trị dương  PATƯ Kết luận: - PATƯ là x* = (x1, x2, x3, x4) = (0, 7, 6, 1)

- Giá trị tối ưu đạt được là: f(x*) = - g(x*) = 2

Chú ý 2: Từ bảng thứ 2 của bảng đơn hình đối ngẫu, ta nên tính cột giả phương án trước, nếu chúng đều nhận giá trị ≥ 0 thì ta không cần tính các ô còn lại nữa và kết thúc thuật toán kết luận về bài toán.

Ví dụ 2: Giải bài toán QHTT dưới đây bằng PP đơn hình đối ngẫu:

F (x) = 3x 1 - 2x 2 -4x 3 + 10x 4 - 6x 5 + 65x 6 min x1 - x 4 +2x 5 -4x 6 = 8

x 2 + x 4 -2x 5 +6x 6 = 19

x 3 +2x 4 +3x 5 +x 6 = 21

x j 0; j= 1,6

0 0  1



với cơ sở đối ngẫu cho trước: B = (A2, A3, A4) = 1 0 1 



2



0 1 

Ta thấy cơ sở đối ngẫu chưa phải là cơ sở đơn trị, nên ta biến đổi để đưa cơ sở đỗi ngẫu B về cơ sở đơn trị như sau:

1 1 0

1 1

0 8 

27 

B 1 =  2 0 1

b = B 1 b=  2



0 1 19 = 37

j 

1 0 0

1 0

021 

 8 

	1	1	0 	1	0	0	 1	2	 4 		1	1	0	0	0	2
 	2	0	 1	0	1	0	1	 2	 6 =		2	0	1	0	7	 6  

Có thể bạn quan tâm!

• Bài Toán Quy Hoạch Tuyến Tính Đối Ngẫu
• Quan Hệ Giữa Bài Toán Gốc (P) Và Bài Toán Đỗi Ngẫu (D)
• Thuật Toán Đơn Hình Đối Ngẫu Khi Biết Cơ Sở Đối Ngẫu
• Quy hoạch tuyến tính - 13
• Quy hoạch tuyến tính - 14
• Thuật Toán “Quy O Cước Phí Các Ô Chọn”

Xem toàn bộ 152 trang tài liệu này.



4



H= B 1 A=







0

0



1 0  0 1 2 3





1

 1

0

0





1  2 

Ta có bảng đơn hình đối ngẫu dưới đây:

Hệ số

Ẩn CB	Giả PA	3	-2	-4	10	-6	65
		x1	x 2	x 3	x 4	x 5	x 6
-2	X2	27	1	1	0	0	0	2
-4	X3	37	2	0	1	0	7	-7
10	X4	-8	-1	0	0	1	-2	4
k			-23	0	0	0	-42	-1
j			-23/-1				-42/-2=min
	X2	27	1	1	0	0	0	2
	X3	9	-3/2	0	1	7/2	0	7
	X5	4	½	0	0	-1/2	1	-2
k			-2	0	0	-21	0	-82

Kết luận:

- Phương án tối ưu x*= 0, 27,9,0,4,0)

- Giá trị tối ưu: F(x*)= ( -2 *27) + (-4*9) + (-6*4) = -114

2.2.4. Thuật toán đơn hình đối ngẫu khi không biết cơ sở đối ngẫu

Xét bài toán QHTT ở dạng chuẩn tắc:

f(x) =

với hệ ràng buộc:

n

cjxjmin

j1

(1)

x a x a x ... a x b

1 1( m1) m1 1( m2) m2 1n mn 1

x a x a x ... a x b

2 2( m1) m1 2( m2) m2 2n mn 2



.............................................

(2)

x a x a x ... a x b

m m( m1) m1 m( m2) m2 mn mn m

xj  0 (j = 1, 2, . . . , n) (3)

không nhất thiết là bi 0 mà dấu của nó là tùy ý

Bài toán luôn có PA ban đầu là:

x = (x1 , . . . , xm , xm+1 , . . . , xn) = (b1 , . . . , bm, 0 , . . . , 0)

với xi là ẩn cơ bản thứ i (i = 1..m)

Giả sử x không phải là giả phương án, tức là cơ sở B = (A 1 ,A 2 ,A 3 ,..,A m ) của nó không phải là cơ sở đối ngẫu.

Xuất phát từ tình huống này, vấn đề đặt ra là làm thế nào để tìm được một cơ sở đối ngẫu, để có thể giải nó bằng thuật toán đơn hình đối ngẫu. Ý tưởng của giải pháp ở đây giống như phương pháp đơn hình hai pha: người ta lập và giải một bài toán khác mà ở đây gọi là bài toán mở rộng, để tìm một cơ sở đối ngẫu.

Để thiết lập bài toán mở rộng người ta đưa thêm vào một biến phụ x 0 với hệ số của nó trong hàm mục tiêu là c 0 = 0 và 1 ràng buộc chặt : x 0 +x m1 +…+x n =M trong đó M là 1 số dương đủ lớn (như số M trong phương pháp đơn hình mở rộng).

Khi ấy bài toán mở rộng là:

f(x) =

với hệ ràng buộc:

n

cjxjmin

j1

(1)

x 

x x

... 

x M



0 m1 m _ 2 n

1 1( m1) m1 1( m2) m2 1n n 1

x

a x a x

... a x b

x2

a2( m1) xm1 a2( m2) xm2

... a x b

(2)

2n n 2



.............................................

x a x a x ... a x b

m m( m1) m1 m( m2) m2 mn n m

xj  0 (j = 1, 2, . . . , n) (3)

Bài toán luôn có PA ban đầu là:

x = (x0, x1 , . . . , xm , xm+1 , . . . , xn) = (M, b1 , . . . , bm, 0 , . . . , 0)

Sau đó ta lập bảng đơn hình đối ngẫu mở rộng, có dạng sau:

Hệ số

Ẩn cơ bản	Giả PA		0	c1	c2	. . .	cr	. . .	cm	cm+1	. . .	cv	. . .	cn
	i	i (M)	x0	x1	x2	. . .	xr	. . .	xm	xm+1	. . .	xv	. . .	xn
0	x0	0	1	1	0	0	. . .	0	. . .	0	1	. . .	1	. . .	1
c1	x1	b1	0	0	1	0	. . .	0	. . .	0	a1(m+1)	. . .	a1v	. . .	a1n
c2	x2	b2	0	0	0	1	. . .	0	. . .	0	a2(m+1)	. . .	a2v	. . .	a2n
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
cr	xr	br	0	0	0	0	. . .	1	. . .	0	ar(m+1)	. . .	arv	. . .	arn
. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .	. . .
cm	xm	bm	0	0	0	0	. . .	0	. . .	1	am(m+1)	. . .	amv	. . .	am n
	f(x)			0	0	0	0	0	0	0	m+1	. . .	v	. . .	n

Chú ý:

- Vì x chưa phải là giả phương án nên luôn tồn tại j > 0.

- Đối với phương pháp đơn hình đỗi ngẫu, giả phương án luôn có 2 thành phần: xi = i + iM. Do đó, để cho tiện tính toán, ta có thể chia cột giả phương án thành 2 cột, một cột chứa i và một cột chứa i. Để xét dấu xi và so sánh chúng với nhau, ta sử dụng quy tắc sau:

 x < 0 nếu

0 ,

i

0

i

i 0 , _ tuú ý

i i

 x > 0 nếu

0 ,

i

0

i

i 0 , _ tuú ý

i i

, 

 x < x

nếu 

i j i j

i j , ,

_ tuú ý

i j i j

Sau khi lập bảng đơn hình đầu tiên, để có bảng đơn hình đối ngẫu thứ 2, ta biến đổi như sau:

- Ẩn đưa ra luôn là ẩn x0  hàng chứa x0 là hàng xoay.

- Giả sử q

= max k

 ẩn đưa vào là ẩn xq , cột chứa xq là cột xoay.

- Phần tử giao giữa hàng xoay và cột xoay là phần tử xoay.

Sau đó ta biến đổi bảng đơn hình tương tự như ta đã học phương pháp đơn hình.

Từ bảng đơn hình thứ 2 trở đi, ta luôn tìm được cơ sở đối ngẫu của bài toán mở rộng, tức là phương án của bảng đơn hình thứ 2 là giả phương án. Do đó bắt đầu từ bảng này, ta có thể áp dụng thuật toán đơn hình đối ngẫu để giải bài toán mở rộng. Kết thúc thuật toán ta có thể gặp các tình huống sau đây:

a) Nếu bài toán mở rộng vô nghiệm thì bài toán ban đầu cũng vô nghiệm

b) Bài toán mở rộng có phương án tối ưu là: (x* 0 , x* 1 ,x* 2 ,…,x* n ) và x 0 là một ẩn cơ bản, khi đó giá trị hàm mục tiêu không phụ thuộc M nên (x* 1 ,x* 2 ,…,x* n ) là phương án tối ưu của bài toán ban đầu.

c) Bài toán mở rộng có phương án tối ưu là (x* 0 , x* 1 ,x* 2 ,…,x* n ) và x 0 là biến phi cơ sở, khi đó các biến cơ sở sẽ phụ thuộc vào M. Có 2 khả năng sau đây:

Một là: giá trị hàm mục tiêu của bài toán mở rộng phụ thuộc M, khi đó F(x) 

khi M , suy ra bài toán ban đầu không có phương trình tối ưu.

Hai là: Giá trị tối ưu của bài toán mở rộng không phụ thuộc M, khi đó bài toán ban đầu có phương án tối ưu mà ta có thể thu được từ phương án tối ưu của bài toán mở rộng bằng cách loại bỏ x 0 và giảm dần giá trị của M cho đến khi triệt tiêu giá trị của 1 ẩn cơ bản nào đó trong bài toán mở rộng.

Ví dụ 3: Giải bài toán QHTT bằng phương pháp đơn hình đối ngẫu:

F(x)= x1  3x2 x3 x4 x5  4x6  min

x1 x4  2x5 x6 5

x2  2x5 x6  1

x3  3x4 x5  4x6  8

x j  0, j  1,6

Dễ thấy, bài toán trên đã ở dạng chuẩn với các ẩn cơ bản là x1, x2, x3 và có phương án ban đầu là: (x1, x2, x3, x4, x5, x6) = (-5, 1, 8, 0, 0 ,0) nhưng liệu có phải là giả phương án hay không? Ta xét bảng đơn hình dưới đây:

Hệ số

Ân CB	Giả PA	1	3	-1	1	1	-4
		x1	x 2	x 3	x 4	x 5	x 6
1	x1	-5	1	0	0	1	-2	-1
3	x2	1	0	1	0	0	2	-1
-1	x3	8	0	0	1	3	1	-4
k			0	0	0	-3	2	4

 Rò ràng rằng B không phải là cơ sở gốc vì có ẩn x1 = -5, cũng không phải là cơ sở

đối ngẫu vì có

6 = 4 > 0.

Ta thiết lập bài toán mở rộng bằng cách thêm vào bài toán đã cho một ràng buộc chặt sau đây:

x0 x4 x5 x6 M (M>0 đủ lớn) Ta được bài toán mở rộng như sau:

F(x) = x1  3x2 x3 x4 x5  4x6  min

x0 x4 x5 x6 M x1 x4  2x5 x6 5 x2  2x5 x6  1

x3  3x4 x5  4x6  8

x j  0, j  1,6

 Phương án xuất phát là: (x0, x1, x2, x3, x4, x5, x6) = (M, -5, 1, 8, 0, 0 ,0)

Lập bảng đơn hình đối ngẫu:

Hệ số

Ẩn CB	Giả PA		0	1	3	-1	1	1	-4
	i	i (M)	x0	x1	x 2	x 3	x 4	x 5	x 6
0	X0	0	1	1	0	0	0	1	1	1
1	X1	-5	0	0	1	0	0	1	-2	-1
3	X2	1	0	0	0	1	0	0	2	-1
-1	X3	8	0	0	0	0	1	3	1	-4
k				0	0	0	0	-3	2	4

Ở bảng đơn hình đầu tiên, ẩn đưa ra luôn luôn là ẩn x0, còn ẩn đưa vào là ẩn có ∆ > 0 lớn nhất, cụ thể là ∆6 = 4  phần tử xoay là phần tử ở ô bôi màu đen.

-4

X0	0	1	1	0	0	0	1	1	1
1	X1	-5	1	1	1	0	0	2	-1	0
3	X2	1	1	1	0	1	0	1	3	0
-1	X3	8	4	4	0	0	1	7	5	0
k				-4	0	0	0	-7	-2	0

Từ bảng đơn hình trên ta thấy, các giả phương án ≥ 0 nhưng x0 là một trong các ẩn cơ bản, các ẩn cơ bản còn lại phụ thuộc vào M. Đây là trường hợp thứ 3 của thuật toán đơn hình đối ngẫu, do đó ta phải đi tính giá trị tối ưu của bài toán mở rộng:

F(x*)= -4M + (-5+M) + 3(1+M) - (8+4M)= -10 - 4M

Khi M thì F(x*) . Bài toán mở rộng không có phương án tối ưu. Suy ra bài toán ban đầu không có phương án tối ưu.

Ví dụ 4: Giải bài toán QHTT dưới đây bằng thuật toán đơn hình đối ngẫu F(x) = 3 x1  4x2 x3  8x4  4x5 x6  min

x1 x4 x5 x6 7 x2 x4 x5  2x6  2 x3  2x4 x5 x6  8

x j  0

( j  1,6)

Dễ dàng thấy rằng phương án (x1, x2, x3, x4, x5, x6) = (-7, 2, 8, 0, 0, 0) không phải là giả phương án vì tồn tại ∆2 = 2 > 0. Do đó ta lập bài toán mở rộng như sau:

F(x) = 3 x1  4x2 x3  8x4  4x5 x6  min

x0 x4 x5 x6 M x1 x4 x5 x6 7

x2 x4 x5  2x6  2

x3  2x4 x5 x6  8

x j  0

( j  0,6)

Phương án xuất phát là: (x0, x1, x2, x3, x4, x5, x6) = (M, -7, 2, 8, 0, 0, 0)

Lập bảng đơn hình đối ngẫu