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

**fool** · #1 (**permalink**) 07-07-2009

Đ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?