Дискретное программирование - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Дискретное программирование - страница №1/1

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Гуманитарный факультет

Кафедра Информационных Технологий

Андреев Алексей

Реферат на тему: «Дискретное программирование»

Студента 3 курса

ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ


ТИПЫ ЗАДАЧ ДИСКРЕТНОГО ПРОГРАММИРОВАНИЯ


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

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



http://www.ecosyn.ru/imag1/image289.gif

где Ω — некоторое конечное, или счетное, множество. Условие х∊Ω. называется условием дискретности. Если все переменные являются целыми, то задача является полностью целочисленной. Особое место среди дискретных задач занимает целочисленная задача линейного программирования в канонической форме (ЦКЗЛП):

Примерами счетных множеств являются множества натуральных, целых и рациональных чисел.

http://www.ecosyn.ru/imag1/image290.gif

где Z+ ={0; 1; 2; ...} — множество неотрицательных целых чисел.

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

http://www.ecosyn.ru/imag1/image291.gif

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

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

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

Метод ветвей и границ — метод решения переборных задач.

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

Общее описание

c:\users\syter\desktop\image325.gif

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

В основе метода ветвей и границ лежит простое наблюдение, что если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения. Это обычно выполняется с помощью глобальной переменной m, в которой запоминается минимальная верхняя граница, полученная для всех просмотренных до настоящего времени вариантах; любая вершина дерева поиска, нижняя граница которой больше m, может быть исключена из дальнейшего рассмотрения.

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

Ø задачи с неделимостями;

Ø экстремальные комбинаторные задачи;

Ø задачи с разрывными целевыми функциями;

Ø задачи на несвязных и невыпуклых областях и др.



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

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