Дискретное программирование (стр. 1 из 4)
Министерство образования Российской Федерации
Уфимский государственный авиационный технический университет
Кафедра автоматизированных технологических систем
Курсовая работа
По дисциплине: Программирование систем
На тему: Дискретное программирование
Уфа 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. Заключение
Основные понятия. Многие экономические задачи характеризуются тем, что объемы управляемых ресурсов (в силу тех или иных объективных свойств) могут принимать только целые значения. Математическая формализация данных ситуаций приводит к моделям дискретного программирования. В общем виде задача дискретного программирования может быть сформулирована как задача нахождения максимума (или минимума) целевой функции f(x1, x2,...,xn) на множестве D, определяемом системой ограничений
где Ω — некоторое конечное, или счетное*, множество. Условие х∊Ω. называется условием дискретности. Особое место среди дискретных задач занимает целочисленная задача линейного программирования в канонической форме (ЦКЗЛП):
* Напомним, что примерами счетных множеств являются множества натуральных, целых и рациональных чисел.
где Z+ ={0; 1; 2; ...} — множество неотрицательных целых чисел.
Заметим, что в некоторых ситуациях требование "целочисленности" может быть наложено лишь на некоторые переменные xj, что кардинально не меняет характера задачи.
Принципиальная сложность, вызываемая наличием условий целочисленности в системе ограничений оптимизационной задачи, состоит в том, что в значительном количестве случаев невозможно заменить дискретную задачу ее непрерывным аналогом и, найдя соответствующее решение, округлить его компоненты до ближайших целых значений. Пример, показанный на рис.1, демонстрирует, что при округлении оптимального плана х* обычной задачи ЛП до целых значений получается точка ([х1*],[x2*]), не принадлежащая области допустимых планов задачи D. Условимся целую часть числа хj. обозначать [хj], а дробную — как {хj}. Тогда хj =[хj]+{хj}. Отдельно следует добавить, что если даже оптимальный план непрерывной задачи, округленный до целых значений компонент, окажется допустимым, то целевая функция может вести себя так, что ее значение будет на нем существенно "хуже", чем на оптимальном плане целочисленной задачи.
Перечисленные проблемы предопределили необходимость разработки специальных методов решения дискретных и целочисленных задач. Но прежде чем говорить собственно о методах решения, более подробно остановимся на классификации задач дискретного программирования. В литературе, как правило, выделяют следующие классы дискретных оптимизационных задач:
Ø задачи с неделимостями;
Ø экстремальные комбинаторные задачи;
Ø задачи с разрывными целевыми функциями;
Ø задачи на несвязных и невыпуклых областях и др.
В подавляющем большинстве случаев наличие условий неделимости определяется физическими свойствами моделируемых объектов. Так, например, они могут появиться в качестве дополнительных ограничений в уже рассматривавшейся нами выше задаче производственного планирования, если в ней осуществляется управление выпуском крупной штучной продукции.
Классическим представителем задач данного класса стала так называемая задача о ранце. Ее фабула носит достаточно условный характер и состоит в том, что солдат (или турист), собирающийся в поход, может нести груз весом не более W кг. Этот груз может состоять из набора предметов n типов, каждый предмет типа j весит wj кг и характеризуется некоторой "полезностью" uj, j < 1: n. В рамках описанной ситуации вполне естественным представляется вопрос: сколько предметов каждого вида нужно положить в ранец, чтобы его суммарная полезность была максимальной? Если в качестве компонент плана хj. принять количество укладываемых предметов типа j, то данную задачу можно записать:
Как нетрудно заметить, представленная математическая модель носит универсальный характер, и к ней могут быть сведены многие экономические задачи. Ярким подтверждением этому служит и тот факт, что в литературе она также известна как задача о загрузке судна.
2.1 ПримеркоданаязыкеJava
int knapsack(int weights[], int costs[], int needed) {
int n = weights.length;
int dp[][] = new int[needed + 1][n + 1];
for (int j = 1; j <= n; j++) {
for (int w = 1; w <= needed; w++) {
if (weights[j-1] <= w) {
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];}
}
}
return dp[needed][n];
}
2.2 ПримеркоданаязыкеC#
int knapsack(int[] weights, int[] costs, int needed)
{ int n = weights.Length;
int[,] dp = new int[needed + 1, n + 1];
for (int j = 1; j <= n; j++)
{ for (int w = 1; w <= needed; w++)
{ if (weights[j - 1] <= w)
{ 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];}
}
}
return dp[needed, n];}
3. Комбинаторныезадачи
К данному классу относятся задачи оптимизации функции, заданной на конечном множестве, элементами которого служат выборки из n объектов.
Классическим представителем математических проблем такого рода стала задача о коммивояжере. Она состоит в составлении маршрута посещения торговым агентом, находящимся в некотором начальном пункте, n других городов при условии, что задана матрица стоимостей переездов из города в город
(с учетом начального). Причем допустимым является такой маршрут, который предусматривает однократное посещение всех городов и возвращение в исходный пункт. Очевидно, что наилучший маршрут должен минимизировать суммарную стоимость переездов.
Планом задачи является маршрут коммивояжера, и его можно задать с помощью так называемой матрицы смежности
дискретный программирование итерация комбинаторный
элементы которой определяются следующим образом:
| 1, если в маршруте предусмотрен переезд из пункта i в j,xi,j = 0, если в маршруте не предусмотрен переезд из пункта i в j,причем по условию задачи xii =0, i<1:n. |
Допустимыми планами служат связные маршруты, однозначно определяемые упорядоченным набором посещаемых пунктов:
Каждый такой маршрут можно отождествить с перестановкой n чисел (упорядоченной выборкой из n элементов по n). В свою очередь, таким
перестановкам взаимно однозначно соответствуют матрицы X, у которых в каждой строке и каждом столбце содержится точно одна единица.
С учетом сказанного задача коммивояжера принимает вид целочисленной задачи линейного программирования:
Условия 6 и 7 с содержательной точки зрения означают, что в каждый пункт можно въехать и выехать только один раз. Приведенная форма записи задачи коммивояжера 4-8 не является самой рациональной и предназначена только для того, чтобы подчеркнуть ее общность с другими задачами дискретного программирования. Существует и другая форма, которая более ярко отражает комбинаторный характер данной проблемы:
где D — множество перестановок чисел от 1 до n.
Отдельно следует остановиться на том, что задача коммивояжера имеет большое количество содержательных аналогов. Скажем, к аналогичной модели приведет задача разработки графика переналадки оборудования, которое может выпускать разные типы изделий, но требует определенных затрат (временных или материальных) при переходе с одного технологического режима на другой.
4. Задачи с разрывными целевыми функциями
Как уже упоминалось выше, многие экономические системы характеризуются наличием так называемых постоянных затрат, которые должны быть произведены независимо от объема производства. Учет в моделях этих и подобных факторов приводит к появлению в них целевых функций, не обладающих свойством непрерывности. В качестве примера может быть приведена транспортная задача с фиксированными доплатами. Она отличается от транспортной задачи в матричной постановке, рассмотренной в главе 3, тем, что в ней затраты по перевозке груза из i-го пункта производства в j-й пункт потребления определяются как
где сi,j — по-прежнему издержки на перевозку единицы груза;
di,j — фиксированная доплата за аренду транспортных средств.
При таких предпосылках целевая функция суммарных затрат на перевозку
содержит "скачкообразные" разрывы, что существенно затрудняет ее минимизацию, поэтому стандартный метод решения основан на следующем преобразовании. Если ввести вспомогательные переменные уi,j, такие, что