Динамическое программирование (стр. 10 из 10)

В) если недопустимости есть, т.е. M

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

3) Для i

проверяем правило 1.

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

4)

для i образуем ^N_i j : j N', ^a_ij 0 и проверяем правило 2.

5) Если ранее был получен рекорд, то проверяем правило 3.

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

6)

по правилу 4 для j N ^S выбираем ^x_j*;

Расчитываем для ветвей ^x_j* 1, ^x_j* 0 показатели: А) x _j* 1 :

N

N'

J.

y

z _j

Б) x

N

N'

J. y

zj

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

Пусть все условия, необходитмые для метода Балаша выполняются, т.е. задача на минимум, ограничения типа

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

2)

Для каждой ^d _j можно определить ^k _j , при котором выполняется условие: d j 2 k 2 k 1 ... 2 0 2 k 1 1 .

3)

Далее, зная ^k _j каждую переменную ^x_j можно представить в виде двоичного разложения: x j 2 k tk 1 2 k 1 tk 2 0 t1 , tk 0,1 .

4)

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

Если коэффициенты ^c_j 0 , то ^t _j

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

Задача целочисленного программирования:

Z max (1)

x(2)

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

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

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

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

Относительная погрешность: (4).

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

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

c ^x_j (5)

При этом если ^c _j одного знака, то использование (3) и (4) являются оправданными. Если ^c _j разных зна-

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

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

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

пишем относительную погрешность: ' (6). f₁( x*) f₂( x*)

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

Все ЗЦП можно разделить на 2 класса:

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

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

К задачам 1-го класса относятся эвристические алгоритмы поиска приближенного решения.

Задачи 2-го класса используют для получения приближенного решения следующие методы:

1) аппроксимация на основе точных методов и точно решаемых задач;

2) методы локальной оптимизации;

3) случайного поиска;

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

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

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

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

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

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

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

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

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

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

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

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

f ( x ^ö ) f ( x ^ÇËÏ ) .

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

32