Chương 4: Các phương pháp hữu hạn giải quyết bài toán qui hoạch tuyến tính

Tham khảo tài liệu chương 4: các phương pháp hữu hạn giải quyết bài toán qui hoạch tuyến tính, khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
Chương 4: Các phương pháp hữu hạn giải quyết bài toán qui hoạch tuyến tínhLý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́CHƯƠNG IV: CÁC PHƯƠNG PHÁP HỮU HẠN GIẢI BÀI TOÁN QUI HOẠCH TUYẾN TÍNH§1 Phương pháp đơn hình1.1 Bài toán QHTT dạng chuẩn Để mô tả các phương pháp hữu hạn giải bài toán QHTT người tathường xét bài toán cho ở dạng sau đây, gọi là bài toán QHTT dạng chuẩn: Tìm giá trị nhỏ nhất (hoặc lớn nhất) của hàm số n Z = Z(x) = ∑ c j x j j =1 (1.1)trên tập hợp các vec tơ x thỏa mãn các điều kiện: n ∑ a ij = bi ,i = 1, 2,..., m (1.2) j =1 x j ≥ 0, j = 1, 2,..., n (1.3)Trong đó cj, aij, bi, i = 1,2,…,m và j = 1,2,…,n là những số thực cho trước. Bài toán trên có thể viết dưới dạng ma trận: Tìm x* làm cực tiểu hàm số Z = 〈c, x〉 dưới các điều kiện Ax = b (1.4) x≥ 0 (1.5)Chú ý: Bài toán QHTT dạng chuẩn (1.1) – (1.3) chỉ khác bài toán QHTTdạng cơ bản ở chỗ các ràng buộc (1.2) cho ở dạng phương trình. Trongthực tế sản xuất, kinh doanh có nhiều bài toán có thể đưa về bài toánQHTT với nhiều dạng khác nhau. Bằng các phép biến đổi tương đươngnhư trình bày trong chương III, phần 3.2, người ta có thể đưa về bài toánở dạng chuẩn. n Đặt X = {x ∈ R / ∑ a ij x j = bi .i = 1, 2,..., m; x j ≥ 0, j = 1, 2,.., n} (1.6) n j =1Hay cũng vậy X = {x∈Rn/ Ax = b, x ≥ 0} Tương tự như ở phần 1.1 chương III, tập X, định nghĩa như trên đượcgọi là tập chấp nhận được, hàm Z = Z(x) được gọi là hàm mục tiêu, cácLê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣76Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́điều kiện (4.2) gọi là các ràng buộc, các điều kiện (4.3) là các hạn chế;ma trận A bao gồm các phần tử a ij gọi là ma trận các ràng buộc; vectơ bgọi là vectơ hạn chế (vectơ vế phải); vectơ c gọi là vectơ hệ số (hàm mụctiêu). Vectơ x∈X được gọi là lời giải hoặc phương án chấp nhận được;phương án chấp nhận được x* tại đó hàm mục tiêu Z nhận giá trị nhỏnhất (hoặc lớn nhất, tuỳ theo yêu cầu bài toán) được gọi là lời giải hoặcphương án tối ưu.1.2 Lý thuyết phương pháp đơn hình Để trình bày phương pháp đơn hình ta xét bài toán QHTT dạng chuẩn(1.1) – (1.3). Dễ thấy rằng tập X xác định theo (1.4) có thể được viết lạithành X = {x ∈ R n / A i. , x = bi ,i = 1, 2,..., m; e j , x ≥ 0, j = 1, 2,..., n} (1.7)Trong đó Ai. là các vectơ hàng của ma trận A; ej là vectơ đơn vị thứ j củakhông gian tuyến tính Rn, i = 1,2,…, m; j = 1,2,…,n. Không làm mất tínhtổng quát, có thể giả thiết rằng hạng của A, r[A] = m7 và m < n8). Đồngthời bài toán QHTT chỉ có ý nghĩa, nếu ít nhất có một cj ≠ 0. Như vậy tậpX có dạng như tập M ở phần §5 chương I, tức là cho bởi hệ (5.1), (5.2).Vậy, nếu X ≠ ∅ thì đó là một tập lồi đa diện. Theo định lý 5.5, nếu hệràng buộc xác định X có hạng bằg n thi một điểm x0∈X là điểm cực biênkhi và chỉ khi nó thỏa mãn chặt n ràng buộc độc lập tuyến tính. Theo tínhchất TC3 của bài toán QHTT, người ta chỉ cần khảo sát các điểm cực biêncủa miền chấp nhận được tương ứng. Sau đây chúng ta sẽ khảo sát đặttrưng đại số của các điểm cực biên ứng với bài toán (1.1) – (1.3).Đlí 1.1: Giả sử X ≠ ∅ và x0∈X, A.j là các vectơ cột của ma trận A, j = 1,2, …,n. Để x0 là điểm cực biên của X thì điều kiện cần và đủ là các vectơ A.j ứng với các xj > 0 là độc lập tuyến tính.Chứng minh: Do hệ ràng buộc xác định X (s.s. (1.7)) có chứa n vectơ đơnvị ej, nên hạng của hệ đó bằng n. Vì vậy, nếu x0 là điểm cực biên thì phải7 Nếu trong số các ràng buộc xác định X có ràng buộc nào đó phụ thuộc tuyến tínhvào các ràng buôc khác thì bằng cách loại bỏ dần này theo các pương pháp xác địnhhạng của ma trận thông thường để cho các ràng bộc còn lại là độc lập tuyến tínhvà ký hiệu số ràng buộc ấy là m. Khi ấy tập hợp chấp nhận được X sẽ không thayđổi.8 Rõ ràng r[A] = m ≤ n. Nếu r[A] = n thì hệ (1.2) là hệ phương trình tuyến tínhvuông, không thuần nhất. Hệ này có duy nhất một lời giải. Nếu lời giải này thỏamãn điều kiện không âm thì đó là lời giải tối ưu. Nếu lời giải này khôg thỏa mãn(1.3) thì bài toán QHTT không có lời giải. Trong cả hai trường hợp việc giải bàitoán QHTT không còn có ý nghĩa nữa.Lê Văn Phi, Khoa Toan – Thông kê, Đai hoc Kinh tế Tp. HCM ́ ́ ̣ ̣77Lý thuyêt qui hoach tuyên tinh ́ ̣ ́ ́thỏa mãn chặt n ràng buộc độc lập tuyến tính, tức là lời giải duy nhất củamột hệ phương trình vuông không suy biến. Không giảm tính tổng quát,giả sử x j > 0, j = 1, 2,...., k; x j = 0, j = k + 1,..., n . Ở bài toán QHTT dạng 0 0chuẩn tất cả các ràng buộc đều là chặt. Vì vậy có thể giả thiết rằng x 0 làlời giải duy nhất của hệ phương trình vuông không suy biến sau đây:  A.i , x = bi ,i = 1, 2,..., k    e j , x = 0, j = k + 1,.., n Hay cũng vậy  ∑ a x = b ,i = 1, 2,..., k n  j=1 ij j i  (1.8)  x j = 0, j = k + 1,.., n Thay n-k phương trình cuối vào k phương trình đầu, ta có hệ tươngđương: k ∑ a ij x j = bi ,i = 1, 2,..., k (1.9) j =1Do x0 là lời giải duy nhất của hệ (1.8), nên x 0 = (x1 , x 0 ,. ...