Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
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. | Chương 4 CÁC PHƯƠNG PHÁ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 pháp đặc biệt của nó. 1. Phương pháp đơn hình cải biên 4.1.1. Ý tưởng của phương pháp Phương phá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 phương án cực biên Xj xem 1 chương 3 nhờ các phép tính xo B b Xj B Aj C Xj - Cj C B lAj - Cj j Ể J dễ thấy rằng với j e J thì Aj 0 . Ó đây Aj là cột j của ma trận A B là ma trận các toạ độ của vectơ cơ sở liên kết J là tập chỉ số cơ sở c Cj jej 99 đã biết từ Xq. Như vậy nếu biết B 1 thì ta có thê tính được Xo Xj và Aj. Nếu xo chưa tôi ưu cần xây dựng X . Chú ý rằng ma trận cơ sơ của X khác ma trận cơ sở của X J chỉ bởi một vectơ Ak thay cho A . Để đơn giản ta giả thiết bài toán đã biết trước một phương án cực biên xuất phát ứng với cơ sở liên kết đơn vị. Trong trường hợp tổng quát có phức tạp hơn bạn đọc quan tâm có thể xem 1 7 . Xuât phát từ phương án cực biên xo với ma trận cơ sở liên kết B E đơn vị. Khi đó dễ dàng tính được ma trận nghịch đảo B 1 E. Giả sử ma trận liên kết của Xj là g GZ A. Ta cần tính Xn X A ị thì như đã nêu chủ yêu ta cần tính 5 Đê ý rằng phương pháp tính ma trận nghịch đảo trong đại sô tuyến tính là Ta viết ma trận E I g thực hiện biến đổi theo hàng để được ma trận E-l E . Khi đó E chính là . Do vậy giả sử B E A1A2.Aí.Am và 3 AjAa.-.Ak.-.An thì 1 chính là ma trận tương ứng A A2.A .Am trong bảng Xj chứ không phải trong bảng xơ . 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ý hiệu trong đó ơ là ma trận gồm m 1 hàng n 1 cột. 100 Hàng thứ m 1 của ư là - Ci - c-2 . - cn 1 cột thứ n 1 là 0 0 . 0 1 T. Ký hiệu Rõ ràng 93 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 93 1 có dạng SB 1 b Nhận xét rằng từ công thức tính Aj C B lAj - Cj ta có quy tắc thực hành Aj bằng tích hàng thứ m 1 của ma trận 93 1 với cột A 3
