整數線性規劃

整數線性規劃

整數規劃是指規劃中的變數(全部或部分)限制為整數,若在線性模型中,變數限制為整數,則稱為整數線性規劃。所流行的求解整數規劃的方法往往只適用於整數線性規劃。

一類要求問題的解中的全部或一部分變數為整數的數學規劃。從約束條件的構成又可細分為線性,二次和非線性的整數規劃。 

目錄

正文


整數線性規劃 (integer linear programming )變數取整數值的線性規劃
它的一般形式為min Z,滿足條件,或,且取整數值。在一般線性規劃的約束條件之上,增加要求變數為整數值之後,使問題發生了深刻的變化,對理論和應用均產生影響,從而,形成了整數線性規劃特有分支。在n維歐氏空間E”中的點x,若其所有坐標均為整數,則稱此點為整點。而E0中所有的整點記為Z",是一個格,稱此格為整格。於是,整數線性規劃就是在整格上的線性規劃.