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

Главная arrow Математика, химия, физика arrow Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач

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


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

Особенности задач дискретной оптимизации

Отличия непрерывных и дискретных задач оптимизации

В общем случае задача однокритериальной оптимизации может быть записана в следующем виде:

Найти -вектор неизвестных, D- множество

допустимых значений этого вектора, F(x)- заданная целевая функция.

Задача на шах- сводится к задаче на минимум заменой F(x) на минус F(x). В такой общей формулировке задача оптимизации называется задачей математического программирования. Если В(х)-линейная функция, a D - определяется системой линейных неравенств (равенств), то в этом частном случае имеем задачу линейного программирования. Допустимая область представляет собой замкнутый выпуклый многогранник, но может быть неограниченной или пустой. Такие задачи хорошо изучены, для их решения имеются различные компьютерные программы.

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

Под задачей дискретной оптимизации (дискретного программирования) понимается задача математического программирования, в которой множество допустимых решений конечно, т.е. 0 < |D| = N <оо, где |D| — число элементов множества D. В силу конечности D все допустимые решения можно пронумеровать: x',x2,...,xN, вычислить F(x'), i = 1,2,...,N и найти наименьшее значение.

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

Действительно, если каждая из п координат искомого вектора х может принимать к значений независимо от других координат, то суммарное число решений |D|=N=kn и уже при к=2 оно резко возрастает с ростом п. Так 2*1012. Это означает, что перебор такого числа вариантов на современном компьютере будет длиться часами, а при п=100 вообще невозможен.

Задачи дискретного программирования имеют ряд особенностей, которых нет в таких задачах математического программирования, как линейные или выпуклые задачи. Современные методы исследования непрерывных задач математического программирования основываются на использовании классических понятий: бесконечно малая величина, расстояние, окрестность, производная. Эти понятия не могут аналогичным образом применяться в дискретном программировании. В частности, такое фундаментальное понятие, как окрестность допустимого решения, в задачах дискретного программирования можно ввести лишь с применением различных искусственных приёмов. Это приводит к тому, что два допустимых решения из некоторой как-то формально определённой окрестности могут сколь угодно сильно отличаться по значениям целевой функции. Отсюда следует, что мерой близости двух допустимых решений (точек допустимой области D) является разность значений целевой функции в соответствующих точках или другая величина, вычисляемая по этим значениям. Исходное положение многих методов математического программирования : если две допустимые точки близки, то и значения целевой функции в них также близки в задачах дискретной оптимизации не имеет места. Покажем это на простом примере векторов, координаты которых могут принимать только два значения: 0 или 1. Такие векторы называются булевыми. Под окрестностью такого вектора x(xi,X2,...,xn) будем понимать все векторы, получаемые из х заменой одного нуля (любого) на единицу или одной единицы (любой) на ноль.

Рассмотрим задачу:

Найти шах где к>1, при условиях , i= 1,2,3 и

Искомый максимум равен к+1 и достигается в двух точках: А(0,1,1) и В( 1,0,1). Точка С(0,1,0) попадает в окрестность точки А и даёт значение целевой функции равное 1. Разность значений целевой функции в двух точках А и С из одной окрестности («близкие» точки) равна к и может быть сколь угодно велика при выполнении всех условий задачи. Аналогично для точки В( 1,0,1) и точки Сi( 1,0,0) из её окрестности.

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

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

Частным случаем задач дискретной оптимизации являются задачи, в которых неизвестные могут принимать только целые значения. Идея решения таких задач как непрерывных с последующим округлением полученных значений неизвестных до целых чисел может оказаться несостоятельной. Рассмотрим особенности таких задач на примере целочисленного линейного программирования.

Пример некорректности округлений

Рис. 2.1. Пример некорректности округлений

Пусть допустимая область D такая, как на рис. 2.1. Задача состоит в поиске max Х1+Х2 на допустимой области D, при условии, что xi и хг целые. Очевидно, что без учёта этого условия максимум достигается в точке с координатами (0,5; 4,5) и равен 5. При округлении координат этой точки до целочисленных значений получаем недопустимые точки. Решением исходной целочисленной задачи являются точки с координатами (0;1) и (1;0) и искомый максимум равен 1.

В задачах с большим числом переменных решение, полученное без учёта ограничения по целочисленности переменных, может существенно отличаться от искомого целочисленного решения и по координатам и по значению целевой функции. Так, в этом примере, увеличивая ординату точки А, отклонения решений целочисленной задачи от решения непрерывной задачи можно сделать сколь угодно большими и по целевой функции и геометрически. Вообще целочисленное линейное программирование это особый класс задач [1,11,22,33].

Рассмотрим ещё один пример, демонстрирующий отмеченные особенности целочисленных задач.

На координатной плоскости Х1ОХ2 возьмём прямую Х2=7Ш. Очевидно, что на этой прямой нет точки с целочисленными координатами. Возьмём произвольную точку А на этой прямой (рис. 2.2) и будем рассматривать только первый квадрант.

Отличие непрерывной и дискретной задач

Рис. 2.2. Отличие непрерывной и дискретной задач

Если повернуть прямую ОА на достаточно малый угол с центром в точке А по часовой стрелке, то в треугольнике ОАВ тоже не будет ни одной точки с целочисленными координатами, кроме начала координат.

Аналогично при вращении прямой ОА против часовой стрелки на достаточно малый угол (возможно другой, чем в первом случае) получим треугольник ОАС, также не содержащий точек с целочисленными координатами, кроме точки О.

Пусть нужен шах xi+хг на допустимой области АВОС (рис. 2.2). Без учёта целочисленности переменных этот максимум достигается в точке А, а при учёте этого требования единственной допустимой точкой является точка О и максимум равен нулю, тогда как максимум в непрерывной задаче можно сделать сколь угодно большим числом при удалении точки А от начала координат по прямой Х2=7гхь При этом неограниченно увеличивается и разность координат точек А и О. Более того, если в качестве допустимой области взять треугольник АВС, то целочисленная задача не имеет решений, что невозможно обнаружить, решая непрерывную задачу.

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