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

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

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

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

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

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

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

Уфа 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}. Отдельно следует добавить, что если даже оптимальный план непрерывной задачи, округленный до целых значений компонент, окажется допустимым, то целевая функция может вести себя так, что ее значение будет на нем существенно "хуже", чем на оптимальном плане целочисленной задачи.

Перечисленные проблемы предопределили необходимость разработки специальных методов решения дискретных и целочисленных задач. Но прежде чем говорить собственно о методах решения, более подробно остановимся на классификации задач дискретного программирования. В литературе, как правило, выделяют следующие классы дискретных оптимизационных задач:

Ø задачи с неделимостями;

--> ЧИТАТЬ ПОЛНОСТЬЮ <--