Giáo trình Toán kinh tế (Phần 1)

Nội dung text: Giáo trình Toán kinh tế (Phần 1)

1. Định nghĩa 1.4. Nếu bài toán QHTT có phƣơng án tối ƣu thì bài toán đƣợc gọi là giải được (hay bài toán có lời giải) và phƣơng án tối ƣu của bài toán còn gọi là lời giải của bài toán. Nếu bài toán QHTT không có phƣơng án tối ƣu thì bài toán đƣợc gọi là không giải được (hay bài toán không có lời giải). Định nghĩa 1.5. Nếu phƣơng án X(x1, x2, , xn) của một bài toán QHTT làm thỏa n mãn aij x j b i thì phƣơng án X đƣợc gọi là thỏa mãn chặt ràng buộc i tƣơng ứng j1 (1.2), hoặc (1.3) hoặc (1.4). Nếu phƣơng án X(x1, x2, , xn) có xj = 0 thì phƣơng án X đƣợc gọi là thỏa mãn chặt ràng buộc về dấu tƣơng ứng (nếu có ràng buộc loại xj 0 hoặc xj 0). n n Nếu phƣơng án X(x1, x2, , xn) thỏa mãn aij x j b i (hoặc aij x j b i hoặc j1 j1 xj > 0 hoặc xj < 0) thì phƣơng án X đƣợc gọi là thỏa mãn lỏng ràng buộc tƣơng ứng (nếu có). 2.2. Bài toán quy hoạch tuyến tính dạng chính tắc và chuẩn tắc 2.2.1. Bài toán quy hoạch tuyến tính dạng chính tắc Bài toán QHTT chính tắc có dạng: Tìm X(x1, x2, , xn) sao cho n f (X) c1 x 1 c 2 x 2 c n x n c j x j min (1.6) j1 n aij x j b i ,i 1,m (1.7) với điều kiện j1 xj 0, j 1,n (1.8) a11 a 12 a 1n a a a Nếu ký hiệu A = 21 22 2n là ma trận cấp m n, gọi là ma trận am1 a m2 a mn ràng buộc của bài toán; - 7 -
2. x1 b1 0 x b 0 X = 2 ; B = 2 ; O = x b n n1 m m1 0 n1 Khi đó bài toán QHTT chính tắc (1.6) – (1.8) viết đƣợc dƣới dạng ma trận sau: f(X) = CX min AX B với điều kiện X0 a1j a Nếu ký hiệu: A = 2j là véctơ cột thứ j (j =1,n ) của ma trận A. Khi đó bài j a mj toán QHTT chính tắc (1.6) – (1.8) viết đƣợc dƣới dạng véctơ sau đây: n f (X) cjj x min j1 n xjj A B với điều kiện j1 xj 0, j 1,n Ma trận A A B đƣợc gọi là ma trận bổ sung (hay còn gọi là ma trận mở rộng) của bài toán QHTT dạng chính tắc (1.6) – (1.8). 2.2.2. Bài toán quy hoạch tuyến tính dạng chuẩn tắc. Bài toán QHTT chuẩn tắc có dạng: Tìm X(x1, x2, , xn) sao cho n f (X) c1 x 1 c 2 x 2 c n x n c j x j min (1.9) j1 n aij x j b i ,i 1,m (1.10) với điều kiện j1 xj 0, j 1,n (1.11) - 8 -
3. Bài toán QHTT dạng chuẩn tắc (1.9) – (1.11) viết đƣợc dƣới dạng ma trận nhƣ sau: f(X) = CX min AX B với điều kiện X0 Bài toán QHTT dạng chuẩn tắc (1.9) – (1.11) viết đƣợc dƣới dạng véctơ sau đây: n f (X) cjj x min j1 n xjj A B với điều kiện j1 xj 0, j 1,n 2.3. Chuyển đổi dạng bài toán quy hoạch tuyến tính Bằng cách thực hiện các phép biến đổi nêu dƣới đây, ta có thể chuyển bài toán QHTT bất kỳ về bài toán QHTT chính tắc, chuẩn tắc. n a) Nếu ràng buộc có dạng aij x j b i thì ta thêm biến phụ xn + i 0 để có j1 n aij x j x n i b i . j1 n b) Nếu ràng buộc có dạng aij x j b i thì ta thêm biến phụ xn + i 0 để có j1 n aij x j x n i b i . j1 c) Nếu có ẩn xj nào đó không có ràng buộc về dấu thì ta thay xj bởi hai biến phụ không âm xjj 0 và x 0 sao cho: xj = x j x j . - 9 -
4. n d) Mỗi ràng buộc đẳng thức aij x j b i có thể thay bằng 2 ràng buộc bất đẳng j1 n n thức aij x j b i và aij x j b i . j1 j1 n n e) Một ràng buộc aij x j b i có thể viết lại thành aij x j b i hoặc ngƣợc lại. j1 j1 f) Bài toán tìm cực đạt f max có thể đƣa về bài toán tìm cực tiểu g = -f min. Nhận xét: i) Khi đƣa biến phụ xn + i vào thì hệ số của nó trong hàm mục tiêu f(X) là Cn + i = 0. ii) Khi đƣa biến phụ x j , x j vào thì hệ số của nó trong hàm mục f(X) tƣơng ứng là Cj = Cj , Cj = - Cj. iii) Mọi bài toán QHTT đều đƣa đƣợc về dạng chính tắc và việc giải bài toán QHTT đã cho tƣơng đƣơng với việc giải bài toán QHTT chính tắc tƣơng ứng với nó, theo nghĩa là nếu bài toán dạng chính tắc có PATƢ thì từ đó suy ra đƣợc PATƢ của bài toán ban đầu, còn nếu bài toán chính tắc không có PATƢ thì bài toán ban đầu cũng không có PATƢ. Nói cách khác: Bài toán ban đầu có PATƢ khi và chỉ khi bài toán dạng chính tắc tƣơng ứng với nó có PATƢ. Nhƣ vậy, ta chỉ cần tìm cách giải bài toán QHTT chính tắc. Ví dụ 1.1: Đƣa bài toán QHTT sau về dạng chính tắc, dạng chuẩn tắc. f(X) = 2x1 – x2 min x1 2x 2 x 3 2 2x 2x x 3 với điều kiện 1 2 3 x1 x 2 x 3 4 x23 0;x 0 Giải: * Dạng chính tắc: Bằng cách thay x1 = x4 – x5 với x4, x5 0 và thêm hai biến phụ x6 , x7 0, ta đi đến bài toán: f(X) = – x2 + 2x4 – 2x5 min - 10 -
5. 2x2 x 3 x 4 x 5 x 6 2 2x2 x 3 2x 4 2x 5 x 7 3 với điều kiện x2 x 3 x 4 x 5 4 xj 0; j 2,7 * Dạng chuẩn tắc: Bằng cách thay x1 = x4 – x5 với x4, x5 0, đổi dấu hai vế bất đẳng thức đầu và thay bất đẳng thức cuối bằng hai bất đẳng thức , ta đi đến bài toán: f(X) = – x2 + 2x4 – 2x5 min 2x2 x 3 x 4 x 5 2 2x2 x 3 2x 4 2x 5 3 với điều kiện x2 x 3 x 4 x 5 4 x2 x 3 x 4 x 5 4 xj 0, j 2,5 3. THUẬT TOÁN ĐỒ THỊ GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH HAI BIẾN 3.1. Nhận xét Trong mặt phẳng ¡ 2 với hệ trục tọa độ vuông góc xOy ta có: * Phƣơng trình ax + by = c, biểu diễn một đƣờng thẳng vuông góc với véctơ pháp tuyến n (a, b). * Các điểm (x, y) thỏa mãn ax + by c nằm trên nửa mặt phẳng giới hạn bởi đƣờng thẳng ax + by = c. * Phƣơng trình ax + by = f, khi f thay đổi sẽ cho ta họ đƣờng thẳng song song với véctơ chỉ phƣơng v( b,a) . Giá trị f càng lớn khi dịch chuyển các đƣờng của họ theo hƣớng (a, b). Vì vậy hình ảnh hình học của bài toán QHTT trong ¡ 2 đƣợc mô tả theo thuật toán đồ thị nhƣ sau. 3.2. Thuật toán đồ thị giải bài toán quy hoạch tuyến tính Xét bài toán QHTT với hai biến số - 11 -
6. min(max){f(X) = c1x + c2y: X = (x, y) }, trong đó là tập phƣơng án của bài toán. Bước 1. Biểu diễn các điều kiện buộc của lên mặt phẳng tọa độ vuông góc xOy. Tìm tập phƣơng án . Bước 2. Biểu diễn phƣơng của hàm mục tiêu c1x + c2y = f, bằng cách cho f một giá trị f0 nào đó. Đƣờng thẳng c1x + c2y = f0 đƣợc gọi là đường mức. Bước 3. Tịnh tiến song song đƣờng mức trên tập phƣơng án để tìm phƣơng án tối ƣu. Chú ý: Thay vì xác định véctơ n (c1, c2) để tìm hƣớng tăng, ta có thể kiểm tra giá trị hàm mục tiêu ở gốc tọa độ O(0, 0). Ví dụ 1.2: Giải bài toán QHTT min{f(X) = - 2x + y} x 2y 2 2x 3y 6 với điều kiện 4x 5y 20 x,y 0 Giải: Hình 1.1 Biểu diễn điều kiện buộc của bài toán lên mặt phẳng tọa độ xOy ta đƣợc tập phƣơng án là hình ngũ giác ABCDE (Hình 1.1). Chọn f0 = 1, ta có đƣờng mức -2x + y = 1 (d). Chọn D(2, 0) f(D) = - 4 < f0. Suy ra dịch chuyển đƣờng mức (d) theo chiều mũi tên thì giá trị của hàm là - 12 -
7. 45 11 giảm. Do đó tịnh tiến (d) theo chiều mũi tên, ta có PATƢ là A( , ) và fmin = 11 8 599 . 88 Ví dụ 1.3: Giải bài toán QHTT min{f(X) = x - y} 2x y 4 với điều kiện x 2y 2 x,y 0 Giải: Hình 1.2 Biểu diễn các điều kiện buộc của bài toán lên mặt phẳng xOy ta đƣợc tập phƣơng án (Hình 1.2). Chọn f0 = 1, ta có đƣờng mức (d): x – y = 1. Chọn C(1, 1) suy ra f(C) = 0 < f0 = 1. Vì vậy dịch chuyển (d) theo chiều mũi tên thì giá trị của hàm mục tiêu f(X) giảm. Ta thấy f(X) không bị chặn trên tập phƣơng án nên bài toán không có phƣơng án tối ƣu. Bạn đọc có thể kiểm tra thêm với ví dụ 2, nhƣng chỉ xét với hàm mục tiêu f(X) = -2x + y và max( -2x + y) thì phƣơng án tối ƣu lúc này là điểm A(4, 0), f(A) = 4. - 13 -
8. Cũng cách làm nhƣ vậy với ví dụ 2, nhƣng thêm điều kiện x – 2y 5 thì tập phƣơng án rỗng. Bài toán không có phƣơng án tối ƣu. Ở ví dụ 1, nếu thay f(X) = 2x – 3y thì bài toán có vô số phƣơng án tối ƣu. Nhận xét: i)Tập PA của bài toán QHTT là một miền lồi bị chặn hoặc không bị chặn. ii) Bài toán có thể có PATƢ là một đỉnh hoặc có vô số PATƢ. iii) Bài toán có thể không có PATƢ nếu hàm mục tiêu không bị chặn trên tập PA hoặc tập PA rỗng. 4. MỘT SỐ YẾU TỐ HÌNH HỌC TRONG KHÔNG GIAN ¡ n 4.1. Tập hợp lồi 4.1.1. Tổ hợp lồi. Cho hệ hữu hạn điểm X1, X2, , Xk của không gian véctơ . k k Điểm X = iiX trong đó i 0 (i = 1,k ), i 1 đƣợc gọi là tổ hợp lồi i1 i1 của hệ điểm đã cho. 4.1.2. Đoạn thẳng. Cho X1, X2 . Tập hợp các điểm là tổ hợp lồi của hai điểm đã cho gọi là đoạn thẳng nối hai điểm ấy. n Tập hợp XX1 2 X X X(1 1 )X;0 2 1 gọi là đoạn thẳng nối hai điểm X1, X2. 4.1.3. Tập hợp lồi. Tập M đƣợc gọi là tập hợp lồi nếu mọi đoạn thẳng nối hai điểm của tập hợp thì nằm trọn trong tập hợp đó. Nghĩa là: Với mọi X1, X2 M, X X12 (1 )X ;0 1thì X M. 4.1.4. Điểm cực biên (Đỉnh). Điểm X thuộc tập lồi M đƣợc gọi là điểm cực biên nếu X không thể biểu diễn thành tổ hợp lồi thực sự của hai điểm khác nhau thuộc M. Nghĩa là không tồn tại X1, X2 M (X1 X2) sao cho: X X12 (1 )X ;0 1. 4.1.5. Siêu phẳng. Cho t , aΡ , Khi đó tập hợp các điểm X thỏa mãn điều kiện T,X =a gọi là siêu phẳng thuộc không gian . - 14 -
9. Tập {XΡ n : T,X £ a } gọi là nửa không gian đóng giới hạn bởi siêu phẳng T,X =a. 4.2. Tính chất của tập hợp lồi 4.2.1. Giao của các tập lồi là tập lồi 4.2.2. Cho D1 và D2 là các tập lồi. Khi đó hiệu D = D1 - D2 và tổng D = D1 + D2 là các tập hợp lồi (hiệu và tổng theo nghĩa hiệu và tổng các véc tơ tƣơng ứng thuộc tập hợp). 4.2.3. Tập M lồi khi và chỉ khi tổ hợp lồi của hữu hạn điểm thuộc M cũng thuộc M. ïïìün 4.2.4. Tập M=íýïï X Ρ n : ax £ b,i = 1,2, ,m là tập lồi. ïïå ij j i îþïïj1= Trong trƣờng hợp này, tập M đƣợc gọi là tập lồi đa diện thuộc không gian ¡ n . Nhƣ vậy, tập lồi đa diện là giao của hữu hạn các nửa không gian đóng. 4.2.5. Đa diện lồi M có hữu hạn điểm cực biên X1, X2, , Xr và mọi điểm thuộc đa diện lồi là tổ hợp lồi của các điểm cực biên, nghĩa là mọi XM thì rr Xi X i , i 0, i 1. i 1 i 1 5. TÍNH CHẤT CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 5.1. Các giả thiết ban đầu Không mất tính tổng quát, ta giả thiết: Xét bài toán dạng chính tắc n f (X) c1 x 1 c 2 x 2 c n x n c j x j min (1.6) j1 n aij x j b i ,i 1,m (1.7) với điều kiện j1 xj 0, j 1,n (1.8) * Hệ phƣơng trình (1.7) có đúng m phƣơng trình độc lập tuyến tính. * bi 0, i 1,m . - 15 -
10. * m < n (vì trong trƣờng hợp m n thì tập phƣơng án có nhiều nhất một điểm, do vậy việc xét phƣơng án tối ƣu là tầm thƣờng). Ký hiệu: là tập các phương án của bài toán (1.6) – (1.8). Với bài toán đã cho, để tiện cho việc chứng minh sau này chúng ta nhớ rằng: Phƣơng án X* là phƣơng án tối ƣu khi và chỉ khi f(X*) f(X), X . 5.2. Các tính chất cơ bản của bài toán quy hoạch tuyến tính Định lý 1.1. Tập phương án của bài toán QHTT là tập lồi đa diện. Định nghĩa 1.6 - Điểm cực biên của tập lồi các phƣơng án gọi là phương án cực biên (PACB). - Tập lồi đa diện M đƣợc gọi là bị chặn nếu với mọi X=Î (xj ) M , tồn tại số thực L sao cho xj L, j 1,n . - Tập lồi đa diện khác rỗng và bị chặn đƣợc gọi là đa diện lồi. Định lý 1.2. Phương án X của bài toán QHTT tổng quát là phương án cực biên khi và chỉ khi X thỏa mãn chặt n ràng buộc độc lập tuyến tính. Phƣơng án cực biên thỏa mãn chặt đúng n ràng buộc gọi là phương án cực biên không suy biến. Phƣơng án cực biên thỏa mãn chặt hơn n ràng buộc gọi là phương án cực biên suy biến. Chú ý: i) Số n trong định nghĩa là số biến số của bài toán. ii) Nếu phƣơng án X thỏa mãn ít hơn n ràng buộc chặt (hoặc nếu nó thỏa mãn không ít hơn n ràng buộc chặt nhƣng không có hệ n ràng buộc nào độc lập tuyến tính) thì phƣơng án X không phải là phƣơng án cực biên (hay gọi là phƣơng án không cực biên). Định nghĩa 1.7. Nếu một phƣơng án của một bài toán QHTT vừa là PACB, vừa là PATƢ thì phƣơng án đó đƣợc gọi là phương án cực biên tối ưu. Ví dụ 1.4: Cho bài toán QHTT - 16 -
11. f(X) = 8x1 + 2x2 + 9x3 – x4 min 3x1 2x 3 x 4 14 3x 4x 2x 8 với điều kiện 1 2 4 x1 7x 2 x 3 3x 4 7 x1 0;x 2 0;x 3 0 Xét xem véctơ X0(0, - 1, 6, - 2) và X1(4, 0, 0, -2), véctơ nào là phƣơng án cực biên của bài toán? Giải: ▪ Xét X0(0, -1, 6, -2) + Thay X0 vào hệ ràng buộc của bài toán ta thấy thỏa mãn, do đó X0 là một phƣơng án của bài toán. + Mặt khác X0 thỏa mãn 4 ràng buộc chặt là 3x1 2x 3 x 4 14 3x 4x 2x 8 1 2 4 x1 7x 2 x 3 3x 4 7 x01 Số ràng buộc chặt đúng bằng số biến của bài toán và định thức của ma trận các hệ số ứng với hệ 4 ràng buộc chặt là: 3 0 2 1 0 2 1 1 4 0 2 A = 4 0 2 0 1 7 1 3 7 1 3 1 0 0 0 Suy ra hệ 4 ràng buộc chặt là hệ ràng buộc chặt phụ thuộc tuyến tính, do đó phƣơng án X0 không phải là phƣơng án cực biên. ▪ Xét X1(4, 0, 0, -2) - Thay X1 vào hệ ràng buộc của bài toán ta đƣợc - 17 -
12. 3x1 2x 3 x 4 14 3x1 4x 2 2x 4 8 x 7x x 3x 10 7 1 2 3 4 x1 4 0 x2 0 x3 0 Nhƣ vậy X1 là phƣơng án của bài toán. Phƣơng án X1 làm thỏa mãn 4 ràng buộc chặt. Số ràng buộc bằng số biến của bài toán và định thức của ma trận các hệ số ứng với hệ 4 ràng buộc chặt trên là: 3 0 2 1 3 0 1 1 4 0 2 3 1 B = 1 4 2 5 0 0 1 0 0 1 2 0 1 0 0 0 1 0 Suy ra hệ 4 ràng buộc chặt là hệ ràng buộc chặt độc lập tuyến tính. Do đó phƣơng án X1 là phƣơng án cực biên. Định lý 1.3. Nếu tập phương án của bài toán QHTT tổng quát khác rỗng và bị chặn thì nó là đa diện lồi. Định lý 1.4. Nếu tập phương án của bài toán QHTT là đa diện lồi thì tồn tại phương án cực biên tối ưu. Chứng minh: Theo giả thiết là đa diện lồi, suy ra tồn tại hữu hạn các phƣơng án cực biên (điểm cực biên) X1, X2, , Xr và với mọi X thuộc ta có: rr Xi X i , i 0, i 1. i 1 i 1 Đặt f(X*) = min{f(X1), f(X2), , f(Xr)}, ta có: r r r r f(X)= f( iiX ) = iif (X ) if (X*) = f (X*)i f (X*) . i1 i1 i1 i1 Suy ra f(X) f(X*), X . Vậy X* là phƣơng án cực biên tối ƣu.■ - 18 -
13. Định lý 1.5. Nếu bài toán quy hoạch tuyến tính có phương án tối ưu thì có ít nhất một phương án cực biên tối ưu. Nhận xét: Từ định lý 1.4 và 1.5 cho phép chúng ta tìm phƣơng án tối ƣu của bài toán quy hoạch tuyến tính trên tập các phƣơng án cực biên. Sau này, chúng ta thấy thêm rằng số phƣơng án cực biên là hữu hạn. Định lý 1.6. Phương án X x j là cực biên khi và chỉ khi hệ véc tơ cột Aj ứng với các x j > 0 độc lập tuyến tính. Chứng minh: Không mất tính tổng quát, giả sử X có dạng X = (x1, x2, , xk, 0, , 0), trong đó x1, x2, , xk > 0. Điều kiện cần: Giả sử X là phƣơng án cực biên. Ta chứng minh hệ véc tơ A1, A2, , Ak độc lập tuyến tính. Thật vậy, giả sử ngƣợc lại hệ A1, A2, , Ak phụ thuộc tuyến tính, nghĩa là tồn tại s 0 (s [1, k]) mà 1A1+ 2A2 + + kAk = 0. (1.12) Lại do X là phƣơng án nên x1A1 + x2A2 + + xkAk = B. (1.13) Từ (1.12) và (1.13) ta có (x1 1)A1 + (x2 2)A2 + + (xk k)Ak = B. Vì x1, x2, , xk > 0, nên có thể chọn > 0 đủ bé để xs s 0, s =1, 2, , k. Khi đó ta đƣợc: X1 = (x1 + 1, x2 + 2, , xk + k, 0, , 0) và X2 = (x1 1, x2 2, , xk k, 0, , 0) là hai phƣơng án khác nhau (vì tồn tại s 0, > 0). 11 Nhƣng lúc này X = XX, suy ra X là tổ hợp lồi của hai phƣơng án. 2212 Điều này là mâu thuẫn với X là phƣơng án cực biên. Vậy hệ véctơ cột A1, A2, , Ak độc lập tuyến tính. - 19 -
14. Điều kiện đủ: Cho hệ véctơ cột A1, A2, , Ak của ma trận ràng buộc A trong sự phân tích x1A1 + x2A2 + + xkAk = B, (với x1, x2, , xk > 0) độc lập tuyến tính. Ta chứng minh X = (x1, x2, , xk, 0, , 0) là phƣơng án cực biên. Giả sử X không phải là phƣơng án cực biên, nghĩa là tồn tại hai phƣơng án khác nhau X' (x')j (x',x' 1 2 , ,x' n ) và X" (x")j (x",x", ,x" 1 2 n ) của bài toán sao cho X = X’ + (1 - )X”, (0, 1). Điều này tƣơng đƣơng với xj x' j (1 )x", j j 1,n . Với j k 1,n thì một mặt xj 0, j k 1,n , mặt khác xj x' j (1 )x",j j k 1,n , mà X’, X” là các phƣơng án của bài toán nên x'jj 0, x" 0, j k 1,n . Suy ra x'jj x" 0, j k 1,n . Tức là X’ và X” thỏa mãn x'A x'A x'A B 1 1 2 2 k k x"A1 1 x"A 2 2 x"A k k B Từ đó, ta có (x'1 x")A 1 1 (x' 2 x")A 2 2 (x' k x")A k k 0 . Vì X’ và X” là hai phƣơng án khác nhau nên tồn tại x'll x" 0, từ đẳng thức trên suy ra hệ véctơ A1, A2, , Ak phụ thuộc tuyến tính. Điều này mâu thuẫn với giả thiết. Vậy X là phƣơng án cực biên.■ Ví dụ 1.5: Cho bài toán quy hoạch tuyến tính f(X) x1 2x 2 x 3 x 4 3x 5 min 2x1 x 2 x 3 x 4 3x 5 13 x1 x 2 x 3 5x 4 2x 5 1 với điều kiện 3x1 x 2 x 3 9x 4 3x 5 7 xj 0, j 1,5 Hỏi véctơ X(4, 5, 0, 0, 0) có phải là phƣơng án cực biên của bài toán đã cho hay không? Giải: Thay X vào hệ ràng buộc ta thấy thỏa mãn nên X là phƣơng án của bài toán. - 20 -
15. Phƣơng án X có hai thành phần dƣơng là x1, x2. Hệ véctơ cột của ma trận ràng buộc A ứng với các thành phần tọa độ dƣơng của X là: 2 1 A1 = 1 ; A2 = 1 3 1 Xét ma trận 2 1 1 1 1 1 1 1 2h12 h hh12 3h1 h 3 4/3h 2 h 3 D = [A1, A2] = 1 1 2 1 0 3 0 3 . 3 1 3 1 0 4 0 0 Suy ra rankD = 2 = số véctơ của hệ, do đó hệ véctơ {A1, A2} độc lập tuyến tính. Theo định lý 1.6, phƣơng án X là phƣơng án cực biên của bài toán. Ví dụ 1.6: Cũng với bài toán nhƣ trên, hỏi véctơ X(2, 8, 0, 1, 0) có phải là phƣơng án cực biên hay không? Giải: Dễ thấy X là một phƣơng án của bài toán. Phƣơng án X có 3 thành phần tọa độ dƣơng là x1, x2, x4. Hệ véctơ cột của ma trận ràng buộc A ứng với thành phần tọa độ dƣơng của phƣơng án X là {A1, A2, A4}, hệ này có số véctơ bằng số chiều và định thức của ma trận tạo bởi chúng là: 2 1 1 D = 1 1 5 0 3 1 9 Suy ra hệ véctơ {A1, A2, A4} phụ thuộc tuyến tính. Vậy X không phải là phƣơng án cực biên. Hệ quả 1. Số tọa độ dương của phương án cực biên có tối đa là m (m là số phương trình của hệ ràng buộc). Hệ quả 2. Số phương án cực biên của là hữu hạn. Chú ý: i) Một phƣơng án của bài toán (1.6) – (1.8) có số thành phần tọa độ dƣơng không vƣợt quá m chƣa hẳn là phƣơng án cực biên. ii) Một phƣơng án cực biên có đủ m tọa độ dƣơng thì phƣơng án cực biên đó là phƣơng án cực biên không suy biến. - 21 -
16. iii) Một phƣơng án cực biên của bài toán trên có số thành phần tọa độ dƣơng ít hơn m thì phƣơng án cực biên đó là phƣơng án cực suy biến. iv) Hệ m véctơ Aj độc lập tuyến tính tƣơng ứng với phƣơng án cực biên X nhƣ đã nêu trong định lý 1.6 gọi là cơ sở liên kết. v) Bài toán QHTT có tất cả các phƣơng án cực biên không suy biến đƣợc gọi là bài toán QHTT không suy biến. Ví dụ 1.7: Cho bài toán f(X) 2x1 x 2 x 3 min 2x1 x 2 x 3 x 4 4 3x1 x 2 x 5 5 với điều kiện x1 x 2 x 3 2 xj 0, j 1,5 a) Véctơ X(2, 0, 0, 0, 1) có phải là phƣơng án cực biên không? b) Hệ véctơ {A1, A2, A3} có độc lập tuyến tính không? Nếu có hãy tìm một phƣơng án cực biên tƣơng ứng. Giải: a) Vì hệ véctơ {A1, A4, A5} độc lập tuyến tính, nên X(2, 0, 0, 0, 1) là phƣơng án cực biên. b) Dễ kiểm tra hệ véctơ {A1, A2, A3} độc lập tuyến tính. Giả sử X*(x1, x2, x3, 0, 0) (x1, x2, x3 0) là phƣơng án cực biên cần tìm. Khi đó X* thỏa mãn các điều kiện ràng buộc của bài toán. 16 x 1 9 2x1 x 2 x 3 4 1 3x12 x 5 x 2 3 Hệ vô nghiệm. x x x 2 1 2 3 1 x03 xj 0, j 1,3 9 xj 0, j 1,3 Vậy không tồn tại phƣơng án cực biên nào nhận hệ véctơ {A1, A2, A3} là cơ sơ liên kết. - 22 -
17. Định lý 1.7. Mỗi phương án cực biên của tập phương án đều tồn tại một hàm mục tiêu để nó là phương án tối ưu duy nhất. Chứng minh: Cho X( x1 ,x 2 , ,x j , ,x k ,0 ,0) là phƣơng án cực biên ứng với cơ sở liên kết A1A2 Ak ( k [1, m]). Đặt: J = [1, k] là tập chỉ số cơ sở liên kết của X. 0 nêu j J C = (c ) với c , tức là C = 0,0, ,0,1, ,1 . j j 1 nêu j J  cã k sè 0 n Rõ ràng CX = 0, và với mọi phƣơng án Y y j ta có CY = y j 0. Vậy X j k 1 là phƣơng án tối ƣu. Đồng thời nếu có Y là phƣơng án tối ƣu thì cũng có CY = 0. Lại vì, c j 1với j J, chứng tỏ yj = 0 với j J. Do [A1A2 Ak] không suy biến nên từ hệ phƣơng trình AX = B và AY = B suy ra X =Y, nghĩa là phƣơng án X tối ƣu duy nhất. Định lý 1.8. (Về sự tồn tại PATƢ của bài toán QHTT) Nếu bài toán QHTT có tập phương án khác rỗng và hàm mục tiêu bị chặn dưới đối với bài toán f(X) min ( bị chặn trên đối với bài toán f(X) max) trong tập các phương án thì bài toán có phương án tối ưu. Ví dụ 1.9: Chứng minh bài toán sau có phƣơng án tối ƣu f(X) 3x1 3x 2 x 3 min x1 2x 2 x 3 1 x13 5x 16 với điều kiện 2x23 9x 3 3x1 x 2 3x 3 6 xj 0, j 1,3 Giải: ▪ Nhận thấy X(0, 0, 2) là một phƣơng án của bài toán, do đó tập phƣơng án của bài toán là khác rỗng. - 23 -
18. ▪ Chứng tỏ hàm mục tiêu f(X) bị chặn dƣới. Từ hệ ràng buộc ta có x1 2x 2 x 3 1 x1 5x 3 16 3x 1 3x 2 x 3 9 3x1 x 2 3x 3 6 Vì xj 0, j 1,3 nên x3 - x3. Do đó f(X) 3x1 3x 2 x 3 3x1 3x 2 x 3 9, X . Tức là hàm mục tiêu f(X) bị chặn dƣới trong tập phƣơng án . Theo định lý 1.8 thì bài toán có phƣơng án tối ƣu. Ví dụ 1.9: Cho bài toán QHTT f(X) 5x1 2x 2 2x 3 5x 4 min 2x1 2x 2 x 3 x 4 5 3x1 x 2 3x 3 4x 4 8 với điều kiện x1 2x 2 x 3 3x 4 7 xj 0, j 1,4 Chứng minh rằng bài toán có phƣơng án nhƣng không có phƣơng án tối ƣu. Giải: Xét họ véctơ phụ thuộc tham số X( ) = (0, 2 , 0, ), mọi tùy ý. Thay X( ) vào hệ ràng buộc của bài toán, ta đƣợc: 202(2) 0 5 5 1 3 0 2 3 0 4 2 8 4 0 . 02(2) 03 7 7 xj 0, j 1,4 0 Vậy, với mọi 0 thì X( ) là phƣơng án của bài toán. Mặt khác, thay họ X( ) vào hàm mục tiêu ta đƣợc f(X( )) = khi + . Vậy hàm mục tiêu của bài toán không bị chặn dƣới trong tập phƣơng án, do đó bài toán không có phƣơng án tối ƣu. - 24 -