Содержание
Введение
1. Дискретныеоптимизационные задачи
1.1 Постановка задач дискретного программирования
1.2 Алгоритм методаветвей и границ6
2. Постановка задачикоммивояжера
3. Задачакоммивояжера методом динамического программирования
4. Задачакоммивояжера методом ветвей и границ
Заключение
Списокиспользованных источников
/>
Введение
/>/>Дискретная оптимизация как разделматематики существует достаточно давно. Оптимизация — это выбор, т.е. то, чемпостоянно приходится заниматься в повседневной жизни. Термином«оптимизация» в литературе обозначают процесс или последовательностьопераций, позволяющих получить уточненное решение. Хотя конечной цельюоптимизации является отыскание наилучшего или «оптимального» решения,обычно приходится довольствоваться улучшением известных решений, а не доведениемих до совершенства. Поэтому под оптимизацией понимают скорее стремление ксовершенству, которое, возможно, и не будет достигнуто.
/>/>Необходимость принятия наилучших решенийтак же стара, как само человечество. Испокон веку люди, приступая косуществлению своих мероприятий, раздумывали над их возможными последствиями ипринимали решения, выбирая тем или другим образом зависящие от них параметры — способы организации мероприятий. Но до поры, до времени решения моглиприниматься без специального математического анализа, просто на основе опыта издравого смысла.
/>/>Возьмем пример: человек вышел утром издому, чтобы ехать на работу. По ходу дела ему приходится принять целый рядрешений: брать ли с собой зонтик? В каком месте перейти улицу? Каким видомтранспорта воспользоваться? И так далее. Разумеется, все эти решения человекпринимает без специальных расчетов, просто опираясь на имеющийся у него опыт ина здравый смысл. Для обоснования таких решений никакая наука не нужна, да врядли понадобится и в дальнейшем.
/>/>Однако возьмем другой пример. Допусти,организуется работа городского транспорта. В нашем распоряжении имеетсякакое-то количество транспортных средств. Необходимо принять ряд решений,например: какое количество и каких транспортных средств направить по тому илидругому маршруту? Как изменять частоту следования машин в зависимости отвремени суток? Где поместить остановки? И так далее.
/>/>Эти решения являются гораздо болееответственными, чем решения предыдущего примера. В силу сложности явленияпоследствия каждого из них не столь ясны; для того, чтобы представить себе этипоследствия, нужно провести расчеты. А главное, от этих решений гораздо большезависит. В первом примере неправильный выбор решения затронет интересы одногочеловека; во втором — может отразиться на деловой жизни целого города.
/>/>Наиболее сложно обстоит дело с принятиемрешений, когда речь идет о мероприятиях, опыта, в проведении которых еще несуществует и, следовательно, здравому смыслу не на что опереться, а интуицияможет обмануть. Пусть, например, составляется перспективный план развитиявооружения на несколько лет вперед. Образцы вооружения, о которых может идтиречь, еще не существуют, никакого опыта их применения нет. При планированииприходится опираться на большое количество данных, относящихся не столько кпрошлому опыту, сколько к предвидимому будущему. Выбранное решение должно повозможности гарантировать нас от ошибок, связанных с неточным прогнозированием,и быть достаточно эффективным для широкого круга условий. Для обоснованиятакого решения приводится в действие сложная система математических расчетов.
/>/>Вообще, чем сложнее организуемоемероприятие, чем больше вкладывается в него материальных средств, чем ширеспектр его возможных последствий, тем менее допустимы так называемые«волевые» решения, не опирающиеся на научный расчет, и тем большеезначение получает совокупность научных методов, позволяющих заранее оценитьпоследствия каждого решения, заранее отбросить недопустимые варианты ирекомендовать те, которые представляются наиболее удачными.
/>1. Дискретные оптимизационные задачи
Дискретные оптимизационные задачи находят широкое применение вразличных областях, где используются математические методы для анализапроисходящих там процессов. Необходимость решения таких задач приводит к тому,что дискретная оптимизация становится важным элементом образованияспециалистов, связанных с её применением при решении задач, возникающих вприложениях. Поэтому нам представляется, что технология решения задачдискретного программирования должна стать одной из важных составных частей современногоматематического образования для специалистов по прикладной математике.
Дискретные оптимизационные задачи можно решать двумя методами:метод дискретного программирования и метод ветвей и границ. Они будут рассмотренына примере задачи коммивояжера.1.1 Постановказадач дискретного программирования
Под задачей дискретного программирования (дискретной оптимизации)понимается задача математического программирования
F(x0) = min f(x), x є G,
множество допустимых решений которой конечно, т.е. О ≤ |G| =N
Во многих задачах условия дискретности отделены от других условий,т.е. если х = (х1, х2,…, хn), то xj є Gj = (х j 1, хj2, ..., хjki), kj > 2. Поэтому N = =/>= /> > 2n, отсюда видно, что с ростом числапеременных объем вычислительной работы резко возрастает. 1.2 Алгоритм метода ветвей играниц
Рассмотрим задачу в виде:
f(x0)=min f(x), x є G, |G|=N
Алгоритм ветвей и границ основан на следующих построениях,позволяющих уменьшить объем перебора.
1. Вычисление оценки. Пусть G' /> G, тогда φ(G') называется нижней оценкой, если длялюбого х є G' выполняется неравенство f(x) ≥ φ(G').
2. Ветвление (разбиение множества G на подмножества). Положим
G0 = G и разобьем множество G0 на r1 непересекающихся подмножеств
/>/>/> /> /> /> G0 = /> /> , i ≠ j.
Этот шаг алгоритма считаем начальным, имеющим номер 0. Рассмотримшаг алгоритма с номером k. Пусть /> /> /> /> — множества, еще неподвергавшиеся разбиению. Выберем одно из этих множеств /> и разобьем его нанепересекающиеся подмножества: />
Выполним модификацию списка множеств, еще не подвергавшихсяразбиению. Заменим множество />множествами /> и множества, еще неподвергшиеся разбиению, переобозначим: /> /> /> />.
Эти множества образуют список задач для ветвления. Выберем одно изних и снова повторим процедуру разбиения.
Описанную процедуру разбиения можно представить в виде дерева (рис.1)
/>
Рис. 1
3. Пересчет оценок. Если G1 /> G2, то />
Поэтому, разбивая в процессе ветвления подмножество G’ /> G на непересекающиеся подмножества /> /> />G's, G' = /> , будем предполагать, что φ(G1’) ≥ φ (G’), причем хотя бы для некоторых номеровi0 выполняетсястрогое неравенство φ(/>) ≥ φ (G’).
4. Вычисление планов (допустимых решений). Если на шаге ветвления сномером k известен план хk, на шаге с номером (k + 1) — план хk+1 и если f(xk+1)
5. Признак оптимальности. Пусть G = />. Тогда план /> является оптимальным,т.е. />/>, есливыполняется условие
f(/>) = φ(Gv) ≤ φ(Gi), i=1, 2,...., s.
6. Оценка точности приближенных решений. Пусть G = />,
φ0 = /> φ(Gj), xk — рекорд; тогда имеет место следующее неравенство:
φ0 ≤f(x0) ≤ f(xk).
Разность ∆ = f(xk) — φ0 является оценкой гарантированного отклонения рекорда хk от оптимума х0. Из приведенного неравенстваследует, что для ветвления необходимо выбрать множество с минимальным значениемнижней оценки.
7. Правило отсева. Пусть снова G = />, x0 — оптимум, хk — рекорд. Если φ(Gr) > f(xk), то множество Gr можно отсеять, т.е.исключить из дальнейшего рассмотрения, так как оно не может содержатьоптимальных решений. Действительно, пусть x є G; тогда в силу определения оценки f(x) ≥ φ(G') имеем f(x) ≥ φ(Gr) > f(xk) ≥ f(x0).
Правило φ(Gr) > f(xk) гарантирует, что в процессе работы алгоритма ни одно изподмножеств Gr, в которых содержится точное решение x0, не будет отсеяно. Более сильноеправило φ(Gr) ≥ f(xk) гарантирует, что хотя бы одно оптимальное решение будет найдено,оно и применяется при практическом решении задач.
8. Конечность алгоритма. Конечность алгоритма следует из конечностимножества G.
Под методом ветвей и границ понимается алгоритм решения задачи,имеющий древовидную структуру поиска оптимального решения и использующийрезультаты решения оценочных задач. Древовидная структура называется обычнодеревом ветвления.
Эффективность алгоритма ветвей и границ определяется числомрешенных задач. Решение задачи состоит из двух основных этапов. На первом этапенаходится оптимальное решение (или близкое к нему). На втором этапепроизводится доказательство оптимальности полученного решения. Второй этап, какправило, оказывается более трудоемким, чем первый. Это означает, что число подзадач,решаемых до получения оптимума, может оказаться существенно меньше числаподзадач, решаемых для доказательства оптимальности.
/>2. Постановка задачи коммивояжера
Классическая задача коммивояжера (ЗК) формулируется следующимобразом: имеется полный взвешенный ориентированный граф без петель G с множеством вершин N = {1, 2,…, n}; веса всех дуг неотрицательны; в этомграфе требуется найти гамильтонов цикл минимального веса.
Исходную информацию по ЗК считаем представленной в виде матрицыразмера nxn. S = {sij}, где sij – вес дуги (i, j) графа G, i =/>, j =/>, i ≠ j; все элементы главной диагонали матрицы S являются нулями.
В типовой интерпретации вершины 1, 2,…, n графа G – это города. Дуги отображают возможныеэлементарные переходы. Коммивояжеру, изначально находящемуся в городе 1,необходимо обойти все остальные города, побывав в каждом из них ровно по одномуразу, и затем вернуться в город 1. Веса дуг графа трактуются как длинысоответствующих элементарных переходов. Требуется найти имеющий минимальнуюдлину допустимый (т.е. удовлетворяющий наложенным требованиям) маршруткоммивояжера. С учетом других возможных интерпретаций, на матрицу S требование симметричности неналагается, не считается обязательным и выполнение неравенства треугольника./>
3. Задача коммивояжераметодом динамического программирования
Под методом ветвей и границ понимается алгоритм решения задачи,имеющий древовидную структуру поиска оптимального решения и использующийрезультаты решения оценочных задач. Древовидная структура называется обычнодеревом ветвления.
Один из основных алгоритмов решения ЗК основан на принципединамического программирования. При изложении этого алгоритма будемпридерживаться терминологии, соответствующей приведенной типовой интерпретациизадачи.
Пусть 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 ÎN, j Î {2, 3,…, n}, j ≠ i.(1.1)
Предположим, что значения функции В(i, V ) для всех i ÎN \ {1} и всех возможных k-элементных (k
/> (1.2)
Уравнения (1.1)–(1.12) – рекуррентные соотношения динамическогопрограммирования для решения задачи коммивояжера, они обеспечивают реализациюобратного метода Беллмана. Вычислительная сложность задачи равна />, где С – произвольнаяконстанта (С > 0), n – число городов.
Пример 1.1 Решить задачу коммивояжера, определяемую матрицей:
/>
Сначала, пользуясь формулой (1.1), определяем значения В(i, {j}):
В(2, {3}) = 5 + 6 = 11; В(3, {2}) = 2 + 2 = 4; В(4, {2}) = 5 + 2 =7;
В(2, {4}) = 2 + 1 = 3; В(3, {4}) = 1 + 1 = 2; В(4, {3}) = 4 + 6 =10.
Далее по формуле (1.2) последовательно получаем (в левой частикаждого из ниже записанных равенств выделены те значения параметра j, на которых при подсчете реализуется указанныйв правой части (1.2) минимум):
В(2, {3, 4}) = min [s23 +B(3,{4}); s24 + B(4,{3})] = min(5 + 2; 2 + 10)=7;
В(3, {2, 4}) = min [s32 +B(2,{4}); s34 + B(4,{ 2})] = min(2 + 3; 1 + 7 )=5;
В(4, {2, 3}) = min [s42 +B(2,{ 3}); s43 + B(3,{ 2})] = min(5 + 11; 4 +4)=8;
В(1, {2, 3, 4}) = min [s12 +B(2,{3,4}) s13 + B(3,{ 2,4}) s14 + B(4,{2,3 })] =
= min (4 +7; 3 +5; 4 + 8 ) = 8.
Итак, оптимальное значение критерия в рассматриваемом примереравно 8.
Выполненные выделения позволяют определить оптимальный маршрут. Онследующий:
1 ® 3 ® 2 ® 4 ® 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). Поэтому
/> /> (1.3)
Предположим, что значения функции В*(V, i) для всех i Î N и всех возможных k-элементных (k
/> (1.4)
Уравнения (1.3)–(1.4) – рекуррентные соотношения динамическогопрограммирования для решения классической задачи коммивояжера, они обеспечиваютреализацию прямого метода Беллмана.
Пример 1.2 Методом прямого счета решить задачу коммивояжера,определяемую матрицей:
/>
(заметим, что матрица S в данном примере та же, что и в предыдущем).
Сначала, пользуясь формулой (1.3), определяем значения В*( {j }, i):
В*({2}, 3) = 4 + 5 = 9; В*({3}, 2) = 3 + 2 = 5; В*({4}, 2) = 4 + 5= 9;
В*({2}, 4) = 4 + 2 = 6; В*({3}, 4) = 3 + 1 = 4; В*({4}, 3) = 4 + 4= 8.
Далее по формуле (1.4) последовательно получаем (в левой частикаждого из ниже записанных равенств выделены те значения параметра j, на которых при подсчете реализуетсяуказанный в правой части (1.4) минимум):
В*({2, 3}, 4) = min [B*({2},3) + s34; B*({3}, 2) + s24] = min(9 + 1; 5 + 2)= 7;
В*({2, 4}, 3) = min [B*({2},4) + s43; B*({4}, 2) + s23] = min(6 + 4; 9 + 5 )= 10;
В*({3, 4}, 2}) = min [B*({3},4) + s42; B*({4}, 3) + s32] = min(4 + 5; 8 + 2)= 9;
В*({2, 3, 4}, 1) = min [B*({2,3}, 4) + s41; B*({2, 4}, 3) + s31; B*({3, 4}, 2) + s21;] = min (7 + 1; 10 +6; 9+ 2 ) = 8.
Итак, оптимальное значение критерия в рассматриваемом примереравно 8.
Выполненные выделения позволяют определить оптимальный маршрут. Онследующий:
1 ® 3 ® 2 ® 4 ® 1./>
4. Задача коммивояжераметодом ветвей и границ
Другим алгоритмом решения задачи коммивояжера является методветвей и границ. В сущности, это некоторая модификация полного переборарешений, оптимизируемая за счет того, что по определенным признакам отсекаютсянеоптимальные множества перебора.
Формально строится дерево вариантов, начиная от корня. В корненеобходимо дать верхнюю и нижнюю оценки. Далее ветвимся. Чем меньший фрагментдерева придется построить, тем успешнее сработал метод ветвей и границ.
Имеют место следующие определения:
Текущий рекорд – наибольшая из полученных в процессе реализацииметода нижних оценок.
Вершина именуется мертвой, если верхняя оценка в ней не превышаеттекущего рекорда. Выполнять в ней дальнейшее ветвление бесполезно.
Терминальной называется вершина, в которой верхняя и нижняя оценкисовпадают.
Вершина, ветвление в которой уже выполнено, называется закрытой.
Вершины, которые не являются мертвыми, терминальными илизакрытыми, называются открытыми. Дальнейшее ветвление делаем в них.
Решение заканчивается тогда, когда в нашем дереве вариантов нетоткрытых вершин. Оптимальным решением будет текущий рекорд.
Верхняя оценка определяется при помощи «жадного» алгоритма.
/>
Жадный алгоритм – алгоритм нахождениянаикратчайшего расстояния методом выбора самого короткого, ещё не выбранногоребра, при условии, что оно не образует цикла с уже выбранными рёбрами.«Жадным» этот алгоритм назван потому, что на последних шагах приходится жестокорасплачиваться за жадность (последнее ребро, как правило, самое большое илиблизко к нему по длине).
Стратегия: «иди в ближайший (в который еще невходил) город». Рассмотрим для примера сеть на рис. 2, представляющую узкийромб. Пусть коммивояжер стартует из города 1. Алгоритм «иди вы ближайший город»выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить зажадность, возвращаясь по длинной диагонали ромба. В результате получится некратчайший, а длиннейший тур.
Чтобы вычислить нижнюю оценку, сначала суммируем минимальныеэлементы по строкам и по столбцам, а затем из полученных сумм выбираемнаибольшую, но надо учитывать конфликт.
Пример 2.1 Решить методом ветвей и границ задачу коммивояжера,определяемую матрицей:
/>
1. Вычисляем верхнюю и нижнюю оценки в корне:
Верхнюю оценку подсчитываем, пользуясь, так называемым, «жадным»алгоритмом: каждый переход делаем из текущего в ближайший город. Получаеммаршрут:
1 ® 2 ® 4 ® 3 ® 5 ®1
Суммарная стоимость данного маршрута равна 12, она определяетверхнюю оценку в корне.
Чтобы вычислить нижнюю оценку, сначала суммируем минимальныеэлементы по строкам и по столбцам, а затем из полученных сумм выбираемнаибольшую:
По строкам: 2 + 1 + 2 + 2 + 2 = 9
По столбцам: 2 + 2 + 3 + 1 + 2 = 10
Выбираем максимум из значений и выбираем 10.
Проанализируем столбцы: можем сдвинуться на 2 (конфликт). Отсюданижний предел равен 10 + 2 = 12.
●/>
1 – 2 Далее из корневой вершины начинаем ветвление по городам, в которыеможем идти из первого:
1 — 3 />/>/>/>●/>/> /> /> /> /> />
1-5 />
1 — 4 />
Далее подсчитываем верхние и нижние оценки для новых вершин:
1 – 2: Верхняя оценка («жадный алгоритм»), определяемая суммарной
стоимостью данного маршрута 1 ® 2 ® 4 ® 3 ® 5 ®1 равна 13. Нижняя оценка определяетсясуммой минимальных элементов строк с учетом того, что идем из 1го города во 2й.Она совпадает с нижней оценкой в корне и равна 12.
1 – 3: Верхняя оценка («жадный алгоритм»), определяемая суммарнойстоимостью данного маршрута 1 ® 3 ® 2 ® 5 ® 4®1, равна 16. Нижняя оценка определяетсясуммой минимальных элементов строк с учетом того, что из 1го города идем в 3й.Она равна 2+2+4+ 1+2 = 11 и плюс 2 с учетом конфликта. Итого получаем 13.
1 – 4: Верхняя оценка («жадный алгоритм»), определяемая суммарнойстоимостью данного маршрута 1 ® 4 ® 2 ®5® 3 ® 1 равна 24. Нижняя оценка определяетсясуммой минимальных элементов строк с учетом того, что идем из 1го города в 4й.Она равна 18.
1 – 5: Верхняя оценка («жадный алгоритм»), определяемая суммарнойстоимостью данного маршрута 1 ® 5 ® 4 ®2® 3 ® 1 равна 23. Нижняя оценка определяетсясуммой минимальных элементов строк с учетом того, что идем из 1го города в 5й.И она равна 16
13/12
13/12 />/>/>/>
1-5 />●/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />
1 — 4 />
1-2
1 — 3 /> /> /> /> />
23/16 /> /> /> /> /> /> /> /> /> /> /> /> />
24/18 />
Проанализируем полученные результаты. Текущий рекорд равен 12.
Переход в вершины 3, 4 и 5 дает ухудшение критерия, поэтому данныевершины именуются мертвыми и ветвление из них далее бессмысленно. Дальше будемветвиться во 2 и 3 вершинах.
1 – 2 – 3: Верхняя оценка («жадный алгоритм»), определяемаясуммарной стоимостью данного маршрута 1 ® 2 ® 3 ® 4 ® 5 ®1 равна 19. Нижняя оценка определяетсясуммой минимальных элементов строк с учетом того, что идем из 1го города во 2й,из 2го в 3й. Она равна 14.
1 – 2 – 4: Верхняя оценка («жадный алгоритм»), определяемаясуммарной стоимостью данного маршрута 1 ® 2 ® 4 ® 3 ® 5®1, равна 13. Нижняя оценка определяетсясуммой минимальных элементов строк с учетом того, что из 1го города идем в 2й,из 2го в 4й. Она равна 13.
1 – 2 – 5: Верхняя оценка («жадный алгоритм»), определяемаясуммарной стоимостью данного маршрута 1 ® 2 ® 5 ® 4 ® 3®1, равна 16. Нижняя оценка определяетсясуммой минимальных элементов строк с учетом того, что из 1го города идем в 2й,из 2го в 5й. Она равна 12./> /> /> /> />
13/12 />
1-5 />
1-2-3 />/>
13/12
1-2 />/>
1 — 4 />
23/16 />/>●/> /> /> /> /> /> /> /> /> /> /> /> />
1 — 3 /> /> /> /> /> /> /> />
16/13 /> />
13/13 />/>/>/> /> /> /> /> /> /> /> /> /> /> /> /> />
16/12 /> />
Проанализируем полученные результаты. Переход в вершины 3 и 4 даетухудшение критерия, поэтому данные вершины именуются мертвыми и ветвление изних далее бессмысленно. Дальше будем ветвиться в 5й вершине.
1 – 2 – 5–3: Верхняя оценка («жадный алгоритм»), определяемаясуммарной стоимостью данного маршрута 1 ® 2 ® 5 ® 3 ® 4®1, равна 17. Нижняя оценка определяетсясуммой минимальных элементов строк с учетом того, что из 1го города идем в 2 ® 5® 3. Она равна 15.
1 – 2 – 5–4: Верхняя оценка («жадный алгоритм»), определяемаясуммарной стоимостью данного маршрута 1 ® 2 ® 5 ® 4 ® 3®1, равна 16. Нижняя оценка определяетсясуммой минимальных элементов строк с учетом того, что из 1го города идем в 2й,из 2го в 5й. Она равна 13.
13/12
13/12 />/>/>
1-2 />
1 — 4 />/>/>●/> /> /> /> /> /> /> /> />
/>/>/>/>
13/13 />/>/> /> /> /> /> /> /> /> /> /> /> /> /> />
1-2-5-3 /> /> /> /> /> /> /> /> /> />
17/15 /> />
Врезультате решения задачи, дальше ветвиться нам не куда. Запишемоптимальный маршрут коммивояжера:
1 ® 2 ® 5 ® 4 ® 3®1
Таким образом, задача решена.
Заключение
/>Практика порождает все новые и новые задачи оптимизации, причем ихсложность растет. Требуются новые математические модели и методы, которыеучитывают наличие многих критериев, проводят глобальный поиск оптимума. Другимисловами, жизнь заставляет развивать математический аппарат оптимизации.
Реальные прикладные задачи дискретной оптимизации очень сложны.Современные методы оптимизации далеко не всегда справляются с решением реальныхзадач без помощи человека. Нет, пока такой теории, которая учла бы любыеособенности функций, описывающих постановку задачи. Следует отдаватьпредпочтение таким методам, которыми проще управлять в процессе решения задачи.
Список использованныхисточников
1. Беллман,Р. Динамическое программирование – М.: ИЛ, 1960.– 400 с.
2. Беллман,Р. Прикладные задачи динамического программирования – М.: Наука, 1965. – 457 с.
3. СигалИ.Х., Иванова А.П. Введение в прикладное дискретное программирование: модели ивычислительные алгоритмы. М.: ФИЗМАТЛИТ, 2003. — 240 с.
4. Р.Беллман, С. Дрейфус Прикладные задачи динамического программирования – М., 1965г., 460 стр.