Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 12 kết quả

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

  1. #1
    Ngày gia nhập
    09 2006
    Bài viết
    3

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

    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.

  2. #2
    Ngày gia nhập
    04 2007
    Bài viết
    128

    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!!
    Đã được chỉnh sửa lần cuối bởi soda_chanhmuoi : 23-05-2007 lúc 01:53 PM.

  3. #3
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    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 !

  4. #4
    Ngày gia nhập
    09 2006
    Bài viết
    3

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

  5. #5
    Ngày gia nhập
    04 2007
    Bài viết
    128

    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!

  6. #6
    Ngày gia nhập
    02 2007
    Nơi ở
    TP.HCM - dưới cầu SG
    Bài viết
    12

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

    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!
    Đã được chỉnh sửa lần cuối bởi whoru : 25-05-2007 lúc 04:20 PM. Lý do: Sửa một số câu "tối nghĩa"
    Nơi nào khiến anh dừng bước, nơi đó có em.

  7. #7
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    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 .

  8. #8
    Ngày gia nhập
    09 2006
    Bài viết
    3

    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.

  9. #9
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    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 ?

  10. #10
    Ngày gia nhập
    06 2009
    Bài viết
    13

    hua hua minh khong hieu gi het

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn