Дискретное программирование

Министерство образования Российской Федерации

Уфимский государственный авиационный технический университет

Кафедра автоматизированных технологических систем

Курсовая работа

По дисциплине: Программирование систем

На тему: Дискретное программирование

Уфа 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 < 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

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать