💸 Как сделать бизнес проще, а карман толще?

Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

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

В каждой из рассматриваемых ниже задач оптимальное решение в принципе может быть получено полным перебором возможных вариантов с подсчетом значения оптимизируемого критерия для каждого из таких вариантов. Множество вариантов конечно, но число их, как правило, уже при относительно малых размерностях решаемых задач оказывается столь большим, что полный перебор практически неосуществим. Использование схемы динамического программирования дает возможность определенным образом упорядочить перебор, существенно сократив при этом число подлежащих рассмотрению вариантов.

Задача оптимального распределения капиталовложений (ЗОРК). Имеются денежная сумма (капитал) C и возможные сферы вложений S₁, S₂, …, S_n. Считается, что в каждую сферу S_t может быть вложен целочисленный вклад, не превосходящий константы С_t. Для каждой сферы S_t полагается известной монотонно возрастающая в нестрогом смысле функция f_t(u), определяющая величину дохода, получаемого при вложении в данную сферу вклада u. Требуется определить обеспечивающее максимальный суммарный доход распределение суммы С или ее части по сферам вложений.

Математическая модель задачи следующая:

при условиях:

;

u_t Î {0, 1, …, С_t}, t = 1, …, n.

Покажем, что сформулированную задачу можно трактовать как задачу поиска полной траектории, обеспечивающей максимальный суммарный доход в соответствующим образом построенной дискретной управляемой системе. Исходные данные ЗОРК определяют систему Ω (ЗОРК), управления в которой осуществляется в дискретном времени t = 0, 1, 2, …, n – 1 (в момент t определяется вклад в сферу S_t+1). Состояния системы - пары (t, U), где t – момент дискретного времени, а U – сумма, которая к данному моменту еще не распределена, здесь t Î {0, 1, …, n}, U Î {0, 1, …, С}. Начальное состояние системы (0, C); финальными являются состояния вида (n, U). В любом нефинальном состоянии (t, U) выбор реализуемого в этом состоянии управления u_t+1 осуществляется из совокупности V(t, U) = {0, 1, …, min(С_t+1, U)}; выбранная величина u_t+1 – размер вклада в сферу S_t+1 Под воздействием управления u_t+1 система Ω (ЗОРК) из состояния (t, U) переходит в состояние (t + 1, U – u_t+1), получаемый при этом доход равен f_t+1(u_t+1). Каждая последовательность управлений, переводящая систему из начального состояния в одно из финальных состояний, определяет некоторое допустимое решение ЗОРК (распределение (u₁, u₂, …, u_n) капиталовложений). Исходную ЗОРК трактуем как задачу отыскания траектории системы Ω (ЗОРК), обеспечивающей максимальный суммарный доход.

Функция Беллмана для системы Ω (ЗОРК) определяется соотношениями

В(n, U) = 0, U Î {0, 1, 2, …, С}; (10)

(11)

здесь t Î {0, 1,, …, n – 1}, U Î {0, 1,, …, С}.

При реализации обратного метода Беллмана процесс вычислений реализуется в соответствии с записанными соотношениями. Зная, что В (n, U) = 0 при всех U, по формуле (11) находим все значения В (n – 1, U) при U Î {0, 1, …, S }; здесь оказывается справедливым тождество В (n – 1, U) = f_n (min(С_n, U)). Далее, имея вычисленными значения В (n – 1, U), по той же формуле (11) определяем все значения В (n – 2, U), где U Î {0, 1, …, S }, и т.д. до тех пор, пока не окажется найденной величина В (0, С) – оптимальное значение критерия в решаемой ЗОРК. В процессе вычислений, с целью обеспечения возможности определить оптимальное распределение капиталовложений, после отыскания каждого следующего значения В (t, U), где t Î {0, 1,, …, n – 1} и U Î {0, 1, …, С }, для пары (t, U) отдельно фиксируем значение u_{t +1}, на котором достигается максимум правой части (11).

Прямой метод Беллмана для решения ЗОРК заключается в последовательном вычислении значений функции В* (t, U) в порядке возрастания значений первого аргумента. При этом

В* (0, U) = 0, U Î {0, 1,, …, С}; (12)

(13)

здесь t Î {0, 1, …, n – 1}, U Î {0, 1,, …, С }. Основанные на формуле (13) вычисления заканчиваются отысканием величин В* (n, U), где U Î {1, 2, …, С }; максимальная из найденных величин – оптимальное значение критерия в решаемой ЗОРК.

Пример 1.3. Имеются сферы капиталовложений S ₁, S ₂, S ₃, S ₄; в каждую из них может быть внесен целочисленный вклад, не превосходящий 5. Величина подлежащего распределению капитала равна 6. Функции, определяющие доходы, получаемые при вложении в различные сферы вклада u, заданы табл. 1.1. Требуется найти оптимальное распределение капитала между сферами вложений.

Решение данного примера можно выполнить как прямым, так и обратным методом Беллмана. Будем основываться на рекуррентных соотношениях (10)–(11), т.е. применим обратный метод. Отыскиваемые в процессе счета значения функции В (t, U) вносим в табл. 1.2. В каждую заполняемую клетку (t, U) этой таблицы (параметр t определяет столбец, параметр U – строку) одновременно с В (t, U) вносится и записанное в квадратных скобках значение u_{i +1}, на котором достигается максимум правой части (11) при подсчете В (t, U); если таких значений несколько, вносится любое из них (нашей целью является отыскание какого-либо из оптимальных решений, а не полной их совокупности).

Таблица 1.1 Значения функций дохода f_t (u)

Таблица 1.2 Значения функции В (t, U)

В связи с тем, что В (4, U) тождественно равно нулю, процесс вычислений начинаем с определения значений В (3, U) при всех возможных значениях U. Из равенства (11) следует, что В (3, U) = f ₄(U) при U = 0, 1, 2, 3, 4, 5 и В (3, 6) = f ₄(5). Так заполняется последний столбец табл. 1.2. То же равенство (11) дает возможность последовательного (справа налево) заполнения остальных столбцов. Заметим, что для решения задачи в первом столбце достаточно найти только один, нижний элемент. В рассматриваемом примере оказалось, что В (0, 6) = 0, 8. Это оптимальное значение критерия (максимально возможный доход). В клетке (0, 6) в квадратных скобках записано число 1. Значит, в оптимальном распределении капиталовложений взнос в первую сферу должен равняться единице. В таком случае суммарный взнос в остальные сферы не превосходит 5. В клетке (1, 5) в квадратных скобках записано число 3. Значит, в синтезируемом оптимальном распределении капиталовложений взнос во вторую сферу равняется трем. Получаем, что суммарный взнос в третью и четвертую сферы не превосходит 2. В клетке (2, 2) в квадратных скобках записано число 2. В оптимальном распределении взнос в третью сферу должен равняться двум. В итоге получаем, что оптимальное распределение делит сумму С = 6 между первой, второй и третьей сферами капиталовложений; вносимые в них вклады равны соответственно 1, 3, 2. При этом первая сфера приносит доход 0, 2; вторая сфера дает доход 0, 4 и третья сфера - доход 0, 2. Суммарный доход действительно равен 0, 8.

Задача о выборе траектории набора высоты и скорости (ЗВТНВС). Летательный аппарат, в начальный момент имеющий скорость V ₀ и высоту Н ₀, должен быть поднят на высоту Н ₁, а скорость его должна достигнуть значения V ₁; здесь V ₁ > V ₀ и H ₁ > Н₀. Считаются известными функции F (V, Н) и G (V, Н), определяющие соответственно дополнительный расход горючего при увеличении скорости полета с V до V + 1 при неизменной высоте полета Н и при увеличении высоты полета от Н до Н + 1 при неизменной скорости полета V.

Предполагается, что числа V ₀, Н ₀, V ₁, Н ₁ – целые и что процесс набора высоты и скорости можно разбить на ряд последовательных этапов, результатом каждого из которых является увеличение на единицу одного из параметров полета, высоты или скорости. В таком случае функция F (V, Н) определена для значений V Î { V ₀, V ₀ + 1, V ₀ + 2, …, V ₁ – 1} и Н Î { Н ₀, Н ₀ + 1, Н ₀ + 2, …, Н ₁}; функция G (V, Н) определена для значений V Î { V ₀, V ₀ + 1, V ₀ + 2, …, V ₁ } и Н Î { Н ₀, Н ₀ + 1, Н ₀ + 2, …, Н ₁ – 1}; можно считать эти функции заданными таблично. Требуется найти режим набора высоты и скорости, при котором общий расход горючего будет минимальным.

Исходные данные рассматриваемой задачи определяют систему Ω (ЗВТНВС), управление которой осуществляется в дискретном времени; управление определяет, значение какого параметра полета, высоты или скорости, в создавшейся ситуации следует увеличить на единицу. Состояния системы – пары целых чисел (V, Н), где V – достигнутая скорость, а Н – имеющаяся высота полета. Начальное состояние системы (V ₀, Н ₀); финальным является состояние (V ₁, Н ₁). Пусть В (V, Н) – минимально возможный расход горючего, при котором значения скорости и высоты полета могут быть увеличены от V и Н до V ₁ и Н ₁ соответственно; здесь V Î { V ₀, V ₀ + 1, V ₀ + 2, …, V ₁} и Н Î { Н ₀, Н ₀ + 1, Н ₀ + 2, …, Н ₁}. Очевидно, что

В (V ₁, Н ₁) = 0; (14)

В (V, Н ₁) = F (V, Н ₁) + В (V + 1, Н ₁),

V Î { V ₀, V ₀ + 1, V ₀ + 2, …, V ₁ – 1}; (15)

В (V ₁, Н) = G (V ₁, Н) + В(V ₁, Н + 1),

Н Î { Н ₀, Н ₀ + 1, Н ₀ + 2, …, Н ₁ – 1}. (16)

В общем случае, для V Î { V ₀, V ₀ + 1, V ₀ + 2, …, V ₁ – 1} и Н Î { Н ₀, Н ₀ + 1, Н ₀ + 2, …, Н ₁ – 1}, имеем:

В (V, Н) = min{ F (V, Н) + В (V + 1, Н), G (V, Н) + В (V, Н + 1)}. (17)

Равенства (14)–(17) являются рекуррентными соотношениями динамического программирования, позволяющими определить оптимальную траекторию набора высоты и скорости летательного аппарата. Если в ситуации, характеризуемой парой (V, Н), в правой части последнего записанного соотношения минимум достигается на первой компоненте, то следует на единицу увеличить скорость объекта; если же минимум достигается на второй компоненте, то на единицу следует увеличить высоту полета.

Вычисления по записанным рекуррентным соотношениям можно представить как процесс заполнения табл. 1.3, строки которой соответствуют имеющимся значениям высоты, а столбцы – имеющимся значениям скорости. В каждую клетку, стоящую в пересечении столбца Н и строки V вносятся:

1) соответствующее значение функции В (V, Н);

2) заключенный в квадратные скобки символ v или h; внесение символа v (символа h) означает, что в ситуации, определяемой парой (V, Н), на единицу следует увеличить значение скорости (высоты) полета.

Заполнение таблицы осуществляется в следующем порядке. Сначала на основании равенств (14)–(16) заполняются клетки нижней (последней) строки и крайне правого (последнего) столбца. Дальнейшее заполнение реализуется на основании формулы (17); заполняются клетки предпоследней строки и предпоследнего столбца, и т.д. Если в (17) минимум правой части реализуется на первой компоненте, то в заполняемую клетку в качестве второй компоненты вносится [ v ], в противном случае в заполняемую клетку вносится [ h ].

Таблица 1.3 Значения функции В (V, Н)

