Các Bước Giải Bài Toán Qhtt Hai Biến Bằng Phương Pháp Hình Học

n

Đối với các ràng buộc aijx jbi

j1

chưa có ẩn cơ bản thì ta cộng vào vế trái

phương trình một ẩn giả xn+k 0 ( k =

1, r

với r là số ràng buộc cần thêm ẩn

giả). Trong hàm mục tiêu f(x)min hệ số của các ẩn giả xn+k là M ( với M là số lớn tùy ý, lớn hơn bất kỳ hằng số nào cần so sánh với nó) ; trong hàm mục tiêu f(x)max hệ số của các ẩn giả xn+k là -M.

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

• Quy hoạch toán học - Ngô Hữu Tâm - 2
• Quy Tắc Vàng Khi Lập Mô Hình Toán Học Bài Toán Thực Tế Và Khái Niệm Tối Ưu:
• Đưa Bài Toán Qhtt Dạng Chính Tắc Về Bài Toán Qhtt Dạng Chuẩn
• Định Lý 3 (Dấu Hiệu Bài Toán Có Thể Điều Chỉnh Để Được Pa Tốt Hơn)
• Quy hoạch toán học - Ngô Hữu Tâm - 7
• Quy hoạch toán học - Ngô Hữu Tâm - 8

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

Bài toán mới có được này gọi là bài toán mở rộng, ký hiệu là (PM).

Ví dụ 6Đưa bài toán sau đây về dạng chuẩn ( bài toán ( P )): (1) f(x) = 2x1+3x2+ x3+ x4min(max)



x1

(2) 





5x2

4x2

3x2

x3

5x4

6x4

8x4

25

18

28

(3) x1 0 , x2 0, x3 0, x4 0

Giải

Trước hết, ta đổi dấu hai vế của ràng buộc thứ hai. Ràng buộc thứ nhất đã có một ẩn cơ bản là x1, nên ta chỉ cần thêm ẩn giả x5vào ràng buộc thứ hai và ẩn giả x6vào ràng buộc thứ ba. Ta được bài toán mở rộng (PM) :

(1') fM (xM) = 2x1 +3x2 + x3+ x4 M(x5 +x6)min(max)

(2')

x1





5x2

4x2

x3

5x4

6x4

x5

25

18



3x2

8x4

x6 28

(3') x1 0 , x2 0, x3 0, x4 0, x5 0, x6 0

Ví dụ 7Đưa bài toán sau đây về dạng chuẩn ( bài toán ( P )):

n

(1) f(x) = c jx j

j1

min ( max)

n

(2) aijx jbi

j1

, với bi 0 ( i = 1, m )

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

Giải

Cộng vào vế trái mỗi ràng buộc ở (2) một ẩn giả ta được ta được bài tốn mở rộng

n

(PM): (1’) fM(xM) = c jx j

j1

M(xn+1 +...+xn+m)min ( max)

n

(2’) aijx j+ xn+k bi

j1

, với bi 0 ( i = 1, m , k =1, m )

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

Nhận xét:

i) Nếu x = (x1,..., xn) là phương án của bài toán ( P ) thì xM= (x1,...,xn,0,...,0) là phương án của bài toán mở rộng (PM).

ii) Nếu x*= ( x*,..., x*,0,...,0) là PATƯ của bài toán mở rộng (PM) thì

M 1 n

x*= ( x*,..., x*) là PATƯ của bài tốn ( P ). Ngược lại, nếu x*= ( x*,..., x*) là

1 n 1 n

PATƯ của bài toán ( P ) thì x*= ( x*,..., x*,0,...,0) là PATƯ của bài toán mở

M 1 n

rộng (PM). Suy ra, nếu (PM) không có PATƯ thì ( P ) có cũng không có PATƯ.

iii) Nếu (PM) có PATƯ x* = ( x* ,..., x* , x*

,..., x*

), với ít nhất một ẩn giả

M 1 n

n1

nm

x

* nk

> 0 thì ( P ) không có PA. Thật vậy, giả sử ngược lại ( P ) có PA là

M

x = (x1,..., xn). Khi đó (PM) có PA là xM= (x1,...,xn,0,...,0); hơn nữa vì M lớn

x

tùy ý và

* nk

> 0 nên fM(xM) < fM( x*

) đối với trường hợp fmin và fM(xM)

M

> fM( x*) đối với trường hợp fmax . Điều này vô lý với tính chất tối ưu của

x

.

* M

Kết luận

Bất kỳ bài toán QHTT dạng chính tắc nào cũng đưa được về bài toán QHTT dạng chuẩn.

Nếu bài toán mở rộng (PM) không có PATƯ thì bài toán ( P ) không có PATƯ.

Nếu bài toán mở rộng (PM) có PATƯ và tất cả các ẩn giả đều bằng 0 thì bỏ phần ẩn giả ta được PATƯ của bài tốn ( P ).

