TỔNG HỢP QUY HOẠCH TUYẾN TÍNH

Tài liệu tham khảo về tổng hợp quy hoạch tuyến tính dành cho sinh viên hệ cao đẳng đại học.
Nội dung trích xuất từ tài liệu:
TỔNG HỢP QUY HOẠCH TUYẾN TÍNHTỔNGHỢPQUYHOẠCHTUYẾNTÍNHPhầnI:BàiToánQuyHoạchTuyếnTínhvớiPhươngPhápĐơnHình.f(x)= =>min(max)(1) =bi(iЄI1)(2) ≥(≤)bi(iЄI2)(3)Trongđó:f(x) làhàmmụctiêu,cònhệ(2),(3)làhệphươngtrìnhràngbuộc,mỗi1phươngtrìnhvàbấtphươngtrìnhđượcgọilà1ràngbuộc. A=|aij|mxnlàmatrậnhệràngbuộc(matrậnhệsốphântích). Aj:vectơcộtjcủamatrậnA–vectơđiềukiện. b:vectơhệsốvếphảicủahệptràngbuộc.A. Cáctínhchấtchungcủabàitoánquyhoạchtuyếntính. 1. Vectơxthỏamãnmọiràngbuộc(hệ(2),(3))củabàitoánthìđượcgọilà phươngán,thỏamãnchặtlàthỏamãnvớidấu“=”cònthỏamãnlỏnglàthỏa mãnvớidấubấtđẳngthức. 2. PhươngÁnCựcBiên:làphươngánthỏamãnchặtnràngbuộcđộclậptuyến tính.PACBthỏamãnchặtđúngn(sốnghiệmcủabàitoán)ràngbuộcđượcgọi làPACBkhôngsuybiến,cònthỏamãnchặthơnnràngbuộcđượcgọilà PACBsuybiến. 3. PhươngÁnTốiƯu:làphươngánmàtạiđóhàmmụctiêuf(x)đạtcựctiểuhay cựcđại(PATƯ–haylàphươngántốtnhất) 4. Bàitoángiảiđượcvàkhônggiảiđược: BàitoángiảiđượclàbàitoáncóPATƯ,tứclàcó1vectơxthỏamãn(1),(2), (3). Bàitoánkhônggiảiđượclàbàitoánkhôngcóphươngánhoặccóphương ánnhưnghàmmụctiêukhôngbịchặn(tănghoặcgiảmvôcùng) 5. SựtồntạicủaPACB:1PAchỉlàPACBkhivàchỉkhithỏamãnchặthệđk ràngbuộcvàhạngcủamatrậnhệràngbuộcbằngn=sốẩnsốtrongbài toánchínhtắc,nếucóPAthìsẽcóPACBvìhạngmatrậnhệràngbuộcluôn= n. 6. SốPACBcủa1bàitoánluônlàhữuhạn.B. Cácdạngbàitoánquyhoạchtuyếntính 1. Bàitoándạngtổngquát.(1),(2)&(3). 2. Bàitoándạngchínhtắc.(1)&(2)kèmđiềukiệnxj≥0 j. 3. Bàitoándạngchuẩn=bàitoánchínhtắckèmthêmđiềukiệnbi≥0 i.C. Chúýđặcbiệtđốivớibàitoándạngchínhtắc: 1. Mọibàitoánđềucóthểđưavềdạngchínhtắctươngđươngbằngcáccông thứcsau: ≥(≤)bithìtalầnlượttrừvàcộngthêmẩnphụvào2vếcủabấtpt ràngbuộcnày. Nếuxj≤0thìđặtẩnthêmẩnt=xj 2. ĐặcđiểmPACBcủabàitoánchínhtắc:vớiđiềukiệnxj≥0củabàitoánnày,ta cóthểkhẳngđịnh1PAsẽlàPACBcủabàitoánchínhtắcnếuhệvectơA={Aj :xj>0}làhệđộclậptuyếntính,vìcácthànhphầnPACBchỉcóthểnhận2giá trị=0hoặc>0nênhạngcủamatrậnràngbuộctrongbàitoánchínhtắcsẽ bằngm=sốthànhphầndươngtronghệẩncủaPACBvàhệvectơA={Aj:xj >0}chínhlàcơsởcủaPACBđó. • Chúý:vớibàitoánchínhtắc,khitìmPACBchỉcầnxéthệmatrậnràng buộctươngứngvớimthànhphần>0vàchứngminhhạngcủamatrậnđó =m.D. CácbướccơbảngiảibàitoánQHTTbằngphươngphápđơnhình(đitìmPACBtối ưu) I. Cácchúýcơbản: 1. VìchỉxétbàitoánchínhtắcnênmọibàitoánQHTTkhibắtđầugiảiđềuquy vềbàitoándạngchínhtắc. 0 0 2. Khicóphươngáncựcbiênx vàcơsởJ =Ethìmatrậnhệsốphântíchsẽ trùngvớimatrậnđiềukiệnvàcácẩncơsởchínhlàhệvectơvếphảibcủa hệptràngbuộcnênmọibàitoánchínhtắcđềuquyvềdạngchuẩncónghĩa làcácbđều>0vàvectơhệsốphântíchcủacácẩncơsởtạonênmộtma trậnđơnvị. • Đặcbiệtchúýcácẩncôlập,tứclàẩncấuthànhhệvectơđơnvị,có thểlàẩncũhoặcẩnphụthêmvàohoặcẩngiả. 3. PATƯduynhấtvàtậpPATƯ: MộtPATƯlàduynhấtkhitồntại k )0, k J0thìđólàPATƯduynhất. SẽcótậpPATƯkháckhitồntại =0, k J0: k +TH1: =0, k J0&xjk≤0 j J0tậpPATƯkhôngbịchặn: k D={x:x=x0+ .zk; ≥0} +TH2: =0, k J0&tồntạixjk>0tậpPATƯbịchặn: k D={x:x=x0+ .zk;0≤ ≤ 0 }với 0=min{x0j/xjk}vớiđk: j J0vàxjk>0 .zk=xjknếuj J0 . k z =0nếuj J0vàj#k .zk=1nếuj=k +TasẽcócácPACBtốiưuvớidấu ...