Нажав на кнопку "Скачать архив", вы скачаете нужный вам файл совершенно бесплатно.
Перед скачиванием данного файла вспомните о тех хороших рефератах, контрольных, курсовых, дипломных работах, статьях и других документах, которые лежат невостребованными в вашем компьютере. Это ваш труд, он должен участвовать в развитии общества и приносить пользу людям. Найдите эти работы и отправьте в базу знаний.
Мы и все студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будем вам очень благодарны.
Чтобы скачать архив с документом, в поле, расположенное ниже, впишите пятизначное число и нажмите кнопку "Скачать архив"
Подобные документы
Особенности метода ветвей и границ как одного из распространенных методов решения целочисленных задач. Декомпозиция задачи линейного программирования в алгоритме метода ветвей и границ. Графический, симплекс-метод решения задач линейного программирования.
курсовая работа , добавлен 05.03.2012
Постановка задачи о коммивояжере. Нахождение оптимального решения с применением метода ветвей и границ. Основной принцип этого метода, порядок его применения. Использование метода верхних оценок в процедуре построения дерева возможных вариантов.
курсовая работа , добавлен 01.10.2009
Сущность и описание симплекс-метода и улучшенного симплекс-метода (метода обратной матрицы), преимущества и недостатки их применения в линейном прогаммировании. Листинг и блок-схема программы на языке Turbo Pascal для решения математической задачи.
курсовая работа , добавлен 30.03.2009
Форма организации основного переменно-поточного производства. Особенности переналадки станков как задача динамического программирования. Общая характеристика алгоритма формирования метода ветвей и границ. Сущность понятия комбинаторная конфигурация.
курсовая работа , добавлен 20.12.2008
Постановка линейной целочисленной задачи. Метод отсекающих плоскостей. Дробный алгоритм решения полностью целочисленных задач. Эффективность отсечения Гомори. Сравнение вычислительных возможностей метода отсекающих плоскостей и метода ветвей и границ.
курсовая работа , добавлен 25.11.2011
Постановка и решение дискретных оптимизационных задач методом дискретного программирования и методом ветвей и границ на примере классической задачи коммивояжера. Этапы построения алгоритма ветвей и границ и его эффективность, построение дерева графов.
курсовая работа , добавлен 08.11.2009
Обзор задач, решаемых методом динамического программирования. Составление маршрута оптимальной длины. Перемножение цепочки матриц. Задача "Лестницы". Анализ необходимости использования специальных методов вероятностного динамического программирования.
курсовая работа , добавлен 28.06.2015
В основе метода ветвей и границ лежит идея последовательного разбиения множества допустимых решений на подмножества. На каждом шаге метода для элементов разбиения выполняется проверка для выяснения, содержит данное подмножество оптимальное решение или нет. Для этого вычисляется нижняя оценка целевой функции на данном подмножестве.
Если оценка снизу не меньше рекорда (наилучшего из найденных решений), то подмножество может больше не рассматриваться. Проверяемое подмножество может быть отброшено еще и в том случае, когда в нем удается найти наилучшее решение. Если значение целевой функции на найденном решении меньше рекорда, то происходит смена рекорда. По окончанию работы алгоритма рекорд является результатом его работы. Если удается отбросить все элементы разбиения, то рекорд - оптимальное решение задачи. В противном случае, из неотброшенных подмножеств выбирается наиболее перспективное (например, с наименьшим значением нижней оценки), и подвергается разбиению. Новые подмножества вновь подвергаются проверке и т.д. Вычисление нижней границы является важнейшим элементом данной схемы.
Для каждой конкретной задачи целочисленного программирования (другими словами, дискретной оптимизации) метод ветвей и границ реализуется по-своему. Есть много модификаций этого метода.
Рассмотрим реализацию метода ветвей и границ для задачи коммивояжёра и задачи о рюкзаке.
Рассмотрим алгоритм Литтла (методом ветвей и границ) для задачи коммивояжера. Идею можно сформулировать следующим образом. В каждой строке матрицы расстояний находится минимальный элемент и вычитается из всех элементов соответствующей строки. Получается матрица, приведенная по строкам. Аналогично приводится матрица по столбцам. Получается матрица, приведенная по строкам и столбцам. Суммируя при приведении минимальные элементы, получим константу приведения, которая будет нижней границей множества всех допустимых гамильтоновых контуров. После находятся степени нулей для приведенной матрицы (сумма минимальных элементов строки и столбца, соответствующих этому нулю) и выбирается дуга , для которой степень нулевого элемента достигает максимального значения. Множество всех гамильтоновых контуров разбивается на два подмножества, одно из которых содержит дугу , второе эту дугу не содержит. После этого приводятся полученные матрицы гамильтоновых контуров и сравниваются нижние границы подмножества гамильтоновых контуров с целью выбора для дальнейшего разбиения множества с меньшей нижней границей. Процесс разбиения множеств на подмножества сопровождается построением дерева ветвлений. Сравнивая длину гамильтонова контура с нижними границами оборванных ветвей, выбирается для дальнейшего ветвления подмножество с нижней границей, меньшей полученного контура, до тех пор, пока не получен маршрут с наименьшей длиной или не становится ясно, что такого маршрута не существует.
Пример.
Пусть в задаче коммивояжера задана следующая матрица стоимостей переездов
Находим в каждой строке матрицы минимальный элемент и вычитаем его из всех элементов соответствующей строки. Получим матрицу, приведенную по строкам, с элементами
.
Если в матрице , приведенной по строкам, окажутся столбцы, не содержащие нуля, то приводим ее по столбцам. Для этого в каждом столбце матрицы выбираем минимальный элемент , и вычитаем его из всех элементов соответствующего столбца. Получим матрицу
,
каждая строка и столбец, которой содержит хотя бы один нуль. Такая матрица называется приведенной по строкам и столбцам.
Суммируя элементы и , получим константу приведения:
.
Находим степени нулей для приведенной по строкам и столбцам матрицы. Для этого мысленно нули в матице заменяем на знак и находим сумму минимальных элементов строки и столбца, соответствующих этому нулю. Записываем ее в правом верхнем углу клетки:
.
Выбираем дугу , для которой степень нулевого элемента достигает максимального значения
Разбиваем множество всех допустимых маршрутов на два подмножества:
– подмножество, содержащее дугу ;
– подмножество, не содержащее дугу
Для вычисления оценки затрат для маршрутов, включающих дугу , вычеркиваем в матрице строку и столбец и заменяем симметричный элемент на знак . Приводим полученную матрицу и вычисляем сумму констант приведения .
Метод ветвей и границ
Метод ветвей и границ разработан Литлом, Мерти, Суини и Карелом. Рассмотрим основные идеи этого метода. Прежде всего, этот метод связан с некоторой общей схемой допущения и оценки альтернатив. Схема построения альтернативных предположений в общем виде может быть представлена, как это показано на рис. 3.9.
Вершины на рис. 3.9 соответствуют, как и ранее, состояниям задачи. Из каждой вершины выходит только два альтернативных направления, что, впрочем, не ограничивает общности рассмотрения. Направления отмечены буквами П с индексами. Идентификатор R(b i) есть некоторая числовая оценка, приписываемая вершине b i .
Вообще говоря, не имеется ограничений на глубину построения дерева, хотя ясно, что нужно стремиться к минимальной глубине. Этим, в частности, обосновывается выбор того или иного предположения П m: сначала следует стремиться доказать предположение, достоверность которого в наибольшей степени сомнительна, или наоборот, попытаться опровергнуть предположение, достоверность которого в наибольшей степени правдоподобна, т.е. действовать по принципу reductio ad absurdum, поскольку вероятность получения противоречия здесь наибольшая, это позволяет отсечь соответствующую альтернативу у ее "истоков", вместо того, чтобы строить новые альтернативные предположения.
Пусть ищется состояние b * , в котором R(b *) минимально. Допустим далее, что известно некоторое текущее решение b x с текущим рекордом R(b x) . Тогда ясно, что любое состояние b i , в котором наилучшее достижимое значение R(b i) ³ R(b x) , может быть удалено (соответствующая часть дерева поиска отмечена, как показано с помощью заштрихованной области на рис. 3.9).
Рассмотрим задачу коммивояжера в следующей частной постановке. Пусть дано множество N из 4 городов, соединенных дорогами. Будем интерпретировать N сетью, в которой вершины соответствуют городам, причем дугам, соединяющим вершины, приписаны веса с ij , учитывающие затраты на переход коммивояжера из города i в город j (рис. 3.10а).
Полагаем с ij ³ 0 и с ii = ¥ , причем необязательно, чтобы с ij = с ji . Будем кодировать задачу матрицей затрат С = [с ij ], показанной на рис. 3.10,б.В задаче коммивояжера требуется найти цикл с минимальной суммой затрат образующих его дуг, который обходит каждую вершину не более одного раза, за исключением одной вершины, из которой цикл "стартует" и в которой он же "заканчивается".
Рассмотрим решение этой задачи методом ветвей и границ. Решающими оказываются следующие два обстоятельства.
А1) Решению задачи коммивояжера соответствует выбор ровно одного элемента в каждой строке матрицы затрат С и ровно одного элемента в каждом столбце этой матрицы, причем сумма выбранных элементов минимальна и они образуют цикл. Последнее замечание существенно. Например, элементы (1, 2), (2, 3), (3, 1), (4, 4) не образуют цикл.
А2) Если из любой строки (столбца) вычесть (добавить) одну и ту же константу D , то результирующее значение С* суммарных затрат в оптимальном цикле Ц* уменьшится (увеличится) ровно на эту величину D .
Воспользуемся свойством А2. Выпишем минимальные элементы h j в каждом столбце j , после чего вычтем их из элементов соответствующих столбцов. Затем в полученной матрице выпишем минимальные элементы h i в строках i . Получим приведенную матрицу на рис. 2.11, а. Вычтем из каждой строки соответствующее значение h i (рис. 3.11, б).
Из матрицы на рис. 3.11, б легко устанавливается, что минимально возможное значение С* (которое обозначим ) вычисляется следующим образом
Теперь будем строить предположения для приведенной матрицы затрат на рис. 3.11, б.
Сделаем допущение, что дуга принадлежит Ц*; альтернативное допущение означает, что . Если дуга , то полагаем для дуги с 4,3 = ¥, а также удаляем из матрицы затрат на рис. 2.11, б строку 3 и столбец 4, что в итоге дает матрицу, показанную на рис. 2.12, а. Приведенная матрица изображена на рис.2.12, б.
Для матрицы на рис. 2.12,б находим . Таким образом, получаем, что длина оптимального цикла, содержащего дугу суть
|
В то же время длина цикла равна 5+2+3+2=12, следовательно, делаем вывод, что дуга не входит в оптимальный цикл. Полагаем с 3,4 = ¥ . Допустим теперь, что дуга . Проведя аналогичные выкладки устанавливаем, что минимальная суммарная величина затрат для цикла, содержащего дугу , составляет 13 единиц. Следовательно, это допущение также отбрасывается, т.к. оно не улучшает текущий рекорд. Полагаем с 1,4 = ¥. В результате в столбце 4 матрицы на рис. 3.10, б останется единственный допустимый элемент с 2,4 = 2 . Полагаем, . Это допущение позволяет удалить строку 2 и столбец 4. В результате получаем приведенную матрицу, изображенную на рис. 3.13, для которой Ц* равно 12. Допустим, что дуга Тогда автоматически следует, что дуга . Удалим строку 4 и столбец 3: получим приведенную матрицу, изображенную на рис. 3.14, из которой автоматически следует, что дуга . Таким образом, из исходного предположения о том, что дуга , устанавливаем следующий оптимальный цикл, не содержащий дуги : с суммарными затратами, равными 2 + 3 + 2 + 5 = 12. |
Ниже приведено условие задачи и текстовая часть решения. Все решение полностью, в формате doc в архиве, вы можете скачать. Некоторые символы могут не отображаться на странице, но документе word все отображается. Еще примеры работ по ЭМММ можно посмотреть
ПОСТАНОВКА ЗАДАЧИ
Издательское предприятие должно выполнить в течении недели (число дней m = 5) работу по набору текста с помощью работников n категорий (высокая, средняя, ниже средней, низкая). Требуются определить оптимальную численность работников по категориям, при которой обеспечивается выполнение работы с минимальным расходом фонда зарплаты при заданных ограничениях. Исходные данные приведены в таблице 1 и 2.
Таблица 1
Таблица 2
Задача должна решаться методом целочисленного линейного программирования в Mathcad 2000/2001.
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
РЕШЕНИЯ
ЗАДАЧИ
Для расчета оптимальной численности работников, при которой обеспечивается минимум расхода фонда зарплаты, составляется математическая модель целочисленного линейного программирования, так как численность работников не может быть дробной величиной.
Решение задачи целочисленного программирования выполняется в два этапа.
На первом этапе выполняется задача линейного программирования без учета целочисленности.
На втором этапе производится пошаговый процесс замены нецелочисленных переменных ближайшими верхними или нижними целыми значениями.
Сначала решается, задача без учета условия целочисленности.
Целевая функция определяется по формуле:
где Q - общий фонд зарплаты на выполнение работы;
x 1 , x 2 , …, x n - численность работников по категориям;
n - число категорий работников;
c 1 , c 2 ,…, c n - дневная тарифная ставка одного работника по категориям;
m - число рабочих дней в неделю, m = 5.
Целевую функцию можно записать в векторной форме:
При решении задачи должны выполняться следующие ограничения. Ограничение сверху
x ≤ d (1)
задает максимальную численность работников по категориям, где d —вектор, определяющий численность по категориям.
В ограничении
учтено, что общая численность работников не должна превышать k max .
В ограничении снизу
р × х≥Р (3)
отражается, что все работники вместе должны выполнить заданный объем работ Р .
В качестве последнего ограничения записывается условие неотрицательности вектора переменных
x ≥0 (4)
Математическая модель решения задачи без учета условия целочисленности включает следующие выражения:
x ≤ d
р × х≥Р ,
x ≥ 0 .
Модель целочисленного программирования должна включать выражения (5), а также дополнительные ограничения, с помощью которых нецелочисленные переменные х заменяются целочисленными значениями. Конкретные выражения модели с целочисленными переменными рассмотрены в следующем подразделе.
РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ В MATHCAD
Исходные данные для примера даны в табл. 1 и 2.
Для решения задачи используется пакет Mathcad с функцией Minimize. Данная функция определяет вектор решения задачи:
х := Minimize (Q , x ),
где Q — выражение целевой функции, определяющей минимальный фонд зарплаты, х - вектор переменных.
Сначала задача решается без учета условия целочисленности. Это решение приведено в Приложении 1. В первой строке введены нулевые начальные значения вектора х и целевая функция Q (x ) . После слова Given и перед функцией Minimize указаны ограничения. В результате получена нецелочисленная оптимальная численность по категориям:
х =
с фондом зарплаты Q = 135 у. е.
Из данного решения находится целочисленное решение методом ветвей и границ.
Сначала в полученном решении анализируется дробная величина х 4 =
= 1,143. Для нее можно задать два целочисленных значения: х 4 = 1 и х 4 = 2. Начинается построение дерева решений (Приложение 2). На дереве решений откладывается начальный нулевой узел. Затем он соединяется первым узлом х 4 , и из этого узла проводятся две ветви, соответствующие ограничениям: х 4 = 1 и х 4 = 2.
Для ветви с ограничением х 4 = 1 решается задача линейного программирования, данная в Приложении 1, с учетом этого ограничения.
В результате получено решение этой задачи. Переменная х 1 стала целочисленная, но переменная х 2 стала дробной х 2 = 0,9.
Для продолжения ветви создается узел х 3 и ветвь х 3 = 1. Снова выполняется задача линейного программирования со всеми тремя ограничениями: x 4 = 1, х 2 = 1, х 3 = 1. С этими ограничениями задача имеет решение х Т =
= (1,938 1 1 1).
Для продолжения ветви создается узел х 1 и ветвь х 1 = 2. Снова выполняется задача линейного программирования со всеми тремя ограничениями: x 4 = 1, х 2 = 1, х 3 = 1, х 1 = 2. С этими ограничениями задача имеет решение х Т = = (2 1 1 1).
Процесс построения дерева решении и выполнение задачи линейного программирования повторяется, пока не будут построены все ветви.
В Приложении 2 приводится полное дерево возможных целочисленных решений, из которого следуют, что в задаче имеется 4 результативных решения.
Из результативных выбирается наилучшее и оно принимается как оптимальное целочисленное решение всей задачи с минимальной величиной Q (x ) . В нашем случае мы имеем два оптимальных целочисленных решения
Q (х) = 140,
x T = (2 1 1 1),
x T = (1 1 2 2).
Следовательно, издательская организация должна привлечь для набора текста двух работников высокой категории, одного работника средней категории, одного работника ниже средней категории и одного работника низкой категории. Возможен так же другой равнозначный вариант привлечения работников: один работник высокой категории, один работник средней категории, два работника категории ниже средней и два работника низкой категории. В обоих вариантах затраты будут минимальными и составят 140 ден. ед.
Скачать решение задачи:
Имя файла: 2.rar
Размер файла: 24.99 Kb
Если закачивание файла не начнется через 10 сек, кликните
Введение
При рассмотрении целого ряда задач, необходимо учитывать требование целочисленности используемых переменных. Методы решения задач линейного программирования не гарантируют целочисленности решения.
Иногда задачи целочисленного линейного программирования решают приближенно. Для этого решают задачу без учета целочисленности переменных, затем в полученном оптимальном решении округляют результаты до ближайших целых значений. Использование таких решений допустимо в тех ситуациях, где значения переменных достаточно велики, и погрешностью округления можно пренебречь. Если значения переменных невелики, то округление может привести к значительному расхождению с оптимальным решением.
Одним из широко распространенных методов решения целочисленных задач является метод ветвей и границ, впервые, он был предложен Ленд и Дойг в 1960 г.
ветвь граница линейное программирование
Метод ветвей и границ
Алгоритм метода ветвей и границ предусматривает декомпозицию исходной задачи линейного программирования (ЗЛП) на последовательность задач, содержащих дополнительные ограничения на переменные, которые затем оптимизируются.
1. Процесс начинают с решения задачи симплексным или графическим методом без учета требования на целочисленность переменных. Эту задачу называют ЗЛП-0. Если все переменные оптимального плана целые, то этот план также является оптимальными для задач целочисленного программирования.
2. Если некоторая переменная, не получила целочисленного значения, то производится ветвление на две новые задачи ЗЛП-1, ЗЛП-2. Одна из задач ЗЛП-1 представляет собой задачу ЗЛП-0, дополненную ограничением где - целая часть числа. Вторая образуется путем добавления к задаче ЗЛП-0 ограничения. Следует отметить, что выбор целочисленной переменной может быть произвольным определяться следующим образом:
по возрастанию или убыванию индексов;
переменная представляет важное решение принимаемое в рамках данной задачи;
коэффициент в целевой функции при этой переменной существенно превосходит все остальные.
3. Задачи ЗЛП-1 и ЗЛП-2 решаются самостоятельно. Ветвь оканчивается, если область допустимых решений пуста, либо её оптимальное решение полностью целочисленное. В противном случае возникает необходимость ветвления с п.2, обозначая следующие номера задач ЗЛП в естественном порядке ЗЛП-3, ЗЛП-4.
Процесс решения можно представить в виде дерева, в котором вершина ЗЛП-0 отвечает начальному плану решения задачи, а каждая из соединенных с ней ветвью вершин отвечает оптимальному плану следующей задачи.
Рассмотрим следующий пример. Максимизировать целевую функцию
при ограничениях
Воспользуемся графическим методом решения задачи линейного программирования.
1. Решим исходную задачу без учета требования целочисленности переменных.
Обозначим эту задачу линейного программирования ЗЛП-0.
На рисунке 1.1 штриховкой выделен многоугольник решений данной задачи. Максимальное значение достигается в точке Решение не является целочисленным.
Следующий шаг метода ветвей и границ состоит в ветвлении по одной из целочисленных переменных, имеющих дробное значение, например. Для этого добавим к задаче ЗЛП-0 два новых ограничения и Этими ограничениями удаляется интервал = в котором нет целых значений. Таким образом, в процессе ветвления создаются две новые задачи ЗЛП-1 и ЗЛП-2.
Рисунок 1.1 Решение задачи ЗЛП-0
2. Решим задачу ЗЛП-1 графически.
На рисунке 1.2 изображена допустимая область задачи ЗЛП-1. Максимальное значение достигается в точке. Решение задачи нецелочисленное.
Рисунок 1.2 Решение задачи ЗЛП-1
3. Решим задачу ЗЛП-2 графически.
В данном случае множество допустимых решений пусто (рисунок 1.2). Система ограничений несовместна, и задачу ЗЛП-2 можно исключить из дальнейшего рассмотрения.
Рисунок 1.3 Решение задачи ЗЛП-2
Теперь продолжим исследование задачи ЗЛП-1, поскольку значение нецелое. Произведем еще одно ветвление, путем введения ограничений и. В результате получаем две новые задачи ЗЛП-3 и ЗЛП-4.
