Физико – математический факультет
Кафедра прикладная информатика
Выполнила: Усова Ю.О.
Студенка 1 курса
Заочной формы обучения
Направление «Прикладная информатика в экономике »
Доклад на тему:
Задачи дискретного программирования
Руководитель: Напалков С.В
Арзамас 2019 г.
Оглавление
Введение. 3
1. Задачи дискретного программирования. 3
1.1. Задачи с неделимостями. 3
1.2. Экстремальные комбинаторные задачи. 4
1.3. Задачи с разрывными целевыми функциями. 5
2. Методы решения задач дискретного и целочисленного программирования. 5
2.1. Метод отсечения для решения задач целочисленного линейного программирования. 6
2.2. Комбинаторные методы решения задач целочисленного линейного программирования. 6
2.3. Методы случайного поиска. 6
2.4. Эвристические методы.. 7
Заключение. 8
Введение
Дискретноепрограммирование[discrete programming] — раздел оптимального программирования, изучающий экстремальные задачи, в которых на искомые переменные накладывается условиецелочисленности, а область допустимых решений конечна. Таким образом, здесь используется модельобщей задачи математического программирования с дополнительным ограничением: x1, x2, …, xn — целочисленны.
Задачи дискретного программирования
Многие задачи исследования операций такие, как задачи распределения ресурсов, сетевого планирования и управления, календарного планирования, размещения, замены оборудования – описываются математическими моделями дискретного программирования. По структуре математической модели задачи дискретного программирования делятся на следующие классы:
· Задачи с неделимостями;
· Экстремальные комбинаторные задачи;
· Задачи на несвязных выпуклых областях;
· Задачи с разрывными целевыми функциями.
Задачи с неделимостями
Математические модели задач с неделимостями основаны на требовании целочисленности переменных {х,}, вытекающем из физических условий практических задач.
К таким задачам относится задача об определении оптимальной структуры производственной программы, где {х,, х2,..., х„} —объемы выпуска продукции.
Большинство целочисленных и комбинаторных типов задач, таких, как задача с неделимостями, задача коммивояжера, задача календарного планирования, принадлежит к разряду так называемых трудно
решаемых. Это означает, что вычислительная сложность алгоритма их точного решения — зависимость числа элементарных операций (операций сложения или сравнения), необходимых для получения точного решения, от размерности задачи я — является экспоненциальной (порядка 2n), т.е. сравнимой по трудоемкости с полным перебором вариантов. В качестве п, например, для задачи с неделимостями служит число целочисленных переменных и число ограничений, для задачи коммивояжера — число городов (или узлов графа маршрутов), для задачи календарного планирования — число деталей и число станков. Такие задачи называют еще NP-трудными или NP- полными. Получение их точного решения не может быть гарантировано, хотя для некоторых задач данного типа существуют эффективные методы, позволяющие находить точное решение даже при больших размерностях. Примером таких задач служит задача о ранце с булевыми переменными.
Экстремальные комбинаторные задачи.
Задачи данного класса, называемые также задачами выбора, состоят в отыскании среди конечного множества альтернатив одной, которой отвечает экстремальное значение принятой целевой функции.
Задача о коммивояжере — классический пример задачи выбора оптимального маршрута
Задачи на несвязных выпуклых областях.
Наиболее важный классификационный признак – выпуклость. По этому признаку все задачи математического программирования разделяются на выпуклые и невыпуклые.
Задача математического программирования называется выпуклой, если она состоит в максимизации (минимизации) выпуклой вверх (вниз) целевой функции на выпуклом множестве, в противном случае задача называется невыпуклой.
Однако если задача является выпуклой, то ее решение существенно упрощается. В выпуклой задаче локальный экстремум одновременно является и глобальным. Выпуклая задача может иметь только один строгий экстремум и все сводится к нахождению этого единственного экстремума.
Для решения выпуклых задач разработаны многочисленные численные методы, приспособленные для решения на ЭВМ, связанные с понятием градиента целевой функции и основной идеей о том, что функция наиболее быстро убывает, если двигаться в направлении, противоположном градиенту. К ним относятся метод градиентного спуска, метод сопряженных градиентов и т.д. Но есть и методы, основанные на других идеях: метод штрафных функций, многочисленные варианты метода случайного поиска и т.д.