Tổng hợp quy hoạch tuyến tính

TỔNG HỢP QUY HOẠCH TUYẾN TÍNH Phần I: Bài Toán Quy Hoạch Tuyến Tính với Phương Pháp Đơn Hình. f(x) = => min (max) (1) =bi (i Є I1) (2) ≥(≤)bi (i Є I2) (3) Trong đó: f(x) là hàm mục tiêu, còn hệ (2), (3) là hệ phương trình ràng buộc, mỗi 1 phương trình và bất phương trình được gọi là 1 ràng buộc. A = |aij|mxn là ma trận hệ ràng buộc(ma trận hệ số phân tích). Aj: vectơ cột j của ma trận A – vectơ điều kiện. b : vectơ hệ số vế phải của hệ pt ràng buộc. Các tính chất chung của bài toán quy hoạch tuyến tính. Vectơ x thỏa mãn mọi ràng buộc (hệ (2), (3) ) của bài toán thì được gọi là phương án, thỏa mãn chặt là thỏa mãn với dấu “=” còn thỏa mãn lỏng là thỏa mãn với dấu bất đẳng thức. Phương Án Cực Biên: là phương án thỏa mãn chặt n ràng buộc độc lập tuyến tính. PACB thỏa mãn chặt đúng n(số nghiệm của bài toán) ràng buộc được gọi là PACB không suy biến, còn thỏa mãn chặt hơn n ràng buộc được gọi là PACB suy biến. Phương Án Tối Ưu: là phương án mà tại đó hàm mục tiêu f(x) đạt cực tiểu hay cực đại (PATƯ – hay là phương án tốt nhất) Bài toán giải được và không giải được: Bài toán giải được là bài toán có PATƯ, tức là có 1 vectơ x thỏa mãn (1),(2),(3). Bài toán không giải được là bài toán không có phương án hoặc có phương án nhưng hàm mục tiêu không bị chặn (tăng hoặc giảm vô cùng) Sự tồn tại của PACB: 1 PA chỉ là PACB khi và chỉ khi thỏa mãn chặt hệ đk ràng buộc và hạng của ma trận hệ ràng buộc bằng n = số ẩn số à trong bài toán chính tắc, nếu có PA thì sẽ có PACB vì hạng ma trận hệ ràng buộc luôn = n. Số PACB của 1 bài toán luôn là hữu hạn. Các dạng bài toán quy hoạch tuyến tính Bài toán dạng tổng quát. (1), (2) & (3). Bài toán dạng chính tắc. (1) & (2) kèm điều kiện xj≥0 j . Bài toán dạng chuẩn = bài toán chính tắc kèm thêm điều kiện bi≥0 i. Chú ý đặc biệt đối với bài toán dạng chính tắc: Mọi bài toán đều có thể đưa về dạng chính tắc tương đương bằng các công thức sau: ≥(≤)bi thì ta lần lượt trừ và cộng thêm ẩn phụ vào 2 vế của bất pt ràng buộc này. Nếu xj ≤0 thì đặt ẩn thêm ẩn t=- xj Đặc điểm PACB của bài toán chính tắc: với điều kiện xj ≥0 của bài toán này, ta có thể khẳng định 1 PA sẽ là PACB của bài toán chính tắc nếu hệ vectơ A ={ Aj : xj >0} là hệ độc lập tuyến tính, vì các thành phần PACB chỉ có thể nhận 2 giá trị =0 hoặc >0 nên hạng của ma trận ràng buộc trong bài toán chính tắc sẽ bằng m =số thành phần dương trong hệ ẩn của PACB và hệ vectơ A ={ Aj : xj >0} chính là cơ sở của PACB đó. Chú ý: với bài toán chính tắc, khi tìm PACB chỉ cần xét hệ ma trận ràng buộc tương ứng với m thành phần >0 và chứng minh hạng của ma trận đó =m. Các bước cơ bản giải bài toán QHTT bằng phương pháp đơn hình(đi tìm PACB tối ưu) Các chú ý cơ bản: Vì chỉ xét bài toán chính tắc nên mọi bài toán QHTT khi bắt đầu giải đều quy về bài toán dạng chính tắc. Khi có phương án cực biên x0 và cơ sở J0=E thì ma trận hệ số phân tích sẽ trùng với ma trận điều kiện và các ẩn cơ sở chính là hệ vectơ vế phải b của hệ pt ràng buộc nên mọi bài toán chính tắc đều quy về dạng chuẩn có nghĩa là các b đều >0 và vectơ hệ số phân tích của các ẩn cơ sở tạo nên một ma trận đơn vị. Đặc biệt chú ý các ẩn cô lập, tức là ẩn cấu thành hệ vectơ đơn vị, có thể là ẩn cũ hoặc ẩn phụ thêm vào hoặc ẩn giả. PATƯ duy nhất và tập PATƯ: Một PATƯ là duy nhất khi tồn tại k )0, kJ0 thì đó là PATƯ duy nhất. Sẽ có tập PATƯ khác khi tồn tại k =0, kJ0: + TH1:k =0, kJ0 & xjk≤0 jJ0 à tập PATƯ không bị chặn: D={x:x=x0+.zk;≥0} + TH2:k =0, kJ0 & tồn tại xjk>0 à tập PATƯ bị chặn: D={x:x=x0+.zk;0≤≤0} với 0 = min{x0j/xjk} với đk: jJ0 và xjk>0 . zk = -xjk nếu jJ0 . zk=0 nếu jJ0 và j#k . zk=1 nếu j=k + Ta sẽ có các PACB tối ưu với dấu “=” của điều kiện =0 và =0. Các Bước Của PP ĐƠN HÌNH: Tìm PACB nếu có các biến cô lập dựa trên các ẩn phụ và ẩn giả. Nếu chỉ cần ẩn phụ à tiến hành theo bước 2 bình thường và kết luận với các ẩn phụ giá trị = 0.(chú ý biến đổi sao cho hệ ẩn cơ sở có ma trận hệ số phân tích là vectơ đơn vị) Nếu có ẩn giả à lập bài toán phụ với hàm mục tiêu P(x,xg)=gi => min và giải bình thường theo PP Đơn Hình cho đến khi tìm được PACBTƯ (x0,xg0).(chú ý các hệ số C khi tính trong bảng đơn hình có ẩn giả đều =0) 1.1. Nếu trong quá trình biến đổi ta loại được ẩn giả nào thì bước sau không tính cột ẩn giả đó nữa, và nếu loại hết thì về được bài toán ban đầu tính lại k (với hệ số C như đầu bài) và giải bình thường từ bước 3. 1.2. Nếu có PACBTƯ (tmãn 3) có Pmin>0 thì bài toán đã cho không có phương án. 1.3. Nếu có PACBTƯ(tmãn 3) có Pmin=0 thì x0 PACB của bài toán gốc à tiến hành tính lại các k (với hệ số C như đầu bài) và tiến hành như sau: . nếu các ẩn giả đều đã mất (trở thành ẩn phi cơ sở) thì áp dụng như lúc biến đổi mất hết ẩn giả trong bước 1.1. . nếu trong hệ cở sở vẫn tồn tại ẩn giả thì bỏ các cột có P <0 và tính lại k (với hệ số C như đầu bài) và giải bình thường với các ẩn bỏ đi = 0 theo bước 1.1. Lập bảng đơn hình dựa trên PACB đã biết. Kiểm tra dấu hiệu tối ưu: Nếu k ≤ (≥)0, kJ0 thì x0 là PATƯ à dừng bài toán. Nếu k >(<)0 thì chuyển sang bước 4. Kiểm tra tính không giải được của bài toán: Nếu k >(<)0 mà xjk≤0, jJ0 àbài toán không giải được. Nếu k >(0 thì chuyển sang bước 5. Lựa chọn ẩn đưa ra và đưa vào cơ sở: Chọn Max k (Min k) = s với điều kiện k >(<)0 à ẩn s được đưa vào cơ sở mới. – trường hợp Min k với điều kiện k<0 được áp dụng trong trường hợp f(x) à max. Tính 0 = min {x0j/xjs} với điều kiện xjs>0 à thành phần nào của cơ sở có 0 min thì đó là ẩn r được đưa ra khỏi cơ sở và thay bằng s. Thay đổi cả các hệ số Cr và Cs trong bảng đơn hình à bước 6. Biến đổi bảng mới: = cách biến các thành phần trong cột ẩn của phần tử xoay thành cột vectơ đơn vị bao gồm biến đổi cả k đối với các cột khác. à lại thực hiện lại từ bước 3 cho đến khi kết thúc: có PACBTƯ hoặc không giải được. Phần II: Bài Toán Đối Ngẫu Cách XD bài toán đối ngẫu: Từ bài toán QHTT tổng quát à XD bài toán đối ngẫu: f(x) = => min (max) (1) =bi (i Є I1) (2) ≥(≤)bi (i Є I2) (3) BT Đối Ngẫu; F(y) = => max(min) = cj - phụ thuộc vào sự không ràng buộc về dấu của xj. ≥ cj - phụ thuộc vào ràng buộc về dấu của xj. ≥ cj - phụ thuộc vào ràng buộc về dấu của xj. yi không ràng buộc về dấu “=” của các điều kiện ràng buộc xj. yi ≥(≤)0 – phụ thuộc vào dấu bất đẳng thức các điều kiện ràng buộc xj. (Các cặp ràng buộc đối ngẫu là các cặp ràng buộc có dấu bất đẳng thức ở trên.) Các định lý và tính chất đối ngẫu ( chỉ áp dụng với bài toán QHTT dạng chính tắc nhưng luôn đúng cho bài toán tổng quát) Các tính chất: Tính chất 1:với (x,y) là phương án của bài toán ban đầu và bài toán đối ngẫu ta luôn có f(x) ≥ F(y) Tính chất 2: với (x0,y0) là phương án của bài toán ban đầu và bài toán đối ngẫu và tồn tại f(x0)=F(y0) thì (x0,y0) là các PATƯ của 2 bài toán này. Các định nghĩa: Định nghĩa 1: nếu 1 trong 2 bài toán giải được và có PATƯ (x*,y*) thì ta luôn có: f(x*) = F(y*) Hệ quả: 1 cặp bài toán đối ngẫu luôn có 3TH sau đây: + 2 bài toán đều có PAàcó PATƯ tương ứng và : f(x*) = F(y*) + 2 bài toán đều không có PA. + Chỉ 1 trong 2 bài toán có PA: bài toán có PA sẽ có hàm mục tiêu không bị chặn. Định nghĩa 2: Đk để cặp PA (x0,y0) là PATƯ đó là trong tất cả các cặp ràng buộc đối ngẫu thì ràng buộc nào thỏa mãn với dấu bất đẳng thức thì ràng buộc còn lại thỏa mãn với dấu “=” – Lưu ý sử dụng ĐN này linh hoạt với x0 để tìm ra y0 tương ứng. Tổng hợp các dạng bài cơ bản: Cho PACB từ PACB này giải bài toán đơn hình: CM đó là phương án CB bằng cách thay vào hệ pt ràng buộc, sau đó tính hạng ma trận các ràng buộc chặt(bao gồm cả những ràng buộc về dấu của bài toán). Đưa bài toán về dạng chính tắc, lưu ý biến đổi các cột ẩn cơ sở thành cột đơn vị để tạo thành ma trận đơn vị, ưu tiên thành phần nào có số 1 cùng với số 0 trước(bao gồm cả ẩn phụ) sau đó biến đổi nốt các cột tương ứng thành ma trận đơn vị. Giải bài toán đơn hình. Trường hợp yêu cầu tính f(x) à min sau đó yêu cầu tính theo f(x) à max thì sau khi kết thức ở min thì kẻ bảng tiếp tục giải đơn hình theo phương án max, lưu ý là điều kiện tối ưu đã thay đổi. Chưa cho PACB à giải bình thường với ẩn phụ và ẩn giả. Tìm tập PATƯ có xk = a: Nếu tìm phương án tối ưu dựa trên tập phương án tối ưu đã có thì tính theo bước tìm được PATƯ.( PATƯ sẽ là phương án có x*k = a = xok + .zk à từ đó tính và suy ra phương án cưc biên thỏa mãn điều kiện ràng buộc trên. Tìm PATƯ khi có thêm điều kiện f(x) ≥(≤) a hoặc xk ≤ a: thường sẽ bắt đầu với bài toán không giải được trong phương pháp đơn hình: xk ≤ a : PATƯ sẽ là phương án có x*k = a = xok + .zk à từ đó tính và suy ra phương án cưc biên thỏa mãn điều kiện ràng buộc trên. f(x) ≥ a : áp dụng công thức tìm PATƯ tốt hơn: f(x*) = f(xo) - o. k à o và tính PATƯ tương ứng. ( tương tự TH f(x) ≤ a xảy ra khi hàm mục tiêu à max và tính theo công thức tương tự) Tìm PATƯ có f(x) = a à tương tự trường hợp f(x) ≥(≤) a (như trên) Thay c= c’ hoặc thay b=b’ hoặc thay hàm mục tiêu: Nếu có thay đổi hàm mục tiêu thì tính lại từ bước cuối cùng không giải được. Lưu ý khi có thay đổi trị số C của hàm mục tiêu thì thay vào ở bước loại hết được ẩn giả ra khỏi bài toán đơn hình hoặc tại bước không giải được của bài toán không có ẩn giả.(tương tự với b) Tìm PATƯ của bài toán đối ngẫu: Khi yêu cầu tìm y* của bài toán đối ngẫu thì suy ra từ điều kiện bất đẳng thức của x* để xuất hiện hệ phương trình với y rồi giải, Hệ pt y thường là hệ pt nhiều ẩn bậc nhất nên nghiệm luôn là duy nhấtà đó là PATƯ. Kết luận về bài toán đối ngẫu: nếu f(x) có PATƯ à BTĐN có PATƯ. Cho bài toán và vectơ à xem tính chất của vectơ đó trong bài toán gôc và bài toán đối ngẫu: Viết bài toán đối ngẫu. Thay xo vào hệ pt ràng buộc xem có đủ đk cực biên hay ko ( nếu có thì cm thêm hạng của hệ ma trận ràng buộc đó = n) Giả sử phương án xo là phương án tối ưu để dựa vào đó tìm y, nếu hệ pt y có nghiệm à (xo,yo) là PATƯ, còn không thì ko phải PATƯ. Lưu ý đặc biệt khi giải dạng này có thể đưa về dạng vô định phụ thuộc vào 1 biến yk nào đó (thường quy về yk≥0) thì lúc xét điều kiện của yk nhớ lưu ý các phương trình ràng buộc mà yk chưa thỏa mãn chặt cùng các điều kiện của yj còn lại được biểu diễn qua yk để xác định được điều kiện của yk. Các PATƯ chính là các phương án thỏa mãn dấu “=” của hệ điều kiện yk.