Bài tập C++ | Bài toán lập lịch phân công công việc

[flyflo111]

13. Có n công việc và k thợ cả, biết rằng mỗi người thợ đều làm được mọi công việc và làm công việc thứ i mất Ti¬ thời gian. Các công việc này có liên quan với nhau, phụ thuộc vào các số Pij với i<j, trong đó :
- Nếu Pij=1 thì công việc i cần thực hiện trước công việc j
- Nếu Pij=-1 thì công việc i cần thực hiện sau công việc j
- Nếu Pij=0 thì công việc i, j độc lập với nhau.
Hãy lập lịch phân công cho k thợ cả thực hiện n công việc trên sao cho thời gian để thực hiện các công việc trên là nhỏ nhất và các điều kiện Pij phải được thỏa mãn.


Mọi người có thể gợi hướng giúp em xem bài này nên giải ra sao ko ạ. Cảm ơn.

[soda_chanhmuoi]

Hơ, nghe wen wen, giống môn lý thuyế đồ thị, vẽ đồ thị(có hướng) biểu diễn quá tình hoàn thành công việc, các đỉnh là thứ tự công việc rồi độ dài cạnh là thời gian để hoàn thành, roài tìm đường đi ngắn nhất, nói là thế nhưng ko biết cài đặt sorry!!

[kidkid]

Uhm giống mấy bài thi olympic quá ha ? Mấy gà VN mình hay thay đổi số liệu lại của cùng 1 dạng rồi ra đề như thế này lắm !

[flyflo111]

Vậy ai biết thì gợi ý sơ sơ cho mình với, được ko vậy.

[soda_chanhmuoi]

Thì đó, dùng danh sách kề để lưu đồ thị, roài dùng giải thuật Disktra để tìm ra đường đi ngắn nhất!

[whoru]

Rất tiếc, mình ko thể đưa ra lời gợi ý cho bạn về mặt giải thuật được. Nó chính là một bài toán có ý nghĩa thực tiễn trong việc lập lịch làm việc, trong xây dựng, trong các dự án, công trình... Có thể giải bài toán này bằng phương pháp "sơ đồ mạng PERT": xây dựng sơ đồ mạng, tính các chỉ tiêu thời gian và xác định đường găng. Bạn có thể xem một số giáo trình về "Tối ưu hóa" và "Quy hoạch tuyến tính" để biết về nó. Chẳng hạn:
+ Lý thuyết qui hoạch. Tập 1 - Hoàng Tụy - NXB Khoa học Hà Nội 1968.
+ Quy hoạch tuyến tính( Lý thuyết và bài tập ) - Đặng Hấn - Trường ĐH Kinh tế TPHCM 1995.
+ Giáo trình Tối ưu hóa - Trần Vũ Thiệu,Võ Văn Tuấn Dũng - ĐH DL Kỹ thuật công nghệ 2003
+ Tối ưu hóa: Quy hoạch tuyến tính và rời rạc - Nguyễn Đức Nghĩa - NXB Giáo Dục, Hà Nội 1997 ( cuốn này cơ bản nhất ).
Tuy nhiên chú ý rằng phương pháp sơ đồ mạng PERT phải kết hợp với lý thuyết quy hoạch tuyến tính mới có thể giải quyết trọn vẹn bài toán - vì số nhân lực k là tổng quát và hãy thử tưởng tượng có nhiều công việc có thể làm đồng thời nhưng trong tay bạn lúc đó không có đủ người để bố trí thì sao?
Trong thực tế có khi nào có trường hợp k = 1 ko ta?

Thân!

[kidkid]

hơ hơ bác whoru giỏi thật nói cái gì là em chả hiểu cái nấy ! Đúng là "Ngọa Hổ Tàng Long" ka ka .

[flyflo111]

Mình nói thiệt là mình rất noob đọc mãi mà chẳng hiểu gì cả, ai có thể chỉ rõ hơn thêm được không ạ. Cảm ơn mọi người.

[kidkid]

ai có thể chỉ rõ hơn thêm được không ạ.

Tớ cũng không biết nhưng cậu phải nói là cậu không hiểu chỗ nào chứ , còn nếu là không hiểu chi hết từ a đến z thì anh em cũng không biết giảng giải sao ?

[phanluong]

hua hua minh khong hieu gi het