Дадим оценку вычислительной сложности предложенной процедуры счета. Число вычисляемых значений функции Беллмана В (V, Н) оценивается произведением (V ₁ – V ₀)× (Н ₁ – Н ₀). Каждое очередное значение этой функции вычисляется по записанным рекуррентным соотношениям посредством выполнения нескольких элементарных операций. Общая оценка числа выполняемых для решения задачи элементарных операций С (V ₁ – V ₀)(Н ₁ – Н ₀), где С – достаточно малая натуральная константа (оценка 10 для С является верхней). В случае, например, V – V₀ = Н ₁ – Н ₀ = 10 число выполняемых при синтезе оптимальной траектории элементарных операций не превышает 1000.

Примем следующие обозначения: V ₁ – V ₀ = р, Н ₁ – Н ₀ = q. Сумма р + q – общее число этапов, на каждом из которых на единицу возрастает значение V или Н. Если ЗВТНВС решать методом полного перебора, то общий расход горючего придется подсчитать для С^p p+q различных траекторий набора высоты и скорости полета (через C^m_n как обычно, обозначается число сочетаний из n по m). В случае V₁ – V ₀ = Н ₁ – Н ₀ = 10 расход горю-чего придется подсчитать для C¹⁰₂₀ (т.е. более чем для 180000) различных траекторий.

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

Метод динамического программирования относят к числу схем инвариантного (не меняющего существа проблемы) погружения. Суть схемы инвариантного погружения состоит в замене исходной задачи семейством однотипных задач, одной из которых является исходная. Последовательное, в порядке возрастания (или убывания) значений одного или нескольких параметров решение задач вводимого семейства приводит в итоге к определению оптимального решения исходной задачи.

Достаточно часто при реализации метода динамического программирования в явном виде не записываются и частные задачи, вводится только соответствующая функция Беллмана.

Классическая задача коммивояжера.

Приведем несколько предварительных определений и фактов. Цикл в конечном ориентированном графе называется простым, если он не имеет самопересечений (нет вершины, которую цикл проходит дважды). Простой цикл называется гамильтоновым, если он проходит через все вершины графа. Граф G называется полным, если для любой упорядоченной пары i, j его вершин в G имеется дуга (i, j). Гамильтоновы циклы имеются не во всяком графе. Граф G именуется гамильтоновым, если гамильтонов цикл в нем есть. В полном n -вершинном ориентированном графе имеются (n – 1)! гамильтоновых циклов.

Если G – взвешенный ориентированный граф; то весом произвольного цикла G называется сумма весов дуг, входящих в состав этого цикла.

Классическая задача коммивояжера (ЗК) формулируется следующим образом: имеется полный взвешенный ориентированный граф без петель G с множеством вершин N = {1, 2, …, n }; веса всех дуг неотрицательны; в этом графе требуется найти гамильтонов цикл минимального веса.

Исходную информацию по ЗК считаем представленной в виде (n´ n)-матрицы S = { s_ij }, где s_ij – вес дуги (i, j) графа G, i = n, 1, j = n, 1, i ≠ j; все элементы главной диагонали матрицы S являются нулями.

В типовой интерпретации вершины 1, 2, …, n графа G – это города. Дуги отображают возможные элементарные переходы. Коммивояжеру, изначально находящемуся в городе 1, необходимо обойти все остальные города, побывав в каждом из них ровно по одному разу, и затем вернуться в город 1. Веса дуг графа трактуются как длины соответствующих элементарных переходов. Требуется найти имеющий минимальную длину допустимый (т.е. удовлетворяющий наложенным требованиям) маршрут коммивояжера. С учетом других возможных интерпретаций, на матрицу S требование симметричности не налагается, не считается обязательным и выполнение неравенства треугольника.

Один из основных алгоритмов решения ЗК основан на принципе динамического программирования. При изложении этого алгоритма будем придерживаться терминологии, соответствующей приведенной типовой интерпретации задачи.

Пусть i – произвольный город (i Î N), а V – любое подмножество городов, не содержащее города 1 и города i. Через М (i, V) обозначим совокупность путей, каждый из которых начинается в городе i, завершается в городе 1 и проходит в качестве промежуточных только через города множества V, заходя в каждый из них ровно по одному разу. Через В (i, V) обозначим длину кратчайшего пути множества М (i, V). Для решаемой задачи В (i, V) – функция Беллмана. Как очевидно, В (1, {2, 3, …, n }) – искомая минимальная длина простого (без самопересечений) замкнутого пути, проходящего через все города.

Если V – одноэлементное множество, V ={ j }, где j ≠ 1 и j ≠ i, то совокупность М (i, V) состоит из единственного пути π = = (i, j, 1). Поэтому

В (i, { j }) = s_ij + s_j1, i Î N, j Î {2, 3, …, n }, j ≠ I (18)