Nếu bài toán mở rộng (PM) có PATƯ và ít nhất một ẩn giả khác 0 thì bài toán ( P ) không có PA và do đó không có PATƯ.

Tóm lại, mọi bài toán QHTT dạng tổng quát đều có thể đưa về bài toán QHTT dạng chính tắc; mọi bài toán QHTT dạng chính tắc đều có thể đưa về bài toán QHTT dạng chuẩn. Như vậy, ta chỉ cần giải bài toán dạng chuẩn.

2.4. Các tính chất bài toán QHTT

Ta đã biết, mọi bài toán QHTT tổng quát (P) đều có thể đưa về bài toán QHTT dạng chính tắc ( P ) tương ứng; và bài toán (P) có PATƯ khi và chỉ khi bài toán ( P ) có PATƯ. Do đó, ta chỉ cần xét tính chất của bài toán QHTT dạng chính tắc. Không mất tính tổng quát, ta có thể giả thiết m ràng buộc độc lập tuyến tính và m < n. Nếu thêm giả thiết hệ phương trình ràng buộc có nghiệm thì ta có thể dùng phép khử Gauss-Jordan để biến đổi tương đương hệ đó về hệ phương trình chuẩn. Khi đó ta có các tính chất quan trọng sau đây của bài toán QHTT dạng chính tắc:

Tính chất 1: (sự tồn tại phương án)

Nếu bài toán có phương án thì có phương án cơ bản.

Tính chất 2: (sự tồn tại phương án tối ưu)

Nếu bài toán có phương án tối ưu thì có phương án cơ bản tối ưu.

Tính chất 3: (tính hữu hạn của số phương án )

Số phương án cơ bản khác nhau trong mỗi bài toán là hữu hạn.

.............................................................................................................

Bài tập

Bài 1.19 Trong các bài toán từ 1 đến 6 dưới đây: 1. (1) f(x) = 2x1+3x2+ x3+ x4max



x1

(2) 



x1

x2

x2

x2

2x3

x3

2x3

x4

2x4

x4

x5

32

16

32

(3) x1, x3 0; x2 0; x4, x5 tùy ý

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

2x1

(2) 4x

x2

2x

3x3

x

4x5

5x

17

20

1 3 4 5



2x1 4x5 x6 6

(3) xj 0 (j = 1,6 )

3. (1) f(x) = 2x1 +3x2 + x3+ x4 max

x1

(2) x

x2

2x

2x3

x x

5

15

1 2 3 4



2x1 x2 3x3 8

(3) xj 0 (j = 1,4 )

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

x1

(2) x

2x2

2x

2x3

x

7

15

2 3 4



2x1 3x3 x4 8

(3) xj 0 (j = 1,4 )

5.

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

x1

(2) x

x2

x

x3

x x

15

27

1 2 3 4



2x1 x2 x3

18

(3) xj 0 (j = 1,4 )

6.

(1) f(x) = x1 + 2x2 – x3 max

4x1

(2) x

4x 2

x

2x3

2x

6

6

1 2 3



2x1 x 2 2x3 4

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

a) Những bài toán nào đã có dạng chính tắc?

b) Những bài toán nào có dạng chuẩn? Nếu bài toán có dạng chuẩn thì hãy chỉ ra các ẩn cơ bản và thứ tự của chúng? Hãy tìm phương án cơ bản ban đầu của nó.

c) Bài toán nào chưa có dạng chuẩn hãy đưa về dạng chuẩn sau đó cho biết ẩn nào là ẩn cơ bản, ẩn cơ bản ấy là ẩn gì (ẩn chính? ẩn phụ? ẩn giả? ), thứ tự của nó thế nào? Phương án cơ bản ban đầu của bài toán dạng chuẩn này thế nào?

Đ 3. PHƯƠNG PHÁP HèNH HỌC

3.1. Một số kết quả trong hình học

Đường thẳng ax + by = c chia mặt phẳng Oxy ra thành hai miền: Một miền gồm tất cả các điểm (x,y) thỏa mãn bất phương trình ax + by > c; một miền gồm tất cả các điểm (x,y) thỏa mãn bất phương trình ax + by < c. Như vậy, mỗi bất phương trình dạng ax + by c ( hoặc ax + by c, với điều kiện a2+b20) xác định một nửa mặt phẳng kín.

Họ đường thẳng ax + by = m ( m  ) là tập hợp các đường thẳng song song với nhau, mà ta gọi là các đường mức ( tương ứng với mức m ). Nếu ta tịnh tiến một



đường thẳng trong họ ( một đường mức) theo hướng vectơ n = (a;b) thì giá trị

tương ứng của m tăng, còn theo hướng ngược lại thì giá trị tương ứng của m giảm.

3.2. Các bước giải bài toán QHTT hai biến bằng phương pháp hình học

