Đưa Dạng Chính Tắc Về Dạng Chuẩn Tắc (Bài Toán M)

f(x) = 3x1 – (x’ – x” ) + 2x - 5(x’ – x” ) - 2x’

 min

2 2 3 4 4 5

4 4 5 6

2x1 - x3 + 3(x’ – x” ) - 4x’ - x = 5

(x’ – x” ) + 3x - (x’ – x” ) + x

= -2

2 2 3 4 4 7

4 4 5

x1 - 5(x’ – x” ) + x’ = 3

4x1 - (x’ – x” ) + 3x + 3x’ + x = 8

2 2 3 5 8

x1, x’ , x” , x , x’ , x” , x’ ≥ 0

2 2 3 4 4 5

Ví dụ 2: Đưa bài toán sau về dạng chính tắc:

f(x) = - 2x1 + x2 + x4 max x1 + x2 - x3 ≤ 15 x1 + x2 + x3 + x4 = 27

2x1 - x2 - x3 ≤ 18

x1 ≥ 0 , x2 ≤ 0 , x3 tuỳ ý , x4 ≤ 0

Giải:

3 3 4 4

Đặt x2 = - x’2 ; x3 = x’ – x” ; x = - x’ Bài toán ở dạng chính tắc là:

g(x) = - f(x) = - (- 2x1 - x’2 - x’4 ) min

x1	-	x’2 - (x’ – x” ) 3 3		+ x5	= 15
x1	-	x’2 + (x’ – x” ) 3 3	- x’4		= 27
2x1	+	x’2 - (x’ – x” ) 3 3		+ x6	=18

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

• Quy hoạch tuyến tính - 1
• Quy hoạch tuyến tính - 2
• Bài Toán Quy Hoạch Tuyến Tính Ở Dạng Chuẩn Tắc
• Quy hoạch tuyến tính - 5
• Giải Bài Toán Qhtt Ở Dạng Chính Tắc (Phương Pháp Đánh Thuế)
• Hiện Tượng Xoay Vòng Và Cách Khắc Phục

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

x1, x’ , x’ , x’’ , x’ , x , x ≥ 0

2 3 3 4 5 6

trong đó: x5, x6 là ẩn phụ.

Ví dụ 3: Đưa bài toán sau về dạng chính tắc:

f(x) = x1 + 2x2 + 3x3 + x4 min

x1	- 2x2	+ 3x3		≤ 15
2x1	+ x2	+ 5x3		= 20
x1	+ 2x2	+ x3	+ x4	= 10

x1 , x3 ≥ 0 , x2 ≤ 0 , x4 tuỳ ý

Giải:

4 4

Đặt x2 = - x’2 ; x4 = x’ – x” Bài toán ở dạng chính tắc là:

4 4

f(x) = x1 - 2x’2 + 3x3 + x’ – x” min

x1 + 2x’2 + 3x3 + x5 = 15

4 4

2x1 - x’2 + 5x3 = 20 x1 - 2x’2 + x3 + x’ – x” = 10

x1, x’ , x , x’ , x’’ , x ≥ 0; x

là ẩn phụ

2 3 4 4 5 5

1.2.2. Đưa dạng chính tắc về dạng chuẩn tắc (bài toán M)

Trước hết, nếu trong bài toán QHTT dạng chính tắc có một số hạng tự do bi nào đó âm, ta chỉ cần đổi dấu 2 vế để được bi  0

Ví dụ: 2x1 – 3x2 + 5x3 = -8  - 2x1 + 3x2 - 5x3 = 8

Vì vậy, từ đây ta có thể giả thiết bài toán chính tắc ta đang xét có bi  0 ( i = 1, m ) Xét bài toán QHTT ở dạng chính tắc với bi  0

f(x) =

n

cjxjmin

j1

(1)

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

11 1 12 2 1n n 1

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

21 1 22 2 2 n n 2



(2)

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

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

m1 1 m 2 2 mn n m

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

