Задачи дробно-линейного программирования

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

В общем случае целевая функция имеет вид (28)

Т акая функция легко преобразуется в линейную, если ее знаменатель при всех допустимых значениях переменных строго положителен. Для этого введем новую переменную r (29). Очевидно, что при оговоренном условии она может быть только больше нуля. Тогда функция (28) принимает вид Произведя замену произведения переменных (30) окончательно имеем (31) Получили линейную функцию от n неотрицательных переменных y_j и одной положительной переменной r. Эта функция должна рассматриваться вместе с условием, следующим из (29): или после замены (30) (32) Следует ограничения задачи записать в новых переменных. Для этого умножим обе части каждого ограничения на r и, произведя замену, получаем (33) В результате преобразований имеем задачу ЛП с критерием (31), ограничениями (32), (33) и переменными r>0, y_j 0, j. Воспользовавшись (30) вернемся к исходным переменным. Возможность перехода к линейной задаче геометрически обусловлена тем, что линии уровня дробно-линейной функции описываются линейным уравнением. , из (28) следует или . ( 34) При изменением возникает поворот вокруг мн-ва вращения. Мн-во вращения – это множество точек, образованное пересечением нулевых линий уровня числителя и знаменателя: n=2 – точка, n=3 - прямая

15. Классификация и характеристика методов «спуска».

Так называются численные итерационные методы оптимизации, ориентированные на поиск минимума. При выборе метода следует учитывать свойства целевой функции: унимодальность или многоэкстремальнсть, дифференцируемость, выпуклость-вогнутость или их отсутствие и т. д. Кроме того, функции могут обладать особенностями, такими как седловые точки и овражность. “Овраг” (при максимизации “гребень”) проявляются в том, что вдоль него функция изменяется намного слабее, чем в поперечном направлении.

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

По информации, используемой для определения направления поиска выделяют методы:

- нулевого порядка или прямые, вычисляется только значение функции;

- первого порядка (градиентные), использующие первые производные;

- второго порядка, требующие вычисления также вторых производных;

- случайного поиска, механизм случайного выбора направления;

- генетические, элементы детерминизма и случайности выбора;

- комбинированные.

Все приводимые ниже методы предназначены для минимизации унимодальных функций.

Методы одномерной минимизации. Метод деления шага пополам

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