Подготовил Андреев Алексей. Задача о назначениях Задача о рюкзаке Задача коммивояжера Задача теории распределений Задача маршрутизации транспорта Задача. - презентация

1 Подготовил Андреев Алексей

2 Задача о назначениях Задача о рюкзаке Задача коммивояжера Задача теории распределений Задача маршрутизации транспорта Задача распределения графов.

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

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

5 Примерами счетных множеств являются множества натуральных, целых и рациональных чисел, где Z + ={0; 1; 2;...} множество неотрицательных целых чисел. В некоторых ситуациях требование «целочисленности» может быть наложено лишь на некоторые переменные x j, что кардинально не меняет характера задачи.

6 Принципиальная сложность, вызываемая наличием условий целочисленности в системе ограничений оптимизационной задачи, состоит в том, что в значительном количестве случаев невозможно заменить дискретную задачу ее непрерывным аналогом и, найдя соответствующее решение, округлить его компоненты до ближайших целых значений. Пример, показанный на рис. 4.1, демонстрирует, что при округлении оптимального плана х* обычной задачи ЛП до целых значений получается точка ([х 1 *],[x 2 * ]), не принадлежащая области допустимых планов задачи D. Условимся целую часть числа х j. обозначать [х j ], а дробную как {х j }. Тогда х j =[х j ]+{х j }. Отдельно следует добавить, что если даже оптимальный план непрерывной задачи, округленный до целых значений компонент, окажется допустимым, то целевая функция может вести себя так, что ее значение будет на нем существенно «хуже», чем на оптимальном плане целочисленной задачи.

7 Метод отсекания плоскостей, метод ветвей и границ, метод последовательного анализа и отсева, аддитивный метод и др.

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

9 Общая идея метода может быть описана на примере нахождения решения задачи минимизации функции f(x) по множеству допустимых решений x. Как f, так и x могут быть произвольными. Метод ветвей и границ использует две процедуры: ветвление и нахождение оценок (границ). Ветвление покрывает область допустимых решений областями допустимых решений меньших размеров. Процедура называется ветвлением, так как она повторяется рекурсивным образом далее к каждой из полученных подобластей, образуя дерево, называемое деревом поиска или деревом ветвей и границ. Вершины этого дерева соответствуют построенным подобластям. Другая процедура нахождение оценок, которая является быстрым методом нахождения верхних и нижних границ оптимального решения в подобласти допустимых решений. В основе метода ветвей и границ лежит простое наблюдение, что если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения. Это обычно выполняется с помощью глобальной переменной m, в которой запоминается минимальная верхняя граница, полученная для всех просмотренных до настоящего времени вариантах; любая вершина дерева поиска, нижняя граница которой больше m, может быть исключена из дальнейшего рассмотрения.

10 Метод локальной оптимизации,модификации точных методов,методы случайного поиска и др.

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

12 В экономике огромное количество задач носит дискретный характер. Прежде всего это связано с физической неделимостью многих факторов ­и объектов расчета: например, нельзя построить 2,3 завода или купить 1,5 автомобиля. Допустим, если из расчета получается, что надо построить 2,3 завода, то выбираются либо 2, либо 3 (что, разумеется, требует дополнительного анализа), точно так же не 1,5 автомобиля, а 2 или 1.

13 Дискретное программирования позволяет найти оптимальный для нас вариант решения задачи, при наложении определенных ограничений и правил.

14 КОНЕЦ