135 Постановка задач дискретной оптимизации. Прикладные дискретные модели.

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

f(x)->max(min)

g(x)<(>.=)bj, xj принадлежит Dj – множеству допустимых значений параметра xj.

Классификация задач дискретной оптимизации:

1. В зависимости от вида целевой функции и ограничений задачи делятся на линейные и нелинейные.

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

Прикладные дискретные задачи.

1. Задача о ранце. Имеются предметы n-видов и для каждого j-предмета известна его ценность Cj и объём Aj. Суммарный объём всех предметов ограничен и =b .Необходимо таким образом выбрать предметы, чтобы их суммарная ценность была max, а суммарный объём не превышал бы заданного числа b. Эта Задача интерпретируется как задача загрузки ранца объёма V и называется одномерной задачей о ранце. Если в кач-ве хар-к ранца рассматривается не только объём, ной другие хар-ки bi , то получиться многомерная задача о ранце.

2. Задача о назначении. Имеется n исполнителей и m-видов работ, кот они могут выполнить. Каждый исполнитель может выполнить только одну работу, а каждая работа может быть выполнена только одним исполнителем. Известны значения Cij, характеризующие производительность i-ro работника при назначении на j-ю работу. Необходимо так распределить работников по видам работ, чтобы суммарная производ-ть была max

3 Задача о покрытии. Имеется n-предметов и m признаков, кот они могут обладать. Условия задаются матрицей А с

Переменными Aij (1, если j-й предмет обладает i признаком ; 0- в противном случае)

Необходимо выбрать min набор предметов, кот в совокупности обладали всеми m признаками.

136. Методы решения задач дискретной оптимизации.

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

f(x)->max(min)

g(x)<(>.=)bj, xj принадлежит Dj – множеству допустимых значений параметра xj.

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

1) Метод отсечений – предназначен для решения линейных целочисленных или частично целочисленных задач.

2) Комбинаторные методы 3) Приближенные методы

1) Метод отсечения. Решение задач целочисленной линейной оптимизации методом отсечений сводится к решению последовательности спец. образом построенных задач P0,P1,Ps. Задача P0 образуется из исходной задачи путем отбрасывания условия целочисленности. Каждая последующая задача P1,P2…Ps, образуется из предыдущей путем добавления к ней дополнительных линейных ограничений, которые называются правильным отсечением. Методы отсечения различаются между собой способами формирования дополнительных ограничений. Наиболее распространенным является метод отсечения Гомори.

Основные шаги метода ГОМОРИ.

1. Определение оптимального решения исходной задачи без учета требований целочисленности. Условие целочисленности отбрасывается и задача решается обычным симплекс- методом.

2. Если полученное решение целочисленное – то работа алгоритма заканчивается, в противном случае переход к шагу 3

3. На основании последней симплекс таблицы формируем отсечение ГОМОРИ. ∑{asi}xj >={bsj}, s номер строки таблицы , которой соответствует переменная с наибольшей дробной частью.

4. Добавление дополнительных ограничений к условию решаемой задачи: ∑{asi}xj -xd={bsj}, где xd- дополнительная переменная, умноженная на -1 - ∑{asi}xj +xd=-{bsj}.Добавляется к последней симплекс таблице и полученная задача решается двойственным сиплекс методом.

5. Переход к шагу 2.

Недостатки; метод может использоваться для решения частично- целочисленных задач. Недостатки: метод используется для решения линейно-целочисленных задач. В процессе решения при добавлении дополнительных ограничения размер задачи возрастает.

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

3) Приближённые методы. Для точного алг-ма нужно знать трудоёмкость и память. Для приближенного алгоритма, кроме трудоемкости и памяти, вводят такие параметры, как относительная погрешность еА алгоритма А и вероятность несрабатывания 6А алгоритма А.