Предположим, что значения функции В (i, V) для всех i Î N \ {1} и всех возможных k -элементных (k < n – 1) множеств V уже вычислены. Тогда значение В (i, V'), где V' – произвольное (k + 1)-элементное подмножество совокупности N \ {1, i }, вычисляется по формуле

(19)

Уравнения (18)–(19) – рекуррентные соотношения динамического программирования для решения задачи коммивояжера, они обеспечивают реализацию обратного метода Беллмана.

Пример 1.4. Решить задачу коммивояжера, определяемую матрицей

Сначала, пользуясь формулой (18), определяем значения В (i, {j}):

В (2, {3}) = 4;

В (2, {4}) = 8;

В (3, {2}) = 6;

В (3, {4}) = 5;

В (4, {2}) = 7;

В (4, {3}) = 5.

Далее по формуле (19) последовательно получаем (в левой части каждого из ниже записанных равенств подчеркнуты те значения параметра j, на которых при подсчете реализуется указанный в правой части (19) минимум):

В (2, { 3, 4}) = min (3 + 5, 5 + 5) = 8;

В (3, {2, 4 }) = min (4 + 8, 2 + 7) = 9;

В (4, { 2, 3}) = min (5 + 4, 4 + 6) = 9;

В (1, {2, 3, 4}) = min (5 + 8, 1 + 9, 4 + 9) = 10.

Итак, оптимальное значение критерия в рассматриваемом примере равно 10.

Выполненные подчеркивания позволяют определить оптимальный маршрут. Он следующий:

1 → 3 → 4 → 2 → 1.

Для записи соотношений, по которым реализуется прямой метод Беллмана, введем новые обозначения. Пусть М' (V, i) – совокупность путей, каждый из которых начинается в городе 1, проходит в качестве промежуточных только через города подмножества V, заходя в каждый из них ровно по одному разу, и завершается в городе i; здесь, как и ранее, i – произвольный город (i Î N), а V – любое подмножество N, не содержащее городов 1 и i. Длину кратчайшего пути множества М' (V, i) обозначим В* (V, i). Как очевидно, В* ({2, 3, …, n }, 1) – искомая минимальная длина простого (без самопересечений) замкнутого пути, проходящего через все города. Если V – одноэлементное множество, V = {j}, где j ≠ 1 и j ≠ i, то совокупность М' (V, i) состоит из единственного пути π = (1, j, i). Поэтому

В* ({ j }, i) = s _{1 j} + s_ji, i Î N, j Î {2, 3, …, n }, j ≠ i (20)

Предположим, что значения функции В* (V, i) для всех i ∈ N и всех возможных k -элементных (k < n – 1) множеств V уже вычислены. Тогда значение В* (V', i), где V' – произвольное (k + 1)-элементное подмножество совокупности N \{1, i }, вычисляется по формуле

(21)

Уравнения (20)–(21) – рекуррентные соотношения динамического программирования для решения классической задачи коммивояжера, они обеспечивают реализацию прямого метода Беллмана.

Заметим, что при решении задачи коммивояжера обратным методом состояния моделирующей системы – пары вида (i, V), где i – город, в котором сейчас находится коммивояжер, а V – множество городов, которые ему еще предстоит обойти перед тем, как вернуться в исходный город 1. При решении задачи коммивояжера прямым методом состояния моделирующей системы – пары вида (V, i), где i – город, в котором коммивояжер находится сейчас, а V – множество городов, которые коммивояжер уже обошел после того, как вышел из города 1. По сути, (i, V) и ({2, 3, …, n } \ (V È { i }), i) – это разные обозначения одной и той же ситуации. Данный факт используется при решении рассматриваемой задачи методом встречного счета.

Пример 1.5. Методом встречного счета решить задачу коммивояжера, определяемую матрицей

(заметим, что матрица S в данном примере та же, что и в предыдущем).

В качестве разрезающего выберем множество, включающее следующие состояния:

(2, {3}) /совпадет с ({4}, 2)/;

(2, {4}) /совпадет с ({3}, 2)/;

(3, {2}) /совпадет с ({4}, 3)/;

(3, {4}) /совпадет с ({2}, 3)/;

(4, {2}) /совпадет с ({3}, 4)/;

(4, {3}) /совпадет с ({2}, 4)/.

Реализуя метод обратного счета, определяем:

В (2, {3}) = 4;

В (2, {4}) = 8;

В (3, {2}) = 6;

В (3, {4}) = 5;

В (4, {2}) = 7;

В (4, {3}) = 5.

Реализуя метод прямого счета, получаем:

В* ({4}, 2) = 9;

В* ({3}, 2) = 5;

В* ({4}, 3) = 8;

В* ({2}, 3) = 8;

В* ({3}, 4) = 3;

В* ({2}, 4) = 10.

Далее имеем:

В (2, {3}) + В* ({4}, 2) = 13;

В (2, {4}) + В* ({3}, 2) = 13;

В (3, {2}) + В* ({4}, 3) = 14;

В (3, {4}) + В* ({2}, 3) = 13;

В (4, {2}) + В* ({3}, 4) = 10;

В (4, {3}) + В* ({2}, 4) = 15.

Минимальное, равное 10, значение правая часть принимает в пятом равенстве. Отсюда следует: а) оптимальное значение критерия в рассматриваемой задаче равно 10; б) оптимальная траектория системы проходит через состояние ({3}, 4) или, что то же самое, через состояние (4, {2}). Последнее дает возможность установить оптимальный маршрут коммивояжера:

1 → 3 → 4 → 2 → 1.

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

Задача коммивояжера с минимаксным критерием (ЗК ММК)

Считается заданным полный взвешенный ориентированный граф без петель G с множеством вершин N = {1, 2, …, n }; веса всех дуг неотрицательны. Для каждого цикла С этого графа определена характеристика ω (С), значение которой равно максимальному из весов дуг, данный цикл образующих. В рассматриваемой задаче требуется найти гамильтонов цикл С графа G, имеющий минимально возможное значение характеристики ω (С). Исходную информацию по задаче считаем представленной в виде (n × n)-матрицы S = { s_ij }, где s_ij – вес дуги (i, j) графа G, i =1, …, n, j = 1, …, n, i ≠ j; все элементы главной диагонали матрицы S нулевые.

Придерживаемся прежней интерпретации: вершины графа G – это города, которые коммивояжеру необходимо обойти. Пусть i – произвольный город (i Î N), а V – любое подмножество городов, не содержащее города 1 и города i. Как и ранее, через М (i, V) обозначаем совокупность путей, каждый из которых начинается в городе i, завершается в городе 1 и проходит в качестве промежуточных только через города множества V, заходя в каждый из них ровно по одному разу. Каждый путь π характеризуем показателем ω (π) – максимальным из весов дуг, которые образуют данный путь. Минимальное значение показателя ω (π) для путей множества М (i, V) обозначим В' (i, V). Как очевидно, В' (1, {2, 3, …, n }) – искомое оптимальное значение критерия в решаемой ЗК ММК.

Если V – одноэлементное множество, V = { j }, где j ≠ 1 и j ≠ i, то совокупность М (i, V) состоит из единственного пути π = (i, j, 1). Поэтому

В' (i, { j }) = max(s_ij, s_{j 1}), i Î N, j Î {2, 3, …, n }, j ≠ i (22)

