Экстремальная задача - комбинаторный тип
Cтраница 1
Многочисленные экстремальные задачи комбинаторного типа могут быть записаны как задачи линейного программирования с матрицами из нулей и единиц и с дополнительными условиями целочисленности. Хотя теорема 13 дает метод для решения некоторых из таких задач, этот метод оказывается для большинства задач недостаточно эффективным. [1]
Под экстремальной задачей комбинаторного типа принято понимать любую задачу, в которой требуется среди конечного числа вариантов выбрать экстремальное значение фиксированной целевой функции. Задачи комбинаторного типа, представляющие практический интерес, обычно имеют столь огромное число возможных вариантов, что решение их путем прямого перебора непосильно даже для ЦВМ обозримого будущего. Многие важные комбинаторные задачи удается свести к ЦЛП. В частности, это относится к общей задаче расписаний теории, точных методов решения к-рой до сих пор не существует. [2]
Под экстремальной задачей комбинаторного типа понимают любую постановку, в которой требуется сделать выбор среди конечного числа вариантов, доставляющих экстремальное значение фиксированной целевой функции. В настоящее время большинство комбинаторных задач сведено к целочисленному программированию. [3]
Поставленная задача относится к классу экстремальных задач комбинаторного типа, и решение ее представляет значительные трудности. [4]
Основным экспериментальным материалом, на котором развивалась и апробировалась теория вычислительной сложности, были и являются экстремальные задачи комбинаторного типа и задачи теории графов. С тех пор основные усилия в теории вычислительной сложности были направлены на поиски алгоритмов полиномиальной сложности для задач экспоненциальной сложности и на доказательство сводимости или несводимости конкретных задач к задачам полиномиальной сложности. [5]
В работах [47, 49] содержатся примеры доминантных условий всех четырех типов для областей анализа интеллектуальных способностей человека, математического программирования и экстремальных задач комбинаторного типа. [6]
Является наиболее общей и, очевидно, единственно возможной в тех ситуациях, когда для решения подзадачи оценки предпочтений по правилу (2.2) необходимо предварительно решить вопрос о существовании допустимых решений. Число таких ситуаций довольно велико, особенно в экстремальных задачах комбинаторного типа и в задачах, решаемых итерационными методами. [7]
 |
Граф структур решений классической задачи выбора. [8] |
Учитывая, что задачи математического программирования и, особенно, экстремальные задачи комбинаторного типа весьма чувствительны к вариациям форм критерия, ограничений и даже числовых значений компонентов ограничений, изменим формулировку задачи. [9]
Задачи вторичной оптимизации, решаемые подсистемой Тактика, относятся к классу экстремальных задач комбинаторного типа. Трудности решения таких задач определяются в основном сложностью формализации задач управления в классе известных математических моделей, необходимостью полного учета специфики конкретных промышленных цехов и большой размерностью этих задач. [10]
Каждый путь, показанный на схеме от ее начала до висячей вершины, соответствует отдельной модели. Однако, несмотря на различия, общим у всех моделей является то, что они описывают типичные экстремальные задачи комбинаторного типа. Известно, что получение точного решения таких задач в общем случае сопряжено с большими трудностями и общих методов точного решения пока не существует. Однако специфика задач часто позволяет найти достаточно хорошие приближенные решения. [11]
Одной из основных задач при размещении элементов ИМС является формализация технологических и схемотехнических ограничений, а также выбор критерия оптимальности размещения для достаточно широкого класса схем. В настоящее время можно назвать лишь общий критерий, обязательный для всех ИМС с однослойной металлизацией, который заключается в минимизации числа пересечений междуэлементных соединений. Задачу размещения элементов целесообразно решать в два этапа. На первом этапе определяют характер размещения элементов, обеспечивающий минимум числа пересечений, а на втором осуществляют привязку к конкретным геометрическим размерам. Первый этап соответствует экстремальной задаче комбинаторного типа, которая может быть решена методами дискретной оптимизации. В случае получения неоднозначного решения необходимо учитывать технологические и схемотехнические ограничения, свойственные конкретной схеме. Распространенный метод оценки размещения элементов в процессе выполнения внутрисхемных соединений нельзя считать удовлетворительным, так как он является по существу методом проб и ошибок и не гарантирует ни получения решения вообще, ни тем более получения оптимального размещения. Анализ задачи размещения элементов показывает, что для ее решения возможно применение аппарата математического программирования. [12]
Одной из основных проблем при решении задачи размещения элементов ИМС является формализация технологических и схемотехнических ограничений, а также выбор критерия оптимальности размещения для достаточно широкого класса схем. В настоящее время можно назвать только один общий критерий, обязательный для всех ИМС с однослойной металлизацией, который заключается в минимизации числа пересечений межэлементных соединений. Задачу размещения элементов целесообразно решать в две стадии. На первой стадии определяется характер размещения элементов, обеспечивающий минимум числа пересечений, а на второй стадии осуществляется привязка к конкретным геометрическим размерам. Первая стадия сводится к экстремальной задаче комбинаторного типа, которая может быт решена методами дискретной оптимизации. В случае получения неоднозначного решения требуется учитывать схемотехнические и технологические ограничения, свойственные конкретной схеме. Распространенный в настоящее время метод оценки качества размещения элементов в процессе выполнения внутрисхемных соединений является неудовлетворительным, так как он является по существу методом проб и ошибок и не гарантирует ни получения размещения вообще, ни тем более получения оптимального размещения. Анализ проблемы размещения элементов показывает, что для ее решения возможно применение аппарата математического программирования. [13]
Страницы: 1