- Học! học nửa! học mãi
- Học! học nửa! học mãi
Mã đề:
Câu I (6 điểm ) . Cho bài toán quy hoạch tuyến tính sau.- Đưa bài toán về dạng chuẩn ( 1 điểm ).
- Giải bài toán bằng phương pháp đơn hình ( 3 điểm).
- Lập bài toán đối ngẫu của bài toán (2 điểm).
Câu II (4 điểm). Cho bài toán vận tải (min) sau đây - Tìm một phương án xuất phát của bài toán vận tải trên (1 điểm).
- Giải bài toán vận tải trên bằng phương pháp thế vị (3 điểm).
ĐÁP ÁN CÂU 1a CÂU 1b CÂU 1c quantriTrong đó: 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.ơ ệ ố ế ả ủ ệ ộ A. 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 tơ ỏ ọ ộ ệ ủ oá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 tế ỏ ặ ố ệ ủ oá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 ạạế 1. Bài toán d ng t ng quát. (1), (2) & (3).ạ ổ 2. Bài toán d ng chính t c. (1) & (2) kèm đi u ki n xạ ắ ề ệ j≥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: ặệốớạắ 1. M i bài toán đ u có th đ a v d ng chính t c t ng đ ng b nọ ề ể ư ề ạ ắ ươ ươ ằ g 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 xế j ≤0 thì đ t n thêm n t=-ặ ẩ ẩ xj 2. Đ c đi m PACB c a bài toán chính t c: v i đi u ki n xặ ể ủ ắ ớ ề ệ j ≥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 tậ ị ặ ạ ủ ậ ộ rong 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 ={ Aơ j : 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) ốư I. Các chú ý c b n: ơ ả 1. 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.ề ạ ắ 2. Khi có ph ng án c c biên xươ ự 0 và c s Jơ ở 0 =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 vecớ ậ ề ệ ẩ ơ ở ệ ơ ế ảt 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 ả. 3. PAT duy nh t và t p PAT :Ư ấ ậ Ư
. 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.ướ - 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, k J 0 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, j J 0 bài toán không gi i đ c.ả ượ
- N u ế k >(<)0 mà t n t i ít nh t 1 xồ ạ ấ jk>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 {x 0 j/xjs} v i đi u ki n xớ ề ệ js>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 Cổ ả ệ ố r 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 Є I 1 ) (2) ≥(≤)bi (i Є I 2 ) (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 xụ ộ ự ộ ề ấ ủ j. ≥ cj - ph thu c vào ràng bu c v d u c a xụ ộ ộ ề ấ ủ j. ≥ cj - ph thu c vào ràng bu c v d u c a xụ ộ ộ ề ấ ủ j. yi không ràng bu c v d u “=” c a ộ ề ấ ủ các đi u ki n ràng bu c xề ệ ộ j. yi ≥(≤)0 – ph thu c vào d u b t đ ng th c các đi u ki n ràng ụ ộ ấ ấ ẳ ứ ề ệ bu c xộ j. (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) ưổ I. Các tính ch t: ấ 1. 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) 2. Tính ch t 2: v i (xấ ớ 0 ,y 0 ) 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(xẫ ồ ạ 0 )=F(y 0 ) thì (x 0 ,y 0 ) là các PAT c a 2 bài toán này.Ư ủ
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ìnế ứ ở ẻ ả ế ụ ả ơ h 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 xả ử ươ o 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 pư ặ ệ ả ạ ể ư ề ạ ị h thu cụ ộ vào 1 bi n yế k nào đó (th ng quy v yườ ề k≥0) thì lúc xét đi u ki n c a yề ệ ủ k nh l u ý các ph ng trình ràng bu c mà yớ ư ươ ộ k ch a th a mãn ch t cùngư ỏ ặ các đi u ki n c a yề ệ ủ j còn l i đ c bi u di n qua yạ ượ ể ễ k đ xác đ nh đ c đi uể ị ượ ề ki n c a yệ ủ k. Các PAT chính là các ph ng án th a mãn d u “=” c a hƯ ươ ỏ ấ ủ ệ đi u ki n yề ệ k. | 
