JUN Jan Feb 15 2007 2009 2010 14 captures 14 Apr 05 - 15 Jan 09

Close Help

4. СПОСОБЫ РЕШЕНИЯ ПЕРЕБОРНЫХ ЗАДАЧ

Литература:

2. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. М.: Мир, 1985.

6. Мину М. Математическое программирование. М.: Наука, 1990.

§ 10. Глобальная оптимизация. Метод ветвей и границ

Случайный и последовательный перебор. Метод ветвей и границ в глобальной оптимизации. Описание и стратегии метода.

1. Как уже отмечалось ранее, задачи глобальной оптимизации (т.е. в невыпуклом случае задачи оптимизации вообще) являются переборными. Переборные алгоритмы не эффективны (в расчете на худшую задачу), поэтому успех в решении каждой конкретной задачи существенным образом зависит от способа организации перебора. Если мы готовы оставить возможность или невозможность решения нашей задачи на волю случая, то естественно использовать случайный перебор. Этот способ перебора обычно является самым простым и, как правило, экономит память. Для задачи поиска глобального минимума ему соответствует следующий метод Монте-Карло.

Пусть решается задача (1) из § 8, где (для упрощения изложения) множество ограничений X - единичный n-мерный куб. Выбираем в соответствии с равномерным распределением на X случайные точки x^t, в которых вычисляем значение целевой функции, запоминаем текущее наименьшее значение - рекорд - и реализующую его точку. Тогда "e > 0 вероятность

P(| min t  f(xt)-f*| > e)® 0 при t®Ґ.

Сходимость такого метода будет довольно медленной. При этом не известно, на каком расстоянии от точки минимума находится полученная реализация.

Сузим класс рассматриваемых задач (1), предположив вдобавок к предыдущему, что функция цели липшицева на X с константой L: f О Lip(X,L), т.е. |f(x)-f(xў)| Ј L||x-xў|| "x,xў О X. И не рассчитывая найти точное решение, зададимся подходящим e > 0 с целью поиска e-приближенного решения x^e:  f(x^e) Ј f(x^*)+e. (На близость x^e и x^* никаких условий не накладывается.)

Теперь мы можем применять методы детерминированного перебора. Пассивный (не использующий при выборе очередной точки информацию, полученную для предыдущих) способ поиска приводит к полному перебору: разобьем X на подкубы X^j так, чтобы "x,xў О X^j:   ||x-xў|| Ј d=e/L, в каждом X^j берем произвольную точку x^j и полагаем

f(xe)= min j  f(xj).

Очевидно, x^e и есть искомое e-приближенное решение. (Действительно, "j, "x О X^j  f(x^e) Ј f(x^j) Ј f(x)+e по условию Липшица, и, в частности, для x = x^* имеем f(x^e) Ј f(x^*)+e - соответствие с определением.) Однако сторона каждого j-го подкуба равна e/(LЈn), а всего подкубов и, следовательно, вычислений значений целевой функции будет (LЈn/e)ⁿ в любом случае, чт'о не мыслимо даже для десятка переменных. Поэтому разрабатываются методы последовательного перебора, позволяющие учитывать уже вычисленные значения и адаптироваться к нехудшему случаю.

