|
Ниже описывается новый метод решения задач дискретной оптимизации, использующий сетевое представление функции [(х). Этот метод естественно назвать методом сетевого программирования (в частном случае дихотомического представления, получаем метод дихотомического программирования [25]). Рассмотрим случай, когда функция Дх) допускает сетевое представление в виде дерева. Дадим описание метода сетевого программирования для задачи (1.5.1), (1.5.2). На рис. 1.5.4 приведен пример функции трех переменных, имеющей вид Дхь х2, х3) = ф о № (Х 9 х 2), х 3] = ф0(у, х3) Значения функций ф,(хО даны в нижних половинах квадратов, соответствующих переменным Х, х2 и х3. Идея метода состоит в следующем. Сначала решается задача минимизации функции двух переменных ф1(х0 + ф2(х2) при ограничении ^(хьх2)>у, соответствующая начальной вершине сетевого представления. Обозначим г(у) решение этой задачи в зависимости от у. Далее решаем задачу минимизации функции тоже двух переменных ъ(у) + ф3(х3) при ограничении фо(у, х3) > Ь, соответствующую конечной вершине сетевого представления. Решение этой задачи определяет оптимальное решение исходной задачи. Проиллюстрируем метод на примере рис. 1.5.4. 1 шаг. Рассматриваем нижнюю матрицу и для каждого элемента этой матрицы записываем в нижней половине соответствующей клетки сумму функций ф!(Х) и ф2(х2) для соответствующих значений X] и х2. Так, например, клетке (хь х2) = (3, 2) соответствует сумма ф,(3) + ф2(2) = 20+ 10= 30. Далее будем называть эту сумму затратами на достижение соответствующего состояния. 45 |
Ниже описывается новый метод решения задач дискретной оптимизации, использующий сетевое представление функции f(x). Этот метод естественно назвать методом сетевого программирования (в частном случае дихотомического представления, получаем метод дихотомического программирования [14, 15]). Сетевое представление типа дерева Рассмотрим случай, когда функция f(x) допускает сетевое представление в виде дерева. Дадим описание метода сетевого программирования для задачи (2.1), (2.2). На рис. 2.4 приведен пример функции трех переменных, имеющей вид f(xt, х2, х3) = фо№(хь Х2), х3] = <ро(У»Х з ) Значения функций ф,(х;) даны в нижних половинах квадратов, соответствующих переменным Х, х2 и Хз. Идея метода состоит в следующем. Сначала решается задача минимизации функции двух переменных q>l(Xl) + Обозначим z(y) решение этой задачи в зависимости от у. Далее решаем задачу минимизации функции тоже двух переменных z(y) + <Рз(х3) при ограничении Фо(у, х3) 2>Ъ, соответствующую конечной вершине сетевого представления. Решение этой задачи определяет оптимальное решение исходной задачи. Проиллюстрируем метод на примере рис. 2.4. 1 шаг. Рассматриваем нижнюю матрицу и для каждого элемента этой матрицы записываем в нижней половине соответствующей клетки сумму функций * Так, например, клетке (хь х2) = (3,2) соответствует сумма Ф1(3) + ф2(2) = 2 0 + 10 = 30. Далее будем называть эту сумму затратами на достижение соответствующего состояния. 89 |