perfectstrong

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   16 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 }}\]

Bạn sở hữu một chiếc máy gia công tại một cửa hàng. Buổi sáng bạn mở cửa đón khách. Bạn không biết khi nào khách tới, nhưng khi khách hàng $i$ đến vào thời điểm $r_i$, bạn có thể biết được rằng cần phải dùng $p_i$ thời gian để hoàn thành công việc. Lúc bấy giờ, bạn phải đưa ra quyết định: thực hiện một công việc ($i$ hoặc một công việc nào đó chưa làm), hoặc chờ (bao lâu tùy ý bạn). Phải nhớ rằng một khi đã bắt đầu, bạn không thể dừng máy lại để chuyển cho người khác.

Là một người nhanh nhạy, bạn biết ngay việc thiếu thông tin sẽ khiến bạn không thể đưa ra quyết định tối ưu. Tuy nhiên, bạn vẫn muốn tìm một chiến thuật để đảm bảo rằng, dù trong tình huống tệ nhất, bạn cũng không quá xa với kế hoạch tối ưu nếu biết trước mọi thông tin.

Vậy bạn phải làm thế nào? Và trong tình huống xấu nhất, lịch trình của bạn sẽ tệ thế nào?

Cho trước một đồ thị $G$ có $n$ đỉnh. Trên đỉnh thứ $i$ ta viết số $i$. Bây giờ ta nối các cạnh sao cho không tồn tại tam giác nào có 3 đỉnh $i,j,k$ thỏa mãn $i+j+k \vdots n$.

Hỏi $G$ có tối đa bao nhiêu cạnh?