Excel метод ветвей и границ
Издательское предприятие должно выполнить в течении недели (число дней m = 5) работу по набору текста с помощью работников n категорий (в ы сокая, средняя, ниже средней, низкая). Требуются определить оптимальную численность работников по категориям, при которой обеспечивается выпо л нение работы с минимальным расходом фонда зарплаты при заданных огр а ничениях. Исходные данные приведены в таблице 1 и 2.
Исхо д ные данные
Минимальный общий объём выполнения работ в неделю, у.е.
Максимальная допустимая численность работников всех к а тегорий, чел.
Данные по категориям раб о тающих
Коэффициенты целевой функции (дне в ная тарифная ставка по категориям, у.е.)
Объём работ, выполняемый одним р а ботником в неделю, у.е.
Максимальная численность по катег о риям, чел.
Задача должна решаться методом целочисленного линейного програ м мирования в Mathcad 2000/2001.
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
РЕШЕНИЯ З А ДАЧИ
Для расчета оптимальной численности работников, при которой обе с печивается минимум расхода фонда зарплаты, составляется математическая модель целочисленного линейного программирования, так как численность работников не может быть дробной величиной.
Решение задачи целочисленного программирования выполняется в два этапа.
На первом этапе выполняется задача линейного программирования без учета целочисленности.
На втором этапе производится пошаговый процесс замены нецел о численных переменных ближайшими верхними или нижними целыми зн а чени я ми.
Сначала решается, задача без учета условия целочисленности.
Целевая функция определяется по формуле :
,
г де Q – общий фонд зарплаты на выполнение работы;
x 1 , x 2 , …, x n – численность работников по категориям;
n – число категорий работников;
c 1 , c 2 ,…, c n – дневная тарифная ставка одного работника по кат е гориям;
m – число рабочих дней в неделю, m = 5.
Целевую функцию можно записать в векторной форме :
При решении задачи должны выполняться следующие ограничения. Ограничение сверху
зада е т максимальную численность работников по категориям, где d — вектор, определяющий численность по категориям.
( 2 )
учтено, что общая численность работников не должна превышать k max .
В ограничении снизу
отражается, что все работники вместе должны выполнить заданный объем работ Р .
В качестве последнего ограничения записывается условие неотриц а тельности вектора переменных
Математическ ая модель решения задачи без учета условия целочи с ленности включает следующие выражения:
, ( 5 )
Модель целочисленного программирования должна включать выраж е ния ( 5 ), а также дополнительные ограничения, с помощью которых нецел о численные переменные х заменяются целочисленными значениями. Ко н кретные выражения модели с целочисленными переменными рассмотрены в следующем подразделе.
РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ В MATHCAD
Исходные данные для примера даны в табл. 1 и 2 .
Для решения задачи используется пакет Mathcad с функцией Minimize . Данная функция определяет вектор решения задачи:
х := Minimize ( Q , x ) ,
где Q — выражение целевой функции, определяющей минимальный фонд зарплаты, х – вектор переменных.
Сначала задача решается без учета условия целочисленно сти. Это р е шение приведено в П риложении 1. В первой строке введены нулевые начальные значения вектора х и целевая функция Q ( x ) . После слова Given и перед функцией Minimize указаны ограничения. В результате получена нец е лочисленная оптимальная численность по категориям:
х = [ 2 ; 0; 2 ; 1 ,143 ]
с фондом зарплаты Q = 1 35 у. е.
Из данного решения находится целочисленное решение методом ве т вей и границ.
Сначала в полученном решении анализируется дробная величина х 4 =
= 1,143 . Для нее можно задать два целочисленных значения: х 4 = 1 и х 4 = 2 . Н а чинае тся построение дерева решений (П риложение 2). На дереве решений откладывается начальный нулевой узел. Затем он соединяется первым узлом х 4 , и из этого узла проводятся две ветви, соответствующие ограничениям: х 4 = 1 и х 4 = 2 .
Для ветви с ограничением х 4 = 1 решается задача линейного про гра м мирования, данная в П риложении 1, с учетом этого ограничения .
В результате получено решение этой задачи. Переменная х 1 стала цел о численная, но переменная х 2 стала дробной х 2 = 0,9 .
Далее продолжается построение первой ветви. Из узла х 2 проводится ветвь для х 2 = 1 и с этим ограничением решается задача линейного програ м мирования. Получается решение х Т = ( 2 1 0,875 1 ).
Для продолжения ветви создается узел х 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 ) . В нашем случае мы имеем два оптимальных целочисленных решения
Ветвь, содержащая оптимальное решение, показана на дереве реш е ний . Оптимальное целочисленное решение задачи определения чис ле нности р а ботников приводится в П риложении 1.
Следовательно, издательская организация должна привлечь для набора текста двух работников высокой категории, одного работника средней кат е гории, одного работника ниже средней категории и одного работника низкой категории. Возможен так же другой равнозначный вариант привлечения р а ботников: один работник высокой категории, один работник средней катег о рии , два работника категории ниже средней и два работника низкой катег о рии. В обоих в а риантах затраты будут минимальными и составят 140 ден. ед.
Здравствуй, Хабр! Реализовывая различные алгоритмы для нахождения гамильтонова цикла с наименьшей стоимостью, я наткнулся на публикацию, предлагающую свой вариант. Попробовав в деле, я получил неправильный ответ:
Дальнейшие поиски в Интернете не принесли ожидаемого результата: либо сложное для не-математиков теоретическое описание, либо понятное, но с ошибками.
Под катом вас будет ждать исправленный алгоритм и онлайн-калькулятор.
Сам метод, опубликованный Литтлом, Мерти, Суини, Кэрелом в 1963 г. применим ко многим NP-полным задачам, и представляет собой очень теоритеризованный материал, который без хороших знаний английского языка и математики сразу не применишь к нашей задаче коммивояжера.
Кратко о методе — это полный перебор всех возможных вариантов с отсеиванием явно неоптимальных решений.
Алгоритм состоит из двух этапов:
Первый этап
Приведение матрицы затрат и вычисление нижней оценки стоимости маршрута r.
1. Вычисляем наименьший элемент в каждой строке (константа приведения для строки)
2. Переходим к новой матрице затрат, вычитая из каждой строки ее константу приведения
3. Вычисляем наименьший элемент в каждом столбце (константа приведения для столбца)
4. Переходим к новой матрице затрат, вычитая из каждого столбца его константу приведения.
Как результат имеем матрицу затрат, в которой в каждой строчке и в каждом столбце имеется хотя бы один нулевой элемент.
5. Вычисляем границу на данном этапе как сумму констант приведения для столбцов и строк (данная граница будет являться стоимостью, меньше которой невозможно построить искомый маршрут)
Второй (основной) этап
1.Вычисление штрафа за неиспользование для каждого нулевого элемента приведенной матрицы затрат.
Штраф за неиспользование элемента с индексом (h,k) в матрице, означает, что это ребро не включается в наш маршрут, а значит минимальная стоимость «неиспользования» этого ребра равна сумме минимальных элементов в строке h и столбце k.
а) Ищем все нулевые элементы в приведенной матрице
б) Для каждого из них считаем его штраф за неиспользование.
в) Выбираем элемент, которому соответствует максимальный штраф (любой, если их несколько)
2. Теперь наше множество S разбиваем на множества — содержащие ребро с максимальным штрафом(Sw) и не содержащие это ребро(Sw/o).
3. Вычисление оценок затрат для маршрутов, входящих в каждое из этих множеств.
а) Для множества Sw/o все просто: раз мы не берем соответствующее ребро c максимальным штрафом(h,k), то для него оценка затрат равна оценки затрат множества S + штраф за неиспользование ребра (h,k)
б) При вычислении затрат для множества Sw примем во внимание, что раз ребро (h,k) входит в маршрут, то значит ребро (k,h) в маршрут входить не может, поэтому в матрице затрат пишем c(k,h)=infinity, а так как из пункта h мы «уже ушли», а в пункт k мы «уже пришли», то ни одно ребро, выходящее из h, и ни одно ребро, приходящее в k, уже использоваться не могут, поэтому вычеркиваем из матрицы затрат строку h и столбец k. После этого приводим матрицу, и тогда оценка затрат для Sw равна сумме оценки затрат для S и r(h,k), где r(h,k) — сумма констант приведения для измененной матрицы затрат.
4. Из всех неразбитых множеств выбирается то, которое имеет наименьшую оценку.
Так продолжаем, пока в матрице затрат не останется одна не вычеркнутая строка и один не вычеркнутый столбец.
Небольшая оптимизация — подключаем эвристику
Да, правда, почему бы нам не ввести эвристику? Ведь в алгоритме ветвей и границ мы фактически строим дерево, в узлах которого решаем брать ребро (h,k) или нет, и вешаем двух детей — Sw(h,k) и Sw/o(h,k). Но лучший вариант для следующей итерации выбираем только по оценке. Так давайте выбирать лучший не только по оценке, но и по глубине в дереве, т.к. чем глубже выбранный элемент, тем ближе он к концу подсчета. Тем самым мы сможем наконец дождаться ответа.
Теперь, собственно, об ошибках в той публикации
Ошибка была одна единственная — следует выбирать для разбиения множество с минимальной границей из всех возможных путей, а не из двух полученных в результате последнего разбиения детей.
Доказательство
А вот решение с исправленным алгоритмом:
Ответ: путь:3=>4=>2=>1=>5=>3 длина: 41
Как видите, включая ребро 5:2 в решение будет ошибкой. Что и требовалось доказать
График сравнения метода ветвей и границ и потраченного времени для случайной таблицы от 5х5 до 10х10:
График максимального и минимального потраченного времени для матриц от 5х5 до 66х66.
Попробовать с подробным решением можно тут.
данные измерений были получены по 100 случайным матрицам. не слишком хорошее число, но общее представление обеспечивает.
Исходники на GitHub (обновлены).
В большинстве экономико-математических моделей, сформулированных как задачи линейного программирования, часть или все компоненты вектора-решения должны выражаться в целых числах, т. е. быть целочисленными. К ним относятся, например, задачи, в которых переменные означают количество единиц неделимой продукции, число станков при закупке оборудования, количество домов при очередности строительства и т. д. [3, c. 180]
С другой стороны, это могут быть задачи, в которых при моделировании используются логические (булевы) переменные со значениями 1 и 0, что означает, например, взимать или не взимать арендную плату, создавать или не создавать дополнительный пункт производства и т. д. Покажем особенности фактора целочисленности на следующем примере, который в учебных целях генерируется на компьютере в виде индивидуальных заданий. Оптимальное решение в примере, в принципе, не может быть получено каким-либо округлением решения соответствующей задачи линейного программирования.
Для решения рассмотренного класса задач математического программирования, как правило, используется универсальный метод решения под названием «метод ветвей и границ». [2, с. 158]
Продемонстрируем основные идеи этого метода на примере решения задачи целочисленного линейного программирования (ЦЛП).
Эти задачи включают в себя требования целочисленности ко всем искомым переменным. Они относятся к классу задач полностью целочисленного линейного программирования (задача ЦЛП). В свою очередь, эти задачи являются частным случаем задачи частично целочисленного линейного программирования (ЧЦЛП). [2, с. 160]
При решении задач частично-целочисленного линейного программирования методом ветвей и границ на определенных этапах решаются вспомогательные задачи линейного программирования (ЛП), для которых применяется симплекс-метод.
Рассмотрим развернутую экономико-математическую модель задачи.
Система ограничений: 2x1 + x2 ≤ 9
Целевая функция: F = 27x1 + 21x2 → max
Решение задачи осуществляется симплексным методом [1, с. 176] с помощью сервисной функции MS Excel «Поиск решения».
Описание шагов алгоритма «метода ветвей и границ»
- Решение вспомогательной задачи линейного программирования.
Вспомогательная задача № 1 получается из данной задачи целочисленного линейного программирования путём игнорирования требования целочисленности. Решим задачу симплексным методом с помощью Excel. В результате получим: х1=2,3, х2=4,3, Fmax=154 (схема 1).
2.Очередное ветвление вспомогательной задачи на две вспомогательные подзадачи нижнего уровня.
Так как вышеполученное решение нецелочисленное, то оно дает верхнюю границу F = 154 для максимума целевой функции искомого оптимального решения исходной задачи.
В этом случае одна из переменных, имеющих дробное значение, в данном случае x1, берется за основу для разбиения (ветвления) данной вспомогательной задачи № 1 на вспомогательные подзадачи под номерами 1.1 и 1.2 по нижеприведенной методике:
F = 27x1+21x2 → max → F = 27x1+21x2 → max
При решении подзадачи 1.1. в Excel добавим ограничение х1 =3
В результате получим:
х1=3, х2=3, Fмах=144
Таким образом, получим первый целочисленный рекорд.
- Проверка оптимальности текущего целочисленного рекорда после очередного ветвления на основе формулировки критерия оптимальности текущего целочисленного рекорда по методу ветвей и границ:Текущий целочисленный рекорд объявляется оптимальным решением исходной задачи в том и только том случае, если при данном состоянии дерева решений на концах других ветвей не существует верхних границ, превосходящих значение рекорда.
В данном случае критерий не выполняется, так как 153,75 больше 144.
- Ветвление следует продолжить по подзадаче № 1.1, которая дает наибольшую на данный момент верхнюю границу из подзадач, находящихся на концах ветвей. В качестве основы для ветвления выбирается дробное значение переменной х2 = 4,75.
х1 =0, х2>=0х1>=0, х2>=0
F=27x1+21x2 → max → F=27x1+21x2 → max
При решении подзадачи 1.1.1. в Excel добавим ограничение х2 =5
В результате получим:
х1=1,8, х2=5, Fмах=153,6
153,6 — уточненная верхняя граница.
- Проверка оптимальности текущего целочисленного рекорда после очередного ветвления показывает, что критерий вновь не выполняется, так как 153,6 больше 138.
- Продолжаем ветвление по подзадаче 1. Рассмотрим подзадачу 1.3.В качестве основы для ветвления выбирается дробное значение переменной х2 =4,3.
F=27x1+21x2 → max → F=27x1+21x2→ max
При решении подзадачи 1.3. в Excel добавим ограничение х2 =5
В результате получим:
х1=1,8, х2=5, Fмах=153,6
В качестве основы для ветвления выбирается дробное значение переменной х1 = 1,8.
Так как 1 =5 х2>=2
х1 =0, х2>=0 → х1>=0, х2>=0
F=27x1+21x2 →max → F=27x1+21x2 → max
При решении подзадачи 1.4.2. — поиск не может найти подходящего решения.
При решении подзадачи 1.4.1. в Excel добавим ограничение х2
Похожие статьи
Решение интервальной задачи дробно-линейного.
Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования. Авторы: Немкова Елена Анатольевна, Левин Виталий Ильич. Рубрика: Математика.
Применение метода линейного программирования для.
Цель настоящей статьи — показать использование метода линейного программирования при решении текстовых задач по математике, предполагающих максимизацию (минимизацию) некоторой величины, например.
Решение многокритериальных задач линейного.
многокритериальная оптимизация, задача линейного программирования, метод последовательных уступок.
Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.
Приложения линейного программирования к решению.
Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel. К решению краевых задач пространственных стержней при переменных упруго-пластических нагружениях.
Некоторые прикладные задачи целочисленного.
Значительная часть экономических задач, относящихся к линейному программированию, требует целочисленного решения [1…6]. К ним, например, относятся задачи, в которых переменные означают количество единиц продукции.
Математические методы маршрутизации доставки светлых.
– целочисленное линейное программирование; – метод «ветвей и границ»; – методы локальной оптимизации
Методы целочисленного программирования впервые применили С. Миллер, А. Таккер и Р. Землин [2]. Метод основывается на том, что в задачах возникает.
Математическая модель управления обучением и её решение.
Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.
Применение методов нелинейного программирования к решению экстремальных геометрических задач.
Метод Гомори в решении целочисленной задачи оптимизации.
Целочисленное линейное программирование ориентировано на решение задач линейного программирования, в которых все или некоторые переменные принимают целочисленные значения [1, c. 136].
Решение интервальной задачи дробно-линейного.
Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования. Авторы: Немкова Елена Анатольевна, Левин Виталий Ильич. Рубрика: Математика.
Применение метода линейного программирования для.
Цель настоящей статьи — показать использование метода линейного программирования при решении текстовых задач по математике, предполагающих максимизацию (минимизацию) некоторой величины, например.
Решение многокритериальных задач линейного.
многокритериальная оптимизация, задача линейного программирования, метод последовательных уступок.
Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.
Приложения линейного программирования к решению.
Целочисленное решение задач линейного программирования методом ветвей и границ с помощью Excel. К решению краевых задач пространственных стержней при переменных упруго-пластических нагружениях.
Некоторые прикладные задачи целочисленного.
Значительная часть экономических задач, относящихся к линейному программированию, требует целочисленного решения [1…6]. К ним, например, относятся задачи, в которых переменные означают количество единиц продукции.
Математические методы маршрутизации доставки светлых.
– целочисленное линейное программирование; – метод «ветвей и границ»; – методы локальной оптимизации
Методы целочисленного программирования впервые применили С. Миллер, А. Таккер и Р. Землин [2]. Метод основывается на том, что в задачах возникает.
Математическая модель управления обучением и её решение.
Решение интервальной задачи дробно-линейного программирования сведением к задаче линейного программирования.
Применение методов нелинейного программирования к решению экстремальных геометрических задач.
Метод Гомори в решении целочисленной задачи оптимизации.
Целочисленное линейное программирование ориентировано на решение задач линейного программирования, в которых все или некоторые переменные принимают целочисленные значения [1, c. 136].
В статье автор рассматривает метод ветвей и границ, применяя его к решению задачи о коммивояжёре для нахождения наименьшего пути, а также проводит сравнение с методом грубого перебора.
Ключевые слова: минимальный путь, поиск пути, задача о коммивояжёре, метод ветвей и границ, грубый перебор, алгоритм
В современном мире оптимизация алгоритмов является очень важной проблемой, так как системы должны обрабатывать все большие данные за меньшее время. Одной из известных задач является задача коммивояжёра. Цели данной статьи — оптимизировать решение задачи о коммивояжёре с помощью метода ветвей и границ, разработать алгоритм решения для задачи на языке С++, оценить количество переборов при решении задачи стратегией с помощью грубой силы и с разработанным методом.
Формулировка задачи:
Есть N городов, соединённых между собой дорогами. Необходимо проложить между ними кратчайший замкнутый маршрут, проходящий через каждый город только один раз.
Расстояние из города j в город i считается неотрицательным числом: Dji ≥ 0. Часто Dji называют стоимостью ребра, так как дороги можно представить рёбрами, соединяющими города-вершины некоторого графа.
Допускается несимметричность матрицы Dji ≠ Dji. В ещё более общем случае пути между некоторыми городами могут отсутствовать.
Исходные условия можно записать в формате таблицы, где строки — города отправления, столбцы — города прибытия, в ячейках расстояния между ними.
Необходимые поля:
− Массив минимального пути
− Посещенные пути при текущем проходе
− Вес минимального пути
Необходимые методы:
− Начальный метод поиска пути
− Рекурсивный метод построения пути для заданного начала (в качестве параметра)
− Первый минимум массива
− Второй минимум массива
Алгоритм начального метода поиска пути
− Инициализация нижней границы (bound):
− Цикл вызова рекурсивного поиска минимального пути для каждого узла в качестве начальной точки
Алгоритм рекурсивного поиска пути
− Если все пройдено
- Если есть путь до начальной точки
- Длина пройденного пути = переданная длина + путь до начальной точки
- Если длина пути меньше минимальной длины
- Сохраняем путь и длину в качестве минимальных
− Иначе проходим по всем путям (i=0..N-1)
- Если есть путь до не посещенной точки
- Сохраняем нижнюю границу
- Идем в узел i
- Добавляем к текущей длине пути
- Вычисляем нижнюю границу для текущего пути по формуле выше
− Если текущая длина + граница для текущего пути меньше минимума
- Рекурсивный вызов следующего уровня (проходим в узел i)
- Обрезаем узел
- Очищаем массив посещенных узлов
Расчеты
В ходе тестирования метода ветвей и границ было совершено 30 генераций матриц и использован метод поиска пути для каждой из них. Результаты представлены в таблице 1. При использовании грубого метода использовалось:
(10! вариантов путей) * (10 переходов на 1 путь) = 36 288 000 переходов
Читайте также: