Có một số phương pháp khác nhau để giải bài toán Qui hoạch tuyến tính : phương pháp hình học , phương pháp phân tích sự biến động của hàm mục tiêu và phương pháp đơn hình . Nếu đối với phương án cực biên x0 với cơ sở J0 của bài toán dạng chính tắc mà với mỗi Dk 0 đều tồn tại xjk 0 đối với bài toán f(x) ® min thì ta có thể điều chỉnh PACB x0 để chuyển sang một PACB mới tốt hơn | PHƯƠNG PHÁP ĐƠN HÌNH Các định lí cơ bản Định lí1: ( Dấu hiệu tối ưu của phương án cực biên) Nếu đối với phương án cực biên x0 với cơ sở J0 của bài toán dạng chuẩn mà k 0 ( k J0 ) đối với bài toán f(x) min thì x0 là phương án tối ưu Ta gọi Là ước lượng của biến xk theo cơ sở J0 Định lí2: ( Dấu hiệu bài toán không giải được ) Nếu đối với phương án cực biên x0 với cơ sở J0 của bài toán dạng chính tắc mà tồn tại k > 0 mà xjk 0 ( k J0 ) đối với bài toán f(x) min hoặc: tồn tại k Định lí3: ( Dấu hiệu điều chỉnh PACB) Nếu đối với phương án cực biên x0 với cơ sở J0 của bài toán dạng chính tắc mà với mỗi k >0 đều tồn tại xjk > 0 đối với bài toán f(x) min thì ta có thể điều chỉnh PACB x0 để chuyển sang một PACB mới tốt hơn 2. Phương pháp đơn hình cho bài toán QHTT: A. Thuật toán đơn hình cho bài toán QHTT dạng chuẩn: Ví dụ Hệ số Ẩn cơ bản P Án 2 3 3 8 4 x1 x2 x3 x4 x5 8 x4 16 0 2 0 1 7 3 x3 4 0 5 1 0 2 2 x1 8 1 1 0 0 2 f(x0) 156 0 30 0 0 62 Bảng đơn hình xuất phát Hệ số Ẩn cơ bản Ph Án 2 3 3 8 4 x1 x2 x3 x4 x5 8 3 2 x4 x3 x1 f(x0) 16 4 8 156 0 0 1 2 5 1 0 1 0 1 0 0 7 2 2 0 30 0 0 62 Phương án tối ưu là x0 = (4,0,0,2,2); f(x0) = 32 Hệ số Ẩn cơ bản Ph Án 2 3 3 8 4 x1 x2 x3 x4 x5 8 3 2 x4 x3 x1 f(x0) 16 4 8 156 0 0 1 2 5 1 0 1 0 1 0 0 7 2 2 0 30 0 0 62 8 4 2 x4 x5 x1 f(x’0) 2 0 5/2 1/2 0 1 Hệ số Ẩn cơ bản Ph Án 2 3 3 8 4 x1 x2 x3 x4 x5 8 3 2 x4 x3 x1 f(x0) 16 4 8 156 0 0 1 2 5 1 0 1 0 1 0 0 7 2 2 0 30 0 0 62 8 4 2 x4 x5 x1 f(x’0) 2 2 0 0 -31/2 5/2 -7/2 1/2 1 0 0 1 Hệ số Ẩn cơ bản Ph Án 2 3 3 8 4 x1 x2 x3 x4 x5 8 3 2 x4 x3 x1 f(x0) 16 4 8 156 0 0 1 2 5 1 0 1 0 1 0 0 7 2 2 0 30 0 0 62 8 4 2 x4 x5 x1 f(x’0) 2 2 4 0 0 1 -31/2 5/2 -4 -7/2 1/2 -1 1 0 0 0 1 0 Hệ số Ẩn cơ bản Ph Án 2 3 3 8 4 x1 x2 x3 x4 x5 8 3 2 x4 x3 x1 f(x0) 16 4 8 156 0 0 1 2 5 1 0 1 0 1 0 0 7 2 2 0 30 0 0 62 8 4 2 x4 x5 x1 f(x’0) 2 2 4 0 0 1 -31/2 5/2 -4 -7/2 1/2 -1 1 0 0 0 1 0 32 0 -125 -31 0 | PHƯƠNG PHÁP ĐƠN HÌNH Các định lí cơ bản Định lí1: ( Dấu hiệu tối ưu của phương án cực biên) Nếu đối với phương án cực biên x0 với cơ sở J0 của bài toán dạng chuẩn mà k 0 ( k J0 ) đối với bài toán f(x) min thì x0 là phương án tối ưu Ta gọi Là ước lượng của biến xk theo cơ sở J0 Định lí2: ( Dấu hiệu bài toán không giải được ) Nếu đối với phương án cực biên x0 với cơ sở J0 của bài toán dạng chính tắc mà tồn tại k > 0 mà xjk 0 ( k J0 ) đối với bài toán f(x) min hoặc: tồn tại k Định lí3: ( Dấu hiệu điều chỉnh PACB) Nếu đối với phương án cực biên x0 với cơ sở J0 của bài toán dạng chính tắc mà với mỗi k >0 đều tồn tại xjk > 0 đối với bài toán f(x) min thì ta có thể điều chỉnh PACB x0 để chuyển sang một PACB mới tốt hơn 2. Phương pháp đơn hình cho bài toán QHTT: A. Thuật toán đơn hình cho bài toán QHTT dạng chuẩn: Ví dụ Hệ số Ẩn cơ bản P Án 2 3 3 8 4 x1 x2 x3 x4 x5 8 x4 16 0
