Đến nội dung

Hình ảnh

statistical integer programming


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

#1
L_Euler

L_Euler

    Leonhard Euler

  • Hiệp sỹ
  • 944 Bài viết

mình đang gặp một vấn đề này chưa biết giải quyết thế nào, nhờ anh em xem giúp:

 

cho trước một vector $f \in \left[0, 1 \right]^N$ với $N$ rất lớn. người ta cần phân hoạch tập hữu hạn $S = \left \{1, 2, 3,...,N \right \}$ thành một số tập con không rỗng $S_i$ chứa các số nguyên liên tiếp và đôi một không giao nhau sao cho i) số lượng các tập con được phân hoạch là ít nhất có thể, và ii) đại lượng  $\sum_i\sigma_i^2$ đạt giá trị cực tiểu, trong đó $\sigma_i^2$ là phương sai của các giá trị của vector $f$ trong tập $S_i$. các giả thiết đặt ra có thể quy về bài toán tối ưu sau đây:

$$    \left [\widehat{n}, \widehat{\sigma}_1,..., \widehat{\sigma}_{\widehat{n}} \right] = argmin_{n, \sigma_1,..., \sigma_{n}} \left(n + \lambda \sum_{i=1}^{n} \sigma_i^2 \right),$$

trong đó $\lambda > 0$ là một giá trị trade off giữa hai đại lượng trong hàm mục tiêu.

 

merci d'avance!

L_Euler



#2
perfectstrong

perfectstrong

    $LOVE(x)|_{x =\alpha}^\Omega=+\infty$

  • Quản lý Toán Ứng dụng
  • 4964 Bài viết

Mình chưa hiểu rõ vấn đề lắm. Mình diễn giải lại như sau có đúng ý bạn không?

Đại để là $f$ biểu diễn việc chọn hay không chọn một số $x$ trong tập $S$: với mọi $x \in S$, $f(x)=1$ nếu $x$ nằm trong vecteur $f$, còn không $f(x)=0$. Sau đó, trong mỗi phân hoạch $S_i$, gọi $f_i = \{ x \in S_i \, | \, f(x) = 1 \}$, và tính $\sigma_i^2$ là phương sai của $f_i$.

Bây giờ phải tìm số phân hoạch $n$ nhỏ nhất để $n + \lambda \sum \sigma_i ^2$ đạt GTNN?


Bài viết đã được chỉnh sửa nội dung bởi perfectstrong: 26-09-2023 - 02:56

  • PRP yêu thích
Luôn yêu để sống, luôn sống để học toán, luôn học toán để yêu!!! :D
$$\text{LOVE}\left( x \right)|_{x = \alpha}^\Omega = + \infty $$
I'm still there everywhere.

#3
L_Euler

L_Euler

    Leonhard Euler

  • Hiệp sỹ
  • 944 Bài viết

không, vector $f$ chứa các số trong đoạn $[0, 1]$ chứ không phải tập $\left \{0, 1 \right \}$.;-)

 

mình vừa mới chứng minh được trong trường hợp $\lambda <1$ thì bài toán không có nghiệm nhưng trong trường hợp còn lại $\lambda \ge 1$ thì bài toán phức tạp hơn hẳn. 






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

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