Chào mọi người,
Mình đang nghiên cứu về Linear Program và mình đang có bài toán sau:
(P1): Cho dãy $I_1 \leq I_2 \leq \hdots \leq I_n$. Xét Min $\sum_{i=1}^n{|u-I_i|}$
(P2): Xét Min $\sum_{i=1}^n{v_i}$ thỏa $v_i \geq u - I_i$ và $v_i \geq I_i - u$
(P3): Xét Min $\sum_{i=1}^n{\lamda_iI_i}$ thỏa $0 \leq \lamda_i \leq 2$ và $\sum_{i=1}^n{\lamda_i} = n$
Chứng minh (P1) tương đương (P2)
Chứng minh (P3) là bài toán DUAL của (P2)
Chứng minh bằng cách sử dụng complementary slackness conditions, nếu n lẻ (2m+1) thì cực trị của (P1) đạt tại $u = I_{m+1}$, nếu n chẵn (2m) thì cực trị của (P1) đạt tại bất cứ điểm nào nằm giữ $I_m$ và $I_{m+1}$
Chứng minh cực trị của (P1) bằng phương pháp hình học thì mình biết rất đơn giản bằng cách xét trên 1 trục tọa độ và tính chất của điểm này giữa sẽ suy ra được dễ dàng, còn theo phương pháp này mình thua.
Ngoài ra mình không chứng minh được DUAL của (P2) là (P3).
Bạn nào cao kiến giúp mình với.
Cảm ơn mọi người
Nhờ giải giúp bài toán Linear program này
Bắt đầu bởi vonhatvinh, 11-12-2012 - 05:00
#1
Đã gửi 11-12-2012 - 05:00
1 người đang xem chủ đề
0 thành viên, 1 khách, 0 thành viên ẩn danh