Постановка и методы решения задач дискреттного программирования

Содержание.

Введение.        3

Глава 1.        5

1.1 Постановка и особенности задач дискретного программирования.        5

1.1.1 Постановка задачи дискретного программирования.        5

1.1.2. Особенности задач.        6

1.2 Обзор алгоритмов решения задач дискретной оптимизации.        7

1.2.1 Методы отсечения.        8

1.2.1.1 Первый  и второй алгоритмы Гомори.        9

1.2.2 Комбинаторные методы.        12

1.2.2.1 Метод ветвей и границ.        13

1.2.2.2 Метод динамического программирования.        18

1.2.3. Приближенные методы.        20

1.2.3.1 Метод случайного поиска.        20

1.2.3.2 Методы локальной оптимизации.        23

1.2.3.3 Эвристические алгоритмы.        28

Глава 2.        30

Применение алгоритмов дискретного программирования к решению задач.        30

3.1. Задача целочисленного линейного программирования.        30

3.2  Задача распределения средств между предприятиями.        39

3.3 Задачи теории графов.        42

Заключение.        45

Литература.        47

Введение.

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

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

Цель данной работы: провести классификацию алгоитмов дискретного программирования с подробным рассмотрением тех из них, которые наиболее часто используются для решения прикладных задач экономики и математики и проиллюстрировать работу некоторых алгоритмов на конкретных задачах.

Задачи:  

• найти и изучить литературу по данной теме;
• провести классификацию алгоритмов дискретного программирования, представленных в литературных источниках;
• провести сортировку и выбрать алгоритмы более подходящие для решения прикладных задач;
• произвести краткий теоретический обзор выбранных алгоритмов;
• сформулировать и решить задачи, с применением описанных алгоритмов.

Актуальность рассматриваемой темы: Дискретные процессы в экономике встречаются почти так же часто, как и непрерывные, что в значительной мере определяет роль дискретного программирования в экономических мсследованиях. Моделирование производства станков и машин, приборов и вычислительных устройств приводит к таким условно-экстремальным задачам, в которых переменные могут принимать лишь конечное или счётное множество значений. Существует ряд задач, которые трудно или в настоящее время невозможно решить без того, чтобы не свести их к задачам дискретного программирования и затем воспользоваться методами дискретной оптимизации.