Hilbert temeli (doğrusal programlama) - Hilbert basis (linear programming)

Hilbert temeli bir dışbükey koni C minimum bir tam sayı kümesidir vektörler öyle ki her tam sayı vektörü C bir konik kombinasyon Tamsayı katsayılı vektörlerin Hilbert bazında.

Tanım

Hilbert temel görselleştirme

Verilen bir kafes ${displaystyle Lsubset mathbb {Z} ^ {d}}$ ve jeneratörleri olan bir dışbükey çok yüzlü koni ${displaystyle a_ {1}, ldots, a_ {n}, matematikte {Z} ^ {d}}$

${displaystyle C = {lambda _ {1} a_ {1} + ldots + lambda _ {n} a_ {n} mid lambda _ {1}, ldots, lambda _ {n} geq 0, lambda _ {1}, ldots , lambda _ {n} in mathbb {R}} altkümesi mathbb {R} ^ {d}}$

biz düşünüyoruz monoid ${displaystyle Ccap L}$. Tarafından Gordan'ın lemması bu monoid sonlu olarak üretilir, yani sonlu bir kafes noktaları kümesi vardır ${displaystyle {x_ {1}, ldots, x_ {m}} alt küme Ccap L}$ öyle ki her kafes noktası ${displaystyle xin Ccap L}$ şu noktaların tamsayı konik birleşimidir:

${displaystyle x = lambda _ {1} x_ {1} + ldots + lambda _ {m} x_ {m}, quad lambda _ {1}, ldots, lambda _ {m}, mathbb {Z}, lambda _ {1 }, ldots, lambda _ {m} geq 0}$

Koni C sivri denir, eğer ${displaystyle x, -xin C}$ ima eder ${displaystyle x = 0}$. Bu durumda, monoidin benzersiz bir minimal üretici kümesi vardır. ${displaystyle Ccap L}$ - Hilbert temeli nın-nin C. İndirgenemez kafes noktaları kümesi ile verilir: Bir eleman ${displaystyle xin Ccap L}$ sıfır olmayan iki öğenin toplamı olarak yazılamıyorsa indirgenemez olarak adlandırılır, yani ${displaystyle x = y + z}$ ima eder ${displaystyle y = 0}$ veya ${displaystyle z = 0}$.

Referanslar

• Bruns, Winfried; Gubeladze, Joseph; Henk, Martin; Martin, Alexander; Weismantel, Robert (1999), "Carathéodory teoreminin bir tam sayı analoğuna karşı bir örnek", Journal für die reine und angewandte Mathematik, 1999 (510): 179–185, doi:10.1515 / crll.1999.045
• Cook, William John; Fonlupt, Jean; Schrijver, İskender (1986), "Carathéodory teoreminin tam sayı analoğu", Kombinatoryal Teori Dergisi, B Serisi, 40 (1): 63–70, doi:10.1016 / 0095-8956 (86) 90064-X
• Eisenbrand, Friedrich; Shmonin, Gennady (2006), "Tamsayı konileri için Carathéodory sınırları", Yöneylem Araştırma Mektupları, 34 (5): 564–568, doi:10.1016 / j.orl.2005.09.008
• D. V. Pasechnik (2001). "Hilbert temellerini Elliott-MacMahon algoritması ile hesaplamak üzerine". Teorik Bilgisayar Bilimleri. 263 (1–2): 37–46. doi:10.1016 / S0304-3975 (00) 00229-2.

Bu Uygulamalı matematik ile ilgili makale bir Taslak. Wikipedia'ya şu şekilde yardım edebilirsiniz: genişletmek.