Циклы и их использование
34.Циклы и их использ
Для перехода от одного ОП к другому использ-я циклы. Цикл предст. замкн-ю ломаную линию, сост-ю из звеньем, кот пересек-ся под прямым углом. Цикл. включ. 1 своб. кл-ку. В цикле всегда четное число кл-к. Цикл строится для свободн. кл-ки. Если ломанная линия пересек-ся, то точки самопересечения не явл. вершинами. Для наиб перспективн. кл-ки строится замкнутый цикл с вершинами в загружен. кл-х. Вершинами этого цикла усл. приписыв. знаки: своб. кл-ке «+», следующ. «-» и т. д. из поставок в кл-х цикла с «отриц.» верш. выбир. наименьш. кол-во груза, кот перемещ-ся. по кл-м этого цикла: прибавл. в положит. верш. и вычет. в отрицат., в рез-те чего баланс цикла не наруш.
35.Услож постановки ТЗ 1)Для мин-ции сумм. затрат на пр-во и перевозку прод-ии, критерий оптим-ти – сумма затрат на пр-во 1ед. груза и на перевозку. 2)Если нужно вводить огранич-я, согл. кот-ым отд. поставки от определ. пост-ка опред. потреб-лю должны быть исключены, то в матрице перевозок, содерж-ей оптим. план, определ. клетки должны быть своб-ми(т. е искусств-но завыш. тариф в клетках, перевозки ч/з кот-ые след. запретить) 3)нужно учит-ть огран-я по пропуск. спос-ти маршруток. Напр.,если по маршруту AkBs можно провести не >d ед. прод-ии, то столбец Bs разбив-ся на 2: Bs’ и Bs’’. В 1-м столбце спрос=разности м/у действит. спросом и огр-ем Bs-d, а во 2-м ст-це спрос=d. Тарифы в 2-х ст-ах одинак-ы, а в клетке AkBs’тариф иск-но завыш-ся. 4)Если некот. поставки по некот. маршр-м должны войти в оптим. план, даже если это невыгодно, то тариф иск-но заниж-ся.
37.Пост-ка и мат. модель задачи ЦП.
ЦП-раздел мат. програм-ния, изуч экстрем. задачи, в кот. на искомые перем налагается усл целочисл, а ОДР-конечна. Задача «о контейнерных перевозках»(о рюкзаке)Для перевозки n видов пр-ции исп-ся контейнер с m отсеками. Пр-ция хар-ся св-вом недел, т.е. ее можно взять 0,1,2,3,4…
Сj, j=1,n – полезность ед-цы j-й прод-ции
bi, i=1,n – вместимость i-го отсека
аij, i=1,m, j=1,n – расходi-го отсека для перевозки ед прод-ции j-го вида
Треб-ся найти кол-во каждого вида прод-ции, погруж-ной в контейнер, кот-я обеспеч-ет max общую полезность рейса.
max(min)F= {≤, =, ≥} bi, i=1,m xj≥0, и целые, j=1,n
Если для перевозки исп-ся один отсек и каждый вид прод-ии может быть взят или нет, то тогда задача будет иметь вид maxF= ≤ bi, Xj Є {0,1}, j=1,n
38. Реш зад ЦП мет отсеч
Будем рассматривать следующую задачу ЦП
Max(min) F=∑ nj=1cijxij (1)
∑ nj=1cijxij =bi, i=1,m (2)
xj≥0, j=1,n (3)
xj — целый, j=1,n (4)
Осн в алгоритме — построение доп. огран, кот. наз-ся правильн отсеч. ПО должно удовл. усл:
1)быть линейным
2)отсекать найденное оптим-оенецелочисл-ое решение задачи 1-3:
Алгоритм метода:
1.Реш задача (1)-(3),с отброшенным усл-м целочис-ти(4).
2.Если усл. целочисленности вып-ся по всем переменным, то оптимальн. решение з-чи(1)-(4) совпад-т с оптимальн. решением з-чи(1)-(3).Если же это усл. не выпол-ся хотя бы поодной перемен-й, то переходим к шагу 3.Если з-ча(1)-(3)не разрешима, то и исходная з-ча не имеет реш-я.
3.Строится доп-ое ограничение, кот. отсекает часть ОДР, в кот. содерж-ся оптим-е решение з-чи (1)-(3) и не содер-ся ни одного допуст-го реш-я задачи(1)-(4)
4.Возвращ-ся к з-че с отброш-м условием целочисл-ти, но с расшир-й сис-мой осн-х ограничений. Добавляются огранич-я, построен-е на 3-ем шаге и вновь примен-ся симплексная процедура и т. д.
39. Метод Гомори (метод отсеч-я)
Будем рассм следующую задачу ЦП
Max(min) F=∑ nj=1cijxij (1)
∑ nj=1cijxij =bi, i=1,m (2)
xj≥0, j=1,n (3)
xj- целый, j=1,n (4)
Алгоритм метода:
1.Решается задача (1)-(3),с отброшенным усл-м целочис-ти(4).
2.Если усл. целочисленности вып-ся по всем переменным, то оптимальн. решение з-чи(1)-(4) совпад-т с оптимальн. решением з-чи(1)-(3).Если же это усл. не выпол-ся хотя бы поодной перемен-й, то переходим к шагу 3.Если з-ча(1)-(3)не разрешима, то и исходная з-ча не имеет реш-я.
3.Строится доп-ое ограничение, кот. отсекает часть ОДР, в кот. содерж-ся оптим-е решение з-чи (1)-(3) и не содер-ся ни одного допуст-го реш-я задачи(1)-(4)
4.Возвращ-ся к з-че с отброш-м условием целочисл-ти, но с расшир-й сис-мой осн-х ограничений. Добавляются огранич-я, построен-е на 3-ем шаге и вновь примен-ся симплексная процедура и т. д. Отличие выбора разрешающего элемента: Сначала рассм-ся строка, в кот содерж-ся отриц-е число в столбце свободн. членов и рассмат-ем все неотриц-е числа в этой строке. Выбираем люб. отрицат. число, кот и будет определять разрешающ. столбец. Для чисел с один-ми знаками в столбце свободн. членов и разреш столбце наход-ся симплекс-е отношения. Наименьш. симплексн. отнош и опред разреш-щую строку
41.Постр прав отсеч. Теорема о прав отсеч
Теорема. Рассмотрим i0 –равенство(1):
xi0= bi0-∑xj€спλi0jxj (2);
bi0=[ bi0]+{ bi0}
λi0j =[ λi0j]+{ λi0j } (3);
xi0= ([bi0]-∑xj€сп[λi0j]xj )+ ([bi0]-∑xj€сп{λi0j}xj ) (4);
([bi0]-∑xj€сп{λi0j}xj≤0 (5);
Суть теоремы: Нер-во (5)опред-т правильное отсечение Гомори, т.е.:
Max(min) F=∑ nj=1cijxij (1)
∑ nj=1cijxij =bi, i=1,m (2)
xj≥0, j=1,n (3)
xj- целый, j=1,n (4)
1.Явл-ся линейным
2.Отсекает найденное оптимальное нецелочисл-е знач-е з-чи (1)-(3)
3.Не отсекает ни одного из целочис-х реш-ий з-чи (1)-(4).
Рассмотрим i0 –равенство(1):
xi0= bi0-∑xj€спλi0jxj (2)
a=[a]цел. часть+{a}дроб. ч-ть, где 0<{a}< 1
3,7=3+0,7
-4,1=-5 +0,9
Представим bi0 и λi0j в виде суммы дробной и целой части:bi0=[ bi0]+{ bi0}; λi0j =[ λi0j]+{ λi0j }(3)
Подставим (3) в (2), получим:xi0= ([bi0]-∑xj€сп[λi0j]xj )+ ([bi0}-∑xj€сп{λi0j}xj ) (4)
Понятно, что 1-ая скобка-в сегда целое число. Для того, чтобы xi0-было целым числом надо, чтобы величина Li0={ bi0}-∑xj€сп{λi0j} xj, тоже была целым числом. Покажем, что Li0≤0.Предположим, что Li0>0.По усл величина ∑xj€сп{λi0j} xj не может быть отрицат. Т.к. дробные части 0<{λi0j}<1.По предложению следует, что дробная часть {bi0}>1,а это противоречит определению дроб-ой части числа. След-но Li0≤0Таким образом дополнит-ое огранич, кот. строит в пункте 3 алгоритма должно иметь вид: ([bi0]-∑xj€сп{λi0j}xj≤0 (5).
42.Метод ветвей и границ.
Для определённости будем рассчит з-чу нахожд макс ф-ции. Суть м-да заключ-ся в том, что сначала реш-ся з-ча без учёта целочис-сти. Если в полученном решении нек. переменные имеют дробные знач, то выбираем любую из дроб-х переменных и по ней строим 2-а ограничения. В первом ограничении величина переменной меньше или равна наименьшему целому числу, а во второй переменной ≥ целому числу +1.Таким образом исходная задача ветвится на 2 з-чи. Решаем каждую из подзадач и находим оптимальное решение. Если получ-е решения опять являются нецелыми, то дальнейшему ветвлению подлежит та ветвь, у которой значение ЦФ будет больше. Процесс решения сопровождается построением деревоветвл-ем.
43. Понят о ДП. Принц оптим Беллмана
ДП(динамическое планирование)-метод нахожд-я реш-я в з-чах с многошаговой стр-рой. Суть метода ДП — идея постепенной, пошаговой оптимизации. Если трудно решить слож-ю задачу, то её след-т разбить на ряд более простых. Каждая новая задача оптим-ся не отдельно от осталь-х, а упр-ние на каждом шаге выбир-ся с учетом всех его последствий.Исключ-е-послед-й шаг, кот. мож. план-ся без учета посдед-вий.Особ-сть ДП:всю ДП целесообр-но разворач-ть от конца к началу
Функц-е ур-ния БЕЛЛМАНА. Будем сч-ть, ч.нач-е Х0и кон-еХтсостояния сист. заданы. Об-чим ч/зf1(x0,u1)-зн-ние ф-ции цели на1-м этапе, при нач-м сост-и сист. x0 и при упр-нии u1,ч/з f2(x1,u2)-зн-ние ф-ции цели на2-м этапе ит. д….и fn(xn-1,un) зн-ние ф-ции цели на n-м этапе, тогда F=f(x0,u)=(1).Треб-ся найти оптим. ур-ние U*=U1*,U2*,…,Un*)такое, ч.достав-етЦФ1экср-е зн-е, при огр-яхU€Ω,гдеΩ-обл. опр-я исх. з-чи. Введем обоз-нияΩN,ΩN-1,N,ΩN-2,N,… Ω1,N,=Ω-обл-ти опр-ния дан. з-ч на посл-м этапе,2-х посл-х этапах ит. д. F1(xN-1), F2(xN-2),… FN(x0)-зн-я ЦФ на посл-м этапе,2-х посл. ит. д.
Пусть сост-е xN-1з-ны, тогда F1(xN-1)=max(min)поUn€ΩfN(XN-1,UN) (2); F2(xN-2)=max(min)поUn€ΩN-1,N(fN-2(XN-2,UN-1)+ F1(xN-1)) (3); FN(x0)=max(min)поU1€Ω1,N(f1(x0,u1)+ FN-1(x1)) (4).Ф-лы2-4наз-ся функц-м ур-нием Бел-на. для того, ч.найти оптим ур-ние наNшагах, нужно знать усл.-оптим. ур-ния на предшес-х N-1шаге.
44. Вычисл схема реш задач методом ДП
Раньше всех планир послед N шаг, за ним N-1 и т. д.Для кажд возможн исхода XN-1 на N-1 шаге находим оптим управл на N шаге. Такой набор оптим управл, завис от возможных исходов предыд этапа наз. усл-оптим управл: U*N(XN-1). Заверш анализ конечн этапа – рассм аналог задачу для предпослед этапа, при этом треб, чтобы ц. ф. достиг экстрем знач на 2-х послед этапах вместе. В итоге найдем усл-оптим реш на предпослед этапе: U*N(XN-2) и т. д.