Лекция: Метод ветвей и границ.

Пусть (43.1)

,, (43.2)

, — целые,. (43.3)

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

Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи.

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

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

Пусть переменная в плане – дробное число. Тогда в оптимальном плане ее значение будет, по крайней мере:

1. либо меньше или равно ближайшему меньшему целому числу ;

2. либо больше или равно ближайшему большему целому числу .

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

(43.4)

,, (43.5)

(43.6)

, — целые,. (43.7)

и

(43.8)

,, (43.9)

(43.10)

, — целые,. (43.11)

Возможны четыре случая при решении этой пары задач:

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

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

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

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

Алгоритм метода ветвей и границ:

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

2. Составляет дополнительные ограничения на дробную компоненту плана.

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

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

Стандартная задача нелинейного программирования.

Определение:задачами нелинейного программирования называются задачи математического программирования, в которых нелинейны и (или) целевая функция, и (или) ограничения в виде неравенств или равенств.

Задачи нелинейного программирования можно классифицировать в соответствии с видом функции F(x), функциями ограничений и размерностью вектора (вектора решений).

В самом общем виде классификация представлена в таблице.

Таблица 44.1

Общих способов решения, аналогичных симплекс-методу линейного программирования, для нелинейного программирования не существует.
В каждом конкретном случае способ выбирается в зависимости от вида функции F(x).

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

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

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

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

Найти переменные, удовлетворяющие системе уравнений:

(44.1)

и обращающие в максимум (минимум) целевую функцию:

(44.2)

При этом в отличие от задач линейного программирования, не оговаривается форма ни целевой функции, ни неравенств. Возможны разные случаи: целевая функция нелинейна, а ограничения линейны; целевая функция линейна, а ограничения (хотя бы одно из них) — нелинейны; и целевая функция, и ограничения нелинейны.