Динамическое программирование - Учебное пособие

___________________________________________5 Задача о развитии экономической зоны ________________________________________6 Задача о коммивояжере______________________________________________________7 Задача о назначении_________________________________________________________8 Задачи теории расписаний (календарного планирования) _________________________8 Задача о покрытии_________________________________________________________10 Неоднородная ТЗ с фиксированными доплатами________________________________10 Распределительная задача (обобщенная ТЗ)____________________________________11 Распределительная задача с фиксированными доплатами ________________________12 Модель задачи выпуска продукции с разрывной целевой функцией________________13 Модель многоэкстремальной задачи оптимизации ______________________________14 Задачи логического проектирования: задача о расположении производственных единиц14 Прикладным аспектом ДП являются многие задачи экономики, планирования, управления, проектирования; в рамках ДП также формализуются задачи с логическими условиями, многоэкстремальные задачи. К таким постановкам относятся задачи, использующие в качестве интенсивности производства или распределения некоторые стандартные единицы - модули, комплексы машин и т.д. К таким задачам относятся: - задачи с неоднородной функцией цели на выпуклом многограннике; - задачи, в которых ограничения содержат условия «либо-либо». К задачам транспортного типа относятся также задача о максимальном потоке и задача о кратчайшем пути.Если план x(k) , приносящий максимум f (x) на некотором подмножестве X(k) одновременно удовле-l l творяет исходной системе ограничений x(k) X и является решением на итерации K , то этот план является претендентом на решение исходной задачи. l 3) В процессе решения задачи подмножество X0 увеличивается за счет включения в него X(k) в сле-t дующих случаях: а) если в результате сравнения оценок на разбиениях внутри итерации K хотя бы для одного подмножества X(k) максимум f (x) на подмножестве X(k) меньше максимума f (x) на подмножестве X(k) : r t r Процесс решения задачи (1) с использованием методов ветвей и границ иллюстрируется так называемым деревом ветвлений. Способ разбиения множеств на подмножество на каждом шаге K 0 генерирует две ЗЛП с целевыми функциями исходной задачи (1) и ОДР X(k), X(k) . При построении дерева ветвлений можно следовать по ветвям, приводящим к скорейшему получению 1-го претендента по решению исходной задачи - схема одностороннего обхода дерева.К приближенным методам относят метод ближайшего соседа, метод Фогеля, метод приближенного решения задачи о контейнерных перевозках. Последовательно строятся n путей, в каждом из которых началом берутся i 1,2,...n, а переход осуществляется по кратчайшему расстоянию между пунктами. Алгоритм ближайшего соседа употребляется для: 1) поиска приближенного решения, которое может быть использовано для приближенного решения задачи; 2) поиска приближенного решения, которое используется в качестве первого рекорда в алгоритме Литтла. Для решения задачи приближенно используется эвристический метод (правдоподобный).

СОДЕРЖАНИЕ

1) выбор работы j для исполнителя i или исполнителя i для работы j из набора возможных N , должно производиться по наибольшему значению показателя эффекта cij ;

2) назначение i на j или j на i должно производиться так, чтобы любое другое назначение заметно ухудшало значение функции полезности.

Схема алгоритма: 1) на каждом шаге k 1,2,...n для каждого исполнителя i из N и работы j из N определяется разность между двумя наибольшими элементами i , j ;

k k

2) из полученных i , k k j

25 выбирается наибольшее, тем самым определяется направление назначения: если элемент в строке, т.е. i наибольший, то исполнитель назначается на работу, если элемент в столбце, то работа закрепляется за исполнителем;

k

3) А) если максимальный элемент обнаружен в строке i*, то для исполнителя i* выбирается работа с наибольшей полезностью, т.е. j* выбирается так, что i*j* max, производится назначение i* на c j*, т.е. xi*j* 1, i*, j* вычеркиваются;

Б) если максимальный элемент обнаружен в столбце j*, то ищется исполнитель с наибольшим значением эффекта, т.е. i* выбирается так, что i*j* max, производится закрепление j* за кандидатом на i*, т.е. xi*j* 1, i*, j* вычеркиваются;

c

4) 1-3 повторяются до тех пор, пока не останется 1 элемент, соответствующий последнему назначению.

J I

1 2 … N k j

