Сложность выпуклых задач вещественного и целочисленного полиномиального программирования

СОДЕРЖАНИЕ
ВВЕДЕНИЕ
ОБОЗНАЧЕНИЯ.
МОДЕЛЬ ВЫЧИСЛЕНИЙ.
ГЛАВА I МЕТОД ЭЛЛИПСОИДОВ ДЛЯ ПРИБЛИЖЕННОГО РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПОЛИНОМИАЛЬНОГО ПРОГРАММИРОВАНИЯ С
ЗАДАННЫМИ ГРАНИЦАМ РЕШЕНИЙ В К п
I Постановка задачи и результаты .
2 Вспомогательные построения для метода эллипсоидов
геометрия .
3 Вспомогательные построения для метода эллипсоидов
позиционная арифметика
4 Описание алгоритма АВПП .
5 Доказательство сходимости
6 Оценки трудоемкости приближенного решения задач
выпуклого полиномиального программирования с
заданными границами решений .
7 0 сложности приближенного решения невыпуклых
задач полиномиального программирования с заданными границами решений
ГЛАВА 2 ПОЛИНОМИАЛЬНАЯ РАЗРЕШИМОСТЬ ЛИНЕЙНОГО И
ДРОБНОЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. Ь
8 Постановка задачи и результаты
9 Границы решений, мера несовместности, критерий
ограниченности и чувствительность минимального значения от свободных членов в задачах линейного программирования .
Алгоритм АЛН точного решения систем линейных
неравенств
II Алгоритм АЛЛ точного решения задач линейного
программирования
Полиномиальная разрешимость линейного
программирования
Полиномиальная разрешимость дробнолинейного
программирования. Алгоритм АДЛП
ГЛАВА 3 ПОЛИНОМИАЛЬНАЯ РАЗРЕШИМОСТЬ КВАДРАТИЧНОГО
ПРОГРАММИРОВАНИЯ
Постановка задачи и результаты
Границы решений, критерий ограниченности и
чувствительность минимального значения от свободных членов в задачах квадратичного
программирования
Полиномиальная разрешимость квадратичного
программирования. Алгоритм АКП.
Определение совместности систем линейных и
выпуклых квадратичных неравенств в
Задача о центре системы точек .
ГЛАВА 4 ГРАНИЦЫ РЕШЕНИИ ЗАДАЧ ВЫПУКЛОГО ПОЛИНОМИАЛЬНОГО
ПРОГРАММИРОВАНИЯ В ПЕРИОДИЧЕСКИХ МНОЖЕСТВАХ
Постановка задачи и результаты.
Рецессивные конусы выпуклых полиномов .
Обусловленность выпуклых полиномиальных форм . .
Системы с тривиальным рецессивным конусом . . .
Системы, рецессивный конус которых
подпространство .
Доказательство теоремы .1 о границах решений систем выпуклых полиномиальных неравенств в
периодических множествах .
Доказательство теоремы .2 о границах решений задач выпуклого полиномиального программирования в периодических множествах
ГЛАВА 5 АЛГОРИТМИЧЕСКАЯ СЛОЖНОСТЬ РЕШЕНИЯ СИСТЕМ
ВЫПУКЛЫХ ПОЛШОШАЛЬНЫХ И ДИОФАНТОВЫХ НЕРАВЕНСТВ I
Постановка задачи и результаты
Регуляризация систем выпуклых полиномиальных неравенств в периодических множествах и
аддитивнопоказательная запись решений
Алгоритмическая сложность решения систем
выпуклых диофантовых неравенств .
Приближенное решение систем выпуклых полиномиальных неравенств с вещественными неизвестными
ГЛАВА 6 ПОЛИНОМИАЛЬНАЯ РАЗРЕШИМОСТЬ ЗАДАЧ ВЫПУКЛОГО ДИ0ФАНТ0В0Г0 ПРОГРАММИРОВАНИЯ С ФИКСИРОВАННЫМ ЧИСЛОМ
НЕИЗВЕСТНЫХ .
Постановка задачи и результаты
Доказательство теоремы ЗОЛ
ЗАКЛЮЧЕНИЕ
ПРИЛОЖЕНИЕ I
ПРИЛОЖЕНИЕ 2
ЛИТЕРАТУРА