Các bài giảng về toán cho Mirella (9)

Lời giải cho bài toán khỉ bán chuối

Như Mirella đã nhận xét, khỉ phải có những lúc đi lộn ngược lại để lấy thêm chuối. Nhưng cần lộn ngược bao nhiêu lần,  ở những điểm nào, là tối ưu ?

Rõ ràng là chỉ cần lộn ngược lại điểm ban đầu không quá 2 lần, vì mỗi lần là bê đi được 1000 quả chuối, và tổng cộng chỉ có 3000 quả. Trong các lần bê chuối đi về hướng chợ, khỉ càng cố gắng bê nhiều lên, thì chỉ có làm cho kết quả cuối cùng tốt lên hay vẫn thế, chứ không làm cho kết quả tồi đi được, vì mục đích là dịch chuyển chuối về hướng chợ được càng nhiều càng tốt. Và chỉ cần 3 lần cố gắng là bê được hết đống chuối từ điểm ban đầu đi về hướng chợ.

Thay vì nói đến số lần quay đầu, ta nói đến số lần mà khỉ đi qua mỗi khúc đường thì có lẽ dễ hình dung hơn: Ví dụ như là nếu khỉ quay đầu về điểm xuất phát 2 lần, thì tức là khúc đường đầu tiên được đi qua tổng cộng 5 lần: xuôi – ngược – xuôi – ngược – xuôi – ngược. Nếu chia toàn bộ chặng đường 1000km ra thành các khúc đường theo các điểm quay đầu, thì mỗi khúc như vậy có số lần mà khỉ đi qua là một số lẻ: số lần đi xuôi nhiều hơn số lần đi ngược đúng 1 lần.

Ký hiệu Dn là hợp của các đoạn đường mà khỉ đi qua (2n-1) lần: D1 tức là chỉ đi xuôi qua 1 lần, D2 tức là có 1 lần đi ngược lại qua đó, D3 tức là có 2 lần đi ngược lại qua đó, v.v. Như có nhận xét từ trước, vì chỉ có 3000 quả chuối, vác xuôi 3 lần là hết, và số chuối càng ngày chỉ càng giảm đi chứ không nhiều lên, nên không có đoạn nào cần đi ngược lại quá 2 lần. Hơn nữa, nếu có đoạn nào mà chỉ đi ngược lại x lần (x= 0,1, …) thì tổng số chuối chở theo hướng xuôi qua đoạn đó là không quá 1000x quả, và như vậy ở các đoạn sau đoạn đó (tính về phía chợ) cũng không cần phải đi ngược lại quá x lần làm gì, mà chỉ cần đi ngược lại cùng lắm x lần là khuân được hết các quả chuối muốn khuân về phía chợ.

Lý luận trên có nghĩa là: tổng cộng đường đi của cách tối ưu gồm 3 phần D1, D2, D3, trong đó phần D3 là phần tính từ điểm xuất phát đến một một A nào đó, phần D2 là từ mốc A đến mốc B, và phần D1 là từ mốc B đến chợ.(Mỗi phần D1, D2, D3 là một đoạn thẳng, chứ không gồm nhiều đoạn đan xen kẽ nhau).

Để đỡ phải đưa ra ký hiệu mới, ta gọi luôn đội dài của đoạn D1 là D1 (tính theo km), và tương tự như vậy với D2, D3. Khi đó ta có:

(1) D_1 + D_2 + D_3 = 1000

và tất nhiên là

(2) D_1 \geq 0,D_2 \geq 0,D_3 = 1000- D_1 - D_2 \geq 0

Gọi số chuối mà khỉ mang được đến chợ là X.

Tính từ điểm mốc B, khỉ chỉ vác được 1000 chuối là cùng (vì không quay ngược lại để vác thêm) và sẽ ăn hết D1 chuối trước khi đến chợ, nên số chuối mang được đến chợ phải thỏa mãn bất đẳng thức

(3) X \leq 1000 - D_1

Nếu tính từ điểm A, thì khỉ sẽ vác được cùng lắm là 2000 chuối (vì quay lại 1 lần), nhưng ăn mất số chuối 3 D2 + D1 trên đường đến đến chợ tính từ điểm đó, nên ta có

(4) X \leq 2000 - D_1 - 3D_2

Tương tự như vậy, tính từ điểm xuất phát ban đầu, số chuối mà khỉ ăn là D1 + 3D2 + 5D3, và ta có

(5) X \leq 3000 - D_1 - 3D_2 - 5D_3

