|
|
между a и b есть целое. Неравенство (5) принято называть сечением, т.к по смыслу оно позволяет отсечь нецелочисленные решения.
Если же в оптимальном плане задачи (1-4) несколько переменных принимают дробные значения, то дополнительное неравенство (5) определяется наибольшей дробной частью. Если случится так, что в оптимальном плане задачи (1-4),(5) переменные снова принимают дробные значения, то вновь добавляют одно дополнительное неравенство и процесс продолжений повторяют. Проведя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования, либо устанавливают неразрешимость.
Если требование целочисленности касается лишь определенно некоторых переменных, то такие задачи называют частично целочисленными. В этом случае решение также находят последовательным решением задач, каждая из которых получается из предыдущей с помощью введения дополнительного ограничения. Дополнительное ограничение имеет вид:
Z,, > f (b•) (6),
]
где у. определяются из следующих соотношений:
1) для x}, которые могут принимать нецелочисленные значения:
* * г\
a., при a.. > 0
у j =
f b) * * (7)
- при a* < 0
1 - f (b*)
* a*
2) для x}, которые могут принимать только целочисленные значения,
Уi, =
f (aj) пРи f (aj) ? f (Ь.)
fb) [l - f (a*.)] при f (a*,) > f (b* ). (8)
Подчеркнем, что алгоритм Гомори не является единственным способом решения целочисленных задач. Можно указать также метод ветвей и границ. Однако метод Гомори обладает некоторой алгоритмической общностью. Остановимся на алгебраических способах анализа и нахождения целочисленного решения.
Продемонстрируем применение метода Гомори в решении следующей задачи оптимизации состава смеси.
Из двух продуктов I,II составляется смесь. В состав смеси должно входить не более 35 ед. химического вещества А, не более 900 ед.
279
|
