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 ден. ед.
Определим булевы переменные задачи:
xij = 1, если коммивояжер переезжает из города i в город j;
xij = 0, если коммивояжер не переезжает из города i в город j.
Тогда задача заключается в определении минимума целевой функции:
,
выражающей минимальную длину маршрута, при ограничениях:
, j = 1,2,…,n - коммивояжер может въехать в город j только один раз,
, i= 1,2,…,n - коммивояжер может выехать из города i только один раз.
В задаче коммивояжера в число ограничений необходимо ввести еще одну систему условий:
ui - uj + (n-l) ∙ xij ≤ n-2, i≠j, i,j = 2. n,
которые обеспечивают устранение распадения единого маршрута на несколько не связанных между собой (частичных) маршрутов, а также предотвращают образование циклов, означающих перемещение коммивояжера по замкнутому частичному маршруту.
Задача коммивояжера также относится к классу транспортных задач с дополнительными условиями на целостность и замкнутость маршрута.
Решение задачи коммивояжера в EXCEL
Имеется 5 городов, расстояния cij между которыми приведены в таблице:Города | №1 | №2 | №3 | №4 |
№1 | ∞ | 55 | 39 | 28 |
№2 | 23 | ∞ | 31 | 37 |
№3 | 53 | 49 | ∞ | 44 |
№4 | 45 | 65 | 71 | ∞ |
В диагональные клетки таблицы занесены символы ∞, предотвращающие зацикливание маршрута на одном городе. На практике вместо символа ∞ заносится любое большое число (в данном примере число 1000000), значительно превосходящее остальные числа в таблице.
Коммивояжер, выезжая из города №1, должен посетить все города, побывав в каждом из них только один раз, и вернуться в исходный город №1.
Необходимо определить такой маршрут объезда городов, для которого длина маршрута будет минимальной.
Математическая модель
Переменные xij могут принимать значения, равные либо 0, либо 1. Целевая функция равна:
ограничения имеют вид:
- условие въезда в город j только один раз,
- условие выезда в город j только один раз,
ui - uj+3∙xij ≤ 3, i≠j, i,j=2,3,4.
Задание исходных данных и ограничений
Задание исходных данных в рабочей книге Excel приведено в табл. 1-5. В этих же таблицах приведены формулы для вычисления ограничений и целевой функции.
Таблица 1
Задание ограничений на решение задачи
Таблица 2
Задание матрицы расстояний между городами
Таблица 3
Задание целевой функции
Таблица 4
Задание ячеек для дополнительных переменных ui
Таблица 5
Задание условий для дополнительных переменных
В окне Поиск решения установить следующие параметры решения задачи:
· Установить целевую ячейку - $С$8 ,
· равной минимальному значению.
Изменяя ячейки: $B$2:$E$5 , $C$8:$E$8 - сюда заносятся не только ячейки, которые будут изменяться и в которых будут занесены решения задачи (ячейки с адресами $B$2:$E$5), но и ячейки $C$8:$E$8, содержащие переменные ui, которые также являются изменяемыми.
Ограничения задачи заносятся так же, как указано в лабораторных работах №1-№3, с обязательным указанием того, что переменные в ячейках $B$2:$E$5 - двоичные. В окне Параметры отметить: линейная модель, неотрицательные значения, автоматическое масштабирование.
Оптимальный маршрут (последовательность объезда городов): 1-3-2-4, минимальная длина маршрута F = 170.
В Excel 2007 для включения пакета анализа надо нажать перейти в блок Параметры Excel, нажав кнопку в левом верхнем углу, а затем кнопку «Параметры Excel» внизу окна:
Далее в открывшемся списке нужно выбрать Надстройки, затем установить курсор на пункт Поиск решения, нажать кнопку Перейти и в следующем окне включить пакет анализа.
Для того чтобы решить задачу ЛП в табличном процессоре Microsoft Excel , необходимо выполнить следующие действия:
1. Ввести условие задачи:
a) создать экранную форму для ввода условия задачи:
· переменных,
· целевой функции (ЦФ),
· ограничений,
· граничных условий;
b) ввести исходные данные в экранную форму:
· коэффициенты ЦФ,
· коэффициенты при переменных в ограничениях,
· правые части ограничений;
c) ввести зависимости из математической модели в экранную форму:
· формулу для расчета ЦФ,
· формулы для расчета значений левых частей ограничений;
d) задать ЦФ (в окне "Поиск решения" ):
· целевую ячейку,
· направление оптимизации ЦФ;
e) ввести ограничения и граничные условия (в окне "Поиск решения" ):
· ячейки со значениями переменных,
· граничные условия для допустимых значений переменных,
· соотношения между правыми и левыми частями ограничений.
2. Решить задачу:
a) установить параметры решения задачи (в окне "Поиск решения" );
b) запустить задачу на решение (в окне "Поиск решения" );
c) выбрать формат вывода решения (в окне "Результаты поиска решения" ).
Рассмотрим подробно использование MS Excel на примере решения следующей задачи.
Фабрика "GRM pic" выпускает два вида каш для завтрака - "Crunchy" и "Chewy". Используемые для производства обоих продуктов ингредиенты в основном одинаковы и, как правило, не являются дефицитными. Основным ограничением, накладываемым на объем выпуска, является наличие фонда рабочего времени в каждом из трех цехов фабрики.
Управляющему производством Джою Дисону необходимо разработать план производства на месяц. В приведенной ниже таблице указаны общий фонд рабочего времени и число человеко-часов, требуемое для производства 1 т продукта.
Цех | Необходимый фонд рабочего времени чел.-ч/т | Общий фонд рабочего времени чел.-ч. в месяц | |
"Crunchy" | "Chewy" | ||
А. Производство | 10 | 4 | 1000 |
В. Добавка приправ | 3 | 2 | 360 |
С. Упаковка | 2 | 5 | 600 |
а) Сформулировать модель линейного программирования, максимизирующую общий доход фабрики за месяц.
б) Решить ее c помощью MS Excel.
Ввод исходных данных
Создание экранной формы и ввод исходных данных
Экранная форма для решения в MS Excel представлена на рисунке 1.
В экранной форме на рисунке 1 каждой переменной и каждому коэффициенту задачи поставлена в соответствие конкретная ячейка на листе Excel. Имя ячейки состоит из буквы, обозначающей столбец, и цифры, обозначающей строку, на пересечении которых находится объект задачи ЛП. Так, например, переменным задачи 1 соответствуют ячейки B4 (x1), C4 (x2), коэффициентам ЦФ соответствуют ячейки B6 (c1=150), C6 (c2=75), правым частям ограничений соответствуют ячейки D18 (b1=1000), D19 (b2=360), D20 (b3=600) и т.д.
Ввод зависимостей из формальной постановки задачи в экранную форму
Для ввода зависимостей определяющих выражение для целевой функции и ограничений используется функция MS Excel СУММПРОИЗВ , которая вычисляет сумму попарных произведений двух или более массивов.
Одним из самых простых способов определения функций в MS Excel является использование режима "Вставка функций" , который можно вызвать из меню "Вставка" или при нажатии кнопки fx (рисунок 2) на стандартной панели инструментов.
Рисунок 2
Так, например, выражение для целевой функции из задачи 1 определяется следующим образом:
· курсор в поле D6;
· нажав кнопку fx , вызовите окно "Мастер функций - шаг 1 из 2";
· выберите в окне "Категория" категорию "Математические";
· в окне "Функция" выберите функцию СУММПРОИЗВ (рис. 3);
Рисунок 3
· в появившемся окне "СУММПРОИЗВ" в строку "Массив 1" введите выражение B$4:C$4 , а в строку "Массив 2" - выражение B6:C6 (рис. 4);
Левые части ограничений задачи (1) представляют собой сумму произведений каждой из ячеек, отведенных для значений переменных задачи ( B3, C3 ), на соответствующую ячейку, отведенную для коэффициентов конкретного ограничения ( B13, C13 - 1-е ограничение; B14, С14 - 2-е ограничение и B15, С15 - 3-е ограничение). Формулы, соответствующие левым частям ограничений, представлены в табл.1.
Таблица 1.
Формулы, описывающие ограничения модели (1)
Левая часть ограничения | Формула Excel |
10x1+4x2 или B3×B13+C3×C13 | =СУММПРОИЗВ(B4:C4;B13:C13)) |
3x1+2x2 или B3×B14+C3×C14 | =СУММПРОИЗВ(B4:C4;B14:C14)) |
2x1+5x2 или B3×B15+C3×C15 | =СУММПРОИЗВ(B4:C4;B15:C15) |
Дальнейшие действия производятся в окне "Поиск решения" , которое вызывается из меню "Сервис" (рис.5):
· поставьте курсор в поле "Установить целевую ячейку" ;
· введите адрес целевой ячейки $D$6 или сделайте одно нажатие левой клавиши мыши на целевую ячейку в экранной форме ¾ это будет равносильно вводу адреса с клавиатуры;
· введите направление оптимизации ЦФ, щелкнув один раз левой клавишей мыши по селекторной кнопке "максимальному значению".
Ввод ограничений и граничных условий
Задание ячеек переменных
В окно "Поиск решения" в поле "Изменяя ячейки" впишите адреса $B$4:$С$4 . Необходимые адреса можно вносить в поле "Изменяя ячейки" и автоматически путем выделения мышью соответствующих ячеек переменных непосредственно в экранной форме.
Задание граничных условий для допустимых значений переменных
Окно "Поиск решения" после ввода всех необходимых данных задачи (1) представлено на рис. 5.
Если при вводе условия задачи возникает необходимость в изменении или удалении внесенных ограничений или граничных условий, то это делают, нажав кнопки "Изменить" или "Удалить" (см. рис. 5).
Решение задачи
Установка параметров решения задачи
Задача запускается на решение в окне "Поиск решения" . Но предварительно для установления конкретных параметров решения задач оптимизации определенного класса необходимо нажать кнопку "Параметры" и заполнить некоторые поля окна "Параметры поиска решения" (рис. 7).
Рис. 7 - Параметры поиска решения, подходящие для большинства задач ЛП
Параметр "Максимальное время" служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов).
Параметр "Предельное число итераций" служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32 767.
Параметр "Относительная погрешность" служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Чем меньше количество десятичных знаков во введенном числе, тем ниже точность. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации.
Параметр "Допустимое отклонение" служит для задания допуска на отклонение от оптимального решения в целочисленных задачах. При указании большего допуска поиск решения заканчивается быстрее.
Параметр "Сходимость" применяется только при решении нелинейных задач.Установка флажка "Линейная модель" обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода.
Подтвердите установленные параметры нажатием кнопки "OK" .
Запуск задачи на решение
Запуск задачи на решение производится из окна "Поиск решения" путем нажатия кнопки "Выполнить" .
На этой странице вы найдете готовые примеры решенных задач коммивояжера - одной из самых известных задач комбинаторной оптимизации. Эта задача состоит в поиске наилучшего (выгодного, дешевого, краткого и т.п.) маршрута, проходящего через всех указанные города хотя бы по одному разу (чаще всего - с точностью по одному разу) с возвращением в начальный город.
Данная задача относится к классу NP-трудных задач и решение переборными методами (вычисление длин всех возможных маршрутов и их сравнение) практически невозможно (для $n$ городов существует $(n-1)!/2$ маршрутов). Например, если взять 10 городов - найдем 181440 путей, а для 20 - уже $6,1\cdot 10^$.
На практике чаще всего изучают метод ветвей и границ (и его модификации, в том числе алгоритм Литтла), который позволяет на каждом шаге отбрасывать целую группу неоптимальных маршрутов.
Ниже вы найдете несколько решенных данным методом примеров (оформленные разным способом, выбирайте тот, что близок к вашему пособию/методичке/лекциям), а также пример расчетов на поиск оптимального маршрута в MS Excel.
Заказать решение
Если вам нужна помощь с решением оптимизационных задач дискретной математики (задача коммивояжера, задача о ранце, задача раскроя или выбора пути), обращайтесь в МатБюро. Стоимость от 200 рублей , оформление производится в Word, срок от 2 дней.
Задачи коммивояжера с решением
Задача 1. Решите методом ветвей и границ следующую задачу коммивояжера
Задача 2. Решите методом ветвей и границ задачу коммивояжера
Задача 3.Решить задачу коммивояжёра по алгоритму Литтла:
Задача 4. Для задачи коммивояжера задана матрица расстояний между городами. Вычислить длину маршрута (4,3,2,1,4)
Задача 5. Решить задачу коммивояжера в Excel:
Как найти решение задачи коммивояжера онлайн?
Если вам нужно быстро и бесплатно решить задачу коммивояжера, рекомендую следующие сайты-сервисы (скорее всего, полученное в онлайн-калькуляторе решение потребуется дополнить/переоформить перед сдачей):
Рассмотрим задачу коммивояжера (англ. Travelling Salesman Problem, TSP) заключающуюся в отыскании самого короткого маршрута, проходящего через заданные города по одному разу с последующим возвратом в исходный город (также рассмотрим вариант без возврата).
Задача
Найдем кратчайший путь между 5 городами, координаты которых известны. Рассмотрим замкнутый вариант задачи: коммивояжёру требуется посетить все города, после чего вернуться в исходный город.
Решение
Так как даны координаты городов, то сначала найдем расстояния между ними (см. файл примера, лист 5 городов ).
Расстояния рассчитаем с помощью формулы: = КОРЕНЬ((ИНДЕКС($C$7:$D$11;$F7+1;1)-ИНДЕКС($C$7:$D$11;G$6+1;1))^2 +(ИНДЕКС($C$7:$D$11;$F7+1;2)-ИНДЕКС($C$7:$D$11;G$6+1;2))^2)
Теперь создадим модель для Поиска решения .
Совет : Вводная статья про Поиск решения в MS EXCEL 2010 находится здесь .
Переменные (выделено зеленым) . В качестве переменных модели следует взять номера городов. Так как начальная и конечная точка известны (Город0), то переменных будет 4. Ограничения (выделено синим) . Необходимо, чтобы номера городов не повторялись. Это означает, что количество уникальных (неповторяющихся) номеров городов должно быть равно 4. Для этого используется формула для подсчета уникальных значений : = СУММПРОИЗВ(1/СЧЁТЕСЛИ(B16:B19;B16:B19))
Целевая функция (выделено красным) . Длина маршрута должна быть минимальной.
Примечание : для удобства настройки Поиска решения используются именованные диапазоны .
Выберите Эволюционный метод поиска решения, т.к. созданная модель не является линейной из-за наложенного на переменные ограничения.
Найденное Решение
Поиск решения найдет (должен найти) самый короткий маршрут, т.е. последовательность 0-1-4-2-3-0 (или обратную).
В этой простейшей задаче можно проверить, действительно ли этот маршрут имеет минимальную длину, путем перебора всех вариантов маршрутов. Это реализовано в файле примера .
Совет . Таблицы перебора перестановок от 1 до 5, от 1 до 6, … от 1 до 9 можно найти в этой статье Перебор всех возможных Перестановок в MS EXCEL .
Результаты Эволюционного метода сильно зависят от начальных условий и параметров его настройки (скорость изменения, размер совокупности). Повторный поиск, с теми же начальными условиями и параметрами, может привести к различным результатам. Убедиться в этом можно с помощью модели, созданной в файле примера на листе 11 городов.
Обнулите значения переменных модели на Листе 11 городов, запустите Поиск решения. После окончания поиска (может занять несколько минут) опять обнулите значения переменных и перезапустите Поиск решения: найденные решения могут серьезно отличаться.
Совет . Иногда, для того чтобы улучшить найденное решение, помогает следующий прием: запустите Поиск решения , сохраните найденное решение, измените параметры поиска (например, размер совокупности), повторно запустите Поиск решения.
В файле примера также приведено решение задачи для замкнутого и незамкнутого маршрута посещения 9 городов. Решения найдены с помощью Эволюционного метода со следующими параметрами: Целочисленная оптимальность 0%, Использовать автоматическое масштабирование, Скорость изменения варьировалась 0,25-0,5; Размер совокупности варьировался 10-50. Оба решения проверены с помощью таблиц перебора всех маршрутов (см. таблицы перебора перестановок ). Если при первом прогоне Поиска решения не удавалось найти оптимальное решение, то он запускался повторно, при этом 1 или 2 параметра изменялись. После второго прогона оптимальное решение, как правило, было найдено.
Вывод : задачу коммивояжера (граф полностью связный, гамильтоновый цикл) можно решить стандартным Поиском решения с помощью построения нелинейных моделей. При количестве вершин графа (городов)
Читайте также: