Введем для задачи целочисленного программирования ряд понятий, аналогичных задаче линейного программирования.
Множество векторов 
удовлетворяющих условиям (13.5) – (13.7), называется областью определения задачи целочисленного программирования (13.4) – (13.7).
Вектор X, удовлетворяющий условиям (13.5) – (13.7),называется планом (или допустимым решением) задачи целочисленного программирования (13.4) – (13.7).
Крайняя точка выпуклого многогранника множества D называется опорным планом.
План 
, обращающий в максимум линейную форму (13.4), называется оптимальным планом (или решением) задачи целочисленного программирования (13.4) – (13.7).
Если 
– план (оптимальный план) и 
, то вектор 
называется расширенным (расширенным оптимальным) планом задачи целочисленного программирования (13.4) – (13.7).
Введем следующие обозначения:
D – область определения задачи (13.5) – (13.6);
– область определения задачи (13.5) – (13.7);
(D, F) – задача (13.4) – (13.6);
(, F) задача (13.4) – (13.7);
X (D; F) – оптимальный план задачи (13.4) – (13.6);
X (, F) – оптимальный план задачи (13.4) – (13.7);
(, F) – расширенный оптимальный план задачи (13.4) – (13.7).
Задача целочисленного программирования является разрешимой, если существует оптимальный план 
.
Многогранник D, все опорные планы (вершины) которого целочисленные (т. е. все компоненты каждого из опорных планов целые), называется целочисленным многогранником.
Решить задачу(, F) – значит указать ее оптимальный план или установить, что такого плана не существует (
, если F не ограничена сверху на ). При решении задачи (, F) следует выяснить возможность использования уже известных вычислительных процедур.
Теорема 13.1. В случае целочисленности множества допустимых планов задачи (D, F) справедливы следующие утверждения:
1. Каждому допустимому базису В задачи (D, F) отвечает целочисленный базисный план X(B).
2. Если 
(B) – базисное решение задачи (D, F), то (B) также и оптимальный план задачи (, F).
3. Оптимальный план задачи (D, F) является и решением задачи (, F).
Доказательство. 1. Базисный план X(B) есть вершина целочисленного многогранника выпуклого множества D, и, следовательно, X(B) –целочисленный вектор.
2. Утверждение следует из включения 
.
3. Так как оптимальный план задачи (D, F) базисный, то (B) – решение задачи (D, F) – является также и решением задачи (, F).
Замечание. Если D = , то и = . Однако задача (, F) может иметь решение и в том случае, если задача (D, F) не имеет решения (функция F может быть неограниченной сверху на D, в то время как множество будет состоять из конечного числа точек).
Рассмотрим многогранное множество 
.
Естественно поставить вопрос: каким условиям должны удовлетворять матрица 
и вектор правых частей 
, чтобы многогранное множество D (13.5) – (13.6) было целочисленным?
Матрица А называется унимодулярной, если каждый ее минор равен +1, –1 или 0. Примером унимодулярной матрицы является матрица транспортной задачи в матричной постановке.
Ответ на поставленный вопрос дает следующая теорема.
Теорема 13.2. Если 
-матрица А унимодулярна, вектор 
целочислен и D 
, то многогранное выпуклое множество D целочисленно.
Доказательство. Известно, что 
является экстремальной точкой множества D в том и только в том случае, если система 
столбцов матрицы A, индексы которых отвечают положительным компонентам вектора 
, линейно независимы. Обозначим через k число векторов в множестве 
; через – квадратную подматрицу матрицы А порядка k, составленную из элементов множества 
и таких k строк матрицы А, что det 
; через 
– вектор, включающий k соответствующих компонентов вектора b. Тогда вектор 
, составленный из k положительных компонентов вектора , является решением системы линейных уравнений 
. Так как 
, в силу унимодулярности матрицы A он равен 
. Следовательно, 
– целочисленный вектор (
– целочисленная матрица, 
– целочисленный вектор),а значит, целочислен и вектор 
.
Следствие. Если в канонической задаче целочисленного программирования (13.4) – (13.7) матрица А унимодулярна и вектор b целочислен, то оптимальный план задачи (D, F), полученный любым методом, является решением задачи (, F).
Теорема 13.2 дает достаточные условия целочисленности для некоторых классов многогранных множеств. К сожалению в общем случае эти условия достаточно трудно проверить. Однако, если множество D не целочисленное, то оптимальный план 
задачи (D, F) может не быть целочисленным. Во многих случаях нельзя ограничиться и «приближенным решением» [ 
]: мы не можем гарантировать допустимость вектора [ ].