1 2 … N

k i

1.6 ЗАДАЧИ ЦЕЛОЧИСЛЕННОГО ПРОГРАММИРОВАНИЯ С БУЛЕВЫМИ ПЕРЕМЕННЫМИ. АДДИТИВНЫЙ МЕТОД БАЛАША

Рассмотрим задачу с булевыми (бивалентными) переменными: n cj xj min,cj 0 (1) j 1 n aij xj b ,i 1,m (2). j 1 i xj 0,1 , j 1,n (3)

Сведем ограничения к равенствам: CX min (4)

AX Y B (5) Y 0 (6) X 0,1 (7)

.

Пробным планом задачи (4)-(7) называется любой (n m)-мерный вектор U X,Y , удовлетворяющий

(5)-(6).

Пробный план называется планом, если он удовлетворяет (7) и псевдопланом, если он не удовлетворяет (7).

План называется оптимальным, если он удовлетворяет (4).

26

1.6.1 Описание идеи аддитивного алгоритма

Аддитивный алгоритм является методом частичного перебора. Он состоит в получении оптимального плана путем рассмотрения некоторого подмножества всех пробных планов -2n -штук. Это производится в рамках метода ветвей и границ.

Частичным или q-планом называется набор, состоящий из q фиксированных нулем или единицей значений xj, j N, N - подмножество индексов j .

Дополнением частичного плана называется набор n q переменных, дополняющий q-план до плана исходной задачи.

Если окажется, что конкретный q-план имеет дополнения или не имеет дополнения, приводящего к меньшему значению z, то из рассмотрения можно исключить 2n q планов и искать оптимальный план среди оставшихся.

Анализ (зондирование) q-плана состоит в: А) нахождении наилучшего дополнения, дающего значение Z меньше, чем полученное ранее; в этом случае определенным образом осуществляется переход к новому q 1 плану; такой план называется расширением q-плана;

Б) установлении факта, что таких дополнений нет; в этом случае другие дополнения или расширения q- плана рассматривать не нужно; присвоение последней переменной значения привело в тупик; осуществляется переход к q 1 плану.

1.6.2 Общая схема алгоритма Балаша

В соответствии со схемой ветвей и границ будем считать шагом метода получение допустимого решения - рекорда k .

В соответствии с алгоритмом Балаша итерацией будем называть включение переменной в q-план.

Возьмем в качестве начальных условий: X 0 0,Y 0 B,Z 0 0,U 0 X 0 ,Y 0 0,B .

Этот план приносит минимальное значение Z , т.к. cj 0, однако этот план имеет отрицательные компоненты вектора Y 0 , если решение не тривиально. Другими словами, те ограничения (5), для которых yi 0 не выполняются.

Переход от пробного плана к плану осуществляется последствием итерации S 1, причем на каждой итерации S получается частичное решение в виде: U S X S ,Y S (8)

Z S CX S (9) Здесь:

xjs

J s

1, j J S

0, j N \ J S j : j N,xjs 1

(10)

(11) yis i aij ,i M (13) j J b

S

Z S j J S cj (14)

Таким образом, алгоритм Балаша должен иметь правила: 27

1) формирования подмножеств J S ,N \ J S ; 2) перехода от итерации S к S 1;

3) определения оптимальности решения или неразрешимости исходной задачи.

Булева переменная xjs называется свободной на S -ой итерации, если ее значение до S -ой итерации не зафиксировано ни нулем, ни единицей и подлежит определению в дальнейшем. Введем обозначения: N S - множество индексов j свободных на итерации s переменных;

M - множество индексов i ограничений, для которых дополнительные переменные yi 0; j - индекс переменной, зафиксированной 1;

j- индекс переменной, зафиксированной 0;

N"- подмножество индексов переменных, составляющих частичное решение;

Ni - множество индексов свободных переменных в ограничении i, которые могут быть включены в частичное решение;

J S - индексы переменных, для которых было сделано назначение единицей.

1.6.3 Правила построения частичного решения

Правило 1.Правило по которому из числа свободных исключаются переменные, усиливающие недопустимости для данной итерации s или шага k .

Если на итерации s переменная xr ,r N s i M i: yi 0 :air 0, то присвоение xr : 1 усиливает недопустимости во всех строках i M . В этом случае на итерацию S переменная xr ,r N S исключается.