Предположим, что уже вычислены значения функции в точках x¹,ј,x^j-1 и рекордным оказалось значение f(x^r) = R. Тогда, если f(x^j) < f(x^r), то обновляем рекорд r: = j, R: = f(x^j), а если f(x^j) > f(x^r), то можно не вычислять значений функции на множестве T_j(R)={x О X: ||x-x^j|| Ј (f(x^j)-R)/L}, так как это не даст нового рекорда (ибо "x О T_r  f(x^j)-f(x) Ј L||x-x^j|| Ј f(x^j)-f(x^r), т.е. f(x) і f(x^r) = R, и значит, среди них нет глобально-оптимального решения). Обновление рекорда в принципе позволяет ``отбросить" аналогичные множества T_i(R) для i = 1,ј,j-1.

Естественно, в T_i, T_j могут попасть и точки x^k с уже вычисленным значением f(x^k) (которые таким образом вычислялись зря). Поэтому хотелось бы так организовать перебор, чтобы по возможности уменьшить число подобных ``зряшных" вычислений. К сожалению, оптимальной стратегии организации перебора для многомерных задач нет. Использование случайных точек xⁱ приводит к проблеме хранения и обновления сложного множества ИT_i(R) заведомо не оптимальных точек. Метод послойного перебора дает возможность сокращения лишь по одной переменной. Для задач большой размерности предлагается (различными авторами) следующий метод перебора по схеме ветвей и границ.

2. Метод ветвей и границ (МВГ) для глобальной минимизации.
Пусть x¹ - центр куба X. Вычисляем f(x¹) и присваиваем это значение рекорду R: = f(x¹). Разбиваем куб на 2ⁿ одинаковых подкубов X¹ⁱ со стороной 1/2 и вычисляем значения целевой функции в их центрах: f(x¹ⁱ), i = 1,ј,2ⁿ, обновляя по ходу вычислений значение рекорда R: = min_if(x¹ⁱ). Проверяем выполнение условия X¹ⁱ Н T_1i(R), i = 1,ј,2ⁿ и отбрасываем соответствующие подкубы. Каждый из оставшихся разбиваем на 2ⁿ одинаковых подкубов X^2ij со стороной 1/4 и поступаем, как прежде. На любом шаге у нас формируется множество K ``кубиков" со сторонами 2^-l, l і 2, целое. Правило выбора очередного кубика для разбиения называется правилом ветвления - возможные варианты приводятся ниже. Кубики со стороной не больше e/(LЈn) исключаются из множества K - дробление кубика заканчивается. Также исключаются кубики, попавшие в множество T_k(R) (с индексом k - номером кубика) для текущего значения рекорда, - правило отсечения ветвей. Рекорд обновляется при получении меньшего значения целевой функции (правило получения границ, т.е. оценок). Значения целевой функции вычисляются в центре каждого нового подкубика, включаемого в K после разбиения выбранного для этого кубика. Алгоритм останавливается, когда K пусто.

Указанная терминология и название метода определяются тем, что визуально данная схема перебора представляется в виде графа-дерева, корневая вершина которого соответствует кубу X, вершины первого яруса - подкубам X¹ⁱ, вершины второго яруса - кубикам X^2ij, подсоединенным к своим порождающим вершинам X¹ⁱ 1-го яруса, и т.д. Если кубик исключается из K, его вершина закрывается - из нее не будут идти ветви на следующий ярус. Если кубик еще не включен в K, его вершина еще не раскрыта. Порядок закрытия вершины определяется правилом отсечения (своим для каждой массовой задачи - см. также в § 11), порядок раскрытия - правилом ветвления (своим для каждой индивидуальной задачи). Различают два вида правил ветвления по типу построения дерева решений (выбора вершин для раскрытия): ``в ширину", когда сначала раскрываются все вершины одного яруса до перехода к следующему, и ``в глубину" - всякий раз раскрывается лишь одна (обычно с лучшим значением рекорда) вершина на ярусе до конца ветви. На практике реализуют некоторую смесь, например, первое правило, пока хватает машинной памяти (в K не слишком много элементов), затем переключаемся на второе. Предпочтительность той или иной стратегии ветвления оценивается каждым вычислителем по-своему, исходя из главной задачи метода ветвей и границ - быстрее получить лучший рекорд, чтобы отсечь больше ветвей.

В рассматриваемой задаче есть хороший способ улучшения рекорда - локальная оптимизация (см. в § 8). Ее имеет смысл проводить из текущей точки, в которой произошло обновление рекорда, например, делая несколько шагов градиентного метода. При этом расположение кубиков менять не надо, просто увеличивается шанс сокращения перебора (отбрасывания б'ольших кубиков).

Отметим, что в худшем случае f = const (ИT_i = Ж) - не удается отбросить ни одной точки x - и приходим к полному перебору; т.е. указанная в п.1 экспоненциальная оценка точна на классе всех липшицевых функций.

§ 11. Целочисленное линейное программирование (ЦЛП)

Отличие задач ЦЛП и ЛП: существенная нелинейность ограничений типа целочисленности. Неэффективность округления решения ЛП до ближайшего целого. Случай вполне унимодулярной матрицы ограничений. МВГ в ЦЛП. МВГ для булева линейного программирования (БЛП).

1. По-видимому, наиболее важным классом задач глобальной оптимизации являются задачи ЦЛП. Эти задачи формулируются как задачи ЛП с дополнительным ограничением целочисленности переменных. Последнее ограничение, какими бы способами от него ни избавляться, ``портит" свойство выпуклости (и полиномиальности) задачи ЛП. Например, выразив условие целочисленности в форме ограничений неравенств, рассмотренной в доказательстве утверждения 1 § 8, и сняв их методом штрафов, придем к задаче глобальной оптимизации, имеющей не меньше локальных экстремумов, чем вариантов для целочисленных переменных в исходной ЦЛП. Поэтому на практике удается решать задачи ЦЛП только небольшой размерности или с ограничениями целочисленности не на все, а лишь на несколько переменных.

Существует частный класс задач ЦЛП, в которых ограничение целочисленности оказывается несущественным.

Определение 1. Матрица называется вполне унимодулярной, если определитель любой ее невырожденной квадратной подматрицы равен по модулю 1.

Утверждение 1. Если матрица ограничений разрешимой задачи ЛП с целыми коэффициентами вполне унимодулярна, то у нее существует целочисленное решение.

Доказательство очевидно из принципа граничных решений (§ 5) и правила Крамера (см. доказательство теоремы 1 § 5).

Утверждение 2. Матрица A вполне унимодулярна тогда и только тогда, когда для любого целочисленного вектора b все вершины многогранника Ax Ј b, x і [`0] являются целочисленными.

Доказательство в одну сторону аналогично предыдущему, в другую сторону см. ссылку в [2, с. 333].

Таким образом, вполне унимодулярными матрицами ограничений в принципе ограничивается класс задач ЦЛП, эквивалентных ЛП и, следовательно, допускающих эффективное решение. Отметим, что указанный класс, хотя и чрезвычайно узок с формальной точки зрения (элементами матрицы A могут быть только 0, 1 и -1, причем по большей части 0), соответствует достаточно широкому классу практических задач оптимизации на графах и сетях (одно- и двухпродуктовые сети, двудольные графы и т.п.).

Приведем без доказательства еще одно полезное утверждение, позволяющее в некоторых случаях получать приближенное решение ЦЛП путем решения ЛП.

Утверждение 3. Если все элементы симплекс-таблицы a_ij, b_i, c_j натуральные числа, то для любого решения x⁰ задачи ЛП

max Ax Ј b, x і [`0]  бc,xс

вектор лx⁰ы, составленный из компонент лx⁰_jы, будет допустимым в данной задаче. При этом для решения x^* соответствующей задачи ЦЛП

max Ax Ј b, x О Zn+  бc,xс

очевидна оценка |бc,лx⁰ыс- бc,x^*с| Ј бc,[`1]с.

Условие положительности исходных данных выполняется для некоторых экономических задач. Такой же результат можно получить для ряда многопродуктовых потоковых задач на сетях и других линейных задач максимизации с положительным c, в которых допустимое множество вместе с любой точкой x содержит и все xў с компонентами xў_j О [0,x_j]. Однако поиск x^* по лx⁰ы может потребовать перебора 2ⁿ вариантов округления компонент x⁰.

К сожалению, в общем случае и перебора всех возможных вариантов округления компонент решения непрерывной задачи ЛП оказывается недостаточно для получения решения ЦЛП (например, при n = 2, если для положительного c рассмотреть систему ограничений -9x₁+10x₂ Ј 0, -8x₁+10x₂ Ј -1). Таким образом, поиск решения ЦЛП может потребовать очень большого перебора целочисленных точек, и возникает та же, что и в § 10, задача организации перебора с целью попытаться его сократить в случае не самой плохой задачи. Одним из достаточно употребительных методов перебора здесь является метод ветвей и границ, который для ЦЛП будет рассмотрен в п.2. Другие методы см. в [2,6].

2. Метод ветвей и границ для ЦЛП. Рассматривается задача

max z О Zn: Az Ј b  бc,zс,

(1)

решением которой является целочисленный вектор z^*.

В корневой вершине метода вместо задачи (1) решается озЛП

max x О Rn: Ax Ј b  бc,xс,

(2)

решением которой является вектор x⁰. Если x⁰ оказался целочисленным, то z^*:=x⁰ - решение задачи (1) закончено. Иначе $x⁰_j П Z и осуществляем ветвление по j-й компоненте следующим образом.

Из вершины выходят две ветви, и на новом ярусе к ограничениям озЛП, решаемой в порождающей вершине, добавляется ограничение x_j Ј лx⁰_jы для 1-й ветви или x_j і йx⁰_jщ для 2-й ветви. Значение максимума в исходной задаче ЦЛП (1), очевидно, равно максимальному из значений подзадач ЦЛП на каждой ветви. Но, как и ранее, вместо подзадачи ЦЛП рассматривается подзадача без ограничения целочисленности. Такая озЛП и решается в очередной порожденной вершине в случае ее раскрытия, обозначим решение через x^k.

Если x^k - целочисленное, то вершина закрывается, а значение бc,x^kс функции цели сравнивается с рекордом для его обновления или, по первому разу, присваивается рекорду, и точка x^k - допустимая точка в задаче (1) - запоминается. После получения рекорда может быть закрыта любая раскрытая вершина, для которой оптимальное значение целевой функции окажется меньше рекорда. Действительно, поскольку максимум по большему множеству не меньше максимума по меньшему, то значение озЛП дает оценку сверху (границу) значения соответствующей целочисленной подзадачи, и когда верхняя оценка не превышает рекорда, бессмысленно пытаться увеличить рекорд на данной ветви.

Другим случаем закрытия вершины (отсечения ветви) является неразрешимость поставленной озЛП и, следовательно, той же подзадачи ЦЛП. Заметим, что для проверки неразрешимости не всегда надо решать задачу, несовместными могут сразу при формулировке оказаться, например, ограничения x_j і йx^k-l_jщ, оставшиеся с одного из предыдущих ярусов, и x_j Ј лx^k_jы, добавленные снова.

Если x^k - нецелочисленное, то $x^k_i П Z, и осуществляем ветвление по i-й компоненте описанным выше способом. Процедура заканчивается после закрытия всех вершин, тогда значение (1) равно текущему рекорду, либо рекорд остался неопределенным и задача (1) не имеет решения.

Выбор стратегии ветвления в ЦЛП играет не меньшую роль, чем в глобальной оптимизации. Отсутствие рекорда приводит к лишнему перебору, но процедура ветвления ``в глубину" может вместо рекорда дать несовместную систему ограничений. Кроме того, для нескольких нецелых компонент x^k не понятно, по какой из них лучше осуществлять ветвление: по новой, которая не рассматривалась на предыдущих ярусах, или сначала перебрать все допустимые целые значения одной из компонент (по аналогии с БЛП - см. ниже). Последняя стратегия имеет смысл при наличии двусторонних ограничений на переменные.

3. Метод ветвей и границ для БЛП. Частным случаем задачи (1) ЦЛП является задача БЛП

max z О Bn: Az Ј b  бc,zс,

(3)

решение которой - вектор z⁰ из булева куба.

Из результатов § 2 (утверждения 8) вытекает NP-трудность БЛП и, следовательно, правомерность использования переборных схем для решения (3). В § 12 будет показана схема динамического программирования для БЛП с неотрицательными коэффициентами, а для произвольных задач (3) применима схема предыдущего пункта, которая несколько упрощается за счет дополнительного ограничения 0 Ј z_i Ј 1, превращающего ЦЛП в БЛП. А именно, после замены Zⁿ на Bⁿ, при ветвлении в новые подзадачи добавляется вместо ограничений неравенств условие равенства 0 (для одной ветви) или 1 (для другой) той переменной, по которой осуществляется ветвление. Таким образом указанная переменная становится булевой во всех нижних ярусах, т.е. по ней не придется вновь проводить ветвление, а значит, на n-м ярусе решение (3) будет закончено. Число раскрываемых вершин (или решений подзадач ЛП) при этом не превысит 2ⁿ⁺¹, что, конечно, тоже немало, но заметно меньше, чем для ЦЛП (сравнимо со случаем, предусмотренным утверждением 3).

§ 12. Метод динамического программирования (ДП)

Теоретические основы ДП. Общая схема метода. Метод ДП для БЛП с неотрицательными коэффициентами. Связь с МВГ.

1. Еще одной традиционно используемой схемой перебора является метод динамического программирования (ДП). Один пример алгоритма ДП приводился в § 4, где этод метод позволил построить псевдополиномиальный алгоритм решения задачи о рюкзаке. Вообще говоря, подобные алгоритмы и надеются получить путем применения схемы ДП. Однако ДП можно использовать не для произвольных оптимизационных задач. Класс подходящих задач опишем далее.

Определение 2. Функция f называется разделяемой на f₁ и f₂, если она представима в виде

f(x,y) = f1(x,f2(y)).

(4)

Определение 3. Функция f называется разложимой на f₁ и f₂, если она разделяема на f₁, f₂ и функция f₁ монотонно не убывает по последнему аргументу.

Теорема 1 (оптимальности для разложимых функций).

min (x,y)  f(x,y) = min x  f1(x, min y  f2(y)),

и точно так же для max.

Доказательство проведем для случая минимума.
(Равенство будет вытекать из пары противоположных неравенств.)

По определению минимума   min x,y  f1(x,f2(y)) Ј f1(x0,f2(y0))   "x0, y0

и, следовательно, для  y0: = arg min y  f2(y),  x0: = arg min x  f1(x, f2(y0)),

что доказывает неравенство `` Ј ". Аналогично, в силу неубывания f₁ по последнему аргументу,  f₁(xў,min_y f₂(y)) Ј f₁(xў,f₂(yў))  "xў, yў.

Положим   yў: = arg min y  f1(xў,f2(y)),  xў: = arg min x  { min y  f1(x,f2(y))}.

Поскольку повторный min равен двойному, в правой части получили min_x,y f(x,y), чем доказали и неравенство `` і ".

Для задачи условной оптимизации теорема оптимальности для разложимых функций переписывается следуюшим образом:

min (x,y) О W  f(x,y) = min x: Y(x) № Ж  f1(x, min y О Y(x)  f2(y)),

(5)

где Y(x) = {y| (x,y) О W}. Указанная теорема используется для понижения размерности оптимизационных задач и в методе ДП.

Для начала рассмотрим задачу оптимизации, записанную в виде

f* = min g(x,y) О ET М Rm  f(x,y),  x О X Н Rn, y О Y(x) Н Rk.

(6)

Здесь E_T называется множеством терминальных состояний системы по ассоциации с динамическими системами управления, для оптимизации которых было изобретено ДП. Например, для g = (g₁,ј,g_m), если ограничения задачи заданы в форме  g_i (x,y) Ј 0  "i = [`1,m],  то E_T = R^m_-.  Пусть f разложима (4), а g разделяема:

g(x,y) = h2(y,h1(x)),  h1: Rn®Rm,  h2: Rk+m ®Rm,

тогда введем "x,y  E = h₁(x),  Eў = h₂(y,E) и вычисляем g как g(x,y) = Eў. Функции h₁, h₂ называются функциями перехода, векторы E, Eў - состояниями системы. Множество всех возможных состояний системы обозначается E и формально задается так:

1) E Ј h₁(X)={h₁(x)| x О X},

2) "E О E  {h₂(y,E)|y О Y(X)} М E
(множество в качестве аргумента означает объединение по всем аргументам из этого множества).

