Целочисленное программирование
Математически эта задача формулируется следующим образом, найти максимум или минимум
R(x)=R(x1,x2,…xn)=Enj=1cjxj (1)
При ограничениях
Eaijxj<bi i=1,m (2)
Xj=>0, i=1,n (3)
xj-цене, i=1,p, p<=n (4)
если в (4) p=n-> то имеет место полностью целочисленная задача линейного программирования
p<n -> то частична задача ЛП
рассматриваются также задачи с булевыми переменными, с несколькими целевыми функциями.
Условие (4) накладывают задача на (1-3) линейного программирования дополнительные ограничения. Поэтому в общем случае задача результат будет меньше чем ЛПР, где хцпр-оптимальное решение задачи (1-4), а хЛПР-оптимальное решение задачи (1-3).
Источником дискретности и целочисленности могут быть:
1)физическая неделимость факторов нельзя купить 2,3 самолета, построить полдома
2)комбинаторность
3)размер и партии (иногда нельзя выпускать партии размером меньше чем предельно допустимы
ЦПР ЛПР
Пример
R(x)=R(x1,x2)=21x1+11x2->max (5)
При
7x1+4x2<=13 (6)
X1=>0, x2=>0 (7)
X1,x2-целые (8)
Имеем задачу целочисленного линейного программирования
Вначале решим графически задачу ЛПР (5-7) и если ответ будет целочисленный то задача решена.
Если ответ нецелочисленный, округлим результат до ближайшего целого числа.
TO(0,0)=R0=0
TA(0,3(1/4))=R
TB(13/7,0),Rb=
Ra=21*0+11*3(1/4)=35,75
Rb=21*13/7+11*0=139
Оптимальное решение (1-3)задачи ЛПР.
Таким образом решение оптимальным решением задачи (5-7) является (х1*,х2*)=(13/7,0)
R(x1*,x2*)ЛПР=39
Округление х1* до 2 невозможно, потому что это значение не является допустимым, оно не принадлежит области х, значит округлим х1 до 1.
Х1*ЦПР=1
Х2*ЦПР=0
R(x1*,x2*)ЦПР=21*1+11*0=21
Рассмотрим задачу ДПР(5-8) и нанесем целочисленные точки в область Х.
Вычислим значение целевой функции R(x) в целочисленных точках.
(0,0)=R=0
(1,0)=21
(0,1)=11
(0,2)=22
(0,3)=33
(1,1)=32
Таким образом оптимальной точкой в задача (1-8) ЛПР является точка (0,3).
Таким образом, следовательно, что задача целочисленного программирования решается значительно сложнее.
Трудности решения задач ЦПР существенно возрастают с ростом размерности задач, то есть с ростом n и m.
Методы решения делятся на 2 группы:
1)методы отсечения
2)перебора
Методы отсечения.
Вначале отбрасываются условия целочисленности (4) и решается задача ЛПР (1-3). Если оптимальное решение получается целочисленным, то задача решена, в противном случае к ограничениям (2-3) добавляется еще одно дополнительное линейное ограничение, которому не удовлетворяет полученное только что оптимальное нецелочисленное решение задачи ЛПР, а все целочисленные решения удовлетворяют. Геометрически это означает что новые ограничения отсекает от многогранника нецелочисленную вершину. Затем решается новая задача ЛПР и процесс повторяется для пополненной системы. Решение достигается за конечное число шагов.
Метод частичного перебора
(самый известный метод ветвей и границ).
Исходное множество разбивается на то или иное количество подмножеств из которых обрасываются не перспективные, путем вычисления Rx и сравнения их значений.
Объем вычисления растет по экспоненте с ростом n.
Динамическое программирование (ДПр)
Ричард Беллман
Дпр применяется в задачах многоэтапного (много шагового) процессах принятия оптимальных решений. Много этапность либо существует, либо организуется. Целью является сведение сложной многомерной задачи к последовательности более простых задач оптимизации.
Для более простых задач используется используются изученные раннее методы оптимизации.
В процессе решения находится глобальный экстремум. Критерий оптимизации является адьетивный или мульпликативным. ДПр применяется для непрерывных дикретных, детерминированных и стохастических.
При постановке задачи на целевую функцию не накладывается таких ограничений как, линейность, выпуклость, непрерывность и другие.
Будем рассматривать случаи когда доход для всего процесса, равен сумме доходов на каждой стадии.
Многошаговые процессы
Рассмотрим цепочку аппаратов в которых последовательно проходят переработку исходное вещество и получается некоторое вещество.
Рисунок
на каждой стадии имеется некое управление Ui, на вход каждой стадии подается вещество Pi, на выходе I стадии получается Pi+1(i=1,n). Очевидно что вектор на выходе каждой стадии зависит от его входа и управления на этой стадии,
P2=T(P1,U1)...
P3=T(P2,U2)
… (1)
Pn=T(Pn-1, Un-1)
Pn+1=T(Pn,Un)
должны быть известны математические модели. Задача управления таким процессом заключается в том, чтобы найти такие управления U1,U2…Un чтобы максимизировать некоторые критерии F(P1,P2…Pn,U1,U2…Un)=G(P1,U1,U2…Un).
При P1=const и известных математических моделях получается такая задача
F(P1,P2…Pn,U1,U2…Un)=G(P1,U1,U2…Un).-надо максимизировать (2)
При максимизации (2) выполняются математические модели 1, то есть имеет место задача уравнения связи и имеет место задача условной оптимизации.
В нашем случае надо найти n переменных, U1,U2,…Un. Использовать изученные методы нельзя:
А)по сколько чаще всего нет выражения G то нельзя дифференцировать, найти производные и прировнять к нулю. кроме решение часто находится на границах области изменения управления (основная трудность).
б)применяя не линейное программирование мы получаем лишь локальный экстремум, если использовать перебор то число вычислений огромно.
Критерий оптимизации в данном случае адъективный, то есть G зависит от P1, есть сумма gi, на отдельный стадиях от 1 до n, и каждая эта величина есть на входе, и что есть управление.
Есть сумма g1(P1,U1)+g2(P2,U2)+…gn(Pn,Un) так как число состояний на каждой стадии велико, число стадий также значительно то решение этой задачи крайне затруднитульно.
Идея метода ДПр
Основана на приеме которой в физике называется погружением.
Вместо исходной задачи с заданным начальным состоянием P1 и известным числом стадий n, рассматривается совокупность задач или некоторые множества задач с произвольным начальным состояние Р1 и различным числом стадий n, то есть рассматривается целый класс задач.
В этом классе отыскивается одна простая задача которая решается и находятся связи между этой задачей и решениями задач целого класса, затем переходит от решения одной задачи к исходной задачи.
Проведя подобные рассуждения можно получить уравнение связи в виде
Fn(P1)=max[g1(P1,U1)+f(T(P1,U1))]
Где fn(p2) это максимальный доход полученный на n стадиях при известном начальном состоянии P1.
Fn-1(T(P1U1)) максимальный доход полученный на n-1 стадиях начиная со второй. Это уравнение связывает результаты оптимизации то есть функции fn, fn-1.
В основе динамического программирования лежит принцип оптимальности Беллмана. Характеризующий оптимальную политику.
Политика – это последовательность допустимых решений на отдельных стадиях.
Оптимальная политика – это последовательность управлений на отдельных стадиях которая максимизирует критерий оптимальности g.
Именно оптимальная политика обладает свойством:
1)каковы бы не было начальное состояние и первое решение, последующее решение должны составлять оптимальную политику по отношению к состоянию полученному в результате первого решения.
Рассматривая все стадии последовательно, начиная с последней, то есть решая задачу с конца:
1)последняя стадия
2)две последние и т.д.
Мы можем получить для каждого состояния на входе соответствующей стадии, оптимальные решения именно на этой стадии.
Результатом является следующая система функциональных уравнений Беллмана.
Динамическое программирование
u1*, …, un*
результатом является следующая система Беллмана.
F2(Pn)=max gn(Pn, Un)
F2(Pn-1)=max [gn(Pn-1, Un-1)+f1(T(Pn-1,Un-1))]
…
Fn(P1)=max[g1(P1,U1)+fn-1(T(P2,U2))]
Эти уравнения лежат в основе алгоритма ДПр.
Для них характерно наличие библиотек хранящих информацию о состояниях функционирования на входах каждой стадии, оптимальных управлениях, оптимального управления, для каждого из этого состояния и соответствующих состояний на выходе каждой стадии при оптимальных управления. Благодаря этому исходная сложная задача решается за приемлемое время.
Пример:
Пусть существует N стадийный процесс, на каждой стадии которого может быть n состояний.
При чем из каждого состояния предыдущей стадии можно попасть в любое состояние последующей стадии.
Рузельтат перехода из какого то состояния на предыдущей стадии оценивается числом.
r1(qi-1,qn)
задача заключается в том чтобы на каждой стадии выбрать такое число которая характеризует переход из одного состояния i-1 в конкретное состояние i-ой стадии.
Таким образом чтобы результат перехода из 1 стадии на последнюю n стадию был бы максимальный.
RN=sum ri(qi-1,qn)->max
Рисунок (перерисовать)
Прямым перебором такую задачу решить очень трудно, используя метод динамического программирования.
Для этого рассмотрим последнюю N стадию, для нее входными состояниями являются состояния 1,2,3 n-1 стадии.
Рассмотрим состояние n-1 стадии при этом мы перебрали 3 варианта, если мы оказались во втором состоянии предыдущей стадии.
Решением являются числа
q1N=3
q2N=1
q3N=3
всего мы перебрали 9 вариантов, и из них выбрали 3 варианта.
Рассмотрим n-1 стадию и выберем управление с учетом выбора первой стадии.
Рисунок
У нее также 3 состояния на входе 1,2,3. Рассмотрим состояние 1 N-2 стадии.
q1N-2=1
q2N-2=1
q3N-2=2
рассмотрим далее стадию N-2. И так далее вплоть до первой стадии, в итоге получим N*n2
просмотренных вариантов.
N=20
n=3
M=20*32=180 вариантов
Практическое занятие по динамическому программированию
Задача:
Дан сетевой график (график)
Найти путь при перемещение по которому от узла 1 к узлу 6 затрачивается минимальное время. Двигаться можно только в направление увеличения узлов.
| рам | путь | время | рам | Путь | Время |
| 2а 2б | 1,2,5,6 1,2,5,6 1,2,3,5,6 1,2,4,5 | 4а 4б 4в 4г | 1,2,3,4,5,6 1,2,3,4,6 1,3,4,5,6 1,3,4,6 |
Метод перебора функции