Целочисленное программирование

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

2.4.1 Задача о распределении ресурсов

Данная задача была разобрана в рамках дисциплины «методы оптимизаций».

2.4.2 Выбор транспортных  маршрутов

Пусть путешественник хочет проехать из пункта А в пункт Б, для этого ему нужно проехать ряд городов, движение транспорта организовано только между каждыми двумя городами всего маршрута. Оптимизировать план поездки с наименьшими затратами.

Исходные данные приведены на «рисунке 1.5.2.1».

Рисунок 1.5.2.1

Разделим данную схему на этапы, показанную на «рисунке 1.5.2.2».

Рисунок 1.5.2.2

Рассмотрим, начиная с конечного пункта все расстояния до пункта отправления в «таблицах 1.5.2.1, 1.5.2.2, 1.5.2.1», основывая вычисления Fi(xi) на формуле (1.5.2.1).

Таблица 1.5.2.1

x2	d(x2,x3)	Оптимальное решение
	x3=7	F2(x2)	x3*
5	6	6	7
6	4	4	7

Таблица 1.5.2.2

x1	d(x1,x2)	Оптимальное решение
	x2=5	x2=6	F1(x1)	x2*
2	4+6	-	10	5
4	7+6	3+4	7	6
3	-	6+4	10	6

 

Таблица 1.5.2.3

x0	d(x0,x1)	Оптимальное решение
	x1=2	x1=4	x1=3	F0(x0)	x1*
1	3+7	2+7	3+7	9	4

Полученное оптимальный маршрут с минимальными затратами показан на «рисунке 1.5.2.3»

Рисунок 1.5.2.3

Таким образом, маршрут будет выглядеть следующим образом 1>4>6>7.

3. Теоретические выводы

3.1 Графический  метод

Достоинством данного метода является наглядность, которая ярко показывает множество точек входящих в область допустимых решений. Данный метод, представленный в главе 1 и 2 предназначен только для решения задач с переменными количество которых, не превышает 2, так как теряется наглядность. То есть при количестве переменных равным 3, построение ограничений и анализ полученной области представляет трудоёмкий процесс, который может занять большое количество времени, чем использование другого метода без применения графической интерпретации. Так же большое значение переменных явится проблемой, в связи с которой графическая интерпретация будет затруднена.

3.2 Метод Гомори

Метод впервые был предложен в 1957-1958 годах Р. Гомори.

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

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

Таким образом, при полном анализе решения задач метод Гомори не гарантирует полное представление об оптимальных решениях изучаемых задач.

3.3 Метод ветвей  и границ

Метод ветвей и границ был предложен Лендом и Дойгом в 1960 году.

Данный метод даёт более полное представление о получаемых результатах чем метод Гомори, но затрачивает большое количество времени, которое в современности играет большую роль.

Данный метод предлагает рассмотрение всех решений, в результате наложения ограничений.

Так же при рассмотрении задач данным методом с большим количеством переменных нахождение оптимального решения может быть затруднено. Так как объём работ будет не обосновано велик.

Так как данный метод имеет основу в виде симплекс-метода, как и в методе Гомори, решение может быть затруднено в связи с обладанием не полной информации, либо не умением её применения при решении задач, а именно при нахождении минимума, или первоначальном равенстве ограничений, которые могут быть решены методом искусственного базиса.

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

3.4.1 Задача о назначениях

Задачи данного типа были разобраны в рамках дисциплины «методы оптимизаций».

3.4.2 Задача коммивояжёра

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

В рамках используемых методов рассмотрении полученных подциклов направлено по меньшему циклу, что сокращает количество ветвлений. «Причина этого в том, что введение в задачу нового ограничения автоматически влияет на значения всех переменных этой задачи, что создаёт «благоприятные» условия для формирования полного цикла»[5].

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

Таким образом, в зависимости от прерогатив путника, могут быть выбраны альтернативные маршруты.

3.4.3 Задача о  рюкзаке

Данная задача не была рассмотрена в практической части, так как используемый алгоритм нахождения был использован при нахождении оптимального распределения ресурса в курсе дисциплины «методы оптимизаций».

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

Задачи данного типа относятся к детерминированным моделям с рекуррентным алгоритмом прямой и обратной прогонки.

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

Заключение

В данной курсовой работе было продемонстрировано широкое многообразие задач целочисленного программирования и методов их решения.

На основе полученных решений задач целочисленного программирования можно сделать следующие выводы:

- специфика задачи влечёт за  собой выбор метода решения  данной задачи;

- полученное оптимальное решение  может быть не единственным;

- методы решения задач зависят  от сложности и проблематики  данной задачи.

Существенные проблемы данного раздела математического программирования:

- сложность формализации;

- широкое применение методов  других разделов математического  программирования.

Данный раздел математического программирования имеет не длинную историю, но широкое применение, развитие которого, происходит и сейчас.

Основными методами целочисленного программирования являются:

- метод Гомори;

- метод ветвей и границ, который  взаимно дополняют друг друга.

Список используемой литературы

1. Кофман А., Анри-Лабордер А. Методы и модели исследования операций. Целочисленное программирование: Учебник/ Под ред. Н. П. Бусленко. - М.: Мир, 1977. - 424 с.

2. Кремер Н.Ш., Путко Б.А. и др. Исследование операций в экономике: Учебное пособие для вузов/ Под ред. Н.Ш. Кремер. - М.: Юнити, 2003. - 407 с.

3. Красс М.С., Чупрынов Б.П. Основы математики и её приложение в экономическом образовании: Учебник/ - М.: Дело, 2000 - 688 с.

4. Глухов В.В., Медников М.Д., Коробко  С.Б. Математические методы и модели  для менеджмента: Учебное пособие/ 3-е изд., стер. - СПб.: Лань, 2007 - 528 с.

5. Таха, Хемди А. Введение в исследование операций: Учебник/ Пер. с англ. - 7-е издание - М.: Вильямс, 2005. - 912 с.

6. Косоруков О.А., Мищенко А.В. Исследование  операций: Учебник/ Под ред. Н.П. Тихомирова. - М.: Экзамен, 2003. - 448 с.