Построение приближенных методов для некоторых классов задач нелинейной оптимизации с применением теории двойственности

• Автор: Гвоздев, Сергей Ефимович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Новосибирск
• Количество страниц: 136 c. : ил

Глава I. ИСХОДНАЯ ОЦЕНОЧНАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ
МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
§ I.I. Определения, основные обозначения,
геометрическая интерпретация
§ 1.2. Некоторые свойства функции f{U)
§ 1.3. Общая схема метода решения оценочной
задачи в случае конечности множества
§ 1.4. Заключение
Глава 2. ПОСТРОЕНИЕ ПРИБЛИЖЕННЫХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧИ
С ПРАВИЛЬНЫМ ОГРАНИЧЕНИЕМ
§ 2.1. Предварительные замечания
§ 2.2. Метод решения двойственной задачи
§ 2.3. Получение приближенных решений исходной
задачи
§ 2.4. Метод решения двойственной задачи <&т
§ 2.5. Заключение
Глава 3. СПЕЦИАЛЬНЫЕ ЗАДАЧИ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ
§ 3.1. Предварительные замечания
§ 3.2. Простейшая задача распределения
ресурсов
§ 3.3. Задача выпуклого целочисленного программирования с одним ограничением
§ 3.4. Некоторые модели задачи о ранце
§ 3.5. Двумерная задача о ранце
§ 3.6. Задача минимизации числа транспортных
средств

§ 3.7. Задача нахождения связывающего дерева максимального веса с дополнительным
ограничением
§ 3.8. Минимаксная задача математического
программирования
§ 3.9. Задача дробного программирования
СПИСОК ОСНОВНОЙ ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЕ

Исследования в области построения алгоритмов решения экстремальных задач математического программирования в настоящее время переживают пору интенсивного роста, это обусловлено тесной связью задач математического программирования с реальными физическими задачами, задачами экономики и многими другими областями человеческой деятельности.
Трудности, связанные с разработкой численных методов решения задач на ЭВМ, возникают в связи со сложностью и громоздкостью математических моделей реальных ситуаций. Преодоление этих трудностей является важной актуальной задачей математического программирования, как с точки зрения требований, предъявляемых к вычислительным методам со стороны практики, так и с точки зрения методов математической оптимизации. Модели прикладных задач, как правило, характеризуются большой размерностью и относительно малой точностью исходных данных. При этом задача с конкретными числовыми данными есть лишь представитель из совокупности задач математического программирования, описывающих одну и ту же реальную ситуацию. В связи с этим основной задачей в практических расчетах следует считать не нахождение оптимального решения конкретной задачи, а скорее нахождение серии "близких к оптимуму" решений, выбором из которой можно ограничиться при решении исходной прикладной задачи. Тем более, что сама исследуемая задача обычно является лишь частью более сложной, и зачастую решаемой лишь эвристически, задачи. При такой постановке задачи принципиальное значение приобретает задача на-

из утверждений главы I.
Напомним, что через (я(и), у (U)) обозначается элемент множества Q Ш) . Очевидно, что при фиксированном а мощность множества Я {и) , вообще говоря, не равна / . Пусть llzR (т = 1) докажем некоторые свойства отображений z(u) и уш).
ТЕОРЕМА 2,1. Если и"у и^ 0[и," < и!^ О) ? то 2[u')^Zluf). Действительно, если ип>иг2 0 , то, в силу свойства 6 (§ 1.2), у {и’) > у [и"), поэтому соотношение (1.9) позволяет записать z (и') > Z[u"), Аналогично, если и"< и'^О, то Z(u')^
ъ % [и"), я
ТЕОРША 2.2. Если и>и', то Доказательство следует из свойства 6. ■
СЛЕДСТВИЕ. Пусть (2(а І/Ш')) € Я (и!) и [Z(u’ уЩ*)) Є Я(итогда, если и' и'^(Я 0 , то {Z[u!')-Z[u!))[y[Li")-
- У0.
ЗАМЕЧАНИЕ. Сформулированные свойства для отображений
Z£(U) и Яt(U)) при 8 >0 не верны.
Докажем аналог теоремы 1.3 для задачи Р при m=mf= /. Пусть и' и и" - неотрицательные вещественные числа и элементы (Ze ки!)% уъ{и'))^Я&{.и {z£[u' y^Ll")) еЯ& iu") удовлетворяют условию у£ (и")£ ^ (и'). Обозначим [5 =- max { ф [Щ-ЩиРу-йі гДе й - некоторое неотрицательное вещественное число; f= max [vI W^/l}
(V,W)e£>
Справедлива следующая