Лекция: Дискретное программирование

Задача математического программирования состоит, в общем случае, в поиске минимума целевой функции или функционала (см. п. 6.5.)

, (6.7)

и элементов множества, которые доставляют этот минимум

, .

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

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

.

Пусть некоторое достаточно большое число, — нижняя граница значений на ( в частности, можно полагать. Если, то присвоим. Выбираем далее одно из еще не ветвленных множеств. И если, то повторяем процедуру. Поскольку конечное множество, то конечное число итераций приводит к оптимальному решению задачи. Процесс ветвления удобно изображать в виде графа. Заметим, что обычно на каждом шаге проводят разбиение на два не пересекающихся подмножества. Такой прием вообще часто используется в математике. Важно, чтобы с проведенным разбиением всегда можно было увязать однозначное «да» или «нет» в связи с поставленным вопросом. Например, один из студентов задумал слово, обозначающее тот или иной предмет. Задавая наводящие вопросы таким образом, чтобы он на них мог ответить определенно «да» или «нет», можно спустя конечное число итераций определить задуманное слово.

Рассмотрим типовые задачи, решение которых может быть найдено методом ветвей и границ.

Задача о коммивояжере

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

Введем приведенную матрицу издержек, в каждой строке и столбце которой имеется хотя бы по одному нулю. Чтобы привести матрицу по строкам нужно из всех элементов — строки вычесть минимальный из элементов:. Чтобы привести матрицу по столбцам нужно из всех элементов матрицы вычесть минимальный из них: .

Тогда величина является нижней границей издержек маршрута для матрицы (она называется суммой приводящих констант). Далее решение проводится по следующему алгоритму:

1. Полагается .

2. Получение приведенной матрицы .

3. Определение. Пусть .

4. Отбираем пары, для которых. Они составляют множество — множество маршрутов, содержащих данную пару городов для переезда.

5. Для претендентов на включение в определяется ( — претендент на ветвление).

6. Выбор, где пара .

7. Определение нижней границы для множества (то есть, для множества «не– „):

.

8. Запрет на пару ( –ая строка и –ый столбец исключаются).

9. Определение размерности матрицы. Если порядок матрицы равен 2, то переходим к пункту 10. В противном случае приводим матрицу и переходим к пункту 4.

10. Проверка условия оптимальности. Если оценка полученного маршрута не превышает оценок еще не ветвленных маршрутов, то найденный маршрут является оптимальным. Иначе процесс ветвления продолжается, исходя из множества с меньшей оценкой. При этом полученный маршрут запоминается для сравнения.

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

Схематично процесс ветвления для данной задачи представлен на рис. 6.2.

Рис. 6.2. Условная схема процесса ветвления для задачи о коммивояжере.

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

Пример. Рассмотрим пример задачи о коммивояжере. Пусть некоторый станок используется для обработки партии из n деталей. Пусть детали пронумерованы числами от 1 до n. Время переналадки станка при переходе от обработки детали i к обработке детали j задается матрицей (таблица 6.4, знак означает запрет на переходы (i, i)). Требуется найти последовательность обработки деталей, минимизирующую общее время переналадок.

Таблица 6.4.

Исходная матрица C.

Полагаем k=1.

Приведем матрицу С по строкам: из каждого элемента i –той строки вычтем минимальный элемент этой строки (таблица 6.5).

Таблица 6.5.

Матрица C, приведенная по строкам

Приводим преобразованную матрицу C по столбцам (таблица 6.6).

Таблица 6.6.

Приведенная матрица C.

Находим сумму приводящих констант .

Полагаем .

Находим претендентов на ветвление. Из таблицы 6.6 следует, что это элементы Находим для каждого из этих элементов:

Максимальное. Следовательно, пара (3,6) выбирается для ветвления. Она включается в множество Y, представляющее собой подмножество переходов от обработки детали 3 к отработке детали 6. Соответственно – подмножество, в котором запрещен такой переход.

Найдем оценку подмножества:

Вычеркиваем из Таблицы 6.6. Третью строку и шестой столбец, а также ставим запрет на пару (6.3). Получаем таблицу 5 5(таблица 6.7).

Таблица 6.7.

Полагаем .

Матрица является приведенной, поэтому Претендентами на ветвление являются Находим значения:

Максимальное значение. Оценка Выбираем пару (1,2) для ветвления. В Таблице 6.7 вычеркиваем первую строку и второй столбец и ставим запрет на элемент (2,1) (Таблица 6.8).

Таблица 6.8.

Полагаем .

Матрица 6.8 приведена по строкам, однако, ее необходимо привести по столбцам (таблица 6.9).

Таблица 6.9.

Из Таблицы 6.9 следует, что Соответственно, Претендентами на ветвление являются Находим: Определяем. Оцениваем подмножество: Пара (4.1) выбирается для последующего ветвления. Из Таблицы 6.9 вычеркиваем четвертую строку и первый столбец (таблица 6.10).

Таблица 6.10.

Полагаем .

Матрица 6.10 приведенная, Претенденты на ветвление: Определяем: Максимальная величина. Оценка подмножества будет Пара (2,5)выбирается для ветвления. В Таблице 6.10 вычеркивается вторая строка и пятый столбец (таблица 6.11).

Таблица 6.11.

Таблица 6.11 представляет собой матрицу 2 2. Данная матрица является приведенной, так что. Из данной таблицы получаем пары (5,3), (5,4), (6,4), из которых нужно выбрать замыкающие для подмножества Y, в которое уже входят пары (3,6),(1,2), (4,1), (2,5). Выбрав пары (5,3), (6,4), получаем оптимальную по времени последовательность обработки деталей:

.

Оценка выбранной последовательности составляет 73 единицы времени.

Представим результат ветвления в виде графа:

Рис. 6.3. Графическое представление процесса ветвления.

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

Задача целочисленного программирования. Алгоритм Ленд и Дойг

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

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

Пусть — количество –того груза, предназначенного для транспортировки. Тогда математическая формулировка задачи будет выглядеть следующим образом:

, (6.8.)

, (6.9)

,. (6.10)

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

Для решения задачи целочисленного программирования может быть использован алгоритм Ленд и Дойг. Пусть решение задачи (6.8.)–(6.10.) существует. Пусть хотя бы одна из компонент оптимального решения, например, не является целой. Тогда используем для получения решения метод ветвей и границ. В качестве оценки множества X(1), то есть, в качестве нижней границы множества, можно взять значение. Разобьем на два непересекающихся подмножества :

(6.11)

Здесь через обозначена целая часть числа. В результате ветвления получаем две задачи линейного программирования:

Первая задача:

(6.12.)

(6.13.)

(6.14.)

. (6.15.)

Вторая задача. Вместо последнего условия (6.15.) имеет место условие:

. (6.16)

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

(6.12')

(6.13')

(6.14')

(6.15')

. (6.16')

Здесь – нецелая компонента, – соответствующее множество, для которого имеет место ветвление:

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