В случае, когда air 0 i 1,m переменная xr исключатся насовсем.

Правило 2. Запрет недопустимых вариантов ветвления, когда дополнение частичного решения не может быть получено, т.е. отрицательность yis не может быть устранена.

Если на S хотя бы для одного i M не выполняется неравенство aij yis , где j Ni

Ni j: j N",aij 0 , то данный вариант ветвления отбрасывается и осуществляется переход к (q 1) плану или другому частичному решению.

Если неравенство выполняется, то данный вариант ветвления должен быть развит.

Правило 3. Запрет неперспективных в смысле улучшения рекорда направления ветвления на итерации S и для шага K .

Если был получен рекорд rec и значение целевой функции предыдущего шага z s 1 известно, то для переменной xl ,l N S и при этом cl z s 1 rec, то присвоение переменной xl : 1 на итерации S не улучшит z в сравнении с рекордом, т.е. xl не перспективно и развитие варианта по xl следует прекратить.

Если коэффициент при xl cl сам не меньше рекорда cl rec , то xl не может быть зафиксирован единицей до конца процесса решения задачи.

Правила 1,2,3 формируют на основе N s 1 набор свободных переменных, которые могут быть зафиксированы на итерации S , т.е. N S . Правило 4. Выбор направление ветвления.

28

S

Для выбора направления ветвления используется оценка j , которая есть сумма недопустимостей по переменной j во всех ограничениях i 1,m, которая возникнет, если xj : 1: j m min 0, YIS 1 aij . i 1

Из всех j , j N S выбирается та, которая приносит меньше суммарной недопустимости, т.е. учитывая, то j 0 выбирается максимальное: j* arg max j N

j .

1.6.4 Алгоритм метода Балаша 0) k 0 Записываем начальные условия: N 0 1,2,...,n , X 0 0, Y 0 B, N" , J 0 , n rec z cij 1 j 1

.

1) s 1,2,...

А) образуем M i: yi 0 и проверяем правило 1; при необходимости корректируем N 0 или N s 1 ;

Б) если M , то получаем рекорд.

Записываем: новый рекорд rec min rec,reck для s 1; rec min(reck 1,reck ), записываем X N",Y . Идем на дерево ветвлений.

В) если недопустимости есть, т.е. M , а свободных переменных нет N S , то ветвь тупиковая и исключается из просмотра.

3) Для i M j N S 1 проверяем правило 1.

При необходимости корректируем N S 1 ; если перспективных вариантов нет, то возвращаемся назад и пересчитываем условия.

4) для i M образуем Ni j: j N",aij 0 и проверяем правило 2. 5) Если ранее был получен рекорд, то проверяем правило 3.

Получили набор свободных переменных N S .

6) по правилу 4 для j N S выбираем xj*; Расчитываем для ветвей xj* 1,xj* 0 показатели: А) xj* 1: N S N S \ j*, N" N" j* , J S J S j* , . yis i aij , j J b

S z S z s 1 cj* j J S cj

29

Б) xj* 0: N S N S \ j*, N" N" j* , J S J S , . yis i aij , j J b

S z S z s 1 j J S cj

1.6.5 Сведение ЗЦП в общей постановке к задаче с булевыми переменными

Пусть все условия, необходитмые для метода Балаша выполняются, т.е. задача на минимум, ограничения типа , коэффициенты функции цели неотрицательны, но переменные, все или часть, могут принимать целочисленные значения. Тогда эти переменные можно перевести в булевы, используя следующий прием: 1) пусть известна верхняя граница изменения xj - dj .

2) Для каждой dj можно определить kj , при котором выполняется условие: dj 2k 2k 1 ... 20 2k 1 1.

3) Далее, зная kj каждую переменную xj можно представить в виде двоичного разложения:xj 2k tk 1 2k 1tk 20t1,tk 0,1 .

4) Получив такие двоичные разложения для каждого xj Z подставим их в ЗЦП и получим задачи с бивалентными переменными, решаем ее методом Балаша и по двоичному разложению восстанавливаем xj .

Если коэффициенты cj 0, то tj xj ,cj 0

1 xj ,cj 0

