🔙 Quay lại trang tải sách pdf ebook Các Phương Pháp Toán Kinh Tế Ebooks Nhóm Zalo ĐẶNG VÀN THOAN CÁC PHỬƠNG PHÁP TOÁN KINH TẾ St bản giáo dục -1998 TRƯỜNG ĐẠI HỌC THƯƠNG MẠI ĐẶNG VÀN THOAN CÁC PHƯƠNG PHÁP TORN KINH TẾ NHÀ XUẤT BẢN GIÁO DỤC - 1998 thêm trong "giáo trình bài tập các phương pháp toán kinh tế" se xuất bản trong thời gian gàn đây. Đối tượng phục vụ chính của giáo trình là sinh viên hệ đào tạo chính quy của Trường Đại học Thương mại, song nó vẫn có thể có ích cho những ai muốn tìm hiểu và vận dụng các phương pháp toán kinh tế trong nghiên cứu và hoạt động thực tiễn trong lĩnh vực quản lý và kinh doanh. Trong quá trình biên soạn, tác giả đã nhận được những ý kiên đóng góp quý báu của các đòng nghiệp ở bộ môn Toán Trường Đại học Thương mại. Tác già cũng nhận được những góp ý và những gợi ý để giáo trình có chất lượng tốt hơn của PGS. - Tiến sĩ Nguyễn Xuân Tấn (Viện toán học) và của PTS. Nguyễn Xuân Viên (Học viện kỹ thuật quân sự). Tác giả chán thành cảm ơn tất cả những đóng góp chân tình dó. Tuy nhiên, giáo trình khó tránh khỏi những hạn chế và thiếu sót trong nội dung và cách diễn giải ở các chương, mục. Tác giả mong nhận dược những ý kiến nhận xét của bạn đọc, để tiếp tục hoàn thiện nội dung giáo trình trong những Tân xuất bản sau. Hà Nội, tháng 9 năm 1998 Tác gia 4 CHƯƠNG I Cơ SỞ TOÁN CỦA QUI HOẠCH TUYẾN TÍNH 1.1. VÉC Tơ Ta gọi một bộ n số thực {xx, x2,... xn) -được sắp xếp theo một thứ tự nhất định là một véc tơ n - chiều. Nếu sắp xếp theo thứ tự từ trên xuống dưới thì ta gọi là véc tơ cột và ký hiệu: X1 x2 xn Nếu sắp theo thứ tự từ trái sang phải thì ta gọi là véc *T» * tơ hàng và ký hiệu X = [xx, x2,..., xn]. Số Xj (i = 1,2,... ,n) gọi là thành phần (hay toạ độ) thứ i của véc tơ X. 2 Ví dụ: là một véc tơ cột hai chiều, [-3, 5, -1, -4] là 3 một véctơ hàng bôn chiều. 5 Các véc tợ mà sau này chúng ta thường nói tới, là các véc tơ cột. Để chỉ các véc tơ hàng, ta dùng chỉ số T (chuyển vị) ghi ở góc trên bên phải, chẳng hạn AT = [-5, 4, 2, 6]. Hai véc tơ n chiều X = [xx, x2,...,rXn]T và Y = [yx, y2,...yn]T được gọi là bằng nhau nếu các thành phần tương ứng của chúng bằng nhau, tức là X = Y nếu Xị = y¡, Vị = 1,2,...,n Đối vối hai véc tơ n chiều A = [ax, a2,..., an]T và B = [bi, b2,.... bn]T Ta ký hiệu A < B (đọc là A nhỏ hơn B) nếu xảy ra đồng thời ax < bx, a2 < b2,..., an < bn Ta kí hiệu: A < B nếu ax < bx, a2 < b2(...., an < bn Tương tự, chúng ta đưa ra các ký hiệu: A > B (đọc A lớn hơn B) A > B - Một véc tơ mà tất cả các thành phần của nó đều bằng 0, ta gọi là véc tơ không, ký hiệu 0T = [0, 0,...., 0], 1.2. CÁC PHÉP TÍNH VÉC Tơ 1. Phép nhân véc tơ với một số thực Ta gọi tích của một véc tơ n chiều A vởi một số thực k là một véc tơ n chiều, ký hiệu là kA, mà các thành phần của nó là tích của sô k với các thành phần ứng của véc tơ A. Như vậy: k.A = [kax, ka2,...., kan]T 6 Nếu ta nhân véc tơ A với -1 ta nhận được véc tơ -A, là một véc tơ mà toạ độ của nó sai khác về dấu so với toạ độ của A. Véc tơ -A gọi là véc tơ đối của véc tơ A. 2. Tổng của hai véc tơ Tổng của hai véc tơ n chiều AT = [ab a2,...., an] và BT = [bj, b2,.... bn] là một véc tơ n chiều, ký hiệu AT + BT mà các thành phần của nó là tổng của các thành phần tương ứng của AT và BT. Như vậy AT + BT = [ai + b1( a2 + b2,....., an + bn] Chúng ta định nghĩa hiệu của hai véc tơ A và B như là tổng của véc tơ A và véc tơ -B. Như vậy A - B = [ax - b1; a2 - b2,...., an - bn] Phép nhân véc tơ với một số và phép cộng véç tơ có các tính chất sau: a. Tính giao hoán A + B = B + A b. Tính kết hợp t(kA) = (tk)A; A + (B + C) = (A + B) + c c. Tính phân bố (t + k)A = tA + kA; k(A + B) = kA + kB Vởi mỗi véc tơ A = [a1; a2,...., an] đều tồn tại một véc tơ đối -A = [-ax, -a2,...., -an] để cho . A + (-A) = 0 7 3. Tích vô hướng của hai véc tơ Ta gọi tích vô hướng của hai vềctơ n chiều X và Y là một số thực, được xác định bỏi tổng các tích của các thành phần tương ứng của X và Y, ký hiệu là (X,Y) hay X.Y Như vậy nếu X = [xx, x2,...., xn]T và Y = [yx, y2,...., yn]T thì (X,Y) = ỈVi i = l Ví dụ: Cho X = [-2, 3, -1, 0]T, Y = [4, -1, 5, 2]T thì (X,Y) = -8 - 3 - 5 + 0 = -16 Tích vô hướng có các tính chất sau: a. (X,Y) = (Y,X) b. (kX,Y) = (X,kY) = k(X,Y) c. (X + Y,Z) = (X,Z) + (Y,Z) d. (X,X) > 0. Dấu = xẩy ra khi và chỉ khi X = 0 1.3. ĐỘC LẬP TUYẾN TÍNH VÀ PHỤ THUỘC TUYẾN TÍNH 1. Tổ hợp tuyếi* tính của các véc tơ Cho.m véc tơ n chiều Ax, A2,..., Am khi đó véc tơ A = kxAx +k2A2+.... + kjjAn Vởi kx, k2,..., km là các sô thực, được gọi là tổ hợp tuyến tính của m véc tơ đã cho hay A biểu diễn tuyến tính qua các véc tơ Ax, A2,....,Am Ví dụ-. Cho Ax = [-2, 1, 0], A2 = [1, 3, 2], A3 = [4, -1, 1] thì A = 2AX + 5A2 - 3Ag = [-11, 20, 7] là một tổ hợp tuyêh tính của Ax, A2 và A3 8 - Tổ hợp tuyến tính được gọi là không âm nếu kj > 0 với mọi: i = 1, 2,...., m - Ta gọi tổ hợp tuyến tính: klAl + k2A2 +...... + kmAm là tổ hợp lồi nếu: kl + k2 +...... + km = 1 kị > 0 (i = 1, 2,...., m) 2. Các véc tơ Ax, A2, Ajn được gọi là độc lập tuyến tính nếu tổ hợp tuyến tính của chúng bằng véc tơ không chỉ khi tất cả các hệ số đệu bằng 0, tức là hệ thức kiAi + k2A2 +.... + kujAnj = 0 (1.1) chỉ khi kx = k2 =.... km = 0 (1.2) - Nếu hệ thức (1.1) xẩy ra khi có ít nhất một hệ số kj khác không thì các véc tơ Ax, A2,...., Ajn được gọi là phụ thuộc tuyến tính 3. Điều kiện cần và đủ để hệ véc tơ Ax, A2,.... Aja phụ thuộc tuyến tính là có ít nhất một véc tơ của hệ biểu diễn tuyến tính qua các véc tơ còn lại. Thật vậy, nếu các véc tơ Ax, A2,....., Anj phụ thuộc tuyến tính thì hệ thức (1.1) xẩy ra với ít nhất một hệ số khác không, chẳng hạn kj * 0, khi‘đó từ (1.1) ta có kl ko kj_x kj + x 4 = - ^A!-^A2 -••• "k^-i" 1(^ + 1 tức là A¿ là tổ hợp tuyến tính của các véc tơ còn lại 9 Ngược lại nếu ít nhất một véc tơ của hệ, chẳng hạn Ax biểu diễn tuyến tính qua các véc tơ còn lại, nghĩa là: Ax = a2A2 + Œ3A3 +.... + amAm thế thì Ax - a2A2 - a3A3 - .... - amAm = 0 Với ít nhất hệ sô của Ax khác không. Điều đó chứng tỏ hệ Ax, A2,...., Am phụ thuộc tuyến tính. Từ đây, ta suy ra mệnh đề tương tự cho hệ véc tơ độc lập tuyến tính: Điều kiện cần và đủ để một hệ véc tơ độc lập tuyến tính là bất kỳ véc tơ nào của hệ cũng không thể biểu diễn tuyến tính qua những véc tơ còn lại. Từ định lý trên, ta dễ thấy nếu một trong các véc tơ Ax, A2, ....Am là véc tơ không thì hệ là phụ thuộc tuyến tính. Chẳng hạn Ax = 0 thì Ax có thể biểu diễn tuyến tính qua các véc tơ còn lại Ax = O.A2 + O.A3 +.... + O.Ajn Ví dụ: Các véc tơ: AT = [3, 2, -4], B1' = [2, -1, 3], CT = [0, -7, 17] là phụ thuộc tuyến tính vì 2AT - 3BT + CT =0 Nhưng các véc tơ AT = [3, 2, -4], BT = [2, -1, 3], DT = [2, 2, 2] là độc lập tuyến tính vì không một véc tơ nào trong chúng có thể biểu diễn tuyến tính qua hai véc tơ kia. 10 1.4. HẠNG CỦA HỆ VÉC Tơ 1. Định nghĩa hệ con độc lập tuyến tích cực đại Cho một hệ véc tơ (có thể gồm một số hữu hạn hay vô hạn các véc tơ). Giả sử, hệ này có một hệ con gồm h véc tơ độc lập tuyến tính sao cho nếu thêm vào đó bất kỳ một véc tơ nào của hệ đã cho, ta đều được hệ (h + 1) véc tơ phụ thuộc tuyến tính. Khi đó ta nói hệ h véc tơ ấy là hệ con độc lập tuyến tính cực đại của hệ véc tơ đã cho. Ví dụ: Xét hệ gồm ba véc tơ: AT = [1, -2, 3], BT = [4, 2, -1] và CT = [6, -2, 51. Ta thấy AT và BT là hai véc tơ độc lập tuyến tính, nhưnạ c có thê biểu diễn tuyến tính qua hai véc tơ A và B : c = 2A + BT, nên hệ con độc lập tụ^ến tính cực đại của hệ ba véc tơ đã cho gồm hai véc tơ AT và BT. - Đối với một hệ véc tơ đã cho, mọi hệ con độc lập tuyến tính cực đại của nó có sô lượng véc tơ bằng nhau. 2. Hạng của hệ véc tơ Định nghĩa: số lượng các véc tơ trong hệ con độc lập tuyến tính cực đại củạ một hệ véc tơ, được gọi là hạng của hệ véc tơ ấy. Định lý: Nếu hạng của một hệ véc tơ bằng h thì mỗi véc tơ của hệ đều có thể biểu diễn dưới dạng tổ hợp tuyến tính của h véc tơ độc lập tuyến tính bất kỳ của hệ và cách biểu diễn đó là duy nhất. Chứng minh: Phần một của định lý là hiển nhiên. Thật vậy vì hệ véc tơ có hạng bằng h, nên ta có thể chọn ra h véc tơ độc lập tuyến tính A1; A2,....., Ajj. 11 Giả sử một véc tơ B khác của hệ không có thể biểu diễn tuyến tính qua h véc tơ trên. Điều này có nghĩa (h + 1) véc tơ A1; A2,...., Ah, B lập thành hệ con độc lập tuyến tính - mâu thuẫn với giả thiết hạng của hệ véc tơ bằng h, nên B phải là tổ hợp tuyến tính của các véc tơ A1( A2,...., Ah. Ta chứng minh tính duy nhất của biểu diễn. Giả sử B có thể biểu diễn dưới dạng tổ hợp tuyến tính của A1; A2,...., Ah theo hai cách, tức là: B = (XjAi + a2A2 +.... + ttjjAjj B = ßjAi + ß2A2 +.... + ßhAh Trừ hai phương trình cho nhau ta được 0 = (et} - ßi)Ar + ( a2 - ß2)A2 +..... + ( _ ßh)Ah Vì A1; A2,.... Ah độc lập tuyến tính nên hệ thức trên chỉ xẩy ra khi tất cả các hệ số đều bằng 0, tức là: «i = ßi> Vi = 1, 2, ...., h Như vậy cách biểu diễn của B là duy nhất. Từ định lý trên ta có thể suy ra hai hệ quả quan trọng, chứng minh chúng nhường cho độc giả: Hệ quả 1. Ta loại ra từ hệ véc tơ đã cho một véc tơ là tổ hợp tuyến tính của các véc tơ còn lại thì hạng của hệ không thay đổi. Hệ quả 2'. Ta đưa vào hệ véc tơ đã cho một véc tơ là tổ hợp tuyến tính của các véc tơ của hệ thì hạng của hệ không thay đổi. 12 1.5. CÁC KHÔNG GIAN VÉC Tơ 1. Định nghĩa 1 Tập hợp tất cả các véc tơ n chiều vởi hai phép tính cộng và nhân véc tơ với một số đã nêu ở 1.2, được gọi là một không gian véc tơ n chiều trên trưòng số thực (còn gọi là không gian tuyến tính n chiều), ký hiệu Rn. Như vậy, nếu X G Rn, Y G Rn và a là một số thực thì: X + Y G Rn, aX G Rn Không gian véc tơ Rn có hạng hằng bằng n: Từ hình học giải tích chúng ta biết rằng: Khoảng cách từ điểm A = [a17 a2J đến gốc toạ độ được cho bỏi biểu thức + a2. Sau khi đưa vào khái niệm tích vô hưởng thì biểu thức trên có thể viết dưới dạng >/( A, A ). Chúng ta gọi số này là chuẩn (hay độ dài) của véc tơ A và ký hiệu là |A|. Khoảng cách giữa hai điểm A = [ab a2] và B = [bp b2] ký hiệu là p(A, B) được cho bởi biểu thức: ^(ai - bi)2 + (a2 - b2)2 Khoảng cách đó có thể viết dưới dạng tích vô hướng p(A, B) = V(A-B,A-B) Khái niệm nêu trên về khoảng cách có các tính chất sau: Nếu A, B G Rn thì: 1. p(A, B) = p(B, A) 2. p(A, B) > 0, p(A, B) = 0 <-> A = B 3. p(A, B) < p(A,C) + p(C, B) (qui tắc tam giác) 13 Nếu chúng ta đưa vào không gian véc tơ khái niệm độ dài của véc tơ theo nghĩa trên, thì ta sẽ có khái niệm chặt hơn - không gian ơ-cờ-lít. Tổng quát chúng ta đưa vào không gian véc tơ Rn khái niệm chuẩn bằng cách định nghĩa tích vô hướng và ta gọi |A I = >/( A, A ) là chuẩn (hay độ dài) của véc tơ A và |A - B I gọi là khoảng cách giữa véc tơ A và B. 2. Định nghĩa 2 Nếu trong không gian véc tơ n chiều ta định nghĩa tích vô hướng thì sẽ nhận được không gian ơ-cờ-lít n chiều, ký hiệu là En. 3. Định nghĩa 3 Hệ n véc tơ độc lập tuyến tính được gọi là một cơ sở của không gian n chiều. Khi đã có một cơ sỏ thì mỗi phần tử của không gian có thể biểu diễn một cách duy nhất dưởi dạng tổ hợp tuyến tính của các phần tử thuộc cơ sở. Dễ dàng thấy rằng tập hợp tất cả các véc tơ n chiều đã được định nghĩa ỏ 1.1 tạo nên một không gian ơ-cờ-lít n chiều. Trong tập hợp này chúng ta đã định nghĩa các phép tính với các tính chất thoả mãn theo yêu cầu của không gian ơ cờ-lít. Ta chỉ cần chỉ ra tập hợp này có hạng bằng n. Ta có n véc tơ đơn vị thuộc tập hợp các véc tơ n chiều 14 Ei 1 0 0 0 1 0 > E2 - , ■ ■ ■ , En = 0 0 1 Các véc tơ này có một thành phần bằng 1, các thành phần còn lại bằng 0. Các véc tơ này lập thành hệ n véc tơ độc lập tuyến tính (đọc giả tự chúng minh). Một véc tơ n chiều bất kỳ đều có thể biểu diễn tuyến tính qua n véc tơ đơn vị vì *1 a2 - a]Ex + a2E2 + . . . + anEn Vì khi thêm vào các véc tơ phụ thuộc tuyến tính thì hạng của hệ không thay đổi, từ đó suy ra hệ tất cả các véc tơ n chiều có hạng bằng n và như vậy không gian tương ứng là n chiều. Việc xác định cơ sỏ trong không gian ơ-cờ-lít ứng với việc thiết lập hệ toạ độ trực giao (tức là thiết lập các trục toạ độ và các độ dài đơn vị) Việc chuyển từ một cơ sở này sang một cơ sở khác ứng với việc thay đổi hệ toạ độ. ở phần sau (mục 1.13), chúng ta sẽ nghiên cứu việc xác định toạ độ của véc tơ trong một cơ sở bất kỳ. Nếu chúng ta chọn trong En một hệ véc tơ xác định và lập tất cả các tổ hợp tuyến tính của chúng thì chúng ta 15 cũng nhận được một không gian ơ cờ lít. Điều này là hiển nhiên vì các véc tơ tạo nên như vậy là đóng đối với phép cộng và phép nhân véc tơ với một số, tức là tổng của hai tổ hợp tuyến tính hoặc bội bất kỳ của tổ hợp tuyến tính cũng là những tổ hợp tuyến tính của các véc tơ này. Các đòi hổi khác của không gian ơ cờ lít cũng thoả mãn yì chúng là các phần tử của En. Một không gian được tạo nên như vậy là một bộ phận của En và gọi là không gian con của En Ví dụ về không gian con: Tập hợp tất cả các tổ hợp tuyến tính của hai véc tơ đơn vị n chiều tạo nên không gian con của En. Mỗi mặt phẳng là một không gian con 2 chiều của không gian 3 chiều,... 1.6. MA TRẬN 1. Định nghĩa 1 - Ta gọị một bảng gồm m.n số thực, được sắp xếp thành m hàng và n cột la một ma trận cấp m.n, ký hiệu là Amn Mỗi sô nằm trong cấu thành của ma trận gọi là một phần tử của ma trận. Phần tử nằm ố hàng i cột j của ma trận A ký hiệu là aịj. Như vậy ma trận A cấp m.n có dạng: all a12 • ■ • aln a21 a22 • • • a2n aml am2 ■ ■ • amn _ Thường để chọn gọn khi viết ma trận ta chỉ cần ghi phần tử tổng quát và cấp của nó: 16 A - [a ij] m . n Cần nhấn mạnh rằng ma trận là một bảng được sắp xếp của các phần tử, còn bản thân m.n số thực chưa xác định một ma trận. Ma trận được xác định khi biết thứ tự của các phần tử trong cấc hàng và các cột. Từ đây ta suy ra khái niệm bằng nhau của ma trận. 2. Định nghĩa 2: Hai ma trận A và B bằng nhaú (ký hiệu A = B) khi và chỉ khi hai-ma trận cùng cấp và các phần tử tương ứng của chúng bằng nhau. 3. Định nghĩa 3: Cho A là một ma trận cấp m.n, nếu ta đổi hàng thành cột và cột thành hàng thì được ma trận AT cấp n.m, gọi là ma trận chuyển vị của ma trận A. Như vậy: all a21 • • • AT = a12 a22 ■ • • am2 aln a2n ■ • • amn Một Số dạng đặc biệt của ma trận đóng vai trò quan trọng trong các ứng dụng của ma trận: Ma trận A có Số hàng bằng Số cột, tức là m = n thì ta gọi A là ma trận vuông cấp n. 17 A all a12 • • • aln a21 a22 •• • a2n ^1 an2 • • • ann Các phần tử an, a22,..., ann gọi là các phần tử đường chéo. Các phần tử đường chéo tạo nên đường chéo chính của ma trận. - Ma trận vuông mà tất cả các phần tử nằm ngoài đưòng chéo chính đều bằng 0, tức là ma trận có dạng: an 0 . . . 0 0 a22 ... 0 0 0 . . . ann Gọi là ma trận đưòng chéo. - Ma trận chéo mà tất cả các phần tử nằm trên đưòng chéo chính đều bằng một, gọi là ma trận đơn vị, thường ký hiệu là I (hay E). Đôi khi ta dùng chỉ số để chỉ cấp của ma trận đơn vị, chẳng hạn: 10 0 •I3 = 0 10 0 0 1 Trong các phép tính về ma trận, ma trận đơn vị đóng vai trò tương tự như sô một trong các sô thực. Khi giải cầc phương trình tuyến tính, các ma trận tam giác có vai trò quan trọng. Đó là các ma trận vuông mà tất cả các phần tử nằm phía trên đường chéo chính hoặc phía dưới nó đều bằng không. Chẳng hạn ma trận tam giác (dưới) có dạng: 18 \all 0 a21 a22 a31 a32 a41 a42 ất cả các - Ma trận có m hàng và chỉ một cột là một véc tơ cột m chiều. Ma trận chỉ có một hàng và n cột là một véc tơ hàng n chiều. - Hàng của một ma trận cấp m.n là một véc tơ n chiều (gọi là véc tơ hàng). Cột của ma trận cấp m.n là một véc tơ m chiều (gọi là véc tơ cột). 1.7. MA TRẬN KHỐI Với một ma trận đã cho ta có thể tách nó ra thành một sô ma trận thánh phần - ma trận khối bỏi các đường nằm ngang và thẳng đứng. Việc tách (phân chia) ma trận đã cho thành ma trận khối có thể tiên hành theo nhiều cách khác nhau tuỳ thuộc vào mục đích của việc sử dụng. Chẳng hạn đối với ma trận A cho dưới đây, ta có một trong các cách tách như sau: all a12 a13 a14 a15 a21 a22 a23 a24 a25 a31 a32 a33 a34 a35 a41 a42 a43 a44 a45 ở đây A được tách thành bốn ma trận khối. 19 Nêu chúng ta ký hiệu các ma trận khối bởi An, A12, A21, A22 thì ma trận A có thể viết dưới dạng: A _ An A12 Aỉi a22 Việc tách ma trận thành các ma trận khối là rất thuận lợi vì với một số phép tính về mặt hình thức ta xem chúng như các phần tử của ma trận. Đặc biệt mỗi hàng của ma trận A = 1 aịj m n ta coi như một ma trận hàng (véc tơ hàng) và toàn bộ ma trận A có thể xem như tạo nên từ các véc tơ hàng, tức l'à: ở đây a = [a^, ai2,...,ain] , (i = 1,2,...,m) Tương tự ma trận A có thể xem như tạo nên bỏi các véc tơ cột, tức là: A = [ A1; A2, . . . An ] aij a2j trong đó: =(j= l,2,...,n) amj 20 Tương tự với việc tách ma trận thành các ma trận con bởi các đường nằm ngang và thẳng đứng, ta cũng có thể gộp các ma trận bằng cách gắn một số ma trận vởi số lượng thích hợp các hàng và các cột trong một ma trận duy nhất. 1.8. CÁC PHÉP TÍNH MA TRẬN 1. Tổng (hiệu) của hai ma trận Tổng (hiệu) của hai ma trận A và B cùng cấp m.n là ma trận cấp m.n mà các phần tử của nó là tổng (hiệu) các phẩn tử tương ứng của A và B tức là: all a12 • • aln b11 b12 ... bln a21 a22 • • ■ a2n +'D21 b22 • • ■ b2n aml am2 ■ • amn _ aml bm2 • • • bmn a11 ± bn a12 ± t>!2 • • • aln i bln a21± ^21 a22 ± ^22 • • • a2n ± ^2n aml — bjni am2 ± ^m2 • • amn ± ^mn Ví dụ: 3-10 0 4 2 2 13 3 -4 -25 0 3 3 0 0 3-10 -2 1 3 1 -2-3 .0 4 2 3 -4 -2. .-3 8 4 2. Tích của ma trận với một hằng sô Ta gọi tích của ma trận A cấp m.n với một hằng số k là ma trận cấp m.n, ký hiệu là kA mà các phần tử của 21 nó là các phần tử tương ứng của A được nhân lên với k. Như vậy: au a12 • • • aln k.an k.a12 .. • k.aln k. a21 a22 • • • a2n--k.a21 k.a22 .. • k.a2n _ aml am2 • • • amn _ .k-a«! k-am2 • • k-a^ Ví dụ 1-2 2 [•3 - 6 6 -3 -1 -4. ■ [9 -3 -12. Cũng như các phép tính véc tơ ta dễ thấy hai phép tính ma trận trên có các tính chất sau: - Giao hoán: A + B = B + A kA = Ak - Kết hợp: A + (B + C) = (A + B) + c k (rA) = (kr) A - Phân bố: k (A + B) = kA + kB (k +r) A = kA + rA ở đây các ma trận A, B, c đều cùng cạp. 3. Nhân ma trận Phép nhân ma trận được định nghĩa như sau: Cho ma trận A câp m.n và ma trận B cấp n.p thì tích A.B = c là ma trận cấp .m.p. Phần tử tổng quát của tích Cịj (tức là phần tử nằm ở'hàng i, cột j của C) là tổng các 22 tích giữa các phần tử nằm à. hàng i của ma trận A vởi các phần tử tương ứng nằm ở cột j của ma trận B . Nói cách khác phần tử Cjj của tích A.B là tích vô hướng giữa hàng i của ma trận A và cột j của ma trận B. Như vậy nếu: A = aii a21 a12 • • a22 • • • aln • a2n, B = bu ^21 bi2 • ^22 • • blp' • b2p thì _ aml am2 • • • amn _. bnl t>n2 • ■ bnp _ ỉaii bii X aii bi2 • •• Zj aii bip i=l i=l i=l ỉa2i bjiẳ a2j bi2 . . • ẳ a2i bịp i=l i=l i=l ỉami bịiỉ ami bi2 • • • ỉami bịp i=l i=l i=l Đối vối phép nhân ma trận vẫn có tính chất kết hợp và phân bố khi các má trận tham gia phép tính thoả mãn điều kiện nhân được: Nếu A cấp m.n, B cấp n.p, c cấp p.q thì A.(B.C) = (A.B). c Nếu A cấp m.n, B cấp m.n, c cấp n.p thì (A + B). c = A.c + B.c Phép nhân ma trận không có tính chất giao hoán, tức là nói chung không xẩy ra đảng thức: 23 A.B = B.A Như vậy trong phép nhân thứ tự của các nhân tử không được thay đổi cho nhau vì theo định nghĩa của phép nhân, ma trận A nhân được với B chưa hẳn B đã nhân được vởi A; ngay trong trường hợp nhân được thì kết quả nói chung khác nhau. Ngoài ra còn một trường hợp đặc biệt là với một ma trận A cấp m.n bao giờ cũng tồn tại hai ma trận đơn vị thích hợp sao cho EmA = A = A.En, tuy nhiên đây không phải là tính chất giao hoán vì hai ma trận Em và En không cùng cấp. Chúng ta cần phân biệt nhân bên phải hay nhân bên trái đối vởi phép nhân ma trận. Các ví dụ: 3 3 1 1 0 ’ 0 6 -2 4 _ -1 2 _ -6 8 r-< 1 1 0 3 3 3 3 -1 2 _ -2 4 . -7 5 . 1.2 nhưng -1 2 1 -1 nhưng 312 6 4 0 24 3 2 0- 1 1 1 1.3 3 [2 1 4], = [15] = 15 (quy ưởc), nhưng 1 2 3 1 _ 2 1.4 10 0 -100 10 0 '11 0 0 1 1 10-1 .[2 14] = 110 0 1 1 10-1 .10 0 -10 0 10 0 6 3 12 2 14 4 2 8 1 10 -1 -1 0 1 10 0 0 0 0 0 0 0 0 .0 , nhưng Khi nhân ma trận thường sử dụng cách tách ma trận thành các ma trận khối một cách thích hợp. Chẳng hạn cho hai ma trận 5 6 8 1 0 2 0 0 3 1 -2 0 1 2 0 0 -4 2 1 0 0 , B = 1 0 0 3 3 4 0 0 ' 3 2 1 2 6 - 1 0 0 4 3 2 Để tính A.B, ta có thể tách A, B theo sơ đồ sau: 25 5 6 8 1 0 3 1 -2 0 1 -4 2 1 0 0 3 3 4 0 0 2 6 - 1 0 0 2 0 2 0 1 0 3 2 4 3 Ta tính A.B theo hệ thức Aụ Aị2 A2i A22 Bịi B12 B21 B22 Au A^ Bu B]2 Au Bu + A]2 Ba Au Bj2 + A]2 Ba Aa A22 Ba B22 AaBu + A22 Ba Aa Bjj + A^ B^ Vì A12 là ma trận đơn vị và A22 là những ma trận không, nên ta nhận được: 33 2 1 A.B Aịị Bịị + B A21 B 10 3 2 -3 0 0 16 0 0 Việc tách hai ma trận phải được thực hiện sao cho việc nhân các ma trận con tương ứng là thực hiện được. Như vậy việc tách các cột của ma trận bên trái tương ứng với cách tách các hàng của ma trận bên phải. Ví dụ 1.5. Một xí nghiệp sản xuất ba loại sản phẩm từ bốn loại nguyên liệu. Định mức tiêu thụ nguyên liệu đối vởi từng loại sản phẩm được cho ở bảng 1.1 26 Bảng 1.1 Loại nguyên liệu Định mức nguyên liệu (kg) đối với một đơn vị sản phẩm A B c 1 50 80 120 II 40 20 30 III 15 50 5 IV 25 10 5 Bảng trên là một ma trận cấp 4x3. Theo kế hoạch xí nghiệp sản xuất 100 đơn vị sản phẩm A, 200 đơn vị sản phẩm B và 50 đơn vị sản phẩm c. Kế hoạch sản xuất được 100 cho bởi véc tơ cột ba chiều 200 50 Yêu cầu tiêu thụ tổng cộng đối với từng loại nguyên liệu được cho bồi tích 50 40 15 25 80 20 50 10 120 100 200 27000 9500 11750 4750 Nếu ta biết giá của từng loại nguyên liệu trong ví dụ trên, chẳng hạn là 20, 10, 50 và 40 nghìn đồng/ kg thì chi phí nguyên liệu đối với một đơn vị sản phẩm mỗi loại được tính như sau: 50 80 120 [20, 10, 50, 40] 40 20 30 15 50 5 25 • 10 5 = [3150, 4700, 3150] 27 1.9. HẠNG CỨA MA TRÄN ở mục 1.4 ta đã đưa ra khái niệm hạng của một hệ véc tơ là số cực đại các véc tơ độc lập tuyến tính có thể chọn trong hệ đã cho. Vì các hàng của ma trận hoặc các cột của ma trận tạo nên một hệ véc tơ, vì vậy ta có thể nói đến hạng của hệ véc tơ hàng và hạng của hệ véc tơ cột của một ma trận. Chúng ta sẽ chứng minh hạng của một hệ véc tơ hàng và hạng của hệ véc tơ cột của một ma trận là bằng nhau và để cho đơn giản ta nói đó là hạng của ma trận. Giả sử ma trận A cấp m.n có hạng của hệ véc tơ cột bằng s và hạng của hệ véc tơ hàng bằng r. Khi đó ta có thể chọn trong ma trận A s cột độc lập tuyến tính. Không giảm tính tổng quát ta giả sử s cột đầu tiên của ma trận A lập thành hệ độc lập tuyến tính. Từ s cột này ta lập ma trận Ai = [Aị, A2,....As1 cấp m.s Khi đó tất cả* các cột của ma trận A đều có thể biểu diễn dưới dạng tổ hợp tuyến tính của s cột này. Một cách tổng quát có thể viết Aj = Aibj, (j= 1,2,...,n) ở đây bj là véc tơ cột s chiều: 28 Việc phân tích ma trận A thành tích AịAq chứng tỏ mỗi hàng của ma trận A có thể biểu diễn dưới dạng tổ hợp tuyến tính của s hàng của ma trận Ạ2- Vì theo giả thiết trong ma trận A có thể chọn tối đa r hàng độc lập tuyến tính nên r < s Toàn bộ lập luận trên đuỢc lặp lại. Nếu chúng ta biểu diễn mỗi hàng của ma trận A dưới dạng tổ hợp tuyến tính của r hàng độc lập tuyến tính cực đại, chúng ta sẽ đi tới kết luận s < r Từ đó suy ra rằng r = s Nghĩa là hạng của hệ véc tơ hàng và hạng của hệ véc tơ cột của ma trận A là bằng nhau. Và ta gọi đó là hạng của ma trận A. Vậy: Hạng của ma trận A bằng sô cực đại các véc tơ hàng độc lập tuyến tính hay số cực đại các véc tơ cột độc lập tuyến tính trong ma trận A. 29 Từ chứng minh trên ta suy ra rằng: hạng của ma trận cấp m.n nhỏ hơn hoặc bàng số nhỏ nhất trong hai sô m và n. Một ma trận vuông cấp n có hạng bằng n (tức là bằng số hàng hoặc sô cột) được gọi là không suy biến. Nếu hạng của ma trận vuông cấp n nhỏ hơn n, ta gọi ma- trận đó là suy biến. 1.10. MA TRẬN NGHỊCH ĐẢO Định nghĩa: Cho A là một ma trận vuông không suy biến. Má trận nghịch đảo của ma trận A là một ma trận mà tích của nó với ma trận A cho ta ma trận đơn vị. Do tính không giao hoán của phép nhân ma trận nên một câu hỏi được đặt ra liệu có tồn tại hai ma trận nghịch đảo của ma trận A, trong đó X là ma trận nghịch đảo phải xác định bởi phương trình AX = E (1) và Y là ma trận nghịch đảo trái xác định từ phương trình YA = E (2) Dễ dàng chứng minh được hai ma trận nghịch đảo tiên là bằng nhau. Ta nhân phương trình thứ nhất về bên trái với ma trận Y ta nhận được: YAX = YE = Y Tương tự nhân phương trình (2) về bên phải với ma trận X ta nhận được YAX = EX = X từ đó suy ra 30 Y = X ■ tức là đổỉ với ma trận A tồn tại chỉ một ma trận nghịch đảo, chúng ta sẽ ký hiệu là A’1. Đối với cặp ma trận A và A’1 phép nhân có tính chất giao hoán Ví dụ về ma trận nghịch đảo A = 5] r-2 3-| r-5. 3- 1 0 -3 1.-3 2_ 0 1. Đối với ma trận đường chéo 3 0 0r1/3 0 0 D = 0 -4 0 thì D’1 = 0 -v4 0 0 0 5 0 0 v5_ 3 0 0 V3 0 0 1 0 0 Vì 0 -4 0 0 -14 0 = 0 1 0 0 0 5 0 0 V5. 0 0 1 Tổng quát: Một ma trận đường chéo có các phần tử trên đường chéo khác không thì ma trận nghịch đảo của nó cũng là một ma trận đường chéo cùng cấp, các phần tử trên đưòng chéo bằng nghịch đảo của các 'phần tương ứng trên đường chéo của ma trận ban đầu, tức là nếu’ kl 0 . . 0 0 . . . 0 D =0 k2 . . . 0thì D’1 =0 14c2 . . . 0 0 0 . . • kn. 0 0 .• Để tìm ma trận nghịch đảo của một ma trận A cho trước, ta xét ỏ mục (1.13) 31 1.11. HỆ PHƯƠNG TRÌNH TUYẾN TÍNH Hệ phương trình tuyến tính tổng quát gồm m phương trình với n ẩn có dạng: au xx + a12x2 + . • • + aln Xn - bl a21 X1 + a22 x2 + . • • + a2n Xn = b2 aml X1 + am2 x2 + . . ■ + amn xn - bm ở đây ta sử dụng các ký hiệu: (1.3) aịj là hệ sô của ẩn Xj trong phương trình thứ i (i = l,2,...,m; j = 1,2,.,.,n) A = n là ma trận hệ số của hệ phương trình bi b2 b = véc tơ vế phải của hệ phương trình, véc tơ ẩn số của hệ phương trình , 32 aij a2j véc tơ cột thứ j của ma trận A - a™j A = [A I b] ma trận mở rộng của hệ phương trình. Hệ phương trình (1.3) còn có thể viết dưới dạng: ỀaijXj = bi (i = l,2,...,m) (1.3’) j=i hoặc dưởi dạng véc tơ ỉxjAj=b (1.3”) j=l và dưới dạng ma trận AX = b (1.3’”) Hệ (1.3) được gọi là hệ thuần nhất nếu bị = 0 (i = l,2,...,m) trong trưòng hợp ngược lại (không phải mọi bj = 0) ta gọi là hệ không thuần nhất. - Véc tơ X thoả mãn mọi phương trình của hệ được gọi là một nghiệm của hệ - Một hệ có ít nhất một nghiệm gọi là hệ có nghiệm hay hệ tương thích. - Một hệ có một nghiệm duy nhất gọi là hệ xác định. - Một hệ có hơn một nghiệm (sẽ có vô số nghiệm) gọi là hệ vô định. 33 - Một hệ không có nghiệm gọi là hệ vô nghiệm. - Hai hệ phương trình tuyến tính được gọi là tương đương với nhau nếu mọi nghiệm của hệ này cũng là nghiệm của hệ kia và ngược lại hoặc hai hệ đều không tương thích? 2. Các phép biên đổi sơ cấp trên hệ phương trình tuyến tính Ba phép biến đổi dưới đây được gọi là các phép biến đổi sơ cấp trên hệ thống phương trình tuyến tính: a. Đổi chỗ hai phương trình của hệ cho nhau b. Nhân hai vế của phương trình của hệ với cùng một số khác không c. Cộng vào hai vế củà một phương trình hai vế tương ứng của một phương trình khác sau khi đã nhân với một số. Ta dễ dàng có thể chứng minh được: Các phép biến đổi sơ cấp biến hệ phương trình đã chò thành hệ phương trình tương đương. Đối với một hệ phươữg trình tuyến tính ta quan tâm tới hai câu hqi sau: 1. Khi nào hệ có nghiệm và có bao nhiêu nghiệm? 2. Tìm nghiệm của hệ như thế nào? Đầu tiên chúng ta nghiên cứu câu hỏi thứ hai: phương pháp thực hành để giải hệ phương trình tuyến tính. Phương pháp khử dần các ẩn: Sử dụng phép biến đổi sơ cấp đối với hệ phương trình đã cho, ta lần lượt loại ẩn Xi ra khỏi mọi phương trình kể từ phương trình thứ hai trâ đi nếu hệ số an khác không. Sau đó loại ẩn x2 ra khỏi mọi phương trình, trừ phương 34 trình thứ hai, nếu hệ số của x2 khác không... Quá trình tiếp tục chừng nào còn có thể. Bằng cách như vậy, ta chuyển hệ phương trình đã cho về hệ phương trình tương đương với nó. Đối với hệ phương trình mới này, ta dễ dàng có thể chỉ ra hệ vô nghiệm, hệ có một nghiệm duy nhất hay hệ có vô số nghiệm tuỳ thuộc vào các trưòng hợp cụ thể của hệ được xét. Trong tính toán thực hành, để thực hiện phương pháp khử dần, ta chỉ cần viết ma trận mỏ rộng [A I b], sau đó thực hiện các phép biến đổi sơ cấp trên các hàng của ma trận biến đổi, sao cho các phần tử nằm ngoài đường chéo đều trỏ nên bằng 0. Ví dụ 1.6. Giải hệ phương trình: xt + 3x2 + 4x3 = 25 ' 2xỵ + 9x2 +14x3 - 74 X1 + 7X2 + 14x3 = 61 Lập ma trận mở rộng và biến đổi p r 13 4 25 13 4 25 10-2 1 2 9 14 74 -> 0 3 6 24 -> 0 12 8 1 7 14 61 0 4 10 36 0 0 2 4 1 0 0 5 > 0 1 0 4 0 0 1 2 Từ ma trận đầu, lấy hàng thứ nhất nhân với -2 rồi cộng vào hàng hai, hàng thứ nhất nhân với -1 rồi |CỘng vào hàng thứ ba, ta được ma trận thứ hai. ơ ma trận thứ hai-, lây hàng hai nhân với -1 rồi cộng vào hàng thứ nhất, chia hàng thứ hai cho 3, sau đó nhân với -4 rồi cộng vào hàng 35 thứ ba ta được ma trận thứ ba. ở ma trận thứ ba, ta lấy hàng ba cộng vào hàng thứ nhất, lấy hàng thứ ba nhân vởi -1 rồi cộng vào hàng thứ hai, chia hàng thứ ba cho 2, ta nhận được ma trận thứ tư, ứng với hệ = 5 = 4 = 2 Như vậy hệ có một nghiệm duy nhất XT = (5, 4, 2) Ví dụ 1.7. Giải hệ phương trình xx + 3x2 + 4x3 = 25 2xx + 9x2 +14x3 = 74 X! + 6x2 + 10x3 = 36 Lập ma trận mở rộng và thực hiện các phép biến đổi sơ cấp trên các hàng của ma trận p13 4 25 13 4 25 10-2 1 2 9 14 74 -> 0 3 6 24 -> 0 12 8 16 0 36 0 3 6 11 0 0 0 - 13 Lây hàng một của ma trận đầu nhân với -2 rồi cộng vào hàng hai, lấy hàng một nhân với -1 rồi cộng vào hàng ba, ta được ma trận thứ hai. Trong ma trận thứ hai, ta lấy hàng hai nhân với -1 rồi cộng vào hàng một và ba, sau đó chia hàng hai cho 3 ta được ma trận thứ ba, ứng với hệ: -2x3 = 1 + 2x3 = 8 0 = -13 36 Hệ này vô nghiệm, nên hệ phương trình đã cho vô nghiệm. Ví dụ 1.8. Giải hệ phương trình X! + 3x2 + 4x3 = 38 ' 2xỵ + 9x2 + 14x3 = 74 xx + 6x2 + 10x3 = 36 Lập ma trận mỏ rộng và thực hiện các phép biến đổi sơ cấp trên các hàng của ma trận như sau: —13 4 38 13 4 38’ 10-2 40 2 9 14 74 -> 0 3 6 -2 —> 0 12 -^3 1 6 10 36 0 3 6 -2-, 0 0 0 0 ở ma trận thứ nhất, ta nhân hàng thứ nhất với -2, với -1 rồi cộng vào hàng thứ hai, thứ ba, ta nhận được ma trận thứ hai. ở ma trận thứ hai, ta lấy hàng hai nhân với -1 rồi cộng vào hàng một và ba sau đó lấy hàng hai chia cho 3, ta nhận được ma trận thứ ba, ứng với hệ xx - 2x3 = 40 x2 + 2x3 = -^3 0 =0 Phương trình thứ ba loại khỏi hệ. Từ hai phương trình đầu ta có: xx = 40 + 2x3 x2 = -2/3 - 2x3 ở đây x3 có thể nhận giá trị tuỳ ý và như vậy trong trưồng hợp này hệ có vô số nghiệm. Nghiệm tổng quát của hệ là: XT =[40+2x3; -2/3 -2x3; x3], Vx3 37 Ví dụ 1.9. Giải hệ phương trình xx + 3x2 + 4x3 + 8x4 + 6x5 = 25 • 2xj + 9x2 + 14k3 + 28x4 + 12x5 = 74 xx + 7x2 + 14x3 + 26x4 + 10x5 - 61 Thành lập ma trận mỏ rộngvà thực hiện các phép biến đổi sơ cấp trên các hàng của ma trận, sau ba bưởc ta được: 1 3 4 8 6 25 1 3 4 8 6 25 2 9 14 28 12 74 -> 0 3 6 12 0 24 1 7 14 26 10 61 0 4 10 18 4. 36 1 0-2-4 6 1 10 0-2 10 5 -> 0 12 4 0 8 -> 0102-4 4 0 0 2 2 4 4 0 0 11 2 2 ma trận thứ tư ứng với hệ - 2x4 + 10x5 = 5 + 2x4 - 4x5 = 4 + x4 + 2x5 = 2 Từ các phương trình trên ta chuyển x4, x5 sang vế phải làm ẩn tự do, chúng ta nhận được xx = 5 + 2x4 - 10x5 x2 = 4 - 2x4 + 4x5 x3 = 2 - x4 - 2x5 gán cho x4, x5 các giá trị tuỳ ý, chúng ta sẽ nhận được vô sô nghiệm của hệ Nghiệm tổng quát của hệ: XT = [5+2x4-10x5, 4-2x4+4x5, 2-x4-2x5; x4; X5J, Vx4, Vx5 38 Chú ý: Phương pháp khử dần các ẩn không nhất thiết phải bắt đầu từ ẩn Xi và cũng không nhất thiết với ba ẩn đầu tiên như các ví dự xét ỏ trên. Trong các ví dụ đã xét chúng ta thấy rằng đối vởi một hệ phương trình tuyến tính có thể vô nghiệm, có thể có một nghiệm duy nhất hoặc có thể có vô số nghiệm, ở phần sau ta sẽ thấy trong chứng minh đối với một hệ phương trình tuyến tính tổng quát, cũng chỉ xẩy ra một trong ba khả năng đã nói ở trên. Nếu kết quả cuối cùng của phương pháp khử dần sau khi đã loặi đi các phương trình thừa nếu có, ta chuyển hệ đã cho về hệ tương đương gồm h phương trình độc lập, (h véctơ hàng tương ứng là độc lập tuyến tính), h < n. Trong hệ này có h ẩn (được gọi là các ẩn cơ sỏ) có thể biểu diễn qua (n - h) ẩn còn lại - gọi là các ẩn ngoài (hay phi) cơ sở. Dạng như vậy của một hệ phương trình tuyến tính được gọi là dạng chính tắc của hệ. Trong dạng này mỗi phương trình của hệ chứa một và chỉ một ẩn cơ sở. Khi đã chuyển một hệ phương trình về dạng chính tắc thì xem như hệ đã được giải. Đối với các biến phi cơ sỏ ta có thể gán cho chúng những giá trị tuỳ ý và từ đó ta xác định được các giá trị tương ứng của các biến cơ sỏ. Vì hệ có (n - h) biến có thể nhận giá trị tuỳ ý, nên ta nói hệ phương trình tương ứng có (n - h) bậc tự do. - Nếu gán cho các biến phi cơ sỗ các giá trị bằng không, ta sẽ nhận được một nghiệm của hệ. Nghiệm này được gọi là nghiệm cơ sỏ. Trong nghiệm cơ sỏ không có quá h ẩn (số phương trình độc lập tuyến tính) nhận giá trị khác không và ít nhất (n - h) ẩn nhận giá trị không. 39 Nói cách khác nếu trong hệ chính tắc, các số hạng ỏ vế phải đều khác không thì trong nghiệm cơ sở tương ứng có đúng (n -h) ẩn nhận giá trị không và đúng h ẩn nhận giá trị khác không (nghiệm không suy biến). Ngược lại nếu một hay một số sô hạng ở vế phải bằng không, thì trong nghiệm cơ sở tương ứng sẽ có một hay một số ẩn cơ sở nhận giá trị bằng không, tức là sô ẩn với giá trị khác không sẽ nhỏ hơn h (nghiệm suy biến) Một hệ phương trình có thể có nhiều nghiêm cơ sở. Số nghiệm cơ sỏ bằng sô các cách có thể chuyển hệ vê dạng chính tắc, vậy sô' các nghiệm cơ sở không vượt quá sô các cách chọn h ẩn từ n ẩn, tức là không vượt quá 1.12. ĐỊNH LÝ TỒN TẠI NGHIỆM CỦA HỆ PHƯƠNG TRÌNH TUYẾN TÍNH Ta viết hệ phương trình dưới dạng ma trận hoặc gọn hơn AX = b (1.4a) Rõ ràng việc giải hệ phương trình tuyến tính tương đương với việc biểu diễn véctơ b dưới dạng tổ hợp tuyến tính của các véctơ hệ sô của các ẩn. 40 Giả sử hạng của ma trận các hệ* sô' bằng h. Chúng ta gắn vào ma trận này cột hệ sô ở vê phải, ta sẽ nhận được ma trận mở rộng A = [A I b]. Khi thêm vào một cột hiển nhiên hạng của ma trận không thể giảm. Hạng của ma trận mở rộng sẽ bằng hạng của ma trận A nếu véctơ gắn thêm vào là tổ hợp tuyến tính của các véctơ hệ sô, hoặc tăng lên một nếu véctơ gắn thêm vào không có thể biểu diễn dưới dạng tổ hợp tuyến tính của các véctơ hệ số. Từ đây chúng ta trực tiếp suy ra định lý về điều kiện tồn tại nghiệm của hệ phương trình tuyến tính. Hệ phương trình tuyến tính có nghiệm nếu ma trận các hệ sô và ma trận mỏ rộng có hạng bằng nhau. Hệ vô nghiệm nếu hạng của ma trận mở rộng lởn hơn hạng của ma trận các hệ số. Nếu hệ phương trình có nghiệm, câu hỏi đặt ra là có bao nhiêu nghiêm. Để trả lời câu hỏi này chúng ta giả sử rằng ma trận các hệ số A và ma trận mở rộng [A I b] của hệ phương trình Ax = b có cùng hạng bằng h, và như vậy hệ có nghiệm. Bằng cách đánh số lại các ẩn để h cột đầu tiên tạo nên hệ độc lập tuyến tính. Vì theo giả thiết thì tất cả các cột của ma trận A và véctơ â vế phải có thể biểu diễn dưới dạng tổ hợp tuyến tính của h cột đầu tiên của ma trận A một cách duy nhất, nên ta có thể viết: A — [A1; A2,....,Ah].[e1, e2,....eh, ejj +1,.... , enJ (1.5) b = [Aj, A2,....,Ah].C hoặc gọn hơn A = Ạj [Ih I D] 41 b = Ạxc (1.5a) ở đây Ax là ma trận cấp (m.h) lập bỏi h cột đầu tiên của ma trận các hệ số, Ijj là ma trận đơn vị cấp h, D là ma trận cấp h X (n - h), c là véctơ cột h chiều. Hệ phương trình tuyến tính có thể viết dưôi dạng Ai [Ih I D].x = Ại c (1.6) Vì b có thể biểu diễn tuyến tính qua các véctơ Ax, A2, ..., Ah một cách duy nhất, nên từ hệ thức trên ta suy ra [Ih I D]X = c Và như vậy, chúng ta đã có nghiệm của hệ (hệ phương trình đã đưa về dạng chính tắc). Ta tách véctơ X thành hai phần X?) - chứa h thành phần đầu tiên và x^) - chứa n - h thành phần còn lại. Chúng ta nhận được [Ih I D) -c x(2) Và sau khi nhân ra ta được Ihx(1) + dx(2) = c *1 x2 Vì Ihx(1) = x(1) = xh Và như vậy: 42 = c - DX(2) (1.7) . xh . Ta cho các thành phần của x(2) những giá trị tu.ỳ ý, chúng ta sẽ nhận được các nghiệm khác nhau của hệ Từ (1.7) chúng ta thấy rằng, nghiệm của hệ phương trình là duy nhất nếu h = n, tức là nếu hạng của ma trận các hệ số (và cả ma trận mỏ rộng) bằng sô ẩn (trong trường hợp này x(2) không có). Nếu h < n hệ sẽ có vô số nghiệm. Ta trở lại ví dụ 1.9 ta có ba véc tơ hệ số đầu tiên độc lập tuyến tính và ma trận các hệ số có hạng bằng ba (lớn hơn là không thể vì chỉ có ba hàng), ở đây, tất cả các cột của ma trận mở rộng đểu có thể biểu diễn tuyến tính qua ba véctơ cột đầu tiên. Cụ thể 1 3 4 1 0 0 -2 10 2 9 14 0 1 0 2 -4 A 1 7 14 0 0 1 1 2 Ái I 3 D 1 3 4 5 b = 2 9 14 4 1 7 14 2 Hệ phương trình trong ví dụ 19, có thể viết dưới dạng 43 10 0 0 10 0 0 1 Và từ đó: X1 x2 x3 -2 10 2 -4 1 2 5 4 - .2, -2 10 2 -4 1 2 x4 x5 Đây chính là nghiệm đã tìm khử dần. được bằng phương pháp Đ,ến đây chúng ta có thể tóm tắt như sau: Hệ m phương trình tuyến tính n ẩn 1. Có nghiệm nếu hạng của ma trận các hệ số và hạng của ma trận mỏ rộng bằng nhau a. Có một nghiệm duy nhất, nếu hạng này bằng số ẩn n, tức là nếu các cột của ma trận các hệ số độc lập tuyến tính; b. Có vô sô nghiệm nếu hạng của ma trận các hệ sô nhỏ hơn số ẩn; 2. Không có nghiệm nếu hạng của ma trận mở rộng lớn hơn hạng của ma trận các hệ sô Chúng ta đã thấy, nhờ phương pháp khử dần các ẩn, ta có thể xác định trường hợp nào trong các trường hợp trên sẽ xẩy ra. Từ định lý tồn tại nghiệm của hệ phương 'trình tuyến tính có thể suy rạ các kết quả sau: 44 a. Hệ n phương trình tuyến tính n ẩn có một nghiệm duy nhất khi và chỉ khi nếu ma trận các hệ số không suy biến. b. Hệ n phương trình tưyến tính thuần nhất n ẩn bao giò cũng có nghiệm và: - Chỉ một nghiệm X = 0 (nghiệm tầm thường) nếu ma trận các hệ số không suy biến. - Có cả những nghiệm không tầm thường nếu ma trận các hệ số suy biến. 1.13. BIẾN ĐỔI VÉCTƠ ở mục 1.4, chúng ta đã biết rằng mỗi véc tơ đều có thể biểu diễn dưới dạng tổ hợp tuyến tính của các véctơ của cơ sở bất kỳ. Đối với nhiều trường hợp, ta cần phải xác định toạ độ của véctơ trong một cơ sở đã cho hoặc xác định sự thay đổi toạ độ của véctơ, tức là véctơ sẽ thay đổi như thế nào nếu cơ sỏ thay đổi. Trong thực hành, các phép biến đổi được tiến hành theo trình tự từng bước, ỏ mỗi bước ta chỉ thay một véctơ trong cơ sở. Bằng một dẫy các phép biến đổi cơ bản như vậy, có thể chuyển từ một cơ sỏ đã cho sang một cơ sỏ bất kỳ. Chúng ta giả sử rằng các véctơ ai> a2,...,an tạo nên cơ sỏ của không gian ơ cờ lít n chiều En. Véctơ khác không b có thể biểu diễn tuyến tính qua các véctơ này dưới dạng: b = b^a^ + b2a2 +.... + bjçajç + .... + bnan (1.8) 45 (bj, b2, ...,bn là các thành phần của véc tơ b trong cơ sỏ đã cho). ở đây vấn đề đặt ra là, ta có thể thay một véc tơ nào đó trong cơ sở bỏi véc tơ b và với sự thay đổi này toạ độ của các véc tơ khác sẽ thay đổi như thê nào trong cơ sỏ mới. - Ta có thể thay véc tơ a¡ nào đó trong cơ sở bởi véc tơ b, để được một cơ sỏ mới nếu hệ số bị tương ứng khác không. Để định ý, ta giả sử bk * o Khi đó hệ véc tơ a1( a2, ..., ak_i, b, ak+1, ..., an tạo nên một cơ sỏ mới của En. Thật vậy, nếu hạng của hệ véc tơ này nhỏ hơn n, điều này có nghĩa là véc tơ b có thể biểu diễn tuyến tính qua (n-1) véc tơ ai> a2,...,ak.1, ak+1,...,an và như vậy mâu thuẫn với giả thiết bk * 0 Để cho gọn, ta nói véc tơ ak bị loại ra khỏi cơ sở là véc tơ loại, véc tơ b được đưa vào cơ sở gọi là véc tơ đưa vào. Toạ độ bk gọi là phần tử trục của phép biến đổi. Bây giờ ta xác định tọa độ của véc tơ c bất kỳ trong cơ sỗ mới. Trong cơ sở cũ ta có: c = c^aj + c2a2 +... + ckak +...+ cnan ta thay ak bởi biểu thức „ _ 1 k „ „ lu 1 , k “ _ bv bl &1 “ bv b2 a2 -• • • + bl, b _ K bn K K K K 46 (suy từ 1.8), ta sẽ được: ct ( \ al +ck k c2 “ u b2 l bk ) định. k K 7 Phép biến đổi sơ cấp này về thực chất giống như một bước của phương pháp khử dần. Để dễ nhận biết nếu ta viết phép biến đổi dưới dạng bảng. 47 Trong bảng 1.2a, ghi toạ độ của các véc tơ b và c trong cơ sở xuất phát, trong bảng 1.2b, ghi toạ độ của các véc tơ này trong cơ sâ mới, ở đó véc tơ ak được thay bởi véc tơ b. Trong cơ sỏ này, véc tơ b được chuyển thành véc tơ đơn vị. Để minh hoạ, ta tiến hành biến đổi hệ véc tơ các hệ số trong ví dụ 1.9. Bảng 1.3a Cơ sở ei ®2 e3 ai a2 83 a4 a5 b ei 1 0 0 1 3 4 8 6 25 e2' 0 1 0 2 9 14 28 12 74 e3 0 0 1 1 7 14 26 10 61 Trong bảng 1.3a, ta ghi ở phía trước cơ sở xuất phát - đó là hệ ba véc tơ đơn vị. Ta thay véc tơ e} trong cơ sở bỏi véc tơ ax. Sự thay đổi này là có thể vì an = 1 * 0, ta đựơc bảng 1.3b. Bảng 1.3b Cơ sở ei *2 e.3 ai a2 a3 a4 a5 b a1 1 0 0 1 3 4 8 6 25 e2 -2 1 0 0 3 6 12 0 24 e3 -1 0 1 0 4 10 18 4 36 Kết quả nhận được giống như bước một của phương pháp khử dần. Chúng ta lần lượt đưa vào cơ sỏ (trong bảng 1.3c và 1.3d) véc tơ a2 thay cho e2 và sau đó a3 thay cho e3: 48 Bảng 1.3c Cơ sở ei e2 e3 31 a2 a3 a4 a5 b 31 3 -1 0 1 0 -2 -4 6 1 a2 -2/3 1/3 0 0 1 2 4 0 8 e3 5/3 -4/3 1 0 0 2 2 4 4 Bảng 1.3d (1.10) Cơ sở ei ?2 e3 31 a2 33 a4 a5 b 31 14/3 -7/3 1 1 0 0 -2 10 5 a2 -7/3 5/3 -1 0 1 0 2 -4 4 a3 5/6 -2/3 1/2 0 0 1 1 2 2 Ba lần thực hiện các phép biến đổi sơ cấp hoàn toàn trùng với ba bưâc của phương pháp khử dần mà ta đã làm ở ví dụ 1.9. ở đó, ta không ghi các biến mà chỉ có các véc tơ tương ứng. Trong các bảng trên, ta đưa thêm cơ sở đơn yị và biến đổi nó theo cơ sỏ thay đổi. Mỗi bước của phương pháp khử dần, có thể minh hoạ như thực hiện các phép biến đổi sơ cấp hệ thống véc tơ hệ số và véc tơ hệ số ỏ vế phải, tức là đối với ma trận mở rộng. Vê' thực chất, việc biến đổi hệ véc tơ không phải chỉ bằng dẫy các phép biến đổi sơ cấp mà chúng ta có thể thực hiên bằng cách khác. Chúng ta nhân về phía trái của mỗi véc tơ một ma trận xác định (tức là ma trận của phép biến đổi). - Đó là ma trận nghịch đảo của cơ sỏ đã cho. Trong ví dụ 19 ba véc tơ ai, a2, a3 tạo nên cơ sỏ. Ma trận nghịch 49 đảo của cơ sở này chính là ma trận của phép biến đổi - đó là ma trận: 14/g - 7/g 1 - 7/3 5/3 - 1 - &3 Vg Nếu ta nhân ma trận này về bên trái với các véc tơ trong bảng 1.2a, chúng ta sẽ trực tiếp nhận được hệ (1.10) Trong mục 1.11, chúng ta đã nghiên cứu cách giải hệ phương trình tuyến tính. Chúng ta đã chứng minh rằng bằng phương pháp khử dần có. thể chuyển hệ phương trình về dạng chính tắc, ở đó có thể trực tiếp tìm được nghiệm cơ sở. Việc chuyển hệ phương trình về dạng chính tắc có nghĩa là biến đổi ma trận mỏ rộng của hệ sao cho ma trận các hệ sô chứa cơ sở đơn vị (tức là tất cả các cột của ma trận được biểu diễn theo cơ sỏ đã chọn). Nghiệm cơ sỏ chính là khai triển (biểu diễn)của véc tơ vê phải qua cơ sở này. Trong quy hoạch tuyến tính, chúng ta sẽ dùng đến các nghiệm cơ sỏ cũng như việc chuyển từ một nghiệm cơ sỏ này sang một nghiệm cơ sỏ khác - Thực chất là việc thay đổi cơ sở, chúng ta có thể thực hiện được bởi các phép biến đổi sơ cấp, tức là lần lượt thay một trong các véc tơ của cơ sỏ. Như vậy từ (1.10), ta suy ra một nghiệm cơ sỏ [5,4,2,0,01 với các biến cơ sở là xx, x2, x3 hoặc với các véc tơ ax, a2, a3 trong cơ sỏ. Lần lượt thay các véc tơ này bởi các véc tơ khác, chúng ta sẽ nhận đựợc các nghiệm cơ sỏ khác. Chẳng hạn nếu chúng ta thay.ax bồi a5, chúng ta sẽ đưa x5 vào nghiệm cơ sở thay xx. .Phép biến đổi tương ứng của 50 ma trận (1.10) có thể thực hiện nhò phương pháp khử dần, chúng ta nhận được Bảng 1.3e 31 a2 33 a4 a5 b 0,1 0 0 -0,2 1 0,5 0,4 1 0 1,2 0 6 -0,2 0 1 1,4 0 1 Cho ta nghiệm cơ sở [0; 6; 1; 0; 0,5]. Khi giải hệ phương trình tuyến tính, có thể gặp trưòng hợp đặc biệt: Trong một nghiệm cơ sỏ nào đó có một hoặc một số ẩn cơ sở nhận giá trị không. Nói cách khác, véc tơ vế phải có thể biểu diễn tuyến tính qua một số véc tơ hệ số, số này nhỏ hơn hạng của hệ. Trong những trường hợp như vậy, ta nói bài toán suy biến. Chẳng hạn, nếu chúng ta thay đổi một số hạng ỏ vế phải trong hệ phương trình cuối (ví dụ 1.9) từ 61 sang 57, chúng ta nhận được hê phương trình xr + 3x2 + 4x3 .+ 8x4 + 6x5 = 25 • 2xx + 9x2 + 14x3 V 28x4 + 12x5 = 74 xx + 7x2 + 14x3 + 26x4 + 10x5 = 57 Hệ này suy biến. Hệ có hạng giống như hệ đã xét bằng 3 (vì ma trận các hệ số không thay đổi), nhưng véc tơ vê phải có thể biểu diễn tuyến tính qua hai véc tơ cột hệ sô đầu tiên, vì: 51 1 3 25 2 + 8 9 = 74 1 7 57 Giải hệ này bằng phương pháp khử dần, sau hai bước chúng ta nhận được hệ X! - 2x3 - 4x4 + 6x5 = 1 ■ x2 + 2x3 + 4x4 - 8 2x3 + 2x4 + 4x5 = 0 ở bưởc sau, khử bất cứ ẩn nào, ta cũng nhận được nghiệm [1, 8, 0, 0, 0] chính là nghiệm cơ sở với một số không đầy đủ các thành phần khác không. Sau này chúng ta sẽ thấy tính suy biến sẽ gây khó khàn nhất định, khi giải các bài toán quy hoạch tuyến tính. 1.14. TẬP LỒI Tập hợp các điểm trong mặt phẳng hoặc trong không gian được gọi là tập lồi nếu đoạn thẳng nôi hai điểm bất kỳ của tập hợp này cũng thuộc nó. Ví dụ: Toàn bộ mặt phẳng, góc phần tư thứ nhất, tập trông, tập hợp chỉ có một điểm, tập các điểm của hình tròn, tam giác,hình viên phân... là những tập lồi. Tập hợp các điểm của hình vành khăn hoặc đa giác như trong hình 1.1 không phải là những tập lồi vì trong những tập hợp này ta có thể tìm được hai điểm để đoạn thẳng nối chúng không hoàn toàn nằm trong tập hợp. Tương tự trong không gian ba chiều hình cầu, hình nón, hình trụ, ... là những tập lồi nhưng phần nằm giữa hai hình cầu không phải tập lồi. 52 Hình 1.1 Để có thể tổng quát hoá khái niệm lồi trong không gian n chiều, ta hãy xét cách xác định đoạn thảng nối hai điểm. Trong mặt phẳng, cho hai điểm ax = [a11,a12] và a2 = [a21, a22l, giả sử điểm b = [b1,b2] bất kỳ nằm trên đoạn thẳng nôi chúng và chia khoảng cách giữa hai điểm theo tỷ sô k : (1-k), vởi 0 < k < 1. Khi đó toạ độ của điểm b có thể biểu diễn dưởi dạng (xem hình 1.2) bi = an + k (a21 - an) = (1 - k)ajj + ka2i b2 = a12 - k (a12 - a22) = (1 - k)a12 + ka22 (1.11) hoặc gọn hơn b = (1 - k) a! + ka2. Nói cách khác b là tổ hợp lồi của ax và a2 (mục 1.3) Ta dễ dàng chứng minh điều ngược lại: mỗi tổ hợp lồi của hai điểm ai và a2, tức là mỗi điểm (1 - k)ax +ka2 với 0 < k < 1 nằm trên đoạn thẳng nối hai điểm này. 53 Hình 1.2 Nếu cho k nhận tất cả các giá trị từ 0 đến 1 ta sẽ nhận được tất cả các điểm trên đoạn thẳng nối ax và a2. Như vậy tập hợp các tổ hợp lồi của hai điểm là đoạn thẳng nôi hai điểm này. Tương tự có thể chứng minh đối với các điểm trong không gian ba chiều. Nếu cho k nhận tất cả các giá trị từ - 00 đến + 00 thì tập hợp các điểm (1 - k)a! + ka2 Chính là đường thẳng xác định bởi các điểm ax và a2 Nếu cho k chỉ nhận các giá trị không âm hoặc không dương thì ta được nửa đưòng thẳng. Dựa trên cơ sở cách biểu diễn đại số này, chúng ta có thể đưa ra khái niệm đoạn, đường thẩng, nửa đường thẳng đối với không gian n chiều. 54 Cho hai điểm ax và a2 của không gian n chiều thì a. Tập hợp của tất cả các tổ hợp lồi của chúng (1 -k)ax + ka2 với 0 < k < 1 gọi là đoạn thảng nốì chúng. b. Tập hợp tất cả các điểm (1 - k)ax + ka2 với -00 < k < +00 là đưòng thẳng xác định bởi ax và a2 - Nếu k chỉ nhận các giá trị không âm thì ta được một nửa đường thẳng đi từ ax qua a2. Trong không gian En, ta nói tập hợp c là lồi nếu hai điểm bất kỳ X, Y thuộc c thì điểm Z = XX +(1- Ầ)Y (trong đó 0 < À < 1 ) cũng thuộc c, tức là nếu c chứa hai điểin nào đó thì chứa cả đoạn thẳng nối hai điểm ấy. Tập hợp lồi được gọi là bị chặn nếu nó không chứa một nửa đường thẳng nào và được gọi là không bị chặn nếu nó chứa ít nhất một nửa đường thẳng. Tập hợp lồi bị chặn cũng có thể định nghĩa như sau: Tập lồi được gọi là bị chặn nếu đối vối mỗi điểm X = [xx, x2, ...,xn] thuộc nó ta có Xj < M (j = 1,2,...,n) với M là một số thực (hữu hạn). Từ định nghĩa tập lồi, ta có thể suy ra: - Giao của một sô bất kỳ các tập lồi là một tập lồi. - Tổng (hoặc hiệu) của hai tập lồi chưa hẳn là một tập lồi. 55 - Điểm cực biên của tập lồi: Điểm X thuộc tập lồi c được gọi là điểm cực biên của nó nếu không tồn tại hai điểm khác nhau X! và x2 thuộc c sao cho: X = AXx + (1-X)X2 với 0 < X < 1 túc là X không nằm trên đoạn thảng nào nối hai điểm thuộc c. Một tập lồi có thể không có điểm cực biên nào, chăng hạn toàn bộ mặt phảng hoặc những điểm trong của một hình tròn (không kể các điểm nằm trên đường tròn) là những tập lồi không có điểm cực biên. Tập lồi có thể có một sô hữu hạn các điểm cực biên (chảng hạn góc phần tư thứ nhất, đa giác lồi) và cũng có thể có vô số điểm cực biên (chẳng hạn tập hợp các điểm của hình tròn thì các điểm nằm trên đường tròn là những điểm cực biên). Một tập lồi bị chặn (giới nội) có một số hữu hạn các điểm cực biên gọi là một đa diện lồi. Các điểm cực biên được gọi là các đỉnh của đa diện. Mối liên hệ giữa các khái niệm tổ hợp lồi và tập lồi được thể hiện qua các định lý sau đây: Định lý 1. Nếu đa diện lồi có m đỉnh ax, a2, ..., am thì mỗi điểm của đa dịên có thể biểu diễn dưới dạng tổ hợp lồi của các đỉnh. Định lý 2. Nếu ta có m điểm ax, a2, ..., am thì tập hợp tất cả các điểm là tổ hợp lồi của các điểm này tạo nên một đa diện lồi, số các đỉnh của nó nhiều nhất là bằng sô các điểm a1,a2,...,am 56 Một đa diện lồi như vậy được gọi là bao lồi của các điểm a1; a2,..„ am. Chẳng hạn bao lồi của hai điểm là đoạn thảng nôi chúng. Bao lồi của ba điểm là một tam giác nếu ba điểm không nằm :i'ên một đường thẳng. Đối với m = 2 (tức là đối với đoạn thẳng) là hiển nhiên do trực tiếp suy ra từ định nghĩa đoạn thẳng. Ta chứng minh bằng phương pháp quy nạp, tức là giả sử định lý đúng với các đa diện có m đỉnh, ta chứng minh định lý đúng đối với các đa diện có m + 1 đỉnh. Giả sử chúng ta có đa diện lồi A vỡi m đỉnh a1; a2, ..., am và một điểm b bất kỳ của đa diện này, có thể biểu diễn dưới dạng: b = k1a1 + k2a2 + ... + kmam (1.12) trong đó kj > 0 (i = 1,2,...,m) và ki + k2 + :.. + km = 1 Bằng cách thêm vào các điểm khác nữa từ đa diện A ta lập đa diện lồi A’ với m + 1 đỉnh a1; a2,..., am, am+1. Vì đa diện A’ có thêm một đỉnh am +1 so với đa diện A, nên mỗi điểm cuả đa diện A’ phải nằm trên đoạn thẳng nối đỉnh am + ! và một điểm nào đó của đa diện A. Như vậy đối với một điểm c bất kỳ của đa diện A’ phải thoả mãn c — (1 - km + x)b + km + Ị am + I ở đây b là điểm của đa diện A và 0 < km+1 < 1 Thay biểu thức của b từ (1.12) vào ta được c = (l-km+1) Mx + (l-km+1)k2a2 + ... + (l-km+1)kmam + km+lam+l 57 Mọi hệ số trong biểu thức cuối không âm vì kj > 0 (i = l,2,...,m + 1) và (1 - km+1) > 0 Tổng của chúng bằng một vì (1 * km+^)k^ "^111+1)^2 +•••+ (1 ■ km+2)krn km+i - (1 - km+iXkx + k2 + ... +kj + = 1k^! + k m+1 = 1 Điều này có nghĩa là, một điểm c bất kỳ của đa diện lồi A’ có thể biểu diễn dưới dạng tổ hợp lồi của các đỉnh của nó. Tương tự bằng phương pháp quy nạp hoàn toàn, ta có thể chứng minh định lý hai. 58 CHƯƠNG II BÀI TOÁN QUY HOẠCH TUYÊN TÍNH, PHƯƠNG PHÁP ĐƠN HÌNH 2.1 ĐỊNH NGHĨA BÀI TOÁN QUY HOẠCH TUYÊN TÍNH DẠNG TổNG QUÁT, DẠNG CHUẨN và DẠNG CHÍNH TẮC Định nghĩa 2.1. Bài toán qui hoạch tuyến tính dạng tổng quát là bài toán tìm cực đại (cực tiểu) của một hàm tuyến tính, xác định trên tập hợp nghiệm của một hệ thống hỗn hợp các phương trình và bất phương trình tuyến tính. z (X) =L Cj-Xj -> max (min) (2.1) j=i < bj, i = 1,2,...,s (2.2) j=l - bi , i = s + 1, ..., s + t (2.3) j=l Hàm Z(X) được gọi là hàm mục tiêu, mỗi phương trình hoặc bất phương trình trong hệ điều kiện gọi là một ràng buộc. 59 Bài toán (2.1) - (2.3) có thể viết dưởi dạng ma trận như sau: Z(X) = CTX —> max (min) (2. la) AX < b (2.2a) trong đó A = [aijj là ma trận cấp (s + t).n CT = (Cx, c2,..., Cn) là véc tơ hàng n chiều, bi ^2 là véc tơ cột s + t chiều, bs+t *1 «2 X = là véc tơ cột n chiều. Xn dấu ế có nghĩa là s thành phần đầu tiên của véc tơ điều kiện (2.2a) mang dấu bất đẳng thức và t thành phần sau cùng mang dấu đẳng thức. Định nghĩa 2.2. Bài toán trong đó cần tìm cực đại (cực tiểu) của hàm (2.1) với điều kiện (2.2) và điều kiện 60 Xj > 0, j = 1,2,..., n (2.4) gọi là bài toán quy hoạch tuyến tính dạng chuẩn. Dạng ma trận của bài toán này Z(X) = CTX -> max (2.1’) AX < b (2.2’) X > 0 (2.4’) Định nghĩa 2.3. Bài toán cần tìm cực đại (cực tiểu) hàm (2.1) với các điều kiện (2.3) và (2.4) gọi là bài toán quy hoạch tuyến tính dạng chính tắc. Dạng ma trận của bài toán chính tắc Z(X) = CTX -> max (2.1’) AX = b (2.3’) X > 0 Định nghĩa 2.4. Một véc tơ X = [xx, x2, ..., xn]T thoả mãn mọi ràng buộc của bài toán quy hoạch tuyến tính được gọi là một phương án của nó. Định nghĩa 2.5. Phương án X = [xlỹ x2, ..., xn]T làm cực đại (cực tiểu) hàm (2.1), được gọi là phương án tối ưu hay nghiệm tổì ưu của bài toán quy hoạch tuyến tính. 61 Định nghĩa 2.6. Các cột Aj (j = 1,2, ..., h) của ma trận A gội lă các véc tơ điều kiện và b gọi là véc tờ ràng buộc của bài toán quy hoạch tuyến tính. Định nghĩa 2.7. Bài toán quy hoạch tuyến tính được gọi là có phương án nếu tập các phương án của nó không trống và được gọi là giải được nếu tập phương án tốỉ ưu của nó không trống. Chú ý: Khi cẩn thiết ta có thể chuyển bài toán quy hoạch tụyến tính tổng quát về dạng chính tắc bằng cách đưa vào các biến phụ không âm để chuyển các bất phương trình về dạng phương trình (hệ số của các biến phụ trong hàm mục tiêu bằng 0) và thây biến không ràng buộc về dấu bởi hiệu của hai biến không ,âm. Dưới đây ta xét một số ví dụ đơn giản. Ví dụ 2.1. Chuyển về dạng chính tắc bài toán saú: X| + x2 —> max Xi - x2 < 1 ’ 2xj + x2 - 2 xt > 0 Để đưa ràng buộc thứ nhất về dạng đẳng thức ta cộng vào vế trái ràng buộc này biến không âm x3 (x3 > 0).Tầ thay biến x2 bỏi hiệu của hai biến không âm: x2 = x2’. - x2" . ở đây x2’, x2" > 0 Sau các biến đổi trên bài toán đã cho viết dưói dạng chính tắc như sau: 62 X1 + x2’ ■ x2” “* max xx - x’2 + x”2 + x3 = 1 2xx + x’2 - x”2 =2 Xj > 0 , x2’ > 0 , x2” > 0, Xg > 0 Ví dụ 2.2. Chuyển bài toán Xi + 2x2 - 2x3 -> max X1 + x2 - x3 < 1 1 2xx + ax2 + x3 = 2 x3 > 0 về dạng chính tắc Giải. Đưa vào biến phụ không âm x4 (x4 > 0) và viết ràng buộc thứ nhất dưới dạng đẳng thức xx + x2 - x3 + x4 = 1 Ta khử trong hệ phương trình hai biến X1 và x2 không có ràng buộc về dấu Cụ thể ta xét hệ x4 + x2 - x3 + x4 = 1 2xx + ax2 + x3 =2 ở đây có thể xảy ra hai trường hợp: Trường hợp 1. Nếu a * 2.Các biến xx và x2 biểu diễn duy nhất qua x3 và x4: X1 = 777^ [ 2 - a - (a + 1) x3 + ax4] 63 *2 = 2^ í3-^"2-^) Sau khi thay các giá trị này vào hàm mục tiêu, bài toán có dạng ( \ ( A 1+ a 4- a I2- aj x3 - <2- aj -> max x3 > 0 , x4 > 0 Trường hợp 2. Nếu a = 2. Trong trưòng hợp này không thể biểu diễn x4 và x2 qua x3 và x4 nhưng có thể khử một trong hai biến này, chẳng hạn x4: xx = 1 - x2 + x3 - x4 Nếu thay biểu thức đổi với x4 vào hàm mục tiêu và ràng buộc còn lại thì bài toán có dạng: 1 + x2 - x3 - x4 -> max 3x3 - 2x4 = 0 x3 > 0 , x4 > 0 Bài toán được viết dưới dạng chính tắc, biến x2 có mặt trong hàm mục tiêu với hệ số dương nhưng không có mặt trong các ràng buộc. Điều này có nghĩa bài toán đã cho không giải được. 2.2 MINH HOẠ HÌNH HỌC BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Dưới đây đưa ra minh hoạ hình học cho bài toán quy hoạch tuyến tính khi số biến bằng hai. Tuy nhiên các kết 64 quả thu được có thể mỏ rộng cho trường hợp bài toán có số biến bất kỳ. Khi n = 2 hàm mục tiêu có dạng C]Xj + và tập phương án sẽ là một đa giác lồi M (McR2) - là giao của các đường thẳng tạo bởi các ràng buộc cho dưới dạng phương trình và các nửa mặt phẳng tạo bổi các ràng buộc cho dưới dạng bất phương trình. Phương trình cpq + C2X2 = d (a) xác định một đường thẳng trong R và véc tơ CT = [Ci, c2] là véc tơ chỉ phương của đưòng thẳng. Khi giải bài toán max, ta tịnh tiến đường thẳng (a) song song với chính nó để tìm giá trị lớn nhất của d trên M (nếu có). Lấy một điểm X bất kỳ thuộc M, vế qua X một đường thẳng song song với (a) và tịnh tiến nó theo hướng tăng của d. Có thể xảy ra hai tình thế: 65 a. Có vị trí của đường thẳng song song với (a) có tính chất sau: Nếu ta tiếp tục tịnh tiến nó theo hướng tăng thì tập M và đưòng thẳng sẽ không có điểm chung (hình 2. la, b). Trong trường hợp này, bài toán đã cho là giải được. b. Ta có thể tịnh tiến đưòng thẳng (a) theo hướng tăng mãi thì tập M và đường thẳng vẫn có điểm chung. Trong trường hợp này, hàm mục tiêu không bị chặn trên trong tập phương án của bài toán (hình 2.1c) tức là bài toán không giải được. 2.3 PHƯƠNG ÁN cực BIÊN. CÁC TÍNH CHẤT CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH Ta đã biết, mọi bài toán quy hoạch tuyến tính đều có thể chuyển về dạng chính tắc nên trong các lập luận mà chúng ta trình bày dưới đây chỉ cần xét đối vởi bài toán dạng chính tắc. Cụ thể xét bài toán: Z(X) = CTX max (2.5) 66 AX = b (2.6) ■ X > o (2.7) trong đó CT là véc tơ hàng n chiều - véc tơ hệ số của các ẩn trong hàm mục tiêu A là ma trận hệ số của các ẩn có cấp m.n X là véc tơ cột n chiều - véc tơ ẩn b là véc tơ cột m chiểu - véc tơ ràng buộc Ta giả thiết rằng m < n và ma trận A có hạng bằng m, tức là hệ (2.6) có m phương trình độc lập tuyến tính. Ta biết rằng nếu hệ (2.6) có một số phương trình thừa thì bằng phương pháp khử dần các ẩn, ta có thể loại đi các phương trình thừa. Điều kiện (2.6) có thể viết dưới dạng véctơ: XiAi + x2A2 +....+ xnAn = b (2.6a) ở đầy Aj (j = 1, 2,..., n) là các véctơ cột của ma trận A Định nghĩa 2.8. Phương án X = [xn x2,...., xn]T của bài toán (2.5) - (2.7) được gọi là phương án cực biên nếu các véc tơ điều kiện Aj của ma trận A ứng với các thành phần dương của X tạo thành hệ véctơ độc lập tuyến tính. Vì hạng của ma trận A bằng m nên số véc tơ điều kiện Aj độc lập tuyến tính cực đại bằng m, do đó một phương án cực biên bất kỳ có không quá m thành phần duơng và nó tuơng ứng với ít nhất một hệ véc tơ điều kiện Aj độc lập tuyến tính cực đại. Từ đó ta có định nghĩa sau: 67 Định nghĩa 2.9. Ta gọi một hệ m véc tơ điều kiện {Ạj} độc lập tuyến tính bao hàm hệ thống các véc tơ tương ứng vởi các thành phần dương của phương án cực biên X là cơ sỏ của phương án cực biên ấy, ký hiệu là Aj, trong đó J = {j : Ạj nằm trong cơ sở} - Một phương án cực biên không suy biến có đúng m thành phần dương, m véc tơ Ạj tương ứng với các thành phần duơng -này độc lập tuyến tính nên có một cơ sở duy nhất. - Một phương án cực biên có ít hơn m thành phần dương được gọi là một phương án cực biên suy biến. Đối với nó có thể có nhiều cơ sở khác nhau. - Bài toán được gọi là không suy biến nếu tất cả các phương án cực biên của nó đêu không suy biến. - Khi có một cơ sở của phương án cực biên X, ta gọi các thành phần Xj (j G J) là các thành phần cơ sỏ và các thành phần xk (k Ể J) là các thành phần phi cơ sở hay ngoài cơ sỏ. Đối với phương án cực biên không suy biến thì mọi thành phần cơ sỏ đều dương, còn đối vởi phương án cực biên suy biến thì ít nhất có một thành phần cơ sở bằng 0. Sau đây chúng ta nghiên cứu một số định lý để làm rõ các tính chất của bài toán quy hoạch tuyến tính - Dựa vào đó ta xây dựng thuật toán giải nó. Định lý 2.1. Tập phuơng án của bài toán quy hoạch tuyến tính là một tập lồi với một số hữu hạn các điểm cực biên. 68 Chứng minh. 1. Ta ký hiệu M là tập phương án của bài toán (2.5) - (2.7), ta chứng minh M là một tập lồi. Giả sử Xx và x2 là hai phương án bất kỳ, khác nhau của bài toán, ta có Xi > 0 , AXx = b x2 > 0 , AX2 = b. Lấy X là tổ hợp lồi của Xx và x2: X = aXx + (1 - a)X2 (với 0 < a < 1) Đối với X rõ ràng ta có: X > 0 và AX = AtoXi + (1 - a)X2] = aAXi + (1 - a)AX2 = = ab + (1 - a)b = b Điều đó chứng tỏ X là một phương án của bài toán, tức là X e M và M là một tập lồi. 2. Để chứng minh số điểm cực biên của tập M là hữu hạn, trước tiên ta chứng minh mệnh đề sau: Một phương án của bài toán quỵ hoạch tuyến tính là phương án cực biên khi và chỉ khi nó là điểm cực biên của tập phương án a. Điêu kiện cân. Cho X là một phương án cực biên của bài toán, ta chứng minh nó là một điểm cực biên của M Không làm mất tính tổng quát ta giả sử phương án cực biên X có m thành phần đầu là các thành phần có sở, tức là X = [X|, x2,..., xm, 0,..., 01T 69 trong đó Xj > 0 (j = l,2,...,m) là các thành phần cơ sỏ. Khi đó Aj = {A1( A2,..., Ajjj} là cơ sỏ của phương án nên X1A1 + x2A2 + ... + XmA^ = b Nếu X không phải là điểm cực biên của tập M thì sẽ tồn tại hai điểm khác nhau X’ và X" của M (tức là hai phương án khác nhau của bài toán) sao cho X = kX’ + (1 - k)X’ với 0 < k < 1 Vì các thành phần của X’ và X” không ầm, k và 1 - k là hai số dương nên (n - m) thành phần cuối của X’ và X” cũng phải bằng không giống như (n-m) thành phần cuối của X tức là X’ = [x’j, x’2,....,x’m,0,.....,0]T X” = [X”!, x”2,x”m,0....,0]T Mặt khác do X’ và X” là phương án của bài toán nên X’1A1 + X2A2 +...... + x’nAn = b X”1A1 + x”2A2 +•■••+ x”mAm = b, Nhưng vì hệ Aj (j =l,2,....,m) là cơ sở nên b chỉ có thể khai triển theo m véctơ này một cách duy nhất. Do đó Xj’ = Xj” ( Vj = l,2,...,m) hay X’ = X” = X, điều này mâu thuẫn nên X phải là điểm cực biên của tập lồi M. b. Điều kiện đủ. Cho X là một điểm cực biên của tập M ta chứng minh nó là một phương-án cực biên của bài toán. Giả sử X có k thành phần dương và không giảm tính tổng quát ta giả sử đó là k thành phần đầu tiên dương, 70 các thành phần còn lại bằng 0. Ta chứng minh các véctơ Ax, A2, ....,Ak tương ứng với các thành phần dương tạo nên hệ véctơ độc lập tuyến tính và k < m. Thật vậy, nếu các véctơ Ax, A2,.... ,Ak là phụ thuộc tuyến tính thì sẽ tồn tại các số dx, d2,....,dk, trong đó có ít nhất một số khác không sao cho dxAx + d2A2 dkAk = 0 (2.8) Mặt khác theo giả thiết X e M nên ta có: XXAX + x2A2 +.... + xkAk = b (2.9) Nhân phương trình (2.8) với E > 0, sau đó cộng và trừ vào hai vế của (2.9) ta nhận được: (xx + ed1)A1 + (x2 + ed2)A2 +.... + (xk + edk)Ak = b (xx - sdx)Ax + (x2 - sd2)A2 +.... + (xk - edk)Ak = b Điều này có nghĩa là các véctơ Xx = [xx + Edx, x2 + Ed2,...., xk + Edk,0,....,0]T .-'P Và x2 = [xx -Edx, x2 - ed2,..., xk - Edk,0,...,0] là hai nghiệm của hệ (2.6). Mặt khác có thể chọn E >0 đủ nhỏ để k thành phần đầu của Xx và x2 đều dương. Khi đó Xx và x2 là hai điểm khác nhau thuộc M và ta có X = l/2Xx + 1/2X2 Tức là X không phải là điểm cực biên của M. Điều này mâu thuẫn vởi giả thiết. Vậy các véctơ Ax, A2,...., Ak phải độc lập tuyến tính và theo định nghĩa X là phương án cực biên của bài toán. Số véctơ cột Aj độc lập tuyến tính, ta có thể bổ sung cho đủ sô tối đa m véctơ; nên với mỗi điếm cực biên của M, có thể cho tương ứng vởi m véctơ Aj độc lập tuyến tính 71 tạo nên cơ sở của hệ véctơ Aj, A2, ....., An. Các thành phần của điểm cực biên, tương ứng với m véctơ này, không ầm, các thành phần còn lại đều bằng không. Như vậy, mỗi điểm cực biên của M ứng với ít nhất một hệ m véctơ Aj độc lập tuyến tính mà số hệ m véctơ Aj độc lập tuyến tính của ma trận A không vượt quá C™, nên số điểm cực biên của tập M nếu có chỉ là một sô hữu hạn. Định lý 2.2. Nếu bài toán qui hoạch tuyến tính có phương án thì sẽ có phương án cực biên và nếu có phương án tối ưu thì sẽ có phương án cực biên tối ưu. Chứng minh Đối với tập M các phương án của bài toán qui hoạch tuyến tính chỉ có thể xẩy ra một trong ba trưòng hợp: 1. M là tập trống 2. M là tập bị chặn, khi đó nó là một đa diện lồi, tức là M là bao lồi cua các điểm cực biên. 3. M là tập không bị chặn (không giới nội) Trường hợp 1. Chúng ta không cần quan tâm vì ở đây bài toán không có phương án, tức là các ràng buộc của bài toán mâu thuẫn nhau, hay không tương thích. Trường hợp 2. khi tập M là một đa diện lồi, khi đó mọi điểm thuộc M có thể biểu diễn dưới dạng tổ hợp lồi của các điểm cực biên. Ta sẽ chứng minh bài toán có phương án tối ưu và tập các phương án tối ưu là một tập lồi với các điểm cực biên của nó chính là một sô điểm cực biên của M. 72 Thật vậy, giả sử rằng M cór điểm cực biên: Xj, x2, .....Xj. và hàm mục tiêu CTX nhận giá trị lớn nhất tại Xi (thứ tự các điểm cực biên là tuỳ ý). Lấy 'một điểm X bất kỳ thuộc M, tức là một phương án bất kỳ của bài toán thì X có thể biểu diễn dưới dạng tổ hợp lồi của các điểm cực biên: X = kxXx + k2X2 +.... + kjXy Trong đó kị > 0 (i = 1, 2,....,r) kx + k2 +.... + kr = 1. Giá trị của hàm mục tiêu tại điểm nà.y là: . CTX = ỉki (fXi < CTX1 ¿ki = CTX! i=l i=l Điều này có nghĩa: Giá trị hàm mục tiêu tại một điểm bất kỳ của M không vượt quá giá trị của hàm tại điểm Xx. Nói cách khác, hàm mục tiêu đạt giá trị cực đại tại điểm cực biên Xx Ta chứng minh tương tự đối vối hàm mục tiêu min Trong trường hợp ba; M là tập lồi không bị chặn thì M ngoài chứa bao lồi của các điểm cực biên x1( x2,...., Xj. nó còn chứa các điểm khác và ít nhất chứa một nửa đường thẳng. Nếu hàm mục tiêu đạt cực đại trong bao lồi của các điểm cực biên thì như trong trường hợp hai, ta chứng minh được hàm đạt cực đại tại một điểm cực biên của M. Nếu hàm CTX không đạt cực đại bất cứ điểm nào của bao lồi của các điểm cực biên thì ta có thể chọn trorig M điếm Xe, tại đó hàm c X nhận giá trị lớn hơn tại bất cứ điểm nào thuộc bao lồi của các điểm cực biên của M. Ta 73 lấy điểm x¡ nào đó của bao lồi này và vẽ nửa đường thẳng qua Xe (1 - k)Xị + kXe (k > 0) nửa đường thẳng này nằm trong M. Giá trị hàm mục tiêu tại các điểm của nửa đưòng thẳng này là: (1 - k)CTXi + kCTXe = CTXi + k^Xe - CTXị) Theo giả thiết của chúng ta, vì sô trong ngoặc là dương nên khi k tăng thì giá trị của hàm mục tiêu cũng sẽ tâng không bị chặn. Nói cách khác, nếu hàm mục tiêu không đạt cực đại tại một điểm cực biên nào đó thì nó có thể tăng không bị chặn, tức là bài toán không giải được. Tương tự, với sự thay đổi thích hợp' ta có thể chứng minh đối với bài toán min. Tối đây, ta có thể tóm tắt các kết quả đã chứng minh ở trên như sau: Đối với bài toán qui hoạch tuyến tính, có thể xảy ra một trong ba trường hợp sau: 1. Bài toán không có phương án 2. Bài toán có phương án tối ưu hữu hạn thì: a. Có một phương án tối ưu duy nhất thì hàm mục tiêu đạt giá trị tối ưu tại một điểm cực biên của tập M. b. Có vô số phương án tối ưu. Trong trường hợp này hàm mục tiêu đạt giá trị tốì ưu tại một số điểm cực biên của tập M và tại tất cả các điểm là bao lồi của các điểm này. 74 3. Hàm mục tiêu có thể nhận giá trị lốn tuỳ ý (đối vâi bài toán max) hoặc nhỏ tuỳ ý (đối vối bài toán min) trên tập M. Trong thực tế, phần lớn các bài toán chúng ta gặp rơi vào trưòng hợp hai và như vậy khi tìm phương án tối ưu ta chỉ cần tìm tại một số hữu hạn các điểm cực biên của M tức là tìm trên các nghiệm cơ sở khômg âm của hệ phương trình (2.6) Từ chứng minh định lý 2.2, ta có thể phát biểu hệ qua sau: Hệ quả 2.1. Nếu bài toán qui hoạch tuyến tính có phương án và hàm mục tiêu bị chặn trên tập phương án thì chắc chắn có phương án tối ưu. Chứng minh Theo giả thiết của định lý thì tập M khác trống do đó có phương án cực biên. Mặt khác do giả thiết hàm mục tiêu bị chặn trên tập phương án nên không thể xảy ra trường hợp hàm mục tiêu có thể tăng vô hạn (đối với bài toán max) trên tập M nên đối với bài toán này không thể xảy ra trường hợp 1 và trường hợp 3, tức là bài toán có phương án tối ưu hữu hạn. Để phân biệt tính chất của các ràng buộc đối với một phương án, ta đưa ra khái niệm ràng buộc chặt và lỏng. - Nếu đối với một phương án X mà ràng buộc thứ i thoả mãn vởi dấu đẳng thức, tức là ỉ a,j Xj = bị thì ta nói j=i 75 phương án X thoả mân chặt ràng buộc i hay ràng buộc i là chặt đối với phương án X. - Nếu đối với phương án X mà ràng buộc i thoả mãn với dấu bất đẳng thức thực sự, nghĩa là ỉ ajj Xj > bj thì j=l ta nói phương án X thoả mãn lỏng ràng buộc i hay ràng buộc i là lỏng đối với phương án X. Định lý 2.3. Một phương án của bài toán quy hoạch tuyến tính là phương án cực biên khi và chỉ khi nó thoả mãn chặt n ràng buộc độc lập tuyến tính. Chứng minh Cho X là một phương án của bài toán (2.5) - (2.7) thoả mãn chặt r ràng buộc độc lập tuyến tính. Giả sử k thành phần đầu tiên của X là dương, tức là Xj > 0 (j = 1, 2,....,k) và Xj = 0 (j = k + l,....,n). Ta lập ma trận tương ứng vởi các ràng buộc chặt của phương án X, ký hiệu là H. all a12 ■ • • alk al,k+l al,k+2 • ■ aln a21 a22 • • • a2k a2,k+l a2,k+2 • • aln K aml am2 • • ■ amk am,k+l am,k+2 • • amn 0 0 . . . 0 1 0 . . . 0 0 0 • •. 0 0 1 .. 0 . 0 0 . . 0 0 0 .. 1 ở đây, hạng của ma trận H bằng n. 76 Theo cách tính hạng của ma trận thì Hạng H = (n - k) + hạng K Nên ma trận H có hạng bằng n khi và chỉ khi hạng của ma trận K bằng k, tức là {Ạj : j = 1, 2,... k) độc lập tuyến tính hay {Aj : Xj > 0} độc lập tuyến tính. Chứng tỏ X là 1 phương án cực biên. Từ đây, ta có thể nêu ra một định nghĩa khác của phương án cực biên. Định nghĩa 2.10. Một phương án của bài toán qui hoạch tuyến tính thoả mãn chặt n ràng buộc độc lập tuyến tính là phương án cực biên của bài toán này. Phương án cực biên thoả 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, thoả mãn chặt hơn n ràng buộc gọi là phương án cực biên suy biến. 2.4. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BÀI TOÁN QUI HOẠCH TUYẾN TÍNH 2.4.1. Nội dung của phương pháp Xuất phát từ một phương án cực biên, đánh giá nó theo tiêu chuẩn tối ưu. Nếu nó chưa tối ưú thì ta chuyển sang một phương án cực biên khác tốt hơn và quá trình được lặp lại. Vì số phương án cực biên là hữu hạn nên sau một số hữu hạn bước lặp sẽ dẫn đến một trong hai tình thế: hoặc bài toán không giải được vì hàm mục tiêu không bị chặn hoặc sẽ tìm được phương án cực biên tối ưu. Như vậy phương pháp chỉ áp dụng được cho những bài toán có 77 phương án cực biên. Tuy nhiên mọi bài toán qui hoạch tuyến tính đều có thể đưa về dạng chính tắc và khi nó đã có phương án thì sẽ có phương án cực biên. Vì vậy ta chỉ cần xét bài toán dạng chính tắc và quan tâm đến các cách nhận biết một phương án là phương án cực biên. 2.4.2. Tiêu chuẩn tối ưu Chúng ta xét bài toán (2.5) - (2.7). Nếu coi z là biến thứ (n + 1) khi đó ta có thể phát biểu bài toán như sau: Giải hệ (m + 1) phương trình với (n + 1) ẩn allxl + a12x2 + ■ • • + alnxn = bl a21xl + a22x2 + • • • + a2nxn = b2 , „ . . ..................... (¿./10) amlxl + am2x2 + . . • + amnxn = bm z - cpq - C2X2 + . . . - cnxn = 0 đồng thời Xj > 0 (j = 1, 2,..., n) và z đạt giá trị cực đại. Giả sử bài toán này có phương án cực biên vởi cơ sỗ của nó là Ajo = {Ax, Aọ,...., Am} và phương án cực biên tương ứng là Xo = [x/0), x2( \ ....xm(0), 0...., 0]T có m thành phần đầu tiên không âm. Đe đánh giá phương án cực biên này ta phải khai triển các véctơ điều kiện Aj (j Ể Jo) và véctơ b theo cơ sở Ajo> thay giá trị của Xq vào hàm mục tiêu để đánh giá phương án. Ta biết rằng trong thực tế, để có được các hệ số triển khai, ta phải chuyển các véctơ cơ sở về hệ m véctơ đơn vị. về thực chất, điều này cũng có nghĩa là ta- chuyển hệ phương trình (2.10) về hệ tương đương, ở đó z và m ẩn đầu tiên xb x2,....,xm là các ẩn cơ sở của hệ vởi hệ số bằng 1 trong các phương trình tương ứng, còn trong các phương trình khác hệ số của chúng bằng 0, tức 78 là dùng phương pháp khử dần các ẩn chuyển (2.10) về hệ tương đương: X1 + “l.m+lXm+l + • • • + CtljXj + . . . + - ßi x2 + ccl)m+lxm+l + • • • + CljjXj + . . . + alnXn = ßi « “m)m+lxm+l + • • • + + • ■ • + CCjjjjjXjj — ßm Z + “o,m+lxm+l + • • • + 0 (i = 1, 2,...., m) Nếu ta gán cho các ẩn phi cơ sỏ các giá trị bằng 0, ta nhận được phương án cực biên Xq: \) = [ßi, ß2> ••••> ßm>0» •■■>0] ứng; với nó ta có Z(Xo) = ß0 Phương án này sẽ là tối ưu nếu như khi chuyển sang một phương án khác, giá trị của hàm mục tiêu không thể tăng nữa, còn nếu giá trị của z còn có thể tăng thì phương án chưa phải là tối ưu. Ta biết rằng, từ hệ (2.11) ta sẽ có các nghiệm khác của hệ nếu thay xm+1,...., xn bồi nhũng số thích hợp và khi đó từ (2.11) ta có z = ßo - ao,m+lxm+l ■ ••• ■ a0nxn Vì ta chỉ quan tâm đến các phương án của bài toán, nên ta có thể chuyển sang một phương án khác, nếu ta thay các ẩn phi cơ sỏ bởi các số không âm. Chẳng hạn, ta gán cho xm+1 bỏi một giá trị dương thì giá trị của z chỉ có thể tăng khi: 79 0^0,m+1 < O Từ đây, chúng ta có thể phát biểu tiêu chuẩn tốì ưu một cách đơn giản như sau: Nếu trong phương trinh cuối của hệ (2.11), tất cả các hệ số đều không âm, tức là aOj > 0 (Vj Ế Jo) thì giá trị của z không thể tâng nữa và phương án cực biên đang xét là phương án tối ưu. Nếu còn ít nhất một hệ số âm thì giá trị của hàm mục tiêu z còn có thể tăng Nếu ta xét bài toán min thì phương án sẽ tối ưu khi aOj < 0 (Vj Ể Jo) Chúng ta sẽ nghiên cứu ý nghía các hệ số của hệ (2.11) đặc biệt các hệ số aOj trong hàng cuối của hệ này. Với mục đích đó, ta viết hệ (2.10) dưới dạng ma trận. (2.10a) Để chuyển về dạng (2.11), phải có giả thiết m cột đầu của A độc lập tuyến tính. Ta ký hiệu Aỉo là ma trận cơ sở lập bởi m cột đầu tiên này và A(1) là ma trận con lập bởi các cột còn lại. Ta tách véc tơ c và X một cách thích hợp thành 2 phần: véc tơ m chiều là hệ số của các ẩn cơ sở ký hiệu Cj0 và (n-m) chiều c(1), tương tự đối với Xj0 và x(1). Chúng ta có thể viết lại hệ như sau: 0 AJ0A(l)‘ z ỉk 1 CT - C(1)T(2.10b) b0 X(1) 80 Bằng phương pháp thích hợp, chúng ta sẽ biến đổi (2.10b) về dạng (2.11). Ma trận của phép biến đổi này dễ dàng có thể xác định được là: 0 1(2.12) Nếu nhân về bên trái hai vế của (2.10b) vởi ma trận của phép biến đổi (2.12) ta sẽ nhận được z 0 E A-A» XJ. Aíb 1 0 Cj Aj'A01-c'"T WO WO X(l) cỉ AJxb 0 0 z + (C^A’1^- C(1)T)X(1) = C^A-^b Hệ (2.13) và (2.14) là những cách viết khác của hệ chính tắc (2.11), trong đó Xf là véctơ m chiều của các ẩn cơ sỏ, X J là véc tơ (n - m) chiều của các biến phi cơ sở, CT là véctơ hệ sô của m ẩn cơ sỏ, c(1) là véctơ hệ số của các ẩn phi cơ sỏ. Bây giờ ta xét hệ số của các biến phi cơ sở Xj (j Ể Jo). So sánh (2.11) và (2.14) ta có 81