Giáo trình Quy hoạch tuyến tính: Phần 2

Phần 1 giáo trình "Quy hoạch tuyến tính" gồm nội dung các chương: Chương 4 - Các phương pháp đơn hình đặc biệt, chương 5 - Một số vấn để khác liên quan bài toán quy hoạch tuyến tính. Sau mỗi chương đều có câu hỏi ôn tập và bài tập. Mời bạn đọc tham khảo.
Nội dung trích xuất từ tài liệu:
Giáo trình Quy hoạch tuyến tính: Phần 2 Chương 4 CÁC PHƯƠNG P H Á P ĐƠN HÌNH ĐẶC BIỆT Trên cơ sở phương pháp đơn hình, trong chương n à y chúng ta sẽ nghiên cứu một số phương p h á p đặc biệt của nó. § 1 . P h ư ơ n g phập đ ơ n h ì n h c ả i b i ê n * 4.1.1. Ý tưởng của phương pháp Phương p h á p đơn hình, thực chất là: Xây dựng các phương án cực biên t ố t dần theo hướng giảm. Ở mỗi bước, đi t ừ phương án cực biên Xo sang p h ư ơ n g á n cực biên X j (xem § 1 , chương 3) nhờ các phép tính: Xo* = B -'b Xj = B -'Aj 1 Aj = C*Vj - Cj = C*B- Aj - C j , j € J (dễ thấy r ằ n g với j e J t h ì Aj = 0). Ở đây Aj là cột j của ma t r ậ n A, B là ma t r ậ n các toa độ của vectơ cơ sở liên k ế t , J là tập chỉ s ố cơ sở, c * = (Cj)j6j 99 1 đã biết t ừ X . Như vậy nếu biết B 0 thì ta có t h ê tính được Xo, Vj và Aj. Nếu X chưa t ố i ưu, cần xây dựng X ] . Chú ý rằng ma 0 t r ậ n cơ sở của X Ị khác ma t r ậ n cơ sở của Xo chỉ bởi một vectơ (A thay cho A,). k Đe đơn giản, ta giả t h i ế t bài t o á n đã b i ế t trước một phương án cực biên xuất p h á t , ứng với cơ sở liên k ế t đơn vị. Trong trường hợp tổng q u á t có phức tạp hơn, bạn đọc quan t â m có t h ể xem [1], [7]. Xuất p h á t từ phương án cực biên Xo với ma t r ậ n cơ sở liên k ế t B = E đơn vị. K h i đó dễ d à n g tính được ma t r ậ n 1 nghịch đảo B = E. Giả sử ma t r ậ n liên k ế t của X! là g cz A. Ta cần t í n h X 1; Vj', Áy thì n h ư đã nêu, chủ yêu ta cần t í n h ? \ Để ý rằng phương p h á p tính ma t r ậ n nghịch đảo trong đ ạ i số tuyến t í n h là: Ta viết ma t r ậ n (E ị ?), thực h i ệ n biến đ ổ i 1 theo h à n g để được ma t r ậ n (Ez \ E). K h i đó E chính là S ' . Do vậy, giả sử B = E = ( A ^ . - . A ^ - . A , , , ) và ĩ - (A!A ...A ...A ), thì g' chính là ma t r ậ n tương ứng 2 u m 1 (A]A ...A,...A ) trong bảng X i (chứ k h ô n g phải trong bảng 2 m Xo). (Bạn đọc h ã y tự kiểm tra nhận xét n à y trong ví d ụ đã nêu ở mục 3 chương 3). Tuy nhiên, để dễ tính toán ta ký h i ệ u f A (A tí = (tí.) = K ì ỉ { - c ĩ)' trong đó tí là ma t r ậ n gồm m +1 h à n g , n +1 cột. 100 Hàng thứ m +1 của ư là (- Cj - Cọ ... - c„ 1), cột thứ n T + 1 là (0 0 ... 0 1) . Ký hiệu f B 0^ * -c Ì, Rõ ràng ÍB là ma trận m +1 hàng, m +1 cột, có hạng m +1. Có thể trực tiếp kiểm tra được rằng ma trận ỐB có 1 dạng -Ì l 9> = B 0 * c B Nhận xét rằng, từ công thức tính Aj = C*B l - Ảị - Cị, ta có quy tắc thực hành: 1 • Aj bằng tích hàng thứ m +1 của ma trận ÍB với cột ' A .j ^ « j = - c. trong ma trận tí. _1 • Xj bằng tích của m h à n g đầu của ma t r ậ n £B với ^ A. ) cót tí trong ma trận tì . - c. V ìJ Với nhận xét vừa nêu thì việc tính t t cả các cột của bảng đơn hình là không cần thiết. Do vậy phương pháp đơn hình cải biên được thực hiện trên các bảng đơn hình có những cải tiến, mô tả như sau (bảng 8). loi B ả n g 8. Cơ s ở c*= X = B 1 x k Aj ( v ớ i A j n g o à i c ơ sở) Ai (c,) (Xi) ...