Ta thêm vào mỗi phương trình một ẩn giả không âm xn + i  0 với hệ số +1 ; còn trong hàm mục tiêu, các ẩn giả có hệ số M (M là một số vô cùng lớn, lớn hơn số nào cần phải so sánh). Ta được bài toán mới gọi là bài toán mở rộng hay bài toán M của bài toán xuất phát:

f(x) =

n

cjxjMxn1 Mxn2 ... Mxnm min

j1

(1)

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

11 1 12 2 1n n n1 1

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

21 1 22 2 2 n n n2 2



(2)

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

a x

a x

... a x

x b

m1 1 m 2 2 mn n n m m

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

Ta thấy bài toán mở rộng đã có dạng chuẩn với ẩn cơ bản thứ i là xn+i (i = 1, m ) chính là các ẩn giả.

Chú ý:

1) Ta cần phân biệt ẩn phụ và ẩn giả với 3 ý sau:

- Ẩn phụ để đưa bài toán tổng quát về dạng chính tắc, còn ẩn giả để đưa dạng chính tắc về dạng chuẩn.

- Trong hàm mục tiêu, ẩn giả có hệ số bằng M, còn ẩn phụ có hệ số bằng 0

- Ẩn phụ là con số thực sự giúp ta biến bất phương trình về phương trình, còn ẩn giả thì 2 vế đã bằng nhau mà vẫn cộng thêm là việc làm “giả tạo” cốt để tạo ra véc tơ cột đơn vị mà thôi.

2) Nếu bài QHTT dạng chính tắc có bi  0 (i = 1..m) đã có sẵn một số véc tơ cột đơn vị trong ma trận hệ số A, ta chỉ cần thêm ẩn giả vào những phương trình cần thiết đủ để tạo ra bài toán mở rộng ở dạng chuẩn (cụ thể, nếu thiếu véc tơ cột đơn vị thứ k nào thì ta thêm ẩn giả vào phương trình thứ k)

Ví dụ 4: Chuyển bài toán QHTT sau về bài toán mở rộng:

f(x) = -2x1 + x2 + x4 min

x1 + x2 - x3 = 15 x1 + x2 + x3 + x4 = 27

2x1 - x2 - x3 ≤ 18 xj ≥ 0 (j = 1, 2, 3, 4)

Ở ràng buộc (3) có dấu “≤” nên ta cộng thêm ẩn phụ x5 vào ràng buộc này ta được dạng chính tắc của bài toán trên là:

f(x) = - 2x1 + x2 + x4 min

x1 + x2 - x3 = 15

x1 + x2 + x3 + x4 = 27 2x1 - x2 - x3 + x5 = 18

xj ≥ 0 (j = 1, 2, . . . , 5)

Từ bài toán dạng chính tắc này ta thấy, mới chỉ có ẩn cơ bản thứ 2 và thứ 3, còn thiếu ẩn cơ bản thứ nhất nên tại ràng buộc (1) ta cộng thêm ẩn giả x6 với hệ số +1 và đồng thời trong hàm mục tiêu ta cũng cộng thêm ẩn giả x6 vào với hệ số là M ( M là số dương vô cùng lớn), ta được bài toán mở rộng của bài toán trên như sau:

f(x) = - 2x1 + x2 + x4 + M x6 min x1 + x2 - x3 + x6 = 15 x1 + x2 + x3 + x4 = 27 2x1 - x2 - x3 + x5 = 18

xj ≥ 0 (j = 1, 2, . . . , 6); x5 là ẩn phụ, x6 là ẩn giả.

Ví dụ 5: Chuyển bài toán QHTT sau về bài toán mở rộng: f(x) = 3x1 + x2 - 3x3 max

x1 + 2x2 - x3 = 2

- 10x2 + 5x3 = 5

- 3x2 + 2x3 = 4

xj ≥ 0 (j = 1, 2, 3) Chuyển về dạng chuẩn (bài toán mở rộng):

g(x) = - f(x) = - 3x1 - x2 + 3x3 + Mx4 + Mx5 min