Предположим, что значения функции В' (i, V) для всех i ∈ N и всех возможных k -элементных (k < n – 1) множеств V уже вы-числены. Тогда значение В' (i, V'), где V' – произвольное (k + 1)-элементное подмножество совокупности N \ {1, i }, вычисляется по формуле

(23)

Уравнения (22)–(23) – рекуррентные соотношения динамического программирования для решения ЗК ММК.

Отметим, что изложенным алгоритмом может решаться вопрос определения по произвольному n -вершинному ориентированному графу G, является ли он гамильтоновым. С этой целью по графу G строим полный взвешенный ориентированный граф без петель G* с множеством вершин N = {1, 2, …, n }. Веса дуг графа G* назначаем по следующему правилу: вес s_ij дуги (i, j) равен 1, если дуга (i, j) в исходном графе G имеется; вес s_ij дуги (i, j) равен 2 в противном случае. Далее решаем определяемую графом G* задачу коммивояжера с минимаксным критерием. Если оптимальное значение этого критерия оказывается равным 1, то граф G гамильтонов; в противном случае оптимальное значение критерия равно 2, и граф G гамильтоновым не является.

Задача инкассации

Задача определяется полным ориентированным графом без петель G с множеством вершин N = {1, 2, …, n }. Каждая дуга и каждая вершина этого графа, кроме вершины 1, имеет определенный вес. В интерпретации вершины 2, 3, …, n – это объекты, которые инкассатору необходимо обойти по замкнутому маршруту, посетив каждый из них ровно по одному разу. При этом считаем, что маршрут начинается и заканчивается в вершине 1 (банке). Веса дуг графа G трактуются как длины реализуемых по ним переходов, веса вершин 2, 3, …, n – это денежные суммы, которые соответствующими объектами передаются инкассатору для транспортировки в банк. Из банка инкассатор выходит без денег, в банк он возвращается со всей собранной по объектам множества {2, 3, …, n } денежной суммой.

С целью упрощения обозначений будем считать, что вершина 1 также имеет вес, он равен нулю. Исходную информацию по задаче считаем представленной (n × n)-матрицей S = { s(i, j) } и n- мерным вектором d = (d (1), d (2), …, d (n)), где s (i, j) – вес дуги (i, j), а d (i) – вес вершины i графа G, i =1, …, n, j = 1, …, n, i ≠ j. Все элементы главной диагонали матрицы S считаются нулевыми, первая координата вектора d равна нулю. Каждый гамильтонов цикл C = (1, i ₂, i ₃, …, i_n, 1), здесь (i ₂, i ₃, …, i_n) – произвольная перестановка чисел 2, 3, …, n, оцениваем показателем

χ (С) = d (i ₂) × s (i ₂, i ₃) + (d (i ₂) + d (i ₃)) × s (i ₃, i ₄) + (d (i ₂) + d (i ₃) +

+ d (i ₄)) × s (i₄, i ₅) + … + (d (i ₂) + d (i ₃) + d (i ₄) + … + d (i_n)) × s (i_n, 1).

Задача инкассации состоит в отыскании гамильтонова цикла с наименьшим значением показателя χ (С).

В интерпретации χ (С) – общее количество «деньго-километров» при реализации гамильтонова цикла С. Введенный показатель χ (С) можно считать характеристикой безопасности маршрута. Чем меньше χ (С), тем безопаснее маршрут.

Пусть i – произвольная вершина графа (i Î N), а V – любое подмножество его вершин, не содержащее вершины 1 и вершины i. Как и ранее, через М (i, V) обозначаем совокупность путей, каждый из которых начинается в вершине i, завершается в вершине 1 и проходит в качестве промежуточных только через вершины множества V, заходя в каждую из них ровно по одному разу. Каждый путь π характеризуем показателем η (π), общим числом деньго-километров в его реализации; при этом считаем, что в начальной вершине i пути π из множества М (i, V) инкассатор имеет денежную сумму

именно эта сумма собрана инкассатором в не принадлежащих множеству V пунктах. Минимальное значение показателя η (π) для путей множества М (i, V) обозначим В (i, V). Как очевидно, В (1, {2, 3, …, n }) – искомое оптимальное значение критерия в решаемой задаче инкассации.

Если V – одноэлементное множество, V = { j }, где j ≠ 1 и j ≠ i, то совокупность М (i, V) состоит из единственного пути π = = (i, j, 1). Поэтому

В (i, { j }) = R(N \ { j }) s (i, j) + R (N) s (j, 1),

i Î N, j Î {2, 3, …, n }, j ≠ i (24)

Предположим, что значения функции В(i, V) для всех i Î N и всех возможных k -элементных (k < n – 1) подмножеств V уже вычислены. Тогда значение В (i, V'), где V' – произвольное (k + 1)-элементное подмножество совокупности N \ {1, i }, вычисляется по формуле

(25)

Уравнения (24)–(25) – рекуррентные соотношения динамического программирования для решения задачи инкассации. Отметим, что в рассмотренной задаче на оценку гамильтонова цикла C = (1, i ₂, i ₃, …, i_n, 1) никак не влияет значение s (1, i ₂), т.е. длина первого реализуемого перехода; это вызвано тем, что в данном переходе транспортируется нулевая денежная сумма. В главе 4 будет рассмотрена бикритериальная задача инкассации, где один критерий – суммарная длина (стоимость) маршрута, а другой – количество деньго-километров.

Задача двух коммивояжеров

Математическая постановка задачи следующая. Имеется полный взвешенный ориентированный граф без петель G с множеством вершин N = {1, 2, …, n }; веса всех дуг неотрицательны. Требуется найти пару циклов < C ₁, C₂ > этого графа, имеющую минимальный суммарный вес и удовлетворяющую условиям:

а) вершина 1 – единственная вершина, через которую проходит как цикл C ₁, так и цикл C ₂;

б) через каждую вершину множества N \ {1} проходит либо цикл C ₁, либо цикл C ₂.

Исходная информация по задаче представлена (n´ n)-матрицей S = { s_ij }, где s_ij – вес дуги (i, j) графа G, i =1, …, n, j =1, …, n, i ≠ j; все элементы главной диагонали матрицы S нулевые.

