Polyhedra, Face and Facets

**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:

[Only registered and activated users can see links. ]
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?

**thichhoctoan** · #2 (**permalink**) 07-07-2009

Bạn fool có bao giờ nghiên cứu vấn đề số điểm nguyên nằm trong một đa diện không ? Vấn đề này là một chủ đề khá thú vị liên quan đến nhiều mảng trong hình học đại số và lý thuyết biểu diễn. Thân mến,
THT

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

Dạ không ạ, em học về Tin nên kiến thức Toán yếu và thiếu. Và em không hỏi được thầy em và cũng chưa có course nào để em theo (phải sang mùa xuân năm sau) về những cái này nên post lên đây nhờ mọi người giải đáp cũng như để thảo luận.

Mấy cái này là do em làm về Operation Research (dịch ra tiếng Việt là "Vận trù học"?), em đang đọc về phần (Mixed) Integer Programing, nó có sử dụng các khái niệm về facet, face, polyhedron.

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: [Only registered and activated users can see links. ] 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.

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

1, google khá nhiều nhưng không ra cái polyhedra này.

2. Lúc đó tôi liên tưởng các đa giác lõm trong 2 chiều, và nghĩ là mọi cạnh đa giác đều biểu diễn qua đường thẳng được.

3. Hiện tại đúng là tôi đang có vấn đề về các định nghĩa, thuật ngữ do thiếu tài liệu nên ảnh hưởng khá nhiều đến việc chắp nối suy luận. Cái câu hỏi này cũng đã tìm thấy đáp án trong cái slide mà vừa tìm được. Mong bác thông cảm.