vận trù học 9

Tham khảo tài liệu vận trù học 9, tài chính - ngân hàng, kế toán - kiểm toán phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
vận trù học 9 ng d ng trong các bài toán xác ñ nh chi phí t i thi u nhi u d ng khác. Trong ví dtrên, t p N0 qua các bư c l p ñư c phát tri n như sau: {1}, {1, 3}, {1, 3, 4, 7}, {1, 3, 4,7, 5}, {1, 4, 3, 7, 5}, {1, 4, 3, 7, 5, 6}, {1, 4, 3, 7, 5, 6, 2}.3.2. Bài toán tìm ñư ng ñi ng n nh t và quy ho ch ñ ng Bài toán tìm ñư ng ñi ng n nh t Trong bài toán tìm ñư ng ñi ng n nh t, chúng ta mu n xác ñ nh hành trình ng nnh t t m t ñ a ñi m xu t phát (ñi m g c) ñ ñi t i ñi m c n ñ n (ñi m ñích) trên m tm ng liên thông. ð cho d hi u, chúng ta xem xét ví d sau ñây. Ví d 2: Bài toán ngư i ñi du l ch. Có m t ngư i ñi du l ch, xu t phát t nút 1 và k t thúc hành trình nút 10 theohành trình trên hình III.13. 300 200 2 6 9 400 100 100 200 275 150 175 1 4 5 10 250 150 175 200 275 350 125 3 7 8 Hình III.12. Sơ ñ hành trình ñư ng ñi Ngư i du l ch xu t phát t nút 1. Trong giai ño n ñ u anh ta ch ñư c quy n (và b tbu c) ch n m t trong ba nút (thành ph ) 2, 3, 4 ñ vào thăm quan. Giai ño n ti p theo,anh ta ch ñư c ch n m t trong ba nút 5, 6, 7 ñ du l ch. Trong giai ño n ti p n i, anh tacó quy n vào m t trong hai nút 8 ho c 9 trư c khi k t thúc hành trình t i nút 10. Như v y, trong m i giai ño n ngư i ñi du l ch ch ñư c quy n ñi vào m t thành ph(m i thành ph ñư c coi là m t tr ng thái c a giai ño n ñó). Hãy tìm cách xác ñ nhñư ng ñi ng n nh t t nút 1 t i nút 10 tho mãn các ñi u ki n ñ t ra c a bài toán. Nguyên t c t i ưu Bellman trong quy ho ch ñ ng S d ng nguyên t c t i ưu Bellman trong quy ho ch ñ ng ñ gi i bài toán ngư i dul ch, chúng ta chia bài toán thành nhi u giai ño n, t c là thành nhi u bài toán nh . T im i giai ño n ta c n tìm phương án t i ưu là các phương án t t nh t c a tình tr ng hi ncó, xét trong m i quan h v i các phương án t i ưu ñã tìm ñư c c a các giai ño n trư c.Trư ng ð i h c Nông nghi p Hà N i – Giáo trình V n trù h c ………………………………..........80 Ta có th gi i quy t bài toán d n theo t ng giai ño n theo cách tính toán ti n ho ctính toán lùi. ð gi i bài toán này, ta áp d ng cách tính toán lùi (backward computing)v i các kí ki u và d ki n cho trong b ng III.19. B ng III.19. Các giai ño n c a bài toán quy ho ch ñ ng Kho ng cách Giai ño n ð u vào ð u ra ðư ng ñi t i ưu t i ñích 8 → 10 8 10 150 Giai ño n I 9 → 10 9 10 100 5→8 5 400 8 6→9 Giai ño n II 6 300 9 7→8 7 275 2→6 2 5 600 3→5 Giai ño n III 3 6 600 4→6 4 7 500 1→2 2 700 1→3 Giai ño n IV 1 3 ...