(Các số phía bên phải trong các bất đẳng thức trên, nếu không phải là số nguyên, thì có thể làm tròn lên trên thành số nguyên).

Bài toán bây giờ trở thành bài toán tối ưu có ràng buộc: tìm số nguyên X lớn nhất thỏa mãn các điều kiện (1), (2), (3), (4), (5). Cần giải hệ bất phương trình này để tìm ra X to nhất có thể và D1, D2, D3 tương ứng. Giải nó thế nào ?

Có một cách là, nhân các bất đẳng thức trên theo các hệ số dương nào đó, rồi cộng chúng vào với nhau, để được một bất đẳng thức trong đó chỉ còn có X mà không còn D1, D2, D3 nữa. Trước khi làm vậy, có thể loại bớt D3 đi cho đơn giản, bằng cách thay thế D_3 = 1000 - D_1 - D_2 theo đẳng thức (1). Khi thay thế như vậy, bất đẳng thứ (5) trở thành:

(5′) X \leq 4D_1 + 2D_2 - 2000

Lấy 2 lần bất đẳng thứ (4) cộng với 3 lần bất đẳng thức (5′), để loại đi D2, rồi cộng thêm với 10 lần bất đẳng thức (3) để loại nốt D1, ta được:

(10+2+3)X \leq 10 (1000 - D_1) + 2 (2000 - D_1 - 3D_2) + 3 (4D_1 + 2D_2 - 2000)

hay là

15 X \leq 8000

từ đó ta có

X \leq 8000/15 = 533.33

Vì X là số nguyên, nên giá trị cực đại mà X có thể nhận được là 533, đúng như cách lúc trước cho. Con số này ứng với D3=200, D2=333, D1 = 467.

Câu hỏi 

Bạn thử giải thích vì sao ta không cần dùng đến bất đẳng thức (2) trong lời giải trên ?

Ghi chú 1

Tuy D3 = 200, nhưng điều đó không có nghĩa là khỉ phải bắt buộc mang đống chuối đi 200 km từ điểm xuất phát rồi mới quay đầu lại lấy thêm chuối. Khỉ cũng có thể vận chuyển chuối bằng cách dịch chúng theo những đoạn đường ngắn hơn, chẳng hạn như là từng km một: cứ đi 1km thì quay lại lấy chuối. Bao giờ dịch hết được đống chuối đi 1km (và ăn mất 5 quả chuối), thì dịch tiếp đến km thứ hai, và cứ thế, cho đến khi đống chuối còn 2000 quả và dịch được 200km. Tiếp đó để dịch thêm mỗi km chỉ ăn hết 3 quả, cho đến khi còn 1001 quả và dịch thêm được 333 km. Chặng cuối cùng là đi một lèo.

Ghi chú 2

Bài toán khỉ bán chuối này là một ví dụ của vấn đề qui hoach tuyến tính: có một số ràng buộc tuyến tính (bằng các phương trình và bất đẳng thức tuyển tính), và phải tìm điểm cực đại của một hàm tuyến tính nào đó với các ràng buộc đã cho. Trong mô hình, ta có thể lấy X, D1,D2 làm các biến độc lập (còn D3 = D1 -D2 không phải là biến độc lập nữa), các bất đẳng thức (2), (3), (4), (5′) là các ràng buôc. Tập hợp các điểm (x,d1,d2) thỏa mãn các ràng buộc này là một tập lồi trong R3, và X đạt giá trị cực đại khi nó nằm tại một đỉnh của tập lồi đó. (Đây là một tính chất của qui hoạch tuyến tính: nếu tồn tại duy nhất nghiệm, thì nghiệm đó phải là một đỉnh của hình lồi).  Đỉnh đó chính là điểm cẳt nhau của 3 mặt được tạo thành khi các bất đẳng thức (3), (4), (5) trở thành đẳng thức. Giải ra ta được X = 533,33 nếu không có điều kiện là số nguyên, nhưng vì nó là số nguyên nên X = 533.

Bàii tập

Hãy vẽ hình lồi trong R3 gồm các điểm (X,D1,D2) thỏa mãn các bất đẳng thức (2), (3), (4), (5)

Print Friendly

Pages: 1 2

1 comment to Các bài giảng về toán cho Mirella (9)

  • ninh MonsterID Icon ninh

    cho con khỉ ăn sẵn 1000 quả rồi cho khỉ vác chuối đi nên đáp số là 1000 quả.

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

This blog is kept spam free by WP-SpamFree.