КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Лекция 13. Дискретное программирование.
Постановка задачи дискретного программирования. Многиезадачи системного анализа, такие как распределение ресурсов, задачи сетевого планирования и управления, календарного планирования, описываются математическими моделями дискретного программирования. Рассмотрим общую задачу максимизации. Найти при условиях
(13.12) где D - некоторое множество R(n) Если множество D является конечным или счетным, то условие (13.12) - это условие дискретности, и данная задача является задачей дискретного программирования (ЗДП). Чаще всего условие дискретности разделено по отдельным переменным следующим образом:
где D - конечное (или счетное) множество. Если вводится ограничение х; - целые числа (j=l,2,..., n), то приходят к задачам целочисленного программирования (ЦП), которое является частным случаем дискретного программирования. В задачах дискретного программирования область допустимых решений является невыпуклой и несвязной. Поэтому отыскание решения таких задач сопряжено со значительными трудностями. В частности, невозможно применение стандартных приемов, используемых при замене дискретной задачи ее непрерывным аналогом, состоящих в дальнейшем округлении найденного решения до ближайшего целочисленного. Например, рассмотрим следующую ЗЛП: найти max (x1-3x2 +3х3) при условиях
где х1, х2, х3 ≥ 0, xj - целые числа (j = 1,2, 3). Игнорируя условие целочисленности, находим оптимальный план симплекс-методом: x1опт=1/2, x2=0,…,x2опт= . Проверка показывает, что никакое округление компонент этого плана не дает допустимого решения, удовлетворяющего ограничениям этой задачи. Искомое целочисленное решение задачи x 1пт =2, x 2опт = 0, x 3опт = 5.
Таким образом, для решения задачи дискретного программирования (ЗДП) необходимы специальные методы. Методы решения ЗДП по принципу подхода к проблеме делят на три группы: 1) методы отсечения или отсекающих плоскостей; 2) метод ветвей и границ; 3) методы случайного поиска и эвристические методы. Математические модели задач дискретного программирования. По структуре математической модели задачи дискретного программирования разделяют на следующие классы: 1) задачи с неделимостями; 2) экстремальные комбинаторные задачи; 3) задачи на несвязных и на невыпуклых плоскостях; 4) задачи с разрывными целевыми функциями. Рассмотрим существо некоторых из них. Задачи с неделимостями. Математические модели задач с неделимостями основаны на требовании целочисленности переменных { xi}, вытекающем из физических условий практических задач. К таким задачам относится задача об определении оптимальной структуры производственной программы, где {х1, х2,..., хп} - объемы выпуска продукции. Эта задача заключается в отыскании (13.13) при (13.14) (13.15) Если J =N = (1,2,..., n), то задача называется полностью целочисленной, в противном случае, если J≠N - частично целочисленной. Задача о ранце. Одной из наиболее распространенных задач целочисленного программирования является так называемая задача о ранце. Рассмотрим постановку данной задачи. Турист готовится к длительному переходу в горах. В рюкзаке он может нести груз, масса которого не более W. Этот груз может включать в себя п видов предметов, каждый предмет типа j, массой wj, j = 1,2,..., n. Для каждого вида предмета турист определяет его ценность Ej вовремя перехода. Задача заключается в определении количества предметов каждого типа, которые он должен положить в рюкзак, чтобы суммарная ценность снаряжения была максимальной. Обозначим через хj количество предметов j-го типа в рюкзаке. Тогда математическая модель задачи такова:
(13.16) при ограничениях xj -целое, i= 1,2,..., т. (13.17) Экстремальные комбинаторные задачи. В данных задачах необходимо найти экстремум некоторой целевой функции, заданной на конечном множестве, элементами которого служат перестановки из nсимволов (объектов). Одной из наиболее простых задач этого класса является задача о назначениях: найти такую перестановку (р1,р2,..., рn) из чисел 1,2,3,..., n, при которой обеспечен по всем перестановкам (р1,р2,..., рn). Каждая такая перестановка может быть представлена точкой в п2- мерном евклидовом пространстве или в виде матрицы Хп Вводим переменные: Хij = 1, если i -и механизм предназначен для j-й работы; хij = 0 — в противном случае. Очевидно, что должно выполняться условие (13.18) Данные ограничения означают, что один механизм может быть предназначен для выполнения только одной работы. Тогда задача будет состоять в определении таких чисел {хij}, при которых достигается минимум функционала min при ограничениях (13.18). Задача о коммивояжере. Имеется (n + 1) город. Задана матрица С = ||cij || расстояний между городами. Выезжая из исходного города Aij, коммивояжер должен побывать во всех остальных городах по одному разу и вернуться в город Аij. Требуется определить, в каком порядке следует объезжать города, чтобы суммарное пройденное расстояние было минимально. Введем переменные: Xij — 1, если коммивояжер переезжает из населенного пункта А, в Аj; хij - 0 - в противном случае. Математическая модель задачи имеет следующий вид: найти (13.19) при условиях ; (13.20) ; (13.21) , (13.22)
где ui, uj - произвольные целые и неотрицательные числа. Условие (13.20) означает, что коммивояжер выезжает из каждого города один раз, а условие (13.21)- что он въезжает один раз в каждый город. Если ограничить задачу только условиями (13.20) и (13.21), она будет эквивалентна задаче о назначениях, план которой не обязан быть цикличным. Иначе говоря, путь коммивояжера при этом можно представить как рад несвязанных подциклов, в то время как его путь в действительности состоит из одного цикла. Покажем, что для любого цикла, начинающегося в Aij можно найти ui удовлетворяющие условию (13.22). Пусть ui =p, если коммивояжер посещает город Аi на р- мэтапе. Отсюда следует, что
ui- иj ≤ п - 1 для всех i и j, и, таким образом, условие (13.22) выполняется при xij = 0. При хij = 1 условие (13.22) выполняется как строгое равенство: ui-uj+nxij=p-(p+ 1 )+n = n- 1.
Дата добавления: 2017-02-01; Просмотров: 248; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |