Bài Toán Quy Hoạch Tuyến Tính Ở Dạng Chuẩn Tắc

Nếu phương án x = (x1, x2, . . . , xn) có các thành phần đều ≥ 0 thì nó là phương án cực biên ứng với cơ sở B và B được gọi là cơ sở của bài toán của bài toán QHTT dạng chính tắc trên.

Các biến xj  JB được gọi là biến cơ sở, còn xj  JN là biến phi cơ sở

Định lý 1: Một phương án x* = (x1*, x2*, . . ., xn*) của bài toán QHTT dạng chính tắc là phương án cực biên (PACB) khi và chỉ khi hệ véc tơ cột Aj ứng với thành phần xj* > 0 là độc lập tuyến tính.

Xét PACB x* = (x1*, x2*, . . ., xn*). Đặt: J(x) = { j | xj* > 0}, khi đó:

 Nếu | J(x) | = m thì PA x* trên là PACB không suy biến, tức là nó có đủ m thành phần dương và B = {Aj| j  J(x)} là một cơ sở tương ứng với phương án x*.

 Nếu | J(x) | < m thì PA x* trên là PACB suy biến, tức là nó có ít hơn m thành phần dương. Khi đó, ta có thể bổ sung vào hệ véc tơ {Aj| j  J(x)} một số véc tơ cột của A sao cho thu được một hệ gồm đúng m véc tơ độc lập tuyến tính, tức là thu được một cơ sở B của A và là cơ sở tương ứng với x*.

Bài toán QHTT được gọi là không suy biến nếu mọi PACB đều không suy biến; bài toán QHTT gọi là suy biến nếu có ít nhất một PACB là suy biến.

Ví dụ 6:

Cho bài toán QHTT dạng chính tắc sau:

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

x1 - x2 = 0

xj ≥ 0 , j = 1, 2, 3

Các véc tơ nào sau đây: x = (2; 2; 0), y = (0; 0; 4), z = (1; 1; 2) là PACB của bài toán. Nếu là PACB thì hãy chỉ ra nó là PACB suy biến hay không suy biến.

Giải:

é1 1 1ù

é1ù

é 1 ù

é1ù

Ta có: A =

ê ú; A1 =

ê ú; A2 =

ê ú; A3 =

ê ú;

êë1 - 1 0úû

êë1úû

êë- 1úû

êë0úû

Dễ thấy các véc tơ x, y, z đều thỏa mãn tất cả các ràng buộc bắt buộc và ràng buộc tự nhiên nên x, y, z đều là PA của bài toán trên.

* Xét PA x = (2; 2; 0)  có 2 thành phần dương: x1 = x2 = 2 > 0

mà |A

A | = 1 1 = - 2  {A , A }_ độc lập tuyến tính

1 2 1 - 1 1 2

 PA x = (2; 2; 0) là PACB và không suy biến vì có đủ m = 2 thành phần dương.

* Xét PA y = (0; 0; 4)  có 1 thành phần dương: x3 = 4 > 0 mà véc tơ A3 khác véc tơ không nên nó độc lập tuyến tính

 PA y = (0; 0; 4) là PACB và là PACB suy biến vì có chỉ có 1 thành phần dương.

* Xét PA z = (1; 1; 2)  có 3 thành phần dương: x1 = x2 = 1, x3 = 2

mà hệ véc tơ {A1 , A2 , A3} thuộc không gian 2 chiều nên nó phụ thuộc tuyến tính.

 PA z = (1; 1; 2) không là là PACB của bài toán trên.

Hệ quả 1: (tính hữu hạn của PACB)

Số PACB của bài toán QHTT dạng chính tắc là hữu hạn.

Hệ quả 2:

Số thành phần dương trong mỗi PACB của bài toán QHTT dạng chính tắc tối đa bằng m (m là số dòng của ma trận A và r(A) = m)

Hệ quả 3:

Nếu bài toán QHTT dạng chính tắc có PA thì cũng có PACB

Định lý 2: (Sự tồn tại của PATƯ)

Nếu bài toán QHTT có PA và hàm mục tiêu bị chặn dưới (đối với bài toán f(x)  min) hoặc hàm mục tiêu bị chặn trên (đối với bài toán f(x)  max) trên tập các PA thì bài toán có PATƯ.

Định lý 3: (Sự tồn tại của PACB tối ưu)

Nếu bài toán QHTT dạng chính tắc có PATƯ thì bài toán có PACB tối ưu.

Định lý 4: (Sự tồn tại nhiều PACB tối ưu)

Nếu x0 là PATƯ của bài toán QHTT (P) và x1, x2 cũng là 2 PA khác nhau của bài toán

(P) trên thỏa mãn điều kiện x0 =  x1 + (1 – ) x2 với 0 <  < 1 thì x1, x2 là PATƯ của bài toán (P).

1.1.4. Bài toán quy hoạch tuyến tính ở dạng chuẩn tắc

