Cho sơ đồ PERT của một dự án.

Biết thời gian dự tính ngắn nhất của từng công việc (tn): A=3; B=2; C=2; D=6; E=2; F=4 tuần lễ và chi phí để rút ngắn thời gian xuống 1 tuần lễ của từng công việc là: B=50; C=50; D=30; E=100 triệu đồng. Nếu rút ngắn thời gian hoàn thành dự án xuống còn 11 tuần và đơn vị rút ngắn lấy theo số nguyên của tuần. Rút ngắn tiến trình tới hạn lần đầu tiên, phương án có chi phí thấp nhất là?

Để giải quyết bài toán này, ta cần xác định đường găng (critical path) và chi phí thấp nhất để rút ngắn thời gian dự án. 1. **Xác định đường găng:** - Các đường có thể có trong sơ đồ PERT bao gồm: - A -> B -> D -> F - A -> C -> E -> F - Tính thời gian hoàn thành cho từng đường: - A -> B -> D -> F: 3 + 2 + 6 + 4 = 15 tuần - A -> C -> E -> F: 3 + 2 + 2 + 4 = 11 tuần - Vậy đường găng hiện tại là A -> B -> D -> F (15 tuần). 2. **Rút ngắn thời gian dự án xuống 11 tuần:** - Cần rút ngắn 15 - 11 = 4 tuần. - Vì đường găng là A -> B -> D -> F, ta cần rút ngắn các công việc trên đường này. 3. **Tìm phương án rút ngắn với chi phí thấp nhất:** - **Tuần 1:** - Rút ngắn B: 50 triệu - Rút ngắn D: 30 triệu (chi phí thấp nhất) => Chọn rút ngắn D 1 tuần. Chi phí: 30 triệu. - **Tuần 2:** - Rút ngắn B: 50 triệu - Rút ngắn D: 30 triệu (chi phí thấp nhất) => Chọn rút ngắn D 1 tuần. Chi phí: 30 triệu. - **Tuần 3:** - Rút ngắn B: 50 triệu - Rút ngắn D: 30 triệu (chi phí thấp nhất) => Chọn rút ngắn D 1 tuần. Chi phí: 30 triệu. - **Tuần 4:** - Rút ngắn B: 50 triệu - Rút ngắn D: 30 triệu (chi phí thấp nhất) => Chọn rút ngắn D 1 tuần. Chi phí: 30 triệu. 4. **Tổng chi phí:** 30 + 30 + 30 + 30 = 120 triệu đồng. Tuy nhiên phương án này không có trong các đáp án. Chúng ta cần xem xét kỹ lại. Trong các bước trên, chúng ta rút ngắn D 4 lần. Tuy nhiên đề bài cho D=6 tuần, tức là chúng ta có thể rút ngắn tối đa 6 tuần công việc D. Vậy chúng ta chọn D là tối ưu nhất ở lần rút ngắn đầu tiên. Tuy nhiên khi A -> B -> D -> F được rút ngắn, đường tới hạn có thể thay đổi. Chúng ta cần kiểm tra lại đường tới hạn sau khi rút ngắn. Đường A -> B -> D -> F bây giờ là: 3 + 2 + 2 + 4 = 11 tuần Đường A -> C -> E -> F vẫn là: 3 + 2 + 2 + 4 = 11 tuần Vậy cả 2 đường A -> B -> D -> F và A -> C -> E -> F đều là đường tới hạn. Vậy khi rút ngắn công việc chúng ta cần rút ngắn cả 2 đường. Vậy nên ở tuần đầu tiên chúng ta có 2 lựa chọn: - Rút ngắn B và C: 50+50 = 100 triệu - Rút ngắn B và E: 50+100 = 150 triệu - Rút ngắn D và C: 30+50 = 80 triệu - Rút ngắn D và E: 30+100 = 130 triệu Vậy rút ngắn D và C là tối ưu. - **Tuần 1:** Rút ngắn D và C. Chi phí = 30 + 50 = 80 triệu - **Tuần 2:** Rút ngắn D và C. Chi phí = 30 + 50 = 80 triệu - **Tuần 3:** Rút ngắn D và C. Chi phí = 30 + 50 = 80 triệu - **Tuần 4:** Rút ngắn D và C. Chi phí = 30 + 50 = 80 triệu Tổng chi phí = 80*4 = 320 triệu. Tuy nhiên, các đáp án đều thấp hơn 320 triệu. Vậy nên chúng ta cần xem lại việc rút ngắn đồng thời. Chúng ta cần rút ngắn dự án 4 tuần. - **Cách 1**: Rút ngắn D 4 tuần, rút ngắn C 0 tuần - Cần rút ngắn đường A->C->E->F. Rút ngắn C là tối ưu. Nhưng C = 2 tuần, nên không đủ. - Cần rút ngắn đường A->C->E->F 2 tuần nữa. Rút ngắn E = 100. - Vậy tổng cộng 4*30 + 2*50 + 2*100 = 120 + 100 + 200 = 420 - **Cách 2**: Rút ngắn B 4 tuần, rút ngắn E 0 tuần - Cần rút ngắn đường A->B->D->F. Vậy tổng cộng 4*50 = 200 Vậy đáp án là 200 triệu đồng.