Vietscholar forum - Xem bài viết đơn

timeforchange · #4 (**permalink**) 07-07-2009

	Trích:	fool
	Đang post thread này trong Operation Research & Optimisation thì các bác lại move đi đâu mất lúc submit, chắc đang sửa chửa? Sửa xong các bác move vào box kia giúp nhé. Một số tài liệu về IP: http://coral.ie.lehigh.edu/~ted/teaching/ie418/ Integer Programming (Wosley). ( quyển này hay) Vừa học, đọc vừa hỏi bài các bác : a. Đôi lúc tôi thấy họ ghi Polyhedra P hoặc Polyhedron P. Họ giải thích đâu đó Polyhedra là số nhiều của Polyhedron. Cái này ý kiến các bác thế nào? Tôi thì thấy Polyhedra như là tính từ ấy. b. Polyhedron P thường được miêu tả như sau: $P=\{x \in R^n : a^{i}x<=b_{i};i=1,..n\}$ và họ nói P là full-dimensional nếu chứa n vecto đltt. Nếu P là full-dimensional thì không tồn tại phương trình ax=b mà thỏa mãn với mọi điểm thuộc P (OK) và nếu P là full-dimensional thì nó có biểu diễn cực tiểu duy nhất với mỗi bdt là duy nhất với mỗi hệ số nhân dương. (OK). Nghĩa là nếu bỏ đi mỗi bdt thuộc biểu diễn minimal của P thì thu được P' khác với P. Ngoài ra với các bdt mà không là bội dương của 1 bdt trong P thì nó sẽ biểu diễn tuyến tính được qua các bdt trong P. Câu hỏi là : Conv của P thì lồi còn Polyhedron P có thể lồi hoặc lõm ? Tôi thấy các hình họ vẽ minh họa P toàn lồi. Và vì lõm cũng có thể biểu diễn qua một loạt các bdt tuyến tính. c. Số chiều của P, kí hiệu dim(P) = số điểm độc lập affine cực đại trong P - 1. và nếu $P\subseteq R^n$ là full-dimensional <=> dim(P) = n. (OK). Câu hỏi: Vậy nếu trong biểu diễn của P có m dấu bằng và vecto hệ số liên quan đến các đẳng thức này là đltt, vậy dim(P) <= n-m? Và nói chung, trong biểu diễn cực tiểu mà có n dấu bằng, dim(P)=n-m?

1. Polyhedra là số nhiều. Tôi chả thấy nó "như là tính từ gì cả". Bạn nên tra từ điển cho những câu hỏi kiểu này.

2. Bạn thử đưa ra một ví dụ về polyheron (giao của các nửa không gian) mà lõm xem nào

.

3. Giả sử P được định nghĩa bởi $Ax \leq b$ . $a_ix \leq b_i$ thuộc hệ này gọi là một implied equation nếu ax=b được thỏa mãn bởi mọi điểm trong P. Nếu A'x = b' là hệ tất cả các implied equations này thì dimP = n - rank A'. Đơn giản là vì P nằm trong không gian affine giao của rankA' siêu mặt. Bạn nên tập dùng định nghĩa chứng minh chặt chẽ. Kĩ thuật chứng minh điều này được dùng khá nhiều trong các chứng minh liên quan đến polyhedron.