x1 + 2x2 - x3 = 2

- 10x2 + 5x3 + x4 = 5

- 3x2 + 2x3 + x5 = 4

xj ≥ 0; x4, x5 ẩn giả (j = 1, 2, . . . , 5)

Ví dụ 6: Chuyển bài toán QHTT sau về bài toán mở rộng: f(x) = x1 - 2x2 - 3x3 + x4 max

x1 - 2x2 + 3x3 = 15

2x1 + x2 + 5x3 ≥ 20 x1 + 2x2 + x3 + x4 = 10

xj ≥ 0 (j = 1, 2, 3, 4)

Chuyển về dạng chính tắc:

g(x) = - f(x) = - x1 + 2x2 + 3x3 - x4 min

x1 - 2x2 + 3x3 = 15 2x1 + x2 + 5x3 - x5 = 20 x1 + 2x2 + x3 + x4 = 10

xj ≥ 0 (j = 1, 2, . . . , 5)

Chuyển về dạng chuẩn (bài toán mở rộng):

g(x) = - x1 + 2x2 + 3x3 - x4 + Mx6 + Mx7 min

x1 - 2x2 + 3x3 + x6 = 15 2x1 + x2 + 5x3 - x5 + x7 = 20 x1 + 2x2 + x3 + x4 = 10

xj ≥ 0 ; x5 ẩn phụ; x6, x7 ẩn giả (j = 1, 2, . . . , 7)

Ví dụ 7: Chuyển bài toán QHTT sau về bài toán mở rộng: f(x) = 2x1 + x2 - x3 min

- 4x1 - x2 + 2x3 ≥ 12

- 2x1 + 2x2 - x3 ≤ 10 2 x1 - 4x2 - x3 = 46

xj ≥ 0 (j = 1, 2, 3) Chuyển về dạng chính tắc:

f(x) = 2x1 + x2 - x3 min

- 4x1 - x2 + 2x3 - x4 = 12

- 2x1 + 2x2 - x3 + x5 = 10 2 x1 - 4x2 - x3 = 46

xj ≥ 0; x4, x5 ẩn phụ (j = 1, 2, 3, 4, 5) Chuyển về dạng chuẩn (bài toán mở rộng):

f(x) = 2x1 + x2 - x3 + Mx6 + Mx7 min

- 4x1 - x2 + 2x3 - x4 + x6 = 12

- 2x1 + 2x2 - x3 + x5 = 10

2 x1 - 4x2 - x3 + x7 = 46

xj ≥ 0; x4, x5 ẩn phụ; x6, x7 ẩn giả (j = 1, 2, . . . , 7)

1.3. PHƯƠNG PHÁP ĐƠN HÌNH

Nội dung chính của phương pháp đơn hình gồm các bước sau:

1) Đưa bài toán QHTT dạng tổng quát về dạng chuẩn (bài toán mở rộng)

2) Tìm phương án cực biên ban đầu

3) Đánh giá phương án cực biên đó

- Nếu phương án tối ưu thì việc giải bài toán kết thúc

- Nếu phương án chưa tối ưu thì chuyển sang bước 4

4) Xây dựng phương án mới tốt hơn phương án đang có, sau đó quay lại bước 3 Thuật toán đơn hình được thể hiện bởi sơ đồ sau đây:

Bắt đầu

Chuẩn tắc hoá bài toán

Tối ưu ?

S

Đ

Kết thúc

Xây dựng PACB ban đầu

Xây dựng PACB mới tốt

1.3.1. Giải bài toán QHTT ở dạng chuẩn

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

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 n 1

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

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



(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)

ngoài ra bi  0 , (i = 1, 2, . . . , m) Bài toán luôn có PACB ban đầu là:

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

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

Thuật toán đơn hình giải bài toán QHTT dạng chuẩn gồm 3 bước sau:

Bước 1: Lập bảng đơn hình ban đầu:

Hệ số

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

m

trong đó: f0= cibi

i1

= Cột hệ số nhân với Cột phương án