Giải bài toán : f(x) = c1x1+ c2x2min ( max) (1)

a x a x

b , i 1, m

(2)

D: 

i1 1

i2 2 i



x10 , x20 (hoặc

a x1 b , c x2 d)

(3)

Bước 1Vẽ miền ràng buộc D trong mặt phẳng Ox1x2.

Bước 2Xác định điểm C(c1,c2); vẽ OC hoặc vectơ đơn vị





n cùng chiều OC =

(c1,c2); vẽ tùy ý một đường mức (d) n và cắt miền phương án D.

Bước 3

Để tìm phương án tối ưu đối với bài toán fmax , ta tịnh tiến đường mức (d)



theo hướng véctơ n đến khi việc tịnh tiến tiếp theo làm cho đường mức không

còn điểm chung với D nữa thì dừng. Điểm thuộc D nằm trên đường mức cuối cùng này ( đây là điểm tiếp xúc của (d) với D và có thể có nhiều điểm) là PATƯ và giá trị hàm mục tiêu tại điểm đó là giá trị tối ưu của bài toán.

Để tìm phương án tối ưu đối với bài toán fmin , ta tịnh tiến đường mức (d)



theo hướng ngược lại với véctơ n đến khi việc tịnh tiến tiếp theo làm cho

đường mức không còn điểm chung với D nữa thì dừng. Điểm thuộc D nằm trên đường mức cuối cùng này ( đây là điểm tiếp xúc của (d) với D và có thể có nhiều điểm) là PATƯ và giá trị hàm mục tiêu tại điểm đó là giá trị tối ưu của bài toán.

Nếu tịnh tiến (d) mãi mà không tìm được vị trí tiếp xúc của (d) với D thì kết luận bài toán không có PATƯ và hàm mục tiêu không bị chặn trên miền PA (f-, đối với bài toán min; f +, đối với bài toán max).

Ví dụ 1Giải bài toán QHTT sau đây bằng phương pháp hình học. f(x) = 2x1-2x2min ( max)

D:



3x1 2x2 12

- 2x1 x2 2

x10 , x20,

x2 3

Giải



Miền phương án D, đường mức (d), điểm C và vectơ n được xác định như hình vẽ.



 Trường hợp fmax: Tịnh tiến (d) theo hướng n ta được dmax và từ đó tính được xmax = (4;0) , fmax = 8.



 Trường hợp fmin: Tịnh tiến (d) theo hướng ngược lại với đó tính được xmin = ( 1;3) , fmin = -5.

2

n ta được dmin và từ

Ví dụ 2Giải bài toán QHTT sau đây bằng phương pháp hình học.

f(x) = 4x1 +2x2 min ( max)

2x1 x2 2

x1 2x2 4

D: - 2x1 x2 2



x10 , x20

Giải



Miền phương án D, đường mức (d), điểm C và vectơ n được xác định như hình vẽ.

 Trường hợp fmin: Tịnh tiến (d) theo hướng ngược lại với



n ta được dmin và từ

đó tính được xmin = (t; 2-2t) với 0 t 1, fmin = 4. Tức là, PATƯ ứng với trường hợp fmin là cả đoạn thẳng AB.

 Trường hợp fmax: Tịnh tiến (d) theo hướng



n ta thấy (d) và D không có điểm

tiếp xúc. Tức là, hàm mục tiêu không bị chặn trên và bài toán không có phương án tối ưu.

Ví dụ 3Giải bài toán QHTT sau đây bằng phương pháp hình học. f(x) = 50x1- 50x2min (max)

D:



4x1  3x2  18

 - x1 x2 1

x1 0 , x 2 0,



x1  2

Giải



Miền phương án D, véc tơ n  (1;1) OC  (50;50) , đường mức (d ) như hình vẽ.



Trường hợp fmin: Tịnh tiến (d) theo hướng ngược lại với n ta được dmin và

từ đó tính được X min  (0;6) , f min f (0,6) 300 .

Trường hợp fmax: Tịnh tiến (d) theo hướng



n ta được dmax và từ đó tính

được

X max

là tập hợp tất cả các điểm thuộc đoạn AB như hình vẽ. Tính được

X max  (1 t;t)

với

0 t  1 và

f max 

f (1 t, t)  50(1 t)  50t  50 .

Bài tập

Giải các bài tập toán QHTT sau đây bằng phương pháp hình học.

Bài 1.20f(x) = x1 + x2 min (max)

3x1

3x

2x2 6

x 3

1 2



x1 3

Bài 1.21f(x) = x1 + 2x2 min (max)

x1

x

8x2

x

10

1

1 2



x1 5x2

3x110x2

5

30

Bài 1.22f(x) = -2x1 + x2 min (max)

x1 x2 1

x1 2x2 4



2x1

x2 6



4x1 x2 20

x10 ; x20

Xem tất cả 192 trang.