Квадратичная задача

Cтраница 1

Квадратичная задача о назначениях заключается в следующем. [1]

Решение квадратичной задачи о назначениях является с вычислительной точки зрения нелегким делом. В настоящее время для нее создано несколько точных и приближенных методов; правда, точные методы реализуемы лишь для задач сравнительно небольших размеров. Описание и сравнение ( по результатам - численных экспериментов; нескольких приближенных методов дано в статье Хиллиера и Коннорса [96]; там же приведена библиография по данному вопросу. [2]

Таким образом, квадратичная задача назначения в целочисленной постановке сводится к задаче минимизации функционала (15.24) на множестве связей (15.21) - (15.23) и формально отличается от линейной задачи (15.16) - (15.19) только целевой функцией. [3]

Аналогично можно было бы представить квадратичную задачу о назначениях. [4]

В точке х оценка множителя Лагранжа равна нулю. Точка х предсказанного безусловного минимума удовлетворяет ограничению. [5]

В данном случае даже точный для квадратичных задач критерий, будучи примененным в точке х, может указать, что ограничение а [ х Ь надо снять, хотя в действительности лучше было бы его оставить. [6]

Коль скоро направление спуска предлагается строить как решение квадратичной задачи (3.7.1), нужен алгоритм поиска этого решения. Мы считаем, что здесь стоит применить описанный ранее аппарат разложения матриц, и в частности можно воспользоваться слегка модифицированными версиями квазиньютоновских и ньютоновских методов, представленных в разд. [7]

Работа по решению ( в целых числах) квадратичных задач о назначениях, таких, как описанная выше, продолжается. Однако в настоящее время наиболее полезным алгоритмом, дающим целочисленные значения, является алгоритм транспортной задачи, который может быть применен к задаче о назначениях с линейной целевой функцией. [8]

Другим примером задач с взаимозависимыми назначениями является так называемая квадратичная задача назначения, в которой мера затрат / - го исполнителя на данную работу зависит от назначения на ту же работу не всех остальных, а только j - ro исполнителя. Одной из наиболее распространенных является следующая содержательная постановка, приводящая к квадратичной задаче назначения. [9]

Отметим, что описанные в настоящем пункте результаты относятся к линейным и квадратичным задачам, у которых целочис-ленны лишь коэффициенты целевой функции и элементы матри -: цы условий. На компоненты искомого решения никаких условий целочисленности не накладывается. Задача последнего типа универсальна, а для задач, рассмотренных в [40, 100], универсальность не доказана. [10]

Эффективность алгоритма метода вектора спада подтверждена также при решении другого типа задач размещения - квадратичной задачи о назначениях, в частности, тест-задачи Штейнберга, широко известной в литературе. В табл. 21 приведены данные по решению этой задачи 12 алгоритмами, причем данные по первым десяти алгоритмам заимствованы нами из книги [134], а применение метода сужающихся окрестностей описано в работе [153]; в последней строке таблицы приведены данные о применении метода вектора спада. [11]

В работе [42] предлагается использовать метод ветвей и границ в алгоритме оптимального размещения ЕО технических объектов, представляющий собой квадратичную задачу о назначениях. [12]

Целевая функция (6.14) является квадратичной, поэтому задача компоновки, сформулированная в виде задачи (6.14) - (6.16), является квадратичной задачей дискретного программирования. [13]

Но к ограничениям двойственной формулировки ( 33) это не относится, поэтому, когда Л - положительно определенная матрица, квадратичная задача ( 31) допускает для любого М решение, которое одновременно является решением задачи ( 32) и, следовательно, удовлетворяет ограничениям последней. [14]

Различные интерпретации необходимых условий существования экстремума (2.9) привели к разработке целого ряда алгоритмов, многие из которых преследуют цель свести решение исходной квадратичной задачи к вариантам линейного программирования. [15]

Страницы: 1 2