Методы решения задач дискретного программирования

Скачать файл - Методы решения задач дискретного программирования

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны. Дискретное программирование сформировалось как самостоятельная и важная часть математического программирования в конце х годов. В терминах дискретного программирования формулируются многие важные задачи экономики, управления, планирования, военного дела, биологии и т. Кроме того, к задачам дискретного программирования удается свести ряд экстремальных комбинаторных задач. По мнению автора, дискретное программирование является интересным и перспективным разделом математического программирования. Именно поэтому объектом настоящего исследования являются задачи дискретного программирования. Встают закономерные вопросы, в чем особенность данных задач, в чем прикладное значение их и какие существуют методы решения в дискретном программировании. Чтобы ответить на поставленные вопросы, в данной работе решены следующие задачи: Во-вторых, приводится их классификация. В- третьих, рассматриваются методы решения дискретных задач. Настоящая работа опирается прежде всего на работы авторитетных ученых, работающих в данной область Сигал И. В процессе работы привлекались данные сайтов в сети Интернет. Данная работа состоит из введения , 2 глав, заключения и списка литературы. В 1 главе приводятся теоритические данные, а именно, особенности задач дискретного программирования, классификация и методы решения. Рассмотрим задачу линейного программирования. Среди задач рассматриваемого класса выделяются задачи с булевыми переменными. Сначала введем понятие регулярности задачи. Регулярные задачи - это задачи, в которых выполняются следующие условия. На основе этих условий локальный оптимум целевой функции F x на множестве G может быть найден при помощи некоторого конечного или бесконечного сходящегося процесса. К задачам, не являющимся регулярными, относятся, в частности, так называемые многоэкстремальные задачи, т. К классу нерегулярных задач относятся дискретные задачи, в которых множество G не является связным и выпуклым например, множество G может быть конечным или счетным, либо декартовым произведением конечных или счетных множеств. В задачах регулярного математического программирования значительная часть методов основана на следующем исходном положении: В задачах дискретной оптимизации это положение не имеет места. Если в этом классе задач удается ввести естественным образом понятие окрестности, то близкие точки из этой окрестности могут сколь угодно значительно отличаться по значениям функции. В некоторых задачах дискретной оптимизации не удается естественным образом ввести понятие окрестности, оно вводится с помощью искусственных построений. Трудности нахождения допустимого целочисленного плана в задаче. Предположим, что рассматривается задача частично целочисленного линейного программирования общего вида. Вопрос о существовании допустимого решения сводится к выяснению, разрешима ли система линейных равенств и неравенств в целых неотрицательных числах. Известно, что это трудоемкая вычислительная задача из класса NP. Поэтому в общей задаче рассматриваемого класса поиск допустимого решения может оказаться столь же трудоемким, как и поиск оптимального решения. Идея -перебора для задач с конечным множеством допустимых решений также оказывается. Отсюда вытекает еще одна особенность задач дискретного программирования, а именно:. По структуре математической модели задачи дискретного программирования разделяют на следующие основные классы:. В этих задачах переменные х1, Математическая модель этой задачи имеет следующий вид:. Имеется ранец рюкзак , грузоподъемность которого есть R, при этом? Необходимо положить в ранец набор предметов с максимальной суммарной ценностью. После введения этих переменных суммарная ценность и грузоподъемность соответственно имеют вид. Вместе с задачей 1 - 3 будем рассматривать задачу линейного программирования, в которой вместо условий 3 вводятся условия. В этой задаче каждый предмет имеет т свойств кроме ценности. Вместе с задачей 4 - 6 будем рассматривать задачу линейного программирования, в которой вместо условий 6 вводятся условия. Экономическая интерпретация задачи о ранцах. Требуется выбрать для реализации набор проектов с максимальной суммарной прибылью. Введем п булевых переменных:. Одной из наиболее простых задач этого класса является известная задача о назначениях. То есть ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задача о назначениях является частным случаем транспортной задачи. Эта задача относится к классу экстремальных комбинаторных задач на графах. Рассмотрим типичную задачу о покрытии. Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения: Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого в матрице как бы вычеркивается диагональ. Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат. N - матрица затрат, где Ci j - затраты на переход из i- го города в j-й. Многие экономические системы характеризуются наличием так называемых постоянных затрат, которые должны быть произведены независимо от объема производства. Учет в моделях этих и подобных факторов приводит к появлению в них целевых функций, не обладающих свойством непрерывности. Обозначим через xij объемы перевозок из пункта i в пункт j. Следовательно, задача 19 эквивалентна исходной задаче Задача 19 является задачей частично-целочисленного программирования. Перечисленные примеры далеко не исчерпывают всего многообразия задач дискретного программирования. Далее мы рассмотрим методы решения дискретных задач. Методы решения задач дискретного программирования можно разделить на следующие классы:. Алгоритмы методов отсечения разработаны для решения полностью или частично целочисленных и дискретных задач линейного программирования. Общая схема методов отсечения заключается в переходе от решения задачи целочисленного дискретного линейного программирования к решению последовательности задач линейного программирования. Первая задача последовательности получается из исходной снятием требования целочисленности дискретности. Правильные отсечения - отсечение дополнительное ограничение , которое удовлетворяют следующим требованиям:. Общая формула построения правильного отсечения для всех алгоритмов запишется в следующем виде:. Другими словами, даже к искусственным переменным предъявляется требование целочисленности. Решим исходную задачу без условия целочисленности Симплекс-методом. Если все базисные компоненты оптимального плана решаемой задачи целые, то найденное решение есть оптимальное решение исходной задачи. Если некоторая компонента -. Гомори предложено делать каждый раз дополнительное ограничение для нецелой переменной с наибольшей дробной частью. Итак, задача с отброшенным условием целочисленности решена. Добавляем полученное дополнительное условие к задаче из п. Решаем полученную задачу С-методом. Пусть множество оптимальных планов задачи, полученной из исходной отбрасыванием условий целочисленности, ограничено, и выполняются следующие условия:. В задачах, решаемых алгоритмом Дальтона-Ллевилина, область допустимых значений задается следующим образом. Для того, чтобы при вводе правильных отсечений ограничить размеры симплекс-таблицы, Гомори предложил после решения очередной задачи ЛП вычеркивать из таблицы переменную, по которой построено правильное ограничение. Известно, что с увеличением размерности задачи эффективность методов отсечения значительно снижается. Решение может быть не получено, в частности, из-за недостаточной точности вычисления коэффициентов. Основная идея методов этого класса заключается в использовании конечности множества допустимых решений и замене полного их перебора сокращенным направленным перебором. Таким образом, главную роль в сокращении перебора играют оценка и отбрасывание подмножеств, заведомо не содержащих оптимальных решений. Эта идея реализуется путем последовательного разбиения множества всех допустимых решений на подмножества. При этом среди подмножеств, последовательно порождаемых на каждом шаге процесса, могут обнаружиться как подмножества, не содержащие допустимых решений, так и подмножества, не содержащие оптимальных решений. Отбрасывание таких подмножеств позволяет заменить полный перебор частичным и тем самым делает реализуемым вычислительный процесс. Подмножество, которое не может быть отсеяно, подвергается дальнейшему разбиению. Комбинаторные методы различаются способом разбиения и способом оценивания, эти способы обычно связаны со спецификой решаемых классов задач. Правила, в соответствии с которыми производится отсев подмножеств, заведомо не содержащих оптимальных решений, называются правилами отсева. Суть метода заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов. Метод ветвей и границ состоит в следующем: Процесс продолжается до тех пор, пока не получено оптимальное целочисленное решение исходной задачи. Первоначально находим, к примеру, симплекс-методом оптимальный план задачи без учета целочисленности переменных. Пусть им является план X0. Если же среди компонент плана X0 имеются дробные числа, то X0 не удовлетворяет условию целочисленности и необходимо осуществить упорядоченный переход к новым планам, пока не будет найдено решение задачи. Предполагая, что найденный оптимальный план X0 не удовлетворяет условию целочисленности переменных, тем самым считаем, что среди его компонент есть дробные числа. Пусть, например, переменная приняла xi в плане X0 дробное значение. Определяя эти числа, находим симплекс-методом решение двух задач линейного программирования:. Найдем решение задач линейного программирования 20 и Очевидно, здесь возможен один из следующих четырех случаев:. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам 20 и Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и он вместе со значением целевой функции на нем дает искомое решение. Если же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные 20 и Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные 20 и Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х0 исходной задачи, а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач 20 и Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным. Итак, процесс нахождения решения задачи целочисленного программирования методом ветвей и границ включает следующие основные этапы:. Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане задачи является дробным числом. Находят решение задач 20 и 21 , которые получаются из задачи в результате присоединения дополнительных ограничений. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам 20 и 21 , и находят их решение. Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах. Вычислительная реализация комбинаторных алгоритмов зачастую весьма трудоемка и является препятствием применения методов для решения практических задач. Можно отметить два подхода к повышению вычислительной эффективности комбинаторных алгоритмов:. Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных переход к канонической форме. Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент. Разрешающий элемент равен 3 и находится на пересечении ведущего столбца и ведущей строки. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент. Разрешающий элемент равен 1 и находится на пересечении ведущего столбца и ведущей строки. План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец. Оптимальный целочисленный план можно записать так:. Методом ветвей и границ найти решение задачи, состоящей в определении максимального значения функции. Находим решение сформулированной задачи симплексным методом без учета условия целочисленности переменных. Так как в плане Х0 значения трех переменных являются дробными числами, то Х0 не удовлетворяет условию целочисленности, и следовательно, не является оптимальным планом исходной задачи. Возьмем какую-нибудь переменную, значение которой является дробным числом, например х1. Тогда эта переменная в оптимальном плане исходной задачи будет принимать значение, либо меньшее или равное трём: Так как среди компонент оптимального плана этой задачи есть дробные числа, то для одной из переменных, например x2, вводим дополнительные ограничения:. При этом плане целевая функция принимает максимальное значение. Схему реализованного выше вычислительного процесса можно представить в виде дерева, ветвями которого являются соответствующие ограничения на переменные, а вершинами - решения соответствующих задач линейного программирования. Задача III имеет оптимальный план 3, 1, 2, 3, 3 а задача IV неразрешима. Экстремальные комбинаторные задачи Задача о назначениях, задача коммивояжёра, Задача о покрытии. Были рассмотрены методы решения задач более подробно автор остановился на алгоритме Гомори и методе ветвей и границ, также были решены задачи этими способами. Итак, дискретное программирование очень важная часть оптимального программирования, которая имеет широкое практическое применение и заслуживает глубокого изучения. Введение в прикладное дискретное программирование. Постановка и решение дискретных оптимизационных задач методом дискретного программирования и методом ветвей и границ на примере классической задачи коммивояжера. Этапы построения алгоритма ветвей и границ и его эффективность, построение дерева графов. Модель дискретного программирования как способ нахождения максимума целевой функции на множестве. Коды на языках Java и C для решения заданий с неделимостями. Применение методов итерации Гомори и 'ветвей и границ'. Описание решения комбинаторных задач. Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования. Реализация алгоритма Гомори на языке программирования Object Pascal при использовании среды разработки Borland Delphi 7. Рассмотрение основных способов компьютерного осуществления решения задач целочисленного программирования симплексным методом. Алгоритм решения задач линейного программирования симплекс-методом. Построение математической модели задачи линейного программирования. Решение задачи линейного программирования в Excel. Нахождение прибыли и оптимального плана выпуска продукции. Решение задачи линейного программирования симплекс-методом: Решение транспортной задачи методом потенциалов: Постановка задачи линейного программирования и формы ее записи. Понятие и методика нахождения оптимального решения. Порядок приведения задач к каноническому виду. Механизмы решения задач линейного программирования аналитическим и графическим способами. Постановка задач линейного программирования. Примеры экономических задач, сводящихся к задачам линейного программирования. Допустимые и оптимальные решения. Алгоритм Флойда — алгоритм для нахождения кратчайших путей между любыми двумя узлами сети. Постановка линейной целочисленной задачи. Дробный алгоритм решения полностью целочисленных задач. Сравнение вычислительных возможностей метода отсекающих плоскостей и метода ветвей и границ. Практические навыки моделирования задач линейного программирования и их решения графическим и симплекс-методом с использованием прикладной программы SIMC. Моделирование транспортных задач и их решение методом потенциалов с помощью программы TRAN2. Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т. PPT, PPTX и PDF-файлы представлены только в архивах. Главная База знаний 'Allbest' Программирование, компьютеры и кибернетика Обзор задач дискретного программирования. Предмет, постановка и особенности задач дискретного программирования. Задачи с неделимостями и с разрывными целевыми функциями. Примеры решений задач дискретного программирования методом ветвей и границ, методом Гомори. Обзор и методы решений задач дискретного программирования 1. Примеры решений задач дискретного программирования 2. Рассмотрим особенности задач дискретного программирования. Трудности при определении окрестности: Отсюда вытекает еще одна особенность задач дискретного программирования, а именно: Невозможность большого перебора на ЭВМ. Рассмотрим некоторые из них. Математическая модель этой задачи имеет следующий вид: Задача об одномерном ранце. После введения этих переменных суммарная ценность и грузоподъемность соответственно имеют вид f x1,x2, Эта задача имеет вид f x1,x2, Введем п булевых переменных: Получим задачу о многомерном ранце 4 - 6. Исходные параметры модели задачи о назначениях 1. L X - общая суммарная характеристика качества распределения ресурсов по работам. Математическая модель задачи N - число городов. Xi j - матрица переходов с компонентами: Методы решения задач дискретного программирования можно разделить на следующие классы: Рассмотрим каждый класс в отдельности. Каждая последующая k-ая задача получается из предыдущей k-1 -ой путем добавления к условиям, определяющим область допустимых решений k-1 -ой задачи, еще одного ограничения, называемого правильным отсечением. При положительном ответе итерационный процесс решения задач из последовательности прекращается - полученное оптимальное решение задачи ЛП является и решением исходной задачи. Решение каждой k-ой задачи ЛП называется k-ой большой итерацией. Доказывается, что при выполнении определенных условий решение исходной задачи будет получено через конечное число итераций. Если задачи ЛП не имеют решения, не имеет решения и исходная задача. Основным понятием метода является термин правильное отсечение: Правильные отсечения - отсечение дополнительное ограничение , которое удовлетворяют следующим требованиям: Общая формула построения правильного отсечения для всех алгоритмов запишется в следующем виде: Известны три алгоритма отсечения: Алгоритм Дальтона-Ллевилина решения дискретной задачи ЛП. Скажем пару слов о каждом приведённом алгоритме. Если некоторая компонента - нецелая, то переходим к п. Выразим базисную переменную xi в виде суммы целой и дробной частей. Теорема о конечности первого алгоритма Гомори Пусть множество оптимальных планов задачи, полученной из исходной отбрасыванием условий целочисленности, ограничено, и выполняются следующие условия: Тогда первый алгоритм Гомори требует конечного числа больших итераций. Пример применение первого алгоритма Гомори будет рассмотрено в главе 2. В задачах, решаемых алгоритмом Дальтона-Ллевилина, область допустимых значений задается следующим образом xj? Таким образом, комбинаторные методы основаны на двух элементах: Среди комбинаторных методов выделяют: Остановимся подробнее на самом распространённом из них, на методе ветвей и границ. МЕТОД ВЕТВЕЙ И ГРАНИЦ Суть метода заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов. Алгоритм действия метода ветвей и границ Первоначально находим, к примеру, симплекс-методом оптимальный план задачи без учета целочисленности переменных. Определяя эти числа, находим симплекс-методом решение двух задач линейного программирования: Очевидно, здесь возможен один из следующих четырех случаев: Итак, процесс нахождения решения задачи целочисленного программирования методом ветвей и границ включает следующие основные этапы: Находят решение задачи линейного программирования. Пример решения задачи данным методом разберем в главе 2. Можно отметить два подхода к повышению вычислительной эффективности комбинаторных алгоритмов: Возможные классификации приближенных методов Классификация А. Решим задачу без учета целочисленности. Следовательно, 1-ая строка является ведущей. Следовательно, 2-ая строка является ведущей. В полученном оптимальном плане присутствуют дробные числа. Оптимальный целочисленный план можно записать так: Рассмотрим две задачи линейного программирования: Так как среди компонент оптимального плана этой задачи есть дробные числа, то для одной из переменных, например x2, вводим дополнительные ограничения: Рассмотрим теперь следующие две задачи: Задачи этого класса обладают следующими особенностями: Трудности при определении окрестности, 3. Трудности нахождения допустимого целочисленного плана в задаче, 4. Также была приведена классификация задач: Задачи с неделимостями, к которым относятся задача о ранце 2. Экстремальные комбинаторные задачи Задача о назначениях, задача коммивояжёра, Задача о покрытии 3. Задачи с разрывными целевыми функциями; 4. Задачи на невыпуклых и несвязных областях. Введение в дискретную математику. Метод программирования и схем ветвей в процессах решения задач дискретной оптимизации. Метод ветвей и границ. Реализация целочисленного программирования метод Гомори. Решение задачи линейного программирования симплекс-методом. Методика решения задач линейного программирования. Практикум по решению линейных задач математического программирования. Решение целочисленной задачи линейного программирования. Решение задач линейного программирования различными методами. Другие документы, подобные 'Обзор задач дискретного программирования'.