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

КУРСОВАЯ РАБОТА

на тему: «Целочисленное программирование»

Содержание

Введение

1. Теоретическая база. Методы решения

1.1 Графический метод решения  задач

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

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

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

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

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

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

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

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

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

2. Решения задач целочисленного  программирования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Список литературы

Приложение

Введение

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

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

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

Основными задачами данной курсовой работы является:

1. Анализ и получение оптимальных  решений;

2. Выявление проблем, связанных  с получением оптимального решения;

3. Проработка всех направлений  целочисленного программирования.

Используемые методы для анализа:

- графический метод;

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

- метод ветвей и границ;

- методы динамического программирования;

- и другие

1. Теоретическая база. Методы решения

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

Разделим задачи целочисленного программирования на классы:

- Задачи, которые сводятся к  задачам целочисленного программирования, в которых переменные представляют  собой физически не делимые  единицы. целочисленный программирование гомори

- Другим важным классом таких  задач являются экстремальные  комбинаторные задачи, переменные  которых носят логический характер (х=0 или х=1). Такие переменные называются  булевыми. К таким задачам относятся, например, задача выбора некоторого  подмножества, обладающего какими-либо  экстремальными свойствами.

- Задачи, не требующие явного  условия целочисленности, но сводящиеся к задачам целочисленного или частично целочисленного программирования.

Решение задачи целочисленного программирования сводится к следующим этапам:

1. Построение математической модели;

2. Решение математической модели  выбранным методом;

3. Анализ полученных данных и  принятие решения.

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

- Формализация целевой функции  приведена в формуле (1.1)

- Наложение ограничений показано  в формулах (1.2).

В зависимости от условий конкретной задачи могут быть введены дополнительные ограничения на отдельные переменные, которые могут быть выражены, например, формулой (1.3)

где dj, Dj - свободные коэффициенты.

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

- графический метод решения  задач;

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

- метод ветвей и границ;

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

Рассмотрим методы решения задач целочисленного программирования:

1.1 Графический метод решения задач

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

Целевая функция и ограничения приведены в формулах 1.1.1 и 1.1.2.

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

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

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

Практически любой класс линейного программирования может быть решён практически. Однако данный метод решения не может быть реализован или реализован с большими временными затратами при количестве переменных равным 3 и более. Поэтому данный метод не будет рассмотрен в практической части.

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

Данный метод основан на симплексном методе.

Исходные данные приведены в формулах (1.2.1) и (1.2.2).

На первом этапе данная задача решается симплекс-методом, если полученное решение не целочисленное, то вводим дополнительное ограничение, которые должны быть:

- линейным;

- отсекать найденный оптимальный  не целочисленный план;

- не должно отсекать ни одного  целочисленного плана.

Дополнительное ограничение обладающие этими свойствами называются правильным отсечением[2].

Ограничение накладывается на нецелочисленную переменную или на ту переменную, которая имеет большее дробное значение. Ограничение накладывается на не целочисленную переменную через не основные переменные. Ограничение составляется используя следующее правило: дробная часть свободного члена берётся с тем же знаком, который он имеет и в уравнении, а дробные части неосновных переменных - с противоположным знаком и выделяется положительная дробь. Например, {a}=a, {-a}={-A+a*}, где А - целая часть отрицательное число, а*-положительная дробь.

Получаем новое ограничение, вводим новую основную переменную, приведённое в формуле (1.2.3).

где xn+1 - нововведённая переменная,

xj - переменные не входящие в базис.

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

Полученное базисное решение всегда не допустимое, соответствующее правильному отсечению.

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

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

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

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

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

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

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

Исходные данные полностью соответствуют данным метода Гомори формулы (1.2.1) и (1.2.2).

На первом этапе данная задача решается симплекс-методом, если полученное решение не целочисленное, то составляются дополнительные ограничения предложенные в формулах (1.3.1).

где [xj*] - целая часть нецелочисленного значения переменной xj* в оптимальном решении без учёта целочисленности.

Затем решаются ещё две задачи линейного программирования, в каждую из которых вошли все исходные ограничения и одно из дополнительных (1.3.1).

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

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

- На одной из ветвей недопустимое  решение;

- На одной из ветвей целочисленное  решение. Тогда значение целевой  функции сравнивается с граничное (верхним при max, нижним при min); если полученное значение хуже, оно отбрасывается, если лучше, то принимается за граничное;

- На одной из ветвей нецелочисленное  решение, однако при этом значение целевой функции хуже граничного. Тогда дальнейшее рассмотрение также прекращается[4].

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

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

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

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

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

- задача о назначениях;

- задача коммивояжёра;

- задача о ранце.

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

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

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

Спецификой данной задачи является одинаковое количество представляемого ресурса и источников его использования.

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

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

Каждый сотрудник имеет определённые требование выраженные по шкале от 1 до 10 обозначим их за Cij в связи, с которыми заполняется матрица n?n относительно рабочего места требований сотрудника.

В данной задаче используются булева переменная для назначения i - работника на j - место показанная в формуле (1.4.1.1)

где i=1,2,..n - множество работников

j =1,2,..n - множество рабочих мест.

Таким образом, составляется матрица n?n и решается выбранным методом.

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

Задачи такого типа известны под общим названием задача коммивояжёра, в «классической» формулировке которой коммивояжёр пытается определить кратчайший маршрут для одноразового посещения n городов. По существу, это задача является задачей о назначениях с дополнительными ограничениями, которые гарантируют исключение из оптимального решения неполных замкнутых маршрутов (в задаче коммивояжёра замкнутый маршрут, проходящий через каждый пункт только один раз, называется циклом цикл, проходящий через все пункты, называется полным, в противном случае - частичным или подциклом).

В задаче коммивояжёра с n городами можно определить такие переменный приведённые в формуле (1.4.2.1).

Имея значения Cij - расстояние от города i до города j (считается, что Cij=? при i=j), задачу коммивояжёра можно формализовать следующим образом, показанную в формуле (1.4.2.2)

При ограничениях, показанных в формулах (1.4.2.3)

Решения должно быть полным циклом[5].

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

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

Применение метода ветвей и границ для решения задачи коммивояжера.

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

1. На первом этапе решается  задача о назначениях. Полученное  решение принимается за нижнюю  границу нахождения решения задачи  коммивояжёра. За верхнюю границу  можно принять сумму элементов  С12+С23+С34+..+Сn1.

Если на первом этапе получен цикл, то его принимают за оптимальное решение задачи коммивояжёра.

2. Иначе чтобы исключить частные  циклы в полученном решении  принудительно приравниваются xij, задающие этот цикл, к бесконечности (например, если цикл состоит из 2 переменных, то приравнивается лишь одна переменная к бесконечности).

Каждое из подобных ограничений порождает отдельную ветвь дерева подзадач (и, конечно, отдельную подзадачу). Важно заметить, что нет необходимости разбивать все имеющиеся частные циклы - достаточно исключить только один частный цикл. Причина этого в том, что введение в задачу нового ограничения автоматически влияет на значения всех переменных этой задачи, что создаёт «благоприятные» условия для формирования полного цикла. На основании этого аргумента обычно разбивают один частный цикл, наименьший по количеству составляющих его переменных, поскольку это приводит к меньшему количеству новых ветвей в дереве подзадач.