/>Министерство образования РоссийскойФедерацииУфимский государственный авиационныйтехнический университет
Кафедра автоматизированныхтехнологических систем
Курсоваяработа
Подисциплине: Программирование систем
На тему:Дискретное программирование
Уфа 2011
Содержание
1. Введение
2. Задачи с неделимостями
2.1 Пример кодана языке Java
2.2 Пример кодана языке C#
3. Комбинаторные задачи
4. Задачи с разрывными целевыми функциями
4.1 Основныеидеи и принципы
4.2 Описаниеалгоритма
4.3 Примеррешения ЦЗЛП методом Гомори
4.3.1 Итерация 1
4.3.1 Итерация 2
5. Метод ветвей и границ
5.1 Общая схема метода «ветвей играниц»
5.2 РешениеЦЗЛП методом ветвей и границ
6. Заключение
/>/>/>1. Введение
Основные понятия. Многие экономическиезадачи характеризуются тем, что объемы управляемых ресурсов (в силу тех илииных объективных свойств) могут принимать только целые значения. Математическаяформализация данных ситуаций приводит к моделям дискретного программирования. Вобщем виде задача дискретного программирования может быть сформулирована какзадача нахождения максимума (или минимума) целевой функции f(x1, x2,...,xn) намножестве D, определяемом системой ограничений
/>
где Ω — некоторое конечное, илисчетное*, множество. Условие х∊Ω.называется условием дискретности. Особое место среди дискретных задач занимаетцелочисленная задача линейного программирования в канонической форме (ЦКЗЛП):
* Напомним, что примерами счетных множествявляются множества натуральных, целых и рациональных чисел.
/>
где Z+ ={0; 1; 2; ...} — множество неотрицательных целых чисел.
Заметим, что в некоторых ситуацияхтребование «целочисленности» может быть наложено лишь на некоторыепеременные xj, что кардинальноне меняет характера задачи.
/>
Принципиальная сложность, вызываемая наличиемусловий целочисленности в системе ограничений оптимизационной задачи, состоит втом, что в значительном количестве случаев невозможно заменить дискретнуюзадачу ее непрерывным аналогом и, найдя соответствующее решение, округлить егокомпоненты до ближайших целых значений. Пример, показанный на рис.1,демонстрирует, что при округлении оптимального плана х* обычной задачи ЛП доцелых значений получается точка ([х1*],[x2*]), не принадлежащая области допустимых планов задачи D.Условимся целую часть числа хj.обозначать [хj], а дробную —как {хj}. Тогда хj =[хj]+{хj}.Отдельно следует добавить, что если даже оптимальный план непрерывной задачи,округленный до целых значений компонент, окажется допустимым, то целеваяфункция может вести себя так, что ее значение будет на нем существенно «хуже»,чем на оптимальном плане целочисленной задачи.
Перечисленные проблемы предопределилинеобходимость разработки специальных методов решения дискретных и целочисленныхзадач. Но прежде чем говорить собственно о методах решения, более подробноостановимся на классификации задач дискретного программирования. В литературе,как правило, выделяют следующие классы дискретных оптимизационных задач:
Ø задачи с неделимостями;
Ø экстремальные комбинаторныезадачи;
Ø задачи с разрывными целевымифункциями;
Ø задачи на несвязных и невыпуклыхобластях и др.
/>2. Задачи с неделимостями
В подавляющем большинстве случаев наличиеусловий неделимости определяется физическими свойствами моделируемых объектов.Так, например, они могут появиться в качестве дополнительных ограничений в ужерассматривавшейся нами выше задаче производственного планирования, если в нейосуществляется управление выпуском крупной штучной продукции.
Классическим представителем задач данногокласса стала так называемая задача о ранце. Ее фабула носит достаточно условныйхарактер и состоит в том, что солдат (или турист), собирающийся в поход, можетнести груз весом не более W кг. Этот груз может состоять из набора предметов nтипов, каждый предмет типа j весит wj кги характеризуется некоторой «полезностью» uj, j
/>
Как нетрудно заметить, представленная математическаямодель носит универсальный характер, и к ней могут быть сведены многиеэкономические задачи. Ярким подтверждением этому служит и тот факт, что влитературе она также известна как задача о загрузке судна.
/>2.1 Пример кода на языке Java
intknapsack(int weights[], int costs[], int needed) {
intn = weights.length;
intdp[][] = new int[needed + 1][n + 1];
for(int j = 1; j
for(int w = 1; w
if(weights[j-1]
dp[w][j]= Math.max(dp[w][j — 1], dp[w — weights[j-1]][j — 1] + costs[j-1]);
}else {
dp[w][j]= dp[w][j — 1];}
}
}
returndp[needed][n];
}
/>2.2 Пример кода на языке C#
intknapsack(int[] weights, int[] costs, int needed)
{int n = weights.Length;
int[,]dp = new int[needed + 1, n + 1];
for(int j = 1; j
{for (int w = 1; w
{if (weights[j — 1]
{dp[w, j] = Math.Max(dp[w, j — 1], dp[w — weights[j — 1], j — 1] + costs[j — 1]);
}
else
{dp[w, j] = dp[w, j — 1];}
}
}
returndp[needed, n];}
/>
3. Комбинаторные задачи
К данному классу относятся задачиоптимизации функции, заданной на конечном множестве, элементами которого служатвыборки из n объектов.
Классическим представителем математическихпроблем такого рода стала задача о коммивояжере. Она состоит в составлениимаршрута посещения торговым агентом, находящимся в некотором начальном пункте,n других городов при условии, что задана матрица стоимостей переездов из городав город
/>
(с учетом начального). Причем допустимымявляется такой маршрут, который предусматривает однократное посещение всехгородов и возвращение в исходный пункт. Очевидно, что наилучший маршрут долженминимизировать суммарную стоимость переездов.
Планом задачи является маршруткоммивояжера, и его можно задать с помощью так называемой матрицы смежности
дискретный программированиеитерация комбинаторный
/>
элементы которой определяются следующимобразом:
1, если в маршруте предусмотрен переезд из пункта i в j,
xi,j = 0, если в маршруте не предусмотрен переезд из пункта i в j,
причем по условию задачи xii =0, i
Допустимыми планами служат связныемаршруты, однозначно определяемые упорядоченным набором посещаемых пунктов:
/>
Каждыйтакой маршрут можно отождествить с перестановкой n чисел (упорядоченнойвыборкой из n элементов по n). В свою очередь, таким
перестановкам взаимно однозначносоответствуют матрицы X, у которых в каждой строке и каждом столбце содержитсяточно одна единица.
Сучетом сказанного задача коммивояжера принимает вид целочисленной задачилинейного программирования:
/>
Условия 6 и 7 с содержательной точкизрения означают, что в каждый пункт можно въехать и выехать только один раз.Приведенная форма записи задачи коммивояжера 4-8 не является самой рациональнойи предназначена только для того, чтобы подчеркнуть ее общность с другимизадачами дискретного программирования. Существует и другая форма, которая болееярко отражает комбинаторный характер данной проблемы:
/>
где D — множество перестановок чисел от 1до n.
Отдельно следует остановиться на том, чтозадача коммивояжера имеет большое количество содержательных аналогов. Скажем, каналогичной модели приведет задача разработки графика переналадки оборудования,которое может выпускать разные типы изделий, но требует определенных затрат(временных или материальных) при переходе с одного технологического режима надругой.
/>4. Задачи с разрывными целевыми функциями
Как уже упоминалось выше, многиеэкономические системы характеризуются наличием так называемых постоянныхзатрат, которые должны быть произведены независимо от объема производства. Учетв моделях этих и подобных факторов приводит к появлению в них целевых функций,не обладающих свойством непрерывности. В качестве примера может быть приведенатранспортная задача с фиксированными доплатами. Она отличается от транспортнойзадачи в матричной постановке, рассмотренной в главе 3, тем, что в ней затратыпо перевозке груза из i-го пункта производства в j-й пункт потребленияопределяются как
/>
где сi,j — по-прежнему издержки на перевозку единицы груза;
di,j — фиксированная доплата за аренду транспортных средств.
При таких предпосылках целевая функциясуммарных затрат на перевозку
/>
содержит «скачкообразные»разрывы, что существенно затрудняет ее минимизацию, поэтому стандартный методрешения основан на следующем преобразовании. Если ввести вспомогательныепеременные уi,j, такие, что
/>
то целевая функция примет вид
/>
Действительно,если уi,j =0, то переменные хi,j =0, а при уi,j =1 неравенства 12 становятсянесущественными, поскольку они и так справедливы для любого опорного плана.Следовательно, задача 13 эквивалентна исходной задаче 10. В силу характера ограничений11-12 задача 13 является задачей частично-целочисленного программирования.
Перечисленные примеры далеко неисчерпывают всего многообразия задач дискретного программирования. Однако болееподробное их рассмотрение требует привлечения достаточно сложногоматематического аппарата и выходит за рамки данной книги.
Впоследующих параграфах мы остановимся на способах решения наиболее известных ихорошо изученных дискретных задач. Излагаемые ниже методы не имеютуниверсального характера, с каждым из них связаны определенные ограничения и,соответственно, ответ на вопрос о выборе того или иного из них зависит отконкретных особенностей решаемой задачи. Более того, цель изложения состоит втом, чтобы создать у читателя общие представления об основных идеях и подходах,не углубляясь далеко в вычислительные и математические тонкости, которымибуквально изобилуют алгоритмы дискретного программирования. Заметим также, чтодостаточно эффективный и широко применяемый подход к решению целочисленныхзадач основан на сведении их к задачам транспортного типа. Это объясняется тем,что если в условиях транспортной задачи значения запасов (аi) и потребностей (bj) являются целочисленными, тоцелочисленным будет и оптимальный план.
/>
4.1 Основные идеи и принципы
Данныйметод, который также носит название метода отсекающих плоскостей, предназначендля решения ЦЗЛП в канонической форме 2-3. Кратко представим его основные идеи.
Впервые был предложен Р.Гомори в 1957-1958гг.
Отправной точкой для решения задачи 2-3 являетсярешение ее непрерывного аналога, т. е. КЗЛП без учета условий целочисленности.Если получаемый в результате оптимальный план х* содержит только целыекомпоненты, то мы автоматически получаем и соответствующее решение ЦЗЛП. Впротивном случае к системе ограничений задачи должно быть добавлено такоеограничение, для которого:
Ø найденный нецелочисленныйоптимальный план х* не удовлетворяет вновь добавляемому ограничению;
Ø любой допустимый целочисленныйплан непрерывной задачи 2-3 удовлетворяет вновь добавляемому ограничению.
Такое ограничение называют правильнымотсечением. В первой геометрической интерпретации правильному отсечениюсоответствует гиперплоскость, отсекающая от выпуклого многогранного множествадопустимых планов D некоторый многогранник, не содержащий целочисленных планов.
Добавив сформированное отсекающееограничение к уже существующим, мы получаем новую оптимизационную задачу, послечего вычислительный процесс итеративно повторяется.
Теперь необходимо несколько более подробноостановиться на принципах формирования отсекающих ограничений. Воспользуемсясистемой обозначений, применявшихся при изложении вычислительных методовлинейного программирования. Пусть β(q) — оптимальный базис, полученный на последней итерациирешения нецелочисленной ЗЛП. Если обозначить через αi,j и άi коэффициенты матрицы задачи и вектора ограниченийв текущем базисе (A(β(q))и b(β(q)))
/>
то i-ое уравнение в системе ограниченийзадачи примет вид:
/>
Так как план x(β(q)) является базисным, то в каждомуравнении все коэффициенты αi,j,соответствующие базисным столбцам (j∊N(β(q))), равнынулю за исключением некоторого αi,ji =1,на основе чего из (4.18) получаем:
/>
Если представить каждый коэффициент αi,j в виде суммы целой и дробнойчастей αi,j =[αi,j]+{αi,j}, то получим
/>
или
/>
Из 18 следует, что если все хj, j=1: n являются целыми, то целымбудет и выражение
/>
стоящее в левой части 18, и, стало быть,правая часть данного уравнения:
/>
также должна быть целой. Предположим, что
/>
тогда, в силу того, что 0 ≤ {άi}
/>
Однако неравенства 19 и 20 противоречаттребуемой целочисленности правой части 18 xj(β(q)).Следовательно, для целочисленных решений должно выполняться условие,противоположное неравенству 19, или, что то же самое,
/>
В то же время 21 не выполняется для любогонецелочисленного базисного плана х. Действительно, небазисные компоненты планаравны нулю: хj =0, j∊N(β(q)),и 21 приобретает вид {άi}≤0 {άi}=0, но это противоречит предположению о нецелочисленности плана х, т. к. вбазисном плане хi = άi. Все сказанное позволяетутверждать, что ограничение 21 задает правильное отсечение.
Таким образом, с точки зрения организациитехники, вычислений для осуществления правильного отсечения мы должны к системеограничений нецелочисленной линейной задачи, решаемой на q-й итерации, добавитьусловие
/>
где xn+1 ≥0 — фиктивная переменная, добавляемая дляпреобразования неравенства в строгое равенство. Ей соответствует нулевойкоэффициент в целевой функции.
Данному преобразованию условий задачибудет соответствовать преобразование симплекс-таблицы, показанное на рис.2. Нанем по соображениям обеспечения наглядности использованы обозначения 14 ипредполагается, что текущий базис β(q) состоит из первых m столбцов.
/>
Индекс i соответствует выбранной дляформирования отсечения строке симплекс-таблицы, содержащей нецелочисленноезначение bi(β(q)).
Как видно из рис.2, техническипреобразование таблицы сводится к дописыванию одной строки и одного столбца.При этом легко убедиться, что модифицированные столбцы
/>
совместно с добавленным столбцом
/>
образуют сопряженный (двойственнодопустимый) базис для сформированной задачи, а (ά1, ..., άm, -{άi})являются ненулевыми компонентами соответствующего псевдоплана. Исходя из этого,приходим к тому, что для решения вновь полученной задачи может быть эффективноприменена процедура двойственного симплекс-метода.
Поскольку в начальном псевдоплане имеетсятолько одна отрицательная компонента (-{άi}), то из базиса должен быть выведен соответствующий ейвектор аn+1 . Далее, следуярекомендациям алгоритма двойственного симплекс-метода, находим оптимальныйплан. Если он не является целочисленным, то описанные действия итеративноповторяются.
Если в ходе решения дополнительнаяпеременная хn+1 вновьстановится базисной, ее значение оказывается безразличным для основныхпеременных. Поэтому строку и столбец, отвечающие ей, вычеркивают. Сгеометрической точки зрения это можно обосновать так: если псевдоплан оказываетсявнутри полупространства хn+1 ≥0,то дополнительное ограничение, определяемое гиперплоскостью хn+1=0, становится несущественным иопускается.
/>
4.2 Описание алгоритма
Приведем обобщенную схему алгоритмаГомори. Структурно он делится на так называемые большие итерации. Каждаябольшая итерация содержит этапы:
1) Решение «текущей» задачиметодами линейного программирования (малые итерации). На первой итерации вкачестве «текущей» задачи выступает нецелочисленный аналог исходнойЦЗЛП.
2) Определение первой нецелочисленнойкомпоненты в оптимальном плане, полученном на этапе 1. Если все компонентыявляются целочисленными, то алгоритм завершается.
3) Построение для найденной компонентыусловия отсечения согласно правилу 21, добавление сформированного ограничения ксистеме ограничений текущей задачи, т. е. формирование новой текущей задачи.Переход на начало следующей большой итерации.
Двойственный симплекс-метод являетсяосновой для метода Гомори, так как он позволяет учитывать новые дополнительныеограничения (правильные отсечения) и переходить от текущего псевдоплана кновому оптимальному плану.
Можно доказать, что приведенный алгоритмконечен. Это означает, что на некотором шаге (итерации) будет найден целочисленныйоптимальный план или обнаружен факт отсутствия допустимых целочисленных планов.
В качестве существенного замечания поповоду метода Гомори следует добавить, что при его практической реализации наЭВМ следует считаться с ошибками округления, т, к. в условиях машиннойарифметики практически ни один план не будет целочисленным. Кроме того,накапливающиеся погрешности могут внести возмущения в алгоритм и «увести»от оптимального целочисленного плана.
/>
4.3 Пример решения ЦЗЛП методом Гомори
Рассмотрим особенности применения методаГомори на конкретном примере. Пусть дана задача со следующими условиями:
/>
/>
4.3.1 Итерация 1
Используя обычный симплекс-алгоритм,решаем непрерывный аналог исходной задачи, в котором игнорируются условия целочисленности25. В качестве исходного базиса можно взять первый и второй столбцы. На егооснове заполняется таблица T(1,1) (первыйиндекс в обозначении таблицы соответствует «большой» итерации, авторой — «малой»).
/>
Как видно из строки оценок, данный базисявляется оптимальным, однако соответствующий ему план х ={11/5,17/5, 0) неявляется целочисленным, поэтому выбираем из таблицы T(1,1) строку, содержащую первый нецелый элемент, исогласно формуле 22 строим отсекающее ограничение:
/>
после чего переходим к следующей «большой»итерации.
/>
4.3.1 Итерация 2
С учетом сформированного отсекающегоограничения заполняем симплекс-таблицу T(2,1).
/>
В соответствии с алгоритмом двойственногосимплекс-метода переходим к следующему базису N(β(2,2))={1, 2, 3}.
/>
План, достигнутый в таблице T(2,2),является не только оптимальным (b(β(2,2))>0), но и полностью состоит из целочисленныхкомпонент, т. е. решение задачи найдено: х* = (1, 2, 1) и f(x)=7.
/>
5. Метод ветвей и границ
/>
5.1 Общая схема метода «ветвей и границ»
Другим широко применяемым для решениязадач дискретного программирования методом является метод ветвей и границ.Впервые данный метод для решения ЦЗЛП предложили в 1960 г. Лэнг и Дойг, а его «второе рождение» произошло в 1963 г. в связи с выходом работы Литтла, Мурти, Суини и Кэрел, посвященной решению задачи окоммивояжере [33].
Вообще говоря, термин «метод ветвей играниц» является собирательным и включает в себе целое семейство методов,применяемых для решения как линейных, так и нелинейных дискретных задач,объединяемое общими принципами. Кратко изложим их.
Пусть стоит задача: (*)
/>
где D — конечное множество.
Алгоритм является итеративным, и на каждойитерации происходит работа с некоторым подмножеством множества D. Назовем этоподмножество текущим и будем обозначать его как D(q), где q — индекс итерации. Перед началом первой итерациив качестве текущего множества выбирается все множество D (D(1)=D), и для него некоторымспособом вычисляется значение верхней оценки для целевой функции max f(x) ≤ξ( D(1)). Стандартнаяитерация алгоритма состоит из следующих этапов:
1) если можно указать план x(q)
2) если такой план не найден, то областьопределения D(q) некоторымобразом разбивается на подмножества D1(q), D2(q), ...,Dlq(q), удовлетворяющие условиям:
/>
Для каждого подмножества находятся оценкисверху (верхние границы) для целевой функции ξD1(q),ξD2(q), ..., ξDl1(q), уточняющие ранее полученную оценку ξD(q), то есть ξDi(q) ≤ ξD(q), i
2.1) если существует такой план х(q), что то этот план оптимальный.
/>
/>
2.2) если такой план не найден, товыбирается одно из множеств Di(q), i>1:lq (как правило, имеющее наибольшуюоценку.
/>
Все имеющиеся к текущему моменту концевыеподмножества, т. е. те подмножества, которые еще не подверглись процессудробления, переобозначаются как D1(q+1), D2(q+1),...,Dl(q+1)(q+1), после чего процесс повторяется.
Схема дробления множества D представленана рис.3 в виде графа. Существуют и более сложные системы индексации подмножеств,при которых не требуется их переобозначение на каждом шаге.
Конкретные реализации метода ветвей играниц связаны с правилами разбиения на подмножества (правилами ветвления) ипостроения оценок значений целевых функций на данных подмножествах (границ).
/>
5.2 Решение ЦЗЛП методом ветвей и границ
Рассмотрим применение алгоритма методаветвей и границ для решения ЦЗЛП (4.2)-(4.3). Как уже упоминалось, через D(q) обозначается подмножествомножества допустимых планов задачи. Перед началом первой итерации (q = 1) вкачестве текущего множества берется все множество D (D(1) = D), после чего решается стандартная задачалинейного программирования (D(1),f). Нетрудно заметить, что она является непрерывным аналогом исходной задачи2-3.
/>
Если найденный оптимальный план />(1) содержит только целочисленныекомпоненты, то он является и оптимальным планом для 2-3: />(1) = x*. В противном случае значение f(/>(1)) становится оценкой (верхнейграницей) значения целевой функции на множестве D(1), и мы переходим к выполнению стандартной итерацииалгоритма. Опишем входящие в нее этапы.
1) Выбирается некоторая нецелочисленнаякомпонента плана />k(q).Поскольку в оптимальном плане она должна быть целой, то можно наложитьограничения xk ≤ [/>k(q)] и xk ≥[/>k(q)]+1. Таким образом, D(q) разбивается на подмножества
/>
Графическая интерпретация такого разбиениямножества D(q) приведена на рис.4.
2) Решаются задачи линейногопрограммирования
/>
Соответствующие максимальные значенияцелевой функции принимаются как ее оценки на этих множествах:
/>
Если оптимальный план /> для одной из решенныхзадач удовлетворяет условию
/>
и содержит только целые компоненты, то,значит, найдено решение основной задачи 2-3. В противном случае среди всехконцевых подмножеств, полученных как на предыдущих (Di(q)),так и на текущем (D1(q), D2(q))этапе, выбирается область с наибольшей оценкой ξ(Di(q)).Она становится текущим рассматриваемым подмножеством (D(q+1)). Далее производится перенумерация концевыхмножеств и вычислительный процесс итеративно повторяется.
При решении задач (D1(q), f) и (D2(q), f) можно воспользоватьсярезультатами решения предыдущей задачи (D(q), f). Рассмотрим вариант организации вычислительногопроцесса на примере задачи (/>1(q), f)(для (/>2(q), f) он выглядит аналогично с точностью до знаковнеравенств).
Предположим, что на последнем шаге решения задачи (D(q), f) был получен оптимальныйбазис β. Без ограничения общности можно считать, что он состоит из первыхm столбцов матрицы задачи. Данное предположение делается исключительно дляобеспечения наглядности дальнейшего изложения и очевидно, что его выполненияможно всегда добиться за счет простой перенумерациивекторов аj. По аналогии спредыдущим параграфом введем обозначения для элементов матрицы задачи (D(q), f) и ее вектора ограниченийотносительно базиса />:
/>
Тогда система ограничений задачи (D(q), f) может быть представлена как
/>
а получаемая на ее основе системаограничений задачи (/>1(q), f)как
/>
Или
/>
где хn+1 ≥ 0 — фиктивная переменная, которой соответствуетнулевой коэффициент в целевой функции, добавляемая для преобразованиянеравенства в строгое равенство.
Очевидно, что 1≤k≤m, т. к.небазисные компоненты оптимального плана (m+1≤j≤n) равны нулю, т.е. являются заведомо целочисленными. Тогда с учетом сделанных предположений овиде базиса /> можнозаписать:
/>
Как видно из 35, в k-м столбце имеетсявсего два отличных от нуля элемента: в k-й и (m+1)-й строках. Если вычесть из(m+1)-го уравнения k-e, то, учитывая, что [άk] – άk =-{άk}, получим эквивалентную систему:
/>
Проведенные преобразования системыограничений D1(q) позволили явно выделитьсопряженный базис, образуемый столбцами с номерами 1,..., m, n+1, исоответствующий ему псевдоплан (ά1, ..., άm,0,...., 0, -{άk}), т.е.для решения задачи (D1(q), f) может быть примененалгоритм двойственного симплекс-метода. Практически вычислительный процесс дляданного этапа сводится к преобразованию к симплекс-таблицы, показанному на рис.5.
/>
Для случая задачи (D2(q), f) преобразование симплекс-таблицы, получаемое на базеаналогичных рассуждений, приведено на рис.6.
/>
Очевидным недостатком алгоритма методаветвей и границ при решении задач большой размерности является необходимостьперебрать слишком большое количество вариантов перед тем, как будет найденоптимальный план. Однако он отчасти может быть преодолен, если ограничитьсяпоиском не оптимального, а просто «хорошего» (близкого коптимальному) плана. О степени такой близости и скорости приближения кэкстремуму нетрудно судить по изменению значений оценок.
Подчеркнем, что приведенная реализацияметода ветвей и границ является одной из многих. Помимо нее, например, оченьпопулярна версия метода решения задачи коммивояжера, в которой для ветвления ипостроения оценок используют специфические свойства данной модели.
/>
6. Заключение
Дискретные оптимизационные задачи находят широкое применение в различныхобластях, где используются математические методы для анализа происходящих тампроцессов. Необходимость решения таких задач приводит к тому, что дискретнаяоптимизация становится важным элементом образования специалистов, связанных сее применением при решении задач, возникающих в приложениях. Поэтому технологиярешения задач дискретного программирования должна стать одной из важных составныхчастей современного математического образования для специалистов по прикладнойматематике. В настоящее время разработаны современные методы и алгоритмырешения задач дискретного программирования. Разработаны пакеты прикладныхпрограмм, позволяющие решать ряд стандартных задач дискретного программирования.Знание существа применяемых алгоритмов и технологий их реализации позволяетболее эффективно использовать разработанные пакеты. При возникновении новыхнестандартных задач реализация алгоритмов их решения требует информации отехнологии решения задач дискретной оптимизации.
Для изучения материала необходимы знания основ математического анализа,линейной алгебры, линейного программирования и основ теории графов.