 |
 |
 |
 |
|
 |
 |
76
Принципиальная сложность, вызываемая наличием условий целочисленности в системе ограничений
оптимизационной задачи, состоит в том, что в значительном количестве случаев невозможно заменить
дискретную задачу ее непрерывным аналогом и, найдя соответствующее решение, округлить его ком-
поненты до ближайших целых значений. Пример, показанный на рис. 4.1, демонстрирует, что при
округлении оптимального плана х* обычной задачи ЛП до целых значений получается точка
([х1*],[x2
*
]), не принадлежащая области допустимых планов задачи D. Условимся целую часть числа х
j
.
обозначать [х
j
], а дробную — как {х
j
}. Тогда х
j
=[х
j
]+{х
j
}. Отдельно следует добавить, что если даже
оптимальный план непрерывной задачи, округленный до целых значений компонент, окажется допусти-
мым, то целевая функция может вести себя так, что ее значение будет на нем существенно «хуже», чем
на оптимальном плане целочисленной задачи.
Перечисленные проблемы предопределили необходимость разработки специальных методов
решения дискретных и целочисленных задач. Но прежде чем говорить собственно о методах решения,
более подробно остановимся на классификации задач дискретного программирования. В литературе,
как правило, выделяют следующие классы дискретных оптимизационных задач:
задачи с неделимостями;
экстремальные комбинаторные задачи;
задачи с разрывными целевыми функциями;
задачи на несвязных и невыпуклых областях и др.
4.1.2. Задачи с неделимостями. В подавляющем большинстве случаев наличие условий
неделимости определяется физическими свойствами моделируемых объектов. Так, например, они могут
появиться в качестве дополнительных ограничений в уже рассматривавшейся нами выше задаче
производственного планирования, если в ней осуществляется управление выпуском крупной штучной
продукции.
Классическим представителем задач данного класса стала так называемая задача о ранце. Ее фабула
носит достаточно условный характер и состоит в том, что солдат (или турист), собирающийся в поход,
может нести груз весом не более W кг. Этот груз может состоять из набора предметов n типов, каждый
предмет типа j весит w
j
кг и характеризуется некоторой «полезностью» u
j
, j ? 1: n. В рамках описанной
ситуации вполне естественным представляется вопрос: сколько предметов каждого вида нужно
положить в ранец, чтобы его суммарная полезность была максимальной? Если в качестве компонент
плана х
j
. принять количество укладываемых предметов типа j, то данную задачу можно записать:
Как нетрудно заметить, представленная математическая модель носит универсальный характер, и к
ней могут быть сведены многие экономические задачи. Ярким подтверждением этому служит и тот