Целочисленное программирование

Лекция 10

Общая формулировка задачи

В общем виде математическая модель задачи целочисленного программирования имеет вид

при ограничениях:

целое,

Оптимальное решение задачи, найденное симплексным методом, часто не является целочисленным. Его можно округлить до ближайших целых чисел. Однако такое округление может дать решение, не лучшее среди целочисленных решений, или привести к решению, не удовлетворяющему системе ограничений. Поэтому для нахождения целочисленного решения существует специальный алгоритм, который предложен Гомори.

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

x1			…		…		h1,r+1	…	h1,n	f1
x2			…		…		h2.r+1	…	h2,n	f2
…	…	…	…	…	…	…	…	…	…	…
xi			…		…		hi,r+1	…	hi,n	fi
…	…	…	…	…	…	…	…	…	…	…
xr			…		…		hr,r+1	…	hr,r+1	fr

где r – ранг системы ограничений; h_i,r+1 – коэффициенты симплексной таблицы i-й строки, (r+1)-го столбца; f_i – свободный член i-й строки.

Пусть f_i и хотя бы одно h_ij () – дробные числа.

Обозначим через [f_i] и [h_ij] целые части чисел f_i и h_ij.

Определение 1. Целой частью числа f_i называют наибольшее целое число, не превосходящее числа f_i.

Дробную часть чисел f_i и h_ij обозначим { f_i } { h_ij }, она определяется следующим образом:

{ f_i } = f_i - [f_i], { h_ij } = h_ij - [h_ij].

Дата добавления: 2014-01-11