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

Некоторые задачи линейного программирования требуют целочисленного решения. К ним относятся задачи по произ­водству и распределению неделимой продукции (выпуск стан­ков, телевизоров, автомобилей и т.д.). В общем виде математи­ческая модель задачи целочисленного программирования име­ет вид

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

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

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

Пусть получено оптимальное решение _опт = (f ₁, f ₂,..., f_r, 0,..., 0), которое не является целочисленным, тогда по­следний шаг симплексной таблицы имеет следующий вид:

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

Пусть f_i и хотя бы одно h_ij (j = , r = ) — дроб­ные числа.

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

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

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

Дата добавления: 2014-10-15