Dự án “ĐÀO AO THẢ CÁ” có nội dung như sau: “Đào ao (ký hiệu: A), tiến hành ngay từ đầu với thời hạn 4 tuần. Tìm nguồn và hợp đồng mua cá giống (B), 1 tuần bắt đầu ngay. Kè bờ ao (C), 2 tuần sau đào ao. Làm tường rào bao quanh (D), 3 tuần bắt đầu ngay. Rửa ao, nhận cá giống và thả cá (E), 1 tuần sau kè bờ ao và tìm nguồn, hợp đồng mua cá giống”. Cho biết thời gian mong muốn ngắn nhất của công việc A là 3; B là 1; C là 1,5; D là 2 và E là 0,5 tuần. Chi phí rút ngắn thời gian của công việc A là 10; C là 8,5; D là 5 và E là 9,5 triệu đồng/tuần. Nếu phải rút ngắn thời gian thi công dự án xuống 1 tuần và đơn vị rút ngắn lấy theo số nguyên của tuần, thì?

Phân tích bài toán: 1. **Xác định các công việc và thời gian thực hiện:** - A (Đào ao): 4 tuần (mong muốn 3 tuần) - B (Tìm nguồn và hợp đồng mua cá): 1 tuần (mong muốn 1 tuần) - C (Kè bờ ao): 2 tuần sau A, thời gian thực hiện 1.5 tuần (mong muốn 1.5 tuần) - D (Làm tường rào): 3 tuần, thời gian thực hiện 2 tuần (mong muốn 2 tuần) - E (Rửa ao, nhận cá, thả cá): 1 tuần sau C và B, thời gian thực hiện 0.5 tuần (mong muốn 0.5 tuần) 2. **Xác định mối quan hệ phụ thuộc:** - C phụ thuộc vào A - E phụ thuộc vào C và B 3. **Tính thời gian tối thiểu của dự án:** - Thời gian hoàn thành A là 4 tuần. - C bắt đầu sau A 2 tuần và kéo dài 1.5 tuần. Vậy C hoàn thành sau A 3.5 tuần. Do đó, C hoàn thành sau 2+1.5= 3.5 tuần kể từ khi bắt đầu dự án - B bắt đầu ngay và kéo dài 1 tuần. - E bắt đầu sau C và B 1 tuần, và kéo dài 0.5 tuần. Vậy E hoàn thành sau max(3.5, 1) + 1 + 0.5 = 5 tuần kể từ khi bắt đầu dự án - D bắt đầu sau 3 tuần và kéo dài 2 tuần. Vậy D hoàn thành sau 3+2 = 5 tuần kể từ khi bắt đầu dự án Thời gian hoàn thành dự án là max(thời gian hoàn thành E, thời gian hoàn thành D) = max(5,5) = 5 tuần. 4. **Rút ngắn dự án 1 tuần:** - Cần rút ngắn xuống còn 4 tuần. - Ta thấy E và D hoàn thành sau 5 tuần. Để rút ngắn xuống 4 tuần, ta phải rút ngắn A hoặc kết hợp rút ngắn các công việc khác. - Tuy nhiên, B không thể rút ngắn thêm. E chỉ có thể rút ngắn sau khi C rút ngắn. - C phụ thuộc vào A, vì vậy để rút ngắn E, phải rút ngắn A. Chi phí rút ngắn A là 10 triệu/tuần. - D có thể rút ngắn với chi phí 5 triệu/tuần. - C có thể rút ngắn với chi phí 8.5 triệu/tuần *Các phương án rút ngắn 1 tuần: 1. Rút ngắn D 1 tuần (chi phí 5 triệu): Khả thi. Khi đó D kết thúc sau 4 tuần. 2. Rút ngắn A 1 tuần (chi phí 10 triệu): Khả thi. Khi đó C bắt đầu sau 1 tuần, kết thúc sau 2.5 tuần. E kết thúc sau 2.5+1+0.5 = 4 tuần. Vậy có 2 phương án khả thi.