Работа По теме: «Целочисленное программирование» — страница 7

  • Просмотров 2196
  • Скачиваний 17
  • Размер файла 150
    Кб

линейного программирования всегда распола­гаются на границе области решений. В данном случае граничные точки не являются даже допустимыми решениями, поскольку ни одна из них не целочисленна. Предположим, что область допу­стимых решений сужена до выпуклой оболочки допустимых целых точек внутри допустимой области. На рис. 13.1 эта выпук­лая оболочка показана затененной областью OEFGH. Эту зате­ненную область можно

рассматривать как область допустимых решений некоторой другой задачи линейного программирования. Действительно, если к задаче линейного программирования, опре­деляющей допустимую область OABCD, добавить ограничение типа RR', как показано на рис. 13.1, то вновь полученная задача будет иметь OEFGH в качестве области допустимых решений. Такая вновь полученная область обладает двумя важными свой­ствами: во-первых, она содержит все

допустимые целочисленные точки исходной задачи линейного программирования (поскольку она является выпуклой оболочкой этих точек), во-вторых, все крайние точки новой области — целочисленны. Поэтому любое базисное оптимальное решение модифицированной задачи линей­ного программирования имеет своими компонентами целые числа и является оптимальным ре­шением исходной задачи цело­численного программирования. Именно

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

решение автоматически будет целочисленным. Представ­ленный ниже целочисленный алгоритм обладает следующими свойствами: 1) все дополнительные ограничения сохраняют допустимые точки исходной целочисленной задачи; 2) за конеч­ное число шагов создается достаточное количество дополнитель­ных ограничений для того, чтобы оптимальное решение моди­фицированной задачи было целочисленным; 3) дополнительные ограничения

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