Câu hỏi

Tại một trạm bán xăng, có n người xếp hàng mua xăng. Mỗi người cần mua một số lượng xăngkhác nhau. Hãy chọn cách sắp xếp thứ tự người mua để tổng số thời gian chờđợi của mọi người là nhỏ nhất.

Tại một trạm bán xăng, có n người xếp hàng mua xăng. Mỗi người cần mua một số lượng xăng khác nhau. Hãy chọn cách sắp xếp thứ tự người mua để tổng số thời gian chờ đợi của mọi người là nhỏ nhất.

R. Roboctvx57

Giáo viên

Xác nhận câu trả lời

Giải thích

Gọi thời gian của người thứ i cần để mua xăng là t i ( i = 1 , n ) . Khi đó tổngsố thời gian chờđợi của mọi người là: T = nt 1 + ( n − 1 ) t 2 + ... + 2 t n − 1 + t n Nếu thay đổi thứ tự của mọi người thì tổng thời gian chờđợi là T ′ = nt 1 ′ + ( n − 1 ) t 2 ′ + ... + 2 t n − 1 ′ + t n ′ trong đó ( t 1 ′ , t 2 ′ , ... , t n ′ ) là một hoán vị của (t 1 , t 2 ,...,t n ) Không mất tính tổng quát giả sử t 1 < t 2 <...< t n . Khi đó theo bất đẳng thức hoán vị tổng số thời gian chwof đượi của mọi người nhỏ nhất là T ∗ = nt 1 + ( n − 1 ) t 2 + ... + 2 t n − 1 + t n

Gọi thời gian của người thứ i cần để mua xăng là $t_{i} (i = \overline{1, n})$ . Khi đó tổng số thời gian chờ đợi của mọi người là: $T = nt_{1} + (n - 1) t_{2} + ... + 2 t_{n - 1} + t_{n}$

Nếu thay đổi thứ tự của mọi người thì tổng thời gian chờ đợi là

$T^{'} = nt_{1}^{'} + (n - 1) t_{2}^{'} + ... + 2 t_{n - 1}^{'} + t_{n}^{'}$ trong đó $(t_{1}^{'}, t_{2}^{'}, ..., t_{n}^{'})$ là một hoán vị của (t₁, t₂,...,t_n )

Không mất tính tổng quát giả sử t₁ < t₂ <...< t_n . Khi đó theo bất đẳng thức hoán vị tổng số thời gian chwof đượi của mọi người nhỏ nhất là $T * = nt_{1} + (n - 1) t_{2} + ... + 2 t_{n - 1} + t_{n}$