Полная версия

Главная arrow Логистика arrow Методы управления инвестициями в логистических системах

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ МЕТОДОВ ОПТИМИЗАЦИИ ИНВЕСТИЦИОННЫХ РЕШЕНИЙ В ЛОГИСТИКЕ

ЗАДАЧИ, АЛГОРИТМЫ, СЛОЖНОСТЬ

Анализируя методы решения задач управления ограниченными ресурсами в логистике (таких, например, как выбор оптимальной производственной программы или минимизация инвестиционной фазы проекта строительства склада), разработчик алгоритмов решения часто убеждается в том, что не удается предложить ничего лучшего, чем полный перебор всех вариантов. В том случае, если более эффективного решения дискретной оптимизационной задачи не существует, говорят, что задача труднорешаема.

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

Тем не менее в этой главе будут предложены подходы, позволяющие найти достойный выход из положения. Эти подходы предусматривают доказательство того, что та или иная задача так же трудна, как и большое число других задач, признанных очень трудными и не поддающихся решению в течение многих лет. Методы этих доказательств изложены в теории так называемых NP-полных задач.

Используя эти подходы и методы, можно доказать NP-полноту задачи о выпуске новой продукции и таким образом установить ее эквивалентность всем другим задачам этого класса. Однако проблема решения задачи после выявления ее NP-полноты не исчезает; наоборот, работа над ней только начинается. Знание же этого факта дает важную информацию о том, какие методы окажутся наиболее перспективными. В этом случае не следует пытаться разработать эффективный точный алгоритм, лучше сосредоточить внимание на получении иных, более скромных результатов. Например, можно попытаться разработать эффективные алгоритмы, позволяющие решать различные частные случаи поставленной общей задачи. Можно также заняться отысканием алгоритма, хотя и не гарантирующего быстрого решения во всех случаях, однако работающего быстро в большинстве ситуаций. И наконец, можно «ослабить» постановку задачи, потребовав при разработке алгоритма проектирования нового вида продукции выполнения не всех требований к характеристикам продукции, а только части из них. Иными словами, основное предназначение теории NP-полных задач состоит в том, чтобы помочь разработчикам алгоритмов, направив их усилия на выбор таких подходов к решению задач, которые вероятнее всего приведут к практически полезным алгоритмам.

Далее будем использовать такие понятия, как «труднорешаемые задачи» и «эквивалентные по сложности задачи», а также некоторые другие термины.

Вначале рассмотрим понятие «задача». Под массовой задачей (или просто задачей) будем понимать некоторый общий вопрос, на который необходимо дать ответ. Обычно задача содержит несколько параметров, или свободных переменных, конкретные значения которых не определены.

Массовая задача называется задачей II, если она определяется следующей информацией:

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

Индивидуальная задача I может быть получена из массовой, если всем параметрам задачи II присвоить конкретные значения.

В качестве примера рассмотрим классическую задачу коммивояжера. Параметры этой задачи состоят из конечного набора «городов» С = {С,, С2,..., Ст} и расстояний d (Ср Ср между каждой парой городов р С) из С. Решение задачи — это такой упорядоченный набор <Стг(1), Стг(2), ..., Ск(т)> заданных городов, который минимизирует величину

Это выражение дает длину маршрута, который начинается в городе С7г(1), проходит последовательно через все города и возвращается в С7г(1) непосредственно из последнего города Сп(т).

? Индивидуальная задача коммивояжера, указанная на рис. 9.1, задается следующим образом: С=р С2, С3, С4); Графическая интерпретация задачи коммивояжера

Рис. 9.1. Графическая интерпретация задачи коммивояжера

Последовательность <С,, С2, С4, С3> представляет собой решение задачи, поскольку соответствующий маршрут имеет минимально возможную длину, равную 27. ?

Под алгоритмом будем понимать общую выполняемую шаг за шагом процедуру решения задачи. Для определенности будем считать, что эта процедура записана на одном из формальных языков программирования. Будем говорить, что алгоритм решает массовую задачу II, если он применим для любой индивидуальной задачи I из II и обязательно дает решение задачи I. Отметим здесь следующее: нельзя говорить о том, что алгоритм «решает» задачу коммивояжера, если он не выдает маршрут минимальной длины хотя бы для какой-то одной индивидуальной задачи.

В большинстве случаев с учетом размерности решаемых задач исследователя интересует наиболее эффективный алгоритм решения. Понятие эффективности связано со всеми вычислительными ресурсами, необходимыми для работы алгоритма. Однако под «самым эффективным алгоритмом» понимается самый быстрый, так как именно быстродействие определяет пригодность конкретного алгоритма для практики.

Время работы алгоритма удобно выражать в виде функций от одной переменной, характеризующей размер индивидуальной задачи, т.е. объем входных данных, требуемых для описания этой задачи. Такой подход удобен, так как в дальнейшем сравнительная сложность задачи будет оцениваться через ее размеры. Часто размер задачи определяется неформально. Например, для определения размера в задаче коммивояжера используется число городов. Кроме числа городов в этой задаче важно учитывать расстояния между т городами, которые представляют собой т(т- 1)/2 чисел. Чтобы учесть все факторы, влияющие на время решения задачи, необходимо дать описание индивидуальной задачи, которое можно рассмотреть как некоторую цепочку символов, выбранных из конечного входного алгоритма.

Далее будем полагать, что с каждой массовой задачей связана некоторая фиксированная схема кодирования, которая отображает индивидуальные задачи в соответствующей цепочке символов. Входная длина индивидуальной цепочки задачи I из II определяется как число символов в цепочке, полученной применением к задаче I схемы кодирования для массовой задачи II. Именно это число, т.е. входная длина, и используется в качестве формальной характеристики размера индивидуальной задачи.

? Например, реализуемые конкретные задачи о коммивояжере можно описать с помощью алфавита {С, [,],/,0,1,2,3,4,5,6,7,8,9}, при этом задача на рис. 9.1 может быть закодирована цепочкой символов вида: С[ 1] С[2] С[3] С[4]//10/5/9//6/9//3.

Аналогичным образом могут быть закодированы и более сложные индивидуальные задачи. При такой кодирующей схеме индивидуальная задача о коммивояжере на рис. 9.1 имеет длину 32. ?

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>