Циклический алгоритм целочисленного программирования - Целочисленное программирование

Рассмотрим следующую задачу линейного программирования:

Максимизировать

X0=a00-a01x1-a02x2-........-a0nxn, (2)

При условии:

Xn+1=an+1,0-an+1,1x1-an+1,2x2-.......-an+1,nxn,

Xn+m=an+m,0 - an+m,1x1-an+m,2x2-.......-an+m, nxn,

Xj?0 (j=1,......., n+1,......., n+m).

Заметим, что xn+1., хn+m - слабые переменные, a x1...., хn - исходные переменные задачи (2). Если наряду с ограничениями (2) потребовать, чтобы все хj, (j'=1,..., т) были целыми, то задача будет называться задачей целочисленного программирования. Существует большое количество задач, особенно комбинаторных, которые можно сформулировать как задачи целочисленного программирования.

Именно алгоритмы целочисленного программирования, которые будут описаны ниже, реализуют методы систематического введения дополнительных ограничений с целью сведения исходной допустимой области к выпуклой оболочке ее допустимых целочисленных точек.

Как только это будет сделано, можно решать модифицированную задачу линейного программирования любым обычным методом, и полученное базисное оптимальное решение автоматически будет целочисленным.

Похожие статьи




Циклический алгоритм целочисленного программирования - Целочисленное программирование

Предыдущая | Следующая