Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Программирования






Решение задач дискретной оптимизации связано с трудностями принципиального характера. Полный перебор точек допустимого множества, как правило, не осуществим из-за слишком большого объема вычислительной работы. Из-за дискретности допустимого множества неприменимы многие приемы, разработанные в математическом программировании, например, движение по направлению градиента или антиградиента и так далее. Неприменимы здесь и критерии оптимальности, полученные для непрерывных задач оптимизации. Отметим еще, что в задачах ЦЛП даже отыскание одной произвольной точки допустимого множества может оказаться весьма трудоемкой задачей. Поэтому для решения задач целочисленного программирования приходится создавать специальные методы.

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

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

Рассмотрим задачу (4.1), (4.2) и запишем ее в матричной форме:

f (x) = (c, x) ® min,

Ax ³ b, x ³ 0,

xi = 0, 1, 2, ¼, i = 1, 2, ¼, l,

где с = (с 1, с 2, …, сn) - вектор коэффициентов целевой функции (4.1), х = (х 1, х 2, …, хn) - вектор переменных, A - матрица коэффициентов aij левых частей (4.2), b = (b 1, b 2, …, bm) - вектор правых частей (4.2).

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

На следующем шаге производится ветвление по одной из целочисленных переменных, имеющих дробное значение в оптимальном решении задачи ЛП-1. Для определения переменной, по которой производится ветвление, разработан ряд правил. Приведем некоторые из них.

1. Выбор целочисленной переменной, значение которой в оптимальном решении ЛП-1 имеет наибольшее дробное значение.

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

3. Произвольные правила выбора.

Пусть ветвление происходит по целочисленной переменной хj, дробное значение которой в оптимальном решении ЛП-1 равно b j. Далее рассматриваются две новые задачи ЛП, обозначаемые через ЛП-2 и ЛП-3. Они получаются путем введения ограничений xj £ [b j ] и xj £ [b j ]+1, где через [b j ] обозначается целая часть b j. Условия задач ЛП-2 и ЛП-3 можно записать следующим образом:

ЛП-2 ЛП-3

f = cx ® min f = cx ® min

Ax = b, Ax = b,

xj £ [b j ], x ³ 0. xj £ [b j ]+1, x ³ 0.

Допустим, что оптимальные решения задач ЛП-2 и ЛП-3 также содержат дробные значения целочисленных переменных и поэтому не являются допустимыми для исходной задачи.

На следующем шаге необходимо выбрать задачу ЛП-2 или ЛП-3 и произвести ветвление в соответствующей вершине, вводя новое ограничение. Выбор вершины (задачи ЛП) для дальнейшего ветвления обычно осуществляется с помощью следующих специальных правил.

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

2. Правило “ последним пришел - первым обслужен ”. Для дальнейшего ветвления выбирается произвольным образом) задача ЛП, решавшаяся последней.

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

1. Оптимальное решение, соответствующее данной вершине, целочисленно. В этом случае полученное решение допустимо для исходной задачи ЦЛП.

2. Задача ЛП, соответствующая данной вершине, не имеет допустимых точек.

3. Оптимальное значение f соответствующей задачи ЛП неменьше текущей верхней границы.

При использовании метода ветвей и границ выбор вершин для дальнйшего ветвления происходит до тех пор, пока остается хотя бы одна непрозондированная вершина. Прозондированная вершина с наименьшим значением f дает точку минимума исходной задачи ЦЛП. Таким образом, эффективность метода ветвей и границ существенно зависит от скорости последовательного зондирования вершин. Обычно для выполнения условий 1 и 2 требуется значительное время. Условие 3 нельзя использовать до получения верхней границы для задачи ЦЛП. Однако верхняя граница получается только после просмотра вершины, удовлетворяющей условию 1. Поэтому иногда перед реализацией метода ветвей и границ бывает весьма полезно найти какую-нибудь целочисленную допустимую точку задачи ЦЛП.

Метод ветвей и границ можно применять для решения задач нелинейного целочисленного программирования.

Рассмотрим пример решения задачи ЦЛП методом ветвей и границ.

Пример 4.1. Найдем точку минимума целевой функции f (x 1, x 2) = - 3 x 1 - 2 x 2 на допустимом множестве

Х = { х 1 £ 2, х 2 £ 2, х 1 + х 2 £ 3, 5, х 1, х 2 ³ 0 - целочисленные}.

Шаг 1. Решение задачи ЛП-1: х 11 = 2, х 21 = 1, 5. Нижняя граница: f 1 = f (x 11, x 21) = -9.

Шаг 2. Переменная ветвления - х 2.

ЛП-2 ЛП-3

f (x 1, x 2) = - 3 x 1 - 2 x 2 ® min f (x 1, x 2) = - 3 x 1 - 2 x 2 ® min

X 2: x 1 £ 2, x 2 £ 2, X 3: x 1 £ 2, x 2 £ 2,

x 1 + x 2 £ 3, 5, x 1 + x 2 £ 3, 5,

x 2 £ 1 (новое ограничение), x 2 ³ 2 (новое ограничение),

x 1, x 2 ³ 0. x 1, x 2 ³ 0.

Решение задачи ЛП-2: х 12 = 2, х 22 = 1. Вершина ЛП-2 прозондирована. Верхняя граница: f 2 = f (x 12, x 22) = -8.

Решение задачи ЛП-3: х 13 =1, 5, х 23 = 2. f 3 = f (x 13, x 23) = -8, 5. В вершине ЛП-3 производим следующее ветвление.

Шаг 3. Переменная ветвления - х 1.

ЛП-4 ЛП-5

f (x 1, x 2) = - 3 x 1 - 2 x 2 ® min f (x 1, x 2) = - 3 x 1 - 2 x 2 ® min

X 4: x 1 £ 2, x 2 = 2, X 5: x 1 £ 2, x 2 = 2,

x 1 + x 2 £ 3, 5, x 1 + x 2 £ 3, 5,

x 1 £ 1 (новое ограничение), x 1 ³ 2 (новое ограничение),

x 1, x 2 ³ 0. x 1, x 2 ³ 0.

Допустимое множество Х 5 задачи ЛП-5 пусто. Вершина ЛП-5 прозондирована.

Решение задачи ЛП-4: х 14 = 1, х 24 =2. f 4 = f (x 14, x 24) = -7 > f 2. Вершина ЛП-4 также прозондирована.

Ответ: решение исходной задачи ЦЛП - х 1 = 2, х 2 = 1. Значение целевой функции f = -8.






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.