Рассмотрим для (6) семейство задач поиска

F2(E) = min y: h2(y,E) О ET  f2(y),

которые нужно решать "E О E. По теореме оптимальности

f* = min x О X  f1(x,F2(h1(x))).

В результате задача (6) свелась к последовательности |E|+1 оптимизационных задач меньшей размерности.

В методе ДП данная процедура применяется рекурсивно к задаче

F* = min g(x1,ј,xn) О ET М Rm  f(x1,ј,xn)

(7)

для сведения к семейству одномерных задач следующим образом.

Пусть f последовательно разложима, т.е.

f(x1,ј,xn) = f1(x1, ^ f   2  (x2,ј,xn)), ^ f   2  (x2,ј,xn) = f2(x2, ^ f   3  (x3,ј,xn)), јјјјјј јјјјјјј ^ f   n-1  (xn-1,xn) = fn-1(xn-1,fn(xn)),

и все f_i монотонно не убывают по 2-му аргументу. Пусть g последовательно разделяема, т.е. $E М R^m,  $ функции перехода h₁,h₂,ј,h_n: "x О X = -X_i g(x) = h_n(x_n,E_n-1), E_n-1 = h_n-1(x_n-1,E_n-2),ј, E₂ = h₂(x₂,E₁), E₁ = h₁(x₁) и E_i О E  "i = [`(1,n-1)].

Обозначим "i = [`(2,n-1)],  "E О E через [^h]_i(x_i,x_i+1,ј,x_n,E) функцию, определяемую рекуррентно равенствами:  Eў_i = h_i(x_i,E), Eў_i+1 = h_i+1(x_i+1,Eў_i), ј, Eў_n = h_n(x_n,Eў_n-1)=[^h]_i(x_i,x_i+1,ј,x_n,E). Заметим, что в случае E = E_i-1:  [^h]_i(x_i,x_i+1,ј,x_n,E_i-1) = g(x) и Eў_j = E_j   "j і i. В сделанных обозначениях справедливо возвратное соотношение для ограничений

