Bài giảng Quy hoạch tuyến tính: Chương 5 - ThS. Nguyễn Văn Phong

11/14/2011<br /> <br /> ÑAÏI HOÏC TAØI CHÍNH – MARKETING<br /> BOÄ MOÂN TOAÙN – KHOA CÔ BAÛN<br /> <br /> Baøi giaûng<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> ThS.<br /> ThS. Nguyeãn Vaên Phong<br /> Email : nvphong1980@gmail.com, nv.phong@ufm.edu.com<br /> <br /> Chương<br /> Chương 5. SÔ ÑOÀ PERT<br /> (PERT: Program Evaluation and Review Technique)<br /> 1. CAÙC VÍ DUÏ<br /> 2. MOÄT SOÁ KHAÙI NIEÄM<br /> 3. LAÄP SÔ ÑOÀ PERT<br /> 4. PHAÂN TÍCH SÔ ÑOÀ PERT<br /> 5. MOÄT SOÁ LÖU YÙ<br /> <br /> 2<br /> NGUYEÃN VAÊN PHONG<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> CAÙC VÍ DUÏ<br /> Ví duï1.<br /> Coâng vieäc<br /> <br /> Trình töï<br /> <br /> Thôøi gian<br /> <br /> Kieám vôï<br /> <br /> Baét ñaàu ngay<br /> <br /> 6<br /> <br /> Kieám tieàn mua nhaø<br /> <br /> Baét ñaàu ngay<br /> <br /> 12<br /> <br /> Kieám tieán cöôùi vôï<br /> <br /> Baét ñaàu ngay<br /> <br /> 7<br /> <br /> Ñaùm noùi<br /> <br /> Sau 1<br /> <br /> 2<br /> <br /> Ñaùm hoûi<br /> <br /> Sau 2,3,4<br /> <br /> 4<br /> <br /> Chuïp hình cöôùi<br /> <br /> Sau 5<br /> <br /> 3<br /> <br /> Choïn ñoà cöôùi, nöõ trang<br /> <br /> Sau 5<br /> <br /> 4<br /> <br /> Choïn nôi ñaêt tieäc<br /> <br /> Sau 5<br /> <br /> 5<br /> <br /> Ñaùm cöôùi<br /> <br /> Sau 6,7,8<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> 1<br /> 3<br /> NGUYEÃN VAÊN PHONG<br /> <br /> 1<br /> <br /> 11/14/2011<br /> <br /> CAÙC VÍ DUÏ<br /> Ví duï1.<br /> Vaán ñeà ñaët ra :<br /> 1. Thôøi gian ngaén nhaát ñeå hoaøn thaønh coâng vieäc ?<br /> 2. Muoán ruùt ngaén thôøi gian hoaøn thaønh coâng vieäc ta<br /> caàn ruùt ngaén thôøi gian cuûa nhöõng coâng vieäc naøo ?<br /> 3. Nhöõng coâng vieäc naøo coù theå hoaøn thaønh chaäm treå<br /> moät khoaûng thôøi gian naøo ñoù maø khoâng aûnh höôûng ñeán thôøi<br /> gian ngaén nhaát cuûa toaøn boä coâng vieäc.<br /> <br /> 4<br /> NGUYEÃN VAÊN PHONG<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> CAÙC VÍ DUÏ<br /> Ví duï2.<br /> <br /> 5<br /> NGUYEÃN VAÊN PHONG<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> MOÄT SOÁ KHAÙI NIEÄM<br /> thò.<br /> h,<br /> 1. Ñoà thò. Laø taäp hôïp goàm caùc ñænh (A), caùc caïnh, caùc cung (U)<br /> ñænh.<br /> noái caùc ñænh.<br /> - Kyù hieäu : G(A,U) – ñoà thò G.<br /> A2<br /> Cung U<br /> <br /> Caïnh U<br /> <br /> Ñænh A 1<br /> <br /> A3<br /> <br /> A4<br /> <br /> -Ñoà thò G ñöôïc goïi laø coù höôùng neáu G chæ chöùa caùc cung .<br /> Ñoà<br /> -Daây chuyeàn : Laø taäp goàm caùc ñænh vaø cung keá tieáp nhau.<br /> nhau.<br /> Daâ<br /> -Ñöôøng ñi : Laø moät daây chuyeàn maø moãi ñænh cuûa cung tröôùc seõ laø<br /> Ñöôø<br /> ngoïn cuûa cung sau<br /> -Khuyeân : laø moät cung coù ñænh goác vaø ngoïn truøng nhau<br /> Khuyeâ<br /> -Chu trình : laø moät ñöôøng ñi coù ñænh ñaàu vaø ñænh cuoái truøng nhau 6<br /> Chu<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> NGUYEÃN VAÊN PHONG<br /> <br /> 2<br /> <br /> 11/14/2011<br /> <br /> MOÄT SOÁ KHAÙI NIEÄM<br /> (PERT).<br /> g,<br /> 2. Sô ñoà maïng (PERT). Laø moät ñoà thò höõu haïn, coù höôùng, khoâng<br /> khuyeân, khoâng chu trình vaø moãi 1 cung gaùn moät soá thöïc khoâng<br /> cung)<br /> aâm (ñöôïc goïi laø ñoä daøi cung).<br /> A2<br /> 4<br /> <br /> 2<br /> <br /> A3<br /> <br /> 7<br /> <br /> A1<br /> <br /> 8<br /> <br /> A5<br /> <br /> 9<br /> <br /> 5<br /> A4<br /> <br /> -Ñoä daøi ñöôøng ñi: Laø toång ñoä daøi cuûa caùc cung thuoäc ñöôøng ñi.<br /> Ñoä<br /> ñi:<br /> ñi.<br /> -Ñöôøng ñi daøi nhaát : Ñoä daøi lôùn nhaát trong caùc ñöôøng ñi töø ñænh I<br /> Ñöôø<br /> ñeán j<br /> 7<br /> NGUYEÃN VAÊN PHONG<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> MOÄT SOÁ KHAÙI NIEÄM<br /> sau:<br /> 3. Trong sô ñoà maïng (PERT) ta coù caùc khaùi nieäm sau:<br /> - Ñænh: Töông öùng vôùi moät söï kieän (Hoaøn thaønh moät soá coâng<br /> Ñænh:<br /> vieäc vaø baét ñaàu moät soá coâng vieäc khaùc).<br /> - Cung : Töông öùng vôùi moät coâng vieäc.<br /> - Ñoä daøi cung : Töông öùng vôùi thôøi gian ñònh möùc cho coâng vieäc.<br /> - Döï aùn : Laø 1 quaù trình goàm caùc coâng vieäc, nhieäm vuï coù lieân<br /> nhau,<br /> quan vôùi nhau, ñöôïc thöïc hieän nhaèm ñaït ñöôïc muïc tieâu ñaõ ñeà<br /> gian,<br /> ra trong ñieàu kieän raøng buoäc veà thôøi gian, nguoàn löïc, ngaân<br /> saùch.<br /> h.<br /> <br /> tij<br /> <br /> i<br /> <br /> j<br /> 8<br /> NGUYEÃN VAÊN PHONG<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> MOÄT SOÁ CHUÙ YÙ KHI THIEÁT KEÁ PERT<br /> 1. Coâng vieäc yi baét ñaàu khi ys ,yt hoaøn thaønh<br /> ys<br /> <br /> yi<br /> <br /> yt<br /> <br /> 2. Coâng vieäc ys ,yt baét ñaàu khi yi hoaøn thaønh<br /> yi<br /> <br /> ys<br /> yt<br /> <br /> 1<br /> 1<br /> 3. y 2 BÑ khi HT y1, y 3 BÑ khi HT y1, y 4 BÑ khi y1 HT<br /> 3<br /> 2<br /> <br /> y2<br /> (1 / 3)y1<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> (1 / 6)y1<br /> <br /> y3<br /> (1 / 2)y1<br /> <br /> y4<br /> 9<br /> NGUYEÃN VAÊN PHONG<br /> <br /> 3<br /> <br /> 11/14/2011<br /> <br /> MOÄT SOÁ CHUÙ YÙ KHI THIEÁT KEÁ PERT<br /> 4. Hai coâng vieäc y1, y 2 cuøng BÑ taïi (i) vaø keát thuùc taïi (j).<br /> Neáu hai coâng vieäc cuøng tính chaát.<br /> y2<br /> j<br /> <br /> i<br /> <br /> bieán ñoåi thaønh<br /> <br /> i<br /> <br /> y1<br /> <br /> j<br /> <br /> y1 + y 2<br /> <br /> Neáu hai coâng vieäc coù tính chaát khaùc nhau:<br /> Theâm ñænh môùi cung giaû coù ñoä daøi baèng 0<br /> Cung giaû<br /> <br /> y2<br /> j<br /> <br /> i<br /> <br /> y2<br /> <br /> bieán ñoåi thaønh<br /> <br /> i<br /> <br /> y1<br /> <br /> j<br /> <br /> y1<br /> <br /> 10<br /> NGUYEÃN VAÊN PHONG<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> MOÄT SOÁ CHUÙ YÙ KHI THIEÁT KEÁ PERT<br /> 5. y4 BÑ sau khi y1 , y 2 HT; y5 BÑ sau khi y1 , y 2 , y 3 HT<br /> y1<br /> y1<br /> y4<br /> y2<br /> y<br /> <br /> y4<br /> <br /> 2<br /> <br /> 0<br /> <br /> Bieán ñoåi thaønh<br /> <br /> y3<br /> y2<br /> <br /> y5<br /> <br /> y3<br /> <br /> y5<br /> <br /> y1<br /> 6. y2 BÑ sau khi y1 HT, y 3 BÑ sau khi y1 , y 2 HT<br /> y1<br /> y2<br /> y1<br /> <br /> y3<br /> <br /> Bieán ñoåi thaønh<br /> <br /> y1<br /> <br /> y2<br /> <br /> y3<br /> <br /> y2<br /> 11<br /> NGUYEÃN VAÊN PHONG<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> MOÄT SOÁ CHUÙ YÙ KHI THIEÁT KEÁ PERT<br /> 7. Tính ñôn : Giöõa hai ñænh baát kyø coù nhieàu nhaát moät cung noái<br /> 8. y2 BÑ sau khi y1 HT, y 3 BÑ sau khi y1 , y 2 HT<br /> y1<br /> y4<br /> y1<br /> y2<br /> Bieán ñoåi thaønh<br /> <br /> y2<br /> <br /> 0<br /> <br /> y2<br /> <br /> y5<br /> y3<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> y4<br /> <br /> 0<br /> <br /> y3<br /> <br /> y5<br /> <br /> 12<br /> NGUYEÃN VAÊN PHONG<br /> <br /> 4<br /> <br /> 11/14/2011<br /> <br /> MOÄT SOÁ CHUÙ YÙ KHI THIEÁT KEÁ PERT<br /> 9. y3 BÑ sau khi y1 HT, y4 BÑ sau khi y 2 HT, y5 BÑ sau khi y1 , y2 HT<br /> y1<br /> <br /> y3<br /> <br /> y2<br /> <br /> y4<br /> <br /> y1<br /> <br /> y3<br /> 0<br /> <br /> Bieán ñoåi thaønh<br /> <br /> y1<br /> <br /> 0<br /> <br /> y2<br /> <br /> y5<br /> <br /> y5<br /> <br /> y4<br /> <br /> y2<br /> <br /> 13<br /> NGUYEÃN VAÊN PHONG<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> MOÄT SOÁ CHUÙ YÙ KHI THIEÁT KEÁ PERT<br /> 10.<br /> 10. y4 BÑ sau khi y1 HT, y5 BÑ sau khi y1 , y 2 HT, y6 BÑ sau khi y1 ,<br /> y2 , y 3 HT, y7 BÑ sau khi y4 , y5<br /> y3<br /> 0<br /> <br /> y2<br /> y1<br /> <br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> y6<br /> <br /> 0<br /> <br /> y5<br /> <br /> y7<br /> <br /> y4<br /> <br /> 14<br /> NGUYEÃN VAÊN PHONG<br /> <br /> MOÄT SOÁ CHUÙ YÙ KHI THIEÁT KEÁ PERT<br /> 4. Caùch veõ sô ñoà PERT<br /> + Xaùc ñònh 3 loaïi coâng vieäc<br /> ngay)<br /> - Coâng vieäc khôûi coâng (Baét ñaàu ngay)<br /> - Coâng vieäc keát thuùc (laø caùc coâng vieäc chæ naèm ôû coät<br /> coâng vieäc), khoâng naèm ôû coät trình töï thöïc hieän<br /> - Coâng vieäc trung gian<br /> + Veõ caùc sô ñoà con<br /> + Hieäu chænh vaø noái caùc sô ñoà con<br /> ñænh:<br /> + Ñaùnh soá caùc ñænh:<br /> - Ñaùnh soá 1 cho ñænh khôûi coâng<br /> - Giaû söû ta ñaùnh soá i cho cho 1 ñænh naøo ñoù, khi ñoù<br /> ta taïm xoaù caùc cung coù ñænh goác laø ñænh i. Xem ñænh chæ coù caùc<br /> cung ñi ra ñaùnh soá i + 1 (neáu coù nhieàu ñænh nhö vaäy ta laàn löôït ñaùnh<br /> i + 1, i + 2, …)ñaõ ñaùnh<br /> - Tieáp tuïc cho ñeán khi caùc ñænh ñöôïc ñaùnh soá.<br /> QUY HOAÏCH TUYEÁN TÍNH<br /> <br /> 15<br /> NGUYEÃN VAÊN PHONG<br /> <br /> 5<br /> <br />