Cтраница 4
Аналогичный подход применим и к другим дискретным задачам, возникающим при аппроксимации задач, связанных с отысканием функций непрерывного аргумента. [46]
Аддитивный алгоритм применяют непосредственно к исходной дискретной задаче, не используя, в отличие от первоначальных вариантов метода ветвей и границ, решения соответствующей задачи линейного программирования. Вычислительный процесс чрезвычайно прост, ибо в нем используются лишь операции сложения и вычитания; тем самым устраняется проблема ошибок округления. Важно также, что исходная матрица ограничений в ходе алгоритма не подвергается пересчету. [47]
Отсюда ясно, что в дискретных задачах область допустимых решений G является невыпуклой и несвязной. [48]
Особое место в теории оптимизации занимают дискретные задачи, в которых из конечного множества трудно обозримых вариантов требуется выбрать в каком-то смысле наилучший. Многие из таких задач формально сводятся к максимизации или минимизации линейной функции на множестве целочисленных решений некоторой конечной системы линейных уравнений и неравенств. Рассмотрению этого важного класса экстремальных задач посвящена в нашем курсе отдельная глава. Однако необходимо отметить, что такие задачи являются весьма сложными, и эффективных численных методов для их решения в общем случае не существует. Между тем исследование и решение некоторых дискретных задач удается свести к рассмотрению специальным образом построенной транспортной задачи. Это связано с важным свойством решений транспортных задач, о котором шла речь в замечании 5.4. Приведем характерный пример сведения дискретной экстремальной задачи к транспортной. [49]
Отметим, что описанный прием сведения дискретных задач к целочисленным имеет в основном теоретический интерес, ибо в настоящее время методы отсечения распространены непосредственно на дискретные задачи. [50]
Основные понятия из теории полиномиальной сводимости дискретных задач и вычислительной сложности алгоритмов вводятся в третьем параграфе. Следует отметить, что, в отличие от первых двух, чтение третьего параграфа требует определенного уровня подготовки. Для чтения остальных глав достаточно такого понятия, как временная сложность алгоритма. [51]
Из методов динамического программирования для решения дискретной задачи в общем случае применима вычислительная схема, основанная на полной системе функциональных уравнений, предназначенная для отыскания глобального оптимума. [52]