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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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