Придерживаемся интерпретации, соответствующей изложенной выше. Вершины графа G – это города, которые коммивояжерам необходимо обойти по замкнутым маршрутам; веса дуг графа G – длины соответствующих переходов. Пусть i ∈ N, j ∈ N, i ≠ j за исключением случая i = j = 1, а V – любое подмножество из N, не содержащее городов 1, i и j. Через М'' (V, i, j) обозначим совокупность всех пар (π ₁, π ₂) путей, обладающих следующими свойствами:

а) каждый из путей начинается в городе 1;

б) путь π ₁ заканчивается в городе i;

в) путь π ₂ заканчивается в городе j;

г) в паре (π ₁, π ₂) пути простые (без самопересечений), проходящие в качестве промежуточных только через города под-множества V, при этом через каждый город этого подмножества проходит ровно один путь из данной пары.

Кратчайшую суммарную длину, подсчитанную для пар путей из М'' (V, i, j) обозначим В* (V, i, j). Ясно, что В* ({2, 3, …, n }, 1, 1) – искомая минимальная суммарная длина пары циклов < C ₁, C ₂>, удовлетворяющих требованиям решаемой задачи о двух коммивояжерах.

Как очевидно,

В* (Æ, i, j) = s _{1 i} + s _{1 j} (26)

Множество М'' ({ k }, i, j) состоит из двух пар путей: {π ₁ = (1, k, i), π ₂ = (1, j)} и {π ₁ = (1, i), π ₂ = (1, k, j))}. Суммарная длина путей первой пары: s _{1 k} + s _{k i} + s _{1 j} = (s _{1 k} + s _{1 j} ) + s_ki = В* (Æ, k, j) + s_ki. Аналогичным образом получаем, что суммарная длина путей второй пары равна В* (Æ, i, k)+ s_kj. Поэтому

В* ({ k }, i, j) = min{ В* (Æ, k, j) + s_ki; В* (Æ, i, k)+ s_kj }. (27)

В общем случае, когда i Î N, j Î N, i ≠ j за исключением варианта i = j = 1, а V – любое подмножество N, не содержащее городов 1, i и j, имеем следующее. В путях пары (π ₁, π ₂) из М" (V, i, j) последними являются города i и j соответственно. Если некоторый принадлежащий подмножеству V город k является предпоследним в первом пути, то при данном дополнительном условии минимальная суммарная длина пары путей (π ₁, π ₂) равна В* (V \ { k }, k, j) + s_ki; если же принадлежащий V город k является предпоследним во втором пути, то при данном дополнительном условии минимальная суммарная длина пары путей (π ₁, π ₂) равна В* (V \ { k }, i, k)+ s_kj . Отсюда получаем:

(28)

Равенства (26)–(28) являются рекуррентными соотношениями динамического программирования для решения задачи двух коммивояжеров.

Классическая задача о ранце (КЗР)

Имеются ранец и предметы П ₁, П ₂, …, П_n; каждый предмет П_i характеризуется двумя целыми положительными показателями: с_i – стоимость предмета; v_i – вес предмета, i = 1, …, n. Предметы недробимы, т.е. каждый из них можно поместить в ранец только целиком. Требуется найти совокупность предметов, которые следует поместить в ранец с тем, чтобы суммарная стоимость предметов в ранце оказалась максимальной при условии, что суммарный вес предметов в ранце не может превысить заданной натуральной константы W (предполагается, что суммарный вес всех имеющихся предметов больше W).

КЗР формулируется как следующая задача булева линейного программирования (БЛП):

(29)

при условиях

(30)

х_i Î {0, 1}, i=1, …, n (31)

Задачу (29)–(31) далее будем именовать задачей Z.

По начальным данным задачи Z формулируем совокупность частных задач о ранце Z (k, p), где k Î {1, 2, …, n }; р Î {1, 2, …, W }. Задача Z (k, p) записывается следующим образом:

при условиях

x_i Î {0, 1}

i = 1, …, k

(в частной задаче Z (k, p) имеющимися в наличии считаются только первые k предметов из совокупности { П ₁, П ₂, …, П_n }, суммарный вес предметов в ранце не может превышать константы р).

Оптимальное значение критерия в частной задаче Z (k, p) обозначим В* (k, p). Как очевидно, задача Z (n, W) совпадает с исходной задачей Z; поэтому В* (n, W) – оптимальное значение критерия в задаче Z.

Легко видеть, что

(32)

Пусть для некоторого k, принадлежащего множеству {1, 2, …, n – 1} и всех р Î {1, 2, …, W } значения функции В* (k, p) уже вычислены. Для р Î {0, 1, 2, …, v_{k +1} – 1} cитуация, возникающая при нахождении В* (k + 1, p), фактически не отличается от ситуации, имевшей место при подсчете В* (k, p), ибо дополнительно появляющийся при переходе от задачи Z (k, p) к задаче Z (k + 1, p) предмет П_{k + 1} в ранец поместить невозможно. В случае, когда р Î { v_{k + 1}, v_{k + 1} + 1, …, W }, при переходе от задачи Z (k, p) к задаче Z (k + 1, p) мы получаем дополнительную возможность поместить в ранец предмет П_{k +1}. Этой возможностью можно: а) не воспользоваться; б) воспользоваться. Очевидно, что в случае а) мы получим уже вычисленную величину В* (k, p). В случае б) в ранец кладется предмет П_{k +1} стоимостью с_{k +1} и так как вес этого предмета равен v_{k +1}, то далее мы оказываемся в условиях задачи Z (k, p – v_{k +1}). В итоге получаем:

(33)

здесь k = 2, 3, …, n – 1.

Равенства (32)–(33) – рекуррентные соотношения динамического программирования для решения задачи о ранце. Пользуясь ими, мы находим сначала величины В* (1, p), р Î {1, 2, …, W }, затем величины В* (2, p), р Î {1, 2, …, W }, и т.д., вплоть до отыскания В* (n, W) – оптимального значения критерия в исходной задаче Z.