^ h   i  (xi,xi+1,ј,xn,E) = ^ h   i+1  (xi+1,ј,xn,hi(xi,E)).

(8)

Тогда по определению

F* = min x О X: [^h]2(x2,ј,xn,h1(x1)) О ET  f1(x1, ^ f   2  (x2,ј,xn)),

и по теореме оптимальности

F* = min x1 О X1  f1(x1,F2(h1(x1))),

(9)

где  "E1 О E  F2(E1)= min (x2,ј,xn): [^h]2(x2,ј,xn,h1(x1)) О ET  ^ f   2  (x2,ј,xn) =

(из (8))   = min (x2,ј,xn): [^h]3(x3,ј,xn,h2(x2,E1)) О ET  f2(x2, ^ f   3  (x3,ј,xn)) =

= min x2 О X2  f2(x2,F3(h2(x2,E1)))

(последнее равенство следует из (5) с x = x₂, y = (x₃,ј,x_n)),
и т.д., полагая минимум по пустому множеству равным +Ґ, имеем

Fi(E)= min [^h]i(xi,xi+1,ј,xn,E) О ET  ^ f   i  (xi,xi+1,ј,xn)  "i,E

(10)

- семейство задач, в которое ``погрузили" (7),

Fi(Ei-1) = min xi О Xi  fi(xi,Fi+1(hi(xi,Ei-1)))  "Ei-1 О E