Bài toán QHTT dạng chuẩn tắc là trường hợp đặc biệt của bài toán QHTT ở dạng chính tắc, trong đó ma trận hệ số các ràng buộc A có chứa một ma trận con đơn vị cấp m và các số hạng tự do không âm, tức là bi  0. Dạng chính tắc của bài toán QHTT là:

Tìm (x1 , x2 , . . . , xn) sao cho

f(x) =

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

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

2 n n 2

x2



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

... a x b

(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, n (3)

ngoài ra bi  0 , i = 1, m

Ta thấy ma trận hệ số là:

1

...

0



...

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

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

... a 



1( m1) 1n

... a

A =	0	0	1	...	0	a
	...	...	...	...	...	...

( m1) 2 n 

... a = [A1 , A2 , . . . , Am , Am+1 , . . . , An]

3( m1) 3 n 

...... ... ... 

0 0 0 ... 1 a ... a 

m( m1) mn 

Ma trận đơn vị cấp m

trong đó: Aj là các véc tơ cột của ma trận A ( các véc tơ cột A1 , A2 , . . . , Am trong ma trận A còn được gọi là các véc tơ cột đơn vị)

Đối với bài toán QHTT dạng chuẩn tắc, hệ B gồm m véc tơ cột đơn vị luôn là một cơ sở của ma trận A và là cơ sở đơn vị, các ẩn ứng với các véc tơ cột đơn vị trong ma trận A được là ẩn cơ sở và còn được gọi là các ẩn cơ bản. Ẩn cơ bản ứng với véc tơ cột đơn vị thứ i (i = 1..m) được gọi là ẩn cơ bản thứ i. Các ẩn còn lại là các ẩn không cơ bản.

Nhận xét: Với bài toán dạng chuẩn, ta luôn tìm được PACB ban đầu ứng với cơ sở đơn vị bằng cách cho các ẩn không cơ bản bằng không, các ẩn cơ bản bằng vế phải của ràng buộc chứa nó, tức là:

bj

víi j 1, m

xj =



0 víi j m 1 , n

tức là (x1 , . . . , xm , xm+1 , . . . , xn) = (b1 , . . . , bm, 0 , . . . , 0) (nhớ rằng ở đây bi  0 , i = 1, m)

Chú ý: Ở trên, để tiện cách trình bày, ta xem m ẩn đầu là ẩn cơ bản, đồng thời số thứ

tự của ẩn cơ bản cũng chính là số thứ tự của ẩn. Trong thực tế, có sự xáo trộn và ta phải nhận ra:

 Ẩn nào là ẩn cơ bản

 Ẩn cơ bản ấy là ẩn cơ bản thứ mấy

Ví dụ 7: Cho bài toán QHTT ở dạng chuẩn sau:

f(x) = 2x1 – 5x2 + x3 – x5 + x6  min

2x 2x x

20

1 4 5

3x14x24x4x60

x 2x x 3x 28

1 2 3 4

xj  0 , j = 1, 6

Ta thấy ma trận hệ số là:

2 0 0 2 1 0



1

A 3 4 0 4 0 

1 2 1 3 0 0



A1 A2 A3 A4 A5 A6

Dễ thấy: [A5 A6 A3] =

é1 0 0ù

ê ú

ê0 1 0ú

ë û

ê0 0 1ú

 Véc tơ cột đơn vị thứ nhất là A5 , thứ 2 là A6 , thứ 3 là A3

 Ẩn cơ bản thứ nhất là x5 , ẩn cơ bản thứ 2 là x6 , ẩn cơ bản thứ 3 là x3 Cho các ẩn không cơ bản: x1 = x2 = x4 = 0  x3 = 28, x5 = 20, x6 = 0.

 PACB ban đầu là (x1 , x2 , x3 , x4 , x5 , x6) = (0 , 0 , 28 , 0 , 20 , 0). Đây là PACB suy biến vì số thành phần dương nhỏ hơn m = 3.

Ví dụ 8:

Cho bài toán QHTT ở dạng chuẩn sau:

f(x) = 2x1 – 5x2 + x3 – x5 + x6  min

2x x x 20

2 4 5

3x x 4x

10

2 3 6



x 2x x 3x

28

1 2 5 6

2x x x

25



Có ma trận hệ số là:

5 6 7

xj  0 , j = 1,7

.....

.....

.....



.....

.....

.....



.....

.....

.....

A = .....



Véc tơ cột đơn vị thứ nhất, thứ 2, thứ 3 và thứ 4 lần lượt là ............................................

Ẩn cơ bản thứ nhất, thứ 2, thứ 3 và thứ 4 lần lượt là .......................................................

PACB ban đầu là (x1 , x2 , x3 , x4 , x5 , x6 , x7) = ( , , , , , , ) và là PACB suy biến hay không suy biến ? .........................................................................................

Ví dụ 9:

Cho bài toán QHTT ở dạng chính tắc sau:

f(x) = 2x1 – 5x2 + x3 – x5 + x6  min

2x x x 7

2 4 5

3x x 4x 5

2 3 6



x 2x x 3x

12

2 4 5 6

2x x x

13

5 6 7

xj  0, j = 1,7

Có ma trận hệ số là:

.....

.....

.....



.....

.....

.....



.....

.....

.....

A = .....



Có các véc tơ cột đơn vị thứ mấy ? Cụ thể là các véc tơ nào ? ........................................ Còn thiếu các véc tơ cột đơn vị thứ mấy ? .......................................................................

Có các ẩn cơ bản nào ? Thứ tự của nó thế nào ? ..............................................................

Còn thiếu các ẩn cơ bản thứ mấy ? ...................................................................................

1.2. BIẾN ĐỔI DẠNG CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH

1.2.1. Đưa dạng tổng quát về dạng chính tắc

Mọi bài toán QHTT dạng tổng quát đều có thể đưa về dạng chính tắc với 5 quy tắc mô tả dưới đây:

1) Nếu hàm mục tiêu f(x)  max thì đổi dấu hàm mục tiêu và dạng của nó, tức là ta đặt:

