Целочисленное программирование

Математически эта задача формулируется следующим образом, найти максимум или минимум

R(x)=R(x1,x2,…xn)=Eⁿ_j=1c_jx_j(1)

При ограничениях

Ea_ijx_j<b_i 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*n²

просмотренных вариантов.

N=20

n=3

M=20*3²=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

Метод перебора функции