Процедуру вычисления значений функции В* (k, p) целесообразно реализовывать как процесс последовательного заполнения таблицы стоимостей. В этой таблице строки соответствуют значениям параметра k (по возрастанию), а столбцы – значениям параметра р (также по возрастанию). В каждую клетку, расположенную в пересечении произвольной строки k и произвольного столбца р, вносится значение В* (k, p). Первая строка заполняется согласно формуле (32). Далее заполнение каждой (k + 1)-ой строки, k = 1, 2, …, n – 1, осуществляется в соответствии с формулой (33). Одновременно целесообразно фиксировать множества предметов М (k, p), которые обеспечивают значения В* (k, p) критериев рассматриваемых частных задач. Как очевидно, М (1, p) = Æ, если р < v ₁; М (1, p) ={1} в противном случае. Далее будем считать

В заполненной таблице стоимостей содержимое клетки (n, W) – оптимальное значение критерия в задаче Z. Для обеспечения этого значения в ранец следует поместить предметы совокупности М (n, W).

Изложенный алгоритм решения КЗР далее будем называть алгоритмом A _кзр.

Пример 1.6. Решить КЗР:

5 х ₁ + 2 х ₂ + 4 х ₃ + 7 х ₄ + 5 х ₅ → max

при условиях

2 х ₁ + х ₂ + 2 х ₃ + 4 х ₄ + 3 х ₅ ≤ 8;

х_i Î {0, 1}, i = 1, …, 5.

Таблица 1.4 Таблица стоимостей для примера 1.6

Задача решается путем последовательного, сверху вниз, заполнения строк таблицы стоимостей (табл. 1.4). В каждой клетке (k, p) данной таблицы вслед за полученным значением В* (k, p) в скобках малыми цифрами перечисляются номера предметов, которые согласно оптимальному решению частной задачи Z (k, p) следует положить в ранец. Если задача Z (k, p) имеет несколько оптимальных решений, то указывается только одно из них. Заполнение первой строки таблицы выполняется в соответствии с формулой (32); здесь считается, что в нашем распоряжении имеется только предмет П ₁, его стоимость равна 5 и вес равен 2. Предмет П ₁ можно положить в ранец, если дозволенный вес предметов в ранце не меньше чем 2. Поэтому В* (1, 1) = 0 и В* (1, p) = 5, если p ≥ 2. Заполнение второй и каждой из нижеследующих строк выполняется в соответствии с формулой (33). Рассмотрим в качестве иллюстрации, причем на содержательном уровне, как заполняется клетка (4, 8). Данная клетка соответствует задаче Z (4, 8). В сравнении с задачей Z (3, 8), которой соответствует клетка (3, 8), в Z (4, 8) появляется новая возможность – в ранец можно положить предмет П ₄. Согласно формуле (33), выбирается лучший из двух вариантов. Первый вариант предполагает, что возможностью положить в ранец предмет П ₄ мы не воспользовались. Тогда имеет место абсолютно та же ситуация, что в задаче Z (3, 8), и мы можем обеспечить суммарную стоимость предметов в ранце равную В* (3, 8), т.е. числу 11, записанному в клетке, расположенной непосредственно над заполняемой. Итак, первый вариант обеспечивает суммарную стоимость предметов в ранце, равную 11; реализация данного варианта означает, что в ранец кладутся предметы П ₁, П ₂ и П ₃. Второй вариант предусматривает, что предмет П ₄, его стоимость 7, кладется в ранец. Вес предмета П ₄ равен 4. Поэтому от заполняемой клетки в четвертой строке перемещаемся на 4 клетки влево, оказываемся в столбце, соответствующем оставшемуся резерву веса ранца после того, как в него положен предмет П ₄; непосредственно над полученной клеткой, а именно в клетке (3, 4) записано число 9, это максимально возможная суммарная стоимость предметов, взятых из совокупности { П ₁, П ₂, П ₃}, при условии, что их суммарный вес не превышает четырех (в этой ситуации как показывает заполнение клетки (3, 4), из указанной совокупности следует взять первый и третий предметы). Таким образом, второй вариант обеспечивает суммарную стоимость предметов в ранце 7 + 9=16; реализация данного варианта означает, что в ранец кладутся предметы П, П и П. Второй вариант дает лучший результат, заполнение клетки (4, 8) осуществляется по этому варианту.

Некоторые действия, выполненные нами при решении примера 1.6, являются излишними. Для решения КЗР все клетки таблицы стоимостей заполнять не обязательно. В последней строке нам достаточно заполнить только одну, крайне правую клетку (n, W). Согласно формуле (33), для этого достаточно знать содержимое только двух клеток предпоследней строки, а именно клетки (n – 1, W) и клетки (n – 1, W – v_n). Для заполнения указанных клеток предпоследней строки достаточно знать заполнение максимум четырех клеток строки n – 2, и т.д. Процессу счета по соотношениям динамического программирования (32)–(33) целесообразно предварить процесс разметки, когда двигаясь по строкам таблицы снизу вверх, мы отмечаем, заполнение каких клеток таблицы действительно необходимо для решения заданной КЗР.

К рассмотренной КЗР легко сводится и, следовательно, может решаться алгоритмом A _кзр задача «Разбиение», формулируемая следующим образом. Имеется конечное множество натуральных чисел W = { v ₁, v ₂, …, v_n }. Требуется определить, можно ли разбить совокупность W на два непересекающихся подмножества так, чтобы сумма элементов, входящих в одно подмножество, совпала с суммой элементов, входящих в другое подмножество.

Задачу «Разбиение» определяет набор натуральных чисел { v ₁, v ₂, …, v_n }. Будем считать, что сумма всех входящих в множество W чисел четна (в противном случае рассматриваемая задача положительного решения заведомо не имеет). Пусть v ₁ + + v ₂ + …+ v_n = 2 V, где V – натуральное число. По имеющемуся набору { v ₁, v ₂, …, v_n } строим следующую КЗР:

