Đến nội dung

Hình ảnh

Tìm lời giải tối ưu

- - - - - Vận trù tối ưu

  • Please log in to reply
Chủ đề này có 2 trả lời

#1
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3921 Bài viết
Xin phép anh Tình (Badman) cho em lôi bài này ra đây để các VMFer cùng thảo luận

$\fbox{Bài toán}$
Hai anh em Ân và Bình đạp xe chở nhau đến nhà Cường chơi, mải chơi quá nên đến $05:00\;pm$ mới ra về. Ân và Bình muốn mời Cường đến nhà ăn cơm. Từ nhà Cường về nhà Ân và Bình là $12km$. Khổ nỗi phương tiện duy nhất là chiếc xe đạp, đã vậy lại không thể "cân 3" được! Biết khả năng của mỗi người như sau:
$\begin{array}{|c|c|c|}\hline\;&\text{Đi bộ (km/h)}&\text{Đạp xe (km/h)} \\ \hline \text{Ân}&5&20 \\ \hline \text{Bình}&3&16 \\ \hline \text{Cường}&4&12 \\ \hline\end{array}$

Hỏi bữa cơm của 3 người bạn diễn ra sớm nhất vào mấy giờ?

#2
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3921 Bài viết
Bài toán này có ý nghĩa đời sống khá hay. Mình xin đưa ra "ý tưởng" giải quyết vấn đề này như sau:

Gợi ý

- Gọi $X_1, X_2, X_3$ theo thứ tự là vận tốc đạp xe trên các khoảng thời gian $t_1, t_2, t_3$
- Gọi $b_1, b_2$ theo thứ tự là vận tốc của người đi bộ trên đoạn đầu và đoạn thứ hai
- Còn $S$ là quãng đường cả 3 gặp nhau tính từ điểm xuất phát.

dibo.png

Ta có:

$\begin{cases}X_1t_1-X_2t_2=b_1(t_1+t_2) \\ b_1(t_1+t_2)+X_3t_3=X_1t_1+b_2(t_2+t_3)=S\\ t_1+t_2+t_3=T\end{cases}$

Từ hệ phương trình trên ta rút ra được
$T=S.\dfrac{X_1X_2+X_2X_3+X_1X_3-b_1b_2-(b_1+b_2)X_2}{X_1X_3(b_1+b_2+X_2)-b_1b_2(X_1+X_2+X_3)}$

Như vậy, tổng thời gian $T$ sẽ không phụ thuộc vào việc ta chia đoạn $S$ ra làm mấy phần mà chỉ phụ thuộc vào việc ta chọn bộ $(b_1,b_2,X_1,X_2,X_3)$ như thế nào mà thôi.

Việc tìm $\min T$ là một dạng tìm cực trị rời rạc (hữu hạn). Ta có thể liệt kê ra đầy đủ các bộ $(b_1,b_2,X_1,X_2,X_3)$ dựa vào giả thiết đã cho.

$\begin{align} \quad(3,4,12,20,16)\quad &\quad(3,5,12,12,12)\quad &\quad(4,5,16,16,12)\quad \\ \quad(3,4,12,20,20)\quad & \quad(3,5,12,12,16)\quad &\quad(4,5,16,16,16)\quad \\ \quad(3,4,20,20,16)\quad &\quad(3,5,20,12,12)\quad &\quad(4,5,20,16,12)\quad \\ \quad(3,4,20,20,20)\quad &\quad(3,5,20,12,16)\quad &\quad(4,5,20,16,16)\quad\\ \quad(4,3,16,20,12)\quad &\quad(5,3,12,12,12)\quad & \quad(5,4,12,16,16)\quad \\ \quad(4,3,16,20,20)\quad & \quad(5,3,12,12,20)\quad &\quad(5,4,12,16,20)\quad \\ \quad(4,3,20,20,12)\quad & \quad(5,3,16,12,12)\quad &\quad(5,4,16,16,16)\quad \\ \quad(4,3,20,20,20)\quad &\quad(5,3,16,12,20)\quad &\quad(5,4,16,16,20)\quad\end{align}$
_______________________________
Tham Lang : Bài toán này có liên quan đến một dạng của vật lí lớp 10. Tuy nhiên, nó lại có khá nhiều thông số bắt ta phải tính toán. Ý tưởng của em cũng khá giống của thầy :P

#3
hxthanh

hxthanh

    Tín đồ $\sum$

  • Hiệp sỹ
  • 3921 Bài viết
Như vậy sau khi thử toàn bộ 24 bộ số trên thì ta có kết luận
$\mathop \min\limits_{(b_1,b_2,X_1,X_2,X_3)} T=\dfrac{131}{105} \text{ giờ}$ xấp xỉ khoảng $\text{$1$ giờ $15$ phút}$

Xảy ra tại $(b_1,b_2,X_1,X_2,X_3) \in \{(3,4,20,20,20);\;(4,3,20,20,20)\}$

Nghĩa là: Ban đầu Cường (hoặc Bình) đi bộ còn Ân chở Bình (hoặc Cường) bằng xe đạp tới một địa điểm M nào đó, sau đó để Bình (hoặc Cường) tiếp tục đi bộ. Ân đạp xe quay lại đón Cường (hoặc đón Bình) rồi Ân tiếp tục chở Cường (hoặc Bình) đuổi theo Bình (hoặc Cường) để cả 3 cùng về đích!

Như vậy bữa cơm của 3 người bạn diễn ra sớm nhất là vào khoảng $6^h 15\;pm$

Kết quả cũng tương đối dễ hiểu vì vận tốc xe đạp lớn hơn nhiều so với vận tốc đi bộ, và sự chênh lệch giữa các vận tốc xe cũng tương đối lớn. Bài toán này trở nên khó và hay hơn nữa nếu ta cho các vận tốc đạp xe xấp xỉ bằng nhau! (Chẳng hạn như 18, 19, 20 km/h)





Được gắn nhãn với một hoặc nhiều trong số những từ khóa sau: Vận trù, tối ưu

1 người đang xem chủ đề

0 thành viên, 1 khách, 0 thành viên ẩn danh