(11)

- возвратное (функциональное) уравнение ДП  "i = [`(2,n-1)],

Fn(E) = min xn О Xn: hn(xn,E) О ET  fn(xn).

(12)

Алгоритм ДП:

"E О E вычисляем F_n(E) из (12),

последовательно для i = n-1,ј,2 определяем F_i(E) из (11),(10),

затем F^* из (9).
Число шагов алгоритма (решений задач одномерной минимизации) будет порядка n|E|. Таким образом метод ДП имеет смысл применять для задач с не очень большим числом состояний (|E| мал'о).

2. Примерами разложимых функций могут служить min, max, сумма, произведение (с неотрицательными коэффициентами) и т.п. Исходно метод ДП использовался для оптимизации динамических систем, что нашло отражение в применяемой терминологии. Так, E соответствует физическому пространству состояний (возможных координат траектории движения), x_i - управлению в момент времени t_i, воздействие управления на траекторию определяется функцией перехода в следующее состояние, на конечное состояние наложены ограничения принадлежности к E_T, начальное состояние фиксировано; f_i(x_i,E) - стоимость управления системой, находящейся в состоянии E, f - стоимость всей траектории E₁,ј,E_n-1.

Соотношение (11) означает минимизацию стоимости ``хвоста" траектории в каждый момент времени, что согласуется с принципом оптимальности, сформулированным Р. Бэллманом: оптимальная политика управления такова, что для любого начального состояния и любых решений (по выбору управления), принятых на начальных шагах, оставшиеся решения образуют оптимальную политику, начинающуюся с состояния, возникшего в результате этих решений. (Отметим, что в случае строгой монотонности f таким образом можно получить любое решение, в случае нестрогой монотонности - хотя бы одно).

Проиллюстрируем применение метода ДП на примере решения задач БЛП с неотрицательными коэффициентами (элементами симплекс-таблицы). Итак, вернемся к задаче (3)

F* = max z О Bn: Az Ј b  бc,zс

в предположении a_ij, b_i, c_j О Zⁿ₊. Обозначим через [`a]_j  j-й столбец матрицы A. Рассмотрим семейство задач поиска

Fk(E)= max z: zj О {0,1} "j = k,ј,n  n е j = k  cj zj

n е j = k  _ a   j  zj Ј b-E,

где E О E={E О Zⁿ₊| E_i Ј b_i "i = [`1,m]},  k = [`1,n].

Очевидно, F^* = F₁(0). Возвратное уравнение в данном случае:

Fk(E) = max {Fk+1(E), ck + Fk+1(E+ _ a   k  )},

Fn(E) = м п н п о cn, E Ј b- _ a   n  , 0 иначе.

Находим "E О E  F_n(E) и соответствующие x_n(E), затем для k = n-1,ј,2 определяем F_k(E) и реализующие их x_k(E) из возвратного уравнения, вычисляем F₁(0), x₁(0) и далее x₂(E¹),ј,x_n(E^n-1) в зависимости от того, какие состояния E¹,ј,E^n-1 были в конечном счете использованы при вычислении F₁(0), если посмотреть по всем шагам алгоритма.

Число шагов предложенного алгоритма равно n и на n-м шаге рассматривается min{(b₁+1)·ј·(b_m+1), 2^n-1} состояний, на (n-1)-м - минимум из левой части (равной |E|) и 2^n-2 и т.п. Так что при больших b метод ДП решает примерно столько же задач, сколько МВГ в худшем случае, однако решаемые задачи здесь проще (проверка ограничений вместо ЛП). Подчеркнем, что процедура ДП не дает способов сокращения перебора, тогда как удачный выбор стратегии ветвления в МВГ (например, на основе имеющейся у вычислителя дополнительной информации или эвристических соображений) позволяет (хотя и не гарантированно) решать задачи большей размерности. Отметим также отсутствие ограничения неотрицательности коэффициентов для работы МВГ. В принципе, возможно комбинирование обеих схем (см. [6]).