Метод ветвей и границ (контрольная)

| Категория реферата: Рефераты по экономико-математическому моделированию
| Теги реферата: бесплатные рефераты на тему, шпоры по педагогике
| Добавил(а) на сайт: Denisov.

Итак, процесс нахождения решения задачи целочисленного программирования (32)-(35) методом ветвей и границ включает следующие этапы:

10 Находят решение задачи линейного программирования (32)-(34)

20 Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане задачи (32)-(34) является дробным числом.

30 Находят решения задач (I) и (II), которые получаются из задачи (32)-
(34) в результате присоединения дополнительных ограничений.

40 В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (I) и (II), и находят их решение. Интеграционный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (32)-(34) и такая, что значение в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.

Описанный выше метод ветвей и границ имеет более простую логическую схему расчетов, чем рассмотренный выше метод Гомори. Поэтому в большинстве случаев для нахождения решения конкретных задач целочисленного программирования с использованием ЭВМ применяется именно этот метод. В частности в рассмотренном выше ППП «Линейное программирование в АСУ» для отыскания целочисленного решения конкретных задач используется метод ветвления и границ.

2.51 Методом ветвей и границ найти решение задачи, состоящей в определении максимального значения функции

[pic] при условиях[pic]

[pic] xj – целые (j=[pic])

Р е ш е н и е. Находим решение сформулированной задачи симплексным методом без учета условия целочисленности переменных. В результате устанавливаем, что такая задача имеет оптимальный план Х0= (18/5, 3/5, 0,
0, 24/5). При этом плане F= (X0)=39/5.

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

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

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

(I)[pic] (II)[pic]

Задача (I) имеет оптимальный план [pic] на котором значение целевой функции [pic]. Задача (II) неразрешима.

Исследуем задачу (I). Так как среди компонент оптимального плана этой задачи есть дробные числа, то для одной из переменных, например x2, вводим дополнительные ограничения:

[pic]

Рассмотрим теперь следующие две задачи:

[pic](III) [pic]

(IV) [pic]

Задача (IV) неразрешима, а задача (III) имеет оптимальный план [pic](3,
1, 3, 3, 3), на котором значение целевой функции задачи [pic]

Таким образом исходная задача целочисленного программирования имеет оптимальный план Х*= (3, 1, 2, 3, 3). При этом плане целевая функция принимает максимальное значение [pic].

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

Дадим геометрическую интерпретацию решения задачи (50)-(53). На рис.
2.6 показана область допустимых решений задачи (50)-(52).

Из него видно, что данная задача имеет оптимальный план[pic](18/5, 3/5,
0, 0, 24/5). В то же время [pic] не является планом задачи (50)-(53), поскольку три переменные имеют дробные значения. Возьмем переменную х1 и рассмотрим задачи (I) и (II).