Quy hoạch tuyến tính - Chương 5: Sơ đồ pert

11/14/2011 1 Bài giảng QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á ThS. Nguyễnããã Vănêêê Phong Email : nvphong1980@gmail.com, nv.phong@ufm.edu.com ĐẠI HỌC TÀI CHÍNH Ï Ï ØÏ Ï ØÏ Ï Ø – MARKETING BỘ MÔN TOÁN Ä Â ÙÄ Â ÙÄ Â Ù – KHOA CƠ BẢNÛÛÛ 2 Chương 5. SƠ ĐỒ PERTÀÀÀ QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê (PERT: Program Evaluation and Review Technique) 1. CÁCÙÙÙ VÍ DỤÏÏÏ 2. MỘTÄÄÄ SỐÁÁÁ KHÁIÙÙÙ NIỆMÄÄÄ 3. LẬPÄÄÄ SƠ ĐỒÀÀÀ PERT 4. PHÂNÂÂÂ TÍCH SƠ ĐỒÀÀÀ PERT 5. MỘTÄÄÄ SỐÁÁÁ LƯU ÝÙÙÙ 3 CÁC VÍ DỤÙ ÏÙ ÏÙ Ï QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê Công việc Trình tự Thời gian Kiếm vợ Bắt đầu ngay 6 Kiếm tiền mua nhà Bắt đầu ngay 12 Kiếm tiến cưới vợ Bắt đầu ngay 7 Đám nói Sau 1 2 Đám hỏi Sau 2,3,4 4 Chụp hình cưới Sau 5 3 Chọn đồ cưới, nữ trang Sau 5 4 Chọn nơi đăt tiệc Sau 5 5 Đám cưới Sau 6,7,8 1 Ví dụïïï1. 11/14/2011 2 4 CÁC VÍ DỤÙ ÏÙ ÏÙ Ï QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê Vấnááá đềààà đặtëëë ra : 1. Thờiøøø gian ngắnééé nhấtááá đểååå hoànøøø thànhøøø côngâââ việcäää ? 2. Muốnááá rútùùù ngắnééé thờiøøø gian hoànøøø thànhøøø côngâââ việcäää ta cầnààà rútùùù ngắnééé thờiøøø gian củảûû nhữngõõõ côngâââ việcäää nàòøø ? 3. Nhữngõõõ côngâââ việcäää nàòøø cóùùù thểååå hoànøøø thànhøøø chậmäää trểååå mộtäää khoảngûûû thờiøøø gian nàòøø đóùùù màøøø khôngâââ ảnhûûû hưởngûûû đếnááá thờiøøø gian ngắnééé nhấtááá củảûû toànøøø bộäää côngâââ việcäää . Ví dụïïï1. 5 CÁC VÍ DỤÙ ÏÙ ÏÙ Ï QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê Ví dụïïï2. 6 MỘT SỐ KHÁI NIỆMÄ Á Ù ÄÄ Á Ù ÄÄ Á Ù Ä QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1. Đồààà thị. Làøøø tậpäää hợpïïï gồmààà cácùùù đỉnh (A), cácùùù cạnhïïï , cácùùù cung (U) nốiááá cácùùù đỉnh. - Kýùùù hiệuäää : G(A,U) – đồààà thị G. Đỉnh A1 Cung U Cạnhïïï U A2 A3 A4 -Đồààà thị G đượcïïï gọiïïï làøøø cóùùù hướngùùù nếuááá G chỉ chứáùù cácùùù cung . -Dâyâââ chuyềnààà : Làøøø tậpäää gồmààà cácùùù đỉnh vàøøø cung kếááá tiếpááá nhau. -Đườngøøø đi : Làøøø mộtäää dâyâââ chuyềnààà màøøø mỗiããã đỉnh củảûû cung trướcùùù sẽõõõ làøøø ngọnïïï củảûû cung sau -Khuyênâââ : làøøø mộtäää cung cóùùù đỉnh gốcááá vàøøø ngọnïïï trùngøøø nhau -Chu trình : làøøø mộtäää đườngøøø đi cóùùù đỉnh đầuààà vàøøø đỉnh cuốiááá trùngøøø nhau 11/14/2011 3 7 MỘT SỐ KHÁI NIỆMÄ Á Ù ÄÄ Á Ù ÄÄ Á Ù Ä QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 2. Sơ đồààà mạngïïï (PERT). Làøøø mộtäää đồààà thị hữũõõ hạnïïï , cóùùù hướngùùù , khôngâââ khuyênâââ , khôngâââ chu trình vàøøø mỗiããã 1 cung gánùùù mộtäää sốááá thựcïïï khôngâââ âmâââ (đượcïïï gọiïïï làøøø độäää dàiøøø cung). A1 A2 A3 A5 A4 2 4 7 5 9 8 -Độäää dàiøøø đườngøøø đi: Làøøø tổngååå độäää dàiøøø củảûû cácùùù cung thuộcäää đườngøøø đi. -Đườngøøø đi dàiøøø nhấtááá : Độäää dàiøøø lớnùùù nhấtááá trong cácùùù đườngøøø đi từøøø đỉnh I đếnááá j 8 MỘT SỐ KHÁI NIỆMÄ Á Ù ÄÄ Á Ù ÄÄ Á Ù Ä QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 3. Trong sơ đồààà mạngïïï (PERT) ta cóùùù cácùùù kháiùùù niệmäää sau: - Đỉnh: Tương ứngùùù vớiùùù mộtäää sựïïï kiệnäää (Hoànøøø thànhøøø mộtäää sốááá côngâââ việcäää vàøøø bắtééé đầuààà mộtäää sốááá côngâââ việcäää khácùùù ). - Cung : Tương ứngùùù vớiùùù mộtäää côngâââ việcäää . - Độäää dàiøøø cung : Tương ứngùùù vớiùùù thờiøøø gian định mứcùùù cho côngâââ việcäää . - Dựïïï ánùùù : Làøøø 1 quáùùù trình gồmààà cácùùù côngâââ việcäää , nhiệmäää vụïïï cóùùù liênâââ quan vớiùùù nhau, đượcïïï thựcïïï hiệnäää nhằmèèè đạtïïï đượcïïï mụcïïï tiêuâââ đãõõõ đềààà ra trong điềuààà kiệnäää ràngøøø buộcäää vềààà thờiøøø gian, nguồnààà lựcïïï , ngânâââ sáchùùù . i j tij 9 MỘT SỐ CHÚ Ý KHI THIẾT KẾ PERTÄ Á Ù Ù Á ÁÄ Á Ù Ù Á ÁÄ Á Ù Ù Á Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1. Công việc bắt đầu khi ,y hoàn thành i s t y y yi yt ys 2. Công việc ,y bắt đầu khi hoàn thành s t i y y ys yt yi 2 1 3 1 4 1 1 1 3 2 ,y y y y y y3. BĐ khi HT , BĐ khi HT BĐ khi HT 2y 3y 11 6( / )y 11 2( / )y11 3( / )y 4y 11/14/2011 4 10 MỘT SỐ CHÚ Ý KHI THIẾT KẾ PERTÄ Á Ù Ù Á ÁÄ Á Ù Ù Á ÁÄ Á Ù Ù Á Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1 24. Hai công việc , cùng BĐ tại (i) và kết thúc tại (j).y y i Nếu hai công việc cùng tính chất. 1y 2y biến đổi thành 1 2y y+ j ji Nếu hai công việc có tính chất khác nhau: Thêm đỉnh mới cung giả có độ dài bằng 0 i 1y 2y biến đổi thành 1y j ji 2y Cung giảûûû 11 MỘT SỐ CHÚ Ý KHI THIẾT KẾ PERTÄ Á Ù Ù Á ÁÄ Á Ù Ù Á ÁÄ Á Ù Ù Á Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1y 2y 2y 4y 5. y4 BĐ sau khi y1 , y 2 HT; y5 BĐ sau khi y1 , y 2 , y 3 HT 1y 3y 5y 1y 2y 3y 4y 5y 0Biếnááá đổiååå thànhøøø 6. y2 BĐ sau khi y1 HT, y 3 BĐ sau khi y1 , y 2 HT Biếnááá đổiååå thànhøøø 1y 2y 1y 2y 3y 1y 2y 3y 12 MỘT SỐ CHÚ Ý KHI THIẾT KẾ PERTÄ Á Ù Ù Á ÁÄ Á Ù Ù Á ÁÄ Á Ù Ù Á Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 7. Tính đơn : Giữãõõ hai đỉnh bấtááá kỳøøø cóùùù nhiềuààà nhấtááá mộtäää cung nốiááá 8. y2 BĐ sau khi y1 HT, y 3 BĐ sau khi y1 , y 2 HT 1y 3y 4y 2y 5y 1y 3y 2y 4y 5y Biếnááá đổiååå thànhøøø 0 02 y 11/14/2011 5 13 MỘT SỐ CHÚ Ý KHI THIẾT KẾ PERTÄ Á Ù Ù Á ÁÄ Á Ù Ù Á ÁÄ Á Ù Ù Á Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 9. y3 BĐ sau khi y1 HT, y4 BĐ sau khi y 2 HT, y5 BĐ sau khi y1 , y2 HT 1y 2y 2y 3y 1y 5y 1y 4y 2y 3y 5yBiếnááá đổiååå thànhøøø 0 0 4y 14 MỘT SỐ CHÚ Ý KHI THIẾT KẾ PERTÄ Á Ù Ù Á ÁÄ Á Ù Ù Á ÁÄ Á Ù Ù Á Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 10. y4 BĐ sau khi y1 HT, y5 BĐ sau khi y1 , y 2 HT, y6 BĐ sau khi y1 , y2 , y 3 HT, y7 BĐ sau khi y4 , y5 6y 2y 3y 1y 7y 4y 5y 0 0 15 MỘT SỐ CHÚ Ý KHI THIẾT KẾ PERTÄ Á Ù Ù Á ÁÄ Á Ù Ù Á ÁÄ Á Ù Ù Á Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 4. Cáchùùù vẽõõõ sơ đồààà PERT + Xácùùù định 3 loạiïïï côngâââ việcäää - Côngâââ việcäää khởiûûû côngâââ (Bắtééé đầuààà ngay) - Côngâââ việcäää kếtááá thúcùùù (làøøø cácùùù côngâââ việcäää chỉ nằmèèè ởûûû cộtäää côngâââ việcäää ), khôngâââ nằmèèè ởûûû cộtäää trình tựïïï thựcïïï hiệnäää - Côngâââ việcäää trung gian + Vẽõõõ cácùùù sơ đồààà con + Hiệuäää chỉnh vàøøø nốiááá cácùùù sơ đồààà con + Đánhùùù sốááá cácùùù đỉnh: - Đánhùùù sốááá 1 cho đỉnh khởiûûû côngâââ - Giảûûû sửûûû ta đánhùùù sốááá i cho cho 1 đỉnh nàòøø đóùùù, khi đóùùù ta tạmïïï xoáùùù cácùùù cung cóùùù đỉnh gốcááá làøøø đỉnh i. Xem đỉnh chỉ cóùùù cácùùù cung đi ra đánhùùù sốááá i + 1 (nếuááá cóùùù nhiềuààà đỉnh như vậyäää ta lầnààà lượtïïï đánhùùù i + 1, i + 2, )đãõõõ đánhùùù - Tiếpááá tụcïïï cho đếnááá khi cácùùù đỉnh đượcïïï đánhùùù sốááá . 11/14/2011 6 16 MỘT SỐ CHÚ Ý KHI THIẾT KẾ PERTÄ Á Ù Ù Á ÁÄ Á Ù Ù Á ÁÄ Á Ù Ù Á Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê Ví dụïïï 3. Côngâââ việcäää Trình tựïïï Thờiøøø gian Y1 Bắtééé đầuààà ngay 15 Y2 Bắtééé đầuààà ngay 21 Y3 Sau Y1 9 Y4 Sau Y1 16 Y5 Sau Y2 17 Y6 Sau Y2 20 Y7 Sau Y2 19 Y8 Sau Y3 vàøøø Sau Y5 14 Y9 Sau Y4 11 Y10 Sau Y4 14 Y11 Sau Y7 10 Y12 Sau Y6, Y8 , Sau Y9 Y11 18 Y13 Sau Y7 11 17 MỘT SỐ CHÚ Ý KHI THIẾT KẾ PERTÄ Á Ù Ù Á ÁÄ Á Ù Ù Á ÁÄ Á Ù Ù Á Á QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê Ví dụïïï 3. 1 2 5 7 84 3 6 1y 2y 3y 5y 6y 8y 4y 10y 9y 12y 7y 13y 18 MỘT SỐ CHỈ TIÊU TRÊN SƠ ĐỒÄ Á Â Â ÀÄ Á Â Â ÀÄ Á Â Â À QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1. Chỉ tiêuâââ thờiøøø gian đốiááá vớiùùù đỉnh 1.1. Thờiøøø gian sớmùùù củảûû đỉnh. Thờiøøø gian sớmùùù củảûû đỉnh j làøøø thờiøøø điểmååå sớmùùù nhấtááá màøøø mọiïïï côngâââ việcäää tương ứngùùù vớiùùù cácùùù cung đi tớiùùù đỉnh j đềuààà hoànøøø thànhøøø . s j tKýùùù hiệuäää : 1 0 s t =- Tạiïïï thờiøøø điểmååå bấtááá đầuààà ( ) ( ) ( )1 2, , , , ..., ,ki j i j i j- Tạiïïï mộtäää đỉnh j bấtááá kỳøøø (j > 1), giảûûû sửûûû cóùùù k cung đếnááá j vàøøø thờiøøø gian sớmùùù củảûû cácùùù đỉnh tương ứngùùù làøøø : k s i t Khi đóùùù , vớiùùù thờiøøø gian định mứcùùù tương ứngùùù cácùùù côngâââ việcäää sẽõõõ hoànøøø tạiïïï cácùùù thờiøøø điểmååå ki j t k k s i i j t t+ Thờiøøø gian sớmùùù sẽõõõ đượcïïï xácùùù định theo côngâââ thứcùùù
{ } { } 1 0 Tập các đến đỉnh jä ù áä ù áä ù ámax : k k s s s j i j i j k U t t t t U ∈  =   = + =  11/14/2011 7 19 MỘT SỐ CHỈ TIÊU TRÊN SƠ ĐỒÄ Á Â Â ÀÄ Á Â Â ÀÄ Á Â Â À QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê Lưu ýùùù : -Khi tính thờiøøø gian sớmùùù củảûû đỉnh ta đi theo thứùùù tựïïï từøøø đỉnh 1 tớiùùù đỉnh j. -Khờiøøø gian sớmùùù củảûû đỉnh j làøøø độäää dàiøøø đườngøøø đi dàiøøø nhấtááá từøøø đỉnh khởiûûû côngâââ đếnááá j. -Chúùùù ýùùù cóùùù bao nhiêuâââ cung đếnááá j -Ta cóùùù Làøøø đỉnh kếááá trướcùùù j vàøøø nằmèèè trênâââ đườngøøø dàiøøø nhấtááá từøøø 1 đếnááá j. { }0 00 1 với ùùù max ks sj i i j i jk i t t t t= + = + 1.2. Thờiøøø điểmååå muộnäää củảûû đỉnh. Làøøø thờiøøø điểmååå muộnäää nhấtááá , màøøø mọiïïï côngâââ việcäää tương ứngùùù vớiùùù cácùùù cung đi tớiùùù đỉnh i đềuààà hoànøøø thànhøøø (thờiøøø điểmååå muộnäää nhấtááá hoànøøø thànhøøø đỉnh i ) màøøø khôngâââ làmøøø thay đổiååå thờiøøø điểmååå sớmùùù nhấtááá hoànøøø thànhøøø toànøøø bộäää . - Gọiïïï đỉnh kếtááá thúcùùù làøøø đỉnh n, ta cóùùù m s n n t t= Kýùùù hiệuäää : mit - Tạiïïï mộtäää đỉnh i, giảûûû sửûûû cácùùù cung cóùùù đỉnh gốcááá làøøø i ( ) ( ) ( )1 2, , , ,..., kji j i j i - Thờiøøø gian muộnäää cácùùù đỉnh tương ứngùùù 1 2 , , ..., k m m m j j j t t t 20 MỘT SỐ CHỈ TIÊU TRÊN SƠ ĐỒÄ Á Â Â ÀÄ Á Â Â ÀÄ Á Â Â À QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê - Vớiùùù thờiøøø gian định mứcùùù tương ứngùùù 1 2 , , ..., kij ij ij t t t - Ta cóùùù ràngøøø buộcäää k k k k m m m m i ij j i j ij t t t t t t+ ≤ ⇒ ≤ − - Thờiøøø điểmååå muộnäää củảûû đỉnh đượcïïï xácùùù định
{ } { } R= tập các cung có đỉnh gốc là iä ù ù á øä ù ù á øä ù ù á ømin :k k m s n n m m i j ij k R t t t t t ∈  =   = −  - Ghi cácùùù chỉ tiêuâââ thờiøøø gian lênâââ đỉnh j s j t j k m j t Đỉnh thứùùù j Thờiøøø gian sớmùùù , muộnäää củảûû đỉnh Đỉnh kếááá trướcùùù j vàøøø nằmèèè trênâââ đườngøøø dàiøøø nhấtááá từøøø 1 đếnááá j. 21 MỘT SỐ CHỈ TIÊU TRÊN SƠ ĐỒÄ Á Â Â ÀÄ Á Â Â ÀÄ Á Â Â À QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1.3. Thờiøøø gian dựïïï trữõõõ củảûû đỉnh m s j j j d t t= − 1.4. Đườngøøø Gantt - Làøøø đườngøøø đi dàiøøø nhấtááá từøøø đỉnh khởiûûû côngâââ đếnááá đỉnh kếtááá thúcùùù . - Cácùùù côngâââ việcäää nămêêê trênâââ đườngøøø gantt gọiïïï làøøø côngâââ việcäää gantt - Cácùùù đỉnh nằmèèè trênâââ đườngøøø gantt gọiïïï làøøø đỉnh gantt Ý ÙÙÙ nghĩa: - Độäää dàiøøø đườngøøø gantt làøøø thờiøøø gian ngắnééé nhấtááá hoànøøø thànhøøø toànøøø bộäää dựïïï ánùùù - Nếuááá mộtäää côngâââ việcäää trênâââ gantt chậmäää trểååå thì toànøøø bộäää dựïïï ánùùù sẽõõõ chậmäää trểååå -Thờiøøø gian hoànøøø thànhøøø toànøøø bộäää dựïïï ánùùù đượcïïï rútùùù ngắnééé khi độäää dàiøøø củảûû mọiïïï đườngøøø gantt đượcïïï rútùùù ngắnééé . Lưu ýùùù : Đườngøøø gantt làøøø đườngøøø qua cácùùù đỉnh, cóùùù , hay cóùùù Ví dụïïï . (xétùùù lạiïïï ví dụïïï 3) Yêuâââ cầuààà : xácùùù định cácùùù chỉ tiêuâââ thờiøøø gian, tìm đườngøøø gantt. 0 j d =m s j j t t= 11/14/2011 8 22 MỘT SỐ CHỈ TIÊU TRÊN SƠ ĐỒÄ Á Â Â ÀÄ Á Â Â ÀÄ Á Â Â À QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1 0 − 0 8 70 7 70 4 38 3 38 7 52 4 52 2 15 1 25 3 21 1 21 5 31 2 41 6 40 3 42 1 15:y 2 21:y 3 9:y 4 16:y 5 17:y 6 20:y 7 19:y 8 14:y 9 11:y 10 14:y 11 10:y 12 18:y 13 11:y Đườngøøø gantt: Thờiøøø gian gantt: 21 17 14 181 3 4 7 8→ → → → 21 17 14 18 70+ + + = 23 MỘT SỐ CHỈ TIÊU TRÊN SƠ ĐỒÄ Á Â Â ÀÄ Á Â Â ÀÄ Á Â Â À QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 2. Chỉ tiêuâââ thờiøøø gian đốiááá vớiùùù côngâââ việcäää 2.1. Thờiøøø điểmååå sớmùùù . 2.1.1. Khởiûûû côngâââ sớmùùù : 2.1.2. Hoànøøø thànhøøø sớmùùù : 2.2. Thờiøøø điểmååå muộnäää . 2.2.1. Hoànøøø thànhøøø muộnäää : 2.2.2. Khởiûûû côngâââ muộnäää : 2.3. Thờiøøø gian dựïïï trữõõõ củảûû côngâââ việcäää 2.3.1. Thờiøøø gian dựïïï trữõõõ chung: 2.3.2. Thờiøøø gian dựïïï trữõõõ độcäää lậpäää : 2.3.3. Dựïïï trữõõõ riêngâââ ngọnïïï : 2.3.4. Dựïïï trữõõõ riêngâââ gốcááá : ks s ij j t t= hs ks ij ij ij t t t= + hm m ij j t t= km hm ij ij ij t t t= − ( )c m sij j j ijd t t t= − + ( ){ }0max ,d s mij j j ijd t t t= − + n s s ij j i ij d t t t= − − g m m ij j i ij d t t t= − − 24 MỘT SỐ CHỈ TIÊU TRÊN SƠ ĐỒÄ Á Â Â ÀÄ Á Â Â ÀÄ Á Â Â À QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê Ý ÙÙÙ nghĩa: n s s ij j i ij d t t t= − − g m m ij j i ij d t t t= − − (Dựïïï trữõõõ tựïïï do khởiûûû sớmùùù , dựïïï trữõõõ bắtééé buộcäää ) Làøøø dựïïï trữõõõ khi sửûûû dụngïïï sẽõõõ tựïïï do khởiûûû côngâââ sớmùùù hoặcëëë kéóùù dàiøøø thờiøøø gian côngâââ việcäää màøøø khôngâââ ảnhûûû hưởngûûû đếnááá sựïïï khởiûûû côngâââ sớmùùù củảûû cácùùù côngâââ việcäää tiếpááá theo. (Dựïïï trữõõõ tựïïï do khởiûûû muộnäää , dựïïï trữõõõ liênâââ quan) Làøøø dựïïï trữõõõ khi sửûûû dụngïïï sẽõõõ tựïïï do khởiûûû côngâââ muộnäää hoặcëëë kéóùù dàiøøø thờiøøø gian côngâââ việcäää màøøø khôngâââ ảnhûûû hưởngûûû đếnááá sựïïï khởiûûû côngâââ muộnäää củảûû cácùùù côngâââ việcäää tiếpááá theo. Làøøø mứcùùù thờiøøø gian dựïïï trữõõõ chung cho cácùùù côngâââ việcäää cho phépùùù thờiøøø gian kéóùù dàiøøø củảûû cácùùù côngâââ việcäää khôngâââ đượcïïï phépùùù vượtïïï quáùùù . ( )c m sij j j ijd t t t= − + Côngâââ việcäää khôngâââ gantt : cóùùù hai loạiïïï - Côngâââ việcäää khôngâââ gantt độcäää lậpäää : Làøøø côngâââ việcäää khôngâââ gantt tương ứngùùù vớiùùù cung cóùùù hai đầuààà mútùùù làøøø hai đỉnh gantt - Côngâââ việcäää khôngâââ gantt liênâââ quan : Làøøø côngâââ việcäää khôngâââ gantt cònøøø lạiïïï 11/14/2011 9 25 MỘT SỐ CHỈ TIÊU TRÊN SƠ ĐỒÄ Á Â Â ÀÄ Á Â Â ÀÄ Á Â Â À QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê Ví dụïïï . Xétùùù lạiïïï ví dụïïï 3. 1 2 3 4 5 6 7 8 9 10 11 12 13 CV CUNG TGĐM KCS HTS HTM KCM DTC TGS TGM DTĐ DTRN DTRG Y1 (1,2) 15 0 15 25 10 10 15 0 0 0 10 Y2 (1,3) 21 0 21 21 0 0 21 0 0 0 0 Y3 (2,4) 9 15 24 38 29 14 38 25 4 14 4 Y4 (2,5) 16 15 31 41 25 10 31 25 0 0 0 Y5 (3,4) 17 21 38 38 21 0 38 21 0 0 0 Y6 (3,7) 20 21 41 52 32 11 52 21 11 11 11 Y7 (3,6) 19 21 40 42 23 2 40 21 0 0 2 Y8 (4,7) 14 38 52 52 38 0 52 38 0 0 0 Y9 (5,7) 11 31 42 52 41 10 52 41 0 10 0 Y10 (5,8) 14 31 45 70 56 25 70 41 15 25 15 Y11 (6,7) 10 40 50 52 42 2 52 42 0 2 0 Y12 (7,8) 18 52 70 70 52 0 70 52 0 0 0 Y13 (6,8) 11 40 51 70 59 19 70 42 17 19 17 26 ĐÁNH GIÁ KHẢ NĂNG HOÀN THÀNHÙ Ù Û Ê Ø ØÙ Ù Û Ê Ø ØÙ Ù Û Ê Ø Ø QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê 1. Ướcùùù lượngïïï thờiøøø gian hoànøøø thànhøøø côngâââ việcäää : - Thờiøøø gian dựïïï kiếnááá thựcïïï hiệnäää sớmùùù nhấtááá : - Thờiøøø gian thựcïïï hiệnäää phổååå biếnááá nhấtááá : - Thờiøøø gian thựcïïï hiệnäää kéóùù dàiøøø nhấtááá : - Thờiøøø gian hoànøøø thànhøøø DA: - Thờiøøø gian kỳøøø vọngïïï (tb) củảûû từngøøø côngâââ việcäää - Độäää lệchäää chuẩnååå Gọiïïï S làøøø thờiøøø gian mong muốnááá hoànøøø thànhøøø toànøøø bộäää dựïïï ánùùù a t m t b t ( )t Beta β∼ 4 6 a m b t t t t + + = 6 ( ) b a t t tσ − = 2 ứng với CV ganttù ùù ùù ù ( , ) : ( ) ( ) n n S N T V T t V V t tσ − = − = = ∑ ∑ ∑ ∼ 27 ĐÁNH GIÁ KHẢ NĂNG HOÀN THÀNHÙ Ù Û Ê Ø ØÙ Ù Û Ê Ø ØÙ Ù Û Ê Ø Ø QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê Gọiïïï S làøøø thờiøøø gian mong muốnááá hoànøøø thànhøøø toànøøø bộäää dựïïï ánùùù , ta cóùùù 2 ứng với CV ganttù ùù ùù ù ( , ) : ( ) ( ) n n S N T V T t V V t tσ − = − = = ∑ ∑ ∑ ∼ 2. Đánhùùù giáùùù khảûûû năngêêê dựïïï ánùùù Gọiïïï T làøøø thờiøøø hạnïïï kếááá hoạchïïï hoànøøø thànhøøø toànøøø bộäää dựïïï ánùùù . Khi đóùùù , khảûûû năngêêê đểååå hoànøøø thànhøøø toànøøø bộäää dựïïï ánùùù theo kếááá hoạchïïï làøøø ( ) 00 ( ) ( ) k n n k T T T P P S T t t ϕ ϕ σ σ    − − = ≤ ≤ = −        0 25 0 25 0 5 0 5 Không có khả năng hoàn thànhâ ù û ê ø øâ ù û ê ø øâ ù û ê ø ø có khả năng hoan thành ù û ê øù û ê øù û ê ø Có nhiều khả năng hoàn thànhù à û ê ø øù à û ê ø øù à û ê ø ø . : . . : . : P P P < < < > 11/14/2011 10 28 ĐÁNH GIÁ KHẢ NĂNG HOÀN THÀNHÙ Ù Û Ê Ø ØÙ Ù Û Ê Ø ØÙ Ù Û Ê Ø Ø QUY HOẠCH TUYẾN TÍNHÏ ÁÏ ÁÏ Á NGUYỄN VĂN PHONGÃ ÊÃ ÊÃ Ê Ví dụïïï 4. Cho mộtäää dựïïï ánùùù sau Côngâââ việcäää Trình tựïïï ta tm tb t_TB V(t) Y1 BĐN 7 9 17 10 100/36 Y2 BĐN 11 18 31 19 400/36 Y3 Sau Y1 8 10 12 10 16/36 Y4 Sau Y1 15 19 23 19 64/36 Y5 Sau Y2 , Y3 6 9 18 10 144/36 Ta cóùùù 100 16 144 26030 2 687 36 36 36 36 ; ( ) ; ( ) ( ) . n T V t t V tσ= = + + = = = Giảûûû sửûûû thờiøøø gian dựïïï kiếnááá làøøø Tk = 29, 30, 34 0 27 0 1314 0 29 0 3557 0 30 0 5 0 34 0 9319 ( ) . ; ( ) . ( ) . ; ( ) . P S P S P S P S ≤ ≤ = ≤ ≤ = ≤ ≤ = ≤ ≤ =