Предмет, постановка и особенности задач дискретного программирования. Задачи с неделимостями и с разрывными целевыми функциями. Экстремальные комбинаторные задачи. Примеры решений задач дискретного программирования методом ветвей и границ, методом Гомори.
Аннотация к работе
Глава 1. Обзор и методы решений задач дискретного программирования 1.1 Предмет, постановка и особенности задач дискретного программирования 1.2 Модели дискретного программирования 1.2.1 Задачи с неделимостями 1.2.2 Экстремальные комбинаторные задачи 1.2.3 Задачи с разрывными целевыми функциями 1.3 Методы решения задач дискретного программирования Глава 2.Примеры решений задач дискретного программирования 2.1 Пример решения задачи методом Гомори 2.2 Пример решения задачи методом ветвей и границ Заключение Список литературы Введение Дискретное программирование сформировалось как самостоятельная и важная часть математического программирования в конце 60-х годов. Настоящая работа опирается прежде всего на работы авторитетных ученых, работающих в данной область (Сигал И. Х., Иванова А. П., Дроздов Н. Д., Корбут А. А., Фанкельштейн Ю. Ю.). Глава 1. Обзор и методы решений задач дискретного программирования 1.1 Предмет, постановка и особенности задач дискретного программирования дискретное программирование задача Дискретное программирование - раздел оптимального программирования 0 и вес aj > О, j = 1,2,...,n. После введения этих переменных суммарная ценность и грузоподъемность соответственно имеют вид f(x1,x2,...,xn)= g(x1,x2,...,xn) = Поэтому задача об одномерном ранце имеет вид >max, (1) ?R, (2) x jЄ{0,1} , j=1,…, n. Получим задачу о многомерном ранце (4)-(6). 1.2.2 Экстремальные комбинаторные задачи В данных задачах необходимо найти экстремум некоторой целевой функции, заданной на конечном множестве, элементами которого служат перестановки из n символов. Например, компетентность i-го работника при работе на j-й должности; время, за которое i-е транспортное средство перевезет груз по j-му маршруту; степень квалификации i-й лаборатории при работе над j-й научной темой. Следовательно, задача (19) эквивалентна исходной задаче (17).