Nhờ các bác nào thành thạo về linear programming hay linear algebra giúp một chút :
a. Polyhedron P có dạng như sau , giả sử bdt là đúng (valid inequality) cho P, nghĩa là với mọi x thuộc P thì ax <= b. facet là giao của 1 mặt phẳng ax = b với P. Nếu P có số chiều là d thì 1 facet của nó có số chiều là d-1 (vì dấu bằng xảy ra nên 1 biến được xác định qua d-1 biến còn lại).
Họ nói rằng với một số điều kiện X, Y, Z thì ax<=b là 1 "facet defining inequality", và theo tôi hiểu (dựa vào các định nghĩa trên) thì là với các điều kiện này, dấu bằng sẽ xảy ra với một số điểm thuộc P. Cách hiểu này của tôi có đúng không?
Lấy ví dụ như này: với tam giác thì nó có 3 facet là 3 cái đường thằng chứa 3 cạnh, và còn có các facet khác nữa mà chỉ cắt tam giác tại 1 trong 3 đỉnh của nó. Và tất cả các đường thằng như vậy đều là facet defining inequality.
b. Giả sử X là tập hợp một số điểm nguyên (hoặc nguyên + không nguyên), vậy convex hull của nó định nghĩa như nào, có giống convex hull thông thường không?
Nhờ các bạn giúp. Đang đọc về valid inequality/cutting plane algorithm của Linear programming (optimisation) và có mấy cái định nghĩa cơ bản nhưng chưa rõ lắm.
thay đổi nội dung bởi: fool, 07-06-2009 lúc 01:42 AM
Tớ chả biết thế nào, đọc chả hiểu câu hỏi.
1-dấu bằng xảy ra tại các điểm biên của P. P sẽ được cắt ra bởi các siêu mặt, cứ tưởng tượng như cắt cheese ấy., thế thì hiển nhiên cục cheese sẽ được xác định bới các mặt của nó. Mỗi mặt được định nghĩa bởi Ax=b, và do đó, cheese sẽ thuộc về Ax>b hoặc là Ax<b
2-Chính xác. Giống hệt.
Nghĩa là họ thường nêu định nghĩa về facet, valid inequality, nhưng không nêu định nghĩa về facet defining inequality nhưng lại nói BDT X là 1 facet defining inequality nên là mình muốn làm rõ nó dựa vào mấy cái định nghĩa đã biết.
Có lẽ đến bây giờ thì chính xác (giải thích dựa vào những thứ đã thu lượm được):
Facet defining inequality là 1 valid inequality cx <= d của Polyhedron P (P được xác định thông qua bdt Ax <= b) mà tồn tại x0 thuộc P mà cx0=d.
Ví dụ cheese của WB rất dễ hiểu. Mỗi mặt của cheese là 1 facet defining inequality.
Cái điều kiện đó có liên quan đến chuyện sinh affin. Sinh affine khác với sinh tuyến tính.
v1 được sinh affin bởi v2,...,vn nếu tốn tại a_1 khác 0, a_2,...an và a1= a2+...+an sao cho
a1v1 = a2v2 + ... + anvn.
Sinh affin hiểu theo nghĩa hình học là : qua 2 điểm có 1 đt, qua 3 điểm có 1 mặt phẳng, qua 4 điểm có 1 không gian 3 chiều....
ví dụ : v1 nằm trong không gian affin sinh bởi v2,v3 , v4 nếu như v1 nằm trên mặt phẳng tạo bởi 3 điểm v2,v3,v4.
Để hiểu khái niệm thì bác thử cm : Nếu a1v1 + a2v2 +... + anvn = 0 và a1+a2...+an=0, và nếu a_i khác 0 thì v_i nằm trong bao affine của các điểm còn lại.
- Một valid inequality cho một polyhedron P là một bất đẳng thức tuyến tính dạng cx<=d được thỏa mãn bởi mọi điểm của P, nói cách khác là P nằm hoàn toàn trong nửa không gian định nghĩa bởi bất đẳng thức trên.
- Định nghĩa facet hay face có lẽ bị dùng lẫn với nhau bởi các sách khác nhau. Định nghĩa mà tôi biết (tham khảo Combinatorial Optimization của W.Cook et al.) là
- Một face của P là giao của P với siêu mặt cx=d, với cx<=d là một valid inequality, nếu giao này khác rỗng.
- Facet là một face với số chiều affine = số chiều affine của P - 1.
Ở đây lại đá qua khái niệm số chiều affine.
- Số chiều affine của một tập các điểm là số lớn nhất các điểm độc lập affine trong tập đó - 1
Như vậy trong ví dụ tam giác của bạn, có 7 faces bao gồm : 3 đỉnh, 3 cạnh và bản thân tam giác. Còn facets thì chỉ là 3 cạnh.
Còn về facet defining inequality thì cần nói rõ thêm thế này :
Tuy cái polyhedron P của bạn có thể được định nghĩa bằng nhiều hệ bất đẳng thức khác nhau, thực tế có nhiều hệ là chứa những bất đẳng thức thừa (tức là những BĐT có thể được suy ra từ những BĐT khác hoặc hiển nhiên đúng kiểu 0x <=1). Song hệ cực tiểu định nghĩa polyhedron đó thì là duy nhất (sai khác một hệ số nhân dương), và mỗi BĐT trong hệ cực tiểu này thực ra định nghĩa một facet. Tức là cho dù P có được định nghĩa bởi hệ phức tạp kiểu gì đi nữa thì trong đó chỉ có vài BĐT là quan trọng, chung cho tất cả các hệ, và các facet cũng đều từ đó mà ra cả.
Tập vecto v1,v2,..,vn là affine independence nếu a1v1+a2v2+...+anvn = 0 và a1+a2+..+an=0 thì a1=a2=..=an=0.
Ý nghĩa của cái a1+a2+...+an = 0 là nhằm mục đích gì vậy, các bác? Về mặt hình học thì hiểu thế nào (ví dụ trong 2 chiều).
Định nghĩa : Vecto v được sinh ra affine từ tập vecto v1,v2,..,vn nếu v= a1v1+..+anvn và a1+a2+...+an=1(*), nghĩa là v phụ thuộc affine vào các vecto v1,v2,...,vn.
Nếu ở bên trên (phần câu hỏi), nếu tồn tại ai<>0, giả sử là a1<>0 thì ta có v1=(-a2/a1)v2 +(-a3/a1)v3+...+(-an/a1)vn và (-a2/a1)+...+(-an/a1) = 1 và theo định nghĩa thì v là "phụ thuộc" affine vào các vecto v2,v3,...,vn.
Còn nếu tất cả các ai bắt buộc đồng thời bằng 0 thì không 1 vecto nào có thể biểu diễn affine qua các vecto còn lại và do đó nó được gọi là "độc lập affine".
Cái này là cm để hiểu rõ hơn cái :
Trích:
Nếu a1v1 + a2v2 +... + anvn = 0 và a1+a2...+an=0, và nếu a_i khác 0 thì v_i nằm trong bao affine của các điểm còn lại.
Nghĩa là phải đi từ khái niệm affine và sau đó đi đến độc lập affine.
Đối với 2 chiều thì đl affine ứng với việc 3 điểm không thẳng hàng, 3 chiều thì là 4 điểm không thuộc cùng 1 mặt phẳng...
Định nghĩa : Vecto v được sinh ra affine từ tập vecto v1,v2,..,vn nếu v= a1v1+..+anvn và a1+a2+...+an=1(*), nghĩa là v phụ thuộc affine vào các vecto v1,v2,...,vn.
vậy affine của một tập vector chứa convex set của tập vector đó. (ví dụ 2 điểm thì convex set là đoạn thẳng, còn affine space là đường thẳng)?
Dante nói rằng:
Trích:
Sinh affin hiểu theo nghĩa hình học là : qua 2 điểm có 1 đt, qua 3 điểm có 1 mặt phẳng, qua 4 điểm có 1 không gian 3 chiều....
ví dụ : v1 nằm trong không gian affin sinh bởi v2,v3 , v4 nếu như v1 nằm trên mặt phẳng tạo bởi 3 điểm v2,v3,v4.
Vậy với n điểm đồng phẳng (ex trong 3 chiều) thì affine space mà nó sinh ra = affine của 3 điểm bất kỳ trong đó.
Họ có cái định lý như này:
Nếu thì số solutions độc lập affine tối đa của là
Cái này tôi đọc ở đây: [Only registered and activated users can see links. ] - Lectures 11, Mục some properties of Subspaces.
Bác nào biết quyển sách nào nó có giới thiệu và chứng minh cái này và các thứ cơ bản liên quan đến affine thì send giúp tôi cái link nhé.
Trích:
- Một face của P là giao của P với siêu mặt cx=d, với cx<=d là một valid inequality, nếu giao này khác rỗng.
- Facet là một face với số chiều affine = số chiều affine của P - 1.
Và dựa vào cái định lý trên, thì chắc biết được cần liệt kê bao nhiêu điểm x0 để mà cx0=d và các điểm này độc lập affine với nhau để mà chúng tạo thành facet của P.
a. Các vecto độc lập tuyến tính thì độc lập affine còn ngược lại không đúng.
VD: 3 điểm không thẳng hàng ứng với 3 vecto trong mặt phẳng là đl affine nhưng không đl tuyến tính.
b. Nếu các vecto v1,v2,...,vk là độc lập affine thì v2-v1,...,vk-v1 là độc lập tuyến tính và ngược lại.
(=>) : gs a2(v2-v1)+...+ak(vk-v1)=0 thì => a1v1+...+akvk=0 với a1=-(a2+...+ak) hay a1+..+ak =0 , áp dụng đn đl affine => a1=a2=..=ak=0 hay a2=..=ak=0 => v2-v1,...,vk-v1 đltt.
(<=) : gs a1v1+..+akvk=0 và a1+..+ak=0 => a2(v2-v1)+..+ak(vk-v1)=0. Do v2-v1,...,vk-v1 đltt => a2=..=ak=0 => a1=0 => v1,v2,...,vk đl affine.
c. Nếu v1,v2,..,vk là đl affine thì (v1,1),(v2,1),...,(vk,1) là đltt và ngược lại.
(=>) : a1(v1,1)+...+ak(ak,1) = 0 <=> a1(v1,0)+...+ak(vk,0) + (a1+...+ak)e(n+1)=0 => a1v1+..+akvk=0 và a1+...+ak=0. Do đl affine => a1=...=ak=0 => (v1,1),...,(vk,1) đltt.
(<=) : a1v1+...+akvk=0 và a1+..+ak=0 => a1(v1,1)+...+ak(vk,1)=0. Do đltt => a1=...=ak=0 => đl affine.
d. Tập được gọi là nullspace của A, kí hiệu null(A) và có số chiều là n-rank(A).
CM : giả sử rank(A)=m. Thu gọn A để chỉ còn m hàng và tách A thành A=(A_m,A_(n_m)) với A_m là ma trận vuông khả nghịch.
Ax=0 <=> A_m*x(1..m)+A_(n-m) * x(m+1..n) = 0.
Lấy x_j giá trị thuộc R tùy ý với j = m+1..n. Ta có : A_m*x(1..m) = b.
với b = - A_(n-m) * x(m+1..n). Hệ này có duy nhất nghiệm.
Vậy nullspace này có số chiều là n-rank(A). (CM này có official lắm không các bác, vì thấy phép thu gọn + chọn x(m+1..n) thuộc R^(n-m) nó giống CS quá?).
e. Nếu thì số solutions độc lập affine cực đại của Ax=b là n+1-rank(A).
Các câu hỏi cơ bản về toán 
