Тема 4. Дискретное программирование.

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

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

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

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

Дробную часть числа обозначим , она определяется следующим образом .

Пример. ,

Пусть получено оптимальное решение , которое не является целочисленным. Тогда последний шаг симплексной таблицы имеет вид:

1	0	0
0	1	0

0	0	1

0	0	1

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

Пусть и хотя бы одно дробные числа.

Дополнительное ограничение по целочисленности:

Если - дробное число, а все - целые числа, то ЗЛП не имеет целочисленного решения;
Ограничение целочисленности может быть наложено не на все переменные, а лишь на их часть. В этом случае ЗЛП является частично целочисленной.