哈奇揚算法(Khachian algorithm)亦稱橢球算法.一種求解線性規劃問題的多項式算法(參見“多項式算法”).也即解“嚴格”整係數線性不等式組（Q;與b都是整數）的一種算法.求解線性規劃問題的最優解，可以歸結為解上述線性不等式組。
基本介紹
- 中文名：哈奇揚算法
- 外文名：Khachian algorithm
- 別名：橢球算法
概念,提出者,
概念
哈奇揚算法是一種疊代法，每疊代一次就以某一點x`為中心，並依照一定規則構造一個橢球E(參見“n維橢球”).第一個橢球E，就是圓x日＜2'，它的中心x'是原點.疊代過程就是從x' ,Q,得到x2,Q2，再到x Q3i,..，最多疊代6n2I次.這裡，Q，一22勺，I.是輸人長度，n是未知數的個數，A二是由A,x' br確定的，＜Q;A萬是一個列向量.通過一系列橢球的疊代得到最優解.
提出者
這一算法是蘇聯數學家哈奇揚( au，二，i , J 1. 1'.)於1979年提出的，1981年作了完整的證明.這一算法的重要性在於，他第一個證明了線性規劃問題是存在多項式算法的.1982年8月在第11屆國際數學規劃討論會上，哈奇揚的論文《線性規劃的一個多項式算法》獲得了富爾克森獎.
哈奇揚算法
哈奇揚算法
