perfectstrong

Thầy @thvn nói về các bài toán "căn bản" trong hình học THCS làm mình nhớ ngày xưa có vài bài thú vị cho lớp 6,7

1) Cho tam giác $ABC$ nhọn. Trên $BC$ lấy $D, E$ sao cho $\angle BAD = \angle DAE = \angle EAC$. Trong 3 đoạn thẳng $BD,DE,EC$, đoạn nào dài nhất?

Và bài toán "đảo":

2) Cho tam giác $ABC$ nhọn. Trên $BC$ lấy $D,E$ sao cho $BD=DE=EC$. Trong 3 góc $\angle BAD, \angle DAE, \angle EAC$, góc nào nhỏ nhất?

Một tài liệu cũ năm xưa chung tay viết với người em @BlackSelena

Có vẻ tài liệu này chưa được đăng lên diễn đàn bao giờ, nên mình mạo muội gửi lên đây, cốt để chia sẻ

 TSK HDDH_2.pdf   609.92K   108 Số lần tải

Ta xem xét một trường hợp đặc biệt của bài toán được nêu ở trang này https://diendantoanh...ng-k-out-of-nf/

Cho $n=3$ hàm $f_i:\left[ {0;1} \right] \to \left[ {0;1} \right]$ là hàm giảm trên $]0;1[$, có đạo hàm bậc 2, và ${f_i}\left( 0 \right) = 1;{f_i}\left( 1 \right) = 0$.

Cho trước các số $A_1,A_2,A_3, B$ dương và $A_i \le 1$.

Tìm $x_1,x_2,x_3 \in [0;1]$ sao cho $x_i \le A_i; x_1 + x_2 + x_3 \le B$ và hàm sau đạt GTLN:

\[F = {f_1}\left( {{A_1} - {x_1}} \right){f_2}\left( {{A_2} - {x_2}} \right){f_3}\left( {{A_3} - {x_3}} \right)\]

Một hệ thống có $n$ máy, đánh số $i = 1, \ldots, n$. Ta đặt $F_i(t) : \mathbb{R}^{\ge 0} \rightarrow [0;1] $ là hàm biểu diễn xác suất máy $i$ bị hư (failure) tại thời điểm $t \ge 0$. Theo thông lệ, ta xét $F_i$ liên tục và tăng. Nói nôm na: máy càng sử dụng lâu thì càng có nguy cơ bị hư hỏng.

Hệ thống được gọi là $k-out-of-n:F$ nếu hệ thống chỉ bị coi là hư khi có ít nhất $k$ máy bị hư (tức là có ít nhất $n-k+1$ máy còn hoạt động). Ta sẽ tính toán độ tin cậy (reliability) $R(t)$, tức là xác suất chưa bị hư, của hệ thống tại thời điểm $t$.

$$\begin{equation}\label{eq_rel_fun} R\left( t \right) = \sum\limits_{l < k} {\sum\limits_{\sigma  \in {S}\left( n,l \right)} {\prod\limits_{1 \le j \le n \\j \in \sigma}^{} {{F_j}\left( t \right)} \prod\limits_{1 \le j \le n \\ j\not  \in \sigma}^{} {\left( {1 - {F_j}\left( t \right)} \right)} } }\end{equation} $$

Trong đó, $S(n,l)$ là tập hợp các tập con có đúng $l$ phần tử của tập $\{1,2,\ldots,n\}$.

Một số ví dụ kinh điển là:

* $k=1$ (Hệ thống series (chuỗi)): Hệ thống sẽ hư nếu có máy nào đó hư. Nghĩa là, xác suất hệ thống chưa hư là xác suất chưa máy nào bị hư. Khi đó (1) trở thành:

\[\begin{equation}\label{eq_rel_series} {R_{k = 1}}\left( t \right) = \prod\limits_{1 \le j \le n}^{} {\left( {1 - {F_j}\left( t \right)} \right)}\end{equation} \]

* $k=n$ (Hệ thống parallel (song song)): Hệ thống sẽ hư nếu mọi máy đều hư. Nghĩa là, xác suất hệ thống chưa hư là phần bù của biến cố tất cả máy đều hư. Khi đó (1) trở thành:

\[\begin{equation}\label{eq_rel_parallel} {R_{k = n}}\left( t \right) = 1 - \prod\limits_{1 \le j \le n}^{} {{F_j}\left( t \right)} \end{equation} \]

* $k=2, n=3$: để tiện ghi chép, ta lượt bỏ phần biến số $t$. Khi đó, (1) trở thành:

\[{R_{k = 2,n = 3}} = \left( {1 - {F_1}} \right)\left( {1 - {F_2}} \right)\left( {1 - {F_3}} \right) + {F_1}\left( {1 - {F_2}} \right)\left( {1 - {F_3}} \right) + {F_2}\left( {1 - {F_1}} \right)\left( {1 - {F_3}} \right) + {F_3}\left( {1 - {F_1}} \right)\left( {1 - {F_2}} \right)\]

Câu hỏi mà mình muốn thảo luận là: có cách nào để "đơn giản hóa" (1) không? Hoặc là đánh giá chặn dưới, chặn trên ?

Trong bài toán RCPSP (Resource Constrained Project Scheduling Problem), tài nguyên (resource) là yếu tố tối quan trọng khi lập lịch cho các công việc, vì công việc không tiến hành nếu không có tài nguyên. Ví dụ, không thể khám bệnh cho bệnh nhân nếu không có bác sĩ đang rảnh tay. Có nhiều cách phân loại các vấn đề RCPSP, nhưng một cách phân loại tiêu biểu là theo sự dao động của tài nguyên:

- Loại 1 là hằng số (constant) : Tài nguyên sẽ luôn hiện hữu với độ lớn (availability) là hằng số. Ví dụ, một ê-kíp trực có 5 y tá từ 21h đến 5h sáng hôm sau. Tại mọi thời điểm sẽ luôn có 5 y tá, dù rảnh hay không.

- Loại 2 là biến thiên (time-varying) : Độ lớn tài nguyên thay đổi theo thời gian. Ví dụ, bác sĩ chỉ làm việc vào buổi sáng thứ hai, tư và sáu. Các thời điểm khác, bác sĩ không có mặt.

Ta có thể thấy là sự biến thiên của tài nguyên sẽ ảnh hưởng không ít tới việc lập lịch. Câu hỏi đặt ra là làm sao để đo lường sự biến động này? Để cụ thể hơn, ta lấy một ví dụ như sau.

Trên trục thời gian lập lịch (horizon) $[0;T]$, ta có hàm $R(t)$ biểu diễn độ lớn của tài nguyên tại thời điểm $t$. Dưới đây là minh họa cho 3 trường hợp của $R(t)$.

 res_var_illu_crop.png   55.26K   43 Số lần tải

Tổng lượng tài nguyên $\int_0^T {R\left( t \right)dt}$ trong 3 trường hợp là như nhau, tuy nhiên ta nhận ra về số lượng dao động (số lần lên xuống) thì $R^I > R^{II} > R^{III}$.

Mình có ý tưởng là dựa theo công thức tính độ lệch chuẩn (standard variation):

\[\sqrt {\frac{1}{{N}}\sum\limits_{i = 1}^N {{{\left( {{x_i} - \overline x } \right)}^2}} } \]

Tuy nhiên, công thức này mở rộng thế nào khi có vô hạn $x_i$ ? Hay đúng hơn, nếu ta biết được tập giá trị và tần số của từng giá trị, thì công thức sẽ thay đổi thế nào?

Mình muốn thử như sau nhưng chưa biết đúng hay sai, nên cần mọi người góp ý

Trong vấn đề RCPSP, thông thường, phạm vi lập lịch sẽ được chia thành các đoạn $[a_k, b_k[$ rời nhau sao cho $R(t)=c_k \, \forall t \in [a_k, b_k[$.

Ta đề xuất công thức sau:

\[{\sigma _R} = \sqrt {\frac{1}{T}\sum\limits_k^{} {\left( {{b_k} - {a_k}} \right){{\left( {{c_k} - \bar c} \right)}^2}} } \]

Trong đó, $\overline c$ là độ lớn trung bình của tài nguyên: $\overline c  = \frac{1}{T}\int_0^T {R\left( t \right)dt}$

Và để chuẩn hóa về $[0;1]$, ta tính: \[\widetilde {{\sigma _R}} = \frac{{{\sigma _R}}}{{\overline c }}\]