TÀI LIỆU VỀ BÀI GIẢNG QUY HOẠCH TUYẾN TÍNH | Chương 3. PHƯƠNG PHÁP ĐƠN HÌNH VÀ CÁC THUẬT TOÁN CỦA NÓ . Cơ sở lí luận Xét bài toán quy hoạch tuyến tính dạng chính tắc f x CTx min 1 Ax b 2 x 0 3 Với A là ma trận m X n b 2 Rm c và x 2 Rn trong đó A có hạng là m m n . Bài toán quy hoạch là không suy biến tất cả phương án cực biên của nó đều có số thành phần dương bằng m và x X01 Xo2 x0n là một phương án cực biên. Ký hiệu J0 j x0j 0 . Hệ véc tơ Aj j 2 J0 độc lập tuyến tính cho nên các véc tơ AZ i 1 . n đều biểu thị duy nhất qua cơ sở Aj j 2 J0 A X xijAj i 1 . n 4 Nếu gọi B là ma trận có các cột là Aj j 2 J0 và đặt x1 xjj 2 Rm j 2 J0 thì A Bx hay x B 1Ai i 1 . n. Nếu đặt x0 x0 2 Rm c0 cj0 2 Rm với j 2 J0 thì f x0 CTx0 2 c0x0j Bx0 b. j2Jo Định nghĩa Ước lương . Ta gọi A C0Tx- C i 1 . n là ước lượng của biến x hay của véc tơ A ứng với cơ sở J0. Định lý Dấu hiệu tối ưu . Nếu phương án cực biên x của quy hoạch tuyến tính có Ai 6 0 i 1 . n thì x là phương án tối ưu của bài toán 1 2 3 . Chứng minh. Xét phương án bất kì y yì ta có b XyA Xhi X X Xxijhi. Aj b X x jAj do 4 i 1 i 1 j 2Jo j2Jo i 1 j 2J0 n x j x Xijhi. j 1 2 . n 5 i 1 Từ Ai 6 0 Vi suy ra c Txi 6 Cị. Do đó ta được . y X Chi X c Txi hi i 1 i 1 n X X xijcj hi X X xij y c jeJo i 1 2 cj x j f x jj Vậy x là phương án tối ưu. Định lý Dấu hiệu hàm mục tiêu không bị chặn . Nếu phương án cực biên x của quy hoạch tuyến tính mà có j sao cho Aj 0 và xj 0 thì bài toán 1 2 3 có hàm mục tiêu không bị chặn. Chứng minh. Ta có Ai X xij Aj Vi theo 4 j2J0 Gọi 8 xij j 2 J di dij dij -1 j ị 0 j 2 J ig Xét véc tơ x ớ x0 dải 0 0 ta có n X xj 0 Aj X x0j - 0xoj Aj 0Ai j i jeJo X x0jAj 0 Ai _ X x0jAj b 0 b. j2Jo j2 J Và Xji 0 nên ải 0 mà x0 0 cho nên x 0 0 với mọi 0 0. Do đó x 0 là phương án của bài toán. Mặt khác ta thấy n f x 0 X cjXj 0 X Cj x0j - 0xij 0Q X cjx0j 0 ci - X cjxj f x0 0Ai 1 khi 0 1 do Ai 0. Do đó hàm mục tiêu không bị chặn. Định lý Dấu hiệu xây dựng được phương án tối hơn . Nếu phương án cực biên x0 của quy hoạch tuyến tính tồn tại j sao .