g(x) = - f(x)  min

2) Nếu gặp ràng buộc aij xj

j1

 bi thì ta cộng thêm vào vế trái một ẩn phụ không âm

xn+i  0 để biến về dạng phương trình:

aij xj j1

+ xn+i = bi

3) Nếu gặp ràng buộc aij xj

j1

 bi thì ta cộng thêm vào vế trái một ẩn phụ không âm

xn+i  0 với hệ số -1 để biến về dạng phương trình:

aij xj j1

- xn+i = bi

4) Nếu gặp ẩn xj  0 thì ta đổi biến: xj = - x,

với

,  0

5) Nếu gặp ẩn xj tuỳ ý về dấu, ta thay xj = x,

- x,,

với x,

 0 và

x,,  0

(nhưng xj vẫn có thể âm, dương, bằng 0 tuỳ theo x, nhỏ hơn, lớn hơn hay bằng x,, )

Chú ý:

a) Các ẩn phụ chỉ là những số giúp ta biến bất phương trình thành phương trình, chứ không đóng vai trò gì về kinh tế nên nó không ảnh hưởng đến hàm mục tiêu. Vì vậy hệ số của nó trong hàm mục tiêu bằng 0.

b) Sau khi đưa bài toán QHTT dạng tổng quát về dạng chính tắc, rồi giải bài toán này. Khi đó:

Nếu bài toán mới không có PATƯ thì bài toán xuất phát cũng không có PATƯ.

Nếu bài toán mới có PATƯ

x* (x* , x* ,..., x* , x*

,...)

thì

x*(x*,x*,...,x *)

1 2 n n1

1 2 n

thu được bằng cách bỏ đi các ẩn phụ và nếu các ẩn xi không bị ràng buộc về

j j j

dấu (tức là có dấu tuỳ ý) thì tính phần tương ứng trong x*

x* x,* x,,*

, trong đó ,*

và,,*

là 2 thành

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

f(x) = 3x1 – x2 + 2x3 - 5x4 + 2x5  min

2x x 3x 4x 5

1 3 4 5

x 3x x

2

2 3 4



x 5x x 3

1 4 5

4x x 2x 3x 8

1 2 3 5

x1 , x3  0 ; x5  0 ; x2 , x4 tuỳ ý Ta thấy, bài toán trên chưa ở dạng chính tắc do:

- Ràng buộc 1 , 2 , 4 chưa phải là phương trình

- Ẩn x5  0 và x2 , x4 tuỳ ý

Do đó để đưa bài toán QHTT trên về dạng chính tắc, ta làm như sau:

 Vì dấu của ràng buộc (1) là ≥ nên tại ràng buộc này, ta trừ đi ẩn phụ x6 ≥ 0: 2x1 – x3 + 3x4 + 4x5 – x6 = 5

 Vì dấu của ràng buộc (2) là ≤ nên tại ràng buộc này, ta cộng thêm ẩn phụ x7 ≥ 0: x2 + 3x3 - x4 + x7 = - 2

 Vì dấu của ràng buộc (4) là ≤ nên tại ràng buộc này, ta cộng thêm ẩn phụ x8 ≥ 0: 4x1 – x2 + 2x3 - 3x5 + x8 = 8

Hệ số trong hàm mục tiêu của các ẩn x6 , x7 , x8 đều có hệ số bằng 0. Ngoài ra:

 Vì ẩn x5≤ 0 nên ta thay bằng x5= – x,

với

, ≥ 0

 Vì ẩn x2, x4 là tùy ý nên ta thay bằng: x2 =

x, x,,

; x4 =

x, x,,

(với x, ,

x,, ,x, ,x,,

 0)

2 2 4 4 2

2 4 4

trong hàm mục tiêu và các ràng buộc bắt buộc. Khi đó, dạng chính tắc của bài toán trên là:

Xem tất cả 152 trang.

Ngày đăng: 16/07/2022