14. Метод ветвей и границ: общая схема.

Общая схема ветвей и границ состоит в следующем: используя метод разбиения множества на подмножества, мы последовательно разбиваем исходное множество на все более мелкие подмножества. Параллельно с разбиением производим оценку получаемых множеств. При этом очередное разбиение производится для множества, которое обладает наилучшей оценкой. Описанный процесс продолжается до тех пор, пока не будет получен 1-ый рекорд. С момента появления рекорда схема метода изменяется. Информация о рекорде используется для удаления из дерева неперспективных вершин. Все вершины, оценка которых хуже рекорда, т.е. меньше чем рекорд на max, и больше чем рекорд на min вычеркивается из дерева. В ходе решения задачи рекорд может изменяться.

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

x – множество целочисленных планов.

φ(х) – оценку получим, решив задачу без требования целочисленности.

x^* – оптимальное решение нецелочисленной задачи.

φ(х) = c^Tx^*

Возможны 2 случая:

1) x* – целочисленное решение

2) х* – есть i₀ –компонента, не являющаяся целочисленной, т.е. х*_i0 – нецелочисленное.

х¹={x €X: х_i0≤ [х*_i0]}

х²={x €X: х_i0≥ [х*_i0+1]}

Для определенности φ(х¹)> φ(х²)

В процессе оценки множества х¹(х²) может оказаться х^1*окажется целочисленным в этом случае вершина соответствующая множеству х¹ объявляется рекордом и дальше не разбивается на подмножества, а используется для отсечения неперспективных вершин.

Допустим x^1* – целое значение, обведем 2-ым кружком.

1. φ(х²)< φ(х¹) – удаляем вершину из дерева.

2. φ(х²)> φ(х¹) – с вершиной x² работаем дальше – разбиваем.

Задача считается решенной, если не осталось не вычеркнутых вершин.

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

Отсечением будем называть дополнительное ограничение, которое вводится в задачу и отсекает от множества планов (нецелочисленных) его часть.

Правильным отсечение Гомори будем называть такое отсечение, которое удовлетворяет трем требованиям:

1) Отсечение является линейным.

2) Отсечение отсекает оптимальное нецелочисленное оптимальное решение ЗЛП.

3) Отсечение не отсекает ни одного целочисленного плана исходной задачи.

Рассмотрим произвольное вещественное число α. Его целой частью, которую будем отмечать [α], будем называть максимально целое число не превосходящее заданному. Величину {α}= α-[α] будем называть дробной частью.

Представим ЗЛП:

l₀+l_n^Tx_n→ max

x_b=β-Rx_n

x_b≥0, x_n≥0

предположим, что ЗЛП (нецелочисленная) решена.

x* – ее оптимальное нецелочисленное решение.

Гомори доказал, что правильное отсечение строится по след. формуле:

x_io^*= β_io { βio }>0

x_н^*=0 { β_io }≤0

17. Динамическое программирование: предмет исследования, математическая модель многошагового процесса.

1) Набор параметров, которые характеризуют положение системы

x₁(t), …, x_n(t)

2) Управляющие воздействия

u₁(t), …, u_m(t)

3) Связь между состояниями и управляющими воздействиями

x(t+1)=f( x(t), u(t) )

4) Известное начальное состояние системы

x(0)= x₀

5) Критерий качества, с помощью которого оценивается качество управляющего воздействия