1.7 ПРИБЛИЖЕННОЕ РЕШЕНИЕ. ИСПОЛЬЗОВАНИЕ ТОЧНЫХ МЕТОДОВ И ТОЧНОРЕШАЕМЫХ ЗАДАЧ

Задача целочисленного программирования: Z f (x) max (1) x D (2)

D-допустимое конечное или счетное множество планов, которое задается ограничениями на x x ,x2,...,xn .

1

Если для x условия принадлежности области D выполняются, то решение допустимое x"; если для x" достигается экстремум целевой функции, то решение оптимальное x*.

Любое допустимое решение можно считать приближенным с некоторой точностью.

1.7.1 Оценка качества приближенного решения Абсолютная погрешность решения x" равна: z(x*) z(x") (3).

Относительная погрешность: z x* z x" z x*

(4).

30

Если погрешности равны 0, то приближенное решение является точным. Если абсолютная погрешность не равна нулю, то (3) и (4) служат для оценки качества или точности приближения. n

Запишем функцию цели в виде: f (x) cj xj (5) j 1

При этом если cj одного знака, то использование (3) и (4) являются оправданными. Если cj разных зна-f (x) f1(x) f2(x), ков, то функцию цели можно записать в виде: f1(x) cj xj . j:cj 0 f2(x) cj xj j:cj 0

В этом случае f (x) может оказаться малой разностью больших величин.

Пусть в качестве f (x) используется доход, f1(x) - прибыль, f2(x) - затраты, причем равны соответственно 1001 и 1000 (в оптимальном плане). Тогда f (x*) 1. Требуется оценить приближение f x" 0 через относительную погрешность: 1.

Такая погрешность будет всегда для разности близких величин. И такое положение, не зависящее от слагаемых величин, не допустимо, следовательно, использование (4) здесь не уместно. Для такого случая запишем относительную погрешность: " ff(x*) f2(x*) (6).

(x*) f (x")

1

На этом примере видно, что в каждом конкретном случае оценка решения производится исходя из содержательной постановки задачи и тесно связана с ней.

Все ЗЦП можно разделить на 2 класса: 1) задачи, для которых легко найти допустимые решения, а значит решить приближенно; поиск точного решения задач может быть очень трудным;

2) Задачи, для которых трудно найти допустимое решение, поиск приближенного решения сопоставим по трудностям с нахождением точного решения.

К задачам 1-го класса относятся эвристические алгоритмы поиска приближенного решения. Задачи 2-го класса используют для получения приближенного решения следующие методы: 1) аппроксимация на основе точных методов и точно решаемых задач;

2) методы локальной оптимизации; 3) случайного поиска;

4) случайного поиска с локальной оптимизацией; 5) методы, использующие специфику задачи.

Рассмотрим использование точных методов для построения приближенного решения. Предположим, что задача решается некоторым точным методом и в процессе решения строится последовательность допустимых решений x0,x ,...,xk , упорядоченная по значению целевой функции: 1 f (x0) f (x ) ... f (xk ) f (x*) (7)

1

Если последовательность допустимых решения слишком длинная, то ее можно прервать на любом шаге l и принять xl за приближенное решение.

Например, метод Лэнда и Дойга на каждой большой итерации строит допустимый целочисленный план - рекорд. Если рекорды упорядочить по (7), то прервав последовательность рекордов на любом шаге, получим решение приближенное соответствующей точности.

Метод отсечения Гомори не порождает приближенных решений, т.к. первое допустимое решение является точным решением задачи.

Все методы ветвей и границ порождают приближенное решение.

Пусть f (x*) - рекорд, z - верхняя граница целевой функции.

31

Тогда точное решение будет в интервале f (xk ) f (x*) z.

Таким образом, методы ветвей и границ порождают не только приближенное решение, но и дают оценку их отклонения от оптимума (если известно z).

1.7.2 Использование точно решаемых задач для получения приближенного решения

В рамках метода ветвей и границ используется прием релаксации ограничений. Применительно к ЗЦП он состоит в отбрасывании условия целочисленности и в переходе к задаче ЛП.

Задача ЛП решается точно, и если исходная задача на максимум, то получается соответствие: f (x") f (xo ) f (XCEI ).

Аналогичным образом, задача о назначении может быть использована при релаксации задачи коммивояжера путем отбрасывания условия запрещения подциклов.

32