v ₁ х ₁ + v ₂ х ₂ + … + v_nх_n → max;

v ₁ х ₁ + v ₂ х ₂ + … + v_nх_n ≤ V;

х_i Î {0, 1}, i = 1, …< n.

Оптимальное значение критерия в этой КЗР не может превысить V, ибо критерий задачи совпадает с левой частью ее линейного ограничения. Оптимальное значение критерия равно V тогда и только тогда, когда исходная задача «Разбиение» имеет положительное решение (т.е. совокупность W можно разбить на два непересекающихся подмножества так, чтобы сумма элементов, входящих в одно подмножество, совпала с суммой элементов, входящих в другое подмножество). В отвечающем оптимальному решению КЗР разбиении элемент w_i включается в первое подмножество, если переменная х_i принимает значение 1, и во второе подмножество, если х_i принимает значение 0, i = 1, …, n.

Часто задачу «Разбиение» называют задачей о камнях. При этом предполагается следующая интерпретация. Имеется куча, состоящая из n камней. Камни недробимы, вес каждого камня – заданное натуральное число. Вес любой кучи – это сумма весов составляющих ее камней. Требуется определить, можно ли имеющуюся кучу камней разделить на две подкучи равного веса.

Отметим, что алгоритм A _кзр легко обобщается для решения следующей задачи:

(34)

при условиях

1, …, m ( 35)

x_i Î {0, 1} ( 36)

Задачу (34)–(36) будем называть многомерной задачей о ранце и обозначать символом Z^m.

По начальным данным задачи Z ^m формулируем совокупность частных задач Z (k, р), где k Î {1, 2, …, n }; р = (p ₁, p ₂, …, p_m), причем р_j Î {0, 1, 2, …, W ^j }, j = 1, m. В частной задаче Z (k, р) считаются имеющимися в наличии только первые k предметов из совокупности { П ₁, П ₂, …, П_n }, величина суммарного веса предметов в ранце по j -ому показателю, j = 1, m, не может превышать константы р_j . Оптимальное значение критерия в частной задаче Z (k, р) обозначим В* (k, p). Задача Z ^m совпадает с задачей Z (n, W), где W = (W ¹, W ², …, W ^m). Поэтому В* (n, W) – оптимальное значение критерия в задаче Z ^m. Процедура решения задачи Z ^m методом динамического программирования представима как процесс заполнения таблицы стоимостей, строки которой соответствуют возможным значениям параметра k (по возрастанию), а столбцы – возможным значениям векторного параметра р = = (p ₁, p ₂, …, p_m). Для определенности считаем, что в заголовочной для столбцов строке этой таблицы векторы перечисляются в соответствии с их лексикографическим порядком по возрастанию. В клетку, расположенную в пересечении строки k и столбца р, вносится значение В* (k, p). Заполнение клеток производится по строкам, в порядке возрастания их номеров. Рекуррентные соотношения динамического программирования для решения задачи Z ^m очевидным образом обобщают равенства (32)–(33) на случай многомерной задачи.

За изложенным обобщением алгоритма A _кзр сохраняем прежнее название. Оценим вычислительную сложность алгоритма в применении к m -мерной задаче. Пусть максимальная из координат вектора W равна W. В таком случае число подлежащих заполнению столбцов таблицы стоимостей имеет верхнюю оценку (W + 1) ^m. Число строк таблицы равно n. Верхняя оценка числа подлежащих заполнению клеток n × (W + 1) ^m . Число элементарных операций, необходимых для определения заполнения каждой отдельной клетки, является функцией, линейно зависящей от m. Получаем, что Сmn (W + 1) ^m – верхняя оценка числа элементарных операций, выполняемых изложенным алгоритмом при решении m -мерной задачи о ранце; здесь С – константа, не зависящая от конкретных характеристик задачи. В частном случае, для одномерной задачи о ранце (m = 1) получаем оценку СnW; можно считать, что константа С не превосходит 10.

Задача отыскания кратчайших путей (ЗОКП)

Считается заданным конечный взвешенный ориентированный граф G с множеством вершин N = {1, 2, …, n }, веса всех дуг неотрицательны. Веса дуг трактуем как их длины. Последовательность i ₁, i ₂, …, i_k вершин графа G определяет путь из вершины i ₁ в вершину i_k , если для каждого t =1, 2, …, k – 1 в данном графе имеется дуга (i_t, i_{t + 1}); указанные дуги образуют путь i ₁, i ₂, …, i_k. Сумма длин дуг, образующих путь, называется длиной этого пути. Для каждой вершины х графа требуется найти путь минимальной длины (кратчайший путь) из вершины 1 в вершину х.

Вес дуги (i, j) графа G обозначаем с (i, j). Длину кратчайшего пути из 1 в х будем называть расстоянием от вершины 1 до вершины х. Расстояние от вершины 1 до вершины х будем обозначать s (x).

Ясно, что s (1) = 0. Пусть H – множество вершин, длины кратчайших путей из вершины 1 в которые уже известны. В начальной ситуации это множество одноэлементно: H = {1}. Через s (1, M) обозначим минимальную из длин кратчайших путей от вершины 1 до вершин множества М, М ⊆ {2, 3, …, n }. Как очевидно, для множества вершин Н, содержащего вершину 1, имеет место

(40)

Пусть минимум правой части (40) реализуется на паре (i ⁰, j ⁰). Тогда кратчайший путь из вершины 1 в вершину j ⁰ получаем добавлением к кратчайшему пути из вершины 1 в вершину i ⁰ дуги (i ⁰, j ⁰), длина s (j ⁰) этого пути равна s (i ⁰) + с (i ⁰, j ⁰).

Формула (40) – рекуррентное соотношение динамического программирования для решения ЗОКП. Пользуясь этой формулой, на первом шаге определяем ближайшую к вершине 1 вер-шину i ¹ из совокупности {2, 3, …, n }. На втором шаге определяем ближайшую к вершине 1 вершину i² из совокупности {2, 3, …, n } \ { i ¹}. На третьем шаге определяем ближайшую вершине 1 верш