Реферат: Применение метода ветвей и границ для задач календарного планирования
ФИНАНСОВАЯАКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ РФ
Кафедра «Математика и финансовыеприложения»
Курсовая работа по дисциплине
«Метод ветвей и границ в исследованииопераций»
Применение метода ветвей и границ длязадач календарного планирования
Москва 2011
/>Содержание
Введение
I. Описание задачи целочисленного программирования
II. Методветвей и границ
§1. Описание метода ветвей и границ
§2. Алгоритм действияметода ветвей и границ
§3. Общий алгоритм решения задач с помощью метода границ и ветвей, его суть
§4. Примериспользования метода ветвей и границ
III. Применение метода ветвей и границ для задач календарногопланирования
§1. Алгоритм решениязадачи трех станков методом ветвей и границ
§1.1 Реккурентное вычисление A(sk), В(sk), C(sk) и условие доминирования
§1.2 Способконструирования вариантов последовательностей s и вычисления оценок D(s)для каждого из них.
§2. Пример использования метода ветвей и границ в задачетрех станков
Список литературы
Приложения
Приложение 1
Приложение 2
Приложение 3
Введение
В своей курсовой работемне хотелось бы рассмотреть применения метода ветвей и границ для задачкалендарного планирования. В контексте данной задачи будет дано общее описаниеметода ветвей и границ, его места в общей задаче целочисленногопрограммирования.
Будут рассмотрены примеры,как простого применения метода, так и для задач календарного планирования (будетрассмотрена задача о трех станках).
Данная тема являетсячрезвычайно актуальной, ведь метод ветвей и границ в связи с простотой сущностиалгоритма используется при работе на некоторых ЭВМ, а решения задачкалендарного планирования всегда востребованы как в экономической отрасли, таки других, смежных с ней.
I. Описание задачи целочисленного программирования
По смыслу значительнойчасти экономических задач, относятся к задачам линейного программирования,компоненты решения должны выражаться в целых числах, т.е. быть целочисленными.К ним относятся, например, задачи, в которых переменные означают количествоединиц неделимой продукции, число станков при загрузке оборудования, числосудов при распределениях по линиям, число турбин в энергосистеме, числовычислительных машин в управляющем комплексе и многие другие.
Задача линейногоцелочисленного программирования формируется следующим образом: найти такоерешение (план) X = (x1,x2,...,xn),при котором линейная функция
/> (1)
принимает максимальноеили минимальное значение при ограничениях:
/>/>= bi, />. (2)
хj³ 0, />. (3)
xjÎZ, />. (4).
II. Метод ветвей и границ
§1. Описание метода ветвей и границ
Метод ветвей и границ —один из комбинаторных методов. Его суть заключается в упорядоченном переборевариантов и рассмотрении лишь тех из них, которые оказываются по определеннымпризнакам перспективными, и отбрасывании бесперспективных вариантов.
Метод ветвей и границсостоит в следующем: множество допустимых решений (планов) некоторым способомразбивается на подмножества, каждое из которых этим же способом сноваразбивается на подмножества. Процесс продолжается до тех пор, пока не полученооптимальное целочисленное решение исходной задачи.
§2. Алгоритм действия метода ветвей играниц
Первоначально находим,к примеру, симплекс-методом оптимальныйплан задачи без учета целочисленности переменных. Пусть им является план X0. Если среди компонент этого плананет дробных чисел, то тем самым найдено искомое решение данной задачи и Fmax<sub/>=F(X0).
Если же среди компонентплана X0имеются дробные числа, то X0не удовлетворяет условиюцелочисленности и необходимо осуществить упорядоченный переход к новым планам,пока не будет найдено решение задачи. Покажем, как это можно сделать,предварительно отметив, что F(X0)³F(X)для всякого последующего плана Xв связи с увеличением количества ограничений.
Предполагая, чтонайденный оптимальный план X0не удовлетворяет условиюцелочисленности переменных, тем самым считаем, что среди его компонент естьдробные числа.Пусть, например, переменная /> приняла в плане X0дробное значение. Тогдав оптимальном целочисленном плане ее значение будет по крайней мере либо меньшеили равно ближайшему меньшему целому числу/>, либо больше или равноближайшему большему целому числу />.Определяя эти числа, находим симплекс-методом решение двух задач линейногопрограммирования:
/>
Найдем решение задачлинейного программирования (5) и (6). Очевидно, здесь возможен один изследующих четырех случаев:
1. Одна из задачнеразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план изначение целевой функции на нем и дают решение исходной задачи.
2. Одна из задачнеразрешима, а другая имеет оптимальный план, среди компонент которого естьдробные числа. Тогда рассматриваем вторую задачу и в ее оптимальномплане выбираем одну из компонент, значение которой равно дробному числу, и строимдве задачи, аналогичные задачам (5) и (6).
3. Обе задачиразрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальномплане другойзадачи есть дробные числа. Тогда вычисляем значения целевой функции на этихпланах и сравниваем их между собой.
3.1. Если нацелочисленном оптимальном плане значение целевой функции больше илиравно ее значению на плане, среди компонент которого есть дробные числа,то данный целочисленный план является оптимальным для исходной задачи и онвместе со значением целевой функции на нем дает искомое решение.
3.2. Если же значениецелевой функции больше на плане, среди компонент которого естьдробные числа, то следует взять одно изтаких чисел и для задачи, план которой рассматривается, необходимо построитьдве задачи, аналогичные (5) и (6).
4. Обе задачиразрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогдавычисляем значение целевой функции на данных оптимальныхпланах и рассматриваем ту из задач, для которой значение целевой функции являетсянаибольшим.В оптимальном плане этой задачи выбираем одну из компонент,значение которой является дробным числом, и строим две задачи, аналогичные (5)и (6).
§3. Общий алгоритм решения задач спомощью метода границ и ветвей, его суть
Таким образом,описанный выше итерационный процесс может быть представлен в виде некоторогодерева, на котором исходная вершина отвечает оптимальному плану Х0задачи(1)-(3), а каждая соединенная с ней ветвью вершина отвечает оптимальным планамзадач (5) и (6). Каждая из этих вершин имеет свои ветвления. При этом на каждомшаге выбирается та вершина, для которой значение функции является наибольшим.Если на некотором шаге будет получен план, имеющий целочисленные компоненты, изначение функции на нем окажется больше или равно, чем значение функции вдругих возможных для ветвления вершинах, то данный план является оптимальнымпланом исходной задачи целочисленного программирования и значение целевойфункции на нем является максимальным.
Итак, процесснахождения решения задачи целочисленного программирования (1)-(4) методомветвей и границ включает следующие основные этапы:
1. Находят решениезадачи линейного программирования (1)-(3).
2. Составляютдополнительные ограничения для одной из переменных, значение которой воптимальном плане задачи (1)-(3) является дробным числом.
3. Находят решениезадач (5) и (6), которые получаются из задачи (1)-(3) в результатеприсоединения дополнительных ограничений.
4. В случаенеобходимости составляют дополнительные ограничения для переменной, значениекоторой является дробным, формулируют задачи, аналогичные задачам (5) и (6), инаходят их решение.
Итерационный процесспродолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленномуплану задачи (1)-(4) и такая, что значение функции в этой вершине больше илиравно значению функции в других возможных для ветвления вершинах.
Описанный выше методветвей и границ имеет более простую логическую схему расчетов, чем методГомори. Поэтому в большинстве случаев для нахождения решенияконкретных задач целочисленного программирования с использованием ЭВМприменяется именно этот метод.
§4. Пример использования метода ветвей играниц
В качестве примерак методу ветвей и границ рассмотрим функцию z=4х1+х2+1®max (7) при ограничениях:
/> (8). x1,x2ÎZ, (9).
Пусть Х0= (0; 0), z0= 1 — «оптимальное»[1]решение (10).<sub/>Выполним 1-й этап общего алгоритмаи найдем с помощью симплекс-метода, а затем и двойственного симплекс-метода(см. Приложение 1) X1,исходя из ограничений (8). Итак, X1=(3; 0,5; 0; 1; 0; 2,5), z1= 13,5 (11). Так как z1дробное,то «оптимальным» так и остается план Х0,
Согласно 2-му пунктунашего плана, составим 2 новых системы ограничений для (7):
/> (12) и /> (13).
Выполним 3-й пункталгоритма. Для начала, решим задачу (7), (12) с помощью табличного процессора MicrosoftExcel (см. Приложение 2) иполучим X2= (2; 1)[2],z2= 10 (14). Так как z2≥z0,«оптимальным» становится план Х0.
Решим задачу (7), (13).Из последнего уравнения очевидно, что x2= 0. Отсюда следует, что x1= 3 (максимально возможное). Тогда Х3 = (3; 0), z3= 13 (15), а следовательно, данный план является оптимальным (теперь уже безкавычек).
Нам не пришлосьвыполнять 4-й пункт нашего алгоритма в связи с тем, что оптимальное решениенайдено, переменные целочисленные. К тому же, все необходимые моменты решенияуже были показаны в пунктах 1-3.
Пример, в котором всёскладывается не так просто, приведен в Приложении 3.
календарное планирование программирование
III. Применение метода ветвей и границ для задач календарногопланирования
Метод ветвей и границявляется универсальным методом решения комбинаторных задач дискретногопрограммирования. Сложность практического применения метода заключается втрудностях нахождения способа ветвления множества на подмножества и вычислениясоответствующих оценок, которые зависят от специфики конкретной задачи.
Для того, чтобывыяснить области применения данного метода и ознакомиться с практической егоформой, мы обратимся к задаче трех станков[3],как к классическому примеру.
§1. Алгоритм решения задачи трех станковметодом ветвей и границ
Заданыn деталейdi (i=1, 2, ..., n), последовательнообрабатываемых на трех станках R1,R2,R3,причем технологические маршруты всех деталей одинаковы. Обозначим ai,bi ,ci— длительностьобработки деталей diнапервом, втором и третьем станках соответственно.
Определитьтакую очередность запуска деталей в обработку, при которой минимизируетсясуммарное время завершения всех работ Tц.
Можнопоказать, что в задаче трех станков очередность выполнения первых, вторых итретьих операций в оптимальном решении может быть одинаковой (для четырехстанков это свойство уже не выполняется). Поэтому достаточно определитьочередность запуска только на одном станке (например, третьем).
Обозначимsk= (i1,i2,..., ik)— некоторуюпоследовательность очередности запуска длиной k(1£k £n) и A(sk),В (sk), С (sk)— времяокончания обработки последовательности деталей skнапервом, втором и третьем станках соответственно.
Необходимо найти такуюпоследовательность sопт,что
С(sопт)= min С (s). (16)
§1.1 Реккурентное вычисление A(sk), В(sk), C(sk) и условие доминирования
Покажем, как можнорекуррентно вычислять A(sk),В (sk), С (sk).Пусть sk+1= (sk,ik+i),т. е. последовательность деталей sk+1полученаиз деталей skсдобавлением еще одной детали ik+1.Тогда:
A (sk+1)= A (sk)+/> (17),
В (sk+1)= max [A(sk+1);В (sk)]+ /> (18),
С (sk+1)= max [В (sk+1);С (sk)]+/> (19).
Логика выражений (17) –(19) очевидна, особенно если рассмотреть задачу двух станков.
Для задачи трех станковможно использовать следующее правило доминирования:
Еслиs— некоторая начальная последовательность, а /> —подпоследовательность, образованная из s перестановкойнекоторых символов, то вариант s доминирует над />,когда выполняются следующие неравенства:
А(s)£А (/>),В (s)£В (/>),С (s)£С (/>) (20),
причемхотя бы одно из них выполняется как строгое неравенство.
§1.2 Способ конструирования вариантов последовательностей s и вычисленияоценок D(s) для каждогоиз них
Способ конструированиявариантов последовательностей s и вычисления оценок D(s)для каждого из них состоит в следующем:
Пусть имеется начальнаяподпоследовательность s. Тогда вычисляются величины:
dC(s)= С(s)+/>, (21)
dB(s)= В (s)+/> + />, (22)
dA(s)= A (s)+/> + /> (23),
где J (s)— множество символов, образующих последовательность s.
За оценку критерия С(s)для варианта s можно принять величину
D(s)=max {dA(s),dB(s),dC(s)} (24).
Тогда ход решениязадачи трех станков можно представить следующей формальной схемой:
1) Нулевойшаг.Заданиемножества G(0),образуется всеми возможнымипоследовательностями (s = 0).
Вычисление оценки длямножества G0:
D(0) =max{dA(0),dB(0), dC(0)} (25), где
/>; />; /> (26).
2) Первыйшаг.Образование множеств G1(1),G2(1), …, Gn(1),подмножествоGkопределяетсявсемипоследовательностями с началом ik(k,...,n).
Вычисление оценок.Оценку для последовательности sk<sub/>определяютиз соотношения (24), т. е. D(sk)=max {dA(sk),dB(sk),dC(sk)};k = 1,…,n. (27).
Выбор варианта дляпродолжения. Из всех подпоследовательностей,построенных на предыдущем шаге, выбирают наиболее перспективнуюпоследовательность skс наименьшей оценкой, т. е. D(sk(1))=minD(sj(1)). (28)
Ветвление.Выбрав наиболее перспективный вариант последовательности sk(1),развивают его построением всех возможных подпоследовательностей длиной 2 сначалом sk(1)<sup/>вида sk+1(2)=(sk(1),j), где jне входит в sk.
Вычисление оценокпроизводят в соответствии с соотношениями (21), (22), (23).
3) k-й шаг.Допустим, что уже проведено kшагов,в результате чего построены варианты s1(k),<sup/>s2(k),…,sk(k),а именно подпоследовательности длиной k.
Выбираем самый перспективныйвариант sS(k)такой,что
D(ss(k))=minD(sj(k)).
Множество Gs(k)разбиваем на (n — k)подмножеств,каждое из которых образуется добавлением к последовательности ss(k)некоторогоэлемента ik+1такого, что ik+1/>.
Оценка /> определяется всоответствии с соотношениями (21) — (24).
В результате строимдерево вариантов следующего вида: вершина О отвечает s= 0, вершины первого уровня G1(1),G2(1)...,Gn(1)соответствуютпоследовательностям длиной 1, т. е. s1(1)=1, s2(1)= 2,...,sn(1)= п и т. д. Каждая конечная вершина отвечает последовательности максимальнойдлины n.
Признак оптимальности.Еслиsv(n)отвечаетконечной вершине дерева, причем оценка /> наименьшая изоценок всех вершин, то sv(n)—искомый вариант.
§2. Пример использования метода ветвей играниц в задаче трех станков
Для того, чтобы придатьформальной схеме прикладное значение, рассмотрим конкретный пример задачи трехстанков.
Решим задачу трехстанков, условия которой приведены в табл. 1:
Таблица 1
Длительность операций Деталь 1 2 3 4 5ai
bi
ci
2
3
4
5
2
4
1
1
2
3
4
2
3
5
2
1) Нулевой шаг.s= 0.
dA(s= 0) = A(0) + /> + /> =0 + 14 + 3 = 17;
dB(s= 0) = В(0)+ /> + /> =0 + 15 + 2 = 17;
dC(s= 0) = С(0)+ />=14.
Тогда
∆ (s= 0) = max {17, 17,14} = 17.
2)Первый шаг. Конструируем все возможныепоследовательности длиной 1<sub/>
s1(1)=1; s2(1)= 2; s3(1)= 3; s4(1)= 4; s5(1)= 5.
Находим:
dA(1)= A1+ /> + /> =14 + 3 = 17;
dB(1)= В1 + /> + /> =5 + 12 + 2 = 19;
dC(1)= С1 + />=9 + 10 = 19 .
Откуда ∆ (1) = max{17, 19, 19} = 19.
Аналогично определяем ∆(2), ∆ (3), ∆ (4), ∆ (5).
3) Второй шаг.Среди множества подпоследовательностей длиной 1, s1(1)=1, s2(1)= 2,...,s5(1)=5 выбираем наиболее перспективную s = 1, длякоторой величина оценки-прогноза ∆ (s) оказывается наименьшей.Далее развиваем ее, конструируя возможные варианты длиной 2, т. е. (1.2),(1.3), (1.4), (1.5).
Для каждого из этихвариантов вновь определяем оценки по формулам (21) — (24).
Процесс вычисленийпродолжаем аналогично.
Процесс построениядерева вариантов приведен на рис. 1.
Рисунок 1
/>
Каждой конечной вершинедерева вариантов будет отвечать полная последовательность s= i1,i2,,.in.Еслидля некоторой такой вершины величина оценки ∆ (s)не превосходит величины оценок для всех остальных вершин, то эта оценкаопределяет искомый оптимальный вариант. В противном случае разбиваем болееперспективный вариант с наилучшей оценкой.
Конечная вершинаопределяет вариант (последовательность) /> = 3, 1, 5, 2, 4 снаилучшей оценкой ∆ = 20. Поэтому данный вариант является оптимальным.
Непосредственнойпроверкой убеждаемся, что время обработки всей последовательности деталей дляэтого варианта совпадает со значением оценки-прогноза и является минимальным:
/>.
Список литературы
1. АкуличИ.Л. Математическое программирование в примерах и задачах. М., Высшая школа,1993.
2. ГончаренкоВ.М. «Математические методы и модели операций. Руководство к решению задач».М., Финансовая Академия, 2006.
3. ЗайченкоЮ.П. Исследование операций. Киев, Высшая школа, 1975.
4. КузнецовЮ.Н., Кузубов В.И., Волощенко А.Б. Математическое программирование. М., Высшаяшкола, 1980.
5. ШкурбаВ.В. Задача трех станков. М., Наука, 1976.
Приложение 1
Решение задачи
z= 4х1 + х2 +1 ® max при ограничениях:
/>
симплекс-методом:
базисbi
x1
x2
x3
x4
x5
x6
x3
4 1 2 1x4
12 3 2 1x5
3 1 1x6
3 1 1 1 z 1 -4 -1x2
2 0,5 1 0,5x4
8 2 -1 1x5
3 1 1x6
1 -0,5 -0,5 1 z 3 -3,5 1x1
4 1 2 1x4
-2 -2 1x5
-1 -2 -1 1x6
3 1 1 z 17 7 4,5x1
3 1 1x4
1 -1 1 -1X2
0,5 1 0,5 -0,5x6
2,5 -0,5 0,5 1 z 3,5 1,5 3,5z*=13,5, Х1*=(3;0,5;0;1;0;2,5).
Приложение 2
/>
Решение задачи z = 4х1+ х2+1 ®max при ограничениях:
с помощью табличногопроцессора MicrosoftExcel.
/>
Приложение 3
В качестве примераприменения метода ветвей и границ приведем поиск оптимального значения функцииZ = Зх1 + х2®max приограничениях:
/>
4xl + Зх2< 18,
x1+ 2x2£ 6,
0 £x1£ 5,
0 £x2£ 4,<sub/>
х1, x2— целые числа.
Решение
За нижнююграницу линейной функции примем, например, ее значение в точке (0,0), т.е. Z0= Z (0; 0) = 0.
I этап. Решая задачусимплекс-методом, получим Zmax= 13,5 при Х1* = (4,5; 0; 0; 1,5; 0,5; 4); так как перваякомпонента х1* дробная, то из области решения исключаетсяполоса, содержащая дробное оптимальное значение х1*, т.е.4 < х1 < 5. Поэтому задача 1 разбивается на две задачи 2 и 3.
Задача 2
Z=3x1+x2→max
при ограничениях:
/>
4xl + Зх2< 18
x1+ 2x2£ 6
0 £x1£ 4
0 £x2£ 4<sub/>
х1, x2— целые числа.
Задача 3
Z=3x1+x2→max
при ограничениях:
/>
4xl + Зх2< 18
x1+ 2x2£ 6
5 £x1£ 5
0 £x2£ 4<sub/>
х1, x2— целые числа.
Список задач: 2 и 3.Нижняя граница линейной функции не изменилась: Z0= 0.
II этап. Решаем (повыбору) одну из задач списка, например задачу 3 симплекс-методом.
Получим, что условиязадачи 3 противоречивы.
III этап. Решаем задачу2 симплекс-методом. Получим Zmax= 12 2/3 при X3*= (4; 2/3; 0; 2/3; 0; 10/3). Хотя Z(X3*)= 12 2/3 > Z0= 0, по-прежнему сохраняется Z0= 0, ибо план нецелочисленный. Так как х2* — дробноечисло, из области решений исключаем полосу 0 < x2 < 1 и задачу2 разбиваем на две задачи 4 и 5.
Задача4
Z=3x1+x2→max
при ограничениях:
/>4xl +Зх2 < 18
x1+ 2x2£ 6
0 £x1 £ 4
0 £x2 £ 0<sub/>
х1, x2— целые числа.
Задача5
Z=3x1+x2→max
при ограничениях:
/>4xl +Зх2 < 18
x1+ 2x2£ 6
0 £x1£ 4
1 £x2£ 4<sub/>
х1, x2— целые числа.
Список задач: 4 и 5.Значение Z0= 0.
IV этап. Решаемзадачу4 симплекс-методом.
Получим Zmax = 12 приX4*= (4; 0; 2; 2; 0; 0). Задачу исключаем из списка, но при этом меняемZ0;Z0= Z(X4*) = 12, ибоплан Х4* целочисленный.
V этап. Решаем задачу5 симплекс-методом.
Получим Zmax= 12,25 при X5* = (3,75;1; 0; 0,25; 0,25; 0; 3). Z0 неменяется, т.е. Z0=12, ибо план X5* нецелочисленный.Так какх1* — дробное, из области решений исключаем полосу 3<x1<4,и задача 5 разбивается на две задачи: 6 и 7.
Задача 6
Z=3x1+x2→max
при ограничениях:
/>
4xl + Зх2< 18
x1+ 2x2£ 6
0 £x1£ 3
1 £x2£ 4<sub/>
х1, x2— целые числа.
Задача 7
Z=3x1+x2→max
при ограничениях:
/>
4xl + Зх2< 18
x1+ 2x2£ 6
4 £x1£ 4
1 £x2£ 4<sub/>
х1, x2—целыечисла.
Список задач: 6 и 7.Значение Z0= 12.
VI этап. Решаемодну из задач списка, например задачу 7, симплекс-методом. Получим, что условиязадачи 7 противоречивы.
VII этап. Решаем задачу6 симплекс-методом. Получим Zmax= 10,5, при X6* = (3; 1,5; 1,5; 0; 0; 0,5; 2,5). Так как,Z(X6*) = 10,5 < Z0= 12, то задачаисключается из списка.
Итак, список задачисчерпан и оптимальным целочисленным решением исходной задачи будет X*= Х4* = (4; 0; 2; 2; 0; 0), а оптимум линейной функции Zmax= 12.